Gradient Descent
==

# Review
先複習一下

Gradient:
$\theta^* = argminL(\theta)\\ L:loss function, \theta:parameters$
將參數放入這個loss function他會跟你說這個參數有多不好
$\equiv$要求這個$\theta^*$越小越好

**Gradient指的是$\nabla L(\theta)$的部分**

最終可以整理成$\theta^n = \theta^{n-1} - \eta\triangledown L(\theta^{n-1})$

**Gradient**:Loss的等高線之法線方向

步驟：
1. 在initial參數算出他的gradient
2. 然後從initial參數-(learning rate)*(gradient)
3. 不斷retpeat

# Tip1:Learning rate之調整

**紅色**：$\eta$剛剛好
**藍色**：$\eta$太小，會得到最佳解但是速度太慢
**綠色**：$\eta$太大，可能會在中間卡住
**黃色**：$\eta$太巨大，可能直接爆掉

在正常時候不會是二維空間的圖，所以要判斷$\eta$大小是否適合需要上面右圖來判斷(Loss對經過幾次update)
平常最好把這個圖畫出來，這樣才可以追蹤loss的下降，這樣才可以確定他是穩定的下降

## 自動調整Laerning Rate
Learning rate 會隨著不斷update而越來越小
一般來說initial的位置都離目標比較遠，大一點可以走比較快
經過多次update會比較接近目標，所以這時候降低$\eta$可以更精確找到目標

ex:$\eta^t = \frac{\eta}{\sqrt{t+1}}$ -> 這是依照時間線性的變更learning rate, 可能不是很match
最好是對每一個參數因材施教

## Adagrad

做法就是他每次的learning rate 將會是之前所有的偏微分$g^t$之均方根(root mean square)

可以整理成下列的式子：
可以整理出一般式

**這邊會有一個矛盾**

但是一般來說：
**gradient越大 -> step越大**

但是在**adagrad**之$\sigma$卻是
**gradient越大 -> step越小**
其中有幾種含意

### 解釋一
反差有多大
來看看他的反差有多大
所以如果
某gradient特別大，則其$\sigma$也會很大，所以leanring rate也跟著變小

### 解釋二
在考慮只有**一個參數**的狀況下

首先$y = ax^2+bx+c$之最佳解的位置會在$-\frac{b}{2a}$，若今天從最佳起始位置$x_0$出發，最好的一步將會是$x_0$到最佳解位置的距離(一步到位)，也就是$|x_0+\frac{b}{2a}|=\frac{2ax_0+b}{2a}$

$|x_0+\frac{b}{2a}|$ = $\frac{|2ax_0+b|}{2a}$
踏出去step的大小跟微分成正比的話是最好的(最佳解就是$\frac{微分的解}{2a}$)

但是在**多個參數**的情況下，**gradient越大不一定離最佳解越遠**
所以如上圖，c的微分會大於a，但是c的距離離最佳解比較近
所以在**跨參數的比較**下，微分越大離最佳解越遠**不成立**

所以這邊對y再做一次微分會得到2a
如果今天二次微分(2a)大(較陡的)，他的step便會小=離最佳解近
反之
如果今天二次微分(2a)小(較平的)，他的step便會大=離最佳解遠

最好的step要**和一次微分成正比**，**跟二次微分成反比**
較陡峭的的圖二次微分會比較大
所以在之後的比較，都要將二次微分考慮進去，才可以比較出最好的step
用$\frac{|一次微分|}{二次微分}$這樣才可以再多參數的情況下得到離最佳解的距離
### 其與adagrad的對應
因為要計算二次微分的計算量很大，會多花很多時間，所以adagrad選擇一個可以對應到二次微分但是不會增加額外計算量的方法
因為本來就要計算出$\sigma$所以可以用來對應其二次微分的大小

# Tip2:Stochastic Gradient Decent

使training 更快


gradient descent要計算出所有data的loss 才update參數
-> **穩定，速度慢**

stochastic gradient descent是在之前的data中**隨機**(隨機選效果還不錯)選一個n計算出n的loss才update參數
-> **不穩定，速度快很多**(天下武功唯快不破)
隨機取一數放近一般式，不管對不對，速度最重要

# Tip3:Feature Scaling

可以看出$x_2$的範圍蠻廣的，可以使用**rescaling將分佈壓縮**

如上面左圖，因為$x_2$很大，所以其變更會產生很大的影響，所以可以看到他在對$w_2$時呈現很陡的狀態，對$w_1$呈現較平緩的狀態
在**橢圓**的狀態用adagrad才可以找到較好的解(因為learning rate的調配)其step的方向也不一定會精準的切到最佳解

在看右圖，經過rescaling可以看到他呈現一個近正圓的狀態
他可以沿著**法線**很快地找到最佳解，比較有效率

scaling方法有很多種，下面是一個常見的方法

# Gradient Descent 理論

在做gradient descent的時候，loss的值不一定是越更新越小，可能因為step大小的緣故導致loss上升

## Formal Derivation


我們可以給訂一個圓圈圈然後不斷找在圈圈中最小的點，不斷更新中心點的參數，最後就可以抵達最佳解

## taylor series對單一參數
用taylor series可求他最小的點，如果$x, x_0$很相近的話，其高次方會=0 顧可以整理出上面的式子

舉例：
所以可以得到估測值$\frac{\pi}{4}$

## taylor series對多參數

所以回來到Gradient descent
只要將**圈圈縮小到一定大小**，就可以用taylor series可以找到最佳解


有
1. $L(\theta)=s+u(\theta_1-a)+v(\theta_2-b)$
2. $(\theta_1-a)^2+(\theta_2-b)^2\leq d^2$, (他要在圈圈範圍之內)
求最小的$L(\theta)\equiv(\triangle\theta_1,\triangle\theta_2) \cdot(u,v)$之最小值(其內積的最小值)
又內積之最小值是當他平行的時候，所以**便取(u,v)的反方向，長度為d**

整理可得上式，$\eta$為一個scale使其長度對應到d上

再將(u,v帶回去)便會發現他就是gradient descent 的式子
所以可得 若是learning rate設不夠小，則沒辦法使用

taylor的一次式就是gradient的式子，也是目前主流的流派，因為taylor二次式以上會需要微分兩次，時間上會被拖得很慢。

# Limitation of Gradient Descent

微分值是0，但是一般來說不會微到0因為一般都是gradient小於一定數值便停下來，所以大部分到一平台便會停下來
1. 可能會卡在local minima
2. saddle point