FM系列1-1 FM论文

编程语言2024-11-29 22:30:09

1. FM模型

对于训练集 $FM系列1-1 FM论文,D={(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}), \cdots},第1张$ 。给定一个样本 $FM系列1-1 FM论文,(x^{(j)},y^{(j)}),第2张$ ，即对于特征向量 $FM系列1-1 FM论文,\mathbf{x^{(j)}} = [x_1, x_2, \cdots, x_n],第3张$ ，有如下模型：

1.1 线性回归模型

$FM系列1-1 FM论文,\hat{y}(\mathbf{x}) = w_0+ \sum_{i=1}^n w_i x_i,第4张$

$FM系列1-1 FM论文,n,第5张$ 代表样本的特征数量， $FM系列1-1 FM论文,x_i,第6张$ 是第 $FM系列1-1 FM论文,i,第7张$ 个特征的值， $FM系列1-1 FM论文,w_0、w_i,第8张$ 是模型参数
$FM系列1-1 FM论文,x_i,第6张$ 和 $FM系列1-1 FM论文,x_j (i \neq j),第10张$ 之间是相互独立的，即 $FM系列1-1 FM论文,\hat{y}(\mathbf{x}),第11张$ 中仅考虑单个特征，而没有考虑特征之间的组合(interaction)。

1.2 多项式模型

$FM系列1-1 FM论文,y(\mathbf{x}) = w_0+ \sum_{i=1}^n w_i x_i + \sum_{i=1}^n \sum_{j=i+1}^n w_{ij} x_i x_j,第12张$

$FM系列1-1 FM论文,n,第5张$ 代表样本的特征数量， $FM系列1-1 FM论文,x_i,第6张$ 是第 $FM系列1-1 FM论文,i,第7张$ 个特征的值， $FM系列1-1 FM论文,w_0、w_i、w_{ij},第16张$ 是模型参数
$FM系列1-1 FM论文,x_ix_j,第17张$ ：特征 $FM系列1-1 FM论文,x_i,第6张$ 和 $FM系列1-1 FM论文,x_j,第19张$ 的组合，当 $FM系列1-1 FM论文,x_i,第6张$ 和 $FM系列1-1 FM论文,x_j,第19张$ 都非零时，组合特征 $FM系列1-1 FM论文,x_ix_j,第17张$ 才有意义
$FM系列1-1 FM论文,w_{ij},第23张$ 一共有 $FM系列1-1 FM论文,\frac {n(n−1)} 2,第24张$ 个，任意两个参数都是独立的
缺陷
在数据稀疏性普遍存在的实际应用场景中，每个 $FM系列1-1 FM论文,w_{ij},第23张$ 参数的训练需要大量 $FM系列1-1 FM论文,x_i,第6张$ 和 $FM系列1-1 FM论文,x_j,第19张$ 都非零的样本；由于样本数据本来就比较稀疏，满足“ $FM系列1-1 FM论文,w_{ij},第23张$ 和 $FM系列1-1 FM论文,x_j,第19张$ 都非零”的样本将会非常少。训练样本的不足，很容易导致参数 $FM系列1-1 FM论文,w_{ij},第23张$ 不准确，最终将严重影响模型的性能。

1.3 因子分解机(FM)

为了解决稀疏数据下的特征组合问题，Konstanz大学Steffen Rendle（现任职于Google）于2010年提出了FM（Factorization Machine）。即
$FM系列1-1 FM论文,\hat{y}(\mathbf{x}) = w_0+ \sum_{i=1}^n w_i x_i + \sum_{i=1}^n \sum_{j=i+1}^n \langle \mathbf{v}_i, \mathbf{v}_j \rangle x_i x_j,第31张$

$FM系列1-1 FM论文,w_0 \in \mathbb{R},第32张$ ：全局偏置项
$FM系列1-1 FM论文,w_i,第33张$ ：第 $FM系列1-1 FM论文,i,第7张$ 个特征变量的权重， $FM系列1-1 FM论文,w \in \mathbb{R}^n,第35张$
$FM系列1-1 FM论文,\hat{w}_{ij} = \langle \mathbf{v}_i, \mathbf{v}_j \rangle,第36张$ ， $FM系列1-1 FM论文,\mathbf{V} \in \mathbb{R}^{n \times k},第37张$
$FM系列1-1 FM论文,v_i,第38张$ 是第 $FM系列1-1 FM论文,i,第7张$ 维特征的隐向量，隐向量的长度为 $FM系列1-1 FM论文,k,第40张$ （k<<nk<<n），包含 $FM系列1-1 FM论文,k,第40张$ 个描述特征的因子。
⟨⋅,⋅⟩ 代表向量点积， $FM系列1-1 FM论文,\langle v_i,v_j \rangle=\sum_{f=1}^k{v_{if}v_{jf}},第42张$
模型复杂度 $FM系列1-1 FM论文,O(kn^2),第43张$

1.3.1 公式推导

在数据非常稀疏的场景下，由于大部分特征 $FM系列1-1 FM论文,x_ix_j,第17张$ 的值为0，因此很难直接求解出 $FM系列1-1 FM论文,\hat{w}_{ij},第45张$ ，因此，通过引入辅助变量 $FM系列1-1 FM论文,V_{i}=(v_{i1},v_{i2},...,v_{ik}),第46张$ ，即
$FM系列1-1 FM论文,\ \mathbf{V} = \begin{pmatrix} v_{11} & v_{12} & \cdots & v_{1k} \ v_{21} & v_{22} & \cdots & v_{2k} \ \vdots & \vdots & \ddots & \vdots \ v_{n1} & v_{n2} & \cdots & v_{nk} \ \end{pmatrix}_{n \times k} = \begin{pmatrix} \mathbf{v}_1 \ \mathbf{v}_2 \ \ \vdots \ \mathbf{v}_n \ \end{pmatrix},第47张$
因此，
$FM系列1-1 FM论文,\hat{w} = \mathbf{V} \cdot \mathbf{V}^T = \begin{pmatrix} \mathbf{v}_1 \ \mathbf{v}_2 \ \ \vdots \ \mathbf{v}_n \ \end{pmatrix} \cdot \begin{pmatrix} \mathbf{v}_1^T & \mathbf{v}_2^T & \cdots & \mathbf{v}_n^T \end{pmatrix} = \begin{pmatrix} \mathbf{v}_1 \mathbf{v}_1^T & \mathbf{v}_1 \mathbf{v}_2^T & \cdots & \mathbf{v}_1 \mathbf{v}_n^T \ \mathbf{v}_2 \mathbf{v}_2^T & \mathbf{v}_2 \mathbf{v}_2^T & \cdots & \mathbf{v}_2 \mathbf{v}_n^T \ \vdots & \vdots & \ddots & \vdots \ \mathbf{v}_n \mathbf{v}_1^T & \mathbf{v}_n \mathbf{v}_2^T & \cdots & \mathbf{v}_n \mathbf{v}_n^T \ \end{pmatrix},第48张$
从而，特征组合项
$FM系列1-1 FM论文,\sum_{i=1}^n \sum_{j=i+1}^n \langle \mathbf{v}_i, \mathbf{v}_j \rangle = \text{sum} \begin{pmatrix} 0 & \mathbf{v}_1 \mathbf{v}_2^T & \mathbf{v}_1 \mathbf{v}_3^T & \cdots & \mathbf{v}_1 \mathbf{v}_n^T \ 0 & 0 & \mathbf{v}_2 \mathbf{v}_3^T & \cdots & \mathbf{v}_2 \mathbf{v}_n^T \ \vdots & \vdots & \ddots & \vdots & \vdots \ 0 & 0 & \cdots & 0 & \mathbf{v}_{n-1} \mathbf{v}_n^T \ 0 & 0 & \cdots & 0 & 0\ \end{pmatrix},第49张$
即 $FM系列1-1 FM论文,\sum_{i=1}^n \sum_{j=i+1}^n \langle \mathbf{v}_i, \mathbf{v}_j \rangle,第50张$ 是这个对称矩阵的上三角部分求和（不包含对角线），所以 $FM系列1-1 FM论文,\sum_{i=1}^n \sum_{j=i+1}^n \langle \mathbf{v}_i, \mathbf{v}_j \rangle,第50张$ 等于 $FM系列1-1 FM论文,\sum_{i=1}^n \sum_{j=1}^n \langle \mathbf{v}_i, \mathbf{v}_j \rangle,第52张$ 减去对角线 $FM系列1-1 FM论文,\sum_{i=1}^n \langle \mathbf{v}_i, \mathbf{v}_i \rangle,第53张$ 再除以2。
因此，
$FM系列1-1 FM论文,\begin{align*} & \sum_{i=1}^n{\sum_{j=i+1}^n{<v_i,v_j>x_ix_j}}\ = & \frac{1}{2}\sum_{i=1}^n{\sum_{j=1}^n{<v_i,v_j>x_ix_j}}-\frac{1}{2}\sum_{i=1}^n{<v_i,v_i>x_ix_i}\ =& \frac{1}{2}\left(\sum_{i=1}^n{\sum_{j=1}^n{\sum_{f=1}^k{v_{if}v_{jf}x_ix_j}}}-\sum_{i=1}^n{\sum_{f=1}^k{v_{if}v_{if}x_ix_i}}\right) \ =& \frac{1}{2}\sum_{f=1}^k\left(\left(\sum_{i=1}^n{v_{if}x_i}\right)\left(\sum_{j=1}^n{v_{jf}x_j}\right)-\sum_{i=1}^n{v_{if}^2x_i^2}\right)\ =& \frac{1}{2}\sum_{f=1}^k\left(\left(\sum_{i=1}^n{v_{if}x_i}\right)^2-\sum_{i=1}^n{v_{if}^2x_i^2}\right) \end{align*},第54张$

使用随机梯度下降（Stochastic Gradient Descent）法学习模型参数。那么，模型各个参数的梯度如下：
$FM系列1-1 FM论文,\frac{\partial \hat{y}}{\partial \theta} = \left \{ \begin{array}{ll} 1, & \text{if}\; \theta\; \text{is}\; w_0 \qquad \text{(常数项)} \ x_i & \text{if}\; \theta\; \text{is}\; w_i \;\qquad \text{(线性项)} \ x_i \sum_{j=1}^{n} v_{j,f} x_j - v_{i,f} x_i^2, & \text{if}\; \theta\; \text{is}\; v_{i,f} \qquad \text{(交叉项)} \end{array} \right.,第55张$
其中， $FM系列1-1 FM论文,v_{j,f},第56张$ 是隐向量 $FM系列1-1 FM论文,v_j,第57张$ 的第 $FM系列1-1 FM论文,f,第58张$ 个元素。由于 $FM系列1-1 FM论文,\sum_{j=1}^n v{j,f}x_j,第59张$ 只与 $FM系列1-1 FM论文,f,第58张$ 有关，而与 $FM系列1-1 FM论文,i,第7张$ 无关，在每次迭代过程中，只需计算一次所有 $FM系列1-1 FM论文,f,第58张$ 的 $FM系列1-1 FM论文,\sum_{j=1}^n v{j,f}x_j,第59张$ ，就能够方便地得到所有 $FM系列1-1 FM论文,v_{i,f},第64张$ 的梯度。显然，计算所有 $FM系列1-1 FM论文,f,第58张$ 的 $FM系列1-1 FM论文,\sum_{j=1}^n v{j,f}x_j,第59张$ 的复杂度是 O(kn)；已知 $FM系列1-1 FM论文,\sum_{j=1}^n v{j,f}x_j,第59张$ 时，计算每个参数梯度的复杂度是 $FM系列1-1 FM论文,O(1),第68张$ ；得到梯度后，更新每个参数的复杂度是 $FM系列1-1 FM论文,O(1),第68张$ ；模型参数一共有 $FM系列1-1 FM论文,nk+n+1,第70张$ 个。因此，FM参数训练的复杂度也是 $FM系列1-1 FM论文,O(kn),第71张$ 。综上可知，FM可以在线性时间训练和预测，是一种非常高效的模型。

1.3.2 论文中的示例

假设有一个电影评分系统，该系统记录了用户 $FM系列1-1 FM论文,u \in U,第72张$ 在特定时间 $FM系列1-1 FM论文,t,第73张$ 对电影 $FM系列1-1 FM论文,i \in I,第74张$ 的评分 $FM系列1-1 FM论文,r \in {1,2,3,4,5},第75张$ 数据。
对于用户 (users) $FM系列1-1 FM论文,U,第76张$ 和电影 (items) $FM系列1-1 FM论文,I,第77张$ ，可以假设

电影用户集合

系统记录的数据为

样本集合

需要根据这些数据来预测用户对电影的评分。Steffen Rendle 在文中给了一个创建特征的例子，如下图所示。

特征构建

User (蓝色方框)：表示用户 ID (One-Hot编码)，维度为 $FM系列1-1 FM论文,|U|,第81张$
Movie (红色方框)：表示电影 ID (One-Hot编码)，维度为 $FM系列1-1 FM论文,|I|,第82张$
Other Movies rated (黄色方框)：表示用户评分过的所有电影，假设为电影集合 $FM系列1-1 FM论文,I_u,第83张$ ，则特征分量 $FM系列1-1 FM论文,x_{i} = \frac 1 {|I_u|},第84张$
Time (绿色方框)：表示用户评价电影的时间，如(记录中最早的日期) 2009年1月作为基数1，则2009年5月为5
Last Movie rated (棕色方框)：表示用户最近评分过的一部电影，若当前用户评价当前电影之前还评价过其他电影，则用户评价的上一部电影位置取1，其余为0；若当前用户评价当前电影之前没有评价过其他电影，则所有分量为0

$FM系列1-1 FM论文,x^{(i)}_j,第85张$ ：表示第 $FM系列1-1 FM论文,i,第7张$ 个样本的第 $FM系列1-1 FM论文,j,第87张$ 个特征分量

2. 总结、对比

2.1 FMs vs SVMs

SVM的二元特征交叉参数 $FM系列1-1 FM论文,w_{ij},第23张$ 是相互独立的，而FM的二元特征交叉参数是两个 $FM系列1-1 FM论文,k,第40张$ 维向量的乘积，即 $FM系列1-1 FM论文,\hat w_{i,j} = v_i \cdot v_j,第90张$
多项式 SVM 每个 $FM系列1-1 FM论文,w_{ij},第23张$ 参数的训练需要大量 $FM系列1-1 FM论文,x_i,第6张$ 和 $FM系列1-1 FM论文,x_j,第19张$ 都非零的样本，在数据稀疏场景中，由于样本数据稀疏，满足条件的训练样本将会非常少，容易导致参数 $FM系列1-1 FM论文,w_{ij},第23张$ 不准确，最终将严重影响模型的性能。而 FM 能够在稀疏严重的情况下估计参数，即使某个交叉特征在训练集中从未出现过，但仍然可以通过对应的两个特征的内积来估计其参数。
FM可以在原始形式下进行优化学习，而基于kernel的非线性SVM通常需要在对偶形式下进行
FM的模型预测是与训练样本独立，而SVM则与部分训练样本有关，即支持向量。

2.2 FMs vs MFs

分解模型包括 Matrix factorization (MF)、SVD++、PITF for Tag Recommendation、Factorized Personalized Markov Chains (FPMC)，这些模型都只在特定场景下使用，输入形式也比较单一（比如MF只适用于categorical variables），而 FM通过对输入特征进行转换，同样可可以实现以上模型的功能，而且FM的输入可以是任意实数域的数据，因此FM是一个更为泛化和通用的模型。

参考链接

[1] libfm官网
[2] FM Slice
[3] Factorization Machines (Rendle2010FM)
[4] 第09章：深入浅出ML之Factorization家族
[5] CTR预估论文精读(三)--Factorization Machines
[6] 美团技术-深入FFM原理与实践
[7] FM 论文笔记
[8] Factorization Machines 学习笔记（一）预测任务
[9] Factorization Machines 学习笔记（二）模型方程
[10] FM算法(一)：算法理论

查看全文

https://www.xamrdz.com/lan/5v62016657.html