factorization machine和logistic regression的區別？

01-22

在線廣告系統的click model通常使用logistic regression模型，並通過特徵交叉來獲得高階屬性，而factorization machine能自動學習高階屬性的權值，不用通過人工的方式選取特徵來做交叉，似乎理論上更加完備，那麼問題來了，為何大部分廣告系統使用的是logistic regression模型，而不使用理論上更加完備的factorization machine?
個人猜測原因：因為factorization machine的predict的複雜度是O(k*n)，而logistic regression的複雜度是O(n)，在廣告這種請求量巨大的系統中，factorization machine的開銷更大

我來一句話回答下這個問題：

如果FM是用於二分類，那麼FM就是1) 用了顯式二階多項式kernel的LR 2) 將這個LR的係數矩陣做了low rank分解

PS1: FM真是個好東西... 不多說

PS2: 關於大規模FM，可以參見 @李沐最近的一個paper

為了把LR和FM聯繫起來，我們從這個角度來看logistic regression：它是對log odd ratio做線性回歸 $overrightarrow{w} cdot overrightarrow{x} = log frac{Pr(y=1|x, w)}{Pr(y=-1|x, w)}$ ，所以LR模型是這個有概率意義的sigmoid形式： $Pr(y=1|x,w)=frac{1}{1+e^{-wx}}$ 。

線性的模型本身不能去描述特徵之間的交互因素，這就需要在生成訓練樣本時在特徵工程中加上特徵組合，引入特徵之間的交互因素。這個從理論上可以看做是加上多項式kernel，但是這樣會把模型參數從n變成n^2/2，所以一般是人工來預先指定引入哪一部分特徵的組合。我們專門實現了一套DSL來指定特徵的轉換處理和組合配置，應用到特徵etl中。

比如問題中提到的在線廣告系統中的click model，往往被描述為給定廣告特徵、用戶特徵和上下文特徵下的一個條件概率： $Pr(click | ad, user, context)$ 。特徵組合往往是預先指定ad特徵中的哪些與user特徵中的哪些來組合, ad特徵中的哪些與context特徵中的哪些來組合，以及ad-user-context三階的特徵的組合。

這是許多成熟的在線廣告系統中點擊率模型的工作方式。特徵的選取和組合方案的優劣，依賴於對數據和業務的深入理解，這也是演算法工程師的核心競爭力之一。這些成熟的系統，也往往是被無數有較強核心競爭力的演算法工程師進行過無數次離線和在線實驗，不斷調整優化之後的狀態。

這種在模型訓練之前進行特徵的組合的處理方式，引入的問題是使得特徵維度更高、數據更加稀疏。比如ad本身有m個特徵，user本身有n個特徵，那麼ad和user的組合最多會有m*n個；如果再考慮context有l個特徵，那麼三者的組合最多會有m*n*l個。而這m*n或m*n*l個特徵中的絕大多數會是0，即沒有出現對應取值的樣本。

從這個角度來看，LR是從組合特徵的角度去描述單特徵之間的交互組合，而Factorization Machine實際上是從模型的角度來做的。即FM中特徵的交互是模型參數的一部分，比如只考慮二階的特徵組合：

$f(x)=wx + frac{1}{2}x^TV^TVx - diag(x^Tx)^Tdiag(V^TV)$ ，

$Pr(y=1|x)=frac{1}{1+e^{-f(x)}}$

V矩陣描述的是每個特徵的K維的latent factor，二階的特徵間的交互通過 $frac{1}{2}x^TV^TVx$ 來完成。與LR中的人工指定特徵組合的方案相比，這裡會引入同一類特徵的組合，比如user-user，ad-ad。理論上這類組合會在模型learning的過程中被學習出其對應 $Pr(y=1|x, .)$ 與 $Pr(y=-1|x, .)$ 非常接近，而最終 $v^Tv$ 趨近於0。不過實際應用中，因為數據往往是傾斜的，或者樣本集的分布不足以描述實際的分布，往往並不能保證同類特徵的組合結果參數趨近於0。

解決同類特徵不去做組合這個問題的一個方案是指定哪類特徵與哪類特徵的embedding矩陣去做交互，比如指定類似LR中的user與ad特徵的交互：

另外，當有多個不同範疇的特徵互相交互的時候可以引入不同的embedding。比如user-ad, context-ad，這裡邊ad與兩類特徵交互，可以分別安排兩個V矩陣來處理。這可以理解為ad對user時的k維的latent factor與ad對context時的k維的latent factor在每一個維度上的意義不同。這個方案參考Field-aware Factorization Machines。

---------

這樣，在特徵方面，因為FM模型的原因，與LR相比，人工能干預、影響的因素少了，同時對模型的干預方式變得更加間接和不直觀。

至於線上效率問題，實際上FM的模型結果可以預處理成線性的形式， $w_{i,j}=v_i^Tv_j$ ，所以與LR在效率上並沒有差距。

-------

這裡加上一個鄙司應用Field-aware factorization machine與LR的線上AB test對比。綠色對應FFM的，紅色對應LR的，隱去了具體數值：

---------

這是我的一點點認識，希望大家多多補充和提出建議。

謝邀，這個問題前面的答主回答都很專業，我只做一些補充。

在廣告系統中，FM的使用其實是越來越多了，目前百度、頭條和bing等廣告系統中都有使用，而且效果不錯，畢竟FM對比LR多了二階kernel嘛。

FM一直以來有兩個問題，阻礙了其在廣告上的更大規模應用，目前來看已經得到了一定的解決。這兩個問題主要是：1. 預估性能；2. 可解釋性。預估性能：FM的預估時間複雜度是 $O(nk)$ ，目前可以通過SIMD指令基本做到了近似 $O(n)$ ，這裡要感謝Intel的SSE、AVX和AVX2，以AVX2為例，一次可以操作256bit位寬，意味著在向量用float類型分解，k小於等於8時就是嚴格 $O(n)$ 的，實際上k會大一些，比如64、128，這個時候一般會用到float的q2.13編碼和AVX2的循環展開與流水拼接技術，盡量降低 $O(n)$ 前面的常數因子（做得好的話，常數因子是完全可以降到1的）。2.可解釋性：由於FM增加了二階kernel，不是線性的，直觀意義上的可解釋性肯定是不如LR的，但這個問題並非無解，跟某司交流，他們從理論到實踐，完整解決了二階kernel以內的非線性模型可解釋問題，由於沒有得到授權，就不在這裡展開講了，一種簡單粗暴的方案是將預估特徵逐個的一階、二階項置為0，衡量預估變化程度來做解釋性（特徵是非IID分布時會有判斷誤差）。

談到FM，那麼繞不開的話題肯定包含FFM。FFM風頭始於台大打KDD Cup和Kaggle，一時風頭無倆。FM可以通過簡單的數學變化將複雜度做到 $O(nk)$ ，FFM由於field劃分，就沒有類似的變換了，看似FFM的標準複雜度只能硬抗 $O(n^2k)$ （儘管FFM的k會小一些）。實際上，這個問題也是有解的。一種比較好的策略是將FFM的向量做類似caffe裡邊的img2col展開，然後在做向量乘法，那麼就完全跟FM相同了。可能會說，FFM做img2col展開是 $O(n^2)$ ，這裡還是要再次感謝SIMD指令，以Intel的三種SIMD指令來說，它提供shuffle指令，一次計算好Mask，就可在後續的計算中以 $O(n)$ 複雜度做類似img2col變化啦。所以，FFM在內存上做出一些犧牲，是可以在性能上做到和FM相接近的時間複雜度的；工程做好了，前面的常數可以更小，畢竟k更小嘛。

SIMD指令還有非常多的應用，比如存儲領域的糾刪碼實現，SIMD也是實力擔綱，有機會再展開講。

好的演算法模型的應用，離不開良好的工程實現。演算法研究人員平時多思考工程上的改進，也是一項不錯的休閑娛樂活動。

在最近主流的比賽中和實際廣告系統的經驗，factorization machine的效果完勝lr，另外fm線上計算ecpm的開銷其實相對lr來說並大不了多少：）

目前主流還是lr，主要是fm的優化演算法的並行化並未像lr一樣成為顯學，但未來2，3年後，類fm的一些非線性模型一定會逐步取代lr。

自己的一點理解，可能並不準確，歡迎大家指正。

參考資料：

[1] 關於點擊率模型，你知道這三點就夠了

[2] 點擊率預估的幾個經典模型簡介

[3] 深入FFM原理與實踐 -

[4] 海量數據下的非線性模型探索

[5] Coupled Group Lasso for Web-Scale CTR Prediction in Display Advertising

[6] Simple and scalable response prediction for display advertising

[7] LASER: A Scalable Response Prediction Platform For Online Advertising

[8] Computational Advertising: The LinkedIn Way

[9] Field-aware Factorization Machines for CTR Prediction

[10] Factorization Machines

[11] Factorization Machines with libFM

[12] Netflix winner solution PPT

FM 的問題在於參數比較難以調節，因為參數空間大很多。

其次就是FM的優化問題是非凸的，如果參數調的不好，很可能比LR效果差很多。當然如果精細調好了，是會比LR強。

其實長遠來看，機器學習裡面效果只是一方面，投入的人力和機器時間也是個很大的成本，如果一定要拋棄LR，我會建議直接上GBDT更好一些。

FM從理論和實驗上都完爆LR，FM沒有流行應該是工程上的問題，線上預測性能，上面有人也說了FM比LR性能損失不了多少。

FM適合高度稀疏特徵之間的組合，比如各種上萬維id之間的組合；人工特徵組合適合不那麼稀疏的特徵組合，並且這些組合模式在樣本中都能找到且不少，例如性別和類目ID間的組合，但是如果和adid這種維度的特徵之間的特徵組合，LR模型是學不出來的，樹模型也學不出來，因為組合太多，絕大多數組合模式數據中是不存在的，FM非常學習擅長這種組合。實際上，也有工作用DNN去做這種事情，可以看google widedeep模型。

我寫了一個深入理解FM的文章因子機深入解析，裡面有詳細解釋！

這其實是模型能力、模型複雜度、先驗知識的權衡。

在線廣告的特徵維度太高了，正樣本通常不足以支撐複雜度太高的模型。而且很多特徵都對應著業務上的解釋，有時人工對組合特徵的構建，比交給模型更有效

logistic regression 1.解釋性好 1簡單可靠,容易擴展,大量的feature engineering可以分工合作.

FM用factor來描述特徵間的關係，我覺得其實跟大規模LR中的交叉組合特徵類似，而且當loss使用logistic loss可以退化為logistic regression

所以我覺得在高維lr中，FM優勢可能並不明顯，反而增加了複雜度,(越簡單越容易擴展越容易流行)

為啥FM交互矩陣是正定的？

廣告系統中的lr特徵維數太高了，人工組合交叉的特徵應該解釋性更好吧