轉(zhuǎn)載 http://www.reibang.com/p/776598acc35a
1. 背景
在計算廣告和推薦系統(tǒng)重势篡，CTR預(yù)估(click-through rate)是非常重要的一個環(huán)節(jié)，判斷一個商品的是否進(jìn)行推薦需要根據(jù)CTR預(yù)估的點(diǎn)擊率來進(jìn)行模暗。在進(jìn)行CTR預(yù)估時殊霞，除了單特征外，往往要對特征進(jìn)行組合汰蓉。對于特征組合來說绷蹲，業(yè)界常用的方法有人工特征工程 + LR（Logistic Regression）、GBDT（Gradient Boosting Decision Tree） + LR顾孽、FM（Factorization Machine）和FFM（Field-aware Factorization Machine）模型祝钢。最近幾年也出現(xiàn)了很多基于FM改進(jìn)的方法，如deepFM若厚，F(xiàn)NN拦英，PNN，DCN测秸，xDeepFM等疤估。
2.動機(jī)（one-hot編碼帶來的問題）
FM（Factorization Machine）主要是為了解決數(shù)據(jù)稀疏的情況下灾常，特征怎樣組合的問題。已一個廣告分類的問題為例铃拇，根據(jù)用戶與廣告位對的一些特征钞瀑，來預(yù)測用戶是否會點(diǎn)擊廣告。數(shù)據(jù)如下
clicked 是分類值慷荔，表明用戶有沒有點(diǎn)擊該廣告雕什。1表示點(diǎn)擊，0表示未點(diǎn)擊显晶。而country贷岸，day，ad_type 則是對應(yīng)對的特征磷雇。對于這種categories特征偿警，一般都是進(jìn)行one-hot編碼處理。
將上面的數(shù)據(jù)進(jìn)行one-hot編碼后唯笙，就變成下面這樣螟蒸。
因?yàn)閏ategories 特征，所有經(jīng)過one-hot編碼以后睁本，不可避免的樣本的數(shù)據(jù)就變得很稀疏尿庐。假設(shè)淘寶或者京東上的item為100萬忠怖，如果對item這個維度進(jìn)行one-hot編碼呢堰，光這一個維度數(shù)據(jù)的稀疏度就是百萬分之一。由此可見凡泣，數(shù)據(jù)的稀疏性枉疼，是我們在實(shí)際應(yīng)用場景中面臨的一個非常常見的挑戰(zhàn)與問題。
one-hot編碼帶來的另一個問題是特征空間變大鞋拟。同樣以上面淘寶上的item為例骂维，將item進(jìn)行one-hot編碼以后，樣本空間有一個categorical變?yōu)榱税偃f維的數(shù)值特征贺纲，特征空間一下子暴增一百萬航闺。所以大廠動不動上億維度，就是這么來的
3猴誊、對特征進(jìn)行組合
普通的線性模型潦刃，我們都是將各個特征獨(dú)立考慮的，并沒有考慮到特征與特征之間的相互關(guān)系懈叹。但實(shí)際上乖杠，大量的特征之間是有關(guān)聯(lián)的。最簡單的以電商為例澄成，一般女性用戶看化妝品服裝之類的廣告比較多胧洒，而男性更青睞各種球類裝備畏吓。那很明顯，女性這個特征與化妝品類服裝類商品有很大的關(guān)聯(lián)性卫漫，男性這個特征與球類裝備的關(guān)聯(lián)性更為密切菲饼。如果我們能將這些有關(guān)聯(lián)的特征找出來，顯然是很有意義的汛兜。
一般的線性模型為：
表示巴粪。為了簡單起見，我們討論二階多項式模型粥谬。具體的模型表達(dá)式如下：
為了簡單起見肛根，我們只考慮二階交叉的情況，具體的模型如下：
4.FM 求解
那么漏策，如何解決二次項參數(shù)的訓(xùn)練問題呢派哲？矩陣分解提供了一種解決思路。在model-based的協(xié)同過濾中掺喻，一個rating矩陣可以分解為user矩陣和item矩陣芭届，每個user和item都可以采用一個隱向量表示。比如在下圖中的例子中感耙，我們把每個user表示成一個二維向量褂乍，同時把每個item表示成一個二維向量，兩個向量的點(diǎn)積就是矩陣中user對item的打分即硼。
我們再來看一下FM的訓(xùn)練復(fù)雜度逃片，利用SGD（Stochastic Gradient Descent）訓(xùn)練模型。模型各個參數(shù)的梯度如下：
