机器学习FM、FFM

FMFMFactorization Machine因子分解机是一种适合稀疏特征场景如广告 CTR/CVR的机器学习模型用来同时建模一阶特征和二阶特征交叉。要解决什么问题One-Hot 后特征很稀疏、维度很高很多有用信号来自特征组合如“中国”ד春节”、“化妆品”ד女性”。普通多项式模型为每对交叉单独学一个wij在稀疏数据上很难训准。核心做法把交叉权重做成两个隐向量的点积wijvivj模型二阶为yxw0iwixiij⟨vivjxixj每个特征一个长度为kk≪n的隐向量二次项参数从On2降到Onk不同交叉共享隐向量稀疏时也能互相“借力”学习特点可用不同损失做回归或二分类二次项可化简训练/预测复杂度约Okn较高效一句话FM 用矩阵分解思想高效学习稀疏特征下的二阶交叉。# FM问题来源CTR/CVR预测时用户的性别、职业、教育水平、品类偏好商品的品类等经过One-Hot编码转换后都会导致样本数据的稀疏性。特别是商品品类这种类型的特征如商品的末级品类约有550个采用One-Hot编码生成550个数值特征但每个样本的这550个特征有且仅有一个是有效的非零。由此可见数据稀疏性是实际问题中不可避免的挑战。One-Hot编码的另一个特点就是导致特征空间大。例如商品品类有550维特征一个categorical特征转换为550维数值特征特征空间剧增。同时通过观察大量的样本数据可以发现某些特征经过关联之后与label之间的相关性就会提高。例如“USA”与“Thanksgiving”、“China”与“Chinese New Year”这样的关联特征对用户的点击有着正向的影响。换句话说来自“China”的用户很可能会在“Chinese New Year”有大量的浏览、购买行为而在“Thanksgiving”却不会有特别的消费行为。这种关联特征与label的正向相关性在实际问题中是普遍存在的如“化妆品”类商品与“女”性“球类运动配件”的商品与“男”性“电影票”的商品与“电影”品类偏好等。因此引入两个特征的组合是非常有意义的。# FM基本原理多项式模型是包含特征组合的最直观的模型。在多项式模型中特征 $x_i$ 和 $x_j$ 的组合采用 $x_ix_j$表示即 $x_i$ 和 $x_j$ 都非零时组合特征 $x_ix_j$ 才有意义。从对比的角度本文只讨论二阶多项式模型。模型的表达式如下$$y(x) w_0 \sum_{i1}^n w_i x_i \sum_{i1}^n \sum_{ji1}^n w_{ij} x_i x_j \tag{1}$$其中$n$ 代表样本的特征数量$x_i$ 是第 $i$ 个特征的值$w_0$、$w_i$、$w_{ij}$是模型参数。从公式(1)可以看出组合特征的参数一共有 $\frac{n(n−1)}{2}$个任意两个参数都是独立的。然而在数据稀疏性普遍存在的实际应用场景中二次项参数的训练是很困难的。其原因是每个参数 $w_{ij}$的训练需要大量 $x_i$ 和 $x_j$ 都非零的样本由于样本数据本来就比较稀疏满足“$x_i$ 和 $x_j$ 都非零”的样本将会非常少。训练样本的不足很容易导致参数 $w_{ij}$ 不准确最终将严重影响模型的性能。# 系数矩阵分解那么如何解决二次项参数的训练问题呢矩阵分解提供了一种解决思路。与在model-based的协同过滤中一个rating矩阵可以分解为user矩阵和item矩阵。对于对称矩阵W由于直接求解W不方便因此我们引入隐变量V满足$$VV^T W$$$V$ 的第$ j$列$v_j$便是第$ j $维特征的**隐向量**。换句话说每个参数 $w_{ij}⟨v_i,v_j⟩$这就是FM模型的核心思想。因此FM的模型方程为本文不讨论FM的高阶形式$$y(x) w_0 \sum_{i1}^n w_i x_i \sum_{i1}^n \sum_{ji1}^nv_i, v_j x_i x_j \tag{2}$$# 参数个数$ v_i $是第 $ i $ 维特征的隐向量$ ·,· $ 代表向量点积。隐向量的长度为 $ k k n $包含 $ k $ 个描述特征的因子。根据公式2二次项的参数数量减少为 $ kn $个远少于多项式模型的参数数量。另外参数因子化使得 $ x_h x_i $ 的参数和 $ x_i x_j $ 的参数不再是相互独立的因此我们可以在样本稀疏的情况下相对合理地估计FM的二次项参数。具体来说$ x_h x_i $ 和 $ x_i x_j $ 的系数分别为 $ v_h,v_i $ 和 $ v_i, v_j$它们之间有共同项 $ v_i $。也就是说所有包含“$ x_i $ 的非零组合特征”存在某个 $ j\neq i $使得 $ x_i x_j \neq 0 $的样本都可以用来学习隐向量 $ v_i $这很大程度上避免了数据稀疏性造成的影响。而在多项式模型中$ w_{hi} $ 和 $ w_{ij} $ 是相互独立的。# 预测时间复杂度显而易见公式(2)是一个通用的拟合方程可以采用不同的损失函数用于解决回归、二元分类等问题比如可以采用MSEMean Square Error损失函数来求解回归问题也可以采用Hinge/Cross-Entropy损失来求解分类问题。当然在进行二元分类时FM的输出需要经过sigmoid变换这与Logistic回归是一样的。当我们已经求出所有参数以后对新输入对象进行预测时FM的计算复杂度是 $O(kn^2)$。但是通过公式(3)的等式FM的二次项可以化简其复杂度可以优化到 $O(kn)$。由此可见**FM可以在线性时间对新样本作出预测**。$$\sum_{i1}^n \sum_{ji1}^n \langle \mathbf{v}_i, \mathbf{v}_j \rangle x_i x_j \frac{1}{2} \sum_{f1}^k \left(\left( \sum_{i1}^n v_{i, f} x_i \right)^2 - \sum_{i1}^n v_{i, f}^2 x_i^2 \right) \tag{3}$$# 梯度下降法利用SGDStochastic Gradient Descent训练模型。模型各个参数的梯度如下$$\frac{\partial}{\partial\theta} y (\mathbf{x}) \left\{\begin{array}{ll} 1, \text{if}\; \theta\; \text{is}\; w_0 \\ x_i, \text{if}\; \theta\; \text{is}\; w_i \\ x_i \sum_{j1}^n v_{j, f} x_j - v_{i, f} x_i^2, \text{if}\; \theta\; \text{is}\; v_{i, f} \end{array}\right.$$其中$ v_{j, f} $ 是隐向量 $ v_j $ 的第 $ f $ 个元素。由于 $ \sum_{j1}^n v_{j, f} x_j $ 只与 $ f $ 有关而与 $ i $ 无关在每次迭代过程中只需计算一次所有 $ f $ 的 $ \sum_{j1}^n v_{j, f} x_j $就能够方便地得到所有 $ v_{i, f} $ 的梯度。显然计算所有 $ f $ 的 $ \sum_{j1}^n v_{j, f} x_j $ 的复杂度是 $ O(kn) $已知 $ \sum_{j1}^n v_{j, f} x_j $ 时计算每个参数梯度的复杂度是 $ O(1) $得到梯度后更新每个参数的复杂度是 $ O(1) $模型参数一共有 $ nk n 1 $ 个。因此FM参数训练的复杂度也是 $ O(kn) $。综上可知FM可以在线性时间训练和预测是一种非常高效的模型。FFM:FFMField-aware Factorization Machine场感知因子分解机是在FM基础上引入field场的改进模型用来更精细地建模不同类别特征之间的交叉。相对 FM 改了什么FM每个特征只有1个隐向量vi和谁交叉都用同一个向量。FFM特征先按场分组如 publisher、advertiser、gender同一类目 One-Hot 出的维度通常同属一个 field。特征xi针对对方所属的每个 fieldfj各有一个隐向量vi,fj。含义同一个特征如“日期某天”与“国家”交叉、与“广告类型”交叉时用的是不同隐向量更符合不同场之间的差异。模型形式yxij⟨vi,fjvj,fixixj实践中常只保留二次项FM 可看成「全部特征归为一个 field」时的 FFM 特例。代价二次项参数约nfk多于 FM 的nk与 field 相关二次项一般不能像 FM 那样化简预测复杂度约Okn2notebook 中多用 logistic loss L2偏二分类如 CTR一句话FFM 带场信息的 FM交叉更细表达更强但更重。# FFM原理# 背景及基本原理在FM模型中每一个特征会对应一个隐变量但在FFM模型中认为应该将特征分为多个field每个特征对应每个field分别有一个隐变量。举个例子我们的样本有3种类型的字段publisher, advertiser, gender分别可以代表媒体广告主或者是具体的商品性别。其中publisher有5种数据advertiser有10种数据gender有男女2种经过one-hot编码以后每个样本有17个特征其中只有3个特征非空。简单来说同一个categorical特征经过One-Hot编码生成的数值特征都可以放到同一个field。如果使用FFM模型则17个特征每个特征对应3个隐变量即每个类型对应一个隐变量具体而言就是对应publisher, advertiser, gender三个field各有一个隐变量。在FFM中每一维特征 $x_i$针对其它特征的每一种field $f_j$**其中 $f_j$表示第j维特征所属的field**都会学习一个隐向量 $v_{i,f_j}$。因此隐向量不仅与特征相关也与field相关。也就是说**“Day26/11/15”这个特征与“国家”特征和“广告类型特征进行关联的时候使用不同的隐向量这与“国家”和“广告类型”的内在差异相符**。假设样本的 $n$ 个特征属于 $f$ 个field那么FFM的二次项有 $nf$个隐向量。而在FM模型中每一维特征的隐向量只有一个。FM可以看作FFM的特例是把所有特征都归属到一个field时的FFM模型。根据FFM的field敏感特性可以导出其模型方程。$$y(x) w_0 \sum_{i1}^n w_i x_i \sum_{i1}^n \sum_{ji1}^n v_{i, f_j}, v_{j, f_i} x_i x_j \tag{4}$$其中$f_j$ 是第 $j$ 个特征所属的field。如果隐向量的长度为 $k$那么FFM的二次参数有 $nfk$ 个远多于FM模型的 $nk$ 个。此外由于隐向量与field相关FFM二次项并不能够化简其预测复杂度是 $O(kn^2)$。下面以一个例子简单说明FFM的特征组合方式[9]。输入记录如下|用户|电影| 电影类型| 价格||--|--|--|---||user1|三傻|喜剧, 戏剧 |$9.99|这条记录可以编码成5个特征其中“电影类型喜剧”和“电影类型戏剧”属于同一个field“Price”是数值型不用One-Hot编码转换。为了方便说明FFM的样本格式我们将所有的特征和对应的field映射成整数编号。|field name| Field index| Feature name| Feature index||--|--|--|---||User| 1 |UserYuChin| 1||Movie| 2| Movie3Idiots| 2||Genre| 3| GenreComedy| 3||| | GenreDrama |4||Price|4|Price| 5|那么FFM的组合特征有10项如下图所示。二次项的系数是通过与特征field相关的隐向量点积得到的二次项共有 $\frac{n(n−1)}{2}$ 个。事实上在大多数情况下FFM模型只保留了二次项部分省略常数项和一次项即$$\phi(V,x) \sum_{i1}^n \sum_{ji1}^n v_{i, f_j}, v_{j, f_i} x_i x_j \sum_{i1}^n \sum_{ji1}^n (v^T_{i, f_j}v_{j, f_i} ) x_i x_j $$# 最优化问题FFM模型采用logistic loss作为损失函数和L2惩罚项因此只能用于二元分类问题。根据逻辑回归的损失函数及分析可以得出FFM的最优化问题为$$\min_{\mathbf{v}} \sum_{i1}^L \log \big( 1 \exp\{ -y_i \phi (\mathbf{v}, \mathbf{x}_i ) \} \big) \frac{\lambda}{2} \| \mathbf{v} \|^2$$中$y_i∈\{−1,1\}$ 是第 $i$ 个样本的label$L$ 是训练样本数量$λ$是惩罚项系数。模型采用SGD优化# FFM代码实现符号约定$n$:特征的维数$m$:域的个数$k$:隐向量的维度$j$:在特征中的下标$f$:在域中的下标$d$:在隐向量中的下标$l$:样本的总数粗体字母表示向量或矩阵**特征组合****最基本的线性加权**$$\phi_{LM}(\textbf{w},\textbf{x})\sum_{i1}^n{w_ix_i}$$**任意特征两两组合**$$\phi_{poly2}(\textbf{w},\textbf{x})\sum_{j11}^n{\sum_{j2j11}^n{w_{j1,j2}x_{j1}x_{j2}}}$$$w$是一个对称方阵即$w_{j1,j2}w_{j2,j1}$可以用矩阵分解法来拟合$w$。$$w_{j1,j2}\textbf{v}_{j1}\cdot\textbf{v}_{j2}\textbf{v}_{j2}\cdot\textbf{v}_{j1}w_{j2,j1}$$矩阵$w$的规模是$n×n$矩阵$v$的规模是$n×k$$k≪n$。实际上我们已经推导出了因子分解法。**因子分解法FM**$$\phi_{FM}(\textbf{w},\textbf{x})\sum_{j11}^n{\sum_{j2j11}^n{\textbf{w}_{j1}\cdot \textbf{w}_{j2}x_{j1}x_{j2}}}$$这里的$w_j$相当于上面的$v_j$。**域感知的因子分解法FFM**$$\phi_{FFM}(\textbf{w},\textbf{x})\sum_{j11}^n{\sum_{j2j11}^n{\textbf{w}_{j1,f2}\cdot \textbf{w}_{j2,f1}x_{j1}x_{j2}}}$$在FM中w是规模为$n×k_{FM}$的二维矩阵而在FFM中$w$是规模为$n×m×k_{FFM}$的三维矩阵$k_{FFM}≪k_{FM}$。**逻辑回归二分类****决策函数**$$\hat{y}\frac{1}{1exp(-\phi_{FFM}(\textbf{w},\textbf{x}))}$$**带L2正则的目标函数**$$\min_{\textbf{w}}\;\;\frac{\lambda}{2}\parallel w\parallel_2^2\sum_{i1}^llog(1exp(-y_i\phi_{FFM}(\textbf{w},\textbf{x}_i)))$$ 其中$y_i∈\{−1,1\}$注意虽然在预测结果出来的是0-1之间数但是训练时的y值取-1或1所以当训练结束后及测试集上测试评估模型时要将测试集的y值转换为0-1。在SGD中每次只需要考虑一个样本的损失此时目标函数为$$\min_{\textbf{w}}\;\;\frac{\lambda}{2}\parallel w\parallel_2^2log(1exp(-y\phi_{FFM}(\textbf{w},\textbf{x})))$$**梯度**$$\textbf{g}_{j1,f2}\lambda\cdot\textbf{w}_{j1,f2}\kappa\cdot\textbf{w}_{j2,f1}x_{j1}x_{j2}$$$$\textbf{g}_{j2,f1}\lambda\cdot\textbf{w}_{j2,f1}\kappa\cdot\textbf{w}_{j1,f2}x_{j1}x_{j2}$$梯度之所会这么简单依赖一个很重要的前提同一个域下的各个特征只有一个是非0值。其中$$\kappa\frac{\partial log(1exp(-y\phi_{FFM}(\textbf{w},\textbf{x})))}{\partial\phi_{FFM}(\textbf{w},\textbf{x})}\frac{-y}{1exp(y\phi_{FFM}(\textbf{w},\textbf{x}))}$$**AdaGrad更新w**$$(G_{j1,f2})_d\gets(G_{j1,f2})_d(g_{j1,f2})_d^2$$$$(G_{j2,f1})_d\gets(G_{j2,f1})_d(g_{j2,f1})_d^2$$$$(w_{j1,f2})_d\gets(w_{j1,f2})_d-\frac{\eta}{\sqrt{(G_{j1,f2})_d}}(g_{j1,f2})_d$$$$(w_{j2,f1})_d\gets(w_{j2,f1})_d-\frac{\eta}{\sqrt{(G_{j2,f1})_d}}(g_{j2,f1})_d$$初始化$G_d1$这样在计算$\frac{\eta}{\sqrt{G_d}}$时既可以防止分母为0又可以避免该项太大或太小。$η$是学习率通常可取0.01。初始的$w$可以从均匀分布中抽样$\textbf{w}\sim U(0,\frac{1}{\sqrt{k}})$实现发现将每个$x$归一化即模长为1在测试集得到的准确率会稍微好一点且对参数不太敏感。工业上目前那种方法用的更多若只比FM和 FFM现在更常见、更常用的是FM或其变体/组件纯FFM相对少很多。原因大致是FFM参数多约nfk、预测约Okn2大流量 CTR 上成本和延迟更重FM可化简到约Okn更易上线、当强基线从更大范围看广告/推荐点击率2015–2017 前后 FM/FFM 很火近几年工业界更主流的是深度学习 CTR 模型如 DeepFM、WideDeep、DIN 等其中常内嵌 FM 式交叉而不是单独训一个大 FFM。简要结论二者里选FM 用得更多整体趋势上单独的 FM/FFM 已不如深度交叉模型普遍但 FM 思想仍广泛保留。