Disjunctive Rule Lists

In this study, we present an interpretable model, disjunctive rule list (DisRL) for regression. This research is motivated by the increasing need for model interpretability, especially in high-stakes decisions such as medicine, where decisions are made on or related to humans. DisRL is a generalized form of rule lists. A DisRL model consists of a list of disjunctive rules embedded in an if-else logic structure that stratifies the data space. Compared with traditional decision trees and other rule list models in the literature that stratify the feature space with single itemsets (an itemset is a conjunction of conditions), each disjunctive rule in DisRL uses a set of itemsets to collectively cover a subregion in the feature space. In addition, a DisRL model is constructed under a global objective that balances the predictive performance and model complexity. To train a DisRL model, we devise a hierarchical stochastic local search algorithm that exploits the properties of DisRL's unique structure to improve search efficiency. The algorithm adopts the main structure of simulated annealing and customizes the proposing strategy for faster convergence. Meanwhile, the algorithm uses a prefix bound to locate a subset of the search area, effectively pruning the search space at each iteration. An ablation study shows the effectiveness of this strategy in pruning the search space. Experiments on public benchmark datasets demonstrate that DisRL outperforms baseline interpretable models, including decision trees and other rule-based regressors.