FM论文地址：https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf
1、FM背景
在计算广告和推荐系统中，CTR预估(click-through rate)是非常重要的一个环节，判断一个商品的是否进行推荐需要根据CTR预估的点击率来进行。在进行CTR预估时，除了单特征外，往往要对特征进行组合。对于特征组合来说，业界现在通用的做法主要有两大类：FM系列与Tree系列。今天，我们就来讲讲FM算法。
2、one-hot编码带来的问题
FM(Factorization Machine)主要是为了解决数据稀疏的情况下，特征怎样组合的问题。已一个广告分类的问题为例，根据用户与广告位的一些特征，来预测用户是否会点击广告。数据如下：(本例来自美团技术团队分享的paper)
clicked是分类值，表明用户有没有点击该广告。1表示点击，0表示未点击。而country,day,ad_type则是对应的特征。对于这种categorical特征，一般都是进行one-hot编码处理。
将上面的数据进行one-hot编码以后，就变成了下面这样 ：
因为是categorical特征，所以经过one-hot编码以后，不可避免的样本的数据就变得很稀疏。举个非常简单的例子，假设淘宝或者京东上的item为100万，如果对item这个维度进行one-hot编码，光这一个维度数据的稀疏度就是百万分之一。由此可见，数据的稀疏性，是我们在实际应用场景中面临的一个非常常见的挑战与问题。
one-hot编码带来的另一个问题是特征空间变大。同样以上面淘宝上的item为例，将item进行one-hot编码以后，样本空间有一个categorical变为了百万维的数值特征，特征空间一下子暴增一百万。所以大厂动不动上亿维度，就是这么来的。
3、对特征进行组合
普通的线性模型，我们都是将各个特征独立考虑的，并没有考虑到特征与特征之间的相互关系。但实际上，大量的特征之间是有关联的。最简单的以电商为例，一般女性用户看化妆品服装之类的广告比较多，而男性更青睐各种球类装备。那很明显，女性这个特征与化妆品类服装类商品有很大的关联性，男性这个特征与球类装备的关联性更为密切。如果我们能将这些有关联的特征找出来，显然是很有意义的。
一般的线性模型为：
y = w o + ∑ i = 1 n w i x i y = w_o + \sum_{i=1}^n w_ix_i y=wo+i=1∑nwixi
从上面的式子很容易看出，一般的线性模型压根没有考虑特征间的关联。为了表述特征间的相关性，我们采用多项式模型。在多项式模型中，特征xi与xj的组合用 x i x j x_ix_j xixj表示。为了简单起见，我们讨论二阶多项式模型。具体的模型表达式如下：
y ( x ) : = w o + ∑ i = 1 n w i x i + ∑ i = 1 N ∑ j = i + 1 N w i j x i x j y(x) := w_o + \sum_{i=1}^n w_ix_i + \sum_{i=1}^N \sum_{j=i+1}^Nw_{ij}x_ix_j y(x):=wo+i=1∑nwixi+i=1∑Nj=i+1∑Nwijxixj
上式中，n表示样本的特征数量, x i x_i xi表示第i个特征。
与线性模型相比，FM的模型就多了后面特征组合的部分。
从上面的式子可以很容易看出，组合部分的特征相关参数共有 n ( n − 1 ) 2 \frac {n(n-1)} 2 2n(n−1)个。但是如第二部分所分析，在数据很稀疏的情况下，满足xi,xj都不为0的情况非常少，这样将导致 w i j w_{ij} wij无法通过训练得出。
因此，提出了隐向量的概念。 该模型具有更强的模型表达能力和泛化能力。
为了求出 w i j w_{ij} wij，我们对每一个特征分量 x i x_i xi引入辅助向量 V i = [ v i 1 , v i 2 , ⋯ , v i k ] V_i = [v_{i1}, v_{i2}, \cdots, v_{ik}] Vi=[vi1,vi2,⋯,vik]， 其中 k k k是个超参数，表示的是隐向量的长度。公式变为：
y ( x ) : = w o + ∑ i = 1 n w i x i + ∑ i = 1 N ∑ j = i + 1 N < v i , v j > x i x j y(x) := w_o + \sum_{i=1}^n w_ix_i + \sum_{i=1}^N \sum_{j=i+1}^N<v_i, v_j>x_ix_j y(x):=wo+i=1∑nwixi+i=1∑Nj=i+1∑N<vi,vj>xixj
模型参数包括：
w o ∈ R , W ∈ R n , V ∈ R n × k w_o \in R, W \in R^n, V \in R^{n\times k} wo∈R,W∈Rn,V∈Rn×k
< ⋅ , ⋅ > <\cdot,\cdot> <⋅,⋅>是两个size为k的向量的点积。
< v i , v j > : = ∑ f = 1 K v i f ⋅ v j f <v_i, v_j> := \sum_{f=1}^K v_{if} \cdot v_{jf} <vi,vj>:=∑f=1Kvif⋅vjf
上式的计算复杂度为 O ( k n 2 ) O(kn^2) O(kn2)，通过公式推导，可以简化到 O ( k n ) O(kn) O(kn)的复杂度。公式推导如下：
∑ i = 1 N ∑ j = i + 1 N < v i , v j > x i x j = 1 2 ( ∑ i = 1 N ∑ j = 1 N < v i , v j > x i x j − ∑ i = 1 N < v i , v i > x i x i ) = 1 2 ( ∑ i = 1 N ∑ j = 1 N ∑ f = 1 K v i f v j f x i x j − ∑ i = 1 N ∑ f = 1 K v i f v i f x i x j ) = 1 2 ∑ f = 1 K ( ∑ i = 1 N ∑ j = 1 N v i f v j f x i x j − ∑ i = 1 N v i f v i f x i x j ) = 1 2 ∑ f = 1 K ( ∑ i = 1 N v i f x i ) 2 − ∑ i = 1 N v i f 2 x i 2 ) \begin{aligned} \sum_{i=1}^N \sum_{j=i+1}^N<v_i, v_j>x_ix_j &= \frac 1 2 (\sum_{i=1}^N \sum_{j=1}^N<v_i, v_j>x_ix_j - \sum_{i=1}^N<v_i, v_i>x_ix_i)\\ &= \frac 1 2 (\sum_{i=1}^N \sum_{j=1}^N \sum_{f=1}^K v_{if} v_{jf} x_i x_j - \sum_{i=1}^N \sum_{f=1}^K v_{if} v_{if} x_i x_j)\\ &= \frac 1 2 \sum_{f=1}^K (\sum_{i=1}^N \sum_{j=1}^N v_{if} v_{jf} x_i x_j - \sum_{i=1}^N v_{if} v_{if} x_i x_j)\\ &= \frac 1 2 \sum_{f=1}^K (\sum_{i=1}^N v_{if}x_i)^2 - \sum_{i=1}^N v_{if}^2 x_i^2) \end{aligned} i=1∑Nj=i+1∑N<vi,vj>xixj=21(i=1∑Nj=1∑N<vi,vj>xixj−i=1∑N<vi,vi>xixi)=21(i=1∑Nj=1∑Nf=1∑Kvifvjfxixj−i=1∑Nf=1∑Kvifvifxixj)=21f=1∑K(i=1∑Nj=1∑Nvifvjfxixj−i=1∑Nvifvifxixj)=21f=1∑K(i=1∑Nvifxi)2−i=1∑Nvif2xi2)
计算复杂度降到了 O ( k n ) O(kn) O(kn)。
采用随机梯度法求导可得：
∂ ∂ θ y ^ ( x ) = { 1 , i f θ i s w o x i , i f θ i s w i x i ∑ j = 1 N v j f x j − v i f x i 2 , i f θ i s v i f \frac {\partial} {\partial \theta} {\hat y(x)} = \left\{ \begin{aligned} 1, && if \; \theta \; is \; w_o \\ x_i, && if \; \theta \; is \; w_i \\ x_i \sum_{j=1}^N v_{jf}x_j - v_{if}x_i^2, && if \; \theta \; is \; v_{if} \end{aligned} \right. ∂θ∂y^(x)=⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧1,xi,xij=1∑Nvjfxj−vifxi2,ifθiswoifθiswiifθisvif
当然，对于推荐系统ctr预估问题来说，由于属于二分类问题，需要将输出值 y ( x ) y(x) y(x)作用于Sigmoid激活函数。
参考文章：
- https://www.jianshu.com/p/152ae633fb00