Self-Paced Learning for Latent Variable Models_NIPS10

这一篇是Self-Paced Learning(SPL)的奠基之作。
SPL,固名思义,就是一步步,有自主步伐节奏得学。Motivation应该来自于09年Bengio提出的Curriculum Learning(CL)。CL受到认知科学的启发——人在学东西的时候也没办法一下子接受特别困难的知识,是从简单的开始学起。所以CL是根据某种先验,将按照困难度排好序的样本逐渐喂给模型。SPL与CL最大的不同之处在于这个排样本的先验是嵌入到模型里面的,是动态的,可以优化学习的。
这样子从易到难得学可以看成是一种正则化的手段,有助于加快收敛,并达到一个更好的local minimum.

考虑一个普通的机器学习优化问题
\begin{equation}
w_{t+1}=argmin_{w\in R^d}\left(r(w)+\sum_{i=1}^nf(x_i, y_i; w)\right)
\end{equation}
$r(.)$是一个正则化项,$f(.)$就是loss项了,比如负对数似然函数。SPL需要考虑样本的难易程度,以及一次要用多少样本。所以这篇文章引入了一个binary variable $v_i$,表示这个样本是否是简单的样本,只有简单的样本才在目标函数中有贡献。这样子新的目标函数是一个混合整数规划【mixed-integer program】问题:
\begin{equation}
(w_{t+1}, v_{t+1})=argmin_{w\in R^d, v\in {0,1}^n}\left(r(w)+\sum_{i=1}^nv_if(x_i, y_i; w) - \frac{1}{K}\sum_{i=1}{n}v_i\right)
\end{equation}
$K$是用来调整要选多少简单的样本:当$K$比较大时,为了使目标函数更小,那么就只有$f(.)$比较小【high likelihood,因为是负的】的样本会被选中。
更重要的是,每个样本是否是简单的其实不是单独考虑的——它们之间通过参数$w$联系起来,也即,一组样本是简单的条件是有$w$能够拟合这组样本,得到一个值比较小的$f(.)$。
在训练过程中,我们逐渐减小$K$的值,使得越来越多的样本能够被考虑进来。当$K$趋近于0时,优化(2)其实就相当于在优化(1)。
然而(2)这样的混合整数规划问题通常不好求解,所以我们松弛对参数$v$的约束:允许$v_i$的值落在[0, 1]之间。这个松弛是紧的【tight】,也就是说,取得最优值的$w$,对应的每个$v_i$一定是0或1。这很好理解:如果$f(x_i,y_i;w)\lt 1/K$,那么肯定$v_i=1$能取得最小值;如果$f(x_i,y_i;w)\gt 1/K$,那么肯定$v_i=0$能取得最小值。
经过这样的松弛之后,问题就比较好解了。特殊情况下,如果$r(.)$和$f(.)$都是凸的,那么这个目标函数就是个biconvex的目标函数,可以采用诸如坐标下降的方法求解。作者用的是alternative convex search(ACS)。一般情况下,如果$r(.)$和$f(.)$都是非凸的,也可以用类似的方法求解:给定$w$,最优的$v$值为$v_i=\delta(f(x_i, y_i; w)\lt 1/K$,其中$\delta(.)$为指示函数【indicator function】;给定$v$,优化(2)就跟优化(1)一样。
作者在实验中$w$的初值是设置所有$v_i=1$,然后用CCCP算法跑一段时间。

最后用孟德宇老师的一页ppt总结一下SPL:
SPL