给 ES-HyperNEAT 的四叉树做梯度测试
第 2 部分，共 2 部分。用一次梯度代替四叉树的 2ⁿ 次采样，只需一小部分搜索量，就能找到同样好的网络。
September 23, 2026
ES-HyperNEAT（Risi & Stanley, 2012）决定隐藏神经元放在哪里的方法，是在它检查的每个单元的 \(2^n\) 个子单元上计算 CPPN。这就是基底每增加一个维度，它的搜索就指数级变慢的原因。但在一阶近似下，这 \(2^n\) 个样本只测量了一样东西：权重场梯度的平方。而无论维数多少，一次梯度只需要一次前向传播和一次反向传播。
于是我换掉了这个测试。梯度版本在 98.7% 的情况下与采样做出相同的切分决定，在三维基底上只用大约六分之一的搜索时间，就找到了同样好的网络。更聪明的采样器能追回一部分差距，而树本身仍然是指数级增长的。
认知状态：两者的等价性经过推导，也做了数值验证。训练对比是在一个玩具任务上的 8 对配对运行，足以排除性能上的大差异，但排除不了小差异。
第 1 部分介绍了 ES-HyperNEAT 和这里用到的转向任务。简单说：HyperNEAT 用一个叫 CPPN 的小网络，根据每条连接两端神经元的坐标计算它的权重，\(w = f(\mathbf{p}, \mathbf{q})\)；ES-HyperNEAT 把隐藏神经元放在 \(f\) 变化的地方，并用四叉树找出这些地方。
第 1 部分发现，让基底的维数与问题匹配是有帮助的，而每多一个维度，四叉树搜索的成本就成倍增加。
1. 在一阶近似下，2ⁿ 次采样测量的是同一个梯度
当 CPPN 在一个单元的 \(2^n\) 个子单元中心处给出的权重，方差超过阈值 \(\tau\) 时，四叉树就切分这个单元。一个小单元内的方差，衡量的是权重场在那里变化得有多快，而这正是梯度告诉你的事。
取一个中心为 \(c\)、半宽为 \(r\) 的单元。它的子单元中心是 \(c + \tfrac{r}{2}\sigma\)，其中 \(\sigma\) 取遍所有 \(\pm 1\) 的符号组合。在 \(c\) 附近，场近似是线性的：
\[w\!\left(c + \tfrac{r}{2}\sigma\right) \approx w(c) + \tfrac{r}{2}\, \sigma \cdot \nabla w(c)\]在这 \(2^n\) 种符号组合里，每个 \(\sigma_i\) 一半时候是 \(+1\)、一半时候是 \(-1\)，且彼此独立，所以 \(\mathbb{E}[\sigma_i] = 0\)，\(\mathbb{E}[\sigma_i^2] = 1\)，并且当 \(i \neq j\) 时 \(\mathbb{E}[\sigma_i \sigma_j] = 0\)。常数项 \(w(c)\) 在方差中消掉，剩下
\[\operatorname{Var}_{\text{子单元}}(w) \;\approx\; \left(\tfrac{r}{2}\right)^{2} \sum_{i=1}^{n} \left(\frac{\partial w}{\partial x_i}\right)^{2} \;=\; \left(\tfrac{r}{2}\right)^{2} \lVert \nabla w(c) \rVert^{2}\]所以树、阈值和其余一切都可以保持不变，只改一行：
\[\text{切分条件：} \operatorname{Var}(2^n \text{ 个样本}) > \tau \quad\longrightarrow\quad \text{切分条件：} \left(\tfrac{r}{2}\right)^{2}\lVert \nabla w(c)\rVert^{2} > \tau\]数值上，这个近似表现很好。在随机 CPPN 上，梯度的估计在最大的单元上与采样方差相差 5% 到 15%，在小单元上则难以区分。
梯度之所以便宜，靠的是反向模式自动微分（也就是反向传播）。无论 \(n\) 多大，它都能在一次反向传播里得到全部 \(n\) 个偏导数，代价只是前向计算的一个小常数倍。链式法则从唯一的输出往回推，前向传播里的每个中间值只复用一次，所以一次测试只需一次前向和一次反向传播，而不是 \(2^n\) 次前向传播。
不过树本身没有变。一个被梯度判定为有变化的单元，仍然会切分成 \(2^n\) 个新单元，所以每次测试大约便宜了 \(2^n/2\) 倍，但全部 \((2^n)^m\) 个单元仍然都在。
2. 两种测试几乎总是一致
当场在一个单元内远非线性时，这个近似就失效了。一个恰好以单元为中心的鞍点，在测试所看的那一个点上梯度为零，于是梯度测试认为这个单元是平的，永远不切分它；下面的盲点按钮就会构造一个这样的例子。采样也有自己的盲点：一个以单元为中心的鼓包，会给出四个相同的样本。
对比会勾出两种测试判断不一致的单元。
这在实践中有多常见？我们为 2 到 7 维的随机 CPPN 重建了树，用两种测试给每个单元打分。在 2,580 个切分决定中，两者有 98.7% 一致。34 处分歧里，有 32 处是梯度切分了采样没切的单元，反过来的只有 2 处。
这种偏向与第 1 节相符：在大单元上，梯度的估计略微偏高，会把处在边界上的单元推过阈值。多切一次，只是多花一点算力；漏切一次会丢失细节，而这种情况很少。
3. 节省随维数增长，但更好的采样器会缩小差距
和原始发表的采样方法相比，梯度测试所需的 CPPN 计算次数在二维中少 2 倍，在七维中少 61 倍，搜索时间也遵循同样的曲线。
一棵深度为 2 的树，10 个随机 CPPN（4 个输入、4 个输出）的中位数。一次反向传播算作一次计算；角点缓存采样器只做了计数，没有实际运行。
| n | 采样 | 角点缓存 | 梯度 | 耗时：采样 | 耗时：梯度 |
|---|---|---|---|---|---|
| 2 | 416 | 144 | 208 | 1.1 ms | 0.75 ms |
| 3 | 3,136 | 784 | 784 | 3.9 ms | 1.2 ms |
| 4 | 24,704 | 4,096 | 3,344 | 27 ms | 2.9 ms |
| 5 | 24,832 | 4,540 | 2,576 | 27 ms | 2.4 ms |
| 6 | 786,944 | 67,112 | 27,152 | 873 ms | 24 ms |
| 7 | 6,358,016 | 275,476 | 103,440 | 8.8 s | 0.10 s |
不过这场比较并不完全公平。原始算法在子单元中心采样，这些样本从不复用。改为在单元角点采样并缓存的变体，可以让每个角点被所有与之相邻的单元复用。在同样的树上，这让采样在二维中便宜 3 倍，在七维中便宜 16 倍。
和这个版本相比，梯度测试在二维中其实更贵，在三维中持平，在七维中也只便宜 2.7 倍。两者都仍然陡峭上升，因为两者都还在构建 \(2^n\) 叉树。
4. 用更少的搜索，找到同样好的网络
最后，回到第 1 部分的转向任务，在三维基底和二维地图投影上都做一遍。两个版本除了切分测试之外，每一行代码都相同：同样的树、阈值、网络、任务、进化算法和设置。它们还共用随机种子，所以每次梯度运行都从与它的采样孪生运行相同的 CPPN 出发，得到相同的随机扰动。只有在两种测试第一次对某次切分意见不一时，两者才开始分道扬镳。
上：8 对配对运行的均值，±1 标准误。下：每个种子；圆点落在圆环内，说明两种测试表现一样好。
| 3D 采样 | 3D 梯度 | 2D 采样 | 2D 梯度 | |
|---|---|---|---|---|
| 平均最终得分（8 次运行） | 0.737 | 0.728 | 0.551 | 0.570 |
| 达到 0.68 的运行 | 8 / 8 | 7 / 8 | 4 / 8 | 4 / 8 |
| 每个基因组放置神经元的耗时 | 79 ms | 14 ms | 11.5 ms | 5.0 ms |
| 一次完整训练 | 5.9 分钟 | 1.7 分钟 | 1.2 分钟 | 0.7 分钟 |
计时来自 AMD Ryzen 7 7840HS，15 次运行并行。一个基因组就是一个候选 CPPN。
性能结果相同。在三维中，平均最终得分相差不到 0.01，略微偏向采样（差值的 95% 置信区间：−0.027 到 +0.002），两个版本在八对中各赢四对。这点差距大部分来自一次梯度运行，它在训练停止时仍在进步。
在二维中，梯度版本平均略微领先（95% 置信区间：−0.042 到 +0.089），但在八对中只赢了三对，打平一对，它的领先来自两次大胜。在两种测试下，二维中成功的运行都是同样的四个种子，所以一次运行的结果由它的初始 CPPN 和基底决定，而不是由切分测试决定。
每个版本的全部 8 次运行，每次追逐换一个。采样和梯度的面板总是显示同一个种子。
两者的差别在于时间。放置神经元的耗时在三维中大约只有六分之一，在二维中不到一半，所以一次完整的三维训练快了 3.5 倍。从二维到三维，采样的放置成本增加到 7 倍，梯度只增加到 3 倍，因为采样既要为更大的树买单，也要为每次测试翻倍的成本买单，而梯度只为更大的树买单。
5. 注意事项
这是一个从零写的简化版 ES-HyperNEAT，CPPN 形状固定，用进化策略而不是 NEAT 训练。两个版本共用这一切，所以比较是公平的，但在参考实现里，绝对数值会不一样。
这只是一个玩具任务，每个基底 8 对配对运行，能排除大差异，但排除不了小差异。第 1 部分讲了在任何东西能学起来之前需要做的修正。代码和原始结果在 /experiments/es-hyperneat/（英文），两个版本只在 eshn.py 里的 complexity() 函数上有区别。
6. 五维的生物是什么样子
把四叉树的 \(2^n\) 次采样换成一次梯度，几乎不改变切分决定，也就几乎不改变由此得到的网络，同时去掉了每次测试的指数级成本。树仍然是 \(2^n\) 路分叉，所以高维并不是免费的。但五维、六维、七维的基底，现在已经便宜到可以一试了，这就引出一个问题：五维的任务究竟长什么样？
在生命模拟里，这样的任务比你想象的多。一个能感知食物方向的细胞生活在三维中，但如果它还在乎自己朝向哪边，就又多了三个轴，一共六个。群体中一个对邻居位置和速度做出反应的成员，也生活在同样的六维里。一个会生长的生物，在三维身体之外又多了时间这一维；而一个细胞携带多种化学信号的元胞自动机，在网格之外，每种信号都多一个轴。
人工生命之外也是如此。无人机的控制取决于它的位置和姿态。机械臂的状态存在于由它六七个关节角构成的空间里。医学扫描是随时间变化的三维体积，天气也是。只要一个任务的输入和输出带有超过三维的自然几何结构，一个与之匹配的基底，就可能让正确的网络变得简单，就像三维基底对那个会游泳的细胞所做的那样。
弄清这一点，不再需要每多一维就多付出指数级的代价。我很想看看会发现什么。