HC-Search: Learning Heuristics and Cost Functions for Structured Prediction

Janardhan Rao Doppa, Alan Fern, Prasad Tadepalli

Introduction

Structured prediction is a cornerstone of machine learning, involving the prediction of complex outputs such as part-of-speech tag sequences or segmented images from structured inputs. Traditionally, this is framed as an "Argmin" problem: learning a cost function and finding the output that minimizes it. However, for most real-world applications, this optimization is NP-hard, forcing researchers to rely on heuristic search.

The HC-Search framework addresses a fundamental limitation in existing search-based methods: the reliance on a single function to both guide the search and rank the final candidates. By decoupling these roles into a dedicated heuristic ($H$) and a separate cost function ($C$), HC-Search achieves superior performance and provides a diagnostic tool for understanding prediction errors.

The HC-Search Framework

The core innovation of HC-Search is the separation of the prediction process into two distinct stages:

  1. Candidate Generation (The Heuristic, $H$): This function guides a search strategy (e.g., greedy or beam search) to identify a set of high-quality candidate outputs. It is trained via imitation learning to mimic the behavior of the true loss function, ensuring the search quickly navigates toward low-loss regions of the output space.
  2. Candidate Selection (The Cost Function, $C$): Once a pool of candidates is generated, the cost function ranks them to select the final prediction. Because $C$ only operates on a small subset of the total output space, it can incorporate complex, higher-order features that would be computationally prohibitive in traditional models.

Error Decomposition: Diagnosing Model Failures

A significant contribution of this work is the formal decomposition of total expected loss ($\epsilon$) into two components:

  • Generation Loss ($\epsilon_H$): The error incurred when the heuristic fails to include a high-quality candidate in the search pool.
  • Selection Loss ($\epsilon_{C|H}$): The error incurred when the cost function fails to select the best available candidate from the pool generated by $H$.
Decomposition of prediction error into generation loss ($\epsilon_H$) and selection loss ($\epsilon_{C|H}$).

As shown in the experimental analysis (Figure 3), selection loss is typically the primary bottleneck. This insight suggests that improving the ranking capability of the cost function often yields higher performance gains than simply increasing search depth.

Experimental Results

The HC-Search framework was evaluated against several state-of-the-art methods, including Conditional Random Fields (CRFs), SVM-Struct, and Searn, across diverse benchmarks such as handwriting recognition, phoneme labeling, and scene labeling.

Comparison of HC-Search against baseline algorithms across multiple benchmarks.

HC-Search consistently outperformed competing methods. In the Scene Labeling task, it achieved a 19.71% error rate, a substantial improvement over the 27.05% achieved by C-Search (a single-function search method) and 37.69% by Searn. Similarly, on the Large Handwriting dataset, HC-Search reduced error to 3.78%, compared to 13.11% for CRFs.

Key Insights and Future Directions

The success of HC-Search stems from its ability to leverage "higher-order features for free." Since the cost function only evaluates a small number of candidates, it can utilize complex dependencies (e.g., label triples) without sacrificing inference speed.

Future work may explore the use of non-linear functions, such as regression trees, for the cost function to further minimize selection loss. Additionally, investigating the optimal balance between search effort (heuristic) and ranking complexity (cost function) remains a promising area for research.

Summary updated

Abstract

Structured prediction is the problem of learning a function from structured inputs to structured outputs. 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 uses a separate learned cost function C to select a final prediction among those outputs. We can decompose the regret of the overall approach 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 regret in a greedy stagewise 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. Experiments on several benchmark domains show that our approach significantly outperforms the state-of-the-art methods.
BibTeX
@inproceedings{doppa2013hc,
  author = {Janardhan Rao Doppa and Alan Fern and Prasad Tadepalli},
  title = {{HC-Search: Learning Heuristics and Cost Functions for Structured Prediction}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8664},
}
Figure