[Computer Vision] Metric Learning

본 포스팅은 서울대학교 이준석 교수님의 '시각적 이해를 위한 머신러닝 (2023 spring)' 강의를 바탕으로 작성되었습니다.
모든 내용의 출처는 해당 강의에 있습니다.
Courses: http://viplab.snu.ac.kr/viplab/courses/mlvu_2023_1/index.html
Youtube: https://www.youtube.com/watch?v=cv_iOJ_OaUM&t=1723s

 

Metric Learning

Task

• 객체(이미지, 비디오 등)들 간의 distance function을 학습하는 task
  • 두 개 혹은 그 이상의 샘플을 입력 받아 스코어를 출력
  • 스코어는 샘플들 간의 거리를 의미
• 여기서 거리는 데이터에 따라 그 의미가 달라짐
  • 모델은 데이터로부터 관계를 학습

 

Data

• 객체들 간의 유사성을 정의하는 것은 어려움 (상대적이기 때문)
• 이러한 이유로 기존의 지도학습을 적용하기가 까다로워짐 (명확한 label이 없음)
• 그러나 그림과 같이 객체들 간의 상대적인 유사성(relative similarity)을 가지고 관계를 학습할 수 있음
• 이러한 방식의 장점은 데이터 수집이 비교적 쉽다는 것임 (라벨링이 필요 없기 때문)
  • 같은 장소에서 촬영된 사진들
  • 동일한 유튜브 카테고리에서 시청된 영상들
  • 웹에서 검색했을 때 상단에 나오는 이미지들... 등등
• 여전히 supervised 방식이지만 weaked supervised 방식 (기존과 다른 형태의 label)

---

Learning to Rank

Learning to Rank Problem

• 학습 데이터는 아이템들의 리스트로 이루어져 있고 일련의 특정 순서를 가지고 있음
• ranking model은 새로운 아이템들이 이러한 특정 순서를 모방하도록 학습됨
• Infromation Retrieval
  • Document retrieval: 웹 서치 엔진에서 텍스트 쿼리를 주면 유사도 순서에 따라 웹페이지가 나열됨
  • Collaborative filtering: 추천 시스템에서 사용자 선호도에 따라 아이템이 나열됨
  • Online advertising: 광고 업체의 bidding과 사용자 정보를 종합하여 광고가 나열됨

 

Problem Formulation

• Point-wise
  • 각각의 쿼리-아이템 쌍이 스코어로 묶임
  • 모델은 쿼리-아이템 쌍에 대해 그 스코어를 예측하도록 학습
  • 기존 회귀, 분류 문제 방식으로 풀면 됨
• Pair-wise
  • 두 개 아이템 순서쌍이 쿼리로 이루어짐
  • 모델은 주어진 쿼리의 각 아이템에 대한 스코어를 예측
  • 그 순서가 잘 유지되도록 학습
• List-wise
  • 두 개 이상의 아이템의 순서가 정해진 리스트가 쿼리
  • 어렵고 intractable함

 

Ranking for Representation Learning

• ranking 모델을 학습할 때 최종 목표 (예를 들어, 비디오 추천) 뿐만 아니라 샘플들의 representaion도 학습하도록 함
• 최종적으로, 처음 보는 데이터에 대해서도 잘 구별할 수 있도록 하는 것이 목표
  • 어떤 얼굴이 주어진 얼굴과 더 닮았는가를 관찰하여 '닮은 얼굴'에 기준을 학습함
  • 사용자가 어떤 비디오를 더 좋아하는지를 관찰하여 사용자의 '일반적인 취향'에 대해 학습함

 

Evaluation Metrics

• Normalized Discounted Cumulative Gain (NDCG)  

  

  
  
  • 순위를 평가하는 데 널리 사용되는 ranking metric
  • \( {rel}_i \): i번 째 아이템이 쿼리와 실제로 관련이 있으면 1, 그렇지 않으면 0
  • 그래프의 형태를 보면 알 수 있듯이 상위에 나오는 항목이 더 큰 가중치를 받음
  • 즉, 관련성이 실제로 높은 항목이 높은 순위에 있을 때 DCG의 값은 커짐
  • NDCG는 정규화된 DCG로 DCG 값을 maximum possible DCG 값으로 나눈 것
  • 0 <= NDCG <= 1
• NDCG Example

  

---

Triplet Loss

Main Idea

• Anchor, Positive, Negative의 세 개의 샘플로 구성됨
• 그림과 같이 {anchor, positive}는 가깝게, {anchor, negative}는 멀게 설계
• d(A, P) + alpha < d(A, N)
  • alpha는 마진으로, anchor-negative 쌍의 거리가 anchor-positive 쌍보다 최소 alpha 만큼은 더 멀어야 한다는 것을 의미
  • 예를 들어 alpha = 2이면 첫 번째 distance가 1, 두 번째 distance가 2여도 loss가 발생
  • 그 차이가 2만큼은 되어야 ok

 

Data Collection

Triplet loss를 적용할 때, negative 샘플을 어떻게 설정하는지가 모델 성능에 큰 영향을 미치는데, 다음과 같은 방식들이 존재

Random negative

 

• anchor와 positive는 positive pair로 부터 수집 
• negative는 수집되지 않은 것 중에서 랜덤으로 선택
• 그러나 이 방법을 사용하면 어려운 문제를 못 풀기 때문에 성능이 떨어짐

Online Negative Mining

• 미리 선택된 negative를 사용하는 것이 아니라 그림과 같이 미니배치 내에서 hard negative를 실시간으로 선택
• anchor에 대해 k-NN을 통해 파란색 칸 안의 배치 샘플 중에서 positive가 아니지만 거리가 가장 가까운 것을 찾음
• 더 이상 못 찾을 때까지 반복
• 그러나 이 방법은 효과적으로 작동하려면 큰 배치 사이즈가 필요한데, 이는 GPU 메모리 상에서 돌아가기 힘들고 \( O(B^2) \)의 복잡도가 소요됨

Semi-hard Negative Mining

• Negative sample을 어떻게 선택하는지가 학습 성능에 큰 영향을 미침
• Hard negative (\( n_1 \)): \( d(a, n_1) < d(a, p) \)를 만족하는 샘플
  • positive보다 가까운 negative 샘플을 선택하는 방법
  • 이 경우, \( n_1 \)이 p보다 훨씬 가까워 loss는 단순히 f = 0으로 만들어 alpha를 지불하는 식으로 학습됨
• Semi-hard negative (\( n_2 \)): \( d(a, p) < d(a, n_2) < d(a, p) + \alpha \)를 만족하는 샘플
  • positive보다는 멀지만 여전히 마진(alpha) 내에 있는 negative 샘플을 선택하는 방법
  • 학습 안정성이 향상됨
  • \( n_1 \)은 다른 앵커로부터 학습됨
• Easy negative (\( n_3 \)): \( d(a, p) + \alpha < d(a, n_3) \)를 만족하는 샘플
  • positive보다 거리가 먼 negative 샘플을 선택하는 방법
  • 학습이 너무 쉬워져 문제가 됨

 

FaceNet

Main Idea

• Semi-hard negative mining을 적용한 Face clustering 모델
• 임베딩 공간에서 동일한 사람의 얼굴은 가깝게, 다른 사람들의 얼굴은 멀게 학습됨
• 두 얼굴 간의 유사도를 예측하여 같은 사람인지, 다른 사람인지를 결정
• 개인 사진첩이나 입국 심사 등에 사용

Architecture

• 미니배치는 앞서와 같이 anchor, positive, negative로 구성됨
• 임베딩을 거쳐 triplel loss를 계산하고 역전파
• ZFNet, Inceiption 두 가지 아키텍처로 시도함

Result

 

CDML: Collaborative Deep Metric Learning

Main Idea

• 앞서와 동일한 아이디어를 유튜브 비디오에도 적용
• Collaborative Filtering
  • 사용자들은 그들의 선호(like, dislike와 같은)를 통해 연관 있는 아이템을 필터링하도록 implicit하게 협력함
  • 예를 들어, 나와 비슷한 선호를 가지고 있는 사용자들이 시청한 영상을 추천하는 방식
  • co-watched 영상들을 서로 관련이 있는 것으로 판단
• Video Graph 

  

  
  
  • 그래프 상의 각 노드는 비디오
  • 엣지의 가중치는 함께 시청된 빈도에 따라 결정됨. 자주 같이 시청될 수록 강한 연결
  • Triplet 구성
    • Anchor: 기준이 되는 비디오
    • Positive: Anchor 비디오와 자주 같이 시청되는 비디오
    • Negative: Anchor 비디오와 관련이 없는 비디오 중에서 랜덤으로 샘플링
  • 이렇게 학습을 거치면 Video Embedding이 형성되는데 이를 통해 다양한 task에 응용 가능

Model Architecture

Examples

• co-watched 비디오에 대한 학습이 잘 이루어지며 (첫 번째 행), 함께 시청되지 않았더라도 의미가 유사한 비디오에 대해서도 학습이 잘 이루어짐 (두 번째 행)

Limitations

• 좋은 성능을 내려면 배치 사이즈가 커야됨 (online negative mining)
• CPU로는 너무 많은 시간이 걸리고, GPU로는 메모리가 부족함
• Negative가 랜덤하게 초기화되기 때문

 

GCML: Graph Clustering Metric Learning

Main Idea

• 미니배치 내에서 적당한 negative를 고르는 것은 매우 많은 시간이 소요됨
• 이를 해결하고자 어느 정도 clustering을 해놓고 선택
• Affinity (hierarchical) clustering
  • bottom-up 접근
  • 가까운 비디오 샘플들을 L0 군집으로 묶음
  • 다시, 가까운 군집들을 L1 군집으로 묶음
  • L2, L3, ... 반복
• Sampling triplets
  • anchor는 잎 노드(비디오)에서 랜덤으로 선택
  • positive는 anchor와 동일한 부모로부터의 자식 노드
  • negative는 이웃한 군집으로부터 (그림의 파란색)

Discussions

• 트리의 어느 레벨에서나 샘플링 → 샘플링 유연성 증가
• Semi-hard negative mining을 사용했을 때 할당된 negative가 100배 정도 더 자주 사용됨
• 10배 더 작은 데이터셋으로 SOTA 달성
• 그러나 hard negative mining을 완전히 덜어내지는 못함

---

Contrastive Learning

Main Idea

• Pair-wise loss function: 입력은 쌍을 이루어서 들어오게 되는데, ground truth distance Y는 0 (similar) or 1 (dissimilar)
• 그리고 Y = 0인 경우 \( L_S \)를, Y = 1인 경우 \( L_D \)의 서로 다른 함수를 적용
• 결과적으로 유사하면(Y = 0) 거리가 줄어들도록, 유사하지 않으면(Y = 1) 거리가 늘어나도록 학습됨

  

 

Recall: Normalization Problem

• 분류 문제에서, 우리는 일반적으로 클래스 스코어를 얻기 위해 softmax를 통해 값들을 normalizing 하였음
• 만약 클래스 개수가 백만 개, 천만 개 정도로 많아진다면 계산량도 늘어나게 됨
• 특히 이미 거의 0에 가까운 스코어를 내는 클래스 조차 cross-entropy를 최적화하는 데에 term으로서 들어가게 됨
• Negative Sampling
  • 이러한 아이디어를 적용하여, 거의 대부분이 0에 가까운 negative를 전부 다 계산하지 말고 일부를 sampling
  • 엄밀하지는 않지만 good approximation
  • "Should we really use/update the parameters for the word 'zebra' for every training sentence?"

 

SimCLR

Main Idea

• 각각의 훈련용 이미지를 증강을 통해 서로 다른 두 개의 이미지(\ (x_i, xj) \)로 새로 만듦
• \( (x_i, x_j) \)는 그림과 같은 과정을 거쳐 \( (z_i, z-i) \)로 임베딩됨
• 미니배치 사이즈는 N에서 2N
• 이 중에서 각 이미지는 1개의 positive를 갖고(도플갱어라고 표현), 2N - 2개의 negative를 가짐

Contrastive Loss: NT-Xent (Normalized Temperature-scaled Cross Entropy)

• 분자에는 앞서 임베딩된 positive 관계인 \( (z_i, z_j) \)
• 분모에는 자기 자신인 \( z_i \)를 제외한 2N - 1개
• 라벨링이 필요 없는 self-supervised learning

 

NCE: Noise Contrastive Estimator

Main Idea

• M개의 학습 샘플을 가정 \( \{x_1, ..., x_M\} \)
• \( p_m \): M개의 학습 샘플에 대한 확률 분포
• 가짜 확률 분포 \( p_n \)을 도입하여 이로부터 N개의 \( \{y_1, ..., y_N\} \)를 샘플링
• 각 샘플이 둘 중 어떤 확률 분포로부터 샘플링 되었는지 판단하도록 모델이 학습됨 → logistic regression
• 실제 샘플 \( x_i \)는 \( p_m \)으로 분류되어야 함
• 가짜 샘플 \( y_i \)는 \( p_n \)으로 분류되어야 함

Objective Function

• 그림과 같은 objective function을 최대화하도록 설계됨
• 이를 뜯어서 살펴보면, 실제 확률분포에 실제 샘플을 넣었을 때(\( p_m(x_i;\theta) \))의 값은 최대가 되게, 실제 확률분포에 가짜 샘플을 넣었을 때(\( p_m(y_i;\theta) \))의 값은 최소가 되게 설계됨
• 가짜 확률분포는 말 그대로 학습을 위해 가짜로 생성한 것이므로 건드릴 필요가 없음
• 결과적으로 \( p_m \)에 대해서만 모델링하여 이를 학습하면 됨