User talk:Xxiong

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.