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 *interpretable* by humans. In this work we
study such questions by introducing *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 *any* data distribution and *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}$.

通过简单特征的决策树是否能够逼近深度神经网络的问题，以及该问题的变体，正是对可由人类解释的机器学习模型不断增长的需求。本文通过引入可解释逼近的概念来研究这些问题，这一概念捕捉了通过一些基类概念的小聚合来逼近目标概念 c 的想法。我们的主要贡献是：对于给定的 H 和 c，对于任何给定的 pair，只有下列三种情况之一成立：(i) c 无法以任意精度通过 H 来逼近；(ii) c 可以以任意精度通过 H 来逼近，但不存在一种普遍的速率来限制逼近的复杂度与精度之间的关系；或者 (iii) 存在一个只依赖于 H 和 c 的常数 kappa，对于任何数据分布和任何期望的精度水平，c 可以通过 H 来逼近，并且复杂度不超过 kappa。这种分类法与监督分类的情况形成鲜明对比，后者提供了复杂的分布自由和普遍可学习的场景。我们表明，在可解释逼近的情况下，即使对逼近的复杂度有一个略微非平凡的先验保证，也可以得到具有常数（与分布和精度无关）复杂度的逼近。我们将我们的分类法扩展到具有无界 VC 维度的类 H，并给出了基于 H 生成的代数的可解释性的特征。