FM/FFM-論文筆記

04-30

摘要

1、因式分解機(fm)結合了SVM和因式分解模型二者的優勢

(combine the advantages of suport vector machines with factorization models)

2、FM可以像SVM一樣處理real value 特徵，二者FM還可以處理稀疏的數據，而這裡SVM卻是失敗了的，FM處理稀疏數據主要機制是：因式分解參數可以對任何兩個特徵直接做組合。(they are able to estimate interactions even in problems with huge sparsity where SVM fail)

3、FM可以在線性時間完成計算，而不需要像SVM那樣需要對偶去轉換。

4、因式分解模型也有其他的，如，SVD++等，這些模型具有的缺點是只能在特點輸入數據上進行工作，而且更具不同的任務，模型的計算及優化要分別推導。

(they are not applicable for general prediction tasks but work only with special input data, and furthermore their model equations and optimizeation algoritms are derived indivally for each task)

介紹：

1、如，推薦系統等問題，SVM幾乎沒有重要的地位，在這些領域中最好的模型就是矩陣分解模型（matrix factorization）,SVM沒有在這些領域有所施展的原因是：SVM在稀疏數據在複雜（非線性）核空間中不能構學習到可信賴的參數（超平面）

(AVM are not successfull in these tasks is that they cannot learn reliable parameters(""hyperplnes)in complex(no-linear)kernel spaces under very sparse data

3、張量分解類模型最大的缺點在於：1）不能在標準的預測數據（real valued feature vector）中應用。2）特製模型的推導是在特製任務完成，需要精心設計學習演算法。

（1)they are not applicable to standard prediction data. 2)that specialized models are usually derived individually for specific task requiring effort in modelling and design the learning algorithm）

4、FM和其他模型比較如下：

FM在線性時間計算，計算時間與參數是呈線性關係，存儲模型的時候也不需要存儲訓練數據，而SVM需要存儲訓練數據（支持向量），SVM是在對偶空間中優化。而且FM將其他飲因式分解模型概括在內。

FM模型

模型公式，d=1，定義如下：

需要估計的參數有W0，Wi，V，<..>是大小為k的向量的點乘。

一行向量vi，k個元素的向量描述了第i個變數，(A row vi within V describe the i-th variable with k factors)。d=2，描述了捕捉所有兩個向量之間的組合(captures all single and pairwise interactions between variables)

參數描述：

w0，是全局偏置(global bias)

wi 是模型第i個變數的權重、

wij = <vi,vj>特徵i和j的交互，

數學中的概念：

眾所周知的是假如有一個正矩陣W，總是存在一個矩陣V，只要k足夠大，總會使得 $W=V.V^{T}$ 成立。在FM模型中如果選擇k足夠大，那麼矩陣W可以表達任何特徵之間的交互，在使用中典型的做法是k選擇會比較的小，因為數據量太小，FM中會限制k的大小，這樣導致更好的泛化性能，因此可以提升稀疏數據的交互（理解不透）

（Restricking K - and thus the expression of FM-lead to better generalization and thus improved interaction matrices under sparsity）

數學推導降低FM數學公式的複雜性：

模型的複雜度降低到O(kn)

FM可以應用到的任務：

回歸，二分類，排序

在使用FM應用到上述任務的時候，L2正則經常會加入到損失函數，以避免過擬合。

學習演算法

FM模型的複雜度為線性的，所以使用優化演算法可以很高效的學習這些參數W0，Wi，V

使用SGD學習如下：

作者開源出來自己的libFM庫，可以很容易的搜到，也有很多的FM實現，據說xlearn實現的libFM非常的高效(文檔上看到的)。

總結

FM可以在稀疏數據中學習到組合特徵，甚至是那些數據中沒有觀測值的組合特徵

(the interaction between values can be estimated even under high sparsity,especially, it is possible to generalize to unobserved interactions)

學習過程和參數的線性的，FM的學習更加有效

(The number of parameters as well as the time for prediction and learning is linear. This makes direct optimization using SGD feasible and allows optimizing against a variety of loss functions)

FM VS SVMs

線性SVM

多項式SVM：

式子9，和FM的式子1比較，二者的相同之處在於都試圖去構造這和特徵，不同的是式9組合特徵參數是相互獨立的，如第i個特徵和第j個特徵的組合特徵權值wij和第i個特徵和第k個特徵的組合特徵權值wik，而在FM中第i個特徵和第j個特徵的組合特徵權值<vi,vj>和第i個特徵和第k個特徵的組合特徵權值<vi,vk>有貢獻參數vi

為什麼SVM不能學習稀疏數據

稀疏數據中大部分值都是0，少數為1，假如只有第i個和第u個為1，

線性SVM的計算結果：

多項式SVM

------------------------------------------FFM---------------------------------------------

摘要

1、在CTR預估上FFM的性能超過了FM，

介紹

1、點擊率預估問題可視為二分類問題，採用邏輯回歸估計，邏輯回歸的參數獲得於解決如下問題：

式1中取，線性模型：

2、學習特徵間的關係或者是構造組合特徵（feature conjuctions）（似乎翻譯很不合適）是CTR預估中關鍵部分。

虛構出如下數據：採用如下數據去理解（feature conjuctions）

如Gucci對Vogue有很高的點擊率，但是一般模型會分別學習他們兩個各自的參數

FM模型也稱作為PITF(parewise interaction tensor factorization)

學習，feature conjuctions

1)2項式：

複雜度高O（n^2）

2) FM

將向量在隱空間做英式分解，經過數學推導複雜度能將到O（kn）

FM部分在介紹FM和SVM時候，由於稀疏數據中含有大量的0，和少量的1，在學習參數時候很多參數學習不充分或者學習不到（如，FM中的式10），這裡在FFM文章中作者也介紹為什麼FM優於2項式的原因：table1中ESPN和Adidas只有一個-1，在2項式中學習到的權重 $W_{ESPN,Adidas}$ 只能在這個數據中學習，但是FM中經過英式分解後二者的權重是有 $V_{Adidas}，V_{ESPN}$ 決定，而這兩個參數由可以是從其他的包含Adidas和ESPN數據中學習來的，學習到的會更加的精確。

FFM中提出field的概念，table1中將ESPN,Vogue和NBC屬於Publish field，NIKE，Adidas,Gicci歸為 Advertiser，一下解釋FFM是如何工作的：

對於FM計算會如下：（FFM論文中截圖，在FM論文中w應該是用v來表示，隱向量表示）

FM中每一個特徵只有一個隱向量，這些隱向量的學習也是依據與其他的特徵，如 $w_{ESPN}$ 的學習會受到一下的影響 $<W_{ESPN},W_{NIKE}>$ , $<W_{ESPN},W_{Male}>$ 然而NIKE和Male是來自於不同的域field，所以二者對 $w_{ESPN}$ 的影響肯定是不同的。

在FFM中每一個特徵都會有幾個隱向量，取決於使用的其他特徵field的個數，上圖在FFM中建模的式子為：

$w_{ESPN,A}$ ESPN與Advertiser域學習到的隱向量， $w_{ESPN,G}$ ESPN與Gender域學習到的隱向量，綜上

$f_{1}和f_{2}$ 分別是來自於j1和j2field，f為field的個數，那麼FFM的參數個數就是nfk，，式子4的複雜度為O(n^2k)，這對於FFM來說是沒關係的，因為每一個隱向量都需要去特定的field中學習，而且FFM中的k的設定《= FM中的k。

優化

使用AdaGrad去優化式子，x是稀疏的，只去更新那些x數據中非0項

FFM輸入數據格式

LIBSVM的數據格式是：

label feat1：value1 feat2：value2.。。。

FFM數據輸入格式：

label field1:feat1：value1 field2:feat2：value2.。。。

類別特徵：

一條數據

數值特徵：

實驗

FFM在kaggle兩個點擊率比賽的表現已經證明了他的能力，文中作者指出FFM對迭代次數epoch很敏感，並進行了分析，實驗中使用LIBNEAR和LIBFM分別訓練2項式和FM模型，及作者開發的LIBFFM模型。

1、k值並沒有太大的影響結果

2、正則項lambda和學習率alpha對結果的影響會蠻大

early-stopping會很好的改善FFM的訓練，從上圖就能看出了，及時的停止訓練能增加模型的泛化性能.

3、early_stopping

FFM中部署early_stopping的方法如下

但是FFM對訓練epoche很敏感（會有過擬合問題），early_stopping可能會提前停止，文中作者說了集中方法但是結論是都不如直接使用early_stopping（或者early_stopping的patience參數大點多訓練幾個epoche可以會好點，patience是keras中的early-stopping參數名稱），作者也在左後的總結中指出，解決這個問題（訓練epoche很敏感）是日後的工作