一种可解释性近似理论

Jun, 2024

A Theory of Interpretable Approximations

Marco Bressan, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran...

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

Abstract

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 *→

deep neural network interpretable approximations decision trees complexity interpretable approximations

发现论文，激发创造

计算复杂度视角下的模型可解释性

本文在探讨不同模型的可解释性时，提出了一种基于计算复杂度理论的原则性可解释性概念，并证明了线性模型和基于树的模型相对于神经网络更可解释，同时通过参数化复杂度分析，提出了浅层神经网络比深层神经网络更容易解释的理论证据。

Oct, 2020

通过特征空间分割窥视深度神经网络

本文提出了一种通过构建树形结构，实现对复杂模型进行分级分区并揭示其迭代拒绝可能的类标签的过程，以达到在不影响模型准确性的前提下实现模型解释性的方法。

Nov, 2016

学习最优公平分类树：可解释性、公平性和准确性之间的权衡

本研究设计了一个 MIO（mixed integer optimization）框架，用于学习最优的分类树算法，以及与任意公平性约束进行扩展；提出了一个新的模型可解释性度量标准，称为决策复杂度；在流行数据集上，我们对公平性、可解释性及预测准确性之间的权衡进行了综合分析，证明了我们的方法在几乎完全平等的情况下仍能保持精度.

Jan, 2022

通过单棵树逼近解释模型

提出了一种用于构建决策树的方法，可以近似复杂机器学习模型的性能，可用于解释和简化随机森林（RFs）和其他模型的预测模式。在医学问卷中，树形结构特别有意义，因为它使问卷自适应地缩短，减轻回答负担。研究了分裂的渐近行为，并引入了一种改进的分裂方法，旨在稳定树形结构。经实验证明，我们的方法可以同时实现高近似性和稳定性。

Oct, 2016

通过模型提取方法解释黑匣子模型

为了解释黑盒模型，本文提出使用决策树对其进行全局解释，并采用新的决策树提取算法避免过拟合，评估表明该方法正确率更高且可解释性更强。

May, 2017

可解释模型的概率式数据集重建

解释性是可信任机器学习的一个关键要求，因为通过学习和发布一些内在可解释的模型可以泄露有关底层训练数据的信息，而这可能直接与隐私冲突。本文提出了一个新的框架，用于处理其他形式的可解释模型和更普遍的知识，并证明在对可解释模型结构做出现实的假设的情况下，可以有效地计算重建的不确定性。最后，我们通过比较精确学习算法和启发式学习算法关联的理论信息泄漏，说明了我们方法的适用性，使用决策树和规则列表。我们的结果表明，对于给定的准确性水平，最优解释性模型通常更紧凑，泄露的关于训练数据的信息更少。

Aug, 2023

通过决策树解读核聚类

探索可解释的核聚类算法，提出构建决策树来近似核 k-means 引发的分区的算法，并展示了适当选择特征如何在不损失可解释模型的近似保证的情况下保持可解释性。

Feb, 2024

解释决策树

该研究提出了一种计算 DT 的极小解释集 PI-explanations 的新模型，该模型可在多项式时间内计算一个 PI-explanation，并将枚举 PI-explanations 减少到枚举最小击中集的数量。实验结果表明，在大多数情况下，DT 的路径是 PI-explanations 的子集。

Oct, 2020

概念树：更可解释的代理决策树的高级变量表示

我们提出了一种模型无关的可解释替代方案，用于全局和局部解释黑盒分类器。该替代方案使用相关系数自动发现变量的直观分组，并将其嵌入到替代决策树中，以提高其可理解性。在宏观经济数据库上的实验结果表明，在保持替代模型准确性和保真度的同时，该方案提高了人类可解释性。

Jun, 2019

神经网络中逼近、深度分离与可学习性的关联

本文主要研究深度神经网络、近似能力和可学习性之间的复杂关系，提出了必须在浅层神经网络中近似目标函数的概念，并给出了多个范例证明了深度神经网络的分离性，并结论它们即使被高效近似，也不能被高效学习。

Jan, 2021