本文僅為記錄學習FM、FFM、DeepFM過程中的一些理解，并不會涉及太多公式細節(jié)推導，細節(jié)方面可以參考 深入FFM原理與實踐 和 『我愛機器學習』FM、FFM與DeepFM
以及相關論文，本文主要內容也是摘自與上述博客。
FM模型的引入-廣告特征的稀疏性
FM（Factorization machines）模型由Steffen Rendle于2010年提出，目的是解決稀疏數據下的特征組合問題。
在介紹FM模型之前，來看看稀疏數據的訓練問題。以廣告CTR（click-through rate）點擊率預測任務為例，假設有如下數據：
第一列Clicked是類別標記，標記用戶是否點擊了該廣告，而其余列則是特征（這里的三個特征都是類別類型），一般的，我們會對數據進行One-hot編碼將類別特征轉化為數值特征，轉化后數據如下:
經過One-hot編碼后，特征空間是十分稀疏的。特別的，某類別特征有m種不同的取值，則one-hot編碼后就會被變?yōu)閙維！當類別特征越多、類別特征的取值越多，其特征空間就更加稀疏。
此外，往往我們會將特征進行兩兩的組合，這是因為：通過觀察大量的樣本數據可以發(fā)現，某些特征經過關聯之后，與label之間的相關性就會提高。例如，“USA”與“Thanksgiving”、“China”與“Chinese New Year”這樣的關聯特征，對用戶的點擊有著正向的影響。換句話說，來自“China”的用戶很可能會在“Chinese New Year”有大量的瀏覽、購買行為，而在“Thanksgiving”卻不會有特別的消費行為。這種關聯特征與label的正向相關性在實際問題中是普遍存在的，如“化妝品”類商品與“女”性，“球類運動配件”的商品與“男”性，“電影票”的商品與“電影”品類偏好等。
再比如，用戶更常在飯點的時間下載外賣app，因此，引入兩個特征的組合是非常有意義的。
如何表示兩個特征的組合呢？一種直接的方法就是采用多項式模型來表示兩個特征的組合，????為第??個特征的取值（注意和以往表示第??個樣本的特征向量的區(qū)別），????????表示特征????和????的特征組合，其系數??????即為我們學習的參數，也是????????組合的重要程度：
式1-1也可以稱為Poly2(degree-2 poly-nomial mappings)模型。注意到式子1-1中參數的個數是非常多的！一次項有d+1個，二次項（即組合特征的參數）共有??(???1)/2個，而參數與參數之間彼此獨立，在稀疏場景下，二次項的訓練是很困難的。因為要訓練??????，需要有大量的????和????都非零的樣本（只有非零組合才有意義）。而樣本本身是稀疏的，滿足????????≠0的樣本會非常少，樣本少則難以估計參數??????，訓練出來容易導致模型的過擬合。
為此，Rendle于2010年提出FM模型，它能很好的求解式1-1，其特點如下：
- FM模型可以在非常稀疏的情況下進行參數估計
- FM模型是線性時間復雜度的，可以直接使用原問題進行求解，而且不用像SVM一樣依賴支持向量。
- FM模型是一個通用的模型，其訓練數據的特征取值可以是任意實數。而其它最先進的分解模型對輸入數據有嚴格的限制。FMs可以模擬MF、SVD++、PITF或FPMC模型。
FM模型
前面提到過，式1-1的參數難以訓練時因為訓練數據的稀疏性。對于不同的特征對????,????和????,????，式1-1認為是完全獨立的，對參數??????和??????分別進行訓練。而實際上并非如此，不同的特征之間進行組合并非完全獨立，如下圖所示:
回想矩陣分解，一個rating可以分解為user矩陣和item矩陣，如下圖所示：
分解后得到user和item矩陣的維度分別為????和????，（k一般由用戶指定），相比原來的rating矩陣，空間占用得到降低，并且分解后的user矩陣暗含著user偏好，Item矩陣暗含著item的屬性，而user矩陣乘上item矩陣就是rating矩陣中用戶對item的評分。
因此，參考矩陣分解的過程，FM模型也將式1-1的二次項參數??????進行分解：
其中????是第??維特征的隱向量，其長度為??(?????)。 (?????????)為內積，其乘積為原來的??????，即:
為了方便說明，考慮下面的數據集（實際中應該進行one-hot編碼，但并不影響此處的說明）：
對于上面的訓練集，沒有（NBC，Adidas）組合，因此，Poly2模型就無法學習到參數????????,????????????。而FM模型可以通過特征組合(NBC，Nike)、(EPSN，Adidas) 分別學習到隱向量????????和??????????????，這樣使得在測試集中得以進行預測。
更一般的，經過分解，式2-1的參數個數減少為????個，對比式1-1，參數個數大大減少。使用小的k，使得模型能夠提高在稀疏情況下的泛化性能。此外，將??????進行分解，使得不同的特征對不再是完全獨立的，而它們的關聯性可以用隱式因子表示，這將使得有更多的數據可以用于模型參數的學習。比如????,????與????,????的參數分別為：?????,?????和?????,?????，它們都可以用來學習????，更一般的，包含????????≠0&??≠??的所有樣本都能用來學習????，很大程度上避免了數據稀疏性的影響。
FFM模型
考慮下面的數據集：
對于第一條數據來說，FM模型的二次項為：?????????????????????+?????????????????????+?????????????????????。（這里只是把上面的v符合改成了w）每個特征只用一個隱向量來學習和其它特征的潛在影響。對于上面的例子中，Nike是廣告主，Male是用戶的性別，描述（EPSN，Nike）和（EPSN，Male）特征組合，FM模型都用同一個??????????，而實際上，ESPN作為廣告商，其對廣告主和用戶性別的潛在影響可能是不同的。
因此，Yu-Chin Juan借鑒Michael Jahrer的論文（Ensemble of collaborative filtering and feature engineered models for click through rate prediction），將field概念引入FM模型。
field是什么呢？即相同性質的特征放在一個field。比如EPSN、NBC都是屬于廣告商field的，Nike、Adidas都是屬于廣告主field，Male、Female都是屬于性別field的。簡單的說，同一個類別特征進行one-hot編碼后生成的數值特征都可以放在同一個field中，比如最開始的例子中Day=26/11/15 Day=19/2/15可以放于同一個field中。如果是數值特征而非類別，可以直接作為一個field。
引入了field后，對于剛才的例子來說，二次項變?yōu)椋?/p>
- 對于特征組合（EPSN，Nike）來說，其隱向量采用的是??????????,??和??????????,??，對于??????????,??這是因為Nike屬于廣告主（Advertiser）的field，而第二項??????????,??則是EPSN是廣告商（Publisher）的field；
- 再舉個例子，對于特征組合（EPSN，Male）來說，??????????,?? 是因為Male是用戶性別(Gender)的field，而第二項??????????,??是因為EPSN是廣告商（Publisher）的field。
下面的圖來自criteo，很好的表示了三個模型的區(qū)別：
FFM 數學公式
因此，FFM的數學公式表示為：
其中????和????分別代表第i個特征和第j個特征所屬的field。若field有??個，隱向量的長度為k，則二次項系數共有??????個，遠多于FM模型的????個。此外，隱向量和field相關，并不能像FM模型一樣將二次項化簡，計算的復雜度是??2??。
通常情況下，每個隱向量只需要學習特定field的表示，所以有???????????????。
好了，上面都是轉自博客 『我愛機器學習』FM、FFM與DeepFM
。對于FM和FFM的關系，深入FFM原理與實踐中有這么一段話：假設樣本的 n 個特征屬于 f 個field，那么FFM的二次項有 nf個隱向量。而在FM模型中，每一維特征的隱向量只有一個。FM可以看作FFM的特例，是把所有特征都歸屬到一個field時的FFM模型。根據FFM的field敏感特性，可以導出其模型方程。
說一下自己對上面這段話的理解：
在FM中我們將組合特征系數進行了矩陣分解以進行了一個降維，得到每個特征系數的一個k維隱向量，我們可以理解為將每個特征系數進行了embedding到k維空間中。而在FFM中，我們對這加入了filed信息。從FFM角度理解，在FM中我們可以所有系數的k維embedding向量看作是一個filed中的k維向量，所以一個特征x的的FM隱向量只有[v1, v2, ..., vk]，當加入filed信息后的嵌入空間信息如下：
也即之前是embedding 到同一個filed（f=1）的k維空間中，現在考慮了不同的field信息后，相當于將系數embedding到fk維空間中。
DeepFM
FM模型可以用神經網絡進行表示：
模型輸入??=[????????????1,????????????2,?,??????????????]，這是一個d維的向量，其中??????????????即為第i個field的特征表示，如果是類別，則為one-hot編碼后的向量，連續(xù)值則為它本身。
然后對每個field分別進行embedding，如下圖：
值得注意的是，即使各個field的維度是不一樣的，但是它們embedding后長度均為k。
接著FM層即為embedding后結果的內積和一次項的和，最后一層sigmoid后再輸出結果。
看到這里，可能你感到困惑的就是embedding層，這么表示是為啥？答案是這樣表示和fm模型等價！
假設第i個field 向量維度為k，embedding層的參數可以表示為一個k * m的矩陣：
其中??????可以理解為第a個取值embedding后的結果在隱向量的第b維。
由于進行了one-hot編碼，所以對應的??????????????只有一個值為1，其余的都為0,假設第c列為1，則：
若兩個field做內積，假設非0的那一列為c和d則：
其實和FM模型是一樣的！
DeepFM的模型如下圖：
左邊就是剛才將的FM模型的神經網絡表示，而右邊的則為deep部分，為全連接的網絡，用于挖掘高階的交叉特征。整個模型共享embedding層，最后的結果就是把FM部分和DNN的部分做sigmoid：
參考：
- Rendle, Steffen. “Factorization machines.” Data Mining (ICDM), 2010 IEEE 10th International Conference on. IEEE, 2010.
- Juan, Yuchin, et al. “Field-aware factorization machines for CTR prediction.” Proceedings of the 10th ACM Conference on Recommender Systems. ACM, 2016.
- Guo, Huifeng, et al. “Deepfm: A factorization-machine based neural network for CTR prediction.” arXiv preprint arXiv:1703.04247 (2017).
- 深入FFM原理與實踐
- Factorization Machines
- CTR Prediction: From Linear Models to Field-aware Factorization Machines
