Computational Optimal Transport 정독회 기록 (#18: 4.6)

2742 단어 math기계 학습

배경


  • 지난번 : Computational Optimal Transport 정독회 기록 (#17: 4.5) 은 7/31에 개최, 이번은 8/6에 개최
  • 직장에서 COT를 읽고 {자기만족, 복습, 미래를 위해} 등의 이유로 기록을 하고 있다

    • 마지막 회고와 이번 내용


  • 엔트로피 정규화된 최적화 문제
  • Primal (4.2) $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})$
  • Dual (4.30) $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$

  • 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)}}$

  • 엔트로피 정규화에서 풀린 해는 원래의 해에 대해 바운드되어 있어 사용할 수 있다(수렴하고 있으면)
  • 이번: 일반화 Sinkhorn


    • §4.6 Generalized Sinkhorn


  • Sinkhorn을 도입 한 § 4.2에서 Sinkhorn 알고리즘이 KL-div.의 Proj와 관련이 있다는 이야기를 썼다.
  • 비슷한 노선에서 일반화 된 Sinkhorn에 대해 논의한다. 구체적으로는 $P1_m = a, P^T 1_n = b$라는 지금까지의 제약이 함수 $F, G$로 일반화된 문제(4.49)를 논의한다. 이것은 지금까지와는 달리 $F$와 $G$가 들어가는 것으로 제약없이 최적화되어 있다. 예를 들어 $ F $와 $ G $를 지원 함수로 사용하면 동일합니다.

    • $$\text{(4.49): }\min_{P}\langle C, P\rangle -\varepsilon H(P) + F(P1_m) + G(P^T 1_n)$$
  • 흥미롭게도 (4.49)의 최적화 문제는 Sinkhorn과 동일한 해의 형태를 갖는다. 이것은 $P1_m=f, P^T1_n=g$ 등의 변수를 임시로 두고 라그랑지안을 생각하면, $P$에 대해 편미분을 하는 가정에서 지워지고, Sinkhorn의 해의 형태를 논의한 Prop 4.3(아마도 )와 동일한 식 변형이 가능하기 때문에.

  • 다양한 최근 논문 (Peyre 2015, Frogner et al. 2015, Chizat et al. 2019, Karlsson and Ringh 2016) 덕분에이 공식은 다음과 같은 해방으로 공식화됩니다.
  • $u\leftarrow\frac{1}{Kv}\mathrm{Prox}_F^\mathbf{KL}(Kv)$
  • $v\leftarrow\frac{1}{K^Tu}\mathrm{Prox}_G^\mathbf{KL}(K^Tu)$
  • 원래의 Sinkhorn이 $a, b$를 나눌 뿐이었던 부분이, Prox가 되었다


  • 프록스 정의
  • $\mathrm{Prox}_F^\mathbf{KL}(u) =\arg\min_{u'} KL(u'\mid u) + F(u')$
  • 표현식에서도 $ F $가 지시 함수 인 경우 $ u '= a $의 해만 존재하므로 Sinkhorn과 일치한다는 것을 알 수 있습니다.

  • 특히 증명 등은 나오지 않는다(논문 레벨)
  • argmin과 Prox의 성질로부터, 예를 들면 $F(u)=\sum_i F_i(u_i)$ 와 같이 element-wise로 되어 있을 때, Prox도 element-wise로 좋다

    • Remark 4.28 Duality and Legendre transform


  • 아무것도 모른다 (모집 : 르장돌에 익숙한 사람)



    • 코멘트


  • §4 Sinkhorn 완주! !

    • 다음


  • § 5, 6, 7 근처가 매우 힘들 것 같기 때문에, 토론 결과 다음은 § 9를 해 나간다
    • Computational Optimal Transport 정독회 기록 (#16: 4.4 Part 2)
    3x3의 ○×게임(세째 줄)의 모든 사건

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

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