[Practical ML] Factorization Machine

01-25

最近看到一種「新」演算法（其實早就發布並且廣泛應用在工業界了，只不過我作為一個Infra Engineer比較後知後覺）: Factorization Machine。援引作者原話：

... We introduce Factorization Machines (FM) which are a new model class that combines the advantages of Support Vector Machines (SVM) with factorization models ... In contrast to SVMs, FMs model all interactions between variables using factorized parameters. Thus they are able to estimate interactions even in problems with huge
sparsity (like recommender systems) where SVMs fail...

TL;DR，按我個人的理解就是：

這是一種新的模型類型，可以用作任意Real-Value Vector的分類，跟LR/SVM一樣
它可以拿來對不同變數之間的Interaction建模（比如不同Feature之間的相關性），這點跟帶kernel的SVM類似；它勝過LR的也是這點，因為LR只是一個線性模型
它勝過SVM的地方在於，它使用了"factorization"（簡單來說，理解為矩陣分解？）來進行建模，這就使得它可以用於非常稀疏的Features，而SVM更適合用於Dense Feature，在Sparse Feature上表現並不好

下面進入技術細節

模型結構

我們先從Logistic Regression出發，回顧一下LR的Score Function

$y(X) = w_0 + sum_i^N w_i X_i$

基本就是一個線性模型，對輸入Feautre X的每一個緯度有一個參數w_i。好處是非常簡單，非常容易Scale Up，得到的泛化能力一般都還挺不錯，因此在工業界得到廣泛應用；壞處就是建模能力有限，畢竟只是一個線性模型。

那麼，下面是FM的Score Function

$y(X) = w_0 + sum_i^N w_i X_i + sum_i sum_j ig langle v_i, v_j ig angle X_i X_j$

這裡只是二階的情況（二階的意思是對變數兩兩之間關係建模，三階或更高就是對三個或更多個變數之間的關係進行建模），也是一般實際場景所用的模型。可以看到，跟LR相比，多出來一項是 $langle v_i, v_j angle X_i X_j$ ，其中 $v_i$ 是參數矩陣 $V$ 中的一行，而V是一個 N x k 的矩陣。也就是說，對X中的每一個變數，我們會用一個k維的向量（記住是一個向量，這很重要，後面會提到為什麼）來建模，然後每兩個變數之間的Interaction，就用這兩個k維向量的內積來模擬。

Scalability

前面講到LR的優勢之一是非常Scalable，所以在工業界得到廣泛應用——工業界一般有大量數據，但是計算資源有限啊，而且對實時性要求非常高，所以很多很酷炫，理論效果很好的模型反而得不到重用，就是因為Scalability的問題。前面看到，LR是線性的，基本是O(N)的複雜度；FM加了一個新的項之後，新加的那項看起來似乎需要 $O(N^2)$ 的複雜度，這似乎是不可忍受的複雜度，那為什麼FM還能得到廣泛應用呢？

主要原因就是，原作者通過一個數學Trick，把新加項的計算複雜度降到了O(kN) (k是可以自己選擇的參數，一般會遠遠遠遠小於N，所以基本就相當於O(N)了）。直接上原論文的圖，不感興趣的可以跳過：

得到這個牛逼的公式之後就可以直接上梯度下降了：）

深究與SVM的優劣——為什麼這個方法在Sparse Data下可以Work？

我們把上面FM的Score Function和一個帶有多項式Kernel（Degree=2）的SVM比較。我們知道，簡化來看，帶Kernel的SVM可以看作先把輸入X投影到另外一個特徵空間，再做線性分類的演算法。一個二項式kernel的SVM，相當於對輸入Feature做了如下的變換：

那麼Score Function就是：

可以看到基本上最大的區別就在於模擬變數兩兩Interaction的一項：在SVM裡面，對x_i 和x_j的Interaction，以及x_i和x_k之間的interaction的建模，也就是 $w_{ij}$ 和 $w_{ik}$ ，是相互獨立的參數；但是在FM裡面，這兩者互不獨立，因為 $langle v_i, v_j angle$ 和 $langle v_i, v_j angle$ 都依賴於 $v_i$ 。這點看似減少了模型的自由度，但是Sparse Feature的情況下發揮出了巨大的作用（以下為個人理解）：

對於SVM來說， $w_{ij}$ 必須在有足夠多的滿足 $x_i eq 0, x_j eq 0$ 樣本存在的情況下，才能得到很好的訓練。但是在輸入稀疏的情況下，在輸入特徵X裡面大部分的 $x_i$ 值都是0，更不必提 $x_i,x_j$ 同時不為0了。所以SVM在這種情況下不能得到很好的訓練。

反觀FM，儘管要訓練 $v_i,$ 也依賴於 $x_i eq 0$ ，但是好處是，所有其他非0的 $x_{j [j eq i]}$ 都會成為梯度的一部分，這樣對於 $v_i$ 的訓練就有明顯更多的訓練數據，可以更好地訓練出合適的參數。

同樣的道理，我們平常在工業界裡面常常採用的N-Gram Logistic Regression （人為對輸入特徵對二項式的變換，再把得到之後的特徵拿LR進行訓練），也由於同樣的問題，無法和FM在效果上媲美。

值得注意的是，這個特性是FM是優勢也是它的弊病。在輸入特徵比較稠密的情況下，其實FM的效果應該是並不如SVM的，因為SVM的模型自由度更高。

總結

FM作為一個通用的模型，在Scalability上可以和LR媲美，又可以拿來對變數之間的Interaction建模，在工業界中被廣泛應用於推薦系統，但理論上也可以應用於一般的分類問題。

PS: 封面圖是差分機，原因是個人內心獨白把Factorization Machine翻譯成「拆分機」。。。