梯度下降算法

　　梯度下降法的簡單介紹以及實現

　　梯度下降法的基本思想可以類比為一個下山的過程。假設這樣一個場景：一個人被困在山上，需要從山上下來(i.e.找到山的最低點，也就是山谷)。但此時山上的濃霧很大，導致可視度很低。因此，下山的路徑就無法確定，他必須利用自己周圍的信息去找到下山的路徑。這個時候，他就可以利用梯度下降算法來幫助自己下山。具體來說就是，以他當前的所處的位置為基準，尋找這個位置最陡峭的地方，然后朝著山的高度下降的地方走，同理，如果我們的目標是上山，也就是爬到山頂，那么此時應該是朝著最陡峭的方向往上走。然后每走一段距離，都反復采用同一個方法，最后就能成功的抵達山谷。

　　在這種就情況下,我們也可以假設此時周圍的陡峭程度我們無法用肉眼來測量,需要一個復雜的工具來幫助我們測量,恰巧的是此人正好擁有測量最陡峭方向的能力。因此,這個人每走一段距離，都需要一段時間來測量所在位置最陡峭的方向，這是比較耗時的。那么為了在太陽下山之前到達山底，就要盡可能的減少測量方向的次數。這是一個兩難的選擇，如果測量的頻繁，可以保證下山的方向是絕對正確的，但又非常耗時，如果測量的過少，又有偏離軌道的風險。所以需要找到一個合適的測量方向的頻率，來確保下山的方向不錯誤，同時又不至于耗時太多!

　　梯度下降

　　梯度下降的過程就如同這個下山的場景一樣

　　首先，我們有一個可微分的函數。這個函數就代表著一座山。我們的目標就是找到這個函數的最小值，也就是山底。根據之前的場景假設，最快的下山的方式就是找到當前位置最陡峭的方向，然后沿著此方向向下走，對應到函數中，就是找到給定點的梯度 ，然后朝著梯度相反的方向，就能讓函數值下降的最快!因為梯度的方向就是函數之變化最快的方向(在后面會詳細解釋)

　　所以，我們重復利用這個方法，反復求取梯度，最后就能到達局部的最小值，這就類似于我們下山的過程。而求取梯度就確定了最陡峭的方向，也就是場景中測量方向的手段。

　　三種梯度算法的代碼實現

　　導入函數包

　　import os

　　%matplotlib inline

　　import matplotlib as mpl

　　import matplotlib.pyplot as plt

　　import numpy as np

　　批量梯度下降求解線性回歸

　　首先，我們需要定義數據集和學習率 接下來我們以矩陣向量的形式定義代價函數和代價函數的梯度 當循環次數超過1000次，這時候再繼續迭代效果也不大了，所以這個時候可以退出循環!

　　eta = 0.1

　　n_iterations = 1000

　　m = 100

　　theta = np.random.randn(2, 1)

　　for iteration in range(n_iterations): # 限定迭代次數

　　gradients = 1/m * X_b.T.dot(X_b.dot(theta)-Y) # 梯度

　　theta = theta - eta * gradients # 更新theta

　　theta_path_bgd = []

　　def plot_gradient_descent(theta, eta, theta_path = None):

　　m = len(X_b)

　　plt.plot(X, y, "b.")

　　n_iterations = 1000

　　for iteration in range(n_iterations):

　　if iteration < 10: #取前十次

　　y_predict = X_new_b.dot(theta)

　　style = "b-"

　　plt.plot(X_new,y_predict, style)

　　gradients = 2/m * X_b.T.dot(X_b.dot(theta) - y)

　　theta = theta - eta*gradients

　　if theta_path is not None:

　　theta_path.append(theta)

　　plt.xlabel("$x_1$", fontsize=18)

　　plt.axis([0, 2, 0, 15])

　　plt.title(r"$\eta = {}$".format(eta),fontsize=16)

　　np.random.seed(42) #隨機數種子

　　theta = np.random.randn(2,1) #random initialization

　　plt.figure(figsize=(10,4))

　　plt.subplot(131);plot_gradient_descent(theta, eta=0.02) # 第一個，

　　plt.ylabel("$y$", rotation=0, fontsize=18)

　　plt.subplot(132);plot_gradient_descent(theta, eta=0.1, theta_path=theta_path_bgd ) # 第二個，擬合最好，eta=0.1

　　plt.subplot(133);plot_gradient_descent(theta, eta=0.5) # 第三個

　　save_fig("gradient_descent_plot")

　　運行結果

　　隨機梯度下降

　　隨機梯度下降每次用一個樣本來梯度下降，可能得到局部最小值。

　　theta_path_sgd = []

　　m = len(X_b)

　　np.random.seed(42)

　　n_epochs = 50

　　theta = np.random.randn(2,1) #隨機初始化

　　for epoch in range(n_epochs):

　　for i in range(m):

　　if epoch == 0 and i < 10:

　　y_predict = X_new_b.dot(theta)

　　style = "b-"

　　plt.plot(X_new,y_predict,style)

　　random_index = np.random.randint(m)

　　xi = X_b[random_index:random_index+1]

　　yi = y[random_index:random_index+1]

　　gradients = 2 * xi.T.dot(xi.dot(theta)-yi)

　　eta = 0.1

　　theta = theta - eta * gradients

　　theta_path_sgd.append(theta)

　　plt.plot(x,y,"b.")

　　plt.xlabel("$x_1$",fontsize = 18)

　　plt.ylabel("$y$",rotation =0,fontsize = 18)

　　plt.axis([0,2,0,15])

　　save_fig("sgd_plot")

　　plt.show()

　　運行結果

　　小批量梯度下降

　　小批量梯度下降每次迭代使用一個以上又不是全部樣本。

　　theta_path_mgd = []

　　n_iterations = 50

　　minibatch_size = 20

　　np.random.seed(42)

　　theta = np.random.randn(2,1)

　　for epoch in range(n_iterations):

　　shuffled_indices = np.random.permutation(m)

　　X_b_shuffled = X_b[shuffled_indices]

　　y_shuffled = y[shuffled_indices]

　　for i in range(0, m, minibatch_size):

　　xi = X_b_shuffled[i:i+minibatch_size]

　　yi = y_shuffled[i:i+minibatch_size]

　　gradients = 2/minibatch_size * xi.T.dot(xi.dot(theta)-yi)

　　eta = 0.1

　　theta = theta-eta*gradients

　　theta_path_mgd.append(theta)

　　三者的比較圖像

　　theta_path_bgd = np.array(theta_path_bgd)

　　theta_path_sgd = np.array(theta_path_sgd)

　　theta_path_mgd = np.array(theta_path_mgd)

　　plt.figure(figsize=(7,4))

　　plt.plot(theta_path_sgd[:,0], theta_path_sgd[:,1], "r-s", linewidth = 1, label = "Stochastic")

　　plt.plot(theta_path_mgd[:,0], theta_path_mgd[:,1], "g-+", linewidth = 2, label = "Mini-batch")

　　plt.plot(theta_path_bgd[:,0], theta_path_bgd[:,1], "b-o", linewidth = 3, label = "Batch")

　　plt.legend(loc="upper left", fontsize = 16)

　　plt.xlabel(r"$\theta_0$", fontsize=20)

　　plt.ylabel(r"$\theta_1$", fontsize=20, rotation=0)

　　plt.axis([2.5,4.5,2.3,3.9])

　　save_fig("gradients_descent_paths_plot")

　　plt.show()

　　運行結果

　　總結：綜合以上對比可以看出，批量梯度下降的準確度最好，其次是小批量梯度下降，最后是隨機梯度下降。因為小批量梯度下降與隨機梯度下降每次梯度估計的方向不確定，可能需要很長時間接近最小值點。對于訓練速度來說，批量梯度下降在梯度下降的每一步中都用到了所有的訓練樣本，當樣本量很大時，訓練速度往往不能讓人滿意;隨機梯度下降由于每次僅僅采用一個樣本來迭代，所以訓練速度很快;小批量

　　梯度下降每次迭代使用一個以上又不是全部樣本，因此訓練速度介于兩者之間。