文章目錄
- 1、邏輯回歸
-
- 1.1 sigmoid函數
- 1.2 極大似然估計MLE與損失函數
- 1.3 梯度下降
- 1.4 另一種形式的損失函數及其梯度
- 2、FOBOS與RDA
-
- 2.1 FOBOS基本原理
- 2.2 L1-FOBOS
- 2.3 RDA基本原理
- 2.4 L1-RDA
- 3、FTRL
-
- 3.1 從L1-FOBOS和L1-RDA推導FTRL
- 3.2 FTRL權重更新的最終形式
- 3.3 學習率
- 3.4 工程實作計算過程
-
- 3.4.1 一些定義
- 3.4.2 FTRL算法
- 4、FTRL的工程應用
1、邏輯回歸
FTRL本質上是一種優化方法，最早由google提出并用于CTR預估。常被用于邏輯回歸的優化，是以先簡單介紹一下邏輯回歸的内容。
1.1 sigmoid函數
由于二分類結果是1或者0，這與數學的階躍函數很類似，但是階躍函數在x=0的位置會發生突變，這個突變在數學上很難處理。是以一般使用sigmoid函數來拟合：
g ( z ) = 1 1 + e − z ( 1 ) g(z)={\frac 1{1+e^{-z}}} \qquad(1) g(z)=1+e−z1(1)
具體應用到邏輯回歸算法中：
z = ω 0 + ω 1 x 1 + ω 2 x 2 + . . . . . . + ω n x n = ∑ i = 0 n ω i x i = ω T X ( 2 ) z={\omega}_0+{\omega}_1x_1+{\omega}_2x_2+......+{\omega}_nx_n=\sum_{i=0}^n{\omega}_ix_i=\mathbf{\omega^TX} \qquad(2) z=ω0+ω1x1+ω2x2+......+ωnxn=i=0∑nωixi=ωTX(2)
其中 x i x_i xi表示樣本屬性（對于我們而言，就是标簽IP）的值， ω i \omega_i ωi表示這個屬性對應的系數（也就是算法需要計算的内容）。注意這裡将 x 0 x_0 x0與 ω 0 \omega_0 ω0也代入了上述公式，其中前者恒為1。于是問題就變成了在訓練樣本中，已知屬性x與最終分類結果y（1或者0）時，如何求得這些系數 ω i \omega_i ωi，使得損失最小。
1.2 極大似然估計MLE與損失函數
在機器學習理論中，損失函數（loss function）是用來衡量模型的預測值 f ( x ) f(x) f(x)與真實值 Y Y Y的不一緻程度，它是一個非負實值函數，損失函數越小，模型越優（還需考慮過拟合等問題）。損失函數是經驗風險函數的核心部分，也是結構風險函數重要組成部分。模型的結構風險函數包括了經驗風險項和正則項，通常可以表示成如下式子
ω ∗ = arg min ω 1 m ∑ i = 1 m L ( y i , f ( x i ; ω ) ) + λ Φ ( ω ) ( 3 ) \omega^* = \arg \min_\omega \frac{1}{m}{}\sum_{i=1}^{m} L(y_i, f(x_i; \omega)) + \lambda\ \Phi(\omega) \qquad(3) ω∗=argωminm1i=1∑mL(yi,f(xi;ω))+λ Φ(ω)(3)
其中m表示樣本的數量。對于邏輯回歸，其loss function是log損失，這可以通過極大似然估計進行推導得到。
首先，給定一個樣本 x x x，可以使用一個線性函數對自變量進行線性組合，即上述的（2）式子：
z = ω 0 + ω 1 x 1 + ω 2 x 2 + . . . . . . + ω n x n = ∑ i = 0 n ω i x i = ω T X ( 4 ) z={\omega}_0+{\omega}_1x_1+{\omega}_2x_2+......+{\omega}_nx_n=\sum_{i=0}^n{\omega}_ix_i=\mathbf{\omega^TX} \qquad(4) z=ω0+ω1x1+ω2x2+......+ωnxn=i=0∑nωixi=ωTX(4)
根據sigmoid函數，我們可以得出預測函數的表達式為：
h ω ( x ) = g ( ω T x ) = 1 1 + e − ω T x ( 5 ) h_{\omega}(x) = g(\omega^Tx) = \frac{1}{1 + e^{-\omega^Tx}} \qquad(5) hω(x)=g(ωTx)=1+e−ωTx1(5)
上式表示 y = 1 y=1 y=1的預測函數為 h ω ( x ) h_{\omega}(x) hω(x)。在這裡，假設因變量 y y y服從伯努利分布，那麼可以得到下列兩個式子：
p ( y = 1 ∣ x ) = h ω ( x ) ( 6 ) p ( y = 0 ∣ x ) = 1 − h ω ( x ) ( 7 ) \begin{aligned} p(y=1 | x) &= h_{\omega} (x) \quad\qquad(6)\\ p(y=0 | x) &= 1 - h_{\omega} (x) \qquad(7) \end{aligned} p(y=1∣x)p(y=0∣x)=hω(x)(6)=1−hω(x)(7)
而對于上面的兩個表達式，通過觀察，我們發現，可以将其合并為以下表達式：
p ( y ∣ x ) = h ω ( x ) y ( 1 − h ω ( x ) ) 1 − y ( 8 ) p(y | x) = h_{\omega} (x)^y (1-h_{\omega} (x))^{1-y} \qquad(8) p(y∣x)=hω(x)y(1−hω(x))1−y(8)
根據上面的式子，給定一定的樣本之後，我們可以構造出似然函數，然後可以使用極大似然估計MLE的思想來求解參數。但是，為了滿足最小化風險理論，我們可以将MLE的思想轉化為最小化風險化理論，最大化似然函數其實就等價于最小化負的似然函數。對于MLE，就是利用已知的樣本分布，找到最有可能（即最大機率）導緻這種分布的參數值；或者說是什麼樣的參數才能使我們觀測到目前這組資料的機率最大。使用MLE推導LR的loss function的過程如下。
首先，根據上面的假設，寫出相應的極大似然函數（假定有 m m m個樣本）：
L ( ω ) = ∏ i = 1 m p ( y i ∣ x i ; ω ) = ∏ i = 1 m h ω ( x i ) y i ( 1 − h ω ( x i ) 1 − y i ( 9 ) \begin{aligned} L(\omega)&= \prod_{i=1}^{m} p(y_i | x_i; \omega) \\ &= \prod_{i=1}^{m} h_{\omega} (x_i)^{y_i} (1-h_{\omega} (x_i)^{1-y_i} \\ \end{aligned} \qquad(9) L(ω)=i=1∏mp(yi∣xi;ω)=i=1∏mhω(xi)yi(1−hω(xi)1−yi(9)
上述式子中的 ω \omega ω及 x i x_i xi均為向量，并未顯示其轉置。
直接對上面的式子求導會不友善，是以，為了便于計算，我們可以對似然函數取對數，經過化簡可以得到下式的推導結果：
log L ( ω ) = ∑ i = 1 m log [ ( h ω ( x i ) y i ( 1 − h ω ( x i ) ) 1 − y i ) ] = ∑ i = 1 m [ y i log h ω ( x i ) + ( 1 − y i ) log ( 1 − h ω ( x i ) ) ] ( 10 ) \begin{aligned} \log L(\omega)&= \sum_{i=1}^{m} \log \left [ (h_{\omega} (x_i)^{y_i} (1-h_{\omega} (x_i))^{1-y_i}) \right ] \\ &= \sum_{i=1}^{m} \left [ y_i \log h_{\omega} (x_i) + (1-y_i) \log(1-h_{\omega} (x_i)) \right ] \\ \end{aligned} \qquad(10) logL(ω)=i=1∑mlog[(hω(xi)yi(1−hω(xi))1−yi)]=i=1∑m[yiloghω(xi)+(1−yi)log(1−hω(xi))](10)
是以，損失函數可以通過最小化負的似然函數得到，即下式：
J ( ω ) = − 1 m ∑ i = 1 m [ y i log h ω ( x i ) + ( 1 − y i ) log ( 1 − h ω ( x i ) ] ( 11 ) J(\omega) = - \frac{1}{m} \sum_{i=1}^m \left [ y_i \log h_{\omega}(x_i) + (1-y_i) \log(1-h_{\omega}(x_i) \right ] \qquad(11) J(ω)=−m1i=1∑m[yiloghω(xi)+(1−yi)log(1−hω(xi)](11)
在周志華版的機器學習中，将sigmiod函數代入 h ω ( x i ) h_{\omega}(x_i) hω(xi)，并使用ln代替log，上述公式表示為：
J ( ω ) = − 1 m ∑ i = 1 m [ y i ln h ω ( x i ) + ( 1 − y i ) ln ( 1 − h ω ( x i ) ] = − 1 m ∑ i = 1 m [ y i ln 1 1 + e − ω x i + ( 1 − y i ) ln e − ω x i 1 + e − ω x i ] = − 1 m ∑ i = 1 m [ ln 1 1 + e ω x i + y i ln 1 e − ω x i ] = 1 m ∑ i = 1 m [ − y i w x i + ln ( 1 + e ω x i ) ] ( 12 ) \begin{aligned} J(\omega) &= - \frac{1}{m} \sum_{i=1}^m \left [ y_i \ln h_{\omega}(x_i) + (1-y_i) \ln(1-h_{\omega}(x_i) \right ]\\ &=- \frac{1}{m} \sum_{i=1}^m \left [ y_i\ln \frac{1}{1+e^{-\omega x_i}}+(1-y_i)\ln \frac{e^{-\omega x_i}}{1+e^{-\omega x_i}}\right ]\\ &=- \frac{1}{m} \sum_{i=1}^m \left [ \ln \frac{1}{1+e^{\omega x_i}} + y_i \ln \frac{1}{e^{-\omega x_i}}\right ]\\ &= \frac{1}{m} \sum_{i=1}^m \left [ -y_iwx_i + \ln(1+e^{\omega x_i})\right ] \end{aligned} \qquad(12) J(ω)=−m1i=1∑m[yilnhω(xi)+(1−yi)ln(1−hω(xi)]=−m1i=1∑m[yiln1+e−ωxi1+(1−yi)ln1+e−ωxie−ωxi]=−m1i=1∑m[ln1+eωxi1+yilne−ωxi1]=m1i=1∑m[−yiwxi+ln(1+eωxi)](12)
在某些資料上，還有另一種損失函數的表達形式，但本質是一樣的，如下【推導見下面1.4】：
J ( ω ) = 1 m ∑ i = 1 m l o g ( 1 + e − y i ω x ) ( 13 ) J(\omega) = \frac{1}{m} \sum_{i=1}^m log(1 + e^{-y_i \omega x}) \qquad(13) J(ω)=m1i=1∑mlog(1+e−yiωx)(13)
1.3 梯度下降
這裡就以梯度下降為例對邏輯回歸進行求解，其疊代公式的推導過程如下：
∂ J ( ω ) ∂ ω j = − 1 m ∑ i m [ y i ( 1 − h ω ( x i ) ) ⋅ ( − x i , j ) + ( 1 − y i ) h ω ( x i ) ⋅ ( x i , j ) ] = − 1 m ∑ i m ( − y i ⋅ x i , j + h ω ( x i ) ⋅ x i , j ) = − 1 m ∑ i m ( h ω ( x i ) − y i ) x i , j ( 14 ) \begin{aligned} \frac{ \partial J(\omega)} {\partial \omega_j}&= -\frac{1}{m} \sum_{i}^{m} \left [ y_i(1 - h_{\omega}(x_i)) \cdot (-x_{i,j}) + (1 - y_i) h_{\omega} (x_i) \cdot (x_{i,j}) \right ]\\ & = - \frac{1}{m} \sum_{i}^{m} (-y_i \cdot x_{i,j} + h_{\omega}(x_i) \cdot x_{i,j}) \\ & = -\frac{1}{m} \sum_{i}^{m} (h_{\omega}(x_i) - y_i) x_{i,j} \end{aligned} \qquad(14) ∂ωj∂J(ω)=−m1i∑m[yi(1−hω(xi))⋅(−xi,j)+(1−yi)hω(xi)⋅(xi,j)]=−m1i∑m(−yi⋅xi,j+hω(xi)⋅xi,j)=−m1i∑m(hω(xi)−yi)xi,j(14)
上述中 x i , j x_{i,j} xi,j表示第 i i i個樣本的第 j j j個屬性的取值。
于是， ω \omega ω的更新方式為：
ω j + 1 = ω j − α ∑ i = 1 m ( h ω ( x i ) − y i ) x x , j \omega_{j+1} = \omega_j - \alpha \sum_{i=1}^{m} (h_{\omega}(x_i) - y_i) x_{x,j} ωj+1=ωj−αi=1∑m(hω(xi)−yi)xx,j
對于随機梯度下降，每次隻取一個樣本，則 ω \omega ω的更新方式為：
ω j + 1 = ω j − α ( h ω ( x ) − y ) x j \omega_{j+1} = \omega_j - \alpha (h_{\omega}(x)- y) x_{j} ωj+1=ωj−α(hω(x)−y)xj
其中 x x x為這個樣本的特征值， y y y為這個樣本的真實值， x j x_j xj為這個樣本第 j j j個屬性的值。
這使用周志華版的損失函數更容易得出這個結論。
1.4 另一種形式的損失函數及其梯度
與上面相同，根據sigmoid函數，我們可以得出預測函數的表達式為：
h ω ( x ) = g ( ω T x ) = 1 1 + e − ω T x h_{\omega}(x) = g(\omega^Tx) = \frac{1}{1 + e^{-\omega^Tx}} hω(x)=g(ωTx)=1+e−ωTx1
上式表示 y = 1 y=1 y=1的預測函數為 h ω ( x ) h_{\omega}(x) hω(x)。
但與上面不同，我們假設樣本的分布為{-1,1}，則
p ( y = 1 ∣ x ) = h ω ( x ) p(y=1 | x) = h_{\omega} (x) p(y=1∣x)=hω(x)
p ( y = − 1 ∣ x ) = 1 − h ω ( x ) p(y=-1 | x) = 1 - h_{\omega} (x) p(y=−1∣x)=1−hω(x)
對于sigmoid函數，有以下特性（簡單推導一下就可以得到）：
h ( − x ) = 1 − h ( x ) h(-x) = 1 - h(x) h(−x)=1−h(x)
于是(14)(15)式可以表示為：
p ( y ∣ x ) = h ω ( y x ) p(y|x) = h_\omega(yx) p(y∣x)=hω(yx)
同樣，我們使用MLE作估計，
L ( ω ) = ∏ i = 1 m p ( y i ∣ x i ; ω ) = ∏ i = 1 m h ω ( y i x i ) = ∏ i = 1 m 1 1 + e − y i w x i \begin{aligned} L(\omega)&= \prod_{i=1}^{m} p(y_i | x_i; \omega) \\ &= \prod_{i=1}^{m} h_\omega(y_i x_i)\\ &= \prod_{i=1}^{m} \frac{1}{1+e^{-y_iwx_i}} \end{aligned} L(ω)=i=1∏mp(yi∣xi;ω)=i=1∏mhω(yixi)=i=1∏m1+e−yiwxi1
對上式取對數及負值，得到損失為：
− log L ( ω ) = − log ∏ i = 1 m p ( y i ∣ x i ; ω ) = − ∑ i = 1 m log p ( y i ∣ x i ; ω ) = − ∑ i = 1 m log 1 1 + e − y i w x i = ∑ i = 1 m log ( 1 + e − y i w x i ) \begin{aligned} -\log L(\omega)&= -\log \prod_{i=1}^{m} p(y_i | x_i; \omega) \\ &= -\sum_{i=1}^{m} \log p(y_i | x_i; \omega) \\ &= -\sum_{i=1}^{m} \log \frac{1}{1+e^{-y_iwx_i}}\\ &= \sum_{i=1}^{m} \log(1+e^{-y_iwx_i})\\ \end{aligned} −logL(ω)=−logi=1∏mp(yi∣xi;ω)=−i=1∑mlogp(yi∣xi;ω)=−i=1∑mlog1+e−yiwxi1=i=1∑mlog(1+e−yiwxi)
即對于每一個樣本，損失函數為：
L ( ω ) = log ( 1 + e − y i w x i ) L(\omega)=\log(1+e^{-y_iwx_i}) L(ω)=log(1+e−yiwxi)
對上式求梯度，容易得到：
∂ J ( ω ) ∂ ω j = − y i x i 1 + e y i ω x i \begin{aligned} \frac{ \partial J(\omega)} {\partial \omega_j}&= \frac{-y_i x_i}{1+e^{y_i \omega x_i}} \end{aligned} ∂ωj∂J(ω)=1+eyiωxi−yixi
2、FOBOS與RDA
2.1 FOBOS基本原理
FOBOS算法由John Duchi和Yoram Singer提出，是梯度下降的一個變種。
與梯度下降不同，它将權重的更新分為2個步驟：
W t + 1 2 = W t − η t G t n W t + 1 = arg min { 1 2 ∥ W − W t + 1 2 ∥ 2 + η ( t + 1 2 ) ψ ( W ) } \begin{aligned} W_{t+\frac{1}{2}}&=W_t-\eta_tG_t \\n W_{t+1}&=\arg\min\{\frac{1}{2}\|W-W_{t+\frac{1}{2}}\|^2+\eta_{(t+\frac{1}{2})}\psi(W)\} \end{aligned} Wt+21nWt+1=Wt−ηtGt=argmin{21∥W−Wt+21∥2+η(t+21)ψ(W)}
從上面的2個步驟可以看出：
第一個步驟是一個标準的梯度下降。
第二個步驟是對梯度下降的結果進行微調。這裡可以分為2部分：（1）前半部分保證了微調發生在第一個步驟結果（取梯度下降結果）的附近。（2）後半部分用于處理正則化，産生稀疏性。
** 根據次梯度理論的推斷，可以得出 W ( t + 1 ) W_{(t+1)} W(t+1)不僅僅與疊代前的狀态 W t W_t Wt有關，而且與疊代後的$$相關**
2.2 L1-FOBOS
FOBOS在L1正則化條件下，特征權重的更新方式為：（推導過程暫略）
ω t + 1 , i = s g n ( ω t , i − η t g t , i ) m a x { 0 , ∣ ω t , i − η t g t , i ∣ − η t + 1 2 λ } \omega_{t+1,i}=sgn(\omega_{t,i}-\eta_tg_{t,i})max\{0,|\omega_{t,i}-\eta_tg_{t,i}|-\eta_{t+\frac{1}{2}}\lambda\} ωt+1,i=sgn(ωt,i−ηtgt,i)max{0,∣ωt,i−ηtgt,i∣−ηt+21λ}
其中 g t , i g_{t,i} gt,i為梯度在次元i上的取值
2.3 RDA基本原理
簡單截斷、TG、FOBOS都是建立在SGD基礎上的一個變種，屬于梯度下降類型的方法，這類方法的精度比較高，同時也能得到一定的稀疏性。而RDA是從另一個方面來求解，它的精度比FOBOS等略差，但它更有效的提升了稀疏性。
在RDA中，特征權重的更新政策為：
W t + 1 = arg min { 1 t ∑ r = 1 t < G r , W > + ψ ( W ) + β t t h ( W ) } W_{t+1}=\arg\min\{\frac{1}{t}\sum_{r=1}^{t}<G^{r},W>+\psi(W)+\frac{\beta_t}{t}h(W)\} Wt+1=argmin{t1r=1∑t<Gr,W>+ψ(W)+tβth(W)}
其中 < G r , W > <G^{r},W> <Gr,W>表示梯度 G r G^r Gr對W的積分平均值（積分中值）； ψ ( W ) \psi(W) ψ(W)為正則項； h ( W ) h(W) h(W)為一個輔助的嚴格的凸函數； β t ∣ t ≥ 1 {\beta_t|t\ge1} βt∣t≥1是一個非負且非自減序列。
2.4 L1-RDA
在L1正則化條件下，RDA的各個次元的權重更新方式為：
ω t + 1 , i = { 0 , if ∣ g ‾ t , i ∣ < λ − ( t r ( g ‾ t , i − λ s g n ( g ‾ t , i ) ) , otherwise \omega_{t+1,i} = \begin{cases} 0, & \text{if $|\overline g_{t,i}|<\lambda$} \\ -(\frac{\sqrt{t}}{r}(\overline g_{t,i}-\lambda sgn(\overline g_{t,i})), & \text{otherwise} \\ \end{cases} ωt+1,i={0,−(rt
(gt,i−λsgn(gt,i)),if ∣gt,i∣<λotherwise
亦即當某個次元上的累積梯度平均值的絕對值 ∣ g ‾ t , i ∣ |\overline g_{t,i}| ∣gt,i∣小于門檻值 λ \lambda λ時，該次元權重被置為0。
3、FTRL
理論及實驗均證明，L1-FOBOS這類基于梯度下降的算法有比較高的精度，但L1-RDA卻能在損失一定精度的情況下産生更好的稀疏性。
把這二者的優點結合成一個算法，這就是FTRL算法的來源。
3.1 從L1-FOBOS和L1-RDA推導FTRL
我們令 η t + 1 2 = η t = Θ ( 1 t ) \eta_{t+\frac{1}{2}}=\eta_t=\Theta(\frac{1}{\sqrt{t}}) ηt+21=ηt=Θ(t
1)是一個非增正序列，同時代入L1正則項，得到L1-FOBOS的形式如下：
W t + 1 2 = W t − η t G t W t + 1 = arg min { 1 2 ∥ W − W t + 1 2 ∥ 2 + η t λ ∥ W ∥ 1 } \begin{aligned} W_{t+\frac{1}{2}}&=W_t-\eta_tG_t \\ W_{t+1}&=\arg\min\{\frac{1}{2}\|W-W_{t+\frac{1}{2}}\|^2+\eta_{t}\lambda\|W\|_1\} \end{aligned} Wt+21Wt+1=Wt−ηtGt=argmin{21∥W−Wt+21∥2+ηtλ∥W∥1}
将這2個公式合并到一起，得到L1-FOBOS的形式如下：
W t + 1 = arg min { 1 2 ∥ W − W t + η t G t ∥ 2 + η t λ ∥ W ∥ 1 } W_{t+1}=\arg\min\{\frac{1}{2}\|W-W_t+\eta_tG_t\|^2+\eta_{t}\lambda\|W\|_1\} Wt+1=argmin{21∥W−Wt+ηtGt∥2+ηtλ∥W∥1}
将上式分解為N個獨立的次元進行最優化求解：
w i = arg min { 1 2 ∥ w i − w t , i + η t g t , i ∥ 2 + η t λ ∣ w t , i ∣ 1 } = arg min { 1 2 ( w i − w t , i ) 2 + 1 2 ( η t g t , i ) 2 + w i η t g t , i − w t , i η t g t , i + η t λ ∣ w i ∣ } = arg min { w i g t , i + λ ∣ w i ∣ + 1 2 η t ( w i − w t , i ) 2 + ∣ η t 2 g t , i 2 − w t , i g t , i ∣ } \begin{aligned} w_i&=\arg\min\{\frac{1}{2}\|w_i-w_{t,i}+\eta_tg_{t,i}\|^2+\eta_{t}\lambda|w_{t,i}|_1\} \\ &=\arg\min\{\frac{1}{2}(w_i-w_{t,i})^2+\frac{1}{2}(\eta_t g_{t,i})^2+w_i\eta_tg_{t,i}-w_{t,i}\eta_tg_{t,i}+\eta_t\lambda|w_i|\}\\ &=\arg\min\{w_ig_{t,i}+\lambda|w_i|+\frac{1}{2\eta_t}(w_i-w_{t,i})^2+|\frac{\eta_t}{2}g_{t,i}^2-w_{t,i}g_{t,i}|\} \end{aligned} wi=argmin{21∥wi−wt,i+ηtgt,i∥2+ηtλ∣wt,i∣1}=argmin{21(wi−wt,i)2+21(ηtgt,i)2+wiηtgt,i−wt,iηtgt,i+ηtλ∣wi∣}=argmin{wigt,i+λ∣wi∣+2ηt1(wi−wt,i)2+∣2ηtgt,i2−wt,igt,i∣}
-
上述推導的最後一步是通過除以 η t \eta_t ηt得到的。
由于上式中的最後一項 ∣ η t 2 g t , i 2 − w t , i g t , i ∣ |\frac{\eta_t}{2}g_{t,i}^2-w_{t,i}g_{t,i}| ∣2ηtgt,i2−wt,igt,i∣是一個與 w i w_i wi無關的量，是以上式可簡化為：
w i = arg min { w i g t , i + λ ∣ w i ∣ + 1 2 η t ( w i − w t , i ) 2 } w_i=\arg\min\{w_ig_{t,i}+\lambda|w_i|+\frac{1}{2\eta_t}(w_i-w_{t,i})^2\} wi=argmin{wigt,i+λ∣wi∣+2ηt1(wi−wt,i)2}
把N個獨立優化的次元重新合并，L1-FOBOS可寫成以下形式：
W t + 1 = arg min { G t W + λ ∥ W ∥ 1 + 1 2 η t ∥ W − W t ∥ 2 2 } W_{t+1}=\arg\min\{G_tW+\lambda\|W\|_1+\frac{1}{2\eta_t}\|W-W_t\|_2^2\} Wt+1=argmin{GtW+λ∥W∥1+2ηt1∥W−Wt∥22}
另一方面，L1-RDA可以表達為：
W t + 1 = arg min { G ( 1 : t ) W + t λ ∥ W ∥ 1 + 1 2 η t ∥ W − 0 ∥ 2 2 } W_{t+1}=\arg\min\{G_{(1:t)}W+t\lambda\|W\|_1+\frac{1}{2\eta_t}\|W-0\|_2^2\} Wt+1=argmin{G(1:t)W+tλ∥W∥1+2ηt1∥W−0∥22}
其中 G ( 1 : t ) = ∑ s = 1 t G s G_{(1:t)}=\sum_{s=1}{t}G_s G(1:t)=∑s=1tGs。
我們令 σ s = 1 η s − 1 η s − 1 \sigma_s=\frac{1}{\eta_s}-\frac{1}{\eta_{s-1}} σs=ηs1−ηs−11，可以得到 σ ( 1 : t ) = 1 η t \sigma_{(1:t)}=\frac{1}{\eta_t} σ(1:t)=ηt1。那麼L1-FOBOS與L1-RDA可以寫為以下格式：
W t + 1 = arg min { G t W + λ ∥ W ∥ 1 + 1 2 σ ( 1 : t ) ∥ W − W t ∥ 2 2 } W t + 1 = arg min { G ( 1 : t ) W + t λ ∥ W ∥ 1 + 1 2 σ ( 1 : t ) ∥ W − 0 ∥ 2 2 } \begin{aligned} W_{t+1}&=\arg\min\{G_tW+\lambda\|W\|_1+\frac{1}{2}\sigma_{(1:t)}\|W-W_t\|_2^2\}\\ W_{t+1}&=\arg\min\{G_{(1:t)}W+t\lambda\|W\|_1+\frac{1}{2}\sigma_{(1:t)}\|W-0\|_2^2\} \end{aligned} Wt+1Wt+1=argmin{GtW+λ∥W∥1+21σ(1:t)∥W−Wt∥22}=argmin{G(1:t)W+tλ∥W∥1+21σ(1:t)∥W−0∥22}
比較以上2式的差別：
- （1）L1-FOBOS考慮的是目前梯度的影響，L1-RDA則考慮了累積影響。
- （2）L1-FOBOS限制 W t + 1 W_{t+1} Wt+1不能離 W t W_t Wt太遠，而L1-RDA的W則不能離0太遠，是以後者更容易産生稀疏性。
3.2 FTRL權重更新的最終形式
在google2010公布的理論文章中并沒有使用L2正則項，但在2013年公布工程實施方案時引入了L2。
是以，綜合上述的L1-FOBOS及L1-RDA，FTRL算法的權重更新方式為：
W t + 1 = arg min { G ( 1 : t ) W + λ 1 ∥ W ∥ 1 + λ 2 ∥ W ∥ 2 2 + 1 2 ∑ s = 1 t ( σ s ∥ W − W s ∥ 2 2 ) } W_{t+1}=\arg\min\{G_{(1:t)}W+\lambda_1\|W\|_1+\lambda_2\|W\|_2^2+\frac{1}{2}\sum_{s=1}^t(\sigma_s\|W-W_s\|_2^2)\} Wt+1=argmin{G(1:t)W+λ1∥W∥1+λ2∥W∥22+21s=1∑t(σs∥W−Ws∥22)}
将上式展開，得到
W t + 1 = arg min { ( G ( 1 : t ) − ∑ s = 1 t σ s W s ) W + λ 1 ∥ W ∥ 1 + 1 2 ( λ 2 + ∑ s = 1 t σ s ) ∥ W ∥ 2 + 1 2 ∑ s = 1 t σ s ∥ W s ∥ 2 2 } W_{t+1}=\arg\min\{(G_{(1:t)}-\sum_{s=1}^t\sigma_sW_s)W+\lambda_1\|W\|_1+\frac{1}{2}(\lambda_2+\sum_{s=1}^t\sigma_s)\|W\|^2+\frac{1}{2}\sum_{s=1}^{t}\sigma_s\|W_s\|_2^2\} Wt+1=argmin{(G(1:t)−s=1∑tσsWs)W+λ1∥W∥1+21(λ2+s=1∑tσs)∥W∥2+21s=1∑tσs∥Ws∥22}
由于上式的最後一項相對于W來說是一個常數，同時令 Z t = G ( 1 : t ) − ∑ ( s = 1 ) t σ s W s Z_t=G_{(1:t)}-\sum_{(s=1)}^t\sigma_sW_s Zt=G(1:t)−∑(s=1)tσsWs，上式可表示為：
W t + 1 = arg min { Z t W + λ 1 ∥ W ∥ 1 + 1 2 ( λ 2 + ∑ s = 1 t σ s ) ∥ W ∥ 2 } W_{t+1}=\arg\min\{Z_tW+\lambda_1\|W\|_1+\frac{1}{2}(\lambda_2+\sum_{s=1}^t\sigma_s)\|W\|^2\} Wt+1=argmin{ZtW+λ1∥W∥1+21(λ2+s=1∑tσs)∥W∥2}
各個次元可以獨立表示為：
w i + 1 = arg min { z t , i w i + λ 1 ∣ w i ∣ + 1 2 ( λ 2 + ∑ s = 1 t σ s ) w i 2 } w_{i+1}=\arg\min\{z_{t,i}w_i+\lambda_1|w_i|+\frac{1}{2}(\lambda_2+\sum_{s=1}^{t}\sigma_s)w_i^2\} wi+1=argmin{zt,iwi+λ1∣wi∣+21(λ2+s=1∑tσs)wi2}
使用與L1-FOBOS相同的分析方法可以得到：
ω t + 1 , i = { 0 , if ∣ z i ∣ < λ 1 − ( λ 2 + ∑ s = 1 t σ s ) − 1 ( z t , i − s g n ( z t , i ) λ 1 ) , otherwise \omega_{t+1,i} = \begin{cases} 0, & \text{if $|z_i|<\lambda_1$} \\ -(\lambda_2+\sum_{s=1}^t\sigma_s)^{-1}(z_{t,i}-sgn(z_{t,i})\lambda_1), & \text{otherwise} \\ \end{cases} ωt+1,i={0,−(λ2+∑s=1tσs)−1(zt,i−sgn(zt,i)λ1),if ∣zi∣<λ1otherwise
根據上面的定義:
σ ( 1 : t ) = ∑ s = 1 t σ s = 1 η t \sigma_{(1:t)}=\sum_{s=1}^t\sigma_s=\frac{1}{\eta_t} σ(1:t)=s=1∑tσs=ηt1
我們使用下面介紹的學習率，以及令 n i = ∑ g i 2 n_i=\sum g_i^2 ni=∑gi2，則可以得到FTRL的最終形式：
ω i = { 0 , if ∣ z i ∣ < λ 1 − ( β + n I α + λ 2 ) − 1 ( z i − s g n ( z i ) λ 1 ) , otherwise \omega_i = \begin{cases} 0, & \text{if $|z_i|<\lambda_1$} \\ -(\frac{\beta+\sqrt{n_I}}{\alpha}+\lambda_2)^{-1}(z_i-sgn(z_i)\lambda_1), & \text{otherwise} \\ \end{cases} ωi={0,−(αβ+nI
+λ2)−1(zi−sgn(zi)λ1),if ∣zi∣<λ1otherwise
3.3 學習率
1、per-coordinate learning rate
在FTRL中，學習率的定義如下：
η t , i = α β + ∑ s = 1 t g s , i 2 \eta_{t,i}=\frac{\alpha}{\beta+\sqrt{\sum_{s=1}^tg_{s,i}^2}} ηt,i=β+∑s=1tgs,i2
α
其中 α β \alpha\beta αβ是自定義的參數。
在一般梯度下降算法中，使用的是一個全局的學習率政策： η t = 1 t \eta_t=\frac{1}{\sqrt{t}} ηt=t
1。這個政策保證了學習率是一個正的非增序列，這個值對于每一個特征都是一樣的。
考慮一個極端的情況，我們有多個稀疏特征，其中一個特征 x 1 x_1 x1出現非常頻繁，而另一個特征 x 2 x_2 x2很少出現。比如第一個樣本， x 1 x_1 x1和 x 2 x_2 x2同時出現了，但接下來的99個樣本都隻出現了 x 1 x_1 x1，然後第100個樣本 x 2 x_2 x2又出來了，由于此時的學習率為 1 100 \frac{1}{\sqrt{100}} 100
1，遠小于第一個樣的影響了。也就是說假如第一個樣本是正樣本，第10個樣本是負樣本，此時由于學習率的不同，模型會認為 x 2 x_2 x2會是一個有用的正相關的特征，即 ω > 0 \omega>0 ω>0。但事實上，這個特征隻出現了2次，而且一正一負，是以這應該是一個無用的特征，即 ω = 0 \omega=0 ω=0。
在FTRL中，我們會使用一個特征的累積梯度，由于中間的99個資料沒有這個特征，是以其對應的梯度為0，是以第二次的負樣本對應的學習率隻是略小于第一個正樣本。
3.4 工程實作計算過程
3.4.1 一些定義
對于每一個樣本，我們計算以下數值。
（1） p t p_t pt
使用目前的 ω \omega ω代入sigmoid函數得出的預測值，即：
p = 1 1 + e − ( ∑ i = 1 n ω i x i ) p=\frac{1}{1+e^{-(\sum_{i=1}^n\omega_ix_i)}} p=1+e−(∑i=1nωixi)1
（2） g i g_i gi
損失函數在某一個次元上的梯度，對于邏輯回歸而言：
g i = ( p − y ) x i g_i=(p-y)x_i gi=(p−y)xi
其中y為目前樣本的實際值，即0或者1。
（3） n i n_i ni
這是該次元梯度 g i 2 g_i^2 gi2的累積值，即：
n i = n i + g i 2 n_i=n_i+g_i^2 ni=ni+gi2
（4） η i \eta_i ηi
這是該次元的學習率，它與累積梯度有關。定義為：
η i = α β + ∑ s = 1 t ( g i s ) 2 = α β + n i \eta_i=\frac{\alpha}{\beta+\sqrt{\sum_{s=1}^t(g_i^s)^2}}=\frac{\alpha}{\beta+\sqrt{n_i}} ηi=β+∑s=1t(gis)2
α=β+ni
α
其中 α β \alpha\beta αβ為使用者定義的2個參數。
（5） σ i \sigma_i σi
σ i \sigma_i σi是一個中間計算值，沒有實際含義，其定義為：
σ i = 1 η t , i − 1 η t − 1 , i = 1 α ( n i + g i 2 − n i ) \sigma_i=\frac{1}{\eta_{t,i}}-\frac{1}{\eta_{t-1,i}}=\frac{1}{\alpha}(\sqrt{n_i+g_i^2}-\sqrt{n_i}) σi=ηt,i1−ηt−1,i1=α1(ni+gi2
−ni
)
（6） z i z_i zi
z i z_i zi也是一個輔助計算的中間值，它的定義為：
z t , i = g ( 1 : t ) − ∑ s = 1 t σ s , i ω s , i z_{t,i}=g^{(1:t)}-\sum_{s=1}^t{\sigma_{s,i}\omega_{s,i}} zt,i=g(1:t)−s=1∑tσs,iωs,i
于是 z i z_i zi的更新為：
z t − z t − 1 = g t − σ t ω t z_t-z_{t-1}=g_t-\sigma_{t}\omega_{t} zt−zt−1=gt−σtωt
即：
z i = z i + g t − σ i ω i z_i=z_i+g_t-\sigma_i\omega_i zi=zi+gt−σiωi
3.4.2 FTRL算法
（1）設定以下4個輸入參數，這些參數根據經驗而定，可以參考以下資料：
α = 0.1 , β = 1 , λ 1 = 1 , λ 2 = 1 \alpha=0.1,\beta=1,\lambda_1=1,\lambda_2=1 α=0.1,β=1,λ1=1,λ2=1
（2）初始化以下數值：
z i = 0 , n i = 0 z_i=0,n_i=0 zi=0,ni=0
（3）對于每一個樣本的所帶的每一個次元,更新 ω \omega ω
ω i = { 0 , if ∣ z i ∣ < λ 1 − ( β + n I α + λ 2 ) − 1 ( z i − s g n ( z i ) λ 1 ) , otherwise \omega_i = \begin{cases} 0, & \text{if $|z_i|<\lambda_1$} \\ -(\frac{\beta+\sqrt{n_I}}{\alpha}+\lambda_2)^{-1}(z_i-sgn(z_i)\lambda_1), & \text{otherwise} \\ \end{cases} ωi={0,−(αβ+nI
+λ2)−1(zi−sgn(zi)λ1),if ∣zi∣<λ1otherwise
（4）使用上面更新後的 ω \omega ω，預測這個樣本的值，即代入sigmoid函數計算 p t p_t pt
p = 1 1 + e − ( ∑ i = 1 n ω i x i ) p=\frac{1}{1+e^{-(\sum_{i=1}^n\omega_ix_i)}} p=1+e−(∑i=1nωixi)1
（5）對于每一個樣本的每一個次元，更新 g i , σ i , z i , n i g_i,\sigma_i,z_i,n_i gi,σi,zi,ni，即上面所說的：
g i = ( p − y ) x i σ i = 1 α ( n i + g i 2 − n i ) z i = z i + g t − σ i ω i n i = n i + g i 2 \begin{aligned} g_i&=(p-y)x_i \\ \sigma_i&=\frac{1}{\alpha}(\sqrt{n_i+g_i^2}-\sqrt{n_i})\\ z_i&=z_i+g_t-\sigma_i\omega_i\\ n_i&=n_i+g_i^2 \end{aligned} giσizini=(p−y)xi=α1(ni+gi2
−ni
)=zi+gt−σiωi=ni+gi2
4、FTRL的工程應用
這裡隻列出了google提供的一些建議，我們自身的工程應用并不包含在内。
（1）減少樣本的數量
- Poisson Inclusion：以p的機率接受樣本
- Bloom Filter Inclusion：隻有當特征出現次數達到一定數量後，特征才會被加入模型
（2）使用更少的位來進行浮點數編碼
一般而言，特征對應的 ω \omega ω在(-2,2)之間，是以我們可以将32，或者64位的浮點數編碼規則改為q2.13編碼方式，即2位整數，1位小數點，13位小數。
（3）多個類似的模型
把多個同類型/相似的模型放在一起儲存，可以不需要記錄多個key，隻需要記錄一次Key，以及各個模型中的 ω \omega ω。這可以節省記憶體、帶寬、CPU、存儲。
（4）隻儲存一個模型
在上面的基礎上更進一步，所有模型共用一份 ω \omega ω，以及以一個bit來記錄本模型有哪些特征。當模型更新某個 ω \omega ω後，取它與之前那個值的平均值。
與共用一個模型對比，好處是記錄了這個模型有哪些有效特征，共用模型就無法區分了。
（5）近似計算學習率
隻使用正樣本P與負樣本資料N來近似估計梯度的平方和，前提是假設特征有類似的分布。
∑ g i 2 = P N P + N \sum{g_i^2}=\frac{PN}{P+N} ∑gi2=P+NPN
（6）減少負樣本數量
減少負樣本數量，然後在訓練時彌補其損失。
![邏輯回歸與線性回歸算法梳理邏輯回歸與線性回歸算法[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)