【東北大ライブ講義】第5回: シンクホーンアルゴリズムとは【データ科学と機械学習の数理・2025年度東北大学工学部】

今年度は「最適輸送の理論とアルゴリズム」（佐藤竜馬著・講談社サイエンティフィク）を題材に最適化・学習の理論を紹介します。

シンクホーンアルゴリズムは、なぜ爆速なのか。
でも、速ければいいってものではない。
現実には“実行可能解”でなければ、現場の人に怒られちゃうよ。

受講生の皆さん、外部受講者（公式潜りの方々）はYouTube Live上で質問・コメントをしてください。（講義の時間の許す限りリアクションします）
どうぞよろしくお願いします。

#東北大学
#最適輸送
#最適化問題

【教員情報】
東北大学大学院情報科学研究科教授
大関 真之
Web page
https://altema.is.tohoku.ac.jp/~mohzeki/
twitter
  / mohzeki222  

キーワード：
エントロピー正則化、シンクホーンアルゴリズム、行列スケーリング、大域的収束性

【チャプター】
0:00:00 | 待機画面
0:00:07 | ♩「ZEROから知りたい？」
0:04:40 | ♩「量子なアナタ」
0:09:09 | OP

◼️開始前雑談
0:09:43 | 大関の暑がり事情
0:12:21 | コメント返し
0:13:39 | なぜコンタクトレンズにしないのか
0:18:12 | 大学の講義で何を教えるべきか

◼️前回の復習
0:19:48 | 最適輸送+エントロピー正則化
0:21:31 | エントロピー正則化の双対問題
0:24:04 | シンクホーンアルゴリズム

◼️シンクホーンアルゴリズム
0:26:16 | シンクホーンアルゴリズム | C変換の関係
0:28:40 | シンクホーンアルゴリズム | [step up] ln Σ exp()とmax(便利)
　∟0:30:46 | 証明：lnなしで不等式を書き下すと
0:33:59 | シンクホーンアルゴリズム | ln Σ expはどうなるか
　∟0:37:02 | 雑談＞ ≈と≃ってなんと呼ぶ？
0:38:13 | シンクホーンアルゴリズム | ln Σ exp() ≈ max()で書ける理由
　∟0:40:02 | 雑談＞ 答え合わせ
0:42:11 | シンクホーンアルゴリズム | εのお気持ち
0:43:49 | シンクホーンアルゴリズム | logをなくすと
　∟0:46:09 | 行列・内積計算はGPUで爆速に
　　∟0:48:10 | 雑談＞ 量子コンピュータでワンチャン...？

0:49:35 | CM（研究室PV）
0:52:40 | コメント返し
0:54:10 | メロドーアに物申す

0:57:01 | シンクホーンアルゴリズム | 行列スケーリングとの関係
0:58:12 | シンクホーンアルゴリズム | [step up] 行列スケーリング
　∟1:01:19 | 行列スケーリング | シンクホーンとの対応
　　∟1:05:17 | 雑談＞ 他の最適化問題との類似性
1:06:22 | シンクホーンアルゴリズム | 有限回から実行可能解へ補正
　∟1:08:18 | アルゴリズムを途中で止めて仮の解を得る
　　∟1:09:24 | 補正をしてxiとyiを得る
　∟1:14:58 | Pij~’’とai, bjとの誤差からPijを実行可能解にする
　∟1:18:21 | 実行可能解であることの証明
　　∟1:22:59 | 雑談＞ とりあえず実行可能解を出す重要性
　　∟1:24:35 | 雑談＞ 倉庫内の荷物移動を実体験した話
1:27:04 | シンクホーンアルゴリズム | 大域的収束性
　∟1:29:27 | 大域的収束性 | 双対問題の数式
　∟1:32:02 | 大域的収束性 | 定数倍しても解に影響なし（不定性）
　∟1:33:35 | 大域的収束性 | 次なるステップ

1:35:45 | エンディングトーク
1:36:52 | ED（♩「我らの雑談方程式」）