Learning Decision Lists with Known Rules for Text Mining

Venkatesan Chakravarthy, Sachindra Joshi, Ganesh Ramakrishnan, Shantanu Godbole, Sreeram BalakrishnanIJCNLP 2008 · OpenReview

Abstract

Rule-based systems are essential in industrial text mining for their interpretability and maintainability. However, a significant challenge arises when multiple rules apply to the same instance: determining the optimal sequence in a decision list. This paper addresses the Maximum Decision List (MaxDL) problem—optimizing the order of a pre-existing rule set to maximize accuracy. We prove that MaxDL is NP-Hard and propose a greedy framework utilizing a novel "happiness quotient" to prioritize rules that correctly handle difficult examples. Our results demonstrate that this approach significantly outperforms standard ordering methods across various text-mining tasks.

Introduction

In machine learning, while "black box" models like deep neural networks are popular, rule-based systems remain the gold standard in high-stakes industrial settings due to their human-readability and ease of debugging. A Decision List is a sequence of "if-then" rules where the first matching rule determines the output. The challenge lies in ambiguity; for instance, "Apple" could be an Organization or a Fruit depending on the context. The final classification depends entirely on rule precedence.

While most algorithms learn rules and their order simultaneously, many real-world scenarios involve pre-existing rules from domain experts or legacy models. This paper investigates how to find the optimal order for such fixed rule sets.

The MaxDL Problem and Complexity

The authors formalize the task as the Maximum Decision List (MaxDL) problem. They provide a rigorous proof that finding the absolute best order for a set of rules is NP-Hard. Furthermore, the problem is computationally "stubborn," making it difficult to achieve close approximations using standard techniques as the number of rules increases.

Methodology: The Happiness Heuristic

To address the NP-Hardness of MaxDL, the researchers propose a Greedy Framework using three distinct scoring functions to determine rule priority:

  1. Simple Precision ($Score_{SP}$): A baseline approach that selects the rule with the highest accuracy on the remaining data.
  2. Weighted Precision ($Score_{WP}$): This introduces the "Happiness Quotient" ($h(t)$). For any data point $t$, $h(t)$ represents the fraction of rules that classify it correctly. Instances with low $h(t)$ are considered "hard." The algorithm prioritizes rules that correctly classify these hard instances while penalizing those that misclassify "easy" ones.
  3. Refined Weighted Precision ($Score_{RP}$): A more advanced version that weights the happiness quotient by the individual precision of the rules involved (denoted as $Score_{WP}^{PR}$ in experimental data).

Experimental Evaluation

The heuristics were evaluated on Named Entity Recognition (MUC-7) and various text classification benchmarks (Reuters, TREC, Ohsumed).

Heterogeneous Rule Sets

One of the most significant findings was the performance gain when ordering a mix of different classifiers. As shown in Table 1, the proposed weighted heuristics consistently outperformed simple precision and baseline classifiers like Naive Bayes on datasets such as oh5, where accuracy improved from 74.16% to 83.98%.

Table 1: Performance comparison on heterogeneous rule sets across various datasets.

Improving Existing Learners

The framework also proved effective at refining the output of existing rule learners. By re-ordering the rules generated by the RIPPER algorithm (JRip), the researchers achieved notable improvements in test accuracy across multiple datasets (see Table 2).

Table 2: Accuracy improvements achieved by re-ordering rules generated by the JRip algorithm.

Named Entity Recognition

On the MUC-7 dataset, the Refined Weighted Precision ($Score_{RP}$) achieved 54.5% accuracy, a significant improvement over the 50.0% achieved by simple precision.

Conclusion

This research highlights that rule ordering is as critical as rule induction. The "Happiness" heuristic provides a clever way to value rules that solve difficult cases. While the paper focuses on fixed rule sets, future work may extend this logic to ensemble learning, ordering weak classifiers into decision lists to bridge the gap between interpretability and high performance.

Summary updated

BibTeX
@inproceedings{chakravarthy2008learning,
  author = {Venkatesan Chakravarthy and Sachindra Joshi and Ganesh Ramakrishnan and Shantanu Godbole and Sreeram Balakrishnan},
  title = {{Learning Decision Lists with Known Rules for Text Mining}},
  booktitle = {IJCNLP},
  year = {2008},
  url = {https://openreview.net/forum?id=woZ4VkfpZj},
}
Figure