在线最优化求解(Online Optimization)之二：截断梯度法(TG)

转自http://www.wbrecom.com/?p=342

在预备篇中我们做了一些热身，并且介绍了L1正则化在Online模式下也不能产生较好的稀疏性，而稀疏性对于高维特征向量以及大数据集又特别的重要。因此，从现在开始，我们沿着提升模型稀疏性的主线进行算法介绍。

为了得到稀疏的特征权重，最简单粗暴的方式就是设定一个阈值，当 $W$ 的某维度上系数小于这个阈值时将其设置为 $0$ 称作简单截断）。这种方法实现起来很简单，也容易理解。但实际中（尤其在OGD里面） $W$ 的某个系数比较小可能是因为该维度训练不足引起的，简单进行截断会造成这部分特征的丢失。

截断梯度法（TG, Truncated Gradient）是由John Langford，Lihong Li和Tong Zhang在2009年提出^[1]，实际上是对简单截断的一种改进。下面首先描述一下L1正则化和简单截断的方法，然后我们再来看TG对简单截断的改进以及这三种方法在特定条件下的转化。

1. L1正则化法

由于L1正则项在0处不可导，往往会造成平滑的凸优化问题变成非平滑凸优化问题，因此在每次迭代中采用次梯度[2](Subgradient)计算L1正则项的梯度。权重更新方式为：

$W^{(t+1)}=W^{(t)}-eta ^{(t)}G^{(t)}-eta ^{(t)}lambda sgn(W^{(t)})$ 公式（1）

注意，这里 $lambdainmathbb{R}$ 是一个标量，且 $lambdageq0$ ，为L1正则化参数； $sgn(v)$ 为符号函数，如果 $V=[v_1,v_2...v_N]in mathbb{R}^N$ 是一个向量， $v_i$ 是向量的一个维度，那么有 $sgn(V)=[sgn(v_1),sgn(v_2)...sgn(v_N)]in mathbb{R}^N$ ; $eta ^{(t)}$ 为学习率，通常将其设置成 $frac{1}{sqrt{t}}$ 的函数； $G^{(t)}= riangledown _Wl(W^{(t)},Z^{(t)})$ 代表了第t次迭代中损失函数的梯度,，由于OGD每次仅根据观测到的一个样本进行权重更新，因此也不再使用区分样本的下标j。

2. 简单截断法

以k为窗口，当t/k不为整数时采用标准的SGD进行迭代，当t/k为整数时，采用如下权重更新方式：

$W^{(t+1)}=T_0(W{(t)}-eta ^{(t)}G^{(t)}, heta )$ 公式(2) $T_0(v_i, heta )=left{egin{matrix} 0 & if left | v_i ight |leqslant 0\ v_i & otherwise end{matrix} ight.$

注意，这里面 $heta in mathbb{R}^+$ 是一个正数；如果 $V=[v_1,v_2...v_N]in mathbb{R}^N$ 是一个向量， $v_i$ 是向量的一个维度，那么有 $T_0(V, heta )=[T_0(v_1, heta),T_0(v_2, heta)...T_0(v_N, heta)]in mathbb{R}^N$ 。

3. 截断梯度法(TG)

上述的简单截断法被TG的作者形容为too aggressive，因此TG在此基础上进行了改进，同样是采用截断的方式，但是比较不那么粗暴。采用相同的方式表示为：

$W^{(t+1)}=T_1(W^{(t)}-eta ^{(t)}G^{(t)},eta ^{(t)}lambda ^{(t)}, heta )$ 公式(3) $T_1(V,alpha , heta )=left{egin{matrix} max(0,v_i-alpha ) & if\ v_iin [0, heta ]\ min(0,v_i-alpha ) & if\ v_iin [- heta, 0]\ v_i & otherwise end{matrix} ight.$

其中 $lambda^{(t)} in mathbb{R}^+$ 。TG同样是以k为窗口，每k步进行一次截断。当t/k不为整数时 $lambda^{(t)}=0$ ，当t/k为整数时 $lambda^{(t)}=klambda$ 。从公式(3)可以看出， $lambda$ 和 $heta$ 决定了 $W$ 的稀疏程度，这两个值越大，则稀疏性越强。尤其令 $lambda = heta$ 时，只需要通过调节一个参数就能控制稀疏性。

根据公式(3)，我们很容易写出TG的算法逻辑：

4. TG与简单截断以及L1正则化的关系

简单截断和截断梯度的区别在于采用了不同的截断公式 $T_0$ 和 $T_1$ ，如图1所示。

图1 截断公式T0&T1的曲线

为了清晰地进行比较，我们将公式(3)进行改写，描述特征权重每个维度的更新方式：

$w_i^{(t+1)}=left{egin{matrix} Trnc((w_i^{(t)}-eta {(t)}g_i^{(t)}),lambda _{TG}^{(t)}, heta ) & if\ mod(t,k)=0\ w_i^{(t)}-eta {(t)}g_i^{(t)} & otherwise end{matrix} ight.$ 公式(4) $Trnc(w,lambda _{TG}^{(t)}, heta )=left{egin{matrix} 0 & if\ left | w ight |leqslant lambda _{TG}^{(t)}\ w- lambda _{TG}^{(t)}sgn(w)& if\ lambda _{TG}^{(t)} leqslant left | w ight | leqslant heta \ w & otherwise end{matrix} ight.$ $lambda _{TG}^{(t)}=eta ^{(t)}lambda k$

如果令 $lambda _{TG}^{(t)}= heta$ 截断公式变成：

$Trnc(w, heta , heta )=left{egin{matrix} 0 & if\ left | w ight |leqslant heta \ w & otherwise end{matrix} ight.$

此时TG退化成简单截断法。

如果令 $lambda _{TG}^{(t)}=infty$ 截断公式变成：

$Trnc(w,lambda _{TG}^{(t)},infty)=left{egin{matrix} 0 & if\ left | w ight |leq lambda _{TG}^{(t)}\ w & otherwise end{matrix} ight.$

如果再令k=1，那么特征权重维度更新公式变成：

$w_i^{(T=1)}=Trnc((w_i^{(t)}-eta ^{(t)}g_i^{(t)}),eta ^{(t)}lambda ,infty)$ $=w_i^{(t)}-eta ^{(t)}h_i^{(t)}-eta ^{(t)}lambda sgn(w_i^{(t)})$

此时TG退化成L1正则化法。

参考文献

[1] John Langford, Lihong Li & Tong Zhang. Sparse Online Learning via Truncated Gradient. Journal of Machine Learning Research, 2009

[2] Subgradient. http://sv.wikipedia.org/wiki/Subgradient