M.Sc Thesis

M.Sc StudentMejer Avihai
SubjectConfidence Estimation in Structured Predicition
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Yacov Crammer
Full Thesis textFull thesis text - English Version


Structured classification tasks such as sequence labeling and dependency parsing have seen much interest by the Natural Language Processing and the machine learning communities. Several learning algorithms were adapted for structured tasks such as SVM, Perceptron, Passive-Aggressive and the recently introduced Confidence-Weighted learning. These algorithms yield state-of-the-art performance. However, unlike probabilistic models like Hidden Markov Model and Conditional random fields, these methods generate models that output merely a prediction with no additional information regarding confidence in the correctness of the output. In this work we fill the gap proposing several alternatives to compute the confidence in the output of non-probabilistic algorithms. We show how to compute confidence estimates in the prediction such that the confidence reflects the probability that the word is labeled correctly. Our first method is based on extending the notion of classification margin. A second method is based on the marginal probabilities induced by the prediction model. A third method is based on the level of agreement regarding the prediction among the K highest ranking predictions produced by the model. Finally, a fourth method is based on sampling K alternative predictions and computing the confidence score as the level of agreement among the K predictions. We then show how to use our methods to detect mislabeled words, trade recall for precision and for active learning. We evaluate our methods on four noun-phrase chunking and named entity recognition sequence labeling tasks, and on dependency parsing for 14 languages.