PR402 - 2 : Deep Learning for Two-Sided Matching

오늘 리뷰해볼 논문은 Deep Learning for Two-Sided Matching - Ravindranath et al. 입니다.

저번과 마찬가지로 ICML 2021 Accepted paper이고, 꽤 재미있는 주제로 가져와봤습니다.

Link - https://arxiv.org/abs/2107.03427

Intro:

Two-Sided Matching은 일상에서 꽤 많이 접할 수 있는 태스크입니다. n개의 노동자와 m개의 회사가 있다고 할 때, 노동자들은 각각 회사에 대한 선호를, 회사는 노동자에 대한 선호를 지니고 있을 때 가장 바람직한 (n, m) 쌍을 어떻게 해야 만들 수 있을까에 관한 문제입니다. 노동시장 뿐만 아니라 요즘 많이 볼 수 있는 데이팅 앱이라든지, 듀오 등의 중개회사 등등 적용시켜볼 만한 곳은 많죠. 위의 논문은 이 Two-Sided Matching 태스크를 딥러닝으로 풀어서, 기존의 이론을 뛰어넘는 결과를 낳았다는데 의의가 있습니다.

Preliminaries:

Two-Sided Matching은 경제학에서 많이 다루어지던 문제입니다. Two-Sided Matching에서는 어떤 metric으로 Matching의 적절성을 평가할까요? 보통 크게 두 가지 metric을 가지고 평가하는데, 첫째는 stability, 두 번째는 SP (Strategy-proof)입니다. 

stability는 쉽게 말해 '불륜 커플의 부재'입니다. (A, a) (B, b)라는 쌍이 존재한다고 해봅시다. 만약 A가 a보다 b를 더 선호하고, b가 B보다 A를 더 선호할 경우 A와 b는 서로의 쌍을 버리고 (A, b)의 쌍을 만들 유인이 존재합니다. 따라서 현재의 Matching이 불안정한 것이죠. 이 때 (A, b)를 'Blocking pair'라고 하는데, stability는 이러한 blocking pair가 없을 때 (혹은 가능한 적을 때)를 높게 평가합니다. 

SP는 거짓된 정보를 제공할 유인이 없어야 하는 조건입니다. 만약 A가 짜장면, 짬뽕, 볶음밥 중에서 요리를 골라야 한다고 생각해봅시다. (요리는 하나씩 밖에 없다고 해보겠습니다.) 그런데 A의 실제 선호는 짜장면 - 짬뽕 - 볶음밥 순인데 만약 다른 사람들에게 이렇게 말할 경우 본인이 짬뽕을 먹게 되는 경우를 생각해볼 수 있습니다. 그래서 A는 '차라리 짜장면 - 볶음밥 - 짬뽕 순으로 좋아한다고 하면 어떨까?'라는 생각을 하게 되고, 이렇게 말해서 짜장면을 먹을 수 있게 된다면 A는 자신의 실제 선호를 속이고 거짓으로 선호를 말할 유인이 존재합니다. 따라서 어떤 알고리즘 매칭 방법을 사용하는지에 따라 만약 참가자에게 거짓으로 선호를 말할 유인이 존재한다면 나쁜 알고리즘이라고 하는 것입니다. 

페어링을 위해 기존에 널리 쓰였던 알고리즘들은 DA (Deferred-acceptance) / RSD (Random serial dictatorship) 정도가 있습니다. DA는 stable한 반면 SP가 아니고, RSD는 SP인 반면 stable하지 않습니다. 따라서 이를 해결할 만한 최상의 알고리즘을 찾자는 것이 해당 논문의 키포인트입니다.

Content:

Two-Sided Matching 태스크를 딥러닝으로 풀기 위해서는 적당한 아키텍쳐 설정이 핵심입니다. 본 글에서는 해당 아키텍쳐를 간단히 요약만 하고 넘어가겠습니다.

딥러닝 모델에 들어가는 인풋은 노동자의 선호를 담은 P (N * M size)와, 기업의 선호를 담은 Q (M * N size)입니다. 중간 layer는 Dense와 ReLU를 사용한 레이어로 구성됩니다. 마지막 아웃풋은 특정 노동자와 기업이 매칭될 확률이 담긴 행렬 R로 표시됩니다. (N * M size)

이를 학습시키기 위해서 Metric이 필요한데요, 논문에서는 Stability Violation과 SP-Violation이라는 척도를 사용하여 학습시켰습니다. Stability와 SP는 Trade-off (그렇지 않다면 애초에 어려운 태스크가 아니었겠죠)이기 때문에 학습 이후에 모델들의 성능을 2차원 그래프로 표현할 수 있습니다. 

양쪽 사이드에 보면 DA와 RSD가 위치하고 있는 것을 알 수 있습니다. 딥러닝으로도 도달 가능한 성능의 알고리즘들이었고, 추가적으로 파라미터 조정을 통해 보다 안쪽에 있는 지점들의 알고리즘 또한 만들 수 있습니다. 

Conclusion:

기술하지는 않았으나 수학적 증명들이 약간 가미되었고, 원래 다른 도메인에서 다루어지던 주제이다 보니 딥러닝 아키텍쳐로 끌고 오는게 조금 신선했던 것 같습니다. 아키텍쳐 설정이나 메트릭이 조금 더 최적화된다면 훨씬 더 좋은 성능을 보여줄 것으로 기대됩니다. 실제 사업에서도 충분히 고려해볼 만한 매칭 알고리즘을 서비스할 수 있을 것 같습니다. 해당 논문에서 주는 intuition을 바탕으로 조금 더 문제를 일반화한다면 꽤나 재미있는 태스크들에 적용 가능할 것으로 생각합니다.