深入理解FTRL

FTRL算法是吸取了FOBOS算法和RDA算法的两者优点形成的Online Learning算法。读懂这篇文章，你需要理解LR、SGD、L1正则。

FOBOS算法

前向后向切分（FOBOS，Forward Backward Splitting）是 John Duchi 和 Yoran Singer 提出的。在该算法中，权重的更新分成两个步骤，其中t是迭代次数，\eta^t是当前迭代的学习率，G^t是loss func的梯度，\Psi(W)是正则项，如下：

W^{t+0.5}=W^t-\eta^tG^t
W^{t+1}=argmin_W\{ \frac{1}{2} \Vert W-W^{t+0.5} \Vert^2_2 + \eta^{t+0.5}\Psi(W) \}

权重更新的另外一种形式：
对上式argmin部分求导，令导数等于0可得：
W^{t+1}=W^t-\eta^tG^t-\eta^{t+0.5}\partial\Psi(W^{t+1})
这就是权重更新的另外一种形式，可以看到W^{t+1}的更新不仅与W^{t}有关，还与自己本身有关，有人猜测这就是前向后向的来源。

L1-FOBOS，正则项为L1范数，其中\lambda>0：
W^{t+0.5}=W^t-\eta^tG^t
W^{t+1}=argmin_W\{ \frac{1}{2} \Vert W-W^{t+0.5} \Vert^2_2 + \eta^{t+0.5}\lambda\Vert W \Vert_1 \}

合并为一步：
令\eta^{t+0.5}=\eta^t，将二次项乘开，消去常数项得
W^{t+1}=argmin_W\{ G^t W + \frac{1}{2\eta^t} \Vert W-W^t \Vert^2_2 + \lambda \Vert W \Vert_1\}

闭式解：
w^{t+1}_i = \begin{cases}0, & if\ \vert w^t_i-\eta^t g^t_i\vert\leq\eta^{t+0.5}\lambda \\ (w^t_i-\eta^t g^t_i)-\eta^{t+0.5}\lambda\cdot sgn(w^t_i-\eta^t g^t_i), & otherwise \end{cases}
推导过程略，思路同下方FTRL闭式解的推导过程。

  • 为什么一般设\eta^{t+0.5}=\eta^t？
    我们希望这一步更新中，上半步和下半部的步长（学习率）一样。

RDA算法

RDA（Regularized Dual Averaging Algorithm）叫做正则对偶平均算法，特征权重的更新策略如下，只有一步，其中
累积梯度G^{(1:t)}=\sum_{s=1}^t G^s，
累积梯度平均值g^{(1:t)}=\frac1t\sum_{s=1}^t G^s=\frac{G^{(1:t)}}{t}，
\Psi(W)是正则项，h(W)是一个严格的凸函数，\beta^{(t)}是一个关于t的非负递增序列：

W^{t+1}=argmin_W \{ g^{(1:t)} W + \Psi(W) + \frac{\beta^{(t)} } {t} h(W) \}

L1-RDA：
令\Psi(W)=\lambda\Vert W \Vert_1，令h(W)=\frac{1}{2}\Vert W \Vert^2_2，令\beta^{(t)}=\gamma\sqrt{t}，其中\lambda>0，\gamma>0，并且各项同时乘以t，得：
W^{t+1}=argmin_W\{ g^{(1:t)}W + \lambda \Vert W \Vert_1 + \frac{\gamma}{2\sqrt{t}}\Vert W \Vert^2_2\}

闭式解：
$$
推导过程略，思路同下方FTRL闭式解的推导过程。

  • L1-FOBOS与L1-RDA对比
    从截断方式来看，在 RDA 的算法中，只要梯度的累加平均值小于参数\lambda就直接进行截断，说明 RDA 更容易产生稀疏性；同时，RDA 中截断的条件是考虑梯度的累加平均值，可以避免因为某些维度训练不足而导致截断的问题，这一点与 TG，FOBOS 不一样。通过调节参数\lambda可以在精度和稀疏性上进行权衡。
  • 为什么h(W)是一个严格的凸函数？
    因为凸函数+凸函数=凸函数，可以保证整体的凸性，argmin的部分如果不保证凸性，极值就不存在，则无法更新权重。
  • 为什么\beta^{(t)}是一个关于t的非负递增序列？
    可以认为学习率\eta^t=\frac{1}{\gamma\sqrt{t}}，\beta^{(t)}可以看作是学习率的倒数，因为学习率设置为随着迭代次数增加而减小的正数，所以\beta^{(t)}是一个关于t的非负递增序列。

FTRL算法

FTRL 算法综合考虑了 FOBOS 和 RDA 对于梯度和正则项的优势和不足，其中累积梯度G^{(1:t)}=\sum_{r=1}^t G^r，\sigma^s=\frac{1}{\eta^s}-\frac{1}{\eta^{s-1}}，\sigma^{(1:t)}=\frac{1}{\eta_t}=\sum_{s=1}^t \sigma^s，\lambda_1>0，\lambda_2>0，特征权重的更新公式是：
W^{t+1}=argmin_w\{ G^{(1:t)}W + \lambda_1 \Vert W \Vert_1 + \frac{\lambda_2}{2}\Vert W \Vert^2_2 + \frac{1}{2}\sum_{s=1}^t\sigma^s\Vert W-W^s\Vert^2_2 \}
维度i的学习率设置为\eta^t_i = \frac{\alpha}{\beta+\sqrt{\sum_{s=1}^t (g^{(s)})^2}}，随着迭代次数增加而减小，\beta主要作用是保证分母不为0.

使用\sigma替换学习率可将L1-FOBOS、L1-RDA、FTRL写成类似的形式，如下：
W^{t+1}_{(L1-FOBOS)}=argmin_W\{ G^t W + \lambda \Vert W \Vert_1 + \frac{1} {2} \sigma^{(1:t)} \Vert W-W^t \Vert^2_2 \}
W^{t+1}_{(L1-RDA)}=argmin_W\{ G^{(1:t)}W + t\lambda \Vert W \Vert_1 + \frac{1}{2}\sigma^{(1:t)}\Vert W-0 \Vert^2_2\}
W^{t+1}_{(FTRL)}=argmin_W\{ G^{(1:t)}W + \lambda_1 \Vert W \Vert_1 + \frac{\lambda_2}{2}\Vert W \Vert^2_2 + \frac{1}{2}\sum_{s=1}^t\sigma^s\Vert W-W^s\Vert^2_2 \}
各项解释todo

闭式解及其推导过程：
将二次项乘开，消去常数项，得：
W^{t+1}=argmin_W\{ (G^{(1:t)}-\sum_{s=1}^t \sigma^sW^s)W + \lambda_1 \Vert W \Vert_1 + \frac{1} {2} (\lambda_2+\sum_{s=1} ^t \sigma^s) \Vert W \Vert^2_2 \}
设Z^t=G^{(1:t)}-\sum_{s=1}^t\sigma^sW^s，则Z^t=Z^{t-1}+G^t-\sigma^t W^t，得：
W^{t+1} = argmin_W\{Z^tW+\lambda_1\Vert W \Vert_1 + \frac{1}{2}(\lambda_2+\sum_{s=1}^t \sigma^s)\Vert W \Vert^2_2\}
对于单个维度i来说：
w^{t+1}_i = argmin_w \{ z^t_i w_i + \lambda_1 \vert w_i \vert + \frac{1}{2} (\lambda_2 + \sum_{s=1}^t \sigma^s) w^2_i \}
对上式，假设w^*_i是最优解，令上式导数等于0可得：
z^t_i+\lambda_1sgn(w^*_i)+(\lambda_2+\sum_{s=1}^t\sigma^s)w^*_i=0
我们分三种情况进行讨论

  1. 当\vert z^t_i\vert\leq\lambda_1时：
    1. 当w^*_i=0时，满足sgn(0) \in (-1,1)，成立
    2. 当w^*_i>0时，z^t_i+\lambda_1sgn(w^*_i)=z^t_i+\lambda_1\geq0且(\lambda_2+\sum_{s=1}^t\sigma^s)w^*_i>0上式不成立
    3. 当w^*_i<0时，z^t_i+\lambda_1sgn(w^*_i)=z^t_i-\lambda_1\leq0且(\lambda_2+\sum_{s=1}^t\sigma^s)w^*_i<0上式不成立
  2. 当z^t_i>\lambda_1时：
    1. 当w^*_i=0时，不满足sgn(0) \in (-1,1)，不成立
    2. 当w^*_i>0时，z^t_i+\lambda_1sgn(w^*_i)=z^t_i+\lambda_1>0且(\lambda_2+\sum_{s=1}^t\sigma^s)w^*_i>0，上式不成立
    3. 当w^*_i<0时，z^t_i+\lambda_1sgn(w^*_i)=z^t_i-\lambda_1>0且(\lambda_2+\sum_{s=1}^t\sigma^s)w^*_i<0，w^*_t有解，w^*_t=-(\frac{\beta+\sqrt{\sum_{s=1}^t (g^{(s)})^2}}{\alpha}+\lambda_2)^{-1}(z^t_i-\lambda_1)
  3. 当z^t_i<-\lambda_1时：
    1. 当w^*_i=0时，不满足sgn(0) \in (-1,1)，不成立
    2. 当w^*_i>0时，z^t_i+\lambda_1sgn(w^*_i)=z^t_i+\lambda_1<0且(\lambda_2+\sum_{s=1}^t\sigma^s)w^*_i>0，w^*_t有解，w^*_t=-(\frac{\beta+\sqrt{\sum_{s=1}^t (g^{(s)})^2}}{\alpha}+\lambda_2)^{-1}(z^t_i+\lambda_1)
    3. 当w^*_i<0时，z^t_i+\lambda_1sgn(w^*_i)=z^t_i-\lambda_1<0且(\lambda_2+\sum_{s=1}^t\sigma^s)w^*_i<0，上式不成立

综上，可得分段函数形式的闭式解：
w^{t+1}_i= \begin{cases} 0, & if \ \vert z^t_i\vert<\lambda_1 \\ -(\frac{\beta+\sqrt{\sum_{s=1}^t (g^{(s)})^2}}{\alpha}+\lambda_2)^{-1}(z^t_i-sgn(z^t_i)\lambda_1), & \text{otherwise} \end{cases}

论文内的伪代码
  • 引入L2范数与否是等价的
    我们不难发现论文[1]中的权重更新公式中是没有L2正则项的，但是伪代码中却有L2正则项系数\lambda_2，这是因为更新公式中的超参数\frac\beta\alpha + \lambda_2 \approx \frac\beta\alpha，相当于通过调节超参，引入L2范数与否没有区别。论文中的伪代码这样写，相当于减少了一个超参数，如果是调过参的同学就知道减少一个超参数意味着什么。
  • 为什么学习率长这样
    类似Adagrad的思想

    用硬币实验解释todo
  • 去除正则项的FTRL等价于SGD可推导
    论文原话是Without regularization, this algorithm is identical to standard online gradient descent.
  • 如何直观理解累积梯度的作用
  • 在实现上，full train和increment train的有什么区别

FTRL工程实现上的trick

  • 近似代替梯度平方和

    如果不理解，回去仔细研究LR的公式。

  • 去除低频特征
    由于长尾，大部分特征是稀疏的，且频次很低，online的场景无法用batch的方式去统计特征频次。论文提了两个方案，以泊松概率p决定特征是否更新和建立Bloom Filter Inclusion。我看大部分实现都是用Bloom Filter。
  • 负采样，权重更新时除以负采样率
  • 使用更少的位来进行浮点数编码
  • 四个超参的经验值
  • 如何用FTRL做广告探索todo

[1] McMahan, H. Brendan, et al. "Ad click prediction: a view from the trenches." Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2013.
[2] 张戎 FOLLOW THE REGULARIZED LEADER (FTRL) 算法总结 https://zhuanlan.zhihu.com/p/32903540

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
禁止转载，如需转载请通过简信或评论联系作者。
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 202,980评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,178评论 2赞 380
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 149,868评论 0赞 336
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,498评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,492评论 5赞 364
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,521评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,910评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,569评论 0赞 256
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,793评论 1赞 296
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,559评论 2赞 319
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,639评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,342评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,931评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,904评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,144评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,833评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,350评论 2赞 342

推荐阅读更多精彩内容