# Daume et al, 2006

From Cohen Courses

Revision as of 18:21, 30 September 2010 by PastStudents (talk | contribs)

## Citation

Duame, H., Langford, J., and Marcu, D. 2006. SEARN in Practice. Unpublished Manuscript

## Online version

## Summary

This unpublished manuscript describes how SEARN can be used for three Natural Language Processing related tasks: Sequence Labeling, Parsing, and Machine Translation

The key points of the paper are:

- Authors state that SEARN is efficient, widely applicable, theoretically justified, and simple.
- SEARN looks at problems a search problems, and learns classifiers that walk through the search space in a good way.
- Authors looked at 3 sample problems: Sequence Labeling, Parsing, and Machine Translation
- Efficacy of SEARN hinges on ability to compute an optimal/near-optimal policy. When an optimal policy is not available, authors suggest performing explicit search as an approximation. For segmentaiton and parsing, optimal policy is closed form; for summarization and machine translation, the optimal policy is not available.

## Example SEARN Usage

**Sequence Labeling**

- Discussed SEARN's application to POS tagging and NP chunking

*Tagging*

- Task is to produce a label sequence from an input sequence.
- Search framed as left-to-right greedy search.
*Loss function*: Hamming loss- Optimal Policy:

*NP Chunking*

- Chunking is a joint segmentation and labeling problem.
*Loss function*: F1 measure- Optimal Policy:

**Parsing**

- Looked at dependency parsing with a shift-reduce framework.
*Loss funtion*: Hamming loss over dependencies.*Decisions*: shift/reduce*Optimal Policy*:

**Machine Translation**

- Framed task as a left-to-right translation problem.
- Search space over prefixes of translations.
- Actions are adding a word (or phrase to end of existing translation.
*Loss function*: 1 - BLEU or 1 - NIST*Optimal policy*: given set of reference translations R, English translation prefix e_1, ... e_i-1, what word (or phrase) should be produced next / are we finished.

## Related papers

**Search-based Structured Prediction**: This is the journal version of the paper that introduces the SEARN algorithm - Daume_et_al,_ML_2009.