線上最優化求解(Online Optimization)之二：截斷梯度法(TG)

​

在預備篇中我們做了一些熱身，并且介紹了L1正則化在Online模式下也不能産生較好的稀疏性，而稀疏性對于高維特征向量以及大資料集又特别的重要。是以，從現在開始，我們沿着提升模型稀疏性的主線進行算法介紹。

為了得到稀疏的特征權重 ，最簡單粗暴的方式就是設定一個門檻值，當

的某次元上系數小于這個門檻值時将其設定為

稱作簡單截斷）。這種方法實作起來很簡單，也容易了解。但實際中（尤其在OGD裡面）

的某個系數比較小可能是因為該次元訓練不足引起的，簡單進行截斷會造成這部分特征的丢失。

截斷梯度法（TG, Truncated Gradient）是由John Langford，Lihong Li和Tong Zhang在2009年提出[1]，實際上是對簡單截斷的一種改進。下面首先描述一下L1正則化和簡單截斷的方法，然後我們再來看TG對簡單截斷的改進以及這三種方法在特定條件下的轉化。

1. L1正則化法

由于L1正則項在0處不可導，往往會造成平滑的凸優化問題變成非平滑凸優化問題，是以在每次疊代中采用次梯度[2](Subgradient)計算L1正則項的梯度。權重更新方式為：

  公式（1）

 注意，這裡

是一個标量，且

，為L1正則化參數；

為符号函數，如果

是一個向量，

是向量的一個次元，那麼有

;

為學習率，通常将其設定成

的函數；

代表了第t次疊代中損失函數的梯度,，由于OGD每次僅根據觀測到的一個樣本進行權重更新，是以也不再使用區分樣本的下标j。

2. 簡單截斷法

以k為視窗，當t/k不為整數時采用标準的SGD進行疊代，當t/k為整數時，采用如下權重更新方式：

    公式(2)

 注意，這裡面

是一個正數；如果

。

3. 截斷梯度法(TG)

上述的簡單截斷法被TG的作者形容為too aggressive，是以TG在此基礎上進行了改進，同樣是采用截斷的方式，但是比較不那麼粗暴。采用相同的方式表示為：

   公式(3)

其中

。TG同樣是以k為視窗，每k步進行一次截斷。當t/k不為整數時

，當t/k為整數時

。從公式(3)可以看出，

和

決定了

的稀疏程度，這兩個值越大，則稀疏性越強。尤其令

時，隻需要通過調節一個參數就能控制稀疏性。

根據公式(3)，我們很容易寫出TG的算法邏輯：

4. TG與簡單截斷以及L1正則化的關系

簡單截斷和截斷梯度的差別在于采用了不同的截斷公式

，如圖1所示。

圖1 截斷公式T0&T1的曲線

 為了清晰地進行比較，我們将公式(3)進行改寫，描述特征權重每個次元的更新方式：

    公式(4)

如果令

截斷公式變成：

此時TG退化成簡單截斷法。

如果再令k=1，那麼特征權重次元更新公式變成：

此時TG退化成L1正則化法。