|
|
| (10 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| − | == Citation ==
| |
| | | | |
| − | Duame, H., Langford, J., and Marcu, D. 2006. SEARN in Practice. Unpublished Manuscript
| |
| − |
| |
| − | == Online version ==
| |
| − |
| |
| − | [http://hal3.name/docs/daume06searn-practice.pdf SEARN in Practice]
| |
| − |
| |
| − | == Summary ==
| |
| − |
| |
| − | This unpublished [[Category::Paper|manuscript]] describes how [[UsesMethod::SEARN]] can be used for three Natural Language Processing related tasks: [[AddressesProblem::Sequence Labeling]], [[AddressesProblem::Parsing]], and [[AddressesProblem::Machine Translation]]
| |
| − |
| |
| − | The key points of the paper are:
| |
| − | * Authors state that [[UsesMethod::SEARN]] is efficient, widely applicable, theoretically justified, and simple.
| |
| − | * [[UsesMethod::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: [[AddressesProblem::Sequence Labeling]], [[AddressesProblem::Parsing]], and [[AddressesProblem::Machine Translation]]
| |
| − | * Efficacy of [[UsesMethod::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 [[AddressesProblem::POS tagging]] and [[AddressesProblem::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:
| |
| − | [[File:op-tagging.png]]
| |
| − |
| |
| − |
| |
| − | ''NP Chunking''
| |
| − | * Chunking is a joint segmentation and labeling problem.
| |
| − | * ''Loss function'': F1 measure
| |
| − | * Optimal Policy:
| |
| − | [[File:op-chunking.png]]
| |
| − |
| |
| − | '''Parsing'''
| |
| − | * Looked at dependency parsing with a shift-reduce framework.
| |
| − | * ''Loss funtion'': Hamming loss over dependencies.
| |
| − | * ''Decisions'': shift/reduce
| |
| − | * ''Optimal Policy'':
| |
| − | [[File:op-parsing.png]]
| |
| − |
| |
| − | '''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 [[UsesMethod::SEARN]] algorithm - [[RelatedPaper::Daume_et_al,_ML_2009]].
| |
