強化學習基礎-共軛梯度

本文為 AI 研習社編譯的技術博客，原標題 ：

The base of deep reinforcement learning-Conjugate Gradient

作者 | Jonathan Hui

翻譯 | 斯蒂芬?二狗子

校對 | 斯蒂芬?二狗子 審核| 醬番梨 整理 | 菠蘿妹

原文鏈接：

https://medium.com/@jonathan_hui/rl-conjugate-gradient-5a644459137a

我們可以使用共軛梯度法（conjugate gradient）解線性方程或優化二次方程。並且，針對這兩種問題，共軛梯度法比比梯度下降的效果更好。

其中矩陣A是對稱正定矩陣

在線搜索方法中，我們確定上升的最陡方向，然後選擇步長。舉個例子，例如在梯度上升方法中， 我們採用的步長大小等於梯度乘以學習率。看下面左圖， 根據梯度的輪廓（用點圖圈成橢圓的部分），該點的最大梯度方向是向右的。對應當前點最陡的方向，下一點（迭代）的最陡方向可能是向上並略微偏左。如何我們這次梯度有點微微向左，那麼不是給第一步（向右梯度）過程的作用取消了嗎？

共軛梯度法是一種線性搜索方法，對於每次的移動，他不會撤銷（影響）之前完成的部分。在優化二階方程上，共軛梯度法比梯度下降需要更少的迭代步數。如果x是N維(N個參數），我們可以在最多N步迭代內找到最優值。因為對於每步移動，希望移動方向與之前的所有的移動方向保存共軛的關係。這一點保證了我們不會撤銷所做的移動。簡單說，若x是4維的向量，則需要最多4次移動就可以到達最優點。

Modified from source

1. 在一個指定的方向做梯度上升

2. 我們在這個方向的最佳點處停下來。

3. 我們找到了一個新方向dj ，它與任何先前的移動方向 di 共軛。

從在數學上來講，這表示任何新的方向dj 必須與所有 d(i)^TA 共軛，即

其中A是二次方程的係數矩陣。下面是A共軛（A-conjugate）矩陣在二維空間中的例子。

這些A共軛向量相互之間是獨立的。因此，N個A共軛向量可以張成一個N維空間。

該共軛梯度演算法（CG）的關鍵是找到α 和 d。

讓我先預覽一下該演算法。我們從一個隨機數X(x0)開始猜測問題的解，並計算下一步X1（包括 α 和 d ）。

d 是下一步移動的方向（共軛向量）。 讓我們看看它的工作原理。首先，我們定義兩項：

• e 表示當前猜測點和最佳點之間的誤差。

• r 測量的是我們當前值與正確值b（Ax = b）的距離。我們可以把r看成將A投影到b所在空間後與b的誤差 e（Ax距離b的距離）。

r,e分別定義為：

函數為

對函數求導

下一個點的計算為（其中α是標量，d是方向，是向量）：

為了保證未來的移動方向不會削減之前移動所做的工作，讓我嘗試保證e 和 d 是相互正交。也就是，採取該步迭代後的殘差應該與當前移動方向保持正交的關係。為了保證之後迭代動作不會消減我們剛剛做的工作，因此保持這種正交關係是有道理的。

因此α取決於e，但我們不知道e的實際值是多少。所以使用其他方法代替正交，讓我們嘗試另一種猜測（估計方法）。也就是新的搜索方嚮應與前一個方向正交。 A-orthogonal的定義是：

為了滿足這些條件，下一個迭代步的點 xi 必須是搜索方向d上的最佳點。

Modified from source

根據A正交要求時，α計算如下：

Modified from source

wikipedia上的證明:

這裡不會完整證明。但有興趣的人可以看看：

en.wikipedia.org/wiki/Derivation_of_the_conjugate_gradient_method

想要繼續查看該篇文章相關鏈接和參考文獻？

長按鏈接點擊打開或點擊【強化學習基礎：共軛梯度】：

https://ai.yanxishe.com/page/TextTranslation/1428

【點擊跳轉】強化學習基礎-對偶梯度上升

AI研習社每日更新精彩內容，觀看更多精彩內容：雷鋒網雷鋒網雷鋒網

等你來譯：

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！