優化演算法pdf

⑴ 蟻群優化演算法的使用-編碼的問題！

「蟻群演算法」學習包下載

下載地址： http://board.verycd.com/t196436.html (請使用 eMule 下載)

近一百多篇文章，打包壓縮後有 24.99MB ，基本上是從維普資料庫中下載來的，僅供學習和研究之用，請務用於商業活動或其他非法活動中，各文章版權歸原作者所有。

如果您覺得本人這樣做侵犯了您的版權，請在本帖後回復，本人會馬上刪除相應的文章。

以下是文件列表，全是 PDF 格式的：

基於蟻群優化演算法遞歸神經網路的短期負荷預測
蟻群演算法的小改進
基於蟻群演算法的無人機任務規劃
多態蟻群演算法
MCM基板互連測試的單探針路徑優化研究
改進的增強型蟻群演算法
基於雲模型理論的蟻群演算法改進研究
基於禁忌搜索與蟻群最優結合演算法的配電網規劃
自適應蟻群演算法在序列比對中的應用
基於蟻群演算法的QoS多播路由優化演算法
多目標優化問題的蟻群演算法研究
多線程蟻群演算法及其在最短路問題上的應用研究
改進的蟻群演算法在2D HP模型中的應用
製造系統通用作業計劃與蟻群演算法優化
基於混合行為蟻群演算法的研究
火力優化分配問題的小生境遺傳螞蟻演算法
基於蟻群演算法的對等網模擬器的設計與實現
基於粗粒度模型的蟻群優化並行演算法
動態躍遷轉移蟻群演算法
基於人工免疫演算法和蟻群演算法求解旅行商問題
基於信息素非同步更新的蟻群演算法
用於連續函數優化的蟻群演算法
求解復雜多階段決策問題的動態窗口蟻群優化演算法
蟻群演算法在鑄造生產配料優化中的應用
多階段輸電網路最優規劃的並行蟻群演算法
求解旅行商問題的混合粒子群優化演算法
微粒群優化演算法研究現狀及其進展
隨機攝動蟻群演算法的收斂性及其數值特性分析
廣義蟻群與粒子群結合演算法在電力系統經濟負荷分配中的應用
改進的蟻群演算法及其在TSP中的應用研究
蟻群演算法的全局收斂性研究及改進
房地產開發項目投資組合優化的改進蟻群演算法
一種改進的蟻群演算法用於灰色約束非線性規劃問題求解
一種自適應蟻群演算法及其模擬研究
一種動態自適應蟻群演算法
螞蟻群落優化演算法在蛋白質折疊二維親-疏水格點模型中的應用
用改進蟻群演算法求解函數優化問題
連續優化問題的蟻群演算法研究進展
蟻群演算法概述
Ant colony system algorithm for the optimization of beer fermentation control
蟻群演算法在K—TSP問題中的應用
Parallel ant colony algorithm and its application in the capacitated lot sizing problem for an agile supply chain
基於遺傳蟻群演算法的機器人全局路徑規劃研究
改進的蟻群演算法在礦山物流配送路徑優化中的研究
基於蟻群演算法的配電網路綜合優化方法
基於蟻群演算法的分類規則挖掘演算法
蟻群演算法在連續性空間優化問題中的應用
蟻群演算法在礦井通風系統優化設計中的應用
基於蟻群演算法的液壓土錨鑽機動力頭優化設計
改進蟻群演算法設計拉式膜片彈簧
計算機科學技術
基本蟻群演算法及其改進
TSP改進演算法及在PCB數控加工刀具軌跡中的應用
可靠性優化的蟻群演算法
對一類帶聚類特徵TSP問題的蟻群演算法求解
蟻群演算法理論及應用研究的進展
基於二進制編碼的蟻群優化演算法及其收斂性分析
蟻群演算法的理論及其應用
基於蟻群行為模擬的影像紋理分類
啟發式蟻群演算法及其在高填石路堤穩定性分析中的應用
蟻群演算法的研究現狀
一種快速全局優化的改進蟻群演算法及模擬
聚類問題的蟻群演算法
蟻群最優化——模型、演算法及應用綜述
基於信息熵的改進蟻群演算法及其應用
機載公共設備綜合管理系統任務分配演算法研究
基於改進蟻群演算法的飛機低空突防航路規劃
利用信息量留存的蟻群遺傳演算法
An Improved Heuristic Ant-Clustering Algorithm
改進型蟻群演算法在內燃機徑向滑動軸承優化設計中的應用
基於蟻群演算法的PID參數優化
基於蟻群演算法的復雜系統多故障狀態的決策
蟻群演算法在數據挖掘中的應用研究
基於蟻群演算法的基因聯接學習遺傳演算法
基於細粒度模型的並行蟻群優化演算法
Binary-Coding-Based Ant Colony Optimization and Its Convergence
運載火箭控制系統漏電故障診斷研究
混沌擾動啟發式蟻群演算法及其在邊坡非圓弧臨界滑動面搜索中的應用
蟻群演算法原理的模擬研究
Hopfield neural network based on ant system
蟻群演算法及其實現方法研究
分層實體製造激光頭切割路徑的建模與優化
配送網路規劃蟻群演算法
基於蟻群演算法的城域交通控制實時滾動優化
基於蟻群演算法的復合形法及其在邊坡穩定分析中的應用
Ant Colony Algorithm for Solving QoS Routing Problem
多產品間歇過程調度問題的建模與優化
基於蟻群演算法的兩地之間的最佳路徑選擇
蟻群演算法求解問題時易產生的誤區及對策
用雙向收斂蟻群演算法解作業車間調度問題
物流配送路徑安排問題的混合蟻群演算法
求解TSP問題的模式學習並行蟻群演算法
基於蟻群演算法的三維空間機器人路徑規劃
蟻群優化演算法及其應用
蟻群演算法不確定性分析
一種求解TSP問題的相遇蟻群演算法
基於蟻群優化演算法的彩色圖像顏色聚類的研究
鈑金件數控激光切割割嘴路徑的優化
基於蟻群演算法的圖像分割方法
一種基於蟻群演算法的聚類組合方法
圓排列問題的蟻群模擬退火演算法
智能混合優化策略及其在流水作業調度中的應用
蟻群演算法在QoS網路路由中的應用
一種改進的自適應路由演算法
基於蟻群演算法的煤炭運輸優化方法
基於蟻群智能和支持向量機的人臉性別分類方法
蟻群演算法在啤酒發酵控制優化中的應用
一種基於時延信息的多QoS快速自適應路由演算法
蟻群演算法中參數α、β、ρ設置的研究——以TSP問題為例
基於人工蟻群優化的矢量量化碼書設計演算法
具有自適應雜交特徵的蟻群演算法
蟻群演算法在原料礦粉混勻優化中的應用
基於多Agent的蟻群演算法在車間動態調度中的應用研究
用蟻群優化演算法求解中國旅行商問題
蟻群演算法在嬰兒營養米粉配方中的應用
蟻群演算法在機械優化設計中的應用
蟻群優化演算法的研究現狀及研究展望
蟻群優化演算法及其應用研究進展
蟻群演算法的理論與應用
簡單蟻群演算法的模擬分析
一種改進的蟻群演算法求解最短路徑問題
基於模式求解旅行商問題的蟻群演算法
一種求解TSP的混合型蟻群演算法
基於MATLAB的改進型基本蟻群演算法
動態蟻群演算法求解TSP問題
用蟻群演算法求解類TSP問題的研究
蟻群演算法求解連續空間優化問題的一種方法
用混合型螞蟻群演算法求解TSP問題
求解復雜TSP問題的隨機擾動蟻群演算法
基於蟻群演算法的中國旅行商問題滿意解
蟻群演算法的研究現狀和應用及螞蟻智能體的硬體實現
蟻群演算法概述
蟻群演算法的研究現狀及其展望
基於蟻群演算法的配電網網架優化規劃方法
用於一般函數優化的蟻群演算法
協同模型與遺傳演算法的集成
基於蟻群最優的輸電網路擴展規劃
自適應蟻群演算法
凸整數規劃問題的混合蟻群演算法
一種新的進化演算法—蛟群演算法
基於協同工作方式的一種蟻群布線系統

⑵ 機器學習中有哪些重要的優化演算法

梯度下降是非常常用的優化演算法。作為機器學習的基礎知識，這是一個必須要掌握的演算法。藉助本文，讓我們來一起詳細了解一下這個演算法。

前言

本文的代碼可以到我的Github上獲取：

https://github.com/paulQuei/gradient_descent

本文的演算法示例通過Python語言實現，在實現中使用到了numpy和matplotlib。如果你不熟悉這兩個工具，請自行在網上搜索教程。

關於優化

大多數學習演算法都涉及某種形式的優化。優化指的是改變x以最小化或者最大化某個函數的任務。

我們通常以最小化指代大多數最優化問題。最大化可經由最小化來實現。

我們把要最小化或最大化的函數成為目標函數（objective function）或准則（criterion）。

我們通常使用一個上標*表示最小化或最大化函數的x值，記做這樣：

[x^* = arg; min; f(x)]

優化本身是一個非常大的話題。如果有興趣，可以通過《數值優化》和《運籌學》的書籍進行學習。

模型與假設函數

所有的模型都是錯誤的，但其中有些是有用的。– George Edward Pelham Box

模型是我們對要分析的數據的一種假設，它是為解決某個具體問題從老洞數據中學習到的，因此它是機器學習最核心的概念。

針對一個問題，通常有大量的模型可以選擇。

本文不會深入討論這方面的內容，關於各種模型請參閱機器學習的相關書籍。本文僅以最簡單的線性模型為基礎來討論梯度下降演算法。

這里我們先介紹一下在監督學習（supervised learning）中常見的三個符號：

• m，描述訓練樣本的數量

• x，描述輸入變數或特徵

• y，描述輸出變數或者叫目標值

• 請注意，一個樣本笑或可能有很多的特徵，因此x和y通常是一個向量。不過在剛開始學習的時候，為了便於理解，你可以暫時理解為這就是一個具體的數值。

訓練集會包含很多的樣本，我們用 表示其中第i個樣本。

x是數據樣本的特徵，y是其目標值。例如，在預測房價的模型中，x是房子的各種信息，例如：面積，樓層，位置等等，y是房子的價格。在圖像識別的任務中，x是圖形的所有像素點數據，y是圖像中包含的目標對象。

我們是希望尋找一個函數，將x映射到y，這個函數要足夠的好，以至於能夠預測對應的y。由於歷史原因，這個函數叫做假設函數（hypothesis function）。

學習的過程如下圖所示。即：首先根據已有的數據（稱之為訓練集）訓練我們的演算法模型，然後根據模型的假設函數來進行新數據的預測。

線性模型（linear model）正如其名稱那樣：是希望通過一個直線的形式來描述模式。線性模型的假設函數如下所示：

[h_{ heta}(x) = heta_{0} + heta_{1} * x]

這個公式對於大家來說應該都是非常簡單的。如果把它繪制出來，其實就是一條直線。

下圖是一個具體的例子，即： 的圖形：

在實際的機器學習工程中碰含伍，你會擁有大量的數據。這些數據會來自於某個數據源。它們存儲在csv文件中，或者以其他的形式打包。

但是本文作為演示使用，我們通過一些簡單的代碼自動生成了需要的數據。為了便於計算，演示的數據量也很小。

import numpy as np

max_x = 10
data_size = 10
theta_0 = 5
theta_1 = 2

def get_data:
x = np.linspace(1, max_x, data_size)
noise = np.random.normal(0, 0.2, len(x))
y = theta_0 + theta_1 * x + noise
return x, y


這段代碼很簡單，我們生成了x范圍是 [1, 10] 整數的10條數據。對應的y是以線性模型的形式計算得到，其函數是：。現實中的數據常常受到各種因素的干擾，所以對於y我們故意加上了一些高斯雜訊。因此最終的y值為比原先會有輕微的偏離。

最後我們的數據如下所示：

x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
y = [6.66, 9.11, 11.08, 12.67, 15.12, 16.76, 18.75, 21.35, 22.77, 24.56]


我們可以把這10條數據繪制出來這樣就有一個直觀的了解了，如下圖所示：

雖然演示用的數據是我們通過公式計算得到的。但在實際的工程中，模型的參數是需要我們通過數據學習到的。所以下文我們假設我們不知道這里線性模式的兩個參數是什麼，而是通過演算法的形式求得。

最後再跟已知的參數進行對比以驗證我們的演算法是否正確。

有了上面的數據，我們可以嘗試畫一條直線來描述我們的模型。

例如，像下面這樣畫一條水平的直線：

很顯然，這條水平線離數據太遠了，非常的不匹配。

那我們可以再畫一條斜線。

我們初次畫的斜線可能也不貼切，它可能像下面這樣：

最後我們通過不斷嘗試，找到了最終最合適的那條，如下所示：

梯度下降演算法的計算過程，就和這種本能式的試探是類似的，它就是不停的迭代，一步步的接近最終的結果。


代價函數

上面我們嘗試了幾次通過一條直線來擬合（fitting）已有的數據。

二維平面上的一條直線可以通過兩個參數唯一的確定，兩個參數的確定也即模型的確定。那如何描述模型與數據的擬合程度呢？答案就是代價函數。

代價函數（cost function）描述了學習到的模型與實際結果的偏差程度。以上面的三幅圖為例，最後一幅圖中的紅線相比第一條水平的綠線，其偏離程度（代價）應該是更小的。

很顯然，我們希望我們的假設函數與數據盡可能的貼近，也就是說：希望代價函數的結果盡可能的小。這就涉及到結果的優化，而梯度下降就是尋找最小值的方法之一。

• 代價函數也叫損失函數。

對於每一個樣本，假設函數會依據計算出一個估算值，我們常常用來表示。即 。

很自然的，我們會想到，通過下面這個公式來描述我們的模型與實際值的偏差程度：

[(h_ heta(x^i) - y^i)^2 = (widehat{y}^{i} - y^i)^2 = ( heta_{0} + heta_{1} * x^{i} - y^{i})^2]

請注意， 是實際數據的值， 是我們的模型的估算值。前者對應了上圖中的離散點的y坐標，後者對應了離散點在直線上投影點的y坐標。

每一條數據都會存在一個偏差值，而代價函數就是對所有樣本的偏差求平均值，其計算公式如下所示：

[L( heta) = frac {1}{m} sum_{i=1}^{m}(h_ heta(x^i) - y^i)^2 = frac {1}{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i})^2]

當損失函數的結果越小，則意味著通過我們的假設函數估算出的結果與真實值越接近。這也就是為什麼我們要最小化損失函數的原因。

• 不同的模型可能會用不同的損失函數。例如，logistic回歸的假設函數是這樣的：。其代價函數是這樣的：

藉助上面這個公式，我們可以寫一個函數來實現代價函數：

def cost_function(x, y, t0, t1):
cost_sum = 0
for i in range(len(x)):
cost_item = np.power(t0 + t1 * x[i] - y[i], 2)
cost_sum += cost_item
return cost_sum / len(x)


這個函數的代碼應該不用多做解釋，它就是根據上面的完成計算。

我們可以嘗試選取不同的 和 組合來計算代價函數的值，然後將結果繪制出來：

import numpy as np
import matplotlib.pyplot as plt

from matplotlib import cm
from mpl_toolkits.mplot3d import Axes3D

theta_0 = 5
theta_1 = 2

def draw_cost(x, y):
fig = plt.figure(figsize=(10, 8))
ax = fig.gca(projection='3d')
scatter_count = 100
radius = 1
t0_range = np.linspace(theta_0 - radius, theta_0 + radius, scatter_count)
t1_range = np.linspace(theta_1 - radius, theta_1 + radius, scatter_count)
cost = np.zeros((len(t0_range), len(t1_range)))
for a in range(len(t0_range)):
for b in range(len(t1_range)):
cost[a][b] = cost_function(x, y, t0_range[a], t1_range[b])
t0, t1 = np.meshgrid(t0_range, t1_range)

ax.set_xlabel('theta_0')
ax.set_ylabel('theta_1')
ax.plot_surface(t0, t1, cost, cmap=cm.hsv)


在這段代碼中，我們對 和 各自指定了一個范圍進行100次的采樣，然後以不同的 組合對來計算代價函數的值。

如果我們將所有點的代價函數值繪制出來，其結果如下圖所示：

從這個圖形中我們可以看出，當 越接近 [5, 2]時其結果（偏差）越小。相反，離得越遠，結果越大。


直觀解釋

從上面這幅圖中我們可以看出，代價函數在不同的位置結果大小不同。

從三維的角度來看，這就和地面的高低起伏一樣。最高的地方就好像是山頂。

而我們的目標就是：從任意一點作為起點，能夠快速尋找到一條路徑並以此到達圖形最低點（代價值最小）的位置。

而梯度下降的演算法過程就和我們從山頂想要快速下山的做法是一樣的。

在生活中，我們很自然會想到沿著最陡峭的路往下行是下山速度最快的。如下面這幅圖所示：

針對這幅圖，細心的讀者可能很快就會有很多的疑問，例如：

• 對於一個函數，怎麼確定下行的方向？

• 每一步該往前走多遠？

• 有沒有可能停留在半山腰的平台上？

這些問題也就是本文接下來要討論的內容。


演算法描述

梯度下降演算法最開始的一點就是需要確定下降的方向，即：梯度。

我們常常用 來表示梯度。

對於一個二維空間的曲線來說，梯度就是其切線的方向。如下圖所示：

而對於更高維空間的函數來說，梯度由所有變數的偏導數決定。

其表達式如下所示：

[ abla f({ heta}) = ( frac{partial f({ heta})}{partial heta_1} , frac{partial f({ heta})}{partial heta_2} , ... , frac{partial f({ heta})}{partial heta_n} )]

在機器學習中，我們主要是用梯度下降演算法來最小化代價函數，記做：

[ heta ^* = arg min L( heta)]

其中，L是代價函數，是參數。

梯度下降演算法的主體邏輯很簡單，就是沿著梯度的方向一直下降，直到參數收斂為止。

記做：

[ heta ^{k + 1}_i = heta^{k}_i - lambda abla f( heta^{k})]

• 這里的下標i表示第i個參數。 上標k指的是第k步的計算結果，而非k次方。在能夠理解的基礎上，下文的公式中將省略上標k。

這里有幾點需要說明：

• 收斂是指函數的變化率很小。具體選擇多少合適需要根據具體的項目來確定。在演示項目中我們可以選擇0.01或者0.001這樣的值。不同的值將影響演算法的迭代次數，因為在梯度下降的最後，我們會越來越接近平坦的地方，這個時候函數的變化率也越來越小。如果選擇一個很小的值，將可能導致演算法迭代次數暴增。

• 公式中的 稱作步長，也稱作學習率（learning rate）。它決定了每一步往前走多遠，關於這個值我們會在下文中詳細講解。你可以暫時人為它是一個類似0.01或0.001的固定值。

• 在具體的項目，我們不會讓演算法無休止的運行下去，所以通常會設置一個迭代次數的最大上限。


線性回歸的梯度下降

有了上面的知識，我們可以回到線性模型代價函數的梯度下降演算法實現了。

首先，根據代價函數我們可以得到梯度向量如下：

[ abla f({ heta}) = (frac{partial L( heta)}{ partial heta_{0}}, frac{ partial L( heta)}{ partial heta_{1}}) = (frac {2}{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) , frac {2}{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) x^{i})]

接著，將每個偏導數帶入迭代的公式中，得到：

[ heta_{0} := heta_{0} - lambda frac{partial L( heta_{0})}{ partial heta_{0}} = heta_{0} - frac {2 lambda }{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) heta_{1} := heta_{1} - lambda frac{partial L( heta_{1})}{ partial heta_{1}} = heta_{1} - frac {2 lambda }{m} sum_{i=1}^{m}( heta_{0} + heta_{1} * x^{i} - y^{i}) x^{i}]

由此就可以通過代碼實現我們的梯度下降演算法了，演算法邏輯並不復雜：

learning_rate = 0.01

def gradient_descent(x, y):
t0 = 10
t1 = 10
delta = 0.001
for times in range(1000):
sum1 = 0
sum2 = 0
for i in range(len(x)):
sum1 += (t0 + t1 * x[i] - y[i])
sum2 += (t0 + t1 * x[i] - y[i]) * x[i]
t0_ = t0 - 2 * learning_rate * sum1 / len(x)
t1_ = t1 - 2 * learning_rate * sum2 / len(x)
print('Times: {}, gradient: [{}, {}]'.format(times, t0_, t1_))
if (abs(t0 - t0_) < delta and abs(t1 - t1_) < delta):
print('Gradient descent finish')
return t0_, t1_
t0 = t0_
t1 = t1_
print('Gradient descent too many times')
return t0, t1


這段代碼說明如下：

• 我們隨機選擇了 都為10作為起點

• 設置最多迭代1000次

• 收斂的范圍設為0.001

• 學習步長設為0.01

如果我們將演算法迭代過程中求得的線性模式繪制出來，可以得到下面這幅動態圖：

最後演算法得到的結果如下：


Times: 657, gradient: [5.196562662718697, 1.952931052920264]
Times: 658, gradient: [5.195558390180733, 1.9530753071808193]
Times: 659, gradient: [5.194558335124868, 1.9532189556399233]
Times: 660, gradient: [5.193562479839619, 1.9533620008416623]
Gradient descent finish


從輸出中可以看出，演算法迭代了660次就收斂了。這時的結果[5.193562479839619, 1.9533620008416623]，這已經比較接近目標值 [5, 2]了。如果需要更高的精度，可以將delta的值調的更小，當然，此時會需要更多的迭代次數。


高維擴展

雖然我們舉的例子是二維的，但是對於更高維的情況也是類似的。同樣是根據迭代的公式進行運算即可：

[ heta_{i} = heta_{i} - lambda frac {partial L( heta)}{partial heta_i} = heta_{i} - frac{2lambda}{m} sum_{i=1}^{m}(h_ heta(x^{k})-y^k)x_i^k]

這里的下標i表示第i個參數，上標k表示第k個數據。


梯度下降家族BGD

在上面的內容中我們看到，演算法的每一次迭代都需要把所有樣本進行遍歷處理。這種做法稱為之Batch Gradient Descent，簡稱BGD。作為演示示例只有10條數據，這是沒有問題的。

但在實際的項目中，數據集的數量可能是幾百萬幾千萬條，這時候每一步迭代的計算量就會非常的大了。

於是就有了下面兩個變種。


SGD

Stochastic Gradient Descent，簡稱SGD，這種演算法是每次從樣本集中僅僅選擇一個樣本來進行計算。很顯然，這樣做演算法在每一步的計算量一下就少了很多。

其演算法公式如下：

[ heta_{i} = heta_{i} - lambda frac {partial L( heta)}{partial heta_i} = heta_{i} - lambda(h_ heta(x^k)-y^k)x_i^k]

當然，減少演算法計算量也是有代價的，那就是：演算法結果會強依賴於隨機取到的數據情況，這可能會導致演算法的最終結果不太令人滿意。


MBGD

以上兩種做法其實是兩個極端，一個是每次用到了所有數據，另一個是每次只用一個數據。

我們自然就會想到兩者取其中的方法：每次選擇一小部分數據進行迭代。這樣既避免了數據集過大導致每次迭代計算量過大的問題，也避免了單個數據對演算法的影響。

這種演算法稱之為Mini-batch Gradient Descent，簡稱MBGD。

其演算法公式如下：

[ heta_{i} = heta_{i} - lambda frac {partial L( heta)}{partial heta_i} = heta_{i} - frac{2lambda}{m} sum_{i=a}^{a + b}(h_ heta(x^k)-y^k)x_i^k]

當然，我們可以認為SGD是Mini-batch為1的特例。

針對上面提到的演算法變種，該如何選擇呢？

下面是Andrew Ng給出的建議：

• 如果樣本數量較小（例如小於等於2000），選擇BGD即可。

• 如果樣本數量很大，選擇 來進行MBGD，例如：64，128，256，512。

下表是 Optimization for Deep Learning 中對三種演算法的對比

方法准確性更新速度內存佔用在線學習BGD好慢高否SGD好（with annealing）快低是MBGD好中等中等是
演算法優化

式7是演算法的基本形式，在這個基礎上有很多人進行了更多的研究。接下來我們介紹幾種梯度下降演算法的優化方法。


Momentum

Momentum是動量的意思。這個演算法的思想就是藉助了動力學的模型：每次演算法的迭代會使用到上一次的速度作為依據。

演算法的公式如下：

[v^t = gamma v^{t - 1} + lambda abla f( heta) heta = heta - v_t]

對比式7可以看出，這個演算法的主要區別就是引入了，並且，每個時刻的受前一個時刻的影響。

從形式上看，動量演算法引入了變數 v 充當速度角色——它代表參數在參數空間移動的方向和速率。速度被設為負梯度的指數衰減平均。名稱動量來自物理類比，根據牛頓運動定律，負梯度是移動參數空間中粒子的力。動量在物理學上定義為質量乘以速度。在動量學習演算法中，我們假設是單位質量，因此速度向量 v 也可以看作是粒子的動量。

對於可以取值0，而是一個常量，設為0.9是一個比較好的選擇。

下圖是momentum演算法的效果對比：

對原來的演算法稍加修改就可以增加動量效果：

def gradient_descent_with_momentum(x, y):
t0 = 10
t1 = 10
delta = 0.001
v0 = 0
v1 = 0
gamma = 0.9
for times in range(1000):
sum1 = 0
sum2 = 0
for i in range(len(x)):
sum1 += (t0 + t1 * x[i] - y[i])
sum2 += (t0 + t1 * x[i] - y[i]) * x[i]
v0 = gamma * v0 + 2 * learning_rate * sum1 / len(x)
v1 = gamma * v1 + 2 * learning_rate * sum2 / len(x)
t0_ = t0 - v0
t1_ = t1 - v1
print('Times: {}, gradient: [{}, {}]'.format(times, t0_, t1_))
if (abs(t0 - t0_) < delta and abs(t1 - t1_) < delta):
print('Gradient descent finish')
return t0_, t1_
t0 = t0_
t1 = t1_
print('Gradient descent too many times')
return t0, t1


以下是該演算法的輸出：


Times: 125, gradient: [4.955453758569991, 2.000005017897775]
Times: 126, gradient: [4.955309381126545, 1.9956928964532015]
Times: 127, gradient: [4.9542964317327005, 1.9855674828684156]
Times: 128, gradient: [4.9536358220657, 1.9781180992510465]
Times: 129, gradient: [4.95412496254411, 1.9788858350530971]
Gradient descent finish


從結果可以看出，改進的演算法只用了129次迭代就收斂了。速度比原來660次快了很多。

同樣的，我們可以把演算法計算的過程做成動態圖：

對比原始的演算法過程可以看出，改進演算法最大的區別是：在尋找目標值時會在最終結果上下跳動，但是越往後跳動的幅度越小，這也就是動量所產生的效果。


Learning Rate 優化

至此，你可能還是好奇該如何設定學習率的值。

事實上，這個值的選取需要一定的經驗或者反復嘗試才能確定。

• 《深度學習》一書中是這樣描述的：「與其說是科學，這更像是一門藝術，我們應該謹慎地參考關於這個問題的大部分指導。」。

關鍵在於，這個值的選取不能過大也不能過小。

如果這個值過小，會導致每一次迭代的步長很小，其結果就是演算法需要迭代非常多的次數。

那麼，如果這個值過大會怎麼樣呢？其結果就是：演算法可能在結果的周圍來回震盪，卻落不到目標的點上。下面這幅圖描述了這個現象：

事實上，學習率的取值未必一定要是一個常數，關於這個值的設定有很多的研究。

下面是比較常見的一些改進演算法。


AdaGrad

AdaGrad是Adaptive Gradient的簡寫，該演算法會為每個參數設定不同的學習率。它使用歷史梯度的平方和作為基礎來進行計算。

其演算法公式如下：

[ heta_i = heta_i - frac{lambda}{sqrt{G_t + epsilon}} abla f( heta)]

對比式7，這里的改動就在於分號下面的根號。

根號中有兩個符號，第二個符號比較好理解，它就是為了避免除0而人為引入的一個很小的常數，例如可以設為：0.001。

第一個符號的表達式展開如下：

[G_t = sum_{i = 1}^{t} abla f( heta){i} abla f( heta){i}^{T}]

這個值其實是歷史中每次梯度的平方的累加和。

AdaGrad演算法能夠在訓練中自動的對learning rate進行調整，對於出現頻率較低參數採用較大的學習率；相反，對於出現頻率較高的參數採用較小的學習率。因此，Adagrad非常適合處理稀疏數據。

但該演算法的缺點是它可能導致學習率非常小以至於演算法收斂非常的慢。

關於這個演算法的直觀解釋可以看李宏毅教授的視頻課程：ML Lecture 3-1: Gradient Descent。


RMSProp

RMS是Root Mean Square的簡寫。RMSProp是AI教父Geoff Hinton提出的一種自適應學習率方法。AdaGrad會累加之前所有的梯度平方，而RMSProp僅僅是計算對應的平均值，因此可緩解Adagrad演算法學習率下降較快的問題。

該演算法的公式如下：

[E[ abla f( heta_{i})^2]^{t} = gamma E[ abla f( heta_{i})^2]^{t - 1} + (1-gamma)( abla f( heta_{i})^{t})^{2} heta_i = heta_i - frac{lambda}{sqrt{E[g^2]^{t+1} + epsilon}} abla f( heta_{i})]

類似的，是為了避免除0而引入。 是衰退參數，通常設為0.9。

這里的 是t時刻梯度平方的平均值。


Adam

Adam是Adaptive Moment Estimation的簡寫。它利用梯度的一階矩估計和二階矩估計動態調整每個參數的學習率。

Adam的優點主要在於經過偏置校正後，每一次迭代學習率都有個確定范圍，使得參數比較平穩。

該演算法公式如下：

[m^{t} = eta_{1} m^{t-1} + (1-eta_{1}) abla f( heta) v^{t} = eta_{2} v^{t-1} + (1-eta_{2}) abla f( heta)^2 widehat{m}^{t} = frac{m^{t}}{1 - eta^{t}_1} widehat{v}^{t} = frac{v^{t}}{1 - eta^{t}_2} heta = heta - frac{lambda}{sqrt{widehat{v}^{t}} + epsilon}widehat{m}^{t}]

，分別是對梯度的一階矩估計和二階矩估計。， 是對，的校正，這樣可以近似為對期望的無偏估計。

Adam演算法的提出者建議 默認值為0.9，默認值為0.999，默認值為 。

在實際應用中 ，Adam較為常用，它可以比較快地得到一個預估結果。


優化小結

這里我們列舉了幾種優化演算法。它們很難說哪種最好，不同的演算法適合於不同的場景。在實際的工程中，可能需要逐個嘗試一下才能確定選擇哪一個，這個過程也是目前現階段AI項目要經歷的工序之一。

實際上，該方面的研究遠不止於此，如果有興趣，可以繼續閱讀 《Sebastian Ruder: An overview of gradient descent optimization algorithms》 這篇論文或者 Optimization for Deep Learning 這個Slides進行更多的研究。

由於篇幅所限，這里不再繼續展開了。


演算法限制

梯度下降演算法存在一定的限制。首先，它要求函數必須是可微分的，對於不可微的函數，無法使用這種方法。

除此之外，在某些情況下，使用梯度下降演算法在接近極值點的時候可能收斂速度很慢，或者產生Z字形的震盪。這一點需要通過調整學習率來迴避。

另外，梯度下降還會遇到下面兩類問題。


局部最小值

局部最小值（Local Minima）指的是，我們找到的最小值僅僅是一個區域內的最小值，而並非全局的。由於演算法的起點是隨意取的，以下面這個圖形為例，我們很容易落到局部最小值的點裡面。

這就是好像你從上頂往下走，你第一次走到的平台未必是山腳，它有可能只是半山腰的一個平台的而已。

演算法的起點決定了演算法收斂的速度以及是否會落到局部最小值上。

壞消息是，目前似乎沒有特別好的方法來確定選取那個點作為起點是比較好的，這就有一點看運氣的成分了。多次嘗試不同的隨機點或許是一個比較好的方法，這也就是為什麼做演算法的優化這項工作是特別消耗時間的了。

但好消息是：

• 對於凸函數或者凹函數來說，不存在局部極值的問題。其局部極值一定是全局極值。

• 最近的一些研究表明，某些局部極值並沒有想像中的那麼糟糕，它們已經非常的接近全局極值所帶來的結果了。


鞍點

除了Local Minima，在梯度下降的過程中，還有可能遇到另外一種情況，即：鞍點（Saddle Point）。鞍點指的是我們找到點某個點確實是梯度為0，但它卻不是函數的極值，它的周圍既有比它小的值，也有比它大的值。這就好像馬鞍一樣。

如下圖所示：

多類隨機函數表現出以下性質：在低維空間中，局部極值很普遍。但在高維空間中，局部極值比較少見，而鞍點則很常見。

不過對於鞍點，可以通過數學方法Hessian矩陣來確定。關於這點，這里就不再展開了，有興趣的讀者可以以這里提供的幾個鏈接繼續探索。


參考資料與推薦讀物

• Wikipeida: Gradient descent

• Sebastian Ruder: An overview of gradient descent optimization algorithms

• 吳恩達：機器學習

• 吳恩達：深度學習

• Peter Flach：機器學習

• 李宏毅 - ML Lecture 3-1: Gradient Descent

• PDF: 李宏毅 - Gradient Descent

• Intro to optimization in deep learning: Gradient Descent

• Intro to optimization in deep learning: Momentum, RMSProp and Adam

• Stochastic Gradient Descent – Mini-batch and more

• 劉建平Pinard - 梯度下降（Gradient Descent）小結

• 多元函數的偏導數、方向導數、梯度以及微分之間的關系思考

• [Machine Learning] 梯度下降法的三種形式BGD、SGD以及MBGD

• 作者：阿Paul https://paul.pub/gradient-descent/