Experiments in Graph-Based Semi-Supervised Learning Methods for Class-Instance Acquisition

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1473–1481, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Experiments in Graph-based Semi-Supervised Learning Methods for Class-Instance Acquisition Partha Pratim Talukdar∗ Search Labs, Microsoft Research Mountain View, CA 94043 partha@talukdar.net Fernando Pereira Google, Inc. Mountain View, CA 94043 pereira@google.com Abstract Graph-based semi-supervised learning (SSL) algorithms have been successfully used to extract class-instance pairs from large unstructured and structured text col- lections. However, a careful comparison of different graph-based SSL algorithms on that task has been lacking. We com- pare three graph-based SSL algorithms for class-instance acquisition on a variety of graphs constructed from different do- mains. We find that the recently proposed MAD algorithm is the most effective. We also show that class-instance extraction can be significantly improved by adding semantic information in the form of instance-attribute edges derived from an independently developed knowledge base. All of our code and data will be made publicly available to encourage reproducible research in this area. 1 Introduction Traditionally, named-entity recognition (NER) has focused on a small number of broad classes such as person, location, organization. However, those classes are too coarse to support important ap- plications such as sense disambiguation, seman- tic matching, and textual inference in Web search. For those tasks, we need a much larger inventory of specific classes and accurate classification of terms into those classes. While supervised learn- ing methods perform well for traditional NER, they are impractical for fine-grained classification because sufficient labeled data to train classifiers for all the classes is unavailable and would be very expensive to obtain. ∗ Research carried out while at the University of Penn- sylvania, Philadelphia, PA, USA. To overcome these difficulties, seed-based in- formation extraction methods have been devel- oped over the years (Hearst, 1992; Riloff and Jones, 1999; Etzioni et al., 2005; Talukdar et al., 2006; Van Durme and Pas¸ca, 2008). Start- ing with a few seed instances for some classes, these methods, through analysis of unstructured text, extract new instances of the same class. This line of work has evolved to incorporate ideas from graph-based semi-supervised learning in extrac- tion from semi-structured text (Wang and Cohen, 2007), and in combining extractions from free text and from structured sources (Talukdar et al., 2008). The benefits of combining multiple sources have also been demonstrated recently (Pennac- chiotti and Pantel, 2009). We make the following contributions: • Even though graph-based SSL algorithms have achieved early success in class-instance acquisition, there is no study comparing dif- ferent graph-based SSL methods on this task. We address this gap with a series of experi- ments comparing three graph-based SSL al- gorithms (Section 2) on graphs constructed from several sources (Metaweb Technolo- gies, 2009; Banko et al., 2007). • We investigate whether semantic informa- tion in the form of instance-attribute edges derived from an independent knowledge base (Suchanek et al., 2007) can improve class-instance acquisition. The intuition be- hind this is that instances that share attributes are more likely to …

Content truncated to 500 words