I. 背景介绍
1. 学习曲线(Learning Curve)
我们都知道在手工调试模型的参数的时候，我们并不会每次都等到模型迭代完后再修改超参数，而是待模型训练了一定的epoch次数后，通过观察学习曲线(learning curve, lc) 来判断是否有必要继续训练下去。那什么是学习曲线呢？主要分为两类：
- 1.模型性能是训练时间或者迭代次数的函数：performance=f(time) 或 performance=f(epoch)。这个也就是我们常用到的方法，即横轴记录训练时间(或迭代次数)，纵轴记录准确率。示意图如下：
- 2.模型性能是用于训练模型的数据集大小的函数：performance=f(train_data_size),即横轴记录训练集大小，纵轴记录准确率。
本文使用的是第一种。
2. 饱和函数(Saturating Function)
饱和函数简单理解就是当输入达到一定值后，输出不再有明显变化，或变化很小，所以称之为饱和。
常见的饱和函数有：
- 指数函数
- sigmoid函数
仔细观察可以看到其实理想的学习曲线就是饱和函数。而我们手工判断一个网络是否还有必要继续训练下去的依据，就是看是否已经到了那个临界点，或者我们称之为饱和点。
基于此，本文选取了如图所示的11种饱和函数用来拟合学习曲线。
怎么个拟合法呢？这里做个简单的介绍，下文会更加详细介绍。
就是说假如我们通过训练模型和评估模型得到了n个学习曲线值(或者说是准确率)，即为
。
然后我们通过使用上面的饱和函数对这些数据进行拟合计算出饱和函数的参数，这样我们就可以预测后面的模型性能了。这样也就可以做到断舍离了。
3. 超参数优化(Hyperparameters Optimization)
假设经过上面的步骤得到了饱和函数的参数，但是我们还是需要对超参数进行采样和优化的。
而常用的超参数优化算法有很多种，其中贝叶斯优化算法是使用最多且较为有效的方法。而基于贝叶斯的优化算法中使用广泛的有如下三种：
- Spearmint
- SMAC
- Tree Parzen Estimator(TPE)
有文章对上面三种方法做了比较，得出如下结论：
- Spearmint在数值型超参数较少的情况下表现更加好
- SMAC和TPE在高维超参数和部分离散超参数情况下表现更好
本文使用了后两者优化算法。
4. 无信息先验(Uninformative prior)
由名字就可以很好理解无信息先验是什么意思了，就是说事先我们不知道任何其他信息，所以对于某一事件的先验概率无从得知。这种情况下通常是假设先验概率是均匀分布，因为这样不会对任何事件或元素有偏心。
II. 本文方法
1. Learning Curve Model
假设有K个饱和函数可供选择，记为
,每个饱和函数
都由一组超参数
决定。
部分观察已知的学习曲线上的值记为
,每个值
[y_t=f_k(t|θ) epsilon tag{1} ]
其中
表示高斯分布的噪声，即
.
所以单个观测值
的概率分布是:
[p(y_t|θ_k,sigma^2)=cal{N}(y_t;f_k(t|θ_k),sigma^2) tag{2} ]
2. A weighted Probabilistic Learning Curve Model
上面的y值只由一个饱和函数决定，那为什么不能将这些饱和函数都利用起来呢？所以我们可以给每个饱和函数一个权重，因此可以得到如下合并(combined)饱和函数:
[f_{comb}(t|xi) =sum_{k=1}^Kw_kf_k(t|θ_k) tag{3} ]
[xi = (w_1,...,w_K,θ_1,...θ_K,sigma^2) tag{4} ]
所以此时有
[y_t=f_{comb}(t|xi) epsilon=sum_{k=1}^Kw_kf_k(t|θ_k) epsilon tag{5} ]
[p(y_{1:n}|xi)=prod_{t=1}^ncal{N}(y_t;f_{comb}(t|xi),sigma^2) tag{6} ]
现在有了如公式(5)的模型了，所以一个很简单的办法就是根据
找到该模型的最大似然参数估计，然后将参数带入模型中，这样我们就可以借助这个具体的模型预测后面的模型性能了，从而可以自动决定是否还有必要继续训练下去。但是这样有个缺点，按照原文的说法是：
However, this would not properly model the uncertainty in the model parameters. Since our predictive termination criterion aims at only terminating runs that are highly unlikely to improve on the best run observed so far we need to model uncertainty as truthfully as possible and will hence adopt a Bayesian perspective, predicting values ym using Markov Chain Monte Carlo (MCMC) inference
公式(4)中的参数的先验概率都是无信息先验，另外又因为要确保公式(3)最终还是一个饱和函数，所以规定每个权重都必须为正，参数
的概率分布定义如下：
[p(xi)∝(prod_{k=1}^Kp(w_k)p(θ_k))p(sigma^2)cal{I}(f_{comb}(1|xi)<f_{comb}(m|xi)) tag{7} ]
其中：
是一个indicator function,表示合并饱和函数必须是一个增函数。
- 另外权重
的概率分布为:
[p(w_k)∝ begin{cases} 1 & if ,,, w_k >0 \ 0 & otherwise end{cases} tag{8} ]
初始化时令
现在有了公式(6)(7)之后，我们就可以得到后验概率:
[p(xi|y_{1:n})∝p(y_{1:n}|xi)p(xi) tag{9} ]
借助这个后验概率我们就可以对联合超参数和权重搜索空间
进行MCMC(Markov Chain Monte Carlo) 采样了。那具体怎么个采样法呢？
- 令所有的模型参数
设置为其对应饱和函数的最大似然估计。
- 模型权重均匀分布，即
- 噪声参数初始化为它的最大似然估计，即
3. Extrapolate Learning Curve
上面已经将采样的方式介绍清楚了，那么接下来介绍判断是否继续训练模型的细节。
1) 预测模型性能
2) 模型性能大于阈值的概率分布
因为对于每一个固定的参数
而言，预测分布
都是一个高斯分布，所以有：
[begin{align} p(y_m>hat{y}|y_{1:n}) &= int p(xi|y_{1:n})p(y_m>hat{y}|xi)dxi notag \ &≈frac{1}{S}sum_{s=1}^Sp(y_m>hat{y}|xi_s) notag \ &= frac{1}{S}sum_{s=1}^S(1-Phi(hat{y};f_{comb}(m|xi_s),sigma_s^2)) tag{11} end{align} ]
其中
是均值为μ，方差为
的高斯累计分布函数。
3) 算法细节
- 预设的最大迭代次数为
。
- 在每个epoch中会记录K次模型在验证集上的性能，即
- 每隔P个epoch，就将之前记录的模型性能汇总起来得到n(
)个性能数据，即
。然后根据这些数据预测最后step的性能，即预测第
步的性能
。这里需要用到公式(10)求出预测性能
大于预设性能
的概率，如果概率大于阈值
，那么继续下一P个epoch的训练。反之则返回预测验证集准确率
(由公式（10)求得)。
文中将这一过程称为： predictive termination criterion。
