# Calculus for Machine Learning and Data Science(Week2 - 2 - Gradient Descents)
###### tags: `coursera` `Linear Algebra` `math`
[Week2 - Gradients and Gradient Descent](https://www.coursera.org/learn/machine-learning-calculus/home/week/2)

## Optimization using Gradient Descent in one variable - Part 1
[課程連結](https://www.coursera.org/learn/machine-learning-calculus/lecture/XEQSF/optimization-using-gradient-descent-in-one-variable-part-1)

課程從一個變數開始說明梯度下降
### Hard To Optimize Functions

範例中給定一個函數$f(x)=e^x-\log(x)$，這個函數畫出來就是上圖右一樣子，紅色點點就是它的最佳解。

從之前的課程我們已經知道只要計算其導數為0的地方就是最佳解，也就是$f'(x)=e^x-\dfrac{1}{x}=0$，這個計算應該是蠻難的。
### Hard To Optimize Functions

這個答案大概就是$e^x=\dfrac{1}{x}$，$x=0.5671...$，這個數字又稱為[Omega constant](https://zh.wikipedia.org/zh-tw/%E6%AC%A7%E7%B1%B3%E5%8A%A0%E5%B8%B8%E6%95%B0)。
### Method 1: Try Both Directions

假設上圖紅點是一個隨生的初始點，我們兩邊看看，那一邊可以得到比較好的結果我們就從那個方向前進，然後不斷的重覆這個動作。


重覆這個動作一直到某個神奇的點會發現，左右都不會比較好，那這個雖然不一定是最好的，但已經是足夠好的。

## Optimization using Gradient Descent in one variable - Part 2
[課程連結](https://www.coursera.org/learn/machine-learning-calculus/lecture/daSiv/optimization-using-gradient-descent-in-one-variable-part-2)

### Method 2: Be Clever

剛剛第一種方法我們左右來回的計算，但缺點就是每一次都要計算左右，換個方式。

一樣的隨機初始點，然後我們跟它說，你就慢慢的走一點，現在我們需要的就是有個方法讓它知道要走多少。

以斜率來看，左邊那個紅點的斜率是負的，所以就跟它說往右移動，而右邊的紅點的斜率是正的，就可以跟它說往左移動。也就是說：
* 斜率為負的時候就要加一點向右移動
* 斜率為正的時候就要減一點向左移動

這樣我們就可以得到一個想法，也就是新的點$(x_1)$就會是舊的點$(x_0)$去減掉斜率$(f'(x_0))$，即$x_1 = x_0 - f'(x_0)$。

其實比較直觀的想法就是，我們都知道斜率為0就是最佳解，自然就是要往這個方向前進，那正斜率要減才會接近0，而負斜率要加才會接近0。
### Method 2: Be Clever

不過這樣的方式會有一個問題，當我們處於一個斜率很大點的時候，這個計算動作會很大，相當於你奮力一跳，有可能跳過頭的。我們會比較希望是小小的一步，慢慢的來。

這種情況下我們是可以乘上一個很小的數值，比方說$0.01$之類的，這個數值又稱為學習效率(learning rate)，一般以$\alpha$來表示。
### Method 2: Be Clever

加入$\alpha$之後會得到一些好處，當我們在斜率比較大的地方會透過$\alpha$控制讓它跳也不會跳那麼大，而在接近最佳解的時候它會很小很小的移動。

這樣的方法就稱為梯度下降(Gradient descent)，這在機器學習中是很重要的觀念。

通常採用梯度下降是需要迭代計算的，我們會有一個初始點$x_0$，經過一次迭代計算得到$x_1$，再計算得到$x_2...$，最終我們可以得到一個非常接近最小值的解。

### Gradient Descent

上面就是梯度下降的一個演算過程，我們有個函數$f(x)$，然後目標是找出$f(x)$的最小值：
1. 首先是定義learning rate - $\alpha$，然後選擇一個初始點
2. 利用$x_k = x_{k-1} - \alpha f'(x_{k-1})$更新位置
3. 重覆Step 2一直到你覺得滿意為止

### Gradient Descent

現在我們就可以把一開始的歐米加問題拿來怒算一發：
1. learning rate $\alpha=0.005$，初始位置$x=0.05$
2. 計算在該處的導數，$f'(0.05) = -18.9$，移動至$0.1447$
3. 計算$x=0.1447$的導數，移動至$0.1735$
4. 一直重覆計算直到你滿意

有發現一個重點嗎？我們根本不用去解$e^x - \dfrac{1}{x}=0$，我們唯一做的就是不斷的計算導數，然後變更位置，計算導數。
## Optimization using Gradient Descent in one variable - Part 3
[課程連結](https://www.coursera.org/learn/machine-learning-calculus/lecture/Bl6y7/optimization-using-gradient-descent-in-one-variable-part-3)

### What Is a Good Learning Rate?

學習效率在機器學習中是非常重要的觀念，基本上要找出一個好的學習效率是很難的一件事。

太大的學習效率就跟上圖左一樣，你會不斷的跳動，永遠到不了最佳解。

太小的學習效率就跟上圖右一樣，可能要花很久的時間，或者永遠到不了最佳解。

### What Is a Good Learning Rate?

好的學習效率真的可以帶你上天堂，一路直達最佳解，但這很難，這可能可以寫很多論文來研究，但沒有一個標準答案。
### Drawbacks of Gradient Descent

事實上梯度下降還存在某一個問題，上圖來看，黑色點點是最佳解，但有時候我們會以為我們得到的區域最佳解就是全域最佳解。

這種情況下最好的方法就是隨機生成初始點然後多執行幾次，這樣就比較有機會避免局部最佳解。

## Optimization using Gradient Descent in two variables - Part 1
[課程連結](https://www.coursera.org/learn/machine-learning-calculus/lecture/H0RpK/optimization-using-gradient-descent-in-two-variables-part-1)

課程說明兩個變數的梯度下降

### Gradient Descent With Heat Example

永遠的三溫暖範例，兩個變數與溫度的變化。課程中已經嚐試利用計算偏導數的方式來求得最佳解。現在我們要嚐試利用梯度下降來找出最佳解。

## Optimization using Gradient Descent in two variables - Part 2
[課程連結](https://www.coursera.org/learn/machine-learning-calculus/lecture/MnkhF/optimization-using-gradient-descent-in-two-variables-part-2)

### Idea for Gradient Descent

我們從一個隨機座標$(x+0, y_0)$開始，計算在該座標的斜率，然後決定移動的方向$\nabla{f}$。這邊要注意，如果你就往那方向去的話是會變熱的，我們要往涼的方向，所以取負，實際是往$-\nabla{f}$。

### Idea for Gradient Descent

往梯度所指引的方向前進之後我們會到達新的座標，即$(x_1, y_1) = (x_0, y_0) - \alpha \nabla{f}$。

這作法跟一個變數的情況是完全一樣的，就差在一個是計算導數一個是計算梯度。
### Method 2: Gradient Descent

來面試數學吧。上面給定溫度的$T$函數，起始座標為$(0.5, 0.6)$，梯度的部份就是各別計算兩個變數的偏導數，也就是$\nabla{f}=\begin{bmatrix}\dfrac{\partial{f}}{\partial{x}}\\ \dfrac{\partial{f}}{\partial{y}}\end{bmatrix}$，相關的推論在先前的課程已經有說明過，所以這邊就直接給出偏導數公式，最終會得到梯度為$\nabla{f}(0.5,0.6)=\begin{bmatrix}-0.1134 \\ -0.0935\end{bmatrix}$。
### Method 2: Gradient Descent

經過梯度的指引，我們往下一個地點前進，到達的新標座就是$(0.5057, 0.6047)$
### Gradient Descent

現在，我們只需要不斷不斷的重覆一樣的計算，就可以一小步一小步的往最冷的地方前進。

### Gradient Descent

簡單來說，梯度下降這方法就跟一個變數的做法一樣。定義一個學習效率，然後選擇一個起始點，接著就是根據梯度計算移動方向，不斷的重覆這個作法，一直到你覺好像沒什麼變動為止。
### Gradient Descent With Local Minima

跟一個變數會遇到局部最佳解一樣，兩個變數也是會有同樣的問題。

一樣的，多試幾個隨機起始點就比較有機會得到全域最佳解。
## Optimization using Gradient Descent - Least squares
[課程連結](https://www.coursera.org/learn/machine-learning-calculus/lecture/XhFvn/optimization-using-gradient-descent-least-squares)

### Gradient Descent With Power Lines Example

回顧我們課程中說明過的電力線問題，當初逐步求偏導數得到的解如上圖所示。

### Linear Rrgression: Gradient Descent

這次我們用梯度下降來求解，目標一樣是最小化建置成本，它的梯度如下：
$\nabla {E}=[28m+12b-42,6b+12m-20]$

一樣的，我們給定一組隨機的$m_0,b_0$做為起始值，然後不斷的迭代計算梯度來更新$m,b$。

## Optimization using Gradient Descent - Least squares with multiple observations
[課程連結](https://www.coursera.org/learn/machine-learning-calculus/lecture/1HQXp/optimization-using-gradient-descent-least-squares-with-multiple-observations)

### Gradient Descent



上圖左是三個電塔的問題描述，上圖右則是成本函數的呈現，幾張圖說明的就是不同的$m,b$組合對應不同的成本。
### Gradient Descent

現在我們換個例子來看，假設我們想要做一個廣告預算與產品銷量之間的預測，$x$軸的部份是預算，$y$軸則是銷量，求解的方法是線性迴歸，很明顯的我們找的就是一條$y=mx+b$的線。

上圖左看到的是很多觀察到的資料，以$x_1,y_1$來看，這個資料點的loss就會是$(mx_1+b-y_1)^2$，其中$mx_1+b-y_1$計算的是$y$軸的距離差異，取平方，因此誰減誰都是沒問題的。

把所有的觀察到的資料點的loss加在一起，然後取平均，然後再除以2，這個2的話有的有，有的沒有，算了，這邊就是有，總的成本來看就是：
$L(m,b)=\dfrac{1}{2n}[(mx_1+b-y_1)^2+...+(mx_n+b-y_n)^2]$

這時候迭代更新的數學式就是：
$\begin{bmatrix}m_1 \\ b_1\end{bmatrix}=\begin{bmatrix}m_0 \\ b_0\end{bmatrix} - \alpha \nabla{L_1}(m_0,b_0)$
### Gradient Descent

隨著迭代更新的過程，我們會不斷的取得較好的線性迴歸，最終得到最佳解。