An Incremental Decision List Learner

An Incremental Decision List Learner Joshua Goodman Microsoft Research One Microsoft Way Redmond, WA 98052 joshuago@microsoft.com Abstract We demonstrate a problem with the stan- dard technique for learning probabilistic decision lists. We describe a simple, in- cremental algorithm that avoids this prob- lem, and show how to implement it effi- ciently. We also show a variation that adds thresholding to the standard sorting algo- rithm for decision lists, leading to similar improvements. Experimental results show that the new algorithm produces substan- tially lower error rates and entropy, while simultaneously learning lists that are over an order of magnitude smaller than those produced by the standard algorithm. 1 Introduction Decision lists (Rivest, 1987) have been used for a variety of natural language tasks, including accent restoration (Yarowsky, 1994), word sense disam- biguation (Yarowsky, 2000), finding the past tense of English verbs (Mooney and Califf, 1995), and sev- eral other problems. We show a problem with the standard algorithm for learning probabilistic deci- sion lists, and we introduce an incremental algorithm that consistently works better. While the obvious im- plementation for this algorithm would be very slow, we also show how to efficiently implement it. The new algorithm produces smaller lists, while simul- taneously substantially reducing entropy (by about 40%), and error rates (by about 25% relative.) Decision lists are a very simple, easy to understand formalism. Consider a word sense disambiguation task, such as distinguishing the financial sense of the word “bank” from the river sense. We might want the decision list to be probabilistic (Kearns and Schapire, 1994) so that, for instance, the probabilities can be propagated to an understanding algorithm. The de- cision list for this task might be: IF “water” occurs nearby, output “river: .95”, “fi- nancial: .05” ELSE IF “money” occurs nearby, output “river: .1”, “financial: .9” ELSE IF word before is “left”, output “river: .8”, “financial: .2” ELSE IF “Charles” occcurs nearby, output “river: .6”, “financial: .4” ELSE output “river: .5”, “financial: .5” The conditions of the list are checked in order, and as soon as a matching rule is found, the algorithm outputs the appropriate probability and terminates. If no other rule is used, the last rule always triggers, ensuring that some probability is always returned. The standard algorithm for learning decision lists (Yarowsky, 1994) is very simple. The goal is to min- imize the entropy of the decision list, where entropy representshowuncertainweareaboutaparticularde- cision. For each rule, we find the expected entropy using that rule, then sort all rules by their entropy, and output the rules in order, lowest entropy first. Decision lists are fairly widely used for many rea- sons. Mostimportantly, theruleoutputstheyproduce are easily understood by humans. This can make de- cision lists useful as a data analysis tool: the decision list can be examined to determine which factors are most important. It can also make them useful when the rules must be used by humans, such as when pro- ducing guidelines to help doctors determine whether a particular drug should be administered. Decision …

Content truncated to 500 words