와서스타인 거리

1. 개요[편집]

와서스타인 거리 Wasserstein Distance
다른 이름	칸토로비치-루빈시테인 거리, earth mover's distance
정의	최소 수송비의 p제곱근
정체	확률측도 공간 위의 진짜 거리 (발산이 아니다)
1차원	분위수함수 차이의 적분 — 정렬 한 번, O(n log n)
가우시안	뷔레-와서스타인 닫힌 형태 (FID 의 정체)
KL 대비	지지집합이 안 겹쳐도 유한하고 기울기가 산다
대가	표본 수렴률 n−1/d, 계산비용 O(n³ log n)

와서스타인 거리는 두 확률측도 사이의 최적수송 비용으로 정의한 거리다. $p \ge 1$ 과 거리공간 $(\mathcal{X},d)$ 위의 측도 $\mu,\nu$ 에 대해

$$W_p(\mu,\nu) \;=\; \left( \inf_{\pi \in \Pi(\mu,\nu)} \int_{\mathcal{X}\times\mathcal{X}} d(x,y)^p \, d\pi(x,y) \right)^{1/p}$$

로 정의한다. $\Pi(\mu,\nu)$ 는 주변분포가 각각 $\mu,\nu$ 인 결합측도(수송 계획) 전체다. 최적수송 문제 자체 — 몽주 형태, 칸토로비치 완화, 브레니에 정리 — 는 최적수송 문서가 다루고, 여기서는 이 양이 왜 거리이고, 통계와 기계학습에서 무엇을 대체했는가만 본다.

한 줄로 요약하면 이렇다. 쿨백-라이블러 발산이 “두 분포가 같은 곳에서 얼마나 다른가”를 재는 수직 방향의 양이라면, 와서스타인 거리는 “질량을 얼마나 멀리 옮겨야 하는가”를 재는 수평 방향의 양이다. 이 각도 차이 하나가 겹치지 않는 분포·저차원 다양체 위의 데이터·생성모형 학습에서 판을 바꿨다.¹

2. 왜 “거리”인가[편집]

발산이 아니라 진짜 거리라는 것이 이 양의 첫 번째 자산이다. $p$ 차 적률이 유한한 측도 전체 $\mathcal{P}_p(\mathcal{X})$ 위에서 다음이 모두 성립한다.

• 비음성·동일성: $W_p \ge 0$ 이고, $W_p(\mu,\nu)=0 \iff \mu=\nu$. (수송비가 0이려면 $\pi$ 가 대각선에 몰려야 한다.)
• 대칭성: $d$ 가 대칭이므로 $\pi$ 를 뒤집으면 끝.
• 삼각부등식: $W_p(\mu,\lambda) \le W_p(\mu,\nu) + W_p(\nu,\lambda)$. 증명에 접합 보조정리(gluing lemma)가 쓰인다 — $\mu\to\nu$ 계획과 $\nu\to\lambda$ 계획을 중간 변수에서 이어 붙여 3변수 결합측도를 만든 뒤 민코프스키 부등식을 때린다. “짐을 중간 창고에 들렀다 보내는 것이 직행보다 싸지 않다”는 당연한 사실의 형식화다.

거리이므로 쿨백-라이블러 발산이나 브레그만 발산과 달리 비대칭성·삼각부등식 부재를 걱정할 필요가 없다. 대신 브레그만 계열이 공짜로 주던 것들 — 닫힌 형태, 지수족과의 궁합, 삼점 항등식 — 은 전부 포기해야 한다.

두 번째 자산은 위상이다. $\mathcal{P}_p$ 위에서

$$W_p(\mu_n,\mu)\to 0 \quad\Longleftrightarrow\quad \mu_n \rightharpoonup \mu \ \text{(약수렴)} \ \text{ 그리고 } \int \|x\|^p d\mu_n \to \int \|x\|^p d\mu$$

즉 와서스타인 거리는 약수렴을 거리화한다(적률 수렴을 덤으로 요구하면서). $\mu_n = \delta_{1/n}$ 이 $\delta_0$ 로 가는 상황을 KL이나 총변동 거리는 전혀 감지하지 못하고 영원히 최대값을 뱉지만, $W_p(\delta_{1/n},\delta_0) = 1/n \to 0$ 이다. 점질량과 연속밀도를 한 공간에서 비교할 수 있다는 뜻이며, 라돈 측도 공간에서 최적화하는 문제들이 이 거리를 채택하는 이유다.

3. 닫힌 형태가 있는 두 경우[편집]

일반적으로 $W_p$ 는 LP를 풀어야 나오지만, 실무를 먹여 살리는 예외가 둘 있다.

(1) 1차원. $\mathcal{X}=\mathbb{R}$ 이면 최적 사상은 단조 재배열이고(브레니에 정리의 1차원 판), 답은 분위수함수의 차이로 떨어진다.

$$W_p^p(\mu,\nu) = \int_0^1 \bigl| F_\mu^{-1}(t) - F_\nu^{-1}(t) \bigr|^p \, dt$$

$p=1$ 이면 부분적분으로 누적분포함수 자체의 차이가 된다: $W_1 = \int_{\mathbb{R}} |F_\mu(x) - F_\nu(x)|\,dx$. 표본 $n$ 개씩 두 벌이면 양쪽을 정렬해 순서대로 짝지어 주는 것이 최적해다. 즉 $O(n\log n)$ — 최적화 문제가 통째로 정렬 한 번으로 붕괴한다. 슬라이스드 와서스타인이 이 사실 하나에 기생해서 산다.

(2) 가우시안. $\mu=\mathcal{N}(m_0,\Sigma_0)$, $\nu=\mathcal{N}(m_1,\Sigma_1)$ 이고 $p=2$ 면

$$W_2^2(\mu,\nu) = \|m_0-m_1\|^2 + \operatorname{tr}\!\left( \Sigma_0 + \Sigma_1 - 2\bigl(\Sigma_0^{1/2}\Sigma_1\Sigma_0^{1/2}\bigr)^{1/2} \right)$$

공분산 항을 뷔레-와서스타인 거리라 부르며(원래는 양자정보에서 밀도행렬 사이의 거리로 나온 뷔레 거리다), 최적 사상은 선형 $T(x)=m_1 + A(x-m_0)$, $A = \Sigma_0^{-1/2}(\Sigma_0^{1/2}\Sigma_1\Sigma_0^{1/2})^{1/2}\Sigma_0^{-1/2}$ 다. 생성모형 평가지표 FID(Fréchet Inception Distance)는 특징벡터 분포를 가우시안으로 근사한 뒤 이 공식을 그대로 쓴 것이다 — 이름은 프레셰지만 계산되는 양은 뷔레-와서스타인이다.² 행렬 제곱근이 들어가 있어 특징 차원이 2048쯤 되면 특이값 분해 비용이 만만치 않다는 점만 유의.

4. KL·총변동과의 대비 — WGAN이 나온 이유[편집]

이 문서에서 가장 자주 인용되는 예시. 실수선 위에서 $\mu = \delta_0$, $\nu_\theta = \delta_\theta$ 를 비교하자.

양	$\theta \ne 0$	$\theta = 0$	$\theta$ 에 대한 기울기
KL	$+\infty$	0	없음
젠센-섀넌	$\log 2$	0	0 (상수 구간)
총변동	1	0	0
$W_1$	$\lvert\theta\rvert$	0	$\operatorname{sgn}\theta$

지지집합이 겹치지 않는 순간 KL은 무한대로 터지고 JS·TV는 상수로 포화한다. 둘 다 $\theta$ 를 어느 쪽으로 움직여야 하는지에 대한 정보를 하나도 주지 못한다. 반면 $W_1$ 은 유한하고, 무엇보다 기울기가 살아 있다. 고차원 데이터가 저차원 다양체 위에 놓여 있고 생성기의 출력도 저차원 다양체라면 두 지지집합이 겹칠 확률은 사실상 0이므로, 이 차이는 이론적 취향이 아니라 학습이 되느냐 마느냐의 문제가 된다.

아르욥스키 등(2017)의 WGAN은 이 관찰을 그대로 구현한 것이다. $p=1$ 일 때 칸토로비치 쌍대는 특별히 깔끔한 꼴이 된다(칸토로비치-루빈시테인 쌍대).

$$W_1(\mu,\nu) = \sup_{\|f\|_{\mathrm{Lip}} \le 1} \left( \int f\,d\mu - \int f\,d\nu \right)$$

$c$-변환 조건이 여기서는 ”$f$ 가 1-립시츠”로 붕괴하고, $\psi = -\varphi$ 로 놓을 수 있어 함수가 하나만 남는다. 그래서 판별자(비평가, critic)를 1-립시츠 신경망 족으로 제한해 위 최댓값을 근사하면 된다(신경망 족은 1-립시츠 함수 전체보다 작으므로 결과는 언제나 $W_1$ 의 하한이다). 문제는 립시츠 제약을 어떻게 강제하느냐이고, 그 역사가 곧 WGAN 계열의 역사다.

• 가중치 클리핑(원 논문): 파라미터를 $[-c,c]$ 로 잘라 낸다. 되긴 되는데 $c$ 에 극도로 예민하고, 크면 기울기 폭발·작으면 소실이라 비평가가 사실상 저용량 함수로 퇴화한다. 저자들 본인이 “명백히 끔찍한 방법”이라고 적어 놨다.
• 기울기 벌점(WGAN-GP, 굴라자니 등 2017): 최적 비평가가 최적 수송 경로를 따라 기울기 노름이 정확히 1이라는 성질을 이용해, 실제·생성 표본을 잇는 선분 위의 점 $\hat{x}$ 에서 $\lambda\bigl(\|\nabla_{\hat x} f(\hat x)\|_2 - 1\bigr)^2$ 을 벌점으로 붙인다. 제약을 하드하게 걸지 않고 소프트하게 유도하는 전형적인 벌점법.
• 스펙트럼 정규화: 각 층의 가중치를 최대 특이값으로 나눠 층별 립시츠 상수를 1로 묶는다. 벌점보다 싸고 안정적이라 널리 쓰인다. 다만 층별 곱이 전체 립시츠 상수의 상한일 뿐이라 보수적이다.

주의할 점 하나. WGAN이 실제로 최소화하는 것은 $W_1$ 이 아니라 제한된 함수족 위의 하한이다. 비평가가 최적에 못 미치면 그 값은 진짜 와서스타인 거리가 아니고, “WGAN 손실이 내려가니 분포가 가까워지고 있다”는 해석도 그만큼만 유효하다.³

5. 계산 비용, 그리고 그 우회로[편집]

정확한 $W_p$ 계산은 $n$ 점 대 $n$ 점에서 대략 $O(n^3\log n)$ 이다. 이 벽을 도는 방법이 셋 있고, 실무는 셋 다 쓴다.

슬라이스드 와서스타인. 1차원이 공짜라는 사실을 극한까지 활용한다. 단위구 위의 방향 $\theta$ 로 두 측도를 사영한 뒤 1차원 $W_p$ 를 재고, 방향에 대해 평균낸다.

$$\mathrm{SW}_p^p(\mu,\nu) = \int_{S^{d-1}} W_p^p\bigl(\theta_\#\mu,\ \theta_\#\nu\bigr)\, d\sigma(\theta)$$

이것도 거리 공리를 만족하는 진짜 거리이고, $L$ 개 방향을 몬테카를로로 뽑으면 비용이 $O(Ln\log n)$ 이다. 게다가 표본 수렴률이 차원에 덜 시달린다. 대가는 $\mathrm{SW}_p \le C\, W_p$ 쪽 부등식은 쉬워도 반대 방향이 차원 의존 상수를 달고 나온다는 것, 그리고 고차원에서 무작위 방향 대부분이 아무 정보도 안 준다는 것(그래서 최대-슬라이스 변형이 나왔다).

엔트로피 정규화. 목적함수에 엔트로피를 얹어 싱크혼 반복으로 근사한다. 반복당 $O(n^2)$, GPU 친화적, 무엇보다 미분 가능. 자세한 것은 엔트로피 정규화 문서.

저차원 투영·부분표본. 특징을 줄이거나 미니배치 안에서만 계산한다. 미니배치 와서스타인은 편향된 추정량이라는 점을 잊으면 안 된다 — 배치 크기가 작으면 진짜 거리보다 체계적으로 크게 나온다.

여기서 근본적인 제약 하나를 못 박아 둘 필요가 있다. 표본 $n$ 개로 추정한 $W_p(\hat\mu_n,\mu)$ 는 차원 $d$ 에 대해 대략 $n^{-1/d}$ 로만 줄어든다($d > 2p$ 일 때). $d=10$ 이기만 해도 오차를 절반으로 줄이려면 표본이 $2^{10}\approx1000$ 배 필요하다는 뜻이다. 이 저주는 알고리즘을 바꿔서 피할 수 있는 게 아니라 거리 자체의 성질이며, 슬라이스드·엔트로피 변형이 $n^{-1/2}$ 급 수렴률을 갖는 것은 다른 양을 재기 때문이지 계산을 잘해서가 아니다.

6. 와서스타인 중심[편집]

$K$ 개의 측도 $\nu_1,\dots,\nu_K$ 와 가중치 $\lambda_k$ 에 대해

$$\bar{\mu} = \arg\min_{\mu}\ \sum_{k=1}^K \lambda_k\, W_2^2(\mu,\nu_k)$$

를 와서스타인 중심(barycenter)이라 한다. 아게·카를리에(2011)가 존재·유일성 조건을 정리했다. 유클리드 평균과 결정적으로 다른 점은 모양이 뭉개지지 않는다는 것이다. 위치만 다른 두 개의 뾰족한 봉우리를 산술평균하면 봉우리 두 개짜리 분포가 나오지만, 와서스타인 중심은 가운데에 봉우리 하나를 만든다. 형상 보간·색 팔레트 평균·센서 융합에서 이 성질이 곧바로 값을 한다.

가우시안들의 중심은 고정점 방정식

$$\Sigma = \sum_k \lambda_k \bigl(\Sigma^{1/2}\Sigma_k\Sigma^{1/2}\bigr)^{1/2}$$

으로 반복해 구할 수 있다. 일반적인 이산 측도는 사정이 나쁘다 — 정확한 중심 계산은 차원이 입력의 일부일 때 NP-난해임이 알려져 있고, 지지점을 미리 고정한 격자 위에서 싱크혼 반복을 돌리는 근사가 실무 표준이다. 지지점 위치까지 최적화하면 비볼록 문제가 되어 국소해에 빠진다.

7. 통계와 검증에서의 쓸모[편집]

• 두 표본 검정. 1차원에서는 $W_1$·$W_2$ 통계량이 그대로 검정통계량이 된다. 크라메르-폰 미제스류와 사촌지간이지만, 분포의 위치 차이에 민감하고 꼬리에서의 미세한 밀도 차이에는 둔하다는 성격이 다르다. 순열 검정으로 영분포를 잡는 것이 안전하다.
• 모형 검증(V&V). 시뮬레이션 앙상블과 실험 데이터의 분포를 통째로 비교할 때, 평균·분산만 맞춰 보는 것보다 정보량이 많다. 다만 위 표본 수렴률 때문에 표본 수가 수십 개인 전형적 실험 데이터에서는 신뢰구간을 반드시 붙여야 한다.
• 분포적 강건 최적화. “관측된 경험분포에서 와서스타인 반경 $\varepsilon$ 이내의 모든 분포에 대해 최악의 손실을 최소화한다”는 정식화가 표준이 됐다. 이 문제의 쌍대가 원래 손실에 립시츠 정규화를 붙인 꼴로 떨어진다는 결과 덕에 계산이 감당 가능해진다.
• 거리 사이의 부등식. $W_1(\mu,\nu) \le \operatorname{diam}(\mathcal{X})\cdot \mathrm{TV}(\mu,\nu)$ 이고, $p\le q$ 면 $W_p \le W_q$ 다(횔더). 반대로 $W_2$ 를 KL로 상계하는 수송 부등식(탈라그랑 $T_2$, $W_2^2 \le \tfrac{2}{\rho}\mathrm{KL}$)은 기준측도가 로그-소볼레프 부등식을 만족할 때만 성립한다 — 가우시안 근처에서는 되고 일반적으로는 안 된다. “와서스타인이 KL보다 항상 약하다”는 표현은 대충 맞지만 정리로 쓰려면 조건을 챙겨야 한다.
• 최대 평균 불일치와의 비교. 커널 기반 MMD는 표본 수렴률이 $n^{-1/2}$ 로 차원에 강하고 계산도 $O(n^2)$ 로 싸다. 대신 대응 관계를 주지 않고, 커널 대역폭 선택이 곧 기하 선택이 된다. “대응표가 필요하냐, 검정 통계량만 필요하냐”가 실무의 갈림길.

8. 관련 문서[편집]

• 최적수송 · 엔트로피 정규화 · 라돈 측도
• 쿨백-라이블러 발산 · 브레그만 발산 · 젠센-섀넌 발산
• 헝가리안 알고리즘 · 선형계획법 · 이분 매칭
• 생성적 적대 신경망 · 변분 오토인코더 · 심층 학습
• 특이값 분해 · 벌점법 · 볼록 최적화
• 정보 기하 · 중심극한정리 · k-평균 군집화

9. Footnotes[편집]

1. 이름 표기는 난장판이다. 러시아 수학자 바세르시테인(Vaseršteĭn)의 이름을 영어권에서 Wasserstein으로 옮겨 적은 것이 굳었고, 정작 이 거리를 만든 것은 최적수송의 칸토로비치다. 러시아 문헌은 대체로 칸토로비치 거리라 부르고, 영상처리 쪽은 earth mover’s distance(EMD)라 부르며, 셋이 같은 물건이라는 걸 몰라서 20년쯤 각자 논문을 쓴 역사가 있다. ↩

2. FID의 “프레셰”는 프레셰 거리(두 확률분포 사이의 프레셰 거리 = 가우시안일 때 $W_2$)에서 왔다. 즉 이름 자체는 틀리지 않았는데, 실제로 계산되는 식은 뷔레 형태이고 가우시안 가정이 들어가 있다는 점이 자주 잊힌다. 특징 분포가 가우시안과 거리가 멀면 FID 값의 차이는 “생성 품질”이 아니라 “3차 이상 적률의 차이를 못 본 결과”일 수 있다. ↩

3. 그래서 WGAN 논문의 “손실이 샘플 품질과 상관된다”는 주장은 비평가가 충분히 학습됐을 때에 한한다. 비평가 반복수를 5로 두라는 그 유명한 하이퍼파라미터가 사실상 “쌍대 문제를 얼마나 성실히 푸느냐”의 손잡이인 셈이다. 대충 풀면 그냥 이상한 손실 함수가 된다. ↩