# 淺入淺出瞭解機器學習_04_Computational Graphs
###### tags: `淺入淺出瞭解機器學習`
從linear regression到logistic regression，大概對機器學習的實作已經有一些許的概念，計算，然後求導，接著更新參數，再計算，如此迭代循環，一直到收斂。
在討論深度學習之前，我們先討論另一個議題，那就是Computational Graphs。瞭解這個觀念對深度學習裡面談到的鏈式法則會很有幫助。
## Computation Graphs
Computation Graphs是一種用來描述function的語言，也可以是一種表示數學計算的語言，舉例來說，$y=f(g(h(x)))$，我們可以將它寫成：
* $u = h(x)$
* $v = g(u)$
* $y = f(v)$
然後，以graph來表示如下：
```graphviz
digraph graphname {
rankdir=LR;
x -> u [label="h"];
u -> v [label="g"];
v -> y [label="f"];
}
```
上面流程圖說明著，$x$ input之後經過function-$h$變成$u$，再經過function-$g$得到$v$，最後經過function-$f$得到$y$，透過graph的表示似乎清楚多了。
如果我們將一個數學的計算改以graph來表示，舉例來說，$e = (a + b) * (b + 1)$，我們首先可以用一樣的作法，將這個數學式拆解：
* $c = a + b$
* $d = b + 1$
* $e = c * d$
用代數的方式，讓每一個計算項目有新的別名，然後再以graph來表示：
```graphviz
digraph graphname {
rankdir=BT;
a [label="a(2)"];
b [label="b(1)"];
c [label="c(3)=a+b"];
d [label="d(2)=b+1"];
e [label="e(6)=c*d"];
a -> c;
b -> c;
b -> d;
c -> e;
d -> e;
}
```
以Computational graph方式可以很清楚的看到每一個graph的流向，而且有一個更重要的就是，用這種方式來計算梯度會更簡單，觀念上也更容易理解。
以上圖的範例來看，你可以把它視為一個神經網路計算forward propagation的一個過程。
而下圖就是一個backward propagation的過程，我先把數值拿掉，避免誤會：
```graphviz
digraph graphname {
rankdir=TB;
a [label="a"];
b [label="b"];
c [label="c=a+b"];
d [label="d=b+1"];
e [label="e=c*d"];
e -> c[color="Red"];
e -> d[color="Red"];
d -> b[color="Red"];
c -> b[color="Red"];
c -> a[color="Red"];
}
```
### Example
用一個吳恩達老師課程上的實際案例說明，假設有一個函數$J(a,b,c)=3(a+bc)$，我們假設：
* $u = bc$
* $v = a + u$
* $J = 3v$
* $a=5,b=3,c=2$
然後繪製graph，計算forward propagation：
```graphviz
digraph graphname {
rankdir=BT;
a [label="a(5)"];
b [label="b(3)"];
c [label="c(2)"];
u [label="u(6)=bc"];
v [label="v(11)=a+u"];
J [label="J(33)=3v"];
b -> u;
c -> u;
a -> v;
u -> v;
v -> J;
}
```
接下來計算backward propagation，我們知道，求偏導就是計算其斜率，我們可以利用一個非常小的偏移來計算這個偏移造成多少的影響，以此計算出斜率，我自己理解是這個節點對下一個節點出了多少力這樣，看個人理解，下面給出一個吳恩達老師課程上的範例：
有這麼一個簡單的觀念，就可以來計算backward propagation，我們先把圖畫出來：
```graphviz
digraph graphname {
rankdir=TB;
a [label="a(5)"];
b [label="b(3)"];
c [label="c(2)"];
u [label="u=bc"];
v [label="v=a+u"];
J [label="J=3v"];
J -> v[color="Red"];
v -> u[color="Red"];
v -> a[color="Red"];
u -> b[color="Red"];
u -> c[color="Red"];
}
```
讓我們一個一個慢慢的推：
1. $\dfrac{dJ}{dv}, J=3v$，用著高中的解題技巧，其實一看就知道答案是$3$，不過還是用上面說的計算一次，假設$v$偏移0.001，那$J=33 \to 33.003$，$0.003/0.001=3$
2. $\dfrac{dJ}{da}$，當$a$偏移0.001，$v$會變成11.001，$J$則會變成33.003，有發現到這是一個連動性的反應，這就是chain rule，改變$a$的同時，$J$的變化就會是$a$對$v$的變化乘上$v$對$J$的變化，也就是$\dfrac{dJ}{da}=\dfrac{dJ}{dv} \times \dfrac{dv}{da}$，剛才我們已經知道$a$的偏移會讓$v=11 \to 11.001$，$0.001/0.001=1$，因此$\dfrac{dv}{da}=1$，$\dfrac{dJ}{da}=\dfrac{dJ}{dv} \times \dfrac{dv}{da}=3\times 1=3$
3. $\dfrac{dJ}{du}$跟$\dfrac{dJ}{da}$一樣，都是3
4. $\dfrac{dJ}{db}=\dfrac{dJ}{dv} \times \dfrac{dv}{du} \times \dfrac{du}{db}$，所以我們只要知道$\dfrac{du}{db}$就可以知道$\dfrac{dJ}{db}$，計算偏移$b=3 \to 3.001, u=6 \to 6.002$，因此$\dfrac{du}{db}=0.002/0.001=2$，可得$\dfrac{dJ}{db}=3 \times 1 \times 2=6$
5. $\dfrac{dJ}{dc}=\dfrac{dJ}{dv} \times \dfrac{dv}{du} \times \dfrac{du}{dc}$，計算偏移$c=2 \to 2.001, u=6 \to 6.003$，因此$\dfrac{du}{dc}=0.003/0.001=3$，$\dfrac{dJ}{dc}=3 \times 1 \times 3 = 9$
上面的過程就是求導的過程。
## Summary
透過上面兩個案例我們很快速的明白神經網路在做所謂的forward與backward是怎麼一回事，以及如何利用chain rule來做求導(backward)的計算
## Reference
[李宏毅老師_ATDL_Lecture_3: Computational Graph & Backpropagation](https://hackmd.io/@shaoeChen/HJPvpYtO4)
[吳恩達老師_深度學習_神經網路與深度學習_第二週_深度學習基礎_Basics of Neural Network Programming](https://hackmd.io/@shaoeChen/r100n-Mbz)
## Extension
我們已經學過Logistic regression，試著用一樣的方式來求導，先寫下hypothesis：
* $z = wx + b$，計算forward
* $a = \sigma(z)$，經過sigmoid function
* $\mathcal{L}(a,y)$，計算loss，其中$\mathcal{L}(a, y)=-(y\log(a) + (1-y)\log(1-a))$
以graph來表示forward的部份：
```graphviz
digraph graphname {
rankdir=BT;
x1 [label="x1"];
w1 [label="w1"];
x2 [label="x2"];
w2 [label="w2"];
b [label="b"];
z [label="z=wx1+wx2+b"];
a [label="a=Sigmoid(z)"];
L [label="L(a, y)"];
x1 -> z;
w1 -> z;
x2 -> z;
w2 -> z;
b -> z;
z -> a [label="sigmoid function"];
a -> L [label="count loss"];
}
```
forward的部份很簡單，就是特徵與權重(參數)內積之後加上bias，然後經過sigmoid function，計算與real value之間的距離。
現在來看backward怎麼處理：
```graphviz
digraph graphname {
rankdir=TB;
x1 [label="x1"];
w1 [label="w1"];
x2 [label="x2"];
w2 [label="w2"];
b [label="b"];
z [label="z=wx1+wx2+b"];
a [label="a=Sigmoid(z)"];
L [label="L(a, y)"];
L -> a[color="Red"];
a -> z[color="Red"];
z -> b[color="Red"];
z -> w2[color="Red"];
z -> x2[color="Red"];
z -> w1[color="Red"];
z -> x1[color="Red"];
}
```
一樣的，一個一個來推導：
1. 首先我們計算的是$\mathcal{L}$與$a$的偏微分，即$\dfrac{d\mathcal{L}(a, y)}{da}$，可以得到$-\dfrac{y}{a} + \dfrac{1-y}{1-a}$
* 把loss function拆開來看(可參考[上一篇](https://hackmd.io/87etnLf5SEOSON0T2uAiUg?view#Extension_Logistic-Regression-Deriving-the-Gradient-Equation))，$\mathcal{L}(a, y)=-(y\log(a) + (1-y)\log(1-a))$，計算$\dfrac{d\mathcal{L(a,y)}}{da}$，第一個項目，相乘求微分就是左微乘右加上右微乘左，左微是常數，歸零，右徵是對數，對數對導就拉下來就對了，因此第一項就是$-\dfrac{y}{a}$，第二項也是一樣的觀念，因此得到$\dfrac{1-y}{1-a}$
2. 接著計算$\dfrac{d\mathcal{L}}{dz}$，從剛才的練習已經知道，$\dfrac{d\mathcal{L}}{dz}=\dfrac{d\mathcal{L}}{da} \times \dfrac{da}{dz}$，因此我們只要先求到$\dfrac{da}{dz}$就可以，而$\dfrac{da}{dz}$就是計算sigmoid function的微分，這在上一篇已經說過，因此我們可以直接說『我會』，答案就是$\sigma(z) \cdot (1 - \sigma(z))=a(1-a)$，因此，$\dfrac{d\mathcal{L}}{dz}=\dfrac{d\mathcal{L}}{da} \times \dfrac{da}{dz}=(-\dfrac{y}{a} + \dfrac{1-y}{1-a}) \times (a(1-a))=a-y$
3. 計算參數，$\dfrac{d\mathcal{L}}{dw_1}=\dfrac{d\mathcal{L}}{da} \times \dfrac{da}{dz} \times \dfrac{dz}{dw_1}$，一樣的，先求最後一項$\dfrac{dz}{dw_1}$，很明顯，這邊就是$x_1$，其它兩項不相關的$w_2, b$都直接歸0。因此，$\dfrac{d\mathcal{L}}{dw_1}=\dfrac{d\mathcal{L}}{da} \times \dfrac{da}{dz} \times \dfrac{dz}{dw_1}=(a-y)x_1=dz\times x_1$。$w_2$的計算是一樣的，只是$x_1$變$x_2$
4. 計算bias，常數項微分後就是1，因此不用算，就是$dz$，也就是$a-y$
上面四個步驟就是利用Computational Graphs來重新認識Logistic Regression推導過程。其實過程不難理解，需要的就是自己手寫跟靜心理解。你也可以注意到，對於參數在backward的時候的求導有兩個部份，一個是forward來的，一個是backward來的，怎麼說，我們看參數$w_1=x_1 \times dz$，這個$x_1$是input，$dz$則是backward回來的，也就是說，當我們把這個概念泛化到多層神經網路的時候，第三層的參數的更新就是第二層的output，也就是第三層的input再乘上該層backward的結果。
最後，這邊的說明都是單一個資料點的計算過程，當我們以批次概念來看的話，一定都是採用向量化的方式來計算，這邊不多說，因為把一切交給框架就對了。
Sign in with Wallet
Connect another wallet