Factorization Machines/zh
| Article | |
|---|---|
| Topic area | Machine Learning |
| Difficulty | Introductory |
因子分解机（Factorization Machines，FMs）是一类有监督学习模型，它将多项式回归的表达能力与低秩矩阵分解的参数效率结合在一起。在稀疏、高维数据上尤为有效，例如点击率预测、推荐系统以及排序问题中出现的类别型特征。
概述
标准的多项式回归为每一对特征交互配置一个独立参数，这在输入稀疏时并不实用：大多数特征对在训练数据中出现得太少，难以可靠估计。因子分解机通过为每个特征赋予一个低维潜在向量，并将每个交互建模为相应向量的点积来回避这一问题。这样既显著减少了参数数量，又使得即使是训练中从未共同出现的特征对也能推断其交互强度，所得模型的训练时间与输入非零项数成线性关系。
因子分解机由 Steffen Rendle 于 2010 年提出，作为一个统一框架涵盖了若干专门化的协同过滤模型（矩阵分解、SVD++、因子分解的个性化马尔可夫链），并能自然地推广到任意特征向量。如今它们仍是稀疏表格数据上的强基线，并构成众多生产级排序系统的算法核心。
核心概念
- 潜在因子表示 —— 每个特征 $ j $ 都关联一个潜在因子向量 $ \mathbf{v}_j \in \mathbb{R}^k $；成对交互重用这些共享向量。
- 适应稀疏性 —— 只有活跃（非零）特征的梯度才不为零，因此优化代价随输入密度而非维度伸缩。
- 通用性 —— 单一特征向量可以编码用户 ID、物品 ID、上下文信号以及辅助信息，使因子分解机能够取代若干手工设计的推荐模型。
- 交互阶数 —— 二阶因子分解机建模成对交互；高阶因子分解机将思想推广到三元组及以上，尽管在实践中以二阶为主。
- 线性时间预测 —— 一种闭式重写将表面上 $ O(d^2 k) $ 的成对求和降为 $ O(d k) $，使推断在 Web 规模下变得切实可行。
历史
因子分解机由 Steffen Rendle 在 ICDM 2010 上提出，并在 2012 年 ACM TIST 论文 "Factorization Machines with libFM" 中得到详细阐述；该论文还介绍了具有重要影响的 libFM 参考实现，支持随机梯度下降、交替最小二乘以及马尔可夫链蒙特卡洛训练。2011 年，Rendle 等人证明因子分解机涵盖了张量分解和具有时间感知的推荐模型变体。
2016 年，Juan、Zhuang、Chin 和 Lin 引入了场感知因子分解机（FFMs）——一种在每个交互场中为特征赋予不同潜在向量的改进——并使用 FFMs 赢得了 Criteo 和 Avazu 的 CTR 预测 Kaggle 竞赛，巩固了该家族在工业广告中的声誉。同年，Guo 等人在 DeepFM 中将因子分解机与深度神经网络结合，掀起了一波 "deep + FM" 混合模型（xDeepFM、AutoInt、DCN-V2）的浪潮，并在 2010 年代后半段主导了 CTR 基准测试。因子分解机及其后继模型在 Criteo、Yahoo、阿里巴巴、美团等公司仍被广泛部署。
主要方法
二阶模型
对于输入向量 $ \mathbf{x} \in \mathbb{R}^d $，二阶因子分解机的预测为：
- $ \hat{y}(\mathbf{x}) = w_0 + \sum_{j=1}^{d} w_j x_j + \sum_{j=1}^{d} \sum_{j'=j+1}^{d} \langle \mathbf{v}_j, \mathbf{v}_{j'} \rangle \, x_j x_{j'} $
其中 $ w_0 \in \mathbb{R} $ 是全局偏置，$ w_j \in \mathbb{R} $ 是一阶权重，$ \mathbf{v}_j \in \mathbb{R}^k $ 是潜在因子。超参数 $ k $ 控制容量；常用取值在 8 到 64 之间。
线性时间重写
成对求和可以重写为：
- $ \sum_{j<j'} \langle \mathbf{v}_j, \mathbf{v}_{j'} \rangle x_j x_{j'} = \tfrac{1}{2} \sum_{f=1}^{k} \left[ \left( \sum_{j=1}^{d} v_{j,f} x_j \right)^{\!2} - \sum_{j=1}^{d} v_{j,f}^{2} x_j^{2} \right] $
这一恒等式将看起来的二次代价压缩为每个样本 $ O(d k) $，当 $ \mathbf{x} $ 中仅有 $ \bar{n} $ 个非零项时则为 $ O(\bar{n} k) $。同样的技巧也给出了廉价的解析梯度，使得用随机梯度下降或坐标上升进行高效训练成为可能。
损失函数与训练
因子分解机对损失函数无特定要求。常见选择有：用于回归的平方损失、用于二分类（CTR 预测）的逻辑损失，以及如贝叶斯个性化排序之类的成对排序损失。训练方式包括随机梯度下降、交替最小二乘（利用模型双线性结构的闭式坐标更新），以及通过 Gibbs 采样进行的贝叶斯推断——后者以更高的算力代价免去了大部分超参数调优。
场感知因子分解机
在 FFMs 中，每个特征对其可能交互的每个场（一组相关特征）都拥有独立的潜在向量。若特征 $ j $ 属于场 $ F_j $，交互项变为 $ \langle \mathbf{v}_{j, F_{j'}}, \mathbf{v}_{j', F_j} \rangle x_j x_{j'} $。这使参数数量增加一个等于场数的倍数，但在场划分得当时能持续提升 CTR 精度。
DeepFM 与神经网络混合模型
DeepFM 在 FM 组件（捕获低阶交互）和深度神经网络（捕获高阶非线性交互）之间共享一张嵌入表。xDeepFM 增加了显式的向量级乘积交叉网络，而 AutoInt 用自注意力层（参见Attention Mechanisms）替换了 FM 组件，以学习哪些交互重要。尽管创新不断，调优良好的普通因子分解机在许多表格基准上仍保持竞争力。
高阶因子分解机
该框架可推广到 $ m $ 路交互：
- $ \hat{y}(\mathbf{x}) = w_0 + \sum_j w_j x_j + \sum_{l=2}^{m} \sum_{j_1 < \dots < j_l} \left( \prod_{r=1}^{l} x_{j_r} \right) \sum_{f=1}^{k_l} \prod_{r=1}^{l} v^{(l)}_{j_r,f} $
更高阶能够捕获更丰富的组合结构，但会膨胀参数数量，且很少能胜过结合精心特征工程的二阶因子分解机。
关联
因子分解机介于若干经典模型之间。去掉交互项后退化为线性回归；使用逻辑损失且不进行因子分解时，则恢复为带有手工交叉特征的逻辑回归。当输入仅编码用户和物品的one-hot指示量时，便回到协同过滤的主力——矩阵分解。因子分解机与词嵌入共享低秩归纳偏置：二者都基于这样的思想，即稀疏符号实体之间的交互可以分解为共享的潜在向量。训练通常使用随机梯度下降或其变体，其正则化和学习率方面的考虑与任何损失驱动场景相同；对 $ w_j $ 和 $ \mathbf{v}_j $ 同时施加 L2 正则化是标准做法。在 DeepFM 等混合模型中，因子分解机提供显式的二阶信号，与深度神经网络通过反向传播学到的隐式高阶特征互为补充。对于二元 CTR 任务，最终预测会经过 sigmoid（二元 softmax）压缩，并以交叉熵损失进行训练。
参见
参考文献
- Rendle, S. (2010). "Factorization Machines". Proceedings of the IEEE International Conference on Data Mining (ICDM).
- Rendle, S. (2012). "Factorization Machines with libFM". ACM Transactions on Intelligent Systems and Technology, 3(3).
- Juan, Y.、Zhuang, Y.、Chin, W.-S. 与 Lin, C.-J. (2016). "Field-aware Factorization Machines for CTR Prediction". Proceedings of the 10th ACM Conference on Recommender Systems.
- Guo, H.、Tang, R.、Ye, Y.、Li, Z. 与 He, X. (2017). "DeepFM: A Factorization-Machine based Neural Network for CTR Prediction". Proceedings of IJCAI.
- Lian, J.、Zhou, X.、Zhang, F.、Chen, Z.、Xie, X. 与 Sun, G. (2018). "xDeepFM: Combining Explicit and Implicit Feature Interactions for Recommender Systems". Proceedings of KDD.
- Blondel, M.、Fujino, A.、Ueda, N. 与 Ishihata, M. (2016). "Higher-Order Factorization Machines". Advances in Neural Information Processing Systems (NeurIPS).