Retrieval Task와 Metric Learning

Retrival은 검색이라는 뜻으로, 입력된 쿼리(query)와 가장 유사한 샘플을 데이터베이스(DB)로부터 찾는 Task이다.
Query와 DB의 종류에 따라 여러가지로 분류할 수 있는데, Text to Video Retrieval, Video to Video Retrieval과 같이 다양한 조합이 있을 수 있다.

우리가 흔히 사용하는 유튜브 검색은 단순히 생각하면 Text to Video라고 볼 수 있지만, 사실 검색에 영상과 텍스트 정보 뿐 아니라 메타 데이터를 비롯한 다양한 정보가 활용되므로 Multimodal Video Retrieval이라 할 수 있겠다.

Metric Learning

https://medium.com/@enoshshr/triplet-loss-and-siamese-neural-networks-5d363fdeba9b

머신러닝 모델을 통해 우리는 어떤 데이터를 어떤 parameter space에 임베딩하게 된다.
Retrieval Task를 위해서는 이 parameter space에서 서로 유사한 샘플들이 가까운 거리를 갖고, 서로 다른 샘플들이 더 먼 거리를 갖도록 학습시켜야 하는데, 이렇게 데이터들에 적합한 거리 함수를 학습시키는 과정을 metric learning이라고 한다.

Retrieval 과정

Retrieval은 다음과 같은 과정을 통해 수행된다.

1. 어떤 쿼리를 parameter space에 임베딩하여 query vector를 얻는다.
2. 이 쿼리 vector와 가까운(유사한) 순서로 database의 샘플들을 정렬한다.
3. 이 순위가 검색결과라고 할 수 있다.

이 방법을 활용하기 위해, 쿼리와 유사한 샘플일 수록 가까운 거리를 갖고, 유사하지 않은 샘플일 수록 먼 거리를 갖도록 임베딩하는 모델을 학습시킨다.

거리의 정의

위에서는 편의상 거리가 가까울수록 샘플들이 서로 유사하다고 표현했지만, parameter space에 임베딩된 샘플들의 feature vector들의 유사도를 판단하는 2가지 방법이 있다.

1. L2 Distance

$$ L2(x, y) = \sqrt{\sum_{x_i\in x, y_i\in y}(x_i - y_i)^2}$$

단순하게 feature간의 거리를 계산하는 방법이다. 값이 낮을수록, 거리가 가까운 것이기 때문에 비슷한 샘플들이 가까운 거리를 갖도록 학습시킨다.

2. Consine Similarity

$$ Sim(x, y) = \frac{x\cdot y}{||x|| ||y||}$$ 

코사인 유사도를 이용하는 방법이다. 값이 1이라면 두 벡터가 완전히 동일하다는 의미이고, -1이면 완전히 반대인 것이다.

Metric Learning Loss

위와 같이 유사한 샘플들을 가까이, 유사하지 않은 샘플들을 멀리 나누는 feature vector를 만들기 위해 특별한 Loss를 이용하여 모델을 학습시킨다.

모델의 학습을 위해서는 유사한 영상의 쌍을 의미하는 Positive Pair와 유사하지 않은 영상의 쌍을 의미하는 Negative Pair의 정의가 필요하다.

Contrastive Loss

$$ \text{Constrastive Loss}(i, j) := \max[p_{ij}D^2_{ij} + (1-p_{ij})[\alpha - D_{ij}]^2]$$

대조적 손실함수라고 직역된다. $p_{ij}$는 두 샘플이 Positive Pair라면 1, Negative Pair라면 0이 되는 값이다

함수를 보면 매우 단순하게, Positive Pair에 대해서는 거리가 손실함수가 되어, 거리가 클 수록 손실함수가 커지고, Negative Pair에 대해서는 임의의 마진 값 $\alpha$에서 거리를 뺀 값의 제곱이 손실함수가 되어, Negative Pair와의 거리가 margin값 정도로 벗어나 있도록 설정한다.

Triplet Loss

$$ \text{Triplet Loss} (a,p,n) := \max[D_{ap}^2 - D_{an}^2 + \alpha]$$

Constrastive Loss가 어떤 절대적인 마진 값만큼 Negative Pair가 떨어지도록 만드는 반면, Triplet Loss는 상대적인 거리를 고려한다.

어떤 샘플 $a$(anchor)와 positive pair인 샘플 $p$, negative pair인 샘플 $n$에 대하여, $ap$의 거리가 $an$의 거리보다 상대적으로 가깝지 않은 만큼 손실 함수값을 부여한다.

이 손실함수는 anchor 샘플과 positive, negative 샘플을 어떻게 구성하느냐에 따라 결과가 달라지는 특징이 있다.

• $D_{ap}^2 + \alpha < D_{an}^2$인 Negative Sample을 사용하는 경우(Easy Triplet)
  
  • Easy Neg 샘플이 이미 충분히 떨어진 경우이다.
  • 적절한 Negative Sample을 찾기는 매우 쉬우나, Gradient가 낮기 때문에 학습에 큰 도움이 되지 않는다.
• $D_{an}^2 < D_{ap}^2$인 Negative Sample을 사용하는 경우(Hard Triplet)
  • Hard Neg 샘플이 오히려 Pos 샘플보다 Anchor에 가깝다.
  • 학습에 중요한 샘플이다.
• $D_{ap}^2 < D_{an}^2 < D_{ap}^2 + \alpha$인 Neg Sample을 사용하는 경우 (Semi-hard Triplet)
  • Neg 샘플이 Pos 샘플보다는 멀지만, $\alpha$ 마진 안에 있다. (그렇게 멀지는 않다.)
  • 학습에 중요하며, Hard Triplet 보다는 찾기가 쉽다.

Retrieval 평가 지표

Retrieval의 평가는 추천 시스템에서도 흔히 사용되는 mAP@k, Recall@k를 사용한다.
쿼리 샘플에 대한 유사도 순서로 정렬된 DB에서 상위 $k$개의 샘플을 보고 평가를 수행한다.

mAP@k

상위 $k$개의 샘플에 대한 누적값을 구한다. 예를들어, 상위 5개의 값이 각각 $0, 1, 1, 0, 1$일 때, (0은 유사하지 않음, 1은 유사함) 누적값은 $0, 1, 2, 0, 3$이다. 이를 각각 순위로 나누고 합한 후, $k$개의 샘플 중 맞은 값의 갯수를 나누어준다. 즉, $0+1/2+2/3+0+3/5=53/30$의 누적값에 정규화 값 $3$을 나누어 AP@k는 $53/90$이다.

각 쿼리 영상의 AP의 평균을 구하면 mAP를 구할 수 있다.

Recall@k

$$ \text{Recall@k} = \frac{TP}{TP+FN}$$

상위 $k$개의 샘플 중, 실제로 쿼리와 유사한 샘플의 갯수 $TP$를 전체 쿼리와 유사한 샘플의 갯수($TP+FN$)로 나눈다.
일반적으로 $k$가 작아질 수록 값이 올라간다.(mAP와 반대)

References

• 세종대학교 RCV랩 임근택 연구원님
• Metric Learning Metric Learning 이란 - 학습 방법(Loss) - KM-Hana 님