導讀
Factorization Machines （FM）因子分解機是Steffen Rendle等人於2010年提出基於矩陣分解的機器學習算法，該模型結合了支持向量機（SVM）和因子分解模型的優點。本文詳細介紹了FM的模型表示、推到過程以及使用FM實現一個簡單的二分類任務。
01 FM為什麼可以工作
Factorization Machines （FM）是一種通用的預測器，可用於任何實值特徵向量。與支持向量機一樣，FM使用分解參數對變量之間的所有交互進行建模。因此，即使在支持向量機失效的推薦系統中，FM也能夠估計出交互性。並且對於稀疏數據，FM可以很好地估計變量間的相互作用。
下面我們以論文中給的電影評分數據，通過實際的例子來解釋為什麼FM對於稀疏數據有很好的表現。數據集中每一條記錄都包含了哪個用戶u在什麼時間t對哪部電影i打了多少分r。假定用戶集U和電影集I分別為：
則數據集S為：
利用觀測數據集S構造的特徵向量與標籤如下圖所示：
假設我們要估計愛麗絲（A）和《星際迷航》（ST）之間的相互作用，以預測A對ST的評級。顯然，在訓練數據中不存在變量x_A和x_ST都是非零的，因此直接估計將不會導致相互作用（w_{A，ST}=0）。但是，在這種情況下,FM可以通過因子化的相互作用參數，估計出A與ST之間的相互作用。
- 由於鮑勃對《星際迷航記》與《星球大戰》兩部電影都有相似的評分。故《星際迷航記》（ST）的因子向量很可能與《星球大戰》(SW)中的因子向量相似。
- 這意味著愛麗絲（A）與《星際迷航》中的因子向量的點積（即相互作用）將與愛麗絲（A）與《星球大戰》中的一個因子向量相似。
02 原理
與傳統線性模型不用的是因子分解機（FM）考慮了兩個互異的特徵向量之間的相互關係，在傳統線性模型的基礎上加入了交叉項。度為2的模型方程定義為：
上圖中，紅色框部分就是傳統的線性模型，黃色框部分為交叉項。
- w_0是全局偏置
- w_i為第i個變量的權重
- w_{i,j}是第i個和第j個變量之間的權重，模擬第i個變量與第j個變量間的相互關係
由於直接在交叉項 x_i,x_j 的前面加上交叉係數 w_{ij }的方式，在觀察樣本中未出現交互的特徵分量時，不能對相應的參數進行估計，故文章作者引入了輔助向量V_i=（v_{i1},v_{i2}, ..., v_{ik}）利用來對w{i,j}進行估計：
其中：
- 為兩個大小為K的向量的點積：
V中的行vi描述了具有k個因子的第i個變量。K是定義分解的維度的超參數，k 的大小稱為 FM 算法模型的度。
tips:k值的選取：若數據為稀疏的矩陣，k取較小值。
03 計算
接下來，將展示如何從計算的角度來應用FM。
在FM模型方程中，交叉項是最難計算的部分，對於交叉項的推倒，我們可以從矩陣的角度來理解。
1）首先根據[x_ix_j,]定義一個n*n的矩陣
可以由矩陣A中觀察到交叉項為矩陣A中除去對角線之後上三角元素的和：
- 此矩陣中所有元素的和為：
- 對角線元素之和為：
且矩陣中上、下三角元素之和相等，故：
2）由於
故
至此FM模型的目標函數可以表示為：
tips:通常添加L2正則項到優化目標中以防止過度擬合。
可以通過梯度下降方法（SGD）有效地學習FM的模型參數（w_0，w_i和V）
1）無論選擇什麼形式的損失函數，都可以先計算預測輸出y的偏導：
2）損失函數的選取：
- 迴歸問題：選擇最小均方誤差作為損失函數，即：
求偏導得：
即此損失函數下的梯度為：
- 分類問題：選擇對數損失函數，即：
其中：
即此損失函數下的梯度為：
04 實踐
在瞭解了原理之後，讓我們動手實踐一下，利用FM實現一個簡單的二分類！
- 加載數據
- 訓練數據與測試數據各兩百個。
- 初始化參數
- 將v按照正態分佈進行隨機初始化，w與w_0初始化為0。
- 計算
- 在該部分主要計算損失函數以及準確率。
- 保存模型
- 梯度下降法進行訓練
- 開始訓練，並將訓練得到的w_0,w,v保存在weight_FM中。
訓練結果如下：
訓練得到的權重
- 加載模型並保存預測結果
- 測試
部分測試結果如下：
至此，我們完成了用FM算法實現簡單二分類的實踐。
論文鏈接：
https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf
參考鏈接
https://github.com/GreenArrow2017/MachineLearning/tree/master/MachineLearning
https://github.com/Chaucergit/Code-and-Algorithm/tree/master/ML/3.Factorization%20Machine
