[深度学习] FM FFM 算法基本原理
???? 在推薦系統(tǒng)和計算廣告業(yè)務(wù)中，點(diǎn)擊率CTR（click-through rate）和轉(zhuǎn)化率CVR（conversion rate）是衡量流量轉(zhuǎn)化的兩個關(guān)鍵指標(biāo)。準(zhǔn)確的估計CTR、CVR對于提高流量的價值，增加廣告及電商收入有重要的指導(dǎo)作用。
無論使用什么類型的模型，點(diǎn)擊率這個命題可以被歸納到二元分類的問題，我們通過單個個體的特征，計算出對于某個內(nèi)容，是否點(diǎn)擊了，點(diǎn)擊了就是1，沒點(diǎn)擊就是0。對于任何二元分類的問題，最后我們都可以歸結(jié)到邏輯回歸上面。
- 早期的人工特征工程 + LR(Logistic Regression)：這個方式需要大量的人工處理，不僅需要對業(yè)務(wù)和行業(yè)有所了解，對于算法的經(jīng)驗(yàn)要求也十分的高。
- GBDT(Gradient Boosting Decision Tree) + LR：提升樹短時這方面的第二個里程碑，雖然也需要大量的人工處理，但是由于其的可解釋性和提升樹對于假例的權(quán)重提升，使得計算準(zhǔn)確度有了很大的提高。
- FM-FFM：FM和FFM模型是最近幾年提出的模型，并且在近年來表現(xiàn)突出，分別在由Criteo和Avazu舉辦的CTR預(yù)測競賽中奪得冠軍，使得到目前為止，還都是以此為主的主要模型占據(jù)主導(dǎo)位置。
- Embedding模型可以理解為FFM的一個變體。
一、LR模型
LR是一種寬而不深的結(jié)構(gòu)，所有的特征直接作用在最后的輸出結(jié)果上。模型優(yōu)點(diǎn)是簡單、可控性好，但是效果的好壞直接取決于特征工程的程度，需要非常精細(xì)的連續(xù)型、離散型、時間型等特征處理及特征組合。通常通過正則化等方式控制過擬合。
二、FM模型
因子分解機(jī)（Factorization Machine, FM）是由Steffen Rendle提出的一種基于矩陣分解的機(jī)器學(xué)習(xí)算法，其主要用于解決數(shù)據(jù)稀疏的業(yè)務(wù)場景（如推薦業(yè)務(wù)），特征怎樣組合的問題。
paper指出FM與SVM相比，有如下優(yōu)勢：
FM（Factorization Machines，因子分解機(jī)），在數(shù)據(jù)非常稀疏的情況下，依然能估計出可靠的參數(shù)進(jìn)行預(yù)測。與傳統(tǒng)的簡單線性模型不同的是，因子分解機(jī)考慮了特征間的交叉，對所有嵌套變量交互進(jìn)行建模（類似于SVM中的核函數(shù)），因此在推薦系統(tǒng)和計算廣告領(lǐng)域關(guān)注的點(diǎn)擊率CTR（click-through rate）和轉(zhuǎn)化率CVR（conversion rate）兩項(xiàng)指標(biāo)上有著良好的表現(xiàn)。此外，FM的模型還具有可以用線性時間來計算，以及能夠與許多先進(jìn)的協(xié)同過濾方法相融合等優(yōu)點(diǎn)。
線性模型建模為如下公式：
對于二分類問題則需要在上式的基礎(chǔ)上添加一個對數(shù)幾率回歸：
線性模型的優(yōu)點(diǎn)是簡單、方便、易于求解，但缺點(diǎn)在于線性模型中假設(shè)不同特征之間是獨(dú)立的，即特征 不會相互影響。為了解決簡單線性模型無法學(xué)得特征間交叉影響的問題，SVM通過引入核函數(shù)來實(shí)現(xiàn)特征的交叉，實(shí)際上和多項(xiàng)式模型是一樣的，這里以只考慮兩個特征交叉的二階多項(xiàng)式模型為例：
上式也可以稱為Poly2(degree-2 poly-nomial mappings)模型
模型覆蓋了LR的寬模型結(jié)構(gòu)，同時也引入了交叉特征，增加模型的非線性，提升模型容量，能捕捉更多的信息.? 從公式來看，模型前半部分就是普通的LR線性組合，后半部分的交叉項(xiàng)即特征的組合。單從模型表達(dá)能力上來看，FM的表達(dá)能力是強(qiáng)于LR的，至少不會比LR弱，當(dāng)交叉項(xiàng)參數(shù)全為0時退化為普通的LR模型。
多項(xiàng)式模型的問題在于二階項(xiàng)的參數(shù)過多，設(shè)特征維數(shù)為 n，那么二階項(xiàng)的參數(shù)數(shù)目為 n(n-1)/2。
任意兩個參數(shù)都是獨(dú)立的。然而，在數(shù)據(jù)稀疏性普遍存在的實(shí)際應(yīng)用場景中，二次項(xiàng)參數(shù)的訓(xùn)練是很困難的.
對于廣告點(diǎn)擊率預(yù)估問題，由于存在大量id特征，導(dǎo)致 n 可能為 維，這樣一來，模型參數(shù)的量級為 ，這比樣本量多得多！這導(dǎo)致只有極少數(shù)的二階組合模式才能在樣本中找到，而絕大多數(shù)模式在樣本中找不到，因而模型無法學(xué)出對應(yīng)的權(quán)重。
為此，Rendle于2010年提出FM模型，它能很好的求解上式，其特點(diǎn)如下：
- FM模型可以在非常稀疏的情況下進(jìn)行參數(shù)估計
- FM模型是線性時間復(fù)雜度的，可以直接使用原問題進(jìn)行求解，而且不用像SVM一樣依賴支持向量。
- FM模型是一個通用的模型，其訓(xùn)練數(shù)據(jù)的特征取值可以是任意實(shí)數(shù)。而其它最先進(jìn)的分解模型對輸入數(shù)據(jù)有嚴(yán)格的限制。FMs可以模擬MF、SVD++、PITF或FPMC模型。
FM模型原理
在矩陣分解，一個rating可以分解為user矩陣和item矩陣，如下圖所示：
分解后得到user和item矩陣的維度分別為nk和km，（k一般由用戶指定），相比原來的rating矩陣，空間占用得到降低，并且分解后的user矩陣暗含著user偏好，Item矩陣暗含著item的屬性，而user矩陣乘上item矩陣就是rating矩陣中用戶對item的評分。因此，參考矩陣分解的過程，FM模型也將上式的二次項(xiàng)參數(shù)進(jìn)行分解:
通過上式得變換，因子分解機(jī)的二次項(xiàng)的復(fù)雜度簡化到O(kn)。
FM例子
上圖是一個人造的廣告CTR的數(shù)據(jù)例子，代表的意思是在某個網(wǎng)站（Publisher）上刊登一則廣告（Advertiser），某個用戶（用戶性別特征Gender）是否會點(diǎn)擊某條廣告的數(shù)據(jù)。
這個例子中假設(shè)包含三個特征域（Field）:
網(wǎng)站Publisher(可能的特征值是ESPN、Vogue、NBC)、廣告Advertiser（可能的特征值是Nike、Adidas、Gucci）
性別Gender(可能的特征值是Male、Female)。
由這個例子可以看出組合特征的重要性：
如果在體育網(wǎng)站ESPN上發(fā)布Nike的廣告，那么100次展現(xiàn)，80次會被點(diǎn)擊，而20次不會被點(diǎn)擊。意味著組合特征（Publisher=”ESPN” and Advertiser=”Nike”）是個很強(qiáng)的預(yù)測用戶是否點(diǎn)擊的二階組合特征。
FM模型在做二階特征組合的時候，對于每個二階組合特征的權(quán)重，是根據(jù)對應(yīng)兩個特征的Embedding向量內(nèi)積，來作為這個組合特征重要性的指示。當(dāng)訓(xùn)練好FM模型后，每個特征都可以學(xué)會一個特征embedding向量，如上圖所示。當(dāng)做預(yù)測的時候，比如我們接收到上面例子的數(shù)據(jù)，需要預(yù)測用戶是否會點(diǎn)擊這條廣告，則對三個特征做兩兩組合，每個組合特征的權(quán)重，可以根據(jù)兩個對應(yīng)的特征embedding內(nèi)積求得，對所有組合特征求和后，套接Sigmoid函數(shù)即可做出二分類預(yù)測。
三、FFM模型
FFM(Field Factorization Machine)是在FM的基礎(chǔ)上引入了“場（Field）”的概念而形成的新模型。在FM中的特征 與其他特征的交叉時，特征 使用的都是同一個隱向量 。而FFM將特征按照事先的規(guī)則分為多個場(Field)，特征屬于某個特定的場F。每個特征將被映射為多個隱向量 ，每個隱向量對應(yīng)一個場。當(dāng)兩個特征 ,組合時，用對方對應(yīng)的場對應(yīng)的隱向量做內(nèi)積。
FFM例子
對于FM模型來說，每個特征學(xué)會唯一的一個特征embedding向量。注意，和FFM的最大不同逐漸出現(xiàn)，為了更容易向FFM模型理解過渡，我們可以這么理解FM模型中的某個特征的embedding，我們拿ESPN這個特征作為例子，當(dāng)這個特征和其它特征域的某個特征進(jìn)行二階特征組合的時候，不論哪個特征域的特征和ESPN這個特征進(jìn)行組合，ESPN這個特征都反復(fù)使用同一個特征embedding去做內(nèi)積。也可以理解為ESPN這個特征在和不同特征域特征進(jìn)行組合的時候，共享了同一個特征向量。
沿著這個思路思考，我會問出一個問題：我們可以改進(jìn)下FM模型嗎？ESPN這個特征和不同特征域特征進(jìn)行組合的時候，可以使用不同的特征向量嗎？
既然FM模型的某個特征，在和任意其它特征域的特征進(jìn)行組合求權(quán)重的時候，共享了同一個特征向量。那么，如果我們把這個事情做地更細(xì)致些，比如ESPN這個特征，當(dāng)它和Nike（所屬特征域Advertiser）組合的時候用一個特征embedding向量，而當(dāng)它和Male(所屬特征域Gendor)組合的時候，使用另外一個特征embedding向量，這樣是否在描述特征組合的時候更細(xì)膩一些？
也就是說，當(dāng)ESPN這個特征（屬于Publisher網(wǎng)站這個域）和屬于廣告Advertiser這個域的特征進(jìn)行組合的時候，用一個特征embedding；和屬于性別Gender這個特征域的特征進(jìn)行組合的時候，用另外一個特征embedding。
這意味著，如果有F個特征域，那么每個特征由FM模型的一個k維特征embedding，拓展成了（F-1）個k維特征embedding。之所以是F-1，而不是F，是因?yàn)樘卣鞑缓妥约航M合，所以不用考慮自己。
上圖展示了這個過程，因?yàn)檫@個例子有三個特征域，所以ESPN（屬于Publisher網(wǎng)站這個域站）有兩個特征embedding，
當(dāng)和Nike特征組合的時候，用的是針對網(wǎng)站Advertisor這個特征域的embedding去做內(nèi)積；而當(dāng)和Male這個特征組合的時候，則用的是針對性別Gender這個特征域的embedding去做內(nèi)積。
同理，Nike和Male這兩個特征也是根據(jù)和它組合特征所屬特征域的不同，采用不同的特征向量去做內(nèi)積。
而兩兩特征組合這個事情的做法，FFM和FM則是完全相同的，區(qū)別就是每個特征對應(yīng)的特征embedding個數(shù)不同。
FM每個特征只有一個共享的embedding向量，而對于FFM的一個特征，則有（F-1）個特征embedding向量，用于和不同的特征域特征組合時使用。
從上面的模型演化過程，我們可以推出，假設(shè)模型具有n個特征，那么FM模型的參數(shù)量是n*k（暫時忽略掉一階特征的參數(shù)），其中k是embedding特征向量大小。
而FFM模型的參數(shù)量呢？因?yàn)槊總€特征具有（F-1）個k維特征向量，所以它的模型參數(shù)量是(F-1)*n*k，也就是說參數(shù)量比FM模型擴(kuò)充了(F-1)倍。
這意味著，如果我們的任務(wù)有100個特征域，FFM模型的參數(shù)量就是FM模型的大約100倍。
這其實(shí)是很恐怖的，因?yàn)楝F(xiàn)實(shí)任務(wù)中，特征數(shù)量n是個很大的數(shù)值，特征域幾十上百也很常見。
正因?yàn)镕FM模型參數(shù)量太大，所以在訓(xùn)練FFM模型的時候，很容易過擬合，需要采取早停等防止過擬合的手段。而根據(jù)經(jīng)驗(yàn)，FFM模型的k值可以取得小一些，一般在幾千萬訓(xùn)練數(shù)據(jù)規(guī)模下，取8到10能取得較好的效果，當(dāng)然，k具體取哪個數(shù)值，這其實(shí)跟具體訓(xùn)練數(shù)據(jù)規(guī)模大小有關(guān)系，理論上，訓(xùn)練數(shù)據(jù)集合越大，越不容易過擬合，這個k值可以設(shè)置得越大些。
下面的圖來很好的表示了三個模型的區(qū)別：
參考：
總結(jié)
以上是生活随笔為你收集整理的[深度学习] FM FFM 算法基本原理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 澜起科技澄清申明：有不法分子制作“澜起科
- 下一篇： LeetCode Hot100 ----