用凯莱表补全测试深度学习对离散代数规则的泛化能力缺陷。
Open Problem: Separating Geometric and Algorithmic Compression via Cayley-Table Completion
- 以凯莱表补全为基准任务，检验模型对离散代数结构的隐式偏好。
- 现有方法通过张量分解与平坦性先验，能自动发现结合律等离散代数规律。
- 挑战在于建立严格恢复边界，推动算法复杂度最小化的通用先验设计。
现代统计学习理论与深度学习主要基于连续容量控制（如范数正则化、间隔最大化、低秩偏置）来解释泛化能力。尽管在连续域表现优异，深度学习却始终无法外推精确的算法或离散代数规则，反映出缺乏对算法复杂度最小化的归纳偏置。本文提出凯莱表补全作为该缺失偏置的典型测试场景，其地位相当于离散代数领域的矩阵补全。正如矩阵分解结合权重衰减产生低线性秩的隐式几何偏置，近期研究表明，算子值张量分解搭配平坦性先验可产生对精确离散结合律的隐式算法偏置。本文提出开放问题：建立凯莱表补全的严格精确恢复边界，并呼吁社区将连续平坦性先验推广至自主发现更广泛离散代数公理，而无需组合搜索。
原文摘要 · Abstract (English)
Modern statistical learning theory and deep learning characterize generalization primarily in terms of continuous capacity control (e.g., norm-based regularization, margin maximization, low-rank bias). While highly successful in continuous domains, deep learning consistently fails to extrapolate exact algorithmic or discrete algebraic rules, reflecting a missing inductive bias toward algorithmic complexity minimization. We propose the Cayley-table completion as the canonical testbed for this missing bias, serving as the discrete algebraic counterpart to matrix completion. Just as matrix factorization combined with weight decay yields an implicit geometric bias toward low linear rank, recent results demonstrate that operator-valued tensor factorizations paired with a flatness prior yield an implicit algorithmic bias toward exact discrete associativity. We pose the open problem of establishing formal exact recovery bounds for Cayley-table completion, and challenge the community to generalize continuous flatness priors to autonomously discover broader discrete algorithmic axioms without combinatorial search.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。