AutoML-Zero: Evolving Machine Learning Algorithms From Scratch

基本信息

作者：Esteban Real, Chen Liang, David R. So, Quoc V. Le

DOI: 10.48550/arXiv.2003.03384

网址：http://arxiv.org/abs/2003.03384

日期：2020-06

被引用: 411（来自谷歌学术）

什么是AutoML

说白了就是让机器学习的各个环节实现彻底的自动化，包括数据清洗，模型选择，超参数调整架构设计等等。这样一方面可以降低使用门槛，另一方面有机会可以让机器自己学出一个新的架构。

毕竟机器学习成功的至关因素，就是架构的设计和一些超参数的调整，如果这本身人工智能去学习的话，是有潜力创造出更加厉害的如何设计的。

方法概述

这篇文章使用的方法简单来说，就是把机器学习里面所用到的所有的架构，全部简化成基础的运算，比如加减乘除。把这些基本的运算当作积木，模型训练过程中的前向传播与反向传播全部用这些积木搭建，不进行任何人为的干预。训练通过evolution strategy类似的方法去学习。

积木举例如下： - dot、outer、add/sub/mul/div - maximum（实现 ReLU）、heaviside（实现门控/近似梯度） - gaussian/uniform（随机初始化/加噪） - norm（梯度归一化）

这是一个很有趣的范式，但本质其实还是使用遗传算法或者Evolution strategy。

方法

关键思想：把 ML 算法写成三段程序

论文把一个“学习算法”编码成由三段函数组成的程序：

Setup：初始化全局状态（例如权重、学习率、随机噪声分布参数等）
Predict：读入特征$x$，产生预测$y'$
Learn：读入特征$x$与标签$y$，更新权重

评估一个架构的有效性时，先在一个任务的训练集上交替执行Predict和Learn，最后只用Predict在验证集上测出模型的准确率。

下面给出论文中的伪代码说明：

# (Setup, Predict, Learn) = input ML algorithm.
# Dtrain / Dvalid = training / validation set.
# sX/vX/mX: scalar/vector/matrix var at address X.
def Evaluate(Setup, Predict, Learn, Dtrain, Dvalid):
    # Zero-initialize all the variables (sX/vX/mX).
    initialize_memory()
    Setup()  # Execute setup instructions.
    for (x, y) in Dtrain:
        v0 = x  # x will now be accessible to Predict.
        Predict()  # Execute prediction instructions.
        # s1 will now be used as the prediction.
        s1 = Normalize(s1)  # Normalize the prediction.
        s0 = y  # y will now be accessible to Learn.
        Learn()  # Execute learning instructions.
    sum_loss = 0.0
    for (x, y) in Dvalid:
        v0 = x
        Predict()  # Only Predict(), not Learn().
        s1 = Normalize(s1)
        sum_loss += Loss(y, s1)
    mean_loss = sum_loss / len(Dvalid)
    # Use validation loss to evaluate the algorithm.
    return mean_loss

那么现在应该如何训练呢？

本论文中使用的方法是 regularized evolution（也叫 aging evolution）：维护一个大小为 $P$ 的种群，循环执行：

删除最老个体
随机抽样 $T$ 个个体做 tournament，选最优者为 parent
复制 parent
突变得到 child 并加入种群

论文设计了三种突变类型：

(i) 插入/删除一条随机指令（在某个组件函数的随机位置）
(ii) 随机化某个组件函数：把该组件的全部指令都随机化
(iii) 修改一条指令的一个参数：例如换输出地址、换常量等

补充材料进一步给了实现细节：

控制程序膨胀：“instruction removal is twice as likely as addition”（删除指令的概率是添加的两倍）
类别型随机选择均匀分布
常量扰动：修改实数常量时，将其乘以 $[0.5,2.0]$ 的均匀随机数，并以 10% 概率翻转符号

稍微思考后，我们会发现的这个方法的本质是使用evolution strategy这样的方式去学习的，这样学习带来的一个后果是需要在极大的模型空间里面去寻找很少的可行的模型。这样带来的计算成本是很高的，也就是说我们每设计一个架构，都需要一定的成本去看看这个价格合不合适。如果没有任何东西去指导我们该选择哪个架构的话，这样的代价是无法接受的，所以文章中提出了很多改进的方法。

由于搜索空间“很松”，很多突变可能不影响行为（例如写到一个从未被读取的地址）。为了避免反复训练/验证同一行为的程序，论文引入 FEC：

对每个算法：跑 10 步训练 + 10 个验证样本，记录预测序列
将这些预测截断后 hash 成“指纹”
用一个 LRU cache 维护 100k 个 “fingerprint → accuracy” 映射

这样能显著提高吞吐（主文提到约 4x speedup）。

为进一步提高吞吐，论文采用 hurdles（类似动态门槛的 early stopping）：

若训练过程中没达到最低精度门槛（hurdle），就提前停止该算法评估
作者把 hurdle 设为滚动的、种群“唯一精度的 75 分位”（而不是固定常数），从而稳定节省资源
论文声称这样能稳定节省 75% compute

为了避免无意义程序拖垮系统，还会：

产生 NaN/Inf 则立刻终止并给最小精度 $a_{\min}$（文中用 $a_{\min}=0$）
若训练误差超过阈值 $e_{\max}$（文中用 $e_{\max}=100$），也终止并记最差
若运行时间超过阈值（设置为“普通反传训练的小网络”的 4 倍），也终止

搜索以多进程并行方式运行，进程之间通过 migration 交换模型。

50% worker 在 CIFAR-10 的二分类任务上搜，50% 在 MNIST 上搜，以提升多样性并改善最终 CIFAR-10 表现。

度量难度

作者把“难度”定义成：在随机搜索（RS）中，能找到“可接受算法”的稀疏程度。

先用 RS 跑
统计“优于某个手工参考算法”的候选比例（success rate）
其倒数可看作“找到一个可接受算法平均要试多少个”——即“空间密度/任务难度”的估计

论文给了一个很直观的数字：在线性回归这种“很简单”的任务上，也只有大约每 $10^7$ 个随机算法里才有 1 个可接受算法，于是把线性回归任务难度定义为 $10^7$。在这种稀疏空间里，进化搜索相对随机搜索优势会随难度显著扩大；并且即便在线性回归上，进化也能做到约 5 倍效率提升。

结果

两层网络 + 反向传播

论文展示了一个里程碑：即使 op 集合里没有“梯度/反传”的概念，进化仍能拼出类似两层网络与梯度下降的完整过程。

从主文给出的代码片段看，它包含典型结构：

Setup：初始化一层权重矩阵 m1、学习率 s3、二层权重向量 v4
Predict：
$v6 = m1 \cdot v0$
$v7 = \max(0, v6)$（ReLU）
$s1 = v7 \cdot v4$
Learn：
误差：$s1 \leftarrow s0 - s1$
用 heaviside(v6) 充当 ReLU 的门（近似梯度）
用 outer 构造一层权重的更新量

这说明 AutoML-Zero 的表达能力足以覆盖“反传训练的简单网络”，但它并不是硬编码出来的，而是从基本操作组合中被搜索到的。

最强算法超越手工基线

前面用 teacher 网络/限制 ops 的实验会偏向已知算法，所以这里改用更通用设定。

实验细节（主文“Experiment Details”段落）：

任务来源：CIFAR-10 与 MNIST 的训练集
二分类任务构造：10 类两两配对共有 45 对
36 对作为 $T_{\text{search}}$（搜索任务）
9 对作为 $T_{\text{select}}$（选择/模型选择任务）
每个任务：8000 train / 2000 valid
特征做随机投影：$8 \le F \le 256$
每次评估在 $1 \le D \le 10$ 个任务上取中位数
并行规模：$W=10k$
从此开始使用 3.2 节完整设置（允许可变长度的组件函数）
ops 规模（文中给了一个统计）：Setup/Predict/Learn 的可用 ops 数大约为 7/58/58

在这样的设置下，作者报告：

每次搜索实验产生一个候选算法（在 $T_{\text{search}}$ 上进化得到）
用 $T_{\text{select}}$ 做选择，并与手工参考（两层全连接 + 梯度下降）对比
在 20 次实验中有 13 次候选算法优于参考网络

随后，作者挑出最佳算法，在原始 CIFAR-10 特征维度（3072）上做最终评估与调参（把程序里的常量当作超参，用随机搜索联调），并在 CIFAR-10 测试集上得到：

最佳进化算法：$84.06 \pm 0.10\%$
线性基线（logistic regression）：$77.65 \pm 0.22\%$
非线性基线（2-layer FC NN）：$82.22 \pm 0.17\%$

并且迁移到其它数据集的二分类任务也有优势（论文给出对比三元组：进化/线性/非线性）：

SVHN：88.12% vs 59.58% vs 85.14%
Downsampled ImageNet：80.78% vs 76.44% vs 78.44%
Fashion MNIST：98.60% vs 97.90% vs 98.21%

进化出来的“现代技巧”：噪声、双线性交互、梯度归一化、权重累积

作者对的最佳算法做了“清理与解释”（删冗余、重排不影响性能的指令），并通过消融验证了一些显著结构：

输入加噪声（正则化）：

$$ a = x + u,\quad b = x - u,\quad u \sim U(\alpha,\beta) $$

双线性交互（bilinear / multiplicative interactions）：

$$ o = a^\top W b $$

梯度归一化（normalized gradients）：

令 $\delta = y^* - y$，并构造

$$ g = \delta\, a b^\top,\qquad g_w = \frac{g}{\lVert g\rVert} $$

（论文用这种形式说明它“正确计算了梯度并归一化”，并指出这类归一化在非凸优化里是常见启发式。）

权重累积用于推理（类似 averaged perceptron / weight averaging 的影子）：

$$ W_0 = \sum_t W_t $$

并且训练/验证阶段用不同权重：在 Predict 末尾将当前权重设为 $W_0$，而在 Learn 开头再切回 $W_t$。由于验证时不会调用 Learn，因此验证阶段会一直用 $W_0$。

算法会“适应任务类型”吗？

论文在 4.3 节展示：当搜索任务的性质改变时，进化会系统性地产生不同“技巧”。

样本很少（80 train、100 epochs）：更容易出现类似 Dropout/Noisy ReLU 的噪声注入；作者做了 30 次重复实验，对照组（800 train、100 epochs）几乎不出现；报告显著性：expt 8/30，control 0/30，$p<0.0005$。
需要快速训练（800 train、10 epochs）：反复出现学习率衰减；作者举例为“迭代 arctan 映射”，并且在更长训练（100 epochs）的对照下出现频率明显更低（expt 30/30，control 3/30，$p<10^{-14}$）。
多分类（10 类）：算法倾向于把权重矩阵的均值做变换（如 abs/sin 等）后当学习率；报告 expt 24/30，control 0/30，$p<10^{-11}$。

这些结果支持了一个观点：AutoML-Zero 不只是“找到一个固定模板”，它能在同一表示体系里，根据任务压力演化出不同的归纳偏置与训练策略。

讨论

局限与作者给出的未来方向

论文很坦诚地给出了一些关键瓶颈：

搜索空间仍有隐含偏置：例如当前按样本逐个处理，没有 batch 维度，也没有循环/高阶张量，因此像 batch-norm 这类依赖批统计的机制很难出现。
更深结构很难“复用”：多层网络需要“每一层都被独立发现”，如果引入循环/函数调用，可能更容易发现更深结构。
解释与复现成本高：原始代码复杂，需要静态分析删除冗余，再用“收敛进化（convergent evolution）”线索挑 motif，并用 knock-out/knock-in 做消融验证。
超参耦合（hyperparameter coupling）：有时一个表达式刚好给出某个好常量，但它不是“真正的超参语义”。作者提到需要手动解耦（未来可自动化）。

本人思考

这篇论文把“基本偏置” + “从头学习”这条轴推到极端，展示了从底层训练神经网络的可行性。说明了一些现代技巧可以在更底层的原语上重现。
复现/扩展：
引入 batch 维度、更丰富的张量运算、循环/函数调用
更强搜索：更先进的进化算子、基于程序语义的突变、或与 RL/BO 混合
更系统的可解释性工具：自动识别“语义等价子程序”、自动做 motif 抽取与验证