番外篇(6)——共軛梯度的效果

01-29

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

前面我們聊了許多有關共軛梯度的內容，也基本上推導出了我們想要的演算法，不過在此之前我們還是要完成上一回留下的一個小尾巴，那就是證明某一輪迭代的梯度和之前所有輪的優化方向正交而不是共軛正交。沒有錯，正是因為前面一直再利用共軛正交的性質，到了這裡我們才能實現正交的效果。

梯度和優化方向的關係

在介紹共軛梯度的過程中，我們提出了誤差這個概念，當然我們還有一個類似的概念叫做殘差。這兩個概念還是有很大的不同的，希望大家能夠分別。我們多次提到共軛梯度法的基本思想：每一輪把某一方向優化徹底，保證後面的優化不再對這個方向做任何操作。那麼我們可以想像，假設我們的演算法一共進行了T輪迭代，我們就可以用這T輪求出的優化方向組合成最終的誤差。

假設我們的初始參數值為 $x_1$ ，那麼它到最優點的距離為 $e_1$ ，我們每一步求出的優化方向為 $d_t$ ，於是乎，根據上面的介紹我們可以給出如下的公式：

$e_1=sum_{i=1}^Tgamma_id_i$

也就是說我們可以用這樣的方式表示誤差，同樣，對於不同迭代輪數的誤差，我們也可以用不同的方式進行表示。很顯然，我們可以猜到 $gamma$ 和前面我們提到的 $alpha$ 步長之間的關係。

那麼下面我們就來證明一下：

$d_i^Tg_j=0,(i<j)$

$d_i^Tg_j=d_i^T(AX_j)=d_i^T(AX_j-AX^*)=d_i^TAe_j$

$=d_i^TA(sum_{t=j}^Tgamma_td_t)$

因為我們前面已經說明任意兩個優化方向之前是相互正交的（Gram-Schmidt方法），所以這是式子的結果為0。

所以到這裡我們可以說：通過利用共軛正交的性質，我們得到了更好的正交性質，這個正交性質要比前面的最速下降法的正交性質好很多。這就是共軛梯度法最精髓的地方。

在這裡不免有些感慨，前輩們的腦洞真心不一般，能夠利用一些看上去抽象又無關緊要的定理幫助我們解決一些核心的大問題，這裡面存在的不僅僅是數學的美麗，有時甚至是哲學的精彩……

畢竟不是心靈雞湯文，抒情的套路還是要少一些。我們還是繼續來關注這個演算法，到這裡我們的演算法全過程就應該一目了然了：

def conjugateGradient(A, b, x):ntgrad = np.dot(A, x) - bntp = -gradntwhile True:nttif abs(np.sum(p)) < 1e-6:ntttbreaknttgradSquare = np.dot(grad, grad)nttAp = np.dot(A, p)nttalpha = gradSquare / np.dot(p, Ap)nttx += alpha * pnttnewGrad = grad + alpha * Apnttbeta = np.dot(newGrad, newGrad) / gradSquarenttp = -newGrad + beta * pnttgrad = newGradntreturn xn

好了，代碼放到這裡，相關的實驗就按下不表了。大家感興趣可以自己試試看。

好了，這一次的番外篇就到此結束了。我們實際上介紹了兩個「全自動」的優化演算法，所謂的全自動，就是說它不需要調參。當然為此帶來的代價也比較大，我們無法把這些演算法用在所有的場景上，而且在同樣的場景上，也許還有比他們更好的演算法。

優化演算法是個大坑，我們要慢慢跳，這次就跳到這裡。拜拜了～

廣告時間

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