因子分解机（libffm+xlearn）

本文主要是介绍因子分解机（libffm+xlearn），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

因子分解机

一、简介

  在CTR和CVR预估任务中，可能有大量的ID类特征（Categorical Feature），一般来说并不适合直接送入树模型（xgboost完全不支持，lightgbm只根据取值不同），一种常用的做法是通过Label Encoding变成离散的稀疏的高维向量（最具代表的是Onehot独热编码），然后送入LR训练。在独热编码的作用下，产生了多项式模型参数学习困难的问题。
  因子分解机 Factorization Machine（FM）解决了稀疏特征下的参数学习问题，实现了树模型很难做到的特征交叉（树模型需要手动提取交叉特征），而且可以不考虑0特征以加速训练，对稀疏严重的数据有着较好的相性，因此是LR以外的一个不错的选择。常见的使用方法是Onehot特征直接送入FM，或者经过其他模型输出的离散高维特征（比如提升树模型输出的叶子序号的序列）送入FM做stacking。本文参考了其他的文献，对FM、FFM以及相应的实现包括libffm和xlearn做出基本的介绍。文章以后仍会继续完善，尤其是libffm和xlearn还需要进一步follow代码。

---

二、多项式模型

2.1 多项式模型形式

  考虑一个模型，它的输出由单特征（$d$维）与组合特征的线性组合构成，如果不看二次项，这就是一个线性回归模型，现在引入了交叉项。

$$f(x)=w_0 +\sum_{i=1}^dw_i \cdot x_i +\sum_{i=1}^d \sum_{j=i+1}^d w_{ij}\cdot x_ix_j$$
  其中单特征的参数 $w_i$ 有 $d$ 个，组合特征的参数 $w_{ij}$ 有 $\frac{d(d-1)}{2}$ 个，且任意两个 $w_{ij}$ 之间相互独立。

2.2 交叉项参数训练问题

  现在假设目标函数是 $L(y, f(x))$，为了使用梯度下降法训练交叉项参数，需要求导：

$$\frac{\partial L}{\partial w_{ij}}=\frac{\partial L}{\partial f(x)}\cdot\frac{\partial f(x)}{\partial w_{ij}}=\frac{\partial L}{\partial f(x)}x_ix_j$$
  也就是说，每个二次项参数 $w_{ij}$的训练需要 $x_i$和 $x_j$同时非零，若特征稀疏（例如Onehot过），则一整行中只有一个1，容易导致 $w_{ij}$训练无法进行。

---

三、FM

3.1 FM是什么

  将矩阵 $W=\left\{w_{i,j}\right\}$ 矩阵（这是一个对称方阵）分解成 $W=V^TV$ 的形式，其中 $V=(v_1, v_2,\cdots, v_d)$ 是一个 $k\times d$ 矩阵，且 $k\ll d$，于是 $W$ 矩阵的每一个元素都可以用 $V$ 矩阵对应的两列做内积得到：$w_{ij}=v_i\cdot v_j$，同时多项式模型可以重写，这就是因子分解机模型。

$$f(x)=w_0 +\sum_{i=1}^dw_i \cdot x_i +\sum_{i=1}^d \sum_{j=i+1}^d (v_i\cdot v_j)\cdot x_ix_j$$
  由于只需要用分解后产生的 $V$ 就能表达 $W$，使得参数个数由 $d^2$ 变成了 $kd$。另一方面， $V$ 矩阵的每一列 $v_i$ 是第 $i$ 维特征的隐向量，一个隐向量包含 $k$ 个描述第 $i$ 维特征的因子，故称因子分解。

3.2 为什么FM能解决参数训练问题

  经过因子化之后，组合特征 $x_ix_j$ 和 $x_jx_k$ 的系数 $(v_i\cdot v_j)$ 与 $(v_j\cdot v_k)$不再独立，他们共有了 $v_j$，因此所有包含 $x_j$ 特征的非零组合特征的样本都能拿来训练。这是什么意思呢？现在，如果只看交叉项（不管用什么loss，根据链式法则我们总需要乘上 $\frac{\partial f(x)}{\partial w_{ij}}$）：

$$f(x)\propto\sum_{i} \sum_{j} w_{ij}x_ix_j\rightarrow \frac{\partial f(x)}{\partial w_{ij}}=x_ix_j$$
对于稀疏数据而言， $x_ix_j=0$ 很常见，梯度为0，FM改一下变成：
$$f(x)\propto \sum_{i=1}^d \sum_{j=i+1}^d (v_i\cdot v_j)x_ix_j \rightarrow \frac{\partial y}{\partial v_{i}}=\sum_j v_j\cdot x_ix_j$$
  原本的多项式模型，为了训练 $w_{ij}$，要求 $x_i$ 和 $x_j$ 不能同时为0，现在我们假设 $x_i\neq 0$，则条件变为 “ $x_j$绝对不可以为0”。另一方面，同样假设 $x_i\neq 0$，但是对 $j$ 没有限制，在所有的特征中，任意不为0的 $x_j$ 都可以参与训练，条件减弱为 “ 存在$x_j\neq 0$即可”。因此， FM缓解了交叉项参数难以训练的问题。

3.3 FM计算的时间复杂度

$$f(x)\propto \sum_{i=1}^d \sum_{j=i+1}^d (v_i\cdot v_j)x_ix_j$$
  时间复杂度上，若只看交叉项，两层循环 $O(n^2)$，内层k维内积（O(k)），综合起来应该是 $O(kd^2)$。然而，交叉项是可以化简的，化简为下面的形式后，复杂度是 $O(kd)$。
$$\sum_{i=1}^d\sum_{j=i+1}^d (v_i\cdot v_j)x_ix_j=\frac{1}{2}\sum_{j=1}^k\left ( \left ( \sum_{i=1}^d v_{ij}x_i\right )^2 -\sum_{i=1}^dv_{ij}^2x_i^2\right )$$

3.4 FM的梯度下降求解

  FM模型方程似乎是通用的，根据任务不同，使用不同的loss。比如，回归问题用MSE，分类问题先取sigmoid或者softmax，然后用cross-entropy，比较灵活。

$$f(x)=w_0 +\sum_{i=1}^dw_i \cdot x_i +\frac{1}{2}\sum_{j=1}^k\left ( \left ( \sum_{i=1}^d v_{ij}x_i\right )^2 -\sum_{i=1}^dv_{ij}^2x_i^2\right )$$
计算FM对各参数的梯度：
$$\left \{ \begin{matrix} \frac{\partial y(x)}{\partial w_0}=1\\\frac{\partial y(x)}{\partial w_i}=x_i\\\frac{\partial y(x)}{\partial v_{ij}}=x_i\sum_{t=1}^d v_{tj}x_t-x_i^2v_{ij} \end{matrix} \right .$$

---

四、FFM

4.1 FFM (Field-aware Factorization Machine)

  在FM的基础上，进一步提出 field 的概念。一般来说，同一个ID类特征进行Onehot而产生的所有特征都可以归为同一个 field。在FFM中，对每一个特征 $x_i$，每一个field $f_j$，学习一个隐向量 $v_{i,f_j}$，不同的特征跟同一个 field 进行关联时使用不同的隐向量。假设总共有 $d$ 个特征，属于 $f$ 个field，那么每个特征都用 $f$个隐向量来描述，所以总共有 $d\times f$ 个隐向量。而FM中，一个特征只有一个隐向量，所以FM可以看成FFM中所有特征都属于同一个 field 的特例。

$$f(x)=w_0+\sum_{i=1}^d w_i\cdot x_i +\sum_{i=1}^d\sum_{j=i+1}^d(v_{i,f_j}\cdot v_{j,f_i})\cdot x_ix_j$$
  观察一下，内积 $v_{i,f_j}\cdot v_{j,f_i}$ 表示让特征 $i$ 与 特征 $j$ 的 field 关联，同时让特征 $j$ 与 $i$ 的 field 关联，由此可见，FM的交叉是针对特征之间的，而FFM是针对特征与 field 之间的。

4.2 FFM计算举例

为了更直观地理解FFM的计算，下面给出一个例子。

Clicked	User(U)	Advertizer(A)	Gender(G)
0	Arthur	Lancelot	Male
1	Arthur	Guinevere	Male

One-Hot编码转换，其中等于其他情况的列都是0，省略掉了。

Clicked	U=Arthur	A=Lancelot	A=Guinevere	G=Male
0	1	1	0	1
1	1	0	1	1

这么看不够直观，将特征和对应的field映射成整数编号。

field name	field index	feature name	feature index
User	1	U=Arthur	1
Advertizer	2	A=Lancelot	2
		A=Guinevere	3
Gender	3	G=Male	4

第一个instance的FFM的组合项有6项，注意 $v_{i,f_j}$ 下标的含义，就很好懂了。由于存在部分0，最后实际上只有3项。

$$\sum_{i=1}^d\sum_{j=i+1}^d(v_{i,f_j}\cdot v_{j,f_i})\cdot x_ix_j=\\(v_{1,2}\cdot v_{2,1})\cdot 1\cdot 1+(v_{1,2}\cdot v_{3,1})\cdot 1\cdot 0 +(v_{1,3}\cdot v_{4,1})\cdot 1\cdot 1 \\ + (v_{2,2}\cdot v_{3,2})\cdot 1\cdot 0 + (v_{2,3}\cdot v_{4,2})\cdot 1\cdot 1\\ + (v_{1,4}\cdot v_{3,1})\cdot 0\cdot 1$$
第二个instance的FFM的组合项也有6项，最后实际只有3项。
$$\sum_{i=1}^d\sum_{j=i+1}^d(v_{i,f_j}\cdot v_{j,f_i})\cdot x_ix_j=\\ (v_{1,2}\cdot v_{2,1})\cdot 1\cdot 0+(v_{1,2}\cdot v_{3,1})\cdot 1\cdot 1 +(v_{1,3}\cdot v_{4,1})\cdot 1\cdot 1 \\ + (v_{2,2}\cdot v_{3,2})\cdot 0\cdot 1 + (v_{2,3}\cdot v_{4,2})\cdot 0\cdot 1\\ + (v_{1,4}\cdot v_{3,1})\cdot 1\cdot 1$$

4.3 FFM的实现

  下面这个算法流程摘自美团-深入FFM原理与实践，实际上正是libffm的实现，具体的介绍可以在ffm论文里找到。首先对数据逐列归一化，然后进行迭代，每次迭代计算梯度并更新参数。

libffm模型省略了常数和一次项，将FFM目标简化为下面这个形式。

$$\phi(x)=\sum_{j_1,j_2\in C}(v_{j_1,f_2}\cdot v_{j_2,f_1})x_{j_1}x_{j_2}$$
这里的 $C$是组合非零的集合（即$x_{j_1}x_{j_2}\neq 0$）， $j_1$和 $j_2$是特征编号，两个特征分别属于 field $f_1$和 $f_2$。下面以logistic loss为损失函数举例，并给目标增加L2 正则。
$$\min_v \sum_i \log(1+e^{-y_i\phi(x_i)})+\frac{\lambda}{2}||v||_2^2$$
  其中，前半部分是风险损失 $L_{err}$，后半部分是结构损失 $L_{reg}$。这个 $L_{err}$和我之前看过的logistic loss（交叉熵）不太一样，以前看到的是 $y_i$乘在log外面，但其实这么定义也符合loss的规律， $y_i=1$时， $\phi(x)$越大loss越接近0.

如果用SGD进行更新，具体在计算梯度的时候有一点trick，由于链式法则：

$$\frac{\partial L}{\partial v}=\frac{\partial L_{err}}{\partial \phi} \frac{\partial \phi}{\partial v}+\frac{\partial L_{reg}}{\partial v}$$
$\frac{\partial L_{err}}{\partial \phi}$其实和模型参数无关，只需要预先计算一次就够了，之后在对每一个参数 $v$ 求梯度的时候，直接调用乘上去即可。

  根据论文的描述，学习率更新使用了AdaGrad（但据我所知libffm默认是用sgd的，xlearn默认是用AdaGrad的），学习率分母用历次迭代梯度和代替，前期加速，后期缓和，且保证每个参数的学习率都不同，每个参数既能较快收敛，又不容易震荡。

$$v_{j_1,f_2}\leftarrow v_{j_1,f_2}-\frac{\alpha}{\sqrt{1+\sum_t(g_{v_{j_1,f_2}}^{(t)})^2}}g_{v_{j_1,f_2}}$$

---

五、ffm开源实现之libffm

5.1 数据输入格式

libffm 数据格式如下：

$$\begin{matrix} label & field_1:feature_1:value_1 & field_2:feature_2:value_2\end{matrix}$$
其中，numeric特征的value用原值，ID类特征的value用1代替。
具体以下面这个instance为例。

Clicked	User(U)	Advertizer(A)	Price(P)
0	Arthur	Lancelot	9.99
1	Arthur	Guinevere	9.99

那么这两条样本应该处理成

$$\begin{matrix} 0 & 1:U=Arthur:1 & 2:A=Lancelot:1 & 3:Price:9.99 \\ 1 & 1:U=Arthur:1 & 2:A=Guinevere:1 & 3:Price:9.99 \end{matrix}$$

然后我们要对feature进行编码，编码的方式多种多样，可以直接根据feature取值构造字典（vocabulary），也可以使用哈希函数转换字符串。

例如直接构造字典如下。值得注意的是，只有category类特征需要对不同的特征取值进行编码，数值型特征共享同一编码即可。

vocabulary = {"U=Arthur":1,"A=Lancelot":2,"A=Guinevere":3,"price":4} # 数值型特征共享同一编码

下面列出编码后的结果：

field name	field index	feature name	feature index
User	1	U=Arthur	1
Advertizer	2	A=Lancelot	2
		A=Guinevere	3
Price	3	Price	4

根据以上编码结果，我们的样本变成这样：

$$\begin{matrix} 0 & 1:1:1 & 2:2:1 & 3:4:9.99 \\ 1 & 1:1:1 & 2:3:1 & 3:4:9.99 \end{matrix}$$

另外提供一个hash转换函数

def hashstr(str, nr_bins=1e+6):return int(hashlib.md5(str.encode('utf8')).hexdigest(), 16)%(nr_bins-1)+1

5.2 数据处理技巧

1. 样本归一化

libffm有个参数是pa.norm，默认对样本归一化，如果不这样做可能会导致计算的梯度太大而出现inf的溢出。

2. 特征归一化

当特征中同时含有数值类和ID类时，例如某数值特征a取值为10000，ID类特征b取值是1，做样本归一化后，a=0.9999，b=9.999E-5，就会导致ID类特征没有贡献。因此要对每一列特征先做归一化。

3. 零值省略

上面的输入其实应该是这样的：

$$\begin{matrix} 0 & 1:1:1 & 2:2:1 & 2:3:0 & 3:4:9.99 \\ 1 & 1:1:1 & 2:2:0 & 2:3:1 & 3:4:9.99 \end{matrix}$$
但是没有必要，因为等于0的特征没有贡献，所以在生成输入文件的时候不需要写零值项，这样可以加速训练速度，也减少了文件的空间占用。

---

六、ffm开源实现之xlearn

xlearn其实不止支持ffm，还支持LR和FM。

安装

1. pip安装即可

   sudo pip install xlearn
   

2. git clone后自己编译

   git clone https://github.com/aksnzhy/xlearn.git
   cd xlearn
   ./build.sh
   

使用

在python中调用

    import xlearn as xl

具体使用可参考 ./demo

在命令行中使用

1. build/xlearn_train

   ./xlearn_train train_set -m model
   

2. build/xlearn_predict

   ./xlearn_predict test_set model -o output
   

---

参数

训练指定模型输出文件

-m
-t

# 默认输出模型是 train_set + ".model" 文件
./xlearn_train train_set# 指定输出模型，就会输出一个 xlearn_model 文件
./xlearn_train train_set -m xlearn_model# 指定输出模型到txt
./xlearn_train train_set -t xlearn_model.txt

训练指定机器学习算法

支持GLM(LR)，FM和FFM，三种算法对数据有所要求。LR和FM支持libsvm和csv输入格式，libffm格式会被处理成libsvm格式；FFM只支持libffm格式。

<libsvm format>:label index_1:value_1 index_2:value_2 ... index_n:value_n
<CSV format>:value_1 value_2 .. value_n label
<libffm format>:label field_1:index_1:value_1 field_2:index_2:value_2 ...

-s 0/1/2

./xlearn_train train_set -s 0  # Linear model
./xlearn_train train_set -s 1  # Factorization machine (FM)
./xlearn_train train_set -s 2  # Field-awre factorization machine (FFM)

训练指定验证集

-v

./xlearn_train train_set -v test_set

训练指定指标metric

分类问题支持accuracy、precision、F1和AUC
-x acc/prec/f1/auc

./xlearn_train train_set -v test_set -x acc
./xlearn_train train_set -v test_set -x prec
./xlearn_train train_set -v test_set -x f1
./xlearn_train train_set -v test_set -x auc

回归问题支持mae、mape和rmsd(rmse)

./xlearn_train train_set -v test_set -x mae
./xlearn_train train_set -v test_set -x rmsd

训练时采用交叉验证

默认是5折，可以用-f改变折数
-f
–cv

./xlearn_train train_set -f 3 --cv # 3折交叉验证

训练选择优化方法

支持sgd、adagrad和FTRL
-p

./xlearn_train train_set -p sgd
./xlearn_train train_set -p adagrad
./xlearn_train train_set -p ftrl

训练参数调整

学习率（默认0.2）

-r

./xlearn_train train_set -r 0.01

正则化（默认L2正则且 $\lambda$ 是0.00002）

./xlearn_train train_set -b 0.01

FTRL专用参数

-alpha
-beta
-lambda_1
-lambda_2

./xlearn_train train_set -p ftrl -alpha 0.002 -beta 0.8 -lambda_1 0.001 -lambda_2 1.0

FM和FFM专用参数

latent factor

-k

./xlearn_train train_set -s 2 -k 4

模型初始化（默认0.66）

-u

./xlearn_train train_set -s 2 -u 0.1

训练的迭代次数和EarlyStopping

迭代次数

-e

./xlearn_train train_set -e 10 # 训练10个epoch

EarlyStopping

EarlyStopping是默认选项，但是可以设置不用它
–dis-es

./xlearn_train train_set -e 10 --dis-es

样本归一化

归一化是默认选项，但是可以设置不用它
–no-norm

./xlearn_train train_set --no-norm

安静训练

训练时不会计算指标，可以加速
–quiet

./xlearn_train train_set --quiet

预测时输出概率或者01

–sigmoid
–sign

$ 输出概率
./xlearn_predict test_set model --sigmoid$ 输出0和1
./xlearn_predict test_set model --sigmoid

预测时指定输出文件

-o

$ 指定输出文件
./xlearn_predict test_set model --sigmoid -o submission.txt

---

数据格式

  xlearn支持三种算法LR、FM和FFM，同时支持三种输入数据格式CSV、libsvm和libffm。其中LR和FM支持CSV和libsvm格式，但是FFM只支持libffm格式。LR和FM当然也支持libffm，只不过它会被当成libsvm格式，即field字段无效。
  值得注意的是，一般测试集test是没有label的，但仍然需要添加一列label做占位符（全部设-1或0都可以），否则parser会把第一列数据当成Label的。

libsvm format:

$$\begin{matrix} label & index_1:value_1 & index_2:value_2 & \cdots \end{matrix}$$

CSV format:

$$\begin{matrix} label & value_1 & value_2 & \cdots \end{matrix}$$

libffm format:

$$\begin{matrix} label & field_1:feature_1:value_1 & field_2:feature_2:value_2 & \cdots\end{matrix}$$

---

python调用

  我最喜欢xlearn的一点是，方便python调用，不得不佩服这些造轮子的人。具体的使用参考这里。

---

使用感受

  支持分类和回归，更像是libffm的改进版，在mushroom数据集上比libffm更快，准确率更高（训练集和测试集都是），libffm不支持直接python调用，xlearn则支持。
  根据github上的描述，xlearn支持外存训练（out-of-core），可以并行化。

---

七、从神经网络的角度看FM

  输入是稀疏的高维特征，黑色线是带权值的，将每一维输入直接连接到黄色的带“+”号的结点，这部分是FM中的常数和一次项，相当于LR。另一方面，FM中的二次项相当于首先对输入做了某种Embedding，变成稠密的向量，然后这些向量进行内积，即图中褐色结点，红色线上权值恒为1，不可训练。Embedding涉及到因子$v_i$，它们是可训练的。最终一次项和二次项被加起来，送给sigmoid输出概率。

  举个例子，field i 是某个原始特征（比如性别=男）onehot后的稀疏特征：$[1,0,0]$，让 $x_i=1$，我们知道这个field中其他特征都完全没用，因为它们都是0。一方面，$x_i$ 参与了一次项的计算：

$$\sum w_i\cdot x_i$$
  另一方面， $x_i$ 经过embedding，变成了 $k$ 维向量。怎么做embedding的呢？还记得FM每个 $x_i$ （标量）对应一个隐向量 $v_i$ （ $k$维向量）吗？embedding很简单，就是 $x_i\cdot v_i$ 而已。然后，它和其他非零特征的embedding两两交叉，正是FM的二次项：
$$\sum_i\sum_j x_iv_i\cdot x_jv_j=\sum_i\sum_j (v_i\cdot v_j) x_ix_j$$

因此，对于$m$个field，共$d$维特征，实际上参与训练的参数包括如下几方面：

1. $w$ 向量，长度为 $d$
2. $v$ 矩阵，大小为 $d\times k$

  那么，FM输入格式应该怎么对应到这个网络图上呢？先回顾一下FM格式，以及上面给出的一个实例（省略0）。

$$\begin{matrix} label & index_1:value_1 & index_2:value_2 & \cdots \end{matrix}$$

Clicked	U=Arthur	A=Lancelot	A=Guinevere	G=Male
0	1	1	0	1

$$\begin{matrix} 0 & 1:1 & 2:1 & 4:1 \end{matrix}$$

  首先设定隐向量长度 $k$，然后为每个 index 初始化向量 $v_i$ ，这里 index 最大为4，因此 $v$ 矩阵的大小为 $4\times k$。接着，对于每个特征 $x_i$ 选取 $v$ 矩阵对应的 $index_i$ 行向量 $v_i$ ，做Embedding得到 $x_iv_i$。接下来的步骤不再赘述。
  训练的时候，根据样本中每一个 index 取出 $v$ 矩阵中的某一行，经过FM前向计算得到loss，然后梯度下降更新参数。从这里可以看出，只要存在 $x_i\neq 0$ 的样本，$v_i$ 就能够得到训练。

多值离散特征的处理

  有时候我们会遇到一些特殊的离散特征，在一个样本中该特征会取多个值，例如下面这个例子，我们的劳模Arthur喜欢的水果有四种，如果做onehot的话，Like特征就不像上面介绍的那些特征那样只有一个位置上有1，而是有4个位置有1，其余是0。

Clicked	User	Like
0	Arthur	Apple,Banana,Orange,Grapes

  如果我们按照libsvm格式处理样本，让“User=Arthur”特征编码为1，“Like=Apple”到“Like=Grapes”分别编码为2到5，注意虽然2到5特征编码不同，但它们是属于同一个field的（在FFM的概念里）。我们能得到样本：

$$\begin{matrix} 0 & 1:1 & 2:1 & 3:1 & 4:1 & 5:1 \end{matrix}$$

  可以发现其实没有任何区别，只不过因为FM里面没有field的概念，所以看起来好像是把Like这个特征分成了4个不同的Onehot field，每个field只有一个位置取值为1.

---

参考

1. 【github】libffm下载
2. 【博客】美团深入ffm
3. 【论文】libffm原理
4. 【github】xlearn下载
5. 【博客】推荐系统中使用ctr排序的f(x)的设计-dnn篇之DeepFM模型
6. 【API】xlearn文档
7. 【博客】推荐系统遇上深度学习 (一) FM模型理论和实践
8. 【博客】推荐系统遇上深度学习(二) -FFM模型理论和实践
9. 【博客】推荐系统遇上深度学习(三) -DeepFM模型理论和实践
10. 【博客】推荐系统遇上深度学习（四）-多值离散特征的embedding解决方案

这篇关于因子分解机（libffm+xlearn）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---