?PaperWeekly 原創(chuàng) ·?作者｜蘇劍林

單位｜追一科技

研究方向｜NLP、神經(jīng)網(wǎng)絡

深度學習如此成功的一個巨大原因就是基于梯度的優(yōu)化算法（SGD、Adam 等）能有效地求解大多數(shù)神經(jīng)網(wǎng)絡模型。然而，既然是基于梯度，那么就要求模型是可導的，但隨著研究的深入，我們時常會有求解不可導模型的需求，典型的例子就是直接優(yōu)化準確率、F1、BLEU 等評測指標，或者在神經(jīng)網(wǎng)絡里邊加入了不可導模塊（比如“跳讀”操作）。

▲ Gradient

本文將簡單介紹兩種求解不可導的模型的有效方法：強化學習的重要方法之一策略梯度（Policy Gradient），以及干脆不需要梯度的零階優(yōu)化（Zeroth Order Optimization）。表面上來看，這是兩種思路完全不一樣的優(yōu)化方法，但本文將進一步證明，在一大類優(yōu)化問題中，其實兩者基本上是等價的。

形式描述

首先，我們來形式地定義我們需要解決的問題。以監(jiān)督學習為例，訓練數(shù)據(jù) ，模型為 ， 是待優(yōu)化參數(shù)，其維度為 d，假設模型本身是可導的，其的一般形式為 ，其中 稱為溫度參數(shù)，沒有特別注明的情況下默認 。

假如真實標簽是 ，預測標簽是 ，那么單個樣本的得分記為 ，訓練目標希望總得分越大越好，即：

看上去挺復雜的，但事實上它的含義很直觀清晰：我們想求出參數(shù) ，使得整個數(shù)據(jù)集的得分 盡可能大，而 ，說明模型預測時輸出的是概率最大的那一個。說白了，我們希望“預測概率最大的那一個 y 就是評測得分最高的那一個 y”。

這個形式對應著相當多的機器學習任務，在 NLP 中包括文本分類、序列標注、文本生成等，甚至回歸問題也可以對應上去，可以說是很有代表性了。其困難之處就是 這一步無法提供有效的梯度，因此不好直接用基于梯度的優(yōu)化算法優(yōu)化。

策略梯度

策略梯度的想法很直接，既然原始的目標（1）沒法求梯度，那換個跟它強相關(guān)的、可求梯度的目標就行了，比如：

2.1 排序不等式

很明顯，上述定義的目標并沒有包含 之類的算子，因此它是可導的。那么我們首先想要知道的是上式跟原始目標（1）有什么關(guān)系呢？差異又在哪呢？這需要用數(shù)學中的“排序不等式”來回答：

排序不等式：對于 以及 ，并假設 是 的任一排列，那么：

也就是說“同序積和 ≥ 亂序積和 ≥ 倒序積和”。

排序不等式是很經(jīng)典的不等式，網(wǎng)上很容易找到它的證明（一般用數(shù)學歸納法），這里就不證了。

根據(jù)排序不等式我們可以知道，如果目標（2）達到最大值，那么 與 是同序的，也就是說確實可以實現(xiàn)“預測概率最大的那一個 y 就是評測得分最高的那一個 y” 這個目標，但是同時還實現(xiàn)了“預測概率第二大的那一個y就是評測得分第二高的那一個 y”、“預測概率第三大的那一個 y 就是評測得分第三高的那一個 y” 等目標，而這些并不是原始目標所必須的。

所以，目標（2）跟原始目標是強相關(guān)的，但是要求更多一些。

注意到，排序不等式?jīng)]有要求 都是非負數(shù)，所以實際的打分函數(shù) 有可能是負數(shù)的。

2.2 采樣估計梯度

確定目標（2）是可行的之后，我們可以求它的梯度：

一般來說，求梯度 并不困難，而 才是主要的困難，因為它要對所有候選類別求和，而實際上的候選類別數(shù)目可能大到難以承受，相關(guān)討論在之前的《漫談重參數(shù)：從正態(tài)分布到 Gumbel Softmax》[1] 也出現(xiàn)過。因此，比較好的辦法是轉(zhuǎn)化為采樣估計的形式，即：

這樣原則上我們就只需要采樣適當數(shù)目的 y 估計上式了，最后的結(jié)果便稱為“策略梯度”。有了梯度，就可以套用現(xiàn)成的優(yōu)化器來完成優(yōu)化了。

2.3 降低方差

剛才我們說，往 里加上一個常數(shù)，并不會改變最終的結(jié)果。但是，它有可能改變采樣估算的效率，用統(tǒng)計的語言來說，就是它能改變采樣的方差。舉個簡單的例子，[4, 5, 6] 和 [-10, 10, 15]，它們的均值都是 5（代表我們要估算的目標），但是它們的方差分別為 0.67 和 116.67，也就是后者方差遠大于前者。

如果我們只從中采樣一個樣本，那么前者與目標的最大誤差也不過是 1，后者最大誤差能達到 15，最小誤差都有 5，所以雖然理論上最終的均值都是一樣的，但是前者的估算效率要遠遠高于后者（采樣更少的樣本，得到更高的估算精度）。

這個簡單的例子告訴我們要提高估算效率，就要想辦法得到方差更小的估計量。這時候我們往 里邊減去一個常數(shù) b（稱為 baseline，“常數(shù)”是指不依賴于 y，但可以依賴于 x）：

最終的結(jié)果（均值）不會產(chǎn)生變化：

但是它方差有可能變，我們希望最小化方差，根據(jù) 知最小化方差等價于最小化二階矩：

這只不過是一個二次函數(shù)最小值問題，解得最優(yōu)的 b 是：

即以 為權(quán)重對 求加權(quán)期望。但是要獲取每個候選類別的梯度成本會比較大，我們通常不考慮這個權(quán)重，而使用一個簡化的版本：

結(jié)合式（6），我們可以發(fā)現(xiàn)思想其實很直觀：就是要從 里邊采樣若干個 y，然后算出 的均值 b，大于這個均值的執(zhí)行梯度上升（強化效果），小于這個均值的執(zhí)行梯度下降（削弱效果）。

2.4 一言以蔽之

簡單來說，策略梯度就是在遇到有 操作等不可導目標函數(shù)時，換一個可導的目標（2），這時候用強化的語言來說，y 稱為“策略”， 稱為“決策模型”， 就是“獎勵”，然后配合采樣估計和降低方差技巧，得到原模型的一個有效的梯度估計，從而完成模型的優(yōu)化。

零階優(yōu)化

零階優(yōu)化泛指所有不需要梯度信息的優(yōu)化方法，而一般情況下它指的是基于參數(shù)采樣和差分思想來估計參數(shù)更新方向的優(yōu)化算法。

從形式上來看，它是直接在參數(shù)空間中進行隨機采樣，不依賴于任何形式的梯度，因此理論上能求解的目標是相當廣泛的；不過也正因為它直接在參數(shù)空間中進行采樣，只是相當于一種更加智能的網(wǎng)格搜索，因此面對高維參數(shù)空間時（比如深度學習場景），它的優(yōu)化效率會相當?shù)?#xff0c;因此使用場景會很受限。

不過就算這樣，也不妨礙我們學習零階優(yōu)化的思想，畢竟技多不壓身。此外，深度學習雖然往往參數(shù)量很大，但是通常來說我們設計的模型大部分模塊都是可導的，不可導的可能只有一小部分，因此也許有可能讓可導部分直接用梯度優(yōu)化器來優(yōu)化，不可導的部分才用零階優(yōu)化，這便是它的應用場景之一了，這樣的思想在很多 NAS 的論文中都出現(xiàn)過。

3.1 零階梯度

零階優(yōu)化不需要我們通常意義下所求的梯度，但是它定義了一個基于采樣和差分的“替代品”，我們暫且稱為“零階梯度”：

對于標量函數(shù) f(x)，定義它在 x 處的零階梯度為：

其中 是事先給定的小正數(shù)， 則是事先指定的均值為 0、協(xié)方差矩陣為單位矩陣的分布，通常我們會使用標準正態(tài)分布。

可以看到，只需要從 中采樣若干個點，就可以對零階梯度進行估算，而有了零階梯度之后，我們就可以把它當作普通的梯度來套用基于梯度的優(yōu)化器，這便是零階優(yōu)化的基本思想。

特別地，如果 本身是可導的，那么 ，所以當 時：

也就是說 等于普通的梯度，所以 確實是普通梯度的合理推廣之一。

3.2 也有basline

善于推導的讀者可能會發(fā)現(xiàn)，在定義（11）中，由于 的均值為 0，所以 其實不影響最終結(jié)果，即：

那么 的作用是什么呢？其實跟前面策略梯度一樣，都是為了降低方差，我們同樣可以引入 b，然后最小化二階矩（等價于最小化方差）：

解得最優(yōu)的 b 為：

實驗的時候，可以直接用有限個樣本估計上式。事實上，如果 是可導的話，可以用泰勒展開近似完成積分，結(jié)果是 ，從這個角度看直接取 也是一個合理的選擇，這就說明了引入 項的必要性與合理性。

3.3 一言以蔽之

零階優(yōu)化方法主要是基于差分來定義了一個梯度的合理推廣，由于算差分不需要函數(shù)的可導性，因此自然能適用于可導/不可導目標的優(yōu)化。

當然，由于 u 的維度就是全體參數(shù) 的維度，對于深度學習這樣的參數(shù)量巨大的模型，其實更新過程中的方差會很大，不好收斂，所以通常來說零階優(yōu)化只用來優(yōu)化模型的一小部分參數(shù)，或者作為輔助優(yōu)化手段（比如“可導目標+普通梯度+大學習率”與“不可導目標+零階梯度+小學習率”交替更新）。

對于直接在高維空間中應用零階優(yōu)化方法，也有一定的研究工作（比如Gradientless Descent: High-Dimensional Zeroth-Order Optimization [2] ），但還不算很成功。

此外，之前在《從采樣看優(yōu)化：可導優(yōu)化與不可導優(yōu)化的統(tǒng)一視角》[3] 介紹的統(tǒng)一視角，也可以看作是一種零階優(yōu)化方法，它是對常見優(yōu)化思路的更統(tǒng)一的推廣（通過它可以導出梯度下降、牛頓法、零階梯度等），但原則上來說，它也存在跟零階梯度一樣的方差大等“通病”，這是零階優(yōu)化方法很難避免的。

貌離神合

看上去，策略梯度和零階優(yōu)化確實有很多相似之處，比如大家都是需要隨機采樣來估計梯度，大家都需要想辦法降低方差，等等。當然，不相似之處也能列舉出不少，比如策略梯度是要對策略空間采樣，而零階優(yōu)化則是對參數(shù)空間采樣；又比如策略梯度本質(zhì)上還是基于梯度的，而零階優(yōu)化理論上完全不需要梯度。

那么，兩者之間的關(guān)系究竟是怎樣呢？接下來我們將會證明，對于本文開頭提出來的優(yōu)化問題（1）來說，兩者基本上是等價的。證明的思路是求目標（1）的零階梯度，經(jīng)過一系列簡化后發(fā)現(xiàn)它基本上就是策略梯度。

4.1 劃分全空間

我們記：

那么根據(jù)式（13），它的零階梯度是：

它可以轉(zhuǎn)化為：

看起來很復雜，其實思想很簡單，就是不同的u的預測結(jié)果 也不同，我們將預測結(jié)果同為y的所有 u 放在一起，記為 ，這時候全空間 就被劃分為互不相交的子集 了。

前面沒有特別注明積分區(qū)域的積分默認是在全空間 進行的，劃分空間后，它就等于在各個劃分的子集 上的積分之和了。

4.2 示性函數(shù)

然后，我們用一個“示性函數(shù)”技巧，定義：

那么：

回顧 的含義，對于任意 ，模型 的預測結(jié)果就是 y，在示性函數(shù)里邊則輸出 1，那么我們可以發(fā)現(xiàn)實際上就有：

其中 是 softmax 里邊的溫度參數(shù)（文章開頭已經(jīng)說明）。根據(jù)這個結(jié)論，我們可以近似地用 代替 ，然后代入上述各個式子，得到：

4.3 近似求積分

最后，由于 是可導的，因此利用展開 代入上式完成對 u 的積分得：

對比式（4）可以發(fā)現(xiàn)，上式右端正是策略梯度。

所以，看起來差異蠻大的零階梯度，最終指向的方向?qū)嶋H上跟策略梯度是相近的，真可謂貌離神合、殊途同歸了，有種“正確的答案只有一個”的感覺。這不禁讓筆者想起了列夫·托爾斯泰的名言：

幸福的家庭都是相似的，不幸的家庭各有各的不幸。

參數(shù)的更新方向也是如此。

文末小結(jié)

本文主要介紹了處理不可導的優(yōu)化目標的兩種方案：策略梯度和零階優(yōu)化，它們分別是從兩個不同的角度來定義新的“梯度”來作為參數(shù)的更新方向。

表面上來看兩者走了不同的路徑，但筆者的探討表明，在處理跟策略梯度一樣的優(yōu)化問題時，零階優(yōu)化所給出的更新方向跟策略梯度基本上是等價的，兩者殊途同歸。此外，本文也可以作為強化學習的入門資料供初學者參考。

參考文獻

[1] https://kexue.fm/archives/6705

[2] https://arxiv.org/abs/1911.06317

[3] https://kexue.fm/archives/7521

更多閱讀

#投 稿?通 道#

?讓你的論文被更多人看到?

如何才能讓更多的優(yōu)質(zhì)內(nèi)容以更短路徑到達讀者群體，縮短讀者尋找優(yōu)質(zhì)內(nèi)容的成本呢？答案就是：你不認識的人。

總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術(shù)靈感相互碰撞，迸發(fā)出更多的可能性。?

PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優(yōu)質(zhì)內(nèi)容，可以是最新論文解讀，也可以是學習心得或技術(shù)干貨。我們的目的只有一個，讓知識真正流動起來。

?????來稿標準：

? 稿件確系個人原創(chuàng)作品，來稿需注明作者個人信息（姓名+學校/工作單位+學歷/職位+研究方向）?

? 如果文章并非首發(fā)，請在投稿時提醒并附上所有已發(fā)布鏈接?

? PaperWeekly 默認每篇文章都是首發(fā)，均會添加“原創(chuàng)”標志

?????投稿郵箱：

? 投稿郵箱：hr@paperweekly.site?

? 所有文章配圖，請單獨在附件中發(fā)送?

? 請留下即時聯(lián)系方式（微信或手機），以便我們在編輯發(fā)布時和作者溝通

????

現(xiàn)在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關(guān)注」訂閱我們的專欄吧

關(guān)于PaperWeekly

PaperWeekly 是一個推薦、解讀、討論、報道人工智能前沿論文成果的學術(shù)平臺。如果你研究或從事 AI 領(lǐng)域，歡迎在公眾號后臺點擊「交流群」，小助手將把你帶入 PaperWeekly 的交流群里。

總結(jié)

以上是生活随笔為你收集整理的殊途同归的策略梯度与零阶优化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。