자주 하는 실수와 요약
자주 하는 실수
| 실수 | 나온 문제 | 바로잡는 법 |
|---|---|---|
| 하나씩 차례로 가장 가까운 상대를 골라 짝지으면 전체도 최선이라고 봄 | 1, 3 | 앞에서 고른 쌍이 뒤의 쌍을 망칠 수 있다. 모든 쌍을 함께 놓고 비용 합을 최소로 한다(헝가리안 방법, 선형계획) |
| 짝마다 가장 싼 상대를 고르면 짝짓기가 된다고 봄 | 3 | 여럿이 같은 상대를 고를 수 있다. 짝짓기는 상대가 겹치지 않아야 한다 |
| 몽주 문제는 양이 달라도 풀린다고 봄 | 2 | 한 출발점을 쪼갤 수 없으면 양이 다른 경우 답이 없다. 나눠 보내기를 허락한 칸토로비치 문제로 바꾼다 |
| 자기에게 가장 싼 곳부터 채우면 운반비가 최소라고 봄 | 4 | 다른 출발점과 비교해 상대적으로 유리한 곳에 맡겨야 한다 |
| 나눠 보내기를 허락하면 몽주 문제보다 싼 답이 생긴다고 봄 | 5 | 양이 모두 같으면 어떤 계획도 짝짓기들의 가중평균이라 가장 싼 짝짓기보다 싸질 수 없다 |
| 미니배치 안에서 들어온 순서대로 한 짝짓기도 평균쯤은 된다고 봄 | 6 | 운이 나쁘면 엇갈림이 많은 짝짓기가 된다. 미니배치 안에서 수송 문제를 풀면 엇갈림이 사라진다 |
| 견적의 수입이 크면 좋은 견적이라고 봄 | 7 | 한 길이라도 φ + ψ 가 직접 나르는 비용을 넘으면 그 견적은 받아들여지지 않는다 |
| 쌍대의 값은 하나로 정해진다고 봄 | 8 | 모든 φ 에 상수를 더하고 모든 ψ 에서 같은 상수를 빼도 수입이 같다 |
| 흙을 더하면 최소 비용이 늘 늘어난다고 봄 | 9 | 늘어나는 양은 φᵢ + ψⱼ 이고 음수일 수 있다. 새 흙이 먼 길을 대신하면 비용이 준다 |
| 평균이 같은 두 분포는 바서슈타인 거리가 0이라고 봄 | 10 | 퍼진 모양이 다르면 옮겨야 할 흙이 있다. W₂ 는 멀리 옮기는 샘플이 있는지에 더 민감하다 |
| 거리 비용의 최소가 하나면 최적 짝짓기도 하나라고 봄 | 11 | 거리 비용(W₁)은 최적 짝짓기가 여럿일 수 있다. 제곱거리 비용(W₂)이 엇갈리지 않는 짝짓기 하나를 남긴다 |
| 비용이 최소인 짝짓기면 길도 엇갈리지 않는다고 봄 | 11 | 거리 비용의 최적 짝짓기 가운데에도 두 점이 한 점에서 만나는 짝짓기가 있다 |
| 같은 분포에서 뽑은 샘플 둘의 W₂ 는 0이라고 봄 | 12 | 샘플이 적으면 우연한 차이가 거리로 잡힌다. 샘플 수를 맞춰 견준다 |
| FID 가 0에 가까우면 두 분포가 같다고 봄 | 12 | FID 는 정규분포로 어림해 평균과 공분산만 본다 |
| 행 맞추기와 열 맞추기를 한 번씩 하면 둘 다 맞는다고 봄 | 13 | 열을 맞추면 행의 합이 다시 p에서 벗어난다. 행의 합과 p의 차이가 기준 밑으로 갈 때까지 번갈아 되풀이한다 |
| ε → 0 이면 싱크혼 계획이 늘 짝짓기 하나가 된다고 봄 | 14 | 최소 비용 계획이 여럿이면 그 가운데 엔트로피가 가장 큰 흐린 계획으로 간다 |
| ε 는 작을수록 좋다고 봄 | 14 | 작은 ε 는 바퀴 수가 크게 늘고 e−C/ε 가 0 으로 사라진다. 로그 영역에서 계산하고 알맞은 ε 를 고른다 |
| 그림마다 점수가 큰 묶음을 고르면 된다고 봄 | 15 | 묶음 하나로 몰리는 뻔한 답이 생긴다. 열의 합을 정해 싱크혼 반복으로 고르게 나눈다 |
요약
이 장에서 한 일을 정리해 보자. 한쪽 무더기를 다른 쪽 무더기로 옮기는 가장 싼 방법을 찾는 것이 최적 수송이다. 1781년 몽주는 공병의 흙 나르기를 「출발점마다 도착점 하나를 짝지어 비용 합을 최소로」라는 문제로 적었다. 이 몽주 문제는 짝짓기 n!가지 가운데 하나를 고르는 일이라 하나씩 셀 수는 없지만, 양이 모두 같으면 헝가리안 방법으로 풀린다. 물체 검출 모델 DETR은 예측과 정답을 짝짓는 데 이 방법을 쓴다.
출발점의 양을 여러 도착점으로 나눠 보내도 되게 한 것이 칸토로비치 문제다. 정할 것은 행의 합과 열의 합이 주어진 표 π 하나이고, 비용과 조건이 모두 1차식이라 선형계획으로 풀린다. 양이 달라도 답이 있고, 양이 모두 같으면 답은 몽주 문제의 짝짓기와 같다. 플로우 매칭의 미니배치 최적 수송은 미니배치 안에서 이 문제를 풀어 엇갈리지 않는 짝짓기를 정한다.
같은 문제를 장소마다의 값 φᵢ, ψⱼ로 다시 쓴 것이 쌍대 문제다. 모든 길에서 φᵢ + ψⱼ ≤ Cᵢⱼ를 지키면서 수입을 최대로 하면 그 최댓값이 최소 비용과 같다. 계획이 실제로 쓰는 길에서는 φᵢ + ψⱼ = Cᵢⱼ이고, φᵢ + ψⱼ는 그 출발점과 도착점에 한 단위를 더할 때 최소 비용이 늘거나 주는 양이다(최소 비용을 양으로 미분한 값).
두 분포 사이의 최소 수송 비용이 바서슈타인 거리다. 겹치지 않는 분포 사이에서도 얼마나 떨어졌는지를 알려 주고, 대칭이며 삼각부등식을 지킨다. 한 쌍의 비용을 거리로 잡은 W₁은 최적 짝짓기가 여럿일 수 있고, 거리의 제곱으로 잡은 W₂는 엇갈리지 않는 짝짓기 하나를 남긴다. 생성 모델 평가의 FID는 특징을 정규분포로 어림한 뒤 잰 W₂의 제곱이다.
마지막으로, 비용에 엔트로피 페널티를 더하면 답이 「길마다의 기본 비중 e−C/ε에 행마다, 열마다 수를 곱한 꼴」이 되고, 행의 합과 열의 합을 번갈아 맞추는 싱크혼 반복으로 구해진다. 행 맞추기 한 번은 「행의 합이 p인 표들」 위로의 KL 사영이고, 열 맞추기도 열에 대해 같다. ε가 크면 빠르고 흐리며, 작으면 선형계획의 답에 다가가지만 바퀴 수가 크게 는다.
막힌 곳
이 장의 분포는 모두 칸이 몇 개뿐인 히스토그램이었다. 칸토로비치 문제든 싱크혼 반복이든 출발점과 도착점을 하나하나 늘어놓을 수 있어야 풀린다. 그런데 생성 모델이 내놓는 그림의 분포는 칸을 늘어놓을 수 없을 만큼 큰데, 그 분포와 진짜 그림의 분포 사이의 바서슈타인 거리를 재려면 어떻게 해야 할까? 쌍대 문제에서 값 φ를 장소마다 하나씩 적는 대신 그림을 넣으면 값을 내놓는 함수로 둔다면, 조건 φᵢ + ψⱼ ≤ Cᵢⱼ는 그 함수에 어떤 제약이 될까? 그리고 생성 모델은 그 거리를 줄이려 하고 함수는 그 거리를 정확히 재려고 서로 반대쪽으로 학습한다면, 두 학습은 함께 한 점으로 모일까?