論文内容

現在 (2021年の) のDNNが、競技プログラミングの問題を自動回答する能力があるかを実験によって調査した。

背景

BERTに始まる巨大なDNNモデルによる言語処理は近年様々なタスクで用いられている。プログラミングにおいても、プログラミング言語間の変換やコンパイルエラーの修正タスクにおいて巨大なDNNモデルをもちいた手法が提案されている。

しかし、コーディングタスク (Program Synthesis, Programming by Example) では巨大なDNNモデルは殆ど用いられていない。

実験

データセット

AtCoderやCodeforcesなどの競技プログラミングのサイトからデータセットを作成した。問題は全部で約1万問で解答言語はPython。サイト間での入力形式の違いなどはデータセットの時点で統一している。

収集した問題をIntroductory, Interview, Competitionの3レベルに分類した。Introductoryは1-2年のプログラミング経験があれば解けるようなアルゴリズム・データ構造の知識が必要ないもの、Interviewはcoding interviewで問われるようなレベルのアルゴリズム・データ構造の知識が必要なもの、Competitionはさらに難しい知識が必要なもの、というのが大まかな分類となる。

DNNモデル

GPT-2、GPT-3、GPT-Neoの3種類のモデルで実験を行った。

GPT-2は、GitHub corpusによるpretrainののち、提案データセットによるfine-tuneを行った。GPT-Neoは公開されているpretrain modelから提案データセットによるfine-tuneを行った。GPT-3は公開されているpretrain modelをそのまま利用した。

結果

最も多くの問題を解けたのはGPT-Neoで、Introductoryプログラムの15%のテストケースをpassした。ただし、全テストケースをpassした問題の割合で言うと3.9%となる。問題難易度が上がるにつれて正答率が減少しており、このことはDNNが解答の暗記をしているのではないことを示唆している。

その他、DNNによるProgram Synthesisに関して以下の知見を得た。

fine-tuningとモデルサイズの増加によりsyntax errorの割合が劇的に減少する
従来のProgram Synthesisでmetricとして良く用いられたBLEUは、test caseのpass rateと相関がなく有効な指標とは言えない

メモ・コメント

あるドメインのデータセットを十分な数集められれば巨大DNNモデルによってscratchからのProgram Synthesisが可能になる可能性を示した点で面白い結果と思う。また、GPT-3以後few-shot learningに注目がいきがちな印象があったなかで、fine-tuningの重要性を再確認させる報告でもある。

一方で、結果の解釈は少し慎重に行った方がいいのかなと感じている。

例えば、

問題難易度が上がるにつれて正答率が減少しており、このことはDNNが解答の暗記をしているのではないことを示唆している。 Memorization is an implausible explanation as performance tracks problem difficulty; were models just memorizing, we would expect uniform performance across difficulties.(原文)

については、難易度の低い問題ほどバリエーションが少なく暗記しやすかった・パターンマッチで解きやすかった、という可能性はあるのではないかと思う。

また、

GPT-Neoで、Introductoryプログラムの15%のテストケースをpassした。 Note that for Introductory questions, GPT-Neo passes approximately 15% of the test cases. (原文)

についてももう少しちゃんと見ないといけない気がする。競技プログラミングの問題の一部はYes/Noを答えるように出力のパターンが決まっているものがある。そのような問題は例えば print("Yes")としておけば約50%のtestcaseにpassできることになる。実際に正解したtestcaseのうち何%がこのようなパターンなのかは気になる。

もうひとつ気になる点はmulti modalなprogram synthesisの効果。今回の実験は問題文だけを入力としてプログラミングしているが、競技プログラミングの場合Input/Output exampleも同時に与えられることが一般的である。人間がプログラミングする場合を考えるとInput/Output exampleを用いることでかなり正答率を上げられる気がする。ただ、そのような自然言語以外の入力を使うにはまだDNNモデルの改良が必要ではありそう。

気になる点は上記のようにあるが、とはいえProgram Synthesisも大量のデータを集めればある程度の性能は達成できそう、という見込みがでたのは大きな前進じゃないかと感じている。