Induction of semantic classes from natural language text

ABSTRACT

Many applications dealing with textual information require classification of words into semantic classes (or concepts). However, manually constructing semantic classes is a tedious task. In this paper, we present an algorithm, UNICON, for UNsupervised Induction of CONcepts. Some advantages of UNICON over previous approaches include the ability to classify words with low frequency counts, the ability to cluster a large number of elements in a high-dimensional space, and the ability to classify previously unknown words into existing clusters. Furthermore, since the algorithm is unsupervised, a set of concepts may be constructed for any corpus.

REFERENCES

• 1: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 2: Arora, S. and Sagra, S. 1992. Approximating Clique is NP-Complete. In Proceedings of IEEE Symposium on Foundations of Computer Science. pp. 2.- 13.
• 3: Bomze, I. M., Budinich, M., Pardalos, P. M., and Pelillo, M. 1999. The maximum clique problem. Handbook of Combinatorial Optimization (Supplement Volume A). D.-Z. Du and P. M. Pardalos (Eds.). Kluwar Academic Publishers. Boston,/viA. pp. 1-74
• 4: Hsinchun Chen , Tak Yim , David Fye , Bruce Schatz, Automatic thesaurus generation for an electronic community system, Journal of the American Society for Information Science, v.46 n.3, p.175-193, April 1995 [doi>10.1002/(SICI)1097-4571(199504)46:3<175::AID-ASI3>3.0.CO;2-U]
• 5: Carolyn J. Crouch , Bokyung Yang, Experiments in automatic statistical thesaurus construction, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.77-88, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133180]
• 6: Gregory Grefenstette, Explorations in Automatic Thesaurus Discovery, Kluwer Academic Publishers, Norwell, MA, 1994
• 7: Sanda M. Harabagiu , Marius A. Paşca , Steven J. Maiorano, Experiments with open-domain textual Question Answering, Proceedings of the 18th conference on Computational linguistics, p.292-298, July 31-August 04, 2000, Saarbrücken, Germany [doi>10.3115/990820.990863]
• 8: Harris, Z. 1985. Distributional Structure. In: Katz, J. J. (ed.) The Philosophy of Linguistics. New York: Oxford University Press. pp. 26-47.
• 9: Hays, D. 1964. Dependency Theory: a Formalism and Some Observations. Language, 40:511-525.
• 10: Hudson, R. 1984. Word Grammar. Basil Blackwell Publishers Limited. Oxford, England.
• 11: Jing, Y. and Croft, W. B. 1994. An Association Thesaurus for Information Retrieval. In Proceedings of RIAO-94. pp. 146-160. New York.
• 12: Lin, D. 1998a. Extracting Collocations from Text Corpora. Workshop on Computational Terminology. pp. 57-63. Montreal, Canada.
• 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, PRINCIPAR: an efficient, broad-coverage, principle-based parser, Proceedings of the 15th conference on Computational linguistics, August 05-09, 1994, Kyoto, Japan [doi>10.3115/991886.991970]
• 15: Andrew McCallum , Kamal Nigam , Lyle H. Ungar, Efficient clustering of high-dimensional data sets with application to reference matching, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.169-178, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347123]
• 16: Melcuk, I.A. 1987. Dependency Syntax: theory and practice. State University of New York Press. Albany, NY.
• 17: Young C. Park , Key-Sun Choi, Automatic thesaurus construction using Bayesian networks, Information Processing and Management: an International Journal, v.32 n.5, p.543-553, Sept. 1996 [doi>10.1016/0306-4573(96)00026-X]
• 18: Resnik, P. 1998. Semantic Similarity in a Taxonomy: An Information-Based Measure and its Application to Problems of Ambiguity in Natural Language. Journal of Al Research, 11:95-130.
• 19: G. Salton , C. Buckley , C. T. Yu, An evaluation of term dependence models in information retrieval, Proceedings of the 5th annual ACM conference on Research and development in information retrieval, p.151-173, May 18-20, 1982, West Berlin, Germany
• 20: Roman Yangarber , Ralph Grishman , Pasi Tapanainen , Silja Huttunen, Automatic acquisition of domain knowledge for Information Extraction, Proceedings of the 18th conference on Computational linguistics, July 31-August 04, 2000, Saarbrücken, Germany [doi>10.3115/992730.992782]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing
          Subjects: Language models

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

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.5 Document Capture
          Subjects: Document analysis

General Terms:
Algorithms, Design, Performance