# Logic Operations

可以藉由 Aggregation 來做出邏輯運算的效果。

例如有兩條線 $g_{1}$，$g_{2}$，則可以知道：

$$
AND(g_{1},g_{2})=sign(-1+g_{1}+g_{2})\\
OR(g_{1},g_{2})=sign(1+g_{1}+g_{2})
$$

可以發現常數的 -1、+1 這兩項起到關鍵的作用。

所以我們也可以輕易的推導出一個多邊形區域，也就是把全部的線 AND 起來，但前提是這些線有圍成一個多邊形區域。

## Convex Set Hypothesis

既然我們可以圍成多邊形，那就代表我們的 [$d_{vc}$ 可以到無限大](https://hackmd.io/NmTvjWzoRKWnlN6ALtwR7g?view#Growth-Function)。但也代表要小心 Overfitting。

同時代表我們可以做到逼近平滑邊界，如同 Random Forest 做的一樣。

# Multi-Layer Perceptrons: Basic Neural Network

從上面邏輯運算中，會發現一層結構無法做出 XOR；
因為如果把 XOR 拆成 AND 跟 OR 會發現：

$$
XOR(A,B)=OR(AND(A,\sim B),AND(\sim A,B))
$$

所以我們可以靠兩層結構來達成 XOR。

## bio-inspired model

這種多層的結構啟發自生物當中的神經元。

但是如同眾多生物啟發的工具，例如飛機，雖然是受鳥類飛行所啟發，但是並非真的一定要跟鳥的翅膀一樣可以拍動，我們可以靠其他動力或方法來進行飛行。

多層神經網路確實是受生物神經元啟發，但我們會為其植入深厚的數學原理。

# Transformation Function

最終輸出的地方可以是階梯，線性或 S 型，但通常來說比較喜歡用線性。

而中間轉換的函數，通常來說會統一用一種；普遍喜歡用 S 型，因為：

- 階梯形：不容易做最佳化
- 線性：全都用線性的話，那就跟一個大的線性轉換是等價的

## tanh

這就是普遍常用的 S 型轉換：

$$
tanh(s)=\frac{e^{s}-e^{-s}}{e^{s}+e^{-s}}=2\theta(2s)-1
$$

## 記號

- 層數 $L$：從第 0 層開始，也就是最一開始的輸入資料。
- 維度 $d^{(l)}$，第 $l$ 層有幾個資料
- 通常會加入第 0 筆資料，也就是常數項。
- 或也叫做 bias term

### 權重 weight & 分數 score

將資料在層與層之間轉換，並經由權重算出分數。

$$
\Large{\text{Weight: }w_{ij}^{(l)}}\\
\Large{\text{Score:}s_{j}^{(l)}=\sum_{i=0}^{d^{(l-1)}}w_{ij}^{(l)}x_{i}^{(l-1)}}
$$

- $l$：權重和分數的層數
- $1\le l \le L$
- $i$：前一層輸入數量
- $0\le i \le d^{l-1}$
- 記得 0 是因為有常數項
- $j$：當前層輸入數量
- $1\le j \le d^{l}$

### Transformed Data

$$
\Large{x_{j}^{(l)}}=
\left\{\begin{matrix}
tanh\left(s_{j}^{(l)}\right) & l < L\\
s_{j}^{(l)} & l = L
\end{matrix}\right.
$$

上面的 x 是轉換過的資料，層數大於 0；$x^{0}_{j}$ 代表是一開始的資料。

# Pattern Extraction

隱藏層在做的事，就是看前一層的輸入 $\mathbf{x}$，跟當前這層的權重 $\mathbf{w}$，到底合不合，內積到底大不大。

內積我們之前就知道代表了相似程度，所以每次的轉換都在算 $\mathbf{x}$ 跟 $\mathbf{w}$ 到底多相似；如果很相似，代表作了某種「模式的確認」。

如此一來我們便**萃取出了模式**。

# Gradient boosting

如果隱藏層只有一層，換句話說就是之前出現的 non-uniform linear model，那麼我們可以直接使用 Gradient boosting，一次一次的加入一顆顆 node。

但是如果我們想要多層， GB 就不會是個好方法。

# Backpropagation

想要把潛藏在資料中的模式，使用多層的結構學會，方法就是之前的老朋友 Stochastic Gradient Descent。

首先列出錯誤評估的函數。由於這裡我們最終是用來做 Regression 所以：

$$
e_{n}=\bigl(y_{n}-NNet(\mathbf{x}_{n})\bigr)^{2}
$$

SGD 更新方法：

$$
\large
w_{ij}^{(l)}\leftarrow w_{ij}^{(l)}-\eta\ \frac{\partial e_{n}}{\partial w_{ij}^{(l)}}
$$

## 連鎖率

透過我們的微積分傳統藝能--連鎖率：

1. $e_{n}$ 是 $s_{j}^{(l)}$ 的函數
2. $s_{j}^{(l)}$ 是 $w_{ij}^{(l)}$ 的函數

可以得到：

$$
\large
\frac{\partial e_{n}}{\partial w_{ij}^{(l)}}=\frac{\partial e_{n}}{\partial s_{j}^{(l)}}\frac{\partial s_{j}^{(l)}}{\partial w_{ij}^{(l)}}=\delta_{j}^{(l)}\left(x_{i}^{(l-1)}\right)\\
=\text{該層對分數的微分}\times\text{前一層的 } x
$$

至於 $\large\frac{\partial e_{n}}{\partial s_{j}^{(l)}}$ 的部分，我們知道：

1. $\large x_{j}^{(l)}$ 是 $\large s_{j}^{(l)}$ 的函數
- 因為 $\large x_{j}^{(l)}=tanh\left(s_{j}^{(l)}\right)$
2. $\large{s_{1}^{(l+1)},s_{2}^{(l+1)},...,s_{k}^{(l+1)}}$ 是 $\large x_{j}^{(l)}$ 的函數
- 因為 $\large{s_{k}^{(l+1)}=\sum_{j=0}^{d^{(l)}}w_{jk}^{(l+1)}x_{j}^{(l)}}$

所以我們又可以得到：

$$
\large
\frac{\partial e_{n}}{\partial s_{j}^{(l)}}=
\sum_{k=1}^{d^{(l+1)}}
\frac{\partial e_{n}}{\partial s_{k}^{(l+1)}}
\frac{\partial s_{k}^{(l+1)}}{\partial x_{j}^{(l)}}
\frac{\partial x_{j}^{(l)}}{\partial s_{j}^{(l)}}\\
=\sum_{k}\delta_{k}^{(l+1)}\cdot w_{jk}^{(l+1)}\cdot \left(tanh\left(s_{j}^{(l)}\right)\right)^{'}
$$

所以可以發現 $\large\delta_{j}^{(l)}$ 是可以由下一層的 $\large\delta_{k}^{(l+1)}$ 乘上對應的權重(還有tanh對當層 s 的微分)算出來的。

## 統整

所以再次回顧更新方法：

$$
\large
w_{ij}^{(l)}\leftarrow w_{ij}^{(l)}-\eta\ \delta_{j}^{(l)}\left(x_{i}^{(l-1)}\right)
$$

- $\large x_{i}^{(l-1)}$ 的部分要從第 0 層開始算，一直往後算到最後一層
- 方向是「foward」
- $\large \delta_{j}^{(l)}$ 則可以在算完 $\large x_{i}^{(l-1)}$ 最後一層的時候，再一層一層往回算回第 1 層。
- 方向是「backward」

# Backpropagation Algorithm (Backprop)

每次會隨機挑一個點 $(\mathbf{x}_{n},y_{n})$，進行上述更新權重的步驟；直到 $E_{in}$ 讓你滿意為止。

## Mini-batch

如果每次都挑一個點，有可能並不是很穩定，需要更新比較多次才行，但是中間的計算量又那麼龐大。

所以實務上的作法是挑多個點一起平行的做，每次更新的時候是取 $\delta_{j}^{(l)}\left(x_{i}^{(l-1)}\right)$ 的平均值來更新。

這樣的做法叫做 Mini-batch，在實務上，避免了一次用全部點的龐大計算量，又避免單一個點的不穩定，因此效果比較好。

---

# Neural Network Optimization

事實上 NN 有很多層的時候，達到的多半是 local minimum；不同的權重初始值，也容易給出不同的 local minimum

如果權重初始給太大或太小，轉換成 S 型的時候會落在平緩區，梯度會很小，也就導致更新速度變慢。

所以建議初始值可以嘗試各種「隨機挑選」，並且要注意權重不可以正的過大或負的過小。

# VC Dimension

經過複雜的證明，對於使用類似 tanh 作為轉換的神經網路，$d_{VC}$ 大約為：

$$
d_{VC}=O(VD)
$$

- $V$ 是神經元數量
- $D$ 是權重數量

所以可以知道，神經元夠多，則我們力量就很強大；但也要小心 Overfitting

# Regularization

既然神經網路容易發生 Overfitting，那我們來給他調節一下。

## Weight-decay / L2

可以用老朋友 L2：

$$
\Omega(\mathbf{w})=\sum\left(w_{ij}^{(l)}\right)^{2}
$$

而 L2 的特點是大的權重懲罰的多，小的權重懲罰的少，所以權重的值都還在。

但是我們比較希望的是某些權重是 0，因為根據上面 VC 的公式我們就不會那麼有力量。

## Sparsity / L1

$$
\Omega(\mathbf{w})=\sum\left|w_{ij}^{(l)}\right|
$$

老樣子，他不可微分的特性讓我們不好處理。

## Weight-elimination / Scaled L2

這個跟 L2 很像的酷東西，避免了大的權重懲罰的多，小的權重懲罰的少。

而是透過把 L2 進行一點放縮，可以達成不管大或者小的權重，都懲罰中等的量：

$$
\Omega(\mathbf{w})=\sum\frac{\left(w_{ij}^{(l)}\right)^{2}}{1+\left(w_{ij}^{(l)}\right)^{2}}
$$

都懲罰中等的量，那麼大的就會變小，小的就會變成 0，達成稀疏的效果；也就減少了我們的力量。

# Another Regularization / Early Stopping

可以把更新權重的過程，看做是「拓展眼界」。

- 一開始我們從出發點往固定的範圍內，看哪個方向最好
- 所以隨著走的步數越多，看過的方向越多，「權重可能的組合就越多」
- 也就是說 $d_{vc}$ 就會越大

因此越早停下來，$d_{vc}$ 就可以越小。

所以可以設定由小到大不同停下來的步數進行 Validation，檢查在何時停下來最好。