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.

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

• Initialize policy $h\leftarrow \pi$
• While $h$ is too close to $\pi$...
  • Initialize $S$ as the space of cost-sensitive examples.
  • For every $(x,y)\in S^{SP}$, where $S^{SP}$ is the sample space...
    • Compute a prediction using the current policy: ${\hat {y}}\sim x,h$

To be completed...