# Prototypical Networks for Few-shot Learning
###### tags: `AI`

## Reference
* [小樣本學習（Few-shot Learning）綜述](http://www.ipshop.xyz/12632.html)
* [原形網絡（Prototypical Networks）](https://www.twblogs.net/a/5c25df85bd9eee16b3db81c1)

[論文連結 NIPS 2017](https://papers.nips.cc/paper/6996-prototypical-networks-for-few-shot-learning.pdf)
{%pdf https://papers.nips.cc/paper/6996-prototypical-networks-for-few-shot-learning.pdf%}

## 摘要重點
* Prototypical Networks使用神經網絡訓練embedding函數，並基於變換空間中的歐式距離優化softmax。
* 將每個類別中的樣例數據通過一個embedding函數映射到一個空間當中，並且提取他們的“均值”來表示爲該類的原形（prototype），所以會為每個類別都計算出一個Prototype($c_k$)。
* 距離函數是使用歐幾里得距離，訓練使得本類別數據到本類原形表示的距離爲最近，到其他類原形表示的距離較遠。訓練過程中的評估方法，是對query到各個類別的$c_k$距離做softmax，來判斷query的類別標籤。
* 損失函數: query到$c_k$距離的最小化，藉此訓練一個好的embedding，讓同一類可以距離最近。
* 訓練的episode是隨機從訓練集中選擇的一個類子集，從這些類子集中選擇一些樣例數據作爲支持（support set）集，其剩餘的作爲查詢（query set）集。即可從每個episode的不同類子集中學習few-shot task。

:::info
**Few-shot Learning** 是 Meta Learning 在監督學習領域的應用。Meta Learning，又稱為 learning to learn，在 meta training 階段將資料集分解為不同的 meta task，去學習類別變化的情況下模型的泛化能力，在 meta testing 階段，面對**全新的類別**，不需要變動已有的模型，就可以完成分類。

形式化來說，few-shot 的訓練集中包含了很多的類別，每個類別中有多個樣本。在訓練階段，會在訓練集中隨機抽取 C 個類別，每個類別 K 個樣本（總共 CK 個資料），構建一個 meta-task，作為模型的支撐集（support set）輸入；再從這 C 個類中剩餘的資料中抽取一批（batch）樣本作為模型的預測物件（batch set）。即要求模型從 CK 個資料中學會如何區分這 C 個類別，這樣的任務被稱為 **C-way K-shot** 問題。

訓練過程中，每次訓練（episode）都會採樣得到不同 meta-task，所以總體來看，訓練包含了不同的類別組合，這種機制使得模型學會不同 meta-task 中的共性部分，比如如何提取重要特征及比較樣本相似等，忘掉 meta-task 中 task 相關部分。通過這種學習機制學到的模型，在面對新的未見過的 meta-task 時，也能較好地進行分類。

Few-shot Learning 模型大致可分為三類：
1. Model Based: 通過模型結構的設計快速在少量樣本上更新引數
2. **Metric Based (本論文)**: 通過度量 batch 集中的樣本和 support 集中樣本的距離，借助最近鄰的思想完成分類
3. Optimization Based: 通過調整優化方法來完成小樣本分類的任務
:::

## Prototypical Networks
:::info
*[Bregman divergence (布雷格曼散度)](https://www.zhihu.com/question/22426561)*
如果你抽象地定义一种在特定空间里两个点之间的“距离”，然后在这些点满足任意的概率分布的情况下，这些点的平均值点（mean point）一定是空间中距离这些点的平均距离最小的点（这是一个很正常的我们希望对“距离”的定义吧）
:::

### Notation
給定一個support set，包含N個已經標記的資料。$S=\{(x_1, y_1), ..., (x_N, y_N)\}$，其中$x_i$為D-dimentional的特徵向量，以及$y_i\in\{1, ..., K\}$的其中一種類別。$S_k$表示成標記成類別k的資料集。

### Model
#### embedding function
首先，Prototypical Networks透過訓練embedding function parameters，得到$f_\theta: R^D \rightarrow R^M$。每個類別的 **Prototype($c_k$)** 就是透過計算$S_k$所有資料的$f_\theta$加總取平均，所以$c_k \in R^M$。
$$c_k = \frac{1}{|S_k|} {\sum_{(x_i, y_i)\in S_k}} f_\theta(x_i)$$

#### distance function
計算query point到各個prototypes的距離，並進行softmax形成各類的機率分布。

$$p_\theta(y=k|x)=\frac{exp(-d(f_\theta(x), c_k))}{\sum_{k'}exp(-d(f_\theta(x), c_{k'})}$$

#### learning process
學習方式是通過SGD對正確類別k，進行negative log-probability $J(\theta)=-\log p_\theta (y=k|x)$最小化。

**Training episode**
隨機從訓練資料集裡抽取**C-way K-shot**的support set，並對抽取的類別的剩餘的資料中抽取query set，進行one episode訓練，其中主要包含兩個主要的步驟:

（1） 對episode中的每個類別都計算出一個原形$c_k$，其$c_k$的計算是對該類中的所有支持數據的向量化表示取均值求得。

（2）優化類別中剩餘的query點到原形的距離來訓練模型。


**Inference**
訓練好embedding後，若是新類別則需要另外丟入support set & query，透過support set計算原形，並對待分類的query透過歐式距離進行分類。否則，直接計算待分類的embedding到各類別的原形距離，最短距離即分類結果。

### Design Choices
#### Distance metric
使用squared Euclidean distance可以大幅改善使用cosine distance的效果，猜測是cosine distance不屬於Bregman divergence。

#### Episode composition
訓練和測試使用相同的類別數量(way)和各類別資料量(shot)較為合適，但也發現當訓練時使用更多的way可以訓練得更好，而shot使用相同數量較合適。

### Zero-Shot Learning
Zero-Shot Learning不同之處在於訓練各類別的meta-data(如從文本學習、屬性描述)，而不是給定由訓練點組成的support set。而Prototypical Networks透過另外的meta-data vector，只有將$c_k$的計算方式變成根據每個類別的meta-data vector進行計算。
> Since the meta-data vector and query point come from different input domains, we found it was helpful empirically to fix the prototype embedding g to have unit length, however we do not constrain the query embedding f.

## Experiments
few-shot learning: 使用資料集包含Omniglot、miniImageNet
zero-shot learning: 使用資料集包含CUB-200 2011

## Dataset
### Omniglot Few-shot Classification
28x28的灰階圖片，包含來自50個不同字母的1623個不同手寫字符。每一個字符都是由20個不同的人繪製的。將1623個不同手寫字符，其中1200種+以90度為旋轉倍數進行augumentation，一共有4800 classes作為訓練資料。剩下的包含旋轉作為測試資料。

#### embedding architecture
由四個convolutional blocks組成，每個block包括一個64-filter 3 × 3 convolution、batch normalization layer、一個 ReLU nonlinearity、一個 2 × 2 max-pooling layer。support和query都是使用相同的embedding進行編碼。

使用 Euclidean distance 訓練Prototypical Networks，包含1-shot和5-shot的情況，其中包含60 classes和5 query per class。



### miniImageNet Few-shot Classification
84x84的彩色圖片，包含100個類別，每個類別中包含600個樣本數據。

#### embedding architecture
使用和Omniglot實驗一樣的架構，唯一不同的是輸入的影像大小不同。

訓練包含30-way episodes for 1-shot classification、20-way episodes for 5-shot classification，以及每個類別皆包含15 query points per episode.


* 20-way優於5-way，猜測是20-way更難所以可以讓模型更泛化
* 使用Euclidean distance優於cosine distance，猜測是cosine distance不屬於Bregman divergence


### CUB Zero-shot Classification
CUB數據集包含200種鳥類的11,788張圖像。這裡資料切分成訓練集包含100個類別，驗證集包含50個類別，測試集包含50個類別。訓練episode的類別爲50，每個類別的查詢點爲10個。

#### images
For images we use 1,024-dimensional features extracted by applying GoogLeNet to middle, upper left, upper right, lower left, and lower right crops of the original and horizontally-flipped image. (Features downloaded from https://github.com/reedscot/cvpr2016.)

#### class meta-data
模型對鳥類的多種屬性進行編碼，如顏色、羽毛、形狀等屬性，得到312-dimensional continuous attribute vectors。

We learned a simple linear mapping on top of both the 1024-dimensional image features and the 312-dimensional attribute vectors to produce a 1,024-dimensional output space.

For this dataset we found it helpful to normalize the class prototypes (embedded attribute vectors) to be of unit length, since the attribute vectors come from a different domain than the images.

Training episodes were constructed with 50 classes and 10 query images per class.