2024年6月25日火曜日

STOC1日目の感想 (LLMの話とbest paper sessionのまとめ)

せっかくSTOCに参加しているので日記を書こうと思いたち, 勢いに任せて筆を進めています. 2日目以降は筆が乗らないかもしれません.

今回のSTOCは最初のワークショップではLLMなどのAI分野においてアルゴリズムの理論研究がどのように貢献できるのかという話をしていました. 以下に続く文章はそのWSを聞いて私が解釈したものですので, 内容の正確性は保証しません. あくまでも私が解釈したものなので, AIに関して何かを述べる際はこの記事を情報源にはしないでください.

例えば文章が途中まで与えられた「次の単語は何か?」を学習する際, まず単語ごとに区切りそれぞれの単語を高次元ベクトルに埋め込み (多分Word2Vecみたいな話), 次に出てくる単語の条件付き分布を推定するということをします. この条件付き分布は何らかの分布に従うと仮定しており, 通常はある高次元のパラメータ$\theta$を持ちます (例えば正規分布は平均と分散で二つのパラメータをもつ). 深層学習とはこの「何らかの分布」のテンプレートの一例にすぎず, そのテンプレの中で尤度関数を最適化するという作業に他なりません. 具体的には線形作用と成分毎の非線形作用を交互に組み合わせる分布を考えており, この線形作用の重みがパラメータに対応します. chatGPTとかをみるとあたかも魔法のようなことをしているように見えますが, 実際は次の単語の条件付き分布がある特定のテンプレに従うと仮定し, 与えられたデータセットに最も近いテンプレを見つけるにすぎません.

教師あり学習だと点とそのラベルの組があらかじめデータセットとして与えられ, 未知の点が当てられたときにその点のラベルは何かを推測するということを考えます. この問題点は高精度な推測をするためには多くのデータセットが必要になるという点です. しかしながら, 膨大な点とそれに対応するラベルの組を得るという作業は大変です.

ところが「次の単語は何か?」という問題の場合はインターネット上のデータ (wikiの記事など) から文を持ってくれば膨大なデータセットを容易に得ることができるので, 前段落の問題点は解消されます. あとはこの膨大なデータセットを用いていかに効率よく最適なパラメータを得るかというアルゴリズムのタスクが勝負になります. ここではスーパーコンピュータなどを用いて大規模な並列計算を行うことも視野に入れて「並列化しやすい」アルゴリズムを設計するみたいなことも視野に入れます.

ワークショップではdiffusion modelについての話も出ました. なんとなく「diffusion model」と聞くとたいそうに聞こえますが端的に言えば空間上のただのランダムウォークだと私は思っています. 例えば「子犬と遊ぶ子供」という文からそれに対応する画像を生成するタスクを考えてみましょう. このとき, 任意の画像全体の空間$\mathbb{R}^N$を考え, その上で点$x \in \mathbb{R}^N$に対し小さなランダムなノイズを加えるという操作を繰り返しましょう. $t$回繰り返して得られるベクトルを$x_t$とすると, 十分大きな$t$に対して$x_t$は標準正規分布$N(0,I)$に近いです. diffusion modelとはノイズを除去する過程のモデルであり, $x_t$が与えられたときの$x_{t-1}$の条件付き確率が平均$\mu_t(x_t,t)$, 分散$\sigma_t(x_t,t)$の正規分布に従うと仮定してこのパラメータを最適化するという作業に他なりません. このようにすることで「子犬と遊ぶ子供」という文から実際にそれを表現する画像をサンプリングすることができます. データセットは「子犬と遊ぶ子供」の画像からなります. このデータセットはまずネットサーフィングして画像と脚注の組を得ます. 次に脚注の文章を高次元に埋め込みます. この埋め込みは意味が似てる二つの文章は埋め込んだ後も何らかの意味で距離が近いものになっているとします. すると「子犬と遊ぶ子供」に対応する点に近い点に対応する脚注を持つ画像を抽出することで大量のデータセットを用意することができます (この辺は少し私の理解が曖昧なので不正確かもしれません).

ワークショップの二人目の発表はAtri Rudraでした. 彼はEssential Coding Theoryの著者の一人なので私の中では誤り訂正符号をやってる人というイメージだったので, このような分野で研究をされているというのは意外でした. 今日「Transformer」と呼ばれる技術を算術回路に落とし込み, 効率的な算術回路を提案することでより学習を効率的に行うという旨の話でした.

Transformerでは, まず与えられた文章を$N$個の単語に分解し, それぞれの単語を$d$次元ベクトルに埋め込みます. こうして得られた$N$個のベクトルを並べて得られる行列を$X \in \mathbb{R}^{N \times d}$ とします. 深層学習では各レイヤーで, $X$を$Nd$次元のベクトルとみなして$X_t \leftarrow \sigma (W_t X_{t-1})$という更新式に基づいて$X_T$を出力するときの行列$W_t$を最適化で求めるわけですが, TransformerのAttentionと呼ばれるプロセスでは
\[
X_t \leftarrow \sigma (Q_tX_{t-1}X_{t-1}^{\top} K_t)
\]
という更新式 (ここで$Q_t,K_t$は行列) を繰り返します (これが何でうまくいくかは分かりません). この$Q_t$と$K_t$がパラメータになっており, 学習ではこのパラメータを最適化します. あまりちゃんとわかっていませんがここでの行列がある種の対称性を持っていれば効率的に更新できるみたいな感じの話だと思います. ただしここでは行列への要請として対称性だけではなく, (勾配法の適用を念頭に)パラメータでの微分可能性も要請されていました (行列かけるだけだったら常に微分可能なんじゃないの?と思ったけどよくわからなかった). この辺の話では面白いことにSETH-hardnessの論文があったりするようです.

LLMのワークショップの後はbest paper sessionがありました. 今回のSTOCは3件のbest paperがあり, それぞれ

  • Single-Source Shortest Paths with Negative Real Weights in $\tilde{O}(mn^{8/9})$ Time, Jeremy Fineman.
  • Near Optimal Alphabet-Soundness Tradeoff PCPs, Dor Minzer and Kai Zhe Zheng.
  • Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis, Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu.
でした.

一つ目の論文は負辺持ちグラフ上の単一始点最短経路問題に対してBellman-Fordより速いアルゴリズムを提案するというものです. この問題は2022年のFOCSの論文で$\tilde{O}(m\cdot \mathrm{poly}\log W)$時間で解くアルゴリズム ($W$は最大絶対値重み) が提案されていましたが, このアルゴリズムは反復回数が$\mathrm{poly}\log W$に依存するためいわゆる「弱多項式」時間アルゴリズムです. 一方でこちらの論文は一反復の計算に$\tilde{O}(m n^{2/9})$時間かかる操作を$O(n^{2/3})$回繰り返すというものであり, いわゆる「強多項式」時間アルゴリズムです.

二つ目の論文はPCP定理のアルファベットサイズとsoundnessのトレードオフに関する論文です. PCP定理についてはこちらの記事で説明をしていますが, 「SATは確率的検証可能できる」ことを主張する定理です. SAT (より一般にクラスNPの問題) は, 入力がYesインスタンスのときにYesたりうる証拠たりうる文字列 (例えばSATなら充足割り当て) が存在しそれをみたときは受理し, Noインスタンスのときはどんな文字列が与えられても拒否する検証者(verifier)が存在します. 確率的検証とは証拠として与えられた文字列のうちランダムに選んだ$q=O(1)$個だけをみて受理/拒否を判定する検証を指します. 検証者の受理確率について, 入力がYesインスタンスならば確率$\approx 1$で受理し, Noインスタンスに対しては確率$\le \delta$で受理するものを考えます. ここのパラメータ$\delta$をsoundnessといいます. soundnessパラメータ$\delta$は小さければ小さいほどよいです.
PCPはそのアルファベットサイズ$|\Sigma|$を大きくすることによってクエリ数$q$を保ったままsoundnessを小さくしていく (Razのpararrel repetition) ことができますが, $|\Sigma|$と$\delta$の間のほぼ最適なトレードオフを見つけたというのが今回の論文の主張のようです.

三つ目の論文もPCP定理の改善の話で, パラメタ化計算量の文脈におけるPCP定理の話でした. PCP定理ではNPのwitnessを「符号化」して確率的検証できる証明に変換するのですが, この「符号化」で追加する冗長性をいかに短くできるかという文脈を考えます. パラメタ化計算量の文脈では考える入力のクラスを制限してより効率的なアルゴリズムを得るという研究をしますが, 一方でその困難性についてもいろいろわかってきており, 「NP困難性」に対応する概念として「W[1]困難性」という概念があります. 一般にW[1]困難な問題はFPT時間では解けないだろうと予想されており, 代表的な問題として$k$-クリーク問題があります. そしてW[1]困難な問題に対しても近似アルゴリズムを設計したり何らかの仮定の下での近似不可能性を示す研究もあります. この近似不可能性の文脈でよく出てくるのが PIH (parameterized inapproximatability hypothesis) という予想です. これはMAXSATのギャップ問題のようなパラメタ化問題がFPT時間で解けないという予想です. 今回の論文は指数時間仮説(ETH)の下でPIHが成り立つことを示しており, パラメタ化計算量における「PCP定理」を証明したという論文のようです. 普通のPCP定理の証明を考えるとNP証明を「符号化」するということを考えますが, この符号化によって対応するCSPのインスタンスのパラメタがめちゃくちゃになってしまうのが難しいポイントだと私は解釈しています. 代わりにW[1]困難な問題 vector CSPというものを考えるようです. 一般にNP証明からPCPに符号化する際のオーバーヘッドが定数倍で済むならば$\mathsf{ETH} \Rightarrow \mathsf{Gap}\text{-}\mathsf{ETH}\Rightarrow \mathsf{PIH}$が成り立つと思うのですが, このholy grailにはまだまだ遠いようです.

こうしてみるとbest paperのうち2/3はPCP定理なので今回はSymposium on Theory of pCp theorem (STOC) なのかもしれません.

best paper sessionの後はTCS4Allのイベントがありました. 本来ならばLuca Trevisanが話をする予定だったのですが残念なことに先週亡くなってしまったため, Pravesh KothariがLucaの作成したスライドに基づいてスペクトルグラフ理論の話をしていました. ほとんど知っている内容だったのですが改めて聞くとやはりLucaの偉大さが感じられる非常に素晴らしい内容でした.

coffee breakや懇親会ではいろんな人と話をしましたが, Yuhao Liとの雑談でTFNPにおけるPCP定理の話が興味深かったです (重要な未解決問題らしい). また, 私は加法的組合せ論に基づく平均時から最悪時への帰着が好きなので, その研究グループの一人のIgor Shinkarと話ができたのがとても良かったです. 大阪さんから聞いた遷移問題のPCPの話も面白かったです.

2024年6月20日木曜日

Luca Trevisanについて

Luca Trevisanが癌で52歳の若さで亡くなったという衝撃的なニュースが飛び込んできました.


直接の面識は全くないのですが, 彼の多くの論文や結果, それにまつわる深い洞察は私の数学に重要な影響を与えており, 来週のSTOCでのワークショップでの彼の講演を直接見れるのをものすごく楽しみにしていただけに非常に残念に思います. STOCのワークショップでのスライドは準備されていたとのことですので, まさに「生涯現役」の研究者であるといえるでしょう. 理論計算機科学は世界的に非常に重要なリーダーの一人を喪失してしまいました.

彼の有名なブログ in theory は計算量理論, 加法的組合せ論, エクスパンダーグラフなど幅広い理論の最近の動向や手法を概説してくれるとても素晴らしいものであり, Terrence TaoのWhat's new や Boaz Barak の Windows On Theory などと並んで私のブログのスタイルに大きな影響を与えた存在でです.

計算量理論では, 例えばこちらのページのランダム抽出器の節で紹介した[Trevisan, 2001]や, こちらのページで紹介しているHardness vs. Randomnessに対して誤り訂正符号のlocal list-decodingに基づくアプローチを提案した[Sudan, Trevisan, Vadhan, 2001]が非常に有名です (もちろん, これに限らずもっと色々ありますが). また, Bogdanovと一緒に平均時計算量の非常に有名な教科書も執筆しています.

他にもスペクトルグラフ理論の文脈でよく知られるhigher-order Cheeger inequality (普通のCheeger不等式はグラフの頂点集合を二分割したときのカット辺の本数に関する不等式だが, higher-orderではグラフを$k$分割したときのカット辺の本数に着目する) の論文[Lee, Gharan, Trevisan, 2014]も有名です. この話はTrevisanによる解説記事があります.

また, 加法的組合せ論とその理論計算機科学への応用にまつわる様々な解説記事や講義ノート

も出しており, 私はこれらから加法的組合せ論の多くを学びました.

最近ではBecchettiらの研究グループでグラフ上の合意ダイナミクスと呼ばれるマルコフ連鎖やそれに基づくコミュニティ検出についての研究も精力的に行っており, 私の研究分野に非常に近い論文

を出しており, その多くがSODAなどのトップ会議に採択されています.

私はTrevisanと直接交流したことはないのですが, 理論計算機科学の幅広い文脈でいつも見てよく資料で勉強させていただいた先生が若くして亡くなられたという事実に深い悲しみを覚え哀悼の意を捧げたいと思います.


Håstadのスイッチング補題

回路計算量の理論における重要な結果の一つである Håstadのスイッチング補題 を紹介します. 簡潔にいうとこの補題は, 99%の変数をランダムに固定することによってDNFの決定木が小さくなることを主張する結果です. 応用としてparity関数に対する$\mathrm{AC}^0...