# Deep Metric Learning
> [name=謝朋諺(Adam Hsieh)]
> [time=Thu, Jul 11, 2019 10:51 AM]
###### tags: `paper`

---

## Reference
> [Improved Deep Metric Learning with Multi-class N-pair Loss Objective论文N-pair loss解读与实现](https://blog.csdn.net/silence2015/article/details/84878692)
> [度量学习 度量函数 metric learning deep metric learning 深度度量学习](https://blog.csdn.net/qq_16234613/article/details/81210320)
---

# Improved Deep Metric Learning with Multi-class N-pair Loss Objective

[論文連結](https://papers.nips.cc/paper/6200-improved-deep-metric-learning-with-multi-class-n-pair-loss-objective.pdf)
{%pdf https://papers.nips.cc/paper/6200-improved-deep-metric-learning-with-multi-class-n-pair-loss-objective.pdf %}

## 摘要重點
* 提出一種 $(N+1)$ - tuplet loss 來同時優化一個正樣本和 $N-1$ 個負樣本，當 $N$ 為 $2$ 時等價於 Triplet。
* 當 $N$ 很大時也會承擔很大的計算負擔，因此為了解決這問題，有一種高效的 **Batch Construction** 策略可以解決，僅僅使用 $2N$ 個樣本而不是 $N(N+1)$ 個樣本就能完成 $N$ 類的優化。
* 由於要學習 metric learning 需要大量的計算去找出 Hard Negative Data，因此本文尋求另一種替代方案：每次更新 Loss Function 時都用上更多的 Negative Data。

## Deep Metric Learning with Multiple Negative Examples

* 上圖左邊為 Triplet Loss，右邊為 (N+1)-Tuplet Loss。
* **Embedding Vector:** $f$ 被訓練以滿足每個 Loss 的約束。
* **Triplet Loss** 拉近 Positive 的點，同時推遠了一個 Negative 的點。
* **(N+1)-Tuplet Loss** 基於它們與輸入值的相似性，一次推動 N-1 個 Negative 點。
* 在上圖中可看到一個輸入會有多個 Negative Data，並期待他能夠與所有 Negative Data 分開，而且也希望他能把同類的資料都合併，==但記憶體往往不夠我們做這件事情==。
* 為了解決這問題，本文就發明了 N-pair-mc loss 的流程一次推動 N 個點來逼近理想值。

## Learning to identify from multiple negative examples
這邊將討論 Triplet 跟 Tuplet 的公式跟比較。
* 我們希望以多個 Negative Data 以及一個 Positive Data 去最佳化，因此當以 (N+1)-Tuplet 來考慮訓練，資料為 $\{x,x^+,x_1,...,x_{N+1}\}$:
* $x$ 是 Query。
* $x^+$ 是 Positive Data。
* $\{x_i\}^{N-1}_{i=1}$ 則為 Negative Data。

* **(N+1)-Tuplet Loss** 公式可定義為：
* 其中 $f(\centerdot;\theta)$ 是由深度學習定義的 Enbedding Kernal。
* $L$ 是指所有的類別，如果 $L$ 很大的話 Tuplet Loss 是很耗資源的。

* 當 $N=2$ 時，(2+1)-Tuplet Loss 非常類似 Triplet Loss，因為每對輸入都只有一個 Positive 跟 Negative，如下所示:
* 在粗略的假設下，我們可以證明 Embedding $f$ 最小化 $L_{(2+1)-tuplet}$若且唯若 (if and only if) 最小化 $L_{triplet}$。
* 當 $N>2$ 時，我們可以進一步論證 (N+1)-Tuplet Loss 會優於 Triplet Loss。
* 當我們視 $f$ 為**特徵向量**，$f^+$ 和 $f_i$ 作為**權重向量**，而右邊的分母為 **Partition Function**，上面公式就會類似於 multi-class logistic loss (i.e., softmax)。
* 我們觀察到 **Partition Function** 對應於 (N+1)-tuplet 近似於 (L+1)-tuplet，而且如果 $N$ 越大就會越近似。因此很自然的 (N+1)-tuplet loss 比 triplet loss 更接近理想的 (L+1)-tuplet loss。

## N-pair loss for efficient deep metric learning
* 設 $\{(x_1,x_1^+),...,(x_N,x_N^+)\}$ 是來自 $N$ 個不同類的 $N$ 對例子，即 $y_i \neq y_j, \forall i \neq j$。
* 我們從 $N$ 對中建造了 $N$ 個 tuplets 表示為 $\{S_i\}^N_{i=1}$，$S_i=\{x_i,x_1^+,x_2^+,...,x_N^+\}$。
* $x_i$ 是 $S_i$ 的 Query，$x_i^+$ 是 Positive example，$x_j^+$ 是 Negative example，而且 $i \neq j$。

* 上圖為訓練批次構建的 Triplet Loss、(N + 1)-Tuplet Loss 和 multi-class N-pair loss。
:::success
:bulb: 假設每對都屬於不同的類，**N-pair-mc loss** 中的 N-pair batch 構造利用所有 $2×N$ 嵌入向量來構建 $N$ 個不同的 (N+1)-Tuplets，其中 $\{f_i\}^N_{i=1}$ 作為它們的 Query，之後，我們聚集這 N 個不同的 tuplets 以形成 N-pair-mc loss。

:bulb: 因此假設有 N 個不同 Query，Triplet Loss 需要 $3N$ 次來評估必要的嵌入向量，(N+1)-Tuplet Loss 需要 $(N+1)N$ 次，而本文的 N-pair-mc Loss 僅需要 $2N$。
:::

* 由上圖可推導出我們的 N-pair-mc loss 公式：

* 這個方法結合了兩大部分：
1. (N+1)-tuplet loss，作為 Block Loss 的函式。
2. N-pair 的結構，做為能可高延展性訓練的關鍵。

* 最後，我們注意到 tuplet batch 構造並不特定於 (N+1)-tuplet loss。我們使用 tuplet 構造方法將 loss functions 稱為 N-pair loss。例如，當合併成標準的 triplet loss 中時，我們獲得以下 one-vs-one 的 N-pair loss（N-pair-ovo）：


## Hard negative class mining
* Hard negative data mining 被認為是 Triplet 的基本組成，以提高收斂速度或最後的辨識效果。
* 當輸出類別數量不是太大時，N-pair loss 可能就是不必要的，因為大多數 Negative data 已經被考慮進去了。
* 當輸出類別數量很大時，就會透過選擇放入。
* 對於 N-pair loss 理論上需要 N 個彼此為 Negative 的類別，這實質上增加了 Hard Negative Search 的挑戰。
* 我們提出了 Negative 'class' mining 相對 Negative 'instance' mining 有效的方式來貪婪的選擇 Negative class。
* 步驟如下：
1. **Evaluate Embedding Vectors**：隨機選擇大量要輸出的類別 $C$，每個類別再隨機傳遞一些 examples(一或兩個)以提取 Embedding Vector。
2. **Select Negative Classes**: 從步驟 1. 中的 $C$ 類選擇一類，接下來貪婪地增加一個所選類中最多違反 Triplet 限制的新類別，直到達到 $N$ 類，如果遇到相同時候，我們隨機挑選一個並列的類別。
3. **Finalize N-pair**: 從步驟 2. 中每個選定的類中抽取兩個 examples。

## L2 norm regularization of embedding vectors
數值 $f^T f^+$ 不僅會受到 $f^+$ 的方向影響，也會受到 norm 的影響，即使分類僅僅由方向決定，而 Normalization 可以成為避免這種情況的解決方案，但對於我們的 Loss 來說會限制了 $|f^T f^+|$ 的值小於 １，這會讓優化顯得困難，因此我們的替代方案是使用 $L^2$ norm 的正規化來將 embedding vector 變小。