Weakly-Supervised Acquisition of Labeled Class Instances using Graph Random Walks

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 582–590, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Weakly-Supervised Acquisition of Labeled Class Instances using Graph Random Walks Partha Pratim Talukdar∗ University of Pennsylvania Philadelphia, PA 19104 partha@cis.upenn.edu Joseph Reisinger∗ University of Texas at Austin Austin, TX 78712 joeraii@cs.utexas.edu Marius Pas¸ca Google Inc. Mountain View, CA 94043 mars@google.com Deepak Ravichandran Google Inc. Mountain View, CA 94043 deepakr@google.com Rahul Bhagat∗ USC Information Sciences Institute Marina Del Rey, CA 90292 rahul@isi.edu Fernando Pereira Google Inc. Mountain View, CA 94043 pereira@google.com Abstract We present a graph-based semi-supervised la- bel propagation algorithm for acquiring open- domain labeled classes and their instances from a combination of unstructured and struc- tured text sources. This acquisition method significantly improves coverage compared to a previous set of labeled classes and instances derived from free text, while achieving com- parable precision. 1 Introduction 1.1 Motivation Users of large document collections can readily ac- quire information about the instances, classes, and relationships described in the documents. Such rela- tions play an important role in both natural language understanding and Web search, as illustrated by their prominence in both Web documents and among the search queries submitted most frequently by Web users (Jansen et al., 2000). These observations moti- vate our work on algorithms to extract instance-class information from Web documents. While work on named-entity recognition tradi- tionally focuses on the acquisition and identifica- tion of instances within a small set of coarse-grained classes, the distribution of instances within query logs indicates that Web search users are interested in a wider range of more fine-grained classes. De- pending on prior knowledge, personal interests and immediate needs, users submit for example medi- cal queries about the symptoms of leptospirosis or ∗Contributions made during internships at Google. the treatment of monkeypox, both of which are in- stances of zoonotic diseases, or the risks and benefits of surgical procedures such as PRK and angioplasty. Other users may be more interested in African coun- tries such as Uganda and Angola, or active volca- noes like Etna and Kilauea. Note that zoonotic dis- eases, surgical procedures, African countries and active volcanoes serve as useful class labels that cap- ture the semantics of the associated sets of class in- stances. Such interest in a wide variety of specific domains highlights the utility of constructing large collections of fine-grained classes. Comprehensive and accurate class-instance in- formation is useful not only in search but also in a variety of other text processing tasks includ- ing co-reference resolution (McCarthy and Lehn- ert, 1995), named entity recognition (Stevenson and Gaizauskas, 2000) and seed-based information ex- traction (Riloff and Jones, 1999). 1.2 Contributions We study the acquisition of open-domain, labeled classes and their instances from both structured and unstructured textual data sources by combin- ing and ranking individual extractions in a princi- pled way with the Adsorption label-propagation al- gorithm (Baluja et al., 2008), reviewed in Section 3 below. A collection of labeled classes acquired from text (Van …

Content truncated to 500 words