Truncated Gradient (TG) 算法简介

January 12, 2016 zr9558 1 Comment

现在做在线学习和 CTR 常常会用到逻辑回归（ Logistic Regression），而传统的批量（batch）算法无法有效地处理超大规模的数据集和在线数据流，美国的 Google 公司先后三年时间（2010年-2013年）从理论研究到实际工程化实现的 FTRL（Follow-the-regularized-Leader）算法，在处理诸如逻辑回归之类的带非光滑正则化项（例如 L1 范数，做模型复杂度控制和稀疏化）的凸优化问题上性能非常出色。

通常，优化算法中的 gradient descent 等解法，是对一批样本进行一次求解，得到一个全局最优解。但是，实际的互联网广告应用需要的是快速地进行模型的更新。为了保证快速的更新，训练样本是一条一条地过来的，每来一个样本，模型的参数对这个样本进行一次迭代，从而保证了模型的及时更新，这种方法叫做在线梯度下降法（Online gradient descent）。

在应用的时候，线上来的每一个广告请求，都提取出相应的特征，再根据模型的参数，计算一个点击某广告的概率。在线学习的任务就是学习模型的参数。所谓的模型的参数，其实可以认为是一个目标函数的解。跟之前说的根据批量的样本计算一个全局最优解的方法的不同是，解这个问题只能扫描一次样本，而且样本是一条一条地过来的。

当然这会有误差，所以为了避免这种误差，又为了增加稀疏性，有人又想到了多个版本的算法，Google 公司有人总结了其中几种比较优秀的，例如 FOBOS，AOGD 和微软的 RDA，同时提出了Google自己的算法 FTRL-Proximal。其中，FTRL-Proximal 在稀疏性和精确度等方面表现都比较好。

问题描述（最小化目标函数）

等价条件：

（1）约束优化（convex constraint formulation）：

$\hat{w}=argmin_{w}\sum_{i=1}^{n}L(w,z_{i})$ subject to $||w||_{1}\leq s$

（2）无约束优化描述（soft regularization formulation）：

$\hat{w}=argmin_{w}\sum_{i=1}^{n}L(w,z_{i})+\lambda ||w||_{1}$

注：当选择合适的常数 $\lambda$ 时，这两种描述是等价的。

损失函数：

Linear Regression：

$h(W,X_{j})=W^{T}X_{j}, \ell(W,Z)=\sum_{j=1}^{M}(y_{j}-W^{T}X_{j})^{2}$

Logistic Regression：

$h(W,X_{j})=1/(1+\exp(-W^{T}X_{j})), \ell(W,Z)=\sum_{j=1}^{M}\log(1+\exp(-y_{j}W^{T}X_{j}))$

传统算法（Gradient Descent）

Batch Gradient Descent: Repeat Until Convergence

{ $W^{(t+1)}=W^{(t)}-\eta^{(t)}\nabla\ell_{W}(W^{(t)},Z)$ }

这里的 Gradient Descent 是一种批量处理的方式（Batch），每次更新 W 的时候都需要扫描所有样本来计算一个全局梯度 $\nabla\ell_{W}\ell(W^{(t)},Z).$

传统算法（Stochastic Gradient Descent）

Stochastic Gradient Descent 是另外一种权重更新方法：

Loop{

for j=1 to M { $W^{(t+1)}=W^{(t)}-\eta^{(t)}\nabla\ell_{W}(W^{(t)},Z_{j})$ }

}

这里每次迭代仅仅根据单个样本更新权重 W，这种算法称为随机梯度下降法（Stochastic Gradient Descent）。

Truncated Gradient 算法简介

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

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

（1）L1 正则化法

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

$W_{(t+1)}=W_{(t)}-\eta^{(t)}G^{(t)}-\eta^{(t)}\lambda sgn(W^{t})$

注意，这里 $\lambda \in \mathbb{R}$ 是一个标量，且 $\lambda\geq 0$ ，为 L1 正则化参数。 $sgn(v)$ 是符号函数，如果 $V=(v_{1},...,v_{N})\in \mathbb{R}^{N}$ 是一个向量，那么 $sgn(V)=(sgn(v_{1}),...,sgn(v_{N}))\in\mathbb{R}^{N}$ 。 $\eta^{(t)}$ 是学习率，通常假设为 $t^{-0.5}$ 的函数。 $G^{(t)}=\nabla \ell(W^{(t)},Z^{(t)})$ 代表了第 t 次迭代中损失函数的梯度，由于 OGD 每次仅根据观测到的一个样本进行权重更新，因此也不再使用区分样本的下标 j。

（2）简单截断法

以 k 为窗口，当 t/k 不为整数时采用标准的SGD进行迭代，当 t/k 为整数时，采用如下权重更新方式：这里的 $T_{0}(v_{i},\theta)$ 是分段函数，

$W^{(t+1)}=T_{0}(W^{(t)}-\eta^{(t)}G^{(t)},\theta)$

$T_{0}(v_{i},\theta)=0 \text{ if } |v_{i}|\leq \theta,$

$T_{0}(v_{i},\theta)=v_{i} \text{ otherwise}.$

这里 $\theta\in \mathbb{R}$ 并且 $\theta\geq 0$ 。如果 $V=(v_{1},...,v_{N})\in \mathbb{R}^{N}$ 是一个向量，那么 $T_{0}(V,\theta)=(T_{0}(v_{1},\theta),...,T_{0}(v_{N},\theta))\in \mathbb{R}^{N}$ 。

（3）截断梯度法（Truncated Gradient）

上面的简单截断法看上去十分 aggressive，因此截断梯度法在此基础上进行了改进工作。

$W^{(t+1)}=T_{1}(W^{(t)}-\eta^{(t)}G^{(t)},\eta^{(t)}\lambda^{(t)},\theta)$

这里的方程 $T_{1}$ 定义为：

$T_{1}(v_{i},\alpha,\theta)=\max(0,v_{i}-\alpha) \text{ if } v_{i}\in [0,\theta]$

$T_{1}(v_{i},\alpha,\theta)=\min(0,v_{i}+\alpha) \text{ else if } v_{i}\in [-\theta,0)$

$T_{1}(v_{i},\alpha,\theta)=v_{i} \text{ otherwise }$

其中 $\lambda^{(t)}\in \mathbb{R}$ ，并且 $\lambda^{(t)}\geq 0$ 。Truncated Gradient 方法同样是以 k 作为窗口，每进行 k 步就进行一次截断操作。当 t/k 不是整数时， $\lambda^{(t)}=0$ ，当 t/k 是整数时， $\lambda^{(t)}=k\lambda$ 。从上面的公式可以看出， $\lambda, \theta$ 决定了 W 的稀疏程度，如果 $\lambda$ 和 $\theta$ 都很大，那么稀疏性就会越强。特别的，当 $\lambda=\theta$ 时，此时只需要控制一个参数就可以控制稀疏性。

Truncated Gradient 的算法：

输入 ，初始化 
for t = 1,2,3,... 计算 
按照下面规则更新 W,

    （i）当 t/k 不是整数时，采用标准的 SGD (Stochastic Gradient Descent) 进行迭代。，并且  for all .

    （ii）当 t/k 是整数时，采取截断技术。

     , if 

     , else if 

     , otherwise
return W.

（4）Truncated Gradient，简单截断法，L1 正则化之间的关系。

简单截断法和截断梯度法的区别在于选择了不同的截断公式 $T_{0}$ 和 $T_{1}$ 。如下图所示：

T0 and T1

Truncated Gradient -> 简单截断法

从上图可以直接看出：选择 $\alpha=\theta$ ，截断梯度法就可以变成简单截断法。从公式上也可以通过计算直接得出。

Truncated Gradient -> L1 正则化

貌似有一点问题，需要重新推导。

推荐系统

Forward-Backward Splitting (FOBOS) 算法简介

January 12, 2016 zr9558 Leave a comment

FOBOS 算法简介

（1）FOBOS（Forward Backward Splitting）算法原理

前向后向切分（FOBOS，Forward Backward Splitting）是 John Duchi 和 Yoran Singer 提出的。在该算法中，权重的更新分成两个步骤：

$W^{(t+0.5)}=W^{(t)}-\eta^{(t)}G^{(t)}$

$W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t+0.5)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)\}$

第一个步骤实际上是一个标准的梯度下降（SGD），第二个步骤是对第一个步骤的结果进行局部调整。写成一个公式那就是：

$W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t)}+\eta^{(t)}G^{(t)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)\}$

假设 $F(W)=\frac{1}{2}||W-W^{(t)}+\eta^{(t)}G^{(t)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)$ ，如果 $W^{(t+1)}$ 存在一个最优解，那么可以推断 0 向量一定属于 $F(W)$ 的次梯度集合：

$0 \in \partial F(W)=W-W^{(t)}+\eta^{(t)}G^{(t)}+\eta^{(t+0.5)}\partial\Psi(W)$ .

因为 $W^{(t+1)}=argmin_{W}F(W)$ , 那么可以得到权重更新的另外一种形式：

$W^{(t+1)}=W^{(t)}-\eta^{(t)}G^{(t)}-\eta^{(t+0.5)}\partial\Psi(W^{(t+1)})$

从上面的公式可以看出，更新后的 $W^{(t+1)}$ 不仅和 $W^{(t)}$ 有关，还和自己 $\Psi(W^{(t+1)})$ 有关。这也许就是”前向后向切分”这个名称的由来。

（2）FOBOS（Forward Backward Splitting）的 L1 正则化

假设 $\Psi(W)$ 是 L1 范数，中间向量是 $W^{(t+0.5)}=(v_{1},...,v_{N})\in\mathbb{R}^{N}$ , 并且参数 $\tilde{\lambda}=\eta^{(t+0.5)}\lambda$ ，那么公式就可以展开得到

$W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t+0.5)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)\}$

$=argmin_{W}\sum_{i=1}^{N}(\frac{1}{2}(w_{i}-v_{i})^{2}+\tilde{\lambda}|w_{i}|).$

所以，可以对特征权重 W 的每一个维度进行单独求解：

$w^{(t+1)}_{i}=argmin_{w_{i}}(\frac{1}{2}(w_{i}-v_{i})^{2}+\tilde{\lambda}|w_{i}|)$ for all $latex 1\leq i \leq N$.

Claim. 如果 $w_{i}^{*}$ 是 $\min_{w_{i}}(\frac{1}{2}(w_{i}-v_{i})^{2}+\tilde{\lambda}|w_{i}|)$ 的最优解，那么 $w_{i}^{*}v_{i}\geq 0$ .

证明：反证法，如果 $w_{i}^{*}v_{i}<0$ ，那么 $\frac{1}{2}v_{i}^{2}<\frac{1}{2}(w_{i}^{*}-v_{i})^{2}+\tilde{\lambda}|w_{i}^{*}|$ ，这与条件矛盾。

通过数学计算可以证明：在 L1 正则化下，FOBOS 的特征权重的各个维度的更新公式是：

$w_{i}^{(t+1)}=sgn(v_{i})\max(0,|v_{i}|-\tilde{\lambda})$

$= sgn(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})\max\{0,|w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|-\eta^{(t+0.5)}\lambda\}$ for all $1\leq i \leq N,$

其中 $g_{i}^{(t)}$ 是梯度 $G^{(t)}$ 在第 i 个维度的分量。

从公式上看，

如果 $|w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|\leq\eta^{(t+0.5)}\lambda$ ，则有 $w_{i}^{(t+1)}=0.$ 意思就是如果这次训练产生梯度的变化不足以令权重值发生足够大的变化时，就认为在这次训练中该维度不够重要，应该强制其权重是0.

如果 $|w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|\geq\eta^{(t+0.5)}\lambda$ ，那么则有

$w_{i}^{(t+1)}=(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})-\eta^{(t+0.5)}\lambda \cdot sgn(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})$

L1-FOBOS 的算法：

（1）输入 ，初始化 
（2）for , 计算 
     按照公式更新 ， 
     for all 
（3）Return W

（3）L1-FOBOS 与 Truncated Gradient 的关系

令 $\theta=+\infty, k=1, \lambda_{TG}^{(t)}=\eta^{(t+0.5)}\lambda$ ，可以得到 L1-FOBOS 与 Truncated Gradient 完全一致，换句话说 L1-FOBOS 是 Truncated Gradient 在一些特定条件下的形式。

推荐系统

Regularized Dual Averaging Algorithm (RDA)

January 12, 2016 zr9558 Leave a comment

Regularized Dual Averaging Algorithm 算法介绍

（一）RDA（Regularized Dual Averaging Algorithm）算法原理

RDA（Regularized Dual Averaging Algorithm）叫做正则对偶平均算法，特征权重的更新策略是：

$W^{(t+1)}=argmin_{W}\{\frac{1}{t}\sum_{r=1}^{t}G^{(r)}\cdot W + \Psi(W) +\frac{\beta^{(t)}}{t}h(W)\}$

其中 $G^{(t)}\cdot W$ 指的是向量 $G^{(t)}$ 和 $W$ 的内积， $\Psi(W)$ 是正则项， $h(W)$ 是一个严格凸函数， $\{\beta^{(t)}|t\geq 1\}$ 是一个非负递增序列。

从公式中可以看出：

$\frac{1}{t}\sum_{r=1}^{t}G^{(r)}\cdot W$ 包括了之前所有梯度的平均值。
具有正则项 $\Psi(W)$ 。
额外项 $\frac{\beta^{(t)}}{t}h(W)$ 。

（二）RDA 的 L1 正则化

假设 $\Psi(W)=||W||_{1}$ ； $h(W)=\frac{1}{2}||W||_{2}^{2}$ ，i.e. $h(W)$ 是一个严格凸函数； $\beta^{(t)}=\gamma\sqrt{t} \text{ with } \gamma>0$ 是一个非负递增序列。那么 RDA 算法就可以写成：

$W^{(t+1)}=argmin_{W}\{\frac{1}{t}\sum_{r=1}^{t}G^{(r)}\cdot W + \lambda||W||_{1}+\frac{\gamma}{2\sqrt{t}}||W||_{2}^{2}\}$

此时可以采取同样的策略，把各个维度拆分成 N 个独立的问题来处理。也就是：

$w_{i+1}^{(t+1)}=argmin_{w_{i}}\{\overline{g}_{i}^{(t)}+\lambda|w_{i}|+\frac{\gamma}{2\sqrt{t}}w_{i}^{2}\}$

其中， $\lambda>0, \gamma>0,$ $\overline{g}_{i}^{(t)}=\frac{1}{t}\sum_{r=1}^{t}g_{i}^{(r)}.$

通过数学推导可以证明：

$w_{i}^{(t+1)}=0,$ if $|\overline{g}_{i}^{(t)}|<\lambda$

$w_{i}^{(t+1)}=-\frac{\sqrt{t}}{\gamma}(\overline{g}_{i}^{(t)}-\lambda\cdot sgn(\overline{g}_{i}^{(t)})),$ otherwise

意思就是：当某个维度的累加平均值 $|\overline{g}_{i}^{(t)}|$ 小于 $\lambda$ 时，该维度的权重被设置成零，此时就可以产生特征权重的稀疏性。

RDA 的算法

（1）输入 ，初始化 
（2）for  
         
         更新 ：
         
     end
     return W

（三）L1-RDA 与 L1-FOBOS 的对比

从截断方式来看，在 RDA 的算法中，只要梯度的累加平均值小于参数 $\lambda$ ，就直接进行截断，说明 RDA 更容易产生稀疏性；同时，RDA 中截断的条件是考虑梯度的累加平均值，可以避免因为某些维度训练不足而导致截断的问题，这一点与 TG，FOBOS 不一样。通过调节参数 $\lambda$ 可以在精度和稀疏性上进行权衡。

（四）L1-RDA 与 L1-FOBOS 形式上的统一

在 L1-FOBOS 中，假设 $\eta^{(t+0.5)}=\eta^{(t)}=\Theta(t^{-0.5})$ ，可以得到：

$W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t)}+\eta^{(t)}G^{(t)}||_{2}^{2}+\eta^{(t)}\lambda||W||_{1}\}$

通过计算可以把 L1-FOBOS 写成：

$W^{(t+1)}=argmin_{W}\{G^{(t)}\cdot W+\lambda||W||_{1}+\frac{1}{2\eta^{(t)}}||W-W^{(t)}||_{2}^{2}$

同时 L1-RDA 可以写成：

$W^{(t+1)}=argmin_{W}\{G^{(1:t)}\cdot W + t\lambda||W||_{1}+\frac{1}{2\eta^{(t)}}||W-0||_{2}^{2} \}$

其中 $G^{(1:t)}=\sum_{s=1}^{t}G^{(s)}$ 。如果令 $\sigma^{(s)}=\frac{1}{\eta^{(s)}}-\frac{1}{\eta^{(s-1)}},$ $\sigma^{(1:t)}=\frac{1}{\eta^{(t)}},$ $\sigma^{(1:t)}=\sum_{s=1}^{t}\sigma^{(s)},$ 上面的公式可以写成：

L1-FOBOS：

$W^{(t+1)}=argmin_{W}\{G^{(t)}\cdot W+\lambda||W||_{1}+\frac{1}{2}\sigma^{(1:t)}||W-W^{(t)}||_{2}^{2}\}$

L1-RDA ：

$W^{(t+1)}=argmin_{W}\{G^{(1:t)}\cdot W + t\lambda||W||_{1}+\frac{1}{2}\sigma^{(1:t)}||W-0||_{2}^{2} \}$

可以看出：

L1-FOBOS 考虑了梯度和当前模的 L1 正则项，L1-RDA 考虑的是累积梯度。
L1-FOBOS 的第三项限制 W 不能够距离已经迭代过的 $W^{(t)}$ 值太远，L1-RDA 的第三项限制的是 W 不能够距离 0 太远。

M	T	W	T	F	S	S
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

ZHANG RONG

Daily Archives: January 12, 2016