# Fast Optimization of Weighted Sparse Decision Trees for use in Optimal Treatment Regimes and Optimal Policy Design

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 48 references that are in the map.
- First posted on arXiv 13 Oct 2022.

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

- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [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)
- [Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making](https://mlsanity.com/paper/1903.10598/) (2019)
- [MurTree: Optimal Classification Trees via Dynamic Programming and Search](https://mlsanity.com/paper/2007.12652/) (2020)
- [Learning Certifiably Optimal Rule Lists for Categorical Data](https://mlsanity.com/paper/1704.01701/) (2017)
- [In Pursuit of Interpretable, Fair and Accurate Machine Learning for Criminal Recidivism Prediction](https://mlsanity.com/paper/2005.04176/) (2020)
- [Fast Sparse Decision Tree Optimization via Reference Ensembles](https://mlsanity.com/paper/2112.00798/) (2021)
- [MALTS: Matching After Learning to Stretch](https://mlsanity.com/paper/1811.07415/) (2018)
- [Towards Interpretable-AI Policies Induction using Evolutionary Nonlinear Decision Trees for Discrete Action Systems](https://mlsanity.com/paper/2009.09521/) (2020)
- [Using Decision Lists to Construct Interpretable and Parsimonious Treatment Regimes](https://mlsanity.com/paper/1504.07715/) (2015)
- [An Optimization Approach to Learning Falling Rule Lists](https://mlsanity.com/paper/1710.02572/) (2017)
- [Optimal Decision Trees for the Algorithm Selection Problem: Integer Programming Based Approaches](https://mlsanity.com/paper/1907.02211/) (2019)
- [Tree based weighted learning for estimating individualized treatment rules with censored data](https://mlsanity.com/paper/1707.09632/) (2017)
- [Causal Falling Rule Lists](https://mlsanity.com/paper/1510.05189/) (2015)

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

- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)

## Abstract (arXiv)

Sparse decision trees are one of the most common forms of interpretable models. While recent advances have produced algorithms that fully optimize sparse decision trees for prediction, that work does not address policy design, because the algorithms cannot handle weighted data samples. Specifically, they rely on the discreteness of the loss function, which means that real-valued weights cannot be directly used. For example, none of the existing techniques produce policies that incorporate inverse propensity weighting on individual data points. We present three algorithms for efficient sparse weighted decision tree optimization. The first approach directly optimizes the weighted loss function; however, it tends to be computationally inefficient for large datasets. Our second approach, which scales more efficiently, transforms weights to integer values and uses data duplication to transform the weighted decision tree optimization problem into an unweighted (but larger) counterpart. Our third algorithm, which scales to much larger datasets, uses a randomized procedure that samples each data point with a probability proportional to its weight. We present theoretical bounds on the error of the two fast methods and show experimentally that these methods can be two orders of magnitude faster than the direct optimization of the weighted loss, without losing significant accuracy.