# Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach

arXiv: https://arxiv.org/abs/2206.03718 · HTML: https://mlsanity.com/paper/2206.03718/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 51 references that are in the map.
- First posted on arXiv 8 Jun 2022.

## Builds on (most cited first, 16 of 16)

- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [One Explanation Does Not Fit All: A Toolkit and Taxonomy of AI Explainability Techniques](https://mlsanity.com/paper/1909.03012/) (2019)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020)
- [Boolean Decision Rules via Column Generation](https://mlsanity.com/paper/1805.09901/) (2018)
- [Learning Certifiably Optimal Rule Lists for Categorical Data](https://mlsanity.com/paper/1704.01701/) (2017)
- [Optimal approximation for submodular and supermodular optimization with bounded curvature](https://mlsanity.com/paper/1311.4728/) (2013)
- [A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees](https://mlsanity.com/paper/2011.03375/) (2020)
- [Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications](https://mlsanity.com/paper/1904.09354/) (2019)
- [Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications](https://mlsanity.com/paper/1408.2051/) (2014)
- [Regularized Submodular Maximization at Scale](https://mlsanity.com/paper/2002.03503/) (2020)
- [Learning Optimized Or's of And's](https://mlsanity.com/paper/1511.02210/) (2015)
- [Guess Free Maximization of Submodular and Linear Sums](https://mlsanity.com/paper/1810.03813/) (2018)
- [Diverse Rule Sets](https://mlsanity.com/paper/2006.09890/) (2020)
- [Greed is Good: Near-Optimal Submodular Maximization via Greedy Optimization](https://mlsanity.com/paper/1704.01652/) (2017)
- [LIBRE: Learning Interpretable Boolean Rule Ensembles](https://mlsanity.com/paper/1911.06537/) (2019)

## Built on by (most cited first, 13 of 13)

- [Truly Unordered Probabilistic Rule Sets for Multi-class Classification](https://mlsanity.com/paper/2206.08804/) (2022)
- [A Scalable, Interpretable, Verifiable & Differentiable Logic Gate Convolutional Neural Network Architecture From Truth Tables](https://mlsanity.com/paper/2208.08609/) (2022)
- [Difference of Submodular Minimization via DC Programming](https://mlsanity.com/paper/2305.11046/) (2023)
- [Biological and Radiological Dictionary of Radiomics Features: Addressing Understandable AI Issues in Personalized Prostate Cancer; Dictionary Version PM1.0](https://mlsanity.com/paper/2412.10967/) (2024)
- [Compact Rule-Based Classifier Learning via Gradient Descent](https://mlsanity.com/paper/2502.01375/) (2025)
- [Probabilistic Truly Unordered Rule Sets](https://mlsanity.com/paper/2401.09918/) (2024)
- [MoRE-LLM: Mixture of Rule Experts Guided by a Large Language Model](https://mlsanity.com/paper/2503.22731/) (2025)
- [Personalized Interpretable Classification](https://mlsanity.com/paper/2302.02528/) (2023)
- [A New Interpretable Neural Network-Based Rule Model for Healthcare Decision Making](https://mlsanity.com/paper/2309.11101/) (2023)
- [Minimising changes to audit when updating decision trees](https://mlsanity.com/paper/2408.16321/) (2024)
- [Learning local discrete features in explainable-by-design convolutional neural networks](https://mlsanity.com/paper/2411.00139/) (2024)
- [CogGen: Cognitive-Load-Inspired Fully Unsupervised Deep Generative Modeling for Compressively Sampled MRI Reconstruction](https://mlsanity.com/paper/2603.04438/) (2026)
- [Learning High Coverage Discriminative Parsimonious Rulesets](https://mlsanity.com/paper/2606.14156/) (2026)

## Abstract (arXiv)

Rule sets are highly interpretable logical models in which the predicates for decision are expressed in disjunctive normal form (DNF, OR-of-ANDs), or, equivalently, the overall model comprises an unordered collection of if-then decision rules. In this paper, we consider a submodular optimization based approach for learning rule sets. The learning problem is framed as a subset selection task in which a subset of all possible rules needs to be selected to form an accurate and interpretable rule set. We employ an objective function that exhibits submodularity and thus is amenable to submodular optimization techniques. To overcome the difficulty arose from dealing with the exponential-sized ground set of rules, the subproblem of searching a rule is casted as another subset selection task that asks for a subset of features. We show it is possible to write the induced objective function for the subproblem as a difference of two submodular (DS) functions to make it approximately solvable by DS optimization algorithms. Overall, the proposed approach is simple, scalable, and likely to be benefited from further research on submodular optimization. Experiments on real datasets demonstrate the effectiveness of our method.