FM因子分解机系列简介

简要介绍一下FM因子分解机及其衍生出的一系列模型

包括但不限于FM（factorization machine）、域感知因子分解机FFM（field-aware factorization machine）、域加权因子分解机（Field-weighted factorization machine）、MVM（Multi-view machine）、HFM（holographic factorization machine）。

在信息流推荐、搜索广告推荐等场景下需要对用户的请求选择合适的广告进行展示，CPC收费模式下媒体平台按点击数收费，媒体平台推荐给用户感兴趣的广告要比推荐一条令用户不感兴趣或感到厌烦的广告获得的点击更多收益更大，因此优化点击率预估模型非常关键。每一条训练数据都是一条向量$\mathbf x$，每条训练数据有$n$个特征，其中某个特征记为$x_{i}$，点击率预估模型旨在寻找一个合适的函数$f(x)$，对于每一个用户-广告pair预测该用户对该广告的点击率，并且返回点击率预估值最高的一个用户-广告pair请求以展示到用户界面。

【1】逻辑回归模型（LR）

LR模型：

$$f(x)=w_{0}+\sum_{i=1}^{n}w_{i}x_{i}$$

LR模型是一个线性模型，每个特征变量$x_{i}$都有一个独立的权重$w_{i}$，所有特征的加权组合再加上偏置$w_{0}$就得到了最后的输出，模型复杂度是$O(n)$。

LR的优点是线性模型，建模简单，模型复杂度低，在大规模稀疏数据下容易训练。但是缺点也显而易见，线性模型无法学习到高维的组合特征。比如点击率预估场景下，$x_{1}$表示的是性别、$x_{2}$表示的是广告id，如何不做特征交叉，对于所有的性别为女的用户推送的广告都是一样的，但是如果做了特征交叉（比如这里的性别与广告id交叉），那么就能学习到女性对某一个品牌服饰广告的权重(兴趣)，增强模型的个性化。

特征交叉好是好，但是会带来一个麻烦的问题就是维度爆炸，假设原始有10w维的特征，在特征交叉之后特征维度变成了100亿，如此巨大的特征空间对系统内存、通信、计算都有非常大的压力难以训练，如果不对所有的特征交叉进行建模，只对其中部分特征交叉建模是否可行？答案是肯定的，并且业界对此有个专有名词就是特征工程，在LR时代，特征工程最容易提高推荐效果，但是特征交叉的尝试需要试错成本，并且随着特征交叉达到了一定上限之后，试错成本也随着增大，投入产出比愈来愈低。

既然特征交叉这么有用，人工交叉又愈来愈难，有没有办法能在不过分增大参数空间的前提下让模型自动的学习特征交叉权重？（后面可以看到因子分解机系列模型可以比较有效的解决这个问题）

【2】Poly-2

Poly-2模型相比于LR，多了一个二维的特征穷举交叉项，由此模型可以自动学习每一个特征交叉的权重

$$f(x)=w_{0}+\sum_{i=1}^{n}w_{i}x_{i} +\sum_{i=1}^{n}\sum_{j=1}^{n}w_{ij}x_{i}x_{j}$$

但是该模型存在致命的缺点：

1. 数据稀疏：在稀疏数据中，一个$x_{i}$已经是很小概率了，而$x_{i}$和$x_{j}$同时出现的概率更是微乎其微，为每对特征交叉拟合一个独立参数难以收敛。
2. 参数空间大：参数空间为$O(n^{2})$对内存和机器资源和性能要求太高，在实际业务中无法使用。

【3】因子分解机模型（FM）

对于Poly-2中的特征交叉部分，可以看做是一个$n*n$的矩阵，我们可以借用矩阵论中的矩阵分解法将矩阵分解为两个向量的外积。因此模型的复杂度就随着下降了。因子分解机就是借助这一方法对特征交叉矩阵进行分解，从而得到一个能有效降维版本的模型，使得模型参数空间减小，模型训练变得可行。FM因子分解机最早由Steffen Rendle提出，该模型公式如下：

$$f(x)=w_{0}+\sum_{i=1}^{n}w_{i}x_{i} +\sum_{i=1}^{n}\sum_{j=i+1}^{n}<\mathbf v_{i},\mathbf v_{j}>x_{i}x_{j}$$

其中：

$$<\mathbf v_{i},\mathbf v_{j}>$$

表示的是向量$\mathbf v_{i}$ 和向量 $\mathbf v_{j}$ 的内积，如果我们直接第式子中的第三项部分进行计算，复杂度是$O(kn^{2})$，简单的对式子进行化简，我们可以得到复杂度更低的计算式$O(kn)$：

$$\begin{eqnarray} \sum_{i=1}^{n}\sum_{j=i+1}^{n}<\mathbf v_{i},\mathbf v_{j}>x_{i}x_{j} &=&\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}<\mathbf v_{i},\mathbf v_{j}>x_{i}x_{j} - \frac{1}{2}\sum_{i=1}^{n}<\mathbf v_{i},\mathbf v_{i}>x_{i}x_{i}\\ &=&\frac{1}{2} \left( \sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{f=1}^{k}v_{i,f} \cdot v_{j,f} \cdot x_{i} \cdot x_{j} -\sum_{i=1}^{n}\sum_{f=1}^{k}v_{i,f} \cdot v_{i,f} \cdot x_{i} \cdot x_{i}\right) \\ &=&\frac{1}{2} \left( \left( \sum_{i=1}^{n} v_{i,f} \cdot x_{i} \right) \left( \sum_{j=1}^{n} v_{j,f} \cdot x_{j} \right) - \sum_{i=1}^{n} v_{i,f}^{2} \cdot x_{i}^{2} \right) \\ &=&\frac{1}{2} \left( \left( \sum_{i=1}^{n} v_{i,f} \cdot x_{i} \right)^{2} - \sum_{i=1}^{n} v_{i,f}^{2} \cdot x_{i}^{2} \right) \\ \end{eqnarray}$$

我们再用一个简单的例子回顾下FM模型，假设我们有三个特征：gender（性别）、weekday（星期几）、city（城市），那么FM模型如下：

$$\hat y_{FM}=w_{0}+\sum_{i=1}^{n}w_{i} +\sum_{i=1}^{n}\sum_{j=i+1}^{n}<\mathbf v_{i},\mathbf v_{j}>x_{i}x_{j}$$

注意，此处省略了$x_{i}$，因为在one-hot编码中，激活的$x_{i}$就是1，未激活的为0。

取一条训练数据例子如下：

$$\begin{eqnarray} \hat y_{FM} &=&w_{Male}+w_{London}+w_{Tuesday} \\ &+&<v_{Male},v_{London}>\\ &+&<v_{London},v_{Tuesday}>\\ &+&<v_{Male},v_{Tuesday}>\\ \end{eqnarray}$$

参数$v_{Male}$的梯度为：

$$\triangledown_{Male} \hat y_{FM}=v_{London}+v_{Tuesday}$$

因此性别特征参数的更新，会在城市和星期两个方向进行，这是在假设年龄和星期之间不独立，存在一定相关性，但是如果性别和星期之间是相互独立的，那么我们希望对于性别特征参数的更新应该与星期正交，FM的这一假设降低了模型的空间，使得特征权重的更新相互耦合（后续我们可以看到，FFM则可以解决这个问题）

FM相关论文：
Factorization Machines

【4】神经网络因子分解机（NFM）

因子分解机由于使用了向量内积输出的是一个标量，难以和深度学习结合起来。但是向量内积可以看做是两步操作即element-wise的hardmard积之后再做一个sum。hardmard积的结果是在向量空间中的每个维度上累积特征交叉的信息，如果去掉sum操作，输出k维的向量，后面可以再接多层FC或者其他结构从而构建一个深度网络。hardmard积输出的向量可以看做特征交叉之后在向量空间中的特征表示，契合神经网络中的representation learning 表示学习的思想。

$$\begin{eqnarray} c_{f}= \frac{1}{2} \sum_{F_{1}=1}^{m}\lbrace (\sum_{i\in F_{1}}^{n} v_{iF_{1}f}\cdot x_{i} )^{2} -(\sum_{i\in F_{1}}^{n} v_{iF_{1}f}^{2}\cdot x_{i}^{2}) \rbrace \end{eqnarray}$$

NFM相关论文：

Neural Factorization Machines for Sparse Predictive Analytics

【5】域感知因子分解机模型（FFM）

首先来看下FFM模型公式：

$$f(x)=w_{0}+\sum_{i=1}^{n}w_{i}x_{i} +\sum_{i=1}^{n}\sum_{j=i+1}^{n}<\mathbf v_{i,F_{j}},\mathbf v_{j,F_{i}}>x_{i}x_{j}$$

化简为：

$$\begin{eqnarray} c_{f}= \sum_{F_{1}=1}^{m}\sum_{F_{2}>F_{1}}^{m}(\sum_{i\in F_{1}}^{n}v_{iF_{2}f} \cdot x_{i})(\sum_{j\in F_{2}}^{n}v_{jF_{1}f} \cdot x_{j}) +\frac{1}{2} \sum_{F_{1}=1}^{m}\lbrace (\sum_{i\in F_{1}}^{n} v_{iF_{1}f}\cdot x_{i} )^{2} -(\sum_{i\in F_{1}}^{n} v_{iF_{1}f}^{2}\cdot x_{i}^{2}) \rbrace \end{eqnarray}$$

FFM相比FM模型多了一个域的概念，域指的是同一类性质的特征可以被归类到同一个域，比如最简单的2-field case: 广告侧特征作为一个域，用户侧特征作为一个域。或者更细的划分，每个one-hot前的原始特征都作为一个域，比如性别one-hot之后有两个特征，这两个特征都属于同一个域。

同上继续看这条训练数据的case：

$$\begin{eqnarray} \hat y_{FFM} &=&w_{Male}+w_{London}+w_{Tuesday} \\ &+&<v_{Male,City},v_{London,Gender}> \\ &+&<v_{London,Weekday},v_{Tuesday,City}> \\ &+&<v_{Male,Weekday},v_{Tuesday,Gender}> \\ \end{eqnarray}$$

参数$v_{Male,F_{City}}$的梯度为：

$$\triangledown_{Male,F_{City}} \hat y_{FFM}=v_{London,Gender}$$

参数$v_{Male,F_{Weekday}}$的梯度为：

$$\triangledown_{Male,F_{Weekday}} \hat y_{FFM}=v_{Tuesday,Gender}$$

从而实现了特征权重更新的解耦。但是参数空间也因此而增大，变成了$O(nkf)$，$f$是field的维度。

FFM相关论文：
Field-aware Factorization Machines in a Real-world Online Advertising System

【6】域加权因子分解机（FwFM）

FFM虽好，但是参数空间是FM的$f$倍，在计算广告点击率预估中，one-hot之后的特征维度就达到了10w维，FM模型对每维one-hot特征都用$k$维的隐向量表示，参数空间达到了$kn$维，假设k是20，则参数空间为200w维，FFM为每个特征对于每个域都学习一个隐向量，假设有40个域，那么参数空间将达到8000w维，学习如此大的参数空间需要非常多的数据、机器资源和时间，在工业界是不可接受的。比如在计算广告点击率预估中通常FFM只分为用户和广告两个域，但是参数空间也加倍了。为了解决这个问题，FwFM被提出来了。

首先来看看Fw-FM的公式：

$$f(x)=w_{0}+\sum_{i=1}^{n}w_{i}x_{i} +\sum_{i=1}^{n}\sum_{j=i+1}^{n}x_{i}x_{j} <\mathbf v_{i},\mathbf v_{j}>r_{F(I),F(j)}$$

相比于FM模型，Fw-FM在特征交叉部分为每个交叉另外乘上了一个域交叉系数因子$r_{F(I),F(j)}$，由于域的个数$k$远小于特征参数$n$（$k << n$），因此Fw-FM模型的复杂度依旧为$O(kn)$。

继续用上面的训练数据为例子：

$$\begin{eqnarray} \hat y_{FwFM} &=&w_{Male}+w_{London}+w_{Tuesday} \\ &+&<v_{Male},v_{London}>\cdot r_{Gender,City}\\ &+&<v_{London},v_{Tuesday}>\cdot r_{City,Weekday}\\ &+&<v_{Male},v_{Tuesday}>\cdot r_{Gender,Weekday}\\ \end{eqnarray}$$

参数$v_{Male}$的梯度为：

$$\triangledown_{Male} \hat y_{FwFM}=v_{London} \cdot r_{Gender,City} +v_{Tuesday} \cdot r_{Gender,Weekday}$$

如果Gender域的特征与Weekday的特征不相关，那么这两个域的权重$r_{Gender,Weekday}$就非常小，因此$v_{Male}$在梯度更新的时候受到Weekday的特征影响较小，因此保证了Gender域的权重能够在合理的方向上更新，做到了去耦合的作用，并且参数空间相比FFM大幅度减小。

除此之外Fw-FM还有其他两个变体：

Fw-FM-FeLV:

$$f(x)=w_{0}+\sum_{i=1}^{n}<\mathbf w_{i} \mathbf v_{i}> x_{i} +\sum_{i=1}^{n}\sum_{j=i+1}^{n}x_{i}x_{j} <\mathbf v_{i},\mathbf v_{j}>r_{F(I),F(j)}$$

Fw-FM-FiLV:

$$f(x)=w_{0}+\sum_{i=1}^{n}<\mathbf w_{F_{i}} \mathbf v_{i}> x_{i} +\sum_{i=1}^{n}\sum_{j=i+1}^{n}x_{i}x_{j} <\mathbf v_{i},\mathbf v_{j}>r_{F(I),F(j)}$$

这两个变体都是利用embedding向量$v_{i}$对线性项进行改进，增强泛化性。FM模型存在的另一个缺点就是一阶参数和二阶参数是割裂开学习的，对于同一个特征，却有两种参数需要独立学习，在泛化性上存在缺点，以上这两种改进的都是基于考虑到既然已经学习到了特征的两阶权重向量，何不利用两阶权重向量对一阶权重进行表达，一阶参数和二阶参数统一起来权重更新更为紧凑和高效，实验也证明能增强泛化性。

Fw系数建模域间特征交叉的思想可以扩展开来，比如FFM模型可以看做是多个FM和MF模型的组合，Fw标量系数可以对各个子模型的输出值做reweight以建模同层layer内各子模型的权重，有点归纳偏置作用于模型融合框架下的思想，从而提升模型效果。

FwFFM

$$\begin{eqnarray} c_{f}= \sum_{F_{1}=1}^{m}\sum_{F_{2}>F_{1}}^{m}(\sum_{i\in F_{1}}^{n}v_{iF_{2}f} \cdot x_{i})(\sum_{j\in F_{2}}^{n}v_{jF_{1}f} \cdot x_{j}) \cdot r_{F1,F2} +\frac{1}{2}\sum_{F_{1}=1}^{m}\lbrace (\sum_{i\in F_{1}}^{n} v_{iF_{1}f}\cdot x_{i} )^{2} -(\sum_{i\in F_{1}}^{n} v_{iF_{1}f}^{2}\cdot x_{i}^{2}) \rbrace \cdot r_{F1,F1} \end{eqnarray}$$

FwFM相关论文：
Field-weighted Factorization Machines for Click-Through Rate Prediction in Display Advertising

【7】张量因子分解机（MVM）

FM、FFM、Fw-FM模型都只考虑了两阶的特征交叉，更高阶的特征交叉并没有被建模，如果考虑更高阶的特征交叉。FM模型是不能胜任的，比如三阶的FM，模型复杂度太高，在生产环境中无法接受。MVM模型采用了另一种建模方式，通过CP分解的方式，将任意高阶的特征交叉降维成$k$维的张量，因此模型复杂度变成了$O(k(m+d))$，由此高阶的特征交叉训练成为了可能。

$$f(x)=\sum_{i_{1}=1}^{I_{1}+1} \cdot \cdot \cdot \sum_{i_{m}=1}^{I_{m}+1}\left( \prod_{p=1}^{m}z_{i_{p}}^{p}\right)\left(\sum_{f=1}^{k}\prod_{p=1}^{m}a_{i_{p},f}^{p}\right)$$

简单化简下：

$$\begin{eqnarray} f(x) &=&\sum_{i_{1}=1}^{I_{1}+1} \cdot \cdot \cdot \sum_{i_{m}=1}^{I_{m}+1}\left(\prod_{p=1}^{m}z_{i_{p}}^{p}\right)\left(\sum_{f=1}^{k}\prod_{p=1}^{m}a_{i_{p},f}^{p}\right) \\ &=& \sum_{f=1}^{k} \sum_{i_{1}=1}^{I_{1}+1} \cdot \cdot \cdot \sum_{i_{m}=1}^{I_{m}+1} \left(\prod_{p=1}^{m} z_{i_{p}}^{p} a_{i_{p},f}^{p}\right)\\ &=&\sum_{f=1}^{k} \left( \sum_{i_{1}=1}^{I_{1}+1} z_{i_{1}}^{1} a_{i_{1},f}^{1} \right) \cdot \cdot \cdot \left( \sum_{i_{m}=1}^{I_{m}+1} z_{i_{m}}^{m} a_{i_{m},f}^{m}\right)\\ \end{eqnarray}$$

反向传播更新式如下：

$$\frac{\partial f(x)}{\partial a_{i_{p},f}^{p} } = z_{i_{p}}^{p}\left( \sum_{i_{1}=1}^{I_{1}+1} z_{i_{1}}^{1} a_{i_{1},f}^{1} \right)\cdot \cdot\cdot\left(\sum_{i_{m}=1}^{I_{m}+1} z_{i_{m}}^{m} a_{i_{m},f}^{m} \right)$$

可以看出反向传播更新式是一个连乘式，MVM的缺点也在于此，当考虑高阶建模的时候，m非常大，连乘式子很长。相对于FM的连和式，对异常点波动更敏感，对模型的收敛挑战越大，实际生产环境中应用较难。如果只使用两阶的MVM则退化成MF模型。

MVM相关论文：

Multi-View Factorization Machines

【8】全息因子分解机（Holographic factorization machine）

FM模型引入了一个很重要的概念是将离散的one-hot特征端到端的学习一个embedding向量，从而将高达数十万（加入广告id特征）甚至上亿维（加入用户id特征）的离散特征空间映射到同一个$k$维向量空间中，从而实现了降维，其中$k$是FM模型的隐向量维度。特征表达都在同一个空间中有个很好的特性，即可以采用一些数学上的距离函数来计算两个特征点的距离，FM模型采用的是向量内积来度量两个特征向量之间的距离。但是向量内积也有一些局限性，比如向量内积只考虑了向量之间同维度element-wise的交叉，从而限制了一些表达能力。一个简单的想法是我们是否可以用向量外积来建模向量之间的交叉，但是向量外积存在一个问题是维度爆炸；两个$k$维的向量内积结果是一个标量，而两个$k$维的向量外积结果是一个$k^2$维的矩阵，参数量和计算量都增大了很多，难以在实际业务中使用，为了缓解向量外积的参数爆炸问题，可以对向量外积借助全息降维表示（Holographic reduction representation）对向量外积的结果从$k^2$降维成一个$k$维的向量。全息降维表示还有一些很好的特性，比如降维的过程中可以保留绝大部分矩阵信息、可以近似还原回原矩阵（带一些noise）、有一对逆操作循环卷积和循环相关可以天然适用于反向传播。用循环卷积或者循环相关替代内积我们可以推导出全息FM/MF公式如下：

（1）全息FM模型（CCOV）：

$$\begin{eqnarray} \vec c &=& \sum_{i=1}^{n}\sum_{j=i+1}^{n} (\vec v_{i} \odot \vec x_{i}) \circledast (\vec v_{j} \odot \vec x_{i}) \\ &=& \frac{1}{2} \lbrace \sum_{i=1}^{n}\sum_{j=1}^{n} (\vec v_{i} \odot \vec x_{i}) \circledast (\vec v_{j} \odot \vec x_{i}) - \sum_{i=1}^{n}(\vec v_{i} \odot \vec x_{i}) \circledast (\vec v_{j} \odot \vec x_{i}) \rbrace \\ &=&\frac{1}{2} \lbrace (\sum_{i=1}^{n} \vec v_{i}\odot \vec x_{i} )\circledast (\sum_{i=1}^{n} \vec v_{i}\odot \vec x_{i}) -\sum_{i=1}^{n} (\vec v_{i} \odot \vec x_{i}) \circledast (\vec v_{i} \odot \vec x_{i}) \rbrace \\ &=&\frac{1}{2} \lbrace \xi ^{-1} \lbrack \xi(\sum_{i=1}^{n} \vec v_{i} \odot \vec x_{i}) \odot \xi (\sum_{i=1}^{n} \vec v_{i}\odot \vec x_{i}) \rbrack - \sum_{i=1}^{n} \xi ^{-1}\lbrack \xi(\vec v_{i} \odot \vec x_{i}) \odot \xi(\vec v_{i} \odot \vec x_{i} )\rbrack \rbrace \end{eqnarray}$$

可以看到全息FM模型的计算复杂度稍高，为$O(nklogk)$，比推荐系统中常用的FM模型高了近一个数量级的复杂度。

（2）全息MF模型（CCOV）：

$$\begin{eqnarray} \vec c &=& \sum_{F_{1}=1}^{m}\sum_{F_{2}>F_{1}}^{m} \lbrack (\sum_{i\in F_{1}}^{n} \vec v_{iF_{2}} \odot \vec x_{i}) \circledast (\sum_{j\in F_{2}}^{n} \vec v_{jF_{1}} \odot \vec x_{j})\rbrack \\ &=& \sum_{F_{1}=1}^{m}\sum_{F_{2}>F_{1}}^{m} \xi^{-1} \lbrack \xi (\sum_{i\in F_{1}}^{n} \vec v_{iF_{2}} \odot \vec x_{i}) \odot \xi(\sum_{j\in F_{2}}^{n} \vec v_{jF_{1}} \odot \vec x_{j}) \rbrack \\ \end{eqnarray}$$

全息MF模型的计算复杂度为$O(nk)$和传统向量内积版本的FM/MF一样，可以在现网大规模使用。事实上全息降维表示有两种互逆算子，循环卷积（CCOV）和循环相关（CCOR），因此可以同时采用这两种算子从不同角度挖掘特征交互关系，如Dual HMF模型

HFM相关论文：Holographic Factorization Machines for Recommendation

总的来说，借鉴SVD的因子分解思想衍生出了FM系列模型仍然在embedding+特征交互函数框架下，二阶特征交互

不定期更新~