Pairwise / Triplet Loss

Pairwise ranking loss

친구한테 영화를 추천해야 하는 상황을 생각해보자. 친구가 이때까지 본 영화에 대해 매긴 평점이나 영화평을 통해, 많은 새로운 영화 후보 중 친구가 볼 법한 영화를 순위를 매겨 제공해주는 것이다. 이런 종류의 문제를 딥러닝으로 풀고 싶으면 어떤 모델을 사용하는게 좋을까?

물론 Recommendation system 같은 내용이 있겠지만, 여기서는 문제를 다음과 같이 단순화해보자.

"여러 개의 입력 $x_1, x_2, ..., x_n$ 이 주어질 때 입력 간의 상대적인 순위 $r(x_1), r(x_2), ..., r(x_n)$ 를 구하기"

만약 $x_i$랑 관련된 일종의 점수 $y_i$가 제공된다면 가장 쉬운 방법은 $x_i$를 입력으로 받아서 $y_i$를 예측하는 regression model을 만드는 것이다. 위의 예시의 경우 친구가 본 영화들에 대해 평점을 매겨준다면 영화 정보를 입력으로 받아 평점을 예측하는 모델을 만들면 된다.

하지만 항상 이렇게 예쁜 점수 값이 주어지는 것은 아니다. 각 입력에 대한 순위만 주어질 때도 많을 뿐더러, 위와 같은 상황에서는 사실 친구가 정말 볼 법한 영화 4~5개 정도를 뽑는 것이 중요하지 각 영화에 대해 친구가 어떤 평점을 줄 지 정확하게 맞추는 것이 중요한 게 아니다. 그렇다고 binary classification으로 접근하기엔 boundary를 딱 떨어지게 나눌 수 없다는 점이 어렵다. 이럴 때 사용하기 적합한 것이 pairwise ranking loss이다.

Pairwise ranking loss의 주요 목표는 입력 $x_i, x_j$가 $rank(x_i) > rank(x_j)$를 만족하면 $f(x_i) > f(x_j)$ 가 성립하는 실수 함수 $f : X \rarr R$ 를 찾는 것이다. 여기선 $rank(x)$ 값이 클수록 더 좋은 입력이라고 정의했다. 두 입력에 대한 함수값이 확실히 차이나게 하기 위해서 margin $\alpha > 0$를 도입해 $f(x_i) > f(x_j) + \alpha$를 만족하는 $f$를 찾으면 더 좋을 것이다. 즉 좋은 입력의 점수가 더 안 좋은 입력의 점수값보다 $\alpha$ 이상 높게 $f$를 가르치는 것이다. 좋은 입력은 실수 중 큰 값으로, 나쁜 입력은 실수 중 작은 값으로 보내는 embedding function이라고 볼 수도 있다.

이제 자연스럽게 loss 함수를 유도할 수 있다. $f(x_i) > f(x_j) + \alpha$ 가 만족되지 않는 경우만 제재해주면 되니까, $max(0, f(x_j) + \alpha - f(x_i))$ 을 최소화 시키게 하면 된다. 앞의 부등식이 만족되면 loss 값은 0이 될 것이고, 그렇지 않으면 $f(x_j) + \alpha$가 $f(x_i)$ 보다 얼마나 (부당하게) 더 컸는지만큼 loss가 추가될 것이다.

이제 남은 점은 학습 과정에서 $x_i, x_j$ 쌍을 어떻게 선택해야 하냐는 것이다. 모든 쌍에 대해서 계산하면 $O(n^2)$이기 때문에 계산량이 감당이 안되고, 또 학습이 진행됨에 따라 앞의 부등식이 만족되는 쌍이 점점 늘어날 텐데 이런 쌍은 loss 값이 0이라 학습에 도움이 안되기 때문에 피하는 것이 좋다. 또 그렇다고 부등식을 만족하지 않는 쌍만 잘 고르면 너무 아웃라이어에 학습이 집중되어 성능이 떨어질 수 있다.

최근 CVPR 논문을 통해 Pairwise ranking이 어떻게 사용되는지 살펴보자.

Improving Pairwise Ranking for Multi-label Image Classification

---

2017 CVPR에 제출된 논문이다. https://arxiv.org/abs/1704.03135

제목에서도 알 수 있듯이 주어진 이미지와 관련된 여러 레이블을 뽑는게 목표이고, 모델을 학습하는데 Pairwise ranking loss를 적용했다. softmax를 쓰지 않고 굳이 ranking loss를 쓰는 이유는 모델이 정확한 레이블을 예측하는 것도 중요하지만, 예측에 실패하더라도 정답이 되는 레이블의 확률이나 점수가 다른 수많은 오답 레이블보다는 높은게 좋다는 점을 살리기 위해서라고 설명한다.

레이블 선정은 두 단계로 이루어지는데,

1. 모든 가능한 클래스에 대해 Confidence score를 계산해 순위표를 만들고
2. 각 클래스마다 따로 있는 threshold를 넘으면 해당 클래스에 속한다고 판정한다.

그런데 단순히 $x_i, x_j$ 쌍을 한 이미지에서 레이블 $i, j$가 각각 존재할 confidence score로 두고 위에서 설명한 pairwise loss function으로 학습할 경우, 임계치를 정하는 것이 문제가 된다. 이전까지 많이 쓰이던 휴리스틱인 top-k개 레이블을 뽑거나 미리 정한 threshold 이상의 confidence score를 가진 레이블을 뽑는 경우, 해당 이미지의 요소는 무시하고 threshold를 정하는 것이기 때문에 좋은 방법이라 보기 어렵다. 이미지에 따라 정답이 되는 레이블의 수가 다를 수 있는데 이를 고려하지 못하기 때문이다.

위의 문제를 다루는 것이 이 논문의 핵심이고, label decision 모듈을 삽입하는 것으로 해결하였다. label decision 모듈 $g$를 VGG16의 마지막 바로 앞 fc layer(fc7) 를 입력으로 받는 MLP로 설정한 뒤, 그 출력값으로 label의 threshold를 결정해 레이블을 선택하는 것이다. $g$는 다음과 같이 두가지 버전이 있다.

1. Label count estimation $n$ 이 한 이미지에 허락되는 최대 label 개수라고 했을 때, $g$를 n-way classification을 푸는 함수로 사용하는 것이다. $g$는 softmax loss로 학습하면 된다. 이는 기존의 top-k 레이블을 뽑는 휴리스틱을 개선한 것으로 볼 수 있다.
2. Threshold estimation 전체 클래스 개수가 $K$개 일 때, 각 클래스마다 고유의 threshold real value 값을 regression으로 정하는 것이다. $g$는 Binary Cross Entropy로 학습하고, 이는 기존의 global thresholding을 개선한 것으로 볼 수 있다.

위의 것보단 덜 중요해 보이지만, 저자들은 hinge loss form이 smooth 하지 않기 때문에 학습에 악영향을 미친다고 주장한다. 따라서 원래의 $l_{rank} = \sum_{neg} \sum_{pos} max(0, \alpha + f_{neg}(x_i) - f_{pos}(x_i) )$ 대신 log-sum-exp form인 $l_{lsep} = log(1+\sum_{neg} \sum_{pos} exp(f_{neg}(x_i) - f_{pos}(x_i)))$ 를 쓰자고 주장한다. 여기서 $f_{neg}(x_i)$는 $x_i$ 이미지에서 정답이 아닌 레이블에 대한 confidence score이고, $f_{pos}(x_i)$ 는 정답인 레이블에 대한 값이다.

마지막으로 sampling은 항상 1000개의 pair를 word2vec의 negative sampling과 같은 방법으로 뽑았다고 한다.

 

Who's Better? Who's Best? Pairwise Deep Ranking for Skill Determination

---

마찬가지로 2017 CVPR에 제출된 논문이다. https://arxiv.org/abs/1703.09913

굉장히 재미있는 task를 다루는 논문인데, 유튜브 같은 사이트에 올라온 How-to 영상이 여러 개 주어졌을 때 어느 동영상이 더 잘하는 지를 supervised deep ranking 으로 푸는 것이 목표이다.

위의 예시 같은 경우 소닉을 그리는 여러 영상이 있을 때 어떤 영상이 더 잘 그리는지 학습하는 것이다.

문제를 좀 더 명확히 정의하자면, 한 task(소닉 그리기 등)에 대한 영상 $p_i$가 $K$ 개 있을 때, 두 비디오 $p_i, p_j (1 \le i, j \le K)$ 를 직접 비교하는 함수 $E(p_i, p_j)$ 를 예측하고 싶은 것이다. $p_i$ 가 $p_j$보다 나은 경우 $E(p_i, p_j) = 1$ 이고 그 반대의 경우는 $E(p_i, p_j) = -1$, 둘 다 비슷한 경우에는 $E(p_i, p_j) = 0$ 이 되어야 한다. $E(p_i, p_j) = -E(p_j, p_i)$가 성립하고 한 영상 안에서 task를 여러 번 시행하는 경우 각각 독립된 영상으로 분리해서 학습한다.

$\psi = \{(p_i, p_j) | E(p_i, p_j) = 1\}$ 로 두면, 즉 $\psi$ 를 첫번째 영상이 두번째 영상보다 더 나은 쌍으로 이루어진 집합으로 두면 $f(p_i) > f(p_j) \quad \forall (p_i, p_j) \in \psi$ 인 $f$ 를 학습해 $E$를 예측할 수 있다. 학습은 pairwise loss $\sum_{(p_i, p_j) \in \psi} max(0, \alpha-f(p_i)+f(p_j))$ 를 바로 사용해 할 수 있다.

하지만 더 원활한 학습을 위해서, 저자들은 위의 loss 함수를 바로 사용하지 않고 두가지 변형 loss를 정의해 $f$를 학습했다.

첫번째 아이디어는 영상을 통째로 사용해 비교하는 것이 아니라, task의 각 step 별로 영상을 잘라서 비교하게 하는 것이다. 영상을 $N$개로 균일하게 나눈 후, $p_i^k$ 를 $p_i$의 $1 \le k \le N$ 번째 영상 조각이라고 하면 $E(p_i^k, p_j^k) = E(p_i, p_j)$ 로 둔 뒤 $L_{rank2} = \sum_{(p_i, p_j) \in \psi} \sum_{k=1}^N max(0, m-f(p_i^k)+f(p_j^k))$를 학습하는 것이다¹. 실험적으로 $N = 7$을 사용했다고 한다.

두번째 아이디어는 숙련도가 비슷한 영상은 비슷한 score가 나오게 학습하자는 것이다. $E(p_i, p_j) = 0$인 쌍에 대해 $|f(p_i) - f(p_j)| \le m$ 이 되게 학습함으로써 학습 데이터도 낭비하지 않고 $f$가 두 영상의 similarity도 찾아낼 수 있음을 기대할 수 있다. Pairwise loss와 비슷한 맥락으로 $\sum_{E(p_i, p_j)=0} \sum_{k=1}^N max(0, |f(p_i) -f(p_j)| -m)$ 을 loss로 사용해 학습하면 된다.

중요한 아이디어는 이게 끝이고, 그 외에는 실험 방법과 결과만 있다.

 

Triplet loss

Pairwise ranking loss와 비슷한 형태를 가지는 loss로 person re-identification이나 face recognition 분야에 널리 쓰이는 triplet loss가 있다.

주로 $L = max(0, \alpha + d(f(x_i), f(x_{pos})) - d(f(x_i), f(x_{neg})))$ 꼴로 나타내어지는데, 여기서 $f$는 embedding function이고 $d$는 distance function으로 두 입력 간의 거리를 측정하는 함수이다. loss의 목표는 기준점(anchor, $x_i$)과 비슷한 점(positive, $x_{pos}$) 을 임베딩 했을 때의 거리 $d(f(x_i), f(x_{pos}))$가 기준점과 다른 점(negative, $x_{neg}$) 의 임베딩 간 거리보다 $\alpha$ 이상 더 가깝게, 즉 부등식 $d(f(x_i), f(x_{pos})) + \alpha < d(f(x_i), f(x_{neg}))$가 만족하게 하는 것이다. $f$는 명백히 학습 대상이고, $g$는 경우에 따라 학습 대상일 때도 있고 L2 norm 등 기존의 distance function을 사용할 때도 있다.

loss function 꼴은 pairwise ranking loss와 비슷하지만, 주로 ranking 값을 위한 real value score를 학습하는, 일종의 regression과 비슷한 pairwise loss와 달리 triplet loss는 $f$의 결과가 고차원이고 clustering을 위한 metric learning에 주로 쓰인다는 차이점이 있다. 또 다른 관점으로는 naive한 pairwise loss는 서로 다른 pair 끼리 멀어지는 효과(push)만 있지만, triplet은 push 뿐만 아니라 anchor - positive distance를 통해 비슷한 점들이 모이는(pull) 효과가 있다는 것을 살펴 볼 수 있다.

Classification과 비교해 좋은 점은 각각 입력에 대한 명시적인 레이블이 필요한 classification loss와 달리, triplet loss는 anchor와 positive가 같은 클래스이고 anchor와 negative가 다른 클래스인 것만 알면 학습이 가능하다는 것이 있다. 또한 학습 과정에서 본 적이 없는 데이터에 대해 경험적으로 더 잘 동작한다고 한다.

또한 서로 다른 두 점만 뽑으면 되는 pairwise loss에 비해 triplet loss는 anchor, positive, negative로 이루어진 triplet을 뽑기 때문에 sampling을 좀 더 까다롭게 해야 한다. 대충 고르면 loss 값이 0인 triplet이 많이 나오게 되어 학습 효율이 떨어진다는 점이나 0이 아닌 것만 고르면 outlier에 오버 피팅 된다는 문제점도 공유하고, sampling에 따라 결과의 성능이 많이 달라지기 때문에 triplet loss를 사용하는 논문은 sampling 방법에 비중을 좀 더 싣는 편이다.

이제 Triplet loss가 적용된 논문을 보며 해당 loss가 어떻게 사용되는지 알아보자.

FaceNet: A Unified Embedding for Face Recognition and Clustering

---

2015년 구글에서 발표한 논문으로, triplet loss를 사용한 초창기 논문 중 하나이다. https://arxiv.org/abs/1503.03832

 

이 논문에서 다루는 task는 각각 face verification (같은 얼굴인지), recognition (주어진 얼굴이 누구인지), clustering (비슷한 얼굴끼리 묶기) 이다. FaceNet 이전에는 CNN을 classification 등으로 학습시킨 뒤, CNN 중간의 hidden layer 값을 얼굴에 대한 embedding으로 사용하는 우회적인 방법을 사용했다. 반면 FaceNet에서는 embedding을 triplet loss function을 통해 직접 학습한 뒤, face verification $\rarr$ thresholding, recognition $\rarr$ kNN classification, clustering $\rarr$ k-means / Hierarchical clustering 으로 해결했다.

$L = max(0, \alpha + d(f(x_i), f(x_{pos})) - d(f(x_i), f(x_{neg})))$ 에서 $f$는 ZFnet / Inception 기반의 CNN, $d$는 L2 norm의 제곱을 사용했다. 따라서 $L = \sum max(0, |f(x_i^a) - f(x_i^p)|_2^2 - {|f(x_i^a)-f(x_i^n)|}_2^2 +\alpha)$ 가 된다.

가장 집중해서 봐야 할 것은 triplet을 고르는 방법이다. 만약 loss가 0이 안되는 triplet만 고르면 된다면, 주어진 기준점 $x_i^a$ 에 대해 $x_i^p$는 기준점과의 거리가 가장 먼 positive point $argmax_{x_i^p} |f(x_i^a)-f(x_i^p)|_2^2$ 로 고르고, $x_i^n$는 기준점과의 거리가 가장 가까운 negative point $argmin_{x_i^n} |f(x_i^a)-f(x_i^p)|_2^2$ 로 고르면 된다. 이 두 점을 각각 hard positive, hard negative라고 부른다. 하지만 매번 hard point를 찾는 건 계산량도 너무 많이 들고, 아웃라이어에 오버피팅 될 위험도 높이기 때문에 현실성이 없다.

FaceNet에서는 몇천 단위의 크기를 가지는 mini batch 안에서 hard point를 찾는 방법을 통해 계산량과 오버피팅 문제를 동시에 해결했다. mini batch를 구성할 땐 anchor - positive distance를 안정적으로 배우기 위해서 먼저 한 사람당 40개 정도의 얼굴 사진을 먼저 batch에 넣은 뒤, negative point는 랜덤으로 뽑아 batch를 채웠다고 한다.

또한 실험적으로 hard positive를 뽑는 것 보단 모든 anchor - positive 쌍을 학습에 사용하는 것이 더 좋고, hard n egative를 뽑을 땐 $|f(x_i^a) - f(x_i^p) |_2^2 < | f(x_i^a) - f(x_i^n) |_2^2$인 $x_i^n$ 중에 뽑는 것이 좋다고 한다. 즉 anchor - positive 보다 anchor - negative 간 거리가 더 멀긴 하지만 margin이 충분히 크진 않은 negative를 뽑는 것이다.

이렇게 학습해서 Labeled Faces in the Wild 데이터셋에서 99.63%의 정확도를, YouTube Faces DB에서 95.12%의 정확도를 기록했다고 한다. 2015년도 논문임을 생각하면 굉장히 높은 정확도임을 알 수 있다.

그 외에도 batch 단위에서 hard point를 뽑는 아이디어는 이후 triplet loss를 사용하는 논문에서도 많이 채택된다.

In Defense of the Triplet Loss for Person Re-Identification

---

2017년 논문이다. https://arxiv.org/abs/1703.07737

논문의 주 내용은 Person Re-Identification에서 좋은 sampling을 사용한 triplet loss가 다른 classifcation loss 등 보다 좋은 성능을 보인다고 주장하는 것이다. 주장이 주장인만큼 논문의 핵심은 triplet sampling에 있다.

Sampling의 내용은 다음과 같다.

• Batch를 만들 때 먼저 $P$명의 사람을 고르고, 한 사람당 $K$개의 사진을 골라 만든다.
• Batch 내에서 모든 anchor point에 대해 hardest positive, hardest negative로 triplet을 구성하는 loss를 Batch Hard라고 부른다. 이 경우 loss는 $PK$개의 triplet에서 나온다.
• Batch 내에서 모든 가능한 triplet을 사용한 loss를 Batch All. 이 경우 loss에 기여하는 triplet 개수는 (# of anchor) * (# of positive points) * (# of negative points) = $PK * (K-1) * (PK-K)$가 된다.

여기서도 hinge form 보다 soft form이 더 좋다고 한다.

위의 sampling을 통해 triplet loss를 구성해 학습하면, state of the art 수준의 결과가 나옴을 보여준다. TriNet이 pretrained를 사용한 저자의 모델, LuNet이 처음부터 학습한 저자의 모델이다.

Beyond triplet loss: a deep quadruplet network for person re-identification

---

2017 CVPR 논문이다. https://arxiv.org/abs/1704.01719

Triplet loss가 unseen data에 대해 약하다는 점, 즉 generalization 성능이 떨어진다고 주장한 뒤 이를 보완하기 위한 quadruplet loss를 제안하는 것이 요점이다.

이해를 돕기 위한 예제 이미지가 있는데, (a)가 triplet으로 학습했을 때의 기대되는 embedding space, (b)가 저자가 제안한 quadruplet으로 학습했을 때의 기대되는 embedding space이다. 전자에 비해 후자가 intra-class(같은 클래스 간의) variation이 더 작고, inter-class(서로 다른 클래스 간의) variation이 더 크기 때문에 구분이 잘 돼 test set에서 더 좋은 성능을 보일 것이라 주장한다.

$X_i$가 $X$라는 사람의 $i$ 번째 이미지를 나타낸다고 하자. 원래의 triplet loss는 $d(X_i, X_j)$가 $d(X_i, Y_k)$ 보다만 작게 하면 학습이 성공했다. 하지만 저자들은 $d(X_i, X_j)$가 $d(Y_k, Z_w)$ 보다 작게 하는 것을 loss에 추가하면, 즉 클래스에 상관 없이 같은 클래스 간의 거리가 다른 클래스 간의 거리보다 작게 해주면 intra-class variation이 줄어들고 inter-class variation이 커진다고 주장한다.

좀 더 자세한 내용은 아래와 같다.

• 위의 논문들과는 다르게 distance function $g$를 학습 가능한 함수로 사용했다. margin 값이 유효할 수 있게 $g$의 범위는 [0, 1]에 들어오게 softmax를 적용했다.

• 위에서 말한 부분을 loss term에 추가했다. 아래 이미지에서 색칠된 부분이 새롭게 추가된 term이다. 새로운 negative example $Neg2$를 $Ref, Pos, Neg$의 클래스와 상관없이 뽑은 뒤 $d(Ref, Pos)$와 $d(Neg, Neg2)$의 관계를 새롭게 넣어주었다.

  

• 최종 loss는 아래와 같이 계산된다. $\alpha_1$이 있는 term이 기존 triplet loss 부분이고, $\alpha_2$가 있는 부분이 새롭게 추가된 항이다. 뒤쪽 항은 보조적인 역할을 하는 항이고, 앞쪽 항을 dominate하면 안되기 때문에 $\alpha_2$를 $\alpha_1$ 보다 작게 잡는다.

한가지 더 중요한 점은 margin 값을 adaptive 하게 계산하는 것이다. Triplet이든 Quadruplet이든 hard point를 뽑을 텐데, margin이 너무 작으면 loss에 쓰일 tuple이 부족하게 되고 너무 크면 오버피팅이 일어나게 되는데 adaptive margin을 도입해 해결했다.

Adaptive margin을 구하기 위해 저자들은 한가지 가정을 도입했는데, positive pair 간의 distance와 negative pair 간의 distance는 각각 서로 다른 분포를 따른다는 상당히 합리적인 가정이다. 그 뒤 각각의 distribution의 mean 값을 추정한 뒤, 그 차이에 적당한 상수를 곱해서 margin으로 사용했다. 위에서 말한 것과 같이 $\alpha_2 < \alpha_1$을 지키기 위해 $w_1 = 1, w_2 = 0.5$를 사용했다고 한다.

 

 

 

 

---

1 논문에는 $f_k(p_i)$ 꼴로 적혀 있어서 $k$ 마다 다른 함수를 학습한다고 혼동할 수 있는데 3.7 section의 표기와 뒤의 내용을 살펴 보면 $f$는 공유되는 것이 맞아 보인다.↩