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

符号说明：

• $x表示样本特征数据$
• $y表示样本目标数据$
• $第i个训练样本为\left(x_i,y_i\right)，为了方便也可以用x=x_i表示第i个样本$

1 基于域的分解机模型（FFM）

1.1 线性模型

$$\varnothing \left(w,x\right)=w^{T}x=w_0+\sum _{j\in C_1}{w}_j{x}_j----(1)$$

$C_1表示x中非零元素索引的集合$

1.2 二次多项式模型

$$\varnothing \left(w,x\right)=w^{T}x=w_0+\sum _{j1,j2\in C_2}{w}_{j1,j2}{x}_{j1}{x}_{j2}----(2)$$

$C_2表示x中非零的组合元素索引的集合$

1.3 分解机模型

$$\varnothing \left(w,x\right)=w^{T}x=w_0+\sum _{j\in C_1}{w}_j{x}_j+\sum _{j1,j2\in C_2}⟨{\mathbf{w}}_{j1},{\mathbf{w}}_{j2}⟩x_{j1}{x}_{j2}----(3)$$

$\mathbf{w}是二维矩阵，{\mathbf{w}}_i表示第i行向量，长度为k，k是用户自定义的参数，也称之为隐变量$

1.4 域分解机模型

$$\varnothing \left(w,x\right)=w^{T}x=w_0+\sum _{j\in C_1}{w}_j{x}_j+\sum _{j1,j2\in C_2}⟨{\mathbf{w}}_{j1,f_{j2}},{\mathbf{w}}_{j2,f_{j1}}⟩x_{j1}{x}_{j2}----(4)$$

因为线性项$$w_0+\sum _{j\in C_1}{w}_j{x}_j$$在训练过程中非常容易计算，所以可以先将其忽略，只需要研究$$\sum _{j1,j2\in C_2}⟨{\mathbf{w}}_{j1,f_{j2}},{\mathbf{w}}_{j2,f_{j1}}⟩x_{j1}{x}_{j2}$$，将其写成另一种形式

$$\sum _{i=1}^n\sum _{j=i+1}^n⟨{\mathbf{w}}_{i,f_j},{\mathbf{w}}_{j,f_i}⟩x_i{x}_j----(5)$$

1.5 基于FFM的逻辑回归模型

1.5.1 -1，1损失的逻辑回归模型

$$\underset{w}{\min }\sum _{p=1}^L\left(\log \left(1+exp\left(-y_p\varnothing \left(\mathbf{w},x_p\right)\right)\right)+\frac{\lambda }{2}{\Vert \mathbf{w}\Vert }^2\right)----(6)$$

其中

$$\varnothing \left(\mathbf{w},x_p\right)=\sum _{i=1}^n\sum _{j=i+1}^n⟨{\mathbf{w}}_{i,f_{p,j}},{\mathbf{w}}_{j,f_{p,i}}⟩x_{p,i}{x}_{p,j}----(7)$$

令

$$L\left(x_p,y_p\right)=log\left(1+exp\left(-y_p\varnothing \left(\mathbf{w},x_p\right)\right)\right)+\frac{\lambda }{2}{\Vert \mathbf{w}\Vert }^2----(8)$$

其为每个样本的损失函数。

$L\left(x_p,y_p\right)对参数\mathbf{w}的导数为：$

$$\frac{\partial L\left(x_p,y_p\right)}{\partial \mathbf{w}}=\frac{-y_p\exp \left(-y_p\varnothing \left(\mathbf{w},x_p\right)\right)}{1+exp\left(-y_p\varnothing \left(\mathbf{w},x_p\right)\right)}\frac{\partial \varnothing \left(\mathbf{w},x_p\right)}{\partial \mathbf{w}}+\lambda \mathbf{w}----(9)$$

在式（8）的导数计算公式中，$$\frac{-y_p\exp \left(-y_p\varnothing \left(\mathbf{w},x_p\right)\right)}{1+exp\left(-y_p\varnothing \left(\mathbf{w},x_p\right)\right)}$$是标量，对于每个样本只要按照式（7）计算即可，第二项$$\lambda \mathbf{w}$$用惩罚参数乘以对应的参数即可，比较麻烦的就是$$\frac{\partial \varnothing \left(\mathbf{w},x_p\right)}{\partial \mathbf{w}}$$的计算。

1.5.2 $\varnothing \left(\mathbf{w},{\mathbf{x}}_{\mathbf{p}}\right)$的求导过程$

为了便于理解首先对$$⟨{\mathbf{w}}_{i,f_{p,j}},{\mathbf{w}}_{j,f_{p,i}}⟩x_{p,i}{x}_{p,j}$$中的$${\mathbf{w}}_{i,f_{p,j}}$$和$${\mathbf{w}}_{j,f_{p,i}}$$分别的偏导数如下

$$\frac{\partial ⟨{\mathbf{w}}_{i,f_{p,j}},{\mathbf{w}}_{j,f_{p,i}}⟩x_{p,i}{x}_{p,j}}{\partial {\mathbf{w}}_{i,f_{p,j}}}={\mathbf{w}}_{j,f_{p,i}}{x}_{p,i}{x}_{p,j}----(10)$$

$$\frac{\partial ⟨{\mathbf{w}}_{i,f_{p,j}},{\mathbf{w}}_{j,f_{p,i}}⟩x_{p,i}{x}_{p,j}}{{\mathbf{w}}_{j,f_{p,i}}}={\mathbf{w}}_{i,f_{p,j}}{x}_{p,i}{x}_{p,j}----(11)$$

$$所以\varnothing \left(\mathbf{w},x_p\right)对{\mathbf{w}}_{i,f_{p,j}}和{\mathbf{w}}_{j,f_{p,i}}的偏导数分别如下$$

$$\frac{\partial \varnothing \left(\mathbf{w},x_p\right)}{\partial {\mathbf{w}}_{i,f_{p,j}}}=\sum _{i=1}^n\sum _{j=i+1}^n{\mathbf{w}}_{j,f_{p,i}}{x}_{p,i}{x}_{p,j}----(12)$$

$$\frac{\partial \varnothing \left(\mathbf{w},x_p\right)}{\partial {\mathbf{w}}_{j,f_{p,i}}}=\sum _{i=1}^n\sum _{j=i+1}^n{\mathbf{w}}_{i,f_{p,j}}{x}_{p,i}{x}_{p,j}----(13)$$

假设有如下的例子，五个特征，两个域

$按照式（7），去掉下标p，计算图1中所示的分解模型，如下$

$$\varnothing \left(\mathbf{w},x\right)=\sum _{i=1}^5\sum _{j=i+1}^5⟨{\mathbf{w}}_{i,f_j},{\mathbf{w}}_{j,f_i}⟩x_i{x}_j$$

$$=⟨{\mathbf{w}}_{1,f_1},{\mathbf{w}}_{2,f_1}⟩x_1{x}_2+⟨{\mathbf{w}}_{1,f_1},{\mathbf{w}}_{3,f_1}⟩x_1{x}_3+⟨{\mathbf{w}}_{1,f_2},{\mathbf{w}}_{4,f_1}⟩x_1{x}_4+⟨{\mathbf{w}}_{1,f_2},{\mathbf{w}}_{5,f_1}⟩x_1{x}_5$$

$$

• \left\langle \mathbf{w}{2,f{1}},\mathbf{w}{3,f{1}} \right\rangle x_{2}x_{3} + \left\langle \mathbf{w}{2,f{2}},\mathbf{w}{4,f{1}} \right\rangle x_{2}x_{4} + \left\langle \mathbf{w}{2,f{2}},\mathbf{w}{5,f{1}} \right\rangle x_{2}x_{5}
  $$

$$

• \left\langle \mathbf{w}{3,f{2}},\mathbf{w}{4,f{1}} \right\rangle x_{3}x_{4} + \left\langle \mathbf{w}{3,f{2}},\mathbf{w}{5,f{1}} \right\rangle x_{3}x_{5}
  $$

$$

• \left\langle \mathbf{w}{4,f{2}},\mathbf{w}{5,f{2}} \right\rangle x_{4}x_{5}
  $$

$从上式中抽取i=1,f_j=1和i=3,f_j=2$

$$\frac{\partial \varnothing \left(\mathbf{w},x\right)}{\partial {\mathbf{w}}_{1,f_1}}={\mathbf{w}}_{2,f_1}{x}_1{x}_2+{\mathbf{w}}_{3,f_1}{x}_1{x}_3$$

$$\frac{\partial \varnothing \left(\mathbf{w},x\right)}{\partial {\mathbf{w}}_{3,f_2}}={\mathbf{w}}_{4,f_1}{x}_3{x}_4+{\mathbf{w}}_{5,f_1}{x}_3{x}_5$$

在模型学习时，需要迭代公式$$\mathbf{w}=\mathbf{w}+\eta \mathbf{g}$$，$$\eta ,\mathbf{g}$$分别为学习率和梯度向量，则在计算$${\mathbf{w}}_{3,f_2}$$时有两种方式：

方式1：

$${\mathbf{w}}_{3,f_2}={\mathbf{w}}_{3,f_2}+\eta \left({\mathbf{w}}_{4,f_1}{x}_3{x}_4+{\mathbf{w}}_{5,f_1}{x}_3{x}_5\right)$$

方式2：

$${\mathbf{w}}_{3,f_2}={\mathbf{w}}_{3,f_2}+{\eta }_1\left({\mathbf{w}}_{4,f_1}{x}_3{x}_4\right)$$

$${\mathbf{w}}_{3,f_2}={\mathbf{w}}_{3,f_2}+{\eta }_2\left({\mathbf{w}}_{5,f_1}{x}_3{x}_5\right)$$

$因为采用的是AdaGrad所以学习率\eta 在方式二中是变化的。$

在学习过程中是采用方式1还是方式2哪。答案是方式2。因为在计算实际问题时可能特征分布在多个域中，如果按照方式1则需要把每个域中的信息累加起来，结果是编程上非常麻烦，如果按照方式2，非常符合SGD的思想，把${\mathbf{w}}_{4,f_1}{x}_3{x}_4$和${\mathbf{w}}_{5,f_1}{x}_3{x}_5$看成两个样本，再带回到$x_3{x}_4$组合时更新下${\mathbf{w}}_{3,f_2}$，当访问到$x_3{x}_5$组合时再次更新下${\mathbf{w}}_{3,f_2}$，在实际编程中，具体更新哪些参数可以通过相应的索引进行访问，非常方便。

2 libFFM介绍

2.1 使用介绍

1）编译
下载libffm-1.13.tar.gz，解压，在libffm-1.13下直接make，会产生两个可执行的文件ffm-train和ffm-predict分别用于训练和预测结果。
2）输入数据格式

<label>\t<field1>:<index1>:<value1>\t<field2>:<index2>:<value2>\t...
fieldi表示域的id，indexi表示特征的id，它们都是非负值。
0 1:7759:0.3651 2:7921:0.3651 3:8661:0.3651 4:9619:0.3651
1 1:7633:0.3651 2:8195:0.3651 3:9952:0.3651 4:9619:0.3651
**注意：**libFFM中使用的是“-1，1”损失函数，所以label只能取-1或者1，而这里的样例数据中目标是0、1。因为在libFFM中读取数据时将大于0的目标当成1，小于等于0的当成-1。所以数据中的0、1并不表示损失是0，1。 |

3）命令行调用方式
训练：ffm-train [options] training_set_file [model_file]
options控制参数如下表

$$表1options控制参数解释$$

说明：

• –no-norm：缺省状态时用每个样本向量的2范数对样本中的每个元素进行归一化，如果设置了这个参数，则不进行归一化处理。
• –no-rand：缺省状态训练时随机从数据中选取训练样本，如果不想随机的抽取训练样本，而是想按照数据集中的样本顺序训练，则可以使用此参数，同时还要配合参数”-s
  1”使用。
• –on-disk：如果训练数据较大内存无法加载全量数据，则可以使用此参数。需要注意的是，这种训练模式下不支持随机的抽取训练数据，所以此时需要设置参数“—no-rand”，同时这种模式下不支持交叉验证。同时还会在磁盘上产生临时的二进制文件[training_set_file].bin。

**预测**：
**ffm-predict** test\_file model\_file output\_file

作者给的几个例子

- 使用缺省参数训练模型

     - ffm-train bigdata.tr.txt model

- 使用如下参数训练模型
    - regularization cost = 0.001
    - latent factors = 16
    - iterations = 30
    - learning rate = 0.05
    - threads = 4
    - ffm-train -l 0.001 -k 16 -t 30 -r 0.05 -s 4 bigdata.tr.txt model
- 使用bigdata.te.txt作为validation数据
    - ffm-train -p bigdata.te.txt bigdata.tr.txt model
- 使用5折交叉验证
   - ffm-train -v 5 bigdata.tr.txt
- 用--quiet参数训练时不打印训练信息
   - ffm-train --quiet bigdata.tr.txt
- 预测
 -ffm-predict bigdata.te.txt model output

- 基于磁盘的训练

ffm-train --no-rand --on-disk bigdata.tr.txt

- 使用--auto-stop参数，当达到最优的validation损失时停止训练

ffm-train -p bigdata.te.txt -t 100 bigdata.tr.txt


### 2.2 源码分析

#### 2.2.1 存储模型用到的数据结构

- 存储特征的结构体如下
$$f表示域id，j表示特征id，v表示特征的值$$

<div align=center>
![这里写图片描述](https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwMTIwMTE0MjE5MzA2?x-oss-process=image/format,png)
图2 

- 存储整个训练数据集的结构体如下
$m表示特征个数；l表示样本可是，即训练数据的行数；m表示域的个数；X存储训练数据中非零特征；P用来记录X中每个样本数据的起始位置和结束位置；Y存储样本数据的标签值$
<div align=center>
![这里写图片描述](https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwMTIwMTE0NDUyNzc1?x-oss-process=image/format,png)
图3
- $下面介绍X和Y的存储格式$

<div align=center>
![这里写图片描述](https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwMTIwMTE0NzE0MDIz?x-oss-process=image/format,png)
图4

- 存储模型结构体如下：下面会主要介绍W的结构
<div align=center>
![这里写图片描述](https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwMTIwMTE0NzU2NjAy?x-oss-process=image/format,png)
图5

- $W的存储格式如下$
<div align=center>
![这里写图片描述](https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwMTIwMTE0ODU0NzQ3?x-oss-process=image/format,png)
图6

-----
#### 2.2.2 训练

- 主要的训练方法为

shared_ptr<ffm_model> train(ffm_problem *tr,vector<ffm_int> &order, ffm_parameter param,   ffm_problem *va=nullptr)
在该方法中采用AdaGrad对每个样本进行训练。值得一提的是该方法中采用OpenMP和SSE进行加速，为了理解加速的位置，下面将伪码写出


for i = 0:l   //l为特征个数
	ffm_float t = wTx(xi, model);
     	ffm_float expnyt = exp(-y*t);
    	tr_loss += log(1+expnyt);
     	ffm_float kappa = -y*expnyt/(1+expnyt);
    	wTx(begin, end, r, *model, kappa, param.eta, param.lambda, true);
end

- 下面两条获得进程数
ffm_int old_nr_threads = omp_get_num_threads();
omp_set_num_threads(param.nr_threads);
下面的指令使多线程中的ffm_float t = wTx(xi, model);
     ffm_float expnyt = exp(-y*t);结果，在tr_loss += log(1+expnyt);出合并然后继续下面的过线程
**#pragma omp parallel for schedule(static) reduction(+: tr_loss)**

<div align=center>
![这里写图片描述](https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwMTIwMTE1NTUxNDA5?x-oss-process=image/format,png)


- libFFM中加速技术概述
<div align=center>
![这里写图片描述](https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwMTIwMTE1NjQyMzY0?x-oss-process=image/format,png)
图7

**OpenMP**

代码被多个线程并行执行
<div align=center>
![这里写图片描述](https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwMTIwMTE1ODExMDIy?x-oss-process=image/format,png)
图8

for循环被发送到多个线程执行
<div align=center>
![这里写图片描述](https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwMTIwMTE1OTE5MTAy?x-oss-process=image/format,png)
图9

for循环先被发送到多个线程，接着合并，然后再次被分发
<div align=center>
![这里写图片描述](https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwMTIwMTIwMDMxMzQ1?x-oss-process=image/format,png)
图10

对比加速图
<div align=center>
![这里写图片描述](https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwMTIwMTIwMTA5NDAx?x-oss-process=image/format,png)
图11

**SSE**
 
SSE(Streaming SIMD Extensions)/AVX(Advanced Vector Extensions)是Intel公司设计，对其X86体系的SIMD扩展指令集，它基于SIMD向量化技术，增强X86多核处理器的图像和视频处理能力
常用指令如下
_mm_load_ps   从数组中读取向量到寄存器
_mm_store_ps   将寄存器中的向量存储到数组
_mm_add_ps   寄存器中的向量相加
_mm_sub_ps    寄存器中的向量相减
_mm_mul_ps    寄存器中的向量相乘
_mm_rsqrt_ps    寄存器中的向量开方倒数
<div align=center>
![这里写图片描述](https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcwMTIwMTIwMjMzMTg0?x-oss-process=image/format,png)
图12