# 李宏毅_ATDL_Lecture_3
###### tags: `Hung-yi Lee` `NTU` `Advance Topics in Deep Learning`
[課程撥放清單](https://www.youtube.com/channel/UC2ggjtuuWvxrHHHiaDH1dlQ/playlists)
## Computational Graph & Backpropagation
[課程連結](https://www.youtube.com/watch?v=-yhm3WdGFok&list=PLJV_el3uVTsPMxPbjeX7PicgWbY7F8wW9&index=3)
### Introduction

計算梯度比較有效率的作法就是利用Backpropagation，可參考課程連結：
* [Backproagation for feedforward](http://speech.ee.ntu.edu.tw/~tlkagk/courses/MLDS_2015_2/Lecture/DNN%20backprop.ecm.mp4/index.html)
* [Backpropagation throuth time for RNN](http://speech.ee.ntu.edu.tw/~tlkagk/courses/MLDS_2015_2/Lecture/RNN%20training%20(v6).ecm.mp4/index.html)

這次的課程會以Computational graph的觀念來說明。
### Computational graph

Computational graph是一種語言，一個用來描述function用的語言。
* None: Variable(i.e. scalar, vector, tensor, matrix.)
* Edge: operation

舉例說明：
$y=f(g(h(x)))$

將上述函式拆解為下：
1. $u=h(x)$
1. $v=g(u)$
1. $y=f(v)$

以Computational graph來描述的話就如圖示，箭頭下方$h$代表將$x$丟到$h$得到$u$，以此類推。

當有多輸入的時候就可簡報右上一樣，兩個輸入經過相同的function-$f$得到輸出$a$

### Computational graph

上圖是另一個Computational graph的案例。

Computational graph的好處在於，在graph上計算每一個Variable的gradient是簡單的
### Review: Chain Rule

快速覆習Chain Rule

Case1:
$z=f(x)\rightarrow y=g(x), z=h(y)$

將上述函式利用graph來表示，可以清楚看的到，如果要計算$\dfrac{dz}{dx}$的梯度，可以由$\dfrac{dz}{dy} \dfrac{dy}{dz}$來計算

Case2:
$z=f(x) \rightarrow x=g(s), y=h(s), z=k(x,y)$
將上述函數利用graph來表示，可以看的到$s$帶入兩個function分別得到$x,y$，再進入一個function得到最後的$z$，因此$\dfrac{dz}{dx}$就會從兩邊的偏微分計算相加而得。

透過Computational graph可以清楚瞭解如何利用Chain rule來表示微分。
### Computational graph

利用更早之前的案例，透過graph的呈現，我們清楚知道計算$\dfrac{\partial e}{\partial b}$會經過兩段的Chain rule，甚至可以很快速的就在graph上計算每一個Variable的偏微分。
### Computational graph

計算$\dfrac{\partial e}{\partial a}$也是一樣的方式，計算從$a$到$c$的路徑即可，很直觀的，它就是`1x3=3`
### Computational graph

如果要同時計算$\dfrac{\partial e}{\partial a}$與$\dfrac{\partial e}{\partial b}$的偏微分，那就需要利用`Reverse mode`，反向的作法，如果採行正向作法那要計算兩次，比較沒有效率。

既然是反向，就從$e$開始回推：
$\dfrac{\partial e}{\partial a}=(1*3)*1=3$
$\dfrac{\partial e}{\partial a}=(((1*3)*1)+((1*5)*1))=8$

實作NN的時候我們就需要應用到這種`Reverse mode`，理由在於我們會計算所有參數對`Cost function`的偏微分，如果將它用`Computational graph`來描述的話，它只有一個output，我們就從這個output開始利用`Reverse mode`對`Cost function`做偏微分是比較有效率的。

### Computational graph

如果有`Parameter sharing`_{(參數共享，i.e. CNN, RNN)}的情況，可以怎麼處理?以下函式為例：
* $y=xe^{x^2}$
* 首先將它以`Computational graph`繪製
* 計算各點偏微分
* 計算$\dfrac{\partial y}{\partial x}$
* $e^{x^2}+x \cdot e^{x^2} \cdot 2x$

### Review: Backpropagation

Backpropagation的計算分為兩段，`Forward`與`Backward`。
* Forward: $\dfrac{\partial z_i^l}{\partial w_i^l}$
* 直觀來看，前一層layer的neuron output就是該neuron的偏微分
* 如果前一層是input layer的話，那input就是該neuron的偏微分
* Backward: $\dfrac{\partial C}{\partial z_i^l}$
* $\delta_i^l:$對第$l$個layer的第$i$個neuron計算Error signal

### Feedforward Network

現在，利用Computational graph的方式來說明Feedforward。

以兩個layer為例：
1. $W^1x+b^1=z^1$
2. $z^1$經過啟動函數得到$a^1$
3. $W^2a^1+b^2=z^2$
4. $z^2$經過啟動函數得到$y$

在Computational graph中，每一個node都是一個Variable，$w,b$也是Variable，由外部加入主幹，再與$a$一起計算得到$z$
### Loss Function of Feedforward Network

再延伸至Loss Function，我們有一個真實的Label-$\hat{y}$，帶入`Cost Function`計算可得$C=L(y, \hat{y})$。
### Gradient of Cost Function

繪製好Computational graph就可以計算$w,b$對$C$的偏微分。
* $C$是一個Scale
* $b,a,z$是Vector
* $W$是Matrix
### Jacobian Matrix

Vector對Vector做偏微分得到的稱之為『Jacobian Matrix』。

舉例來說：
$y=f(x)$，並且$x,y$皆為Vector，當計算$x$對$y$的偏微分之後我們會得到Matrix，其維度為($y$的維度, $x$的維度)，並分別對兩兩數值做偏微分
### Gradient of Cost Function

瞭解`Jacobian Matrix`的定義之後就可以明白，對兩個Vector做偏微分得到的就是一個`Jacobian Matrix`。

$\dfrac{\partial C}{\partial y}$，其中$C$是一個1維數值，$y$是Vector，因此計算所得是一個扁扁的結果，其Dimension為(C, y)的大小。

以分類問題來看的話，$\hat{y}$是一個`One Hot`的資料，僅其中1維為1，其餘為0，$C=-logy_r$。

因此，計算$\dfrac{\partial C}{\partial y}$的結果僅在所屬第$r$維的地方會計算偏微分$\dfrac{-1}{y_r}$，其餘維度皆為0。
### Gradient of Cost Function

計算$z^2$對$y$的偏微分，這時候所得是一個`Jacobian Matrix`，$z^2$經過啟動函數之後得到$y$。

依之前對`Jacobian Matrix`說明可知，索引為(i-row, j-column)的地方所得的偏微分為$\dfrac{\partial y_i}{\partial z^2_j}$
* $i \neq j$：，其偏微分為0，因為沒有影響性。
* $i=j$：，計算所在結果切線斜率

結果來看，它是一個`Diagonal Matrix`，因為僅於$i=j$的地方計算，這是可以理解的，而且這是以最終為`Sigmoid`為輸出。

當最後是以`Softmax`為輸出的時候，結果就不會是`Diagonal Matrix`，原因在於最終得到並不會僅於某一個維度上有值，每一個維度都會影響到最終的輸出。
### Gradient of Cost Function

再往前推導，其中$\dfrac{\partial z^2}{\partial a^1}$是`Jacobian matrix`

$z^2=W^2a^1$
* $\dfrac{\partial z^2_i}{\partial a^1_j}=w^2_{ij}$
* 此`Jacobian matrix`即為$W^2$
### Gradient of Cost Function

$z^2=W^2a^1$
* $\dfrac{\partial z^2}{\partial W^2}$
* 假設$W^2$是一個mxn維度的矩陣，$a^1$為n維，$z^2$為m維。
* 原應該將$\dfrac{\partial z^2}{\partial W^2}$視為擁有三維的tensor，但為了說明上的理解，將$W^2$視為擁有mxn的**Vector**
* 僅於$i=j$的部份偏微分有值，其餘$i\neq j$偏微分皆為0
* 直觀來看，$z^2_i$僅與$w^2_i$是有相關性的，因此在$i\neq j$的地方對$z^2_i$是無關的。
* 偏微分的值為$a^1_k$
### Gradient of Cost Function

以相同的方式求出$z^1$對$a^1$的偏微分，以及$x,W^1$對$z^1$。

如果希望計算$W^1$對$C$的偏微分，就只要一路乘過來就可以得到每一個$W$的元素對$C$的偏微分，即維度為1x$W^1$
### Question

雖然在說明`Computational graph`的時候好像只有提到`Backward Pass`，但其實在求`Backward Pass`的時候還是需要用到`Forward Pass`的值，i.e. $a, z$
### Recurrent Network

這邊說明的是如何利用`Computational graph`來表示`Recurrent Network`，這只是單一表示。
### Recurrent Network

`Computational graph`中，如何表示一個Function是由自己來定義的，因此我們些許減化RNN的`Computational graph`的表示方式，最終將每一個`Time Step`的`Cost`加總得到$C$，再計算$W^h$對$C$的偏微分。

一樣的由$C$開始倒推，而$W^h$並非僅出現於最後一個`Time Step`，因此需要一路計算到最初始的$W^h$
### Recurrent Network

$W^h$是一個共用參數，因此需要將每一個$\frac{\partial C}{\partial W^h}$的計算出之後加總才是真正的值。
### Reference