---
title: "Phrase Clustering for Discriminative Learning — Lin 2009"
description: "The paper tackles lexical sparsity in supervised NLP. 25 references, cited by 70 papers here."
authors: ["Dekang Lin", "Xiaoyun Wu"]
year: 2009
venue: "Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP"
source: "https://aclanthology.org/P09-1116/"
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/lin-2009-phrase-clustering-discriminative-learning/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/lin-2009-phrase-clustering-discriminative-learning/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2009](https://md.research.elamur.ai/free/en/papers/2009/) / Phrase Clustering for Discriminative Learning

# Phrase Clustering for Discriminative Learning

**Authors:** [Dekang Lin](https://md.research.elamur.ai/free/en/authors/dekang-lin/) and Xiaoyun Wu · **Year:** 2009 · **Venue:** [Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP](https://md.research.elamur.ai/free/en/venues/acl/) ([ACL 2009](https://md.research.elamur.ai/free/en/venues/acl/2009/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **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/P09-1116/) · [PDF](https://aclanthology.org/P09-1116.pdf) · [OpenAlex](https://openalex.org/W2168596788)

**Citations:** 226 citations (OpenAlex, 2026-10-14) · [70](https://md.research.elamur.ai/free/en/papers/lin-2009-phrase-clustering-discriminative-learning/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
The paper tackles lexical sparsity in supervised NLP. Most word types are rare or absent in labeled data, and the usual fix of Brown word clusters is quadratic and cannot handle tens of millions of phrases. The authors cluster phrases instead of single words, since the words inside a phrase disambiguate each other. They take about 20 million frequent queries from an anonymized query log, keeping only those that also occur in a 700-billion-token web corpus. Each phrase is described by PMI-weighted counts of the words in small windows around its occurrences. A distributed K-Means implemented in MapReduce then groups these vectors, using cosine similarity and an inverted index over centroids. The resulting soft clusters, at several granularities, serve as features in discriminative classifiers. On CoNLL 2003 English NER the system reaches an F1 of 90.90, about one point above the previous best. In KDDCUP 2005 query classification it equals the winning systems without their heavy manual knowledge engineering. This shows that cheap unsupervised phrase clusters can stand in for hand-built resources.

## Key points
- Phrase list: 20M unique queries that appear in a 700B-token web corpus with frequency ≥ 100. A Bloom filter tests phrase membership, and its false positives are simply tolerated.
- Context features are single-word tokens in windows of size 1 or 3, weighted by PMI and compared with cosine similarity. Each phrase is capped at 300K instances when its vector is built.
- NER: F1 90.90 on CoNLL 2003 English, roughly 1 point better than the prior best result.
- Query classification (KDDCUP 2005): only 12% of words in the 800 test queries occur in the training examples, so bag-of-words features perform very poorly. Word clusters give a large gain, phrase clusters add another, and combining several phrase clusterings works best.
- Soft clustering assigns an element to every cluster whose similarity exceeds a threshold. For queries, a phrase is linked to its nearest centroids when similarity is above 0.04.

## Interesting ideas
- **Window size controls cluster type.** Narrow context windows give categorical clusters, such as kinds of lessons, while wider ones give topical clusters, such as language learning. This lets one pipeline produce clusters suited to tagging-style tasks or to topic-style tasks.
- **Partial sums inside mappers.** Each mapper accumulates per-cluster vector sums for its partition and emits only those sums, instead of every assignment. This avoids an expensive shuffle and numerical underflow, and the trick applies to any large-scale centroid-based aggregation.
- **Inverted index from features to centroids.** With sparse, unit-length vectors, scoring an element against all centroids only needs the features it shares with them. This replaces kd-trees, which fail in high dimensions, and is useful for nearest-centroid search over sparse data generally.
- **Skip choosing k.** Clusterings built with several different k values are fed in together, and the supervised learner picks the useful granularity. Unlike Brown-based approaches, the clusterings do not need to be hierarchical.
- **Cap occurrences per item.** Limiting how many instances contribute to a phrase's vector cuts computation and evens out vector sizes across frequent and rare items. This is a cheap safeguard for any distributional representation built from web-scale data.

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

## Institutions

- [Google](https://md.research.elamur.ai/free/en/companies/google/) — Company, Mountain View, United States · 353 works · 364,806 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,085 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,888 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works

## Cite

Cite as: Dekang Lin and Xiaoyun Wu. 2009. Phrase Clustering for Discriminative Learning. Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP.

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

```bibtex
@inproceedings{lin2009phrase,
  title = {{Phrase Clustering for Discriminative Learning}},
  author = {Dekang Lin and Xiaoyun Wu},
  booktitle = {Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP},
  year = {2009},
  doi = {10.3115/1690219.1690290},
  url = {https://doi.org/10.3115/1690219.1690290}
}
```

- [← previous Unsupervised Type and Token Identification of Idiomatic Expressions](https://md.research.elamur.ai/free/en/papers/fazly-2009-unsupervised-type-token-identification-idiomatic/)
- [next → A Survey of Paraphrasing and Textual Entailment Methods](https://md.research.elamur.ai/free/en/papers/androutsopoulos-2009-survey-paraphrasing-textual-entailment-methods/)
- [↑ back to papers of 2009](https://md.research.elamur.ai/free/en/papers/2009/)

## References

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

1. R. Ando and T. Zhang A Framework for Learning Predictive Structures from Multiple Tasks and Unlabeled Data. Journal of Machine Learning Research, Vol 6:1817-1853, 2005. [find](https://scholar.google.com/scholar?q=R%2E+Ando+and+T%2E+Zhang+A+Framework+for+Learning+Predictive+Structures+from+Multiple+Tasks+and+Unlabeled+Data%2E+Journal+of+Machine+Learning+Research%2C+Vol+6%3A1817%2D1853%2C+2005%2E)
2. B.H. Bloom. 1970, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM 13 (7): 422–426 [find](https://scholar.google.com/scholar?q=B%2EH%2E+Bloom%2E+1970%2C+Space%2Ftime+trade%2Doffs+in+hash+coding+with+allowable+errors%2C+Communications+of+the+ACM+13+%287%29%3A+422%E2%80%93426)
3. A. Blum and T. Mitchell. 1998. [Combining labeled and unlabeled data with co-training](https://md.research.elamur.ai/free/en/papers/blum-1998-combining-labeled-unlabeled-data-co-training/). Proceedings of the Eleventh Annual Conference on Computational Learning Theory pp. 92–100.
4. P.F. Brown, V.J. Della Pietra, P.V. de Souza, J.C. Lai, and R.L. Mercer. 1992. Class-based n-gram models of natural language. Computational Linguistics, 18(4):467–479. [find](https://scholar.google.com/scholar?q=P%2EF%2E+Brown%2C+V%2EJ%2E+Della+Pietra%2C+P%2EV%2E+de+Souza%2C+J%2EC%2E+Lai%2C+and+R%2EL%2E+Mercer%2E+1992%2E+Class%2Dbased+n%2Dgram+models+of+natural+language%2E+Computational+Linguistics%2C+18%284%29%3A467%E2%80%93479%2E)
5. H. L. Chieu and H. T. Ng. Named entity recognition with a maximum entropy approach. In Proceedings CoNLL-2003, pages 160–163, 2003. [find](https://scholar.google.com/scholar?q=H%2E+L%2E+Chieu+and+H%2E+T%2E+Ng%2E+Named+entity+recognition+with+a+maximum+entropy+approach%2E+In+Proceedings+CoNLL%2D2003%2C+pages+160%E2%80%93163%2C+2003%2E)
6. J. Dean and S. Ghemawat. 2004. MapReduce: Simplified data processing on large clusters. In Proceedings of the Sixth Symposium on Operating System Design and Implementation (OSDI-04), San Francisco, CA, USA S Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, and R. A. Harshman. 1990. Indexing b… [find](https://scholar.google.com/scholar?q=J%2E+Dean+and+S%2E+Ghemawat%2E+2004%2E+MapReduce%3A+Simplified+data+processing+on+large+clusters%2E+In+Proceedings+of+the+Sixth+Symposium+on+Operating+System+Design+and+Implementation+%28OSDI%2D04%29%2C+San+Francisco%2C+CA)
7. R. Florian, A. Ittycheriah, H. Jing, and T. Zhang. [Named entity recognition through classifier combination](https://md.research.elamur.ai/free/en/papers/florian-2003-named-entity-recognition-through-classifier/). In Proceedings CoNLL-2003, pages 168–171, 2003.
8. D. Klein, J. Smarr, H. Nguyen, and C. D. Manning. Named entity recognition with character-level models. In Proceedings CoNLL-2003, pages 188– 191, 2003. [find](https://scholar.google.com/scholar?q=D%2E+Klein%2C+J%2E+Smarr%2C+H%2E+Nguyen%2C+and+C%2E+D%2E+Manning%2E+Named+entity+recognition+with+character%2Dlevel+models%2E+In+Proceedings+CoNLL%2D2003%2C+pages+188%E2%80%93+191%2C+2003%2E)
9. P. Koehn, F.J. Och, and D. Marcu. 2003. Statistical phrase-based translation. In Proceedings of HLT-NAACL 2003, pp. 127–133. [find](https://scholar.google.com/scholar?q=P%2E+Koehn%2C+F%2EJ%2E+Och%2C+and+D%2E+Marcu%2E+2003%2E+Statistical+phrase%2Dbased+translation%2E+In+Proceedings+of+HLT%2DNAACL+2003%2C+pp%2E+127%E2%80%93133%2E)
10. T. Koo, X. Carreras, and M. Collins. [Simple Semi-supervised Dependency Parsing](https://md.research.elamur.ai/free/en/papers/koo-2008-simple-semi-supervised-dependency-parsing/). Proceedings of ACL, 2008.
11. J. Lafferty, A. McCallum, F. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In: Proc. 18th International Conf. on Machine Learning, Morgan Kaufmann, San Francisco, CA (2001) 282–289 [find](https://scholar.google.com/scholar?q=J%2E+Lafferty%2C+A%2E+McCallum%2C+F%2E+Pereira%2E+Conditional+random+fields%3A+Probabilistic+models+for+segmenting+and+labeling+sequence+data%2E+In%3A+Proc%2E+18th+International+Conf%2E+on+Machine+Learning%2C+Morgan+Kaufmann)
12. Y. Li, Z. Zheng, and H.K. Dai, KDD Cup-2005 Report: Facing a Great Challenge. SIGKDD Explorations, 7 (2), 2005, 91-99. [find](https://scholar.google.com/scholar?q=Y%2E+Li%2C+Z%2E+Zheng%2C+and+H%2EK%2E+Dai%2C+KDD+Cup%2D2005+Report%3A+Facing+a+Great+Challenge%2E+SIGKDD+Explorations%2C+7+%282%29%2C+2005%2C+91%2D99%2E)
13. D. Lin, S. Zhao, and B. Van Durme, and M. Pasca. 2008. Mining Parenthetical Translations from the Web by Word Alignment. Proc. of ACL-08. Columbus, OH. [find](https://scholar.google.com/scholar?q=D%2E+Lin%2C+S%2E+Zhao%2C+and+B%2E+Van+Durme%2C+and+M%2E+Pasca%2E+2008%2E+Mining+Parenthetical+Translations+from+the+Web+by+Word+Alignment%2E+Proc%2E+of+ACL%2D08%2E+Columbus%2C+OH%2E)
14. J. Lin. Scalable Language Processing Algorithms for the Masses: A Case Study in Computing Word Co-occurrence Matrices with MapReduce. Proceedings of EMNLP 2008, pp. 419-428, Honolulu, Hawaii. [find](https://scholar.google.com/scholar?q=J%2E+Lin%2E+Scalable+Language+Processing+Algorithms+for+the+Masses%3A+A+Case+Study+in+Computing+Word+Co%2Doccurrence+Matrices+with+MapReduce%2E+Proceedings+of+EMNLP+2008%2C+pp%2E+419%2D428%2C+Honolulu%2C+Hawaii%2E)
15. J. B. MacQueen (1967): Some Methods for classification and Analysis of Multivariate Observations, Proc. of 5-th Berkeley Symposium on Mathematical Statistics and Probability", Berkeley, University of California Press, 1:281-297 [find](https://scholar.google.com/scholar?q=J%2E+B%2E+MacQueen+%281967%29%3A+Some+Methods+for+classification+and+Analysis+of+Multivariate+Observations%2C+Proc%2E+of+5%2Dth+Berkeley+Symposium+on+Mathematical+Statistics+and+Probability%22%2C+Berkeley%2C+University+of+)
16. S. Miller, J. Guinness, and A. Zamanian. 2004. [Name Tagging with Word Clusters and Discriminative Training](https://md.research.elamur.ai/free/en/papers/miller-2004-name-tagging-word-clusters-discriminative/). In Proceedings of HLT-NAACL, pages 337–342.
17. M. Sahami and T.D. Heilman. 2006. A web-based kernel function for measuring the similarity of short text snippets. Proceedings of the 15th international conference on World Wide Web, pp. 377–386. [find](https://scholar.google.com/scholar?q=M%2E+Sahami+and+T%2ED%2E+Heilman%2E+2006%2E+A+web%2Dbased+kernel+function+for+measuring+the+similarity+of+short+text+snippets%2E+Proceedings+of+the+15th+international+conference+on+World+Wide+Web%2C+pp%2E+377%E2%80%93386%2E)
18. D. Shen, R. Pan, J.T. Sun, J.J. Pan, K. Wu, J. Yin, Q. Yang. Q2C@UST: our winning solution to query classification in KDDCUP 2005. [find](https://scholar.google.com/scholar?q=D%2E+Shen%2C+R%2E+Pan%2C+J%2ET%2E+Sun%2C+J%2EJ%2E+Pan%2C+K%2E+Wu%2C+J%2E+Yin%2C+Q%2E+Yang%2E+Q2C%40UST%3A+our+winning+solution+to+query+classification+in+KDDCUP+2005%2E)
19. SIGKDD Explorations, 2005: 100~110. [find](https://scholar.google.com/scholar?q=SIGKDD+Explorations%2C+2005%3A+100%7E110%2E)
20. J. Suzuki, and H. Isozaki. 2008. Semi-Supervised Sequential Labeling and Segmentation using Gigaword Scale Unlabeled Data. In Proc. of ACL/HLT-08. Columbus, Ohio. pp. 665-673. [find](https://scholar.google.com/scholar?q=J%2E+Suzuki%2C+and+H%2E+Isozaki%2E+2008%2E+Semi%2DSupervised+Sequential+Labeling+and+Segmentation+using+Gigaword+Scale+Unlabeled+Data%2E+In+Proc%2E+of+ACL%2FHLT%2D08%2E+Columbus%2C+Ohio%2E+pp%2E+665%2D673%2E)
21. E. T. Tjong Kim Sang and F. De Meulder. 2003. [Introduction to the CoNLL-2003 Shared Task: Language-Independent Named Entity Recognition](https://md.research.elamur.ai/free/en/papers/sang-2003-introduction-conll-2003-shared-task/). In Proc. of CoNLL-2003, pages 142–147.
22. Y. Wong and H. T. Ng, 2007. One Class per Named Entity: Exploiting Unlabeled Text for Named Entity Recognition. In Proc. of IJCAI-07, Hyderabad, India. [find](https://scholar.google.com/scholar?q=Y%2E+Wong+and+H%2E+T%2E+Ng%2C+2007%2E+One+Class+per+Named+Entity%3A+Exploiting+Unlabeled+Text+for+Named+Entity+Recognition%2E+In+Proc%2E+of+IJCAI%2D07%2C+Hyderabad%2C+India%2E)
23. J. Uszkoreit and T. Brants. 2008. Distributed Word Clustering for Large Scale Class-Based Language Modeling in Machine Translation. Proceedings of ACL-08: HLT, pp. 755-762. [find](https://scholar.google.com/scholar?q=J%2E+Uszkoreit+and+T%2E+Brants%2E+2008%2E+Distributed+Word+Clustering+for+Large+Scale+Class%2DBased+Language+Modeling+in+Machine+Translation%2E+Proceedings+of+ACL%2D08%3A+HLT%2C+pp%2E+755%2D762%2E)
24. V. Vapnik, 1999. The Nature of Statistical Learning Theory, 2nd edition. Springer Verlag. [find](https://scholar.google.com/scholar?q=V%2E+Vapnik%2C+1999%2E+The+Nature+of+Statistical+Learning+Theory%2C+2nd+edition%2E+Springer+Verlag%2E)
25. D. Vogel, S. Bickel, P. Haider, R. Schimpfky, P. Siemen, S. Bridges, T. Scheffer. Classifying Search Engine Queries Using the Web as Background Knowledge. SIGKDD Explorations 7(2): 117-122. 2005. [find](https://scholar.google.com/scholar?q=D%2E+Vogel%2C+S%2E+Bickel%2C+P%2E+Haider%2C+R%2E+Schimpfky%2C+P%2E+Siemen%2C+S%2E+Bridges%2C+T%2E+Scheffer%2E+Classifying+Search+Engine+Queries+Using+the+Web+as+Background+Knowledge%2E+SIGKDD+Explorations+7%282%29%3A+117%2D122%2E+2005%2E)

*Updated 24 October 2026*