sgr-interview-300

第 31 题：FM的二阶交互分解，复杂度从O(n²)到O(kn)的推导过程？

题目

FM的二阶交互分解，复杂度从O(n²)到O(kn)的推导过程？

完整讲解

一、FM 的二阶项原始形式

设特征向量 $\boldsymbol{x} \in \mathbb{R}^n$（已 one-hot 或离散化），FM 的二阶交互项定义为所有特征对 $(i,j)$ 的加权和。若用完整矩阵 $\boldsymbol{W} \in \mathbb{R}^{n \times n}$ 表示交互权重，则 $\phi^{(2)}(\boldsymbol{x}) = \sum_{i=1}^{n}\sum_{j=i+1}^{n} w_{ij} x_i x_j.$ 这里 $w_{ij}$ 有 $O(n^2)$ 个参数；且当特征稀疏时，很多 $(i,j)$ 在训练中几乎从未共现，$w_{ij}$ 难以学到可靠估计，参数量与样本需求都很大。

二、低秩分解：从 $O(n^2)$ 到 $O(kn)$

FM 的核心假设：交互矩阵可分解为低秩形式，即 $w_{ij} = \langle \boldsymbol{v}_i, \boldsymbol{v}_j \rangle$，其中 $\boldsymbol{v}_i, \boldsymbol{v}_j \in \mathbb{R}^k$，$k \ll n$。代入二阶项： $\phi^{(2)}(\boldsymbol{x}) = \sum_{i=1}^{n}\sum_{j=i+1}^{n} \langle \boldsymbol{v}_i, \boldsymbol{v}_j \rangle x_i x_j.$ 参数从 $n^2$ 变为 $n \cdot k$，即 $O(kn)$。接下来把双重求和化成「先按维度聚合、再平方差」的形式，实现计算也从 $O(n^2)$ 降到 $O(kn)$。

三、化简公式推导

利用恒等式 $2 \sum_{i<j} a_i a_j = \big(\sum_i a_i\big)^2 - \sum_i a_i^2$，令 $a_i = (\boldsymbol{v}_i x_i)$（这里为向量），对每一维 $f=1,\ldots,k$ 有： $\sum_{i=1}^{n}\sum_{j=i+1}^{n} (v_{i,f} x_i)(v_{j,f} x_j) = \frac{1}{2}\left[ \Big(\sum_{i=1}^{n} v_{i,f} x_i\Big)^2 - \sum_{i=1}^{n} (v_{i,f} x_i)^2 \right].$ 因此 $\phi^{(2)}(\boldsymbol{x}) = \frac{1}{2} \sum_{f=1}^{k} \left[ \Big(\sum_{i=1}^{n} v_{i,f} x_i\Big)^2 - \sum_{i=1}^{n} (v_{i,f} x_i)^2 \right].$

对每个 $f$：先对 $i$ 做一次遍历得到 $\sum_i v_{i,f} x_i$（$O(n)$），再算平方与第二项（$O(n)$），共 $O(n)$。
$k$ 维合计：总复杂度 $O(kn)$，且无需显式枚举所有 $(i,j)$，在稀疏 $\boldsymbol{x}$ 上只需遍历非零维度，工程上非常高效。

四、小结

FM 通过「交互矩阵低秩分解 + 代数化简」两步：参数量从 $O(n^2)$ 到 $O(kn)$，计算量从 $O(n^2)$ 到 $O(kn)$，同时缓解稀疏场景下二阶参数难学的问题，是 CTR 等场景里二阶特征交互的经典做法。

面试要点

能写出 FM 二阶项原始形式 $\sum_{i<j} w_{ij} x_i x_j$，并说明直接存 $w_{ij}$ 导致 $O(n^2)$ 参数与计算。
能写出低秩假设 $w_{ij} = \langle \boldsymbol{v}_i, \boldsymbol{v}_j \rangle$，参数变为 $O(kn)$。
能推导或口述「平方差」化简：$\sum_{i<j} (v_{i,f}x_i)(v_{j,f}x_j) = \frac{1}{2}[(\sum_i v_{i,f}x_i)^2 - \sum_i (v_{i,f}x_i)^2]$，从而每维 $O(n)$、总计 $O(kn)$。
能说明在稀疏特征下只遍历非零维，实现上进一步省计算。

记忆要点

FM 二阶：$\sum_{i<j} w_{ij} x_i x_j$；低秩 $w_{ij}=\langle \boldsymbol{v}_i,\boldsymbol{v}_j \rangle$ → 参数 $O(kn)$。
化简：$\sum_{i<j} (v_{i,f}x_i)(v_{j,f}x_j) = \frac{1}{2}[(\sum_i v_{i,f}x_i)^2 - \sum_i (v_{i,f}x_i)^2]$，按 $f$ 聚合 → 计算 $O(kn)$。
稀疏时只算非零维，工程友好。

返回模块

返回总览