一、技術背景
CTR(Click-Through-Rate)即點擊通過率，是指網絡廣告的點擊到達率。網絡廣告包括：文字廣告、圖片廣告、關鍵詞廣告、排名廣告、視頻廣告等。CTR預估是很多互聯網主流應用（廣告、搜索、推薦）的核心算法問題，包括Google和Facebook都一直在投入研究該領域。
二、研究現狀
傳統的CTR預估主要是使用Logistic Regression，外加人為特徵工程。LR是線性模型，它的學習能力有限，所以需要引入大量的領域知識人為進行特徵工程，構造交叉特徵來間接補充算法的非線性擬合能力。但是LR模型的優點是可以很容易的實現並行化，輕鬆的處理上億條訓練樣本不成問題。
之後，業界一直在研究新的非線性模型。有成果但是也伴隨著一些缺點，比如Kernel方法，因為複雜度太高在高維度稀疏輸入的前提下很難實現；Facebook在2014年提出了LR + GBDT的模型，Tree-Based有效的解決了LR模型的特徵組合問題，但是輸入全是id的情況下，樹模型更多的是對歷史行為的一種記憶，缺乏推廣性；FM（Factorization Machine）模型能夠自動學習高階特徵的權重，不用人工來做特徵交叉，而且解決了在高維度樣本下數據量不充分導致的問題，但是FM模型只能擬合特定的非線性模式。比如最常用的二階FM模型，只能擬合線性模式和二階非線性模式，缺乏對高階非線性模式的學習。深度神經網絡的非線性擬合能力非常強，但是面對廣告這種大規模工業級稀疏數據，適合數據規律、具備推廣性的模型結構仍然在探索中。
那麼如何從大規模工業級稀疏數據中，挖掘出一個具備推廣性的非線性模型那？
三、MLR算法
2011-2012年期間，阿里媽媽蓋坤團隊給出了答案：MLR(mixed logistic regression)，在論文中的名稱是LS-PLM(Large Scale Piece-wise Linear Model).
總的來說，MLR應用分而治之的思想，通過將特徵空間劃分成多個區域，每個區域都學習一個線性模型LR，來學習非線性模式。MLR可以基於數據自動挖掘非線性模式，把算法工程師從繁瑣的特徵工程中拯救出來，更具有推廣性。 同時MLR還引入了結構化先驗、L1 L21正則化，分組稀疏、線性偏置、模型級聯、增量訓練、Common Feature Trick來提升模型性能。
MLR就像它的名字一樣，由很多個LR模型組合而成。用分片線性模式來擬合高維空間的非線性模式，形式化表述如下：
g保證最終的預測結果是一個概率，π用來劃分區域，η用來在區域內學習LR線性模型。論文中給出的函數選取如下： g(x) = x,π(x)=softmax,η(x)=sigmoid 即：
目標函數：
MLR主要適合在大規模工業級稀疏數據，通過分片線性模型來學習高維下的非線性模式，主要優勢有兩點：
1、端到端的非線性學習：從數據中自動挖掘蘊含的非線性模式，不在需要人工特徵工程的干預。這使得MLR可以端到端的的完成訓練，在不同場景中遷移非常輕鬆。
2、稀疏性：MLR在建模時使用了L1，L2,1正則化，實現了分組稀疏，使得訓練出來的模型具有較高的稀疏度。無論是在模型的訓練還是在線預測性能更好，當然，目標函數非凸非光滑為算法優帶來了新的挑戰。
看個例子：
這種菱形分界面其實非常難學，MLR表現出色。通過控制分片數量m，可以平衡模型的擬合能力和過擬合。上圖m=4。論文中m=12得到了不錯的效果。
理論上來說，增大m可以帶來無限制的非線性擬合能力，但是同樣會增加計算、存儲的開銷，同時會帶來過擬合的風險。具體如何選取m要 針對MLR上面提到的各種特性，現一一介紹.
3.1 結構化先驗
MLR中非常重要的就是如何劃分原始特徵空間。通過引入結構化先驗，我們使用用戶特徵來劃分特徵空間，使用廣告特徵來進行基分類器的訓練，減小了模型的探索空間，收斂更容易。 同時，這也是符合我們認知的：不同的人群具有聚類特性，同一類人群具有類似的廣告點擊偏好。
3.2 線性偏置
針對CTR預估問題中存在的兩種偏置：
Position Bias：排名第1位和第5位的樣本，點擊率天然存在差異。寶貝展示的頁面、位置影響點擊率
Sample Bias：PC和Mobile上的樣本，點擊率天然存在差異。
在原來寶貝特徵X的基礎上，增加偏移向量y(場景、頁數、位置等)。如果直接學習聯合概率P(X,Y)面臨問題：學習聯合概率一定需要x和y的大部分組合，但是實際情況，並不是所有的x，y的組合都能有采樣。針對這個問題，提出了帶偏移MLR算法，形式化表述如下：
而且，大規模非線性CTR預估和偏移變量的分解一起優化。並且，只需要很少的一些x，y組合就可以了。從蓋坤給出的數據中，AUC提高了2-8個百分點。
3.3 模型級聯
雖然論文裡沒說，但是在阿里技術中有講到，MLR支持與LR的級聯式訓練。有點類似於Wide & Deep，一些強Feature配置成級聯形式能夠提高模型的收斂性。例如典型的應用方法是：以統計反饋類特徵構建第一層模型，輸出FBctr級聯到第二級大規模稀疏ID特徵中去，能得到更好的提升效果。
反饋特徵常用的如反饋CTR，是指系統上線一段時間之後得到的歷史CTR值。
3.4 增量訓練
實踐證明，MLR利用結構先驗（用戶特徵進行聚類，廣告特徵進行分類）進行pretrain，然後再增量進行全空間參數尋優訓練，會使得收斂步數更少，收斂更穩定。
3.5 L1，L2,1正則化 / 分組稀疏
L2,1公式如下：
d是特徵維度，m是劃分的區域個數。
L2,1正則化實現了分組稀疏的特性。從MLR形式化的公式中可以發現，每一個維度的特徵都對應多個參數。包括區域劃分函數的參數、分類函數的參數。針對一個特徵，L2,1首先對其所有的參數都進行L2正則化，然後每個維度的特徵都得到了一個非負數，再在特徵維度上進行L1正則化。導致的效果就是，對於不是很重要的特徵，L2,1會使得它的所有參數都為0，也就是分組稀疏。 在目標函數中，還增加了L1正則化，盡一切可能只為得到一個稀疏模型。下面是實驗結果：
可以看到L2,1的稀疏效果略差與L1.兩者結合起來得到了最稀疏的模型，並且AUC也是最高的。
四、實現技巧
4.1 並行化
論文裡的實現基於分佈式，包括兩個維度的並行化，模型並行化，數據並行化。每一個計算節點中都包含兩種角色：Server Node, Worker Node，這樣做的好處有兩點：
1、最大化利用CPU計算資源。之前大多數Server Node單獨放到一臺服務器上，造成CPU資源的極大浪費。
2、最大化利用Memory資源。
4.2 Common Feature Trick
一個用戶在一次pageview中會看到多個廣告，每個廣告都組成一條樣本。所以這些樣本之間很多特徵都是重複的。這些特徵包括：用戶特徵（年齡、性別等）、用戶的歷史訪問信息（之前購買的物品、喜歡的店鋪等）。那麼我們對於向量內積的計算分成兩部分：common和non-common parts:
利用Common Feature Trick可以從三個方面來優化並行化：
1、對於有Common Feature的樣本作為一組一起訓練，並保證在存儲在一個worker上
2、對於Common Feature僅僅保存一次，以便來節省內存
3、對於Common Feature的loss和梯度更新只需要一次即可
下面是實驗結果：
可以看到Common Feature Trick效果還是非常明顯的。
五、總結
MLR從2012年就開始在阿里內部使用，到2017年才發表論文。不出意料，現在的模型應該已經不再是MLR這麼簡單了。另外，從MLR和LR進行級聯，以便加強強特徵來看，MLR還是有很大的侷限性。個人感覺模型理論上來說確實非常棒，利用分片線性來模型高維非線性，但是分片函數的選擇以及全局最優解的尋優都帶來了非常大的挑戰。
總結起來，MLP主要特性原理如下：
1、LS-PLM或者是MLR針對大規模工業級稀疏數據，採用分而治之的思想，在多個區域學習線性分類器，來在高維特徵空間中學習非線性模型；
2、應用L1和L2,1正則化實現了分組稀疏，得到了稀疏模型； Common Feature Trick極大的降低了內存開銷，縮短了訓練時間；
3、另外一些高級特性：結構化先驗、線性偏置、模型級聯、增量訓練；
Reference
1、Learning Piece-wise Linear Models from Large Scale Data for Ad Click Prediction
2、蓋坤講MLR視頻 https://v.youku.com/v_show/id_XNjA1MDEyNDU2.html
3、阿里技術 https://mp.weixin.qq.com/s/MtnHYmPVoDAid9SNHnlzUw?scene=25#
4、wechat_redirect 《海量數據下的非線性模型探索》
說個小花邊，阿里內部最開始的CTR不能算機器學習模型，就是一個純的規則： ad_ctr, cate_ctr, ad_pv為特徵，預測下一天ad的ctr：
一共用了三個特徵 + 一個if-else使用了很多年。聽說是打敗了很多機器學習工程師設計的LR模型
閱讀更多 機器學習與數據挖掘 的文章
