Anchor text mining for translation of Web queries: A transitive translation approach

ABSTRACT

To discover translation knowledge in diverse data resources on the Web, this article proposes an effective approach to finding translation equivalents of query terms and constructing multilingual lexicons through the mining of Web anchor texts and link structures. Although Web anchor texts are wide-scoped hypertext resources, not every particular pair of languages contains sufficient anchor texts for effective extraction of translations for Web queries. For more generalized applications, the approach is designed based on a transitive translation model. The translation equivalents of a query term can be extracted via its translation in an intermediate language. To reduce interference from translation errors, the approach further integrates a competitive linking algorithm into the process of determining the most probable translation. A series of experiments has been conducted, including performance tests on term translation extraction, cross-language information retrieval, and translation suggestions for practical Web search services, respectively. The obtained experimental results have shown that the proposed approach is effective in extracting translations of unknown queries, is easy to combine with the probabilistic retrieval model to improve the cross-language retrieval performance, and is very useful when the considered language pairs lack a sufficient number of anchor texts. Based on the approach, an experimental system called LiveTrans has been developed for English--Chinese cross-language Web search.

REFERENCES

• 1: Ahonen, H., Heinonen, O., Klemettinen, M., and Verkamo, A. 1999. Finding co-occurring text phrases by combining sequence and frequent set discovery. In Proceedings of IJCAI'99 Workshop on Text Mining: Foundations, Techniques and Applications, 1--9.
• 2: Einat Amitay , Cécile Paris, Automatically summarising Web sites: is there a way around it?, Proceedings of the ninth international conference on Information and knowledge management, p.173-179, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354816]
• 3: Lisa Ballesteros , W. Bruce Croft, Resolving ambiguity for cross-language retrieval, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.64-71, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290958]
• 4: Michael Berry , Theresa Do , Gavin O''Brien , Vijay K %A , Sowmini Varadhan, SVDPACKC (Version 1.0) User''s Guide, University of Tennessee, Knoxville, TN, 1993
• 5: Lars Borin, You'll take the high road and I'll take the low road: using a third language to improve bilingual word alignment, Proceedings of the 18th conference on Computational linguistics, p.97-103, July 31-August 04, 2000, Saarbrücken, Germany [doi>10.3115/990820.990835]
• 6: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 7: Peter F. Brown , Vincent J. Della Pietra , Stephen A. Della Pietra , Robert L. Mercer, The mathematics of statistical machine translation: parameter estimation, Computational Linguistics, v.19 n.2, June 1993
• 8: Soumen Chakrabarti , Byron Dom , Prabhakar Raghavan , Sridhar Rajagopalan , David Gibson , Jon Kleinberg, Automatic resource compilation by analyzing hyperlink structure and associated text, Proceedings of the seventh international conference on World Wide Web 7, p.65-74, April 1998, Brisbane, Australia
• 9: Chen, K. H. and Chen, H. H. 2001. The Chinese text retrieval tasks of NTCIR workshop 2, In Proceedings of the Second NTCIR Workshop Meeting on Evaluation of Chinese & Japanese Text Retrieval and Text Summarization.
• 10: Lee-Feng Chien, PAT-tree-based keyword extraction for Chinese information retrieval, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.50-58, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 11: Dagan, I., Church, K. W., and Gale, W. A. 1993. Robust bilingual word alignment for machine aided translation. In Proceedings of the Workshop on Very Large Corpora, 1--8.
• 12: Deogun, J. S., Raghavan V. V., and Server, H. 1997. Data mining: Research trends, challenges, and applications. In Rough Sets and Data Mining: Analysis of Imprecise Data. Kluwer Academic Publishers, 9--45.
• 13: Dumais, S. T., Landauer, T. K., and Littman, M. L. 1996. Automatic cross-linguistic information retrieval using latent semantic indexing. In Proceedings of ACM-SIGIR'96 Workshop on Cross-Linguistic Information Retrieval. ACM, New York, 16--24.
• 14: Dumais, S. T., Letsche, A., Littman, M. L., and Landauer, T. K. 1997. Automatic Cross-Linguistic Retrieval Using Latent Semantic Indexing. In AAAI Spring Symposium on Cross-Language Text and Speech Retrieval, 15--21.
• 15: Usama M. Fayyad , Gregory Piatetsky-Shapiro , Padhraic Smyth , Ramasamy Uthurusamy, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 16: Feldman, R. and Dagan, I. 1995. KDT---Knowledge discovery in texts. In Proceedings of the 1st International Conference on Knowledge Discovery and Data Mining, 112--117.
• 17: Feldman, R., Aumann, Y., Amir, A., Kloesgen, W., and Zilberstien, A. 1997. Maximal association rules: A new tool for mining for keyword co-occurrences in document collections. In Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining, 167--170.
• 18: Dieter Fensel, Ontologies: A Silver Bullet for Knowledge Management and Electronic Commerce, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 19: Pascale Fung , Lo Yuen Yee, An IR approach for translating new words from nonparallel, comparable texts, Proceedings of the 17th international conference on Computational linguistics, August 10-14, 1998, Montreal, Quebec, Canada
• 20: G. W. Furnas , S. Deerwester , S. T. Dumais , T. K. Landauer , R. A. Harshman , L. A. Streeter , K. E. Lochbaum, Information retrieval using a singular value decomposition model of latent semantic structure, Proceedings of the 11th annual international ACM SIGIR conference on Research and development in information retrieval, p.465-480, May 1988, Grenoble, France [doi>10.1145/62437.62487]
• 21: Tim Gollins , Mark Sanderson, Improving cross language retrieval with triangulated translation, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.90-95, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383965]
• 22: Marti A. Hearst, Untangling text data mining, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.3-10, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034679]
• 23: Djoerd Hiemstra , Franciska de Jong, Disambiguation Strategies for Cross-Language Information Retrieval, Proceedings of the Third European Conference on Research and Advanced Technology for Digital Libraries, p.274-293, September 22-24, 1999
• 24: David A. Hull , Gregory Grefenstette, Querying across languages: a dictionary-based approach to multilingual information retrieval, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.49-57, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243212]
• 25: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 26: Knight, K. 1997. Automating knowledge acquisition for machine translation. AI Mag. 18, 4.
• 27: Kwok, K. L. 2001. NTCIR-2 Chinese, cross language retrieval experiments using PIRCS. In Proceedings of the Second NTCIR Workshop Meeting on Evaluation of Chinese & Japanese Text Retrieval and Text Summarization.
• 28: Wen-Hsiang Lu , Lee-Feng Chien , Hsi-Jian Lee, Anchor Text Mining for Translation of Web Queries, Proceedings of the 2001 IEEE International Conference on Data Mining, p.401-408, November 29-December 02, 2001
• 29: Wen-Hsiang Lu , Lee-Feng Chien , Hsi-Jian Lee, Translation of web queries using anchor text mining, ACM Transactions on Asian Language Information Processing (TALIP), v.1 n.2, p.159-172, June 2002 [doi>10.1145/568954.568958]
• 30: Wen-Hsiang Lu , Lee-Feng Chien , Hsi-Jian Lee, A transitive model for extracting translation equivalents of web queries through anchor text mining, Proceedings of the 19th international conference on Computational linguistics, p.1-7, August 24-September 01, 2002, Taipei, Taiwan [doi>10.3115/1072228.1072236]
• 31: Victor Lavrenko , Martin Choquette , W. Bruce Croft, Cross-lingual relevance models, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564408]
• 32: I. Dan Melamed, Models of translational equivalence among words, Computational Linguistics, v.26 n.2, p.221-249, June 2000 [doi>10.1162/089120100561683]
• 33: Mori, T., Kokubu, T., and Tanaka, T. 2001. Cross-lingual information retrieval based on LSI with multiple word spaces. In Proceedings of the 2nd NTCIR Workshop Meeting on Evaluation of Chinese & Japanese Text Retrieval and Text Summarization.
• 34: Jian-Yun Nie , Michel Simard , Pierre Isabelle , Richard Durand, Cross-language information retrieval based on parallel texts and automatic mining of parallel texts from the Web, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.74-81, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312656]
• 35: Oard, D. and Diekema, A. 1998. Cross-language information retrieval. Ann. Rev. Inf. Sci. Tech. 33, 223--256.
• 36: Reinhard Rapp, Automatic identification of word translations from unrelated English and German corpora, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.519-526, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034756]
• 37: Philip Resnik , Douglas Oard , Gina Levow, Improved cross-language retrieval using backoff translation, Proceedings of the first international conference on Human language technology research, p.1-3, March 18-21, 2001, San Diego [doi>10.3115/1072133.1072185]
• 38: Barry G. Silverman , Mintu Bachann , Khaled Al-Akharas, Do What I Mean: Online Shopping with a Natural Language Search Agent, IEEE Intelligent Systems, v.16 n.4, p.48-53, July 2001 [doi>10.1109/5254.941357]
• 39: Silverstein, C., Henzinger, M., Marais, J., and Moricz, M. 1998. Analysis of a very large altavista query log. Tech. Rep. 1998--014. Digital Systems Research Center.
• 40: Simard, M. 2000. Multilingual text alignment. In Parallel Text Processing, J. Veronis, Eds. Kluwer Academic Publishers, The Netherlands, 49--67.
• 41: Frank Smadja , Kathleen R. McKeown , Vasileios Hatzivassiloglou, Translating collocations for bilingual lexicons: a statistical approach, Computational Linguistics, v.22 n.1, p.1-38, March 1996
• 42: Soderland, S. 1997. Learning to extract text-based information from the world wide web. In Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining, 251--254.
• 43: S. K. M. Wong , Y. Y. Yao, On modeling information retrieval with probabilistic inference, ACM Transactions on Information Systems (TOIS), v.13 n.1, p.38-68, Jan. 1995 [doi>10.1145/195705.195713]
• 44: Jinxi Xu , Ralph Weischedel , Chanh Nguyen, Evaluating a probabilistic model for cross-lingual information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.105-110, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383968]
• 45: Yiming Yang , Jaime G. Carbonell , Ralf D. Brown , Robert E. Frederking, Translingual information retrieval: learning from bilingual corpora, Artificial Intelligence, v.103 n.1-2, p.323-345, Aug. 1998 [doi>10.1016/S0004-3702(98)00063-0]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Textual databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Hypertext/hypermedia

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Multilingual translation, anchor text mining, competitive linking algorithm, cross-language Web search, cross-language information retrieval