演化策略(Evolutionary Strategies)

演化策略是一種求解參數優化問題的方法，所以我先介紹一下什么是優化。

(資料圖片)

1. 優化（Optimization）

優化就是計算一個函數的最大值或者最小值的問題，下面以求解單變量的最小值為例進行介紹。

假設函數f(x)的具體表達式是未知的，把它看作一個黑盒函數，我們只能通過向盒子輸入得到輸出。它可能存在局部最小點和全局最小點，很顯然進行坐標點窮舉然后對比出最小值的方法是不可行的，這時就需要我們根據一定的策略一步步地向我們的最小值逼近，不同策略就對應著不同的優化算法。

因為，在機器學習的過程中，根據我們搭建的模型并不是一開始就能根據輸入獲得我們想要的結果，所以就需要對我們的模型進行優化，以使誤差函數值（loss）達到最小或者適應度函數值（fitness）達到最大。優化分為黑盒優化和白盒優化。

黑盒優化：所謂的黑盒優化就是指尋找黑盒函數的全局最優化解。非形式化的來說，一個黑盒函數F 可以理解為從 輸入 X(x1,x2,x3...) 到 輸出 的一個映射.但是映射關系F的具體表達式及梯度信息均未知，我們只能通過不斷地將數據輸入到黑盒函數中然后通過得到的輸出值來猜測黑盒函數的結構信息。下圖表示一個黑盒問題的映射關系。

1.2 黑盒優化方法

介紹超參數優化之前先介紹一下參數的概念。模型中的參數分為模型參數和超參數，模型參數就是我們的模型根據訓練數據訓練學習到的參數，不需要人為設定；而超參數是模型開始訓練前人為設定的參數，通過不斷調整超參數使模型最后的輸出越來越復合我們的預期，下面三種是常見的超參數優化方法（屬于黑盒優化）。

1.2.1 網格搜索（Grid Search）

以機器學習中的分類問題為例，在模型訓練過程中，我們通常需要多次調整超參數以使我們的輸出準確率更高，如果涉及到參數過多就需要多次的人工修改，這時我們可以采用網格搜索---也就是多參數的交叉組合，從而在所有組合中一次性找出最優超參數，比如我們有兩個超參數，設定超參數x的范圍(0,1),步長0.3，y的范圍(0,1),步長0.3，那么兩個超參數的組合方式有3*3=9種。

1.2.2 隨機搜索（Random Search）

與網格搜索相比，隨機搜索并未嘗試所有參數值，而是從指定的分布中采樣固定數量的參數設置。它的理論依據是，如果隨機樣本點集足夠大，那么也可以找到最優的超參數，或它的近似值。通過對搜索范圍的隨機取樣，隨機搜索一般會比網格搜索要快一些，以了sklearn中的RandomizedSearchCV接口通過設定n_iter 的值來決定采樣的數量。

1.3 網格搜索和隨機搜索遇到的問題

1.2.3貝葉斯優化（Bayesian Optimization）

網格搜索窮舉地搜索整個超參數空間，隨著待優化超參數的增加計算量呈指數增長，速度非常慢。而對于隨機搜索來說，進行稀疏的簡單隨機抽樣并不會遇到該問題，但采樣過少很難找到全局最優解。貝葉斯優化算法能很好地解決前兩種搜索算法遇到的問題。貝葉斯優化能利用先驗知識動態縮小超參數搜索空間，并且迭代次數少，速度更快。

下面簡單介紹一下貝葉斯優化：

首先明確我們的目標，通過不斷調整輸入（超參數）來最大化目標函數值（比如對于線性回歸調優時的評估函數是均方誤差（fitness），我們的目標就是最大化 -1*fitness），也即我們的目標并不是使用盡可能多的數據點完全推斷未知的目標函數，而是希望能求得最大化目標函數值的參數。

貝葉斯優化用于機器學習調參的主要思想是：給定優化的目標函數(廣義的函數，只需指定輸入和輸出即可，無需知道具體的函數形式)，根據已知的樣本點在函數上的分布（先驗知識）不斷地添加樣本點來更新目標函數的最大值。

上圖可以直觀地解釋貝葉斯優化。其中紅色的曲線為實際的目標函數，并且我們并不知道該函數確切的表達式。所以我們希望使用高斯過程逼近該目標函數。把采樣點（上圖有 4 個抽樣點）根據高斯過程我們能夠得出綠色的置信區間，即目標曲線最有可能處于的區域。從上面的先驗知識中，我們確定了第二個點（f+）為最大的樣本觀察值，所以下一個最大點應該要比它大或至少與之相等。因此，我們繪制出一條藍線，并且下一個最大點應該位于這一條藍線之上。因此，下一個采樣在交叉點 f+和置信域之間，我們能假定在 f+點以下的樣本是可以丟棄的，因為我們只需要搜索令目標函數取極大值的參數。所以現在我們就縮小了觀察區域，我們會迭代這一過程，直到搜索到最優解。（有關網格搜索、隨機搜索、貝葉斯優化的具體實例代碼及函數可以跳轉https://www.jianshu.com/p/5378ef009cae）

1.4 梯度優化

在高數課本中我們可以找到梯度這個概念， 梯度是一個矢量，是函數一個點上導數最大值的方向，也就是函數值在該方向上變化最快，因此只要隨著梯度的方向，便能最快的到達極值點。梯度下降（gradient descent）的方法就是這么得來的。梯度下降法的基本思想可以類比為一個下山的過程：想象我們在山頂，只要我們每一步都沿著最陡的方向邁出下一步，那么我們一定可以最快到達山腳。因此，找到了梯度，我們也需要小心注意步長值，若步長值太大，我們可能一步邁出過大，錯過了極值點，若步長值太小，我們到達極值點的次數會增加。

1.4.1 隨機梯度下降（SAG）

在模型訓練的過程中，梯度下降是常用的最小化誤差函數loss的方法。一般而言，梯度下降需要在遍歷所有的數據后才進行梯度計算然后更新參數。假設現有數據集有10,000條數據，那么在這10,000條數據都進行訓練之后才會確定梯度，這樣的計算會耗時很長。

隨機梯度下降也稱小批量梯度下降（mini-batch gradient decent），它解決了需要遍歷所有數據才更新一次參數的問題。隨機梯度下降根據每一個小批量數據進行更新參數。也就是說，10,000個數據，假設分成10個批量，每個批量是1,000個數據，那么在遍歷完每個批量后，計算這個小批量的梯度然后進行更新參數，這樣在遍歷完10,000個多有數據后，梯度下降實際上已經進行了十次，相比于普通梯度下降而言，速度快了10倍。實驗結果表明，在數據打亂情況下，隨機梯度下降的每一個批量是可以很好近似整個數據集的。隨機梯度下降的參數更新公示如下,gt為目標函數關于參數w的梯度：

1.4.2  SAG + Momentum

SGD最大的缺點是下降速度慢，而且可能會在溝壑的兩邊持續震蕩，停留在一個局部最優點。為了抑制SGD的震蕩，Momentum 通過保持前一步的行動勢頭從而加速誤差函數loss的收斂過程。如果當前一步與前一步的方向保持一致，那么即將邁出的步伐就會大一些，如果方向不一致則會因為受到上一步的權值影響減小反方向的步伐，從而對傳統的梯度下降產生優化。

α表示的是學習率（learning rate），也就是下山例子中的步長值，所以學習率的設置影響著優化過程，通常設為0-0.1之間。v是實際邁出的步長，w是待優化的目標函數。

1.4.3 自適應矩估計（Adam）

Adam （ adaptive moment estimation）自適應矩估計算法是目前比較流行的一種優化算法 ，于2015 年在ICLR論文 Adam: A Method for Stochastic Optimisation被提出。Adam 算法根據梯度grad的一階動量和二階動量動態調整步長。動量我理解為歷史上每一代t 的梯度對下一步步長的影響程度。Adam算法的步驟如下：

首先定義：待優化參數： w，目標函數： f(w) ，初始學習率 α。

而后，開始進行迭代優化。對每一代 t ：

1.計算目標函數關于當前參數的梯度：

2.根據歷史梯度計算一階動量和二階動量：

3.

4.計算當前時刻的下降梯度:

5.根據下降梯度進行更新：

當優化的參數w只有一個時梯度就是函數的導數，當參數有多個時梯度就變成了了向量，上面四步所求的也均為向量。算法中的一階動量mt就是參考的momentum防止產生震蕩，最原始的二階動量形式為，對于經常更新的參數，我們已經積累了大量關于它的知識，不希望被單個樣本影響太大，希望學習速率慢一些；對于偶爾更新的參數，我們了解的信息太少，希望能從每個偶然出現的樣本身上多學一些，即學習速率大一些。但是因為Vt 是單調遞增的，會使得學習率單調遞減至0，可能會使得訓練過程提前結束，所以我們參考momentum關于一階動量的公式對Vt進行修改，避免了二階動量持續累積、防止訓練過程提前結束。 第三步的目的是解決訓練剛開始初始化Mt=0，Vt=0時梯度變化很小的問題?？梢詫⒌谒牟降目醋鰧W習率，β1、β2為衰減參數、epos（=1e-10）為防止動量為0導致除0操作。

下面為大家介紹三種演化策略領域（ES）比較流行的黑盒優化方法：協方差矩陣自適應策略（CMA-ES）、自然進化策略（NES）、強化學習（RL-ES）。

2.演化策略（Evolution Strategy , ES）

演化策略是一種在搜索空間中尋找最優的解決方案的優化技術，屬于演化算法大家庭中的一員，另外三個成員分別是遺傳算法(Genetic Algorithms)、遺傳編程（Genetic Programming）和演化編程(Evolution Programming)，他們當中的靈感大多來自于自然界中的生物進化。

在介紹演化策略的變體之前先講解一下ES的實現步驟：

1.生成由候選解決方案組成的種群。

2.依據適應度函數評估種群中的每一個個體。

3.篩選出適應度高的個體作為繁衍后代的父代。

4.通過重組和變異的方式產生下一代個體。

5.重復上述過程直到滿足進化的終止條件（比如：達到指定迭代次數 或者找到適應度值滿足要求的個體 或者種群進化不再使使適應度值變大）

這是一張演化策略與遺傳算法的差異對比，截斷選擇就是指從當前種群個個體中將適應度值較高的前個個體保留，其余淘汰。重組就是將選中的2或4個父體的均值作為新個體，變異一般是以選中的父體基準隨機產生后代，父體與其后代符合均值為父體，某一方差的正態分布。

上圖是GA的框架流程圖，ES的流程圖只需將GA的遺傳操作部分進行替換即可

下面以求解 黑盒函數f(x)的最小值 為例介紹Basic ES：

如果對截斷選擇、重組、變異的原理理解不太深刻，可以參考一下外文中針對多個自變量的目標函數最小值問題（25張幻燈片，就不往這里放了）

https://www.slideshare.net/OsamaSalaheldin2/cmaes-presentation

2.1 協 方 差 矩 陣 自 適 應 進 化 策 略 （CMA-ES）

CMA-ES（Covariance Matrix Adaptation-Evolutionary Strategies）是 在 演化策略 ( Evolution Strategy，ES) 的基礎上發展起來的一種高效搜索算法，它將 ES 的可靠性、全局性與自適應協方差矩陣的高引導性結合起來，對求解非凸非線性優化問題具有較強的適應性，目前以其良好的尋優性能在優化領域備受關注。并且，在對全局優化問題（與進化算法相比） 的求解中，CMA-ES 對步長的優化可以避免種群過早收斂以及在種群很大的情況下避免局部最優，并且它是一種黑盒優化算法。

2.1.1基本概念

協方差 是一種用來度量兩個隨機變量關系的統計量：結果>0表示兩個變量正相關（比如身高越高的人往往體重越大） ，<0表示兩個變量負相關， =0表示兩個變量獨立，方差是指變量關于其均值的偏離程度。公式如下：

均值（期望）：

協方差：       cov(X,Y)=cov(Y,X)

方差：D(X)=cov(X,X)=VAR(X)

協方差矩陣：兩個向量（多個參數）之間的相關性統計，協方差矩陣的維度等于待優化參數的個數。假設有兩個待優化參數A，B。對應協方差矩陣為C = 由方差和協方差的定義可以確定：協方差矩陣中D(X)增大會使得樣本點在X軸的方向上更分散（樣本點在X軸的方向被拉伸，圖片中的橫坐標由原來的[-3,3]變成了[-5,5]），D(Y)增大會使得樣本點在Y軸的方向上更分散；cov(X,Y)大于0 會使得樣本點成正相關性偏移，也即隨樣本點X值的增大Y值也會增大。下面是協方差矩陣各個位置變化對樣本分布的影響：

通過上面的講解，相信你對協方差矩陣各個位置的變幻 對樣本點進化方向的改變有了一個初步的認識，下面再介紹一下步長（step-size）：

參數σ控制分布的總體規模。它是從協方差矩陣中分離出來的，這樣我們就可以比完全計算出協方差矩陣更快地改變步長。步長越大，參數更新越快，新產生的個體（樣本）是在步長內進行隨機選取的。

累計步長適應（cumulative step-size adaptation，CSA）是指綜合考慮本代樣本均值的大小和方向與歷史步長的進化方向相同或者相反，決定下一代步長的變化。由下圖可見，當代樣本的更新方向與歷史進化方向相同則會加速步長的增加，從而擴大種群的搜索范圍，反之則會減小步長甚至改變進化的方向，從而使得下一代個體更加密集，更利于找到全局最優的樣本點。

下面開始步入正軌，我們參考basic ES的流程來介紹CMA-ES的優化流程：

首先介紹需要初始化的參數，設待優化的參數個數為n個，則樣本點x，均值m都是n維的向量,目標函數為f(x),值越小越好，最小為0：

：每一代的種群規模

：通過截斷選擇截取個最優的個體作為產生下一代的父體。

C=I（協方差矩陣初始為n*n維單位陣）

m：人為猜測的一個n維初始樣本均值

：人為猜測的一個n*1步長矩陣

：第i個個體所占的更新權重

1.產生新個體：通過對m進行變異產生個后代，他服從均值為m，協方差為^2*C的多元正態分布，即從這個分布中隨機取樣。

等價于

2.適應度評估：根據適應度函數或者誤差函數對個體進行評估，然后排序，使得f(x1)<=f(x2)<=f(x3)...<=f()

3.更新均值：通過最優的個個體更新均值，當代最優的個體所占權重最大，使均值更偏向于最優個體的方向：

4.更新步長，采用上面提到的累計步長適應策略進行更新，相應的也需要對每一代的累計步長進行更新：

是累計步長的衰減率， =  - m，

5，更新協方差矩陣：

（1）      （2）

為協方差矩陣累積路徑的衰減率，、分別為rank-1、rank-u更新策略的學習率， =  - m

此公式結合了rank-u-update和rank-1-update對協方差矩陣進行更新，一方面，當代種群的所有信息通過rank-u策略被充分利用，另一方面，進化過程中每代種群間的相關性信息通過rank-one的演化路徑策略充分探索，前一種策略對種群規模很大時重要（考慮種群中最優的u個個體），后者對種群規模小時重要（類似于步長的更新方式，使用累計路徑策略來兼顧之前的種群信息），這樣在不同種群規模下的評估結果會更加準確。

6.重復上述過程直到滿足進化的終止條件（比如：達到指定迭代次數 或者找到適應度值滿足要求的個體 或者種群進化不再使使適應度值變大）

除了協方差矩陣C的自適應規則外，我們引入步長控制來對后代樣本點更新，還有兩個原因： 1.最佳步長不能用步驟5中的公式（2）很好地逼近。 2.公式（2）中協方差矩陣更新的最大可靠學習率太慢，無法實現總體步長的競爭性變化率。

2.2自然進化策略 (Natural Evolution Strategies，NES)

NES的重點是自然梯度，所以先介紹一下常規梯度（見上面1.4節介紹）與自然梯度的區別：

給定一個參數為 θ 的目標函數 J (θ)，我們的目標是找到最優的 θ，從而最大化目標函數的值。

常規梯度會以當前的 θ 為起點，在很小的一段歐氏距離內找到最陡峭的方向，也就是J(θ)相對于θ的負梯度方向，而樣本的分布是無規律的；

而在演化策略中，第一代種群個體的生成是在當前的分布空間（高斯分布）中進行抽樣產生的，所以在NES中每一代的個體進化過程可以理解為概率分布空間的優化過程：θ的優化-->種群分布空間的變化-->在分布空間中隨機采樣的個體的變化

自然梯度考慮的是參數的變化引起樣本分布空間的變化，比如p(xi;)-->p(xi;),而這一概率屬性距離（無法用Euclidean distance來度量）可以用Kullback-Lubler差離度來度量，自然梯度是按KL距離度量來進行梯度下降過程的。自然梯度法采用分布空間距離約束 —> KL散度二階泰勒級數展開—> Fisher信息矩陣近似—> 拉格朗日乘數法計算KL散度約束下的目標函數最大值—>自然梯度：

完整的自然梯度推導過程如下：

下面步入正題：

NES 也是一種黑箱式優化算法。Wirestra等人提出了將進化算法和神經網絡中的梯度下降思路結合在一起的想法。傳統的進化算法包含突變和重組這兩個步驟。 我們通過這兩個步驟， 期待找到更好的解法。 然而， 突變和重組是完全隨機的，不會根據已知的數據集特征產生 進化的傾向性，所以多數情況下，他們不會產生比當前這一代更優的解法。 因此, 我們想引入梯度下降或者梯度上升的思想, 從而使得突變總是能夠朝著使個體適應度更好的方向（比如誤差更小的方向）邁進。換句話說,我們用梯度下降替代了進化算子中的突變和重組步驟，官方定義 為 NES是一類利用分布參數上的估計梯度策略迭代更新搜索分布的進化策略。具體的實現步驟如圖（類比遺傳編程中的種群進化過程）：

1. 利用參數化分布空間隨機抽樣產生個個體，對每一個個體求適應度函數值。

2. 沿著自然梯度執行梯度下降步驟更新分布空間參數θ。

3. 整個過程迭代進行，直到滿足停止條件。

NES引入了一些新技術并解決了很多問題：(以下技術的原理推導及實驗證明詳見14年 Wierstra 等人發表的論文Natural Evolution Strategies)

1. 引入 自然梯度 解決 常規梯度 存在的過早收斂和尺度不變性問題。

2. 引入Fitness shaping使NES算法不受適應度保序變換的影響，增強算法的魯棒性

3. 適應性抽樣調整了在線學習率，在基準上產生了高績效的結果

4. 指數參數化是維持正定協方差矩陣的關鍵

5. 自然坐標系保證了計算的可行性。

2.3強化學習（ Reinforcement Learing，RL）

2.3.1基本概念

眾所周知，當AlphaGO戰勝了世界圍棋冠軍李世石之后，整個工業界都為之振奮，而AlphaGO背后的技術原理正是強化學習。現如今強化學習因其普適性在越來越多的領域得到了應用。

首先我們來看一下強化學習所屬的分支，如圖所示：

RL與有監督學習、無監督學習的比較：

（1）有監督的學習是從一個已經給出正確結果的訓練集中進行學習，訓練集中每一個樣本的特征可以視為是對該situation的描述，而其label可以視為是應該執行的正確的action，但是有監督的學習不能學習交互的情景，因為在交互的問題中獲得期望行為的樣例是非常不實際的，agent只能從自己的經歷（experience）中進行學習，而experience中采取的行為并不一定是最優的。這時利用RL就非常合適，因為RL不是利用正確的行為來指導，而是利用已有的訓練信息來對行為進行評價。

（2）因為RL利用的并不是采取正確行動的experience，從這一點來看和無監督的學習確實有點像，但是還是不一樣的，無監督的學習的目的可以說是從一堆未標記樣本中發現隱藏的結構，而RL的目的是最大化reward signal。

（3）總的來說，RL與其他機器學習算法不同的地方在于：其中沒有監督者，只有一個reward信號；反饋是延遲的，不是立即生成的；時間對于RL具有重要的意義；agent的行為會影響之后一系列的data。這三種不同訓練方式的核心區別在于loss的設計，三者可以用于同一task，就像黑貓白貓，能抓耗子的都是好貓。具體選擇哪一種工具要看哪一種模型會使最終的loss最小或者fitness 達到最優。

強化學習 是一種通過交互的目標導向學習方法，旨在找到連續時間序列的最優策略。

這個定義比較抽象，舉個栗子方便大家理解：在你面前有兩條路，但是只有一條路到達目的地，有個前提條件是你不知道目的地在它們當中的哪個方向。是不是感覺很抓瞎，但是如果給你個機會，讓你在兩個不同方向都去嘗試一下，你是不是就知道哪一個方向是正確的。

強化學習的一個核心點就是要嘗試，因為只有嘗試了之后，它才能發現哪些行為會導致獎勵的最大化，而當前的行為可能不僅僅會影響即時獎勵，還會影響下一步的獎勵以及后續的所有獎勵。因為一個目標的實現，是由一步一步的行為串聯實現的。在上面的場景當中，涉及到了強化學習的幾個主要因素：智能體、環境、狀態、動作、獎勵、策略。

智能體（Agent）：強化學習的本體，作為學習者或者決策者，上述場景是指我們自己。

環境（Environment）：強化學習智能體以外的一切，主要由狀態集合組成。

狀態（State）：一個表示環境的數據，狀態集則是環境中所有可能的狀態。比如，走一步就會達到一個新的狀態。

動作（Action）：智能體可以做出的動作，動作集則是智能體可以做出的所有動作。比如，你可以走第一條路也可以走第二條。

獎勵（Reward）：智能體在執行一個動作后，獲得的正/負反饋信號，獎勵集則是智能體可以獲得的所有反饋信息。走正確就獎勵，錯誤就懲罰。

策略（Policy）：策略就是指智能體的行為，是從狀態到動作的映射，即智能體如何選擇動作的思考過程，分為確定策略和與隨機策略，確定策略就是某一狀態下的確定動作a=π(s), 隨機策略以概率來描述，即某一狀態下執行這一動作的概率π(a|s)=P[At=a|St=s]。

RL 的具體步驟為：

1. 智能體嘗試執行了某個動作后，環境將會轉換到一個新的狀態，當然，對于這個新的狀態，環境會給出獎勵或者懲罰。

2. 智能體根據新的狀態和環境反饋的獎勵或懲罰，執行新的動作，如此反復，直至到達目標。

3. 智能體根據獎勵最大值找到到達目標的最佳策略，然后根據這個策略到達目標。

下圖列出了各元素之間的作用關系。要注意的是，智能體要嘗試執行所有可能的動作，到達目標，最終會有所有可能動作對應所有可能狀態的一張映射表（Q-table）

2.3.2涉及到的公式

強化學習基本上可以總結為通過最大化reward來得到一個最優策略。但是如果只是瞬時reward最大會導致每次都只會從動作空間選擇reward最大的那個動作，這樣就變成了最簡單的貪心策略(Greedy policy)，所以為了使reward是包括未來的當前reward值最大（即使從當前時刻開始一直到狀態達到目標的總reward最大），構造了值函數（value function）來描述這一變量。表達式如下：

t表示當前時刻，R是reward，S是狀態，γ是折扣系數(取值在[0,1])，折扣系數與我們的認知是一致的，就是在衡量權重時我們更看重時間距離更近時的Reward影響。

強化學習的算法迭代都是基于Bellman方程