Constraint-Driven Rank-Based Learning for Information Extraction

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 729–732, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Constraint-Driven Rank-Based Learning for Information Extraction Sameer Singh Limin Yao Sebastian Riedel Andrew McCallum Dept. of Computer Science University of Massachusetts Amherst MA 01003 {sameer,lmyao,riedel,mccallum}@cs.umass.edu Abstract Most learning algorithms for undirected graphical models require complete inference over at least one instance before parameter up- dates can be made. SampleRank is a rank- based learning framework that alleviates this problem by updating the parameters during in- ference. Most semi-supervised learning algo- rithms also perform full inference on at least one instance before each parameter update. We extend SampleRank to semi-supervised learning in order to circumvent this compu- tational bottleneck. Different approaches to incorporate unlabeled data and prior knowl- edge into this framework are explored. When evaluated on a standard information extraction dataset, our method significantly outperforms the supervised method, and matches results of a competing state-of-the-art semi-supervised learning approach. 1 Introduction Most supervised learning algorithms for undirected graphical models require full inference over the dataset (e.g., gradient descent), small subsets of the dataset (e.g., stochastic gradient descent), or at least a single instance (e.g., perceptron, Collins (2002)) before parameter updates are made. Often this is the main computational bottleneck during training. SampleRank (Wick et al., 2009) is a rank-based learning framework that alleviates this problem by performing parameter updates within inference. Ev- ery pair of samples generated during inference is ranked according to the model and the ground truth, and the parameters are updated when the rankings disagree. SampleRank has enabled efficient learn- ing for massive information extraction tasks (Culotta et al., 2007; Singh et al., 2009). The problem of requiring a complete inference it- eration before parameters are updated also exists in the semi-supervised learning scenario. Here the sit- uation is often considerably worse since inference has to be applied to potentially very large unlabeled datasets. Most semi-supervised learning algorithms rely on marginals (GE, Mann and McCallum, 2008) or MAP assignments (CODL, Chang et al., 2007). Calculating these is computationally inexpensive for many simple tasks (such as classification and re- gression). However, marginal and MAP inference tends to be expensive for complex structured pre- diction models (such as the joint information extrac- tion models of Singh et al. (2009)), making semi- supervised learning intractable. In this work we employ a fast rank-based learning algorithm for semi-supervised learning to circum- vent the inference bottleneck. The ranking function is extended to capture both the preference expressed by the labeled data, and the preference of the domain expert when the labels are not available. This allows us to perform SampleRank as is, without sacrificing its scalability, which is crucial for future large scale applications of semi-supervised learning. We applied our method to a standard information extraction dataset used for semi-supervised learning. Empirically we demonstrate improvements over the supervised model, and closely match the results of a competing state-of-the-art semi-supervised learner. 2 Background Conditional random fields (Lafferty …

Content truncated to 500 words