本人才疏學淺，不足之處歡迎大家指出和交流。
今天繼續帶來傳統模型之MLR算法模型，這是一篇來自阿裡蓋坤團隊的方案（LS-PLM），發表于2017年，但實際在2012年就已經提出并應用于實際業務中，當時主流仍然是我們上一篇提到過的的LR模型，而本文作者創新性地提出了MLR(mixed logistic regression, 混合邏輯斯特回歸)算法，引領了廣告領域CTR預估算法的全新更新。總的來說，MLR算法創新地提出并實作了直接在原始空間學習特征之間的非線性關系，基于資料自動發掘可推廣的模式，相比于人工來說效率和精度均有了大幅提升。下面我們一起來了解下細節。
原文：《Learning Piece-wise Linear Models from Large Scale Data for Ad Click Prediction》
1、背景
CTR預估(click-through-rate prediction)是廣告行業比較常見的問題，根據使用者的曆史行為來判斷使用者對廣告點選的可能性。在常見工業場景中，該問題的輸入往往是數以萬計的稀疏特征向量，在進行特征交叉後會維數會更高，比較常見的就是采用邏輯回歸模型加一些正則化，因為邏輯回歸模型計算開銷小且容易實作并行。之前提到的facebook的一篇論文（LR+GBDT）中先用樹模型做分類之後再加一個邏輯回歸模型，最後得出效果出奇的好，應該也是工業界比較常用的方法，同時樹模型的選擇或者說是再構造特征的特性也逐漸被大家所關注。另一種比較有效的就是因子分解模型系列，包括FM及其的其他變種，它們的主要思想就是構造交叉特征或者是二階的特征來一起進行訓練。
這篇文章中，作者主要提出了一種piece-wise的線性模型，并且給出了其在大規模資料上的訓練算法，稱之為LS-PLM(Large Scale Piecewise Linear Model)，LS-PLM采用了分治的思想，先分成幾個局部再用線性模型拟合，這兩部都采用監督學習的方式，來優化總體的預測誤差，總的來說有以下優勢：
- 端到端的非線性學習： 從模型端自動挖掘資料中蘊藏的非線性模式，省去了大量的人工特征設計，這 使得MLR算法可以端到端地完成訓練，在不同場景中的遷移和應用非常輕松。通過分區來達到拟合非線性函數的效果；
- 可伸縮性（scalability）：與邏輯回歸模型相似，都可以很好的處理複雜的樣本與高維的特征，并且做到了分布式并行；
- 稀疏性: 對于線上學習系統，模型的稀疏性較為重要，是以采用了 L 1 L_{1} L1和\(L_{2,1}\)正則化，模型的學習和線上預測性能更好。當然，目标函數非凸非光滑為算法優帶來了新的挑戰。
2、MLR總覽
MLR就像它的名字一樣，由很多個LR模型組合而成。用分片線性模式來拟合高維空間的非線性模式，形式化表述如下：
目标損失函數為：
論文中一個直覺的例子，如下圖，LR不能拟合非線性資料，MLR可以拟合非線性資料，因為劃分-訓練模式。
這種菱形分界面（非線性資料）其實非常難學，但MLR在其中表現出色。通過控制分片數量m，可以平衡模型的拟合能力和過拟合。上圖m=4。論文中m=12得到了不錯的效果。
理論上來說，增大m可以帶來無限制的非線性拟合能力，但是同樣會增加計算、存儲的開銷，同時會帶來過拟合的風險。具體如何選取m要結合實際情況取舍；
同時MLR還引入了結構化先驗、分組稀疏、線性偏置、模型級聯、增量訓練、Common Feature Trick來提升模型性能。
針對MLR上面提到的各種特性，下面我們一一來介紹細節。
3、模型細節
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 模型級聯
蓋坤在PPT講解到，MLR支援與LR的級聯式訓練。有點類似于Wide & Deep，一些強Feature配置成級聯形式能夠提高模型的收斂性。例如典型的應用方法是：以統計回報類特征建構第一層模型，輸出FBctr級聯到第二級大規模稀疏ID特征中去，能得到更好的提升效果。
回報特征常用的如回報CTR，是指系統上線一段時間之後得到的曆史CTR值。
3.4 增量訓練
實驗證明，MLR利用結構先驗（使用者特征進行聚類，廣告特征進行分類）進行pretrain，然後再增量進行全空間參數尋優訓練，會使得收斂步數更少，收斂更穩定。
4、一些trick
論文的idea簡單有效的，重點是工程中出來的論文，對工程實作上的優化細節都很詳細，下面我們來看下：
4.1 并行化
論文裡的實作基于分布式，包括兩個次元的并行化，模型并行化，資料并行化。每一個計算節點中都包含兩種角色：Server Node, Worker Node，這樣做的好處有兩點：
- 最大化利用CPU計算資源。之前大多數Server Node單獨放到一台伺服器上，造成CPU資源的極大浪費。
- 最大化利用Memory資源。
4.2 Common Feature Trick
一個使用者在一次pageview中會看到多個廣告，每個廣告都組成一條樣本。是以這些樣本之間很多特征都是重複的。這些特征包括：使用者特征（年齡、性别等）、使用者的曆史通路資訊（之前購買的物品、喜歡的店鋪等）。那麼我們對于向量内積的計算分成兩部分：common和non-common parts:
利用Common Feature Trick可以從三個方面來優化并行化：
- 對于有Common Feature的樣本作為一組一起訓練，并保證在存儲在一個worker上
- 對于Common Feature僅僅儲存一次，以便來節省記憶體
- 對于Common Feature的loss和梯度更新隻需要一次即可
下面是實驗結果：
可以看到Common Feature Trick效果還是非常明顯的。
5、總結
文末說LS-PLM在2012年就應用于阿裡巴巴的ctr預估，到2017年才發表論文。不出意料，現在的模型應該已經不再是MLR這麼簡單了。
另外，從MLR和LR進行級聯，以便加強強特征來看，MLR還是有很大的局限性。個人感覺模型從理論上來說确實非常棒，利用分片線性來模型高維非線性，但是雖然取得了非常不錯的成績，但是帶來的挑戰也不小：比如初值問題、非凸問題的局部極值、雖然MLR比LR好，但不知道和全局最優相比還有多遠；第二，在初值的Pre-train方面需要改進和優化模型函數等等；第三，目前規模化能力方面也需要能夠吞吐更多特征和資料，比如采用更快的收斂算法等等；最後，整體的MLR算法的抽象能力也需進一步得到強化。
實作MLR的一個Demo，感興趣的童鞋可以看下我的[github](https://github.com/Jesse-csj/TensorFlow_Practice)。