Talukdar and Pereira ACL 2010
Contents
Citation
Partha Pratim Talukdar and Fernando Pereira. 2010. Experiments in graph-based semi-supervised learning methods for class-instance acquisition. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL '10). Association for Computational Linguistics, Morristown, NJ, USA, 1473-1481.
Online version
Summary
This paper conducted an empirical comparison of three graph based semi-supervised learning (SSL) methods for the Class-Instance Acquisition task.
Motivation
Traditional NER have focused on a small number of classes such as person and location. These classes are too broad to be useful for applications like word sense disambiguation and textual inference in practice. There are limited training data for supervised learning methods for the fine-grained classification. Therefore seed-based information extraction systems have been developed to extract new instances of a class from unstructured text using a few seed instances of that class.
Graph based semi-supervised methods have been successfully applied in this class instance acquisition task but there is no comparison done to demonstrate which methods are better.
Methods Compared
The general idea of graph based semi-supervised learning method works as follows: Given a connectivity graph which contains both labeled (seeds) and unlabeled data, the labels of the labeled data are propagated to the unlabeled data through the graph with some constrains.
LP-ZGL (Zhu et al., ICML 2003) is the first graph based semi-supervised learning method. It propagates the labels of training data by ensuring the smoothness of the label assignment and preserving the labels of the training data. The smoothness (manifold assumption) of the label assignment implies that two highly connected nodes in the graph should have same or similar labels.
Adsorption (Baluja et al., WWW 2008) uses an iterative method. Its main idea is to limit the information that passes through each node and it relaxes the constrain of preserving the labels of training data.
MAD (Talukdar and Crammer, ECML 2009) re-expressed the Adsorption method as a optimization problem. The labels of training data can also be changed.
Evaluation
The comparison was done on subsets of Freebase in 18 domains, TextRunner (Banko et al., IJCAI 2007) results. The evaluation metric used is the Mean Reciprocal Rank.
Results
MAD performed significantly better than the other two on Freebase datasets using classes from (Pantel et al., EMNLP 2009) and WordNet as the gold standards. Three methods performs comparably on TextRunner data using the classes from WordNet. From the evaluation, MAD performs the best when the average degree of nodes are high.
The authors also investigated the impact of semantic constrains (additional edges between instances and attributes) to these graph based learning methods. These constrains are from YAGO KB (Suchanek et al, WWW 2008). The evaluation shows it is very beneficial to use these semantic constrains for these graph based semi-supervised learning methods.
Related papers
Three graph based SSL methods can be found in Zhu et al., ICML 2003, Baluja et al., WWW 2008, and Talukdar and Crammer, ECML 2009.
