本文字數 2755，預計閱讀需要 6 分鐘
在計算廣告和推薦系統中，CTR 預估是非常重要的一個環節，判斷物品是否進行推薦，需要根據 CTR 預估的點擊率排序決定。業界常用的方法有人工特徵 + LR，GBDT + LR，FM 和 FFM 等模型。
近幾年提出了很多基於 FM 改進的方法，如 DeepFM，FNN，PNN，DCN，xDeepFM 等，今天給大家分享 FM。
FM（Factorization Machines，因子分解機）最早由 Steffen Rendle 於 2010 年在 ICDM 上提出，它是一種通用的預測方法，在即使數據非常稀疏的情況下，依然能估計出可靠的參數進行預測。與傳統的簡單線性模型不同的是，因子分解機考慮了特徵間的交叉，對所有嵌套變量交互進行建模（類似於SVM 中的核函數），因此在推薦系統和計算廣告領域關注的點擊率 CTR 和轉化率 CVR 兩項指標上有著良好的表現。
此外，FM 的模型還具有可以用線性時間來計算，以及能夠與許多先進的協同過濾方法（如 Bias MF、SVD++ 等）相融合等優點。
1、什麼是 Factorization Machine？
One-Hot 帶來的問題？
在面對 CTR 預估的問題的時候，我們常常會轉化為下面這種類型的二分類問題。
由於 性別，國別 等特徵都是類別特徵，所以在使用的時候常常採用 One-Hot Encoding 將其轉化為數值類型。
上圖可以看出，在經過 One-Hot 編碼之後，每個樣本的特徵空間都變大了許多，特徵矩陣變得非常稀疏，在現實生活中，我們常常可以看見超過 10⁷ 維的特徵向量。
如果我們採用單一的線性模型來學習用戶的點擊，打分習慣，我們很容易忽略特徵潛在的組合關係，比如：女性喜歡化妝品，男性喜歡打遊戲，買奶粉的用戶常常買尿不溼等。
二階多項式核 SVM
SVM 為了學習交叉特徵，引入了核函數的概念，最簡單直接的做法就是為兩兩的特徵組合分配一個權重參數。這些新的權重參數和原始特徵對應的參數一樣，交給模型去在訓練階段學習。如此一來就形成了如下的預測函數：
這實際上就是核函數選擇為二階多項式核的 SVM 模型。這樣設計的模型看起來能夠學到特徵的兩兩交叉帶來的信息，但這只是理論上的改進，但是模型在處理大量稀疏數據時，沒有很好的泛化能力。
由於 w_{i,j} 的取值完全取決於 x_i 和 x_j 的乘積，在數據稀疏的場景下，可能存在訓練集中 x_ix_j 始終為零的情況，這樣一來，模型就無法有效的更新權重 w_{i,j} 了，更進一步，在預測階段，模型遇到 x_ix_j 不為零的情況就很難有效的泛化。
因子分解機模型
既然二階多項式核 SVM 泛化性能不足的原因是 w_{i,j} 的取值完全取決於 x_i 和 x_j 的乘積，那麼最直接的辦法就是突破這一限制了。
FM 模型的解決辦法是為每個維度的特徵 (x_i) 學習一個表徵向量 (v_i， 其實可以理解為特徵 ID 的 Embedding 向量)。而後將 x_i 和 x_j 的乘積的權重設定為各自表徵向量的點積，也就是有如下形式的預測函數：
顯然，FM 模型也具有二階多項式核 SVM 的優點：能夠學習到特徵兩兩交叉帶來的信息。
那麼為什麼 FM 相對二階多項式核 SVM 做出的改進能提高模型的泛化性能？
通過下面這個表達可以看出，FM 很像是計算每個經過 One-Hot 編碼變化的特徵 Embedding，然後學習不同特徵之間 Embedding 相似度對於最後預測結果的影響。由於我們可以將上千萬維的稀疏向量壓縮為幾十，或者幾百維的 Embedding，極大地減小了模型的參數數量級，從而增強模型的泛化能力，得到更好的預測結果。
我們回到上一小節舉的例子：訓練集中 x_ix_j 始終為零。在二階多項式核 SVM 中，由於參數權重 w_{i,j} 得不到更新，模型無法學到 x_i 和 x_j 交叉帶來的信息。但是在 FM 中，x_i 和 x_j 的參數並不完全由 x_i 和 x_j 的乘積決定。具體來說，每一維特徵的表徵向量由該維特徵與其它所有維度特徵的交叉共同決定。於是，只要存在某個 k 使得 x_i 和 x_k 的乘積不總是為零，那麼第 i 維特徵的表徵向量 v_i 就能夠學到有效的信息—同理對 v_j 也有同樣的結論。於是乎，哪怕在訓練集中，x_ix_j 始終為零，其參數 ⟨v_i,v_j⟩ 也是經過了學習更新的，因此能夠表現出很好的泛化性能。
FM 和矩陣分解
基於矩陣分解的協同過濾是推薦系統中常用的一種推薦方案，從歷史數據中收集 user 對 item的 評分，可以是顯式的打分，也可以是用戶的隱式反饋計算的得分。由於 user 和 item 數量非常多，有過打分的 user 和 item 對通常是十分稀少的，基於矩陣分解的協同過濾是來預測那些沒有過行為的 user 對 item 的打分，實際上是一個評分預測問題。
矩陣分解的方法假設 user 對 item 的打分 R 由 User Embedding 和 Item Embedding 相似性以及用戶，物品的偏見決定。
這些參數可以通過最小化經驗誤差得到:
從上面的敘述來看，FM 的二階矩陣也用了矩陣分解的技巧，那麼基於矩陣分解的協同過濾和 FM 是什麼關係呢？以 user 對 item 評分預測問題為例，基於矩陣分解的協同過濾可以看做 FM的一個特殊例子，對於每一個樣本，FM 可以看做特徵只有 userid 和 itemid 的 onehot 編碼後的向量連接而成的向量。另外，FM 可以採用更多的特徵，學習更多的組合模式，這是單個矩陣分解的模型所做不到的！因此，FM 比矩陣分解的方法更具普遍性！事實上，現在能用矩陣分解的方法做的方案都直接上 FM 了!
FM 如何解決效率問題？
考慮到 FM 模型會對特徵進行二階組合，在有 n 個原始特徵時，交叉特徵就會有 (n^2-n)/2 個。因此，如果不做任何優化，FM 模型的複雜度會是 O(n2)，具體來說是 O(kn^2)（其中 k 是表徵向量的長度）。在特徵規模非常大的場景中，這是不可接受的。
那麼問題來了，是否有辦法將複雜度降低到 O(kn) 呢？答案是可以的，我們來看針對特徵交叉項的一系列變換。
可以看到這時的時間複雜度為 O(kn)。
參數學習
從上面的描述可以知道FM可以在線性的時間內進行預測。因此模型的參數可以通過梯度下降的方法（例如隨機梯度下降）來學習，對於各種的損失函數。FM 模型的梯度是：
與 i 是獨立的，可以提前計算出來，並且每次梯度更新可以在常數時間複雜度內完成，因此 FM 參數訓練的複雜度也是 O(kn) 。綜上可知，FM 可以在線性時間訓練和預測，是一種非常高效的模型。
總結
FM模型有兩個優勢：
- 在高度稀疏的情況下特徵之間的交叉仍然能夠估計，而且可以泛化到未被觀察的交叉
- 參數的學習和模型的預測的時間複雜度是線性的
- FM是一個通用模型，它可以用於任何特徵為實值的情況
FM模型的優化點：
- 特徵為全交叉，耗費資源，通常 user 與 user，item 與 item 內部的交叉的作用要小於 user 與 item 的交叉。
- 使用矩陣計算，而不是 for 循環計算。
- 高階交叉特徵的構造。
閱讀更多 隨時學丫 的文章
