Paper: Learning Decision Lists with Known Rules for Text Mining

ACL ID I08-2118
Title Learning Decision Lists with Known Rules for Text Mining
Venue International Joint Conference on Natural Language Processing
Session Main Conference
Year 2008
Authors

Many real-world systems for handling unstructured text data are rule-based. Examples of such systems are named entity annotators, information extraction systems, and text classifiers. In each of these appli- cations, ordering rules into a decision list is an im- portant issue. In this paper, we assume that a set of rules is given and study the problem (MaxDL) of or- dering them into an optimal decision list with respect to a given training set. We formalize this problem and show that it is NP-Hard and cannot be approxi- mated within any reasonable factors. We then propose some heuristic algorithms and conduct exhaustive ex- periments to evaluate their performance. In our ex- periments we also observe performance improvement over an existing decision list learning algorithm, by merely re-or...