Coaxing Confidences from an Old Freind: Probabilistic Classifications from Transformation Rule Lists

Coaxing Confidences from an Old Friend: Probabilistic Classifications from Transformation Rule Lists Radu Florian* John C. Henderson t Grace Ngai* *Department of Computer Science Johns Hopkins University Baltimore, MD 21218, USA {rflorian,gyn}@cs.jhu.edu tThe MITRE Corporation 202 Burlington Road Bedford, MA 01730, USA jhndrsn@mitre.org Abstract Transformation-based learning has been success- fully employed to solve many natural language processing problems. It has many positive fea- tures, but one drawback is that it does not provide estimates of class membership probabilities. In this paper, we present a novel method for obtaining class membership probabilities from a transformation-based rule list classifier. Three ex- periments are presented which measure the model- ing accuracy and cross-entropy of the probabilistic classifier on unseen data and the degree to which the output probabilities from the classifier can be used to estimate confidences in its classification decisions. The results of these experiments show that, for the task of text chunking 1, the estimates produced by this technique are more informative than those generated by a state-of-the-art decision tree. 1 Introduction In natural language processing, a great amount of work has gone into the development of machine learning algorithms which extract useful linguistic information from resources such as dictionaries, newswire feeds, manually annotated corpora and web pages. Most of the effective methods can be roughly divided into rule-based and proba- bilistic algorithms. In general, the rule-based methods have the advantage of capturing the necessary information in a small and concise set of rules. In part-of-speech tagging, for exam- ple, rule-based and probabilistic methods achieve comparable accuracies, but rule-based methods capture the knowledge in a hundred or so simple rules, while the probabilistic methods have a very high--dimensional parameter space (millions of parameters). One of the main advantages of probabilistic methods, on the other hand, is that they include a measure of uncertainty in their output. This can take the form of a probability distribution over potential outputs, or it may be a ranked list of IA11 the experiments are performed on text chnnklng. The technique presented is general-purpose, however, and can be applied to many tasks for which transformation- based learning performs well, without changing the inter- rials of the learner. candidate outputs. These uncertainty measures are useful in situations where both the classifi- cation of an sample and the system's confidence in that classification are needed. An example of this is a situation in an ensemble system where ensemble members disagree and a decision must be made about how to resolve the disagreement. A similar situation arises in pipeline systems, such as a system which performs parsing on the output of a probabilistic part-of-speech tagging. Transformation-based learning (TBL) (Brill, 1995) is a successful rule-based machine learning algorithm in natural language processing. It has been applied to a wide variety of tasks, including part of speech tagging (Roche and Schabes, 1995; Brill, 1995), noun phrase chvnklng (Ramshaw and Marcus, 1999), parsing (Brill, 1996; Vilain and Day, 1996), spelling correction (Mangu and Brill, 1997), prepositional phrase attachment (Brill and Resnik, 1994), …

Content truncated to 500 words