【ETHZ博士论文】监督学习中的频谱偏差，149页pdf

我们基于过去几十年在监督学习中的进展，重点关注两个成功的模型类别：决策树集成和神经网络。这些模型展现了一种称为“频谱偏差”的属性，即它们学习的函数可以使用紧凑的傅立叶（沃尔什-哈达玛德）表示来表示。这一属性构成了本论文的基础。 对于神经网络，我们知道尽管它们有能力学习复杂函数，但用于训练的算法，如随机梯度下降，往往会导致学到的函数更简单。在这个上下文中，简单性的概念通过沃尔什-哈达玛德变换来检查。神经网络发现学习低阶傅立叶频率，这对应于具有因式分解形式的函数。（集成的）决策树深度d可以精确表示为最高d阶的稀疏函数。 论文包括三个章节：

• “一种可扩展的沃尔什-哈达玛德正则化器，用于克服神经网络的低阶频谱偏差”解决了神经网络中简单性与复杂性之间的权衡。低阶频谱偏差可能会阻碍学习复杂函数，导致次优的泛化。提出了一种可扩展的正则化方法来缓解这种偏差，提高了各种数据集上的泛化能力。
• “通过函数近似计算摊销的SHAP值”介绍了一种计算SHAP值的方法，SHAP值是一种可解释AI特征归因方法。使用神经网络和决策树集成的紧凑傅立叶表示来高效计算SHAP值，与现有方法相比实现了显著的加速。
• “高效学习傅立叶稀疏集函数”介绍了一种高效计算具有稀疏性和低阶假设的黑箱函数傅立叶变换的算法。这种算法通过利用低阶特性和新颖的哈希方案，超越了现有的稀疏沃尔什-哈达玛德变换。这项工作的一个扩展进一步提高了查询效率。

总体而言，本论文为探索监督学习模型中的频谱偏差奠定了基础，并提供了三个不同的章节，这些章节从不同的角度解决这一现象，提出了解决神经网络中频谱偏差、计算SHAP值和高效计算稀疏函数傅立叶变换的新方法。 在过去三十年中，监督学习领域取得了巨大的进步。这些努力大多集中在提供更准确的模型以适应各种不同的（监督）任务。在本论文中，我们研究了两类在表格数据上表现出色的非常成功的模型：（集成的）决策树和神经网络。这两种模型在训练后代表的函数具有一个通常被称为频谱偏差的属性。具体来说，我们可以准确地表示（在决策树集成的情况下）或高效地近似（在神经网络的情况下）这些模型，使用紧凑的傅立叶，也就是沃尔什-哈达玛德表示。这一基本事实是本论文的基础。在讨论我们的贡献之前，我们明确了我们对决策树模型和神经网络的频谱偏差的含义。 神经网络集成的频谱偏差： 我们知道，通过（随机）梯度下降训练的深度全连接网络代表的函数是“简单”的。这似乎与经典的关于神经网络的工作形成对比，经典工作显示深度全连接神经网络可以近似任意（复杂）函数，更常被称为通用逼近定理[1, 2]。然而，正如许多工作[3–7]所正式表明的，尽管深度网络可以学习任意复杂的函数，用于训练它们的算法，即（随机）梯度下降，产生的学习函数是“简单”的。这种简单性的概念并未得到一致认同，像[8–11]这样的工作每个都引入了不同的“简单性”概念。量化这种简单性的一种方式是通过傅立叶（频谱）域。在离散域，对于表格数据集，神经网络的输入是高维零一向量，Valle-Perez, Camargo & Louis [10]和Yang & Salman [12]为神经网络学习的函数提供了频谱偏差结果。通过将全连接神经网络视为将零一向量映射到实值的函数，可以用傅立叶——即沃尔什-哈达玛德——基函数来展开这个函数。通过对布尔立方体上的NTK格拉姆矩阵的分析，Yang & Salman [12]理论上显示，大致而言，神经网络倾向于学习低阶傅立叶频率。 我们澄清低阶频率的意义。沃尔什-哈达玛德基函数按其复杂度的自然顺序进行排序，称为它们的度数。度数指定了每个基函数依赖的特征数量。例如，零度基函数是常数函数，一度基函数是完全依赖于一个特征的函数。因此，当神经网络学习低阶频率时，意味着它代表的函数承认一个简单的分解形式。即如果函数是低度数d，那么它可以被写成（傅立叶基）函数的总和，其中每个函数最多依赖于d个变量。 决策树集成的频谱偏差： 我们知道，深度为d的决策树代表的函数是稀疏的，k = O(4^d)-稀疏，即它在支持中最多包含k = O(4^d)个非零傅立叶（沃尔什-哈达玛德）系数[13–15]。深度为d的决策树包含最多为d度的频率。将这一点扩展到决策树集成，如果集成由T棵不同的树组成，则其傅立叶变换是k = O(T4^d)-稀疏的，并且包含度数小于或等于其最大深度的频率。