原文：Factorization Machines
地址：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.393.8529&rep=rep1&type=pdf
初來乍到，首先簡(jiǎn)紹一篇學(xué)到的基礎(chǔ)論文：
一、問題由來
在計(jì)算廣告和推薦系統(tǒng)中，CTR預(yù)估(click-through rate)是非常重要的一個(gè)環(huán)節(jié)，判斷一個(gè)商品的是否進(jìn)行推薦需要根據(jù)CTR預(yù)估的點(diǎn)擊率來進(jìn)行。傳統(tǒng)的邏輯回歸模型是一種廣義線性模型，非常容易實(shí)現(xiàn)大規(guī)模實(shí)時(shí)并行處理，因此在工業(yè)界獲得了廣泛應(yīng)用，但是線性模型的學(xué)習(xí)能力有限，不能捕獲高階特征(非線性信息)，而在進(jìn)行CTR預(yù)估時(shí)，除了單特征外，往往要對(duì)特征進(jìn)行組合。對(duì)于特征組合來說，業(yè)界現(xiàn)在通用的做法主要有兩大類：FM系列與DNN系列。今天，我們就來分享下FM算法。
二、為什么需要FM
1、特征組合是許多機(jī)器學(xué)習(xí)建模過程中遇到的問題，如果對(duì)特征直接建模，很有可能會(huì)忽略掉特征與特征之間的關(guān)聯(lián)信息，因此，可以通過構(gòu)建新的交叉特征這一特征組合方式提高模型的效果。
2、高維的稀疏矩陣是實(shí)際工程中常見的問題，并直接會(huì)導(dǎo)致計(jì)算量過大，特征權(quán)值更新緩慢。試想一個(gè)10000*100的表，每一列都有8種元素，經(jīng)過one-hot獨(dú)熱編碼之后，會(huì)產(chǎn)生一個(gè)10000*800的表。因此表中每行元素只有100個(gè)值為1，700個(gè)值為0。特征空間急劇變大，以淘寶上的item為例，將item進(jìn)行one-hot編碼以后，樣本空間有一個(gè)categorical變?yōu)榱税偃f維的數(shù)值特征，特征空間一下子暴增一百萬。所以大廠動(dòng)不動(dòng)上億維度，就是這么來的。
而FM的優(yōu)勢(shì)就在于對(duì)這兩方面問題的處理。首先是特征組合，通過對(duì)兩兩特征組合，引入交叉項(xiàng)特征，提高模型得分；其次是高維災(zāi)難，通過引入隱向量（對(duì)參數(shù)矩陣進(jìn)行矩陣分解），完成對(duì)特征的參數(shù)估計(jì)。
三、原理及求解
在看FM算法前，我們先回顧一下最常見的線性表達(dá)式：
其中w0為初始權(quán)值，或者理解為偏置項(xiàng)，wi?為每個(gè)特征xi對(duì)應(yīng)的權(quán)值。可以看到，這種線性表達(dá)式只描述了每個(gè)特征與輸出的關(guān)系。
FM的表達(dá)式如下，可觀察到，只是在線性表達(dá)式后面加入了新的交叉項(xiàng)特征及對(duì)應(yīng)的權(quán)值。
求解過程 ：
從上面的式子可以很容易看出，組合部分的特征相關(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呢？主要采用了公式：
具體推導(dǎo)過程如下：
四、參數(shù)求解
利用梯度下降法，通過求損失函數(shù)對(duì)特征（輸入項(xiàng)）的導(dǎo)數(shù)計(jì)算出梯度，從而更新權(quán)值。設(shè)m為樣本個(gè)數(shù)，θ為權(quán)值。
其中，是和i無關(guān)的，可以事先求出來。每個(gè)梯度都可以在O(1)時(shí)間內(nèi)求得，整體的參數(shù)更新的時(shí)間為O(kn)。
一個(gè)小問題：隱向量?
?就是embedding vector?
答案：不是，具體計(jì)算過程大家可以舉個(gè)例推導(dǎo)下。
結(jié)論：
我們口中的隱向量實(shí)際上是一個(gè)向量組，其形狀為（輸入特征One-hot后的長(zhǎng)度，自定義長(zhǎng)度（嵌入向量的長(zhǎng)度如k維））；
隱向量vi代表的并不是embedding vector，而是在對(duì)輸入進(jìn)行embedding vector的向量組，也可理解為是一個(gè)權(quán)矩陣；
由輸入Xi*vi得到的向量才是真正的embedding vector。
第一篇博客就到此結(jié)束啦~ 之后會(huì)繼續(xù)分享計(jì)算廣告相關(guān)的論文和知識(shí)。
