在線最優(yōu)化求解(OnlineOptimization)-馮揚(yáng)

1、在線最優(yōu)化求解(Online Optimization)馮揚(yáng)(fengyoung)新浪微博商業(yè)平臺(tái)及產(chǎn)品部推薦引擎2014-12-09摘要：最優(yōu)化求解問(wèn)題可能是我們?cè)诠ぷ髦杏龅降挠蚨嗟囊活悊?wèn)題了：從己右的數(shù)據(jù)中提煉 出最適介的模型參數(shù)，從而對(duì)未知的數(shù)據(jù)進(jìn)行預(yù)測(cè).為我們而對(duì)高維高數(shù)據(jù)量的場(chǎng)景時(shí)，常 見(jiàn)的批最處理的方式己經(jīng)顯得力不從心，需要有在線處理的方法來(lái)解決此類問(wèn)題。本文以模 型的稀疏性作為主線，逐一介紹兒個(gè)在線最優(yōu)化求解算法，并進(jìn)行推導(dǎo)，力求講晴楚算法的 來(lái)龍去脈，以及不同算法之間的區(qū)別和聯(lián)系，達(dá)到融會(huì)貫通。在各個(gè)算法原理介紹之后，都 會(huì)給出該算法的工程實(shí)現(xiàn)偽代碼，可以用于實(shí)際工作的參考。1

2、動(dòng)機(jī)與目的在實(shí)際工作中，無(wú)論是工程師、項(xiàng)目經(jīng)理、產(chǎn)品同學(xué)都會(huì)經(jīng)常討論一類話題：“從線上 對(duì)比的效果來(lái)看，某某特征或?qū)貙?duì)xx產(chǎn)品的最終效果右很人的影響”。這類話題本質(zhì)上說(shuō) 的是通過(guò)己有的數(shù)搖反映出某些特定的因素對(duì)結(jié)果有很強(qiáng)的正(或負(fù))相關(guān)性。而如何定量 計(jì)算這種相關(guān)性？如何得到一套模型參數(shù)能夠使得效果達(dá)到最優(yōu)？這就是最優(yōu)化計(jì)算要做 的事情。舉一類典型點(diǎn)的例子：在推薦和廣告計(jì)算中，我們經(jīng)常會(huì)需要對(duì)某些值進(jìn)行預(yù)測(cè)，例如 在一條推薦或廣告在曝光之前先預(yù)測(cè)用戶是否會(huì)產(chǎn)生點(diǎn)擊(CTR預(yù)估)，或者是否會(huì)tl此產(chǎn) 生某些轉(zhuǎn)換(RPM預(yù)估)。這類問(wèn)題可以表示為：針對(duì)一個(gè)輸入x = xllX2 .XN e 通

3、過(guò)某個(gè)函數(shù)h(X)計(jì)算(預(yù)測(cè))輸出y 。根據(jù)y值為連續(xù)的還是離散的，預(yù)測(cè)問(wèn)題被劃分 成回歸問(wèn)題(Regression)和分類問(wèn)題(Classification)o而利用己仃的樣本數(shù)據(jù)(再,”)|)= 1,2,M訓(xùn)練h(X)的過(guò)程往往轉(zhuǎn)換成一個(gè)最優(yōu)化求解的過(guò)程。無(wú)論是線性回歸(Linear Regression)、邏輯回歸(Logistic Regression )x支持向；就機(jī)(SVM)、 深度學(xué)習(xí)(Deep Learning)中，最優(yōu)化求解都是基本的步驟。常見(jiàn)的梯度下降、牛頓法、擬 牛頓法等屬丁批量處理的方法(Batch),每次更新都需要對(duì)己經(jīng)訓(xùn)練過(guò)的樣本重新訓(xùn)練一遍。 而為我們面對(duì)高維高數(shù)

4、據(jù)量的時(shí)候，批量處理的方式就顯得笨重和不夠高效，因此需要有在 線處理的方法(Online)來(lái)解決相同的問(wèn)題。關(guān)于在線最優(yōu)化問(wèn)題(Online Optimization)的 論文比較多，逐一查找閱讀費(fèi)時(shí)費(fèi)力，那么本文就以高維高數(shù)據(jù)量的應(yīng)用場(chǎng)景中比較看重的 稀疏性作為主線，來(lái)介紹一些在線最優(yōu)化的方法。本文的預(yù)期讀者大概有如下幾類：1. 具有很深機(jī)器學(xué)習(xí)經(jīng)驗(yàn)和背景的高階人員：就拿這篇文章當(dāng)作一個(gè)關(guān)于在線最優(yōu)化 算法的回顧材料好了，如有錯(cuò)誤和不足歡迎指正。2. 具有一定機(jī)器學(xué)習(xí)經(jīng)驗(yàn)的中級(jí)讀者：可以將本文作為-個(gè)理論資料進(jìn)行閱讀，略過(guò)“預(yù)備知識(shí)”部分，直接進(jìn)入主題，將之前對(duì)于在線最優(yōu)化算法的理解串聯(lián)起來(lái)

5、， 希墊能對(duì)將來(lái)的工作提供幫助。3. 對(duì)機(jī)譽(yù)學(xué)習(xí)有認(rèn)識(shí)但是實(shí)踐經(jīng)驗(yàn)較少的初級(jí)讀者；從預(yù)備知識(shí)看起，逐一理解相關(guān) 概念和方法，從而達(dá)到融會(huì)貫通的目的。4. 僅僅對(duì)算法的工程實(shí)現(xiàn)感興趣的讀者：大致瀏覽一下預(yù)備知識(shí)中的2.3節(jié)，了解我們要討論什么，然后直奔各算法的算法邏輯(偽代碼)，照著實(shí)現(xiàn)就Ok鳥。5. 高富帥和白富美：只需要知道本文討論的是-堆好用的求故優(yōu)解的方法，可以用于 分類預(yù)測(cè)、回歸預(yù)測(cè)等一系列問(wèn)題。然后吩咐攻城獅去實(shí)踐就好了。還可以京這篇 文章嘲笑機(jī)器學(xué)習(xí)的隔絲：看你們都弄些啥.累死累活的，掙那么兒個(gè)鋼錨©2預(yù)備知識(shí)2.1凸函數(shù)如果f(X)是定義在N維向屋空間上的實(shí)值函數(shù)，對(duì)于

6、在/'(X)的定義域C匕的任意曲個(gè)點(diǎn) X和X2，以及任意0,1之間的值t都有：/(tXi + (1 - t)X2) < tf(Xj + (1 - t)/(X2)vxpx2 e c, o < t < 1那么稱/*(X)是凸函數(shù)(Convex)【現(xiàn)一個(gè)函數(shù)是凸函數(shù)是它存在最優(yōu)解的充分必要條件。 此外，如果/'(X)滿足：f(tX, + (1 - t)X2) < tf(X) + (1 - t)f (X2)yxlfx2 e cz o < t < 1則f(X)是嚴(yán)格凸函數(shù)(StrictConvex)。如圖1所示，(a)為嚴(yán)格凸函數(shù)，(b)為凸函數(shù)。伽/

7、f(7fM/if(紺/ /-f(txzdg)/f(Xl)愉)yX/t)x? Q劉2(1 如Q(a)嚴(yán)格曲政(b) DiftM圖1凸函數(shù)2.2拉格朗日乘數(shù)法及KKT條件通常我們需要求解的最優(yōu)化問(wèn)題有如下三類:(1)無(wú)約束優(yōu)化問(wèn)題：。X = argminf(X)含義是求解X.令目標(biāo)換數(shù)f(X)最小;(2)有等式約束的優(yōu)化問(wèn)題：X = argmvnf(X)s. t. hk(X) = 0; k = 1,2 .9n含義是在門個(gè)等式約束加(乂)的條件下，求解X,令目標(biāo)函數(shù)f(X)敲小。(3)有不等式約束的優(yōu)化問(wèn)題：X = argmin fX)xh*(X) = 0; k = 1,2 .,ns giW <

8、; 0； 1= 1,2 .,m含義是在n個(gè)等式約束(X)以及m個(gè)不等式約束®(X)的條件下，求解X,令 目標(biāo)函數(shù)f(X)最小。針對(duì)無(wú)約束最優(yōu)化問(wèn)題，通常做法就是對(duì)/'(X)求導(dǎo)，并令魯/(x) = o,求解可以得到 最優(yōu)值。如果f(X)為凸函數(shù)，則可以保證結(jié)果為全局繪優(yōu)解。針対右等式約束的最優(yōu)化問(wèn)題，采用拉格朗日乘數(shù)法(Lagrange Multiplier)囚進(jìn)行求解：通過(guò)拉格朗口系數(shù)4=, .anT把等式約束和目標(biāo)函數(shù)組介成為一個(gè)式子，對(duì)該式子進(jìn)行最優(yōu)化求解：X = argminf(X) +"H(X)X其中，H(X)=加(X)M2(X).入(X)F ER&quo

9、t;,相當(dāng)干將有等式約束的最優(yōu)化問(wèn)題轉(zhuǎn)換成了 無(wú)約束最優(yōu)化求解問(wèn)題，解決方法依舊是對(duì)f(X)+"H(X)的各個(gè)參數(shù)(XM)求偏導(dǎo)，并 令其等于0,聯(lián)立等式求解。針對(duì)有不等式約束的最優(yōu)化問(wèn)題，常用的方法是KKT條件(KarushKuhnTuckerConditions)：同樣地，把所有的不等式約束、等式約束和目標(biāo)函數(shù)全部寫為一個(gè)式子：LX,A,B) = /(X) + ATH(Xy) + BtGX)KKT條件是說(shuō)瑕優(yōu)值必須滿足以下條件：dL(XM,B)=0H(X) = 0BtGX) = 0其中，B = bL,b2.bmTG(X) = (X), g2(X) . gm(X)T E 0 KKT

10、 條件是求解最優(yōu)tfix的必要條件，要使其成為充分必要條件，還需要/XX)為凸函數(shù)才行。在KKT條件中，Mg(X)= 0這個(gè)條件最有趣，因?yàn)?(X)S0,如果要滿足這個(gè)等式, 需要價(jià)=0或者®(X)= 0。在我們后面的推導(dǎo)中會(huì)用到這個(gè)性質(zhì)。2.3 從 Batch 到 Online我們面對(duì)的最優(yōu)化問(wèn)題都是無(wú)約束的最優(yōu)化問(wèn)題(有約束最優(yōu)化問(wèn)題可以利用拉格朗口 乘數(shù)法或KKT條件轉(zhuǎn)換成無(wú)約束最優(yōu)化問(wèn)題)，I大I此我們通?？梢詫⑺鼈兠枋龀桑篧 = ar grainZ)(2-3-1) Z = (,»)L/ = 1,2,.MyhiW.Xj)這里Z為觀測(cè)樣本集合(訓(xùn)練集)：召為第j條樣本

11、的特征向屋；yj =/i(W,勺)為預(yù)測(cè)值；/i(W,再)為特征向量到預(yù)測(cè)值的映射函數(shù)；#(W,Z)為最優(yōu)化求解的目標(biāo)函數(shù)，也稱作損失函 數(shù).損失函數(shù)通?？梢苑纸鉃楦鳂颖緭p失兩數(shù)的累加，即"為特 征權(quán)亜，也就是我們需要求解的參數(shù)。以線性回歸籾邏輯回歸為例，它們的映射甫數(shù)和損失 函數(shù)分別為；MLin ear Regressi onh(W.Xj) = WTXjLogistic Regression£(W,Z)=®=1M£(", Z)=2og迪 + 曠力“ W)J=i在2.1中我們給出了無(wú)約束最優(yōu)化問(wèn)題解析解的求法。而在我們實(shí)際的數(shù)值計(jì)算中，通 常做

12、法是隨機(jī)給定一個(gè)初始的"(°),通過(guò)迭代，在每次迭代中計(jì)算損失函數(shù)在當(dāng)前“的下 降方向，并更新“，直到損失函數(shù)穩(wěn)定在垠小的點(diǎn)叫例如著名的梯度下降法(GD, Gradient Descent)就是通過(guò)計(jì)算損失函數(shù)的在當(dāng)前“處的梯度叫Gradient),以梯度V以("(),Z)的 反方向作為下降方向更新"，如果損失函數(shù)是一個(gè)非平滑的凸函數(shù)(Non-smooth convex), 在不可導(dǎo)處用次梯度(Subgradient)方向的反方向作為下降方向。算法如下:Algorithm 1. Batch Gradient DescentRepeat until con

13、vergence “(r+1) = “(r) _ q(r)%f(“(r),z)JGD是一種批崑處理的方式(Batch),每次更新"的時(shí)候都要掃描所有的樣本以計(jì)算一個(gè)全 局的梯度巾(W,Z)?？紤]另_Algorithm 2. Stochastic Gradient DescentLoop for j=l to M “"+】)= W(r)- 於)(7少£(“(。弓)在算法2中，每次迭代僅僅根據(jù)單個(gè)樣本更新權(quán)重W,這種算法稱作隨機(jī)梯度卜降 (SGD, Stochastic Gradient Descent)«與GD相比較，GD每次打描所有的樣本以計(jì)算一個(gè)全局的

14、梯度，SGD則每次只針對(duì)一 個(gè)觀測(cè)到的樣本進(jìn)行更新。通常情況下，SGD能夠比GD “更快”地令"逼近最優(yōu)值。當(dāng)樣 本數(shù)M特別人的時(shí)候，SGD的優(yōu)勢(shì)更加明顯，并且由于SGD針對(duì)觀測(cè)到的“一條”樣本更新 W,很適合進(jìn)行增量計(jì)算,實(shí)現(xiàn)梯度下降的0nline模式(OGD, Online Gradient Descent )o2.4正則化lh則化(Regularization)的意義本質(zhì)匕是為避免訓(xùn)練得到的模型過(guò)度擬合(overfitting) 訓(xùn)練數(shù)據(jù)。我們用圖2來(lái)說(shuō)明什么是過(guò)擬合，該圖來(lái)自于王科的微博(王小科科科)。圖 2是一個(gè)局部加權(quán)線性回歸(Locally weighted linea

15、r regression)的訓(xùn)練結(jié)果，當(dāng)學(xué)習(xí)度為1 時(shí)，相當(dāng)于進(jìn)行線性回歸，這時(shí)候模型與訓(xùn)練樣本以及實(shí)際曲線擬介得都不夠好，模型處于 欠擬合(underfitting)狀態(tài)；當(dāng)學(xué)習(xí)度逐漸增加到4的過(guò)程中，模型逐漸與實(shí)際曲線吻合: 隨著學(xué)習(xí)度繼續(xù)増加，越來(lái)越參的樣本直接落到模型曲線上(模型擬合訓(xùn)練數(shù)據(jù))，但是模 型卻與實(shí)際曲線相差越來(lái)越人，出現(xiàn)了過(guò)擬合。過(guò)擬合體現(xiàn)出來(lái)的現(xiàn)象就是特征權(quán)重"的各個(gè)維度的絕對(duì)值非常人：一些人正數(shù).一些 人負(fù)數(shù)。這種模型雖然能夠很好I兀配樣本(如圖2-l« Degree = 20的情況)，但是對(duì)新樣本做 預(yù)測(cè)的時(shí)候會(huì)使得預(yù)測(cè)值與真實(shí)值相差很遠(yuǎn)。為了避

16、免過(guò)擬合的情況.我們通常在損失函數(shù)的基礎(chǔ)上加一個(gè)關(guān)于特征權(quán)棗“的限制, 限制它的模不要太人，如果用9(")表示特征權(quán)施"的一種求模計(jì)算，那么(231)轉(zhuǎn)換成：W = argminHWfZ)s.t. ip(W) v S這個(gè)時(shí)候我們面對(duì)的是一個(gè)有約束的最優(yōu)化問(wèn)題。根據(jù)KKT條件，我們知道當(dāng)選取合適的系 數(shù)兒 那么這個(gè)有約束故優(yōu)化問(wèn)題等價(jià)于如下無(wú)約束址優(yōu)化問(wèn)題：W = argrninf(W 9Z) + 靈諷")”(w) = llivlhN其中0(")稱作止則化因子(Regularized,是一個(gè)關(guān)干"求模的兩數(shù).我們常用止則化內(nèi)子 有L1和L2正則化

17、：LI RegularizationNL2 Regularization屮(W) = Wl =wf = WTWi=l不管是使用LI還是L2止則化，其基本原理都是一樣的，即在最小化損失函數(shù)f(W,Z)的 同時(shí)，還要考左"的模帶來(lái)的貢獻(xiàn)，從而避免”的維度上取一些絕對(duì)值很人的值。L1和L2正則化的區(qū)別主要有兩個(gè)：(1)L1正則化在0處不可導(dǎo)，而L2正則化可導(dǎo)。好 在無(wú)論是L1還是L2止則化本身都是凸歯數(shù)，因此在計(jì)算L1止則化的梯度方向的可以采用 次梯度代替；(2)在Batch模式b L1止則化通常產(chǎn)生更加稀疏(Sparse)的模型，"的更 多維度為0,這些為0的維度就代表了不是很

18、相關(guān)的維度，從而起到了待征選擇(Feature Selection)的目的。我們対稀疏性(Sparsity)比牧感興趣。除了特征選擇的作用以外，桶疏性可以使得預(yù) 測(cè)il算的復(fù)雜度降低。那么為什么L1止則化會(huì)產(chǎn)生這種桶疏性?通?？梢愿鶕?jù)文獻(xiàn)屮的 理解，如圖3所示：假如特征維度N= 2,那么LI lE則化引入的約束條件是W只能取轉(zhuǎn)置方 形中的值（圖3-（a）中黑色方框內(nèi)），L2正則化對(duì)應(yīng)的是一個(gè)圓形區(qū)域（圖3-（b）-t«黑色圓形區(qū) 域），圖3中綠色部分代表?yè)p失函數(shù)的等高線，等高線與約束區(qū)域的首次相交的地方就是報(bào) 優(yōu)解?？梢钥吹?，由于L1正則化的約束區(qū)域與坐標(biāo)軸相交的地方都有“角”出現(xiàn)，

19、等高線 更容易在這個(gè)“角”上與約束區(qū)域相交，導(dǎo)致另一個(gè)維度上的權(quán)重值為0；而L2止則化則 沒(méi)有這種性質(zhì)，因?yàn)闆](méi)右“他”,等高線在坐標(biāo)軸上與約束區(qū)域相交的概率大為減小。這樣 從直觀上就解釋了 L1正則化更容易產(chǎn)生稀疏性的原因。圖3 L1正則化與L2正則化產(chǎn)生稀疏解示意圖那么在Online模式卜呢，不同于Batch, Online中每次"的更新并不是沿著全局梯度進(jìn) 行下降，而是沿著某個(gè)樣本的產(chǎn)生的梯度方向進(jìn)行下降，整個(gè)尋優(yōu)過(guò)程變得像是一個(gè)“隨機(jī)” 査找的過(guò)程（SGD中Stochastic的來(lái)歷），這樣Online最優(yōu)化求解即使采用L1正則化的方式， 也很難產(chǎn)生稀疏解。后面介紹的各個(gè)在線最

20、優(yōu)化求解算法中，稀疏性是一個(gè)主要的追求冃標(biāo)。3在線最優(yōu)化求解算法在前面我們做了一些熱身，下面將針對(duì)在線最優(yōu)化求解介紹一些算法。在2.4中介紹了 L1正則化在Online模式下也不能產(chǎn)生較好的稀疏性，而桶疏性對(duì)于高維特征向量以及人數(shù) 據(jù)集又特別的甫要。因此，我們沿著提升模型桶疏性的主線進(jìn)行算法介紹。為了得到稀疏的特征權(quán)重“，故簡(jiǎn)單S1最的方式就是設(shè)定個(gè)閾值，當(dāng)”的某維度上系 數(shù)小于這個(gè)閾值時(shí)將其設(shè)員為0（稱作簡(jiǎn)單截?cái)啵＿@種方法實(shí)現(xiàn)起來(lái)很簡(jiǎn)單，也容易理解。 但實(shí)際中（尤斤在OGD里面）W的某個(gè)系數(shù)比較小可能是因?yàn)樵摼S度訓(xùn)練不足引起的，簡(jiǎn) 單進(jìn)行截?cái)鄷?huì)造成這部分特征的丟失。截?cái)嗵菹瘏玻═G. Tr

21、uncated Gradient）泉由 John Langford, Lihong Li 和 Tong Zhang 在 2009 年提出【均，實(shí)際上是對(duì)簡(jiǎn)單截?cái)嗟囊环N改進(jìn)。下面首先描述一下L1正則化和簡(jiǎn)單截?cái)嗟姆?法，然后我們?cè)賮?lái)看TG對(duì)簡(jiǎn)單截?cái)嗟母倪M(jìn)以及這三種方法在待定條件下的轉(zhuǎn)化。3.1.1 L1正則化法由于L1止則項(xiàng)在0處不町導(dǎo)，往往會(huì)造成平滑的凸優(yōu)化問(wèn)題變成非平滑凸優(yōu)化問(wèn)題， 因此在每次迭代中采用迪度計(jì)算L1正則項(xiàng)的梯度。權(quán)重更新方式為：online時(shí)不會(huì)產(chǎn)生稀疏解 "（+】）=“一於匕仗）_ rjAsgnw（t（3-1-1）注意，這里/IER是一個(gè)標(biāo)最，且A>0,為L(zhǎng)

22、1正則化參數(shù)：sgn（v）為符號(hào)兩數(shù)，如果 V=vvv2咖疋創(chuàng)是一個(gè)向量，可是向量的一個(gè)維度，那么有 sgn（V） = sgn（"i）, sgnd）, .,sgn（珈）G R*v：可為學(xué)習(xí)率，通常將其設(shè)置成1/Vi的函數(shù)： G（r）=知«”®，Z（）代表了第t次迭代中損失函數(shù)的梯度，由于OGD每次僅根據(jù)觀測(cè)到的7/17一個(gè)樣本進(jìn)行權(quán)重更新內(nèi)此也不再使用區(qū)分樣本的卜標(biāo)八3.1.2簡(jiǎn)單截?cái)喾ㄒ詋為窗1丨，當(dāng)t/k不為整數(shù)時(shí)采用標(biāo)準(zhǔn)的SGD進(jìn)行迭代，當(dāng)t/c為整數(shù)時(shí)，采用如卜權(quán) 重更新方式：k步做-次截斯= To（"（r）_ q（r）G（氣 8）%（%&

23、;） =0 ifvt<d “ otherwise（3-1-2）注總.這里而06 R是一個(gè)標(biāo)崑 且0 >0：如果V = vlfv2f.9vNElSLN是一個(gè)向量，匕是 向量的一個(gè)維度.那么有TQ（vfo）= To（vptq（V2,d.,tq（vNf o） e 創(chuàng)。3.1.3截?cái)嗵荻确ǎ═G）上述的簡(jiǎn)單截?cái)喾ū籘G的作者形容為too aggressive此TG在此基礎(chǔ)上進(jìn)行了改進(jìn). 同樣是采用截?cái)嗟姆绞?，但是比較不那么粗暴。采用相同的方式表示為：W（r+1） = n（“a）一盧七“久,。）7i（vpa,0）=maxEO, vt a） minf Vi + a）if" E 0,8

24、 if E -0,0 otherwise（3-1-3）其中a（O E R且人TG同樣是以k為窗【丨，每k步進(jìn)行一次截?cái)?。?dāng)t/k不為整數(shù)時(shí) 人（）= 0,臨/k為整數(shù)時(shí)A（f）= kA.從公式（3-1-3）可以石出，久和&決定了W的稀疏程度，這 兩個(gè)值越大，則掘疏堆越強(qiáng)尤其令久=8時(shí)，只需要通過(guò)調(diào)節(jié)一個(gè)參數(shù)就能控制棉疏性。根據(jù)公式（3<L3）,我們很容易寫出TG的算法邏輯：Algorithm 3. Truncated Gradient1input 62initial W 6 Rv3for t = 1,2,3. do4G = rW（W,X（r）,y（r）5refresh W acc

25、ording to（maxEg W rj"）g 於上）人（巧if （w.仙）G 0,刃> min wt = < max迤+ 卅）久（'）if （叫-於） e -0, o（叫-沙）。otherwise6end7return W3.1.4 TG與簡(jiǎn)單截?cái)嘁约癓1正則化的關(guān)系簡(jiǎn)單截?cái)嗪徒財(cái)嗵荻鹊膮^(qū)別在于采用了不同的截?cái)喙介T和如圖4所示。為了清晰地進(jìn)行比較，我們將公式（3亠3）進(jìn)行改寫，描述特征權(quán)重每個(gè)維度的更新方式:7/17if mod(t,fc) = 0otherwisew(t+i)=卩皿(3$)-他 v),熄&) 叫_ 屮_聲護(hù))酉2 = rjAk(3-1

26、-4)t pif|w|S 衿2Ec (w,雄,&) = w -蕊 sgn(w) if 觀 <M<0lwotherwise如果令觀=8,截?cái)喙絋rnc(w,0)變成：7Ync(w,e,&) = ° 空上。iw otherwise此時(shí)TG退化成簡(jiǎn)單截?cái)喾āＨ绻?=8截?cái)喙絋rnc(w,0)變成；Tmc(w,A,oo) =1° b»l -atg'， (W otherwise如果再令k = ,那么待征權(quán)重維度更新公式變成w/+i)= 7Vnc(wf)-於“兒 8)= w$)_ 瀘)_ qa)Asgn(w/)此時(shí)TG退化成L1正則化

27、法。3.2 FOBOS3.2.1 FOBOS算法原理前向后向切分(FOBOS, Forward-Backward Splitting)是曲 John Duchi 和 Yoram Singer 捉 出的網(wǎng)。從全稱上來(lái)看，該方法應(yīng)該叫FOBAS,但是由于一開始作者管這種方法叫FOLOS (Forward Looking Subgradients).為了減少讀昔的困擾，作者干脆只修改一個(gè)字母，叫FOBOS。在FOBOS中，將權(quán)重的更新分為兩個(gè)步驟：(3-2-1)前個(gè)步驟實(shí)際上是個(gè)標(biāo)準(zhǔn)的梯陳卜隧步驟，后一個(gè)步驟可以理解為對(duì)梯度卞降的結(jié)果進(jìn) 行傲週。觀察第二個(gè)步驟，發(fā)現(xiàn)對(duì)"的微調(diào)也分為兩部分：

28、(1)前一部分保證微調(diào)發(fā)生在梯度下 降結(jié)果的附近:(2)后一部分則用于處理正則化，產(chǎn)生號(hào)疏性。如果將(321)中的兩個(gè)步驟合二為一，即將以嗚)的計(jì)算代入WE沖,有:”(t+i)= argrninw 一 “ + 可G©+ 同)屮(“)令尸(147)=；|0_"(。+於叫2+,葉扌)屮(“)，如果脅殲1)存在一個(gè)最優(yōu)解，那么可以 推斷0向鼠一定屬于F(W)的次梯度集合:0 e °F(”)=W - IV(C) + 汕)G(t)+ 怡 £)d屮(W)由于"（r+1）= argmin F（W）9 那么有：o = “ _ “ _ 於r）G（）4-屮（W）|

29、（卄“上式實(shí)際上給出了 FOBOS中權(quán)更更新的另一種形式：加+1）= “一於一可（囲）。屮（加+1）我們這里可以看到，”（舛1）不僅僅與迭代前的狀態(tài)“有關(guān)，而且與迭代后的屮（“（"】）有 關(guān)?？赡苓@就是FOBOS名稱的由來(lái)。3.2.2 L1-FOBOS關(guān)于FOBOS的收斂性和Regret就不在此討論了.詳情可參見(jiàn)論文11。這里我們來(lái)看 看FOBOS如何在L1止則化下取得比較好的稀疏性。在L1正則化下,右屮（“）=劉"|1。為了簡(jiǎn)化描述，用向量"=也宀關(guān)e創(chuàng)來(lái) 表示以嗚），用M12CR來(lái)表示，嗨辦，并將公式（3-2-1）等號(hào)右邊按維度展開:N”(r+i)= argm

30、in(3-2-2)（扌3 -叭嚴(yán)+見(jiàn)叫|） i=l我們可以看到，在求和公式理1&仙-刃）2 + ；悶）中的每一項(xiàng)都是大于等于0的，所以 公式（3-2-2）可以拆解成對(duì)特征權(quán)重"每一維度單獨(dú)求解：=arcmin (學(xué)(w： 珂)2 + j|wj)首先，假設(shè)w；是minimizewi （；（叫一 v,）2 +久|wj）的最優(yōu)解，則冇w® > 0,這是丙為: 反證法：假設(shè)：w-vt < 0,那么有：扌評(píng) v ivt2 - WfFf + |（w；）2 < |（w； _ vf）2 +|w：|這與w：足minimize” Q（wt - v,）2 +見(jiàn)w： |）

31、的瑕優(yōu)解矛盾，故假設(shè)不成立，w- v（ >0既然有> 0,那么我們分兩種情況珂> 0和珂V 0來(lái)討論:11/17(1) 當(dāng) n 0 時(shí)：由于w：刃> 0,所以w： > 0.相當(dāng)于對(duì)minimiz% (土(叫一 vf)2 +為叫|)引入了不等 式約束條件一叱< 0；為了求解這個(gè)含不等式約束的故優(yōu)化問(wèn)題，引入拉格朗口乘子/?>0,由KKT條件， 有：詁7(扌3 - Vr)2 + Awt -. = 0 以及 pw； = 0；Ur|=Ur|根據(jù)上面的求導(dǎo)等式可得：w；=叭一;1 + 0：分為兩種情況：(D w * > o :由于0w； = 0所以0=0這

32、時(shí)候有：= v, -1又由于w： > 0,所以vf -1 > 0 w= 0 :這時(shí)候有：刃一力+ 0 = 0又由于0 >0,所以vr - A < 0所以，在刃二0時(shí)，w； = ma煥0, V A)(2) 當(dāng)刃V 0時(shí)：采用相同的分析方法，在可V 0時(shí)，有：w- = -max&jJD.-Vj - A)綜合上面的分析，可以得到在FOBOS在L1止則化條件I、'，特征權(quán)巫的各個(gè)維度更新的 方式為：= sn(vf)max(0,|Vi| - A)(3-2-3)=sgn (叩)於OgJ) maxo,於)g卜汕+刃久其中，為梯度G()在維度i上的取值。根據(jù)公式(3-2

33、-3),我們很容易就可以設(shè)計(jì)出L1-F0B0S的算法邏輯：Algorithm 4. Forward-Backward Splitting with LI Regularization1input A2initial W 63for t = 1,2,3. do4G = *（W,X（r）,yC）5refresh W according toW = sgn（wt -於t）s）maxo, |叫一曠）q | -）可6end7return W3.2.3 L1-FOBOS 與 TG 的關(guān)系從公式(323)町以看出，L1-F0B0S在每次更新“的時(shí)候，対"的每個(gè)維度都會(huì)進(jìn)行判定, 當(dāng)滿足葉)一於糾一

34、瀘珈I M 0時(shí)對(duì)該維度進(jìn)行“截?cái)唷?，令?yán))=0。那么我們?cè)趺慈ダ斫膺@個(gè)判定條件呢？如果我們把判定條件寫成葉)-代屈)| <於嗨)久，那么這個(gè)含 義就很清晰了：為一條樣本產(chǎn)生的梯度軍足以4+燉維度主的按垂伯喪生是夠夫的孌化 某個(gè)維度I的梯度不足 ” 1夠犬帶規(guī)析為冬屮+如九認(rèn)為在本次更新過(guò)程中該維度不夠覓要應(yīng)當(dāng)令其權(quán)覓為0。對(duì)于L1-FOBOS特征權(quán)重的各個(gè)維度更新公式(323),也可以寫作如下形式:-円gf) -嚴(yán)刃久sgn (叫-代滬)if時(shí))一於糾5瀘助otherwise13/17#/17比較上式與TG的特征權(quán)重維度更新公式(3-1-4),我們發(fā)現(xiàn)如果令& = s,k =

35、1,久需=瀘旳幾L1-FOBOS與TG完全一致。我們可以認(rèn)為L(zhǎng)1-FOBOS是TG在特定條件下的特殊形式。3.3 RDA3.3.1 RDA算法原理不論怎樣，簡(jiǎn)單截?cái)?、TG、FOBOS都述是建立在SGD的基礎(chǔ)之上的，屬于梯度下降類 型的方法，這類型方法的優(yōu)點(diǎn)就是精度比較高，并且TG、FOBOS也都能在稀疏性上得到提 升。但是有些其它類型的算法,例如RDA,是從另一個(gè)方面來(lái)求解Online Optimization并且 更有效地提升了特征權(quán)重的稀疏性。|卜丿川対偶平均(RDA. Regularized Dual Averaging)是微軟十年的研究成果，RDA是Simple Dual Averag

36、ing Scheme 一個(gè)擴(kuò)展.由 Lin Xiao 發(fā)表于 2010 年在RDA中，特征權(quán)重的更新策略為：“(C+1) = arg疇7i£2(G(r), W) + 屮(“)+ 罕(3-3-1)其中，衷示梯度G()對(duì)"的積分平均值(積分中值)：出他為正則項(xiàng)；咤為個(gè) 輔助的嚴(yán)格凸函數(shù)：fi<2|t> 1是一個(gè)非負(fù)且非自減序列。本質(zhì)上，公式(3-3-1)中包含了 3個(gè)部分： 線性函數(shù)姐;“(GOW，色含了之前所右様痔(或;欠梯疔)的平均值(山口I avar科a), (2)正則項(xiàng)屮(IV)： (3)額外正則項(xiàng) 它是一個(gè)嚴(yán)格凸函數(shù)。3.3.2 L1-RDA我們下面來(lái)看看

37、在L1正則化K RDA中的特征權(quán)重更新其有什么樣的形式以及如何產(chǎn) 生血it性。令卩(”)=人|"|1，并且由于/i(“)是一個(gè)關(guān)于W的嚴(yán)格凸換數(shù)，不妨令h(W) = Wl， 此外，將非負(fù)非自減序列定義為0(r)=y&,將L1正則化代入公式(3-3-1)W：”(r+i) = ar gm in j-(3-3-2)G(rW + AWWl針對(duì)特征權(quán)重的各個(gè)維度將其拆解成N個(gè)獨(dú)立的標(biāo)量址小化問(wèn)題：(3-3-3)minimizeUGR這里久>0,和>0；我)=扭；“胡)；公式(3-3-3)就是一個(gè)無(wú)約束的非平滑最優(yōu)化問(wèn)題。 其中第2項(xiàng)川叱|在函=0處不可導(dǎo)。假?zèng)]w：是其繪優(yōu)解

38、，并且定edw；為|函|在w；的 次導(dǎo)數(shù)，那么有：o o O => < W;氣叫 «/3-3(-1 V § V 1 引W：l彳(-1如果對(duì)公式(333)求導(dǎo)(求次導(dǎo)數(shù))并等丁 0,次梯度最優(yōu)化條件 於。+箱叫=0(3-3-5)由于久> 0,我們針對(duì)(3-3-5)分三種情況|於)| V久、護(hù) > 人和帶 V -久來(lái)進(jìn)行討論:(1) 當(dāng)|護(hù)| v久時(shí)：還可以分為三種情況： 如果w： = 0,由(335)得f = -g/A 6 d|0|,滿足(33-4) 如果w； > 0,由(33-4)得f = 1,則誹)+久+令叱誹)+ A> 0,不滿足(3

39、35) 如杲 w： V 0,由(3-3-4)得 f = -1,則於)一久 + =wt<g -A< 0,不滿足(3-3-5) 所以，當(dāng)|°|<A時(shí)，w： = 0(2) 當(dāng)©$)>久時(shí)：采用相同分析方法得到w； <0,有§ = 一1滿足條件，即：=一人)當(dāng)©,)< -A時(shí)：采用相同分析方法得到w； >0,有§ = 1滿足條件，即：叫=一¥(0$)+久)綜合上面的分析，可以得到L1-RDA特征權(quán)電的各個(gè)維度更新的方式為：15/17#/170- ¥(卿-脳卯(即)otherwise(3-3-

40、6)#/17這里我們發(fā)現(xiàn)，當(dāng)某個(gè)維度上累枳梯度平均値的絕對(duì)值|卩|小J：閾值A(chǔ)的時(shí)候，該維度權(quán)巫 將被置0,特征權(quán)重的稀疏性由此產(chǎn)生。根據(jù)公式(3-3-b).可以設(shè)計(jì)出L1-KDA的算法邏輯：Algorithm 5. Regularized Dual Averaging with LI Regularization1input y, A2initialize W ERN,G = 0e3for1,2,3. do4G = G t+ ?以（W,X（W）5refresh W according to（t+i）wf=0一乎©-人sgn©） rif Isl < 人 otherwi

41、se6end7return W3.3.3 Ll-RDA 與 Ll-FOBOS 的比較在3.2.3中我們看到了 L1-FOBOS實(shí)際上是TG的一種待殊形式，在L1-FOBOS中，進(jìn)行 “截?cái)唷钡呐卸l件是時(shí)）-於）諾）上短=嚴(yán)況 通常會(huì)定義可為與命正相關(guān)的函數(shù) 5 = 0（加），因此L1-FOBOS的“截?cái)嚅撝怠睘?#169;（）/1,隨著t的増加，這個(gè)閾值會(huì)逐漸 降低。相比較而盲，從（33-6）可以看出，L1-RDA的“截?cái)嚅撝怠睘榫?，是一個(gè)常數(shù)，并不隨著t而變 化,因此可以認(rèn)為L(zhǎng)1-RDA比L1-FOBOS在截?cái)嗯卸ㄉ细觓ggressive,這種性質(zhì)使得L1-RDA 更容易產(chǎn)生稀疏性：此外

42、，RDA中判定對(duì)象是梯度的累加平均值那），不同于TG或 L1-FOBOS中針對(duì)單次梯度計(jì)算的結(jié)果進(jìn)行判定，避免了由丁某些維度由丁訓(xùn)練不足導(dǎo)致截 斷的問(wèn)題.并且通過(guò)調(diào)節(jié)久一個(gè)參數(shù)，很容易在精度和稀疏性上進(jìn)行權(quán)衡。3.4 FTRL在3.3.3中我們從原理上定性比較了 L1-FOBOS和L1-RDA任稀疏性上的表現(xiàn)。有實(shí)驗(yàn)證 明，L1-FOBOS這一類基于梯度下降的方法右比較高的精度，但是L1-RDA卻能在損失一定精 度的情況下產(chǎn)生更好的柿疏性。那么這兩者的優(yōu)點(diǎn)能不能在一個(gè)算法上體現(xiàn)出來(lái)？這就是 FTRL要解決的問(wèn)題。FTRL （Follow the Regularized Leader）是由 Go

43、ogle 的 H. Brendan McMahan 在 2010 年提 出的網(wǎng),后來(lái)在2011年發(fā)表了一篇關(guān)于FTRL和AOGD、FOBOS、RDA比較的論文冋，2013 年又和Gary Holt, D. Sculley, Michael Young等人發(fā)表了一篇關(guān)于FTRL匸程化實(shí)現(xiàn)的論文（均。本節(jié)我們首先從形式上將L1-F0B0S和L1-RDA進(jìn)行統(tǒng)一，然后介紹從這種統(tǒng)一形式產(chǎn)生 FTRL算法，以及介紹FTRL算法工程化實(shí)現(xiàn)的算法邏輯。3.4.1 L1-FOBOS和L1-RDA在形式上的統(tǒng)一L1-F0B0S在形式上，每次迭代都可以表示為（這里我們令少4）=於）=0（1）是一個(gè) 隨t變化的非

44、堀正序列）：“(t+1) = argmin -+ 於5|"|寸把這兩個(gè)公式合并到一起，有：V7(t+i) = argmin 匸 |W "(，)+ 於必+ 可久|W|h(2 丿通過(guò)這個(gè)公式很難直接求出"(州1)的解析解，但是我們町以按維度將其分解為N個(gè)獨(dú)立的 最優(yōu)化步驟：minimize屮+產(chǎn)硏)+7/<CU|wt|1 2 1 2=minimize2(« _ wf) + 2(r)(f) + 貯勺詰)+ rAwt=minimize USGR叫護(hù)+刃叫| +為(叫一叫")+字(捫)19/17#/172由于學(xué)P) 沙)與變量叫無(wú)關(guān)，因此上式可以等

45、價(jià)于:minimize + A|wJ + 厲話' (叱 一 wf)再將這N個(gè)獨(dú)立最優(yōu)化子步驟介并，那么L1-FOBOS可以寫作：“一 ”訓(xùn)？WtGR" +刀Will +"(t+1) = argmin而對(duì)于Ll-RDA的公式(332),我們可以寫作:這里G(m)= Y；“G(£)：如果令(7($)=命一命，ad：t) = _L,上面兩個(gè)式子可以寫作:(3-4-1)”a+i)=argrnin g(。 W + 刃|W|h +-2)4#/17需要注意，與論文15中的Table 1不同，我們并沒(méi)有將L1-F0B0S也寫成累加梯度的形式。 比較(341)利(342)這

46、兩個(gè)公式，町以看出L1-FOBOS和L1-RDA的區(qū)別在于： 前者 對(duì)計(jì)算的是累加梯度以及L1正則項(xiàng)只考慮當(dāng)前模的貢獻(xiàn)，而后者采用了累加的處理方式： (2)前者的第三項(xiàng)限制“的變化不能離己迭代過(guò)的解太遠(yuǎn)，而后者則限制"不能離0點(diǎn)太遠(yuǎn)。342 FTRL算法原理FTRL綜介考慮了 FOBOS和RDA對(duì)于止則項(xiàng)和"限制的區(qū)別其特征權(quán)棗的更新公式為:t“(r+i) = argjnin)Gllt (3-4-3)w + AJWII1 + A2i|VK|2 + 訖*$)W - W($)|；S = 1注意，公式(343)中岀現(xiàn)fL2iE則項(xiàng)扌IWII%在論文15的公式中并沒(méi)有這一項(xiàng)，但是在

47、其2013 年發(fā)表的FTRL工程化實(shí)現(xiàn)的論文16卻使用到了 L2正則項(xiàng)。班實(shí)上該項(xiàng)的引入并不影響FRTL 的稀疏性，后面的推導(dǎo)過(guò)程會(huì)顯示這一點(diǎn)。L2正則項(xiàng)的引入僅僅相當(dāng)于對(duì)最優(yōu)化過(guò)程多了一 個(gè)約束，使得結(jié)果求解結(jié)果更加“平滑”。公式(343)看上去很復(fù)雜更新特征權(quán)重貌似非常困難的樣子。不妨將其進(jìn)行改寫，將 最后一項(xiàng)展開，等價(jià)于求下面這樣一個(gè)最優(yōu)化問(wèn)題：|（G（"） w + 如Wh + 扌卜 +IWIE+扭旳w噸S=1由于弭叫|W($)|；相對(duì)于"來(lái)說(shuō)是一個(gè)常數(shù)，并且令Z()=G(M-&“*s)W($),上 式等價(jià)于：”（r+i） = argmin久2+處)II哪S

48、= 1)#/17針對(duì)特征權(quán)覓的乞個(gè)維度將氏拆解成N個(gè)獨(dú)立的標(biāo)最最小化問(wèn)題:minimize UGR#/17#/17到這里，我們遇到了與(333)類似的優(yōu)化問(wèn)題，用相同的分析方法可以得到：0if v 兒（3-4-4）/ t T(+汩(z$)右 sgn(zf) otherwise從(3-4-4)町以看出，引入L2 lF則化并沒(méi)有對(duì)FTRL結(jié)果的稀疏性產(chǎn)生任何影響。3.4.3 Per-Coordinate Learning Rates前面介紹了 FTRL的基本推導(dǎo)，但是這里還有一個(gè)問(wèn)題是一直沒(méi)有被討論到的：關(guān)于學(xué) 習(xí)率耳的選擇和計(jì)算。事實(shí)上在FTRL中，每個(gè)維度上的學(xué)習(xí)率都是單獨(dú)考慮的 (Per-C

49、oordlnaie Learnlng Rates )o在一個(gè)標(biāo)準(zhǔn)的OGD里面使用的是一個(gè)全局的學(xué)習(xí)率策略於)=命,這個(gè)策略保證了學(xué)習(xí) 率是一個(gè)正的非增長(zhǎng)序列，對(duì)于每一個(gè)待征維度都是一樣的。考慮特征維度的變化率：如果特征1比特征2的變化更快，那么在維度1上的學(xué)習(xí)率應(yīng) 該下降得更快。我們很容易就可以想到町以用某個(gè)維度上梯度分最來(lái)反映這種變化率。在 FTRL中，維度i上的學(xué)習(xí)率是這樣計(jì)算的：F疣0+后:訶,3-4'5)由于水=侖所以公式(344)中廉旳=命=(0 +(詁)2)/心這里的a和0是需要輸入的參數(shù)，(3-4-4)中學(xué)習(xí)率寫成累加的形式，是為了方便理解后面FTRL的迭代 計(jì)算邏輯。3

50、.4.4 FTRL算法邏輯到現(xiàn)在為止，我們已經(jīng)得到了 FTRL的特征權(quán)重維度的更新方法(公式(344),每個(gè)特#/17Algorithm 6. FTRL-Proximal with LI & L2 Regularization1 input a, p, Alz A22 initialize W G Z = 0 G vz Q = 0CN45678G = Vw(Wttt gradient of loss functionfor / in 1,2,.,N do # for each coordinateZf =Zf+5-5Wf (Qif < Aiotherwise5 =扌 J% + 冊(cè)

51、一何 & 4 = 4 + 3i-(人2 +i(Zj -入iSgn(Zi)end10 end 11 return WFTRL里面的4個(gè)參數(shù)需要針對(duì)具體的問(wèn)題進(jìn)行設(shè)置，指導(dǎo)性的意見(jiàn)參考論文16。4結(jié)束語(yǔ)本文作為在線最優(yōu)化算法的整理和總結(jié)，沿著稀疏性的主線，先后介紹了簡(jiǎn)單截?cái)喾ā?TG、FOBOS、RDA以及FTRL。從類型上來(lái)看，簡(jiǎn)單截?cái)喾?、TG、FOBOS屬于同一類，都是 梯度下降類的算法，并且TG在特定條件可以轉(zhuǎn)換成簡(jiǎn)單截?cái)喾ê虵OBOS： RDA屬于簡(jiǎn)單對(duì)偶 平均的擴(kuò)展應(yīng)用：FTRL可以視作RDA和FOBOS的結(jié)介，同時(shí)具備二者的優(yōu)點(diǎn)。目前來(lái)看, RDA和FTRL是最好的稀疏模型On

52、line Training的算法。談到高維高數(shù)據(jù)量的最優(yōu)化求解，不可避免的要涉及到并行計(jì)算的問(wèn)題。作者之前令篇 博客討論了 batch模式下的并行邏輯回歸，其實(shí)只要修改損失函數(shù)，就可以用于其它問(wèn)題 的最優(yōu)Algorithm 7. ParallelSGD(Zlf Z2 . Zm, T,耳,Wo, fc)for all i 6 1,2 k parallel dovt = SGD(ZvZ2on clientendAggregate from all computers v = 7SL1 vi and return vA對(duì)于Online模式的并行化計(jì)算，一方面可以參考ParallelSGD的思路，另一

53、方面也可以 借鑒batch模式下對(duì)高維向量點(diǎn)乘以及梯度分量并行計(jì)算的思路?？傊诶斫馑惴ㄔ淼?基礎(chǔ)上將計(jì)算步驟進(jìn)行拆解，使得各節(jié)點(diǎn)能獨(dú)自無(wú)關(guān)地完成計(jì)算最后匯總結(jié)果即町。故后，需要指出的是相關(guān)論文里面使用的數(shù)學(xué)符號(hào)不盡相同，并且有的論文里面也存在 一定的筆誤，但是并不影響我們對(duì)其的理解。在本文中盡量采用了統(tǒng)一風(fēng)格和含義的符號(hào)、 變量等，因此在與參考文獻(xiàn)中的公式對(duì)比的時(shí)候會(huì)稍有出入。另外，F(xiàn)h于筆者的水平有限, 行文中存在的錯(cuò)課難以避免，歡迎大家指正、拍磚。參考文獻(xiàn)1 Convex function. /wiki/Convex fun ction2 Lagrange multiplier. http:/en.