因式分解机（Factorization Machines，FM ）

FM优化（0）：因式分解机（Factorization Machines，FM ） FM优化（1）：基于地理因式分解法的POI推荐排序算法（Rank-GeoFM）

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

前言

FM全称为factorization machine, 可以用解决回归、二分类问题 FM模型在基本的线性模型上引入一个交叉项，交叉项系数是定义一个辅助变量v,利用正定矩阵来估计交叉项的系数。 FM主要是考虑了特征之间的关联。 目的：解决高维稀疏数据中特征组合问题，适用于categorical feature。

背景

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

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

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

FM模型

step1：一般的线性模型为（n表示n维特征）： $$y=w_0+\sum _{i=1}^n{w}_i{x}_i$$

step2：如果在线性模型中加入二阶特征的组合，那么会是这个样子的 $$\hat{y}(x)=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$$ $$\left\{\begin{array}{cccc}{w}_{11}& w_{12}& ...& w_{1n}\\ w_{21}& w_{22}& ...& w_{2n}\\ ...& ...& ...& ...\\ w_{n1}& w_{n2}& ...& w_{nn}\end{array}\right\}$$ 注：$x_i$表示第i个特征，$w_{ij}$是组合参数，其中$w_{ij}$和$w_{ji}$是相等的，因此组合特征部分相关参数共有(n-1) + (n-2) + … + 1 = n(n-1)/2。只需要计算上三角或下三角。

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

step4：为了解决这个问题，FM诞生了，我们看一下FM是如何解决这个问题的： 对每一个特征分量$x_i$引入辅助向量$v_i=(v_{i,1，i,2，....，i,k})$，利用$v_i{v}_i^T$对交叉项的系数$w_{ij}$进行估计，即令$w_{ij}=v_i{v}_j^T$ $$V={\left\{\begin{array}{cccc}{v}_{11}& v_{12}& ...& v_{1k}\\ v_{21}& v_{22}& ...& v_{2k}\\ ...& ...& ...& ...\\ v_{n1}& v_{n2}& ...& v_{nk}\end{array}\right\}}_{n\times k}=\left\{\begin{array}{c}{v}_1\\ v_2\\ ...\\ v_n\end{array}\right\}$$则， $$W=V{V}^T=\left\{\begin{array}{c}{v}_1\\ v_2\\ ...\\ v_n\end{array}\right\}\left\{\begin{array}{cccc}{v}_1^T& v_2^T& ...& v_n^T\end{array}\right\}$$ 这就对应了一种矩阵的分解。对k值的限定，对FM的表达能力有一定的影响。这也解释了FM因式分解机名字的由来，它是将$w_{ij}$进行了拆解。

step5：FM对于度为2的因式分解机FM的模型为： $$\hat{y}=w_0+\sum _{i=1}^n{w}_i{x}_i+\sum _{i=1}^{n-1}\sum _{j=i+1}^n⟨v_i,v_j⟩x_i{x}_j$$ 其中，参数$w_0\in \mathbb{R}，w\in {\mathbb{R}}^n，V\in {\mathbb{R}}^{n\times k}$。$⟨v_i,v_j⟩$表示两个大小为k的向量的$v_i$和向量$v_j$的点积： $$w_{ij}=⟨v_i,v_j⟩=\sum _{f=1}^k{v}_{i,f}.v_{j,f}$$ 其中，$v_i$表示的是系数矩阵V的第$i$维向量，且$v_i=(v_{i,1，i,2，....，i,k})，k\in {\mathbb{N}}^{+}$称为超参数。在因子分解机FM模型中，前面两部分是传统的线性模型，最后一部分将两个互异特征分量之间的相互关系考虑进来。

step6：要求出$⟨v_i,v_j⟩$，主要是采用了如公式$((a+b+c{)}^2-a^2-b^2-c^2)$求出交叉项。具体过程如下： $$\begin{gathered} \sum _{i=1}^{n-1}\sum _{j=i+1}^n⟨v_i,v_j⟩x_i{x}_j \\ =\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\sum _{j=1}^n⟨v_i,v_i⟩x_i{x}_i \\ =\frac{1}{2}(\sum _{i=1}^n\sum _{j=1}^n\sum _{f=1}^k{v}_{i,f}{v}_{j,f}{x}_i{x}_i-\sum _{i=1}^n\sum _{f=1}^k{v}_{i,f}{v}_{i,f}{x}_i{x}_i) \\ =\sum _{f=1}^k((\sum _{i=1}^n{v}_{i,f}{x}_i)(\sum _{j=1}^n{v}_{j,f}{x}_j)-\sum _{i=1}^n{v}_{i,f}^2{x}_i^2) \\ =\sum _{f=1}^k((\sum _{i=1}^n{v}_{i,f}{x}_i{)}^2-\sum _{i=1}^n{v}_{i,f}^2{x}_i^2) \end{gathered}$$

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

基本原理

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

星球大战盗梦空间教父笔记本U153-1U24--1U311-5U41--4U5-154

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

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

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

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

step3：梯度下降法的更新规则是由使误差梯度最小化来定义的，以下给出$p_{ik}$和$q_{kj}$的梯度 $$\frac{\partial e_{ij}^2}{\partial p_{ik}}=-2(r_{ij}-\widehat{r_{ij}})q_{kj}=-2e_{ij}{q}_{kj}\frac{\partial e_{ij}^2}{\partial q_{kj}}=-2(r_{ij}-\widehat{r_{ij}})p_{ik}=-2e_{ij}{p}_{ik}$$

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

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

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

星球大战盗梦空间教父笔记本U14.972.982.180.98U23.972.401.970.99U31.020.935.324.93U41.000.854.593.93U51.361.074.894.12

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

FM算法详解

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

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

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

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

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

对参数求偏导： $$\frac{\partial los{s}^R(\hat{y},y)}{\partial \theta }=2(\hat{y}-y)\frac{\partial \hat{y}}{\partial \theta }$$

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

对参数求偏导： $$\begin{gathered} \frac{los{s}^C(\hat{y},y)}{\partial \theta }=-\frac{1}{\sigma (\hat{y}y)}\sigma (\hat{y}y).[1-\sigma (\hat{y}y)].y.\frac{\partial \hat{y}}{\partial \theta } \\ =[\sigma (\hat{y}y)-1].y.\frac{\partial \hat{y}}{\partial \theta } \end{gathered}$$ 而 $$\frac{\partial \hat{y}}{\partial \theta }=\{\begin{array}{c}1,if\theta =w_0\\ x_i,if\theta =w_i\\ x_i{\sum }_{j=1}^n{v}_{j,f}{x}_j-v_{i,f}{x}_i^2,if\theta =w_{i,f}\end{array}$$

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

基于随机梯度下降方式的伪代码

输入：训练集D，正则化系数$\lambda$，学习率η，正态分布方差参数σ 输出：参数模型 $\Theta =(w_0,w,V)$ Initialization：$w_0=0;w=0;VN(0，\sigma )$ Repeat \qquad FOR (x,y) $\in$ D DO \qquad { $w_0=w_0-\eta (\frac{\partial loss(\hat{y}(x),y)}{\partial w_0}+2{\lambda }^0{w}_0)$ \qquad \qquad FOR i $\in$ {1,2,…,n} DO \qquad \qquad { \qquad \qquad \qquad IF $x_i̸=0$ \qquad \qquad \qquad { $w_i=w_i-\eta (\frac{\partial loss(\hat{y}(x),y)}{\partial w_i}+2{\lambda }_{\pi (i)}^i{w}_i)$ \qquad \qquad \qquad \qquad FOR j$\in$ {1,2,…,k} DO \qquad \qquad \qquad \qquad { $v_{ij}=v_{ij}-\eta (\frac{\partial loss(\hat{y}(x),y)}{\partial v_{if}}+2{\lambda }_{f,\pi (i)}^i{v}_{i,f})$ \qquad \qquad \qquad \qquad } \qquad \qquad \qquad } \qquad \qquad } \qquad }

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

FM优点 1、可以对稀疏数据中的特征进行组合 2、计算时间复杂度为O（kn） 3、FM是一种可以与任何实值特征向量一起使用的通用预测器。

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

点击供应商（P）广告商（A）性别（G）YesESPNNikeMaleNoNBCAdidasMale

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

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

其中$w_0$，$w_{ESPN}$等表示参数（parameters），$x_{ESPN}$，x_{Nike}表示数据集中各个特征（features）。通过最小化上述函数的log-loss（log损失函数），我们能得到逻辑回归模型。获得特征交互的一种方法是使用多项式函数 $$\begin{gathered} \widehat{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}+... \end{gathered}$$ 这也可以被称为是Poly2模型，因为我们只考虑两个特征的组合。

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

下一篇：基于地理因式分解法的POI推荐排序算法（Rank-GeoFM）