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).