2020q3 課程專題 (quiz9)
===
contributed by < `jeremy3951` >
:::success
綠色代表延伸問題題目
:::
:::info
藍色代表引用文章的話
:::
:::danger
紅色代表觀念更正
:::
###### tags: `(2020q3)進階電腦系統理論與實作`
# 題目1:
:::success
延伸問題 :
1. 解釋解釋程式碼運作原理，應補充相關背景知識
:::
## 1. 解釋解釋程式碼運作原理，應補充相關背景知識
### 補充相關背景知識
__問題 1 : sigmoid function 是對應神經元中的什麼行為 ?__
引用[參考網站](https://zrn-coding.github.io/2020/03/21/AI-2/)的一段話 :
:::info
激活函數模擬神經傳導的運作方式，當輸出神經元接受刺激的總和
經過激活函式的運算大於臨界值時，會傳遞至下一個神經元。
:::
sigmoid function 就是模擬神經元中訊號是否傳遞的機制(開關)
__問題 2 : 為什麼要挑 sigmoid 當作 activate function ?__
參考資料: [Neural Networks (一)](https://chtseng.wordpress.com/2017/07/24/neural-networks-%E4%B8%80/)
若要模仿神經元中全開全關的模式用一般的 step function 比較好，可是 step function 不可微分不能用 gradient descent 來算梯度。
基於下列原因讓大部分的類神經網路都用 sigmoid function 作為該神經網路的激勵函數 :
1. Sigmoid 的回傳值是連續且可微分的
2. 與 step function 不同，它的值是漸近
__問題 3 : 為什麼要使用 back-propagation ?__ (跟 gradient descent 有關)
首先要提到 gradient descent :
1. 為何要使用 gradient descent ?
根據台大李宏毅教授的[影片](https://www.youtube.com/watch?v=fegAeph9UaA)中有提到 gradient descent 只要是針對可以微分的 function ，此方法都可以把 funciotn set 中誤差最小的那個 funciton 找出來(局部或全域)
2. gradient descent 的目的 ?
將 function set 中 loss 最低的 funciotn 找出來
3. gradient descent 怎麼做 ?
假設一 loss function , L(w)，w 是一個 function set 裡面的 function ，現在要求 L(w) 的最小值。
在這種情況下需要一個參數叫做 learning rate ，有了 learning rate 後就可以把它跟 $\partial L(w)/\partial w$ 相乘，$\partial L(w)/\partial w$ 為梯度，利用 learning rate 不斷去更新梯度最後得到最小值
(參考)[【Python】淺談梯度下降與實作(上)：為什麼是你](https://dotblogs.com.tw/shaynling/2019/09/10/142936)
(參考台大李宏毅教授的影片)[ML Lecture 7: Backpropagation](https://www.youtube.com/watch?v=ibJpTrp5mcE&t=1279s)
backpropagation 利用 chain rule 加速 gradient descent 的運算，提升神經網路的學習速度
### 解釋程式碼運作原理
__初始化神經網路__ : `ann_init`
ann_init(3,1,2,1) : New network with 3 inputs, 1 hidden layer of 2 neurons , and 1 output.
神經網路圖如下 :
```graphviz
digraph a{
rankdir = "LR"
node[shape = circle]
A
B
C
D
E
F
A->D
A->E
B->D
B->E
C->D
C->E
D->F
E->F
}
```
記憶體配置以及指標指向的記憶體位址 :
`ret->weight = (double *) ((char *) ret + sizeof(ann_t));`
右邊的括號已經寫好了要指向的記憶體位置了，那為什麼需要 (double *)?
(將其拿掉也可以正常執行程式碼)
Ans : 不加也可以，這樣寫是為了方便觀察。
權重初始化 : `ann_randomize(ret);`
```cpp=
void ann_randomize(ann_t *ctx) {
for (int i = 0; i < ctx->total_weights; ++i)
ctx->weight[i] = ANN_RAND() - 0.5; /* weights from -0.5 to 0.5 */
}
```
total_weight 裡面不只有神經元運算需要的 weight ，連運算完要加上的 bias 也順便放在這個變數裡面了 (`double sum = *w++ * (-1.0);`就是先算 bias)
探討 activation 加速 :
連續轉離散...
__訓練神經網路__ :
```cpp=
do {
++count;
if (count % LOOP_MAX == 0) {
ann_randomize(ctx);
last_err = LOOP_MAX;
}
ann_t *save = ann_copy(ctx);
/* Take a random guess at the ANN weights. */
for (int i = 0; i < ctx->total_weights; ++i)
ctx->weight[i] += RRR;
err = 0;
for (int k = 0; k < (1 << 3); k++)
err += pow(*ann_run(ctx, input[k]) - output[k], 2.0);
/* Keep these weights if they're an improvement. */
if (err < last_err) {
ann_free(save);
last_err = err;
} else {
ann_free(ctx);
ctx = save;
}
} while (err > 0.01);
```
第 3~6 行設定執行次數 ，次數內沒完成任務就重來
第 11~12 初始化權重
第 15~16 計算 error
第 19~24 行 => ( 當下 model 是否為 best model )? 保存 : 棄掉
該神經網路透過將權重隨機更新並且計算 error 來保留最佳 model
:::success
延伸問題 :
2. 使用 back-propagation (反向傳遞) 改寫上述程式碼，並探討激勵函數的特性
:::
## 2.使用 back-propagation (反向傳遞) 改寫上述程式碼，並探討激勵函數的特性
針對此次的類神經網路 (ann_init(3,1,2,1))，總共有 11 個 weights 且 loss function 為 MSE ， 若用 gradient descent ，就要把 MSE 對 11個 weights 個別做偏微分。
若想加速運算，可以使用 back-propagation ...
$\ell(x, y) = L = \{l_1,\dots,l_N\}^\top, \quad
l_n = - w_n \left[ y_n \cdot \log \sigma(x_n)
+ (1 - y_n) \cdot \log (1 - \sigma(x_n)) \right],$
$\ell(x, y) = \begin{cases}
\operatorname{mean}(L), & \text{if reduction} = \text{`mean';}\\
\operatorname{sum}(L), & \text{if reduction} = \text{`sum'.}
\end{cases}$
這次的實作參考的文章 : [專為程式人寫的神經網路導論 (以反傳遞演算法為入門磚)](https://www.slideshare.net/ccckmit/ss-93434977)
將要偏微分的函式分別 __"拆分成一個個的運算單元"__，然後再從結果開始算梯度逆推回去
舉例 :
將 x 拆分成 x、x1、x2 後，再從結果逆推得到各個變數的梯度(d->c->a、b)
然後利用剛剛得到的梯度再乘上 learning rate 來更新權重。
回到題目，
本次要更新的權重有 11 個，所以在算 bp 的時候，只要算這 11 個和 output 的梯度再不斷的更新權重就可以了。
初步結果 :
網路架構如同此次題目 ann_init(3,1,2,1)
input = { 1 , 0 , 1 } ， output = 1.0 ， train 50 次
w11 是 output ， learning rate = 0.01，可以看到經過 R1 後 output 從 0.48 變成 0.49 ，更接近 output(=1) 了，不過 learning rate 太小所以更新的幅度就會比較小，
透過調整 lr 成 0.1 :
很明顯地更接近 output 了
__但是!!__
如果將 input 多組放入神經網路用上述的方式 training 會很難 train
train 完 10000個 epoch 值依然還差很遠...
後來我試著把此神經網路當作分類問題， output 因為 sigmoid function 的關係值域在 0 到 1 之間，我讓 output >=0.5 就變成 1 反之變成 0。
雖然過了 1000 epoch 還是沒能訓練完畢，感覺繼續訓練下去就能 train 出來了
實作結果 :
當初以為再多幾個 epoch 訓練就能得到正確解答了。不過，事情出乎我意料之外，我就算訓練 40 萬個 epoch 也訓練不出正確解答...
可能的原因 :
在 training 的過程中每組 input 得到的 output 值都很接近，但是每組 input 對應的答案卻是截然不同的 (0 和 1)，當某個 predict 錯誤而導致梯度算出來後正準備要更新 weight 的時候，其他的 weight 也會因為這個 gradient 變動而跟著更新，這也導致有些原本是對的 output 因為別組答錯，它也更著被更新，原本就答對了，更新完後又錯了，一直這樣循環下去，所以才遲遲訓練不出精準的答案
程式碼如下 :
https://github.com/jeremy3951/NeronNetwork/blob/main/bp-2
流程說明 :
1. input 進入 NN 後透過一系列的前饋計算得到 output
2. 將 loss function 對每個 weight 的偏微分算出來得到 gradient
3. w[i] -= lr * gradient[i]
4. 再回到第一步...
check :
- [x] 在 forward 的時候 output 是否一直都是正確的 ?
- [x] 確認 loss function 的偏微分公式推導是否正確 ?
- [x] 確認在 backward 的時候梯度是否都計算正確 ?
- [x] 確認 weight 是否都正確地被更新了 ?
理解到本題是分類問題，用 MSE 來當 loss function 不適合
[为什么均方差（MSE）不适合分类问题？](https://blog.csdn.net/weixin_41888969/article/details/89450163)
解釋 : 梯度會互相消掉 ! !
用 binary cross entropy 當 loss function 就沒事了嗎？
神經網路(3,1,2,1)本身有什麼問題? ( underfitting )
[零基礎自學深度學習 ：（二）優化神經網路](https://medium.com/@evan_hsiao/%E9%9B%B6%E5%9F%BA%E7%A4%8E%E8%87%AA%E5%AD%B8%E6%B7%B1%E5%BA%A6%E5%AD%B8%E7%BF%92-%E4%BA%8C-%E5%84%AA%E5%8C%96%E7%A5%9E%E7%B6%93%E7%B6%B2%E8%B7%AF-d2c71b5df7e5)
加深網路就好了嗎 ? (梯度消失問題)
回到前面的疑問，到底是網路深度問題還是 loss function 的問題?
若 loss function 實作沒問題的話，那這題就不是 loss function 選用的問題
實作觀察到的點 :
如果把資料改成5筆以下就可以 train 得出來 (underfitting)
:::success
延伸問題 :
3. 引入其他激勵函數，例如 ReLU，並確保針對其特性進行適度初始化
:::
## 3.引入其他激勵函數，例如 ReLU，並確保針對其特性進行適度初始化
若將原本的程式碼的 sigmoid function 直接改成 ReLU 執行所需要的迴圈數會變得非常多 ...
# 題目2:
## 1.解釋程式碼運作原理，指出上述實作的缺失並改進
觀察這兩個 function，
solve function 回傳 bool 值
solveSudoku 不回傳值，且在最後一行呼叫 solve
由上述觀察可得知 solve 會一直被呼叫，而 solveSudoku 執行完就結束了
為了先了解該程式的架構，所以先從 solveSudoku 開始解讀 !
### 函式 solveSudoku 的理解
先看第一個迴圈 :
```cpp
for (int i = 0; i < 9; ++i)
m.row[i] = m.col[i] = m.box[i] = ALL_NUMS;
```
還有定義 :
```cpp
const uint16_t ALL_NUMS = 0x1FF;
```
ALL_NUMS 裡面裝著 9 個 1 並且分別賦值給 row 、 col 、 box
第一個二層迴圈 :
```cpp=
for (int y = 0; y < 9; ++y) {
for (int x = 0; x < 9; ++x) {
if (board[y][x] != '.') {
int n = board[y][x] - '1';
uint16_t k = ~(1U << n);
m.row[x] &= k, m.col[y] &= k, m.box[bi(x, y)] &= k;
}
}
}
```
觀察這個迴圈裡面的操作，第 4、5、6 行一起看 :
board 裡面的字元減掉 '1' 得到這個字元所代表的數字，然後將這個數字用 bitwise 的方式來表示 (9個都是1的bits中，把該數字的位置改成0)
然後將此 k 值分別寫入 row 、 col 、 box 中
__執行完第一個二層迴圈後可以知道每個 row、column、box 裡面有什麼數字 !__
接下來觀察第二個二層迴圈 :
```cpp=
for (int y = 0; y < 9; ++y) {
for (int x = 0; x < 9; ++x) {
if (board[y][x] != '.')
continue;
uint16_t mask = m.row[x] & m.col[y] & m.box[bi(x, y)];
if ((mask & (MMM)) == 0) {
size_t n = __builtin_ctz(mask);
uint16_t k = ~(1U << n);
board[y][x] = '1' + n;
m.row[x] &= k, m.col[y] &= k, m.box[bi(x, y)] &= k;
}
}
}
```
由第 3 、 4 行可以知道這個二層迴圈是針對空白的格子。
接下來的第 5 行用畫圖比較好理解，
|.|1|2|
|-|-|-|
|3|4|5|
|7|8|9|
假設 (x,y)=(0,0)
`mask = row[0]&col[0]&box[0]` 此行蒐集了 row[0]、col[0]、box[0] 裡面的所有數字，也就是說 __mask 裡面的數字是空格不能填的數字!__
接下來先跳過 if 的條件敘述看裡面的程式行為 :
第 7 行的 n 裡面裝的是 __空格可以填的最小數字!__
第 8、9 行則是把最小數字填進去 board 裡面
第 10 行則是把這個最小數字寫入 row、col、box 裡面
後來回頭想了一下，如果照我上面說的，每個空格都用可以填的最小數字來填，那這個數獨填到一半就填不下去了!
後來我發現，數獨只有一種狀況不用分析就可以直接填數字進去，那就是只剩一個數字還沒填的時候! __為了方便我簡稱為 trivial 數__
```
trivial 數舉例 :
|.|1|2|
|3|4|5|
|7|8|9|
or
|.|1|2|3|4|5|7|8|9|
此時 trival 數為 6 (只剩一個可以填)
```
已知 mask 裡面放著空格不能填的數字，如果這個空格有 trvial 數，則 mask 裡面的 bits 只有一個 bit 是 1 !
所以 if 裡面的 MMM 應該要填 __( e ) mask - 1__
(選項 b 在 mask = 00...01 的時候會出錯)
:::danger
認知修正 : 前面對第 7~9 行的理解不準確應修改為以下
第 7 行的 n 裡面裝的是 __trvial 數__
第 8、9 行則是把 __trvial 數__ 填進去 board 裡面
第 10 行則是把 __trvial 數__ 寫入 row、col、box 裡面
:::
__所以第二個二層迴圈用途是把 trivial 數給填上去而已__
在填完所有 trivial 數就要真正解 board 了 (solve function)
### 函式 solve 的理解
```cpp=
static bool solve(char **board, masks_t *m)
{
for (int y = 0; y < 9; ++y) {
for (int x = 0; x < 9; ++x) {
if (board[y][x] != '.')
continue;
int b = bi(x, y);
uint16_t posmoves = m->row[x] & m->col[y] & m->box[b];
while (posmoves) {
size_t n = __builtin_ctz(posmoves);
uint16_t k = ~(1U << n);
board[y][x] = '1' + n;
m->row[x] &= k, m->col[y] &= k, m->box[b] &= k;
if (solve(board, m))
return true;
m->row[x] |= ~k, m->col[y] |= ~k, m->box[b] |= ~k;
posmoves &= MOVE;
}
board[y][x] = '.';
return false;
}
}
return true;
}
```
solve 的引數有 :
board : input
masks_t : 每(行、列、box)裡面已有的數字，用 bitwise 的方式表示，0代表空格不能填的數字，1代表空格可以填的數字
第 9 行的 posmoves 裡面裝著該空格可以填的數字
由第 10、20、21 行的行為(當 posmoves == 0 時，把該空格歸零，並且回傳錯誤)可以得知當 posmoves == 0 時， __一定有其他格子填錯!__
第 11、12、13 這個形式前面有分析過了，其程式行為就是 __"把能填的數字中最小的數字填進 board 中"__
第 14 行把已填的數字放進 board 中
第 15、16 行繼續迭代下去來看看這次的數字是否填錯
第 17 行代表該數字填錯了，把 m 還原成填此數字前的狀態
第 18 行，如果執行到此行，代表當下的填字造成後面填字錯誤
舉例 : (狀態為填完2後準備往下填)(填字順序為 2->3->4->5->6)
|.|6(guess)|5(g)|4(g)|3(g)|2(g)|7(input)|8(in)|9(in)|
|-|-|-|-|-|-|-|-|-|
|1(input)|
空格(0,0) ，此時 posmoves = 000000000 ,
`posmoves &= posmoves-1` , posmoves = 0, return false
-> 空格 (0,1) ，此時 posmoves = 000100000 ,
`posmoves &= posmoves-1` , posmoves = 0 , return false
-> 空格 (0,2) ，此時 posmoves = 000110000 ,
`posmoves &= posmoves-1` , posmoves = 000100000 , __posmoves != 0 , 換個值填入繼續迭代下去 !__
此時狀態為 :
|.|.|6(new)|4(g)|3(g)|2(g)|7(input)|8(in)|9(in)|
|-|-|-|-|-|-|-|-|-|
|1(input)|
然後繼續迭代到解出來為止...
缺失 :
1. column major
2. 遞迴成本大
3. solveSudoku 有兩個引數用不到
改進 :
1. 換成 row major
2. 把遞迴去掉
3. 縮小範圍
:::success
2.重寫不同於上述的程式碼，效能表現應優於上述
:::
原本的程式碼 submit 結果 :
Sign in with Wallet
Connect another wallet