Paper: An Incremental Decision List Learner

ACL ID W02-1003
Title An Incremental Decision List Learner
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2002

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.