神经控制器只学专家动作轨迹,也能被证明精确执行算法:4335参数DFST在500符号上限通过全部10项通用模拟任务
核心概要
一种可微精确学习框架把状态追踪神经控制器接到可无限扩展的外部网格环境上,只用记录专家观察与动作、隐藏内部状态的动作轨迹观测训练。4335个参数的DFST仅用75条轨迹、输入不超过5个符号,就在全部10项通用模拟任务上达到500符号评测上限,其中5个程序未参与训练;从训练好的模型提取出的离散控制器还被证明与专家通用解释器等价。
深度剖析
神经控制器现在可以在只看到专家动作、看不到专家内部状态的情况下,被训练成能处理任意长输入的算法执行器,并且训练完成后还能从中提取出可被证明正确的离散控制器。 此前从输入输出对学习算术的Transformer和RNN只能向更长输入做有限外推,而能证明恢复十进制加法的神经程序解释器依赖递归调用与返回标注,这种监督强于只观察外部环境中的专家动作。 在二进制与十进制加法、乘法上,DFST在操作数最多3位(加法)和5位(乘法)的轨迹上训练后,达到加法每操作数5000位、乘法1000位的测试上限,且同时通过随机探针与全9、全1这类结构化重复数字探针。
做法是把一个能模拟有限状态机的神经控制器放进一个按需增长的符号网格,控制器每步只读当前格子的符号,输出要写的符号和移动方向。 训练信号是动作轨迹观测,它记录环境在专家策略下如何变化,但不暴露专家的内部状态转移;这避开了仅凭输入输出无法在极限内识别全部可计算函数的障碍。 通用模拟任务中,15维、4335个参数的DFST用5个程序、输入不超过5个符号的75条轨迹训练,在含5个未见过程序的10项任务上达到500符号上限;最长的采样轨迹需要15316822次连续动作匹配。
训练后的模型可以通过聚类隐藏状态或对Softmax转移概率做锐化,读出一个有限的离散状态机,再对这个离散对象做归纳证明。 有限长度的测试本身无法证明任意长输入上的正确性,因为不存在一个可计算的有限测试长度能保证两个网格智能体在所有输入上一致。 八份证书覆盖二进制与十进制的加法、乘法以及通用模拟;通用控制器被证明能在任意非空二进制输入上正确模拟任意二进制图灵机,而把结论转移到神经控制器本身还需要图稳定性或有界泄漏这两类假设。
启示与展望
已展示的范围是符号网格上的二进制与十进制加法、乘法,以及一个15状态的通用图灵机模拟器;评测采用带上限的搜索,加法5000位、乘法1000位、通用模拟500符号,通用任务的训练输入不超过5个符号。读者对象是关心算法外推与形式化验证的机器学习研究者。
把提取控制器的等价性转移到神经控制器,需要图稳定性或有界泄漏假设,这些假设只有经验支持而非证明。Softmax DFST在十进制任务上连小训练集都难以拟合,普通DFST的成功也随训练日程变化,更多更新不一定改善泛化。
