主要内容：動機
FM算法模型
FM算法VS 其他算法
一、動機
在傳統的線性模型如LR中，每個特征都是獨立的，如果需要考慮特征與特征直接的互動作用，可能需要人工對特征進行交叉組合；非線性SVM可以對特征進行kernel映射，但是在特征高度稀疏的情況下，并不能很好地進行學習；現在也有很多分解模型Factorization model如矩陣分解MF、SVD++等，這些模型可以學習到特征之間的互動隐藏關系，但基本上每個模型都隻适用于特定的輸入和場景。為此，在高度稀疏的資料場景下如推薦系統，FM(Factorization Machine)出現了。
下面所有的假設都是建立在稀疏資料的基礎上，舉個例子，根據使用者的評分曆史預測使用者對某部電影的打分，這裡的每一行對應一個樣本，Feature vector x表示特征，Targer y表示預測結果。從下圖可以看出，這是一個稀疏特征的例子，後面的相關内容會以此為例子進行說明。
特征中的前四清單示使用者u(one-hot編碼，稀疏)，接着五清單示電影i(ont-hot編碼，稀疏)，再接下去五清單示使用者u對電影i的打分(歸一化特征)，緊接着一清單示時間(連續特征)，最後五清單示使用者u對電影i打分前評價過的最近一部電影(one-hot編碼，稀疏)
二、FM算法模型
1、模型目标函數
二進制交叉的FM(2-way FM)目标函數如下：
其中，w是輸入特征的參數，是輸入特征i,j間的交叉參數，v是k維向量。
前面兩個就是我們熟知的線性模型，後面一個就是我們需要學習的交叉組合特征，正是FM差別與線性模型的地方。
為什麼要通過向量v的學習方式而不是簡單的wij參數呢？
這是因為在稀疏條件下，這樣的表示方法打破了特征的獨立性，能夠更好地挖掘特征之間的相關性。以上述電影為例，我們要估計使用者A和電影ST的關系w(A&ST)以更好地預測y，如果是簡單地考慮特征之間的共現情況來估計w(A&ST)，從已有的訓練樣本來看，這兩者并沒有共現，是以學習出來的w(A&ST)=0。而實際上，A和ST應該是存在某種聯系的，從使用者角度來看，A和B都看過SW，而B還看過ST，說明A也可能喜歡ST，說明A很有可能也喜歡ST。而通過向量v來表示使用者和電影，任意兩兩之間的互動都會影響v的更新，從前面舉的例子就可以看過，A和B看過SW，這樣的互動關系就會導緻v(ST)的學習更新，是以通過向量v的學習方式能夠更好的挖掘特征間的互相關系，尤其在稀疏條件下。
2、模型的計算複雜度
可能有人會問，這樣兩兩交叉的複雜度應該O(k*n^2)吧，其實，通過數學公式的巧妙轉化一下，就可以變成O(kn)了。轉化公式如下所示，其實就是利用了2xy = (x+y)^2 – x^2 – y^2的思路。
3、模型的應用
FM可以應用于很多預測任務，比如回歸、分類、排序等等。
1.回歸Regression：y^(x)直接作為預測值，損失函數可以采用least square error；
2.二值分類Binary Classification：y^(x)需轉化為二值标簽，如0,1。損失函數可以采用hinge loss或logit loss；
3.排序Rank：x可能需要轉化為pair-wise的形式如(X^a,X^b)，損失函數可以采用pairwise loss
4、模型的學習方法
前面提到FM目标函數可以線上性時間内完成，那麼對于大多數的損失函數而言，FM裡面的參數w和v更新通過随機梯度下降SGD的方法同樣可以線上性時間内完成，比如logit loss，hinge loss，square loss，模型參數的梯度計算如下：
這部分求和跟樣本i是獨立的，是以可以預先計算好。
5、模型延伸：多元交叉
前面提到到都是二進制交叉，其實可以延伸到多元交叉，目标函數如下：(看起來複雜度好像很高，其實也是可以線上性時間内完成的)
6、總結
前面簡單地介紹了FM模型，總的來說，FM通過向量交叉學習的方式來挖掘特征之間的相關性，有以下兩點好處：
1.在高度稀疏的條件下能夠更好地挖掘資料特征間的相關性，尤其是對于在訓練樣本中沒出現的交叉資料；
2.FM在計算目标函數和在随機梯度下降做優化學習時都可以線上性時間内完成。
三、FM算法 VS 其他算法
1、FM 對比 SVM
1)SVM
SVM是大家熟知的支援向量機模型，其模型原理在這裡就不詳述了。
SVM的線性模型函數表示為：
其非線性形式可以通過核映射kernel mapping的方式得到，如下所示：
其中多項式核表示為：
當d=2時為二次多項式，表示為：
多項式核映射後的模型函數表示為：
2)FM 對比 SVM
看到上面的式子，是不是覺得跟FM特别像？SVM和FM的主要差別在于，SVM的二進制特征交叉參數是獨立的，如wij，而FM的二進制特征交叉參數是兩個k維的向量vi、vj，這樣子的話，和就不是獨立的，而是互相影響的。
為什麼線性SVM在和多項式SVM在稀疏條件下效果會比較差呢？線性svm隻有一維特征，不能挖掘深層次的組合特征在實際預測中并沒有很好的表現；而多項式svn正如前面提到的，交叉的多個特征需要在訓練集上共現才能被學習到，否則該對應的參數就為0，這樣對于測試集上的case而言這樣的特征就失去了意義，是以在稀疏條件下，SVM表現并不能讓人滿意。而FM不一樣，通過向量化的交叉，可以學習到不同特征之間的互動，進行提取到更深層次的抽象意義。
此外，FM和SVM的差別還展現在：1)FM可以在原始形式下進行優化學習，而基于kernel的非線性SVM通常需要在對偶形式下進行；2)FM的模型預測是與訓練樣本獨立，而SVM則與部分訓練樣本有關，即支援向量。
2、FM 對比 其他分解模型Fac torization Model
這部分不詳述，其他分解模型包括Matrix factorization (MF)、SVD++、PITF for Tag Recommendation、Factorized Personalized Markov Chains (FPMC)，這些模型都隻在特定場景下使用，輸入形式也比較單一(比如MF隻适用于categorical variables)，而FM通過對輸入特征進行轉換，同樣可可以實作以上模型的功能，而且FM的輸入可以是任意實數域的資料，是以FM是一個更為泛化和通用的模型。詳細内容參考：https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf
四、參考文獻
1、《Factorization Machines》