Computational Optimal Transport 정독회 기록 (#13: 4.2 3)

배경

직장에서 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 알고리즘 최고

$\mathbf{u}^{(l+1)} =\frac{\mathbf{a}}{\mathbf{Kv}^{(l)}}$, $\mathbf{v}^{ (l+1)} =\frac{\mathbf{b}}{\mathbf{K}^T\mathbf{u}^{(l + 1)}}$

Hilbert projective metric은 축소 매핑입니다 (Theorem 4.1)

이번 : Sinkhorn 알고리즘의 수렴성에 대해 Hilbert projective metric의 축소 매핑을 사용하여 논의한다

지난번 이후

Remark 4.13 페론 플로베니우스 정리

조금 기분 전환하고(거짓말), 선형 대수나 페이지 랭크의 이야기로 나오는 Perron-Frobenius의 이야기에 가는 길

CS 적으로는 마르코프 체인이 정상 분포에 수렴한다는 말을 할 때 나온다

마르코프 체인은 한 벡터에 전이 확률 행렬 (이중 확률 행렬)을 곱하면 수렴한다는 이야기

Sinkhorn과 유사 (중요)

고유 벡터를 고려하면 $\mathbf{K}p^* = p^*$

따라서 적절한 초기 값 $p_0$에 $l$회 $K$를 적용한 결과 어떻게 되는지를 논의할 수 있다

$d(\mathbf{K}^lp_0, p^\star) = d(\mathbf{K}^lp_0,\mathbf{K}^lp^\star)\leq\lambda(K)^l d (p_0, p_\star)$

부등식은 Theorem 4.1에서

축소 맵의 동작 이미지가 찍혀있다

주장 : $ l $ 회 Sinkhorn 알고리즘을 적용하면 (4.22), (4.23), (4.24)가 성립한다. 각각 다음과 같은 식.

$ d (v, v ') $의 정의에서, 이것은 다음과 같이 변경 되더라도

$v, v'$는 $m$ 차원 벡터로 한다(굵게 되어 있지 않은 것은 귀찮으니까)

$d(v, v') = d(v/v', 1_m) = d(1_m/v, 1_m/v')$

Sinkhorn 알고리즘의 업데이트 식 (위쪽에 쓰여짐)에서 $d(u^{(l+1)}, u^\star) = d(Kv^{(l)}, Kv^\star)\leq\lambda(K) d(v^{(l)}, v^\star)$

이것은 $v\to u$의 이야기이므로, 한 번 더 Sinkhorn 알고리즘의 분을 전개하면, $u\to v\to u$로 갱신할 때 $\lambda(K)$는 $2l $의 순서로 기여한다. 따라서 (4.22)를 얻는다.

식 (4.23)은 삼각 부등식으로부터 얻을 수있다

식 (4.24)는 어렵기 때문에 자세한 내용은 논문 참조이다

식이 잘못 된 것 같습니다 (4.25)

어렵고 몰랐다

§4.3으로 진행합시다

이 문제에 관하여(Computational Optimal Transport 정독회 기록 (#13: 4.2 3)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/takilog/items/dbad32096ba11471fbad

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다