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の話も面白かったです.