---
# System prepended metadata

title: CS231N (2017) Lec 04 課程筆記
tags: [CV]

---

# 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 )
