# AP-Loss for Accurate One-Stage Object Detection
###### tags: `Object Detection`, `One Stage Object Detection`, `Loss Function`

**本文是本人針對該篇論文的理解，若有不對之處，或是對本人在下文中提出的疑問有解答或想法的話，還請不吝賜教，非常感謝**

**在開始閱讀文章之前，強烈建議先去了解一下以下知識**:
* [Ranking Loss](https://gombru.github.io/2019/04/03/ranking_loss/)
* convexity and non-convexity function optimization problem: [link](https://www.solver.com/convex-optimization), [深度學習與凸論](https://www.zhihu.com/question/22125449)
* [Focal Loss](https://arxiv.org/pdf/1708.02002): 不只解決正負樣本不平衡，更專注在分類難易樣本。

論文題目雖說是提出一個新的損失函數，但其實不只這樣。

論文提出一個新型框架將一階段目標檢測中的分類(classfication)任務替換成排名(ranking)任務，而在排名問題上採用Average-Precision loss(AP-loss)。並且為了解決AP-loss本身因使用Heaviside step function(非凸且不可微分)作為激活函數而造成不可直接優化等問題，作者又開發了一個新型優化演算法(optimizer)，將感知器學習中的誤差驅動(error-driven)更新方案與深度學習框架中的反向傳播無縫接軌地融合在一起。

*補充說明*:
1. 非凸函數代表無法保證順著梯度方向能獲得全局最優解，因此容易陷在或是獲得局部最優解 -> 基本上深度學習得損失函數都可以視為非凸函數，[詳細說明](https://www.zhihu.com/question/265516791)。
2. 不可微分則造成梯度下降(反向傳播)等基於微分的方法無法使用。

### 目的

說了這麼多，AP-loss主要是解決什麼問題呢? 它主要是解決分類任務上正負樣本資料不平衡的問題，並且是將分類任務轉換成排名任務來達到目標。

### Ranking Task/Procedure

以下是總體架構圖，概略說明整個方法如何運作，細節在之後章節。通過下圖知道該論文只改動分類任務/分支。圖中的Ranking Procedure/Task有兩條主線:
1. Ground Truth: 通過Label Assignment和Ranking Label Transformation兩個步驟，將標籤轉換成對應anchor的ground truth。
2. Detector: 檢測器實際訓練與推論的過程，針對各問題設計解決方案 - Difference Transformation, Error-driven Update...

而以上的兩條主線中有以下幾個主要組成:

1. Ground Truth轉換成Ranking label
2. AP-loss的定義與優化器
3. 如何解決不可微分

#### Label Assignment


在過去anchor-based的一階段目標檢測中，會從一張圖中產生一些預先定義好的框集合(anchors) $B$，且每個anchor $b_{i}\in B$會給定一個基於ground truth和IoU策略的標籤$t_{i}\in \{-1,0,1,...,K\}$，檢測器則會對每個anchor $b_{i}$輸出一個score-vector $(s^{0}_{i}, ..., s^{K}_{i})$。$1$~$K$是目標的ID，標籤$0$是背景、標籤$-1$是忽略的框體。

該論文也是基於計算ground truth與anchor間的IoU方法給予標籤，但對整體架構有所更動。若有$K$個類別，則其中第$i$個anchor $b_{i}$將會被複製$K$次 ($b_{ik},k = 1, ...,K$)，而第$k$個 $b_{i}$ anchor用 $b_{ik}$ 來表示。每個$b_{ik}$會被分配一個標籤 $t_{ik} \in \{-1,0,1\}$，在ranking loss中，標籤-1不用被計算，所以標籤會變成二分類 $t_{ik} \in \{0,1\}$。<font color="red">**因此在訓練與測試階段，與過去一階段檢測器不同的是，每個anchor $b_{ik}$ 都會給予一組對應的預測scalar score $s_{ik}$**</font>。所以<font color="red">**此方法與RetinaNet和YOLOv2以後的版本相同的是都在多分類中用二分類標籤(binary labels)，不同的是論文更進一步的把標籤換成排名標籤(ranking labels)**</font>。

下圖簡單說明label assignment的過程以及與以前一階段檢測器給定ground truth label的差別，後續Ranking Label Transformation的具體轉換公式定義在AP-loss章節中。

排名任務對於每個anchor的分數有制定一項規則: 所有正樣本anchor(包含目標的anchor)的排名要比所有負樣本anchor(該anchor不包含該目標)來得**高**。此外，有個小細節要注意，本方法與評估指標中的mAP有些微不同，本方法的AP是從所有類別計算，原因是作者認為**分數分布應該要是統一的，若對各類別分別進行計算則無法實現**。

*疑問*:
我個人對上圖傳統一階段目標檢測的部分有些許疑問。就我理解，用YOLOv5舉例，label會是 $[P_{obj}, x, y, w, h, c_{1}, c_{2}, ..., c_{k}]$，而$[c_{1}, c_{2}, ..., c_{k}]$代表其中的類別是呈現向量的形式，與上圖中直接給予該anchor此類別的方式並不相符。

*回答*:
我回去複習YOLOv5和YOLOv7發現一些問題與以上提問的解答。首先，我上面的提問有誤。提問中的認知是最後輸出層的label形式，但上文中主要是在描述**如何把label配對到anchor中，而在YOLOv5與YOLOv7中的build_target函數可以清楚知道，確實一個anchor只會配對一個class**，所以上圖中對傳統一階段目標檢測的說明並沒有錯。若理解有誤，麻煩大佬再給予提點，不勝感激。

#### Ranking Label Transformation
接續label assignment之後，把 $k$ anchors轉換成實際ranking label的動作。將所有標籤 $t_{i}$ 轉換成對應的順序點對(pairwise ordered)形式，$1$ 是一個指示函數(indicator function)等於 $1$，表示只有當 $t_{i} = 1, t_{j} = 0$ 時成立，其餘則是 $0$:
$$
\forall i,j,\ y_{ij} = 1_{t_{i} = 1,\ t_{j} = 0}
$$
以上公式我認為用以下表示法會比較直觀:
$$
\forall i,j,\ y_{ij} = \left\{
\begin{align*}
& 1,\ t_{i} = 1\ and \ t_{j} = 0\\
& 0,\ else
\end{align*}
\right.
$$

<!-- *疑問*:
針對label assignment到ranking label transformation的部分，具體如何直觀理解轉換後的ranking label含意? 就我理解，ranking是對Difference Transformation得到的score進行排序，但問題在於ground truth那個側又是如何進行轉換的呢?

*回答*:
-->

#### AP Loss

Average precision被廣泛用在目標檢測、資訊檢索等領域上，作為評估指標評估並量化模型的好壞。但在目標檢測任務的模型訓練上，卻並非一個好的或是常用的優化目標/損失函數，原因是其非凸與不可微分的特性(激活函數)。雖然有許多前人將AP-loss應用在目標檢測上，也都有不錯的結果，但效能與效果依然受限於其內部限制(?什麼內部限制?)。

從細節上來說，論文方法與前人用AP loss的方法有以下不同:
1. 可用在任何可微分的線性或非線性模型。
2. 直接優化AP-loss且不用顯著的loss gap。
3. 過去方法都是用期望(expectation)函數與包絡(envelope)函數來分別逼近原本的目標函數，由於該近似函數是平滑的，所以能用此來近似梯度，但該方法依舊受限於AP-loss的非凸與非擬凸性，進而導致梯度下降的效率更差。而本方法在優化(optimize)時不採用與前人方法一樣的近似梯度方案，因此也不用忍受目標函數的非凸性。
4. 端到端訓練與推論。

為了後續說明方便，將簡化一些代數表述並再次進行一些說明:
1. $B$代表所有複製過後的anchor box集合。
2. $b_{i}$則代表第$i$個還未複製的anchor box，且每個anchor box $b_{i}$ 對應到一組scalar score $s_{i}$ 和一個binary標籤 $t_{i}$。

以下將介紹一系列公式，如何從ranking loss到實際AP-loss:

1. **Difference Transformation**: 計算anchor pair間的差值。將分數 $s_{i}$ 轉換成分差的形式，$s(b_{i}; \theta)$ 是CNN based對anchor進行評估的分數計算函數，其中 $\theta$ 是神經網絡的權重:
$$
\forall i,j,\ x_{ij} = -(s(b_{i}; \theta) - s(b_{j}; \theta)) = -(s_{i} - s_{j})
$$
2. **Vector-valued Activation Function $L( \cdot )$**: $P$ 是正樣本集合、$N$ 是負樣本集合:
$$
L_{ij}(x) = \frac{H(x_{ij})}{1+ \sum_{k \in P \cup N, k \ne i}{H(x_{ik})}} = L_{ij}
$$
$H( \cdot )$ 是Heaviside step fucntion，在此的定義為以下:
$$
H(x) = \left\{
\begin{align*}
1, x \ge 0\\
0, x \lt 0
\end{align*}
\right.
$$

接著使用 $x$ 分別計算每對anchors的AP-loss。當其結果不存在任意相同的分數時($i.e., \forall i \ne j, s_{i} \ne s_{j}$)，則稱該排名(ranking)為合適的排名(proper ranking)。在不喪失一般性(generality)的前提下，作者打破任意聯繫/關係，將所有排名視為適當的排名(proper ranking)。AP-loss $L_{AP}$ 的公式推算如下，其中$x,y,L \in \mathbb{R}^{d}$，$d = (|P|+|N|)^{2}$，並且第三條運算是**對AP-loss進行normalize**:

$$
\begin{align*}
L_{AP} = & \ 1 - AP = 1 - \frac{1}{|P|} \sum_{i \in P}{\frac{rank^{+}(i)}{rank(i)}}\\
= & \ 1- \frac{1}{|P|} \sum_{i \in P} \frac{1 + \sum_{i \in P, j \ne i}{H(x_{ij})}}{1 + \sum_{i \in P, j \ne i}{H(x_{ij})} + \sum_{j \in N}{H(x_{ij})}}\\
= & \ \frac{1}{|P|} \sum_{i \in P}{\sum_{j \in N}{L_{ij}}} = \frac{1}{|P|} \sum_{i,j}{L_{ij} \cdot y_{ij}} = \frac{1}{|P|} \langle L(x), y \rangle
\end{align*}
$$

*符號與代數解釋*:
* $\langle , \rangle$: 兩個向量的點乘/內積
* $rank(i)$: 在所有有效樣本中，分數 $s_{i}$ 的排名。
* $rank^{+}(i)$: 在所有正樣本中，分數 $s_{i}$ 的排名。
* $P=\{i|t_{i}=1\}$
* $N=\{i|t_{i}=0\}$
* $|P|$ 表示 $P$ 集合的大小
* $L$ 與 $y$ 分別是 $L_{ij}$ 與 $y_{ij}$ 的向量形式

最後此優化問題就會能用以下公式表示，其中$\theta$代表檢測模型的權重:

$$
min_{\theta}L_{AP}(\theta) = 1 - AP(\theta) = \frac{1}{|P|}\langle L(x(\theta)), y \rangle
$$

作者在此有提到，除了AP指標能作為ranking loss function之外，其他如AUC-loss等ranking loss能應用在此框架中。但通過作者過去的經驗與實驗，表明AP-loss應該要比AUC-loss更合適。

### Optimization Algorithm

該論文的優化器或是優化演算法的核心就是"錯誤驅動更新(error-driven algorithm)"，它是從感知器學習演算法中推廣出來，且用來克服目標函數無法微分的問題。

感知器是一種非常簡單的智能神經元，只用Heaviside step function(Unit step function)作為激活函數。但Heaviside step funciton在感知器中一樣不可微分，因此不適用梯度下降，所以感知器用一個錯誤驅動更新方案取代cross-entropy來直接作用在神經元的權重，並且該演算法在訓練集是線性可分的前提下，保證可以在有限的步數中收斂。

*Questions*: 有限步數的具體解讀是什麼? 如何用數學方式證明該方法能收斂在有限步數嗎?

*Answer*: AP-loss在以下條件都能滿足前提下，就能保證收斂在有限步數，<font color="red">**具體數學證明請到論文附錄1**</font>:
1. 該模型是線性模型
2. 訓練資料集線性可分

#### Error-Driven Update

回顧感知器學習演算法，更新輸入變數的方法是"誤差驅動"，其方法是直接通過**期望輸出與實際輸出的差值**進行參數的更新。作者採用此方法，並進一步延伸到激活函數帶有vector-valued輸入輸出的情況中，假設此時的輸入輸出為 $x_{ij}$ 以及 $L_{ij}$，$L^{*}_{ij}$ 是期望輸出，則 $x_{ij}$ 的更新公式為:

$$
\Delta x_{ij} = L^{*}_{ij} - L_{ij}
$$

**注意**:
當每組 $L_{ij} \cdot y_{ij} = 0$時，AP-loss將能達到它理論上的最小值 $0$，並且會有以下兩種情況:
1. 若 $y_{ij} = 1$時，應該要把期望輸出設為 $0$ ($L^{*}_{ij}=0$)。
2. 若 $y_{ij} = 0$時，由於並不關心此時的期望輸出所以把它設為 $0$ ($L^{*}_{ij}=0$)，因此它不會對AP-loss的更新有任何貢獻。

通過上述事項，可以將更新公式簡化為:

$$
\Delta x_{ij} = -L_{ij} \cdot y_{ij}
$$

#### Target Function / Optimization problem

$$
arg\ min_{\Delta\theta} \{ -\langle \Delta x , x(\theta^{(n)} + \Delta\theta) - x(\theta^{(n)}) \rangle + \lambda||\Delta\theta||^{2}_{2} \}
$$

<!-- 利用已知的$\Delta x$，期望找到一個更新網絡權重 $\Delta\theta$ 得到一個對 $x$ 來說最合適的更新移動大小。論文用期望移動(更新)的大小與實際更新大小的點乘來衡量連續一棟 -->

<!-- ###### Back propagation

ToDo -->

### Summary

#### AP-loss
* AP-loss理解簡述:
從上述公式直觀來看，其分母是表示正樣本在所有樣本中的正確排名，對於該正樣本來說是個定值，所以當分數高於該正樣本的副樣本增加時(該正樣本排名下降時)，$L_{AP}$增加。
*補充*:
此外從公式中可以看到AP-loss只針對**正負樣本間的關係**建立數學模型，而[Rank & Sort loss(RS loss)](https://openaccess.thecvf.com/content/ICCV2021/papers/Oksuz_Rank__Sort_Loss_for_Object_Detection_and_Instance_Segmentation_ICCV_2021_paper.pdf)則是又增加**建立正樣本內部間關係數學模型**。
<!-- 簡而言之，AP-loss應用在分類任務上就是**不直接**計算ground truth label 與預測兩者的相似度或是差值，而是進一步用IoU threshold 0.5計算AP，並用AP差值作為損失函數來更新網絡。 -->
* 排名任務如何解決分類問題:
排名任務是直接對正負樣本之間關係建立數學模型，從而降低對正負樣本比例的影響，讓正負樣本不平衡的問題得以解決。
* AP-loss的AP是對總體類別的排名結果進行計算，而非各類別分別計算。
* AP除了能同時反映precision和recall的情況外，更直接是評估值標之一，因此能更貼近實際推論的情況。
* 結合誤差驅動網絡優化演算法解決激活函數不可微分的問題。

### Reference

1. [Towards Accurate One-Stage Object Detection with AP-Loss](https://openaccess.thecvf.com/content_CVPR_2019/papers/Chen_Towards_Accurate_One-Stage_Object_Detection_With_AP-Loss_CVPR_2019_paper.pdf)