M.Sc Thesis | |

M.Sc Student | Mejer Avihai |
---|---|

Subject | Confidence Estimation in Structured Predicition |

Department | Department of Computer Science |

Supervisor | ASSOCIATE PROF. Yacov Crammer |

Full Thesis text |

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.