Lr
二、 邏輯回歸
? ? ? ?言歸正傳，因為廣告大部分是按照CPC計費的，而我們手里的流量是固定的，因此對每條廣告請求我們就需要保證這條廣告的展示收益更大。而廣告收益是可以根據點擊率、廣告計費價格、廣告質量度均衡決定的，所以我們就需要評估廣告的質量度和點擊率，本文就主要研究廣告點擊率預估中廣泛使用的邏輯回歸模型。在實際廣告點擊率預估的應用中，樣本數目和特征(邏輯回歸粗暴離散化后)的數目均可以達到上億緯度，而LR因為其簡單和易并行，并且基于復雜的特征工程后也能得到非常好的效果，所以在工業界獲得了廣泛的應用。
? ? ? 邏輯回歸，相對于線性回歸是用來處理目標函數是離散數值的情況。它的映射函數和損失函數分別為：
? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? （2）
? ? ? 使用梯度下降法進行求解，得到迭代公式：
? ? ? ? ? ?
1. ?邏輯回歸的優缺點：
? ? ? 優點： ?
? ? ? ? ? a. 簡單
? ? ? ? ? b. 易于并行、速度快
? ? ? 缺點：
? ? ? ? ? a. 需要復雜的特征工程
? ? ? 注意事項：
? ? ? ? ? a. 輸入特征需要離散化。
三、 SGD算法
? ? ? ? ?對于如上LR的迭代公式來說，我們可以得到GD（Gradient Descent）的求解算法。(W為求解的參數，l(w, z)為損失函數）。
? ? ??
? ? ? 可是如果我們對參數做一輪迭代求解，都需要遍歷所有的樣本，這在實際應用中未免迭代速度太慢，模型更新速度也太慢。而且做機器學習的時候往往更多的數據意味著更好的效果，我們能把線上實時的數據和樣本標注也利用進來么？答案是 Yes。仔細研究參數的迭代我們可以發現，都是給定一個初始的參數W，通過迭代逐步求解出當前W下降的方向并更新W直到損失函數穩定在最小點。那么我們是不是可以取部分訓練集作為原訓練集的子集，使用這些子集做迭代，并逐步求解W的下降方向，逐步對W進行更新（理論證明未知）。特別的，如果我們每次取原訓練樣本的一個訓練樣本，對W的值逐步進行更新，那么我們就得到了SGD算法。
? ? ? ? ? ? ?
? ? ? ? ?? ?與SGD比較，GD需要每次掃描所有的樣本以計算一個全局梯度，SGD則每次只針對一個觀測到的樣本進行更新。通常情況下SGD可以更快的逼近最優值，而且SGD每次更新只需要一個樣本，使得它很適合進行增量或者在線計算（也就是所謂的Online learning）。
? ? ? ? ?特別的，迭代和選取模型的時候我們經常希望得到更加稀疏的模型，這不僅僅起到了特征選擇的作用，也降低了預測計算的復雜度。在實際使用LR的時候我們會使用L1或者L2正則，避免模型過擬合和增加模型的魯棒性。在GD算法下，L1正則化通常能得到更加稀疏的解；可是在SGD算法下模型迭代并不是沿著全局梯度下降，而是沿著某個樣本的梯度進行下降，這樣即使是L1正則也不一定能得到稀疏解。在后面的優化算法中，稀疏性是一個主要追求的目標。
四、 TG算法
1. ?L1 正則化法
? ? ? ? 由于L1正則項在0處不可導，往往會造成平滑的凸優化問題變成非平滑的凸優化問題，因此可以采用次梯度(Subgradient)來計算L1正則項的梯度。權重更新方式為：
? ? ? ? ?
? ? ? ?其中是一個標量，為L1正則化的參數；v是一個向量，sgn(v)為符號函數；稱為學習率，通常將其設置為的函數；代表第t次迭代中損失函數的梯度。
2. ?簡單截斷法
? ? ? ? ?既然L1正則化在Online模式下也不能產生更好的稀疏性，而稀疏性對于高維特征向量以及大數據集又特別的重要，我們應該如何處理的呢？
? ? ? ? ?簡單粗暴的方法是設置一個閥值，當W的某緯度的系數小于這個閥值的時候，將其直接設置為0。這樣我們就得到了簡單截斷法。簡單截斷法以k為窗口，當t/k不為整數時采用標準的SGD進行迭代，當t/k為整數時，權重更新方式如下：
? ? ? ? ? ?
? ? ? ? ? ?
? ? ? ? ?這里是一個正數；V是一個向量。
3. ?梯度截斷法
? ? ? ? ?簡單截斷法法簡單且易于理解，但是在實際訓練過程中的某一步，W的某個特征系數可能因為該特征訓練不足引起的，簡單的截斷過于簡單粗暴(too aggresive)，會造成該特征的缺失。那么我們有沒有其他的方法，使得權重的歸零和截斷處理稍微溫柔一些呢？對，這就是梯度截斷法，簡單截斷法和梯度截斷法對特征權重的處理映射圖對比如下：
?? ? ? ? ? ?
? ? ? ? ? ?梯度截斷法的迭代公式如下：
? ? ? ? ? ??
? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? (3)
? ? ? ? ? ?同樣的梯度截斷法也是以k為窗口，每k步進行一次截斷。當t/k不為整數時，當t/k為整數時。從公式(3)可以看出和決定了截斷的區域，也決定了W的稀疏程度。這兩個數值越大，截斷區域越大，稀疏性也越強。尤其這兩個值相等的時候，只需要調節一個參數就能控制稀疏性。根據公式(3)，得到TG的算法邏輯如下：
? ? ? ? ?
? ? ? ? ?特別的對(3)進行改寫，得到描述特征權重的更新方式為：
? ? ? ? ? ? ? ??
? ? ? ? ? ? ? ??
? ? ? ? ?如果令，截斷公式變成：
? ? ? ? ? ? ? ??
? ? ? ? ?此時TG退化成簡單截斷法。同樣如果令，我們就可以得到L1正則化方法。
四、 FOBOS算法
? ? ? ? ? FOBOS(Forward-Backward Splitting)是由John Duchi和Yoram Singer提出的。FOBOS算法把正則化的梯度下降問題分成一個經驗損失梯度下降迭代和一個最優化問題。其中第二個最優化問題有兩項：第一項2范數那項表示不能離loss損失迭代結果太遠，第二項是正則化項，用來限定模型復雜度、抑制過擬合和做稀疏化等。
? ? ? ? ?
? ? ? ? ? 由于求和公式中的每一項都是大于等于0的，所以公式(2)可以拆解成對特征權重每一緯度單獨求解：
? ? ? ? ??? ? ? ? ? ? (2)
? ? ? ? ? ?首先假設w是(2)的最優解，則有。反正時代入，可以得到w=0是(2)的最優解。。。
? ? ? ? ? ?對v和w的取值分別進行求解可以得到：
? ? ? ? ? ?
? ? ? ? ? ?
? ? ? ? ? ?其中g_i^(t)為梯度G^(t)在緯度i上的取值。然后我們可以得到L1-FOBOS的算法邏輯：
? ? ? ? ? ?
1. ?L1-FOBOS與TG的關系 ?
? ? ? ? ? ?從公式3)可以看出，L1-FOBOS 在每次更新W的時，對W的每個緯度都會加以判定，當滿足時對該緯度的特征進行截斷，這個判定的含義是當一條樣本的梯度不足以令對應緯度上的權重值發生足夠大的變化時，認為在本次更新中該緯度不夠重要，應當令其權重為0。
? ? ? ? ? ?對于L1-FOBOS特征權重的各個緯度更新公式(3)，也可以寫為如下形式：
? ? ? ? ? ???
? ? ? ? ? ? 如果令，L1-FOBOS與TG完全一致，L1-FOBOS是TG在特定條件下的特殊形式。
五、 RDA算法
? ? ? ? ? ?之前的算法都是在SGD的基礎上，屬于梯度下降類型的方法，這類型的方法的優點是精度比較高，并且TG、FOBOS也能在稀疏性上得到提升。但是RDA卻從另一個方面進行在線求解，并且有效提升了特征權重的稀疏性。RDA是Simple Dual Averaging Scheme的一個擴展，由Lin Xiao發表與2010年。
? ? ? ? ? 在RDA中，特征權重的更新策略包含一個梯度對W的積分平均值，正則項和一個輔助的嚴格凸函數。具體為：
。其中<G(t),W>表示梯度G對W的積分平均值，包含了之前所有梯度的平均值；為正則化項，表示一個非負且非自減序列，是一個嚴格的凸函數。
1. ?算法原理
? ? ? ? ? ?之前的算法都是在SGD的基礎上，屬于梯度下降類型的方法，這類型的方法的優點是精度比較高，并且TG、FOBOS也能在稀疏性上得到提升。但是RDA卻從另一個方面進行在線求解，并且有效提升了特征權重的稀疏性。RDA是Simple Dual Averaging Scheme的一個擴展，由Lin Xiao發表于2010年。
? ? ? ? ? L1-RDA特征權重各個緯度更新方式為：
? ? ? ? ? ? ? ??
? ? ? ? ? 這里當某個緯度上累積梯度平均值小于閥值的時候，該緯度權重將被設置為0，特征稀疏性由此產生。
? ? ? ? ? 對比L1-FOBOS我們可以發現，L1-FOBOS是TG的一種特殊形式，在L1-FOBOS中，進行截斷的判定條件是
，通常會定義為正相關函數。因此L1-FOBOS的截斷閥值為，隨著t增加，這個閥值會逐漸降低。而相比較而言L1-RDA的截斷閥值為，是一個固定的常數，因此可以認定L1-RDA比L1-FOBOS更加aggressive。此外L1-FOBOS判定是針對單次梯度計算進行判定，避免由于訓練不足導致的截斷問題。并且通過調節一個參數，很容易在精度和稀疏性上進行權衡。
六、FTRL算法
? ?有實驗證明，L1-FOBOS這一類基于梯度下降的方法有較高的精度，但是L1-RDA卻能在損失一定精度的情況下產生更好的稀疏性。如何能把這兩者的優點同時體現出來的呢？這就是
1. ?L1-FOBOS與L1-RDA在形式上的統一：
L1-FOBOS在形式上，每次迭代都可以表示為（這里我們令）
FTRL綜合考慮了FOBOS和RDA對于正則項和W的限制，其特征權重為：
注意，公式(3)中出現了L2正則項，而論文[2]的公式中并沒有這一項，但是在2013年發表的FTRL工程化實現的論文中卻使用了L2正則化項。事實上該項的引入并不影響FTRL的稀疏性，僅僅相當于對最優化過程多了一個約束，使得結果求解更加平滑。
公司(3)看上去很復雜，更新特征權重貌似非常困難。不妨將其改寫。將其最后一項展開等價于求解下面的這樣一個最優化問題：
，于是針對特征權重的各個緯度將其拆解成N個獨立的標量最小化問題。上式最后一項相對于W說是一個常數項，并且令，上式等價于：
到這里，我們遇到了與RDA求解類似的最優化問題。用相同的分析方法可以得到：
上式可以看出，引入L2正則化對于FTRL結果的稀疏性產生任何影響。
在一個標準OGD中使用的是一個全局學習策略，這個策略保證了學習率是一個正的非增長序列，對于每個特征的緯度都是一樣的。
考慮特征緯度的變化率：如果特征1比特征2的變化更快，那么緯度1上學習率應該下降的比較快。我們就很容易可以用某個緯度上梯度分量來反映這種變化率。在FTRL中緯度i上的學習率是這樣計算的：
。由于，所以公式(4)中有，這里的和是需要輸入的參數，公式(4)中學習率寫成累加的形式，是為了方便理解后面FTRL的迭代計算邏輯。偽碼采用的事L1和L2混合正則，即實際的迭代是如下形式：
總結：
從類型上來看，簡單截斷法、TG、FOBOS屬于同一類，都是梯度下降類的算法,并且TG在特定條件可以轉換成簡單截斷法和FOBOS；RDA屬于簡單對偶平均的擴展應用；FTRL可以視作RDA和FOBOS的結合，同時具備二者的優點。目前來看，RDA和FTRL是最好的稀疏模型Online Training的算法。FTRL并行化處理，一方面可以參考ParallelSGD，另一方面可以使用高維向量點乘，及梯度分量并行計算的思路。
參考文獻：
1. ?http://www.wbrecom.com/?p=342 ? 本文顯然大量參考了該文章。 作者寫的確實好，我再寫一遍以便加深自己的理解。
總結
- 上一篇： 互联网金融之量化投资深度文本挖掘——附源
- 下一篇： 入门lr