FM和FFM原理的探索和應用的經(jīng)驗

　FM和FFM模型是最近幾年提出的模型，憑借其在數(shù)據(jù)量比較大并且特征稀疏的情況下，仍然能夠得到優(yōu)秀的性能和效果的特性，屢次在各大公司舉辦的CTR預估比賽中獲得不錯的戰(zhàn)績。美團點評技術團隊在搭建DSP的過程中，探索并使用了FM和FFM模型進行CTR和CVR預估，并且取得了不錯的效果。本文旨在把我們對FM和FFM原理的探索和應用的經(jīng)驗介紹給有興趣的讀者。
　　前言
　　在計算廣告領域，點擊率CTR（click-through rate）和轉化率CVR（conversion rate）是衡量廣告流量的兩個關鍵指標。準確的估計CTR、CVR對于提高流量的價值，增加廣告收入有重要的指導作用。預估CTR/CVR，業(yè)界常用的方法有人工特征工程 + LR（Logistic Regression）、GBDT（Gradient Boosting Decision Tree） + LR［1］［2］［3］、FM（Factorization Machine）［2］［7］和FFM（Field-aware Factorization Machine）［9］模型。在這些模型中，F(xiàn)M和FFM近年來表現(xiàn)突出，分別在由Criteo和Avazu舉辦的CTR預測競賽中奪得冠軍［4］［5］。
　　考慮到FFM模型在CTR預估比賽中的不俗戰(zhàn)績，美團點評技術團隊在搭建DSP（Demand Side Platform）［6］平臺時，在站內CTR/CVR的預估上使用了該模型，取得了不錯的效果。本文是基于對FFM模型的深度調研和使用經(jīng)驗，從原理、實現(xiàn)和應用幾個方面對FFM進行探討，希望能夠從原理上解釋FFM模型在點擊率預估上取得優(yōu)秀效果的原因。因為FFM是在FM的基礎上改進得來的，所以我們首先引入FM模型，本文章節(jié)組織方式如下：
　　首先介紹FM的原理。其次介紹FFM對FM的改進。然后介紹FFM的實現(xiàn)細節(jié)。最后介紹模型在DSP場景的應用。
　　FM原理
　　FM（Factorization Machine）是由Konstanz大學Steffen Rendle（現(xiàn)任職于Google）于2010年最早提出的，旨在解決稀疏數(shù)據(jù)下的特征組合問題［7］。下面以一個示例引入FM模型。假設一個廣告分類的問題，根據(jù)用戶和廣告位相關的特征，預測用戶是否點擊了廣告。源數(shù)據(jù)如下［8］
　　Clicked？
　　Country
　　Day
　　Ad_type
　　1 USA 26/11/15 Movie
　　0 China 1/7/14 Game
　　1 China 19/2/15 Game
　　“Clicked？”是label，Country、Day、Ad_type是特征。由于三種特征都是categorical類型的，需要經(jīng)過獨熱編碼（One-Hot Encoding）轉換成數(shù)值型特征。
　　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 0 1 0 0 1 0
　　0 0 1 0 1 0 0 1
　　1 0 1 0 0 1 0 1
　　由上表可以看出，經(jīng)過One-Hot編碼之后，大部分樣本數(shù)據(jù)特征是比較稀疏的。上面的樣例中，每個樣本有7維特征，但平均僅有3維特征具有非零值。實際上，這種情況并不是此例獨有的，在真實應用場景中這種情況普遍存在。例如，CTR/CVR預測時，用戶的性別、職業(yè)、教育水平、品類偏好，商品的品類等，經(jīng)過One-Hot編碼轉換后都會導致樣本數(shù)據(jù)的稀疏性。特別是商品品類這種類型的特征，如商品的末級品類約有550個，采用One-Hot編碼生成550個數(shù)值特征，但每個樣本的這550個特征，有且僅有一個是有效的（非零）。由此可見，數(shù)據(jù)稀疏性是實際問題中不可避免的挑戰(zhàn)。
　　One-Hot編碼的另一個特點就是導致特征空間大。例如，商品品類有550維特征，一個categorical特征轉換為550維數(shù)值特征，特征空間劇增。
　　同時通過觀察大量的樣本數(shù)據(jù)可以發(fā)現(xiàn)，某些特征經(jīng)過關聯(lián)之后，與label之間的相關性就會提高。例如，“USA”與“Thanksgiving”、“China”與“Chinese New Year”這樣的關聯(lián)特征，對用戶的點擊有著正向的影響。換句話說，來自“China”的用戶很可能會在“Chinese New Year”有大量的瀏覽、購買行為，而在“Thanksgiving”卻不會有特別的消費行為。這種關聯(lián)特征與label的正向相關性在實際問題中是普遍存在的，如“化妝品”類商品與“女”性，“球類運動配件”的商品與“男”性，“電影票”的商品與“電影”品類偏好等。因此，引入兩個特征的組合是非常有意義的。
　　多項式模型是包含特征組合的最直觀的模型。在多項式模型中，特征 xi 和 xj 的組合采用 xixj 表示，即 xi 和 xj 都非零時，組合特征 xixj 才有意義。從對比的角度，本文只討論二階多項式模型。模型的表達式如下：
　　
　?。?）
　　其中，n 代表樣本的特征數(shù)量，xi 是第 i 個特征的值，w0、wi、wij 是模型參數(shù)。
　　從公式（1）可以看出，組合特征的參數(shù)一共有 n（n?1）/2 個，任意兩個參數(shù)都是獨立的。然而，在數(shù)據(jù)稀疏性普遍存在的實際應用場景中，二次項參數(shù)的訓練是很困難的。其原因是，每個參數(shù) wij 的訓練需要大量 xi 和 xj 都非零的樣本；由于樣本數(shù)據(jù)本來就比較稀疏，滿足“xi 和 xj 都非零”的樣本將會非常少。訓練樣本的不足，很容易導致參數(shù) wij 不準確，最終將嚴重影響模型的性能。
　　那么，如何解決二次項參數(shù)的訓練問題呢？矩陣分解提供了一種解決思路。在model-based的協(xié)同過濾中，一個rating矩陣可以分解為user矩陣和item矩陣，每個user和item都可以采用一個隱向量表示［8］。比如在下圖中的例子中，我們把每個user表示成一個二維向量，同時把每個item表示成一個二維向量，兩個向量的點積就是矩陣中user對item的打分。