HC-Search: A Learning Framework for Search-based Structured Prediction

Janardhan Rao Doppa, Alan Fern, Prasad Tadepalli

TL;DR

This paper introduces HC-Search, a novel framework for structured prediction that separates the roles of search guidance (heuristic) and final selection (cost function). By learning these two functions independently, HC-Search achieves significantly better performance than existing methods that combine these roles, offering a more robust and interpretable approach to complex prediction tasks.

What Problem Does This Paper Address?

Structured prediction involves mapping complex inputs to complex outputs, like tagging parts of speech in a sentence or labeling regions in an image. Traditional approaches often struggle to balance the need for flexible, accurate predictors with the computational constraints of real-world applications. A common strategy is to learn a cost function that scores potential outputs, but finding the best output often requires solving an intractable "Argmin" problem. Output-space search methods try to circumvent this by using a learned cost function to guide a search through possible outputs. However, these methods use a single function for both guiding the search and scoring the final output, which can lead to suboptimal learning and performance. This paper addresses this limitation by proposing a framework that explicitly separates these two crucial roles.

Methods

The core of HC-Search is its two-component learning approach:

  • Heuristic Function (H): This function guides the search process, aiming to quickly uncover high-quality candidate outputs. It's learned using imitation learning, where the system learns to mimic the decisions made by the true loss function on training data. This is akin to learning an expert's strategy.
  • Cost Function (C): Once a set of candidate outputs is generated by the heuristic, the cost function ranks them to select the best final prediction. This function is learned using rank learning, specifically by ensuring that the true best outputs are ranked higher than others.

The training process is staged: first, the heuristic (H) is trained to generate good candidates, and then the cost function (C) is trained to pick the best among those candidates. This decomposition allows for targeted improvement of each component.

Datasets

The authors evaluated HC-Search on four structured prediction tasks:

  • Handwriting Recognition (HW): A sequence labeling task for recognizing handwritten letters.
  • NETtalk Stress: A text-to-speech mapping task assigning stress labels to letters.
  • NETtalk Phoneme: Similar to NETtalk Stress, but assigning phoneme labels.
  • Scene labeling: A 2D image labeling task where patches in an image are assigned semantic labels.

Key Insights and Ideas

  • Separation is Key: The most significant insight is that separating the search heuristic (H) from the cost function (C) leads to substantial performance gains. This is because each function can be optimized for its specific role without the compromises required when a single function tries to do both.
  • Loss Decomposition for Diagnosis: The framework naturally decomposes the overall error into "generation loss" (due to the heuristic not finding good candidates) and "selection loss" (due to the cost function not picking the best candidate). This provides valuable insights for debugging and understanding performance bottlenecks.
  • Imitation Learning for Heuristics: Using imitation learning to train the heuristic function, by mimicking the behavior of the true loss function, proves to be a highly effective strategy for guiding the search.
  • Rank Learning for Cost Functions: Framing the cost function learning as a ranking problem, where the goal is to rank correct outputs above incorrect ones, is a powerful approach for selecting the best candidate.

Key Results

  • HC-Search significantly outperforms state-of-the-art methods, including its own single-function variant (C-Search), across all tested benchmarks.
  • In the scene labeling domain, HC-Search improved the error rate from 27.05% to 19.71%.
  • The ablation study showed that using HC-Search (with separate H and C) is superior to using only the learned heuristic (HH-Search) or only the learned cost function (CC-Search) for both roles.
  • The results indicate that the selection loss is a major contributor to overall error, suggesting that improving the cost function learning is a promising avenue for further gains.
  • The framework demonstrates robustness to different time bounds and is sensitive to the loss function used during training.

Limitations and Future Work

  • Learning Complexity: The paper notes that learning the optimal (H, C) pair can be NP-Hard, suggesting that finding the absolute best functions might be computationally challenging.
  • Heuristic Improvement: While exact imitation learning works well, the authors suggest exploring more sophisticated imitation learning algorithms (like DAGGER) to further improve heuristic performance and potentially reduce generation loss.
  • Cost Function Expressiveness: The authors suggest that using more expressive cost functions (e.g., non-linear cost functions) could further improve performance, especially in reducing selection loss.
  • Search Space Optimization: The effectiveness of HC-Search is tied to the quality of the search space. Future work could focus on learning to optimize these search spaces by leveraging problem structure.
  • Efficiency: While the framework is efficient, further work on learning pruning rules could improve the efficiency of both learning and inference.

Summary updated

Abstract

Structured prediction is the problem of learning a function that maps structured inputs to structured outputs. Prototypical examples of structured prediction include part-of-speech tagging and semantic segmentation of images. Inspired by the recent successes of search-based structured prediction, we introduce a new framework for structured prediction called HC-Search. Given a structured input, the framework uses a search procedure guided by a learned heuristic H to uncover high quality candidate outputs and then employs a separate learned cost function C to select a final prediction among those outputs. The overall loss of this prediction architecture decomposes into the loss due to H not leading to high quality outputs, and the loss due to C not selecting the best among the generated outputs. Guided by this decomposition, we minimize the overall loss in a greedy stage-wise manner by first training H to quickly uncover high quality outputs via imitation learning, and then training C to correctly rank the outputs generated via H according to their true losses. Importantly, this training procedure is sensitive to the particular loss function of interest and the time-bound allowed for predictions. Experiments on several benchmark domains show that our approach significantly outperforms several state-of-the-art methods.
BibTeX
@article{doppa2014hc,
  author = {Janardhan Rao Doppa and Alan Fern and Prasad Tadepalli},
  title = {{HC-Search: A Learning Framework for Search-based Structured Prediction}},
  journal = {J. Artif. Intell. Res.},
  year = {2014},
  doi = {10.1613/jair.4212},
}
Figure