从几何角度解析动态规划模型泛化难的原因
On the Representational Geometry of Dynamic Programs
- 用图、多项式、多面体三重几何描述动态规划结构
- 发现长度泛化时决策边界无法直接延续，存在结构性障碍
- 适合研究模型泛化与形式推理的学者参考
标准神经架构在处理更长输入的动态规划（DP）任务时往往表现不佳。本文从几何角度探究其原因：每个有限的 min-plus DP 都可视为有向无环图（DAG）上的最短路径，等价于一个热带多项式，其扩展牛顿多面体编码了决定最优路径的决策边界。我们证明这三种描述（图、多项式、多面体）在形式多项式与计算函数两个层次上构成同构的半环，并由刻画所有结构冗余的操作连接。随后，我们从几何角度分析长度泛化问题：长度为 T 时的决策边界能否决定长度为 T+1 时的边界？我们给出两个结构性反例：半环中两种降维方式（将变量设为各恒等元）既不单射也不总封闭于 DP；串并联组合无法构建所有 DAG 拓扑，甚至仅终端操作也无法涵盖所有 DP 组合。
原文摘要 · Abstract (English)
Standard neural architectures often fail to generalize to longer inputs for dynamic programming (DP) targets. We investigate what makes this hard geometrically. Every finite min-plus DP is a shortest path on a DAG, which is equivalently a tropical polynomial whose extended Newton polyhedron encodes the decision boundary of which path wins. We prove these three descriptions (graph, polynomial, polyhedron) form isomorphic semirings at two levels --- formal polynomials and their computed functions --- connected by operations that characterize all structural redundancies. We then address the length-generalization question geometrically: does the decision boundary at length $T$ decide the boundary at $T+1$? We present two structural negatives. The semiring's two native ways to reduce dimension (setting a variable to each identity) are neither injective nor always closed within the DP. Series and parallel composition fail to construct all DAG topologies from smaller sub-DAGs, and even all terminal-only operations do not capture all DP compositions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。