Computational Optimal Transport 정독회 기록 (#14: 4.3 1)

1897 단어 math기계 학습

배경


  • 지난번 : Computational Optimal Transport 정독회 기록 (#13: 4.2 3) 은 6/28에 개최, 이번은 7/4에 개최
  • 직장에서 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)}}$

  • 이번: Sinkhorn 알고리즘의 가속


  • §4.3 Speeding Up Sinkhorn's Iterations


  • 매번 $K$라든지 $K^T$의 곱셈이 필요하게 되기 때문에 겉보기 생각이 들지만, GPU를 사용하면 우선 복수본 히스토그램의 계산은 동시에 가능

  • Sinkhorn의 업데이트 표현식은 거의 그대로 행렬형입니다.
  • $U^{(l+1)} =\frac{A}{KV^{(l)}}$
  • $V^{(l+1)} =\frac{B}{K^T U^{(l+1)}}$


  • $V$와 $U$가 수렴했는지 여부를 확인하는 식으로 (4.26) 아래에있는 식은 잘못 된 것 같습니다 (자세히 알 수 없음)
  • 누군가 말해


  • 커널 분할(separable kernel)


  • 고속화를 위한 하나의 특수 케이스로서 커널 $K$를 분할할 수 있는 경우

  • 이미지는 어렵지만 비용 행렬이 작은 비용 행렬의 합으로 다시 작성할 수있는 경우를 말합니다.
  • $i=(i_k)_{k=1}^d, j=(j_k)_{k=1}^d\in [n_1]\times\dots\times[n_d]$
  • $C_{ij} =\sum_{k=1}^d C^k_{i_k, j_k}$
  • Sinkhorn 알고리즘에서는 $C$는 $\exp(\cdot)$ 안에 들어 사용되므로 커널로서는 $K=\prod_{k=1}^d K^k_{i_k, j_k} $가됩니다

  • 예 : 격자상의 히스토그램에서 각 차원에 대한 거리의 합이되는 경우 ($q$-norm)
  • 잘 모르겠습니다
  • 노트에는 수수께끼의 그림만 남아 있었다



  • 다음


  • 다음 번은 7/16에 § 4.3의 계속을 읽는다
  • 좋은 웹페이지 즐겨찾기