在线最优化求解(Online Optimization)之二:截断梯度法(TG)
在预备篇中我们做了一些热身,并且介绍了L1正则化在Online模式下也不能产生较好的稀疏性,而稀疏性对于高维特征向量以及大数据集又特别的重要。因此,从现在开始,我们沿着提升模型稀疏性的主线进行算法介绍。
为了得到稀疏的特征权重 ,最简单粗暴的方式就是设定一个阈值,当的某维度上系数小于这个阈值时将其设置为称作简单截断)。这种方法实现起来很简单,也容易理解。但实际中(尤其在OGD里面)的某个系数比较小可能是因为该维度训练不足引起的,简单进行截断会造成这部分特征的丢失。
截断梯度法(TG, Truncated Gradient)是由John Langford,Lihong Li和Tong Zhang在2009年提出[1],实际上是对简单截断的一种改进。下面首先描述一下L1正则化和简单截断的方法,然后我们再来看TG对简单截断的改进以及这三种方法在特定条件下的转化。
1. L1正则化法
由于L1正则项在0处不可导,往往会造成平滑的凸优化问题变成非平滑凸优化问题,因此在每次迭代中采用次梯度[2](Subgradient)计算L1正则项的梯度。权重更新方式为:
公式(1)
注意,这里是一个标量,且,为L1正则化参数;为符号函数,如果是一个向量,是向量的一个维度,那么有;为学习率,通常将其设置成的函数;代表了第t次迭代中损失函数的梯度,,由于OGD每次仅根据观测到的一个样本进行权重更新,因此也不再使用区分样本的下标j。
2. 简单截断法
以k为窗口,当t/k不为整数时采用标准的SGD进行迭代,当t/k为整数时,采用如下权重更新方式:
公式(2)
注意,这里面是一个正数;如果是一个向量,是向量的一个维度,那么有。
3. 截断梯度法(TG)
上述的简单截断法被TG的作者形容为too aggressive,因此TG在此基础上进行了改进,同样是采用截断的方式,但是比较不那么粗暴。采用相同的方式表示为:
公式(3)
其中。TG同样是以k为窗口,每k步进行一次截断。当t/k不为整数时,当t/k为整数时。从公式(3)可以看出,和决定了的稀疏程度,这两个值越大,则稀疏性越强。尤其令时,只需要通过调节一个参数就能控制稀疏性。
根据公式(3),我们很容易写出TG的算法逻辑:
4. TG与简单截断以及L1正则化的关系
简单截断和截断梯度的区别在于采用了不同的截断公式和,如图1所示。
图1 截断公式T0&T1的曲线
为了清晰地进行比较,我们将公式(3)进行改写,描述特征权重每个维度的更新方式:
公式(4)
如果令截断公式变成:
此时TG退化成简单截断法。
如果令截断公式变成:
如果再令k=1,那么特征权重维度更新公式变成:
此时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