在线学习算法FTRL

现在的位置: 首页 > 综合 > 正文

RSS

在线学习算法FTRL

2019年07月25日 ⁄ 综合 ⁄ 共 2273字 ⁄ 字号小中大 ⁄ 评论关闭

在线学习算法FTRL

声明：

1）该博文是Google专家所无私奉献的论文资料整理的。具体引用的资料请看参考文献。具体的版本声明也参考原文献

2）本文仅供学术交流，非商用。所以每一部分具体的参考资料并没有详细对应，更有些部分本来就是直接从其他博客复制过来的。如果某部分不小心侵犯了大家的利益，还望海涵，并联系老衲删除或修改，直到相关人士满意为止。

3）本人才疏学浅，整理总结的时候难免出错，还望各位前辈不吝指正，谢谢。

4）阅读本文需要机器学习、优化算法等等基础（如果没有也没关系了，没有就看看，当做跟同学们吹牛的本钱）。

5）此属于第一版本，若有错误，还需继续修正与增删。还望大家多多指点。请直接回帖，本人来想办法处理。

6）本人手上有word版的和pdf版的，有必要的话可以上传到csdn供各位下载，地址：http://download.csdn.net/detail/mytestmy/7973463

优化算法中的LBFGS解法以及GD等解法，是对一批样本进行一次求解，得到一个全局最优解。

实际的互联网广告应用需要的是快速地进行model的更新。为了保证快速的更新，训练样本是一条一条地过来的，每来一个样本，model的参数对这个样本进行一次迭代，从而保证了model的及时更新，这种方法叫做OGD（Online gradient descent）。

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

在应用的时候，线上来的每一个广告请求，都提取出相应的特征，再根据model的参数，计算一个点击某广告的概率。在线学习的任务就是学习model的参数。

所谓的model的参数，其实可以认为是下面的（1）作为目标的函数的解。跟之前说的根据批量的样本计算一个全局最优解的方法的不同是，解这个问题只能扫描一次样本，而且样本是一条一条地过来的。

${\rm{J}}\left( {\rm{x}} \right) = {\rm{l}}\left( {\rm{x}} \right) + {\rm{C}} \sum \limits_i \left| {{x_i}} \right|$
(1)

其中的l(x)是逻辑回归的似然函数的负对数，右边第二项是L1正则项，具体情况可以参看博文《从广义线性模型到逻辑回归》。
对于上面的优化问题，可以在已有L1正则的基础上，再加L2正则来防止过拟合。

1.1 FTRL-Proximal算法

下面介绍这个算法。

令给定model参数x，和第t个样本 ${v_t}$ ，定义 ${p_t} = 1/\left( {1 + {\rm{exp}}\left( { - x \cdot {v_t}} \right)} \right)$ 为该样本的label为1（也就是点击某广告）的概率；定义 ${l_t}\left( {{x_t}} \right) = - {y_t}log{p_t} - \left( {1 - {y_t}} \right){\rm{log}}\left( {1 - {p_t}} \right)$ 表示第t个样本的对数损失，也就是第t个样本的概率的负对数。第t个样本的梯度就可以表示成

${g_t} = \nabla {l_t}\left( {{x_t}} \right) = \left( {{p_t} - {y_t}} \right){v_t}$
(2)

其中model参数 ${x_t}$ 也带了下标的原因是，每次一个样本迭代完后，model参数x也发生了变化，所以可以认为model参数x跟样本v的下标是一一对应的。
原始的OGD使用下面的迭代公式

${x_{t + 1}} = {x_t} - {\eta _t}{g_t}$
(3)

其中 ${\eta _t} = 1/\sqrt t$ 是一个非增的学习率，也就是步长。

这种迭代方式够简单，但不够好，也不产生稀疏解。
FTRL-Proximal算法把OGD的迭代方式变成一个优化问题。
${x_{t + 1}} = {{\rm{argmin}}}\limits_x \left( {{g_{1:t}} \cdot x + \frac{1}{2} \sum \limits_{s = 1}^t {\sigma _s}x - {x_s}_2^2 + {\lambda _1}{x_1}} \right)$
(4)

其中 ${g_{1:t}} = \sum \limits_{s = 1}^t {g_s}$
，同时使用 ${\sigma _s}$ 定义学习率，即 ${\sigma _{1:t}} = 1/{\eta _t}$ 。这里的 ${\lambda _1}$ 是L1正则系数，如果 ${\lambda _1} = 0$ ，这个问题就能产生一个一致的迭代公式。如果 ${\lambda _1} > 0$ ，则能产生比较好的稀疏解。

上面的右边括号里面的几项都有各自的意义，第一项是对损失函数的贡献的一个估计，第二项是控制x（也就是model）在每次迭代中变化不要太大，第三项代表L1正则。
这个优化问题看起来比较难解，因为看起来要存储迭代过程产生过的所有model参数。实际上，经过巧妙的处理，只要为model参数x的每个系数存一个数就可以了。
上面的问题的最小化的部分可以重写为下面的形式

(5)

所以，只要存储一个向量 ${z_{t - 1}} = {g_{1:t - 1}} - \sum \limits_{s = 1}^{t - 1} {\sigma _s}{x_s}$ ，在第t次迭代开始后，只要用下面的公式

${z_t} = {z_{t - 1}} + {g_t} + \left( {\frac{1}{{{\eta _t}}} - \frac{1}{{{\eta _{t - 1}}}}} \right){x_t}$
(6)

就能得到 ${z_t}$ 。

只要让上面的优化问题(5)的次梯度为0，就能得到问题的解。从而可以得到上述问题的每一个维度（每一个特征的权重）的一个闭式的迭代公式。

(7)

对于上面的迭代式，如果 ${\lambda _1} = 0$ ，同时学习率η取一个常数，这个迭代过程就跟OGD是一致的。

对于步长学习率方面，FTRL-Proximal算法还做了改进，让每一个特征的学习率都不一样。每次每个特征的学习率也用下面的公式计算。

${\eta _{t,i}} = \frac{\alpha }{{\beta + \sqrt { \sum \nolimits_{s = 1}^t g_{s,i}^2} }}$
(8)

其中α根据数据和特征自适应调整，β一般取值为1。
同时，优化问题（5）还可以加上惩罚系数为 ${\lambda _2}$ 的L2正则。
经过上面的讨论，可以得到FTRL-Proximal算法的流程。

致谢
Google的多位科学家，无私地公布他们的成果。

参考文献

[1]
Follow-the-regularized-leader and mirror descent: Equivalence theorems and L1 regularization. In AISTATS, 2011.H. B. McMahan.

[2] Ad Click Prediction: a View from the Trenches.H. Brendan McMahan, Gary Holt, D. Sculley et al.

【上篇】LeetCode题解：Merge k Sorted Lists
【下篇】ftrl学习之路

作者: Unsonoroyap

该日志由 Unsonoroyap 于5年前发表在综合分类下，最后更新于 2019年07月25日.
转载请注明: 在线学习算法FTRL | 学步园 +复制链接

抱歉!评论已关闭.

学步园