Abstract
In this paper, we consider linear prediction models in the form of a sparse linear combination of rules, where a rule is an indicator function defined over a hyperrectangle in the input space. Since the number of all possible rules generated from the training dataset becomes extremely large, it has been difficult to consider all of them when fitting a sparse model. In this paper, we propose Safe Optimal Rule Fit (SORF) as an approach to resolve this problem, which is formulated as a convex optimization problem with sparse regularization. The proposed SORF method utilizes the fact that the set of all possible rules can be represented as a tree. By extending a recently popularized convex optimization technique called safe screening, we develop a novel method for pruning the tree such that pruned nodes are guaranteed to be irrelevant to the prediction model. This approach allows us to efficiently learn a prediction model constructed from an exponentially large number of all possible rules. We demonstrate the usefulness of the proposed method by numerical experiments using several benchmark datasets.
Introduction
In machine learning, practitioners often face a trade-off between the high performance of "black box" models, such as deep neural networks, and the interpretability of "glass box" models, like linear regressions or decision rules. Rule-based models offer a compelling middle ground by predicting outcomes through a sparse combination of "if-then" rules. However, traditional methods for fitting these models have relied on heuristic, two-step processes that often fail to identify the most predictive rules from the vast search space.
Existing frameworks typically generate a dictionary of rules using heuristics (e.g., growing decision trees) and then apply sparse learning methods like Lasso. The limitation is that this dictionary is often incomplete. For a dataset with 10 features and 10 values each, there are approximately $2.5 \times 10^{17}$ possible rules defined as hyperrectangles in the input space. Searching this space exhaustively has been computationally impossible until now.
The Safe RuleFit (SRF) Framework
The proposed Safe RuleFit (SRF) treats rule selection as a convex optimization problem over the set of all possible rules. The model $f(x)$ is constructed as a combination of linear terms and rule-based indicator functions, as shown below:
To make this optimization tractable, the authors introduce two key innovations:
- Safe Screening (SS): A technique used in sparse learning to identify features guaranteed to have a zero coefficient at the optimal solution, allowing them to be removed before optimization.
- Meta Safe Screening (mSS): This is the core contribution. Standard screening requires checking every feature individually. mSS exploits the inclusion-relations of rules. Since rules are hyperrectangles, if a "parent" rectangle satisfies the mSS condition, all sub-rectangles within it are also guaranteed to be inactive and can be screened out simultaneously.
By organizing rules into a tree structure where ancestors contain their descendants, the algorithm can prune entire branches—billions of rules at a time—without ever explicitly evaluating them.
Key Insights and Results
Efficiency and Pruning Power
The mSS technique proves remarkably effective. In numerical experiments, the algorithm identified optimal models while examining less than 2% of the total possible rules. When compared against REPR, a previous state-of-the-art optimal rule method, SRF demonstrated orders-of-magnitude speed improvements. For instance, on the "Airfoil" dataset, SRF completed in approximately 591 seconds, whereas REPR required nearly 8,000 seconds.
Accuracy and Stability
SRF significantly outperforms standard linear Lasso and remains competitive with non-linear models like Kernel SVMs. Unlike heuristic models (e.g., Random Forests), which can be unstable and change significantly with different random seeds, SRF is based on convex optimization. This makes it deterministic and stable, a critical requirement for high-stakes applications like medical diagnosis.
Interpretability
The authors also introduced Group Safe RuleFit (GSRF), which utilizes a Sparse Group Lasso penalty. This approach groups rules that use the same set of input features, effectively reducing the variety of feature combinations and making the final model easier for humans to interpret.
Conclusion
Safe RuleFit represents a significant advancement in interpretable machine learning by enabling the globally optimal selection of rules from an astronomical search space. While the computational cost still grows with the number of input features, the use of geometric pruning via mSS makes optimal rule fitting feasible for many real-world datasets. Future work may involve combining SRF with active set methods to further enhance performance on high-dimensional data.
Summary updated