摘要
在實際的應用場景中，資料的稀疏性會大大降低支援向量機（support vector machine，svm）等經典算法的預測性能。另外，傳統的因式分解類算法，如矩陣分解（Matrix Factorization，MF）泛化能力弱，無法滿足實際需求。為解決上述問題，Steffen Rendle提出一種基于分解思想的算法，即因子分解機（Factorization Machines，FM）。憑借出色的通用性以及較低的線性計算複雜度，FM 在推薦算法大家族中起着舉足輕重的作用。
1. FM模型
本小節将簡要地介紹FM的工作模型。
FM的模組化公式為：
算法需要學習的參數為：
其中， V V V是一個因子矩陣，裡面包含n個物品與k個隐類的關系。
式（1）是FM的模型公式。 w 0 w_0 w0是全局偏置， w i w_i wi表示具體某一個樣本的權重，< v i v_i vi, v j v_j vj>表示兩個樣本的互動權重（interaction）。是以，FM的輸出是由全局偏置，單樣本資訊，樣本互動資訊三個部分組成的。
式（2）表示模型要學習的參數，可以看出 V V V是一個n行k列的矩陣，行數表示具體的樣本，列數表示隐變量。舉個例子：
其中，每一列代表一個隐變量，當然隐變量往往具有不可解釋性，這裡隻是為了友善讀者了解而賦予其具體含義。
式（3）說明< v i v_i vi, v j v_j vj>表示兩個向量做點積，而我們知道點積可以用來計算兩個向量的相似性，是以互動權重可以用來表示兩個使用者的相似性。
2. FM如何解決資料的稀疏性
在實際的業務場景中，資料往往具有一定的稀疏性，産生這種稀疏性往往有兩個原因：資料缺失（使用者沒對某一個電影進行評分）以及one-hot編碼。舉一個電影評分的例子：
上圖中，藍色框代表使用者，紅色框代表目前被評分的電影，黃色框表示使用者的曆史打分情況，綠色框表示最近一次打分到現在的時間，紫色塊表示最後一次評分的電影。
那 麼 ， 稀 疏 性 會 帶 來 什 麼 問 題 ？ \color{red}{那麼，稀疏性會帶來什麼問題？} 那麼，稀疏性會帶來什麼問題？
假設現在目的是預估使用者A對電影ST的評分，從上圖可以發現，沒有一個樣本x的A列和ST列同時為非0（這說明使用者A從來沒對電影ST産生過互動），是以一般的算法可能因為缺乏資訊而不能預估A對ST的評分。
那 麼 ， F M 怎 麼 解 決 稀 疏 性 帶 來 的 問 題 呢 ？ \color{red}{那麼，FM怎麼解決稀疏性帶來的問題呢？} 那麼，FM怎麼解決稀疏性帶來的問題呢？
回顧公式（1），FM在計算預測值時引入了互動資訊，是以可以依賴模型學習到的互動資訊來進行估計(相當于饒了一點路，迂回估計)。 同樣以預估使用者A對電影ST為例，用B對ST與SW的評分幾乎一樣，那麼可以認為ST 與SW的隐向量（ v s w v_{sw} vsw, v s t v_{st} vst）幾乎一緻，那麼就可以通過使用者A對電影SW的評分來估計使用者A對電影ST的評分。
3 FM的線性複雜度
觀察FM的模型公式（公式1），由于需要計算樣本的互動資訊，FM的計算複雜度為 O （ O（ O（kn2 ） ） ），但對公式1進行轉換之後，可以把線性複雜度降低至 O ( k n ) O(kn) O(kn)。
公式1經過轉化後具有可直接求導的性質，是以就可以很友善地使用随機梯度下降法（Stochastic Gradient Descent，SGD）等優化算法進行求解。
4.FM與其他算法的對比
4.1 FM與SVM的對比
與SVM對比，FM具有以下優點：
- FM可以直接求解，而SVM需要先把原問題轉化成對偶問題再求解
- 可以處理稀疏資料：SVM處理稀疏資料的能力很弱，如下圖。 原因分析：在使用高階核的情況下，要準确估計高階的互動資訊參數 w i , j w_{i,j} wi,j（高階會産生很多互動項，了解以下 ( x 1 + x 2 ) (x_1+x_2) (x1+x2)的平方就好了），SVM要求 x i x_i xi, x j x_j xj均不為零，這就要求資料不能太稀疏。
（推薦系統） FM算法：Factorization Machines摘要1. FM模型2. FM如何解決資料的稀疏性3 FM的線性複雜度4.FM與其他算法的對比5 總結 - FM對訓練資料的依賴性不高，SVM的效果很依賴支援向量。
4.2 FM與傳統因子分解算法的對比
經推導發現，FM可以近似模拟如SVD++，矩陣分解，PITF等傳統的因子分解算法這說明FM具有良好的泛化性。詳細的公式推導建議閱讀原論文，此處不作贅述。
5 總結
本來簡要地對FM算法進行了梳理，筆者認為FM算法十分經典，是後序涉及因子分解思想的算法的基礎。應重點了解FM算法為何FM能解決稀疏性的問題以及如何降低算法複雜度。
FM算法也為設計推薦算法提供了幾個需要考慮的次元：
- 是否充分考慮了互動資訊
- 怎麼去解決資料稀疏的問題
- 求解是否友善？
- 算法複雜度如何？
- 泛化性如何？算法是否隻對某些資料有效？