Semantic relatedness

Computational Measures of Semantic Relatedness are [http://cwl-projects.cogsci.rpi.edu/msr/ publically available] means for approximating the relative meaning of words/documents. These have been used for essay-grading by the Educational Testing Service, search engine technology, predicting which links people are likely to click on, etc.

* LSA (Latent semantic analysis) (+) vector-based, adds vectors to measure multi-word terms; (-) non-incremental vocabulary, long pre-processing times
* PMI (Pointwise Mutual Information) (+) large vocab, because it uses any search engine (like Google); (-) cannot measure relatedness between whole sentences or documents
* GLSA (Generalized Latent Semantic Analysis) (+) vector-based, adds vectors to measure multi-word terms; (-) non-incremental vocabulary, long pre-processing times
* ICAN (Incremental Construction of an Associative Network) (+) incremental, network-based measure, good for spreading activation, accounts for second-order relatedness; (-) cannot measure relatedness between multi-word terms, long pre-processing times
* NGD (Normalized Google Distance; see below) (+) large vocab, because it uses any search engine (like Google); (-) cannot measure relatedness between whole sentences or documents
* WordNet: (+) humanly constructed; (-) humanly constructed (not automatically learned), cannot measure relatedness between multi-word term, non-incremental vocabulary
* [http://www.cs.technion.ac.il/~gabr/papers/ijcai-2007-sim.pdf ESA (Explicit Semantic Analysis)] based on Wikipedia and the ODP
* [http://cwl-projects.cogsci.rpi.edu/papers/VGG08.pdf VGEM] (Vector Generation of an Explicitly-defined Multidimensional Semantic Space) (+) incremental vocab, can compare multi-word terms (-) performance depends on choosing specific dimensions
* [http://www.cogsci.rpi.edu/cogworks/publications/270_BLOSSOM_final.pdf BLOSSOM] (Best path Length On a Semantic Self-Organizing Map) (+) uses a Self Organizing Map to reduce high dimensional spaces, can use different vector representations (VGEM or word-document matrix), provides 'concept path linking' from one word to another (-) highly experimental, requires nontrivial SOM calculation

Semantic similarity measures

SimRank

Google distance

Google distance is a measure of semantic interrelatedness derived from the number of hits returned by the Google search engine for a given set of keywords. Keywords with the same or similar meanings in a natural language sense tend to be "close" in units of Google distance, while words with dissimilar meanings tend to be farther apart.

Specifically, the "normalized Google distance" between two search terms "x" and "y" is

:$operatorname\{NGD\}(x,y)\; =\; frac\{max\{log\; f(x),\; log\; f(y)\}\; -\; log\; f(x,y)\}\{log\; M\; -\; min\{log\; f(x),\; log\; f(y)$

where "M" is the total number of web pages searched by Google; "f"("x") and "f"("y") are the number of hits for search terms "x" and "y", respectively; and "f"("x", "y") is the number of web pages on which both "x" and "y" occur.

If the two search terms "x" and "y" never occur together on the same web page, but do occur separately, the normalized Google distance between them is infinite. If both terms always occur together, their NGD is zero.

See also

* Semantic differential

References

* Cilibrasi, R. & Vitanyi, P.M.B. (2006). Similarity of objects and the meaning of words. Proc. 3rd Conf. Theory and Applications of Models of Computation (TAMC), J.-Y. Cai, S. B. Cooper, and A. Li (Eds.), Lecture Notes in Computer Science, Vol. 3959, Springer-Verlag, Berlin.
* Dumais, S. (2003). Data-driven approaches to information access. Cognitive Science, 27(3), 491-524.
* Gabrilovich, E. and Markovitch, S. (2007). "Computing Semantic Relatedness using Wikipedia-based Explicit Semantic Analysis", Proceedings of The 20th International Joint Conference on Artificial Intelligence (IJCAI), Hyderabad, India, January 2007. [http://www.cs.technion.ac.il/~gabr/papers/ijcai-2007-sim.pdf]
* Juvina, I., van Oostendorp, H., Karbor, P., & Pauw, B. (2005). Towards modeling contextual information in web navigation. In B. G. Bara & L. Barsalou & M. Bucciarelli (Eds.), 27th Annual Meeting of the Cognitive Science Society, CogSci2005 (pp. 1078-1083). Austin, Tx: The Cognitive Science Society, Inc.
* Kaur, I. & Hornof, A.J. (2005). A Comparison of LSA, WordNet and PMI for Predicting User Click Behavior. Proceedings of the Conference on Human Factors in Computing, CHI 2005 (pp. 51-60).
* Landauer, T. K., & Dumais, S. T. (1997). A solution to Plato's problem: The latent semantic analysis theory of acquisition, induction, and representation of knowledge. Psychological Review, 104(2), 211-240.
* Landauer, T. K., Foltz, P. W., & Laham, D. (1998). Introduction to Latent Semantic Analysis. Discourse Processes, 25, 259-284.
* Lee, M. D., Pincombe, B., & Welsh, M. (2005). An empirical evaluation of models of text document similarity. In B. G. Bara & L. Barsalou & M. Bucciarelli (Eds.), 27th Annual Meeting of the Cognitive Science Society, CogSci2005 (pp. 1254-1259). Austin, Tx: The Cognitive Science Society, Inc.
* Lemaire, B., & Denhiére, G. (2004). Incremental construction of an associative network from a corpus. In K. D. Forbus & D. Gentner & T. Regier (Eds.), 26th Annual Meeting of the Cognitive Science Society, CogSci2004. Hillsdale, NJ: Lawrence Erlbaum Publisher.
* Lindsey, R., Veksler, V.D., Grintsvayg, A., Gray, W.D. (2007). The Effects of Corpus Selection on Measuring Semantic Relatedness. Proceedings of the 8th International Conference on Cognitive Modeling, Ann Arbor, MI.
* Pirolli, P. (2005). Rational analyses of information foraging on the Web. Cognitive Science, 29(3), 343-373.
* Pirolli, P., & Fu, W.-T. (2003). SNIF-ACT: A model of information foraging on the World Wide Web. Lecture Notes in Computer Science, 2702, 45-54.
* Turney, P. (2001). Mining the Web for Synonyms: PMI versus LSA on TOEFL. In L. De Raedt & P. Flach (Eds.), Proceedings of the Twelfth European Conference on Machine Learning (ECML-2001) (pp. 491-502). Freiburg, Germany.
* Veksler, V.D. & Gray, W.D. (2006). Test Case Selection for Evaluating Measures of Semantic Distance. Proceedings of the 28th Annual Meeting of the Cognitive Science Society, CogSci2006.

Google distance references

*Rudi Cilibrasi and Paul Vitanyi (2004). [http://arxiv.org/abs/cs.CL/0412098 , The Google Similarity Distance, ArXiv.org] or [http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/trans/tk/&toc=comp/trans/tk/2007/03/k3toc.xml&DOI=10.1109/TKDE.2007.48 The Google Similarity Distance, IEEE Trans. Knowledge and Data Engineering, 19:3(2007), 370-383.] .
* [http://www.newscientist.com/article.ns?id=dn6924 Google's search for meaning] at Newscientist.com.
*Jan Poland and Thomas Zeugmann (2006), [http://www-alg.ist.hokudai.ac.jp/~thomas/publications/dag_c2c_pz.pdf Clustering the Google Distance with Eigenvectors and Semidefinite Programming]
*Aarti Gupta and Tim Oates (2007), [http://www.ijcai.org/papers07/Papers/IJCAI07-261.pdf Using Ontologies and the Web to Learn Lexical Semantics] (Includes comparison of NGD to other algorithms.)
* Wilson Wong, Wei Liu and Mohammed Bennamoun (2007), [http://www.springerlink.com/content/u331u5122822046m/ Tree-Traversing Ant Algorithm for term clustering based on featureless similarities] , Journal of Data Mining and Knowledge Discovery (the use of NGD for term clustering)

External links

* [http://cwl-projects.cogsci.rpi.edu/msr/ Measures of Semantic Relatedness]
* [http://wn-similarity.sourceforge.net WordNet-Similarity] , an open source package for computing the similarity and relatedness of concepts found in WordNet