SEARN

Being edited by Francis Keith

Citation

A detailed description and introduction to SEARN is available here.

Motivation

SEARN is a meta-algorithm for doing structured prediction. The basic premise is to combine learning and searching to transform a complex structured prediction problem into a simple classification problem. The learning algorithm is designed to begin with a classifier that uses the training data directly, and use that classifier to produce a fully-learned classifier. In this sense, it moves away from the classifier created by the training data.

Input

Running the SEARN meta-algorithm requires a few different inputs.

• $L(y,f({\hat {y}}))$ - A loss function, which must be computable for any sequence of predictions
• $A$ - A cost-sensitive learning algorithm. This algorithm will produce learned classifiers, which SEARN refers to as policies.
• $\pi$ - The optimal policy. This should produce low loss when applied to the training data

Algorithm

The algorithm is defined in Daume et al, ML 2009

First, begin with the current policy being the optimal policy. The goal of the algorithm is to actually move away from the optimal policy, in an effort to produce a more generalized classifier. This is because the optimal policy is generally produced by searching the training data, or sometimes is provided by an expert system.

The outermost loop requires an unclear amount of iterations. Since each loop produces an interpolated version of a learned classifier and the current priority, eventually the interpolation weights for $\pi$ will allow the claim of