因式分解机（Factorization Machines，FM ）

• 前言
• FM背景
• FM模型
• FM算法详解
• FM模型为什么优于多项式和线性模型

前言

FM全称为factorization machine, 可以用解决回归、二分类问题
FM主要是考虑了特征之间的关联。
目的：解决高维稀疏数据中特征组合问题，适用于categorical feature。

背景

强调一点，FM的适用对象是稀疏数据。
任何研究过点击预测问题或推荐系统的人都会面临类似的情况：由于数据集非常庞大，因此使用有限的计算资源对这些数据集进行预测变得非常困难。

但是，在大多数情况下，这些数据集是稀疏的（每个训练示例只有少数变量为非零）。在数据稀疏的情况下，满足求解参数都不为0的情况很少，所以很难训练。然而因子分解机有助于从从现有的原始数据中，提取最重要的潜在的或隐藏的特征。

一般来说，可以使用低维密集矩阵来表示对象和预测器之间关系，而分解有助于与前者建立大致相同的关联。

FM模型

一般的线性模型为（n表示n维特征）：
$y = w_0+ \sum_{i=1}^nw_ix_i$y=w0​+i=1∑n​wi​xi​

如果在线性模型中加入二阶特征的组合，那么会是这个样子的
$\hat y(x) =w_0 + \sum_{i=1}^nw_ix_i + \sum_{i=1}^{n-1}\sum_{j=i+1}^nw_{ij}x_ix_j$y^​(x)=w0​+i=1∑n​wi​xi​+i=1∑n−1​j=i+1∑n​wij​xi​xj​
$\begin{Bmatrix} w_{11}& w_{12} & ... & w_{1n}\\ w_{21}& w_{22} & ... & w_{2n}\\ ...& ... & ... & ...\\ w_{n1}& w_{n2} & ... & w_{nn} \end{Bmatrix}$⎩⎪⎪⎨⎪⎪⎧​w11​w21​...wn1​​w12​w22​...wn2​​............​w1n​w2n​...wnn​​⎭⎪⎪⎬⎪⎪⎫​
注：$x_i$xi​表示第i个特征，$w_{ij}$wij​是组合参数，其中$w_{ij}$wij​和$w_{ji}$wji​是相等的，因此组合特征部分相关参数共有(n-1) + (n-2) + … + 1 = n(n-1)/2。只需要计算上三角或下三角。

在实际问题中，x往往非常稀疏：x中非零个数远远小于n，比如$x = \begin{pmatrix} 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \end{pmatrix}^T$x=(1​0​0​1​0​1​0​1​0​)T
这里存在一个问题，对于稀疏数据来说，$x_i$xi​ 和$x_j$xj​同时不为0的情况非常少，这样会导致$w_{ij}$wij​无法通过训练获得。

为了解决这个问题，FM诞生了，我们看一下FM是如何解决这个问题的：
对每一个特征分量$x_i$xi​引入辅助向量$v_i = (v_{i,1，i,2，....，i,k})$vi​=(vi,1，i,2，....，i,k​)，利用$v_iv_i^T$vi​viT​对交叉项的系数$w_{ij}$wij​进行估计，即令$w_{ij}=v_iv_j^T$wij​=vi​vjT​
$V = \begin{Bmatrix} v_{11}& v_{12} & ... & v_{1k}\\ v_{21}& v_{22} & ... & v_{2k}\\ ...& ... & ... & ...\\ v_{n1}& v_{n2} & ... & v_{nk} \end{Bmatrix} _{n×k} = \begin{Bmatrix} v_1\\ v_2\\ ...\\ v_n\end{Bmatrix}$V=⎩⎪⎪⎨⎪⎪⎧​v11​v21​...vn1​​v12​v22​...vn2​​............​v1k​v2k​...vnk​​⎭⎪⎪⎬⎪⎪⎫​n×k​=⎩⎪⎪⎨⎪⎪⎧​v1​v2​...vn​​⎭⎪⎪⎬⎪⎪⎫​则，
$W = VV^T = \begin{Bmatrix} v_1\\ v_2\\ ...\\ v_n\end{Bmatrix} \begin{Bmatrix} v_1^T & v_2^T & ... & v_n^T\end{Bmatrix}$W=VVT=⎩⎪⎪⎨⎪⎪⎧​v1​v2​...vn​​⎭⎪⎪⎬⎪⎪⎫​{v1T​​v2T​​...​vnT​​}
这就对应了一种矩阵的分解。对k值的限定，对FM的表达能力有一定的影响。

这也解释了FM因式分解机名字的由来，它是将$w_{ij}$wij​进行了拆解。FM的模型为

对于度为2的因式分解机FM的模型为：
$\hat y = w_0 + \sum_{i=1}^nw_ix_i + \sum_{i=1}^{n-1}\sum_{j=i+1}^n\langle v_i,v_j \rangle x_ix_j$y^​=w0​+i=1∑n​wi​xi​+i=1∑n−1​j=i+1∑n​⟨vi​,vj​⟩xi​xj​
其中，参数$w_0 \in \mathbb{R}，w \in \mathbb{R}^n，V \in \mathbb{R}^{n×k}$w0​∈R，w∈Rn，V∈Rn×k。$\langle v_i,v_j \rangle$⟨vi​,vj​⟩表示两个大小为k的向量的$v_i$vi​和向量$v_j$vj​的点积：
$\langle v_i,v_j \rangle = \sum_{f=1}^kv_{i,f}.v_{j,f}$⟨vi​,vj​⟩=f=1∑k​vi,f​.vj,f​
其中，$v_i$vi​表示的是系数矩阵V的第$i$i维向量，且$v_i = (v_{i,1，i,2，....，i,k})，k \in \mathbb{N}^+$vi​=(vi,1，i,2，....，i,k​)，k∈N+称为超参数。在因子分解机FM模型中，前面两部分是传统的线性模型，最后一部分将两个互异特征分量之间的相互关系考虑进来。

因子分解机FM也可以推广到高阶的形式，即将更多互异特征分量之间的相互关系考虑进来。

基本原理

FM模型是基于矩阵分解的基础上的，让我们看一个例子。假设我们有一个评级的用户电影矩阵（1-5），其中矩阵的每个值代表用户给予电影的评级（1-5） 。

	星球大战	盗梦空间	教父	笔记本
U1	5	3	-	1
U2	4	-	-	1
U3	1	1	-	5
U4	1	-	-	4
U5	-	1	5	4

我们从上表中观察到一些评级缺失，我们想设计一种方法来预测这些缺失的评级。很明显，可以使用矩阵分解来解决这个问题。设想，应该有一些潜在的特征来决定用户如何评价电影。例如 - 如果用户A和B都是Al Pacino的粉丝，那么他们都会对Al Pacino电影（教父）评价很高。因为我们没有明确地将对特定演员的偏好包括在评级矩阵中，所以这就是一个隐藏特征。

假设我们想要计算隐藏或潜在特征K，那么我们只要找出矩阵P（U x K）和Q（M x K）（U - 用户，M - 电影），使得P x Q$^T$T作为评级矩阵

step1：P的每一行将表示用户U与特征K之间的相关性，而Q的每一行代表电影M与特征K的相关性，现在要做的就是提取用户U和电影M的交叉特征K。为了得到用户$u_j$uj​评定的电影$m_j$mj​的等级，我们可以计算出对应于$u_j$uj​和$m_j$mj​的2个向量的点积。
$r_{ij} = p_iq_j^T$rij​=pi​qjT​

step2：计算P和Q矩阵。我们使用梯度下降算法来实现此计算。目标是最小化实际值和由P，Q得到的预估值之间的平方误差。以下给出平方误差公式
$e_{ij}^2 = (r_{ij}-\hat{r_{ij}})^2 = (r_{ij} - \sum_{k=1}^{K}p_{ik}q_{kj})^2$eij2​=(rij​−rij​^​)2=(rij​−k=1∑K​pik​qkj​)2

step3：梯度下降法的更新规则是由使误差梯度最小化来定义的，以下给出$p_{ik}$pik​和$q_{kj}$qkj​的梯度
$\frac{\partial e_{ij}^2}{\partial p_{ik}} = -2(r_{ij}-\hat{r_{ij}})q_{kj} = -2e_{ij}q_{kj} \qquad \frac{\partial e_{ij}^2}{\partial q_{kj}} = -2(r_{ij}-\hat{r_{ij}})p_{ik} = -2e_{ij}p_{ik}$∂pik​∂eij2​​=−2(rij​−rij​^​)qkj​=−2eij​qkj​∂qkj​∂eij2​​=−2(rij​−rij​^​)pik​=−2eij​pik​

step4：获得梯度后，为$p_{ik}$pik​和$q_{kj}$qkj​制定更新规则
$p_{ik}' = p_{ik} - \alpha \frac{\partial e_{ij}^2}{\partial p_{ik}} = p_{ik} + 2\alpha e_{ij}q_{kj} \qquad q_{kj}' = q_{kj} - \alpha \frac{\partial e_{ij}^2}{\partial q_{kj}} = q_{kj} + 2\alpha e_{ij}p_{ik}$pik′​=pik​−α∂pik​∂eij2​​=pik​+2αeij​qkj​qkj′​=qkj​−α∂qkj​∂eij2​​=qkj​+2αeij​pik​
这里， α是可以控制更新大小的学习率。使用上述更新规则，我们可以迭代地执行操作，直到误差收敛到最小值。

step5：我们可以使用以下等式检查计算的总误差，并确定何时应该停止该过程.
$E = \sum e_{ij} = \sum (r_{ij} - \sum_{k=1}^{K}p_{ik}q_{kj})^2$E=∑eij​=∑(rij​−k=1∑K​pik​qkj​)2

step6：上述解决方案很简单，但是经常导致过拟合，即模型在训练样本数据上表现的很好，但在实际测试样本上表现的较差，不具备良好的泛化能力。。为了避免过拟合，最常用的一种方法是使用使用正则化。这里采用L2 正则化，直接在原来的损失函数基础上加上权重参数的平方和：
$L = E + \lambda \sum_jw_j^2$L=E+λj∑​wj2​
（E：是未包含正则化项的训练样本误差；λ 是正则化参数，可调）
代码实现：
一旦我们使用上述方法计算了P和Q，我们得到的近似评级矩阵如下：

	星球大战	盗梦空间	教父	笔记本
U1	4.97	2.98	2.18	0.98
U2	3.97	2.40	1.97	0.99
U3	1.02	0.93	5.32	4.93
U4	1.00	0.85	4.59	3.93
U5	1.36	1.07	4.89	4.12

注意到我们能够再生成现有评级，而且我们现在能够获得未知评级值的近似值。用数学公式来表示就是如下过程

FM算法详解

要求解的话肯定需要一个优化目标，就是使损失函数loss最小，FM的优化目标是整体损失函数

因子分解机FM算法可以处理如下三类问题：

$L = \sum _{i=1}^{N}loss(\hat y(x^{(i)}),y^{(i)})$L=i=1∑N​loss(y^​(x(i)),y(i))
输入：n维参数x
预测：标量y

1. 回归问题(Regression)：x的元素和y都为实数
2. 二分类问题(Binary Classification)：x的元素为实数，y = $\pm$± 1
3. 排序问题(Ranking)：x = ($x^a,x^b$xa,xb)为有序对，y = $\pm$± 1

1. 回归问题(Regression)
在回归问题中，直接使用$\hat y$y^​作为最终的预测结果。在回归问题中使用最小均方误差(the least square error)作为优化的标准，即
$loss^R(\hat y,y) = \frac{1}{2}\sum_{i=1}^{m}(\hat y(i)-y(i))^{2}$lossR(y^​,y)=21​i=1∑m​(y^​(i)−y(i))2
其中，m表示样本个数。

2. 二分类问题(Binary Classification)
与Logistic回归类似，通过阶跃函数，如Sigmoid函数，将$\hat y$y^​映射成不同的类别。在二分类问题中使用logit loss作为优化的标准，即
$loss^C(\hat y,y) = \sum_{i=1}^{m}-ln\sigma (\hat y(i)y(i))$lossC(y^​,y)=i=1∑m​−lnσ(y^​(i)y(i))
其中，$\sigma$σ表示的是阶跃函数Sigmoid，具体形式为
$\sigma(x) = \frac{1} {1+e^x}$σ(x)=1+ex1​

3. FM最优化问题就变成了
$\overrightarrow{\theta} = arg \ min\sum_{i=1}^N loss(\hat y(x^{(i)}),y^{(i)})$θ=arg mini=1∑N​loss(y^​(x(i)),y(i))
通常我们还考虑L2正则，因此，最优化问题变成
$\Theta = arg \ min\sum_{i=1}^N loss(\hat y(x^{(i)}),y^{(i)} + \sum _{\theta \in \Theta} \lambda_\theta \theta^2)$Θ=arg mini=1∑N​loss(y^​(x(i)),y(i)+θ∈Θ∑​λθ​θ2)
其中，$\lambda_\theta$λθ​表示参数$\theta$θ的正则化系数

基于随机梯度下降方式的求解

输入：训练集D，正则化系数$\lambda$λ，学习率$\eta$η，正态分布方差参数$\sigma$σ
输出：参数模型 $\Theta = (w_0,w,V)$Θ=(w0​,w,V)
Initialization：$w_0 = 0$w0​=0

FM模型为什么优于多项式和线性模型

我们分析下来自于点击预测数据集的几个训练示例。这个数据集是关于体育新闻网（供应商）和体育用品公司（广告商）的点击情况。

点击	供应商 （P）	广告商 （A）	性别 （G）
Yes	ESPN	Nike	Male
No	NBC	Adidas	Male

在FM（Factorization Machines）或 FFM（Field-aware Factorization Machines ）中 ，数据集中每一列（供应商，广告商）都归属于一个field，每个值（ESPN，NBC）都归属于一个feature，field和feature是一对多的关系。

线性建模技术（Linear modeling technique）和逻辑建模技术（Logistic modeling technique）非常好，并且他们在各种问题中运用良好，但缺点是模型仅单独地而不是整体地学习所有变量或特征的效果。
$\hat{LM} = w_0 + w_{ESPN}x_{ESPN} + w_{Nike}x_{Nike} + w_{NBC}x_{NBC} + w_{Adidas}x_{Adidas} + w_{Male}x_{Male}$LM^=w0​+wESPN​xESPN​+wNike​xNike​+wNBC​xNBC​+wAdidas​xAdidas​+wMale​xMale​

其中$w_0$w0​，$w_{ESPN}$wESPN​等表示参数（parameters），$x_{ESPN}$xESPN​，x_{Nike}表示数据集中各个特征（features）。通过最小化上述函数的log-loss（log损失函数），我们能得到逻辑回归模型。获得特征交互的一种方法是使用多项式函数
$\hat{Poly2} = w_0 + w_{ESPN}x_{ESPN} + w_{Nike}x_{Nike} + w_{NBC}x_{NBC} + w_{Adidas}x_{Adidas} + w_{Male}x_{Male} \\+ w_{ESPN,Nike}x_{ESPN}x_{Nike} + w_{ESPN,Male}x_{ESPN}x_{Male} + ...$Poly2^​=w0​+wESPN​xESPN​+wNike​xNike​+wNBC​xNBC​+wAdidas​xAdidas​+wMale​xMale​+wESPN,Nike​xESPN​xNike​+wESPN,Male​xESPN​xMale​+...
这也可以被称为是Poly2模型，因为我们只考虑两个特征的组合。

• 即使是对应中型数据集的问题，我们也需要有一个很大模型。而这对存储模型的内存量和训练模型的时间都有很大的影响。
• 再者，对于离散的数据集来说，运用这种技术并不能很好的计算所有可靠的权重或参数。即我们没有足够的训练样本用于每对特征（$x_{ESPN},x_{Nike}$xESPN​,xNike​），使得每个权重（$w_{ESPN,Nike}$wESPN,Nike​）可靠。