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

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

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

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

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

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

6、在/'(X)的定義域C匕的任意曲個點 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)一個函數(shù)是凸函數(shù)是它存在最優(yōu)解的充分必要條件。 此外，如果/'(X)滿足：f(tX, + (1 - t)X2) < tf(X) + (1 - t)f (X2)yxlfx2 e cz o < t < 1則f(X)是嚴格凸函數(shù)(StrictConvex)。如圖1所示，(a)為嚴格凸函數(shù)，(b)為凸函數(shù)。伽/

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

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

9、t;,相當干將有等式約束的最優(yōu)化問題轉換成了 無約束最優(yōu)化求解問題，解決方法依舊是對f(X)+"H(X)的各個參數(shù)(XM)求偏導，并 令其等于0,聯(lián)立等式求解。針對有不等式約束的最優(yōu)化問題，常用的方法是KKT條件(KarushKuhnTuckerConditions)：同樣地，把所有的不等式約束、等式約束和目標函數(shù)全部寫為一個式子：LX,A,B) = /(X) + ATH(Xy) + BtGX)KKT條件是說瑕優(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這個條件最有趣，因為3(X)S0,如果要滿足這個等式, 需要價=0或者®(X)= 0。在我們后面的推導中會用到這個性質(zhì)。2.3 從 Batch 到 Online我們面對的最優(yōu)化問題都是無約束的最優(yōu)化問題(有約束最優(yōu)化問題可以利用拉格朗口 乘數(shù)法或KKT條件轉換成無約束最優(yōu)化問題)，I大I此我們通?？梢詫⑺鼈兠枋龀桑篧 = ar grainZ)(2-3-1) Z = (,»)L/ = 1,2,.MyhiW.Xj)這里Z為觀測樣本集合(訓練集)：召為第j條樣本

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

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

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

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

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

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

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

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

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

20、優(yōu)化求解算法中，稀疏性是一個主要的追求冃標。3在線最優(yōu)化求解算法在前面我們做了一些熱身，下面將針對在線最優(yōu)化求解介紹一些算法。在2.4中介紹了 L1正則化在Online模式下也不能產(chǎn)生較好的稀疏性，而桶疏性對于高維特征向量以及人數(shù) 據(jù)集又特別的甫要。因此，我們沿著提升模型桶疏性的主線進行算法介紹。為了得到稀疏的特征權重“，故簡單S1最的方式就是設定個閾值，當”的某維度上系 數(shù)小于這個閾值時將其設員為0（稱作簡單截斷）。這種方法實現(xiàn)起來很簡單，也容易理解。 但實際中（尤斤在OGD里面）W的某個系數(shù)比較小可能是因為該維度訓練不足引起的，簡 單進行截斷會造成這部分特征的丟失。截斷梯席叢（TG. Tr

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

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

23、;） =0 ifvt<d “ otherwise（3-1-2）注總.這里而06 R是一個標崑 且0 >0：如果V = vlfv2f.9vNElSLN是一個向量，匕是 向量的一個維度.那么有TQ（vfo）= To（vptq（V2,d.,tq（vNf o） e 創(chuàng)。3.1.3截斷梯度法（TG）上述的簡單截斷法被TG的作者形容為too aggressive此TG在此基礎上進行了改進. 同樣是采用截斷的方式，但是比較不那么粗暴。采用相同的方式表示為：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步進行一次截斷。當t/k不為整數(shù)時 人（）= 0,臨/k為整數(shù)時A（f）= kA.從公式（3-1-3）可以石出，久和&決定了W的稀疏程度，這 兩個值越大，則掘疏堆越強尤其令久=8時，只需要通過調(diào)節(jié)一個參數(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與簡單截斷以及L1正則化的關系簡單截斷和截斷梯度的區(qū)別在于采用了不同的截斷公式門和如圖4所示。為了清晰地進行比較，我們將公式（3亠3）進行改寫，描述特征權重每個維度的更新方式:7/17if mod(t,fc) = 0otherwisew(t+i)=卩皿(3$)-他 v),熄&) 叫_ 屮_聲護)酉2 = rjAk(3-1

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

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

28、(1)前一部分保證微調(diào)發(fā)生在梯度下 降結果的附近:(2)后一部分則用于處理正則化，產(chǎn)生號疏性。如果將(321)中的兩個步驟合二為一，即將以嗚)的計算代入WE沖,有:”(t+i)= argrninw 一 “ + 可G©+ 同)屮(“)令尸(147)=；|0_"(。+於叫2+,葉扌)屮(“)，如果脅殲1)存在一個最優(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、（卄“上式實際上給出了 FOBOS中權更更新的另一種形式：加+1）= “一於一可（囲）。屮（加+1）我們這里可以看到，”（舛1）不僅僅與迭代前的狀態(tài)“有關，而且與迭代后的屮（“（"】）有 關?？赡苓@就是FOBOS名稱的由來。3.2.2 L1-FOBOS關于FOBOS的收斂性和Regret就不在此討論了.詳情可參見論文11。這里我們來看 看FOBOS如何在L1止則化下取得比較好的稀疏性。在L1正則化下,右屮（“）=劉"|1。為了簡化描述，用向量"=也宀關e創(chuàng)來 表示以嗚），用M12CR來表示，嗨辦，并將公式（3-2-1）等號右邊按維度展開:N”(r+i)= argm

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

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

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

33、-3),我們很容易就可以設計出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 的關系從公式(323)町以看出，L1-F0B0S在每次更新“的時候，対"的每個維度都會進行判定, 當滿足葉)一於糾一

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

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

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

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

38、，并且定edw；為|函|在w；的 次導數(shù)，那么有：o o O => < W;氣叫 «/3-3(-1 V § V 1 引W：l彳(-1如果對公式(333)求導(求次導數(shù))并等丁 0,次梯度最優(yōu)化條件 於。+箱叫=0(3-3-5)由于久> 0,我們針對(3-3-5)分三種情況|於)| V久、護 > 人和帶 V -久來進行討論:(1) 當|護| v久時：還可以分為三種情況： 如果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) 所以，當|°|<A時，w： = 0(2) 當©$)>久時：采用相同分析方法得到w； <0,有§ = 一1滿足條件，即：=一人)當©,)< -A時：采用相同分析方法得到w； >0,有§ = 1滿足條件，即：叫=一¥(0$)+久)綜合上面的分析，可以得到L1-RDA特征權電的各個維度更新的方式為：15/17#/170- ¥(卿-脳卯(即)otherwise(3-3-

40、6)#/17這里我們發(fā)現(xiàn)，當某個維度上累枳梯度平均値的絕對值|卩|小J：閾值A的時候，該維度權巫 將被置0,特征權重的稀疏性由此產(chǎn)生。根據(jù)公式(3-3-b).可以設計出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實際上是TG的一種待殊形式，在L1-FOBOS中，進行 “截斷”的判定條件是時）-於）諾）上短=嚴況 通常會定義可為與命正相關的函數(shù) 5 = 0（加），因此L1-FOBOS的“截斷閾值”為©（）/1,隨著t的増加，這個閾值會逐漸 降低。相比較而盲，從（33-6）可以看出，L1-RDA的“截斷閾值”為久，是一個常數(shù)，并不隨著t而變 化,因此可以認為L1-RDA比L1-FOBOS在截斷判定上更加aggressive,這種性質(zhì)使得L1-RDA 更容易產(chǎn)生稀疏性：此外

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

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

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

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

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

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

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

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

50、.4.4 FTRL算法邏輯到現(xiàn)在為止，我們已經(jīng)得到了 FTRL的特征權重維度的更新方法(公式(344),每個特#/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% + 冊

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

52、line Training的算法。談到高維高數(shù)據(jù)量的最優(yōu)化求解，不可避免的要涉及到并行計算的問題。作者之前令篇 博客討論了 batch模式下的并行邏輯回歸，其實只要修改損失函數(shù)，就可以用于其它問題 的最優(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對于Online模式的并行化計算，一方面可以參考ParallelSGD的思路，另一

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