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

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