Competition-Level Code Generation with AlphaCode
https://gyazo.com/975ef2419378302656cf851ace573c14
選んだ理由
純粋にすごいと思ったから
競プロを少しやったことがあるのもあり
どのようにして達成しているか気になったから
73ページ（選んだ理由ではないですね...）
著者情報
DeepMind の人達
すごい...
どこがすごい
AlphaCode というコード生成システムを構築
Codeforces でのコンテストで平均上位54.3%を達成した
過去6ヶ月にコンテストに参加したユーザの中でレーティング上位28%を達成したと推定
https://gyazo.com/adfa272f9bc6f78192cf1e56b9a86805
高いパフォーマンスを得るために以下の3つが必要であることを発見
(1) 学習と評価のためのクリーンな競技プログラミングデータセット(CodeContests)の作成
モデルの信頼性が高い
(2) 大規模で効率的な Transformer-base のアーキテクチャの構築
(3) 提出を作成するための大規模モデルによるサンプリングとフィルタリングの提案
個人的には様々な手法を組み合わせていて総合格闘技感を感じた(感想)
導入
Transformer ベースの言語モデル(GPT-3)はテキスト生成で高いパフォーマンスを達成している。
特にCodex(GitHub Copilot) は単純な問題を解決するコードを生成することができる。
一方で Codex の論文や類似研究での問題は短い解を持つ単純なタスクであり、実際のコーディングはこれらのタスクより非常に複雑性が高い
そのため、C++ や Python のような汎用言語で、長い自然言語の問題からプログラム全体を生成するのは未解決であった。
今回左のような問題を解くようなコード(右)を生成するタスクを解く(下図)
Codeforces の問題を解くことを目的としている
https://gyazo.com/5be411132235a4713de596129be9892b https://gyazo.com/b43904875de9e28421892b5a4d0ff84d
全体像
https://gyazo.com/f5b1776f5b4b3f6c8cb7f5958254f52d
タスクを解くコードを生成するのは探索空間が巨大すぎる & 競プロのデータセットはあまり多くない
探索空間を小さくする必要がある -> pre-train からの fine-tune
1. Transformer-based language model を GitHub のソースコードで pre-train
BERT を使用
Scaling Law に従って学習量を調整
性能(loss)と(計算能力、データセットのサイズ、モデルのパラメータ)の間にべき乗則が観測
2. CodeContests データセットを使って fine-tune
3. 問題に対する解答候補を学習したモデルからたくさんサンプリング
4. 生成した解答候補に対して、example(公開されているテストケース)とクラスタリングを使用して最大10件取得し、（公開されていない）テストケースで評価
データセット
Pre-training Dataset
2021/07/14に取得された GitHub 公開リポジトリのスナップショット
1MB以上のファイル、1,000文字以上の行を持つファイル、自動生成のコードを除外
空白を無視したときに同じファイルの重複を削除
全部で 715.1GB
言語の構成は以下
https://gyazo.com/ff719408e12ca1a938872124f086afc1
CodeContests
Codeforces から問題、提出、テストケースをスクレイピング
正解/不正解両方含んでいる
上に加えて、scription2Code, CodeNet を組み合わせて学習データセットとした。
上記は既存の公開済みの競プロデータセット
valid, test データは新たにスクレイピングした Codeforces の問題で構成
train: 〜2021/07/14, valid: 2021/07/15〜2021/09/20, test: 2021/09/21〜
leakage を防ぐため( Pre-train のデータセットは 2021/07/14 のスナップショット)
データクリーニング
重複を削除したり、C++ の場合は include を全て #include<bits/stdc++.h> に置き換えたり、typedef を展開した。
テストケースに通して条件に従って削除
テストケース
テストケースは網羅的だと嬉しいが、Codeforces ではテストケースが約 400 文字より長い場合、全てのテストケースが表示されない場合がある。
テストケースが完璧でない場合が少なからず存在する
上記から、完全でないテストケースを用いるため、間違っている提出を正しいと判定してしまう（テストが通ってしまう）False Positive や、出力は正しいが、時間やメモリの制約を満たさない解を正しいと判定してしまう Slow Positive を引き起こしてしまう。
公開されているテストケースはプログラムの動作を保証するには仕様不足であるという問題がある（false positiveが高くなる）。また、テスト数が多いといって網羅的とは限らない。
これらの問題に対応するため、既存のテストケースの入力に変更を加えて追加のテストケースを作成する
ex. ビット反転、ランダムなインクリメント、デクリメント、文字列の swap
変更後の入力に対して、30個の正しい解答を実行して全て同じ出力であることを確認することで検証
200個 or 一定時間経つまで生成される。
valid と test に対して、網羅性が不十分な問題を排除し、公開されていないテストケースが 5 つ以上、テストケースの出力が2種類以上を満たすようにした
定数出力で OK としないようにするため
作成したデータセットの概要
https://gyazo.com/ab5d3ed164cd3066bc392d5adaf47413
データセット間の False Positive, Slow Rate の比較
APPS データセットは平均テストケース数は多いが False Positive が高い
似通ったテストケースが多い
CodeContests データセットの False Positive が 62% から 4% に減少している。
Slow Rate はある程度存在する
https://gyazo.com/d8b1464b18bea3b3a92b14250153d2b2
Fine-tune
CodeContests を使って fine-tune する。
Encoder-Decoder モデルを使用する（入力: 自然言語, 出力: ソースコードの翻訳モデル）
Encoder: 1536次元, Decoder: 768次元
入力が出力の平均2倍であったため
非対称にすることで効率よく学習/推論できる
tokenizer は GitHub と CodeContests を SentencePiece で学習したものを使用 ( 8,000 語彙)
https://gyazo.com/603d88b4ce980b98eaf14f64d34116da
モデルの工夫
サンプリングコスト削減のため Multi Query Attention を用いる
attention block 毎に key head と value head を共有することでメモリ使用量、(key, value の)キャッシュ周りのコストが削減されるというもの
かなり高速化していてすごい（元論文からの引用）
https://gyazo.com/b632d6689e4c2c47e371b4119301fc83
メモリ使用量を減らしたことによって、バッチサイズを大きくすることができるので更に高速化
Haiku で記述
JAX のライブラリ
JAX は高速な自動微分ライブラリ
NTK 界隈では JAX が主流になるみたいな話があるらしい(要出典)
TPUv4 で学習
強い(感想)
GOLD: Generation by Off-policy Learning from Demonstrations
競プロの問題と解答の関係は 1:N である
それぞれの問題に対して、アルゴリズムや実装に依存した複数の解答が存在する
CodeContests では問題に対して、100 オーダーの提出がある。
タスクの評価は、最大提出回数内(10回)で1回正しい提出ができればOKというものなので、1つ1つの提出に対して損失を計算するのはあまり嬉しくない（ Recall より Precision を高めたい）
複数提出に対して損失(or reward) を計算するようにする。
複数提出に対して1つでも正解が存在すればOKとしたい（下図は GOLD の論文からの引用）
https://gyazo.com/b4c28aec3b57eb76d43aa08cc63e2f7e
最尤推定量の勾配は以下（θ: モデルパラメータ）
https://gyazo.com/a485d2afc9889cbe9d80ab9da12a5a3a
$ \text{log} P_\theta(s): 次の token を予測するための対数尤度
$ P_\theta(s): 尤度を weight として乗算
これによって、高い尤度を割り当てた token から学習し、その分布にない token を無視することが出来る
これによって Recall ではなく、 Precision を高めることが出来る
TODO: 考え中...(わかっていません...)
tempering
検証データで適切な温度を決定し、温度付き softmax を用いる手法
学習データが少ないと過学習する傾向にあり、これを温度付き softmax を用いることで過学習を抑えることが出来る。
元論文の主張では T > 1 を使用すると過学習を防ぐというものだったが、本研究では T = 0.2 < 1 を用いることで過学習を防ぐことが出来た
Value conditioning & prediction
CodeContests には正解/不正解の両方の提出が含まれている
（不正解データも有効活用するために？）入力の先頭にメタデータを追加する(CORRECT SOLUTION(RATING(難易度) や TAGS(ex. dp, math) なども同様))ことで、不正解データであることをモデルに教える。
valid, test ではこれらのメタデータはないことに注意する。
サンプル生成のときは CORRECT SOLUTION に固定するイメージ
正解/不正解 を予測するタスクを追加（サンプリングには使用しない）
https://gyazo.com/f1ef44d25e43ff6ef98d3bd61643f036
Large scale sampling
Overview のモデルからたくさんサンプリングするのところの話
並列化可能であるため、問題あたりのサンプル数を数百万まで拡張
ここのサンプリングの多様性が重要
多様性のための工夫
サンプルを C++ と Python で半分ずつ
Java san ...(感想)
入力に与えるタグと Rating をランダム化
50 個あるタグ( dp, data structures, hashing, math etc...) からランダムに選択
Rating は 800 〜 3,500 の間でサンプリング
ここは思うところがある
これによって、サンプルの多様性が向上し、性能が向上することを示唆
サンプリング温度を高めに設定
一般的に、サンプル数が多いほど最適な温度は高くなる
実際に温度を変えて実験してみたところ温度によって性能はさほど変わらなかった
GOLD を使用する実験では T=0.25、 Tempering だけを使う場合は T=0.12 で固定
フィルタリング
公開されたテストケースが通るものだけにサンプルをフィルタリングする。
これに通らないと必ず不正解となるため
99%程度フィルタリングされるが、多くの問題では数千〜数万のサンプルが残る
クラスタリング
フィルタリングしても数千程度の提出候補が残る
最大 10 件に絞りたい
ランダムに選択すると、構文が異なるが、アルゴリズムが同じプログラムを提出してしまう可能性がある。
ここで、以下の手順でクラスタリングを行う。
テストケースの入力を生成するモデルを学習/推論して、テストケースの入力を生成
このモデルも GitHub データセットで pre-train、テストケースの入力で fine-tune
このモデルの入出力がその問題において正しくなくて良い
意味的に等価であるプログラムなら同じ出力をするため
作成されたテストケースに対して同じ出力をするプログラムを同じクラスタとして扱う
大きなクラスタから順にプログラムを提出していく
正解のプログラムは同じ振る舞いをする傾向にあるため、大きなクラスタから提出することが有効なのではないかという示唆
Result
Codeforces でのシミュレーション
2021/12/01〜2021/12/28 の全てのコンテストでシステムを評価
9B(87億パラメータ) と41B(411億パラメータ)のアンサンブル(valid set で最高perf)
3回シミュレーションを回す
1回目: 提出制約あり(最大10件)
2, 3回目: 提出制約なし
評価結果
Estimated: 推定順位
Best: 不正解を出したときのペナルティなし
Worst: 不正解を出したときのペナルティ無限（同じ点数の人の中で最下位ケース）
https://gyazo.com/408ea3321b329f6be3c56d8c3effcf6d
提出制約がなかった場合、上位49.7%で、平均提出数は 29.0 件だった
この場合過去6ヶ月間にコンテスト参加したユーザの上位28%
CodeContests での評価
以下の metric で評価
pass@k: 各問題から k サンプル使用し、提出したときの正解率
10@k: 各問題から k サンプルとり、そのうち10件提出したときの正解率
サンプリング数による正解率の変動を見る
pass@10@k みたいなイメージです(逆にわかりにくい...？)
評価結果
1問題あたり100万件サンプリングすると、valid set の 34.2% を解くことが出来る
41B は 9B より一貫して正解率が高い
valid set と test set の正解率の違いは問題分布のばらつき（時間的に離れている）といくらかの過学習によるもの
valid set の best を取っているため
https://gyazo.com/2c0570186f95ac82af7c4a1a28d4e9f4
パラメータ数とサンプル数を変えたときの正解率
サンプル数が増えるほど性能が向上
10@k で向上していることから、10件までしか提出出来ない場合でも探索空間を十分に探索することが重要であることがわかる
サンプル数を増やすのはコストがやばいらしい（やばそうではある）
パラメータ数が増えるほど性能が向上
https://gyazo.com/947b45cbd041d1285c4738a1be12a0e7
学習時間と 10@k の関係
学習時間の増加に伴い 10@k も向上する
サンプリング時間も同様の傾向
一方、パラメータが大きなモデルはサンプリングするのに時間はかかるが、大きなモデルのサンプリングの品質が性能を支配しており、同じサンプリング時間でも小さなモデルより性能が高くなることが示唆
41B はサンプリングに時間がかかりすぎるからこのような結果になっている？(感想)
https://gyazo.com/8e5d9e39e579ae8c81516a2a7950a22c
サンプル数を増やすことで性能向上できるので、サンプリング速度をあげることで正解率も向上することになる。
AlphaCode の工夫: Enc-Dec の次元数、 Multi Query Attention
大幅に Samples/TPU sec が向上していることがわかる
https://gyazo.com/595ddf75db62873417bac17e25a8bbed
Pre-train dataset の議論
pre-train → CodeContests で fine-tune を行ったときの 10@k ( No pre-training を除く)
どの pre-train も CodeContests 単体で0から学習するよりも結果が改善される
GitHub の全言語で pre-train をおこなうと MassiveText データセットで pre-train をおこなうよりも有意に良い結果が見られた
https://gyazo.com/4ee7429ab4d38a1364e213e4d0bd7d37
Ablation Study
括弧内は95%信頼区間
No Enhancements = 普通の Transformer に Multi Query Attention の変更を加えたもの
様々な工夫によって性能がかなり向上していることがわかる（感想寄り）
https://gyazo.com/79f16b5792b0f0792104ac7915db8f2b
フィルタリング周りの統計
公開されたテストケースに通った割合に関する統計量
平均して1%未満しか全てのテストケースが通っていない(99%以上がフィルタリングされている)ことがわかる
正解した問題については、平均の2倍くらい公開されたテストケースを通している
https://gyazo.com/c543c7af01aa78644ccac16f5a985888
クラスタリング
クラスタリングの有用性に関するグラフ
クラスタリングしないものはランダムに選択する
クラスタリングを行うことで、性能が向上していることがわかる
一方で pass@k との差はまだ大きい
https://gyazo.com/a015bc0eaff0972c2d07762ddfeb16e1
先行研究との比較
APPS ベンチマークでの評価の実施
Introductory: 入門レベル
Interview: 面接レベル: データ構造に関する問題等
Competition: 上限なし(とても難しい)
IOI や ACM、USACO レベルの問題を含む
Codex: GitHub Copilot
全ての指標で GPT-Neo を上回り、Interview(コーディング面接), Competition において Codex 12B を上回った。
サンプル数を増やすことで性能が向上していることがわかり、大規模なサンプリングの重要性が高いことが示唆される
https://gyazo.com/2f923a076585bad5fca02e975658b716
感想
めちゃくちゃ面白い
Rating（難易度）毎に分析してみても良さそう
難しい問題だと、大きなクラスタから順に選ぶので、単純な解法が同じクラスタにたくさんはいってきてしまう可能性はありそう
後半の問題のほうが難しいなどあるので、どんな場合も800〜3500から一様サンプリングするよりは何らかの範囲の絞り込みをしても良さそう（Meta情報ではある）
Meta 情報を除いたものを入力として難易度推定モデルを別で作っても良い？