推荐算法学习（八）：因子分解机

在使用MF解决评分预测问题时，我们仅考虑了user和item特征，但实际上一个预测问题包含的特征维度可能很多，如评分时间、用户信息等。FM算法则可用于解决此类预测问题，包括回归问题及二分类问题。

FM

普通线性模型将各个特征独立考虑，并没有考虑特征之间的相互关系，为了表述特征间的相关性，采用多项式模型，这里只讨论二阶多项式模型（只考虑二阶特征组合，即两个特征变量之间的交互影响）。对于特征向量，目标预估函数为：

使用$w_{ij}$进行二阶特征组合的参数估计存在问题，即如果观察样本中没有出现过该交互的特征分量（数据稀疏），那么直接估计将为0。对于$w_{ij}$的估计，可转换成矩阵分解MF问题：

其中，直接计算，复杂度为O($k*n^2$)，n是特征个数，k是特征的embedding size。通过公式变换，可将复杂度由，变换过程如下（并不需要对于每个特征和不同特征交叉时都估计一个辅助向量，而是只用对每个特征单独估计一个k维辅助向量即可。这里k维辅助向量类似于词向量，但是和词向量存在区别，词向量中是将一个单词转换为向量表示形式，而单词是固定的，因此一个单词对应一个词向量；而在FM中，我们是将一个类别特征onehot后的每一个特征分量映射到一个向量）：

FM与MF的区别在于：1）MF是FM的特例，即MF是特征只有User ID 和Item ID的FM模型；2）FM矩阵将User和Item（离散特征）都进行了one-hot编码作为特征，使得特征维度非常巨大且稀疏；3）矩阵分解MF只适用于评分预测，进行简单的特征计算，无法利用其他特征；4）FM引入了更多辅助信息（Side information）作为特征；5）FM在计算二阶特征组合系数的时候，使用了MF。

CTR预估是个二分类问题,使用线性模型无法学习到特征之间的相关性，运用FM则可考虑到”性别“+“年龄”特征交叉情况对点击率的影响，从而提高预估准确性。

FM的学习算法主要有：1）ALS，交替最小二乘法；2）MCMC，马尔科夫链蒙特卡罗法；3）SGD，随机梯度下降法：

考虑D个特征交叉的FM算法成为D-阶FM算法，但由于计算量大，一般FM采用2阶特征组合的方式，实际上高阶/非线性的特征组合适合采用深度模型。 $w_{ij}=<v_i,v_j>$是FM的核心思想，使得稀疏数据下学习不充分的问题也能得到充分解决。

FFM

FM有唯一一个隐向量用来学习与其他任意特征间的影响。FFM引入field的概念，把相同性质的特征归于同一个field，比如“Day=26/11/15”、“Day=1/7/14”、“Day=19/2/15”这三个特征代表日期，放到同一个field中。属于不同的领域的特征，它们的隐性影响应该是不一样的。例如，当“Day=26/11/15”与Country特征，Ad_type特征进行特征组合时，由于Country特征和Ad_type特征的field不同，FFM算法则使用不同的隐向量（Field-aware）。

对于FFM算法：

FFM算法每个特征会有几个不同的隐向量，fj 是第 j 个特征所属的field，使用哪个取决于和哪个向量进行点乘。FM算法可以看做是FFM算法的一个特例。

FFM算法中隐向量的长度为 k，FFM的二次参数有 nfk 个，多于FM模型的 nk 个，由于隐向量与field相关，FFM二次项并不能够化简，计算复杂度是 O($k*n^2$)，FFM的k值一般远小于FM的k值。

FFM算法中特征格式记为：field_id：feat_id：value，field_id代表field编号，feat_id代表特征编号，value是特征值。若特征为数值型，只需分配单独的field编号，比如评分，item的历史CTR/CVR等。若特征为分类（categorical）特征，需要经过One-Hot编码成数值型，编码产生的所有特征同属于一个field，其特征值是0或1，比如性别、商品的品类id等。

DeepFM算法

DeepFM是将Deep与FM相结合：，用FM做特征间低阶组合，用DNN部分做特征间高阶组合，采用end-to-end模型结构共享模型输入，无须人工特征工程。其架构如下：

上图左侧为FM的结构层，右侧为Deep部分的结构层，两者公用相同的特征输入。对于特征i，wi是1阶特征的权重，Vi表示该特征与其他特征的交互影响，输入到FM模型中可以获得特征的2阶特征表示，输入到DNN模型得到高阶特征。

FM模型计算的过程为：

Deep模型：由于原始特征向量维度非常大，高度稀疏，为了更好的发挥DNN模型学习高阶特征的能力，设计子网络结构（从输入层=>嵌入层），将原始的稀疏表示特征映射为稠密的特征向量，Deep模型结构如下图所示。

输入层=>嵌入层：不同field特征长度不同，但是子网络输出的向量具有相同维度k，利用FM模型的隐特征向量V作为网络权重初始化来获得子网络输出向量。

Embedding：一种降维方式，将不同特征转换为维度相同的向量。在推荐系统中，对于离线变量我们需要转换成one-hot ，维度非常高，可以将其转换为k维embedding向量：。方法为：接入全连接层，对于每个Field只有一个位置为1，其余为0，因此得到的embedding就是图中连接的红线，对于Field 1来说就是，FM模型和Deep模型中的子网络权重共享，也就是对于同一个特征，向量Vi是相同的。

DeepFM中的模块：

Sparse Features，输入多个稀疏特征
Dense Embeddings，对每个稀疏特征做embedding，学习到他们的embedding向量(维度相等，均为k），因为需要将这些embedding向量送到FM层做内积。同时embedding进行了降维，更好发挥Deep Layer的高阶特征学习能力
FM Layer，一阶特征：原始特征相加，二阶特征：原始特征embedding后的embedding向量两两内积
Deep Layer，将每个embedding向量做级联，然后做多层的全连接，学习更深的特征
Output Units，将FM层输出与Deep层输出进行级联，接一个dense层，作为最终输出结果

很多特征，在高阶情况下，人很难理解，但是机器可以发现规律（使用DNN模型），DeepFM采用FM+DNN的方式，在低阶和高阶特征组合上更接近真实世界，因此效果也更好。

实例1：使用libfm工具对movielens进行评分预测

数据集：movielens数据集中ratings.csv
使用libfm工具，将数据格式转换为libsvm格式，libfm进行训练（采用SDG优化算法），输出结果文件 out.txt

代码：https://github.com/Alice1214/RS/tree/master/RS07/libfm

实例2：使用DeepFM对movielens进行评分预测

数据集：movielens
对数据进行预处理（对特征标签进行编码，将数据集切分成训练集和测试集），使用deepctr工具，运用DeepFM算法进行训练，并预测评分

代码：https://github.com/Alice1214/RS/tree/master/RS07/deepfm

FM

FFM

DeepFM算法

相关工具

实例1：使用libfm工具对movielens进行评分预测

实例2：使用DeepFM对movielens进行评分预测