Cogprints

Human-Level Performance on Word Analogy Questions by Latent Relational Analysis

Turney, Peter D. (2004) Human-Level Performance on Word Analogy Questions by Latent Relational Analysis. [Departmental Technical Report] (Unpublished)

Full text available as:

[img]
Preview
 PDF
217Kb

Abstract

This paper introduces Latent Relational Analysis (LRA), a method for measuring relational similarity. LRA has potential applications in many areas, including information extraction, word sense disambiguation, machine translation, and information retrieval. Relational similarity is correspondence between relations, in contrast with attributional similarity, which is correspondence between attributes. When two words have a high degree of attributional similarity, we call them synonyms. When two pairs of words have a high degree of relational similarity, we say that their relations are analogous. For example, the word pair mason/stone is analogous to the pair carpenter/wood; the relations between mason and stone are highly similar to the relations between carpenter and wood. Past work on semantic similarity measures has mainly been concerned with attributional similarity. For instance, Latent Semantic Analysis (LSA) can measure the degree of similarity between two words, but not between two relations. Recently the Vector Space Model (VSM) of information retrieval has been adapted to the task of measuring relational similarity, achieving a score of 47% on a collection of 374 college-level multiple-choice word analogy questions. In the VSM approach, the relation between a pair of words is characterized by a vector of frequencies of predefined patterns in a large corpus. LRA extends the VSM approach in three ways: (1) the patterns are derived automatically from the corpus (they are not predefined), (2) the Singular Value Decomposition (SVD) is used to smooth the frequency data (it is also used this way in LSA), and (3) automatically generated synonyms are used to explore reformulations of the word pairs. LRA achieves 56% on the 374 analogy questions, statistically equivalent to the average human score of 57%. On the related problem of classifying noun-modifier relations, LRA achieves similar gains over the VSM, while using a smaller corpus.

Item Type:Departmental Technical Report
Keywords:analogies, semantic relations, vector space model, noun-modifier expressions, latent relational analysis
Subjects:Computer Science > Language
Linguistics > Computational Linguistics
Linguistics > Semantics
Computer Science > Machine Learning
ID Code:3981
Deposited By: Turney, Peter
Deposited On:11 Dec 2004
Last Modified:11 Mar 2011 08:55

References in Article

Select the SEEK icon to attempt to find the referenced article. If it does not appear to be in cogprints you will be forwarded to the paracite service. Poorly formated references will probably not work.

Ando, R.K. (2000). Latent semantic space: Iterative scaling improves inter-document similarity measurement. Proceedings of the 23rd Annual International ACM SIGIR, 216-223.

Baeza-Yates, R., and Ribeiro-Neto, B. (1999). Modern Information Retrieval. Addison-Wesley.

Banerjee, S., and Pedersen, T. (2003). Extended gloss overlaps as a measure of semantic relatedness. Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03). Acapulco, Mexico, 805-810.

Barker, K., and Szpakowicz, S. (1998). Semi-automatic recognition of noun modifier relationships. Proceedings of the 17th International Conference on Computational Linguistics and the 36th Annual Meeting of the Association for Computational Linguistics (COLING-ACL’98), Montréal, Québec, 96-102.

Barzilay, R., and Elhadad, M. (1997). Using lexical chains for text summarization. Proceedings of the ACL’97/EACL’97 Workshop on Intelligent Scalable Text Summarization, 10-17.

Berland, M. and Charniak, E. (1999). Finding parts in very large corpora. Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics (ACL ‘99). ACL, New Brunswick NJ, 57-64.

Berry, M.W. (1992). Large scale singular value computations. International Journal of Supercomputer Applications, 6(1), 13-49.

Budanitsky, A., and Hirst, G. (2001). Semantic distance in WordNet: An experimental, application-oriented evaluation of five measures. Proceedings of the Workshop on WordNet and Other Lexical Resources, Second Meeting of the North American Chapter of the Association for Computational Linguistics, Pittsburgh, 29-34.

Church, K.W., And Hanks, P. (1989). Word association norms, mutual information and lexicography. Proceedings of the 27th Annual Conference of the Association of Computational Linguistics. Association for Computational Linguistics, New Brunswick, NJ, 76-83.

Claman, C. (2000). 10 Real SATs. College Entrance Examination Board.

Clarke, C.L.A., Cormack, G.V., and Palmer, C.R. (1998). An overview of MultiText. ACM SIGIR Forum, 32(2), 14-15.

Daganzo, C.F. (1994). The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory. Transportation Research Part B: Methodological, 28(4), 269-287.

Deerwester, S., Dumais, S.T., Furnas, G.W., Landauer, T.K., and Harshman, R. (1990). Indexing by latent semantic indexing. Journal of the American Society for Information Science (JASIS), 41(6), 391-407.

Dolan, W.B. (1995). Metaphor as an emergent property of machine-readable dictionaries. Proceedings of the AAAI 1995 Spring Symposium Series: Representation and Acquisition of Lexical Knowledge: Polysemy, Ambiguity and Generativity, 27-32.

Dumais, S.T. (1990). Enhancing Performance in Latent Semantic Indexing (LSI) Retrieval. TM-ARH-017527 Technical Report, Bellcore.

Dumais, S.T. (1993). Latent semantic indexing (LSI) and TREC-2. Proceedings of the Second Text REtrieval Conference (TREC-2), D.K. Harman, Ed., National Institute of Standards and Technology, 105-115.

Dunning, T. (1993). Accurate methods for the statistics of surprise and coincidence. Computational Linguistics, 19, 61-74.

Falkenhainer, B., Forbus, K.D., and Gentner, D. (1989). The structure-mapping engine: Algorithm and examples. Artificial Intelligence, 41(1), 1-63.

Falkenhainer, B. (1990). Analogical interpretation in context. Proceedings of the Twelfth Annual Conference of the Cognitive Science Society, Lawrence Erlbaum Associates, 69-76.

Fellbaum, C. (editor). (1998). WordNet: An Electronic Lexical Database. MIT Press.

Foltz, P.W., Kintsch, W., and Landauer, T.K. (1998). The measurement of textual coherence with latent semantic analysis. Discourse Processes, 25, 285-307.

Foltz, P.W., Laham, D., and Landauer, T.K. (1999). Automated essay scoring: Applications to educational technology. Proceedings of the ED-MEDIA ‘99 Conference, Association for the Advancement of Computing in Education, Charlottesville.

French, R.M. (2002). The computational modeling of analogy-making. Trends in Cognitive Sciences, 6(5), 200-205.

Gentner, D. (1983). Structure-mapping: A theoretical framework for analogy. Cognitive Science, 7(2), 155-170.

Gentner, D., Bowdle, B., Wolff, P., and Boronat, C. (2001). Metaphor is like analogy. In D. Gentner, K.J. Holyoak, and B. Kokinov (Eds.), The Analogical Mind: Perspectives from Cognitive Science. Cambridge, MA: MIT Press.

Gildea, D., Jurafsky, D. (2002). Automatic labeling of semantic roles. Computational Linguistics, 28(3), 245-288.

Golub, G.H., and Van Loan, C.F. (1996). Matrix Computations. Third edition. Johns Hopkins University Press, Baltimore, MD.

Harman, D. (1986). An experimental study of factors important in document ranking. Proceedings of the Ninth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'86). Pisa, Italy. 186-193.

Hearst, M.A. (1992a). Automatic acquisition of hyponyms from large text corpora. Proceedings of the Fourteenth International Conference on Computational Linguistics, Nantes, France, 539-545.

Hearst, M.A. (1992b). Direction-based text interpretation as an information access refinement. In P. Jacobs (Ed.), Text-Based Intelligent Systems: Current Research and Practice in Information Extraction and Retrieval. Mahwah, NJ: Lawrence Erlbaum Associates.

Hofmann, T. (1999). Probabilistic latent semantic indexing. Proceedings of the 22nd Annual ACM Conference on Research and Development in Information Retrieval (SIGIR ‘99), Berkeley, California, 50-57.

Hofstadter, D., and the Fluid Analogies Research Group (1995). Fluid Concepts and Creative Analogies: Computer Models of the Fundamental Mechanisms of Thought. New York: Basic Books.

Jarmasz, M. and Szpakowicz, S. (2003). Roget’s thesaurus and semantic similarity. Proceedings of the International Conference on Recent Advances in Natural Language Processing (RANLP-03), Borovets, Bulgaria, 212-219.

Jiang, J., and Conrath, D. (1997). Semantic similarity based on corpus statistics and lexical taxonomy. Proceedings of the International Conference on Research in Computational Linguistics (ROCLING X), Tapei, Taiwan,19-33.

Lakoff, G., and Johnson, M. (1980). Metaphors We Live By. University of Chicago Press.

Lakoff, G. (1987). Women, Fire, and Dangerous Things. University of Chicago Press.

Landauer, T.K., and Dumais, S.T. (1997). A solution to Plato’s problem: The latent semantic analysis theory of the acquisition, induction, and representation of knowledge. Psychological Review, 104, 211-240.

Lee, D.D., Seung, H.S. (1999). Learning the parts of objects by nonnegative matrix factorization. Nature, 401, 788-791.

Lesk, M.E. (1969). Word-word associations in document retrieval systems. American Documentation, 20(1): 27-38.

Lesk, M.E. (1986). Automatic sense disambiguation using machine readable dictionaries: How to tell a pine cone from a ice cream cone. Proceedings of ACM SIGDOC ’86, 24-26.

Lewis, D.D. (1991). Evaluating text categorization. Proceedings of the Speech and Natural Language Workshop, Asilomar, 312-318.

Lin, D. (1998a). An information-theoretic definition of similarity. Proceedings of the Fifteenth International Conference on Machine Learning (ICML ‘98), 296-304.

Lin, D. (1998b). Automatic retrieval and clustering of similar words. Proceedings of the 36th Annual Meeting of the Association for Computational Linguistics and the 17th International Conference on Computational Linguistics (COLING-ACL ‘98), Montreal, Canada, 768-774.

Lin, D. (1998c). Dependency-based evaluation of MINIPAR. Proceedings of the Workshop at LREC’98 (First International Conference on Language Resources and Evaluation) on the Evaluation of Parsing Systems, Granada, Spain.

Martin, J. (1992). Computer understanding of conventional metaphoric language. Cognitive Science, 16, 233-270.

Medin, D.L., Goldstone, R.L., and Gentner, D. (1990). Similarity involving attributes and relations: Judgments of similarity and difference are not inverses. Psychological Science, 1(1), 64-69.

Medin, D.L., Goldstone, R.L., and Gentner, D. (1993). Respects for similarity. Psychological Review, 100(2), 254-278.

Mel’cuk, I. (1988). Dependency Syntax: Theory and Practice. New York: State University of New York Press.

Morris, J., and Hirst, G. (1991). Lexical cohesion computed by thesaural relations as an indicator of the structure of text. Computational Linguistics, 17(1), 21-48.

Nastase, V., and Szpakowicz, S. (2003). Exploring noun-modifier semantic relations. Fifth International Workshop on Computational Semantics (IWCS-5), Tilburg, The Netherlands, 285-301.

Paice, C.D., and Black, W.J. (2003). A three-pronged approach to the extraction of key terms and semantic roles. Proceedings of the International Conference on Recent Advances in Natural Language Processing (RANLP-03), Borovets, Bulgaria. 357-363.

Pantel, P., and Lin, D. (2002). Discovering word senses from text. Proceedings of ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 613-619.

Patwardhan, S., Banerjee, S., and Pedersen, T. (2003). Using measures of semantic relatedness for word sense disambiguation. Proceedings of the Fourth International Conference on Intelligent Text Processing and Computational Linguistics, Mexico City.

Rehder, B., Schreiner, M.E., Wolfe, M.B., Laham, D., Landauer, T.K., and Kintsch, W. (1998). Using latent semantic analysis to assess knowledge: Some technical considerations. Discourse Processes, 25, 337-354.

Reitman, W.R. (1965). Cognition and Thought: An Information Processing Approach. New York, NY: John Wiley and Sons.

Resnik, P. (1995). Using information content to evaluate semantic similarity in a taxonomy. Proceedings of the 14th International Joint Conference on Artificial Intelligence. Morgan Kaufmann, San Mateo, CA, 448-453.

Rosario, B., and Hearst, M. (2001). Classifying the semantic relations in noun-compounds via a domain-specific lexical hierarchy. Proceedings of the 2001 Conference on Empirical Methods in Natural Language Processing (EMNLP-01), 82-90.

Rosario, B, Hearst, M., and Fillmore, C. (2002). The descent of hierarchy, and selection in relational semantics. Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL ‘02), Philadelphia, PA, 417-424.

Ruge, G. (1992). Experiments on linguistically-based term associations. Information Processing and Management, 28(3), 317-332.

Ruge, G. (1997). Automatic detection of thesaurus relations for information retrieval applications. Foundations of Computer Science: Potential - Theory - Cognition, C. Freksa, M. Jantzen, R. Valk (Eds.), Lecture Notes in Computer Science, Springer-Verlag, 499-506.

Salton, G., and McGill, M.J. (1983). Introduction to Modern Information Retrieval. McGraw-Hill, New York.

Salton, G. (1989). Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer. Addison-Wesley, Reading, Massachusetts.

Salton, G., and Buckley, C. (1988). Term-weighting approaches in automatic text retrieval. Information Processing and Management, 24(5), 513-523.

Scholkopf, B., Smola, A.J., and Muller, K. (1997). Kernel principal component analysis. Proceedings of the International Conference on Artificial Neural Networks (ICANN-1997), Berlin, 583-588.

Smadja, F. (1993). Retrieving collocations from Text: Xtract. Computational Linguistics, 19, 143-177.

Terra, E., and Clarke, C.L.A. (2003). Frequency estimates for statistical word similarity measures. Proceedings of the Human Language Technology and North American Chapter of Association of Computational Linguistics Conference 2003 (HLT/NAACL 2003), 244–251.

Turney, P.D. (2001). Mining the Web for synonyms: PMI-IR versus LSA on TOEFL. Proceedings of the Twelfth European Conference on Machine Learning. Springer-Verlag, Berlin, 491-502.

Turney, P.D. (2002). Thumbs up or thumbs down? Semantic orientation applied to unsupervised classification of reviews. Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL’02). Philadelphia, Pennsylvania, 417-424.

Turney, P.D. (2003). Coherent keyphrase extraction via Web mining. Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03). Acapulco, Mexico, 434-439.

Turney, P.D. (2004). Word sense disambiguation by Web mining for word co-occurrence probabilities. Proceedings of the Third International Workshop on the Evaluation of Systems for the Semantic Analysis of Text (SENSEVAL-3), Barcelona, Spain, 239-242.

Turney, P.D., Littman, M.L., Bigham, J., and Shnayder, V. (2003). Combining independent modules to solve multiple-choice synonym and analogy problems. Proceedings of the International Conference on Recent Advances in Natural Language Processing (RANLP-03). Borovets, Bulgaria, 482-489.

Turney, P.D., and Littman, M.L. (2003a). Measuring praise and criticism: Inference of semantic orientation from association. ACM Transactions on Information Systems (TOIS), 21 (4), 315-346.

Turney, P.D., and Littman, M.L. (2003b). Learning Analogies and Semantic Relations, National Research Council, Institute for Information Technology, Technical Report ERB-1103.

Turney, P.D., and Littman, M.L. (2005). Corpus-based learning of analogies and semantic relations. Machine Learning, in press.

Vanderwende, L. (1994). Algorithm for automatic interpretation of noun sequences. Proceedings of the Fifteenth International Conference on Computational Linguistics, Kyoto, Japan, 782-788.

Veale, T. (2003). The analogical thesaurus. Proceedings of the 15th Innovative Applications of Artificial Intelligence Conference (IAAI 2003), Acapulco, Mexico, 137-142.

Yarowsky, D. (1993). One sense per collocation. Proceedings of the ARPA Human Language Technology Workshop. Princeton, 266-271.

Yarowsky, D. (1995). Unsupervised word sense disambiguation rivaling supervised methods. Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics. Cambridge, MA, 189-196.

Yi, J., Lin, H., Alvarez, L., and Horowitz, R. (2003). Stability of macroscopic traffic flow modeling through wavefront expansion. Transportation Research Part B: Methodological, 37(7), 661-679.

Zhang, H.M. (2003). Driver memory, traffic viscosity and a viscous vehicular traffic flow model. Transportation Research Part B: Methodological, 37(1), 27-41.

Metadata

Repository Staff Only: item control page

Cogprints is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.