在线最优化求解(Online Optimization)之二：截断梯度法(TG)
在预备篇中我们做了一些热身，并且介绍了L1正则化在Online模式下也不能产生较好的稀疏性，而稀疏性对于高维特征向量以及大数据集又特别的重要。因此，从现在开始，我们沿着提升模型稀疏性的主线进行算法介绍。
为了得到稀疏的特征权重 ，最简单粗暴的方式就是设定一个阈值，当的某维度上系数小于这个阈值时将其设置为
称作简单截断）。这种方法实现起来很简单，也容易理解。但实际中（尤其在OGD里面）
的某个系数比较小可能是因为该维度训练不足引起的，简单进行截断会造成这部分特征的丢失。
截断梯度法（TG, Truncated Gradient）是由John Langford，Lihong Li和Tong Zhang在2009年提出，实际上是对简单截断的一种改进。下面首先描述一下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