Self-Delimiting Neural Networks
Juergen Schmidhuber
cs.NE
2012-09-29
给RNN加停机神经元和阈值激活,一次计算只追踪用过的连接;未用权重不进学习搜索,网络按任务自选有效规模。全文没有SLIM的实验数字。
RNN 的权重矩阵就是程序。一个足够稀疏的网络,用非线性 AND / NAND 当神经元,可以直接模拟传统微处理器,所以 RNN 原则上能当通用计算机用。
但渐近最优程序搜索(AOPS)一直没接到 RNN 上。AOPS 的经典对象是顺序的自定界程序:指令指针指到没见过的地址,就在线要一条新指令,接到当前程序末尾;遇到停机指令就结束。停机程序构成前缀码,没有哪一段会是另一段的前缀。2012 年主流的 RNN 训练是梯度下降和进化。矩阵乘法实现还会把整张权重表乘一遍,哪怕绝大多数连接这次根本没被点亮。过拟合靠事先写进目标函数的正则项,权重怎么配没有原则。Schmidhuber 还想把网络接到 PowerPlay 上,一个从零开始不断发明「当前最容易新增」任务的通用求解器,传统 RNN 切不出互不干扰的任务模块。
SLIM NN 给网络加一个特殊的停机神经元,激活函数改成阈值,或者一组里只留赢家的 winner-take-all。目的很具体:让大多数单元在大多数时刻保持静默,程序才有机会自己决定自己有多长。
一次计算回合从输入神经元往外传激活。输出可以改环境,环境再给新输入。停机神经元被点亮,回合结束;否则用学习算法给出的时间上限 $t{lim}$ 强行切断。这次用过的连接权重就是这段程序。
Spread 过程用三张表(old / new / trace)只跟踪最近两步用过的神经元和至少用过一次的连接。没被点到的出边根本不会被读。重置初始状态的代价不超过刚跑完的这段程序。论文里的思想实验是一张万亿连接、十亿神经元、每人一千出边的稀疏网:一次计算可能只点亮极小一部分,矩阵乘法在这种网上是在给空气做乘法。
学习算法必须跳过所有未用权重。程序前缀决定后缀,早发生的权重变化会改变后面哪些连接被考虑,所以权重修改要嵌在激活传播过程里在线做。网络生长也走这条路:某条连接第一次被点到、权重还没定义,可以临时赋一个非零值,有效拓扑就长出这条边。
每条连接维护一份任务列表,记录自己服务过哪些任务。改完权重,只在这些列表的并集上重测,并集以外的任务表现保证不变。
Universal SLIM NN Search 把 Levin 搜索套上来。每个候选 trace 分到的搜索时间份额跟它的概率成正比。若某个未知程序用不超过 $f(k)$ 步解决规模为 $k$ 的问题并完成验证,整个搜索也是 $O(f(k))$ 步。实现上用程序前缀空间的深度优先加栈回溯,和 2004 年的 Optimal Ordered Problem Solver(OOPS)同一套路。
成功之后可以平移偏置。对用过的连接统计「源和目标下一步同时为 1」的次数 yes,以及「源为 1、目标为 0」的次数 no,令 $\Delta=(\mathrm{yes}-\mathrm{no})/$ 使用次数,落在 $[-1,1]$。学习率 $\eta$ 按 $\Delta$ 的符号加大或减小该权重取值的概率。$\Delta$ 为负就降低当前权重的概率,为正就抬高。这是 Hebb 规则写在概率分布上的版本。
概率的负对数就是 Huffman 编码这段 trace 所需的比特数。短、快、概率高是同一件事,Occam 剃刀被写进了搜索的时间分配里,不再是目标函数上另挂的正则超参。
面向当时设想的三维多处理器硬件,每条连接带一个常数代价,可以看成线长。目标函数加上 $\sum$ 线长 $\times$ 使用次数,子任务会被逼到物理上靠近的神经元子集上去解。Universal Search 本身已经在按代价分配时间,这条惩罚不必另挂超参。
这篇是技术报告,不是实验论文。第 4 节写明第一批实验正在 PowerPlay 框架里做,结果另文发表。SLIM NN 在任何公开 benchmark 上都没有数字。
文中出现的错误率全部属于 IDSIA 组 2009 到 2012 年用别的网络拿下的竞赛,用来说明 RNN 已经能在真实任务上干活,不能当成 SLIM 的成绩:
| 来源 | 指标 | 数字 | 是不是 SLIM |
| MNIST 2012 多列深度网 | 错误率 | 0.23% | 否 |
| IJCNN 2011 交通标志 | 错误率 | 0.56%(人类平均 1.16%) | 否 |
| ICDAR 2009 手写识别 | 名次 | LSTM RNN 拿下法/阿/波斯三项冠军 | 否 |
理论侧写清楚了两件事。Universal SLIM NN Search 近偏置最优、渐近最优。前缀码性质在可重置的确定性环境里成立;环境不可重置时,要把环境输入也算进程序,前缀码才保得住。
对 2012 年还在用爬山法和神经进化的人,约束很实在:搜索空间从整张权重矩阵缩到这次实际用到的连接。对现在做稀疏激活、条件计算、混合专家的人,Spread 的「只算点亮的边」并不陌生,只是当时没有对应的 GPU kernel。
把它当可落地的训练算法会失望。阈值激活切断了反传,Levin 搜索的组合爆炸在权重空间里没有消失。这篇的价值是把 Kolmogorov 复杂度、算法概率和神经网络接到同一套记号上,并给出一条原则性的反过拟合路径:让网络按任务自己选有效自由参数个数。
PowerPlay 那一节更接近后来的课程学习和模块化。系统优先发明验证代价低的新任务,等于隐式奖励「别改太多旧权重」,任务空间会自己裂成相对独立的区域。
作者自己把实验推到另文。到这篇为止,SLIM NN 没有公开的分类或控制数字,无法判断「自选规模」到底有没有压过拟合。
阈值和 winner-take-all 让网络容易自定界,也让梯度没了。和当时已经打赢竞赛的 LSTM、卷积深度网不是一条训练路线。
前缀码论证依赖可重置的确定性环境。真实机器人、在线数据流都不满足这个假设。
万亿连接的加速是思想实验,没有实现、没有测过墙钟时间。三维硬件和按线长惩罚是展望,2012 年没有对应芯片。
$O(f(k))$ 藏着巨大的常数因子:要枚举程序前缀。OOPS 用深度优先加栈回溯减过这个常数,论文没有给出 SLIM 版的实测搜索时间。