推薦系統(tǒng)-重排序-CTR-FM模型及FFM等

1 概述

重排序模型中壹粟，特征主要使用離散one-hot編碼的特征畜晰。這是由任務(wù)本身特點(diǎn)與歷史發(fā)展以及模型特點(diǎn)決定的西土。
首先就任務(wù)本身來說陆错，主要涉及到的特征分為用戶特征-物品特征-行為特征。這些特征往往都是離散的如用戶性別剪侮，用戶愛好拭宁，物品分類等
就歷史發(fā)展來說，是從人工規(guī)則--LR--GBDT+LR--FM--... 發(fā)展而來，這里都傾向于離散特征
而就整個(gè)發(fā)展過程中最關(guān)鍵以及工業(yè)應(yīng)用中最常用的模型LR來講杰标，離散特征更有優(yōu)勢
而one-hot編碼的離散特征兵怯，更容易引入非線性以及容易后續(xù)的特征組合，所以獨(dú)熱(one-hot)編碼的離散特征在推薦系統(tǒng)重排序以及CTR預(yù)測中都十分普遍在旱。

1.1 特征與特征域(feature field)

例如我們有數(shù)據(jù)：用戶性別，年齡推掸，物品品牌桶蝎，物品價(jià)格等特征，則可以做如下轉(zhuǎn)化
性別：[男谅畅，女]：[1,0] 表示男
年齡：[0-15歲登渣，15-25歲，25-35歲毡泻，35-50歲胜茧，大于50歲]：[0,0,1,0,0] 表示用戶年齡在25-35之間
物品品牌：[李寧，特步仇味，Nike呻顽，Adidas，匡威] ： [0,0,0,1,0]表示Adidas
物品價(jià)格：[0-500元丹墨，500-1000元廊遍，1000-2000元，大2000元]：[0,1,0,0]則表示物品價(jià)格500-1000元

域	性別		年齡					品牌					價(jià)格
特征	男	女	15	25	35	50	>50	ln	tb	nike	adi	kw	500	1000	2000	>2000
樣本	1	0	0	0	1	0	0	0	0	0	1	0	0	1	0	0

則 $x=[1,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0]$ 表示一個(gè)樣本
y=1可以表示一個(gè)年齡25-35歲的男性購買或點(diǎn)擊了一個(gè)adi品牌價(jià)格500-1000之間的商品或其廣告
所以男女分別變成了特征通過01表示是否是該特征贩挣，而性別作為男女的抽象則變成了特征域喉前。
這里其實(shí)對于域，并沒有嚴(yán)格的規(guī)定王财，從常識來講傾向于把域如此來分卵迂，但同樣，也可以根據(jù)具體樣本特征做分組绒净。
其主旨是：相同類型的特征組成一個(gè)域

2 FM(Factorization Machine)

2.1 模型推導(dǎo)

一般線性模型
$f_{line}(x)=w_0+\sum_{i=1}^{n}w_ix_i \tag{2.1}$
注意此處 $x_i$ 表示樣本的第i個(gè)特征见咒，而不是第i個(gè)樣本。n表示每個(gè)樣本共n維特征挂疆。

LR
$f_{LR}(x)=\frac{1}{1+exp(-f_{line}(x))}=\frac{1}{1+exp(-w_0-\sum_{i=1}^{n}w_ix_i)} \tag{2.2}$
LR是線性模型的一個(gè)轉(zhuǎn)換论颅。
但是從線性模型公式我們可以看出，線性模型只是使用了單個(gè)特征囱嫩，沒有考慮不同特征之間交叉的因素恃疯。例如性別和品牌的交叉，組成新特征“男-Nike”墨闲，“女-Nike”今妄，“男-李寧”，“女-李寧”等，這些同樣也是能夠提供信息的盾鳞。
所以犬性，可以設(shè)計(jì)一個(gè)新模型
$f(x)=w_0+\sum_{i=1}^{n}w_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}w_{ij}x_ix_j \tag{2.3}$
這相比于一般線性模型，就多了二元特征交叉的信息腾仅。當(dāng)然乒裆，也可以繼續(xù)添加三元交叉，四元交叉等等
但是推励，這里又要考慮計(jì)算量的問題鹤耍。首先要注意，對于CTR任務(wù)验辞，n是很大的稿黄，因?yàn)楠?dú)熱編碼之后，域的展開就非常大跌造。而當(dāng)我們考慮二元交叉特征時(shí)杆怕，組合特征是 $n^2$ 數(shù)量級的
這會造成參數(shù)數(shù)量呈指數(shù)增長，而樣本量m基本固定壳贪。這就導(dǎo)致添加三元等更高的特征交叉后陵珍，特征維度很容易超過樣本量m
當(dāng)特征維度遠(yuǎn)大于樣本量m時(shí)，每個(gè)參數(shù)就難以得到足夠的訓(xùn)練违施，造成欠擬合
所以暫時(shí)只考慮二元特征交叉
而僅僅是二元特征交叉撑教，其參數(shù) $w_{ij}$ 是 $n^2$ 級別的。而又由于 $x$ 本身就稀疏醉拓，所以 $x_ix_j$ 更加稀疏伟姐，在總體樣本上，很容易出現(xiàn)某個(gè)組合 $x_ix_j$ 總為0的情況亿卤，這樣對應(yīng)的 $w_{ij}$ 就得不到訓(xùn)練愤兵。
為了應(yīng)對這個(gè)問題，就需要把參數(shù)數(shù)量降下來排吴。

通過線性代數(shù)知識我們知道可以使用矩陣分解技術(shù)把矩陣Ｗ分解
$W=VV^T$
W是 $n*n$ 維秆乳，V是 $n*k$ 維，當(dāng)令 $k<<n$ 時(shí)钻哩，就可以把計(jì)算量從 $o(n^2)$ 降到 $nk\approx o(n)$
所以根據(jù)這樣的思想屹堰，我們可以對每個(gè)特征 $x_i$ 構(gòu)建一個(gè)向量 $v_i=(v_1,v_2...v_k)$ ,則 $w_{ij}=<v_i·v_j>$
則式(2.3)可以轉(zhuǎn)換成
$f(x)=w_0+\sum_{i=1}^{n}w_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}<v_i·v_j>x_ix_j \tag{2.4}$
進(jìn)一步轉(zhuǎn)化得
$f(x)=w_0+\sum_{i=1}^{n}w_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(\sum_{l=1}^{k}v_{il}v_{jl})x_ix_j \tag{2.5}$
式(2.4)(2.5)就是FM模型，我們稱 $v_{i}$ 為隱向量或者 $x_i$ 的隱向量

2.2 優(yōu)化算法

我們對式(5)的最后一部分做進(jìn)一步轉(zhuǎn)換 $^1$ (詳情見最后注釋)
$\begin{alignedat}{2} \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(\sum_{l=1}^{k}v_{il}v_{jl})x_ix_j&=\sum_{l=1}^{k}\bigg[\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(v_{il}v_{jl})x_ix_j \bigg]\\ &=\sum_{l=1}^{k}\bigg[\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(v_{il}x_i)(v_{jl}x_j) \bigg]\\ &=\sum_{l=1}^{k}\frac{1}{2}\bigg[(\sum_{i=1}^{n}v_{il}x_i)^2-\sum_{i=1}^{n}(v_{il}x_i)^2 \bigg] \end{alignedat}$

對于此模型街氢，設(shè)有損失函數(shù)
$L(f(x),y)$
可以是MAE扯键，也可以是交叉熵?fù)p失函數(shù)
其根據(jù)鏈?zhǔn)椒▌t梯度
$\frac{\partial L}{\partial \theta}=\frac{\partial L}{\partial f(x)}·\frac{\partial f(x)}{\partial \theta}$
即表示為損失函數(shù)對模型的導(dǎo)乘以模型對參數(shù)的導(dǎo)。
模型對參數(shù)的求導(dǎo)：
$f(x)=w_0+\sum_{i=1}^{n}w_ix_i+\sum_{l=1}^{k}\frac{1}{2}\bigg[(\sum_{i=1}^{n}v_{il}x_i)^2-\sum_{i=1}^{n}(v_{il}x_i)^2\bigg]$

$\frac{\partial f(x)}{\partial \theta}= \begin{cases}1,&\text{ if }\theta=w_0 \\ x_i, &\text{ if }\theta=w_i \\ x_i\sum_{j=1}^{n}v_{jl}x_j-v_{il}x_i^2, &\text{ if }\theta=v_{il} \end{cases}$

面對這樣的情況珊肃，我們可以使用如下幾種優(yōu)化算法求解參數(shù)

隨機(jī)梯度下降法(SGD)
交替最小二乘法(ALS)
馬爾科夫鏈蒙特卡羅法(MCMC)

隨機(jī)梯度下降法(SGD)

很容易理解荣刑，根據(jù)上述式子可以得出損失函數(shù)的梯度馅笙，得知梯度后就很方便的可以應(yīng)用SGD

交替最小二乘法(ALS)

又稱坐標(biāo)下降法
即每次只優(yōu)化一個(gè)參數(shù)。令導(dǎo)數(shù)=0厉亏，求解當(dāng)前這個(gè)參數(shù)的最優(yōu)值董习。

馬爾科夫鏈蒙特卡羅法(MCMC)

不會不想查 :)

以上三種方法具體可移步參考鏈接

3 FFM(Field Factorization Machine)

3.1 模型推導(dǎo)

FM的核心是特征交叉，這里面最重要的就是隱向量爱只。FM中皿淋，每個(gè)特征 $x_i$ 都有且只有一個(gè)隱向量 $v_i$
在特征交叉時(shí)，對應(yīng)的隱向量點(diǎn)乘得到這個(gè)交叉特征的權(quán)重 $w_{ij}$
然而恬试，每個(gè)特征所代表的意義是不一樣的窝趣，例如在計(jì)算交叉特征：“男性-20到30歲”，“男性-Nike”時(shí)忘渔，用同一個(gè)男性隱向量v點(diǎn)乘20-30歲和nike的隱向量結(jié)果的區(qū)別度低高帖。FFM認(rèn)為缰儿，每個(gè)特征 $x_i$ 的隱向量應(yīng)該有多個(gè)畦粮，當(dāng)該特征與不同類型(域field)的特征做交叉時(shí)，應(yīng)該使用對應(yīng)的隱向量乖阵，這樣可以做到更精細(xì)地刻畫交叉特征的權(quán)重宣赔。所以每個(gè)特征應(yīng)該有和field數(shù)量相同的隱向量個(gè)數(shù)。
假設(shè)樣本共有l(wèi)個(gè)域 $(f_1,f_2,..f_l)$
特征 $x_i,x_j$ 分別屬于域 $f_I,f_J$
$x_i$ 有l(wèi)個(gè)隱向量 $(v_{i1},v_{i2}...v_{il})$ 分別對應(yīng)l個(gè)域瞪浸，v是一個(gè)k維向量
$x_j$ 有l(wèi)個(gè)隱向量 $(v_{j1},v_{j2}...v_{jl})$ 分別對應(yīng)l個(gè)域儒将，v是一個(gè)k維向量
則當(dāng) $x_i,x_j$ 做交叉時(shí)，
$x_i$ 應(yīng)該選取 $x_j$ 所在域?qū)?yīng)的隱向量 $v_{iJ}$
$x_j$ 應(yīng)該選取 $x_i$ 所在域?qū)?yīng)的隱向量 $v_{jI}$
即
$<v_{iJ}·v_{jI}>x_ix_j$
這樣更精準(zhǔn)了对蒲，但是參數(shù)量多了l倍钩蚊。所以實(shí)際應(yīng)用中，F(xiàn)FM設(shè)置的隱向量長度k會比FM的k小很多以盡可能降低計(jì)算量蹈矮。

3.2 優(yōu)化算法

同F(xiàn)M

4 總結(jié)

FM模型相比傳統(tǒng)LR模型砰逻，多了二元交叉特征組合。提高了模型表征能力泛鸟。
從根本上來說蝠咆，F(xiàn)M之所以可以這么容易的拓展與組合，是因?yàn)槿蝿?wù)使用的是獨(dú)熱編碼的離散化特征
FM全稱Factorization Machine北滥。其中Factorization是因式分解的意思刚操。通過上面的介紹，我想很容易理解這個(gè)因式分解的意思再芋。當(dāng)出現(xiàn)特征交叉如 $x_i,x_j$ 菊霜，必然會有這個(gè)交叉特征的參數(shù) $w_{ij}$ ，而FM把這個(gè)參數(shù)分解成了兩個(gè)向量的點(diǎn)乘 $<v_i·v_j>$ 济赎。而這兩個(gè)向量可以看成是特征 $x_i,x_j$ 的一種編碼占卧。
對隱向量的進(jìn)一步探討
對于onehot編碼來說遗菠，
$x_i$ 特征對應(yīng)著向量 $[0,0...1...0...0]$ 其中第i位=1，其他=0华蜒；
$x_i$ 特征對應(yīng)著向量 $[0,0...0...1...0]$ 其中第j位=1辙纬，其他=0；
所以 $x_i$ 的隱向量= $v_i$ 等價(jià)于 $[0,0...1...0...0]$ 被編碼成 $v_i$ ：
$v_i=transform([0,0...1...0...0])$
而 $x_i*x_j$ 表示兩特征交叉叭喜，其權(quán)重 $w_{ij}$ 則被FM表示成了兩隱向量的內(nèi)積 $<v_i·v_j>$
則 $<v_i·v_j>x_i*x_j=transform([0,0...1...0...0])·transform([0,0...0...1...0])$
注意式子
$\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}<v_i·v_j>x_ix_j \tag{4.1}$
雖然看似有 $o(n^2)$ 的復(fù)雜度贺拣，但實(shí)際上 $x_ix_j$ 絕大多數(shù)時(shí)候都=0，這表示對于每一個(gè)樣本捂蕴，式(4.1)計(jì)算量遠(yuǎn)達(dá)不到 $o(n^2)$ 譬涡。對于一個(gè)特定的樣本，式(4.1)退化成
$\sum_{i=1}^{\overline{n} -1}\sum_{j=i+1}^{\overline{n}}<v_i·v_j>x_ix_j \tag{4.2}$
$\overline{n}$ 表示該樣本的稀疏特征中1的數(shù)量啥辨。
即
$\begin{alignedat}{2} \sum_{i=1}^{\overline{n} -1}\sum_{j=i+1}^{\overline{n}}<v_i·v_j>x_ix_j = \sum_{i=1}^{\overline{n} -1}\sum_{j=i+1}^{\overline{n}}transform([0,0...1...0...0])·transform([0,0...0...1...0]) \end{alignedat}$
請理解這段涡匀，這段在理解DeepFM中有用。
參加過一個(gè)會議溉知，會上有人說對于CTR預(yù)測或推薦系統(tǒng)重排序來說陨瘩，最根本的是做特征組合。
因?yàn)楠?dú)熱編碼的特征级乍，每一維表征的信息太少舌劳，需要通過組合來提高每一維的表征能力。
同時(shí)玫荣，特征組合引入了非線性甚淡，可以提高擬合能力。
其實(shí)GBDT+LR模型捅厂，也是一種特征組合贯卦。
FM實(shí)際上做了一個(gè)Embedding 工作，把稀疏的獨(dú)熱特征轉(zhuǎn)換成了稠密特征焙贷，這對于深度學(xué)習(xí)是友好的撵割，所以后續(xù)有很多FM和神經(jīng)網(wǎng)絡(luò)結(jié)合的工作。

未完待續(xù)盈厘。睁枕。。

5 注釋

[1].此處應(yīng)用平方和公式
$(x_1+x_2+x_3)^2=x_1^2+x_2^2+x_3^2+2x_1x_2+2x_1x_3+2x_2x_3$
$x_1x_2+x_1x_3+x_2x_3=\frac{1}{2}((x_1+x_2+x_3)^2-(x_1^2+x_2^2+x_3^2))$
即
$\sum_{i=1}^{2}\sum_{j=i+1}^{3}x_ix_j=\frac{1}{2}\bigg[(\sum_{i=1}^{3}x_i)^2-\sum_{i=1}^{3}(x_i)^2\bigg]$

參考

https://www.cnblogs.com/pinard/p/6370127.html
https://tracholar.github.io/machine-learning/2017/03/10/factorization-machine.html
https://www.cnblogs.com/wkang/p/9788012.html

最后編輯于：2019.07.17 16:57:25

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末沸手，一起剝皮案震驚了整個(gè)濱河市外遇，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌契吉，老刑警劉巖跳仿，帶你破解...
沈念sama閱讀 221,576評論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異捐晶，居然都是意外死亡菲语，警方通過查閱死者的電腦和手機(jī)妄辩，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,515評論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來山上，“玉大人眼耀，你說我怎么就攤上這事∨搴叮” “怎么了哮伟？”我有些...
開封第一講書人閱讀 168,017評論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長妄帘。經(jīng)常有香客問我楞黄，道長，這世上最難降的妖魔是什么抡驼？我笑而不...
開封第一講書人閱讀 59,626評論 1贊 296
?港島之戀（遺憾婚禮）
正文為了忘掉前任鬼廓，我火速辦了婚禮，結(jié)果婚禮上致盟，老公的妹妹穿的比我還像新娘碎税。我一直安慰自己，他們只是感情好勾邦，可當(dāng)我...
茶點(diǎn)故事閱讀 68,625評論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布蚣录。她就那樣靜靜地躺著割择，像睡著了一般眷篇。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上荔泳，一...
開封第一講書人閱讀 52,255評論 1贊 308
城市分裂傳說
那天蕉饼，我揣著相機(jī)與錄音，去河邊找鬼玛歌。笑死昧港，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的支子。我是一名探鬼主播创肥，決...
沈念sama閱讀 40,825評論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼值朋！你這毒婦竟也來了叹侄？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 39,729評論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤昨登，失蹤者是張志新（化名）和其女友劉穎趾代，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體丰辣，經(jīng)...
沈念sama閱讀 46,271評論 1贊 320
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡撒强，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,363評論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年禽捆，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片飘哨。...
茶點(diǎn)故事閱讀 40,498評論 1贊 352
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡胚想，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出芽隆，到底是詐尸還是另有隱情顿仇，我是刑警寧澤，帶...
沈念sama閱讀 36,183評論 5贊 350
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布摆马，位于F島的核電站臼闻，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏囤采。R本人自食惡果不足惜述呐，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,867評論 3贊 333
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望蕉毯。院中可真熱鬧乓搬，春花似錦、人聲如沸代虾。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,338評論 0贊 24
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽棉磨。三九已至江掩，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間乘瓤，已是汗流浹背环形。一陣腳步聲響...
開封第一講書人閱讀 33,458評論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留衙傀，地道東北人抬吟。一個(gè)月前我還...
沈念sama閱讀 48,906評論 3贊 376
代替公主和親
正文我出身青樓，卻偏偏與公主長得像统抬，于是被迫代替她去往敵國和親火本。傳聞我的和親對象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,507評論 2贊 359