大家好，又见面了，我是你们的朋友全栈君。

在推荐系统和计算广告业务中，点击率CTR（click-through rate）和转化率CVR（conversion rate）是衡量流量转化的两个关键指标。准确的估计CTR、CVR对于提高流量的价值，增加广告及电商收入有重要的指导作用。业界常用的方法有人工特征工程 + LR（Logistic Regression）、GBDT（Gradient Boosting Decision Tree） + LR、FM模型。在这些模型中，FM近年来表现突出，分别在由Criteo和Avazu举办的CTR预测竞赛中夺得冠军。

因子分解机（Factorization Machine, FM）是由Steffen Rendle提出的一种基于矩阵分解的机器学习算法，其主要用于解决数据稀疏的业务场景（如推荐业务），特征怎样组合的问题。

paper指出FM与SVM相比，有如下优势：

FM可以实现非常稀疏数据参数估计，而SVM会效果很差，因为训出的SVM模型会面临较高的bias；
FMs拥有线性的复杂度, 可以通过 primal 来优化而不依赖于像SVM的支持向量机；

一、FM原理

1. 为什么进行特征组合？

在feed流推荐场景中，根据user和item基础信息（clicked：是否点击；userId：用户ID；userGender：用户性别；itemTag：物品类别），来预测用户是否对物品感兴趣（点击与否，二分类问题）。源数据如下：

clicked	userId	userGender	itemTag
1	1	男	篮球
0	1	男	化妆品
0	2	女	篮球
1	2	女	化妆品

由于userGender和itemTag特征都是categorical类型的，需要经过独热编码（One-Hot Encoding）转换成数值型特征。

clicked	userId	userGender_男	userGender_女	itemTag_篮球	itemTag_化妆品
1	1	1	0	1	0
0	1	1	0	0	1
0	2	0	1	1	0
1	2	0	1	0	1

经过One-Hot编码之后，大部分样本数据特征是比较稀疏的。上面的样例中，每个样本有5维特征，但平均仅有3维特征具有非零值。实际上，这种情况并不是此例独有的，在真实应用场景中这种情况普遍存在。例如，CTR/CVR预测时，用户的性别、职业、教育水平、品类偏好，商品的品类等，经过One-Hot编码转换后都会导致样本数据的稀疏性。特别是商品品类这种类型的特征，如商品的三级品类约有1000个，采用One-Hot编码生成1000个数值特征，但每个样本的这1000个特征，有且仅有一个是有效的（非零）。由此可见，数据稀疏性是实际问题中不可避免的挑战。

One-Hot编码的另一个特点就是导致特征空间大。例如，商品三级类目有1000维特征，一个categorical特征转换为1000维数值特征，特征空间剧增。

同时通过观察大量的样本数据可以发现，某些特征经过关联之后，与label之间的相关性就会提高。例如，“男性”与“篮球”、“女性”与“化妆品”这样的关联特征，对用户的点击有着正向的影响。换句话说：男性用户很可能会在篮球有大量的浏览行为；而在化妆品却不会有。这种关联特征与label的正向相关性在实际问题中是普遍存在的。因此，引入两个特征的组合是非常有意义的。

2. 如何组合特征？

多项式模型是包含特征组合的最直观的模型。在多项式模型中，特征 $x_{i}$ 和 $x_{j}$ 的组合采用 $x_{i}x_{j}$ 表示，即 $x_{i}$ 和 $x_{j}$ 都非零时，组合特征 $x_{i}x_{j}$ 才有意义。从对比的角度，本文只讨论二阶多项式模型。模型的表达式如下：

$y(X)=w_{0}+\sum_{i=1}^{n}w_{_i}x_{_i}+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}w_{ij}x_{i}x_{j}$

其中，代表样本的特征数量， $x_{i}$ 是第个特征的值， $w_{0},w_{_i}x_{_i},w_{ij}$ 是模型参数。

从公式来看，模型前半部分就是普通的LR线性组合，后半部分的交叉项即特征的组合。单从模型表达能力上来看，FM的表达能力是强于LR的，至少不会比LR弱，当交叉项参数全为0时退化为普通的LR模型。

从上面公式可以看出，组合特征的参数一共有 $\frac{n(n-1)}{2}$ 个，任意两个参数都是独立的。然而，在数据稀疏性普遍存在的实际应用场景中，二次项参数的训练是很困难的。其原因是：每个参数 $w_{ij}$ 的训练需要大量 $x_{i}$ 和 $x_{j}$ 都非零的样本；由于样本数据本来就比较稀疏，满足 $x_{i}$ 和 $x_{j}$ 都非零的样本将会非常少。训练样本的不足，很容易导致参数 $w_{ij}$ 不准确，最终将严重影响模型的性能。

3. 如何解决二次项参数的训练问题呢？

矩阵分解提供了一种解决思路。在model-based的协同过滤中，一个rating矩阵可以分解为user矩阵和item矩阵，每个user和item都可以采用一个隐向量表示。比如在下图中的例子中，我们把每个user表示成一个二维向量，同时把每个item表示成一个二维向量，两个向量的点积就是矩阵中user对item的打分。

推荐系统FM & FFM算法解读与实践

任意的 $N\times N$ 实对称矩阵都有个线性无关的特征向量。并且这些特征向量都可以正交单位化而得到一组正交且模为1的向量。故实对称矩阵 $\vec{A}$ 可被分解成：

$\vec{A}=\vec{Q}\vec{\Lambda} \vec{Q}^{T}$

其中 $\vec{Q}$ 为正交矩阵， $\vec{\Lambda}$ 为实对角矩阵。

类似地，所有二次项参数 $w_{ij}$ 可以组成一个对称阵 $\vec{W}$ （为了方便说明FM的由来，对角元素可以设置为正实数），那么这个矩阵就可以分解为 $\vec{W}=\vec{V}^{T} \vec{V}$ ， $\vec{V}$ 的第列( $v_{j}$ )便是第维特征( $x_{j}$ )的隐向量。换句话说，特征分量 $x_{i}$ 和 $x_{j}$ 的交叉项系数就等于 $x_{i}$ 对应的隐向量与 $x_{j}$ 对应的隐向量的内积，即每个参数 $w_{ij}=\left \langle v_{i}, v_{j}\right \rangle$ ，这就是FM模型的核心思想。

为了求出 $w_{ij}$ ，我们需要求出特征分量 $x_{i}$ 的辅助向量 $v_{i}=\left ( v_{i1},...,v_{ik} \right )$ , $x_{j}$ 的辅助向量 $v_{j}=\left ( v_{j1},...,v_{jk} \right )$ , 表示隐向量长度（实际应用中 k<<n ），转换过程如下图所示：

$\vec{W}=\vec{V}^{T}\vec{V}=\begin{bmatrix} \vec{V_{1}}\\ \vec{V_{2}}\\ ...\\ \vec{V_{n}} \end{bmatrix}\times \begin{bmatrix} \vec{V_{1}}& \vec{V_{2}} & ...& \vec{V_{n}} \end{bmatrix}=\begin{bmatrix} w_{11} &w_{12} &... &w_{1n} \\ w_{21} &w_{22} &... &w_{2n} \\ ...& ...&... &... \\ w_{n1}&w_{n2} &... &w_{nn} \end{bmatrix} \\=\begin{bmatrix} w_{11} &w_{12} &... &w_{1k} \\ w_{21} &w_{22} &... &w_{2k} \\ ...& ...&... &... \\ w_{n1}&w_{n2} &... &w_{nk} \end{bmatrix}\times \begin{bmatrix} w_{11} &w_{21} &... &w_{n1} \\ w_{12} &w_{22} &... &w_{n2} \\ ...& ...&... &... \\ w_{1k}&w_{2k} &... &w_{nk} \end{bmatrix}$

$\vec{W}$ 矩阵对角线上面的元素即为交叉项的参数。

FM的模型方程为（本文不讨论FM的高阶形式）：

$\hat{y}\left ( X \right ):=w_{0}+\sum_{i=1}^{n}w_{_i}x_{_i}+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n} \left \langle v_{i},v_{j} \right \rangle x_{i}x_{j}$

$\left \langle v_{i},v_{j} \right \rangle:=\sum_{f=1}^{k}v_{i,f}\cdot v_{j,f}$

其中， $v_{i}$ 是第维特征的隐向量， $\left \langle \cdot ,\cdot \right \rangle:$ 代表向量点积。隐向量的长度为 k<<n ，包含个描述特征的因子。根据公式，二次项的参数数量减少为 $k\times n$ 个，远少于多项式模型的参数数量。所有包含 $x_{i}$ 的非零组合特征（存在某个 $j\neq i$ ，使得 $x_{i}x_{j}\neq 0$ ）的样本都可以用来学习隐向量 $v_{i}$ ，这很大程度上避免了数据稀疏性造成的影响。

显而易见，上述是一个通用的拟合方程，可以采用不同的损失函数用于解决回归、二元分类等问题，比如可以采用MSE（Mean Square Error）损失函数来求解回归问题，也可以采用Hinge/Cross-Entropy 损失来求解分类问题。当然，在进行二元分类时，FM的输出需要经过sigmoid变换，这与Logistic回归是一样的。直观上看，FM的复杂度是 $O(kn^{2})$ 。但是，通过公式(3)的等式，FM的二次项可以化简，其复杂度可以优化到 O(kn) 。由此可见，FM可以在线性时间对新样本作出预测。

采用随机梯度下降法SGD求解参数

$\frac{\partial \hat{y}(x)}{\partial x}=\left\{\begin{matrix} 1,\theta =w_{0}\\ x_{i},\theta =w_{i}\\ x_{i}\sum_{j=1}^{n} v_{i,f}x_{j} - v_{i,f}x_{i}^{2},\theta =v_{i,f} \end{matrix}\right.$

由上式可知， $v_{i,f}$ 的训练只需要样本 $x_{i}$ 的特征非0即可，适合于稀疏数据。

在使用SGD训练模型时，在每次迭代中，只需计算一次所有的 $\sum_{j=1}^{n}v_{i,f}x_{j}$ ，就能够方便得到所有 $v_{i,f}$ 的梯度，上述偏导结果求和公式中没有，即与无关，只与有关，显然计算所有的 $\sum_{j=1}^{n}v_{i,f}x_{j}$ 的复杂度是 O(kn) ，模型参数一共有 kn+n+1 个。因此，FM参数训练的复杂度也是 O(kn) 。综上可知，FM可以在线性时间训练和预测，是一种非常高效的模型。

二、FFM原理

1. 特征组合为什么引入field？

同样以feed流推荐场景为例，我们多引入user维度用户年龄信息，其中性别和年龄同属于user维度特征，而tag属于item维度特征。在FM原理讲解中，“男性”与“篮球”、“男性”与“年龄”所起潜在作用是默认一样的，但实际上不一定。FM算法无法捕捉这个差异，因为它不区分更广泛类别field的概念，而会使用相同参数的点积来计算。

在FFM（Field-aware Factorization Machines ）中每一维特征（feature）都归属于一个特定和field，field和feature是一对多的关系。如下表所示：

field	user field(U)					item field(I)
clicked	userId	userGender_男	userGender_女	userAge_[20.30]	userAge_[30,40]	itemTag_篮球	itemTag_化妆品
1	1	1	0	1	0	1	0
0	1	1	0	1	0	0	1
0	2	0	1	0	1	1	0
1	2	0	1	0	1	0	1

FFM模型认为 $v_{i}$ 不仅跟 $x_{i}$ 有关系，还跟与 $x_{i}$ 相乘的 $x_{j}$ 所属的Field有关系，即 $v_{i}$ 成了一个二维向量 $v_{F\times K }$ ，是隐向量长度，是Field的总个数。设样本一共有个特征, 个field，那么FFM的二次项有个隐向量。而在FM模型中，每一维特征的隐向量只有一个。FM可以看作FFM的特例，是把所有特征都归属到一个field时的FFM模型。

$y(X)=w_{0}+\sum_{i=1}^{n}w_{_i}x_{_i}+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\left \langle V_{i,fj},V_{j,fi} \right \rangle x_{i}x_{j}$

其中， $f_{j}$ 是第的特征所属的字段。如果隐向量的长度为，那么FFM的二次参数有 nfk 个，远多于FM模型的个。此外，由于隐向量与field相关，FFM二次项并不能够化简，时间复杂度是 $O\left ( kn^{2} \right )$ 。
需要注意的是由于FFM中的latent vector只需要学习特定的field，所以通常：

$K_{FFM}<<K_{FM}$

2. 如何组合特征？

还是以feed流场景为例，说明FFM是如何组合特征的。输入记录如下：

clicked	userId	userGender(U)	userAge(U)	itemTag(I)
1	1	男	[20,30]	篮球

FM模型交叉项为：

推荐系统FM & FFM算法解读与实践 xLearn是一款高性能，易于使用且可扩展的机器学习软件包，包括FM和FFM模型，可用于大规模解决机器学习问题。xlearn比libfm和libffm库快得多，并为模型测试和调优提供了更好的功能。这里以xlearn实现FM和FFM算法。

1. FM实现

数据来自Kaggle预测泰坦尼克号的生存数据集，xlearn可以直接处理csv以及libsvm格式数据来实现FM算法，但对于FFM必须是libsvm格式数据。

1.1 python代码

import xlearn as xl

# 训练
fm_model = xl.create_fm()  # 使用xlearn自带的FM模型
fm_model.setTrain("./fm_train.txt")  # 训练数据

# 参数:
#  0. 二分类任务
#  1. learning rate: 0.2
#  2. lambda: 0.002
#  3. metric: accuracy
param = {'task':'binary', 'lr':0.2,
         'lambda':0.002, 'metric':'acc'}

# 使用交叉验证
fm_model.cv(param)

1.2 运行

[ ACTION ] Start to train …
[ ACTION ] Cross-validation: 1/3:
[————] Epoch Train log_loss Test log_loss Test Accuarcy Time cost (sec)
[ 10% ] 1 0.520567 0.519509 0.770270 0.00
[ 20% ] 2 0.462764 0.504741 0.787162 0.00
[ 30% ] 3 0.451524 0.499556 0.790541 0.00
[ 40% ] 4 0.446151 0.497348 0.787162 0.00
[ 50% ] 5 0.443402 0.494840 0.793919 0.00
[ 60% ] 6 0.440488 0.494532 0.793919 0.00
[ 70% ] 7 0.439055 0.493156 0.804054 0.00
[ 80% ] 8 0.438151 0.493404 0.800676 0.00
[ 90% ] 9 0.437012 0.492352 0.807432 0.00
[ 100% ] 10 0.436463 0.492059 0.804054 0.00
[ ACTION ] Cross-validation: 2/3:
[————] Epoch Train log_loss Test log_loss Test Accuarcy Time cost (sec)
[ 10% ] 1 0.529570 0.491618 0.798658 0.00
[ 20% ] 2 0.474390 0.477966 0.788591 0.00
[ 30% ] 3 0.461248 0.470482 0.785235 0.00
[ 40% ] 4 0.456666 0.469640 0.788591 0.00
[ 50% ] 5 0.452902 0.468955 0.788591 0.00
[ 60% ] 6 0.450912 0.467620 0.785235 0.00
[ 70% ] 7 0.449447 0.467692 0.785235 0.00
[ 80% ] 8 0.447781 0.466430 0.781879 0.01
[ 90% ] 9 0.447122 0.466931 0.785235 0.00
[ 100% ] 10 0.446272 0.466597 0.788591 0.00
[ ACTION ] Cross-validation: 3/3:
[————] Epoch Train log_loss Test log_loss Test Accuarcy Time cost (sec)
[ 10% ] 1 0.544947 0.470564 0.781145 0.00
[ 20% ] 2 0.491881 0.448169 0.794613 0.00
[ 30% ] 3 0.479801 0.442210 0.794613 0.00
[ 40% ] 4 0.475032 0.438578 0.804714 0.00
[ 50% ] 5 0.472111 0.436720 0.808081 0.00
[ 60% ] 6 0.470067 0.435224 0.811448 0.00
[ 70% ] 7 0.468599 0.434378 0.811448 0.00
[ 80% ] 8 0.466845 0.434049 0.811448 0.00
[ 90% ] 9 0.466121 0.433529 0.811448 0.00
[ 100% ] 10 0.465646 0.433083 0.814815 0.00
[————] Average log_loss: 0.463913
[————] Average Accuarcy: 0.802486
[ ACTION ] Finish Cross-Validation
[ ACTION ] Clear the xLearn environment …
[————] Total time cost: 0.04 (sec)

2. FFM实现

数据来自Criteo点击率预测挑战赛中CTR数据集的一个微小（1％）抽样，首先我们需要将其转换为xLearn所需的libffm格式以拟合模型。

2.1 python代码

import xlearn as xl

# 训练
ffm_model = xl.create_ffm() # 使用FFM模型
ffm_model.setTrain("./FFM_train.txt")  # 训练数据
ffm_model.setValidate("./FFM_test.txt")  # 校验测试数据

# param:
#  0. binary classification
#  1. learning rate: 0.2
#  2. regular lambda: 0.002
#  3. evaluation metric: accuracy
param = {'task':'binary', 'lr':0.2,
         'lambda':0.002, 'metric':'acc'}

# 开始训练
ffm_model.fit(param, './model.out')

# 预测
ffm_model.setTest("./FFM_test.txt")  # 测试数据
ffm_model.setSigmoid()  # 归一化[0,1]之间

# 开始预测
ffm_model.predict("./model.out", "./output.txt")

2.2 运行

[ ACTION ] Initialize model …
[————] Model size: 5.56 MB
[————] Time cost for model initial: 0.01 (sec)
[ ACTION ] Start to train …
[————] Epoch Train log_loss Test log_loss Test Accuarcy Time cost (sec)
[ 10% ] 1 0.600614 0.534322 0.770000 0.00
[ 20% ] 2 0.541555 0.536250 0.770000 0.00
[ 30% ] 3 0.521822 0.530098 0.770000 0.00
[ 40% ] 4 0.505286 0.537378 0.770000 0.00
[ 50% ] 5 0.492967 0.528159 0.770000 0.00
[ 60% ] 6 0.483819 0.533365 0.775000 0.00
[ 70% ] 7 0.472950 0.537750 0.770000 0.00
[ 80% ] 8 0.465698 0.531461 0.775000 0.00
[ 90% ] 9 0.457841 0.531676 0.770000 0.00
[ 100% ] 10 0.450092 0.531530 0.770000 0.00
[ ACTION ] Early-stopping at epoch 8, best Accuarcy: 0.775000
[ ACTION ] Start to save model …
[————] Model file: ./model.out
[————] Time cost for saving model: 0.00 (sec)
[ ACTION ] Finish training
[ ACTION ] Clear the xLearn environment …
[————] Total time cost: 0.05 (sec)
———————————————————————————————-
_
| |
__ _| | ___ __ _ _ __ _ __
\ \/ / | / _ \/ _` | ‘__| ‘_ \
> <| |___| __/ (_| | | | | | |
/_/\_\_____/\___|\__,_|_| |_| |_|

xLearn — 0.36 Version —
———————————————————————————————-

[————] xLearn uses 4 threads for prediction task.
[ ACTION ] Load model …
[————] Load model from ./model.out
[————] Loss function: cross-entropy
[————] Score function: ffm
[————] Number of Feature: 9991
[————] Number of K: 4
[————] Number of field: 18
[————] Time cost for loading model: 0.00 (sec)
[ ACTION ] Read Problem …
[————] First check if the text file has been already converted to binary format.
[————] Binary file (./FFM_test.txt.bin) found. Skip converting text to binary.
[————] Time cost for reading problem: 0.00 (sec)
[ ACTION ] Start to predict …
[————] The test loss is: 0.531461
[ ACTION ] Clear the xLearn environment …
[————] Total time cost: 0.00 (sec)