在线学习：从梯度截断到FTRL

作者: yi_cloud | 来源:发表于2019-01-11 17:49 被阅读0次

在线学习：从梯度截断到FTRL
在线学习FTRL
TensorFlow 梯度截断
关于在线学习算法ftrl的理解
机器学习从梯度分析到回归
「机器学习笔记」梯度下降 Gradient Descent
从机器学习到深度学习（二）梯度下降
SQLZOO笔记-SELECT基础
第一周 - Parameter Learning
TensorFlow从0到1 - 7 - TensorFlow线

什么是在线学习，为什么要用在线学习

在一些大型互联网公司的广告系统中，Logistic Regression的权重更新非常看重速度，否则无法应对超大规模的数据集和在线数据流，因此就不能再用传统的批量梯度更新方法。在线学习是根据新来的样本，一边学习，一边对样本进行预测，从而保证了模型的及时更新。在线更新算法主要为了减少在线更新的误差同时又保证参数的稀疏性。

Truncated Gradient

问题定义：

无优化约束描述：

soft regularization formulation，L1正则约束

Logistic Regression损失函数：

LR损失函数

相对于TG来说，两种传统的优化算法是Gradient Decsent和Stochastic Gradient Decsent。SGD每次只选择一个样本更新参数，但是没有考虑稀疏性。

简单截断

解决参数稠密问题，最简单粗暴的方法就是当参数矩阵W中某维参数w小于设定阈值时直接置为0，但是w数值比较小可能是因为迭代轮数小学习不充分，简单截断可能会丢失重要特征。

K是截断窗口的大小，窗口中的迭代正常进行。

简单截断更新公式

T0是分段函数

梯度截断

上面的简单截断法看上去十分 aggressive，TG则是对简单截断的一种改进，同样是以 k 作为窗口，每进行 k 步就进行一次截断操作：

梯度截断更新公式

T1是分段函数，cta是截断阈值，alpha是截断斜率

从上面的公式可以看出， $\lambda ,\theta$ 决定了 W 的稀疏程度，如果 $\lambda$ 和 $\theta$ 都很大，那么稀疏性就会越强。

简单截断和梯度截断的对比

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

FOBOS（FORWARD-BACKWARD SPLITTING）

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

第一项2范数那项表示不能离loss损失迭代结果太远，第二项通常是正则化项（例如L1范数），用来限定模型复杂度、抑制过拟合和做稀疏化等。设：

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

那么Wt+1的最优解一定在F(W)的偏导集合中：

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

进而得到另一种权重更新方式：

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

RDA（Regularized Dual Averaging Algorithm）

RDA的特点是：相对FOBOS，在精度与稀疏性之间做平衡，其中实验表明，在L1正则下，RDA比FOBOS可以更加有效地得到稀疏解。

$W^{(t+1)}=argmin_W{\{\frac {1}{t}\sum\nolimits_{r=1}^t G^{(r)}\cdot W + \Psi(W) + \frac{\beta^{(t)}}{t}h(W)\}}$

公式中第一项表明前t轮所有梯度的均值作为了当前轮参数的稀疏， $\psi (W)$ 通常指L1范数 $||W||_1$ ， $h(W)$ 通常指L2范数 $\frac{1}{2}||W||_{2}^2$ 。 $\beta^t=\gamma \sqrt{t} (\gamma >0)$ 是一个非负递增序列。自然地RDA的L1形式如下：

$W^{(t+1)}=argmin_W{\{\frac {1}{t}\sum\nolimits_{r=1}^t G^{(r)}\cdot W + \lambda||W||_1 + \frac{\gamma}{2\sqrt{t}}||W||_2^2\}}$

因此第t+1轮的参数矩阵中 $\omega _{i+1} (i\in [0,n-1])$ 的更新方式如下：

$\omega _{i+1}^{(t+1)}=argmin_{w_1}{\{\bar{g}_i^{(t)}+\lambda|\omega_i|+\frac{\gamma}{2\sqrt{t}}\omega_i^2 \}}$

其中 $g_i^{(t)}=\frac{1}{t}\sum\nolimits_{r=1}^t g_i^{(r)}$

经过推导证明， $\omega _{i+1}$ 可以表示成如下形式：

$\omega_i^{(t+1)}=0, if |\bar{g}_i^{(t)}|<\lambda \\ \omega_i^{(t+1)}=-\frac {\sqrt t}{\gamma}(\bar{g}_i^{(t)}-\lambda\cdot sgn(\bar{g}_i^{(t)})),otherwise$

意思就是：当某个维度的累加平均值小于 $\lambda$ 时，时，该维度的权重被设置成零，此时就可以产生特征权重的稀疏性。

RDA与FOBOS形式上的统一：

假设 $\eta ^{(t+0.5)}=\eta ^{(t)}=\Theta (t^{-0.5})$ ，并带入到FOBOS-L1的权重更新公式中，可以得到：

$W^{(t+1)}=argmin_W{\{||\frac {1}{2}W-W^{(t)}+\eta^{(t)}G^{(t)} ||_2^2 +\eta^{(t)}\lambda ||W||_1\}}$

等式右边除以 $\eta ^{(t)}$ 可以整理成如下形式:

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

同时LDA-L1可以整理成：

$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}^tG^{(s)}$ ，如果令： $\sigma^{(s)}=\frac {1}{\eta^{(s)}}-\frac {1}{\eta^{(s-1)}},\sigma^{(1:t)}=\frac {1}{\eta^{(s)}},\sigma^{(1:t)}=\sum_{s=1}^t\sigma ^{(s)}$

上面的公式可以写成：

FOBOS:

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

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\}}$

从公式上来看，

FTRL

FTRL同时借鉴了RDA和FPBOS的思想

用公式表达就是

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

可以看出，既用到了RDA的前t轮梯度均值，又用到了保证每次迭代权重不会变化太多。

FTRL求解过程如下：

在线学习：从梯度截断到FTRL
什么是在线学习，为什么要用在线学习在一些大型互联网公司的广告系统中，Logistic Regression的权重...
在线学习FTRL
CTR预估背景介绍点击率预测是对每次广告的点击情况做出预测，可以判定这次为点击或不点击，也可以给出点击的概率，有...
TensorFlow 梯度截断
关于在线学习算法ftrl的理解
今晚在看ftrl算法的参数更新策略，看得不是很懂，然后就手抄一下，就感觉知道是那么回事了。当中损失函数对向量的...
机器学习从梯度分析到回归
因素：因直播平台故障临时更换直播平台，导致视频卡顿延迟严重，为当天没有看到直播的学员道歉，但是学员仍旧热情高涨，与...
「机器学习笔记」梯度下降 Gradient Descent
前言：梯度下降是常用的机器学习算法，本篇笔记写的是在线性回归模型使用「梯度下降算法」。通过循环同时修改斜率和y轴...
从机器学习到深度学习（二）梯度下降
梯度下降用于迭代求解函数最优解，是大数据领域用于求解问题的常用思想。步长：每一步梯度下降时向目标方向前进的长度。...
SQLZOO笔记-SELECT基础
SQLZoo网站是一个SQL在线交互课程，适合初学者入门。优点：学习梯度平稳，带着实例，从最基础的一小块知识点...
第一周 - Parameter Learning
梯度下降算法梯度下降算法可以将代价函数J最小化，它不仅被用在线性回归上，实际上被广泛的应用于机器学习领域中的众多...
TensorFlow从0到1 - 7 - TensorFlow线
TensorFlow从0到1系列回顾上一篇 6 解锁梯度下降算法解释清楚了学习率（learning rate）。...