摘要：

本文将要介绍一个在推荐、CTR中很常见的模型，FM（Factorization Machines）。

前言

我们首先回忆一下在推荐或者CTR预估的场景下我们经常用的模型是LR。具体来说我们熟悉的LR即如(0)式。
y^=w1x1+w2x2+...wnxn=∑ni=1wixi(0)$\begin{array}{}\text{(0)}& \hat{y}=w_1{x}_1+w_2{x}_2+...w_n{x}_n=\sum _{i=1}^n{w}_i{x}_i\end{array}$
接触过CTR或者推荐场景的可能很清楚，在这些场景下，我们通常会做一些交叉特征(cross feature)来增强LR的非线性以加强线性模型的表达能力。这种做法可以认为是在特征工程上下功夫。

而我们能否解放特征工程。从模型上下功夫来解决特征交叉的问题呢？
其实可以，比如说，我对(0)进行一点点修改，如(1)式子。
y^=∑ni=1wixi+∑ni=1∑nj=i+1wijxixj(1)$\begin{array}{}\text{(1)}& \hat{y}=\sum _{i=1}^n{w}_i{x}_i+\sum _{i=1}^n\sum _{j=i+1}^n{w}_{ij}{x}_i{x}_j\end{array}$
非常的直观，我们直接在线性模型的基础上增加多各个特征的乘积项。其表达的含义就是两个特征之间做交叉的意思。(1)式增加了n(n+1)2$\frac{n(n+1)}{2}$个参数。通常来说，会用到这种模型下的特征维度n$n$都非常的大。所以这种如此暴力的方法（从式子(0)到式子(1)的变化）存在一定优化空间。

其实大量参数并非这种方法的最大问题，最大的问题在于由于推荐和CTR这两种场景下的特征非常的稀疏(sparse data)，这会导致有大量的权重wij$w_{ij}$将得不到训练。可以直观上理解：当且仅当xixj$x_i{x}_j$同时不为0时，权重wij$w_{ij}$在进行梯度下降时才会更新。否则每次梯度下降会保持不变。

为了解决这两个问题，第一个缩减参数的规模，第二个让交叉项的权重能够更好的学习，Steffen Rendle在提出了FM。

FM模型

上面提到FM是为了解决直接采用用多项式即式子(1)带来的几个问题所提出的模型。
那么FM到底是如何解决的呢？这里其实可以从多个角度来理解。这里采用一种个人比较理解的角度来说明。

假设我们给每个特征xi$x_i$学习一个长度为k$k$的向量表达vi$v_i$。即向量vi$v_i$为特征xi$x_i$的k$k$维表达。
那么我们在做特征组合的时候，比如组合xi$x_i$与xj$x_j$时，我们可以把学习的权重转化为学习vi$v_i$和vj$v_j$的向量点积的结果，⟨vi,vj⟩$⟨v_i,v_j⟩$，也就是说(1)式改为：
y^=∑ni=1wixi+∑ni=1∑nj=i+1⟨vi,vj⟩xixj(2)$\begin{array}{}\text{(2)}& \hat{y}=\sum _{i=1}^n{w}_i{x}_i+\sum _{i=1}^n\sum _{j=i+1}^n⟨v_i,v_j⟩x_i{x}_j\end{array}$

其中：⟨vi,vj⟩=∑kf=1vi,f⋅vj,f$⟨v_i,v_j⟩=\sum _{f=1}^k{v}_{i,f}\cdot v_{j,f}$

我们这样做之后能够改善上面所提到部分权重得到不学习的问题。
这里我举一个例子。

---

比如我们有一个训练集，训练集中只有三个特征。其中一条样本如下
x1=1,x2=0,x3=1()$\begin{array}{}\text{()}& x_1=1,x_2=0,x_3=1\end{array}$
这个时候，我们如果采用式子(1)来学习时，我们需要学习其中的三个参数w12$w_{12}$、w13$w_{13}$、w23$w_{23}$。
由于：仅有x1x3=1$x_1{x}_3=1$不为0，故仅有w13$w_{13}$这个权重在梯度下降时得到了学习。那么在进行预测的时候，我们就利用了根本没有经过学习的、非常不准确的参数w12$w_{12}$、w23$w_{23}$。

而如果我们采用式子(2)来学习，我们有如下（方便起见，向量长度为k=1$k=1$）

虽然我们只有x1x3=1$x_1{x}_3=1$不为0,但是在梯度下降的时候，v1,v3$v_1,v_3$都得到了学习。那么这个时候，我们在预测的时候，尽管v2$v_2$没有得到学习。但是由于⟨v1,v2⟩$⟨v_1,v_2⟩$和⟨v2,v3⟩$⟨v_2,v_3⟩$
中包含了我们学习过的v1,v3$v_1,v_3$。所以从模型最终的效果上来看，尽管部分交叉特征从来出现过，但是由于其中包含有已经学习过的权重，所以还是能够使得这些交叉特征的权重是一个相对合理的值，而不是一个从未经过训练的值。

---

上面的权重的学习得到了改善，另外在进行预测时候的复杂度，其实也从O(n2)$O(n^2)$降到了线性O(nk)$O(nk)$。
整个FM的复杂度其实来源于交叉特征部分。直观上看复杂度为O(n2k)$O(n^{2}k)$，但是我们其实可以做一个简单的数学推导：
（这个推导直接摘论文里面的了，敲公式太累了- -!!!)

从式子(5)中可以看到，最外层的求和要计算O(k)次$O(k)次$，里面一共需要计算O(n)$O(n)$次。所以总的复杂度为O(nk)$O(nk)$。所以整个复杂度变成了线性。

关于FM的训练

那么，我们对FM模型有了一定的认识之后，我们下一步需要考虑的就是如何进行训练，或者说如何求出上面所涉及到的一些参数。这里我们把式子(5)的推导结果带入式子(2)可以得到：

y^=∑ni=1wixi+12∑kf=1{(∑ni=1vi,fxi)2−∑ni=1v2i,fx2i}(3)$\begin{array}{}\text{(3)}& \hat{y}=\sum _{i=1}^n{w}_i{x}_i+\frac{1}{2}\sum _{f=1}^k\{(\sum _{i=1}^n{v}_{i,f}{x}_i{)}^2-\sum _{i=1}^n{v}_{i,f}^2{x}_i^2\}\end{array}$

对于分类任务，一般我们可以选择logloss作为我们的损失函数。那么对于logloss我们有(对于第m$m$条样本）：
L(y(m),y(m)^)=−{y(m)Ln(p(m))+(1−y(m))Ln(1−p(m))}(6)$\begin{array}{}\text{(6)}& L(y^{(m)},\widehat{y^{(m)}})=-\{y^{(m)}Ln(p^{(m)})+(1-y^{(m)})Ln(1-p^{(m)})\}\end{array}$
其中：p(m)=11+ey(m)^$p^{(m)}=\frac{1}{1+e^{\widehat{y^{(m)}}}}$

把(3)式中的所有参数统一记为θ，然后$\theta ，然后$(6)式对θ$\theta$求导有：
∂L(y(m),y(m)^)∂θ=(y(m)−p(m))∂y(m)^∂θ(7)$\begin{array}{}\text{(7)}& \frac{\mathrm{\partial }L(y^{(m)},\widehat{y^{(m)}})}{\mathrm{\partial }\theta }=(y^{(m)}-p^{(m)})\frac{\mathrm{\partial }\widehat{y^{(m)}}}{\mathrm{\partial }\theta }\end{array}$

最后对于∂y(m)^∂θ=⎧⎩⎨⎪⎪1xixi∑nj=1vj,fxj−vi,fx2iθ=w0θ=wiθ=vi,f(8)$\begin{array}{}\text{(8)}& \frac{\mathrm{\partial }\widehat{y^{(m)}}}{\mathrm{\partial }\theta }=\{\begin{array}{ll}1& \theta \text{=}{w}_0\\ x_i& \theta \text{=}{w}_i\\ x_i\sum _{j=1}^n{v}_{j,f}{x}_j-v_{i,f}{x}_i^2& \theta \text{=}{v}_{i,f}\end{array}\end{array}$

有了每个参数的梯度之后，就可以利用SGD来对各个参数进行训练了。
可以看到，对于训练过程其复杂度也是线性的O(nk)$O(nk)$。

FM与多项式的SVM对比

在FM的论文里有FM和SVM的一个简单的对比，其实总结起来。主要想表达就是，当SVM的核函数选择多项式核时即d=2$d=2$的情况，SVM为下式：

可以看到这个式子大体上就和式子(1)类似。所以对比FM和多项式核下的SVM其实就是文中一开始讨论的内容。

总结

到这里，我们可以稍微整理一下前面的内容。其实我们无非做了以下几点事情。
首先，我们阐述通过做特征工程来使得LR非线性表达能力增强的想法。后面，我们希望通过模型本身来做特征的交叉，阐述了直接利用二阶多项式的方法所带来的问题。最后，我们利用FM来解决上述所带来的一些问题。

所以FM其实很好的解决了两个问题
第一，将需要交叉特征部分的参数从n(n+1)2$\frac{n(n+1)}{2}$个降到了nk$nk$个。
第二，改善了交叉特征部分的权重的学习。

建议参考文章：美团技术点评-FFM