Confidence in Structured-Prediction Using Confidence-Weighted Models

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 971–981, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics Confidence in Structured-Prediction using Confidence-Weighted Models Avihai Mejer Department of Computer Science 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 Confidence-Weighted linear classifiers (CW) and its successors were shown to perform well on binary and multiclass NLP prob- lems. In this paper we extend the CW ap- proach for sequence learning and show that it achieves state-of-the-art performance on four noun phrase chucking and named entity recog- nition tasks. We then derive few algorith- mic approaches to estimate the prediction’s correctness of each label in the output se- quence. We show that our approach provides a reliable relative correctness information as it outperforms other alternatives in ranking label-predictions according to their error. We also show empirically that our methods output close to absolute estimation of error. Finally, we show how to use this information to im- prove active learning. 1 Introduction In the past decade structured classification has seen much interest by the machine learning community. After the introduction of conditional random fields (CRFs) (Lafferty et al., 2001), and maximum mar- gin Markov networks (Taskar et al., 2003), which are batch algorithms, new online method were in- troduced. For example the passive-aggressive algo- rithm was adapted to chunking (Shimizu and Haas, 2006), parsing (McDonald et al., 2005b), learning preferences (Wick et al., 2009) and text segmenta- tion (McDonald et al., 2005a). These new online algorithms are fast to train and simple to implement, yet they generate models that output merely a pre- diction with no additional information, as opposed to probabilistic models like CRFs or HMMs. In this work we fill this gap proposing few al- ternatives to compute confidence in the output of discriminative non-probabilistic algorithms. As be- fore, our algorithms output the highest-scoring la- beling. However, they also compute additional la- belings, that are used to compute the per word con- fidence in its labelings. We build on the recently introduced confidence-weighted learning (Dredze et al., 2008; Crammer et al., 2009b) and induce a dis- tribution over labelings from the distribution main- tained over weight-vectors. We show how to compute confidence estimates in the label predicted per word, such that the con- fidence reflects the probability that the label is not correct. We then use this confidence information to rank all labeled words (in all sentences). This can be thought of as a retrieval of the erroneous words, which can than be passed to human anno- tator for an examination, either to correct these mis- takes or as a quality control component. Next, we show how to apply our techniques to active learning over sequences. We evaluate our methods on four NP chunking and NER datasets and demonstrate the usefulness of our methods. Finally, we report the performance of obtained by CW-like adapted to se- quence prediction, which …

Content truncated to 500 words