FM因子分解机中的特征交叉

从事推荐和广告算法的同学，大概都绕不开一个话题：怎么做特征组合。

比如”用户是年轻男性”这个特征单独看没什么信息量，”商品是球鞋”这个特征单独看也很普通，但如果模型能学到”年轻男性 × 球鞋”这个组合的权重明显偏高，点击率预估的效果往往会有质的提升。问题是，怎么让模型自动学到这种组合关系，而不是靠人工一个个去构造交叉特征？这条路，业界走了LR、POLY2、FM三步，每一步都是在补上一个前作留下的窟窿。今天就把这条演进链彻底捋一遍。

基础线性模型

最朴素的做法是LR（逻辑回归的线性打分部分）：

$$ y = w_0 + \sum_{i=1}^n w_i x_i $$

其中n是样本的特征数量，$x_i$是第i个特征的取值，$w_i$是它对应的系数。

这个模型简单、训练快、权重可解释，工业界用了很多年，至今仍是很多场景里的baseline。但它有个致命假设——所有特征都是独立起作用的，谁也不影响谁，模型只是把每个特征的贡献线性加总。现实世界显然不是这样：年龄和职业会互相影响购买意愿，时间和地点会互相影响用户的行为模式。LR对这些交互统统视而不见，这是它天生的表达能力上限。

加个交叉项——POLY2

既然问题出在”看不到交互”，那最直接的补救办法就是把两两特征的乘积也当成一个新特征，单独学一个权重，这就是POLY2：

$$ 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 $$

这里$w_0, w_i, w_{ij}$都是待学习的参数，思路很直接：只要$x_i$和$x_j$同时不为0，这一项就会生效，模型就有机会学到这对特征组合的权重。

听起来合理，用起来却处处碰壁，原因出在两个地方，一个是理论上的参数规模问题，一个是实际训练中的稀疏性问题。

第一，参数爆炸。 特征一旦做了one-hot编码（推荐、广告场景里几乎是标配），维度轻松上万甚至上百万，交叉项的数量是$n + \frac{n(n-1)}{2}$级别，n一大，这个数字直接爆炸式增长，模型的存储和训练开销都变得难以承受。

第二，数据稀疏导致求解困难。 这一点比参数量爆炸更致命。one-hot之后数据变得极为稀疏，$x_i$和$x_j$同时不为0的样本少之又少。这会带来一连串连锁反应：

• 很多交叉项对应的$w_{ij}$根本没有足够的样本去训练；
• 在梯度下降过程中，这些参数的梯度大量时候都是0，参数几乎不更新；
• 最终的结果是，即便理论上POLY2能表达特征交互，实际上大部分交叉权重都学不出来，模型学不到有意义的交互关系。

POLY2在理论上没问题，但一到高维稀疏场景就水土不服，正是这两个局限，直接催生了FM。

FM因子分解机——用隐向量做参数共享

FM（Factorization Machine，因子分解机）的核心思想，是借助矩阵分解的方法，给每个特征引入一个k维的隐向量，用两个隐向量的内积去近似原来POLY2里那个独立的交叉权重，从而解决多项式扩展在稀疏特征下的求解难题。相比POLY2，FM具有线性的计算复杂度，并且能同时处理连续特征和离散特征。

完整的FM公式是：

$$ y = w_0 + \sum_{i=1}^n w_i x_i + \sum_{i=1}^{n-1} \sum_{j=i+1}^n w_{i,j}x_i x_j = w_0 + \sum_{i=1}^n w_i x_i + \sum_{i=1}^{n-1} \sum_{j=i+1}^n \langle V_i, V_j \rangle x_i x_j $$

各符号的含义：

• $w_0$：全局偏置项；
• $w_i$：一阶特征权重；
• k：隐向量的维度，是一个需要人工设定的超参数；
• V：一个维度为(one-hot之后的特征数, k)的矩阵；
• $V_i$：特征i对应的k维隐向量；
• $\langle V_i, V_j \rangle$：两个隐向量的内积。

为什么用内积去近似$w_{ij}$

POLY2里每一对特征组合都单独存一个$w_{ij}$，FM换了个思路：给每个特征$x_i$引入一个k维的辅助向量

$$ V_i = (v_{i1}, v_{i2}, \cdots, v_{ik}) $$

然后用两个隐向量的内积去近似原来的交叉权重：

$$ w_{ij} \approx V_i V_j^T $$

内积的具体计算方式是：

$$ \langle V_i, V_j \rangle = \sum_{f=1}^k v_{i,f} v_{j,f} $$

这一步转换看着不大，实际上是整个方法的核心。在POLY2里，$w_{ij}$和$w_{ik}$是两个毫不相干的参数，各学各的，谁也帮不了谁；但引入隐向量之后，$w_{ij} = \langle V_i, V_j \rangle$和$w_{ik} = \langle V_i, V_k \rangle$共享着同一个$V_i$，两者之间就建立起了关联。也就是说，只要样本里出现过特征i和任意一个非零特征j的组合（即存在某个$j \neq i$使得$x_i x_j \neq 0$），这条样本就能拿来训练$V_i$，而不需要恰好凑齐$(i,j)$这个特定的组合才行。稀疏性带来的训练不足问题，就这样被参数共享绕开了。

这还带来一个额外的好处：泛化能力变强了。哪怕训练集里从没同时出现过某两个特征，只要它们各自的隐向量都学得不错，FM依然可以通过两个k维隐向量的内积，算出一个合理的组合特征权重。这是POLY2完全做不到的——POLY2里没见过的组合，权重就是学不出来。

FM中的两处优化

FM之所以能真正落地，靠的是两处优化，一处是参数规模的压缩，一处是计算复杂度的压缩，两者是分开的两件事，容易被混在一起说，这里拆开讲清楚。

优化一：参数规模从$n^2$降到$nk$。 通过引入特征隐向量替代原有权重的方式$w_{ij} = \langle v_i, v_j \rangle$，把原先$n^2$级别（准确说是$n(n-1)/2$个）的权重参数，降低到了$n \times k$的级别。因为通常$k$远小于$n$（k取几十到几百，n在one-hot之后可能是百万级），这一步就已经把参数量压缩了一个甚至几个数量级。

优化二：训练复杂度从$O(kn^2)$降到$O(kn)$。 这一步是通过转换目标函数的数学形式实现的，也是接下来要重点推导的部分。相比POLY2，这一步进一步极大地降低了训练开销，是FM能在工业界大规模落地的关键。

公式化简

下面我们来看一下二阶交叉项是怎么从O(n²)降到O(kn)的。原始的二阶交互项长这样：
$$ \sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle V_i, V_j \rangle x_i x_j $$

其中$\langle V_i, V_j \rangle = \sum_{f=1}^k v_{i,f} v_{j,f}$。直接算这个双重求和，需要遍历所有的$(i,j)$对，复杂度是$O(n^2k)$，特征数一大就扛不住。下面一步步把它化简掉。

第一步，展开内积求和。 把内积展开成隐向量各维度的乘积和，再交换求和顺序：

$$ \sum_{i=1}^{n} \sum_{j=i+1}^{n} \left( \sum_{f=1}^k v_{i,f} v_{j,f} \right) x_i x_j = \sum_{f=1}^k \left( \sum_{i=1}^{n} \sum_{j=i+1}^{n} v_{i,f} v_{j,f} x_i x_j \right) $$

第二步，利用平方恒等式。 这里用到一个很基础的代数恒等式：$ab = \frac{1}{2}[(a+b)^2-(a^2+b^2)]$，推广到多项就是：

$$ \left( \sum_{i=1}^n v_{i,f} x_i \right)^2 = \sum_{i=1}^n v_{i,f}^2 x_i^2 + 2 \sum_{i=1}^{n} \sum_{j=i+1}^{n} v_{i,f} v_{j,f} x_i x_j $$

直观上看，左边是”n个数先求和再平方”，右边拆开后，平方项里既包含每个数自己的平方（$i=j$的部分），也包含所有两两交叉项的和（乘了2，因为$ij$和$ji$是同一项算了两次）。把等式移项，就能把我们要的那个双重求和单独解出来：

$$ \sum_{i=1}^{n} \sum_{j=i+1}^{n} v_{i,f} v_{j,f} x_i x_j = \frac{1}{2} \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) $$

第三步，代入并合并所有维度。 把这个结果代回第一步的求和式中：

$$ \sum_{f=1}^k \left( \frac{1}{2} \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) \right) = \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) $$

二阶项最终的化简结果：

$$ \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) $$

代入完整公式，化简后最终的FM公式是：

$$ y = w_0 + \sum_{i=1}^n w_i x_i + \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) $$

需要特别说明一句：实际项目里的代码实现，用的都是这个化简后的公式，而不是最开始那个双重求和的原始形式。

对每个隐向量维度f，先算出$\sum_{i=1}^n v_{i,f} x_i$（相当于把所有特征在这一维上的贡献先加总），这一步对所有f一起算是$O(kn)$；接下来平方求和是$O(k)$；再减去对角线上$i=j$那部分自乘项（也是$O(kn)$），把无效的自交叉排除出去。整体加起来，总复杂度就是$O(kn)$，和特征数n只是线性关系，而不是原始形式那种平方关系。

从直观上理解这三步分别在干什么：

• 平方项：捕获的是所有特征在隐空间某一维度上的联合贡献；
• 减去平方和：是为了消除特征自身的重复计算，也就是把$i=j$这种无意义的”自己和自己交叉”项去掉；
• 隐向量维度k：控制的是交互能表达的潜在语义空间大小，k越大表达能力越强，但计算量和过拟合风险也随之上升。

这个数学变换是整个FM方法里最值得记住的一步，没有它，FM大概率也就停留在论文里，不会在工业界大规模落地。

FM的复杂度分析

把参数复杂度、训练复杂度、推理复杂度分开看一遍。

参数复杂度：$O(kn)$。 对比一下POLY2：POLY2需要为每对特征组合单独存储参数$w_{ij}$，参数量是组合数$\frac{n(n-1)}{2}$（二阶项部分）；FM改为给每个特征学一个k维隐向量$V_i$，二阶项的参数量变成$kn$。当$k \ll n$时（k通常取几十到几百，n是one-hot之后的特征总数），参数量大幅减少。

训练时间复杂度：$O(kn)$。 这是前面推导的直接结果。

推理（预测）计算复杂度：$O(kn)$。 预测公式可以拆成两部分看：

$$ y = w_0 + \underbrace{\sum_{i=1}^n w_i x_i}_{\text{一阶项，} O(n)} + \underbrace{\sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle V_i, V_j \rangle x_i x_j}_{\text{二阶项，优化后为} O(kn)} $$

二阶项在化简之后：

$$ \sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle V_i, V_j \rangle x_i x_j = \frac{1}{2} \left( \sum_{f=1}^k \left( \sum_{i=1}^n v_{i,f} x_i \right)^2 - \sum_{i=1}^n \sum_{f=1}^k (v_{i,f} x_i)^2 \right) $$

具体分三步：先计算每个隐向量维度f的求和$\sum_i v_{i,f} x_i$，复杂度$O(kn)$；再平方后求和，复杂度$O(k)$；最后减去对角线项，复杂度$O(kn)$。三步加起来总复杂度还是$O(kn)$，和特征数n、隐向量维度k都只是线性关系，这才是FM能扛住工业级高维稀疏数据的根本原因。

优缺点分析

优点

参数共享机制。 用隐向量内积近似代替单独的参数$w_{ij} \approx \langle V_i, V_j \rangle$，二阶项参数量从POLY2的$\frac{n(n-1)}{2}$降为$kn$，这是前面反复强调的核心机制。

解决了稀疏性问题。 共享隐向量使得所有包含特征i的交互项都能用来训练$V_i$。即便某些特征组合在训练集里从未出现过，仍然可以通过隐向量内积算出它的权重——比如$w_{ij} = \langle V_i,V_j\rangle$和$w_{ik} = \langle V_i,V_k\rangle$共享了$V_i$，所有包含$V_i$的非零组合特征都可以用来学习$V_i$，这在数据稀疏的场景下是决定性的优势。

泛化能力提升。 FM可以预测训练数据中从未出现过的特征组合，靠的是隐向量内积计算新组合的权重，而不是依赖独立的、必须见过才能学到的参数。这是它相对POLY2最本质的进步。

缺点

高阶特征交叉能力有限。 FM默认只建模特征的两两交互（二阶多项式），没法直接捕获三阶及以上的特征组合关系。虽然理论上可以扩展出高阶FM，但计算复杂度会显著增加，性价比不高。这个短板后来主要靠DeepFM、xDeepFM这类模型来补，它们结合深度神经网络去捕捉高阶的非线性特征交互。

隐向量维度k需要人工选择。 k是一个预设的超参数，大小直接影响模型表现：k太小，特征交叉的表达能力不够，容易欠拟合；k太大，计算开销上升，还可能过拟合。这个超参数没有解析解，只能靠交叉验证去调，增加了训练的复杂度和成本。

对非稀疏数据提升有限。 FM的优势场景主要是稀疏数据，比如推荐系统、CTR预估里大量one-hot编码之后的类别特征。对于本身就是稠密特征的场景（比如图像、音频），FM的表现未必比得过神经网络一类的模型。另外，如果特征本身已经包含了显式的交互信息（比如人工构造好的组合特征），FM的隐式交叉反而可能带来不必要的冗余计算。

隐向量解释性较弱。 隐向量$V_i$本身的物理意义不直观，很难说清楚$\langle V_i, V_j \rangle$到底对应什么具体的业务逻辑，这是一种黑箱性。相比之下，线性模型的权重$w_i$，或者决策树的分裂规则，解释起来要直接得多。

计算效率的权衡。 FM相比POLY2已经好了很多，但也不是没有上限。它把二阶参数量从$O(n^2)$降到了$O(kn)$，可当特征数n极大时（比如百万维的稀疏特征），计算和存储隐向量仍然需要不小的资源。工业级场景里，往往还要结合哈希技巧或者模型压缩之类的手段进一步优化。

FFM引入特征域的FM

FFM（Field-aware Factorization Machine）相比FM（Factorization Machine）的核心优化，在于引入了特征域（Field） 的概念，让模型能够更细致地刻画特征间的交互。

简单来说，FM为每个特征学习一个隐向量，而FFM为每个特征针对不同域学习多个隐向量。

FM 的做法与局限

FM（Factorization Machine）的数学表达式为：

$$ y = 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 $$

关键在于隐向量 $ \mathbf{v}_i $。每个特征 $ i $ 只对应一个固定的隐向量 $ \mathbf{v}_i $。当特征 $ i $ 与任何特征 $ j $ 交互时，都使用这同一个向量 $ \mathbf{v}_i $ 去计算内积。

这带来一个问题：特征的“身份”在不同上下文里其实不一样，FM用同一个向量去参与这两种截然不同的交互，就会产生信息混淆，限制了模型的表达能力。

FFM 的优化：场感知

FFM 的表达式改进为：

$$ y = w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle \mathbf{v}_{i, f_j}, \mathbf{v}_{j, f_i} \rangle x_i x_j $$

这里的核心变化是 $ \mathbf{v}_{i, f_j} $。其中 $ f_j $ 代表特征 $ j $ 所属的域（Field）。

这意味着，特征 $ i $ 不再只有一个隐向量，而是为每一个域都维护一个独立的隐向量。具体来说：

• 当计算特征“周末”与“快餐”（域=菜品类型）的交互时，会用“周末”针对“菜品类型”域的隐向量。
• 当计算特征“周末”与“高端餐厅”（同样属于域=菜品类型）的交互时，会用同样的向量。
• 但当计算特征“周末”与“北京”（域=城市）的交互时，则会切换到“周末”针对“城市”域的另一个隐向量。

这让模型能根据交互对象的“域”来动态调整特征的表示，从而更精确地捕捉复杂关系。

FM的优化在于“用向量代替标量”，而FFM的优化在于“用一组向量代替单一向量”，让同一个特征在面对不同域的特征时，能拿出最合适的那一面来交互。

小结

从LR到POLY2再到FM，这条演进路线其实是同一个诉求推着走的：怎么在不引爆参数量、不被数据稀疏性卡死的前提下，把特征交叉的信息用起来。LR最先暴露了”特征独立假设”的短板；POLY2给出了正确的方向——显式引入交叉项——但没能解决工程上的两个硬伤，参数爆炸和稀疏训练不足；FM用隐向量的参数共享机制解决了稀疏性问题，又用一个漂亮的数学恒等式把复杂度从$O(n^2)$压到了$O(n)$级别，这才让”自动学习特征交叉”这件事真正在工业界跑了起来。FFM则是在表达能力上又往前推了一步，用训练成本的上升换取了区分”域”的能力。

理解这条推导逻辑，再去看DeepFM、xDeepFM乃至后面一大批基于Embedding的推荐模型，会顺畅很多——它们本质上都是在FM打下的这个地基上，继续往高阶和非线性方向添砖加瓦。