creators_name: Turney, Peter D. creators_id: peter.turney@nrc-cnrc.gc.ca type: journalp datestamp: 2009-01-05 23:58:22 lastmod: 2011-03-11 08:57:17 metadata_visibility: show title: The Latent Relation Mapping Engine: Algorithm and Experiments ispublished: pub subjects: comp-sci-lang subjects: ling-comput subjects: ling-sem subjects: comp-sci-mach-learn subjects: comp-sci-art-intel full_text_status: public keywords: analogy, metaphor, semantic relations, structure mapping, vector space models, analogical mapping, latent relational analysis note: NRC-50738 abstract: Many AI researchers and cognitive scientists have argued that analogy is the core of cognition. The most influential work on computational modeling of analogy-making is Structure Mapping Theory (SMT) and its implementation in the Structure Mapping Engine (SME). A limitation of SME is the requirement for complex hand-coded representations. We introduce the Latent Relation Mapping Engine (LRME), which combines ideas from SME and Latent Relational Analysis (LRA) in order to remove the requirement for hand-coded representations. LRME builds analogical mappings between lists of words, using a large corpus of raw text to automatically discover the semantic relations among the words. We evaluate LRME on a set of twenty analogical mapping problems, ten based on scientific analogies and ten based on common metaphors. LRME achieves human-level performance on the twenty problems. We compare LRME with a variety of alternative approaches and find that they are not able to reach the same level of performance. date: 2008-12-22 date_type: published publication: Journal of Artificial Intelligence Research volume: 33 publisher: AI Access Foundation pagerange: 615-655 refereed: TRUE referencetext: Ando, R. K. (2000). Latent semantic space: Iterative scaling improves precision of inter-document similarity measurement. In Proceedings of the 23rd Annual ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR-2000), pp. 216–223. Banko, M., & Etzioni, O. (2007). Strategies for lifelong knowledge extraction from the web. In Proceedings of the 4th International Conference on Knowledge Capture (K-CAP 2007), pp. 95–102. Bullinaria, J., & Levy, J. (2007). Extracting semantic representations from word co-occurrence statistics: A computational study. Behavior Research Methods, 39 (3),510–526. Büttcher, S., & Clarke, C. (2005). Efficiency vs. effectiveness in terabyte-scale information retrieval. In Proceedings of the 14th Text REtrieval Conference (TREC 2005), Gaithersburg, MD. Chalmers, D. J., French, R. M., & Hofstadter, D. R. (1992). High-level perception, representation, and analogy: A critique of artificial intelligence methodology. Journal of Experimental & Theoretical Artificial Intelligence, 4 (3), 185–211. Deerwester, S. C., Dumais, S. T., Landauer, T. K., Furnas, G. W., & Harshman, R. A. (1990). Indexing by latent semantic analysis. 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. In Proceedings of the AAAI 1995 Spring Symposium Series: Representation and Acquisition of Lexical Knowledge: Polysemy, Ambiguity and Generativity, pp. 27–32. Evans, T. (1964). A heuristic program to solve geometric-analogy problems. In Proceedings of the Spring Joint Computer Conference, pp. 327–338. Falkenhainer, B., Forbus, K. D., & Gentner, D. (1989). The structure-mapping engine: Algorithm and examples. Artificial Intelligence, 41 (1), 1–63. Firth, J. R. (1957). A synopsis of linguistic theory 1930–1955. In Studies in Linguistic Analysis, pp. 1–32. Blackwell, Oxford. Forbus, K., Usher, J., Lovett, A., Lockwood, K., & Wetzel, J. (2008). Cogsketch: Open domain sketch understanding for cognitive science research and for education. In Proceedings of the Fifth Eurographics Workshop on Sketch-Based Interfaces and Modeling, Annecy, France. Forbus, K. D., Riesbeck, C., Birnbaum, L., Livingston, K., Sharma, A., & Ureel, L. (2007). A prototype system that learns by reading simplified texts. In AAAI Spring Symposium on Machine Reading, Stanford University, California. French, R. (1995). The Subtlety of Sameness: A Theory and Computer Model of Analogy-Making. MIT Press, Cambridge, MA. French, R. M. (2002). The computational modeling of analogy-making. Trends in Cognitive Sciences, 6 (5), 200–205. Gärdenfors, P. (2004). Conceptual Spaces: The Geometry of Thought. MIT Press. Gentner, D. (1983). Structure-mapping: A theoretical framework for analogy. Cognitive Science, 7 (2), 155–170. Gentner, D. (1991). Language and the career of similarity. In Gelman, S., & Byrnes, J. (Eds.), Perspectives on Thought and Language: Interrelations in Development, pp. 225–277. Cambridge University Press. Gentner, D. (2003). Why we’re so smart. In Gentner, D., & Goldin-Meadow, S. (Eds.), Language in Mind: Advances in the Study of Language and Thought, pp. 195–235. MIT Press. Gentner, D., Bowdle, B. F., Wolff, P., & Boronat, C. (2001). Metaphor is like analogy. In Gentner, D., Holyoak, K. J., & Kokinov, B. N. (Eds.), The analogical mind: Perspectives from Cognitive Science, pp. 199–253. MIT Press, Cambridge, MA. Gildea, D., & Jurafsky, D. (2002). Automatic labeling of semantic roles. Computational Linguistics, 28 (3), 245–288. Girju, R., Nakov, P., Nastase, V., Szpakowicz, S., Turney, P., & Yuret, D. (2007). Semeval-2007 task 04: Classification of semantic relations between nominals. In Proceedings of the Fourth International Workshop on Semantic Evaluations (SemEval 2007), pp. 13–18, Prague, Czech Republic. Golub, G. H., & Van Loan, C. F. (1996). Matrix Computations (Third edition). Johns Hopkins University Press, Baltimore, MD. Hawkins, J., & Blakeslee, S. (2004). On Intelligence. Henry Holt. Hirst, G., & St-Onge, D. (1998). Lexical chains as representations of context for the detection and correction of malapropisms. In Fellbaum, C. (Ed.), WordNet: An Electronic Lexical Database, pp. 305–332. MIT Press. Hofmann, T. (1999). Probabilistic Latent Semantic Indexing. In Proceedings of the 22nd Annual ACM Conference on Research and Development in Information Retrieval (SIGIR ’99), pp. 50–57, Berkeley, California. Hofstadter, D. (2001). Epilogue: Analogy as the core of cognition. In Gentner, D., Holyoak, K. J., & Kokinov, B. N. (Eds.), The Analogical Mind: Perspectives from Cognitive Science, pp. 499–538. MIT Press. Hofstadter, D., & FARG (1995). Fluid Concepts and Creative Analogies: Computer Models of the Fundamental Mechanisms of Thought. Basic Books, New York, NY. Holyoak, K., & Thagard, P. (1989). Analogical mapping by constraint satisfaction. Cognitive Science, 13, 295–355. Holyoak, K., & Thagard, P. (1995). Mental Leaps. MIT Press. Hummel, J., & Holyoak, K. (1997). Distributed representations of structure: A theory of analogical access and mapping. Psychological Review, 104, 427–466. Jiang, J. J., & Conrath, D. W. (1997). Semantic similarity based on corpus statistics and lexical taxonomy. In Proceedings of the International Conference on Research in Computational Linguistics (ROCLING X), pp. 19–33, Tapei, Taiwan. Kilgarriff, A. (1997). I don’t believe in word senses. Computers and the Humanities, 31, 91–113. Lakoff, G., & Johnson, M. (1980). Metaphors We Live By. University Of Chicago Press. Landauer, T. K., & 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 (2), 211–240. Leacock, C., & Chodrow, M. (1998). Combining local context and WordNet similarity for word sense identification. In Fellbaum, C. (Ed.), WordNet: An Electronic Lexical Database. MIT Press. Lee, D. D., & Seung, H. S. (1999). Learning the parts of objects by nonnegative matrix factorization. Nature, 401, 788–791. Lepage, Y. (1998). Solving analogies on words: An algorithm. In Proceedings of the 36th Annual Conference of the Association for Computational Linguistics, pp. 728–735. Lepage, Y., & Denoual, E. (2005). Purest ever example-based machine translation: Detailed presentation and assessment. Machine Translation, 19 (3), 251–282. Lin, D. (1998). An information-theoretic definition of similarity. In Proceedings of the 15th International Conference on Machine Learning (ICML-98). Martin, J. H. (1992). Computer understanding of conventional metaphoric language. Cognitive Science, 16 (2), 233–270. Marx, Z., Dagan, I., Buhmann, J., & Shamir, E. (2002). Coupled clustering: A method for detecting structural correspondence. Journal of Machine Learning Research, 3, 747–780. Mason, Z. (2004). CorMet: A computational, corpus-based conventional metaphor extraction system. Computational Linguistics, 30 (1), 23–44. Minsky, M. (1986). The Society of Mind. Simon & Schuster, New York, NY. Mitchell, M. (1993). Analogy-Making as Perception: A Computer Model. MIT Press, Cambridge, MA. Nastase, V., & Szpakowicz, S. (2003). Exploring noun-modifier semantic relations. In Fifth International Workshop on Computational Semantics (IWCS-5), pp. 285–301, Tilburg, The Netherlands. Reitman, W. R. (1965). Cognition and Thought: An Information Processing Approach. John Wiley and Sons, New York, NY. Resnik, P. (1995). Using information content to evaluate semantic similarity in a taxonomy. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI-95), pp. 448–453, San Mateo, CA. Morgan Kaufmann. Rosario, B., & Hearst, M. (2001). Classifying the semantic relations in noun-compounds via a domain-specific lexical hierarchy. In Proceedings of the 2001 Conference on Empirical Methods in Natural Language Processing (EMNLP-01), pp. 82–90. Santorini, B. (1990). Part-of-speech tagging guidelines for the Penn Treebank Project. Tech. rep., Department of Computer and Information Science, University of Pennsylvania. (3rd revision, 2nd printing). Scholkopf, B., Smola, A. J., & Muller, K.-R. (1997). Kernel principal component analysis. In Proceedings of the International Conference on Artificial Neural Networks (ICANN-1997), pp. 583-588, Berlin. Turney, P. D. (2001). Mining the Web for synonyms: PMI-IR versus LSA on TOEFL. In Proceedings of the Twelfth European Conference on Machine Learning (ECML-01), pp. 491–502, Freiburg, Germany. Turney, P. D. (2005). Measuring semantic similarity by latent relational analysis. In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI-05), pp. 1136–1141, Edinburgh, Scotland. Turney, P. D. (2006). Similarity of semantic relations. Computational Linguistics, 32 (3), 379–416. Turney, P. D. (2008). A uniform approach to analogies, synonyms, antonyms, and associations. In Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008), pp. 905–912, Manchester, UK. Turney, P. D., & Littman, M. L. (2005). Corpus-based learning of analogies and semantic relations. Machine Learning, 60 (1–3), 251–278. Turney, P. D., Littman, M. L., Bigham, J., & Shnayder, V. (2003). Combining independent modules to solve multiple-choice synonym and analogy problems. In Proceedings of the International Conference on Recent Advances in Natural Language Processing (RANLP-03), pp. 482–489, Borovets, Bulgaria. van Rijsbergen, C. J. (2004). The Geometry of Information Retrieval. Cambridge University Press, Cambridge, UK. Veale, T. (2003). The analogical thesaurus. In Proceedings of the 15th Innovative Applications of Artificial Intelligence Conference (IAAI 2003), pp. 137–142, Acapulco, Mexico. Veale, T. (2004). WordNet sits the SAT: A knowledge-based approach to lexical analogy. In Proceedings of the 16th European Conference on Artificial Intelligence (ECAI 2004), pp. 606–612, Valencia, Spain. Widdows, D. (2004). Geometry and Meaning. Center for the Study of Language and Information, Stanford, CA. Yan, J., & Forbus, K. D. (2005). Similarity-based qualitative simulation. In Proceedings of the 27th Annual Meeting of the Cognitive Science Society, Stresa, Italy. citation: Turney, Peter D. (2008) The Latent Relation Mapping Engine: Algorithm and Experiments. [Journal (Paginated)] document_url: http://cogprints.org/6305/1/NRC-50738.pdf