CTR預估演算法（2） | MLR
一、動機
點擊率預估需要解決的超高維度離散特徵空間模式識別的問題，它需要演算法在做到可以有效發現當前數據規律的同時，還要具有足夠的泛化能力去應對線上多變的user-context-content模式，所以到目前為止有許多的CTR模型被應用於實際場景中，諸如LR、DNN、Tree Model、FM/FFM，這些模型都有各自的優勢，但也存在缺陷，主要如下：
阿里媽媽在2011年提出了MLR模型，全稱Large Scale Piecewise Linear Model (LS-PLM)，大規模分片線性模型，背後的思想就是根據領域知識先驗將整個空間劃分為多個區域，每個區域由一個特定的線性模型來擬合，區域之間平滑連接，當區域達到一定的數量，即可擬合任意複雜的非線性模式。MLR可以看做是LR模型的推廣，從線性過渡到非線性，同時省去了大量的人工特徵工程，可以端到端訓練。
二、模型
上面講到MLR通過先驗領域知識劃分空間為局部區域，然後每個區域擬合線性模型，可使用如下判別公式來刻畫：
其中σ代表領域先驗，決定空間劃分（dividing function），η代表每個局部區域的分類預測模型（fitting function），函數g保證模型輸出符合概率定義。
在實際中，使用softmax函數作為dividing function，使用sigmoid函數作為fitting function，以及規定 ，則判別函數可改寫為如下：
由（2）可知，該模型包含 個參數，論文中使用了
正則和
正則，其中
對參數行範數約束結構化稀疏，壓縮
個參數逼近零值，
則進一步產生稀疏性，使得模型兼具可解釋性和泛化能力。目標函數如下：
但是，引入 和
正則項之後，得到了非凸非平滑的目標函數，因為不是處處可導，所以沒法用傳統的梯度下降演算法或者EM演算法來優化，但又因為運算的效率與存儲對在線預測來說很關鍵，模型稀疏性就必須要納入，所以文章論文針對這個問題提出一個大規模非凸問題的優化求解方法，即利用LBFGS演算法框架來根據方嚮導數找到最快下降方向進行參數更新，此外團隊實現了一個大規模分散式系統來支持模型的高效並行訓練，以下會一一介紹。
三、優化
3.1 方嚮導數
上面說到，目標函數非凸非光滑，無法使用導數，作者退而使用方嚮導數，顧名思義，方嚮導數就是某個方向上的導數，而且在每一個方向上都是有導數的，梯度與方嚮導數的關係就是在梯度方向上的方嚮導數最大。如下圖所示，紫色箭頭表示某一方向，在這個方向上的函數的方嚮導數如黑色實線所示，
對於一個存在梯度的函數 
作者在附錄A證明瞭在方向 上的方嚮導數
是一定存在的，附錄B求出了目標函數(4)的方嚮導數，我們依次看一下：
證明與求解
首先證明（4）式方嚮導數一定存在：
首先 可以展開為三部分，分別是損失函數、
罰函數、
罰函數在Θ處的偏導。
對於第一部分，可以直接求導：
第二部分 在
時，其偏導存在
而當 時，則意味著參數矩陣的行參數
，其方嚮導數為：
將以上兩種情況整合到一起：
類似地，對於 罰函數，其導數可以表示為：
至此，我們證明瞭三個部分對於任意的 和方向
，
一定存在。
然後求解方嚮導數：
將問題轉化為不等式約束優化問題:
採用拉格朗日乘數法求解，其中 
求函數 對d的偏導，令為零，可分為三種情況,過程略，最終求解得到如下：
其中：
至此我們得到了方嚮導數，接下里的問題就是如何利用方嚮導數來更新參數，文中使用LBFGS框架，並採取了類似於OWLQN演算法的做法，接下來介紹一下論文是如何優化的。
3.2 LBFGS
大多數的數值優化演算法都是迭代式的，優化的目的就是希望參數序列收斂，從而使 最優化。在牛頓法中使用二階泰勒展開來近似目標函數：
?令 表示
在
處的梯度，
表示目標函數
在
處的Hessian矩陣，簡化
求導令其為零，得到的 都是他的局部極值點，若
是凸函數，則
為正定矩陣，則此時局部最優即為全局最優。
得到如下更新式：
其中步長 可採用line search的方法，比如backtracking line search方法，即選用逐漸遞減的步長。
其迭代演算法偽代碼如下：
但實踐中，模型參數都是超高維度的，根本無法計算Hessian矩陣及其逆，BFGS就是為瞭解決這個問題，他使用了一種QuasiUpdate的策略生成 的近似，偽代碼如下：
其中 與
保存的是輸入和梯度的變化量，即
，
,初值
選取任意對稱的正定矩陣。
具體的QuasiUpdate那一步的推導略複雜，略過，最終BFGS的迭代偽代碼如下：
其中 只要給定方向 ，該演算法可以直接計算出
，卻不需要求出
。
LBFGS是對BFGS的改進，因為BFGS擬牛頓雖然無需計算海森矩陣，但仍然需要保存每次迭代的 與
的歷史值。內存負擔依然很重，L-BFGS是limited BFGS的縮寫，簡單地只使用最近的m個
與
記錄值，以此來近似計算
在BFGS的迭代過程中，需要使用梯度信息，但因為我們的目標函數有 正則和
正則項，不是處處可導的，這時候OWLQN就上場了
3.3 OWLQN
OWLQN演算法在LBFGS框架下針對非凸非平滑函數優化主要做出了兩點改進：
1、在不可導處用次梯度取代梯度
當模型參數不為零時，此時可導，按一般方法計算即可；當模型參數為零時，此時不可導，正則項的左偏導數為 ，右偏導數
。
如何確定在零的位置的時候用左導數還是右導數呢？做法是防止象限穿越，通俗的講就是在負象限的時候減去正值，在正象限的時候減去負值（加上正值）
2、在line search的時候做象限約束
當參數不在零點時，line search保持在參數所在象限內搜索；當參數在零點時，參數在次梯度約束的象限內進行line search
以下公式可以描述以上兩點改進
3.4 MLR的優化演算法
MLR中使用的優化演算法是從OWLQN改進過來的，主要有三個地方的變化：
- MLR使用方嚮導數來優化目標函數，而不是OWLQN的次梯度
- MLR對更新方向p進行了象限約束：非正定時直接用方嚮導數作為搜索方向，否則要進行象限約束在方嚮導數所在象限內。
- 線性搜索的象限約束不同，當MLR參數不在零點時，line search保持在參數所在象限內搜索，在零點時，參數在方嚮導數約束的象限內進行line search
給定更新方向，MLR使用了 backtracking line search方法找到合適的步長α，其迭代更新公式如下：
MLR最終的優化演算法偽代碼如下：
四、分散式
待更新
4.1 參數伺服器
4.2 Common Feature Trick
五、高級特性
在阿里媽媽團隊寫的MLR分享文章裡面，提及了以下幾點MLR的高級特性：
1、領域知識先驗，這個分別體現在上文說到的dividing function和fitting function，他是基於領域的先驗知識來設定dividing function和fitting function，比方說以用戶的特徵設計分片函數，以廣告的特徵設計擬合函數，這是基於不同人羣具有聚類特性，同一類人羣對廣告有類似的偏好這樣一個前提，此外這樣的結構先驗也有助於縮小解空間，更容易收斂
2、加入線性偏置，因為特徵的差異導致點擊率天然存在一些差異，比如說位置和資源位，所以在損失函數中加入如公式所示的線性偏置，實踐中對位置bias信息的建模，獲得了4%的RPM提升效果。
3、模型級聯，與LR模型級聯式聯合訓練，實踐中發現一些強feature配置成級聯模式有助於提高模型的收斂性，比如以統計反饋類特徵構建第一層模型，它的輸出(如下圖中的FBCtr)級聯到第二級大規模稀疏ID特徵體系中去，這樣能夠有助於獲得更好的提升效果。
4、增量訓練。實踐證明，MLR通過結構先驗進行pretrain，然後再增量進行全空間參數尋優訓練，會獲得進一步的效果提升。同時增量訓練模式下模型達到收斂的步數更小，收斂更為穩定。在我們的實際應用中，增量訓練帶來的RPM增益達到了3%。
六、業務現狀
阿里媽媽團隊主要將MLR主要應用於定向廣告的CTR預估和定向廣告的Learning to Match：
對於定向廣告CTR，他們將用戶畫像特徵、用戶歷史行為特徵、廣告畫像特徵組成2億為的embedding向量，直接放到MLR模型中訓練，並且採用了線性偏置、領域知識先驗、增量訓練的高級特徵，提升了CTR預估的精度。
Learning to Match，即基於用戶的人口屬性、歷史行為等信息來猜測用戶可能感興趣的廣告集合，一般會使用規則匹配和協同過濾來做召回模塊，阿里媽媽研發了基於MLR的learning to match演算法框架，首先基於用戶的行為歷史來學慣用戶個性化興趣，召回候選集，MLR框架很容易融合將不同的特徵源、標籤體系，省去交叉組合的成本，靈活性很高。
參考資料
A Stochastic Quasi-Newton Method for Online Convex Optimization
Learning Piece-wise Linear Models from Large Scale Data for Ad Click Prediction
重磅！阿里媽媽首次公開自研CTR預估核心演算法MLR
如何直觀形象的理解方嚮導數與梯度以及它們之間的關係？
推薦閱讀：
