IGLM（二）：从样本挂载到迭代扩展的结构学习
说明：本文中的具体实现、数学整理与写作表述均由 GPT 辅助完成，笔者本人主要负责提出核心想法、研究方向与关键判断。
上一篇我先把核心定义立住了：如果要把“学习就是压缩”说清楚，那么需要一个明确的压缩对象。我这里给出的对象是最小计算元素集合，也就是
\[K_\Omega(f;\mathcal P) = \min_{S \leadsto f} |S \setminus \mathcal P|.\]这一篇继续往前走一步：既然最优结构可以定义出来，那学习过程本身该怎么理解？
我的看法是，IGLM 的训练过程天然可以拆成两个阶段：
- 先把样本挂载进去，保证信息不丢；
- 再通过迭代扩展和结构复用，把冗余解释压缩成更小的元素集合。
这和常规神经网络非常不一样。后者通常是一开始就在做连续优化，而 IGLM 更像是先搭材料，再做重写。
背景
如果只讨论最终的最小元素集合，问题会变得过于静态。实际学习过程中，模型不可能一开始就直接跳到最优结构，而是需要逐步积累中间元素。
这件事和很多工程问题很像：
- 你不可能直接写出最终最优程序；
- 你通常会先写一版能跑的；
- 然后识别重复逻辑，抽象公共模块；
- 最后再把整体结构收紧。
IGLM 也是同样的过程。它和直线程序复杂度的区别在于，我这里不只是想给出“最终最优大小”的定义，更想把“如何从样本走到这个结构”作为学习过程来建模。
样本挂载：先保证可表示
设训练集为
\[\mathcal D = \{(x^{(1)}, y^{(1)}), \dots, (x^{(N)}, y^{(N)})\}.\]为了便于讨论，仍然先考虑单输出布尔任务，$y^{(i)} \in {0,1}$。
最直接的学习策略，是先构造一个能够在训练集上完全正确的系统。也就是说，先满足
\[\forall (x,y) \in \mathcal D, \quad \hat f(x)=y.\]在 IGLM 里，我把这一步叫做“挂载”。
它的意义不是说这种结构已经足够好，而是说：
- 先把数据约束完整写入系统；
- 不急着立刻压缩；
- 给后续的结构合并提供材料。
如果用最朴素的想法来做，每个样本都可以先对应一段局部解释结构。这样得到的系统通常很大，但有一个很重要的优点：它一定覆盖了当前训练集。
这一步在概念上类似一个冗余的查找表，只不过后续不是直接停在这里，而是继续做结构压缩。
迭代扩展的数学定义
有了挂载阶段之后，下一步就是从已有元素出发，不断构造更高层的元素。
仍然记原始元素集合为
\[\mathcal P = \{x_1,\dots,x_n,0,1\},\]允许使用的二元运算符集合为
\[\Omega = \{op_1, op_2, \dots, op_r\}.\]定义第 $t$ 轮时模型已经拥有的计算元素集合为 $E_t$。初始化为
\[E_0 = \mathcal P.\]如果只考虑理论上的完全扩展，那么第 $t+1$ 轮的闭包为
\[E_{t+1}^{\mathrm{full}} = E_t \cup \{ op(g,h) \mid g,h \in E_t,\ op \in \Omega \}.\]这个定义非常暴力，但它至少把问题说清楚了：
学习不是在参数空间里微调一个函数，而是在元素空间里不断扩展可达集合。
如果目标函数 $f$ 在某一轮第一次出现在集合里，那么说明系统已经有能力表达它：
\[D_\Omega(f;\mathcal P)=\min\{t \mid f \in E_t^{\mathrm{full}}\}.\]不过完全扩展的代价很大，因为每一轮都要把所有成对组合都算一遍。这在理论上很干净，但在实现上几乎不可能直接用。
所以 IGLM 的真正重点不是做完整闭包，而是做“增量扩展”：
- 只扩展一小部分候选；
- 但长期来看仍然有机会覆盖重要结构；
- 并且一旦发现更优结构，就把旧结构重写掉。
从元素集合到结构图
虽然我这里没有把实现绑定到某一种固定图表示上，但为了理解方便，可以把每个元素 $g \in E_t$ 看成一个节点，而“由哪两个旧元素、通过哪个算子生成”看成这个节点的来源信息。
于是整个学习过程实际上在维护一个有向无环构造图：
- 原始元素是源点；
- 中间元素是内部节点；
- 目标输出是末端节点；
- 每条边都代表一次计算依赖。
这时，前一篇定义的最小计算元素集合，其实就对应于：
在所有能生成目标输出的构造图里，节点数最少的那一张。
如果训练只是挂载样本，不做任何合并，那么会得到大量彼此平行、几乎不共享的子图； 如果训练过程中能不断识别公共子结构，那么原本分散的构造图就会开始合并，最后形成更短的公共路径。
这就是我说的“压缩”。
为什么先挂载再压缩是合理的
这里最容易被质疑的一点是：为什么不一开始就搜索最优结构，而要先允许冗余？
答案很简单，因为在数据还不充分、结构还没长出来的时候，过早压缩很容易得到错误规律。
这件事在离散任务上尤其明显。假设只看到了很少几个样本，那么存在大量不同的短结构都能拟合当前训练集。如果此时强行选择其中一个最短结构，它很可能只是碰巧解释了这几个点，而不是任务真正的规律。
相反，先挂载更多样本，相当于先把约束条件写完整。随着样本增多，那些“投机取巧”的短结构会逐渐被排除，真正稳定的公共结构才会被保留下来。
所以“先挂载再压缩”并不是浪费，而是在给最优结构创造可辨认条件。
一个更具体的形式：经验风险约束下的最小元素集
把上面的想法写得更明确一点，可以得到一个约束优化问题。
对于训练集 $\mathcal D$，定义经验误差
\[\mathcal L_\mathcal D(g) = \frac{1}{|\mathcal D|}\sum_{(x,y)\in\mathcal D} \mathbf 1[g(x) \neq y].\]如果只考虑完全拟合训练集，那么目标是求
\[\min_{g} K_\Omega(g;\mathcal P) \quad \text{s.t.} \quad \mathcal L_\mathcal D(g)=0.\]这个表达已经很接近我想要的学习定义了：
在所有能把训练集解释正确的结构里，选择元素数量最少的那个。
如果允许一定程度的近似压缩，也可以写成
\[\min_{g} \big( K_\Omega(g;\mathcal P) + \lambda \mathcal L_\mathcal D(g) \big),\]其中 $\lambda > 0$ 控制拟合和压缩之间的权衡。
不过这一系列文章当前还是以“先不考虑近似误差”为主，所以我后面主要讨论 $\mathcal L_\mathcal D(g)=0$ 的情形。
泛化为什么会自然出现
从这个视角看，泛化其实并不神秘。
假设训练集只覆盖了输入空间的一部分点。如果系统只是逐点记忆，那么在训练集之外它几乎没有任何依据，自然也谈不上泛化。
但如果训练过程确实找到了一个很小的元素集合，并且这个元素集合对应一个在整个输入空间上定义良好的计算结构，那么它就会自动把未见输入也映射出去。
此时泛化好不好，取决于这个压缩出来的结构是否真的是任务的内在规律，而不是训练样本的偶然拼接。
所以 IGLM 对泛化的理解是：
泛化不是额外奖励，而是共同结构被成功抽取之后的自然外延。
一个简单例子：逐点记忆与共享中间量
考虑 1-bit 全加器的和位
\[s = a \oplus b \oplus c_{in}.\]如果把 8 个输入输出样本逐点记忆，那么最坏情况下需要接近样本数规模的局部结构。
但如果先构造一个中间量
\[t = a \oplus b,\]再构造
\[s = t \oplus c_{in},\]那么 8 个样本就被两个关键中间元素统一解释了。更进一步，进位位
\[c_{out} = (a \land b) \lor (c_{in} \land (a \oplus b))\]也能复用前面得到的 $t = a \oplus b$。
这正是我关心的结构性现象：
- 中间元素一旦被发现；
- 它就不只服务某一个样本；
- 而是同时服务很多输入点，甚至多个输出位；
- 整个系统的元素总数因此明显下降。
这一篇的结论
到这里，IGLM 的学习过程可以用一句话概括：
学习 = 在训练样本约束下，迭代扩展计算元素集合，并不断把冗余解释压缩成更小的共享结构。
更具体一点，就是：
- 初始元素集合是 $E_0=\mathcal P$；
- 新元素由已有元素通过二元运算符组合得到；
- 样本挂载保证当前训练信息可表示；
- 结构压缩的目标是逼近最小元素集合；
- 一旦发现共享中间元素，整体复杂度就会下降，并自然带来泛化。
下一篇我会把这个过程进一步具体成一个算法：DILR。它的核心不是一次性做完整闭包，而是在当前元素池里随机挑选元素，用二元运算符组合出新元素，并且对同一个结果始终保留当前最短路径。这样就能得到一个“算力越多，结构越优”的单调逼近过程，也可以进一步用来解释 scaling law。