Semi-Supervised Convex Training for Dependency Parsing

Proceedings of ACL-08: HLT, pages 532–540, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics Semi-supervised Convex Training for Dependency Parsing Qin Iris Wang Department of Computing Science University of Alberta Edmonton, AB, Canada, T6G 2E8 wqin@cs.ualberta.ca Dale Schuurmans Department of Computing Science University of Alberta Edmonton, AB, Canada, T6G 2E8 dale@cs.ualberta.ca Dekang Lin Google Inc. 1600 Amphitheatre Parkway Mountain View, CA, USA, 94043 lindek@google.com Abstract We present a novel semi-supervised training algorithm for learning dependency parsers. By combining a supervised large margin loss with an unsupervised least squares loss, a dis- criminative, convex, semi-supervised learning algorithm can be obtained that is applicable to large-scale problems. To demonstrate the benefits of this approach, we apply the tech- nique to learning dependency parsers from combined labeled and unlabeled corpora. Us- ing a stochastic gradient descent algorithm, a parsing model can be efficiently learned from semi-supervised data that significantly outper- forms corresponding supervised methods. 1 Introduction Supervised learning algorithms still represent the state of the art approach for inferring dependency parsers from data (McDonald et al., 2005a; McDon- ald and Pereira, 2006; Wang et al., 2007). How- ever, a key drawback of supervised training algo- rithms is their dependence on labeled data, which is usually very difficult to obtain. Perceiving the limitation of supervised learning—in particular, the heavy dependence on annotated corpora—many re- searchers have investigated semi-supervised learn- ing techniques that can take both labeled and unla- beled training data as input. Following the common theme of “more data is better data” we also use both a limited labeled corpora and a plentiful unlabeled data resource. Our goal is to obtain better perfor- mance than a purely supervised approach without unreasonable computational effort. Unfortunately, although significant recent progress has been made in the area of semi-supervised learning, the perfor- mance of semi-supervised learning algorithms still fall far short of expectations, particularly in chal- lenging real-world tasks such as natural language parsing or machine translation. A large number of distinct approaches to semi- supervised training algorithms have been investi- gated in the literature (Bennett and Demiriz, 1998; Zhu et al., 2003; Altun et al., 2005; Mann and McCallum, 2007). Among the most prominent ap- proaches are self-training, generative models, semi- supervised support vector machines (S3VM), graph- based algorithms and multi-view algorithms (Zhu, 2005). Self-training is a commonly used technique for semi-supervised learning that has been ap- 532 plied to several natural language processing tasks (Yarowsky, 1995; Charniak, 1997; Steedman et al., 2003). The basic idea is to bootstrap a supervised learning algorithm by alternating between inferring the missing label information and retraining. Re- cently, McClosky et al. (2006a) successfully applied self-training to parsing by exploiting available un- labeled data, and obtained remarkable results when the same technique was applied to parser adaptation (McClosky et al., 2006b). More recently, Haffari and Sarkar (2007) have extended the work of Abney (2004) and given a better mathematical understand- ing of self-training algorithms. They also show con- nections between these algorithms and other related machine learning …

Content truncated to 500 words