Randomized Greedy Search for Structured Prediction:
Amortized Inference and Learning
Abstract
In a structured prediction problem, we need to learn
a predictor that can produce a structured output
given a structured input (e.g., part-of-speech tagging). The key learning and inference challenge is
due to the exponential size of the structured output
space. This paper makes four contributions towards
the goal of a computationally-efficient inference
and training approach for structured prediction that
allows to employ complex models and to optimize
for non-decomposable loss functions. First, we de-
fine a simple class of randomized greedy search
(RGS) based inference procedures that leverage
classification algorithms for simple outputs. Second, we develop a RGS specific learning approach
for amortized inference that can quickly produce
high-quality outputs for a given set of structured
inputs. Third, we plug our amortized RGS inference solver inside the inner loop of parameterlearning algorithms (e.g., structured SVM) to improve the speed of training. Fourth, we perform
extensive experiments on diverse structured prediction tasks. Results show that our proposed approach is competitive or better than many state-ofthe-art approaches in spite of its simplicity