Learning with Average Precision : Training Image Retrieval with a Listwise Loss

두 번째로 포스팅할 논문은 ICCV 2019에 개제 된 Learning with Average Precision : Training Image Retrieval with a Listwise Loss라는 논문입니다. 이전 포스팅과 마찬가지로 NAVER LABS의 localization으로 소개된 R2D2 논문을 읽던 중 Average Precision에 관한 지식이 부족해서 핵심 부분만 읽었습니다. 논문에서 다루고 있는 메인 아이디어만 수식을 통해서 알아보겠습니다.

 

제목에서 알 수 있듯이 AP(Average Precision)를 사용한 학습이 논문의 핵심입니다. 따라서 AP(Avergae Precision)가 무엇인지 알아야 합니다. Average Precision에 대해서 잘 정리해주신 글이 있어 링크를 첨부합니다.

 

물체 검출 알고리즘 성능 평가방법 AP(Average Precision)의 이해

간단히 말해서 AP는 Precision과 Recall이라는 개념을 통해서 알고리즘의 성능을 평가하는 지표입니다. 첨부한 글에서는 Detection 알고리즘의 성능평가만을 언급했지만 Metric Learning에도 사용할 수 있습니다. 본 논문에서는 이 Metric Learning의 관점에서 AP를 이용한 학습을 제안합니다.

 

다음 그림은 Metric Learning에서 널리 사용되는 Triplet Ranking Loss(이전 포스팅 참고)와 본 논문에서 소개하는 Listwise Loss의 차이점을 도식화한 것입니다.

 

Triplet Ranking Loss는 3개의 이미지를 통해서 벡터 상의 거리에 따라 Network를 학습하는 것이 목적이라면 Listwise Loss는 AP를 이용해서 더 많은 개수의 이미지의 ranking을 구함으로써 동시에 많은 양을 비교할 수 있습니다. 하지만 AP를 계산하는 식이 미분이 불가능(non-differentiable) 하기 때문에 AP를 근사하는 differentiable 한 식을 만들어 학습에 사용함으로써 문제를 해결합니다.

 

AP를 수식으로 정의하고 어떻게 이를 differentiable 하게 바꾸는지 알아보겠습니다.

 

$S = \{ x \in \mathbb {R}^C \, \vert \,   \| x \| = 1\}$

 

$I$는 이미지를 나타내고 $S$는 $C$차원의 unit hyperspher를 나타냅니다.

여기서 unit hyperspher는 크기가 1인 $C$차원 벡터들의 집합을 의미합니다. 3차원을 예로 들면 $(0,0,0)$을 중심으로 길이가 1인 벡터들의 집합이므로 구의 형태이고 2차원에서는 $(0,0)$을 중심으로 길이가 1인 벡터들의 집합이기 때문에 원의 형태를 나타냅니다. $S$는 4차원 이상의 크기를 가질 수 있기 때문에 hyperspher라고 하고 길이가 1인 단위 벡터이기 때문에 unit을 붙였습니다.

 

$f_\theta : I \rightarrow S$

 

신경망 $f_\theta$를 통해 $I$를 $S$로 embedding 합니다. 이미지의 descriptor를 신경망을 통해 계산하는 것과 똑같은 과정이고 $\theta$는 신경망의 parameter입니다. 즉 이미지 $I$를 $C$차원의 단위 벡터로 변환하는 함수로 생각할 수 있습니다. 변환된 벡터는 $C$차원의 단위 벡터이기 때문에 $S$상의 한 점이 됩니다.

 

$S_i^j = sim(I_i, I_j) = d_i^\top d_j \in [-1, 1]$

 

$sim(I_i, I_j)$는 이미지 $I_i$와 이미지 $I_j$의 유사도를 나타냅니다. 각각의 이미지를 신경망 $f_\theta$로 embedding 하여 계산된 벡터 $f_\theta ( I_i)$, $f_\theta (I_j)$ 들을 코사인 유사도(cosine similarity)를 통해 계산합니다. 두 벡터는 모두 단위 벡터이기 때문에 가장 유사할때 1 가장 유사하지 않을때 -1의 값을 가집니다.

 

$R : \mathbb {R}^N \times \mathcal {N} \rightarrow \mathcal {N} $

 

코사인 유사도식을 이용하면 query 이미지와 데이터베이스 상의 모든 이미지에 대해서 각각 코사인 유사도를 계산할 수 있고 이를 통해 query 이미지와 유사한 순으로 데이터베이스 상의 모든 이미지들$\{I_i\}_{1 \leq i \leq N}$을 정렬(rank)할 수 있습니다. $R$은 이 ranking function을 의미합니다. 즉 $R(S^q, i)$는 query 이미지 $I_q$와 데이터베이스상의 모든 이미지 $I_i$간의 유사도를 기준으로 순위를 매겼을 때 $i$번째로 높은 이미지의 index를 뜻합니다. 또한 $R(S^q)$는 모든 이미지들의 index를 가지고있는 리스트를 뜻합니다.

 

$Y^q$는 $\{ 0, 1\}^N$의 크기를 가지는 ground-truth입니다. $Y_i^q$는 이미지 $I_i$가 query 이미지 $I_q$와 유사하면 1 그렇지 않으면 0입니다. $Y^q$를 이용해 $R(S^q)$를 평가할 수 있습니다.

 

$R(S^q)$를 평가하는 목적이 무엇일까요? 거꾸로 한번 생각해보겠습니다. $R(S^q)$는 query 이미지와 데이터베이스상의 이미지들 간의 거리에 의해 결정됩니다. 그런데 거리는 고정된 식 코사인 유사도를 통해 결정되므로 코사인 유사도의 성능을 평가하기 위해 $R(S^q)$를 평가하는 것이 아닙니다. 한 단계 더 뒤로 가서 코사인 유사도는 이미지를 변환한 벡터를 이용해서 계산되고 이 벡터는 신경망 $f_\theta$를 통해서 변환합니다. 즉 $R(S^q)$를 평가하는 것은 신경망 $f_\theta$를 통해 이미지에서 변환된 벡터가 코사인 유사도를 통해 얼마나 잘 정렬되는가를 평가하는 것입니다. 다시 말해 신경망 $f_\theta$를 통해 변환된 벡터는 이미지들 간의 유사성을 코사인 유사도를 통해 계산하기에 얼마나 적절한가를 평가한다고 할 수 있습니다.

 

계속해서 $R(S^q)$과 $Y(S^q)$를 어떻게 비교하여 평가하는지 알아보겠습니다. 본 논문에서는 AP(Average Precision)를 사용하여 평가합니다. 즉, $R(S^q)$와 $Y(S^q)$를 이용해 계산한 AP의 값이 높으면 신경망 $f_\theta$는 이미지를 적절한 벡터로 변환하고 있다는 것이고 AP의 값이 낮으면 그렇지 못하다는 뜻으로 해석할 수 있습니다. 따라서 AP가 최대가 되도록 신경망을 학습하는 것이 목표라고 할 수 있습니다.

 

$AP(S^q, Y^q) = \sum_{k=1}^{N} P_k (S^q, Y^q) \Delta r_k (S^q, Y^q)$

 

AP는 위의 식으로 나타냅니다. $P_k$는 rank $k$에서 precision값이고 다음과 같은 식으로 계산합니다.

 

$P_k (S^q, Y^q) =  {1 \over k} \sum_{i=1}^k \sum_{j=1}^N Y_j^q 𝟙[R(S^q, i) = j]$

 

$\Delta r_k$는 $k-1$에서 $k$로의 incremental recall을 의미하고 다음과 같은 식으로 계산합니다.

 

$\Delta r_k (S^q, Y^q) = { 1 \over N^q } \sum_{j=1}^N Y_j^q 𝟙[R(S^q, k) = j], \, \, N^q = \sum_{i=1}^N Y_i^q$

 

𝟙는 indicator function을 뜻합니다. 프로그래밍의 if문을 수식으로 표현한 것입니다. 괄호 안의 식이 참일 경우 1 그렇지 않으면 0이 됩니다.

 

precision $P_k$부터 살펴보겠습니다. 식 안쪽 $\sum$를 풀어 수식을 다음처럼 전개할 수 있습니다. ${1 \over k} \sum_{i=1}^k ( Y_1^q 𝟙[R(S^q, i) = 1] + Y_2^q 𝟙[R(S^q, i) = 2] + \dots + Y_N^q 𝟙[R(S^q, i) = N])$

indicator function에 의해 $R(S^q, i)$이 $j$와 같을 때만 1이 되고 그렇지 않을 경우 전부 0이 되므로 $Y_j^q 𝟙 [R(S^q, i) = j]$는 i번째로 높은 $S^q$값을 갖는 이미지 $I_j$의 ground truth $Y_j$값이라고 할 수 있습니다. 식 전체를 보면 $i$가 1부터 $k$까지 커지면서 총합을 구해 $k$로 나누므로 이는 평균을 뜻합니다. 즉, 식 전체는 query 이미지 $I_q$와의 거리를 기준으로 순위를 매겼을 때 1부터 $k$번째 순위까지의 ground truth 값을 모두 더하여 k로 나눈 것이 됩니다. 

 

Recall에 해당하는 $\Delta r_k$입니다. Precision 식과 거의 유사하므로 전개하지 않고 의미를 생각해보겠습니다. 첨부했던 글에서 볼 수 있듯이 원래의 Recall은 Precision과 마찬가지로 1부터 $k$까지 값을 누적하면서 계산하지만 본 논문에서는 incremental recall이라고 표현하는 rank 단위 변화량만을 계산하여 recall로 사용하여 AP를 계산하였습니다. Precision과 마찬가지로 indicator function에 의해 $R(S^q, k)$값이 $j$와 같을 때만 1이 되고 그렇지 않은 경우 0이 되므로 수식의 의미는 $k$번째로 높은 $S^q$값을 갖는 이미지 $I_j$의 ground truth $Y_j$값을 전체 ground truth의 값으로 나눈 것이 됩니다. 그리고 ground truth $Y_j$는 0 혹은 1의 값을 갖기 때문에 $k$번째 순위의 이미지에 해당하는 ground truth 값이 0이라면 $\Delta r_k(S^q, Y^q)$ 값은 0이 됩니다. 즉 $\Delta r_k(S^q, Y^q)$는 $k$번째 순위의 이미지의 ground truth 값을 ground truth의 개수로 나눈 값이라고 할 수 있습니다.

 

AP는 precision $P_k$와 incremental recall $\Delta r_k ( S^q, Y^q )$를 곱한 것을 모두 더해 계산합니다. 위에서 AP가 최대가 되도록 신경망을 학습하는 것이 목표라고 했습니다. 그렇다면 AP가 최대가 되는 조건이 무엇일까요? 먼저 $\Delta r_k (S^q, Y^q)$는 $k$번째 순위에 해당하는 이미지의 ground truth값과 ground truth의 총개수에 따라 결정됩니다. 다시 말해 순위와 상관없이 이미지에 할당된 값으로 볼 수 있고 즉 신경망의 학습 정도에 따라서 달라지지 않습니다. 반면에 precision $P_k$는 순위에 따라 누적하여 값을 결정하기 때문에 신경망의 학습 정도에 따라 값이 달라집니다. 따라서 precision $P_k$의 값이 최대가 되면 AP의 값도 최대가 됨을 알 수 있습니다.

 

precision $P_k$는 1부터 $k$번째 순위까지의 ground truth 값을 모두 더하여 $k$로 나눈 값입니다. $k$는 고정된 값이기 때문에 1부터 $k$번째 순위까지 ground truth를 더한 값이 최대가 되면 $P_k$가 최대가 됩니다. 즉 높은 순위에 해당하는 이미지의 ground truth값이 1이 되면 precision $P_k$값이 커지게 되고 그에 따라 AP값도 최대가 됩니다. 이는 직관적으로 생각해봐도 알 수 있습니다. query 이미지 q와 비교해서 유사도가 높은 이미지가 높은 순위에 위치하고 유사도가 낮은 이미지가 낮은 순위에 위치하는 정렬은 올바른 정렬이지만 유사도가 낮은 이미지가 높은 순위에 위치하고 유사도가 높은 이미지가 낮은 순위에 위치하면 잘못된 정렬입니다. 따라서 코사인 유사도를 기준으로 값이 높은 이미지(ground truth = 1)가 높은 순위에 위치하고 값이 낮은 이미지(ground truth = 0)가 낮은 순위에 위치하도록 이미지를 벡터로 변환하는 신경망 $f_\theta$의 AP가 최대가 됩니다. 신경망은 loss가 최소가 되도록 학습하므로 $1-AP$를 loss로 설정합니다.

 

여기까지 Metric Learning 관점에서 Average Precision을 수식으로 정의하고 의미를 알아봤습니다. 계속해서 위에서 정의한 AP를 differentiable 하게 바꾸는 과정을 수식으로 작성하고 의미를 알아보겠습니다.

 

신경망의 $\theta$는 loss를 미분하여 각각의 parameter들이 loss에 영향을 준 비율에 따라 값의 수정을 반복하면서 학습합니다. 하지만 앞서 정의한 AP는 indicator function에 의해 미분이 불가능(non-differentiable)합니다. 따라서 이 hard assignment(이전 포스팅 참고) 𝟙를 soft assignment $\delta$로 바꾸어 AP에 근사하는 미분이 가능한(differentiable)식을 정의합니다.

 

첫 번째로 rank에 따라 계산했던 AP를 유사도 구간에 따라 계산하도록 바꿉니다.

양의 정수 $M$이 주어졌을 때, 유사도의 범위 $[-1, 1]$를 $M -1$개의 동일한 크기의 간격으로 나눕니다. 각각의 구간은 $b_m$이라고 하는 bin center를 갖고 다음처럼 나타냅니다.

 

$b_m = 1 - ( m - 1) \Delta, \, \{b_m\}_{1 \leq m \leq M}, \, \Delta = {2 \over {M - 1}}$

 

위에서 AP를 계산할 때 precision $P_k$와 incremental recall $\Delta r_k$를 rank $k$에 따라 계산했습니다. 이를 각각의 구간$b_m$에 따라 계산합니다. 

 

$P_m^{bin}(S^q, Y^q) = {{\sum_{m'=1}^{m} \sum_{i=1}^{N} Y_i^q 𝟙[S_i^q \in \bar {b}_m']} \over {\sum_{m'=1}^{m} \sum_{i=1}^{N}𝟙[S_i^q \in \bar {b}_{m'}]}} $  ,      $\Delta r_m^{bin} (S^q, Y^q) = { {\sum_{i=1}^{N} Y_i^q 𝟙[S_i^q \in \bar {b}_m]} \over {N^q}}$

 

$\bar {b}_m = [max(b_m - \Delta, -1), min(b_m + \Delta, 1)]$

 

precision과 recall을 구간에 따라 계산한다는 것은 무엇을 의미할까요? 변경 전에는 순위에 따라 precision과 recall을 계산하였기 때문에 이미지의 유사도는 대소 비교를 통해 순위를 결정할 때만 사용되었습니다. 예를 들어 2순위 이미지의 유사도가 0.5라고 한다면 1순위 유사도는 크기에 상관없이 0.5보다 크기만 하면 AP를 계산하는 데에 영향을 끼치지 않았습니다. 반면에 유사도 구간에 따라 precision과 recall을 계산하면 유사도가 높은 구간에 유사한 이미지가 포함되고 유사도가 낮은 구간에 유사하지 않은 이미지가 포함돼야 AP가 최대가 됩니다. 즉 단순히 정렬을 하기 위한 유사도를 계산하기 위해 신경망을 학습하는 것을 넘어 유사한 이미지는 유사도를 높게 하고 유사하지 않은 이미지는 유사도를 낮게 계산하도록 신경망을 학습할 수 있습니다.

 

두 번째로 hard assignment 𝟙를 soft assignment로 대체합니다.

 

$\delta(x, m) = max( 1 - {{\vert x - b_m \vert}\over {\Delta}}, 0)$

 

$\delta(x, m)$은 hard assignment indicator function 𝟙을 대체합니다. 논문에서는 함수 $\delta$가 히스토그램의 커널 밀도 추정으로 소개됩니다만 히스토그램에 대해서 자세히 몰라 어떤 의미로 사용됐는지만 알아보겠습니다. 본래의 indicator function 𝟙는 $S_i^q$가 $\bar {b}_m$에 포함될 때 1 그렇지 않으면 0을 나타냈고 이 때문에 non-differentiable 했습니다. 반면에 $\delta(x, m)$은 $x$가 $\bar {b}_m$일 때 0에서 1 사이의 값을 가지고 범위를 벗어날 경우 0, $x$값이 $b_m$일 때 $\delta(x, m)$은 1로 최댓값을 가집니다. 즉 이미지의 유사도가 특정 범위에 포함되어 있는지 아닌지만을 검사하는 것을 넘어 구간의 중심에 가까울수록 1 멀어질수록 0을 부여해 differentiable 하게 바꿉니다.

 

$\delta(x, m)$을 이용해 precision과 recall의 수식을 다음과 같이 바꿀 수 있고 이를 quantization function이라고 부릅니다.

 

$ \hat {P} _m (S^q, Y^q) = { { \sum_{m'=1}^{m} \delta (S^q, m') \top Y^q } \over { \sum_{m'=1}^{m} \delta (S^q, m') \top {\bf {1}}}} $   ,      $\Delta \hat {r}_m (S^q, Y^q) = { {\delta (S^q, m) \top Y^q} \over {N^q} }$

 

새롭게 계산된 precision과 recall의 수식을 이용해 AP를 다음과 같은 수식으로 나타내고 이를 quantized average precision이라고 부릅니다.

 

$AP_Q (S^q, Y^q) = \sum_{m=1}^{M} \hat {P}_m (S^q, Y^q) \Delta \hat {r}_m (S^q, y^q)$

여기까지 AP를 수식으로 정의하고 구간별 precision, recall의 계산과 hard assignment를 근사하는 soft assignment를 이용해 AP를 신경망을 통해 학습이 가능하도록 변경하는 과정을 알아봤습니다. 마지막으로 실제 학습단계에서 loss가 어떻게 계산되는지 알아보고 포스팅을 마치겠습니다.

 

$\mathcal {B} = \{ I_1, \dots, I_B \}$ 는 이미지들의 batch를 나타내고 각각의 이미지는 label $y_i$를 갖습니다. $ D = [ d_1, \dots, d_B] \in \mathcal {S}^B$ 는 이미지들의 descriptor들을 나타냅니다. batch내의 각각의 이미지 $I_i$를 potential query로 설정하여 $S_i$를 이미지 $I_i$와 batch내의 다른 이미지들 간의 similarity scores로 나타냅니다. $Y_i$는 이미지 $I_i$와 batch내의 다른 이미지들 간의 ground thruth relavant값을 나타내고 이미지 $I_i$의 label $y_i$와 이미지 $I_j$의 label $y_j$가 같을 경우에 1이 되며 그렇지 않을 경우 0이 됩니다. 다음과 같은 식으로 표현합니다. $Y_ij = 𝟙[y_i = y_j]$

 

batch 한 개당 $B$개의 이미지가 있기 때문에 이미지 $I_1$부터 이미지 $I_B$까지 각각의 이미지가 query 이미지가 되어 총 $B$개의 $AP_Q$를 계산하고 평균을 취해 최종 $mAP_Q$ 값을 계산합니다. 수식으로 표현하면 다음과 같습니다.

 

$mAP_Q(D, Y) = {{1}\over {B}} \sum_{i=1}^{B} AP_Q (d_i \top D, Y_i)$

 

신경망은 $mAP$를 최대화하는 것이 목적이므로 loss $L$을 다음과 같이 정의합니다. $L(D, Y) = 1 - mAP_Q(D, Y)$ 

 

pytorch로 구현한 QAP

key-rnaker/QAP-pytorch

다음 포스팅에서는 이번 포스팅에 이어서 NAVER LABS에서 2019년 NeurIPS에 발표한 R2D2 : Repeatable and Reliable Detector and Descriptor 논문을 리뷰하겠습니다.

 

[참고자료]

[1] J.Revaud, J.Almaza ́n, R.Rezende and C.Souza. Learning with Average Precision: Training Image Retrieval with a Listwise Loss. In Proc. ICCV, 2019 

[2] Learning with Average Precision 

[3] 물체 검출 알고리즘 성능 평가방법 AP(Average Precision)의 이해