# Rule Generation for Classification: Scalability, Interpretability, and Fairness

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 110 references that are in the map.
- First posted on arXiv 21 Apr 2021.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI](https://mlsanity.com/paper/1910.10045/) (2019)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [Algorithmic decision making and the cost of fairness](https://mlsanity.com/paper/1701.08230/) (2017)
- [Fairness in Machine Learning: A Survey](https://mlsanity.com/paper/2010.04053/) (2020)
- [Fairness in Criminal Justice Risk Assessments: The State of the Art](https://mlsanity.com/paper/1703.09207/) (2017)
- [Local Rule-Based Explanations of Black Box Decision Systems](https://mlsanity.com/paper/1805.10820/) (2018)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Boolean Decision Rules via Column Generation](https://mlsanity.com/paper/1805.09901/) (2018)
- [MurTree: Optimal Classification Trees via Dynamic Programming and Search](https://mlsanity.com/paper/2007.12652/) (2020)
- [Accuracy and Fairness Trade-offs in Machine Learning: A Stochastic Multi-Objective Approach](https://mlsanity.com/paper/2008.01132/) (2020)
- [Generalized Linear Rule Models](https://mlsanity.com/paper/1906.01761/) (2019)
- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [Optimization of Tree Ensembles](https://mlsanity.com/paper/1705.10883/) (2017)
- [Principles to Practices for Responsible AI: Closing the Gap](https://mlsanity.com/paper/2006.04707/) (2020)
- [A unified approach to mixed-integer optimization problems with logical constraints](https://mlsanity.com/paper/1907.02109/) (2019)
- [Interpretable multiclass classification by MDL-based rule lists](https://mlsanity.com/paper/1905.00328/) (2019)
- [Optimization Problems for Machine Learning: A Survey](https://mlsanity.com/paper/1901.05331/) (2019)
- [Learning Optimized Or's of And's](https://mlsanity.com/paper/1511.02210/) (2015)
- [MLIC: A MaxSAT-Based framework for learning interpretable classification rules](https://mlsanity.com/paper/1812.01843/) (2018)
- [Sparsity in Optimal Randomized Classification Trees](https://mlsanity.com/paper/2002.09191/) (2020)
- [The Price of Interpretability](https://mlsanity.com/paper/1907.03419/) (2019)
- [IMLI: An Incremental Framework for MaxSAT-Based Learning of Interpretable Classification Rules](https://mlsanity.com/paper/2001.01891/) (2020)

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

- [Clinicians' Voice: Fundamental Considerations for XAI in Healthcare](https://mlsanity.com/paper/2411.04855/) (2024)
- [From Prototypes to Sparse ECG Explanations: SHAP-Driven Counterfactuals for Multivariate Time-Series Multi-class Classification](https://mlsanity.com/paper/2510.19514/) (2025)
- [Ethical Fairness in Ubiquitous Health Sensing without Known Attributes](https://mlsanity.com/paper/2603.13373/) (2026)
- [Human Guided Learning of Transparent Regression Models](https://mlsanity.com/paper/2502.15992/) (2025)

## Abstract (arXiv)

We introduce a new rule-based optimization method for classification with constraints. The proposed method leverages column generation for linear programming, and hence, is scalable to large datasets. The resulting pricing subproblem is shown to be NP-Hard. We recourse to a decision tree-based heuristic and solve a proxy pricing subproblem for acceleration. The method returns a set of rules along with their optimal weights indicating the importance of each rule for learning. We address interpretability and fairness by assigning cost coefficients to the rules and introducing additional constraints. In particular, we focus on local interpretability and generalize a separation criterion in fairness to multiple sensitive attributes and classes. We test the performance of the proposed methodology on a collection of datasets and present a case study to elaborate on its different aspects. The proposed rule-based learning method exhibits a good compromise between local interpretability and fairness on the one side, and accuracy on the other side.