---
title: "A Discriminative Matching Approach to Word — Taskar 2005"
description: "The paper reframes word alignment between parallel sentences as a learned, feature-rich bipartite matching task, as an alternative to generative…"
authors: ["Ben Taskar", "Simon Lacoste-Julien", "Dan Klein"]
year: 2005
venue: "Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing"
source: "https://aclanthology.org/H05-1010/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/taskar-2005-discriminative-matching-approach-word-alignment/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/taskar-2005-discriminative-matching-approach-word-alignment/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2005](https://md.research.elamur.ai/free/en/papers/2005/) / A Discriminative Matching Approach to Word Alignment

# A Discriminative Matching Approach to Word Alignment

**Authors:** [Ben Taskar](https://md.research.elamur.ai/free/en/authors/ben-taskar/), Simon Lacoste-Julien, [Dan Klein](https://md.research.elamur.ai/free/en/authors/dan-klein/) · **Year:** 2005 · **Venue:** Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/H05-1010/) · [PDF](https://aclanthology.org/H05-1010.pdf) · [OpenAlex](https://openalex.org/W2119224513)

**Citations:** 167 citations (openalex-snapshot · 2026-10-14) · [70](#cited-by) in our library, of the 140673 papers whose bibliographies we read

## Summary
The paper reframes word alignment between parallel sentences as a learned, feature-rich bipartite matching task, as an alternative to generative IBM-style models trained with EM. Each candidate pair of words gets a score that is a linear function of arbitrary features: Dice association counts from unlabeled text, positional distortion, orthographic similarity, frequency and others. The alignment is then the best-scoring one-to-one matching. The weights are trained with a large-margin objective. Because loss-augmented matching can be written as a linear program with integral solutions, training becomes a saddle-point problem, which the authors solve with the extragradient method and projections computed via min-cost quadratic flow. On the English-French Hansards data, 100 hand-aligned training sentences and cheap count-based features give AER close to unsymmetrized IBM Model 4. Adding Model 4 outputs as features yields 5.4 AER, which beats intersected Model 4 by 22% relative. The approach brings flexible feature engineering to alignment, needs very little supervision, and trains much faster than GIZA++.

## Key points
- Data: the English-French Hansards set from the 2003 NAACL shared task, with 1.1M sentence pairs, a 39-pair validation set and a 447-sentence hand-aligned test set. The test set was split into 100 training and 347 evaluation sentences, so comparisons with other published results are not perfectly clean.
- AER improved as feature groups were added:
  - Dice only: 29.8
  - plus distance features: 15.5
  - plus word shape and frequency: 14.4
  - plus common-word bilexical and next-pair Dice features: 10.7
  - plus Model 4 predictions: 5.4
- Baselines for comparison: IBM Model 4 scored 8.9 and 9.7 in each direction and 6.9 when intersected. Raw Dice without matching scored about 36–39.
- With the same features, an averaged perceptron reached only 8.1 AER. This is worse than the single intersected Model 4 feature.
- Speed: GIZA++ needed 18 hours on the full corpus. The discriminative learner trained in 6 minutes on 100 sentences and in about 3 hours on 5K sentences labeled noisily by Model 4.

## Interesting ideas
- **Asymmetric Hamming loss as the training cost.** Missed links (false negatives) were penalized 3 times more than spurious links, with the ratio tuned on validation data. This is a simple way to push a structured model toward the recall/precision balance that the evaluation metric rewards.
- **Exact training via LP integrality.** Since the matching polytope has integral vertices, loss-augmented inference can be relaxed to an LP without any approximation. The same trick applies to other structured outputs whose polytopes behave this way.
- **Context dependencies moved into features.** The matcher itself treats each link independently, but features such as the Dice score of the following word pair bring in neighbor information. This keeps inference cheap while still capturing some context.
- **Stacking strong systems as features.** Directional and intersected Model 4 predictions were fed in as edge features. A small labeled set was then enough to learn how much to trust each one, which is a cheap way to improve on existing aligners for a new language pair such as Ukrainian–English.
- **Noisy automatic labels for scaling.** Model 4 alignments served as extra training data when gold labels were scarce. This is a reusable recipe for bootstrapping supervised models from the output of a slower unsupervised system.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

Fields: [Linguistics & languages](https://md.research.elamur.ai/free/en/shelves/linguistics/) · [Machine translation](https://md.research.elamur.ai/free/en/shelves/machine-translation/) · [Natural language processing](https://md.research.elamur.ai/free/en/shelves/nlp/)

## Cited by

Cited by

70 papers of our library cite it (of the 140673 whose bibliographies we read); 3 of them have a page here, 67 not yet.

- [Better Word Alignments with Supervised ITG Models](https://md.research.elamur.ai/free/en/papers/haghighi-2009-better-word-alignments-supervised-itg/)
- [Alignment by Agreement](https://md.research.elamur.ai/free/en/papers/liang-2006-alignment-agreement/)
- [Creating a Translation Matrix of the Bible's Names Across 591 Languages](https://md.research.elamur.ai/free/en/papers/wu-2018-creating-translation-matrix-bible-s/)

## Cite

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{taskar2005discriminative,
  title = {{A Discriminative Matching Approach to Word Alignment}},
  author = {Taskar, Ben and Lacoste-Julien, Simon and Klein, Dan},
  booktitle = {Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing},
  year = {2005},
  doi = {10.3115/1220575.1220585},
  url = {https://doi.org/10.3115/1220575.1220585}
}
```

- [← previous A Classifier-Based Parser with Linear Run-Time Complexity](https://md.research.elamur.ai/free/en/papers/sagae-2005-classifier-based-parser-linear-run/)
- [next → A Finite-State Morphological Grammar of Hebrew](https://md.research.elamur.ai/free/en/papers/aclbulk-2005-yona-finite-state-morphological-grammar-hebrew/)
- [↑ back to papers of 2005](https://md.research.elamur.ai/free/en/papers/2005/)

## References

18 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. D. P. Bertsekas, L. C. Polymenakos, and P. Tseng. 1997. An e-relaxation method for separable convex cost network flow problems. SIAM J. Optim., 7(3):853–870. [find](https://scholar.google.com/scholar?q=D%2E+P%2E+Bertsekas%2C+L%2E+C%2E+Polymenakos%2C+and+P%2E+Tseng%2E+1997%2E+An+e%2Drelaxation+method+for+separable+convex+cost+network+flow+problems%2E+SIAM+J%2E+Optim%2E%2C+7%283%29%3A853%E2%80%93870%2E)
2. P. F. Brown, J. Cocke, S. A. Della Pietra, V. J. Della Pietra, F. Jelinek, J. D. Lafferty, R. L. Mercer, and P. S. Roossin. 1990. A statistical approach to machine translation. Computational Linguistics, 16(2):79–85. [find](https://scholar.google.com/scholar?q=P%2E+F%2E+Brown%2C+J%2E+Cocke%2C+S%2E+A%2E+Della+Pietra%2C+V%2E+J%2E+Della+Pietra%2C+F%2E+Jelinek%2C+J%2E+D%2E+Lafferty%2C+R%2E+L%2E+Mercer%2C+and+P%2E+S%2E+Roossin%2E+1990%2E+A+statistical+approach+to+machine+translation%2E+Computational+Linguisti)
3. M. Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proc. EMNLP. [find](https://scholar.google.com/scholar?q=M%2E+Collins%2E+2002%2E+Discriminative+training+methods+for+hidden+markov+models%3A+Theory+and+experiments+with+perceptron+algorithms%2E+In+Proc%2E+EMNLP%2E) [our card](https://md.research.elamur.ai/free/en/papers/collins-2002-discriminative-training-methods-hidden-markov/)
4. T. H. Cormen, C. E. Leiserson, and R. L. Rivest. 1990. Introduction to Algorithms. MIT Press, Cambridge, MA. [find](https://scholar.google.com/scholar?q=T%2E+H%2E+Cormen%2C+C%2E+E%2E+Leiserson%2C+and+R%2E+L%2E+Rivest%2E+1990%2E+Introduction+to+Algorithms%2E+MIT+Press%2C+Cambridge%2C+MA%2E)
5. L. R. Dice. 1945. Measures of the amount of ecologic association between species. Journal of Ecology, 26:297– 302. [find](https://scholar.google.com/scholar?q=L%2E+R%2E+Dice%2E+1945%2E+Measures+of+the+amount+of+ecologic+association+between+species%2E+Journal+of+Ecology%2C+26%3A297%E2%80%93+302%2E)
6. F. Guerriero and P. Tseng. 2002. Implementation and test of auction methods for solving generalized network flow problems with separable convex cost. Journal of Optimization Theory and Applications, 115(1):113–144, October. [find](https://scholar.google.com/scholar?q=F%2E+Guerriero+and+P%2E+Tseng%2E+2002%2E+Implementation+and+test+of+auction+methods+for+solving+generalized+network+flow+problems+with+separable+convex+cost%2E+Journal+of+Optimization+Theory+and+Applications%2C+1)
7. B.S. He and L. Z. Liao. 2002. Improvements of some projection methods for monotone nonlinear variational inequalities. JOTA, 112:111:128. [find](https://scholar.google.com/scholar?q=B%2ES%2E+He+and+L%2E+Z%2E+Liao%2E+2002%2E+Improvements+of+some+projection+methods+for+monotone+nonlinear+variational+inequalities%2E+JOTA%2C+112%3A111%3A128%2E)
8. G. M. Korpelevich. 1976. The extragradient method for finding saddle points and other problems. Ekonomika i Matematicheskie Metody, 12:747:756. [find](https://scholar.google.com/scholar?q=G%2E+M%2E+Korpelevich%2E+1976%2E+The+extragradient+method+for+finding+saddle+points+and+other+problems%2E+Ekonomika+i+Matematicheskie+Metody%2C+12%3A747%3A756%2E)
9. E. Matusov, R. Zens, and H. Ney. 2004. Symmetric word alignments for statistical machine translation. In Proc. of COLING 2004. [find](https://scholar.google.com/scholar?q=E%2E+Matusov%2C+R%2E+Zens%2C+and+H%2E+Ney%2E+2004%2E+Symmetric+word+alignments+for+statistical+machine+translation%2E+In+Proc%2E+of+COLING+2004%2E)
10. I. D. Melamed. 2000. Models of translational equivalence among words. Computational Linguistics, 26(2):221– 249. [find](https://scholar.google.com/scholar?q=I%2E+D%2E+Melamed%2E+2000%2E+Models+of+translational+equivalence+among+words%2E+Computational+Linguistics%2C+26%282%29%3A221%E2%80%93+249%2E)
11. R. Mihalcea and T. Pedersen. 2003. An evaluation exercise for word alignment. In Proceedings of the HLT-NAACL 2003 Workshop, Building and Using parallel Texts: Data Driven Machine Translation and Beyond, pages 1–6, Edmonton, Alberta, Canada. [find](https://scholar.google.com/scholar?q=R%2E+Mihalcea+and+T%2E+Pedersen%2E+2003%2E+An+evaluation+exercise+for+word+alignment%2E+In+Proceedings+of+the+HLT%2DNAACL+2003+Workshop%2C+Building+and+Using+parallel+Texts%3A+Data+Driven+Machine+Translation+and+Beyo) [our card](https://md.research.elamur.ai/free/en/papers/mihalcea-2003-evaluation-exercise-word-alignment/)
12. F. Och and H. Ney. 2003. A systematic comparison of various statistical alignment models. Computational Linguistics, 29(1):19–52. [find](https://scholar.google.com/scholar?q=F%2E+Och+and+H%2E+Ney%2E+2003%2E+A+systematic+comparison+of+various+statistical+alignment+models%2E+Computational+Linguistics%2C+29%281%29%3A19%E2%80%9352%2E)
13. A. Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer. [find](https://scholar.google.com/scholar?q=A%2E+Schrijver%2E+2003%2E+Combinatorial+Optimization%3A+Polyhedra+and+Efficiency%2E+Springer%2E)
14. B. Taskar, V. Chatalbashev, D. Koller, and C. Guestrin. 2005a. Learning structured prediction models: a large margin approach. In Proceedings of the International Conference on Machine Learning. [find](https://scholar.google.com/scholar?q=B%2E+Taskar%2C+V%2E+Chatalbashev%2C+D%2E+Koller%2C+and+C%2E+Guestrin%2E+2005a%2E+Learning+structured+prediction+models%3A+a+large+margin+approach%2E+In+Proceedings+of+the+International+Conference+on+Machine+Learning%2E)
15. B. Taskar, S. Lacoste-Julien, and M. Jordan. 2005b. Structured prediction via the extragradient method. In Proceedings of Neural Information Processing Systems. [find](https://scholar.google.com/scholar?q=B%2E+Taskar%2C+S%2E+Lacoste%2DJulien%2C+and+M%2E+Jordan%2E+2005b%2E+Structured+prediction+via+the+extragradient+method%2E+In+Proceedings+of+Neural+Information+Processing+Systems%2E)
16. J. Tiedemann. 2003. Combining clues for word alignment. In Proceedings of EACL. [find](https://scholar.google.com/scholar?q=J%2E+Tiedemann%2E+2003%2E+Combining+clues+for+word+alignment%2E+In+Proceedings+of+EACL%2E)
17. L. G. Valiant. 1979. The complexity of computing the permanent. Theoretical Computer Science, 8:189–201. [find](https://scholar.google.com/scholar?q=L%2E+G%2E+Valiant%2E+1979%2E+The+complexity+of+computing+the+permanent%2E+Theoretical+Computer+Science%2C+8%3A189%E2%80%93201%2E)
18. S. Vogel, H. Ney, and C. Tillmann. 1996. HMM-based word alignment in statistical translation. In COLING 16, pages 836–841. [find](https://scholar.google.com/scholar?q=S%2E+Vogel%2C+H%2E+Ney%2C+and+C%2E+Tillmann%2E+1996%2E+HMM%2Dbased+word+alignment+in+statistical+translation%2E+In+COLING+16%2C+pages+836%E2%80%93841%2E)