K-Inverse-RFM: 一种改进的递归特征机器，弥合神经网络在处理数据损坏数学任务中的差距

# K-Inverse-RFM：一种改进的RFM，用于弥合神经网络在数据损坏数学任务中的差距  
来源：https://arxiv.org/html/2607.00329  
\\increasemargins \.1in  
\\degree计算机科学  
\\硕士学位  
\\chairRamamohan Paturi  
\\committeeMikhail Belkin  
\\committeeTaylor Berg\-Kirkpatrick  
\\degreeyear2025  
\\makecopyright  
\\makesignature  
\{dedication\}  
\\setsinglespacing  
致我伟大的父母——他们一生中搬了12,500英里，只为给我今天提交这篇论文的机会  
致我的妹妹，感谢你成为我成长中的朋友  
致我的外祖父母，感谢你们无限的爱、支持和友谊  
致我的祖父母，感谢你们的爱——希望我没有让你们失望  
致我的曾祖父迈克尔，感谢你为我铺平了道路  
致丹妮尔，感谢你的爱让我熬过艰难的日子  
致亚历克、埃里克、约翰、杰西、阿隆、阿萨夫、温克勒：感谢你们无尽的支持、建议和欢笑  

###### 目录  
1. 1引言 (https://arxiv.org/html/2607.00329#Ch1)  
2. 2相关背景 (https://arxiv.org/html/2607.00329#Ch2)  
   1. 2\.1核与核岭回归 (https://arxiv.org/html/2607.00329#Ch2.S1)  
   2. 2\.2AGOP与神经特征假设 (https://arxiv.org/html/2607.00329#Ch2.S2)  
   3. 2\.3递归特征机器 (https://arxiv.org/html/2607.00329#Ch2.S3)  
   4. 2\.4模算术的Grokking现象 (https://arxiv.org/html/2607.00329#Ch2.S4)  
3. 3RFM\-NN差距 (https://arxiv.org/html/2607.00329#Ch3)  
   1. 3\.1标签噪声 (https://arxiv.org/html/2607.00329#Ch3.S1)  
   2. 3\.2不平衡数据 (https://arxiv.org/html/2607.00329#Ch3.S2)  
      1. 3\.2\.1输入与输出不平衡 (https://arxiv.org/html/2607.00329#Ch3.S2.SS1)  
      2. 3\.2\.2系统性排除 (https://arxiv.org/html/2607.00329#Ch3.S2.SS2)  
   3. 3\.3替代数据表示 (https://arxiv.org/html/2607.00329#Ch3.S3)  
4. 4弥合差距：K\-Inverse\-RFM (https://arxiv.org/html/2607.00329#Ch4)  
   1. 4\.1方法 (https://arxiv.org/html/2607.00329#Ch4.S1)  
   2. 4\.2结果 (https://arxiv.org/html/2607.00329#Ch4.S2)  
      1. 4\.2\.1标签噪声 (https://arxiv.org/html/2607.00329#Ch4.S2.SS1)  
      2. 4\.2\.2不平衡数据 (https://arxiv.org/html/2607.00329#Ch4.S2.SS2)  
      3. 4\.2\.3替代数据表示 (https://arxiv.org/html/2607.00329#Ch4.S2.SS3)  
   3. 4\.3综合分析 (https://arxiv.org/html/2607.00329#Ch4.S3)  
5. 5结论、局限性与未来方向 (https://arxiv.org/html/2607.00329#Ch5)  
6. A关于神经网络性质的有趣观察 (https://arxiv.org/html/2607.00329#A1)  
   1. A\.1神经网络早期学习鲁棒特征 (https://arxiv.org/html/2607.00329#A1.S1)  
   2. A\.2第二层用于特异性 (https://arxiv.org/html/2607.00329#A1.S2)  
   3. A\.3宽度与角色的关系 (https://arxiv.org/html/2607.00329#A1.S3)  
7. 参考文献 (https://arxiv.org/html/2607.00329#bib)  

###### 图列表  
1. 3\.1RFM与神经网络在模加法（上，p=61）和模乘法（下，p=61）训练步骤上的测试集性能对比 (https://arxiv.org/html/2607.00329#Ch3.F1)  
2. 3\.2RFM与神经网络在模加法（左，p=61）和模乘法（右，p=61）训练步骤上的测试集性能对比 (https://arxiv.org/html/2607.00329#Ch3.F2)  
3. 3\.3含噪声训练数据的模加法各种方法比较 (https://arxiv.org/html/2607.00329#Ch3.F3)  
4. 3\.4RFM与神经网络在可被3整除的输入对和标签的多种重新加权下的性能比较 (https://arxiv.org/html/2607.00329#Ch3.F4)  
5. 3\.5随着训练集中可被3整除输入权重的增加，RFM在可被3整除输入与不可被3整除输入上的模加法性能比值 (https://arxiv.org/html/2607.00329#Ch3.F5)  
6. 3\.6模乘法任务（p=61）中，可被3整除输入不同权重（有放回输入采样）下的方法比较 (https://arxiv.org/html/2607.00329#Ch3.F6)  
7. 3\.7模乘法任务（p=61）中，不同输入排除形式下的方法比较 (https://arxiv.org/html/2607.00329#Ch3.F7)  
8. 3\.8RFM与神经网络在不同CRT编码下的性能比较 (https://arxiv.org/html/2607.00329#Ch3.F8)  
9. 3\.9拉普拉斯核与神经网络第一层（后非线性）特征在多种CRT编码下的性能比较 (https://arxiv.org/html/2607.00329#Ch3.F9)  
10. 4\.1RFM、K\-Inverse\-RFM与神经网络在模加法和模乘法上的性能比较 (https://arxiv.org/html/2607.00329#Ch4.F1)  
11. 4\.2RFM、K\-Inverse\-RFM与神经网络在模加法和模乘法上的性能比较 (https://arxiv.org/html/2607.00329#Ch4.F2)  
12. 4\.3按每个不均匀样本中唯一点数重新解读图4\.2 (https://arxiv.org/html/2607.00329#Ch4.F3)  
13. 4\.4K\-Inverse、RFM与神经网络在模加法不同排除输入上的比较 (https://arxiv.org/html/2607.00329#Ch4.F4)  
14. 4\.5RFM、K\-Inverse\-RFM与神经网络在图3\.8中不同CRT编码大小上的比较 (https://arxiv.org/html/2607.00329#Ch4.F5)  
15. A\.1\textbf{上排：}在32%训练集标签噪声下训练的二次激活神经网络，与在其第一层和第二层后非线性特征上训练的拉普拉斯核预测器比较 (https://arxiv.org/html/2607.00329#A1.F1)  
16. A\.2不同第二层宽度下二次激活函数的2层神经网络性能 (https://arxiv.org/html/2607.00329#A1.F2)  
17. A\.3模乘法任务中第一层和第二层宽度变化的二次激活2层神经网络性能 (https://arxiv.org/html/2607.00329#A1.F3)  

###### 致谢  
攻读硕士学位与攻读学士学位的经历截然不同。本科期间，我学会了完全为自己的结果和表现负责；而硕士阶段则是一段合作与向他人学习的历程。因此，有几位关键人物若没有他们的帮助，这项研究将无法完成。  
首先，我衷心感谢我的导师Mikhail Belkin和Ramamohan Paturi，没有他们，这篇论文不可能完成。Belkin博士——感谢您带我走进RFM和AGOP的世界，用您的讲座深深吸引了我，并给予我指导和支持，使我能够为这一领域做出贡献。我对您的感激之情无以言表。Paturi博士——感谢您在我硕士期间的指导，以及教会我如何成为一名研究者。您对AI Tutor项目和偏差风险基准项目的见解、鼓励我紧跟最新文献、以及对本论文的指导，都无比宝贵。没有您的指导，我无法想象自己会走上研究之路。  
本文中的许多工作还得益于Neil Mallinar的指导，他的无限耐心和乐于助人令我深表感激。值得注意的是，Neil提出了我第一次尝试的K\-Inverse的初版，我很高兴有机会在他的工作基础上进一步发展。我还要感谢Leon Bergen、Andre Wang以及LEI小组其他成员。Bergen博士——感谢您引导我早期的研究工作，向我介绍更广阔的研究图景，并指导我完成第一个完整的研究项目。Andre Wang和LEI的其他成员——感谢你们对我的信任，以及在偏差风险基准项目上的合作。  
此外，我还要感谢Hannah Carter、James Talwar、Seth Levine和Colin Jemmott——我的第一批研究导师。你们的指导是我继续追求研究的原因。Carter博士——感谢您的指导，并帮助我整体规划研究生学习。James——我非常珍视您的友谊和无尽的建议，正是这些帮助我在两年内取得了远超想象的成就。Seth——您的指导（和友谊）、建议和鼓励给了我创作自由，让我成长为一名独立的研究者。您在我塑造对这一职业的热爱中扮演了重要角色，对此我无比感激。Jemmott教授——感谢您在我18岁、毫无经验时对我充满信心。没有您的课程和Likelihood研究项目，我不知道自己是否会从事研究、攻读硕士学位，甚至从事人工智能领域的工作。  
所有这一切都离不开我的家人。爸爸妈妈——你们逃离了崩溃的苏联，两次背井离乡，为你们和孩子们寻找更好的生活。你们为我们离开父母、亲戚和朋友，搬到数千英里之外，并辛勤工作，使我的美国梦成为可能。你们在道德和智力上倾注了无数心血来教育我。不用说，没有你们就没有今天的我。Yael——感谢你一直以来的好朋友，我真的很感激你。致我的外祖父母——感谢你们每天第一个给我打电话。我们非常规律的交谈和无穷的笑声让我从根本上变得更快乐，并激励我朝着曾经认为不可能的地平线努力。致我的祖父母——感谢你们的爱与支持。愿你们的记忆是一种祝福。  
最后，任何致谢都不能缺少对丰富我生活的爱与友谊的认可。Danielle——感谢你在论文旅程中无尽的爱、积极和鼓励。你的力量、光彩和对生活的热爱激励着我，在那些似乎一切都不顺利的日子里，你是我前进的动力。我非常感激你。Alec——我深深感谢你过去十年的友谊。回想起来，我所取得的任何成就中，几乎都有你的参与——无论是教我写作、在你全职工作时帮我启动STEMLearn，还是帮我做出艰难的人生决定。Eric——除了你的工作态度推动我在每日联合工作期间实际完成这篇论文，以及你帮助将STEMLearn变为现实，你在过去的八年里一直是我生活中最可靠、最稳定、最值得信赖的人之一。我感激不尽。John——感谢你八年的非凡友谊、无数只有我们懂的共同欢笑，以及你无限的善良和可靠。Alon——感谢你在整个硕士期间成为世界上最好的室友，愿意倾听任何研究讨论，并一直是一个很棒的朋友。Jesse——感谢你总是愿意倾听技术或非技术（生活）问题，无数次帮我调试代码，以及八年来的真挚友谊。  
还有许多人在过去两年中对我的生活产生了深远影响。虽然无法在此一一列举，但我要向Winkler、Assaf、Daniel、Alex、Eugene、Mendy、Fung博士、Maxes、Varun、Upo以及更多朋友表示感谢——感谢你们所做的一切。这篇论文是许多人指导、支持和友谊的产物，我对你们每一位都感激不尽。  

\{dissertationabstract\}  
递归特征机器（RFMs）是一类利用平均梯度外积（AGOP）作为特征学习机制的核机器。它们已被证明能够在多种设置下有效复制前馈神经网络（FNNs）的学习动态和特征表示。然而，尽管在特征学习能力以及获取的特征相似性方面相当，RFMs在某些数据相关场景下的性能显著低于神经网络。在本工作中，我们针对数学问题研究了这些局限性。作为解决方案，我们引入了一种对训练标签进行惊人有效的变换，该变换能够促进在含噪声、复杂表示和类别不平衡数据中的学习。这一简单而强大的调整使得RFMs能够弥合与FNNs的性能差距，甚至在某些情况下超越它们。  

## 第一章 引言  
神经网络是当今最强大且广泛使用的学习算法之一，应用涵盖语言处理、计算机视觉和生物学。其成功的一个基本方面是能够学习非线性特征——通常是在较低维子空间中。这种特征学习机制相比经典方法（如线性回归、决策树和提升方法）具有显著优势，这些方法通常参数较少，且缺乏发现复杂特征交互的隐式偏差。  
最近的研究表明，将一种称为平均梯度外积（AGOP）的特征学习机制与核回归相结合，有助于弥合经典方法与神经网络之间的差距。由此产生的模型——递归特征机器（RFMs）originalrfm2023——已被证明在表格数据基准上能够匹配或超越神经网络性能。它们还以高度相关性复制神经网络的表示，并表现出关键的神经学习现象，包括Loterry Ticket假设和Grokking。一个经过实证验证的神经特征假设（Neural Feature Ansatz）表明，RFMs倾向于逼近神经网络的神经特征矩阵。  
在本工作中，我们对神经网络与RFMs在数学问题（如模算术和最大公约数）上的差异进行了深入研究。通过广泛的实验，我们观察到在数据被标签噪声破坏、标签分布不均匀或以复杂方式表示时，RFMs与神经网络之间存在差距。我们在第三章中全面回顾了这些结果。然后在第四章中，我们提出并论证了一种称为“K\-Inverse\-RFM”的解决方案，这是对RFM的修改，用于解决这些问题。“K\-Inverse\-RFM”能够稳定地弥合RFMs与神经网络在这些情境下的部分或全部差距，有时甚至超越神经网络，并且可以轻松在CPU上训练。我们还提供了所有任务上的全面结果，并深入分析了K\-Inverse\-RFM何时可能成功。最后，在第五章和附录中，我们概述了潜在的未来方向以及从实验中收集到的其他有趣的RFM/神经网络相关观察。总之，我们的贡献如下：  
- •我们对RFMs在多种离散数学任务上的性能进行了深入研究。  
- •我们定位并理解了神经网络性能与RFM性能之间的各种差距。  
- •我们提出了一种RFM的改进以解决这些不足，并对其性能进行了全面比较。  
- •我们解释了实验中发现的其它有趣的神经网络现象，表明有时仅使用第一层特征就能超越神经网络的整体性能。  

## 第二章 相关背景  
### 2.1 核与核岭回归  
我们首先介绍核方法与核岭回归，后者被我们的RFM用作预测模型。核方法是一个迷人的研究领域，可以深入探讨liang2016kernel，但为简洁起见，我们仅提供必要内容。