Elamur Research⌕
☰
home / papers / 1999 / Measures of Distributional Similarity

Measures of Distributional Similarity

Summary

The paper tackles sparse data in statistical NLP: how to estimate the probability of a word pair that never appeared in training. Lee uses distance-weighted averaging, which builds the estimate from the cooccurrence behaviour of distributionally similar words. She asks which similarity function best picks those proxy words. The testbed is verb–object pairs from the 1988 Associated Press newswire, restricted to the 1000 most frequent nouns, with a pseudoword-style binary decision task on unseen pairs.

Seven measures are compared using a stripped-down, weight-free evaluation. They fall into four performance groups. The grouping tracks how much each measure relies on verbs that occur with both nouns. Building on this, and on the observation that substitutability is often one-directional, Lee introduces an asymmetric smoothed KL variant, the skew divergence. It outperforms all the others and cuts error by about 4% on average relative to the Jensen-Shannon divergence. The work offers both a better metric and a principled way to classify similarity functions.

Key points

  • Data: verb–object cooccurrences drawn from the 1988 AP newswire, limited to pairs whose noun is among the 1000 most frequent, and obtained using Church's and Yarowsky's tools.
    • 587,833 pairs (80%) were used for training.
    • Test sets were built from the remaining 20% after removing pairs already seen in training, then split into five partitions.
  • Measures compared: Euclidean (L2) distance, L1 norm, cosine, Jaccard's coefficient, Jensen-Shannon divergence, confusion probability, and Kendall's τ.
    • Every one of them stays far below Katz backoff's 51% error rate.
  • Performance groups:
    1. L2 (worst)
    2. Kendall's τ
    3. confusion probability and cosine
    4. L1, Jensen-Shannon, and Jaccard (best)
  • Skew divergence: defined as the KL divergence of r from a mixture αq + (1−α)r. With α = 0.99, it beats Jensen-Shannon by about 4% average error reduction (significant at .01). It also beats Jaccard significantly under a paired t-test at nearly all k.
  • Measures excluded and why:
    • Mutual information compares a joint distribution with a product distribution, not two arbitrary distributions.
    • Dice is monotonic in Jaccard, so it would be redundant.
    • Hamming-type metrics are meant for symbolic features, and the value difference metric needs probability-labelled training data.
    • Plain KL needs a smoothed base model.

Interesting ideas

  • I1. Separate ranking quality from weighting. Instead of judging similarity functions inside the full smoothing model, count how many of the top-k neighbours make the correct decision. This shows whether a metric ranks well, independent of the weighting scheme. The same trick applies to evaluating any retrieval or neighbour-selection component.
  • I2. Decompose measures by support regions. Rewriting each function as sums over shared versus non-shared contexts explains why some measures behave alike. This analytic lens could help compare embedding or feature similarity metrics.
  • I3. Rely mainly on shared contexts. The best functions depend mostly on contexts both words share, which is also computationally cheap because that set is small. This argues for discounting purely negative evidence in sparse settings.
  • I4. Use asymmetric similarity for proxies. A broad word like "fruit" can stand in for "apple" more easily than the reverse. Directional measures may therefore suit tasks such as hypernymy or backoff to more general categories.
  • I5. Smooth one distribution with the other. Mixing a small portion of the second distribution into the first keeps KL defined on sparse counts without a separately smoothed base model. This is a cheap fix wherever zero probabilities break divergence computations.

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: Natural language processing

Institutions

🎓Cornell UniversityIthaca · United States68 works · 52,012 citations

Cite

Cite as Lillian Lee. 1999. Measures of Distributional Similarity. Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics.

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

@inproceedings{lee1999measures,
  title = {{Measures of Distributional Similarity}},
  author = {Lillian Lee},
  booktitle = {Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics},
  year = {1999},
  doi = {10.3115/1034678.1034693},
  url = {https://doi.org/10.3115/1034678.1034693}
}

References

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

  1. Claire Cardie. 1993. A case-based approach to knowledge acquisition for domain-specific sentence analysis. In 11th National Conference on Artifical Intelligence, pages 798-803. find
  2. Kenneth Ward Church and Patrick Hanks. 1990. Word association norms, mutual information, and lexicography. Computational Linguistics, 16(1):22-29. our card
  3. Kenneth W. Church. 1988. A stochastic parts program and noun phrase parser for unrestricted text. In Second Conference on Applied Natural Language Processing, pages 136-143. our card
  4. Thomas M. Cover and Joy A. Thomas. 1991. Elements of Information Theory. John Wiley. find
  5. Ido Dagan, Shanl Marcus, and Shanl Markovitch. 1995. Contextual word similarity and estimation from sparse data. Computer Speech and Language, 9:123-152. find
  6. Ido Dagan, Lillian Lee, and Fernando Pereira. 1999. Similarity-based models of cooccurrence probabilities. Machine Learning, 34(1-3) :43-69. find
  7. Ute Essen and Volker Steinbiss. 1992. Co-occurrence smoothing for stochastic language modeling. In ICASSP 92, volume 1, pages 161-164. find
  8. Jean Dickinson Gibbons. 1993. Nonparametric Measures of Association. Sage University Paper series on Quantitative Applications in the Social Sciences, 07-091. Sage Publications. find
  9. Ralph Grishman and John Sterling. 1993. Smoothing of automatically generated selectional constraints. In Human Language Technology: Proceedings of the ARPA Workshop, pages 254-259. find
  10. Vasileios Hatzivassiloglou and Kathleen McKeown. 1993. Towards the automatic identification of adjectival scales: Clustering of adjectives according to meaning. In 31st Annual Meeting of the ACL, pages 172-182. find
  11. Vasileios Hatzivassiloglou. 1996. Do we need linguistics when we have statistics? A comparative analysis of the contributions of linguistic cues to a statistical word grouping system. In Judith L. Klavans and Philip Resnik, editors, The Balancing Act, pages 67-94. MIT Press. find
  12. Don Hindle. 1990. Noun classification from predicate-argument structures. In 28th Annual Meeting of the A CL, pages 268-275. our card
  13. Frederick Jelinek and Robert L. Mercer. 1980. Interpolated estimation of Markov source parameters from sparse data. In Proceedings of the Workshop on Pattern Recognition in Practice. find
  14. William P. Jones and George W. Furnas. 1987. Pictures of relevance. Journal of the American Society for Information Science, 38(6):420-442. find
  15. Yael Karov and Shimon Edelman. 1998. Similarity-based word sense disambiguation. Computational Linguistics, 24(1):41-59. find
  16. Slava M. Katz. 1987. Estimation of probabilities from sparse data for the language model component of a speech recognizer. IEEE Transactions on Acoustics, Speech and Signal Processing, ASSP-35(3):400–401, March. find
  17. Leonard Kanfman and Peter J. Rousseeuw. 1990. Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley and Sons. find
  18. Lillian Lee. 1997. Similarity-Based Approaches to Natural Language Processing. Ph.D. thesis, Harvard University. find
  19. Dekang Lin. 1997. Using syntactic dependency as local context to resolve word sense ambiguity. In 35th Annual Meeting of the ACL, pages 64-71. find
  20. Dekang Lin. 1998a. Automatic retrieval and clustering of similar words. In COLING-A CL '98, pages 768-773. our card
  21. Dekang Lin. 1998b. An information theoretic definition of similarity. In Machine Learning: Proceedings of the Fiftheenth International Conference (ICML '98). find
  22. Jianhua Lin. 1991. Divergence measures based on the Shannon entropy. IEEE Transactions on Information Theory, 37(1):145-151. find
  23. Alpha K. Luk. 1995. Statistical sense disambiguation with relatively small corpora using dictionary definitions. In 33rd Annual Meeting of the ACL, pages 181-188. find
  24. Hwee Tou Ng and Hian Beng Lee. 1996. Integrating multiple knowledge sources to disambiguate word sense: An exemplar-based approach. In 3~th Annual Meeting of the ACL, pages 40–47. our card
  25. Hwee Tou Ng. 1997. Exemplar-based word sense disambiguation: Some recent improvements. In Second Conference on Empirical Methods in Natural Language Processing (EMNLP-2), pages 208-213. find
  26. C. Radhakrishna Rao. 1982. Diversity: Its measurement, decomposition, apportionment and analysis. SankyhZt: The Indian Journal of Statistics, 44(A):1-22. find
  27. Philip Resnik. 1995. Using information content to evaluate semantic similarity in a taxonomy. In Proceedings of IJCAI-95, pages 448-453. our card
  28. Gerard Salton and Michael J. McGill. 1983. Introduction to Modern Information Retrieval. find
  29. Frank Smadja, Kathleen R. McKeown, and Vasileios Hatzivassiloglou. 1996. Translating collocations for bilingual lexicons: A statistical approach. Computational Linguistics, 22(1):1-38. our card
  30. Craig Stanfill and David Waltz. 1986. Toward memory-based reasoning. Communications of the ACM, 29(12):1213-1228. find
  31. K. Sugawara, M. Nishimura, K. Toshioka, M. Okochi, and T. Kaneko. 1985. Isolated word recognition using hidden Markov models. In ICASSP 85, pages 1-4. find
  32. C. J. van Rijsbergen. 1979. Information Retrieval. Butterworths, second edition. find
  33. Jakub Zavrel and Walter Daelemans. 1997. Memory-based learning: Using similarity for smoothing. In 35th Annual Meeting of the A CL, pages 436-443. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/lee-1999-measures-distributional-similarity/