漫谈在线学习:阴阳论

作者:李沐

Primal-dual的观点

《红楼梦》第三一回云:天地间都赋阴阳二气所生。世间有阴便有阳,在优化界也是如此。我们将需要最小化的目标函数称之为primal problem. 其对应就有dual problem. 例如常见的Lagrange Duality. 如果primal是凸的,那么dual便是凹的。且在常见情况下,最小化primal等价于最大化dual. 有时候直接求解primal problem很麻烦,但dual却方便很多。或是通过考察dual problem的性质能得到最优解的一些性质。一个经典的案例就是SVM.

上节我们通过子空间投影\Pi_{\mathcal{H}} 来处理罚,这里我们直接考虑最小化损失+罚的形式,既\min_w f(w) + \sum_{t=1}^T\ell_t(w) (罚前的参数\lambda 在这里写进了f(w) 里了)。注意到罚f(w) 的存在,使得目标函数不能如前面那样自然的分成T 块,从而不能直接对每块做梯度下降得到online gradient descent. 于是我们转向dual problem.

Shai Shalev-Shwartz提出可以用Fenchel Duality来研究其对偶式。Shai最近在online/stochastic界相当活跃。虽然和他不熟,不过因为他姓比较长,所以下面亲切的用Shai来称呼他。Shai 毕业于耶路撒冷希伯来大学,PHD论文便是online learning. 然后他去了online learning重地TTIC, 更是习得满身武艺,现在又回了耶路撒冷希伯来大学任教。他的数学直觉敏锐,善于将一些工具巧妙的应用到一些问题上。

两个概念

对一个凸函数,如下图所示,我们可以用两种不同的描述方式。一种就是函数上的所有点,函数曲线变由这些点构成;另外一种是每一个点所对应的切线,此时函数由所有切线形成的区域的上边缘确定。

函数上每一个点可由(w,f(w)) 表示,每一条切线可由斜率\theta 及与y轴交点,记为-f^\star(\theta) ,来确定。前一种表示是函数的primal form, 而后者则被称之为Fenchel conjudate, 是一种dual form, 其定义为

\displaystyle f^\star(\theta) = \max_w \langle w, \theta \rangle - f(w).

既然我们称它们为primal-dual, 当然意味着可以相互转换。实际上,对于一个闭凸函数,有f^{\star\star}=f .

另外一个概念是关于函数凸的程度的。一个函数被称为\sigma -强凸(strongly convex),那意味着对任意的w u , 有

\displaystyle f(w)-f(u)-\langle \nabla f(u), w-u\rangle\ge \frac{\sigma^2}{2}\|u-w\|^2.

示意图如下。直观上来说就是这个凸函数要凸得足够弯。这个定义可以拓展到一般的范数和次导数上来处理诸如稀疏罚\|\cdot\|_1 之类,此乃后话了。

Regret Bound分析

使用这两个概念可以得到一个重要定理。假设f \sigma -强凸的,且f^\star(0)=0 . 对任意的向量序列v_1,\ldots,v_T , 记w_t=\nabla f^\star\big(\sum_{j<t}v_j\big) 。那么对任意的向量u , 有

\displaystyle \sum_t \langle u, v_t \rangle - f(u) \le f^\star \big(\sum_t v_t\big) \le \sum_t \big( \langle w_t, v_t\rangle + \frac{1}{2\sigma}\|v_t\|^2\big).

此定理可以为Boosting, learning theory里的Rademecher Bound提供简单的证明,不过我们先关注它在online上的应用。不等式两边左右移项得\sum_t \langle u - w_t, v_t\rangle \le f(u) + \frac{1}{2\sigma} \sum_t \|v_t\|^2 . 注意到w_t 只和比t v_j 相关,所以我们可以取v_t=-\nabla \ell_t(w_t) ,立即由f 是凸函数有f(w_t)-f(u)\le \langle u - w_t, v_t \rangle . 同前记w^* 是离线最优解,且假设\|\nabla \ell_t(w_t)\|\le L , 联立上面两不等式有,R(T)\le f(w^*) + \frac{TL^2}{2\sigma} .

如果我们用\ell_2 罚,那么f=\lambda \|\cdot\|^2 , 且\sigma=2\lambda . 如果\lambda=\frac{L\sqrt{T}}{2\|w^*\|} ,则有R(T)\le LD\sqrt{T} , 这里D=2\|w^*\| 是对子空间\mathcal{H} 直径的一个估计。与上节Online Gradient Descent的regret bound比较,他们一样!

一般化的online算法

不小心先把理论讲完了,下面来解释下算法。接回一开始我们谈到的要考虑dual problem. 先观察到primal problem可以写成

\displaystyle \min_{w_0,\ldots,w_T}\left( f(w_0) + \sum_{t} \ell_t(w_t) \right)\quad \textrm{s.t.}\quad \forall t,\ w_t=w_0.

引入T 拉格朗日乘子u_t , 那么拉格朗日形式就是

\displaystyle \mathcal{L}(w_0,\ldots,u_1,\ldots) = f(w_0) + \sum_t\ell_t(w_t) + \sum_t\langle u_t,w_0-w_t\rangle.

这样dual problem就是最大化函数\min_{w_t} \mathcal{L}(w_0,\ldots,u_1,\ldots) ,记为\mathcal{D}(\cdot) . 套进Fenchel conjugate的定义,就有

\displaystyle \mathcal{D}(u_1,\ldots,u_T)=-f^\star\big(-\textstyle \sum_t u_t\big)-\displaystyle \sum_t \ell^\star_t(u_t).

注意到与primal problem不同,这时罚里面的变量也被拆成了T 份,所以在t 时刻我们可以假设比t 大的u_j 都是0, 从而只更新u_t 来增大\mathcal{D} .

总结下算法。在t 时刻,我们先计算w_t = \nabla f^\star\big(-\sum_{i<t} u_i\big) ,在收到数据的label后,选择u_t 来保证足够大的增加dual:

\displaystyle \mathcal{D}(u_1,\ldots,u_{t-1},u_t,0,\ldots) \ge \mathcal{D}(u_1,\ldots,u_{t-1},\nabla \ell_t(w_t), 0, \ldots).

下面是一个示意图。在每个时间里我们根据新来的数据不断的增大dual, 同时使得primal变小。

一个值得讨论的是,在这里我们可以控制算法的aggressive的程度。例如,如果我们每次只取u_t=\ell_t(w_t) ,就是意味着维持最小但使得理论分析成立的步伐长度。我们也可以使用更加激进的步伐,u_t = \arg\max_u\mathcal{D}(\ldots,u_{t-1},u,0,\ldots) ,来最大限度的增加dual以期望收敛更快。不过这样通常使得每一步的计算开销更大。所以是仁者见仁智者见智了。

这个算法框架可以解释一系列算法,例如前面提到的Halving, 它使用激进步伐,或是WM, 使用平缓的步伐,以及Adaboost. 当然,我们可以从这个算法框架里推出新的有no-regret保证的新的online算法。

到这里,我们介绍的三个算法(前面是Online Gradient Descent, Weighted Majority)的regret bound都是\mathcal{O}(\sqrt{T}) 。事实上,对于强凸的目标函数,目前已知最优的regret bound是\mathcal{O}(\log T) 。记得在OGD中我们使用固定的\mathcal{O}(1/\sqrt{T}) 的学习率,如果我们将其改成变长的\mathcal{O}(1/t) ,那么变可以达到这个最优上界。对于这节介绍的方法,我们可以通常将罚f(w) 里面的\lambda 分成T 份给每个loss \ell_t , 这样前t 个loss的和就是t\lambda/T -强凸,从而达到使用变长学习率的效果。具体可见Shai的NIPS ’08.

本文转自:https://mli7.wordpress.com/2011/04/10/online_learning_3/

转载请注明:《 漫谈在线学习:阴阳论 | 我爱计算机