演算法對比圖

1. 演算法時間復雜度比較：根號n與logn相比哪個更優優多少試根據下圖猜想其演算法

米勒羅賓是logn的演算法，但是實際應用上它並不穩定，一般在范圍較大（int64范圍）才會用，一般的情況用的都是sqrt(n)的演算法，但是在需要判斷大量素數的情況下（假設判斷次數為m），一般是比較m*sqrt(n)和n的大小，如果前者小就暴力判斷，否則用篩法會更快。

然後比較，在不考慮常數的情況下是logn更優，但是演算法常數導致在數據較小的一些情況下sqrt(n)反而更快。

第一個根號n的：

#include<cmath>

inlineboolisPrime(intx){
if(x==2){returntrue;}
if(x<2){returnfalse;}
intpos=int(sqrt(x))+1;
for(inti=2;i<=pos;++i){
if(x%i==0){returnfalse;}
}
returntrue;
}

然後logn的米勒羅賓你可以看下博客網頁鏈接

然後提供一個篩法的代碼（stl版本）

#include<vector>

boolvis[MAXNUM];//MAXNUM就是最大數字
std::vector<int>primes;//儲存素數

inlinevoidgetPrimes(intmaxn){
for(inti=2;i<=maxn;++i){
if(!vis[i]){primes.push_back(i);}
for(size_tj=0;j<primes.size()&&primes[j]*i<=maxn;++j){
vis[primes[j]*i]=true;
}
}
}

實際應用一般用篩法或者sqrt(n)演算法，只有大數據才會用米勒羅賓

2. matlab怎麼把兩個不同演算法的模擬圖放在一個圖里作比較

在畫春物完一張圖後，加一條hold on語句，再畫第二者森羨張圖，以此類推，就可以在一張圖上花畫多條曲線首拍，另外可以通過代碼設置成不同顏色或者線形加以區分

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

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

前言

本文的代碼可以到我的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/

4. 從頭理解JPS尋路演算法

本文的思路受到博客： http://blog.sina.com.cn/s/blog_4a5c75d40102wo5l.html
和論文： http://www.doc88.com/p-6099778647749.html 的啟發和借鑒。
JPS(jump point search)演算法實際上是對A 尋路算李祥桐法的一個改進，即在擴展搜索節點時，提出了更優化的策略，A 在擴展節點時會把節點所有鄰居都考慮進去，這樣openlist中點的數量會很多，搜索效率較慢。JPS演算法通過尋找跳點的方式，排除了大量不感興趣的點，減少了openlist中搜索的點的數量，速度大大提高。

水平(垂直)搜索：如圖右邊部分描述，點1和4如果經過x到達，還不如從點p(x)到達，所以不用考慮點1,4，同理繼續向右搜索時，點2,5和點3,6，都是類似的情況，直到遇到黑色的障礙，沒有發現感興趣的點，x處水平方向搜索完成，垂直方向搜索類似。如圖左邊部分描述，在點x處向右搜索至點y時，點y有一個強迫鄰居(點7)，因此y是從點x處沿水平方向搜索的一個跳點，需要將y加入到openlist中。水平搜索結束。

對角搜索：斜向搜索時，需要先在當前點的水平和垂直方向搜索一下，看能否找到感興趣的點，如果找到，則將當前點加到openlist，結束斜向搜索，如果找不到，則繼續宴卜斜向多走一步，繼續，直到找到感興趣的點或者斜向方向遇到障礙。

一條完整路線的搜索過程：

搜索演算法：

下面兩張對比圖，摘自上面的論文，可以看出，JPS演算法實在優秀。

github鏈接

上圖中紅色塊為節點x，基於前節點為P(x)的情況下的自然鄰居節點。而被迫鄰居則是圖中綠色的方塊（其對稱情況未畫出）。x被迫鄰居包含三層隱藏含義：首先被迫鄰居的位置是基於P(x)、x、阻擋塊的相對關系定的，如第三個圖所示，如果第三個圖中，P(x)的位置在節點6的位置，那麼綠色方塊就不是x的被迫鄰居了。其次，被迫鄰居一點是考察非自然鄰居的節點。最後被迫鄰居一定是P(x)經過x到達才能取得最短路徑的點。

起點S，終點T，黑色塊為阻擋黃色塊為跳點，紅色箭頭是搜索方向，但是沒有找到跳點，綠色箭頭表示找到跳點。橫坐標A-N，縱坐標1-10。

起始位置S，將A10加入openlist里，開始演算法流程。
從openlist里取出代價最小的節點(現在為S)，當前節點沒有方向，所以需要搜索8個方向，只有右上方B9點是跳點。因為根據跳點定義iii，斜向搜索時，需要在兩個分量方向查找跳點，右方是牆壁，略過，上方B8點有強迫鄰居點C7，所以B8是跳點（根據跳點定義ii），所以B9是跳點。將B9加入openlist里。A10處理完後，將其從openlist中移除，加入closelist里。

從openlist中取出B9點，該點的父親是S，所以搜索方向為右斜上，需要在右斜上，右方，上方搜索跳點，只有B8滿足要求，將B8加入openlist。處理完B9點將其移到closelist。

從openlist取出B8點，該點搜索哪坦方向為上，B8有被鄰居C7點，在斜上方搜索跳點，可以看出D8是C7的被迫鄰居，所以C7是跳點，B8處繼續向上搜索結束。

從openlist中取出C7點。需要搜索右上，右，上三個方向。水平搜索時發現被迫鄰居D8，加入openlist。右上搜索時發現跳點G3（因其在上方搜索時發現具有被迫鄰居節點的G2），將G3加入openlist。C7點處理結束。

取出G3點（為啥是G3，而不是D8點呢，因為從總代價來說G3比D8更小，總代價=已經走過的距離 + 估值，估值可採用曼哈頓距離或者高斯距離），需要搜索右上，右，上三個方向。向上搜索到跳點G2。

其餘點路徑在圖上標注，就不再重復了。

(1) 若current方向是直線
i. 如果current左後方不可走且左方可走，則沿current左前方和左方尋找跳點。
ii. 如果current當前方向可走，則沿current方向尋找跳點。
iii. 如果current右後方不可走且右方可走，則沿current右前方和右方尋找跳點。
(2) 若current方向是斜線
i. 如果當前方向的水平分量可走，則沿current方向的水平分量方向尋找跳點。
ii. 如果當前方向可走，沿current方向尋找跳點。
iii. 如果當前方向的垂直分量可走，則沿current方向的垂直分量方向尋找跳點。

上述演算法流程是建立在斜向不可穿過阻擋基礎上。

5. 6. Actor-Critic演算法

本文主要介紹如下幾個內容：

首先我們肆譽還是回顧一下之前提到的REINFORCE演算法：

在這個演算法的第二步驟裡面我們引入了「reward to go」這一項洞皮，該 表示了從當前的時間步t開始，所有的reward的期望之和。

我們可以把這個由casuality引出的期望稱之為「true expected reward-to-go」， 之所以我們這里考慮的是期望，是因為裂顫段我們在實際中每個trajectory采樣出來都是不一樣的，我們需要把這不同的采樣結果進行最後的平均以求期望。

優勢函數（Advantage function）

我們在policy gradient的方法中為了降低variance，也考慮過引入一個基線來減少梯度的方差。這里我們更進一步一點，我們使用 代替原來的"reward to go"，並且使用值函數（V function）去代替原來的baseline,這樣我們就有了新的估計值，即優勢函數。

與原始版本的baseline相比，原來的估計是無偏估計，但是在單個采樣估計中具有很高的方差（variance），現在使用了優勢函數之後可以降低方差。他們的比較如下圖：

三個函數的比較：Q, V and A

在模型擬合的階段，我們需要去評估結果，這個時候就要考慮去擬合Q, V 還是A。他們之間是有密切關系的：

其中對於Q函數他是在已經確定了 的情況下，並且已經產生了 ,即我們可以寫為:

既然他們是有關系的，那麼我們在實際使用的時候只需要計算一個期望函數 .

對於如何去評估一個Policy是好是壞，我們從 的定義可以知道，強化學習的目標函數其實就是這個值關於初始狀態 的期望值。

這里有兩種Monte Carlo的方法來評估：

第一種是在一個sample裡面累積 reward，第二種還考慮了多個sample的平均。

我們從上面的第一種簡單得到 的方法中得到了訓練數據，我們就可以把評估的問題轉換成了一個監督學習的問題：

形式化理解為，我們用同一個函數去擬合了很多很多的樣本。

上面使用的方法會有很高的方差，在實際中我們是用一種近似的方式去減少方差：

這里我們是直接使用了之前的V值（ ）去近似，然後得到了訓練數據的樣本 ,這種方式稱之為bootstrap。

有了前面的基礎，介紹了如何去擬合 ，計算優勢函數我們就能夠導出Actor-critic演算法，

上面的actor-critic演算法里第一步還需要采樣一整個trajectory。想要變成每次只採樣一個狀態就需要先引入Discount factors的概念。

因為值函數V的定義是當前狀態以後所有反饋值的和，在有限步長的任務中沒有問題，但是如果是一個無限步長的任務，那麼這個值有可能是無限大的。因此需要引入一個折損系數 ，它的意義在於讓離當前狀態比較近的反饋值更重要，而離得比較遠的可能不那麼看重.

上面舉了個例子，在機器人做操作這種episodic tasks的時候是有限步長的就不需要discount factor，但是另外一種continuous任務，就不需要設定episodic所以這種情況加入discount factor就很重要。

加入了Dicount factor，我們對應的目標函數也變化：

這種情況下MC policy gradients有兩種選擇：

第一種是直接從當前時間t開始加系數 ，而第二種是從最開始t=1就開始加系數 。然後再通過利用causasity去掉 之前的反饋值。這樣最終兩種寫法的系數還是有一些差別。

一般情況下兩種方式有兩種不同的解釋和應用場景。第二種寫法是對應著帶有死亡狀態的MDP形式。系數從第一步就開始加入，這就意味著這種寫法更在意從頭開始的動作，對於往後的動作給的關注更少。

而第一種寫法是從時刻t開始加系數，也就是說它會一直在意從當前時刻開始的動作。這種形式一般用在一直連續運動的場景里。

第一種寫法實際上不是一個正確的加了discount factor後的寫法。它相當於是對平均反饋值加了一個系數來減小方差，它去除掉那些距離太遠的反饋值的影響，因為可能太遠了已經沒有了意義。當然這樣會是平均反饋的有偏估計。

第一種寫法實際中更常用，也就是作為減小方差的方式。而第二種寫法能夠向我們解釋在經典的場景里discount factor的意義。

加入了discount factors之後的actor-critic演算法可以採用對每個狀態進行採用的形式，這樣就有了online形式的演算法，兩種演算法對比如下

在實際實現actor-critic演算法的時候可以選擇兩種結構。一種是讓策略函數與值函數分別訓練。這樣做可能比較簡單而且穩定，但是這樣就不能共享一些提取特徵的網路層。第二種是兩種函數共享一部分網路，這樣就能夠共享前面提取特徵的部分。

實際中如果實現一個online形式的演算法，最好的做法並不是對每一個狀態都做一次更新，而是得到足夠多的樣本里作為一個batch來更新。因為這樣能夠減小更新的方差。而實現這樣的方式也有兩種，一種是同步的一種是非同步的。

我們把AC和PG對比一下，AC一般會因為有critic所以有更低的方差，但是如果critic不好那麼他的bias會很大。PG是沒有bias的，但是他的方差很高。把他們結合在一起就能產生比較好的unbias,低方差的演算法。

之前用到作為baseline的函數一直都是V，實際上Q也能夠作為baseline。只不過這樣做實際上得到的不是一個advantage函數，在期望上得到一個期望為0的函數。因為減小了這部分的值，就能夠減小對應部分的方差。

但是期望為0直接帶入得不到目標函數的梯度值，因此計算梯度值的時候還需要把 以期望的形式修正回來，這樣目標函數梯度值的期望與原來保持一致

目前我們有兩種得到advantage函數的形式，一種 是bootstrap的，有更低的方差，但是有比較高的偏差。第二種是蒙特卡洛采樣減去估計值的 ，這樣做沒有偏差，但是方差比較大。因此我們需要想辦法把這兩種結合起來。

我們可以使用n-step和Eligibility trace的方法來改善。

使用n-step的直覺如下圖：

6. java 對比圖片相似度的演算法。。說說想法也行

每張圖分成四塊，將每部分的圖片混成一種純色，對比這四個純色可以篩掉大部分的圖片

7. RAFT與PBFT

【一．raft演算法】

因為網上已經有大量文章對raft演算法進行過詳細的介紹，因此這部分只會簡單的闡述演算法的基本原理和流程。raft演算法包含三種角色，分別是：跟隨者（follower），候選人（candidate）和領導者（leader）。集群中的一個節點在某一時刻只能是這三種狀態的其中一種，這三種角色是可以隨著時間和條件的變化而互相轉換的。

raft演算法主要有兩個過程：一個過程是領導者選舉，另一個過程是日誌復制，其中日誌復制過程會分記錄日誌和提交數據兩個階段。raft演算法支持最大的容錯故障節點是（N-1）/2，其中N為 集群中總的節點數量。

國外有一個動畫介紹raft演算法介紹的很透徹，鏈接地址在這里[1]。這個動畫主要包含三部分內容，第一部分介紹簡單版的領導者選舉和日誌復制的過程，第二部分內容介紹詳細版的領導者選舉和日誌復制的過程，第三部分內容介紹的是如果遇到網路分區（腦裂），raft演算法是如何恢復網路一致的。有興趣的朋友可以結合這個動畫來更好的理解raft演算法。

【二．pbft演算法】

pbft演算法的提出主要是為了解決拜占庭將軍問題。什麼是拜占庭將軍問題呢？拜占庭位於如今的土耳其的伊斯坦布爾，是古代東羅馬帝國的首都。拜占庭羅馬帝國國土遼闊，為了達到防禦目的，每塊封地都駐扎一支由將軍統領的軍隊，每個軍隊都分隔很遠，將軍與將軍之間只能靠信差傳遞消息。 在戰爭的時候，拜占庭軍隊內所有將軍必需達成一致的共識，決定是否有贏的機會才去攻打敵人的陣營。但是，在軍隊內有可能存有叛徒和敵軍的間諜，左右將軍們的決定影響將軍們達成一致共識。在已知有將軍是叛徒的情況下，其餘忠誠的將軍如何達成一致協議的問題，這就是拜占庭將軍問題。

下圖列出了raft演算法和pbft演算法在適用環境，通信復雜度，最大容錯節點數和流程上的對比。

關於兩個演算法的適用環境和最大容錯節點數，前文已經做過闡述，這里不再細說。而對於演算法通信復雜度，為什麼raft是o（n），而pbft是o（n^2）呢？這里主要考慮演算法的共識過程。

對於raft演算法，核心共識過程是日誌復制這個過程，這個過程分兩個階段，一個是日誌記錄，一個是提交數據。兩個過程都只需要領導者發送消息給跟隨者節點，跟隨者節點返回消息給領導者節點即可完成，跟隨者節點之間是無需溝通的。所以如果集群總節點數為 n，對於日誌記錄階段，通信次數為n-1，對於提交數據階段，通信次數也為n-1，總通信次數為2n-2，因此raft演算法復雜度為O（n）。

對於pbft演算法，核心過程有三個階段，分別是pre-prepare（預准備）階段，prepare（准備）階段和commit（提交）階段。對於pre-prepare階段，主節點廣播pre-prepare消息給其它節點即可，因此通信次數為n-1；對於prepare階段，每個節點如果同意請求後，都需要向其它節點再 廣播parepare消息，所以總的通信次數為n （n-1），即n^2-n；對於commit階段，每個節點如果達到prepared狀態後，都需要向其它節點廣播commit消息，所以總的通信次數也為n （n-1），即n ^{2-n。所以總通信次數為（n-1）+（n} 2-n）+（n ^{2-n），即2n} 2-n-1，因此pbft演算法復雜度為O（n^2）。

流程的對比上，對於leader選舉這塊，raft演算法本質是誰快誰當選，而pbft演算法是按編號依次輪流做主節點。對於共識過程和重選leader機制這塊，為了更形象的描述這兩個演算法，接下來會把raft和pbft的共識過程比喻成一個團隊是如何執行命令的過程，從這個角度去理解raft演算法和pbft的區別。

一個團隊一定會有一個老大和普通成員。對於raft演算法，共識過程就是：只要老大還沒掛，老大說什麼，我們（團隊普通成員）就做什麼，堅決執行。那什麼時候重新老大呢？只有當老大掛了才重選老大，不然生是老大的人，死是老大的鬼。

對於pbft演算法，共識過程就是：老大向我發送命令時，當我認為老大的命令是有問題時，我會拒絕執行。就算我認為老大的命令是對的，我還會問下團隊的其它成員老大的命令是否是對的，只有大多數人（2f+1）都認為老大的命令是對的時候，我才會去執行命令。那什麼時候重選老大呢？老大掛了當然要重選，如果大多數人都認為老大不稱職或者有問題時，我們也會重新選擇老大。

8. 拍照硬體和演算法誰更重要看完OPPO三星蘋果的對比就知道

要知道，現在影像體驗已經成為了用戶購機的關鍵因素之一，尤其是手機攝像頭像素從11萬到200萬、500萬再到如今甚至有上億像素，再加上各大廠商紛紛在影像演算法方面的調教，手機的綜合成像質量也不斷在提高，現在甚至可以取代卡片機成為人們在身邊最好的「攝影器材」。下面我們就以三星S21 Ultra、OPPO Reno6 Pro+以及iPhone 12 Pro為例，來看看手機的影像體驗，究竟「進化」到什麼程度。

（左：三星S21 Ultra，中：OPPO Reno6 Pro+，右：iPhone 12 Pro）

攝像頭配置大比拼：誰是真「硬核」

首先，我們還是來看看這三款手機的硬體配置，先從iPhone 12 Pro說起，因為它的硬體配置看起來似乎是裡面相對最差的，三顆攝像頭（主攝、超廣角以及長焦）均為1200萬像素；而OPPO Reno6 Pro+則搭載5000萬像素主攝（索尼IMX766旗艦感測器）+1600萬像素超廣角鏡頭+1300萬像素長焦鏡頭+200萬像素微距鏡頭；而三星S21 Ultra搭載的則是1.08億像素主攝 +1000萬像素長焦鏡頭+1000萬像素潛望式長焦鏡頭+1200萬像素超廣角鏡頭，所以毫無疑問硬體配置是三星 OPPO iPhone。

（中：三星S21 Ultra，左：OPPO Reno6 Pro+，右：iPhone 12 Pro）

人像實拍：誰最會玩？

不過手機拍照並不只是看硬體，各大廠商在演算法方面的調教也是十分重要的，那麼下面我們一起來看看經過演算法調教以後，三款機型各自的表現如何？首先，我們來看看人像方面的實拍照片，下面這組對比圖上，很明顯擁有煥採光斑人像視頻加持的OPPO Reno6 Pro+拍出來的照片更具質山配感，大家可以看到前景小姐姐的人物主體很清晰，還有就是色彩還原很到位，小姐姐的膚色以及衣服的顏色已經很接近肉眼所見了，而背景的虛化模擬出光斑的效果，照片的質感就上來了；而三星S21 Ultra拍出來的照片人物和背景之間的過渡以及虛化做得並不是很到位；至於iPhone 12 Pro拍出來的照片只能說「平平無奇」。反正在人像這個環節，我覺得OPPO Reno6 Pro+ 三星S21 Ultra iPhone 12 Pro。

（人像實拍 左：三星S21 Ultra，中：OPPO Reno6 Pro+，右：iPhone 12 Pro）

白天大場景：誰更好「色」

接著，更換為白天的大場景，再來看看它們三者的實拍效果。從下面這組對比照片來看，盡管當時沒有大太陽，但是三部手機拍出來的照片總體表現都不錯，不過在一些細節的處理上，我覺得還是OPPO Reno6 Pro+更好，比如遮雨棚的頂部的紅色、紫色、黃色、綠色、藍色逗枯指都一一精準還原了，還有就是光線的捕捉也很到位，看出了光影的效果；而三星S21 Ultra在光線的捕捉上則稍微差了一些，整體畫面比較暗；至於iPhone 12 Pro在光線和色彩方面的調教還有待改進，整體畫面偏暗，而且畫面上的色彩也不夠討好眼球，說白了就是看著照片有種「食慾不強」的感覺。

（白天大場景實拍 左：三星S21 Ultra，中：OPPO Reno6 Pro+，右：iPhone 12 Pro）

夜景實拍：誰才是真正的「暗影精靈」

最後，我們來看看夜景方面的實拍對比。大家可以看看我用紅圈標記的地方，它們能夠充分表現出這三款手機的綜合夜景實拍能力。其實夜景拍攝，無非就是對光線的把控，尤其是高光的壓制，畢竟拍攝夜景照片的時候，不可控的光源太多，而且那些高亮的燈光，往往會一「亮」毀所有。從實拍的效果來看，OPPO Reno6 Pro的高光壓制以及色彩還原是最到位的，高樓的廣告燈箱上的字樣都能夠看得十分清晰，而三星和iPhone的則有過分提亮的「嫌疑」，所以照片上的廣告燈箱字樣不是看得很清楚敗宏。

（白天大場景實拍 左：三星S21 Ultra，中：OPPO Reno6 Pro+，右：iPhone 12 Pro）

綜合來看，手機影像在各大廠商不斷的調教下，已經成為了當下人們最愛的「攝影器材」，畢竟它太方便了，看見什麼好吃的、漂亮的，隨手都可以從口袋裡掏出手機「咔嚓」將它們定格下來，並且分享到各大社交平台。在影像實測對比中，我們可以發現，其實手機影像最重要的還是軟硬體相互相成，才可以發揮出最大的「功效」。OPPO Reno6 Pro+在色彩還原以及細節處理上做得十分出色，而三星S21 Ultra則在解析力上有不錯的提升，至於iPhone 12 Pro則相對比較中庸，沒有很亮眼的表現。最近有購機需求的網友不妨關注一下，這三款機型各有千秋，消費者可以根據自己的實際需求來選購。

9. Q-Learning 和 SARSA 演算法對比

Q-learning演算法的過程可以根據下面的步驟：

首先，我們會初始化一個Q-table，可以是全0或者是其他的數值，一般咐褲悉都是全0，然後我們設定訓練的輪數episodes，這里從初始狀態直到終止狀態算作一輪。那麼在每一輪中，我們會有一個初始狀態，然後會不斷的採取動作，這里每一個動作叫做一個step。在每一個step中，我們根據當前的狀態通過一定的策略選擇動作A，這里的策略可能是以0.9的概率選擇Q-table中當前狀態對應的q值最大的動作，以0.1的概率選擇隨機動作。然後在選擇動作A之後，我們可以得到獎勵值R和新的狀態S，那麼當前q值的更新基於下面的公式：

其中alpha是學習率，表示保留之前訓練效果的多少，學習速率α越大，保留之前訓練的效果就越少，如果學習率是1的話，完全用新學到的q值替換掉了原來的q值。R是從環境獲得的獎勵，而gamma是折現系數，我們會選擇到新狀態之後能夠得到的最大的Q值來更新當前的Q值。

對於Q-learning來說，
1.在狀態s'時，只是計算了 在s'時要採取哪個a'可以得到更大的Q值，並沒有真的採取這個動作a'。
2.動作a的選取是根據當前Q網路以及策略（e-greedy），即每一步都會根據當前的狀況選擇一個動作A，目標Q值的計算是根據Q值最大的動作a'計算得來，因此為off-policy學習。

SARSA演算法根Q-learning很像，也是基於Q-table，但是不同的是，在每一個episode的每一個step，我們會確定下一步採取的動作，而不是在下一個衡乎step開始時動態的確定step，演算法步驟看下面的圖示。

因此對於SARSA來說
1.在狀態s'時，就知道了要採取哪個a'，並真的採取了這個動作。
2.動作a的選取遵循e-greedy策略，目標Q值的計算也是根據（e-greedy）策略得到的動作a'純檔計算得來，因此為on-policy學習。