Transformer内部计算里挖出预条件算法:RAPID在31个SuiteSparse矩阵上每一步都降低条件数
核心概要
一个只在上下文线性系统预测上训练的softmax注意力Transformer,其内部计算被追踪出一个保持解不变的合同变换,能改善Gram矩阵的条件数。研究者把它提炼成不含任何学习组件的独立算法RAPID:反复做随机正交混合,再让每行挑出最小的非对角元做稀疏修正。在四类合成谱和31个SuiteSparse对称正定矩阵上,RAPID在每一个测试步数下都降低了条件数,并减少了共轭梯度达到目标精度所需的迭代次数。
深度剖析
一个为上下文线性系统预测而训练的Transformer,其逐层计算本身就在改善矩阵条件数,这一效应可以被提取成一个与模型无关的数值算法。 此前对上下文学习的研究表明,Transformer能复现梯度下降、预条件梯度下降和类牛顿方法等已知算法;这次得到的是一个此前不在已知算法清单里的预条件原语。 在训练好的深度模型上,Gram矩阵的条件数中位数从约104降到103以下(最佳层),而用两个标量替换每层权重乘积后的近似迭代给出几乎相同的预测,平方Pearson相关系数为0.9999,测试MSE仅变化0.01%。
RAPID把这一原语变成可直接作用于任意对称正定矩阵的随时预条件器,每一步都产出一个合法的预条件因子。 经典预条件器通常构造不完全Cholesky分解、稀疏近似逆或代数多重网格层级,随机化Nyström则做一次性低秩近似;RAPID改为反复混合坐标再做稀疏局部修正,不显式计算特征向量或矩阵逆。 实验在四类合成谱(Chebyshev、线性、对数、幂律)和31个SuiteSparse对称正定矩阵上进行,矩阵按维度和Jacobi缩放后的条件数独立于RAPID表现挑选,全部按稠密算子处理。
条件数的改善转化为共轭梯度迭代次数的下降,且随RAPID步数增加而单调推进。 以Jacobi缩放后的矩阵为基准,比较对象是随机化Nyström预条件,后者对谱结构更敏感,在对数谱上有效,但在Chebyshev和线性谱上即使加大草图也提升有限。 在每一个测试步数下,RAPID都降低了全部31个SuiteSparse矩阵的条件数,而不只是平均值;所有求解器都达到目标精度,只有Nyström在一个SuiteSparse实例上失败。
启示与展望
实验覆盖四类合成谱的对称正定矩阵和31个SuiteSparse矩阵,全部转换为稠密形式,维度在数百到数千之间,Jacobi缩放后条件数约102到105;理论保证只针对采用Haar混合与分块行最小选择的理想化变体。
收敛定理依赖Haar混合的旋转对称性来刻画行最小漂移,实际使用的Walsh–Hadamard混合缺少这一精确不变性,把保证迁移过去仍是未解决的问题;全局行最小选择下的列负载界也只有经验支持。单步成本与稠密共轭梯度迭代在数量级上相当,但实际每步可能更贵,因为其算子没有同等优化的GPU实现,确定性的运行时间比较需要两边的优化实现。扩展到稀疏与无矩阵系统还需避免显式构造稠密混合矩阵。
