Are You Sure? Confidence in Prediction of Dependency Tree Edges

2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 573–576, Montr´eal, Canada, June 3-8, 2012. c⃝2012 Association for Computational Linguistics Are You Sure? Confidence in Prediction of Dependency Tree Edges 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 describe and evaluate several methods for estimating the confidence in the per-edge cor- rectness of a predicted dependency parse. We show empirically that the confidence is asso- ciated with the probability that an edge is se- lected correctly and that it can be used to de- tect incorrect edges very efficiently. We eval- uate our methods on parsing text in 14 lan- guages. 1 Introduction Dependency parsers construct directed edges be- tween words of a given sentence to their arguments according to syntactic or semantic rules. We use MSTParser of McDonald et al. (2005) and focus on non-projective dependency parse trees with non- typed (unlabeled) edges. MSTParser produces a parse tree for a sentence by constructing a full, di- rected and weighted graph over the words of the sentence, and then outputting the maximal spanning tree (MST) of the graph. A linear model is em- ployed for computing the weights of the edges using features depending on the two words the edge con- nects. Example features are the distance between the two words, words identity and words part-of-speech. MSTParser is training a model using online learning and specifically the MIRA algorithm (Crammer et al., 2006). The output of MSTParser is the highest scoring parse tree, it is not accompanied by any ad- ditional information about its quality. In this work we evaluate few methods for estimat- ing the confidence in the correctness of the predic- tion of a parser. This information can be used in several ways. For example, when using parse trees as input to another system such as machine transla- tion, the confidence information can be used to cor- rect inputs with low confidence. Another example is to guide manual validation to outputs which are more likely to be erroneous, saving human labor. We adapt methods proposed by Mejer and Cram- mer (2010) in order to produce per-edge confidence estimations in the prediction. Specifically, one ap- proach is based on sampling, and another on a gen- eralization of the concept of margin. Additionally, we propose a new method based on combining both approaches, and show that is outperforms both. 2 Confidence Estimation In Prediction MSTParser produces the highest scoring parse trees using the trained linear model with no additional information about the confidence in the predicted tree. In this work we compute per-edge confidence scores, that is, a numeric confidence value, for all edges predicted by the parser. Larger score values indicate higher confidence. We use three confidence estimation methods that were proposed for sequence labeling (Mejer and Crammer, 2010), adapted here for dependency parsing. A fourth method, described in …

Content truncated to 500 words