배경
지난번 : Computational Optimal Transport 정독회 기록 (#15: 4.3 2, 4.4 1) 은 7/16에 개최, 이번은 7/26에 개최 직장에서 COT를 읽고 {자기만족, 복습, 미래를 위해} 등의 이유로 기록을 하고 있다 마지막 회고와 이번 내용
엔트로피 정규화가 있는 운송 문제
$L^\varepsilon_C({\bf a}, {\bf b}) =\min_{{\bf P}\in U({\bf a},{\bf b})}\langle {\bf P}, C\rangle -\varepsilon H({\bf P})$ Sinkhorn 알고리즘 최고 → 제대로 수렴하고, 고속화할 수 있어. 안정화를 위해서는 Log 도메인이 필수입니다.
$\mathbf{u}^{(l+1)} =\frac{\mathbf{a}}{\mathbf{Kv}^{(l)}}$, $\mathbf{v}^{ (l + 1)} =\frac{\mathbf{b}}{\mathbf{K}^T\mathbf{u}^{(l + 1)}}$ 엔트로피 정규화된 듀얼 문제
$L_C^\varepsilon(a,b) =\max_{f, g}\langle f, a\rangle +\langle g, b\rangle -\varepsilon\langle\exp(f/\varepsilon), K\exp(g/\varepsilon)\rangle$ 이번: 상세를 확인해 간다 Remark 4.21
Sinkhorn 알고리즘은 $u, v$를 번갈아 갱신해 가므로, 이것을 block coordinate ascent로서 보자 각각 $f, g$에 대해 편미분하면 (4.33), (4.34)를 얻는다.
(4.33) $\nabla|_f Q(f, g) = a -\exp(f/\varepsilon)\odot (K\exp(g/\varepsilon))$ (4.34) $\nabla|_g Q(f, g) = b -\exp(g/\varepsilon)\odot (K^T\exp(f/\varepsilon))$ $ f $와 $ g $ 측을 각각 coordinate로 간주하고 번갈아 갱신하면 (4.35), (4.36)을 얻는다 예를 들면 식(4.33)=0으로 한 경우
$a =\exp(f/\varepsilon)\odot K\exp (g/\varepsilon)$ 양변의 로그를 취하여 $\varepsilon\log a = f +\varepsilon\log (K\exp(g/\varepsilon))$ $f$를 갱신하는 형태의 식으로 하면 $f^{(l+1)} =\varepsilon a -\varepsilon\log (K\exp(g^{(l)}/\varepsilon))$ → 식(4.35) Remark 4.22
갱신 식 (4.35)와 (4.36)은 block coordinate ascent로도 볼 수 있지만 soft-minimum으로도 볼 수있다 soft-min 정의 $$\min_\varepsilon\mathbf{z} = -\varepsilon\log\sum_i\exp(-\mathbf{z}_i/\varepsilon)$$
눈을 얇게 보면, 식(4.35), (4.36)의 갱신식은 soft-min을 하고 있다고 생각된다
soft-min 기호($\min_\varepsilon$)로 업데이트 식 다시 쓰기
(4.35)를 다시 쓴 (4.38): $f^{(l+1)}) =\min_\varepsilon\{ (C_{ij} -\mathbf{g}_j^{(l)})\} +\varepsilon\log a$
조금 기호가 수상할지도 모른다 (첨자) 이 작업을 쉽게 작성하기 위해 두 개의 연산자를 정의합니다 
이것을 사용하여 식 (4.40), (4.41)과 같은 갱신 식을 얻는다.
이것은 엔트로피 정규화가있는 C- 변환과 같은 조작입니다.
구현적인 이야기를 할 때 기계 학습에서 자주 나오는 log-sum-exp도 사용하십시오 다음
수식이 너무 많아 Qiita 에디터 입력이 번거롭습니다 다음은 § 4.5에 따라 근사 해법에 대해 다루어진다
Reference
이 문제에 관하여(Computational Optimal Transport 정독회 기록 (#16: 4.4 Part 2)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/takilog/items/0849d543bbdfd7a9c971
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
