FTRL 是 Google 提出的一种优化算法。常规的优化方法例如梯度下降、牛顿法等属于批处理算法，每次更新需要对 batch 内的训练样本重新训练一遍。在线学习场景下，我们希望模型迭代速度越快越好。例如用户发生一次点击行为后，模型就能快速进行调整。FTRL 在这个场景中能求解出稀疏化的模型。

基础知识

• L1 正则比 L2 正则可以产生更稀疏的解。
• 次梯度：对于 L1 正则在 $x=0$ 处不可导的情况，使用次梯度下降来解决。次梯度对应一个集合 ${v: v(x-x_t) \le f(x)-f(x_t)}$，集合中的任意一个元素都能被当成次梯度。以 L1 正则为例，非零处梯度是 1 或 -1，所以 $x=0$ 处的次梯度可以取 $[-1, 1]$ 之内任意一个值。

FTL

FTL(Follow The Leader) 算法：每次找到让之前所有损失函数之和最小的参数。

$$W=argmin_W \sum^t_{i=1}F_i(W)$$

FTRL 中的 R 是 Regularized，可以很容易猜出来在 FTL 的基础上加正则项。

$$W=argmin_W \sum^t_{i=1}F_i(W) + R(W)$$

代理函数

FTRL 的损失函数直接很难求解，一般需要引入一个代理损失函数 $h(w)$。代理损失函数常选择比较容易求解析解以及求出来的解和优化原函数得到的解差距不能太大。

我们通过两个解之间的距离 Regret 来衡量效果：

$$
\begin{array}{c}{w_{t}=\operatorname{argmin}{w} h{t-1}(w)} \ {\text {Regret}{t}=\sum{t=1}^{T} f_{t}\left(w_{t}\right)-\sum_{t=1}^{T} f_{t}\left(w^{*}\right)}\end{array}
$$

其中 $w^{*}$ 是直接优化 FTRL 算法得到的参数。当距离满足 $\lim {t \rightarrow \infty} \frac{\text {Regret}{t}}{t}=0$，损失函数认为是有效的。其物理意义是，随着训练样本的增加，两个优化目标优化出来的参数效果越接近。

推导过程

参数 $w_{t+1}$ 的迭代公式：

$${w_{t+1}=argmin_w{ g_{(1:t)}w + \frac{1}{2} \sum_{s=1}^t \sigma_s \lVert w - w_s \rVert ^2 + \lambda_1 \lVert W \rVert_1 + \frac{1}{2} \lambda_2 \lVert W \rVert^2 }}$$

其中 $g_{(1:t)}=\sum^{t}{s=1}g_s$，$g_s$ 为 $f(w_s)$ 的次梯度。参数 $\sum^t{s=1}\sigma_s=\frac{1}{\eta _t}$，学习率 $\eta _t = \frac{1}{\sqrt{t}}$，随着迭代轮数增加而减少。

展开迭代公式

$${F(w)= g_{(1:t)}w + \frac{1}{2} \sum_{s=1}^t \sigma_s \lVert w - w_s \rVert ^2 + \lambda_1 \lVert W \rVert_1 + \frac{1}{2} \lambda_2 \lVert W \rVert^2 }$$

$${F(w)= g_{(1:t)}w + \frac{1}{2} \sum_{s=1}^t \sigma_s ( w^Tw - 2w^Tw_s + w_s^Tw_s) + \lambda_1 \lVert W \rVert_1 + \frac{1}{2} \lambda_2 \lVert W \rVert^2 }$$

$${F(w)= (g_{(1:t)} - \sum_{s=1}^t \sigma_s w_s)w + \frac{1}{2} (\sum_{s=1}^t \sigma_s + \lambda_2) w^Tw + \lambda_1 \lVert W \rVert_1 + const }$$

$${F(w)= z_t^Tw + \frac{1}{2} (\frac{1}{\eta _t} + \lambda_2) w^Tw + \lambda_1 \lVert W \rVert_1 + const }$$

其中 ${z_{t-1}=g^{(1:t-1)} - \sum_{s=1}^{t-1} \sigma_s w_s}$。

对 $F(w)$ 求偏导得到：

$${z_t + (\frac{1}{\eta _t} + \lambda_2) w + \lambda_1 \partial \lvert W \rvert = 0}$$

$w$ 和 $z$ 异号时，等式成立。

根据基础知识里面提到的对于 L1 正则利用偏导数代替无法求解的情况，得到：

$$
\partial|W|=\left{\begin{array}{ll}{0,} & {\text { if }-1<w<1} \ {1,} & {\text { if } w>1} \ {-1,} & {\text { if } w<-1}\end{array}\right.
$$

1. 当 ${ z_t > \lambda_1}$ 时，${w_i < 0}$ , ${w_i = \frac{- z_t + \lambda_1 }{\frac{1}{\eta _t} + \lambda_2 }}$
2. 当 ${ z_t < - \lambda_1}$ 时，${w_i > 0}$ , ${w_i = \frac{- z_t - \lambda_1 }{\frac{1}{\eta _t} + \lambda_2 }}$
3. 当 ${ \lvert z_t \rvert < \lambda_1}$ 时，当且仅当 ${w_i=0}$ 成立

因此可得：

$$
w_{i}=\left{\begin{array}{ll}{0,} & {\text { if }\left|z_{i}\right| \leq \lambda_{1}} \ {\frac{-\left(z_{i}-\text sgn(z_i) \lambda_{1}\right)}{\eta_{t}+\lambda_{2}},} & {\text { if others }}\end{array}\right.
$$

FTRL 和 SGD 的关系

将 SGD 的迭代公式写成：${W^{t+1}=W^t - \eta _tg_t}$

FTRL 迭代公式为：${W^{t+1}=argmin_w{ G^{(1:t)}W + \lambda_1 \lVert W \rVert_1 +\lambda_2 \frac{1}{2} \lVert W \rVert }}$

代入 ${\sum^t_{s=1}\sigma _s= \frac{1}{\eta t}}$ 到上面的公式中，得到 ${W^{t+1}=argmin_w{ \sum_t^{s=1}g_sW + \frac{1}{2} \sum^t{s=1}\sigma _s\lVert W - W_s \rVert_2^2 }}$

求偏导得到 ${\frac{\partial f(w)}{\partial w} = \sum^t_{s=1}g_s + \sum^t_{s=1}\sigma _s( W - W_s )}$

令偏导等于 0 ：${\sum^t_{s=1}g_s + \sum^t_{s=1}\sigma _s( W^{t+1} - W_s ) = 0}$

化简得到：${(\sum^t_{s=1}\sigma s) W^{t+1} = \sum^t{s=1}\sigma s W^{s} - \sum^t{s=1}g_s}$

代入 $\sigma$：${\frac{1}{\eta t} W^{t+1} = \sum^t{s=1}\sigma s W^{s} - \sum^t{s=1}g_s}$

根据上一个公式得出上一轮的迭代公式：${\frac{1}{\eta {t-1}} W^{t} = \sum^{t-1}{s=1}\sigma s W^{s} - \sum^{t-1}{s=1}g_s}$

两式相减：${\frac{1}{\eta _t} W^{t+1} - \frac{1}{\eta _{t-1}} W^{t} = (\frac{1}{\eta _t} - \frac{1}{\eta _{t-1}}) W_t - g_t}$

最终化简得到和 SGD 迭代公式相同的公式：${W_{t+1} = W_t - \eta_t g_t}$

FTRL 工程化伪代码

引用自论文 Ad Click Prediction: a View from the Trenches

下面的伪代码中学习率和前面公式推导时使用的一些不一样： $\eta_{t_{i}}=\frac{\alpha}{\beta+\sqrt{\sum_{s=1}^{t} g_{s_{i}}^{2}}}$。Facebook 在 GBDT + LR 的论文中研究过不同的学习率影响，具体可以参看博文 Practical Lessons from Predicting Clicks on Ads at Facebook(gbdt + lr) | 算法花园。

例：FM 使用 FTRL 优化

FM 是工业界常用的机器学习算法，在之前博文 (FM)Factorization Machines 中有简单的介绍。内部的 FTRL+FM 代码没有开源，所以也不好分析。从 FM+FTRL算法原理以及工程化实现 - 知乎 中找了一张 FTRL+FM 的伪代码图片。

Reference

• Online Learning算法理论与实践 - 美团技术团队
• FTRL公式推导 - 知乎
• 每周一文】Ad Click Prediction: a View from the Trenches(2013)_机器学习,CTR,online_fangqingan_java的专栏-CSDN博客

Factorization Machines(FM) 由日本 Osaka University 的 Steffen Rendle [1] 在 2010 年提出,是一种常用的因子机模型。

FM

假设现在有一个电影评分的任务，给定如下如所示的特征向量 x（包括用户名、当前在看的电影、已经打分的电影、时间特征、之前看的电影），预测用户对当前观看电影的评分。

作者在线性回归模型的基础上，添加交叉项部分，用来自动组合二阶特征。

$$\hat y(x):= w_0 + \sum_{i=1}^{n} w_ix_i + \sum_{i=1}^n \sum_{j=i+1}^n \left \langle v_i,v_j \right \rangle x_ix_j$$

其中交叉特征的权重由两个向量的点积得到，可以解决没有在模型中出现的特征组合权重问题，以及减少参数数量。

$$W_{i,j}=\left \langle v_i,v_j \right \rangle = \sum_{f=1}^kv_{i,f} \cdot v_{j,f}$$

通过下面的方法来化简交叉项权重计算，算法复杂度降到线性。

$$\sum_{i=1}^n \sum_{j=i+1}^n \left \langle v_i,v_j \right \rangle x_iy_i = \frac{1}{2}\sum^k_{f=1} \left( \left(\sum_{i=1}^nv_{i,f}x_i \right)^2 - \sum^n_{i=1} v^2_{i,f} x_i^2 \right)$$

对交叉项部分的求导：

$$\frac{\partial}{\partial \theta} \hat y \left( x \right) =
\begin{cases}
1, & \text{ if $\theta$ is $w_0$} \
x_i, & \text{ if $\theta$ is ${w_i}$} \
x_i\sum^n_{j=1} v_{j,f}x_j - v_{i,f}x_i^2, &\text{if $\theta$ is ${v_{i,f}}$}
\end{cases}$$

其中 ${\sum^n_{j=1} v_{j,f}x_j}$ 与 ${x_i}$ 无关，可以在计算导数前预处理出来。

FM vs SVM

对于经典的特征组合问题，不难想到使用 SVM 求解。Steffen 在论文中也多次将 FM 和 SVM 做对比。

在考虑 SVM 的 Polynomial kernel 为 ${K(\mathbf{x}, \mathbf{z}) :=(\langle\mathbf{x}, \mathbf{z}\rangle+ 1)^{2}}$，映射
$$
\begin{array}{l}{\phi(\mathbf{x}) :=\left(1, \sqrt{2} x_{1}, \ldots, \sqrt{2} x_{n}, x_{1}^{2}, \ldots, x_{n}^{2}\right.} {\sqrt{2} x_{1} x_{2}, \ldots, \sqrt{2} x_{1} x_{n}, \sqrt{2} x_{2} x_{3}, \ldots, \sqrt{2} x_{n-1} x_{n} )}\end{array}
$$

SVM 的公式可以转化为：

$$
\begin{aligned} \hat{y}(\mathbf{x})=w_{0}+\sqrt{2} \sum_{i=1}^{n} w_{i} x_{i}+\sum_{i=1}^{n} w_{i, i}^{(2)} x_{i}^{2} &+\sqrt{2} \sum_{i=1}^{n} \sum_{j=i+1}^{n} w_{i, j}^{(2)} x_{i} x_{j} \end{aligned}
$$

论文中提到一句上面的公式中 ${w_{i}}$ 和 ${w_{i,i}}$ 表达能力类似，我猜这也是为什么 FM 中没有自身交叉项的原因吧。

FM 相比于 SVM 有下面三个特点：

1. SVM 中虽然也有特征交叉项，但是只能在样本中含有相对应的特征交叉数据时才能学习。但是 FM 能在数据稀疏的时候学习到交叉项的参数。
2. SVM 问题无法直接求解，常用的方法是根据拉格朗日对偶性将原始问题转化为对偶问题。
3. 在使用模型预测时，SVM 依赖部分训练数据（支持向量），FM 模型则没有这种依赖。

Rank

FM 用来做回归和分类都很好理解，简单写一下如何应用到排序任务中。以 pairwise 为例。假设排序结果有两个文档 ${x_i}$ 和 ${x_j}$，显然用户点击文档有先后顺序，如果先点击 ${x_i}$，记 label ${y_{ij}=1}$，反之点击 ${x_j}$，label ${y_{ij}=0}$。模型需要去预测 ${\hat y_{ij} = sigmoid(\hat y_i - \hat y_j)}$。

参考逻辑回归，用最大似然对参数进行估计，得到损失函数为 ${L=\log(1+\exp(-(\hat y(x_i)-\hat y(x_j))}$。优化过程和前面提到类似。

NFM

NFM 和 AFM 两篇论文是同一个作者写的，所以文章的结构很相近。

FM 模型由于复杂度问题，一般只使用特征二阶交叉的形式，缺少对 higher-order 以及 non-liner 特征的交叉能力。NFM 尝试通过引入 NN 来解决这个问题。

NFM 的结构如下：第一项和第二项是线性回归，第三项是神经网络。神经网络中利用 FM 模型的二阶特征交叉结果做为输入，学习数据之间的高阶特征。与直接使用高阶 FM 模型相比，可以降低模型的训练复杂度，加快训练速度。

$$
\hat{y}{N F M}(\mathbf{x})=w{0}+\sum_{i=1}^{n} w_{i} x_{i}+f(\mathbf{x})
$$

NFM 的神经网络部分包含 4 层，分别是 Embedding Layer、Bi-Interaction Layer、Hidden Layers、Prediction Score。

• Embedding Layer 层对输入的稀疏数据进行 Embedding 操作。最常见的 Embedding 操作是在一张权值表中进行 lookup ，论文中作者强调他们这一步会将 Input Feture Vector 中的值与 Embedding 向量相乘。
• Bi-Interaction Layer 层是这篇论文的创新，对 embedding 之后的特征两两之间做 element-wise product，并将结果相加得到一个 k 维（Embeding 大小）向量。这一步相当于对特征的二阶交叉，与 FM 类似，这个公式也能进行化简：

$$
f_{B I}\left(\mathcal{V}{x}\right)=\sum{i=1}^{n} \sum_{j=i+1}^{n} x_{i} \mathbf{v}{i} \odot x{j} \mathbf{v}{j} =\frac{1}{2}\left[\left(\sum{i=1}^{n} x_{i} \mathbf{v}{i}\right)^{2}-\sum{i=1}^{n}\left(x_{i} \mathbf{v}_{i}\right)^{2}\right]
$$

• Hidden Layers 层利用常规的 DNN 学习高阶特征交叉
• Prdiction Layer 层输出最终的结果：
  $$
  \begin{aligned} \hat{y}{N F M}(\mathbf{x}) &=w{0}+\sum_{i=1}^{n} w_{i} x_{i} +\mathbf{h}^{T} \sigma_{L}\left(\mathbf{W}{L}\left(\ldots \sigma{1}\left(\mathbf{W}{1} f{B I}\left(\mathcal{V}{x}\right)+\mathbf{b}{1}\right) \ldots\right)+\mathbf{b}_{L}\right) \end{aligned}
  $$

实验结果：

AFM

AFM(Attentional Factorization Machine), 在 FM 的基础上将 Attention 机制引入到交叉项部分，用来区分不同特征组合的权重。

$$
\hat{y}{A F M}(\mathbf{x})=w{0}+\sum_{i=1}^{n} w_{i} x_{i}+\mathbf{p}^{T} \sum_{i=1}^{n} \sum_{j=i+1}^{n} a_{i j}\left(\mathbf{v}{i} \odot \mathbf{v}{j}\right) x_{i} x_{j}
$$

单独看上面公式中的第三项结构：

• Embedding Layer 与 NFM 里面的作用一样，转化特征。
• Pair-wise Interaction Layer 是将特征两两交叉，如果对这一步的结果求和就是 FM 中的交叉项。
• Attention 机制在 Attention-based Pooling 层引入。将 Pair-wise Interaction Layer 中的结果输入到 Attention Net 中，得到特征组合的 score ${a_{i j}^{\prime} }$，然后利用 softmax 得到权重矩阵 ${a_{ij}}$。
  $$
  \begin{aligned} a_{i j}^{\prime} &=\mathbf{h}^{T} \operatorname{Re} L U\left(\mathbf{W}\left(\mathbf{v}{i} \odot \mathbf{v}{j}\right) x_{i} x_{j}+\mathbf{b}\right) \ a_{i j} &=\frac{\exp \left(a_{i j}^{\prime}\right)}{\sum_{(i, j) \in \mathcal{R}{x}} \exp \left(a{i j}^{\prime}\right)} \end{aligned}
  $$
• 最后将 Pair-wise Interaction Layer 中的二阶交叉结果和权重矩阵对应相乘求和得到 AFM 的交叉项。

和前一节的实验结果对比，AFM 效果比 NFM 要差一些。这大概就能说明为什么论文中提到 NFM，但是最后没有把 NFM 的结果贴出来，实在是机智。又回到，发论文是需要方法有创新，还是一味追求 state-of-the-art。

参考资料

• 深入浅出Factorization Machines系列 | Kubi Code’Blog
• FM模型在LTR类问题中的应用 - 知乎