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

时间:2021-02-06 19:50:27

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

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

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

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

1. L1正则化法

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

在线最优化求解(Online Optimization)之二:截断梯度法(TG)  公式(1)

注意,这里在线最优化求解(Online Optimization)之二:截断梯度法(TG)是一个标量,且在线最优化求解(Online Optimization)之二:截断梯度法(TG),为L1正则化参数;在线最优化求解(Online Optimization)之二:截断梯度法(TG)为符号函数,如果在线最优化求解(Online Optimization)之二:截断梯度法(TG)是一个向量,在线最优化求解(Online Optimization)之二:截断梯度法(TG)是向量的一个维度,那么有在线最优化求解(Online Optimization)之二:截断梯度法(TG);在线最优化求解(Online Optimization)之二:截断梯度法(TG)为学习率,通常将其设置成在线最优化求解(Online Optimization)之二:截断梯度法(TG)的函数;在线最优化求解(Online Optimization)之二:截断梯度法(TG)代表了第t次迭代中损失函数的梯度,,由于OGD每次仅根据观测到的一个样本进行权重更新,因此也不再使用区分样本的下标j

2. 简单截断法

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

在线最优化求解(Online Optimization)之二:截断梯度法(TG)    公式(2)在线最优化求解(Online Optimization)之二:截断梯度法(TG)

注意,这里面在线最优化求解(Online Optimization)之二:截断梯度法(TG)是一个正数;如果在线最优化求解(Online Optimization)之二:截断梯度法(TG)是一个向量,在线最优化求解(Online Optimization)之二:截断梯度法(TG)是向量的一个维度,那么有在线最优化求解(Online Optimization)之二:截断梯度法(TG)

3. 截断梯度法(TG)

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

在线最优化求解(Online Optimization)之二:截断梯度法(TG)   公式(3)在线最优化求解(Online Optimization)之二:截断梯度法(TG)

其中在线最优化求解(Online Optimization)之二:截断梯度法(TG)。TG同样是以k为窗口,每k步进行一次截断。当t/k不为整数时在线最优化求解(Online Optimization)之二:截断梯度法(TG),当t/k为整数时在线最优化求解(Online Optimization)之二:截断梯度法(TG)。从公式(3)可以看出,在线最优化求解(Online Optimization)之二:截断梯度法(TG)在线最优化求解(Online Optimization)之二:截断梯度法(TG)决定了在线最优化求解(Online Optimization)之二:截断梯度法(TG)的稀疏程度,这两个值越大,则稀疏性越强。尤其令在线最优化求解(Online Optimization)之二:截断梯度法(TG)时,只需要通过调节一个参数就能控制稀疏性。

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

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

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

简单截断和截断梯度的区别在于采用了不同的截断公式在线最优化求解(Online Optimization)之二:截断梯度法(TG)在线最优化求解(Online Optimization)之二:截断梯度法(TG),如图1所示。

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

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

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

在线最优化求解(Online Optimization)之二:截断梯度法(TG)    公式(4)在线最优化求解(Online Optimization)之二:截断梯度法(TG)在线最优化求解(Online Optimization)之二:截断梯度法(TG)

如果令在线最优化求解(Online Optimization)之二:截断梯度法(TG)截断公式变成:

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

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

如果令在线最优化求解(Online Optimization)之二:截断梯度法(TG)截断公式变成:

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

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

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

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

参考文献

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

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