1、背景
在計算廣告和推薦系統(tǒng)中，CTR預(yù)估(click-through rate)是非常重要的一個環(huán)節(jié)挟裂，判斷一個商品的是否進行推薦需要根據(jù)CTR預(yù)估的點擊率來進行属愤。在進行CTR預(yù)估時号胚，除了單特征外籽慢，往往要對特征進行組合。對于特征組合來說猫胁，業(yè)界常用的方法有人工特征工程 + LR（Logistic Regression）箱亿、GBDT（Gradient Boosting Decision Tree） + LR、FM（Factorization Machine）和FFM（Field-aware Factorization Machine）模型弃秆。最近幾年也出現(xiàn)了很多基于FM改進的方法届惋，如deepFM，F(xiàn)NN菠赚，PNN脑豹，DCN，xDeepFM等衡查。
2瘩欺、動機（one-hot編碼帶來的問題）
FM(Factorization Machine)主要是為了解決數(shù)據(jù)稀疏的情況下，特征怎樣組合的問題拌牲。已一個廣告分類的問題為例俱饿，根據(jù)用戶與廣告位的一些特征，來預(yù)測用戶是否會點擊廣告塌忽。數(shù)據(jù)如下：(本例來自美團技術(shù)團隊分享的paper)
clicked是分類值，表明用戶有沒有點擊該廣告砚婆。1表示點擊械拍，0表示未點擊。而country,day,ad_type則是對應(yīng)的特征装盯。對于這種categorical特征，一般都是進行one-hot編碼處理甲馋。
將上面的數(shù)據(jù)進行one-hot編碼以后埂奈，就變成了下面這樣 ：
因為是categorical特征定躏，所以經(jīng)過one-hot編碼以后账磺，不可避免的樣本的數(shù)據(jù)就變得很稀疏。舉個非常簡單的例子痊远，假設(shè)淘寶或者京東上的item為100萬垮抗，如果對item這個維度進行one-hot編碼，光這一個維度數(shù)據(jù)的稀疏度就是百萬分之一碧聪。由此可見冒版，數(shù)據(jù)的稀疏性，是我們在實際應(yīng)用場景中面臨的一個非常常見的挑戰(zhàn)與問題逞姿。
one-hot編碼帶來的另一個問題是特征空間變大辞嗡。同樣以上面淘寶上的item為例捆等，將item進行one-hot編碼以后，樣本空間有一個categorical變?yōu)榱税偃f維的數(shù)值特征续室，特征空間一下子暴增一百萬栋烤。所以大廠動不動上億維度，就是這么來的挺狰。
3明郭、對特征進行組合
普通的線性模型，我們都是將各個特征獨立考慮的丰泊，并沒有考慮到特征與特征之間的相互關(guān)系达址。但實際上，大量的特征之間是有關(guān)聯(lián)的趁耗。最簡單的以電商為例沉唠，一般女性用戶看化妝品服裝之類的廣告比較多，而男性更青睞各種球類裝備苛败。那很明顯满葛，女性這個特征與化妝品類服裝類商品有很大的關(guān)聯(lián)性，男性這個特征與球類裝備的關(guān)聯(lián)性更為密切罢屈。如果我們能將這些有關(guān)聯(lián)的特征找出來嘀韧，顯然是很有意義的。
一般的線性模型為：
? ???????????????????
從上面的式子很容易看出缠捌，一般的線性模型壓根沒有考慮特征間的關(guān)聯(lián)锄贷。為了表述特征間的相關(guān)性，我們采用多項式模型曼月。在多項式模型中谊却，特征與
的組合用
表示。為了簡單起見哑芹，我們討論二階多項式模型炎辨。具體的模型表達式如下：
為了簡單起見，我們只考慮二階交叉的情況聪姿，具體的模型如下：
? ???????????????????
式中碴萧，表示樣本的特征數(shù)量,
表示第
個特征，與線性模型相比末购，F(xiàn)M的模型就多了后面特征組合的部分破喻。
4、FM求解
從FM公式可以看出盟榴，組合特征的參數(shù)一共有?n(n?1)/2個曹质，任意兩個參數(shù)都是獨立的。然而，在數(shù)據(jù)稀疏性普遍存在的實際應(yīng)用場景中咆繁，二次項參數(shù)的訓(xùn)練是很困難的讳推。其原因是，每個參數(shù)的訓(xùn)練需要大量
和
都非零的樣本玩般；由于樣本數(shù)據(jù)本來就比較稀疏银觅，滿足
和
都非零”的樣本將會非常少。訓(xùn)練樣本的不足坏为，很容易導(dǎo)致參數(shù)?
不準(zhǔn)確究驴，最終將嚴(yán)重影響模型的性能。
那么匀伏，如何解決二次項參數(shù)的訓(xùn)練問題呢洒忧？矩陣分解提供了一種解決思路。在model-based的協(xié)同過濾中够颠，一個rating矩陣可以分解為user矩陣和item矩陣熙侍，每個user和item都可以采用一個隱向量表示。比如在下圖中的例子中履磨，我們把每個user表示成一個二維向量蛉抓，同時把每個item表示成一個二維向量，兩個向量的點積就是矩陣中user對item的打分剃诅。
類似地，所有二次項參數(shù)可以組成一個對稱陣
（為了方便說明FM的由來矛辕，對角元素可以設(shè)置為正實數(shù)）笑跛，那么這個矩陣就可以分解為
，
的第
列便是第
維特征的隱向量聊品。換句話說飞蹂，每個參數(shù)
，這就是FM模型的核心思想杨刨。因此晤柄，F(xiàn)M的模型方程為（本文不討論FM的高階形式）
? ??????????????????
其中，是第
維特征的隱向量妖胀，
代表向量點積。隱向量的長度為
惠勒，二次項的參數(shù)數(shù)量減少為
個赚抡，遠少于多項式模型的參數(shù)數(shù)量。另外纠屋，參數(shù)因子化使得
的參數(shù)和
的參數(shù)不再是相互獨立的涂臣，因此我們可以在樣本稀疏的情況下相對合理地估計FM的二次項參數(shù)。具體來說，
和
的系數(shù)分別為
和
赁遗，它們之間有共同項
署辉。也就是說，所有包含“
的非零組合特征”（存在某個
岩四，使得
）的樣本都可以用來學(xué)習(xí)隱向量?vivi哭尝，這很大程度上避免了數(shù)據(jù)稀疏性造成的影響。而在多項式模型中剖煌，
和
是相互獨立的材鹦。
顯而易見，F(xiàn)M的模型公式是一個通用的擬合方程耕姊，可以采用不同的損失函數(shù)用于解決回歸桶唐、二元分類等問題，比如可以采用MSE（Mean Square Error）損失函數(shù)來求解回歸問題茉兰，也可以采用Hinge/Cross-Entropy損失來求解分類問題尤泽。當(dāng)然，在進行二元分類時规脸，F(xiàn)M的輸出需要經(jīng)過sigmoid變換坯约，這與Logistic回歸是一樣的。直觀上看燃辖，F(xiàn)M的復(fù)雜度是鬼店。但是，通過下面的等式黔龟，F(xiàn)M的二次項可以化簡妇智，其復(fù)雜度可以優(yōu)化到
?。由此可見氏身，F(xiàn)M可以在線性時間對新樣本作出預(yù)測巍棱。????????
? ??????????????????
我們再來看一下FM的訓(xùn)練復(fù)雜度航徙，利用SGD（Stochastic Gradient Descent）訓(xùn)練模型。模型各個參數(shù)的梯度如下：
其中到踏，是隱向量
的第
個元素。由于
只與
有關(guān)尚猿，而與
無關(guān)窝稿，在每次迭代過程中，只需計算一次所有
的
凿掂，就能夠方便地得到所有
的梯度伴榔。顯然，計算所有
的
的復(fù)雜度是
；已知
時踪少，計算每個參數(shù)梯度的復(fù)雜度是
塘安；得到梯度后，更新每個參數(shù)的復(fù)雜度是
援奢；模型參數(shù)一共有
個兼犯。因此，F(xiàn)M參數(shù)訓(xùn)練的復(fù)雜度也是
萝究。綜上可知免都，F(xiàn)M可以在線性時間訓(xùn)練和預(yù)測，是一種非常高效的模型帆竹。
5绕娘、代碼練習(xí)
參考文獻：
論文：Factorization Machines with Follow-The-Regularized-Leader for CTR prediction in Display Advertising
推薦系統(tǒng)遇上深度學(xué)習(xí)(一)--FM模型理論和實踐
