A Dynamic Confusion Score for Dependency Arc Labels

International Joint Conference on Natural Language Processing, pages 1237–1242, Nagoya, Japan, 14-18 October 2013. A Dynamic Confusion Score for Dependency Arc Labels Sambhav Jain and Bhasha Agrawal Language Technologies Research Center IIIT-Hyderabad, India {sambhav.jain, bhasha.agrawal}@research.iiit.ac.in Abstract In this paper we propose an approach to dynamically compute a confusion score for dependency arc labels, in typed depen- dency parsing framework. This score ac- companies the parsed output and aims to administer an informed account of parse correctness, detailed down to each edge of the parse. The methodology explores the confusion encountered by the oracle of a data driven parser, in predicting an arc la- bel. We support our hypothesis by empiri- cally illustrating, for 20 languages, that the labels with a high confusion score are no- tably the predominant parsing errors. 1 Introduction Recently, a major research drive has been to- wards building data driven dependency parsers for various languages. Shared tasks like CoNLL-X and CoNLL 2007 have acted as development and testing grounds for various efforts in the field. The majority of the emerged systems follow ei- ther graph based paradigm (McDonald et al., 2005; McDonald and Pereira, 2006) eg. MST Parser (McDonald et al., 2005) or transition based paradigm (Yamada and Matsumoto, 2003; Nivre and Scholz, 2004) eg. MaltParser(Nivre et al., 2007). A time complexity relatively lower than their earlier counterparts makes the above parsers apt for use by real time NLP applications like Ma- chine Translation (Galley and Manning, 2009). However, Popel et al.(2011) in the context of MT pointed out that an incorrect parse can hurt the ac- curacy of output. Thus, correctness of individual parses becomes a key factor in such a setup. This calls for measures which can indicate up- front the quality of each individual output. A rele- vant work in this direction is by Mejer and Cram- mer (2012). They proposed methods to estimate confidence of correctness of predicted parse in a graph based parsing scenario using MSTParser. Graph-based and transition-based parsers exhibit two very distinctive approaches towards parsing, each having its own strengths and limitations (Mc- Donald and Nivre, 2007; Zhang and Clark, 2008). The diversity in the two techniques motivated us to explore and formulate a similar measure in tran- sition based paradigm. We choose MaltParser1 (Nivre et al., 2007), which produces a parse tree using a shift-reduce based transition algorithm, to work with. It uses SVM to train an oracle to pre- dict parsing action. The measures proposed by Mejer and Crammer (2012) can not be straight off applied in transition based parsers, as unlike the graph based approach they commit local opera- tions and thus can not directly produce globally optimum k-best parses. We propose computing an entropy based label confusion score, dynamically computed and as- signed while parsing (the computational details are presented in section 2 of this paper). Since en- tropy measures the uncertainty in a random vari- able, we prefer to call the measure, in our ap- proach, confusion score. This measure aims to give a …

Content truncated to 500 words