Efficient Graph-Based Semi-Supervised Learning of Structured Tagging Models

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 167–176, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics Efficient Graph-Based Semi-Supervised Learning of Structured Tagging Models Amarnag Subramanya Google Research Mountain View, CA 94043 asubram@google.com Slav Petrov Google Research New York, NY 10011 slav@google.com Fernando Pereira Google Research Mountain View, CA 94043 pereira@google.com Abstract We describe a new scalable algorithm for semi-supervised training of conditional ran- dom fields (CRF) and its application to part- of-speech (POS) tagging. The algorithm uses a similarity graph to encourage similar n- grams to have similar POS tags. We demon- strate the efficacy of our approach on a do- main adaptation task, where we assume that we have access to large amounts of unlabeled data from the target domain, but no additional labeled data. The similarity graph is used dur- ing training to smooth the state posteriors on the target domain. Standard inference can be used at test time. Our approach is able to scale to very large problems and yields significantly improved target domain accuracy. 1 Introduction Semi-supervised learning (SSL) is the use of small amounts of labeled data with relatively large amounts of unlabeled data to train predictors. In some cases, the labeled data can be sufficient to pro- vide reasonable accuracy on in-domain data, but per- formance on even closely related out-of-domain data may lag far behind. Annotating training data for all sub-domains of a varied domain such as all of Web text is impractical, giving impetus to the develop- ment of SSL techniques that can learn from unla- beled data to perform well across domains. The ear- liest SSL algorithm is self-training (Scudder, 1965), where one makes use of a previously trained model to annotate unlabeled data which is then used to re-train the model. While self-training is widely used and can yield good results in some applica- tions (Yarowsky, 1995), it has no theoretical guaran- tees except under certain stringent conditions, which rarely hold in practice(Haffari and Sarkar, 2007). Other SSL methods include co-training (Blum and Mitchell, 1998), transductive support vector ma- chines (SVMs) (Joachims, 1999), and graph-based SSL (Zhu et al., 2003). Several surveys cover a broad range of methods (Seeger, 2000; Zhu, 2005; Chapelle et al., 2007; Blitzer and Zhu, 2008). A ma- jority of SSL algorithms are computationally expen- sive; for example, solving a transductive SVM ex- actly is intractable. Thus we have a conflict between wanting to use SSL with large unlabeled data sets for best accuracy, but being unable to do so because of computational complexity. Some researchers at- tempted to resolve this conflict by resorting to ap- proximations (Collobert et al., 2006), but those lead to suboptimal results (Chapelle et al., 2007). Graph-based SSL algorithms (Zhu et al., 2003; Joachims, 2003; Corduneanu and Jaakkola, 2003; Belkin et al., 2005; Subramanya and Bilmes, 2009) are an important subclass of SSL techniques that have received much attention in the recent past, as they outperform other approaches and also scale …

Content truncated to 500 words