了解一下？點擊率預估中的FM＆FFM演算法

特徵決定了所有演算法效果的上限，而不同的演算法只是離這個上限的距離不同而已

CTR方法概覽

廣義線性模型+人工特徵組合（LR+FeatureEngineering）

非線性模型（GBDT，FM，FFM，DNN，MLR）

廣義線性模型+非線性模型組合特徵（模型融合，常見的是LR+GBDT）

其中 2（非線性模型）又可以分為：

矩陣分解類 （FM，FFM）

回歸類 （GBDT，MLR）

神經網路類 （DNN）

FM演算法

背景

FM演算法（Factorization Machine）一般翻譯為「因子分解機」，2010年，它由當時還在日本大阪大學的Steffen Rendle提出。

此演算法的主要作用是可以把所有特徵進行高階組合，減少人工參與特徵組合的工作，工程師可以將精力集中在模型參數調優。

FM只需要線性時間複雜度，可以應用於大規模機器學習。經過部分數據集試驗，此演算法在稀疏數據集合上的效果要明顯好於SVM。

要解決的問題

假設一個廣告分類問題，根據用戶和廣告位相關的特徵，預測用戶是否點擊了廣告。

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

經過one-hot編碼之後，特徵變得稀疏，上邊實例中每個樣本有7維的特徵，但平均僅有3維為非0值，在電商場景中預測sku是否被點擊的過程中，特徵往往要比上例中多的多，可見數據稀疏性是工業環境中不可避免的問題。另外一個問題就是特徵在經過one-hot編碼之後，維度會變得非常大，比如說三級品類有3k個，那麼sku的所屬三級品類特徵經過編碼之後就會變成3k維，特徵空間就會劇增。

依舊分析上邊的例子，特徵在經過關聯之後，與label之間的相關性就會增加。例如「USA」與「Thanksgiving」、「China」與「Chinese New Year」這樣的關聯特徵，對用戶的點擊有著正向的影響。換句話說，來自「China」的用戶很可能會在「Chinese New Year」有大量的瀏覽、購買行為，而在「Thanksgiving」卻不會有特別的消費行為。這種關聯特徵與label的正向相關性在實際問題中是普遍存在的，如「化妝品」類商品與「女」性，「球類運動配件」的商品與「男」性，「電影票」的商品與「電影」品類偏好等。因此，引入兩個特徵的組合是非常有意義的。

綜上，FM所解決的問題是

1)：特徵稀疏

2)：特徵組合

模型形式

對於特徵集合x=（x1,x2,x3,x4,....,xn）和標籤y，希望得到x和y的對應關係，最簡單的是建立線性回歸模型，

但是，一般線性模型無法學習到高階組合特徵，所以會將特徵進行高階組合，這裡以二階為例(理論上，FM可以組合任意高階，但是由於計算複雜度，實際中常用二階，後面也主要介紹二階組合的內容)。模型形式為

其中n代表樣本的特徵數量，x_i是第i個特徵，w_0，w_i，w_ij是模型參數

從公式(2)中可以看出，組合特徵參數一共有n(n-1)/2個，任意兩個參數之間都是獨立的，在數據特別稀疏的情況下，二次項參數的訓練是十分困難的，原因為每個wij的訓練都需要大量的非零x_i，x_j樣本，由於樣本稀疏，滿足條件的樣本很少，就會導致參數w_ij不準確，最終將影響模型的性能。

如何解決二次項參數的訓練？可以利用矩陣分解的思路。

在model-based的協同過濾中，一個rating矩陣可以分解為user矩陣和item矩陣，每個user和item都可以採用一個隱向量表示。比如在下圖中的例子中，我們把每個user表示成一個二維向量，同時把每個item表示成一個二維向量，兩個向量的點積就是矩陣中user對item的打分。

所有的二次項參數 w_ij 可以組成一個對稱矩陣W，那麼這個矩陣可以分解為W=V^T * V，V的第j列便是第j維特徵的隱向量，換句話說就是每個參數w_ij=，這裡的v_i和v_j是分別是第i，j個特徵的隱向量，這就是FM的核心思想，因此FM的模型方程為（二階形式）

其中，V_i是第i維特徵的隱向量，表示兩個向量內積，隱向量的長度k（k

另外，參數因子化使得 x_h，x_i的參數和 x_i，x_j 的參數不再是相互獨立的，因此我們可以在樣本稀疏的情況下相對合理地估計FM的二次項參數。具體來說，x_h，x_i 和 x_i，x_j 的係數分別為 ?v_h,v_i? 和 ?v_i,v_j?，它們之間有共同項 vi。也就是說，所有包含「xi的非零組合特徵」（存在某個 j≠i，使得 x_i x_j≠0）的樣本都可以用來學習隱向量 v_i，這很大程度上避免了數據稀疏性造成的影響。而在多項式模型中，w_hi 和 w_ij 是相互獨立的。

顯而易見，公式(3)是一個通用的擬合方程，可以採用不同的損失函數用於解決回歸、二元分類等問題，比如可以採用MSE（Mean Square Error）損失函數來求解回歸問題，也可以採用Hinge/Cross-Entropy損失（鉸鏈損失，互熵損失）來求解分類問題。當然，在進行二元分類時，FM的輸出需要經過sigmoid變換，這與Logistic回歸是一樣的。直觀上看，FM的複雜度是 O(kn^2)。但是，通過公式(3)的等式，FM的二次項可以化簡，其複雜度可以優化到 O(kn)。由此可見，FM可以在線性時間對新樣本作出預測。

從(3)—>(4)推導如下：

解讀第（1）步到第（2）步，這裡用A表示係數矩陣V的上三角元素，B表示對角線上的交叉項係數。由於係數矩陣V是一個對稱陣，所以下三角與上三角相等，有下式成立：

如果用隨機梯度下降（Stochastic Gradient Descent）法學習模型參數。那麼，模型各個參數的梯度如下：

其中，v_j,f 是隱向量 v_j 的第 f 個元素。由於 ∑nj=1vj,fxj 只與 f 有關，而與 i 無關，在每次迭代過程中，只需計算一次所有 f 的 ∑nj=1vj,fxj，就能夠方便地得到所有 v_i,f 的梯度。顯然，計算所有 f 的 ∑nj=1vj,fxj 的複雜度是 O(kn)；已知 ∑nj=1vj,fxj 時，計算每個參數梯度的複雜度是 O(1)；得到梯度後，更新每個參數的複雜度是 O(1)；模型參數一共有 nk+n+1 個。因此，FM參數訓練的複雜度也是 O(kn)。綜上可知，FM可以在線性時間訓練和預測，是一種非常高效的模型。

FM總結

FM降低了交叉項參數學習不充分的影響

one-hot編碼後的樣本數據非常稀疏，組合特徵更是如此。為了解決交叉項參數學習不充分、導致模型有偏或不穩定的問題。借鑒矩陣分解的思路：每一維特徵用k維的隱向量表示，交叉項的參數w_ij用對應特徵隱向量的內積表示，即?v_i,v_j?（也可以理解為平滑技術）。這樣參數學習由之前學習交叉項參數w_ij的過程，轉變為學習n個單特徵對應k維隱向量的過程。

很明顯，單特徵參數（k維隱向量v_i）的學習要比交叉項參數w_ij學習得更充分。示例說明：

假如有10w條訓練樣本，其中出現女性特徵的樣本數為3w，出現男性特徵的樣本數為7w，出現汽車特徵的樣本數為2000，出現化妝品的樣本數為1000。特徵共現的樣本數如下：

的含義是女性看汽車廣告。可以看到，單特徵對應的樣本數遠大於組合特徵對應的樣本數。訓練時，單特徵參數相比交叉項特徵參數會學習地更充分。

因此，可以說FM降低了因數據稀疏，導致交叉項參數學習不充分的影響

FM提升了模型預估能力

依然看上面的示例，樣本中沒有交叉特徵，即沒有男性看化妝品廣告的數據。如果用多項式模型來建模，對應的交叉項參數W_男性,化妝品是學不出來的，因為數據中沒有對應的共現交叉特徵。那麼多項式模型就不能對出現的男性看化妝品廣告場景給出準確地預估。

FM模型是否能得到交叉項參數W_男性,化妝品呢？答案是肯定的。由於FM模型是把交叉項參數用對應的特徵隱向量內積表示，這裡表示為W_男性,化妝品=?v_男性,v_化妝品?。

用男性特徵隱向量v_男性和v_化妝品特徵隱向量v化妝品的內積表示交叉項參數 W_男性,化妝品。

由於FM學習的參數就是單特徵的隱向量，那麼男性看化妝品廣告的預估結果可以用?v_男性,v_化妝品?得到。這樣，即便訓練集中沒有出現男性看化妝品廣告的樣本，FM模型仍然可以用來預估，提升了預估能力。

FM提升了參數學習效率

這個顯而易見，參數個數由(n^2+n+1)變為(nk+n+1)個，模型訓練複雜度也由O(mn^2)變為O(mnk)。m為訓練樣本數。對於訓練樣本和特徵數而言，都是線性複雜度。

此外，就FM模型本身而言，它是在多項式模型基礎上對參數的計算做了調整，因此也有人把FM模型稱為多項式的廣義線性模型，也是恰如其分的。

從交互項的角度看，FM僅僅是一個可以表示特徵之間交互關係的函數表法式，可以推廣到更高階形式，即將多個互異特徵分量之間的關聯信息考慮進來。例如在廣告業務場景中，如果考慮User-Ad-Context三個維度特徵之間的關係，在FM模型中對應的degree為3。

總結

FM最大特點和優勢：FM模型對稀疏數據有更好的學習能力，通過交互項可以學習特徵之間的關聯關係，並且保證了學習效率和預估能力

FFM演算法

背景

FFM（Field-aware Factorization Machine）最初的概念來自Yu-Chin Juan（阮毓欽，畢業於中國台灣大學，現在美國Criteo工作）與其比賽隊員，是他們借鑒了來自Michael Jahrer的論文中的field概念提出了FM的升級版模型。

模型形式

通過引入field的概念，FFM把相同性質的特徵，歸結於同一個field。還是以FM中的廣告分類為例，「Day=26/11/15」、「Day=1/7/14」、「Day=19/2/15」這三個特徵都是代表日期的，可以放到同一個field中。同理，三級品類有3k個，那麼sku的所屬三級品類特徵經過編碼之後就會變成3k維，那麼這3k維可以放到一個field中，簡單來說，同一個categorical特徵經過One-Hot編碼生成的數值特徵都可以放到同一個field。

在FFM中，每一維特徵x_i，針對其他特徵的每一種field f_j，都會學習到一個隱向量V_i,f_ j。因此，隱向量不僅與特徵有關，還與filed有關。也就是說，「Day=26/11/15」這個特徵與「Country」特徵和「Ad_type"特徵進行關聯的時候使用不同的隱向量，這與「Country」和「Ad_type」的內在差異相符，也是FFM中「field-aware」的由來。

假設樣本的 n 個特徵屬於 f 個field，那麼FFM的二次項有 nf個隱向量。而在FM模型中，每一維特徵的隱向量只有一個。FM可以看作FFM的特例，是把所有特徵都歸屬到一個field時的FFM模型。根據FFM的field敏感特性，可以導出其模型方程。

其中，f_ j 是第 j 個特徵所屬的field。如果隱向量的長度為 k，那麼FFM的二次參數有 f * kn 個，遠多於FM模型的 kn 個。此外，由於隱向量與field相關，FFM二次項並不能化簡，其預測複雜度是 O(kn^2)。

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

這條記錄可以編碼成5個特徵，其中「Genre=Comedy」和「Genre=Drama」屬於同一個field，「Price」是數值型，不用One-Hot編碼轉換。為了方便說明FFM的樣本格式，我們將所有的特徵和對應的field映射成整數編號。

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

其中，紅色是field編號，藍色是特徵編號，綠色是此樣本的特徵取值。二次項的係數是通過與特徵field相關的隱向量點積得到的，二次項共有 n(n?1)/2 個。

應用場景

在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訓練預估模型，並測試模型的性能。

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

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

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

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

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

參考資料

http://bourneli.github.io/ml/fm/2017/07/02/fm-remove-combine-features-by-yourself.html

https://tech.meituan.com/deep_understanding_of_ffm_principles_and_practices.html

http://www.52caml.com/head_first_ml/ml-chapter9-factorization-family/

https://cloud.tencent.com/developer/article/1104673?fromSource=waitui

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！