【통계학】 Optimal Transport 및 Gromov-Wasserstein 거리 이해하기

Optimal Transport 및 Gromov-Wasserstein 거리(Kantorovich–Rubinstein metric, Earth Mover's Distance, EMD)

 

추천글 : 【통계학】 5-2강. 거리함수와 유사도 

---

1. 개요 [본문]

2. Kontorovich's problem [본문]

3. optimal transport plan [본문]

4. Wasserstein distance [본문]

5. 응용 [본문]

---

 

1. 개요 [목차]

⑴ 결합확률분포(결합확률질량함수, joint probability distribution; 커플링, coupling) 

① 이산확률변수 : X =｛x₁, ···, x_m｝, Y =｛y₁, ···, y_n｝에 대해, π(x_i, y_j) = π(X = x_i, Y = y_j)인 함수 π(x, y)

② 연속확률변수 : ∂²F(x, y) / ∂x ∂y = π(x, y)인 함수 π(x, y)

③ 성질 1. π(x, y) ≥ 0

④ 성질 2. ∑∑ π(x, y) = 1

⑵ 주변확률분포(marginal probability distribution)

① 정의 : 결합확률분포를 확률변수 X 또는 Y만의 분포로 바꾼 것

② 이산확률분포의 주변확률분포

 

 

③ 연속확률분포의 주변확률분포

 

 

 

2. Kontorovich's problem [목차]

⑴ 정의 : X의 확률분포 (i.e., π_X), Y의 확률분포 (i.e., π_Y), 비용함수 (i.e., c(x, y))가 주어져 있을 때, 비용의 기댓값이 최소가 되는 결합확률분포 π를 찾는 문제

① X를 source, Y를 target이라고 함

 

Figure. 1. Kontorovich's problem

 

⑵ 가정 : X와 Y 간의 함수 관계가 존재해야 함 (∵ π(x, y)가 실질적으로 의미를 가져야 하므로)

⑶ π_X 대신 {x₁, x₂, ···, x_n}처럼 조건이 주어지기도 함 (단, π_X=x1 = π_X=x2 = ··· = π_X=xn)

⑷ 예시 : {x₁, x₂, ···, x_n}, {y₁, y₂, ···, y_n}이 주어져 있을 때 가까운 것끼리 pair로 매칭시켜주는 문제 

 

출처 : 이미지 클릭

Figure. 2. Kontorovich's problem의 예시

 

⑸ Kantorovich-Rubinstein duality (KD) problem도 위 정의식을 변형한 것에 불과함 

 

 

3. optimal transport plan [목차]

⑴ 정의 : Kontorovich's problem의 해로 convex 함

 

 

⑵ 해의 존재성 : lower semicontinuous와 같은 mild한 조건 하에 항상 존재함

⑶ 해를 구하는 방법

① north west corner method 

② Vogel's approximation method 

③ least-cost method 

④ 기타 수치해석 기법

⑷ 예 1. 수요와 공급이 고정돼 있을 때 자원을 어떻게 분배하는 게 좋을지를 결정할 수 있음

 

출처 : 이미지 클릭

Figure. 3. 경제학에서의 optimal transport plan

 

⑸ 예 2. 연속변수, 이산변수에 따른 optimal transport plan의 차이

 

출처 : 이미지 클릭

Figure. 4. 연속변수, 이산변수에 따른 optimal transport plan의 차이

 

 

4. Wasserstein distance [목차]

⑴ 비용함수 c(x, y)를 유클리드 거리 d(x, y)로 갖는 특수한 Kontorovich's problem 상황에서의 비용함수의 기댓값

① 거리와 같은 단위를 갖는 거리의 기댓값이 도출됨 

 

 

 

② 모래산을 한 장소에서 다른 장소로 옮길 때, 그 형태가 얼마나 변형되었는지를 측정하는 것이 바로 Wasserstein 거리임

 

출처 : DALL∙E

Figure. 5. 모래산을 옮기는 과정

 

⑵ metric space가 다른 두 표본 집단의 거리를 구할 수도 있음

① 예 : X는 2차원 데이터포인트의 집합이고, Y는 3차원 데이터포인트의 집합인 경우 

⑶ 예시 : WGAN(Wasserstein generative adversarial neural network)

 

 

5. 응용 [목차]

⑴ 응용 1. p-th order Wasserstein distance : p차 적률(p-th moment, p ≥ 1)을 이용한 뒤 1/p 승을 하여 유클리드 거리와 같은 단위를 갖는 거리의 기댓값이 도출됨

 

 

⑵ 응용 2. partial Wasserstein distance : X와 Y의 일부만 가지고 Wasserstein distance를 구하는 경우

① 예 1. X = {x₁, x₂, ···, x_n}, Y = {y₁, y₂, ···, y_n}을 예시로 생성하고, 2D-partial Wasserstein distance를 구하는 코드 (ref)

 

plot_partial_wass_and_gromov.ipynb

0.01MB

 

⑶ 응용 3. entropic Wasserstein distance : product measure (i.e., X ⊗ Y), 상대 엔트로피(Kullback-Leibler divergence) 도입

 

 

① entropic Wasserstein distance를 Sinkhorn divergence라고도 함

② 장점 1. Kontorovich's problem을 미분가능하게 만들어 gradient-based optimazation method 등을 사용할 수 있음

③ 장점 2. 𝝐을 도입하여 optimal transport plan을 조절할 여지를 둠 

⑷ 응용 4. robust Wasserstein distance : c(x, y) 대신 c_λ(x, y) = min { c(x, y), 2λ }를 사용

⑸ 응용 5. Sinkhorn-Knopp algorithm : 비용함수를 normalize 함으로써 optimal transport에서 ultra-fast optimization을 가능케 함

⑹ 응용 6. collective OT (COT) : 다양한 pair에 대한 optimal transport를 한꺼번에 최적화하는 기법 (e.g., COMMOT) 

 

Figure. 6. COMMOT 모식도

 

 

입력: 2023.11.04 02:09