---
tags: cs231
---
# Lecture 2: Image Classification

## 影像辨識在生活中的應用

1. 車牌辨識
<center>

</center>

2. 路跑的名牌辨識
<center>

</center>

## 肉眼和電腦所認知的影像大不相同
對於電腦而言，圖片就僅僅是一堆數字的矩陣
<center>

</center>

在各個類別裡，只使用一個template去顯示
就會呈現下列這種狀況，而且每張圖片所著重的位置不盡相同
所以一個template是無法去滿足我們現在想實現的事情
<center>

</center>

## 影像辨識的挑戰
1. 不同視角
<center>

</center>

2. 不同明暗度
<center>

</center>

3. 不同動作、位置、顏色、形狀
<center>

</center>

4. 沒拍到全景
<center>

</center>

5. 與背景色相近
<center>

</center>

## 找出目標邊緣(Find edges)來進行分類
<center>

</center>

缺點：需要針對每個類別去建立判斷的規則，且該規則還需要能有分辨各物種差異性的功能。

## 簡單的分類器：K-Nearest Neighbor (KNN)
記住所有訓練集和標籤，再看測試集的影像和訓練集哪幾張長的最像

### 演算法如下：
1）算距離：給定未知物件，計算它與訓練集中的每個物件的距離；
2）找近鄰：圈定距離最近的k個訓練物件，作為未知物件的近鄰；
3）做分類：在這k個近鄰中出線次數最多的類別就是測試物件的預測類別。

訓練過程只是將訓練集給儲存起來，測試的時候就將測試的圖片與所有訓練的圖片進行比較，所以測試的時間會遠高於訓練的時間。

N個sample D個維度
Training 複雜度：O(1)
Predict 複雜度：O(N*D)

訓練快但預測慢，但實際上我們希望預測快，訓練可以久一點沒關係

- k值小意昧著模型較為複雜，且容易over-fitting
- k值太大則會讓模型變得過於簡單。
- 適合使用在<font color=red>維度較低</font>的數據中
### 優點：
1. 簡單
2. 不需要輸入資料的假設
3. 對於異常值不敏感
### 缺點：
1. 計算量大
2. 非常耗時
3. 記憶體空間用量大

## L1 L2

### p-norm
一個向量投影到投影到[0, )範圍內的值。
### L1-norm 曼哈頓距離 manhattan distance
p = 1
曼哈頓距離倚賴座標系統的轉度，而非系統在座標軸上的平移或映射。

### L2-norm 歐式距離 Euclidean distance
p = 2
### 比較
- L1 對異常值較不敏感
- L1 在非稀疏向量上計算效率低

### 結論
- kNN非常耗時
- 只使用L1和L2來進行像素比對是不夠的，這樣圖片會按照背景或是顏色來分類，而不是依照圖片主體的本身。

## 簡單的分類器：線性分類 Linear Classification


- example:


### 問題
| 組別 |<center> 問題 </center>|
|:--------:| -------- |
| 第一組|<center>報告組</center>|
| 第二組| 1. 在做L1, L2的比較時，講師提到如果 vector 中的元素是有意義的，ex. 一個人的feature vector (薪水、工作年資、教育程度...)，用 L1 比較make sense，如果feature vector沒有特別的資訊則不一定要用L1，有點不知道為何這樣說？<br> 2. Why L1-Distance depends on coordinate axes? <br>3.linear classifier的參數b是怎麼選出來的|
| 第三組|1.影片提到在小資料適用Cross validation,但在資料量較大時有沒有其他推薦的方法來檢驗呢？ （35:10左右） <br>2.p64 提到有些資料難用線性分類，如何判斷資料是否適合用linear classifier？ |
| 第四組| 1. kNN各個距離的優缺點（除了L1、L2）<br>2. 可以用什麼搜尋法加速kNN預測的速度|

### 綜合回答

Minkowski distance



L1 norm 傾向於讓模型不重要的參數變成 0，這意味著參數將更加稀疏，而這麼做除了可以讓模型泛化能力更好外，還有額外的 2 個好處：
1. 要儲存的參數較少，減少模型大小與記憶體需求
1. 運算時候的乘法次數較少，增加預測時的速度

L2 norm 傾向於讓參數的值更小，而不是變成 0

## 補充區

### kNN與k-means的比較
|<center>KNN</center>|<center> K-Means</center> |
| -------- | -------- |
| 1. KNN是分類算法<br>2. 監督式學習|1. K-Means是分群算法<br>2. 非監督式學習|
| 沒有前期的訓練過程，<br>屬於memory-based learning|有前期的訓練過程|
| K的含義： 在樣本x中尋找最近的k個點，<br>若k個點鐘類別c佔多數，則判定x為c類別。| K的含義：將樣本點分為k群。|

### KD-Tree
對k維空間中的點進行存儲以便後續的快速搜尋的<font color=red>二叉樹</font>
(如果搜尋的點很少，使用暴力法會比KD-Tree快)
<center>

</center>

若使用KD-Tree時間複雜度為O(DlogN)
不過如果D過高也是會造成維度災難。
<font color=red>適合D小於30的時候</font>

### Ball-Tree
改進KDtree的二叉樹結構，在超球體上分割數據。
雖然在構建數據結構的花費上大過於KD-Tree，
但是在高維的數據上都表現的很高效。