競技プログラミングのコード生成で上位54%以内を達成,AlphaCode

Competition-Level Code Generation with AlphaCode

f:id:e4exp:20220204130714p:plain

  • 自然言語からコード生成するシステムAlphaCodeを提案
  • モデルは巨大な(最大41B)transformer encode-decoder
    • GitHubオープンソースコード715.1GB分で事前学習
    • 学習サンプルをランダムに前後に分け前半をencoder, 後半をdecoderに使用しmasked言語lossで学習
    • マルチクエリ注意(注意ブロックごとにqueryは別,key,valueは共通にする)を利用してメモリコストを削減している
    • 競技プログラミングデータセットCodeContestsを作成し,これでfine-tuning.データセットは公開している
      • temparing(softmax前にlogitを温度Tで割る)を使用,学習目的はGOLD(Pang and He, 2020)
      • GOLDはオフラインRLアルゴリズムで、最尤目標の勾配にトークン尤度重みを掛けたもの.すでに高い尤度を割り当てたトークンを重視し,その分布担いトークンを無視させる
    • 学習した1個のモデルから大量のサンプルを生成し,フィルタリング,クラスタリングを経て数件を提出し非公開テストで評価
      • サンプルの半分はpython,残りはC++を生成.フィルタリングはテストケースに正解することを確認,クラスタリングは同じ入力に対して同じ出力を返すプログラムは同じクラスタに割当て,同じクラスタからは提出物を選ばない
  • 競技プログラミングCidefircesの最近10件のコンテストで評価を行い5000人以上の中で平均54.3%のランキング達成
    • 評価では「k件の生成結果の中からn件を提出し,解決された問題の割合」を意味するn@kという指標を使う

f:id:e4exp:20220204130800p:plain 問題の例
問題は次のようなもの.文字列sとtが与えられ,sを構成する文字を入力しながら何回かbackspaceで文字を削除する操作を混ぜることでtの文字列を作ることができるかを問う.作ることができるならYES, できないならNOを出力する.入力形式は最初の行に問題の数,次の行からsとtが1行ずつ記載される.問題数4ならs,tが4つずつなので合計9行の入力が来る(問題数の行も入れれば9行)

f:id:e4exp:20220204130810p:plain 提案手法が出力した回答
入力文字列を逆順にし,whileループ内で先頭から文字を消していく方法でsがtを一致するか確認するプログラムを生成できている