Factorization Machines

参考

1. 刘建平的博客: https://www.cnblogs.com/pinard/p/6370127.html

2. Tracholar的博客: https://tracholar.github.io/machine-learning/2017/03/10/factorization-machine.html

3. 知乎小孩不笨的文章: https://zhuanlan.zhihu.com/p/50426292

1 准备

通常，我们的机器学习模型是学习一个映射函数
$f(\cdot) \rightarrow T$f(⋅)→T

该函数使我们输入的n维实值特征向量 $x \in R^n$x∈Rn 映射到一个目标域$T$T，例如对与回归问题，这个目标域$T = R$T=R，而对于分类问题，$T = \{C1, C2, ..., C_n\}$T={C1,C2,...,Cn​}。在常见的有监督学习任务中，我们的训练样本数据通常还带有一个标签$y$y，数据格式如：

$D = \{(x^{(1)},y^{(1)}), (x^{(2)},y^{(2)}), ..., (x^{(m)},y^{(m)})\}$D={(x(1),y(1)),(x(2),y(2)),...,(x(m),y(m))}

其中$x^{(i)} \in R^n$x(i)∈Rn为输入数据，对应样本的特征向量，$y^{(i)}$y(i)对应该样本的标签，$m$m为样本的数目。

在现实世界中，许多应用问题（如文本分析、推荐系统等）会产生高度稀疏的（特征）数据，即特征向量$x^{(i)}$x(i)中几乎所有的分量都为0

这里，我们以电影评分系统为例，给出一个关于高度稀疏数据的实例:

关于这个数据各部分含义这里不再解释。

在上面的例子中，特征向量x的实际维度为$|U|+|I|+|I|+1+|I| = |U|+3|I|+1$∣U∣+∣I∣+∣I∣+1+∣I∣=∣U∣+3∣I∣+1，真实场景中，用户数目$|U|$∣U∣与电影数目$|I|$∣I∣都非常大，而每个用户对电影的评分数目非常有限。以此可知我们的特征向量x将会多么的稀疏，用$N_z(X)$Nz​(X)来表示一条样本数据/特征向量x的非0分量个数，并记：

$\overline{N_z}(X) = \frac{1}{N} \sum_i^m N_z(x^{(i)})$Nz​​(X)=N1​i∑m​Nz​(x(i))

$\overline{N_z}(X)$Nz​​(X)表示训练集D中所有特征向量中非零分量数的平均数，显然，对于稀疏数据$\overline{N_z}(X) << m$Nz​​(X)<<m

2 FM二阶模型方程

对于上面提到的样本数据D，我们先回顾一下线性回归的做法：

$\hat{y} = w_0 + w_1x_1 + ... + w_nx_n$y^​=w0​+w1​x1​+...+wn​xn​

$= w_0 + \sum_{i=1}^n w_i x_i$=w0​+i=1∑n​wi​xi​

如果我们采用单一的线性模型来学习用户的点击，打分习惯，各特征分量是相互独立的，没有考虑特征分量之间的相互关系，我们很容易忽略特征中潜在的组合关系，比方说“男性用户”喜欢看“漫威电影”，买“奶粉”的用户也常常买“尿不湿”等等。

为了学习特征间的交叉，SVM通过多项式核函数来实现特征的交叉，实际上和多项式模型是一样的，问题在于二阶项的参数过多，设特征维数为n，那么二阶项的参数数目为$\frac{n(n+1)}{2}$2n(n+1)​，对于广告点击率预估问题，由于存在大量id特征，导致 n 可能为 $10^7$107维，这样一来，模型参数的量级为$10^{14}$1014，这导致只有极少数的二阶组合模式才能在样本中找到， 而绝大多数模式在样本中找不到，因而模型无法学出对应的权重。例如，对于某个$w_{ij}$wij​，样本中找不到$x_i=1,x_j=1$xi​=1,xj​=1 （这里假定所有的特征都是离散的特征，只取0和1两个值）这种样本，那么wij的梯度恒为0，从而导致参数学习失败！

很容易想到，可以对二阶项参数施加某种限制，减少模型参数的自由度。FM 施加的限制是要求二阶项系数矩阵是低秩的，能够分解为低秩矩阵的乘积。

下面我们做改进：

$\hat{y} = 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$y^​=w0​+i=1∑n​wi​xi​+i=1∑n−1​j=i+1∑n​wij​xi​xj​

上式将任意两个互异的分量之间的关系也考虑进来了。接下来对二阶项参数$w_{ij}$wij​进行改进。针对每个维度的特征$x_i$xi​，引入辅助向量(相当于给每个特征一个隐向量)$v_i$vi​，(注意是对每一个特征，$x_i$xi​是一个特征分量，引入一个向量)，从而将$w_{ij}$wij​表示为$v_i与v_j$vi​与vj​内积的形式。其中：

$v_i = (v_{i1},v_{i2},...,v_{ik}) \in R^k, i = 1, 2,..,n$vi​=(vi1​,vi2​,...,vik​)∈Rk,i=1,2,..,n

这里的$n$n对应一条样本数据中的特征数目$n$n，$k$k对应每个特征要表示为k维的辅助向量(隐向量)，是一个可调节的超参数。则$w_{ij}$wij​应表示为：

$\hat{w}_{ij} = v_i^T v_j := \sum_l^k v_{il} v_{jl}$w^ij​=viT​vj​:=l∑k​vil​vjl​

这样就将参数个数减少到 kn，可以设置较少的k值（一般设置在100以内，k << n），极大地减少模型参数，增强模型泛化能力，这跟矩阵分解的方法是一样的。但是这样为什么说可以提高模型的泛化能力呢？

以上述电影评分系统为例，假设我们要计算用户$A$A与电影$ST$ST的交叉项，很显然，训练数据里没有这种情况，这样会导致 $w_{A,ST}=0$wA,ST​=0 ，但是我们可以近似计算出 $<V_A,V_{ST}>$<VA​,VST​> 。首先，用户 $B$B 和 $B$B 有相似的向量 $V_B$VB​ 和 $V_C$VC​ ，因为他们对 $SW$SW 的预测评分比较相似， 所以$<V_B,V_{SW}>$<VB​,VSW​> 和 $<V_C,V_{SW}>$<VC​,VSW​> 是相似的。用户 $A$A 和 $C$C 有不同的向量，因为对 $TI$TI 和 $SW$SW 的预测评分完全不同。接下来， $ST$ST 和 $SW$SW 的向量可能相似，因为用户 $B$B 对这两部电影的评分也相似。最后可以看出， $<V_A,V_{ST}>$<VA​,VST​> 与 $<V_A,V_{SW}>$<VA​,VSW​> 是相似的。

于是，函数$\hat{y}$y^​可以进一步改写为：

$\hat{y}(x) = w_0 + \sum_{i=1}^n w_ix_i + \sum_{i=1}^{n-1} \sum_{j=i+1}^n <v_i^T, v_j> x_i x_j$y^​(x)=w0​+i=1∑n​wi​xi​+i=1∑n−1​j=i+1∑n​<viT​,vj​>xi​xj​

这就是FM的模型方程。

3 复杂度分析与化简

FM模型的方程中，参数包括：

$w_0 \in R, W \in R^n, V \in R^{n \times k}$w0​∈R,W∈Rn,V∈Rn×k

共有$1+n+n \times k$1+n+n×k个参数，其中$w_0$w0​为整体的偏置，$W$W为各特征分量$x_i$xi​的参数向量，$V$V为交叉特征的参数向量矩阵，函数的计算复杂度为：

$\{n+(n-1)\}+\left\{\frac{n(n-1)}{2}[k+(k-1)+2]+\frac{n(n-1)}{2}-1\right\}+2=\mathcal{O}\left(k n^{2}\right)${n+(n−1)}+{2n(n−1)​[k+(k−1)+2]+2n(n−1)​−1}+2=O(kn2)

第一个花括号内对应$\sum_{i=1}^n w_ix_i$∑i=1n​wi​xi​的加法和乘法操作，第二个花括号内对应$\sum_{i=1}^{n-1} \sum_{j=i+1}^n <v_i^T, v_j> x_i x_j$∑i=1n−1​∑j=i+1n​<viT​,vj​>xi​xj​的加法和乘法操作。

我们对方程进行改写约简，即可将计算复杂度降到$O(kn)$O(kn)，推导过程如下：

$\sum_{i=1}^{n} \sum_{j=i+1}^{n}<v_{i}, v_{j}>x_{i} x_{j}$i=1∑n​j=i+1∑n​<vi​,vj​>xi​xj​

$=\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n}<v_{i}, v_{j}>x_{i} x_{j}-\frac{1}{2} \sum_{i=1}^{n}<v_{i}, v_{i}>x_{i} x_{i}$=21​i=1∑n​j=1∑n​<vi​,vj​>xi​xj​−21​i=1∑n​<vi​,vi​>xi​xi​

$=\frac{1}{2}\left(\sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{f=1}^{k} v_{i, f} v_{j, f} x_{i} x_{j}-\sum_{i=1}^{n} \sum_{f=1}^{k} v_{i, f} v_{i, f} x_{i} x_{i}\right)$=21​⎝⎛​i=1∑n​j=1∑n​f=1∑k​vi,f​vj,f​xi​xj​−i=1∑n​f=1∑k​vi,f​vi,f​xi​xi​⎠⎞​

$=\frac{1}{2} \sum_{f=1}^{k}\left(\left(\sum_{i=1}^{n} v_{i, f} x_{i}\right)\left(\sum_{j=1}^{n} v_{j, f} x_{j}\right)-\sum_{i=1}^{n} v_{i, f}^{2} x_{i}^{2}\right)$=21​f=1∑k​((i=1∑n​vi,f​xi​)(j=1∑n​vj,f​xj​)−i=1∑n​vi,f2​xi2​)

$=\frac{1}{2} \sum_{f=1}^{k}\left(\left(\sum_{i=1}^{n} v_{i, f} x_{i}\right)^{2}-\sum_{i=1}^{n} v_{i, f}^{2} x_{i}^{2}\right)$=21​f=1∑k​⎝⎛​(i=1∑n​vi,f​xi​)2−i=1∑n​vi,f2​xi2​⎠⎞​

可以计算出，上式的计算复杂度为

$k\{[n + (n-1) + 1] + [3n + (n-1)] + 1\} + (k-1) + 1 = O(kn)$k{[n+(n−1)+1]+[3n+(n−1)]+1}+(k−1)+1=O(kn)

需要注意的是：在高度稀疏的数据集中，特征向量X中绝大部分分量为0，即文章开始我们引入的$N_z(X)$Nz​(X)会很小，于是计算复杂度为$O(k N_z(X))$O(kNz​(X))，对整个数据集D而言，平均计算复杂度为：$O(k \overline{N_z}(X))$O(kNz​​(X))

4 推广高阶

$\hat{y}(x)=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{l=2}^{d} \sum_{i_{1}=1}^{n-(l-1)} \sum_{i_2=i_1+1}^{n-(l-2)} \ldots \sum_{i_{l}=i_{l-1}+1}^{n}\left(\prod_{j=1}^{l} x_{i_{j}}\right)\left(\sum_{f=1}^{k_{l}} \sum_{j=1}^{l} v_{i_{j}, f}^{(l)}\right)$y^​(x)=w0​+i=1∑n​wi​xi​+l=2∑d​i1​=1∑n−(l−1)​i2​=i1​+1∑n−(l−2)​…il​=il−1​+1∑n​(j=1∏l​xij​​)⎝⎛​f=1∑kl​​j=1∑l​vij​,f(l)​⎠⎞​

详细理解见最上方参考文献。

5 回归与分类任务的损失函数

5.1 回归问题

回归问题常用的衡量损失的函数有最小平方误差(LSE)、均方差(MSE)，均方根误差(RMSE)、平均绝对误差(MAE)，这里以最小平方误差为例：

$loss(\hat{y},y) = (\hat{y}-y)^2$loss(y^​,y)=(y^​−y)2

5.2 二分类

01损失，交叉熵损失函数等

6 优化方法

6.1 梯度下降

对SGD超参数的讨论：

1. 学习率$\eta$η: SGD的收敛依赖于$\eta$η的取值，$\eta$η太大，则可能不收敛；太小，则收敛会很慢，因此这个参数要取得合适
2. 正则化系数$\lambda$λ: FM模型的泛化能力（相应的预测质量）很大程度上依赖于这些正则化系数的选取。它们通常是在单独的 holdout set上通过 grid search方法来获取，由于它们个数多，取值区间大，因此，通过 grid search方法来选取会非常费时。一种提高效率的做法是减少它们的个数。例如，可以考虑让矩阵V中行号经$\pi$π映射后为同一个值的那些行使用同一个正则化系数。此时，正则化系数集$\lambda$λ变为$\lambda^{0}, \quad \lambda_{\pi(i)}^{w}, \quad \lambda_{\pi(i)}^{v}, \quad i \in\{1,2, \cdots, n\}$λ0,λπ(i)w​,λπ(i)v​,i∈{1,2,⋯,n}
3. 正态分布方差参数$\sigma$σ: 矩阵V的初始化采用符合正态分布$N(0,\sigma)$N(0,σ)的随机初始化，方差参数$\sigma$σ通常取得很小

7 FM与MF的关系

FM包含矩阵分解的模型，矩阵分解的模型是FM的一个特例，当特征只剩下userID和itemID时，FM就退化成了MF。

以user对item评分预测问题为例，基于矩阵分解的协同过滤可以看做FM的一个特殊例子，对于每一个样本，FM可以看做特征只有userid和itemid的onehot编码后的向量连接而成的向量。从FM和MFCF公式来看，MFCF的用户embedding和item embedding可以看做FM中的隐向量，用户和item的bias向量就是FM中的一次项系数，常数μ也和FM中的常数$w_0$w0​相对应，可以看到，MFCF就是FM的一个特例！另外，FM可以采用更多的特征，学习更多的组合模式，这是单个矩阵分解的模型所做不到的！因此，FM比矩阵分解的方法更具普遍性！事实上，现在能用矩阵分解的方法做的方案都直接上FM了!

另外，FM与决策树，FM与神经网络的关系请参考参考文献2