User talk:Xxiong
From Cohen Courses
Citation
Einat Minkov, Richard C. Wang & William W. Cohen, Extracting Personal Names from Emails: Applying Named Entity Recognition to Informal Text, in HLT/EMNLP 2005
Online version
Extracting Personal Names from Emails
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.
