Measuring the similarity between implicit semantic relations using web search engines

ABSTRACT

Measuring the similarity between implicit semantic relations is an important task in information retrieval and natural language processing. For example, consider the situation where you know an entity-pair (e.g. Google, YouTube), between which a particular relation holds (e.g. acquisition), and you are interested in retrieving other entity-pairs for which the same relation holds (e.g. Yahoo, Inktomi). Existing keyword-based search engines cannot be directly applied in this case because in keyword-based search, the goal is to retrieve documents that are relevant to the words used in the query -- not necessarily to the relations implied by a pair of words. Accurate measurement of relational similarity is an important step in numerous natural language processing tasks such as identification of word analogies, and classification of noun-modifier pairs. We propose a method that uses Web search engines to efficiently compute the relational similarity between two pairs of words. Our method consists of three components: representing the various semantic relations that exist between a pair of words using automatically extracted lexical patterns, clustering the extracted lexical patterns to identify the different semantic relations implied by them, and measuring the similarity between different semantic relations using an inter-cluster correlation matrix. We propose a pattern extraction algorithm to extract a large number of lexical patterns that express numerous semantic relations. We then present an efficient clustering algorithm to cluster the extracted lexical patterns. Finally, we measure the relational similarity between word-pairs using inter-cluster correlation. We evaluate the proposed method in a relation classification task. Experimental results on a dataset covering multiple relation types show a statistically significant improvement over the current state-of-the-art relational similarity measures.

REFERENCES

• 1: Ken Barker , Stan Szpakowicz, Semi-automatic recognition of noun modifier relationships, Proceedings of the 17th international conference on Computational linguistics, August 10-14, 1998, Montreal, Quebec, Canada
• 2: Matthew Berland , Eugene Charniak, Finding parts in very large corpora, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.57-64, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034697]
• 3: R. Bhagat and D. Ravichandran. Large scale acquisition of paraphrases for learning surface patterns. In Proc. of ACL'08: HLT, pages 674--682, 2008.
• 4: R. C. Bunescu and R. Mooney. Learning to extract relations from the web using minimal supervision. In Proc. of ACL'07, pages 576--583, 2007.
• 5: P. Cimiano and J. Wenderoth. Automatic acquisition of ranked qualia structures from the web. In Proc. of ACL'07, pages 888--895, 2007.
• 6: Aron Culotta , Jeffrey Sorensen, Dependency tree kernels for relation extraction, Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, p.423-es, July 21-26, 2004, Barcelona, Spain [doi>10.3115/1218955.1219009]
• 7: Douglass R. Cutting , David R. Karger , Jan O. Pedersen, Constant interaction-time scatter/gather browsing of very large document collections, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.126-134, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160706]
• 8: D. Davidov and A. Rappoport. Classification of semantic relationships between nominals using pattern clusters. In Proc. of the ACL'08, 2008.
• 9: D. Davidov and A. Rappoport. Unsupervised discovery of generic relationships using pattern clusters and its evaluation by automatically generated sat analogy questions. In Proc. of ACL'08-HLT, pages 692--700, 2008.
• 10: Brian Falkenhainer , Kenneth D. Forbus , Dedre Gentner, The structure-mapping engine: algorithm and examples, Artificial Intelligence, v.41 n.1, p.1-63, Nov. 1989 [doi>10.1016/0004-3702(89)90077-5]
• 11: Z. Harris. Distributional structure. Word, 10:146--162, 1954.
• 12: Marti A. Hearst, Automatic acquisition of hyponyms from large text corpora, Proceedings of the 14th conference on Computational linguistics, August 23-28, 1992, Nantes, France [doi>10.3115/992133.992154]
• 13: Dekang Lin, Automatic retrieval and clustering of similar words, Proceedings of the 17th international conference on Computational linguistics, p.768-774, August 10-14, 1998, Montreal, Quebec, Canada
• 14: Dekang Lin , Patrick Pantel, DIRT @SBT@discovery of inference rules from text, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.323-328, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502559]
• 15: Zvika Marx , Ido Dagan , Joachim M. Buhmann , Eli Shamir, Coupled clustering: a method for detecting structural correspondence, The Journal of Machine Learning Research, 3, 3/1/2003
• 16: D. Medin, R. Goldstone, and D. Gentner. Respects for similarity. Psychological Review, 6(1):1--28, 1991.
• 17: G. Miller, R. Beckwith, C. Fellbaum, D. Gross, and K. Miller. Introducton to wordnet: An on-line lexical database. International Journal of Lexicography, 3:238--244, 1990.
• 18: P. Nakov and M. Hearst. Solving relational similarity problems using the web as a corpus. In Proc. of ACL'08-HLT, pages 452--460, 2008.
• 19: M. Pasca, D. Lin, J. Bigham, A. Lifchits, and A. Jain. Organizing and searching the world wide web of facts - step one: the one-million fact extraction challenge. In Proc. of AAAI'06, pages 1400--1405, 2006.
• 20: Jian Pei , Jiawei Han , Behzad Mortazavi-Asl , Jianyong Wang , Helen Pinto , Qiming Chen , Umeshwar Dayal , Mei-Chun Hsu, Mining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach, IEEE Transactions on Knowledge and Data Engineering, v.16 n.11, p.1424-1440, November 2004 [doi>10.1109/TKDE.2004.77]
• 21: Deepak Ravichandran , Eduard Hovy, Learning surface text patterns for a Question Answering system, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania [doi>10.3115/1073083.1073092]
• 22: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 23: M. Schultz and T. Joachims. Learning a distance metric from relative comparisons. In Proc. of NIPS'03, 2003.
• 24: Hinrich Schütze, Automatic word sense discrimination, Computational Linguistics, v.24 n.1, March 1998
• 25: R. Snow, D. Jurafsky, and A. Ng. Learning syntactic patterns for automatic hypernym discovery. In Proc. of Advances in Neural Information Processing Systems (NIPS) 17, pages 1297--1304, 2005.
• 26: P. Turney. Measuring semantic similarity by latent relational analysis. In Proc. of IJCAI'05, pages 1136--1141, 2005.
• 27: Peter D. Turney, Expressing implicit semantic relations without supervision, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, p.313-320, July 17-18, 2006, Sydney, Australia [doi>10.3115/1220175.1220215]
• 28: Peter D. Turney, Similarity of Semantic Relations, Computational Linguistics, v.32 n.3, p.379-416, September 2006 [doi>10.1162/coli.2006.32.3.379]
• 29: Peter D. Turney , Michael L. Littman, Corpus-based Learning of Analogies and Semantic Relations, Machine Learning, v.60 n.1-3, p.251-278, September 2005 [doi>10.1007/s10994-005-0913-1]
• 30: P. Turney, M. Littman, J. Bigham, and V. Shnayder. Combining independent modules to solve multiple-choice synonym and analogy problems. In Proc. of RANLP'03, pages 482--486, 2003.
• 31: A. Tversky. Features of similarity. Psychological Review, 84(4):327--352, 1997.
• 32: T. Veale. The analogical thesaurus. In Proc. of 15th Innovative Applications of Artificial Intelligence Conference (IAAI'03), pages 137--142, 2003.
• 33: T. Veale. Wordnet sits the sat: A knowledge-based approach to lexical analogy. In Proc. of ECAI'04, pages 606--612, 2004.
• 34: T. Veale and M. T. Keane. The competence of structure mapping on hard analogies. In Proc. of IJCAI'03, 2003.
• 35: K. Weinberger, J. Blitzer, and L. Saul. Distance metric learning for large margin nearest neighbor classification. In Proc. of NIPS'05, pages 1473--1480, 2005.
• 36: Dmitry Zelenko , Chinatsu Aone , Anthony Richardella, Kernel methods for relation extraction, The Journal of Machine Learning Research, 3, 3/1/2003

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms

Keywords:
relational similarity measures, web mining