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:
- Simple Precision ($Score_{SP}$): A baseline approach that selects the rule with the highest accuracy on the remaining data.
- 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.
- 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%.
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).
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