在线学习–FTRL

140次阅读
没有评论

OGD 基本概念

OGD ( online gradient descent ) 是传统梯度下降的 online 版本,参数更新公式为: $$ {w}_{t+1} = {w}_t – \eta_t {g}_t \tag{1.1} $$ t 表示第 t 轮迭代,注意上式中的学习率 $\eta_t$ 每轮都会变,一般设为 $ \eta_t = \frac{1}{\sqrt{t}} $

OGD 在准确率上表现不错,即 regret 低,但在上文的另一个考量因素 sparsity 上则表现不佳,即使加上了 L1 正则也很难使大量的参数变零。一个原因是浮点运算很难让最后的参数出现绝对零值;另一个原因是不同于批处理模式,online 场景下每次 w 的更新并不是沿着全局梯度进行下降,而是沿着某个样本的产生的梯度方向进行下降,整个寻优过程变得像是一个“随机” 查找的过程,这样 online 最优化求解即使采用 L1 正则化的方式, 也很难产生稀疏解。正因为 OGD 存在这样的问题,FTRL 才致力于在准确率不降低的前提下提高稀疏性。 上面的1-1的公式是GD 算法中权重参数 BP 优化的公式。下面给出另外一个定义: $$ {w}{t+1} = \mathop{\text{argmin}}{w} \left({g}_t \cdot {w} + \frac{1}{2\eta_t}||{w} – {w}_t||_2^2 \right) \tag{1.2} $$ 试着对上面的公式进行求导,首先是加法左边的式子对${w}$ 求导只会保留左边的 ${g}_t$ ,右边二范数求导变成 $\frac{1}{g_t}(w-w_t)$,公式的坐标为 0,所以得到以下公式 $$ {g}_t + \frac{1}{\eta_t}({w} – {w}_t) = 0 \;\;\implies\;\; {w} = {w}_t – \eta_t {g}_t \tag{1.3} $$ 在看上面的1.3公式其实本质是跟 1.1 是相同的。不过以前在学习GD 的时候,以简单的LR 模型来推导公式顺利推出 1.1 ,现在是为了学习后面的 FTRL 的铺垫了 1.2 ,由1.3 式来说明1.1 与 1.2 的等价。

FTRL

ftrl的优化就是在保证准确性的基础上又要保证稀疏性,现在我们看下它在这方面的优化

${g}_t$ 优化 — 保证精度

ftrl 在这块使用了累积梯度来优化,之前的公式是只用当前批次的数据计算出来的梯度来优化,线上实时的数据肯定会存在一定的抖动,那么会导致我们的模型随机向不同的方向去优化,万一回不来咋整。顾名思义,使用累积的梯度,就是借助于历史大量的数据保证参数更新的平稳,即使你来了一些异常的样本也不会影响模型的效果。所以的 1.2 公式中的 ${g}t$需要替换为${g}{1:t}$,这里的1:t 标识就是迭代到第 t 轮。这个方法验证了算法名 FTL –Follow the leader

稀疏优化 — 稀疏解

一提到稀疏解,第一想到的是 L1 稀疏解,那么在前面将 OGD 的时候由于计算精度的问题,即使你加上 L1 也不会得到稀疏解,那为什么 FTRL 就会得到稀疏解,FTRL 的公式中包含了 L1和L2 正则。 $$ {w}{t+1} = \mathop{\text{argmin}}{{w}}\left({g}{1:t} \cdot {w} + \frac12 \sum\limits{s=1}^t \sigma_s ||{w} – {w}_s||_2^2 + \lambda_1||{w}||_1 + \frac12 \lambda_2||{w}||_2^2\right) \tag{1.4} $$ 1.4 公式中就是给出了相应的 FTRL 更新的公式,乍一看也没有啥特别的,除了之前介绍的累积梯度,就是正则项了,我们自己都能想到,谷歌肯定也会想到,但是谷歌这么做也能达到之前描述的效果,那么这中间存在特别的地方。

上面的公式中的 $ \sigma_s$的定义 $ \sigma_s = \frac{1}{\eta_s} – \frac{1}{\eta_{s-1}}$,对其累积求和可以得到 $\sigma_{1:t} = \sum_{s=1}^t \sigma_s = \frac{1}{\eta_s}$

定理推导

首先将 1.4 公式中的二范数项拆开: $$ {w}{t+1} = \mathop{\text{argmin}}{{w}} \left{ \left({g}{1:t} – \sum\limits{s=1}^t\sigma_s{w}s \right) \cdot {w} + \lambda_1||{w}||_1 + \frac12 \left(\lambda_2 + \sum\limits{s=1}^t \sigma_s \right) \cdot ||{w}||2^2 + \frac12 \sum\limits{s=1}^t \sigma_s||{w}s||_2^2 \right} \tag{1.5} $$ 公式中的 w 才是变量,并且也是求导的对象,所有公式最右边的的变量 $\frac12 \sum\limits{s=1}^t \sigma_s||{w}_s||_2^2$ 与 w 没有关系,所以可以直接在优化的过程中直接忽略掉。

对于大括号里面第一个公式: $$ {z}t = {g}{1:t} – \sum\limits_{s=1}^t \sigma_s{w}s $$ 这样优化之后的公式就变为: $$ {w}{t+1} = \mathop{\text{argmin}}{{w}} \left{ {z}_t \cdot {w} + \lambda_1||{w}||_1 + \frac12 \left(\lambda_2 + \sum\limits{s=1}^t \sigma_s \right) \cdot ||{w}||2^2 \right} \tag{1.6} $$ 参考谷歌的wide&deep的实现,ftrl 的作用在 wide 侧,对输入的每一个稀疏特征做相应的优化,所以将 1.6 的公式拆分到对应的每一个特征上, $$ w{t+1,i} = \mathop{\text{argmin}}{w_i \in \mathbb{R}} \left{ z{t,i} \, w + \lambda_1 |w_i| + \frac12 \left(\lambda_2 + \sum\limits_{s=1}^t \sigma_s \right) \cdot w_i^2 \right} \tag{1.8} $$ 上面的公式中 $i$ 表示 第 i 个特征。上面的式子存在一个比较大的问题就是 第二项不可导

但是,你要去优化,就得可导啊,不然没办法走下一步了,所以有个新概念–次导数

看下维基百科上面的次导数示意:

在线学习--FTRL

上面的蓝色原始曲线在x0处是不可导,红色线就是给出的次导数。 $$ \partial |w_i^| = \begin{cases} \quad\quad{1} &\quad \text{if}\;\; w_i^ > 0 \[1ex] -1 < \phi < 1 & \quad \text{if}\;\; w_i^* = 0 \[1ex] \tag{1.9} \quad\;\;{-1} &\quad \text{if}\;\; w_i^* < 0 \end{cases} $$ 定义 $\phi \in \partial |w_i^*|$ 代表上式的次导数

那么公式 1.6 计算对 w 的导数可以得到: $$ z_{t,i} + \lambda_1 \phi + \left(\lambda_2 + \sum\limits_{s=1}^t \sigma_s\right)\cdot w_i = 0 \tag{1.10} $$ 接下来就是比较繁琐的对1.10 的公式进行彻底的分析,先说下结论,这个剖析的过程会跟稀疏解有关系。

1.10 的公式等于 0 ,但是这其中的正则小系数都是大于0,并且$ \sum_{s=1}^t \sigma_s $ 也是大于0 的,$w_i$ 是要求解的目标,还剩下两个参数。固定其中一个来做分析,感觉有点 EM 的味道。

就以 $z_{t,i}$的取值讨论:

  1. $|z_{t, i}| < \lambda_1$,那么 $w_i=0$,如果$w_i>0$那么对应的次导数就是 1 ,那么1.10 左边的式子肯定大于 0 ,同理 $w_i<0$ ,那么左边的式子小于 0

  2. $z_{t, i} > \lambda_1$ 那么 $\phi = -1 \implies w_i = -\frac{1}{\lambda_2 + \sum_{s=1}^t \sigma_s} (z_{t, i} – \lambda_1) < 0$ 分析的方式与 1 相同

  3. $z_{t, i} < \lambda_1$ 那么 $\phi = 1 \implies w_i = -\frac{1}{\lambda_2 + \sum_{s=1}^t \sigma_s} (z_{t, i} + \lambda_1) > 0$ 同上

最终得到的w更新迭代的公式 $$ w_{t+1,i} = \begin{cases} \qquad\qquad \large{0} & \text{if}\;\; |z_{t,i}| < \lambda_1 \[2ex] -\frac{1}{\lambda_2 + \sum_{s=1}^t\sigma_s} \left(z_{t,i} – \text{sgn}(z_{t,i})\cdot\lambda_1 \right) & \text{otherwise} \tag{1.11} \end{cases} $$

哈哈,看到这里稀疏解就出来了。L2 的加入并没有影响稀疏性,在公式中处于分母的位置,是w更加趋向于 0 ,看起来还是符合正则化的意思。

学习率

FTRL 采用的是 Per-Coordinate Learning Rate,即每个特征采用不同的学习率,这种方法考虑了训练样本本身在不同特征上分布的不均匀性。如果一个特征变化快,则对应的学习率也会下降得快,反之亦然。

FTRL 中第 t 轮 第 i 个特征的学习率: $$ \eta_{t, i} = \frac{\alpha}{\beta + \sqrt{\sum_{s=1}^t g_{s, i}^2}} \tag{1.12} $$ 可以得到 $$ \begin{align} \sum\limits_{s=1}^t \sigma_s &= (\frac{1}{\eta_t} – \frac{1}{\eta_{t-1}}) + (\frac{1}{\eta_{t-1}} – \frac{1}{\eta_{t-2}}) + \cdots + (\frac{1}{\eta_1} – \frac{1}{\eta_0}) \ &=\;\; \frac{1}{\eta_t} \;\;=\;\; \frac{\beta + \sqrt{\sum_{s=1}^tg_{s,i}^2}}{\alpha} \tag{1.13} \end{align} $$ 最后的迭代公式为: $$ w_{t+1,i} = \begin{cases} \qquad\qquad \large{0} & \quad\text{if}\;\; |z_{t,i}| < \lambda_1 \[2ex] -\left(\lambda_2 + \frac{\beta + \sqrt{\sum_{s=1}^t g_{s,i}^2}}{\alpha} \right)^{-1} \left(z_{t,i} – \text{sgn}(z_{t,i})\cdot\lambda_1 \right) & \quad \text{otherwise} \tag{1.14} \end{cases} $$

admin
版权声明:本站原创文章,由admin2021-09-06发表,共计4479字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)