Inferring hierarchical descriptions

ABSTRACT

We create a statistical model for inferring hierarchical term relationships about a topic, given only a small set of example web pages on the topic, without prior knowledge of any hierarchical information. The model can utilize either the full text of the pages in the cluster or the context of links to the pages. To support the model, we use "ground truth" data taken from the category labels in the Open Directory. We show that the model accurately separates terms in the following classes: self terms describing the cluster, parent terms describing more general concepts, and child terms describing specializations of the cluster. For example, for a set of biology pages, sample parent, self, and child terms are science, biology, and genetics respectively. We create an algorithm to predict parent, self, and child terms using the new model, and compare the predictions to the ground truth data. The algorithm accurately ranks a majority of the ground truth terms highly, and identifies additional complementary terms missing in the Open Directory.

REFERENCES

• 1: Sharon A. Caraballo, Automatic construction of a hypernym-labeled noun hierarchy from text, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.120-126, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034705]
• 2: D. Fasulo. An analysis of recent work on clustering algorithms. Technical report, University of Washington, 1999. Available at: http://citeseer.nj.nec.com/fasulo99analysi.html.
• 3: Eric J. Glover , Kostas Tsioutsiouliklis , Steve Lawrence , David M. Pennock , Gary W. Flake, Using web structure for classifying and describing web pages, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511520]
• 4: 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]
• 5: Marti~A. Hearst. Automated discovery of WordNet relations. In Christiane Fellbaum, editor, WordNet: An Electronic Lexical Database. MIT Press, 1998.
• 6: Thomas Hofmann , Jan Puzicha, Statistical Models for Co-occurrence Data, Massachusetts Institute of Technology, Cambridge, MA, 1998
• 7: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1481-1493, May 17, 1999
• 8: Alexandrin Popescul and Lyle~H. Ungar. Automatic labeling of document clusters. Unpublished manuscript, available at: http://citeseer.nj.nec.com/popescul00automatic.html.
• 9: Dragomir R. Radev , Weiguo Fan, Automatic summarization of search engine hit lists, Proceedings of the ACL-2000 workshop on Recent advances in natural language processing and information retrieval: held in conjunction with the 38th Annual Meeting of the Association for Computational Linguistics, October 08-08, 2000, Hong Kong [doi>10.3115/1117755.1117768]
• 10: Mark Sanderson , Bruce Croft, Deriving concept hierarchies from text, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.206-213, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312679]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Linguistic processing

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
cluster naming, feature selection, hierarchical relationships, statistical models, web analysis