在线学习–FTRL

2,142次阅读

共计 4479 个字符，预计需要花费 12 分钟才能阅读完成。

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 在这块使用了累积梯度来优化，之前的公式是只用当前批次的数据计算出来的梯度来优化，线上实时的数据肯定会存在一定的抖动，那么会导致我们的模型随机向不同的方向去优化，万一回不来咋整。顾名思义，使用累积的梯度，就是借助于历史大量的数据保证参数更新的平稳，即使你来了一些异常的样本也不会影响模型的效果。所以的 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}$ 的取值讨论：

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

正文完

请博主喝杯咖啡吧！