Optimal Transport

# Optimal Transport

Optimal Transport
: 하나의 확률 분포를 다른 확률 분포로 옮기는데 필요한 비용 계산 문제 (두 확률간의 거리 측정)

• Transport Plan $\gamma(x,y)$: 두 분포 사이의 거리를 구하고, 각 점을 다른 점으로 어떻게 옮길지 정의
• Cost function $c(x,y)$ : 위치 $x$에서 위치 $y$로 물질을 옮길 때 드는 비용

 

---

# 두 확률 분포 간의 거리를 측정하는 방법

확률 변수 $X$, $Y$가 분포 $P$, $Q$를 갖고, 확률밀도함수를 각각 $p$,$q$라고 하자.

확률밀도함수 간의 거리를 측정하는 방법에는 아래와 같은 여러 방법들이 있다.

1. KL(Kullback-Leibler) Divergence

: 두 확률 분포 $P$와 $Q$간의 차이를 측정하는 비대칭적인 방법

: $P$가 $Q$로부터 얼마나 다른지에 대한 상대적인 엔트로피 차이 나타냄

$$D_{KL}(P \parallel Q) = \int P(x) \log \left( \frac{P(x)}{Q(x)} \right) \, dx$$

2. JS(Jensen-Shannon) Divergence

: KL의 대칭화된 버전, 두 분포의 평균을 기반으로 차이 측정

: $P$와 $Q$가 완전히 일치하면 JS는 0이되고, 최댓값은 1

$$D_{JS}(P \parallel Q) = \frac{1}{2} \left( D_{KL}(P \parallel M) + D_{KL}(Q \parallel M) \right)$$

$$M = \frac{1}{2}(P + Q)$$

3. Wasserstein Distance

: OT에서 나오는 거리로, 확률 질량을 분포 간에 옮기는 데 드는 최소 비용 측정

: 분포 간의 지리적 차이를 반영하여, 데이터가 연속적이거나 이미지와 같은 공간적 분포에서 사용하기 적합

  $$min_{\gamma\prod (P,Q)}\int c(x,y)d\gamma (x,y)$$

4. TV(Total Variation Distance) Distance

: 두 확률분포간의 최대 차이 측정

: 두 분포가 얼마나 겹치는지 나타냄, 완전히 일치하면 0이고 완전히 다르면 1

$$d_{TV}(P, Q) = \frac{1}{2} \int |P(x) - Q(x)| \, dx$$

5. Hellinger Distance

: 두 분포 간의 유사도 측정, 0--1의 값, 대칭적

: 분포가 같을 때 거리는 0, 완전히 다를 때 1

$$H(P, Q) = \frac{1}{\sqrt{2}} \left( \int \left( \sqrt{P(x)} - \sqrt{Q(x)} \right)^2 \, dx \right)^{1/2}$$

 

---

참고블로그

https://ddangchani.github.io/Optimal-Transport/

Optimal Transport

 

https://pythonot.github.io/auto_examples/plot_Intro_OT.html

Introduction to Optimal Transport with Python — POT Python Optimal Transport 0.9.4 documentation