番外篇(4)——共軛梯度法入坑

01-29

本文收錄在無痛的機器學習第一季。

前面我們已經把最速下降法的內容介紹的差不多了，下面我們要做的就是介紹這個真正的主角了——共軛梯度法。這個優化方法算是活躍在優化世界的一個經典演算法了，它的計算速度還算不錯，方法也算相對簡單——真的是相對，因為比起梯度下降它還是複雜不少，但是和其他的一些方法比較，那就不算難了。

好了，我們直奔主題。在番外篇的開篇我們就提到了機器學習的三個部件。優化演算法作為一個黑盒，一般來說是不為人所知的。所以我們的重點就是揭開它的面紗，儘可能清楚地闡述它的原理。

更高級的約束

前面在最速下降法中，我們提到了最速下降法的一個性質——那就是相鄰兩次的優化方向是正交的。乍一聽上去，總感覺這個性質很酷，但是看過了一些實際案例，又不免讓人心灰——走成"zig-zag"的形狀，還好意思標榜這個性質？

於是乎，我們開始對優化方向有了更大的野心——能不能讓我們的優化方向更加智能，我們每朝一個方向走，就把這個方向走到極致？所謂的極致，可以理解為在優化的過程中我們再也不需要朝這個方向走了。於是乎我們引出了另外一個變數，叫做誤差：

$e_t=x^*-x_t$

這個誤差表示了參數的最優點和當前點之間的距離。那麼我們的目標就可以更在形式化了，我們希望每一步優化後，當前的誤差和我們剛才優化的方向正交！注意，這裡我們已經不再使用梯度這個詞，而是使用優化方向，因為從現在開始，我們的優化方向不一定是梯度了。當然我們也要換一個變數名比較好，不然會引起誤會：

$r_t$

還是寫個公式出來比較靠譜：

$r_t^Te_{t+1}=0$

這樣我們可以想像，如果我們的優化空間有d維，那麼我們最多只需要迭代d輪就可以求解出來了。聽上去蠻靠譜的。

好了，大餅畫完了，下面就是填坑時間了。

坑

理想很豐滿，但是現實很骨感。如果我能知道那個誤差，我還優化幹嘛？直接按誤差更新不就完事了？但是想知道誤差還是需要一步一步地求解啊？感覺我們掉入了"chicken-egg senario"裡面。

但是別著急，我們還有數學武器在手，我們可以用線性代數的知識偷天換日，填滿這個坑。於是乎，見證奇蹟的時刻就要來臨了。

共軛

偷天換日的關鍵就在這個共軛上了。其實一開始看到這個詞的時候我是拒絕的，這是什麼鬼？這詞是啥意思？

一個按原意的解釋——軛就是綁在兩頭牛身上的木頭，它讓兩個本來獨立的個體變成了一個整體，屬於牽線搭橋之類的關鍵道具。

好了，我們再回到剛才的問題中，前面我們說了我們新的正交特性，那麼放在共軛這個環境下是什麼效果呢？我們希望現在的關係變為共軛正交，存在一個矩陣A（A就是軛），使得：

$r_t^TAe_{t+1}=0$

其實看到這裡我依然是拒絕的……這又是什麼鬼，三觀都崩塌了好不好，這麼亂搞有什麼意義？

別著急，其實如果我們把上面的原始公式中間加一個東西，看上去就舒服很多了：

$r_t^TIe_{t+1}=0$

單位陣不改變結果，現在我們要加一個能改變結果的東東，僅此而已。那麼這個矩陣是什麼作用呢？

我們可以認為這個矩陣要完成線性變換的作用，將一個向量從一個線性空間轉換到另一個空間。轉換後的向量可以滿足正交的性質，如果這個矩陣一直保持不變，聽上去這個性質也是合理的啊。

那麼有沒有更加實際的例子呢？

比方說我們有兩個向量：

$a=[1,1] , b=[1,0.5]^T$

很顯然它們不是正交的，但是如果我們多了一個矩陣A：

$A=[[1,0][0, -2]]$

那麼我們發現，b經過A轉換後就與a正交了。

所以這個新的條件實際上只是多繞了一個彎，和前面的條件差距並不大。

一旦接受了這樣的設定，下面的內容就好理解多了。

共軛梯度法的流程

好了，我們已經明確了共軛梯度法的目標和特點，那麼我就要開始推導演算法公式了。當然，共軛梯度法也屬於line search的一種，我們的總體思路不變：

確定優化方向
確定優化步長

相對而言，確定優化方向比確定優化步長麻煩，我們放在後面說，現在先來撿個軟柿子，那就是第2步，我們從上面提過的公式開始：

$r_t^TAe_{t+1}=0$

好了，開始推導：

$r_t^TAe_{t+1}=r_t^TA[e_{t}+X_t-X_{t+1}]=r_t^TA[e_{t}+alpha_t r_t]$

$=r_t^TAe_{t}+alpha_t r_t^TAr_t=0$ ，於是

$alpha_t=-frac{r_t^TAe_{t}}{r_t^TAr_t}$

$alpha_t=-frac{r_t^TA(X^*-X_t)}{r_t^TAr_t}$

我們知道 $AX^*=0$ ， $g_t=AX_t$ ,於是公式最終變為：

$alpha_t=frac{r_t^Tg_t}{r_t^TAr_t}$

好了，我們發現我們利用多出來的A把前面的誤差e成功地消掉了，這下子步長可解了。讓我們記住這個公式——不是背下來，而是大概記住這個形式，後面我們還會用到它。

下一回我們繼續來看看後面的推導。

廣告時間

更多精彩盡在《深度學習輕鬆學：核心演算法與視覺實踐》！