[기계 학습] 최고의 운송과 POT 라이브러리에 대해

개시하다
운송에 가장 적합한 개념을 배웠기 때문에 자신의 이해를 위해 필기를 간단하게 정리했다.
최적 운송 정보
확률 분포를 비교하는 방법으로 쓸 수 있다.이동 확률로 분포된 산을 통해 일치에 필요한 원가를 달성한다.이하 상황의 확률 분포μ0에서 확률로 분포μ산을 1로 옮겼을 때는 모래산처럼 움직이는 느낌이었다.μ0의 모든 위치에서μ1의 어디든지 옮길 수 있지만 가장 효율적인 이동 방식이 가장 적합한 운송 방식이다.

인용자 Transportation theory (mathematics), Wikipedia
이산 분포 사이의 최적 전송 거리의 공식화
입력

비교의 이산분포

\mu_0 = \{a_1,a_2,...,a_m\},  \mu_1 =\{b_1,b_2,...,b_n\}

각 점의 거리 비용을 나타내는 행렬

M \in \mathbb{R}^{m \times n}_{+}

출력: 최적 수송 거리
최적 전송 거리를 다음 최적화 문제의 최적 값으로 정의합니다. $\gamma^* 달러입니다.
여기 있습니다.{ij}달러는 i에서 j까지의 운송 원가를 나타낸다.

\gamma^* = \underset{\gamma\in\mathbb{R}^{n \times m}_+}{arg\mathrm{min}}\sum_{i,j}^n\gamma_{i,j}M_{i,j}\\


\mathrm{s.t.} \quad M_{ij} \geq 0,\forall i,j, \quad \sum_{j=1}^m\gamma_{ij}=\mu_0,\forall i,\quad\sum_{i=1}^n\gamma_{ij}=\mu_1,\forall j

또한 KL 분집은 두 확률 분포의 비교에도 사용된다.P와 Q의 두 확률 분포가 존재할 때 다음은 이산 분포할 때의 KL 분집의 정의이다.

D_{KL}(p||q) = \sum_i{P(i)\log\frac{P(i)}{Q(i)}}

KL 분집은 pythonscipy.special.kl_div에서 계산할 수 있습니다.
그러나 KL 분집은 각 요소에 독립적으로 항목을 더한 관계이기 때문에 때때로 적당한 비교를 할 수 없다.최상의 운송 아이디어라면 요소 간 거리를 잘 정의하고 다른 요소를 고려해 비교할 수 있어 비교를 더 잘할 수 있다.그러나 최상의 운송은 KL의 계산 원가보다 높다는 것을 주의해야 한다.
또 이산 분포 상황에서 선형 계획이 되면 기존의 POT 등 라이브러리로 풀 수 있다.연속 분포된 상황에서 사랑을 나누었지만 직접적으로 해결하기 어렵다. 상응하는 연속 분포에서 샘플을 채취하여 점조 비교로 돌아가 해결하도록 한다.
POT 라이브러리 정보
최상의 운송 문제는 POT 라이브러리를 통해 해결할 수 있다.설치는 POT: Python Optimal Transport와 같이 pip를 통해 설치할 수 있다.
POT는 이전에 이산 분포 시 선형 계획 최적화 문제를 해결하는 해답기를 실현했다.emd(a, b, M) 호출 시 최적 수송 매트릭스γ*되돌아오다a와 b는 질량 히스토그램이고 M은 거리 행렬이다.또한 M은 2개의 분포를 입력하여 POT 라이브러리에서 계산할 수 있다.
경을 베껴 보아라quick start의 2D Optimal transport between empirical distributions.

import numpy as np
import matplotlib.pylab as pl
import ot
import ot.plot

n = 100 # 各分布のサンプル数

#1つ目の分布パラメータ
mu_s = np.array([0, 0])
cov_s = np.array([[1, 0], [0, 1]])

#2つ目の分布パラメータ
mu_t = np.array([4, 4])
cov_t = np.array([[1, -.8], [-.8, 1]])

#2Dガウス分布で作成それぞれの分布を作成
xs = ot.datasets.make_2D_samples_gauss(n, mu_s, cov_s)
xt = ot.datasets.make_2D_samples_gauss(n, mu_t, cov_t)
#各点の重さ。今回は全て1/nとしている
a, b = np.ones((n,)) / n, np.ones((n,)) / n 

# 距離を定義する
# ot.distで、xsとxtの距離行列を計算する。
# https://pythonot.github.io/all.html?highlight=dist#ot.dist
M = ot.dist(xs, xt) 
M /= M.max()

#作成した2つの分布を可視化
pl.figure(1)
pl.plot(xs[:, 0], xs[:, 1], '+b', label='Source samples')
pl.plot(xt[:, 0], xt[:, 1], 'xr', label='Target samples')
pl.legend(loc=0)
pl.title('Source and target distributions')

#計算した距離行列の可視化
pl.figure(2)
pl.imshow(M, interpolation='nearest') #２次元配列を画像として表示
pl.title('Cost matrix M')

#最適輸送行列の計算
G0 = ot.emd(a, b, M)

#最適輸送行列の可視化。前と後の対応関係がわかる。
pl.figure(3)
pl.imshow(G0, interpolation='nearest') #２次元配列を画像として表示
pl.title('OT matrix G0')

#2つの分布図に対しての輸送対応を可視化
pl.figure(4)
ot.plot.plot2D_samples_mat(xs, xt, G0, c=[.6, .6, .6]) #見やすさのため、サンプルと線の色を変えました。
pl.plot(xs[:, 0], xs[:, 1], '+b', label='Source samples')
pl.plot(xt[:, 0], xt[:, 1], 'xr', label='Target samples')
pl.legend(loc=0)
pl.title('OT matrix with samples')

우선, 두 분포의 가장 좋은 운송에 관해서는 이 견본 코드를 참고하여 적당히 교체하면 된다.
최후
최우선 운송 계산 알고리즘의 연구 동향에 따르면 색상 변환과 모양 변환 등 이미지 프로세싱 시스템의 응용, 언어 프로세싱 시스템, 데이터 생성과 데이터 보완 등에도 활용되는 등 소품으로도 흥미롭다.
문헌 목록

Transportation theory (mathematics), Wikipedia

POT: Python Optimal Trnasport

R ́emi Flamary, POT: Python Optimal Transport, Journal of Machine Learning Research 22 (2021) 1-8

KL 분집

횡정 선생님, 최고의 운송 방법

조토 씨, 최상의 운송 해결 방법

IBIS2021의 자습서

최우선 운송 계산 알고리즘의 연구 동향