Learning Adaptive Value of Information for Structured Prediction
Discriminative methods for learning structured models have enabled wide-spread use of very rich feature representations. However, the computational cost of feature extraction is prohibitive for large-scale or time-sensitive applications, often dominating the cost of inference in the models. Significant efforts have been devoted to sparsity-based model selection to decrease this cost. Such feature selection methods control computation statically and miss the opportunity to finetune feature extraction to each input at run-time. We address the key challenge of learning to control fine-grained feature extraction adaptively, exploiting nonhomogeneity of the data. We propose an architecture that uses a rich feedback loop between extraction and prediction. The run-time control policy is learned using efficient value-function approximation, which adaptively determines the value of information of features at the level of individual variables for each input. We demonstrate significant speedups over state-of-the-art methods on two challenging datasets. For articulated pose estimation in video, we achieve a more accurate state-of-the-art model that is also faster, with similar results on an OCR task.
This is an interesting paper on budgeted structured 
      prediction where the costs of computing features is substantial. A 
      naive approach to reducing computation would be to add an 
      L1-regularization term to the optimization and only compute the 
      non-zero-weight features. However, the paper is motivated by the 
      observation that for specific instances, some features may not be 
      computationally worthwhile to compute. A controller is constructed using 
      reinforcement learning techniques to sequentially choose the subset of 
      features to evaluate for prediction within the allocated budget. 
      This is an empirical papers as there is not much in the way of new 
      theory (no theorems, etc.) presented to support the combination of 
      techniques and detailed engineering employed to realize improved 
      efficiency. A discussion of the literature on budgeted learning 
      for decision trees would be worthwhile since that field of work has 
      similar motivations for discriminative prediction under hard budgets. From 
      that work, the use of information gain rather than pure predictive 
      accuracy might better inform the reward signal employed. I tend to 
      think that the ideal discriminative model for this setting would have 
      unique weights for each choice of z. This could be re-expressed by 
      expanding the feature space, but much is lost from this level of 
      generalization by employing the proposed much smaller size set of 
      features. There is not much discussion of this, unfortunately. In 
      (10), why is L2 and not L1 regularization employed? What is the 
      comparative computational time required to train each of the models? 
      I have difficulty understanding why the performance is better 
      using a subset of the features. Should I interpret this as a better form 
      of feature selection than e.g., regularization or is there some deeper 
      explanation? Which objective is the “greedy” baseline using? Would 
      a two-step “greedy” algorithm produce results more similar to the 
      reinforcement learning-based approach? For the OCR task, how does 
      the performance compare other state-of-the-art approaches for this task?