梯度下降法(gradient descent)是一種常用的一階(first-order)優化方法,是求解無約束優化問題最簡單、最經典的方法之一。
梯度下降最典型的例子就是從山上往下走,每次都尋找當前位置最陡峭的方向小碎步往下走,最終就會到達山下(暫不考慮有山谷的情況)。
首先來解釋什麼是梯度?這就要先講微分。對於微分,相信大家都不陌生,看幾個例子就更加熟悉了。
先來看單變量的微分:
再看多變量的微分:
補充:導數和微分的區別
導數是函數在某一點處的斜率,是Δy和Δx的比值;而微分是指函數在某一點處的切線在橫坐標取得增量Δx以後,縱坐標取得的增量,一般表示為dy。
梯度就是由微分結果組成的向量,令
有
那麼,函數f(x,y,z)在(1,2,3)處的微分為
因此,函數f(x,y,z)在(1,2,3)處的梯度為(6,11,6)。
梯度是一個向量,對於一元函數,梯度就是該點處的導數,表示切線的斜率。對於多元函數,梯度的方向就是函數在該點上升最快的方向。
梯度下降法就是每次都尋找梯度的反方向,這樣就能到達局部的最低點。
那為什麼按照梯度的反方向能到達局部的最低點呢?這個問題直觀上很容易看出來,但嚴禁起見,我們還是給出數學證明。
對於連續可微函數f(x),從某個隨機點出發,想找到局部最低點,可以通過構造一個序列,能夠滿足
那麼我們就能夠不斷執行該過程即可收斂到局部極小點,可參考下圖。
那麼問題就是如何找到下一個點 ,並保證呢?我們以一元函數為例來說明。對於一元函數來說,x是會存在兩個方向:要麼是正方向( ),要麼是負方向( ),如何選擇每一步的方向,就需要用到大名鼎鼎的泰勒公式,先看一下下面這個泰勒展式:
其中表示f(x)在x處的導數。
若想,就需要保證,令
步長是一個較小的正數,從而有
因此,有
每一步我們都按照更新x,這就是梯度下降的原理。
這裡再對解釋一下,α在梯度下降算法中被稱作為學習率或者步長,意味著我們可以通過α來控制每一步走的距離。既要保證步子不能太小,還沒下到山底太陽就下山了;也要保證步子不能跨的太大,可能會導致錯過最低點。
在梯度前加負號就是朝梯度的反方向前進,因為梯度是上升最快的方向,所以方向就是下降最快的方向。
梯度下降的實例一元函數的梯度下降
設一元函數為
函數的微分為
設起點為,步長,根據梯度下降的公式
,經過4次迭代:
多元函數的梯度下降
設二元函數為
函數的梯度為
設起點為(2,3),步長,根據梯度下降的公式,經過多次迭代後,有
損失函數也叫代價函數(cost function),是用來衡量模型預測出來的值h(θ)與真實值y之間的差異的函數,如果有多個樣本,則可以將所有代價函數的取值求均值,記做J(θ)。代價函數有下面幾個性質:
對於每種算法來說,代價函數不是唯一的;
代價函數是參數θ的函數;
總的代價函數J(θ)可以用來評價模型的好壞,代價函數越小說明模型和參數越符合訓練樣本(x, y);
J(θ)是一個標量。
最常見的代價函數是均方誤差函數,即
其中,
m為訓練樣本的個數
表示估計值,表達式如下
y是原訓練樣本中的值
我們需要做的就是找到θ的值,使得J(θ)最小。代價函數的圖形跟我們上面畫過的圖很像,如下圖所示。
看到這個圖,相信大家也就知道了我們可以用梯度下降算法來求可以使代價函數最小的θ值。
先求代價函數的梯度
這裡有兩個變量和,為了方便矩陣表示,我們給x增加一維,這一維的值都是1,並將會乘到上。那麼cost function的矩陣形式為:
這麼看公式可能很多同學會不太明白,我們把每個矩陣的具體內容表示出來,大家就很容易理解了。
矩陣為:
矩陣X為:
矩陣y為:
這樣寫出來後再去對應上面的公式,就很容易理解了。
下面我們來舉一個用梯度下降算法來實現線性回歸的例子。有一組數據如下圖所示,我們嘗試用求出這些點的線性回歸模型。
首先產生矩陣X和矩陣y
X0 = np.ones((m, 1))
X1 = np.arange(1, m+1).reshape(m, 1)
X = np.hstack((X0, X1))
y = np.array([2,3,3,5,8,10,10,13,15,15,16,19,19,20,22,22,25,28]).reshape(m,1)
按照上面的公式定義梯度函數
def gradient_function(theta, X, y):
diff = np.dot(X, theta) - y
return (1./m) * np.dot(np.transpose(X), diff)
接下來就是最重要的梯度下降算法,我們取和的初始值都為1,再進行梯度下降過程。
def gradient_descent(X, y, alpha):
theta = np.array([1, 1]).reshape(2, 1)
gradient = gradient_function(theta, X, y)
while not np.all(np.absolute(gradient) <= 1e-5):
theta = theta - alpha * gradient
gradient = gradient_function(theta, X, y)
return theta
通過該過程,最終求出的,,線性回歸的曲線如下
clc;
close all;
clear all;
%%
delta = 1/100000;
x = -1.1:delta:1.1;
y = x.^2;
dot = [1, 0.2, 0.04, 0.008];
figure;plot(x,y);
axis([-1.2, 1.2, -0.2, 1.3]);
grid on
hold on
plot(dot, dot.^2,'r');
for i=1:length(dot)
text(dot(i),dot(i)^2,['\theta_{',num2str(i),'}']);
end
title('一元函數的梯度下降過程');
import numpy as np
import matplotlib.pyplot as plt
delta = 1/100000
x = np.arange(-1.1, 1.1, delta)
y = x ** 2
dot = np.array([1, 0.2, 0.04, 0.008])
plt.figure(figsize=(7,5))
plt.plot(x,y)
plt.grid(True)
plt.xlim(-1.2, 1.2)
plt.ylim(-0.2, 1.3)
plt.plot(dot, dot**2, 'r')
for i in range(len(dot)):
plt.text(dot[i],dot[i]**2,r'$\theta_%d$' % i)
plt.title('一元函數的梯度下降過程')
plt.show()
using PyPlot
delta = 1/100000
x = -1.1:delta:1.1
y = x.^2
dot = [1, 0.2, 0.04, 0.008]
plot(x, y)
grid(true)
axis("tight")
plot(dot, dot.^2, color="r")
for i=1:length(dot)
text(dot[i], dot[i]^2, "\$\\theta_$i\$")
end
title("Single variable function gradient descent")
pecision = 1/100;
[x,y] = meshgrid(-3.1:pecision:3.1);
z = x.^2 + y.^2;
figure;
mesh(x,y,z);
dot = [[2,3];[1.6,2.4];[1.28,1.92];[5.09e-10, 7.64e-10]];
hold on
scatter3(dot(:,1),dot(:,2),dot(:,1).^2+dot(:,2).^2,'r*');
for i=1:4
text(dot(i,1)+0.4,dot(i,2),dot(i,1).^2+0.2+dot(i,2).^2+0.2,['\theta_{',num2str(i),'}']);
end
title('二元函數的梯度下降過程')
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
x = np.linspace(-3.1,3.1,300)
y = np.linspace(-3.1,3.1,300)
x,y = np.meshgrid(x, y)
z = x**2 + y**2
dot = np.array([[2,3],[1.6,2.4],[1.28,1.92],[5.09e-10, 7.64e-10]])
fig = plt.figure(figsize = (10,6))
ax = fig.gca(projection = '3d')
cm = plt.cm.get_cmap('YlGnBu')
surf = ax.plot_surface(x, y, z, cmap=cm)
fig.colorbar(surf,shrink=0.5, aspect=5)
ax.scatter3D(dot[:,0], dot[:,1], dot[:,0]**2 + dot[:,1]**2, marker='H',c='r')
for i in range(len(dot)-1):
ax.text(dot[i,0]+0.4, dot[i,1], dot[i,0]**2 + dot[i,1]**2, r'$\Theta_%d$' % i)
ax.text(dot[3,0]+0.4, dot[3,1]+0.4, dot[3,0]**2 + dot[3,1]**2-0.4, r'min')
plt.show()
這個圖的text死活標不上,希望知道的朋友可以告知一下。再多說一句,雖然我之前出了個Julia的教程,裡面也包含4種繪圖工具(Plots,GR,Gadfly & PyPlot),但沒有畫過3維的圖形,今天為了畫這個圖可真是費盡周折,Julia官網上的3D繪圖的程序基本沒有一個可以直接使用的,具體的繪圖過程和調試中碰到的問題我還會整理篇文章到知乎和公眾號,大家可以看一下。
using Plots
Plots.plotlyjs()
n = 50
x = range(-3, stop=3, length=n)
y= x
z = zeros(n,n)
for i in 1:n, k in 1:n
z[i,k] = x[i]^2 + y[k]^2
end
surface(x, y, z)
dot = [[2 3]; [1.6 2.4]; [1.28 1.92]; [5.09e-10 7.64e-10]]
scatter!(dot[:,1], dot[:,2], dot[:,1].^2 .+ dot[:,2].^2)
m = 18;
X0 = ones(m,1);
X1 = (1:m)';
X = [X0, X1];
y = [2,3,3,5,8,10,10,13,15,15,16,19,19,20,22,22,25,28]';
alpha = 0.01;
theta = gradient_descent(X, y, alpha, m);
function [grad_res] = gradient_function(theta, X, y, m)
diff = X * theta - y;
grad_res = X' * diff / m;
end
function [theta_res] = gradient_descent(X, y, alpha, m)
theta = [1;1];
gradient = gradient_function(theta, X, y, m);
while sum(abs(gradient)>1e-5)>=1
theta = theta - alpha * gradient;
gradient = gradient_function(theta, X, y, m);
end
theta_res = theta;
end
import numpy as np
import matplotlib.pyplot as plt
m = 18
X0 = np.ones((m, 1))
X1 = np.arange(1, m+1).reshape(m, 1)
X = np.hstack((X0, X1))
y = np.array([2,3,3,5,8,10,10,13,15,15,16,19,19,20,22,22,25,28]).reshape(m,1)
alpha = 0.01
def cost_function(theta, X, y):
diff = np.dot(X, theta) - y
return (1./2*m) * np.dot(np.transpose(diff), diff)
def gradient_function(theta, X, y):
diff = np.dot(X, theta) - y
return (1./m) * np.dot(np.transpose(X), diff)
def gradient_descent(X, y, alpha):
theta = np.array([1, 1]).reshape(2, 1)
gradient = gradient_function(theta, X, y)
while not np.all(np.absolute(gradient) <= 1e-5):
theta = theta - alpha * gradient
gradient = gradient_function(theta, X, y)
return theta
[theta0, theta1] = gradient_descent(X, y, alpha)
plt.figure()
plt.scatter(X1,y)
plt.plot(X1, theta0 + theta1*X1, color='r')
plt.title('基於梯度下降算法的線性回歸擬合')
plt.grid(True)
plt.show()
m = 18
X0 = ones(m,1)
X1 = Array(1:m)
X = [X0 X1];
y = [2,3,3,5,8,10,10,13,15,15,16,19,19,20,22,22,25,28];
alpha = 0.01;
theta = gradient_descent(X, y, alpha, m)
function gradient_function(theta, X, y, m)
diff = X * theta .- y;
grad_res = X' * diff / m;
end
function gradient_descent(X, y, alpha, m)
theta = [1,1]
gradient = gradient_function(theta, X, y, m)
while all(abs.(gradient) .>1e-5)==true
theta = theta - alpha * gradient
gradient = gradient_function(theta, X, y, m)
end
theta_res = theta
end