arXiv:2512.14338cs.LG2025-12

Hopfield网络能从部分图数据中自动学习对称性,实现高效记忆。

Implicit Bias and Invariance: How Hopfield Networks Efficiently Learn Graph Orbits

  • 用能量梯度下降等价于最小范数支持向量机,实现隐式对称学习
  • 少量随机样本即可逼近完整对称结构,样本数与图大小无关
  • 适用于图同构问题,尤其在稠密图中效率更高,适合对称数据学习

许多学习问题具有群对称性。尽管通常通过架构或群平均来施加不变性,我们探讨在仅从轨道的有限随机子集中训练时,不变性是否可自发产生。研究聚焦于经典霍普菲尔德网络,其中严格记忆可表示为线性间隔问题。将能量流最小化(MEF)重参数化为指数损失,使梯度下降等价于对应的最小范数硬间隔记忆器。主要结果表明:对于任意有限置换轨道的独立均匀采样,精确样本硬间隔支持向量机(HSVM)以指数速度集中在不变的全轨道HSVM附近。因此,仅需轨道大小无关的多项式数量样本,即可同时实现近似参数不变性和所有轨道元素的记忆;方向收敛将此结论渐进推广至MEF梯度下降。针对图同构轨道,我们刻画了不变参数为三维子空间,并证明每类轨道均可记忆。对于固定线性密度的团,额外对称性将均匀记忆界优化至$O(v^4\log(1/δ))$,远小于轨道规模。结合多种学习规则的实验,这些结果为优化偏差如何从部分群结构数据中恢复对称性提供了有限样本解释。

原文摘要 · Abstract (English)

Many learning problems are organized by group symmetries. While invariance is often imposed through architectures or group averaging, we ask when it can emerge from training on a finite random subset of an orbit. We study this question in classical Hopfield networks, where strict memorization can be expressed as a linear margin problem. Reparameterizing minimization of energy flow (MEF) as an exponential loss connects gradient descent to the corresponding minimum-norm hard-margin memorizer. Our main result shows that, for independent uniform samples from any finite permutation orbit, the exact sample hard-margin support vector machine (HSVM) concentrates exponentially around the invariant full-orbit HSVM. Consequently, an orbit-size-independent polynomial number of samples suffices both for approximate parameter invariance and for simultaneous memorization of every orbit element; directional convergence transfers this conclusion asymptotically to MEF gradient descent. For graph-isomorphism orbits, we characterize the invariant parameters as a three-dimensional subspace and show that every such orbit is memorizable. For cliques of fixed linear density, additional symmetry sharpens the uniform memorization bound to $O(v^4\log(1/δ))$, exponentially smaller than the orbit size. Together with experiments across several learning rules, these results give a finite-sample account of how optimization bias can recover symmetry from partial group-structured data.

霍普菲尔德网络对称性学习图同构优化偏差

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。