2020q3 課程專題 (quiz9)

contributed by < jeremy3951 >

綠色代表延伸問題題目

藍色代表引用文章的話

紅色代表觀念更正

tags: `(2020q3)進階電腦系統理論與實作`

題目1:

延伸問題 :

解釋解釋程式碼運作原理，應補充相關背景知識

1. 解釋解釋程式碼運作原理，應補充相關背景知識

補充相關背景知識

問題 1 : sigmoid function 是對應神經元中的什麼行為 ?
引用參考網站的一段話 :

激活函數模擬神經傳導的運作方式，當輸出神經元接受刺激的總和
經過激活函式的運算大於臨界值時，會傳遞至下一個神經元。

sigmoid function 就是模擬神經元中訊號是否傳遞的機制(開關)

問題 2 : 為什麼要挑 sigmoid 當作 activate function ?
參考資料: Neural Networks (一)

若要模仿神經元中全開全關的模式用一般的 step function 比較好，可是 step function 不可微分不能用 gradient descent 來算梯度。
基於下列原因讓大部分的類神經網路都用 sigmoid function 作為該神經網路的激勵函數 :

Sigmoid 的回傳值是連續且可微分的
與 step function 不同，它的值是漸近

問題 3 : 為什麼要使用 back-propagation ? (跟 gradient descent 有關)

首先要提到 gradient descent :

為何要使用 gradient descent ?
根據台大李宏毅教授的影片中有提到 gradient descent 只要是針對可以微分的 function ，此方法都可以把 funciotn set 中誤差最小的那個 funciton 找出來(局部或全域)
gradient descent 的目的 ?
將 function set 中 loss 最低的 funciotn 找出來
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】淺談梯度下降與實作(上)：為什麼是你

(參考台大李宏毅教授的影片)ML Lecture 7: Backpropagation
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.
神經網路圖如下 :

記憶體配置以及指標指向的記憶體位址 :

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

ret->weight = (double *) ((char *) ret + sizeof(ann_t));
右邊的括號已經寫好了要指向的記憶體位置了，那為什麼需要 (double *)?
(將其拿掉也可以正常執行程式碼)

Ans : 不加也可以，這樣寫是為了方便觀察。

權重初始化 : ann_randomize(ret);




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 加速 :
連續轉離散…

訓練神經網路 :


























    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

延伸問題 :
2. 使用 back-propagation (反向傳遞) 改寫上述程式碼，並探討激勵函數的特性

2.使用 back-propagation (反向傳遞) 改寫上述程式碼，並探討激勵函數的特性

針對此次的類神經網路 (ann_init(3,1,2,1))，總共有 11 個 weights 且 loss function 為 MSE ，若用 gradient descent ，就要把 MSE 對 11個 weights 個別做偏微分。
若想加速運算，可以使用 back-propagation …

ℓ (x, y) = L = {l_{1}, \dots, l_{N}}^{⊤}, l_{n} = - w_{n} [y_{n} \cdot \log σ (x_{n}) + (1 - y_{n}) \cdot \log (1 - σ (x_{n}))],

ℓ (x, y) = {\begin{cases} mean (L), & if reduction = `mean'; \\ sum (L), & if reduction = `sum'. \end{cases}

這次的實作參考的文章 : 專為程式人寫的神經網路導論 (以反傳遞演算法為入門磚)
將要偏微分的函式分別 "拆分成一個個的運算單元"，然後再從結果開始算梯度逆推回去
舉例 :　

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

將 x 拆分成 x、x1、x2 後，再從結果逆推得到各個變數的梯度(d->c->a、b)

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

然後利用剛剛得到的梯度再乘上 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

流程說明 :

input 進入 NN 後透過一系列的前饋計算得到 output
將 loss function 對每個 weight 的偏微分算出來得到 gradient
w[i] -= lr * gradient[i]
再回到第一步…

check :

在 forward 的時候 output 是否一直都是正確的 ?
確認 loss function 的偏微分公式推導是否正確 ?
確認在 backward 的時候梯度是否都計算正確 ?
確認 weight 是否都正確地被更新了 ?

理解到本題是分類問題，用 MSE 來當 loss function 不適合

为什么均方差（MSE）不适合分类问题？
解釋 : 梯度會互相消掉 ! !

用 binary cross entropy 當 loss function 就沒事了嗎？
神經網路(3,1,2,1)本身有什麼問題? ( underfitting )
零基礎自學深度學習：（二）優化神經網路

加深網路就好了嗎 ? (梯度消失問題)
回到前面的疑問，到底是網路深度問題還是 loss function 的問題?
若 loss function 實作沒問題的話，那這題就不是 loss function 選用的問題

實作觀察到的點 :
如果把資料改成5筆以下就可以 train 得出來 (underfitting)

延伸問題 :
3. 引入其他激勵函數，例如 ReLU，並確保針對其特性進行適度初始化

3.引入其他激勵函數，例如 ReLU，並確保針對其特性進行適度初始化

若將原本的程式碼的 sigmoid function 直接改成 ReLU 執行所需要的迴圈數會變得非常多 …

題目2:

1.解釋程式碼運作原理，指出上述實作的缺失並改進

觀察這兩個 function，
solve function 回傳 bool 值
solveSudoku 不回傳值，且在最後一行呼叫 solve
由上述觀察可得知 solve 會一直被呼叫，而 solveSudoku 執行完就結束了
為了先了解該程式的架構，所以先從 solveSudoku 開始解讀 !

函式 solveSudoku 的理解

先看第一個迴圈 :

for (int i = 0; i < 9; ++i)
        m.row[i] = m.col[i] = m.box[i] = ALL_NUMS;

還有定義 :

const uint16_t ALL_NUMS = 0x1FF;

ALL_NUMS 裡面裝著 9 個 1 並且分別賦值給 row 、 col 、 box

第一個二層迴圈 :










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 裡面有什麼數字 !

接下來觀察第二個二層迴圈 :














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 的時候會出錯)

認知修正 : 前面對第 7~9 行的理解不準確應修改為以下
第 7 行的 n 裡面裝的是 trvial 數
第 8、9 行則是把 trvial 數 填進去 board 裡面
第 10 行則是把 trvial 數 寫入 row、col、box 裡面

所以第二個二層迴圈用途是把 trivial 數給填上去而已

在填完所有 trivial 數就要真正解 board 了 (solve function)

函式 solve 的理解

























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)

然後繼續迭代到解出來為止…

缺失 :

column major
遞迴成本大
solveSudoku 有兩個引數用不到

改進 :

換成 row major
把遞迴去掉
縮小範圍

2.重寫不同於上述的程式碼，效能表現應優於上述

原本的程式碼 submit 結果 :

2020q3 課程專題 (quiz9)

tags: (2020q3)進階電腦系統理論與實作

題目1:

1. 解釋解釋程式碼運作原理，應補充相關背景知識

補充相關背景知識

解釋程式碼運作原理

2.使用 back-propagation (反向傳遞) 改寫上述程式碼，並探討激勵函數的特性

3.引入其他激勵函數，例如 ReLU，並確保針對其特性進行適度初始化

題目2:

1.解釋程式碼運作原理，指出上述實作的缺失並改進

函式 solveSudoku 的理解

函式 solve 的理解

tags: `(2020q3)進階電腦系統理論與實作`