0
| 本文作者： AI研習社-譯站 | 2019-01-28 11:09 |
本文為 AI 研習社編譯的技術(shù)博客，原標題 ：
The base of deep reinforcement learning-Conjugate Gradient
作者 | Jonathan Hui
翻譯 | 斯蒂芬?二狗子
校對 | 斯蒂芬?二狗子 審核| 醬番梨 整理 | 菠蘿妹
原文鏈接：
https://medium.com/@jonathan_hui/rl-conjugate-gradient-5a644459137a
我們可以使用共軛梯度法（conjugate gradient）解線性方程或優(yōu)化二次方程。并且，針對這兩種問題，共軛梯度法比比梯度下降的效果更好。
其中矩陣A是對稱正定矩陣
在線搜索方法中，我們確定上升的最陡方向，然后選擇步長。舉個例子，例如在梯度上升方法中， 我們采用的步長大小等于梯度乘以學習率?？聪旅孀髨D， 根據(jù)梯度的輪廓（用點圖圈成橢圓的部分），該點的最大梯度方向是向右的。對應當前點最陡的方向，下一點（迭代）的最陡方向可能是向上并略微偏左。如何我們這次梯度有點微微向左，那么不是給第一步（向右梯度）過程的作用取消了嗎？
共軛梯度法是一種線性搜索方法，對于每次的移動，他不會撤銷（影響）之前完成的部分。在優(yōu)化二階方程上，共軛梯度法比梯度下降需要更少的迭代步數(shù)。如果x是N維(N個參數(shù)），我們可以在最多N步迭代內(nèi)找到最優(yōu)值。因為對于每步移動，希望移動方向與之前的所有的移動方向保存共軛的關(guān)系。這一點保證了我們不會撤銷所做的移動。簡單說，若x是4維的向量，則需要最多4次移動就可以到達最優(yōu)點。
Modified from source
在一個指定的方向做梯度上升
我們在這個方向的最佳點處停下來。
我們找到了一個新方向dj ，它與任何先前的移動方向 di 共軛。
從在數(shù)學上來講，這表示任何新的方向dj 必須與所有 d(i)^TA 共軛，即
其中A是二次方程的系數(shù)矩陣。下面是A共軛（A-conjugate）矩陣在二維空間中的例子。
這些A共軛向量相互之間是獨立的。因此，N個A共軛向量可以張成一個N維空間。
該共軛梯度算法（CG）的關(guān)鍵是找到α 和 d。
讓我先預覽一下該算法。我們從一個隨機數(shù)X(x0)開始猜測問題的解，并計算下一步X1（包括 α 和 d ）。
d 是下一步移動的方向（共軛向量）。
讓我們看看它的工作原理。首先，我們定義兩項：
e 表示當前猜測點和最佳點之間的誤差。
r 測量的是我們當前值與正確值b（Ax = b）的距離。我們可以把r看成將A投影到b所在空間后與b的誤差 e（Ax距離b的距離）。
r,e分別定義為：
函數(shù)為
對函數(shù)求導
下一個點的計算為（其中α是標量，d是方向，是向量）：
為了保證未來的移動方向不會削減之前移動所做的工作，讓我嘗試保證e 和 d 是相互正交。也就是，采取該步迭代后的殘差應該與當前移動方向保持正交的關(guān)系。為了保證之后迭代動作不會消減我們剛剛做的工作，因此保持這種正交關(guān)系是有道理的。
因此α取決于e，但我們不知道e的實際值是多少。所以使用其他方法代替正交，讓我們嘗試另一種猜測（估計方法）。也就是新的搜索方向應與前一個方向正交。 A-orthogonal的定義是：
為了滿足這些條件，下一個迭代步的點 xi 必須是搜索方向d上的最佳點。
Modified from source
根據(jù)A正交要求時，α計算如下：
Modified from source
wikipedia上的證明:
這里不會完整證明。但有興趣的人可以看看：
en.wikipedia.org/wiki/Derivation_of_the_conjugate_gradient_method
想要繼續(xù)查看該篇文章相關(guān)鏈接和參考文獻？
長按鏈接點擊打開或點擊【強化學習基礎(chǔ)：共軛梯度】：
https://ai.yanxishe.com/page/TextTranslation/1428
【點擊跳轉(zhuǎn)】強化學習基礎(chǔ)-對偶梯度上升
AI研習社每日更新精彩內(nèi)容，觀看更多精彩內(nèi)容：雷鋒網(wǎng)雷鋒網(wǎng)雷鋒網(wǎng)
等你來譯：
雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
