【통계학】 Gromov-Wasserstein distance 이해하기

Gromov-Wasserstein distance(Kantorovich–Rubinstein metric, Earth Mover's Distance, EMD)

 

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

---

1. 개요 [본문]

2. 코드 [본문]

---

 

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만의 분포로 바꾼 것

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

 

 

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

 

 

⑶ Kontorovich's problem

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

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

② 가정 : 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. 1. Kontorovich's problem의 예시

 

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

⑷ optimal transport plan 

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

 

 

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

③ 해를 구하는 방법

○ north west corner method 

○ Vogel's approximation method 

○ least-cost method 

○ 기타 수치해석 기법

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

 

출처 : 이미지 클릭

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

 

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

 

출처 : 이미지 클릭

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

 

⑸ Wasserstein distance 

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

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

 

 

 

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

 

출처 : DALL∙E

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

 

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

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

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

⑹ 응용 

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

 

 

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

③ 응용 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을 가능케 함

 

 

2. 코드 [목차]

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

 

plot_partial_wass_and_gromov.ipynb

0.01MB

 

입력: 2023.11.04 02:09