因子分解機(FM) +場感覺分解機 (FFM) 入門

前言

FM和FFM模型是最近幾年提出的模型，憑借其在資料量比較大并且特征稀疏的情況下，仍然能夠得到優秀的性能和效果的特性，屢次在各大公司舉辦的CTR預估比賽中獲得不錯的戰績。在計算廣告領域，點選率CTR（click-through rate）和轉化率CVR（conversion rate）是衡量廣告流量的兩個關鍵名額。準确的估計CTR、CVR對于提高流量的價值，增加廣告收入有重要的指導作用。預估CTR/CVR，業界常用的方法有人工特征工程 + LR、GBDT+ LR[1][2][3]、FM（Factorization Machine）[2][7]和FFM[9]模型。在這些模型中，FM和FFM近年來表現突出，分别在由Criteo和Avazu舉辦的CTR預測競賽中奪得冠軍[4][5]。

FM原理

FM（Factorization Machine）是由Konstanz大學Steffen Rendle于2010年最早提出的，旨在解決稀疏資料下的特征組合問題[7]。以一個示例引入FM模型。假設一個廣告分類的問題，根據使用者和廣告位相關的特征，預測使用者是否點選了廣告。源資料如下[8]

Clicked?	Country	Day	Ad_type
1	USA	26/11/15	Movie
China	1/7/14	Game
1	China	19/2/15	Game

"Clicked?"是label，Country、Day、Ad_type是特征。由于三種特征都是categorical類型的，需要經過獨熱編碼（One-Hot Encoding）轉換成數值型特征。

Clicked?	Country=USA	Country=China	Day=26/11/15	Day=1/7/14	Day=19/2/15	Ad_type=Movie	Ad_type=Game
1	1	1	1
1	1	1
1	1	1	1

由上表可以看出，經過One-Hot編碼之後，大部分樣本資料特征是比較稀疏的。上面的樣例中，每個樣本有7維特征，但平均僅有3維特征具有非零值。實際上，這種情況并不是此例獨有的，在真實應用場景中這種情況普遍存在。例如，CTR/CVR預測時，使用者的性别、職業、教育水準、品類偏好，商品的品類等，經過One-Hot編碼轉換後都會導緻樣本資料的稀疏性。特别是商品品類這種類型的特征，如商品的末級品類約有550個，采用One-Hot編碼生成550個數值特征，但每個樣本的這550個特征，有且僅有一個是有效的（非零）。由此可見，資料稀疏性是實際問題中不可避免的挑戰。

One-Hot編碼的另一個特點就是導緻特征空間大。例如，商品品類有550維特征，一個categorical特征轉換為550維數值特征，特征空間劇增。

同時通過觀察大量的樣本資料可以發現，某些特征經過關聯之後，與label之間的相關性就會提高。例如，“USA” 與 “Thanksgiving” 、“China”與“Chinese New Year”這樣的關聯特征，對使用者的點選有着正向的影響。換句話說，來自“China”的使用者很可能會在“Chinese New Year”有大量的浏覽、購買行為，而在“Thanksgiving”卻不會有特别的消費行為。這種關聯特征與label的正向相關性在實際問題中是普遍存在的，如“化妝品”類商品與“女”性，“球類運動配件”的商品與“男”性，“電影票”的商品與“電影”品類偏好等。是以，引入兩個特征的組合是非常有意義的。

多項式模型是包含特征組合的最直覺的模型。在多項式模型中，特征 

和 

的組合采用 

表示，即 

和 

都非零時，組合特征

才有意義。從對比的角度，本文隻讨論二階多項式模型。模型的表達式如下

                                             (1)

其中，

代表樣本的特征數量，

是第 

個特征的值，

、

、

 是模型參數。

從公式(1)可以看出，組合特征的參數一共有 

個，任意兩個參數都是獨立的。然而，在資料稀疏性普遍存在的實際應用場景中，二次項參數的訓練是很困難的。其原因是，每個參數 

的訓練需要大量 

和 

都非零的樣本；由于樣本資料本來就比較稀疏，滿足“

和 

都非零”的樣本将會非常少。訓練樣本的不足，很容易導緻參數 

不準确，最終嚴重影響模型的性能。

那麼，如何解決二次項參數的訓練問題呢？矩陣分解提供了一種解決思路。在model-based的協同過濾中，一個rating矩陣可以分解為user矩陣和item矩陣，每個user和item都可以采用一個隐向量表示[8]。比如在下圖中的例子中，我們把每個user表示成一個二維向量，同時把每個item表示成一個二維向量，兩個向量的點積就是矩陣中user對item的打分。

類似地，所有二次項參數 

可以組成一個對稱陣 

（為了友善說明FM的由來，對角元素可以設定為正實數），那麼這個矩陣就可以分解為 

，

 的第 

列便是第 

維特征的隐向量。換句話說，每個參數 

，這就是FM模型的核心思想。是以，FM的模型方程為（本文不讨論FM的高階形式）

                                   (2)

其中，

是第 

維特征的隐向量，

代表向量點積。隐向量的長度為

（

），包含 

個描述特征的因子。根據公式(2)，二次項的參數數量減少為 

個，遠少于多項式模型的參數數量。另外，參數因子化使得 

的參數和 

的參數不再是互相獨立的，是以我們可以在樣本稀疏的情況下相對合理地估計FM的二次項參數。具體來說，

和 

的系數分别為 

和 

，它們之間有共同項 

。也就是說，所有包含“

的非零組合特征”（存在某個

，使得 

）的樣本都可以用來學習隐向量 

，這很大程度上避免了資料稀疏性造成的影響。而在多項式模型中，

和 

是互相獨立的。

顯而易見，公式(2)是一個通用的拟合方程，可以采用不同的損失函數用于解決回歸、二進制分類等問題，比如可以采用MSE（Mean Square Error）損失函數來求解回歸問題，也可以采用Hinge/Cross-Entropy損失來求解分類問題。當然，在進行二進制分類時，FM的輸出需要經過sigmoid變換，這與Logistic回歸是一樣的。直覺上看，FM的複雜度是 

。但是，通過公式(3)的等式，FM的二次項可以化簡，其複雜度可以優化到 

[7]。由此可見，FM可以線上性時間對新樣本作出預測。

                       (3)

下面給出詳細證明過程：

其中第（1）步到第（2）步，這裡用AA表示系數矩陣VV的上三角元素，BB表示對角線上的交叉項系數。由于系數矩陣VV是一個對稱陣，是以下三角與上三角相等，有下式成立： 

我們再來看一下FM的訓練複雜度，利用SGD（Stochastic Gradient Descent）訓練模型。模型各個參數的梯度如下:

                               (4)

其中，

 是隐向量 

 的第 

個元素。由于

隻與 

有關，而與 

無關，在每次疊代過程中，隻需計算一次所有 

 的 

，就能夠友善地得到所有 

的梯度。顯然，計算所有

的 

的複雜度是

；已知

時，計算每個參數梯度的複雜度是 

；得到梯度後，更新每個參數的複雜度是 

；模型參數一共有 

個。是以，FM參數訓練的複雜度也是 

。綜上可知，FM可以線上性時間訓練和預測，是一種非常高效的模型。

FM與其他模型的對比

FM是一種比較靈活的模型，通過合适的特征變換方式，FM可以模拟二階多項式核的SVM模型、MF模型、SVD++模型等[7]。

相比SVM的二階多項式核而言，FM在樣本稀疏的情況下是有優勢的；而且，FM的訓練/預測複雜度是線性的，而二項多項式核SVM需要計算核矩陣，核矩陣複雜度就是N平方。

相比MF而言，我們把MF中每一項的rating分改寫為

，從公式(2)中可以看出，這相當于隻有兩類特征 

和 

的FM模型。對于FM而言，我們可以加任意多的特征，比如user的曆史購買平均值，item的曆史購買平均值等，但是MF隻能局限在兩類特征。SVD++與MF類似，在特征的擴充性上都不如FM，在此不再贅述。

FFM原理

FFM（Field-aware Factorization Machine）最初的概念來自Yu-Chin Juan（阮毓欽，畢業于中國台灣大學，現在美國Criteo工作）與其比賽隊員，是他們借鑒了來自Michael Jahrer的論文[14]中的field概念提出了FM的更新版模型。通過引入field的概念，FFM把相同性質的特征歸于同一個field。以上面的廣告分類為例，“Day=26/11/15”、“Day=1/7/14”、“Day=19/2/15”這三個特征都是代表日期的，可以放到同一個field中。同理，商品的末級品類編碼生成了550個特征，這550個特征都是說明商品所屬的品類，是以它們也可以放到同一個field中。簡單來說，同一個categorical特征經過One-Hot編碼生成的數值特征都可以放到同一個field，包括使用者性别、職業、品類偏好等。在FFM中，每一維特征 xixi，針對其它特征的每一種field fjfj，都會學習一個隐向量 vi,fjvi,fj。是以，隐向量不僅與特征相關，也與field相關。也就是說，“Day=26/11/15”這個特征與“Country”特征和“Ad_type"特征進行關聯的時候使用不同的隐向量，這與“Country”和“Ad_type”的内在差異相符，也是FFM中“field-aware”的由來。

假設樣本的 

個特征屬于

個field，那麼FFM的二次項有 

個隐向量。而在FM模型中，每一維特征的隐向量隻有一個。FM可以看作FFM的特例，是把所有特征都歸屬到一個field時的FFM模型。根據FFM的field敏感特性，可以導出其模型方程。

                                   (4)

其中，

是第 

個特征所屬的field。如果隐向量的長度為 

，那麼FFM的二次參數有 

個，遠多于FM模型的 

個。此外，由于隐向量與field相關，FFM二次項并不能夠化簡，其預測複雜度是 

。

下面以一個例子簡單說明FFM的特征組合方式[9]。輸入記錄如下

User	Movie	Genre	Price
YuChin	3Idiots	Comedy, Drama	$9.99

這條記錄可以編碼成5個特征，其中“Genre=Comedy”和“Genre=Drama”屬于同一個field，“Price”是數值型，不用One-Hot編碼轉換。為了友善說明FFM的樣本格式，我們将所有的特征和對應的field映射成整數編号。

Field name	Field index	Feature name	Feature index
User	1	User=YuChin	1
Movie	2	Movie=3Idiots	2
Genre	3	Genre=Comedy	3
Price	4	Genre=Drama	4
Price	5

那麼，FFM的組合特征有10項，如下圖所示。

其中，紅色是field編号，藍色是特征編号，綠色是此樣本的特征取值。二次項的系數是通過與特征field相關的隐向量點積得到的，二次項共有 

個。

FFM實作

Yu-Chin Juan實作了一個C++版的FFM模型，源碼可從Github下載下傳[10]。這個版本的FFM省略了常數項和一次項，模型方程如下。

                                                (5)

其中，

是非零特征的二進制組合，

是特征，屬于field 

，

是特征

對field 

 的隐向量。此FFM模型采用logistic loss作為損失函數，和L2懲罰項，是以隻能用于二進制分類問題。

其中，

 是第 

個樣本的label，

是訓練樣本數量，

是懲罰項系數。模型采用SGD優化，優化流程如下。

參考 

, 下面簡單解釋一下FFM的SGD優化過程。

算法的輸入 

、

、

分别是訓練樣本集、驗證樣本集和訓練參數設定。

1. 根據樣本特征數量（

   

   ）、field的個數（

   

   ）和訓練參數（

   

   ），生成初始化模型，即随機生成模型的參數；
2. 如果歸一化參數 

   

   為真，計算訓練和驗證樣本的歸一化系數，樣本 i 的歸一化系數為：

   

3. 對每一輪疊代，如果随機更新參數 

   

   為真，随機打亂訓練樣本的順序；
4. 對每一個訓練樣本，執行如下操作
   • 計算每一個樣本的FFM項，即公式(5)中的輸出 

     

     ；
   • 計算每一個樣本的訓練誤差，如算法所示，這裡采用的是交叉熵損失函數 

     

     ；
   • 利用單個樣本的損失函數計算梯度

     

     ，再根據梯度更新模型參數；
5. 對每一個驗證樣本，計算樣本的FFM輸出，計算驗證誤差；
6. 重複步驟3~5，直到疊代結束或驗證誤差達到最小。

在SGD尋優時，代碼采用了一些小技巧，對于提升計算效率是非常有效的。

第一，梯度分步計算。采用SGD訓練FFM模型時，隻采用單個樣本的損失函數來計算模型參數的梯度。

上面的公式表明，

與具體的模型參數無關。是以，每次更新模型時，隻需計算一次，之後直接調用 

的值即可。對于更新 

個模型參數，這種方式能夠極大提升運算效率。

第二，自适應學習率。此版本的FFM實作沒有采用常用的指數遞減的學習率更新政策，而是利用 nfknfk 個浮點數的臨時空間，自适應地更新學習率。學習率是參考AdaGrad算法計算的[11]，按如下方式更新

其中，

是特征

 對field 

 隐向量的一個元素，元素下标未标出；

是損失函數對參數 

的梯度；

是第 

 次疊代的梯度；

是初始學習率。可以看出，随着疊代的進行，每個參數的曆史梯度會慢慢累加，導緻每個參數的學習率逐漸減小。另外，每個參數的學習率更新速度是不同的，與其曆史梯度有關，根據AdaGrad的特點，對于樣本比較稀疏的特征，學習率高于樣本比較密集的特征，是以每個參數既可以比較快速達到最優，也不會導緻驗證誤差出現很大的震蕩。

第三，OpenMP多核并行計算。OpenMP是用于共享記憶體并行系統的多處理器程式設計的編譯方案，便于移植和多核擴充[12]。FFM的源碼采用了OpenMP的API，對參數訓練過程SGD進行了多線程擴充，支援多線程編譯。是以，OpenMP技術極大地提高了FFM的訓練效率和多核CPU的使用率。在訓練模型時，輸入的訓練參數ns_threads指定了線程數量，一般設定為CPU的核心數，便于完全利用CPU資源。

第四，SSE3指令并行程式設計。SSE3全稱為資料流單指令多資料擴充指令集3，是CPU對資料層并行的關鍵指令，主要用于多媒體和遊戲的應用程式中[13]。SSE3指令采用128位的寄存器，同時操作4個單精度浮點數或整數。SSE3指令的功能非常類似于向量運算。例如，

 和 

 采用SSE3指令相加（aa 和 bb 分别包含4個資料），其功能是 

中的4個元素與 

 中4個元素對應相加，得到4個相加後的值。采用SSE3指令後，向量運算的速度更加快捷，這對包含大量向量運算的FFM模型是非常有利的。

除了上面的技巧之外，FFM的實作中還有很多調優技巧需要探索。例如，代碼是按field和特征的編号申請參數空間的，如果選取了非連續或過大的編号，就會造成大量的記憶體浪費；在每個樣本中加入值為1的新特征，相當于引入了因子化的一次項，避免了缺少一次項帶來的模型偏差等。

FFM應用

在DSP的場景中，FFM主要用來預估站内的CTR和CVR，即一個使用者對一個商品的潛在點選率和點選後的轉化率。

CTR和CVR預估模型都是線上下訓練，然後用于線上預測。兩個模型采用的特征大同小異，主要有三類：使用者相關的特征、商品相關的特征、以及使用者-商品比對特征。使用者相關的特征包括年齡、性别、職業、興趣、品類偏好、浏覽/購買品類等基本資訊，以及使用者近期點選量、購買量、消費額等統計資訊。商品相關的特征包括所屬品類、銷量、價格、評分、曆史CTR/CVR等資訊。使用者-商品比對特征主要有浏覽/購買品類比對、浏覽/購買商家比對、興趣偏好比對等幾個次元。

為了使用FFM方法，所有的特征必須轉換成“field_id:feat_id:value”格式，field_id代表特征所屬field的編号，feat_id是特征編号，value是特征的值。數值型的特征比較容易處理，隻需配置設定單獨的field編号，如使用者評論得分、商品的曆史CTR/CVR等。categorical特征需要經過One-Hot編碼成數值型，編碼産生的所有特征同屬于一個field，而特征的值隻能是0或1，如使用者的性别、年齡段，商品的品類id等。除此之外，還有第三類特征，如使用者浏覽/購買品類，有多個品類id且用一個數值衡量使用者浏覽或購買每個品類商品的數量。這類特征按照categorical特征處理，不同的隻是特征的值不是0或1，而是代表使用者浏覽或購買數量的數值。按前述方法得到field_id之後，再對轉換後特征順序編号，得到feat_id，特征的值也可以按照之前的方法獲得。

CTR、CVR預估樣本的類别是按不同方式擷取的。CTR預估的正樣本是站内點選的使用者-商品記錄，負樣本是展現但未點選的記錄；CVR預估的正樣本是站内支付（發生轉化）的使用者-商品記錄，負樣本是點選但未支付的記錄。建構出樣本資料後，采用FFM訓練預估模型，并測試模型的性能。

#(field)	#(feature)	AUC	Logloss
站内CTR	39	2456	0.77	0.38
站内CVR	67	2441	0.92	0.13

由于模型是按天訓練的，每天的性能名額可能會有些波動，但變化幅度不是很大。這個表的結果說明，站内CTR/CVR預估模型是非常有效的。

在訓練FFM的過程中，有許多小細節值得特别關注。

第一，樣本歸一化。FFM預設是進行樣本資料的歸一化，即 pa.normpa.norm 為真；若此參數設定為假，很容易造成資料inf溢出，進而引起梯度計算的nan錯誤。是以，樣本層面的資料是推薦進行歸一化的。

第二，特征歸一化。CTR/CVR模型采用了多種類型的源特征，包括數值型和categorical類型等。但是，categorical類編碼後的特征取值隻有0或1，較大的數值型特征會造成樣本歸一化後categorical類生成特征的值非常小，沒有區分性。例如，一條使用者-商品記錄，使用者為“男”性，商品的銷量是5000個（假設其它特征的值為零），那麼歸一化後特征“sex=male”（性别為男）的值略小于0.0002，而“volume”（銷量）的值近似為1。特征“sex=male”在這個樣本中的作用幾乎可以忽略不計，這是相當不合理的。是以，将源數值型特征的值歸一化到 [0,1][0,1] 是非常必要的。

第三，省略零值特征。從FFM模型的表達式(4)可以看出，零值特征對模型完全沒有貢獻。包含零值特征的一次項群組合項均為零，對于訓練模型參數或者目标值預估是沒有作用的。是以，可以省去零值特征，提高FFM模型訓練和預測的速度，這也是稀疏樣本采用FFM的顯著優勢。

後記

本文主要介紹了FFM的思路來源和理論原理，并結合源碼說明FFM的實際應用和一些小細節。從理論上分析，FFM的參數因子化方式具有一些顯著的優勢，特别适合處理樣本稀疏性問題，且確定了較好的性能；從應用結果來看，站内CTR/CVR預估采用FFM是非常合理的，各項名額都說明了FFM在點選率預估方面的卓越表現。當然，FFM不一定适用于所有場景且具有超越其他模型的性能，合适的應用場景才能成就FFM的“威名”。

參考文獻

1. http://blog.csdn.net/lilyth_lilyth/article/details/48032119
2. http://www.cnblogs.com/Matrix_Yao/p/4773221.html
3. http://www.herbrich.me/papers/adclicksfacebook.pdf
4. https://www.kaggle.com/c/criteo-display-ad-challenge
5. https://www.kaggle.com/c/avazu-ctr-prediction
6. https://en.wikipedia.org/wiki/Demand-side_platform
7. http://www.algo.uni-konstanz.de/members/rendle/pdf/Rendle2010FM.pdf
8. http://www.cs.cmu.edu/~wcohen/10-605/2015-guest-lecture/FM.pdf
9. http://www.csie.ntu.edu.tw/~r01922136/slides/ffm.pdf
10. https://github.com/guestwalk/libffm
11. https://en.wikipedia.org/wiki/Stochastic_gradient_descent#AdaGrad
12. http://openmp.org/wp/openmp-specifications/
13. http://blog.csdn.net/gengshenghong/article/details/7008704
14. https://kaggle2.blob.core.windows.net/competitions/kddcup2012/2748/media/Opera.pdf