분할-정복을 논문에서 본 건 처음!

알고리즘을 공부하면서 항상 분할-정복이 다른 문제에서는 어떻게 사용되는지 궁금했던 적이 많았습니다. (생각해보면 딥러닝이 가능한게 GPU+병렬 컴퓨팅이고 이게 분할-정복인데 그건 생각못했네요. :-( )

딥러닝에서 주제별로 학습자를 많이 만들고, 그 학습자의 결과를 합친다면 병렬 연산도 가능하고, 각 문제의 스케일도 줄어들고 장점이 있지 않을까요? 이번에 소개할 논문은 바로 그런 논문입니다.

논문 제목은 Divide and Conquer the Embedding Space for Metric Learning입니다. CVPR2019에 나온 논문입니다.

제목부터 Divide and Conquer라니 기대가 됩니다. 논문과 코드 링크는 아래와 같습니다.

paper : http://openaccess.thecvf.com/content_CVPR_2019/papers/Sanakoyeu_Divide_and_Conquer_the_Embedding_Space_for_Metric_Learning_CVPR_2019_paper.pdf

github : https://github.com/CompVis/metric-learning-divide-and-conquer

초록으로 읽기

(의미론적으로 유사한 객체가 서로 가까이 위치하고, 닮지 않은 객체가 멀리 떨어져 있는) 임베딩 공간을 학습하는 것은 많은 컴퓨터 비전 어플리케이션에 초석이 됩니다.

기존의 접근법은 일반적으로 이용 가능한 모든 데이터 포인트에 대한 임베딩 공간에서 단일 metric을 학습합니다. 이는 매우 복잡한 비균일 분포를 가질 수 있으며, 이는 객체들 간의 유사성과 다른 개념을 가집니다.

(eg. 외관, 모양, 색깔 또는 의미론적 의미(semantic meaning))

단일 disance metric을 학습하는 접근법은 모든 다른 유형의 관계를 인코딩하는 데 종종 어려움을 겪고 일반화도 잘 되지 않습니다.

본 논문에서는 쉬운 구현의 분할 정복을 이용하여 metric의 학습 능력을 향상 시킵니다.

논문의 접근법은 임베딩 공간과 데이터를 K 개의 작은 서브문제들로 공동 분할함으로써 임베딩 공간을보다 효율적으로 이용합니다.

데이터와 임베딩 공간을 모두 K 개의 서브 세트로 나누고, 신경망의 임베딩 레이어에 있는 뉴런그룹에 의해 정의된 임베딩 공간의 중첩되지 않는 부분 공간에서 K 개의 별도의 ditance metric을 학습합니다.

제안 된 접근법은 각 서브문제의 복잡성이 원래의 문제와 비교하여 줄어들기 때문에 수렴 속도를 증가시키고 일반화를 향상시킵니다.

CUB200-2011, CARS196, Stanford Online Products, Inshop Clothes , PKU VehicleID datasets 데이터셋에서 검색, 클러스터링 및 재식별 task에서 큰 차이를 보이며 최첨단 성능을 능가하는 것을 보였습니다.

1

2

3

4

5

6

7

8

9

10

11

12

Leave a Comment