Difference between revisions of "SEARN"
Line 7: | Line 7: | ||
== Motivation == | == Motivation == | ||
− | SEARN is a [[Category::Method|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. | + | SEARN is a [[Category::Method|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 == | == Input == | ||
Line 18: | Line 18: | ||
== Algorithm == | == Algorithm == | ||
− | + | The algorithm is defined in [[Daume et al, ML 2009]] | |
− | + | [[File:searn-algorithm.png]] | |
− | |||
− | |||
− | |||
− | |||
− | + | 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 <math>\pi</math> will allow the claim of | ||
== Output == | == Output == |
Revision as of 18:14, 29 September 2011
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.
- - A loss function, which must be computable for any sequence of predictions
- - A cost-sensitive learning algorithm. This algorithm will produce learned classifiers, which SEARN refers to as policies.
- - 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 will allow the claim of