せっかく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.
