최적 수송(Optimal transport)

흙더미를 파서 구덩이를 메워야 합니다. 위 줄의 노란 막대가 흙더미 a, 아래 줄의 파란 막대가 구덩이 b이고, 흙의 총량과 구덩이의 총부피는 똑같이 1입니다. 흙 한 단위를 한 칸 옮기는 데 비용이 1 든다면, 가장 싸게 옮기는 계획은 무엇일까요? 구덩이의 모양을 로 바꾸고, 오른쪽으로 칸 옮겨 보세요.

한 줄 위에서는 답이 간단합니다. 왼쪽 흙부터 왼쪽 구덩이부터 차례로 채우면, 곧 경로들이 서로 엇갈리지 않게 하면 됩니다. 엇갈린 두 경로는 목적지를 맞바꾸기만 해도 비용이 줄거나 적어도 늘지 않기 때문입니다. 왼쪽부터 쌓인 양의 비율로 말하면, 흙더미의 30%가 그 왼쪽에 있는 지점의 흙이 구덩이의 30%가 그 왼쪽에 있는 지점으로 가는 것입니다. 이런 지점을 분위수라 하니, 분위수끼리의 짝짓기입니다. 흙의 총량을 1로 맞춰 두면 흙더미와 구덩이는 각각 확률⁠(probability)⁠분포로 볼 수 있고, 이 최소 비용이 두 분포 사이의 거리인 1-바서슈타인 거리입니다(1969년 이 거리를 다룬 러시아 수학자 레오니트 바서슈타인의 이름). 지금 $W_1 =$ 칸입니다.

왼쪽 그림은 두 분포의 누적 분포 함수⁠(cumulative distribution function)⁠ $F_a$(노랑)와 $F_b$(파랑)입니다. 누적 분포 함수 $F(x)$는 x와 그 왼쪽에 있는 흙의 비율로, 왼쪽에서 오른쪽으로 가며 0에서 1까지 계단처럼 올라갑니다. 가장 싼 계획에서 칸과 칸 사이의 경계를 넘어가는 흙의 양은 그 자리에서 두 계단의 높이 차이 $|F_a - F_b|$와 정확히 같습니다. 그러니 전체 비용은 두 계단 사이의 넓이⁠(area)⁠, 곧 적분⁠(integral)⁠입니다. 1차원에서 $W_1$은 누적 분포 함수 사이의 맨해튼 거리(L1 거리)입니다.

비교해 봅시다. 히스토그램⁠(histogram)⁠을 16개 수의 벡터⁠(vector)⁠로 보고 칸마다의 차이로 잰 L2 거리는 입니다. 오른쪽 그림은 구덩이를 0칸부터 7칸까지 옮길 때 두 값을 각자의 최댓값이 1이 되도록 맞춰 그린 것입니다. 바서슈타인 거리는 멀리 옮길수록 꾸준히 커지지만, L2 거리는 두 분포가 겹치지 않게 되는 순간부터 더 커지지 않습니다. 칸마다 비교하는 거리는 '얼마나 다른가'만 알고 '얼마나 멀리 옮겨야 하는가'는 모릅니다. 이 차이 때문에 바서슈타인 거리는 1990년대 말부터 '흙 옮기기 거리'라는 이름으로 이미지 검색에서 쓰였습니다(두 그림의 색 분포를 비교). 2017년에는 진짜 같은 그림을 만들어 내는 신경망(생성 모델⁠, generative model⁠)을 학습시키는 데 쓰였습니다. 만든 그림들의 분포와 진짜 그림들의 분포가 겹치지 않는 처음 단계에서도, 바서슈타인 거리는 '얼마나 더 옮겨야 하는지'를 알려 주어 학습이 나아갈 방향을 잃지 않기 때문입니다(바서슈타인 GAN).

평면이나 그래프 위처럼 일반적인 경우에는 흙을 어디서 어디로 얼마나 보낼지를 정하는 최적화⁠(optimization)⁠ 문제를 풀어야 합니다. 보낼 양들을 미지수로 두면 비용도 조건(흙더미마다 내보내는 양의 합, 구덩이마다 받는 양의 합)도 모두 일차식이라서, 일차 부등식과 등식 아래서 일차식을 가장 작게 하는 선형 계획⁠(linear programming)⁠ 문제가 됩니다. 문제를 처음 적은 사람은 프랑스의 가스파르 몽주로, 1781년 논문에서 파낸 흙(déblais)을 메울 곳(remblais)으로 옮기는 비용을 따졌습니다. 몽주의 문제는 흙 한 덩이를 쪼개지 않고 한 곳으로만 보내야 해서 매우 어려웠습니다. 1939~1942년 무렵 소련의 레오니트 칸토로비치는 흙을 쪼개 여러 곳에 나눠 보낼 수 있게 풀어 선형 계획 문제로 만들었고, 자원 배분에 관한 이런 연구로 1975년 미국의 경제학자 찰링 쿠프만스와 함께 노벨 경제학상을 받았습니다.

이어지는 곳. 바서슈타인 거리는 분포들 사이의 진짜 거리 함수⁠(metric)⁠입니다. 흙을 모두 한 점 c로 모을 때의 비용 $\sum_i a_i |x_i - c|$를 가장 작게 하는 c는 중앙값⁠(median)⁠이고, 거리 제곱으로 비용을 매기면 평균입니다. 같은 거리 제곱 비용으로 데이터를 점 k개짜리 분포로 가장 싸게 옮기는 문제의 답은 k-평균 군집⁠(k-means clustering)⁠의 답과 같습니다. 참 분포의 기댓값⁠(expected value)⁠이 유한하면, 표본⁠(sample)⁠으로 만든 분포는 표본이 늘수록 참 분포에 바서슈타인 거리로도 다가갑니다(큰 수의 법칙⁠(law of large numbers)⁠). 도시들을 잇는 그래프 위라면 칸 사이의 거리 대신 최단 경로⁠(shortest path)⁠의 길이가 비용이 되고, 문자열을 바꾸는 최소 비용인 편집 거리⁠(edit distance)⁠도 같은 생각입니다. 흙더미와 구덩이가 같은 크기의 덩이 n개씩이고 덩이를 쪼갤 수 없으면 문제는 짝짓기(배정 문제⁠, assignment problem⁠)가 됩니다. 모두에게 짝을 줄 수 있는지는 홀의 정리⁠(Hall's theorem)⁠가, 용량⁠(capacity)⁠이 정해진 관망으로 얼마나 보낼 수 있는지는 최대 흐름 최소 절단 정리⁠(max-flow min-cut theorem)⁠가 답하고, 비용 대신 양쪽이 서로에게 매긴 선호 순서를 따지면 안정 매칭⁠(stable matching)⁠이 됩니다.