[機器學習]（三）梯度下降法(Gradient descent)

梯度下降法解說：

梯度下降法可以自動將成本函數最小化，其常用在回歸問題，也可以拿來最小化其他函數，不僅僅是成本函數而已。

假設現在有個成本函數：$J({ \theta  }_{ 0 },{ \theta  }_{ 1 })$

我們想要最小化這個成本函數，也就是：$\underset { { \theta  }_{ 0 },{ \theta  }_{ 1 } }{ minimize } J({ \theta  }_{ 0 },{ \theta  }_{ 1 })$

首先，先初始化${ \theta  }_{ 0 }$與${ \theta  }_{ 1 }$的值，初始值為多少其實不重要，但通常會將${ \theta  }_{ 0 }$與${ \theta  }_{ 1 }$的值都先設為0，透過在梯度下降過程中一點一點改變${ \theta  }_{ 0 }$與${ \theta  }_{ 1 }$的值，來逐漸最小化成本函數$J({ \theta  }_{ 0 },{ \theta  }_{ 1 })$，直到我們找到成本函數$J({ \theta  }_{ 0 },{ \theta  }_{ 1 })$的最小值為止，而這或許是一個局部最小值(局部最優解)。

什麼是局部最小值？以下圖為例：
想像你在一個公園，裡面有兩座山丘，而你現在正站在某個紅色山丘 上。在梯度下降法中，我們要做的就是旋轉360度看看周圍並問自己，如果我想要用小碎步儘快下山，應該朝哪個方向下山比較好？當你用小碎步走了一次後，再重複看看周圍，再想想應該再朝哪個方向下山比較好，直到你走到了局部最低點(局部最優解)的位置為止。

梯度下降法一個有趣的特性就是，當你選擇右靠一點點的點當作起始出發點時，你可能最後會走到另一個局部最低點(局部最優解)。

梯度下降演算法：
Repeat{
 ${ \theta  }_{ j }:={ \theta  }_{ j }-\alpha \frac { \partial  }{ \partial { \theta  }_{ j } } J({ \theta  }_{ 0 },{ \theta  }_{ 1 }) (for j=0 and j=1)$
}

不斷重複上述動作一直更新${ \theta  }_{ j }$，直到收斂為止。

:= 代表賦值運算符(assignment)，$\alpha$代表一個學習速率，在梯度下降法中，它會控制我們下山時會邁出多大的步伐，如果$\alpha$值很大，我們就會跨大步下山，反之就是走小碎步。關於如何設置$\alpha$會在之後說明。

對於這個式子：${ \theta  }_{ j }:={ \theta  }_{ j }-\alpha \frac { \partial  }{ \partial { \theta  }_{ j } } J({ \theta  }_{ 0 },{ \theta  }_{ 1 }) (for j=0 and j=1)$

如果你想要「同時更新」${ \theta  }_{ 0 }$與${ \theta  }_{ 1 }$，也就是讓以下兩個式子同時做：
${ \theta  }_{ 0 }$ := ${ \theta  }_{ 0 }$ - 一些東西
${ \theta  }_{ 1 }$ := ${ \theta  }_{ 1 }$ - 一些東西

你一定要等兩個式子的右邊全部算出來後才能進行更新。

正確的同時更新：
temp0 := ${ \theta  }_{ 0 }-\alpha \frac { \partial  }{ \partial { \theta  }_{ 0 } } J({ \theta  }_{ 0 },{ \theta  }_{ 1 })$
temp1 := ${ \theta  }_{ 1 }-\alpha \frac { \partial  }{ \partial { \theta  }_{ 1 } } J({ \theta  }_{ 0 },{ \theta  }_{ 1 })$
${ \theta  }_{ 0 }$ := temp0
${ \theta  }_{ 1 }$ := temp1

不正確的同時更新(因為根本沒同步)：
temp0 := ${ \theta  }_{ 0 }-\alpha \frac { \partial  }{ \partial { \theta  }_{ 0 } } J({ \theta  }_{ 0 },{ \theta  }_{ 1 })$
${ \theta  }_{ 0 }$ := temp0 #此時就更新${ \theta  }_{ 0 }$，下一步就是用到新的${ \theta  }_{ 0 }$來計算微分項了
temp1 := ${ \theta  }_{ 1 }-\alpha \frac { \partial  }{ \partial { \theta  }_{ 1 } } J({ \theta  }_{ 0 },{ \theta  }_{ 1 })$
${ \theta  }_{ 1 }$ := temp1

直觀的梯度下降法：

前言：
對於這個式子：${ \theta  }_{ j }:={ \theta  }_{ j }-\alpha \frac { \partial  }{ \partial { \theta  }_{ j } } J({ \theta  }_{ 0 },{ \theta  }_{ 1 }) (for j=0 and j=1)$
$\alpha$代表學習速率，會控制我們以多大的幅度來更新參數${ \theta  }_{ j }$。$\frac { \partial  }{ \partial { \theta  }_{ 0 } } J({ \theta  }_{ 0 },{ \theta  }_{ 1 })$則是導數項。此處將會解釋這兩部分有什麼用，以及為什麼把這兩部分放在一起更新過程會是有意義的。

假設我們的成本函數$J({ \theta  }_{ 1 })$，目前只有一個${ \theta  }_{ 1 }\in R$，此時讓我們來計算一下導數項。

求導數的目的基本上就是取一條與成本函數曲線相切於某一點的切線，這條切線的斜率就是導數。

舉例來說，圖上首先把參數${ \theta  }_{ 1 }$初始化到右邊這點，則與成本函數曲線相切於該點的紅色切線具有正斜率。由於該點具有正斜率，代表該點具有正導數(positive derivative)，此時導數項會大於等於0。

因此，我所得到一個新的${ \theta  }_{ 1 }$就是${ \theta  }_{ 1 }$減去$\alpha$乘以一個「正數」，相當於讓${ \theta  }_{ 1 }$左移使${ \theta  }_{ 1 }$變小，讓其更接近成本函數曲線的最低點。

換個例子，圖下這次把參數${ \theta  }_{ 1 }$初始化到左邊這點，則與成本函數曲線相切於該點的紅色切線具有負斜率。由於該點具有負斜率，代表該點具有負導數(negative derivative)，此時導數項會小於等於0。

因此，我所得到一個新的${ \theta  }_{ 1 }$就是${ \theta  }_{ 1 }$減去$\alpha$乘以一個「負數」，相當於讓${ \theta  }_{ 1 }$右移使${ \theta  }_{ 1 }$變大，讓其更接近成本函數曲線的最低點。

接下來看看學習速率$\alpha$，如果$\alpha$設定太小，梯度下降的速度會過慢。如果$\alpha$設定太大，每次移動都會愈跨愈大步，一下往左一下往右，離最低點愈來愈遠，導致最後無法收斂，甚至發散。

此時有個問題，如果${ \theta  }_{ 1 }$的起始點剛好已經在一個局部最低點了，梯度下降法下一步會怎麼做呢？

答案是不會改變${ \theta  }_{ 1 }$，因為局部最低點的導數就是那條切線的斜率，而斜率此時為0，導數等於0，代表這條式子：${ \theta  }_{ 1 }$:=${ \theta  }_{ 1 }-\alpha \frac { \partial  }{ \partial { \theta  }_{ 1 } } J({ \theta  }_{ 0 },{ \theta  }_{ 1 })$變成了：${ \theta  }_{ 1 }$:=${ \theta  }_{ 1 }$-$\alpha$ * 0，意味著${ \theta  }_{ 1 }$已經不會再改變了，因此你最後的解始終都會是局部最優解。

來看一張圖，此圖解釋了為何$\alpha$保持不變，梯度下降法仍可以收斂到局部最低點。

假設把參數${ \theta  }_{ 1 }$初始化在右邊最上面這個起始點：

隨著該點愈來愈接近局部最低點，該點的切線斜率(導數)會愈來愈趨近於0，意味著${ \theta  }_{ 1 }$每次更新的幅度會愈來愈小，直到最後收斂到局部最低點為止。

所以，即使$\alpha$保持不變，當我們愈來愈接近局部最低點時，梯度下降法也會自動採取愈小的步伐來移動，原本的式子自然不需要另外減掉$\alpha$了。

總結一下，你可以使用梯度下降法來最小化任何成本函數，而不只是線性回歸中的成本函數，接下來我們將會結合梯度下降法與線性回歸中的成本函數(平方誤差函數)，這樣我們就學會第一個機器學習演算法了，即線性回歸演算法。

結合線性回歸模型的平方誤差成本函數與梯度下降法：

結合線性回歸模型的平方誤差成本函數與梯度下降法，也就是用梯度下降法來最小化平方誤差成本函數，關鍵是這個偏(partial)導數項：$\frac { \partial  }{ \partial { \theta  }_{ 0 } } J({ \theta  }_{ 0 },{ \theta  }_{ 1 })$

計算這些偏導數項需要一些多元微積分的概念，在我們算出這些微分項後，即是成本函數J的斜率，最後將它放回我們的梯度下降法。

以下就是線性回歸的梯度下降法，${ \theta  }_{ 0 }$和${ \theta  }_{ 1 }$會不斷被同時更新：

為什麼要用梯度下降法的其中一個原因是因為它很容易得到局部最優值(local optimum)。根據你初始化的起始點，你會得到不同的局部最優解。

但是如下圖，用於線性回歸的成本函數總是這樣一個弓形的樣子，這個函數的專用術語是凸函數(convex function)，這種函數沒有任何局部最優解，只有一個全局最優解(Global optimum)，無論何時其總是收斂到全局最優解，因為沒有其餘局部最優解。

來看看梯度下降演算法用於這種凸函數的執行過程：

通常初始化參數${ \theta  }_{ 0 }$和${ \theta  }_{ 1 }$的值都會設為0，但為了展示過程，這邊先將${ \theta  }_{ 0 }$初始化為-900，${ \theta  }_{ 1 }$初始化為-0.1。

隨著點在成本函數上移動，左邊的直線(假設函數)也會改變「傾向」，當成本愈來愈下降(參數跟隨著軌跡移動)，直線也變得愈來愈擬合data，直到收斂到全局最小值(global minimum)，這全局最小值所對應的就是最終最擬合data的直線(假設函數)，這就是梯度下降法。

實際上我們剛剛使用的演算法又叫做批次(Batch)梯度下降法，意思就是在梯度下降的每一步過程中，我們都用到了所有的training example，也就是每次在計算微分求導項時，我們需要進行求和運算：$\sum _{ i=1 }^{ m }{ ({ h }_{ \theta  }({ x }^{ (i) })-{ y }^{ (i) }) }$

由於需要對所有m個訓練樣本進行求和，所以每一次運算我們都要考慮所有這一「批」訓練樣本，未來會介紹不屬於批次處理的梯度下降法。

以上就是大家第一個學會的機器學習演算法。


最後：

當你特徵x不止一個時，你該如何表示這些特徵？可以使用向量化的方式，也就是使用線性代數中的矩陣來表示大量的特徵x，並用向量來表示結果y，因此線性代數在機器學習中可說有廣泛的運用。