Rendle S. Factorization machines[C]//2010 IEEE International conference on data mining. IEEE, 2010: 995-1000.
因子分解机（Factorization Machines，FM）是推荐系统中非常经典的一类模型。它在高维稀疏特征场景下，给出了一个非常优雅的二阶特征交叉建模方法。很多后续模型，例如 FFM、DeepFM、NFM，本质上都和 FM 有直接关系。
一、问题背景
在推荐系统、广告点击率预估、搜索排序等任务中，输入特征通常具有两个非常典型的特点：
- 维度很高
- 非常稀疏
例如一个样本可能包含如下信息：
- 用户 ID
- 性别
- 年龄段
- 城市
- 商品 ID
- 商品类别
- 广告位
- 时间段
这些离散特征通常会经过 one-hot 或 multi-hot 编码。编码之后，样本向量 $x$ 的维度可能非常大，但每个样本真正非零的位置却很少，因此形成了典型的高维稀疏输入。
在这种场景下，线性模型虽然训练稳定、实现简单，但表达能力有限；而复杂的高阶特征交叉如果直接显式建模，又会带来参数爆炸和严重的数据稀疏问题。
FM 就是在这个背景下提出的。
二、从线性模型说起
设输入特征向量为：
$$
x = (x_1, x_2, \ldots, x_n)
$$
最基本的线性模型可以写成：
$$
\hat y = w_0 + \sum_{i=1}^{n} w_i x_i
$$
其中：
- $w_0$ 是偏置项
- $w_i$ 是第 $i$ 个特征的线性权重
这个模型的含义很直接：每个特征独立地对预测结果产生影响。
例如：
- 男性用户对点击率有一个固定提升
- 晚上时段对点击率有一个固定提升
- 某个商品类别对点击率有一个固定提升
但问题在于，现实中的很多信号并不是“单个特征本身”决定的，而是“特征之间的组合关系”决定的。例如：
- 男性用户是否更偏好数码类商品
- 年轻用户是否更容易在夜间点击短视频内容
- 某个用户与某个商品之间是否存在强匹配
这些关系都不是一阶线性项能表达的。
三、显式二阶交叉的问题
为了引入特征交互，一个自然的想法是在线性模型上直接加入二阶项：
$$
\hat y = 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
$$
这里 $w_{ij}$ 表示第 $i$ 个特征和第 $j$ 个特征之间的交叉权重。
这个公式本身没有问题，甚至可以说非常自然。但它有两个致命缺点。
1. 参数量太大
如果有 n 个特征，那么二阶交叉参数 wij 的数量大约是：
$$
\frac{n(n-1)}{2}
$$
也就是 O(n^2) 级别。
在推荐系统中，特征维度常常以十万、百万计，显式学习所有特征对之间的参数几乎不可行。
2. 参数学习很困难
高维稀疏输入意味着大部分特征组合在训练集中出现次数极少，甚至一次都不出现。
例如：
- 用户 A 和商品 X 可能从未同时出现
- 城市 C 和品类 Y 的联合样本可能非常少
如果为每一对特征单独学习一个 $w_{ij}$，那么大量交叉参数根本没有足够样本支撑，估计会非常不稳定。
所以问题不只是“参数多”，更是“参数学不准”。
四、从显式二阶模型到 FM 的数学推导
如果我们把所有二阶交叉参数组织成一个矩阵 $W$，其中：
$$
W(i, j) = w_{ij}
$$
那么显式二阶模型可以写成更紧凑的形式：
$$
\hat y = w_0 + w^T x + \sum_{i=1}^{n} \sum_{j=i+1}^{n} w_{ij} x_i x_j
$$
如果进一步把 $W$ 视为一个对称矩阵，并约定对角线元素 $W(i, i) = 0$，那么上式也可以写成：
$$
\hat y = w_0 + w^T x + \frac{1}{2} x^T W x
$$
这里乘上 $\frac{1}{2}$ 的原因是：在 $x^T W x$ 中，$w_{ij} x_i x_j$ 和 $w_{ji} x_j x_i$ 会被重复计算两次。
写成矩阵形式之后，问题就更清楚了。FM 真正要解决的，其实不是“怎么随便造一个交叉项公式”，而是下面这个更本质的问题：
- 我们想学习一个二阶交互矩阵 $W$
- 但这个矩阵维度巨大，而且在稀疏数据下很难直接估计
- 所以需要给 $W$ 加一个强结构约束，让它既能表达交互，又能共享参数
FM 采用的约束就是：假设这个二阶交互矩阵是一个低秩矩阵，或者至少可以被一个低秩矩阵很好地近似。
具体来说，设：
$$
V \in \mathbb{R}^{n \times k}
$$
其中第 i 行记作特征 i 的隐向量：
$$
v_i = (v_{i1}, v_{i2}, \ldots, v_{ik})
$$
并且 $k \ll n$。如果令：
$$
W \approx V V^T
$$
那么矩阵元素就满足：
$$
w_{ij} \approx \langle v_i, v_j \rangle = \sum_{f=1}^{k} v_{if} v_{jf}
$$
这里有一个容易忽略的细节：$V V^T$ 的对角线元素 $W(i, i) = \langle v_i, v_i \rangle$ 通常不为 0。但 FM 在定义二阶项时只保留 $i < j$ 的交叉，因此真正参与预测的是非对角元素；自交叉项不会被算进去。
于是原来需要单独学习的每一个交叉权重 $w_{ij}$，都被改写成两个低维向量的内积。
这样一来，显式二阶模型：
$$
\hat y = 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
$$
就自然变成了 FM 的二阶形式：
$$
\hat y = w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle v_i, v_j \rangle x_i x_j
$$
所以从数学上看，FM 并不是凭空定义了一个内积形式，而是对“二阶交互矩阵 $W$ 做低秩分解”后的结果。
这个视角非常重要，因为它解释了“因子分解机”这个名字的由来：
- “因子”指的是每个特征对应的隐向量，也就是潜在因子
- “分解”指的是把原本庞大的交互矩阵 $W$ 分解成低秩形式 $V V^T$
五、低秩分解为什么成立
接下来的关键问题是：为什么可以假设 $W$ 是低秩的？
严格来说，这并不是说真实世界中的交互矩阵一定严格低秩，而是说在高维稀疏场景下，低秩约束是一种很有效的归纳偏置。
它隐含的假设是：
- 特征之间的交互并不是彼此完全独立的
- 很多交互关系可以由少数几个潜在语义维度解释
比如在推荐系统里，一个物品和一个用户是否匹配，往往并不需要为这对组合单独记一个参数，而是可能由几个更底层的因素决定，例如：
- 是否偏好某类内容
- 是否匹配某种价格带
- 是否符合某种时间场景
如果这些潜在因素的维度是 $k$，那么每个特征只需要学习一个 $k$ 维表示，很多交互关系就可以共享统计强度。
从参数化角度看，这相当于把原本自由度约为 $O(n^2)$ 的矩阵 $W$，限制在一个自由度约为 $O(nk)$ 的低秩空间内。这个限制虽然降低了模型表达能力，但换来了两个非常关键的好处：
- 参数量大幅下降
- 不同交互之间可以共享参数，从而提升稀疏场景下的泛化能力
六、这个公式到底在表达什么
这个公式可以分成三部分理解。
1. 偏置项
表示全局平均效应。
2. 一阶项
表示每个特征单独带来的线性贡献。
3. 二阶项
表示任意两个特征同时出现时，它们之间的交互影响。
其中最关键的是内积 $\langle v_i, v_j \rangle$。它可以理解为：
- 如果两个特征在隐空间中方向相近，内积较大，说明它们之间有较强正相关交互
- 如果两个特征关系弱，内积接近 0
- 如果方向相反，交互作用甚至可能为负
因此，FM 不再把“特征交叉”看作互相独立的离散事件，而是把每个特征映射到一个隐空间里，用隐空间中的相似性来表达交互强度。
七、为什么这种做法能缓解稀疏问题
这是 FM 最值得理解的地方。
在显式二阶模型里，$w_{ij}$ 只属于 $(i, j)$ 这一对特征。一旦 $(i, j)$ 在训练集中出现得很少，那么这个参数就学不好。
而在 FM 中，交互项变成：
$$
w_{ij} = \langle v_i, v_j \rangle
$$
此时：
- $v_i$ 不仅参与 $(i, j)$ 的交互
- 还参与 $(i, p)$、$(i, q)$、$(i, r)$ 等所有与特征 $i$ 相关的交互
因此，一个特征的隐向量会从许多样本和许多交互关系中共同学习。
举个直观的例子。
假设：
- 用户 A 看过电影 1、电影 2
- 用户 B 看过电影 1
那么即使“用户 B 和电影 2”这个组合在训练集中很少出现，模型仍然可能通过：
- $v_{\text{用户B}}$
- $v_{\text{电影2}}$
这两个向量各自在其他样本中的学习结果，推断出它们之间可能存在怎样的交互关系。
这就是 FM 能在稀疏场景下泛化的根本原因。
八、FM 的参数规模
如果直接学习显式二阶参数，那么总参数量大约为：
$$
O(n^2)
$$
而在 FM 中，需要学习的参数包括：
- 一个偏置项
w0 n个一阶权重wi- $n$ 个 $k$ 维隐向量 $v_i$
因此总参数规模约为：
$$
O(nk)
$$
只要 k << n，这个规模就远小于显式二阶模型。
例如：
- 若 $n = 100000$
- $k = 10$
则显式二阶参数规模约为 10^10 量级，而 FM 的隐向量参数规模只有 10^6 量级，两者完全不是一个数量级。
九、二阶项的高效计算
虽然 FM 用隐向量取代了显式交叉参数，但如果仍然直接根据定义计算：
$$
\sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle v_i, v_j \rangle x_i x_j
$$
那么时间复杂度依旧会达到 O(n^2 k)。
FM 之所以能真正落地，还因为它有一个非常重要的代数化简。这个化简本质上是在计算：
$$
\frac{1}{2} x^T (V V^T) x
$$
但如果直接先算出完整的 V V^T，代价仍然会非常高。FM 的技巧在于：不显式构造交互矩阵，而是直接在代数层面对求和式进行变形。
先把内积展开：
$$\begin{aligned}
\sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle v_i, v_j \rangle x_i x_j
&= \sum_{i=1}^{n} \sum_{j=i+1}^{n} \sum_{f=1}^{k} v_{if} v_{jf} x_i x_j
\end{aligned}$$
交换求和顺序：
$$\begin{aligned}
\sum_{i=1}^{n} \sum_{j=i+1}^{n} \sum_{f=1}^{k} v_{if} v_{jf} x_i x_j
&= \sum_{f=1}^{k} \sum_{i=1}^{n} \sum_{j=i+1}^{n} v_{if} v_{jf} x_i x_j
\end{aligned}$$
对于固定的第 f 个隐因子维度，有一个经典恒等式：
$$\begin{aligned}
\sum_{i=1}^{n} \sum_{j=i+1}^{n} a_i a_j
&= \frac{1}{2}\left[\left( \sum_{i=1}^{n} a_i \right)^2 - \sum_{i=1}^{n} a_i^2\right]
\end{aligned}$$
令：
$$
a_i = v_{if} x_i
$$
则可得：
$$\begin{aligned}
\sum_{i=1}^{n} \sum_{j=i+1}^{n} v_{if} v_{jf} x_i x_j
&= \frac{1}{2}\left[\left( \sum_{i=1}^{n} v_{if} x_i \right)^2 - \sum_{i=1}^{n} v_{if}^2 x_i^2\right]
\end{aligned}$$
因此二阶项可整体写成：
$$\begin{aligned}
\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}^2 x_i^2\right]
\end{aligned}$$
这样每个隐因子维度只需要对所有特征扫一遍，计算复杂度就从：
$$
O(n^2 k)
$$
降到了：
$$
O(nk)
$$
这也是 FM 在工业界非常实用的关键原因。
十、直观理解这个化简
这个化简的本质是：原本我们想逐对枚举所有特征交互，但实际上可以先在每个隐因子维度上把所有特征贡献加总，再扣掉自身和自身相乘的部分。
可以把它想象成：
- 先把所有特征在第 $f$ 维上的“投影贡献”加起来
- 对总和平方，就等于把所有两两组合都算进去了
- 但平方中包含了
i = j的自交叉项 - 所以再减去这些自交叉项
- 最后由于
(i, j)和(j, i)被重复计算一次，所以再乘1/2
这个推导很像很多线性代数和概率论里常见的“先整体求和，再扣除重复项”的技巧。
十一、一个简单样例
假设只有三个特征非零：
- $x_1 = 1$
- $x_2 = 1$
- $x_3 = 1$
并且设隐向量维度 $k = 2$，三个特征对应的隐向量分别为：
$$
v_1 = (1, 2)
$$
$$
v_2 = (2, 1)
$$
$$
v_3 = (1, 1)
$$
则交互项为：
$$
\langle v_1, v_2 \rangle x_1 x_2 + \langle v_1, v_3 \rangle x_1 x_3 + \langle v_2, v_3 \rangle x_2 x_3
$$
分别计算内积：
$$
\langle v_1, v_2 \rangle = 1 \cdot 2 + 2 \cdot 1 = 4
$$
$$
\langle v_1, v_3 \rangle = 1 \cdot 1 + 2 \cdot 1 = 3
$$
$$
\langle v_2, v_3 \rangle = 2 \cdot 1 + 1 \cdot 1 = 3
$$
所以二阶项总和为：
$$
4 + 3 + 3 = 10
$$
这个例子说明，FM 的每一对交互强度本质上都是通过隐向量相似性给出的，而不是一个单独存储的查表参数。
十二、FM 与矩阵分解的关系
FM 这个名字里有“分解”两个字，并不是偶然。它和矩阵分解（Matrix Factorization）有非常紧密的关系。
在推荐系统中，如果输入特征只包含：
- 用户 ID
- 物品 ID
并都用 one-hot 编码表示，那么每个样本通常只有一个用户特征和一个物品特征取值为 1。此时 FM 的二阶交互项就退化为：
$$
\langle v_{\text{user}}, v_{\text{item}} \rangle
$$
这和矩阵分解中的用户向量与物品向量内积是同一个思想。
因此可以认为：
- 矩阵分解是 FM 在特定输入形式下的特例
- FM 是把矩阵分解中的隐向量交互思想推广到了一般特征空间
十三、小结
FM 的核心公式是：
$$
\hat y = w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle v_i, v_j \rangle x_i x_j
$$
它最重要的思想可以概括成两句话：
- 用隐向量内积替代显式二阶交叉参数
- 用低秩分解解决高维稀疏场景下的交互建模问题
如果从建模角度看，FM 介于“线性模型”和“深度推荐模型”之间。它保留了线性模型对稀疏特征友好的优点，同时又引入了隐向量来建模特征交互，因此成为推荐系统历史上非常关键的一步。