原文：Factorization Machines

地址：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.393.8529&rep=rep1&type=pdf

初來(lái)乍到，首先簡(jiǎn)紹一篇學(xué)到的基礎(chǔ)論文：

一、問(wèn)題由來(lái)

　　　在計(jì)算廣告和推薦系統(tǒng)中晌块，CTR預(yù)估(click-through rate)是非常重要的一個(gè)環(huán)節(jié)令哟，判斷一個(gè)商品的是否進(jìn)行推薦需要根據(jù)CTR預(yù)估的點(diǎn)擊率來(lái)進(jìn)行但绕。傳統(tǒng)的邏輯回歸模型是一種廣義線性模型齿椅，非常容易實(shí)現(xiàn)大規(guī)模實(shí)時(shí)并行處理戈轿，因此在工業(yè)界獲得了廣泛應(yīng)用症副，但是線性模型的學(xué)習(xí)能力有限店雅，不能捕獲高階特征(非線性信息)，而在進(jìn)行CTR預(yù)估時(shí)贞铣，除了單特征外闹啦，往往要對(duì)特征進(jìn)行組合。對(duì)于特征組合來(lái)說(shuō)辕坝，業(yè)界現(xiàn)在通用的做法主要有兩大類：FM系列與DNN系列窍奋。今天，我們就來(lái)分享下FM算法。

二琳袄、為什么需要FM

　　　　1江场、特征組合是許多機(jī)器學(xué)習(xí)建模過(guò)程中遇到的問(wèn)題，如果對(duì)特征直接建模窖逗，很有可能會(huì)忽略掉特征與特征之間的關(guān)聯(lián)信息址否，因此，可以通過(guò)構(gòu)建新的交叉特征這一特征組合方式提高模型的效果碎紊。

　　　　2佑附、高維的稀疏矩陣是實(shí)際工程中常見(jiàn)的問(wèn)題，并直接會(huì)導(dǎo)致計(jì)算量過(guò)大矮慕，特征權(quán)值更新緩慢帮匾。試想一個(gè)10000*100的表，每一列都有8種元素痴鳄，經(jīng)過(guò)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(wàn)維的數(shù)值特征，特征空間一下子暴增一百萬(wàn)顾画。所以大廠動(dòng)不動(dòng)上億維度取劫，就是這么來(lái)的。

　　　　而FM的優(yōu)勢(shì)就在于對(duì)這兩方面問(wèn)題的處理研侣。首先是特征組合谱邪，通過(guò)對(duì)兩兩特征組合，引入交叉項(xiàng)特征庶诡，提高模型得分惦银；其次是高維災(zāi)難，通過(guò)引入隱向量（對(duì)參數(shù)矩陣進(jìn)行矩陣分解）末誓，完成對(duì)特征的參數(shù)估計(jì)扯俱。

三、原理及求解

在看FM算法前喇澡，我們先回顧一下最常見(jiàn)的線性表達(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ò)程 ：　　　

　　　　從上面的式子可以很容易看出拜英，組合部分的特征相關(guān)參數(shù)共有n(n?1)/2個(gè)。但是如第二部分所分析琅催，在數(shù)據(jù)很稀疏的情況下居凶，滿足xi,xj都不為0的情況非常少，這樣將導(dǎo)致ωij無(wú)法通過(guò)訓(xùn)練得出藤抡。

為了求出ωij侠碧，我們對(duì)每一個(gè)特征分量xi引入輔助向量Vi=(vi1,vi2,?,vik)。然后缠黍，利用vivj^T對(duì)ωij進(jìn)行求解：

　　　　那么ωij組成的矩陣可以表示為:

那么弄兜，如何求解vi和vj呢？主要采用了公式：

　　　　具體推導(dǎo)過(guò)程如下：

四瓷式、參數(shù)求解

　　　　利用梯度下降法替饿，通過(guò)求損失函數(shù)對(duì)特征（輸入項(xiàng)）的導(dǎo)數(shù)計(jì)算出梯度，從而更新權(quán)值贸典。設(shè)m為樣本個(gè)數(shù)视卢，θ為權(quán)值。

其中廊驼，是和i無(wú)關(guān)的据过，可以事先求出來(lái)。每個(gè)梯度都可以在O(1)時(shí)間內(nèi)求得妒挎，整體的參數(shù)更新的時(shí)間為O(kn)绳锅。

一個(gè)小問(wèn)題：隱向量?

?就是embedding vector?

答案：不是，具體計(jì)算過(guò)程大家可以舉個(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í)。