各大公司广泛使用的在线学习算法FTRL详解
現(xiàn)在做在線學習和CTR常常會用到邏輯回歸（?Logistic Regression），而傳統(tǒng)的批量（batch）算法無法有效地處理超大規(guī)模的數(shù)據(jù)集和在線數(shù)據(jù)流，google先后三年時間（2010年-2013年）從理論研究到實際工程化實現(xiàn)的FTRL（Follow-the-regularized-Leader）算法，在處理諸如邏輯回歸之類的帶非光滑正則化項（例如1范數(shù)，做模型復(fù)雜度控制和稀疏化）的凸優(yōu)化問題上性能非常出色，據(jù)聞國內(nèi)各大互聯(lián)網(wǎng)公司都第一時間應(yīng)用到了實際產(chǎn)品中，我們的系統(tǒng)也使用了該算法。這里對FTRL相關(guān)發(fā)展背景和工程實現(xiàn)的一些指導(dǎo)點做一些介紹，凸優(yōu)化的理論細節(jié)不做詳細介紹，感興趣可以去查閱相應(yīng)paper，相關(guān)paper列表會在文后附上。機器學習并非本人在校時的專業(yè)方向，不過在校期間積累的基礎(chǔ)不算太差，而且很多東西也是相通的，鉆研一下基本意思都還能搞明白。當然，有不準確的地方歡迎大家討論指正。
? ??? 本文主要會分三個部分介紹，如果對理論產(chǎn)生背景不感興趣的話，可以直接看第3部分的工程實現(xiàn)（這一部分google13年那篇工程化的paper介紹得很詳細）：
一、相關(guān)背景
??【問題描述】
? ? ?對于loss函數(shù)+正則化的結(jié)構(gòu)風險最小化的優(yōu)化問題（邏輯回歸也是這種形式）有兩種等價的描述形式，以1范數(shù)為例，分別是：
? a、無約束優(yōu)化形式的soft regularization formulation：
? ? ? b、帶約束項的凸優(yōu)化問題convex constraint formulation：
? ? ? ?當合理地選擇g時，二者是等價的。這里提這兩種形式的問題描述，原因在于引出下面無約束優(yōu)化和帶約束優(yōu)化問題的不同算法，對于不同的描述形式，會有一系列相關(guān)算法。
? ?【批量（batch）算法】
? ? ? 批量算法中每次迭代對全體訓練數(shù)據(jù)集進行計算（例如計算全局梯度），優(yōu)點是精度和收斂還可以，缺點是無法有效處理大數(shù)據(jù)集（此時全局梯度計算代價太大），且沒法應(yīng)用于數(shù)據(jù)流做在線學習。這里分無約束優(yōu)化形式和約束優(yōu)化（與上面問題描述可以對應(yīng)起來）兩方面簡單介紹一下一些傳統(tǒng)批量算法。
? ? ? a、無約束優(yōu)化形式：1、全局梯度下降，很常用的算法，就不細說了，每一步求一個目標函數(shù)的全局梯度，用非增學習率進行迭代；2、牛頓法（切線近似）、LBFGS（割線擬牛頓，用之前迭代結(jié)果近似Hessian黑塞矩陣的逆矩陣，BFGS似乎是幾個人名的首字母的簡稱）等方法。牛頓和擬牛頓等方法一般對于光滑的正則約束項（例如2范數(shù)）效果很好，據(jù)說是求解2范數(shù)約束的邏輯回歸類問題最好的方法，應(yīng)用也比較廣，但是當目標函數(shù)帶L1非光滑、帶不可微點的約束項后，牛頓類方法比較無力，理論上需要做修改。感興趣的可以去查查無約束優(yōu)化的相關(guān)數(shù)值計算的書，我也沒有更深入研究相關(guān)細節(jié)，這里不做重點關(guān)注。
? ? ? b、不等式約束凸優(yōu)化形式：1、傳統(tǒng)的不等式約束優(yōu)化算法內(nèi)點法等；2、投影梯度下降（約束優(yōu)化表示下），gt是subgradient，直觀含義是每步迭代后，迭代結(jié)果可能位于約束集合之外，然后取該迭代結(jié)果在約束凸集合上的投影作為新的迭代結(jié)果（第二個公式中那個符號標識向X的投影）：
?
【在線算法】
如上所述，批量算法有自身的局限性，而在線學習算法的特點是：每來一個訓練樣本，就用該樣本產(chǎn)生的loss和梯度對模型迭代一次，一個一個數(shù)據(jù)地進行訓練，因此可以處理大數(shù)據(jù)量訓練和在線訓練。常用的有在線梯度下降（OGD）和隨機梯度下降（SGD）等，本質(zhì)思想是對上面【問題描述】中的未加和的單個數(shù)據(jù)的loss函數(shù) L（w，zi)做梯度下降，因為每一步的方向并不是全局最優(yōu)的，所以整體呈現(xiàn)出來的會是一個看似隨機的下降路線。典型迭代公式如下：
這里使用混合正則化項：，例如可能是1范數(shù)與2范數(shù)強凸項的混合（后面會看到其實很多都是這種混合正則化的格式，而且是有一定直觀含義的）。迭代公式中：gt是loss函數(shù)（單點的loss，未加和）的subgradient，與gt相加的那一項是混合正則化項中的第二項的梯度，投影集合C是約束空間（例如可能是1范數(shù)的約束空間），跟上面介紹的投影梯度下降類似的做法。
梯度下降類的方法的優(yōu)點是精度確實不錯，但是不足相關(guān)paper主要提到兩點：
1、簡單的在線梯度下降很難產(chǎn)生真正稀疏的解，稀疏性在機器學習中是很看重的事情，尤其我們做工程應(yīng)用，稀疏的特征會大大減少predict時的內(nèi)存和復(fù)雜度。這一點其實很容易理解，說白了，即便加入L1范數(shù)（L1范數(shù)能引入稀疏解的簡單示例可以產(chǎn)看PRML那本書的第二章，我前面一篇blog的ppt里也大概提了），因為是浮點運算，訓練出的w向量也很難出現(xiàn)絕對的零。到這里，大家可能會想說，那還不容易，當計算出的w對應(yīng)維度的值很小時，我們就強制置為零不就稀疏了么。對的，其實不少人就是這么做的，后面的Truncated Gradient和FOBOS都是類似思想的應(yīng)用；
2、對于不可微點的迭代會存在一些問題，具體有什么問題，有一篇paper是這么說的：the iterates of the subgradient method are very rarely at the points of non-differentiability。我前后看了半天也沒看明白，有熟悉的同學可以指導(dǎo)一下。
?
二、Truncated Gradient、FOBOS以及RDA（Regularized Dual Averaging）
上面提到了，稀疏性在機器學習中是很重要的一件事情，下面給出常見的三種做稀疏解的途徑：
1）、簡單加入L1范數(shù)
–局限如上面所提，a+b兩個float數(shù)很難絕對等于零，無法產(chǎn)生真正稀疏的特征權(quán)重
2）、在1范數(shù)的基礎(chǔ)上做截斷，最直觀沒技術(shù)含量的思路，那就設(shè)定一個閾值，做截斷來保證稀疏，可以結(jié)合L1范數(shù)
–簡單截斷方法，每online訓練K個數(shù)據(jù)截斷一次，對OGD的迭代結(jié)果，每K步做一次截斷置零：
但是簡單截斷方法有問題：權(quán)重小，可能是確實是無用特征，還或者可能是該特征才剛被更新一次（例如訓練剛開始的階段、或者訓練數(shù)據(jù)中包含該特征的樣本數(shù)本來就很少），另外，簡單rounding技術(shù)太aggressive了，可能會破壞在線訓練算法的理論完備性。
-簡單截斷基礎(chǔ)上，不太aggressive的Truncated gradient （09年的工作），其實后面的FOBOS也可以歸為這一類：
3）、Black-box wrapper approaches：
–黑盒的方法去除一些特征，然后重新訓練的看被消去的特征是否有效。
–需要在數(shù)據(jù)集上對算法跑多次，所以不太實用
? ? ? 下面會提一下FOBOS（Forward-Backward Splitting method?，其實應(yīng)該叫FOBAS的，歷史原因）以及RDA，因為后面的FTRL其實相當于綜合了這兩種算法的優(yōu)點：
a、FOBOS，google和伯克利09年的工作：
–可以看作truncated gradient的一種特殊形式
–基本思想：跟projected subgradient方法類似，不過將每一個數(shù)據(jù)的迭代過程，分解成一個經(jīng)驗損失梯度下降迭代和一個最優(yōu)化問題。分解出的第二個最優(yōu)化問題，有兩項：第一項2范數(shù)那一項表示不能離第一步loss損失迭代結(jié)果太遠，第二項是正則化項，用來限定模型復(fù)雜度抑制過擬合和做稀疏化等。這個最優(yōu)化問題有一些特殊的性質(zhì)，從而保證了最終結(jié)果的稀疏性和理論上的完備，具體細節(jié)感興趣的可以查看對應(yīng)paper。我這里更多關(guān)注直觀含義和工程實現(xiàn)，忽略理論方面的內(nèi)容。
b、RDA（Regularized dual averaging），微軟10年的工作，更加理論性一些，這里就直接略過去了，僅對其特點做一個簡單介紹：
–非梯度下降類方法，屬于更加通用的一個primal-dual algorithmic schema的一個應(yīng)用
–克服了SGD類方法所欠缺的exploiting problem structure，especially for problems with explicit regularization。
–能夠更好地在精度和稀疏性之間做trade-off
ok，背景和一些鋪墊終于完成了，下面重點進入FTRL的部分。。。
?
三、FTRL (Follow-the-regularized-Leader)
【發(fā)展歷程】
FTRL的理論推進和工程應(yīng)用首先要感謝這個人：H. Brendan McMahan, google這哥們兒護了三年的坑，直到13年工程性paper出來。發(fā)展歷程和基本說明如下：
?–10年理論性paper，但未顯式地支持正則化項迭代；11年證明regret bound以及引入通用的正則化項；11年另一篇的paper揭示OGD、FOBOS、RDA等算法與FTRL關(guān)系；13年的paper給出了工程性實現(xiàn)，并且附帶了詳細的偽代碼，開始被大規(guī)模應(yīng)用。
?–可以看作RDA和FOBOS的混合，但在L1范數(shù)或者其他非光滑的正則項下，FTRL比前兩者更加有效
?
【基本思想及迭代公式】
我簡單畫了個圖：
與其他在線算法的迭代公式的對比（其實OGD如何一步步到類似形式的迭代公式的過程，限于時間，這里就不細說了，最后我會附一篇自己做分享會時做的ppt，里面有，感興趣的可以下載看看），不同的方法在這種統(tǒng)一的描述形式下，區(qū)別點僅在第二項和第三項的處理方式：
–第一項：梯度或累積梯度；
–第二項：L1正則化項的處理；
–第三項：這個累積加和限定了新的迭代結(jié)果x不要離已迭代過的解太遠（也即FTRL-Proximal中proximal的含義），或者離0太遠（central），這一項其實也是low regret的需求
?
【工程實現(xiàn)】
大家對上面那一大坨前因后果和公式都不感興趣，ok，沒關(guān)系，google非常貼心地在13年給出了一篇工程性很強的paper，其實大部分公司使用FTRL的，根本不會關(guān)心上面那一大段東西，直接按著偽代碼寫，調(diào)調(diào)參，看結(jié)果很不錯就可以了。我們公司開始就是這么搞的，哈哈，不過人總是要有點兒好奇心的不是，深究一下前因后果和基本的理論公式感覺還是挺不同的。
邏輯回歸下的per-coordinate FTRL_Proximal的偽代碼如下，在公式表達的基礎(chǔ)上做了一些變換和實現(xiàn)上的trick，細節(jié)paper里有，大家在自己做實現(xiàn)的時候，可以在實際數(shù)據(jù)集上再并行加加速：
四個參數(shù)的設(shè)定結(jié)合paper里的指導(dǎo)意見以及反復(fù)實驗測試，找一組適合自己問題的參數(shù)就可以了。這里我想提一點，即上面所謂的per-coordinate，其意思是FTRL是對w每一維分開訓練更新的，每一維使用的是不同的學習速率，也是上面代碼中l(wèi)amda2之前的那一項。與w所有特征維度使用統(tǒng)一的學習速率相比，這種方法考慮了訓練樣本本身在不同特征上分布的不均勻性，如果包含w某一個維度特征的訓練樣本很少，每一個樣本都很珍貴，那么該特征維度對應(yīng)的訓練速率可以獨自保持比較大的值，每來一個包含該特征的樣本，就可以在該樣本的梯度上前進一大步，而不需要與其他特征維度的前進步調(diào)強行保持一致。
?
【工程實現(xiàn)中的memory saving策略】
這里對google所提的一些節(jié)省內(nèi)存的實現(xiàn)細節(jié)做一個介紹
- Predict時的memory saving：
–L1范數(shù)加策略，訓練結(jié)果w很稀疏，在用w做predict的時候節(jié)省了內(nèi)存，很直觀，不細說了
- Training時的memory saving：
1）Poisson Inclusion：對某一維度特征所來的訓練樣本，以p的概率接受并更新模型；
2）Bloom Filter Inclusion：用bloom filter從概率上做某一特征出現(xiàn)k次才更新
2.?浮點數(shù)重新編碼
1）特征權(quán)重不需要用32bit或64bit的浮點數(shù)存儲，存儲浪費空間
2）16bit encoding，但是要注意處理rounding技術(shù)對regret帶來的影響
3.?訓練若干相似model
1）對同一份訓練數(shù)據(jù)序列，同時訓練多個相似的model
2）這些model有各自獨享的一些feature，也有一些共享的feature
3）出發(fā)點：有的特征維度可以是各個模型獨享的，而有的各個模型共享的特征，可以用同樣的數(shù)據(jù)訓練。
4.?Single Value Structure（據(jù)說有公司已經(jīng)在實際中這么搞，大數(shù)據(jù)量下也能夠保證不錯的auc）
? 1）多個model公用一個feature存儲（例如放到cbase或redis中），各個model都更新這個共有的feature結(jié)構(gòu)
? 2）對于某一個model，對于他所訓練的特征向量的某一維，直接計算一個迭代結(jié)果并與舊值做一個平均
5. ?使用正負樣本的數(shù)目來計算梯度的和（所有的model具有同樣的N和P）
6.?Subsampling Training Data
1）在實際中，CTR遠小于50%，所以正樣本更加有價值。通過對訓練數(shù)據(jù)集進行subsampling，可以大大減小訓練數(shù)據(jù)集的大小
2）正樣本全部采（至少有一個廣告被點擊的query數(shù)據(jù)），負樣本使用一個比例r采樣（完全沒有廣告被點擊的query數(shù)據(jù)）。但是直接在這種采樣上進行訓練，會導(dǎo)致比較大的biased prediction
3）解決辦法：訓練的時候，對樣本再乘一個權(quán)重。權(quán)重直接乘到loss上面，從而梯度也會乘以這個權(quán)重。
先采樣減少負樣本數(shù)目，在訓練的時候再用權(quán)重彌補負樣本，非常不錯的想法。
?
【References】
我大概標注了一下各篇paper的主要內(nèi)容，感興趣的可以有選擇性地看一下，如果只關(guān)注工程實現(xiàn)，看標紅的那篇就ok了：
[1] J. Langford, L. Li, and T. Zhang. Sparse online learning via truncated gradient.JMLR, 10, 2009. （截斷梯度的paper）
[2] H. B. McMahan. Follow-the-regularized-leader and mirror descent: Equivalence theorems and L1 regularization. In AISTATS, 2011 （FOBOS、RDA、FTRL等各種方法對比的paper）
[3] L. Xiao. Dual averaging method for regularized stochastic learning and online optimization. In NIPS, 2009 （RDA方法）
[4] J. Duchi and Y. Singer. Efficient learning using forward-backward splitting. In Advances in Neural Information Processing Systems 22, pages 495{503. 2009. （FOBOS方法）
[5] H. Brendan McMahan, Gary Holt, D. Sculley, Michael Young,?Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov,?Daniel Golovin, Sharat Chikkerur, Dan Liu, Martin Wattenberg,?Arnar Mar Hrafnkelsson, Tom Boulos, Jeremy Kubica, Ad Click Prediction: a View from the Trenches, Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)?(2013)（這篇是那篇工程性的paper）
[6] H. Brendan McMahan. A unied analysis of regular-ized dual averaging and composite mirror descent with implicit updates. Submitted, 2011 （FTRL理論發(fā)展，regret bound和加入通用正則化項）
[7] H. Brendan McMahan and Matthew Streeter. Adap-tive bound optimization for online convex optimiza-tion. InCOLT, 2010 （開始的那篇理論性paper）
?
轉(zhuǎn)載請注明本文鏈接：http://www.cnblogs.com/EE-NovRain/p/3810737.html
后面附上我在組里分享時做的ppt，感興趣的可以看看：http://pan.baidu.com/s/1eQvfo6e
總結(jié)
以上是生活随笔為你收集整理的各大公司广泛使用的在线学习算法FTRL详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 在线机器学习FTRL(Follow-th
- 下一篇： Spark性能相关参数配置详解