FTRL在线最优化

（一）RDA（Regularized Dual Averaging）

是微软的研究成果，它更有效地提升了特征权重的稀疏性。

算法原理--特征权重的更新策略为： $W^ {(t+1)} ={\arg\min}_{W} \{ \frac{1}{2}\sum_{r=1}^t <G^{(t)},W >+\psi (W)+\frac{\beta ^t }{t} h(W) \}$ ---公式(1)

其中 $\frac{1}{2} <G^{(t)},W >$ 表示梯度 $G^{(t)}$ 对W的积分中值； $\psi (W)$ 表示正则项；h(W)表示一个辅助的严格凸函数； $\{\beta ^t |t \geq 1 \}$ 是一个非负且非自减序列。

L1-RDA

令: $\psi (W)=\lambda \mathop \| W \|_{1}$ ， $h(W)=\frac{1}{2} \| W \|_{2}^2$ ， $\beta ^t =\gamma \sqrt{t}$ ，将公式(1)L1正则化

$W^ {(t+1)} ={\arg\min}_{W} \{ \frac{1}{2}\sum_{r=1}^t <G^{(t)},W >+\lambda \mathop \| W \|_{1}+\frac{\gamma }{2\sqrt{t}} \| W \|_{2}^2 \}$

根据特征权重的各个维度将其拆解成N个独立的标量最小化问题：

$\min_{w_{i}\in \mathbb {R} } \{ \frac{1}{2}\sum_{r=1}^t <{g_{i} }^{(t)},w_{i} >+\lambda \mathop \| w_{i} \|_{1}+\frac{\gamma }{2\sqrt{t}} \| w_{i} \|_{2}^2 \}$

即 $\min_{w_{i}\in \mathbb {R} } \{ \frac{1}{2}\sum_{r=1}^t {g_{i} }^{(t)} w_{i} +\lambda \mathop | w_{i} |+\frac{\gamma }{2\sqrt{t}} w_{i} ^2 \}$

这里 $\lambda \geq 0$ ， $\gamma > 0$ ，假设 $w_i^*$ 是最优解

次导数 $\partial | w_{i} |=\left\{ \begin{aligned}\{-1<\xi <1\} \quad if \ w_{i}^* = 0 \\\{1\} \quad if \ w_{i}^* > 0 \\\{-1\} \quad if \ w_{i}^* </p><p>求导并等于0：<img class=$ ---公式(2)

令 $\bar{g}_{i} ^t =\frac{1}{2}\sum_{r=1}^t {g_{i} }^{(t)}$

求导并令等于0： $\bar{g}_{i} ^t +\lambda \partial | w_{i}^* | +\frac{\gamma }{\sqrt{t}} w_{i}^*=0$

(1)当 $w_{i}^* = 0$ 时， $\bar{g}_{i} ^t +\lambda \partial | w_{i}^* | =0$ ，得 $| \bar{g}_{i} ^t | < \lambda$

(2)当 $w_{i}^* < 0$ 时， $w_{i}^* =\frac{\sqrt{t} }{\gamma } (\lambda -\bar{g}_{i} ^t)$ ，则 $\frac{\sqrt{t} }{\gamma } (\lambda -\bar{g}_{i} ^t)<0$ ，即 $0 \leq \lambda <\bar{g}_{i} ^t$

(3)当 $w_{i}^* > 0$ 时， $w_{i}^* =\frac{\sqrt{t} }{\gamma } (-\lambda -\bar{g}_{i} ^t)$ ，则 $\frac{\sqrt{t} }{\gamma } (-\lambda -\bar{g}_{i} ^t)>0$ ，即 $\bar{g}_{i} ^t < -\lambda \leq 0$

综合可知，L1-RDA特征权重的各个维度更新的方式为： $w_{i}^{(t+1)} =\left\{ \begin{aligned}0 \ \ \ \ \ \ \ \ \ \ \ \ \quad if \ | \bar{g}_{i} ^t | < \lambda \\\frac{\sqrt{t} }{\gamma } (\lambda \cdot sgn(\bar{g}_{i} ^t) -\bar{g}_{i} ^t ) \quad if \ otherwise )\end{aligned} \right\}$

L1-RDA的“截断阈值”为λ，是一个常数，并不随着t而变化，因此这种性质使得L1-RDA更容易产生稀疏性。某一维特征的梯度累加中值未达到“截断阈值”时，其特征权重仍置为0。

（二）FOBOS(Forward-Backward Splitting)

算法原理---把正则化的梯度下降问题分成一个经验损失梯度下降迭代和一个最优化问题：其中第二个最优化问题有两项：第一项2范数那项表示不能离loss损失迭代结果太远，第二项是正则化项，用来限定模型复杂度、抑制过拟合和做稀疏化等。

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

$W^{(t+1)}=\arg\min_{W} \{ \frac{1}{2}\|W-W^{(t+\frac{1}{2})} \|_2^2+\eta^{(t+\frac{1}{2})}\Psi (W) \}$

其中 $\eta>0$ 是学习率，通常定义为 $\frac{1}{\sqrt{t} }$ 的正相关函数； $\Psi (W)>0$ 是正则项；

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

L1-FOBOS

令 $V=W^{(t+\frac{1}{2})}$ 是已知的， $\Psi (W) =\lambda ||W||_1$ , $\tilde{\lambda } =\eta^{(t+\frac{1}{2} )} \lambda$ ，并拆解成对特征权重每一维度单独求解：

$w_i^{(t+1)}=\arg \min_{w_i} \{ \frac{1}{2}(w_i-v_i)^2+\tilde{\lambda }|w_i| \}$

假设 $w_i^*$ 是最优解，有 $w_i^* v_i\geq 0$

反证法：

假设 $w_i^* v_i<0$ 成立，则 $\frac{1}{2}(w_i-v_i)^2+\tilde{\lambda }|w_i| > \frac{1}{2}v_i^2$ ，则此时最优解是 $w_i^*=0$ ，与假设矛盾。得证： $w_i^* v_i\geq 0$ 。

wi的次导数见上面的公式(2)

求导： $w_i^*-v_i+\tilde{\lambda }\partial |w_i^*| =0$

(1)当 $w_i^*=0$ 时， $|v_i|<\tilde{\lambda }$

(2)当 $w_i^*>0$ 时， $w_i^*=v_i-\tilde{\lambda } =v_i-\tilde{\lambda } \cdot sgn(v_i)$ ， $v_i>-\tilde{\lambda }$

(3)当 $w_i^*<0$ 时， $w_i^*=v_i+\tilde{\lambda } =v_i-\tilde{\lambda } \cdot sgn(v_i)$ ， $v_i<-\tilde{\lambda }$

综合可知，L1-FOBOS特征权重的各个维度更新的方式为：

$w_{i}^{(t+1)} =\left\{ \begin{aligned}0 \ \ \ \ \ \quad if \ | w_i^{( t )}-\eta^{(t)} g_i^{(t)} | < \eta^{(t+\frac{1}{2} )}\lambda \\\ w_i^{(t)}-\eta^{(t)} g_i^{(t)}-\eta^{(t+\frac{1}{2} )} \lambda \cdot sgn(w_i^{(t)}-\eta^{(t)} g_i^{(t)}) \quad if \ otherwise )\end{aligned} \right\}$

L1-RDA VS L1-FOBOS

在L1-FOBOS中，“截断阈值”随着时间t会逐渐减低，而L1-RDA是固定的，这种性质使得L1-RDA更容易产生稀疏性；RDA中判定对象是梯度的累加平均值，而L1-FOBOS针对单次梯度计算的结果进行判定，使得L1-RDA避免了由于某些维度由于训练不足导致截断的问题。

实验证明，L1-FOBOS这一类基于梯度下降的方法有比较高的精度，但是L1-RDA却能在损失一定精度的情况下产生更好的稀疏性。

（三）FTRL（Follow the Regularized Leader）

$W^{(t+1)}=\arg \min_{W} \{ G^{(1:t)}W+\lambda_1 ||W||_1+\lambda _2||W||_2^2+\frac{1}{2}\sum_{s=1}^t (\delta ^{(s)}||W-W^{(s)}||_2^2) \}$ -----公式(3)

$G^{(1:t)}=\sum_{s=1}^t G^ {(s)}$

$\delta ^{(s)}=\frac{1}{\eta ^{(s)} } -\frac{1}{\eta ^{(s-1)}}$

$\delta ^{(1:t)}=\sum_{s=1}^t \delta ^{(s)}=\frac{1}{\eta ^{(t)} }$

公式(3)中出现了L2正则项，在论文[2]的公式中并没有这一项，但是在其2013年发表的FTRL工程化实现的论文[3]却使用到了L2正则项。事实上该项的引入并不影响FRTL的稀疏性，后面的推导过程会显示这一点。L2正则项的引入仅仅相当于对最优化过程多了一个约束，使得结果求解结果更加“平滑”。

根据特征权重的各个维度将其分解成若干个独立的标量最小化问题：

$w_i^{(t+1)}=\arg \min_{w_i} \{ g^{(1:t)}w_i+\lambda_1 |w_i|+\lambda_2 w_i^2+\frac{1}{2}\sum_{s=1}^t (\delta ^{(s)}(w_i-w_i^{(s)})^2) \}$

公式(3)最后一项展开，等价于：

$w_i^{(t+1)}=\arg \min_{w_i} \{ (g^{(1:t)}-\sum\nolimits_{s=1}^t \delta ^{(s)}w_i^{(s)} )w_i+(\lambda _2 +\frac{1}{2} \sum_{s=1}^t \delta ^{(s)} )w_i^2+\lambda _1|w_i|+\frac{1}{2} \sum_{s=1}^t \delta^{(s)}(w_i^{(s)})^2 \}$

最后一项是常数项，可忽略，并令 $z^{(t)}=g^{(1:t)}-\sum\nolimits_{s=1}^t \delta ^{(s)}w_i^{(s)}$

$w_i^{(t+1)}=\arg \min_{w_i} \{ z^{(t)}w_i+(\lambda _2 +\frac{1}{2} \sum_{s=1}^t \delta ^{(s)} )w_i^2+\lambda _1|w_i| \}$

花括号里面求导并令等于0： $z^{(t)}+(2\lambda _2 + \sum_{s=1}^t \delta ^{(s)} )w_i+\lambda _1 \partial|w_i| =0$

令 $w_i^*$ 是最优解

(1)当 $w_i^*=0$ 时， $| z^{(t)}|\leq \lambda _1$

(2)当 $w_i^*> 0$ 时， $z^{(t)}<- \lambda _1<0$ ， $w_i^*=-(2\lambda _2+\sum_{s=1}^t \delta ^{(s)})^{-1} \cdot (z_i^{(t)}+\lambda _1)=-(2\lambda _2+\sum_{s=1}^t \delta ^{(s)})^{-1} \cdot (z_i^{(t)}-\lambda _1\cdot sgn(z_i^{(t)}))$

(3)当 $w_i^*< 0$ 时， $z^{(t)}> \lambda _1>0$ ， $w_i^*=-(2\lambda _2+\sum_{s=1}^t \delta ^{(s)})^{-1} \cdot (z_i^{(t)}-\lambda _1)=-(2\lambda _2+\sum_{s=1}^t \delta ^{(s)})^{-1} \cdot (z_i^{(t)}-\lambda _1\cdot sgn(z_i^{(t)}))$

综合可知，FTRL特征权重的各个维度更新的方式为：

$w_{i}^{(t+1)} =\left\{ \begin{aligned}0 \ \ \ \ \ \ \ \ \ \ \ \ \quad if \ | z^{(t)} | < \lambda_1 \\\ -(2 \lambda _2+\sum_{s=1}^t \delta ^{(s)})^{-1} \cdot (z_i^{(t)}-\lambda _1\cdot sgn(z_i^{(t)})) \quad if \ otherwise )\end{aligned} \right\}$

或者简化等价为 $w_{i}^{(t+1)} =\left\{ \begin{aligned}0 \ \ \ \ \ \ \ \ \ \ \ \ \quad if \ | z^{(t)} | < \lambda_1 \\\ -(\lambda _2+\sum_{s=1}^t \delta ^{(s)})^{-1} \cdot (z_i^{(t)}-\lambda _1\cdot sgn(z_i^{(t)})) \quad if \ otherwise )\end{aligned} \right\}$ ---公式(4)

可知，引入L2正则化并没有对FTRL结果的稀疏性产生任何影响。

Per-Coordinate Learning Rates

标准的学习率 $\eta ^{(t)} =\frac{1}{\sqrt{t} }$ ，这个策略保证了学习率是一个正的非增长序列，对于每一个特征维度都是一样的。

事实上在FTRL中，每个维度上的学习率都是单独考虑的（Per-Coordinate Learning Rates）。

公式(4)变为： $w_{i}^{(t+1)} =\left\{ \begin{aligned}0 \ \ \ \ \ \ \ \ \ \ \ \ \quad if \ | z^{(t)} | < \lambda_1 \\\ -(\lambda _2+\frac{1}{\eta_i ^{(t)}} )^{-1} \cdot (z_i^{(t)}-\lambda _1\cdot sgn(z_i^{(t)})) \quad if \ otherwise )\end{aligned} \right\}$

$\eta_i ^{(t)} =\frac{\alpha }{\beta +\sqrt{\sum_{s=1}^t (g_i^{(s)})^2} }$

（四）FTRL工程实现

完毕。

最后编辑于：2019.05.12 17:23:51

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

FTRL在线最优化

推荐阅读更多精彩内容