# CS231N (2017) Lec 04 課程筆記
###### tags: `CV`

🔷 計算圖（Computational Graph）

📌 Recall
Lec 03 提到了兩種分析梯度的方法
(1) 實務上不可行，可做為 debugging tool，慢且不準確的「數值型梯度」（numerical gradient）
(2) 實務上可行，快且準確的「分析型梯度」（analytic gradient）

📌 Today topic
issue: 如何針對任意複雜的函數: 計算其「分析型梯度」
tool: 計算圖（Computational Graph）

📌 計算圖（Computational Graph）
利用多個節點以解釋損失函數的計算過程，每個節點代表一個計算步驟

📌 反向梯度傳播（Backward Propagation）
計算梯度的主要工具，遞迴地: 使用鏈鎖率（chain rule）計算梯度（即: 偏導數）
-------------------------
從終點（箭頭的終點，位於最右側）起算，
逐漸向左移動（逆向或反向傳播）到起點（箭頭的起點，位於最左側）
-------------------------
🔘 計算範例 -1: fig. 6-8
每條線之上的是旁邊節點的函數值，
每條線之上的是旁邊節點的梯度值=偏導數值

🔘 計算範例 -2: fig. 9-11
(1) 對於一張「計算圖」（computational graph），
可先定義所有「計算節點」（computational nodes）
(2) 直接指向（向前傳播到）每個 計算節點 的梯度
可分解為:
「上游梯度」（upstream gradient）
和「局部梯度」（local gradient）

🔘 計算範例 -3: fig. 12-16
f (w, x) = 1 / (1 + e ^ [ - ( w_0 * x_0 + w_1 * x_1 + w_2 ) ] )

這是個比較複雜（計算節點較多）的計算圖
但對應到（指向，向前傳播到）每個節點的 2 個輸出
都可拆解為: 加法 及 乘法 的簡單形式
---
透過 (a) 計算導數 和 (b) 梯度 = 上游梯度 x 局部梯度
便可從最右側的終點
逐個向後（箭頭的反方向，即左側）計算梯度
---
> 詳見 "fig. 12 - 梯度計算過程"

🔘 計算範例 -4: fig. 17
"計算範例 -3" 中的 1 / (1 + e ^ -x) 等效於 Sigmoid 函數: σ(x)
經過以下推導，
我們知道 Sigmoid 函數對 x 的導數可簡化為: [ 1 - σ(x) ] * σ(x)
因此「計算 1 / (1 + e ^ -x) 的梯度」原本需要 4 次運算
可替換為計算這個簡化後的算式: [ 1 - σ(x) ] * σ(x)，只需 1 次運算
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
σ(x) = 1 / (1+e^-x)

d [ σ(x) ] / dx = d [ (1+e^-x)^(-1) ] / dx
= (-1) * (1+e^-x)^(-2) * [0+(-e^-x)]
= e^-x / (1+e^-x)^2
= (1+e^-x-1) * 1 / (1+e^-x)^2
= [ (1+e^-x-1) / (1+e^-x) ] * [ 1 / (1+e^-x) ]
= [ 1 - σ(x) ] * σ(x)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> 詳見 "fig. 12 - 梯度計算過程"

🔘 梯度計算的表示
∂ f / ∂ x = Σ_i (∂ f / ∂ q_i) * (∂ q_i / ∂ x)

📌 向量編碼後的梯度（Gradient for vectorized code）
假設 f 函數有兩輸入: x 和 y，並有一輸出 z
則: 損失函數 L 在 x 方向上的梯度為
∂ L / ∂ x = (∂ L / ∂ z) * (∂ z / ∂ x) ,
其中: (1) ∂ L / ∂ z 為 上游梯度, ∂ z / ∂ x 為 局部梯度
// 與 non-vectorized 無異
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
(2) x, y, z 皆為「向量」而非數值
// 與 non-vectorized 不同
(3) 局部梯度: ∂ z / ∂ x 為「Jacobian 矩陣」
// 與 non-vectorized 不同
// 代表 "z 向量所有元素" 對 "各自對應的 x 向量元素" 的若干個偏導數所構成的矩陣

📌 向量化運算（Vectorized operations）
輸入: 4096 維, 向量
輸出: 4096 維, 向量
函數: f (x) = max (0, x),
對應於: 逐個元素（element-wise, i.e., x）

(1) Jacobian 矩陣的大小
4096 x 4096 ➡️ 對單一訓練樣本
409600 x 409600 ➡️ 對（實際上常見的）多個訓練樣本
此例假設有 100 個樣本／每個 mini-batch
➡️ 41 萬 x 41 萬
= 1677 億個元素（需運算次數）---❌: 實務上不可行
➡️ 考慮「哪個輸入維度」各自會主要影響對應的「哪個輸出維度」
可推知: row 1 → col 1, row 2 → col 2, row 3 → col 3, etc.
輸出會被輸入影響的主要維度，皆位於對角線上
因此，實務上在建立 Jacobian 矩陣時:
(1) 會先計算「對角線元素」
(2) 再填充其它非對角線元素
42:48

(2) 範例
🔘 輸入和節點
f (x, W) = | dot_product( W, X ) | ^2
= Σ_i to n [ (dot_product( W, X )_i) ^2 ]
W: 「權重」輸入值,
函數值為一個 2x2 矩陣,
其值為 [ [ 0.1 0.5 ] [ -0.3 0.8 ] ]

x : 「資料（特徵）」輸入值,
函數值為一個 2x1 向量,
其值為 [ [ 0.2 ] [ 0.4 ] ]

q : 「*」節點的函數,
函數值為一個 2x1 向量,
其中 q = dot_product( W, x ),
其函數值（輸出）為 [ [ 0.22 ] [ 0.26 ] ]

f (q) : 「L2」節點的函數,
函數值為一個常數,
其中 f (q) = | q | ^2 = q_1 ^2 + ... + q_n ^2,
其函數值為 0.116

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

🔘 梯度計算
(a) ∂ f / ∂ q_i
= ∂ ( || q || ^2 ) / ∂ q_i
= 2 * q_i

➡️ ▽_q f = dot (2 , q) （反向傳播的「梯度」和順向傳播「原始數值」的關係式）

➡️ 利用上述的關係式，可計算
對應到 q 函數值（輸出）的梯度：
▽_q f = 2 * [ [ 0.22 ] [ 0.26 ] ]
= [ [ 0.44 ] [ 0.52 ] ]

(b) ∂ f / ∂ W_( i, j )
-------------------------
∂ q_( i ) / ∂ W_( i, j )
= x_( j )

∂ f / ∂ W_( i, j )
= [ ∂ ( || q_( i ) || ^2 ) / ∂ q_( i ) ] * [ ∂ q_( i ) / ∂ W_( i, j ) ]
= 2 * q_( i ) * x_( j )

➡️ ▽_w f = dot ( 2 * q, transpose( x ) )
（反向傳播的「梯度」和順向傳播「原始數值」的關係式）

➡️ 利用上述的關係式，可計算
對應到 w 函數值（輸出）的梯度：
▽_w f = 2 * [ [ 0.22 ] [ 0.26 ] ] * [ 0.2 0.4 ]
= [ [ 0.44 ] [ 0.52 ] ] * [ 0.2 0.4 ] // (2x1) x (1x2) => (2x2)
= [ [ 0.44*0.2 0.44*0.4 ]
[ 0.52*0.2 0.52*0.4 ] ]
= [ [ 0.088 0.176 ]
[ 0.104 0.208 ] ]

// 永遠記得檢查:「變數的梯度」與「變數本身」兩者應「尺寸相同」
// i.e., shape (▽_w f ) = shape(w) = (2, 2) // 2 row x 2 col

(c) ∂ f / ∂ x_( j )
-------------------------
∂ q_( i ) / ∂ x_( j )
= W_( i, j )

∂ f / ∂ x_( j )
= [ ∂ ( || q_( i ) || ^2 ) / ∂ q_( i ) ] * [ ∂ q_( i ) / ∂ x_( j ) ]
= 2 * q_( i ) * W_( i, j )

➡️ ▽_x f = dot ( transpose( w ), 2 * q )
（反向傳播的「梯度」和順向傳播「原始數值」的關係式）

➡️ 利用上述的關係式，可計算
對應到 x 函數值（輸出）的梯度：
▽_x f = transpose(w) * 2 * [ [ 0.22 ] [ 0.26 ] ]
= [ [ 0.1 -0.3 ] [ 0.5 0.8 ] ] * [ [ 0.44 ] [ 0.52 ] ]
= [ [ -0.112 ] [ 0.636 ] ]

// 永遠記得檢查:「變數的梯度」與「變數本身」兩者的「尺寸」應相同
// i.e., shape (▽_x f ) = shape(x) = (2, 1) // 2 row x 1 col

📌 模組化實現: forward/backward API
（略）
Caffe: 快速特嵌入的卷積結構

🔷 神經網路（Neural Network）: 借鏡大腦神經網路的「功能」作為架構，但不包含其「內容」
(1) Before: Linear score function 線性分數函數
f = W x

(2) Now: 2-layer Neural Network 雙層神經網路
f = W_2 * max ( 0, W_1 * x )
or 3-layer Neural Network 三層神經網路
f = W_3 * max ( 0, W_2 * max ( 0, W_1 * x ) )

神經網路 = 階層式堆疊（Hierarchically stack）多個線性層，其中帶有幾個非線性函數（層）
----------------------------------------------------------------
Analog:
「權重矩陣 W」
就像是用來表達輸入數值（express input values）的「模板」（template）
----------------------------------------------------------------
Explanation:
W_1: 與輸入 X 直接相連，因此較依賴於「輸入特徵」
無法有效的廣義化（泛化, generalize）
假設訓練集的「車子類別」只包含紅色車，則黃色車與 W_1 模板的匹配程度較低

W_2: 為一個「加權和」（weighted sum）
相較 W_1，較能有效的廣義化（泛化, generalize）
假設訓練集的「車子類別」只包含紅色車，則黃色車與 W_2 模板的匹配程度較高

// 若能得到類似上述這樣的結果，實務上很有用，
// 代表模型接近輸出層的權重矩陣 W_n 有學習出:
// 「車子」除了「顏色特徵」以外的「其它特徵」
// 且足夠廣義化的模型，在 測試集 或 未知資料 上的穩健性較佳

h: 「分數向量」，代表: 對應到 每個類別模板 的分數
其計算方法在此為線性整流函數 ReLU，即: max ( 0, W_1 * X )
// 註: 「線性整流函數 ReLU」是一個「非線性」函數

(3) Neuron 神經元
🔘 nerve impulse（神經脈衝）: 又稱 spike，來自外部的刺激，可以推動細胞本體前進
➡️ 即: 數值／訊號

🔘 dendrite（樹突）: 「接收」外部神經脈衝，流向細胞本體
➡️ 即: 輸入層

🔘 cell body（細胞本體）: 「整合」外部神經脈衝
➡️ 即: 淨輸入／分數向量

🔘 axon（軸突）: 「傳遞」經整合的刺激訊號到下游的神經元
➡️ 即: 中間層

🔘 presynaptic terminal（突觸前神經元）: 位於下游的神經元
➡️ 即: 輸出層

(4) Activation function 激勵函數
🔘 Sigmoid
➡️ σ ( x ) = 1 / ( 1 + e ^ -x )

🔘 tanh
➡️ tanh ( x )

🔘 ReLU
➡️ max ( 0, x )

🔘 Leaky ReLU
➡️ max ( 0.1 * x, x )

🔘 ELU
➡️ x if x >= 0
α ( e ^ x + 1 ) otherwise

🔘 Maxout
➡️ max ( w_1 * x + b_1, w_2 * x + b_2 )