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

Janardhan Rao Doppa, Alan Fern, Prasad Tadepalli

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},
}

Loading related content...

Figure