# Machine Learning 筆記（ 9 - ~）
###### tags : `shaimejump520`, `machine learning`
##### contributed by <`江家銘`>

[參考影片：Machine Learning (Hung-yi Lee, NTU)](https://www.youtube.com/watch?v=CXgbekl66jc&list=PLJV_el3uVTsPy9oCRY30oBPNLCo89yu49)

---

## ML Lecture 9-1 : Tips for Training DNN

----

### Recipe of Deep Learning


* Deep Learning 跟其他方法(decition tree, k-nearest neighber)不同，在 training 完後會先看 network 在 training set 的表現，如果在 training set 的表現不錯，再用 testing set 測試看看 preformance
* 過去的方法都是基於 trainging set，在 trainging set 的 performance 都是 100%，然而在 testing set 的表現就大不如預期了，換句話說就是 **overfitting** 了

----


* 在看到 testing data 上的表現時，有人會說 56-layer 的 model 是 overfitting 了，可是這並不一定是正確的，因為就如前面提到的，**overfitting 的義含是 model 在 testing data 上的表現不如 training data**。而當同時比較了 56-layer 在 testing 跟 training data 上的表現會發現，56-layer 在 training data 時的表現本來就比 20-layer 的表現差了，並不是 overfitting（可能的原因有很多，可能是卡在了 local minimal 等等之類的狀況）

> 那這種情況可以稱做「underfitting」嗎？
> **underfitting 的義含是 model 所擁有的參數不夠多，不足已解決面臨的問題**
> 而這個狀況我們沒有辦法確定 56-layer 這個 model 是否是 underfitting，因為這個 56-layer 可能是由 20-layer 後面再加上 36 個 layers 而成的 model，基本上 20-layer 能解決的問題，56-layer 一定也能夠解決（若後面 36 層都是 identity，那與 20-layer 是一模一樣的），不能夠稱為 underfitting

* 為了解決 model 在 training data 或 testing data 上表現不佳的問題，有許多不同的方法被提出，分別用於解決前者與後者的問題
* 例如：dropout，就是一種解決 model 在 testing set 上表現不佳的方法，如果把他使用在 training data 表現不佳的情況下，基本上是沒有辦法解決問題的

----

### Good Results on Training Data?

* New activation function
* Adative learning rate

* 上圖是手寫辨識在使用不同層數 model 的 training 結果，可以看到並不是愈多層的表現會愈好（而這個結果不是 overfitting，因為這只是在 training set 上的結果，只能說是 train 壞掉了XD）

----

### Vanishing Gradient Problem


* 在進行 learning 時，若是整個 network 的 learning rate 是相同的，在 backpropagtion 的過程中，前幾層參數的更新會比後幾層的慢上許多，可能後面的參數收斂了，前面的參數還幾乎是 random 的狀態，如此掉進了一個 local minimal，整體的表相當然不好


* 拿手寫數字辨識為例，使用的 activation function 是 sigmoid function
* 如上圖，sigmoid function 會將數值從 $[-\infty , \infty]$ 壓縮到 $[0,1]$ 之間，本來可能很大的 weight $\Delta w$ 卻對最後的 $C$ 僅能造成很小的影響

* 早期的解決方法是 RBM ，想法很簡單，既然在整個 network 做 training 的時候，幾乎沒有辦法更新到第一層 layer，那就先做 pre-train，把每一層 layer 都先 pre-train 過後再將整個 network 兜起來，就比較不會發生上述的問題，對 preformance 有所提升

* 後來有人提出，其實只需要更改我們所使用的 activation function，就可以有效的解決這個問題。Rectified Linear Unit (ReLU) 因此被提出：
* Relu 相較於 sigmoid 相當快速，沒有 exponetial 相關的運算
* 根據一些生物上的現象提出
* 可以視為無數的 sigmoid function 疊加而成
* 最就重要的就是可以解決 Vanishing Gradient Problem

----

### ReLU

* 用 ReLU 取代 Sigmoid 為 activation function
* $\sigma(z) =
\begin{cases}
z , \quad z>=0 \\
0 , \quad otherwise
\end{cases}$
* 若 input 小於 0 則可以忽視該 neuron , 而整個 network 就會變成 linear，並且不會有前幾層的參數都更新不到的問題

* ReLU - variant
* Leaky ReLU：保留負的 input 但給予較小的權重
* Parametric ReLU：可以動態調配權重，甚至每個 neural 的權重都不同（用 learn 的）

----

### Maxout
* 不拘於 ReLU 一種型式的 activation function，可以是很多樣的，**用 Learn 出來的**
* ReLU 變成了一種特別的 Maxout function

* 事先對計算完的 weight 做 grouping（可以超過兩個 elements）
* 對每個 groups 的 input 取 Max 當做 output（有點類似 max pooling）

#### ReLU is a special cases of Maxout

#### But Maxout is more than ReLU

* 根據不同的 $w'$ 跟 $b'$，Maxout 可以做出各種不同的 activation function，而且每個 neural 可以不同
* 並且更新 $w'$ 跟 $b'$ 可以使 activation function 是 learnable 的
* 在 Maxout network 裡的 activation function 可以是任何 piecewise linear convex function，端看你在 grouping 時是幾個 elements 一組

#### Maxout - Training
* Maxout 是可以 train 的嗎？Max function 是不可微分的吧？！
* 紅設框起來的是比較大的 elements，也就是回從 max 傳出的值，而其他，都是不會繼續往下傳的值

* 與先前 ReLU 相似的想法，整個 Network 數值的傳遞應該如下：
* 對於沒有繼續望下傳遞的值，可以暫時忽略，那麼整個架構就會變成 Linear 的，因此變為可微，可以利用 backpropagation 持續更新參數

> Q：那這樣一來，沒有望下傳遞的那些 elements 前的參數，不就都沒有更新到嗎？
> A：不會的，用不同的 Data 做為 input，所計算出的 $z$ 值都不相同，所以每次能夠通過 max function 的 elements 都不一樣，所以每個參數在 training 的過程中，都會被更新到！

----

### RMSProp

#### Review - Adative learning rate

先看到 Adagrad [之前的筆記](https://hackmd.io/zE4SdLqDQ8uW1djumnt7yA?view#Adaptive-Learning-Rates)：

* 藉由過去 gradient 的平方和開根號，來限制 learning rate 的大小，可以使參數更新的幅度較為合適


* 但 adagran 比較適合在 convex 的環境使用（如上圖左），如果在其他比較不規則的環境的話，就比較難以達到好的效果（如上圖右），在同樣的方向，有的地方變化梯度較大，有的較小，比較難以用 adagran 調配 learning rate

----

#### RMSProp

為解決上述問題，會使用 RMSProp 作為調配 learning rate 的方法

$w^1 \leftarrow w^0 - \dfrac{\eta}{\sigma^0}g^0 \quad \sigma^0 = g^0\\
w^2 \leftarrow w^1 - \dfrac{\eta}{\sigma^1}g^1 \quad \sigma^1 = \sqrt{\alpha(\sigma^0)^2 + (1-\alpha)(g^1)^2}\\
w^3 \leftarrow w^2 - \dfrac{\eta}{\sigma^2}g^2 \quad \sigma^2 = \sqrt{\alpha(\sigma^1)^2 + (1-\alpha)(g^2)^2}\\
\quad\quad\quad\vdots\\
\quad\quad\quad\vdots\\
w^{t+1} \leftarrow w^t - \dfrac{\eta}{\sigma^t}g^t \quad \sigma^t = \sqrt{\alpha(\sigma^{t-1})^2 + (1-\alpha)(g^t)^2}$
* 根據我們設定的 $\alpha$ 值，我們可以調配過去的 gradient 跟現在的 gradient 對 learning rate 的影響大小
> Root Mean Square of the gradients with previous gradients being decayed

----

### Hard to find optimal network parameters

* 在 train model 時，常常會擔心說會不會掉進 local minimal 之中，導致花費了許多時間跟運算資源，但 performance 都沒有起色，甚至是在 saddle point 跟 plateau 都會使參數的更新十分緩慢，導致 training 失敗
> 其實不必太過於擔心 local minimal 的問題，因為如果一個地方是 local minimal 的話，他的各個 dimention 都要到達一個谷底的位置，所以其實 local minimal 出現的機率是很低的，在一個很大的 network 之中，local minamal 的數量是很少、很難遇到的，你遇到的 local minimal 卡住的時候，那裡很可能就是 global minimal，或是很接近 global minimal 了。

* 將問題想像成在實際世界中，巨石從山頂滾下，他也會遇到 plateau, saddle point, 及 local minimal，好像也會應此止步不前，但是由於有「慣性」的存在，所以巨石是可以順利的滾絡到山谷，也就是 global minimal

----

### Momentum

* 現在問題就是，我們要怎麼把「慣性」這個想法，實作再我們 network 的更新？

#### Review: Vanilla Gradient Descent

在講到 Momentum 之前，先複習一下，原本的 gradient descent 是怎麼做的，先觀看[先前的筆記](https://hackmd.io/zE4SdLqDQ8uW1djumnt7yA?view#Review-Gradient-Descent)
* 大致上的想法就是計算 gradient，每次更新參數時，往 gradient 的反方向更新（搭配 learning rate），一步步的往 global minimal 靠近

----

#### Movement: movement of last step minus gradient at present


* 可以看到，在更新參數時：
* $\theta^{t+1} = \theta^{t} + v^{t+1}$
* $v^{t+1} = \lambda v^{t} - \eta \nabla L(\theta^{t})$
* $v^{t+1}$ 為新的參數需要修改的方向，可以發現與先前的方法不同，不僅僅採計了前一次的 gradient，還加上了 $\lambda$ 倍的 $v^{t}$，使得現在更新的方向不僅會受當下的因數影響，先前的更新方向也會有一定比例的影響到這次的更新，如此維持了**更新的「慣性」**
* 其中 $\lambda$ 與 $\eta$ 相似，都是我們事先設定好的，可以調配參數更新受慣性影響的程度
* 所以，我們可以說 $v^i$ 其實就是過去所有 gradient（$\nabla L(\theta^0),\nabla L(\theta^0),\cdots, \nabla L(\theta^{i-1})$）的總和，但各個 gradient 保留的權重視是多少，就要看 $\lambda$ 的值是設多少了

* 而 momentum 幫助我們逃離 local minimal 的形象化就會像下圖：
雖然不見得一定可以成功離開 local minimal，但看起來是有希望的，比單單使用 gradient 好上許多

----

### Adam

也就是一個 **RMSProp + Momentum** 的方法！


----

### Good Results on Testing Data?

* Early Stopping
* Regularization
* Dropout

----

### Early Stopping

* 為了避免 overfitting，我們可以提早結束 training
* 為此，我們需要使用 Validation set 來在 trainging 的過程中讓我們知道何時該停止
* [Keras 對此有相應的 document](https://keras.io/getting-started/faq/#how-can-i-interrupt-training-when-the-validation-loss-isnt-decreasing-anymore)

----

### Regularization

* New loss function to be minimized
* Find a set of weight not only minimizing original cost but also close to zero

#### L2 regularization

* $L'(\theta) = L(\theta) + \lambda\dfrac{1}{2} {\left\lVert \theta \right\rVert}_2$
* $L(\theta)$：Original loss（e.g. minimize square error, cross entropy ...)
* $\theta = \{w_1, w_2,\cdots\}$
* regularization term：${\left\lVert \theta \right\rVert}_2 = (w_1)^2 + (w_2)^2 + \cdots$ （通常不考慮 biases）

* Gradient：$\dfrac{\partial L'}{\partial w} = \dfrac{\partial L}{\partial w} + \lambda w$
* Update：$\begin{split}w^{t+1} &\rightarrow w^t - \eta \dfrac{\partial L'}{\partial w} = w^t - \eta \lgroup\dfrac{\partial L}{\partial w} + \lambda w^t\rgroup\\&=(1-\eta\lambda)w^t - \eta\dfrac{\partial L}{\partial w}\end{split}$
* 因為 $\eta$ 跟 $\lambda$ 都是很小的數，所以$(1-\eta\lambda)$ 大約會是 $0.99$ 之類的數字，$(1-\eta\lambda)w^t$ 項會使 $w$ 在一次一次的更新中，愈來愈靠近 $0$
* 這叫作 **Weight Decay**

> Regularization 的目的就是要使 weight 往 0 靠近，與先前 Early stopping 的效果相似（提早結束可以使 weight 不至於過大）

#### L1 regularization

* $L'(\theta) = L(\theta) + \lambda\dfrac{1}{2} {\left\lVert \theta \right\rVert}_1$
* regularization term：${\left\lVert \theta \right\rVert}_1 = |w_1| + |w_2| + \cdots$

* Gradient：$\dfrac{\partial L'}{\partial w} = \dfrac{\partial L}{\partial w} + \lambda sgn(w)$
* 絕對值本來是不可微的，但我們知道他的形狀是一個 v 字型，負數部份微分為 -1，正數部份微分為 1，而 0 的部份微分就不要管他 ~ 把他當成 0，$sgn(w)$ 用來表示上述

* Update：$\begin{split}w^{t+1} &\rightarrow w^t - \eta \dfrac{\partial L'}{\partial w} = w^t - \eta \lgroup\dfrac{\partial L}{\partial w} + \lambda sgn(w^t)\rgroup\\&= w^t - \eta\dfrac{\partial L}{\partial w} - \eta\lambda sgn(w^t)\end{split}$
* 每一次更新參數時，會減去 $\eta\lambda sgn(w^t)$ ，當參數為正時，會減掉一些；當參數為負時，會加上一些
* 逐漸讓參數往 0 靠近，跟 L2 的做用類似，但方法不太一樣（L1 扣掉的值永遠都會是固定的：$\eta\lambda sgn(w^t)$ ，而 L2 扣掉的值，要看當下參數的大小：$\times \eta\lambda$）

> 用 L1 更新的參數會比較 sparse（可能有很多 0 和很大的值），L2 的會比較平均、比較小

#### weight decay


----

### Dropout

#### Training

* 每次在更新參數之前，都會對全部的 neural 做 sample，每個 neuron 有 p% 機率被 dropout
* 在做 training 時，被 dropout 的 neuron 就會被當作不存在，整個 network 架構就會變得細長：
（注意，因為每次 sample 的結果不同，每一次更新參數的時候 network 架構都會不一樣）

#### Testing
* 在 **Testing 的時候不需要做 dropout**
* 如果在 training 時的 dropout rate 是 p%，那在做 testing 時的 weight 要乘上 1-p%

> Why the weights should multiply (1-p)% (dropout
rate) when testing?
> 

#### Dropout is a kind of ensemble

* 根據 dropout 的 neural 不同，總共會有 $2^M$ 種的 network，所以總共也就 train 了那麼多種 network structure

* 在 testing 的時候，把 testing data 分別放進剛剛 train 的一堆 network 當中，取 output 的平均值，就會是我們最終的答案
* 然而，一次做 $2^M$ 個 network 的運算是不實際的，所以我們將 testing data 放進一個完整的 network 之中，其中所有的 weight 會是原始值的 1-p% 倍，最後得出的 output 會很近似上述所講的平均值

> ensemble 用 1-p% weights 的概念可以簡略的用下面的例子解釋：
> 

---

## ML Lecture 10: Convolutional Neural Network

----

### Why CNN for Image

* 如果一般的 DNN 來 train 影像處理的話，用 fully connected network 會像是下方的架構：

* 通常每一層的 hidden layer 會做抽取圖片不同的 feature（像上圖範例，一開始取顏色，再來取紋路，之後可能會是抓出一些物件...，每個 neural 負責不同的種類）
* 但如此的架構會有參數量過多的問題：
* 假設是一張 100 x 100 pixels 的圖片，那麼 input 的維度就會是 100 x 100 x 3 (rgb) = 30000
* 一層 hidden layer 有 1000 個 neural
* 那光第一層的參數就會有 30000 x 1000 那麼多
* 但用人類的思維去做簡單的判斷就會發現許多的 weights 是使用不到、多餘的，所以我們嘗試去簡化網路架構，希望不要使用那麼多的參數就可以進行影像處理

----

#### Property 1

* 通常圖片中的 patterns 是比整張照片的大小小上許多的，所以 neuron 並不需要看到整張照片就可以尋找到所需的 pattern
* 像是範例中，要辨識一張圖片中有沒有鳥，需要看圖片中是否有鳥嘴、翅膀、羽毛等等的存在
* 而在某一層 hidden layer 中的某一個 neuron 是負責偵測是否有鳥嘴存在的，他其實並不需要看到整張圖，只需要靠近鳥嘴的那一小部份就足以判斷是否存在鳥嘴
* 所以，其實那個 neuron 並不需要連接到整張圖，僅需要連接到其中的一小部份就可以

----

#### Property 2

* 相同的 pattern 可能出現在圖片中的不同地方
我們並不需要兩個不同的 neural 擁有兩組一樣的參數去做幾乎一模一樣的事，我們要求他們可以共用那些參數，以減少參數量

----

#### Property 3

* 對於人們來說，一張圖片做 Subsampling（例如每 10 個 pixels 取一個所形成的較小張、解析度較低的圖片）後，依舊是可以辨識出來的
所以使用 subsampling 後的圖片去做 training 依舊可以得到我們所需的結果，同時可以減少大量參數的使用

----

#### The whole CNN


* 其中 Convolution 用於先前提到的 Property 1 及 Property 2
* Max Pooling 可以解決 Property 3

---

### CNN -- Convolution

* Filters 可以視為 fully connected network 中的 neural
* 每個 Filter 都是 Matrix，其中的 elements 就是 network 的 parameters
* Filter 的大小是 3x3，代表它所偵測的是一個 3x3 大小的 pattern（for Property 1）

----

* Convolution 的過程就是做內積，其中 stride 代表 filter 在 image 上每次位移的步數
* 右下是做完 convolution 的結果
* 會發現這個 filter 的結構就是要偵測這整張圖片有沒有對角線都是 1 的這種 pattern
* 而我們用一個 filter 成功的在圖片的兩個不同地方發現了這個 pattern，符合了 Property 2 的要求

----

* 用各種不同的 filter 去做 convolution
會得到許多不同的 4x4 的 image ，我們將他們稱為 feature map

> Q：CNN 使用了固定的 filter 大小，導致我們也只能偵測該 matrix 大小的 pattern，這時候就會有一個問題：如果圖片中的鳥嘴的大小不同該怎麼辦？
>
> A：為解決上述 convolutional 架構網路的困境，Deepmind 提出了 [Spatial Transformer Networks](https://arxiv.org/pdf/1506.02025.pdf)，該架構在進行 convolution 前，會先接一個 Spatial Transformer，會對不同大小、角度、扭曲程度的圖像做 sampling，使整個網路架構可以學習到更加多元的 feature

----

### CNN -- Colorful image

剛剛是以黑白圖片為例介紹 convolution，所使用的都是一層的 matrix，若是要對彩色的圖片做 convolution 的話，因為會分成 RGB 3個 channel，所以不論是 image 還是 filter 都會是多層的、立體的，如下圖：

----

### Convolution v.s. Fully Connected


* 其實做 convolution 就等於在做 fully connected network（只是中間挑掉了一些 weights），convolution 的結果就是 neural 的 output，示意圖如下：
* 比起 fully connected，每個 neural 只用了較少的 input，可以有效減少 parameters 的使用
* 而且對於辨識圖片中不同位置的 neural 可以共用相同的 weights，也可以減少 parameters 的使用

----

### CNN -- Max Pooling

* 對做完 convoiution 的 feature map 做 max pooling（四個四個一組，每一組取最大值）

最後每一個 filter 都取得一個 2x2 的 image

----


一張 6x6 的圖片經過 convolution 跟 max pooling 後會輸出 2x2 的 image，output 的維度取決於 filter 的個數，每個 filter 代表一個 channel

> 做完一次 convolution 跟 max pooling 會得到較小的圖片，再繼續做會得到更小的圖片
> Q：假設有 25 個 filter 做完一次後會得到 25 個 feature map，那再做一次會得到 25x25 個 feature map 嗎？
> A：Filter 會是一個立體的結構，一次會對全部的 feature maps 作用（可以看下方 keras 部分對於參數的解釋），所以 25 個 filter 就只會有 25 個 output
>

----

### Flatten

* 概念很簡單，就是把剛剛做完的 feature maps 丟進 fully connected network 之前先把他們展開：

----

### CNN in Keras

* 跟 DNN 的差別只在 input format (vector -> 3-D tensor) 跟 network 的架構
* 圖片的長、寬各 1 維，再加上 RGB 就是 3 維，tensor 代表高維度的 metrix
* `Dense` 改成 `Convolution(25, 3, 3, Input_shape=(28, 28, 1))`
* 代表有 25 個 3x3 的 filter
* input 是 28x28 pixels 的圖片，1 代表黑白（如果要用 RGB 就改成 3）

* `MaxPooling2D(2, 2)`，表示做 max pooling 的一個 group 是 2x2，每次選最大的那一個

* 在過程中的 data size 變化如下：
* 注意在第一次做 convolution 的時候，每個 filter 因為是 3x3 大小，所以有 9 個 parameters
* 但到了第二次做 convolution 的時候，因為 input 是 25 個 feature maps，所以 filter 的參數數量變成了 25x3x3 = 225 個

* 再經過 flatten 後接上 fully connected network

----

### What does CNN learn？


上圖是取得某幾個 filter 最 activate 的圖片來看，發現每個 filter 是在辨識各種不同的「紋理」

----


這次我們看的是 fully connected network 中的 neural 最被 activate 的圖片