Parameter Learning

Gradient Descent

梯度下降 (Gradient descent) 是一種可以把 cost function 最小化的算法

甚至可以拿來解決 Linear Regression 以外的機器學習問題

我們首先定義 cost function 問題為 :

Gradient descent 可以解決超過 2 個以上的 theta 值

而 gradient descent 是這樣解決問題的 :

所以假設我們在一個 theta 0 和 theta 1 所生成的 cost function 圖表上

我們將他看成地形圖，而最高點的就是山頂

若一開始起始點設在在山頂上

那我們就環繞四周，看哪個方向可以通往最低點

然後我們就往那個方向走幾步路下山

重複這個步驟，直到到達最低點

所以根據我們起始點的不同，會造成下山方向的不同，然後找到不同的最低點

要達成上面這個方法，需要使用到微分技巧

而 gradient descent 的 algorithm 是這樣的 :

\begin{aligned} \text{repeat } &\text{until convergence } :\\ &\theta_j := \theta_j - \alpha \frac{d}{d\theta_j}J(\theta_0, \theta_1, ..., \theta_n) \end{aligned}

我們將公式拆解開來 :

\begin{aligned} := &: 代表的是 \text{ assignment operator 例如 } a := a+1\\ \theta_j&: \text{代表的是第 j 個 } \theta \text{ 值} \\ \alpha&: \text{代表的是下山的步伐大小} \\ \frac{d}{d\theta_j}J(\theta_0,\theta_1,...\theta_n)&: \text{是一個微分方程，用第 j 個 }\theta \\&\,\,\,\text{ 來微分每個回合的 cost function} \end{aligned}

要注意的是，在 gradient descent algorithm 中

所有的 theta 值必須被同時更新

如果先把某一個 theta 算完更新，就會造成其他項的微分發生些微偏差 !

Gradient Descent Intuiton

我們用單個 theta 模型來簡化並解釋 gradient descent 的運作

我們可以很清楚的觀察到，微分項的

\frac{d}{d\theta_1}J(\theta_1) = \text{ 與 } J(\theta_1) \text{ 的 tangent line 斜率}

而此時的斜率是一個正整數

我們將他和 learning rate (Alpha) 相乘，整個式子其實就是

\theta_1 := \theta_1 - \alpha \times \text{ positive number}

所以 theta 1 會越來越往 minimum 移動

若 theta 在另外一邊也可以成功

因為斜率變為負的，所以式子變為

\begin{aligned} \theta_1 &:= \theta_1 - \alpha \times \text{ negative number}\\ &:=\theta_1 + \text{ positive number} \end{aligned}

theta 一樣往 minimum 移動

我們也要定義一個合理的 learning rate (Alpha)

來保證 gradient descent algorithm 能夠在合理時間收斂到 minimum

過小的 alpha 會讓算法變得很慢

而過大的 alpha 可能 overshoot the minimum，甚至變成發散

而當 theta 抵達 minimum 時

我們知道 tangent line 的斜率會變為 0

\theta_1 := \theta_1 - \alpha \times 0

也就是 theta 將會保持不變

另外，我們並不需要隨著 theta 的移動次數來改變 alpha 的大小

因為隨著 theta 下降，斜率將會越變越小

所以就算 alpha 固定，也會自動用越來越小的步伐下山

Gradient Descent For Linear Regression

現在我們可以利用 Gradient descent 來解決 Linear regression 的問題了 !

Gradient descent algorithm

\begin{aligned} \text{repeat } &\text{until convergence } :\\ &\theta_j := \theta_j - \alpha \frac{d}{d\theta_j}J(\theta_0, \theta_1) \end{aligned}

Linear Regression Model

Hypothesis
$h_\theta(x) = \theta_0 + \theta_1x$
Squared error cost function
$J(\theta_0, \theta_1) = \frac{1}{2m} \sum_{i=1}^{m}(h_\theta(x^i)-y^i)^2$

我們要做的就是利用 gradient descent algorithm

來找出 linear regression 中 cost function 的最小值

首先我們將 squared error cost function 套入 gradient descent 最重要的微分部分

\begin{aligned} \frac{d}{d\theta_j}J(\theta_0, \theta_1) &= \frac{d}{d\theta_j} ( \frac{1}{2m} \sum_{i=1}^{m}(h_\theta(x^i)-y^i)^2)\\ &=\frac{d}{d\theta_j} ( \frac{1}{2m} \sum_{i=1}^{m}(\theta_0+\theta_1x^i-y^i)^2) \end{aligned}

這邊要解開需要用到 multivariate calculus 的技術，如 :

我們將 theta 0 和 theta 1 各自解開後

Gradient descent algorithm 將會變成這樣 :

\begin{aligned} \text{repeat } &\text{until convergence } :\\ &\theta_0 := \theta_0 - \alpha \frac{1}{m}\sum_{i=1}^m(h_\theta(x^i)-y^i) \\ &\theta_1 := \theta_1 - \alpha \frac{1}{m}\sum_{i=1}^m((h_\theta(x^i)-y^i)x^i) \end{aligned}

現在我們來看 gradient descent 在 linear regression cost function 的運作

我們知道 gradient descent 會因為 local optima 影響，而有不同的最小值

但其實 linear regression 的 cost function 將會是 bow shaped function (Convex function)

所以只會有一個 global optimum ，也就是永遠都會收斂至最低點

假設我們起始點定在

\theta_0 = 900, \theta_1 = -0.1, h(x) = 900 - 0.1x

隨著 Gradient descent algorithm 的運行

theta 越來越接近最低點

我們的 Hypothesis 也越來越 Fit 所有的 training examples

因為在每個迴圈中，Gradient descent 要微分的 cost function J 都要用到所有的 training sets

\begin{aligned} \text{repeat } &\text{until convergence } :\\ &\theta_0 := \theta_0 - \alpha \frac{1}{m}\sum_{i=1}^{\color{red}{m}}(h_\theta(x^i)-y^i) \end{aligned}

所以這種方法又稱為 Batch Gradient Descent

這就是我們學到的第一個 learning algorithm

在 Linear algebra 中有一種數學算法叫作 Normal equation method
他可以不用像 Gradient descent 用 iteration 的方法解決問題
但事實上，Gradient descent 在處理較大資料時是比較好用的

True

Gradient descent can converge even if \alphaα is kept fixed. (But \alphaα cannot be too large, or else it may fail to converge.)
For the specific choice of cost function J used in linear regression, there are no local optima (other than the global optimum).