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

🔷 影像分類 Image Classification
2:54
https://www.bilibili.com/video/BV1Dx411n7UE/?p=2&spm_id_from=pageDriver

📌 備註-1 > Resources
🔘 TA
Justin Johnson
🔘 Python Numpy Tutorial (with Jupyter and Colab)
https://cs231n.github.io/python-numpy-tutorial/

📌 備註-2 > HW-1:
🔘 K-Nearest Neighbor
🔘 Linear classifiers: SVM, Softmax
🔘 Two-layer neural network
🔘 Image features

📌 A concept: Input & Output
🔘 Input: images (number array) + "labels" (categories)
➡️ labels: A "fixed" set of category labels
➡️ images: For example, the size is 800 x 600 x 3,
representing the height is 800,
the width is 600,
and the depth is 3
(=> 3 channel RGB).

🔘 Output: a "predicted (estimated) label"
for the specific test input image

📌 The Problem & Challenges
🔘 The Problem: Semantic Gap (語意鴻溝)
將 訓練資料集 的 影像 和 標籤 相互對應的困難性
// 「影像」一般表示為一個巨大的「數值矩陣」
// 但這個「數值矩陣」跟「標籤 (語意標籤)」之間的關係
// 對電腦而言似乎無法 "直觀地" 對映
// 這問題稱為 語意鴻溝

🔘 Challenges: Viewpoint variation (視角變化)
▫️ 姿勢改變: 細微的 (subtle) 像素變化
▫️ 鏡頭位置改變: 目標物體的視角變化
// 挑戰: 假設要做 "貓咪辨識"
// 在下列前提之下: (1) 貓的姿勢改變 (2) 鏡頭位置改變 (但貓本身不變)
// (=> Every sinle grid or pixel would be different.)
// 仍能得到 "相同的" 辨識結果 (=> represent as the same cat)
// 才能稱在 Viewpoint variation 具有良好的 "強健性"

🔘 Challenges: Illumination (照明)
// No matter the scene is "dark" or "bright",
// our algorithm need to be robust to that.
// 不論在夕陽下、黑暗的電影場景下 (各種照明條件)，
// 都能辨識出 "貓" 的結果
// 才能稱在 Illumination 具有強健性

🔘 Challenges: Deformation (形變)
// 物體因自身柔軟度 (如: cat | different poses and positions) 或外力導致形變
// 形變前、形變後的不同影像，利用某演算法，能對映同一個預測的語意標籤
// 才能稱在 Deformation 具有強健性

🔘 Challenges: Occlusion (遮蔽)
// 只看到物體的其中一角，仍能得到與完整呈現的物體 "相同" 的辨識結果
// 才能稱在 Occlusion 具有強健性

🔘 Challenges: Background Clutter (背景混亂)
// 在不同的背景之下，針對前景物體的辨識，能得到 "相同" 的辨識結果
// 才能稱在 Background Clutter 具有強健性

🔘 Challenges: Intraclass variation (組內變化)
// 例: 貓咪的組內變化
// 要素 → 形狀, 大小, 顏色, 年齡

📌 Attempts have been made
// i.e., 基於傳統影像處理方法 嘗試解決 影像分類

🔘 API
▫️ classify (input_image)
輸入影像會逐一執行特徵提取的影像處理步驟，
再根據特定規則得到一個「預測標籤」輸出值

🔘 Example: 貓咪辨識 (貓咪分類器)
▫️ 特徵: 耳朵、眼睛、嘴巴、鼻子
▫️ 特徵分析: 邊緣特徵
Hubel & Wiesel 的研究表明: 視覺辨識任務中，
「邊緣特徵」通常很重要
▫️ 傳統影像處理方法 - 「影像分類」: 步驟
(1) Find edges
將 原始影像 提取出 邊緣特徵圖，並做二值化
=> 使: 「邊緣線條」為白色，其它部分皆為黑色
=> 並且邊緣線條若斷掉，能將其補起來

(2) Find corners
- 檢測 (detect): 角點 (corner points)
- 邊界 (boundaries)

(3) Record the exclipit set of rules (記錄明確的規則組合)

(4) Predict

🔘 傳統影像處理方法在「影像分類」的劣勢
廣泛性 (generalization) 差
---------------------------------------
=> 不同種類的物件的規則組合間，特徵差異可能很大
若需對不同種類的物件，以傳統影像處理方法做「影像分類」
需要逐一制定 "特定的" 步驟，以辨識 "特定的" 特徵集合

📌 Data-Driven Approach
🔘 Steps
1. Collect a dataset of images and labels
2. Use Machine Learning to train a classifier
3. Evaluate the classifier on new images

🔘 API
▫️ train (train_images, train_labels)
輸出值: model
▫️ predict (model, test_images)
輸出值: predicted_labels

// 過去的 10 ~ 20 年，電腦視覺研究的主要方法大致奠基於上述概念

🔘 Dataset
▫️ example: CIFAR-10

🔘 Distance Metric
▫️ example: L1 distance = Manhattan distance (曼哈頓距離) = City block distance
➡️ The sum of the absolute values of the pixels
➡️ | x1 - x2 | + | y1 - y2 |
where P1 (x1,y1) and P2 (x2,y2)
➡️ 延伸意義:
L1 距離取決於座標軸 ("Coordinates Dependency")
=> 若座標軸經旋轉，兩點間的 L1 距離會改變
=> 若座標軸「有特殊意義」且有清楚定義或認識
可以採用 L1 距離；否則不要用

▫️ example: L2 distance = Euclidean distance (歐式距離)
➡️ The sum of the absolute values of the pixels
➡️ [ ( x1 - x2 ) ^ 2 + ( y1 - y2 ) ^ 2 ] ^ 0.5
where P1 (x1,y1) and P2 (x2,y2)
➡️ 延伸意義:
L2 距離不取決於座標軸
=> 若座標軸經旋轉，兩點間的 L1 距離不會改變
=> 若不太能區分座標軸之間有何差異或影響
採用 L2 距離比較保險

▫️ Distance Metric 的用途
Distance Metric 不僅可用於 vectors 或 images 間的比較
甚至 (NLP 領域) 兩個段落文字，或兩個句子
皆可指定 Distance Metric 進而計算相似性

▫️ 如何選擇 Distance Metric 及 KNN 中的 K 值 ?
=> Distance Metric、KNN 中的 K 值，稱為「超參數」(hyperparameters)
基本上 "無法" 從訓練資料集中學習得到
=> How to choose hyperpameter in the practice ?
Ans: Depending on the "problem" and the "data",
trying different hyper-parameters,
and finally choose the best.

🔷 KNN Classifier

📌 KNN (K-Nearest Neighbor) Classifier
🔘 Introduction
某個點的「預測標籤」會針對 K 個距離最近的點，採「多數決」方式決定

🔘 KNN 視覺化: 繪製其決策區域 (decision region)
(1) 高維度平面的散佈圖
(2) 對應回資料集的實際影像 (concrete images)
一般使用 KNN 做影像分類，會將上述兩種方式來回/交替使用

📌 設定超參數: 拆分資料集 (train, val, test)

Problem: How to choose the hyperparemeters?

(1) Idea 1: 不拆分資料集 (皆為訓練資料)
>> 取 perforamce 或 accuracy 表現最好的超參數 --- ( ❌ )
🔘 永遠不建議採用此方法
🔘 原因: 會 Overfitting, KNN 分類器選到的總會是 K = 1 (殘差最小, 最佳擬合)
🔘 即: 「以『訓練資料』的表現作為評估超參數的依據」
會導致: 訓練資料外的資料「無從評估」
因此選擇出的超參數不能推廣、泛化到非訓練資料

(2) Idea 2: 拆分資料集為 train、test 兩堆
>> 取在 test data 上，perforamce 或 accuracy 表現最好的超參數 --- ( ❌ )
🔘 永遠不建議採用此方法
🔘 原因: 每個 test data 用來評估超參數後，test data 會失去代表性
🔘 即: 「以『測試資料』的表現作為評估超參數的依據」
會導致: 測試資料外的資料「無從評估」
因此選擇出的超參數不能推廣、泛化到非測試資料

(3) Idea 3: 拆分資料集為 train、test、validation 三堆
>> 取在 test data 上，perforamce 或 accuracy 表現最好的超參數 --- ( ⭕ )
🔘 建議採用此方法
🔘 做法:
Step 1. 採用「不同的超參數」，以「訓練集」訓練模型
Step 2. 選擇在「驗證集」表現最佳的超參數
Step 3. 最後在「測試集」上以 Step 2. 選擇的超參數跑一次
// 通常測試集是「最後跑的」
// 測試集被視為 unseen data，論文的最終資料也只列出測試集結果
//
// 測試資料的順位放在 "最後" 並且 "只跑一次" 很重要！
// 確保沒有洩漏「測試資料」(偷看答案) 進而對模型或超參數作弊

(4) Cross Validation 交叉驗證
也可用來設定超參數
常用於小型資料集
但大型資料集的深度學習較不常用 (因為計算量較大，計算成本較昂貴)
--------
做法:
(以 5-fold 為例)
總共執行五輪：
每一輪取其中一個 fold 與其它四個 folds 比較
>> 可決定一個最佳的 fold，將最佳 fold 設定為 validation set
>> 拆分 train, val, test 資料集

(5) 問題: training set 和 validation set 的最大差異 ?
training set ➡️ 分類器中，用來 "記憶"「標籤 (Y)」與 影像特徵 (X) 間對應關係的資料集
validation set ➡️ 分類器中，用來選擇「超參數」的資料集
➡️ 與 training set 最大差異是:
標籤 在 validation set 中並非用來更新權重 (最佳化目標函數)
而是單純用來選擇表現更好的超參數

(6) 問題: test set 的資料是否可能不夠具有代表性，
造成在 test set 表現好、但在 data in the wild 表現差？
Ans: 實務上有可能，主要是資料的問題 (責任來自 data collector)
而 test set 對於 unseen data 有代表性的前提是:
(1) dataset 服從 "獨立且相同分佈" (i.i.d.)
(2) dataset 來自 "隨機抽樣"
// 可能會因為蒐集資料的時間順序不同
// 導致如: 較早的資料多數分佈在 training set、較晚的資料多數分佈在 test set
// 這樣可能影響 "隨機性"
// => 減輕上述影響的一種策略:
// Make sure the partition (拆分) is random of your entire set of data points

📌 設定超參數: K - Cross Validation Acc 圖表
(1) 水平軸: K
繪製分割線 => range(-20, 140, 20)
(2) 垂直軸: Cross Validation Accuracy
(3) 5-fold cross validation:
對於每個 K 值，都在五個相異的 validation folds 各自執行

📌 KNN on images "never used"
(1) 測試時間 (test time) 非常慢
(2) 像素間的 distance metrics 資訊量不充足 (not informative)
➡️ 感知距離 (perceptual similarity) 是更好的方法
// 但投影片講授的範例使用 L1 (city block) 距離、歐式距離
// 這兩種 distance metric 不太適合用來描述兩張影像的相似性
(3) 維度詛咒 (the curse of dimensionality)
// 主要是說明 KNN 的基礎架構 在資料分佈上沒有包含太多假設,
// 因此對高維度資料使用 KNN 分類, 可能因為 高維資料的分佈不理想 導致效果不彰

➡️ 1. 訓練樣本點之間距離太遠
>> 樣本資料點無法密集覆蓋樣本空間
>> KNN 抓的測試資料(相近的鄰居) 與 input img 實際上不相似
➡️ 2. 嘗試著蒐集 "大量樣本": 試圖讓樣本資料點密集覆蓋樣本空間
>> 在低維度所需樣本數還不大, 但高維空間的所需樣本數隨維度增加，呈 "指數型上升"

// => 可能的改善方法: 對訓練資料分佈做些調整 (如: curved shape)

📌 KNN: Summary
(1) 訓練集 (training set) ➡️ 利用 "大量影像" 和 "大量標籤" 訓練模型
測試集 (test set) ➡️ 用於 "預測出一個標籤"
(2) 「預測」主要基於 "最相近的幾個訓練樣本"
(3) 超參數: (a) K (b) distance metric
(4) 驗證集 (validation set) ➡️ 用於選擇超參數

🔷 Linear Classification
// 前面介紹的 KNN 分類器保留原始 "訓練資料 X"
而此處介紹的 線性分類器 最大的不同是多了 "權重 W"
=> 優勢: "測試階段" 只需「載入權重」即可 預測，省下空間、可在行動裝置執行

📌 Parametric Appraoch: Linear Classification
(1) input
🔘 X
🔘 shape
Array of "32 x 32 x 3" numbers
( 3072 numbers total )
🔘 classes
10 classes

(2) operation
🔘 f ( X , W )
🔘 shape of f ( X , W ) : "10 x 1"
🔘 denotes:
W : weight (權重，如: 一個數值矩陣)
// W 有時會用 θ 代替，取決於不同文獻的符號表示
X: input data (輸入資料，如: 一個數值向量，代表: 經平坦化的像素強度數值)
b: bias (偏誤，如: 一個常數構成的數值向量)
f : output (輸出，如: 一個數值向量，代表: 各類別的預測機率值)
🔘 functional form:
f ( X , W ) = W X + b
➡️ shape of f : 30 x 1
➡️ shape of W : 30 x 3072
➡️ shape of X : 3072 x 1
➡️ shape of b : 30 x 1
🔘 analog:
1. 輸出預測標籤 通常是一個 行向量 (column vector)
2. 「權重」通常是一個矩陣，扮演關鍵角色
3. 線性分類器 的 數值運算: W X + b 就類似傳統影像處理中的「模板匹配」:
權重矩陣 的每一列 (row) 可看作一個「模板」
(過程: 模板與原始影像的對應元素相乘後，加上偏誤向量的對應元素)
最後「輸出」向量中每一列的元素，代表屬於某類別的機率，與特定「模板」對應
// 實際上可以把每一列數值做視覺化
4. 「與特定『模板』對應」:
指的是「單一類別」只對權重矩陣中對應的「一個模板」進行學習
// 模板視覺化後，看起來像個模糊化的輪廓圖
// ➡️ 更複雜的模型可允許單一類別對超過一個模板進行學習，
// 這裡的線性分類器只針對一個模板

(3) output
🔘 10 x 1 number array
= 10 numbers giving class scores (probabilities)

📌 Hard cases for a linear classifier
e.g.1 左圖
如: 計算物體出現數量是奇數或偶數，可能會有左圖的資料分佈
那麼使用單純的線性分類器，失敗機率很高，因為很難用一條直線 (作為決策邊界) 分成兩區

e.g.2 右圖
即 Multi-modal Situation，多峰資料 (multimodal data) 分佈在不同區域，就很難用一條直線區分

📌 Linear Classifier
優勢: 易於解釋 (interpret)、易於理解
劣勢: 資料分佈比較奇怪：難以用一條直線區分的資料