1际歼、FM背景
在計(jì)算廣告和推薦系統(tǒng)中吕粗，CTR預(yù)估(click-through rate)是非常重要的一個(gè)環(huán)節(jié)，判斷一個(gè)商品的是否進(jìn)行推薦需要根據(jù)CTR預(yù)估的點(diǎn)擊率來進(jìn)行议泵。在進(jìn)行CTR預(yù)估時(shí)，除了單特征外池充，往往要對(duì)特征進(jìn)行組合。對(duì)于特征組合來說卧惜，業(yè)界現(xiàn)在通用的做法主要有兩大類：FM系列與Tree系列。今天茅姜，我們就來講講FM算法奋姿。
2、one-hot編碼帶來的問題
FM(Factorization Machine)主要是為了解決數(shù)據(jù)稀疏的情況下寓免，特征怎樣組合的問題。已一個(gè)廣告分類的問題為例嗅蔬，根據(jù)用戶與廣告位的一些特征澜术，來預(yù)測(cè)用戶是否會(huì)點(diǎn)擊廣告猜敢。數(shù)據(jù)如下：(本例來自美團(tuán)技術(shù)團(tuán)隊(duì)分享的paper)
clicked是分類值添寺，表明用戶有沒有點(diǎn)擊該廣告博脑。1表示點(diǎn)擊，0表示未點(diǎn)擊疗杉。而country,day,ad_type則是對(duì)應(yīng)的特征椭蹄。對(duì)于這種categorical特征，一般都是進(jìn)行one-hot編碼處理翼馆。
將上面的數(shù)據(jù)進(jìn)行one-hot編碼以后猜极，就變成了下面這樣 ：
因?yàn)槭莄ategorical特征，所以經(jīng)過one-hot編碼以后携龟，不可避免的樣本的數(shù)據(jù)就變得很稀疏。舉個(gè)非常簡(jiǎn)單的例子蕊蝗，假設(shè)淘寶或者京東上的item為100萬建蹄，如果對(duì)item這個(gè)維度進(jìn)行one-hot編碼痛单，光這一個(gè)維度數(shù)據(jù)的稀疏度就是百萬分之一旭绒。由此可見重父，數(shù)據(jù)的稀疏性，是我們?cè)趯?shí)際應(yīng)用場(chǎng)景中面臨的一個(gè)非常常見的挑戰(zhàn)與問題郭厌。
one-hot編碼帶來的另一個(gè)問題是特征空間變大折柠。同樣以上面淘寶上的item為例扇售，將item進(jìn)行one-hot編碼以后，樣本空間有一個(gè)categorical變?yōu)榱税偃f維的數(shù)值特征嚣艇，特征空間一下子暴增一百萬。所以大廠動(dòng)不動(dòng)上億維度，就是這么來的凑保。
3欧引、對(duì)特征進(jìn)行組合
普通的線性模型，我們都是將各個(gè)特征獨(dú)立考慮的憋肖，并沒有考慮到特征與特征之間的相互關(guān)系婚苹。但實(shí)際上岸更，大量的特征之間是有關(guān)聯(lián)的膊升。最簡(jiǎn)單的以電商為例债查，一般女性用戶看化妝品服裝之類的廣告比較多速和，而男性更青睞各種球類裝備吭敢。那很明顯，女性這個(gè)特征與化妝品類服裝類商品有很大的關(guān)聯(lián)性，男性這個(gè)特征與球類裝備的關(guān)聯(lián)性更為密切纱控。如果我們能將這些有關(guān)聯(lián)的特征找出來辆毡，顯然是很有意義的。
一般的線性模型為：
從上面的式子很容易看出甜害，一般的線性模型壓根沒有考慮特征間的關(guān)聯(lián)舶掖。為了表述特征間的相關(guān)性，我們采用多項(xiàng)式模型唾那。在多項(xiàng)式模型中访锻，特征xi與xj的組合用xixj表示褪尝。為了簡(jiǎn)單起見，我們討論二階多項(xiàng)式模型期犬。具體的模型表達(dá)式如下：
上式中河哑，n表示樣本的特征數(shù)量,xi表示第i個(gè)特征。
與線性模型相比龟虎，F(xiàn)M的模型就多了后面特征組合的部分璃谨。
4、FM求解
從上面的式子可以很容易看出鲤妥，組合部分的特征相關(guān)參數(shù)共有n(n?1)/2個(gè)佳吞。但是如第二部分所分析，在數(shù)據(jù)很稀疏的情況下棉安，滿足xi,xj都不為0的情況非常少底扳，這樣將導(dǎo)致ωij無法通過訓(xùn)練得出。
為了求出ωij贡耽，我們對(duì)每一個(gè)特征分量xi引入輔助向量Vi=(vi1,vi2,?,vik)衷模。然后，利用vivj^T對(duì)ωij進(jìn)行求解蒲赂。
那么ωij組成的矩陣可以表示為:
那么阱冶，如何求解vi和vj呢？主要采用了公式：
具體過程如下：
上面的式子中有同學(xué)曾經(jīng)問我第一步是怎么推導(dǎo)的滥嘴，其實(shí)也不難木蹬，看下面的手寫過程(大伙可不要嫌棄字丑喲)
經(jīng)過這樣的分解之后，我們就可以通過隨機(jī)梯度下降SGD進(jìn)行求解：
參考文章：
1若皱、http://blog.csdn.net/bitcarmanlee/article/details/52143909
2镊叁、https://blog.csdn.net/u012871493/article/details/51593451
