Difference between revisions of "Lacoste-Julien et al, NAACL 2006"
| Line 3: | Line 3: | ||
== Citation == | == Citation == | ||
| − | + | Simon Lacoste-Julien, Ben Taskar, Dan Klein, and Michael I. Jordan. Word alignment via quadratic assignment. In Human Language Technology–North American Association for Computational Linguistics, New York, NY, 2006. [http://acl.ldc.upenn.edu/N/N06/N06-1015.pdf| On-line] | |
== Summary == | == Summary == | ||
| − | In this [[Category::paper]] the authors | + | In this [[Category::paper]] the authors address two major limitations of Taskar et al. (2005) paper on discriminative [[AddressesProblem::Word Alignments|word alignment]] methods: fertility and first order interactions. |
| − | + | The authors show how to extend a discriminative approach to word alignment to allow fertility modeling and to capture first-order interactions between alignments of consecutive words, enhancing the expressive power of the discriminative approach. Allowing to capture phenomena of monotonicity, local inversion and contiguos fertility trends - phenomena that are highly informative for alignment. They do so while remaining computationally efficient. | |
| − | + | Their best models achieves a relative AER reduction of 25 % over the basic matching formulation, beating intersected IBM Model 4 without the use of any compute-intensive features. The authors claim their contribution to be particularly promising for phrase based systems since they perform better with higher recall on the task. | |
| − | + | [[UsesMethod::HMM]] | |
== Brief Description of the Method == | == Brief Description of the Method == | ||
| − | + | The authors base their work in a previous discriminative approach to word alignments by Taskar et al. (2005). In this model, nodes <math>V^s</math> and <math>V^t</math> correspond to words in the source and target language, respectively, and edges <math>\varepsilon = \{ jk:j \in V^s, k\in V^t\}</math> correspond to alignments between words. The edge wights <math>s_{jk}</math> represent the degree to which word <math>j</math> in one sentence cans be translated using word <math>k</math> in the other sentence. The predicted alignments are then chosen by maximizing the sum of the edge scores, which can be formulated in linear programming as: | |
| − | |||
| − | |||
| − | |||
| − | |||
<math> | <math> | ||
| − | \ | + | \max_{0 \le z \le 1} \sum_{jk \in \varepsilon} s_{jk} z_{jk} |
</math> | </math> | ||
| + | <math> | ||
| + | s.t. \sum _{j \in V^s} z_{jk} \le 1, \forall k \in V^t; | ||
| + | </math> | ||
| − | + | <math> | |
| + | \sum _{k \in V^t} z_{jk} \le 1, \forall j \in V^s, | ||
| + | </math> | ||
| − | + | where <math>z_{jk}</math> are relaxations of the binary variables that indicate if <math>j</math> is assigned to <math>k</math>. | |
| − | + | ||
| − | + | [[File:BikelHmmGraph.png|400px]] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Experimental Results == | == Experimental Results == | ||
Revision as of 13:09, 2 November 2011
Being edited by Rui Correia
Citation
Simon Lacoste-Julien, Ben Taskar, Dan Klein, and Michael I. Jordan. Word alignment via quadratic assignment. In Human Language Technology–North American Association for Computational Linguistics, New York, NY, 2006. On-line
Summary
In this paper the authors address two major limitations of Taskar et al. (2005) paper on discriminative word alignment methods: fertility and first order interactions.
The authors show how to extend a discriminative approach to word alignment to allow fertility modeling and to capture first-order interactions between alignments of consecutive words, enhancing the expressive power of the discriminative approach. Allowing to capture phenomena of monotonicity, local inversion and contiguos fertility trends - phenomena that are highly informative for alignment. They do so while remaining computationally efficient.
Their best models achieves a relative AER reduction of 25 % over the basic matching formulation, beating intersected IBM Model 4 without the use of any compute-intensive features. The authors claim their contribution to be particularly promising for phrase based systems since they perform better with higher recall on the task.
Brief Description of the Method
The authors base their work in a previous discriminative approach to word alignments by Taskar et al. (2005). In this model, nodes and correspond to words in the source and target language, respectively, and edges correspond to alignments between words. The edge wights represent the degree to which word in one sentence cans be translated using word in the other sentence. The predicted alignments are then chosen by maximizing the sum of the edge scores, which can be formulated in linear programming as:
where are relaxations of the binary variables that indicate if is assigned to .
Experimental Results
The model was tested with MUC-6 dataset, a collection of 30 Wall Street Journal documents. The authors compared the performance of their model in comparison with the best NE-system so far, a rule-based system. They also tested their solution across different types of input material (mixed case, upper case and speech form) and with a different language (Spanish). The results are shown in the table below:
In the Mixed Case setting the best rules system performed better than the proposed solution in the present paper, although the different is not statistically significant, and does not compensate the effort of having experts maintaining the set of rules. The authors justify the low score for Spanish with the low quantity and quality (inconsistencies) in the training data of the Spanish model.
Another result that came out of this work was the fact that 100k words of training seems to suffice to obtain state-of-the-art results for the NE task.
