Training Dependency Parser Using Light Feedback

2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 488–497, Montr´eal, Canada, June 3-8, 2012. c⃝2012 Association for Computational Linguistics Training Dependency Parser Using Light Feedback Avihai Mejer Department of Electrical Engineering Technion-Israel Institute of Technology Haifa 32000, Israel amejer@tx.technion.ac.il Koby Crammer Department of Electrical Engineering Technion-Israel Institute of Technology Haifa 32000, Israel koby@ee.technion.ac.il Abstract We introduce lightly supervised learning for dependency parsing. In this paradigm, the al- gorithm is initiated with a parser, such as one that was built based on a very limited amount of fully annotated training data. Then, the al- gorithm iterates over unlabeled sentences and asks only for a single bit of feedback, rather than a full parse tree. Specifically, given an example the algorithm outputs two possible parse trees and receives only a single bit indi- cating which of the two alternatives has more correct edges. There is no direct information about the correctness of any edge. We show on dependency parsing tasks in 14 languages that with only 1% of fully labeled data, and light-feedback on the remaining 99% of the training data, our algorithm achieves, on av- erage, only 5% lower performance than when training with fully annotated training set. We also evaluate the algorithm in different feed- back settings and show its robustness to noise. 1 Introduction Supervised learning is a dominant paradigm in ma- chine learning in which a prediction model is built based on examples, each of which is composed of in- puts and a corresponding full annotation. In the task of parsing, examples are composed of sentences in some language and associated with full parse trees. These parse trees are often generated by human an- notators. The annotation process is complex, slow and prone to mistakes as for each sentence a full cor- rect feedback is required. We describe light-feedback learning which suits learning problems with complex or structured out- put, like parsing. After building an initial classi- fier, our algorithm reduces the work of the annota- tor from a full annotation of the input sentence to a single bit of information. Specifically, it provides the annotator with two alternative parses of the in- put sentence and asks for the single bit indicating which of the alternatives is better. In 95% of the sentences both alternatives are identical except for a single word. See Fig. 2 for an illustration. Thus, the work of the annotator boils down to deciding for some specific word in the sentence which of two possible words should be that word’s head. We show empirically, through simulation, that us- ing only 1% of the training set with full annotation, and the remaining 99% with light annotation, our al- gorithm achieves an average accuracy of about 80%, only 5% less than a parser built with full annotated training data. These results are averaged over 14 languages. With additional simple relaxations, our algorithm achieves average accuracy of 82.5%, not far from the performance of an algorithm observing full …

Content truncated to 500 words