Difference between revisions of "SEARN"
From Cohen Courses
Jump to navigationJump to search| Line 1: | Line 1: | ||
Being edited by [[User:Fkeith|Francis Keith]] | Being edited by [[User:Fkeith|Francis Keith]] | ||
| + | |||
| + | == Citation == | ||
| + | |||
| + | A detailed description and introduction to SEARN is available [[Daume et al, ML 2009|here]]. | ||
== Motivation == | == Motivation == | ||
| − | SEARN is a | + | |
| + | 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. | ||
| + | |||
| + | == Input == | ||
| + | |||
| + | Running the SEARN meta-algorithm requires a few different inputs. | ||
| + | * <math>L(y,f(\hat{y}))</math> - A loss function, which must be computable for any sequence of predictions | ||
| + | * <math>A</math> - A cost-sensitive learning algorithm. This algorithm will produce learned classifiers, which SEARN refers to as ''policies''. | ||
| + | * <math>\pi</math> - The ''optimal policy''. This should produce low loss when applied to the training data | ||
| + | |||
| + | == Algorithm == | ||
| + | |||
| + | * Initialize policy <math>h \leftarrow \pi</math> | ||
| + | * While <math>h</math> is too close to <math>\pi</math>... | ||
| + | ** Initialize <math>S</math> as the space of cost-sensitive examples. | ||
| + | ** For every <math>(x,y) \in S^{SP}</math>, where <math>S^{SP}</math> is the sample space... | ||
| + | *** Compute a prediction using the current policy: <math>\hat{y} \sim x,h</math> | ||
| + | *** | ||
| + | |||
| + | To be completed... | ||
| + | |||
| + | == Output == | ||
| + | |||
| + | |||
== Relevant Papers == | == Relevant Papers == | ||
Revision as of 13:13, 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.
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
- Initialize policy
- While is too close to ...
- Initialize as the space of cost-sensitive examples.
- For every , where is the sample space...
- Compute a prediction using the current policy:
To be completed...
