Elamur Research⌕
☰
home / papers / 2009 / Phrase Clustering for Discriminative Learning

Phrase Clustering for Discriminative Learning

Paper · 2009 · Dekang Lin and Xiaoyun Wu

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

  • I1. 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.
  • I2. 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.
  • I3. 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.
  • I4. 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.
  • I5. 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

🏢GoogleMountain View · United States353 works · 364,806 citations

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage 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.

@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}
}

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
  2. B.H. Bloom. 1970, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM 13 (7): 422–426 find
  3. A. Blum and T. Mitchell. 1998. Combining labeled and unlabeled data with 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
  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
  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
  7. R. Florian, A. Ittycheriah, H. Jing, and T. Zhang. Named entity recognition through classifier combination. 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
  9. P. Koehn, F.J. Och, and D. Marcu. 2003. Statistical phrase-based translation. In Proceedings of HLT-NAACL 2003, pp. 127–133. find
  10. T. Koo, X. Carreras, and M. Collins. 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
  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
  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
  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
  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
  16. S. Miller, J. Guinness, and A. Zamanian. 2004. Name Tagging with Word Clusters and Discriminative Training. 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
  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
  19. SIGKDD Explorations, 2005: 100~110. find
  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
  21. E. T. Tjong Kim Sang and F. De Meulder. 2003. Introduction to the CoNLL-2003 Shared Task: Language-Independent Named Entity Recognition. 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
  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
  24. V. Vapnik, 1999. The Nature of Statistical Learning Theory, 2nd edition. Springer Verlag. find
  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

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/lin-2009-phrase-clustering-discriminative-learning/