A Theory of Interpretable Approximations |
Original Papers |
Can a deep neural network be approximated by a small decision tree based on simple features? This question and its variants are behind the growing demand for machine learning models that are \emph{interpretable} by humans. In this work we study such questions by introducing \emph{interpretable approximations}, a notion that captures the idea of approximating a target concept $c$ by a small aggregation of concepts from some base class $\mathcal{H}$. In particular, we consider the approximation of a binary concept $c$ by decision trees based on a simple class $\mathcal{H}$ (e.g., of bounded VC dimension), and use the tree depth as a measure of complexity. Our primary contribution is the following remarkable trichotomy. For any given pair of $\mathcal{H}$ and $c$, exactly one of these cases holds: (i) $c$ cannot be approximated by $\mathcal{H}$ with arbitrary accuracy; (ii) $c$ can be approximated by $\mathcal{H}$ with arbitrary accuracy, but there exists no universal rate that bounds the complexity of the approximations as a function of the accuracy; or (iii) there exists a constant $\kappa$ that depends only on $\mathcal{H}$ and $c$ such that, for \emph{any} data distribution and \emph{any} desired accuracy level, $c$ can be approximated by $\mathcal{H}$ with a complexity not exceeding $\kappa$. This taxonomy stands in stark contrast to the landscape of supervised classification, which offers a complex array of distribution-free and universally learnable scenarios. We show that, in the case of interpretable approximations, even a slightly nontrivial a-priori guarantee on the complexity of approximations implies approximations with constant (distribution-free and accuracy-free) complexity. We extend our trichotomy to classes $\mathcal{H}$ of unbounded VC dimension and give characterizations of interpretability based on the algebra generated by $\mathcal{H}$. |
inproceedings |
Proceedings of Machine Learning Research |
PMLR |
2640-3498 |
bressan24a |
0 |
A Theory of Interpretable Approximations |
648 |
668 |
648-668 |
648 |
false |
Bressan, Marco and Cesa-Bianchi, Nicol{\`o} and Esposito, Emmanuel and Mansour, Yishay and Moran, Shay and Thiessen, Maximilian |
| given |
family |
Marco |
Bressan |
|
| given |
family |
Nicolò |
Cesa-Bianchi |
|
| given |
family |
Emmanuel |
Esposito |
|
| given |
family |
Yishay |
Mansour |
|
|
| given |
family |
Maximilian |
Thiessen |
|
|
2024-06-30 |
|
Proceedings of Thirty Seventh Conference on Learning Theory |
247 |
inproceedings |
|
|
|