Measuring Coding Challenge Competence With APPS

https://arxiv.org/abs/2105.09938
2021

プログラミングは現代社会で最も広く適用できるスキルの一つですが、最新の機械学習モデルでは、基本的な問題に対する解決策をコード化することができません。コード生成の性能を正確に評価することは困難であり、柔軟かつ厳密な方法でコード生成を評価する研究は驚くほど少ない。この課題を解決するために、コード生成のベンチマークであるAPPSを導入しました。このベンチマークは、より限定された環境での先行研究とは異なり、任意の自然言語仕様を受け取り、その仕様を満たすPythonコードを生成するモデルの能力を測定します。企業がソフトウェア開発者の候補者を評価するのと同様に、我々は、生成されたコードをテストケースでチェックすることでモデルを評価します。ベンチマークには10,000の問題が含まれており、1行で解決できる簡単なものから、アルゴリズム上の大きな課題となるものまで様々です。大規模な言語モデルをGitHubと学習セットの両方で微調整したところ、構文エラーの発生率が指数関数的に減少していることが分かりました。 GPT-Neoのような最近のモデルは、入門的な問題のテストケースの約15%をパスすることができ、機械学習モデルがコードの書き方を学び始めていることがわかります。今後、コードの自動生成の社会的意義が高まっていく中で、本ベンチマークは、その進歩を追跡するための重要な指標となります。

https://github.com/hendrycks/apps

1 はじめに

コンピュータ・プログラミングは、社会のほぼすべての場所で目にすることができます。エンターテインメント、医療、教育など、プログラミングは非常に汎用性の高いツールであり、その応用範囲は多岐にわたります。コンピュータが現代生活の中でより多くの場所で使われるようになるにつれ、高品質なコードへの要求が高まり、プログラマーを目指す人の数はますます増えています。人間の専門家は、多様な認知タスクの抽象的な仕様を具体的なプログラムに変換するために、何年も勉強して熟練したプログラマーになる。ここ数年、大規模言語モデルは、言語的推論（Wangら、2019a）、常識的推論（Zellersら、2019；Huangら、2019；Biskら、2019）、論理的推論（Liuら、2020b）、数学（Hendrycksら、2021c）、人間の知識の複数の領域の一般的理解（Hendrycksら、2021b）など、さまざまな認知タスクに一般化することに期待が寄せられている。しかし、大規模な言語モデルが確実にコードを書けるかどうかは、まだ未解決の問題です。最近の研究では、言語モデルがコードを翻訳し、コンパイルの問題を修正できることが実証されているが（Yasunaga and Liang, 2020）、一般的なコーディング問題を与えて大規模言語モデルのコーディング能力を厳密にテストする研究は驚くほど少ない。厳密な評価の必要性と、これらのモデルが示す可能性に触発され、我々は自然言語仕様からのコード生成のベンチマークであるAPPSを紹介する。

言語モデルを用いたコード生成に関する先行研究では、コード変換や擬似コードからコードへの変換に主眼が置かれていますが、本研究では、自然言語で与えられた仕様を受け取り、その仕様を満たすコードを書く能力についてモデルを評価します。この設定は、人間のコーダーが評価される方法を反映しており、モデルをベンチマークする上で、より現実的で有益な設定です。 APPSは、モデルを様々な角度からロバストに評価することができるため、コード生成能力を正確かつ包括的に把握することができます。 APPSには、簡単な入門問題からコーディングコンテストの課題まで、さまざまな難易度のプログラミング問題が10,000問収録されています。 APPSは、言語モデルのコード生成能力を評価する先行研究とは大きく異なる点を指摘しています。 APPSでは、コードの文法を理解する能力だけでなく、タスクの記述を理解し、そのタスクを解決するためのアルゴリズムを考案する能力も評価しています。モデルがAPPSで好成績を収めるということは、データ構造やプログラミング技術を柔軟に使いこなす能力や、多様なタスクの仕様を正しく解釈し、指示に従い、人間の意図を理解する能力があることを示しています（Hendrycks et al.

ほとんどの自然言語生成問題では，高品質な評価には人間のフィードバックが必要であり，それにはコストがかかる．そのため、BLEU(Papineni et al., 2002)のような自動評価指標が手法の比較に用いられることが多い。コード生成では，正しい機能を生成することが目的であるため，テストケースやエラーキャッチによる評価が可能である． APPSでのコード生成の評価は、130,000以上のテストケースと230,000以上の人間が書いたソリューションからなる大規模なバンクによって促進される。テストケースは、エッジケースを含む入力空間全体の正しい機能を調べるために特別に選ばれています。テストケースを使用することで，モデルの性能を測る金字塔的な指標を提供することができます．実験では、モデルがコーディング問題を解決するためのコードを生成できるようになってきていることがわかりました。

モデルは、ゼロではない精度を示し始めています。また、シンタックスエラーも指数関数的に減少しています。また、BLEUはコード生成のための指標としては問題があり、ゴールドスタンダードの精度とは反比例することがあることもわかりました。精度は難易度に応じて低下し、微調整とモデルサイズの増加によって向上することがわかりました。評価した最強のモデルは27億個のパラメータを持ち、入門的な問題のテストケースのほぼ15%をパスしました。これらの結果から、コード生成は大規模言語モデルのテストベッドとして、難易度は高いものの扱いやすいものであると言えます。

自然言語で仕様を満たすコードを書くことは、経済的に価値のある作業であり、解決すれば、悪意のあるコード生成を容易にし、いつかは仕事の自動化につながるという意味で、広く社会に影響を与える。大規模な言語モデルは、コード生成を大きく前進させる可能性があるため、このタスクの進歩を追跡することが不可欠です。この新しいベンチマークは、包括的かつ厳密な方法で性能を測定することを可能にします。 APPSを使ってみると、最近の言語モデルではプログラミングが非常に難しいことがわかります。 APPSベンチマークは、自然言語からプログラムを合成するという重要なタスクにおいて、将来の大規模な言語モデルの性能を予見することができます。データセットと実験コードはgithub.com/hendrycks/appsで公開しています。

3 APPS データセット

APPS データセットは，Codeforces や Kattis など，さまざまなオープンアクセスのコーディングウェブサイトから収集した問題で構成されています． APPS ベンチマークは，制限のない自然言語でコーディング問題を出題し，その解答の正しさを評価することで，人間のプログラマーがどのように評価されるかを反映しようとしています．問題の難易度は、入門レベルから大学の競技レベルまで幅広く、問題解決だけでなくコーディング能力も測定します。 APPS（Automated Programming Progress Standard）と呼ばれるこのテストでは、10,000問のコーディング問題が出題され、解答を確認するためのテストケースが131,836件、人間が書いた解答が232,444件となっています。問題の平均長さは293.2語で、問題は複雑なものになります。データはトレーニングセットとテストセットに均等に分けられ、それぞれ5,000個の問題が用意されています。テストセットでは、すべての問題に複数のテストケースがあり、テストケースの平均数は21.2個です。各テストケースは、対応する問題に合わせて設計されており、プログラムの機能を厳密に評価することができます。データセットの構築 APPS データセットを作成するために，Codewars，AtCoder，Kattis，Codeforces など，プログラマー同士が問題を共有するオープンアクセスサイトから問題を手動で収集しました．問題は、何をコーディングすべきかという制約のない自然言語の仕様として提起され、様々なフォーマットで提供されています。品質と一貫性を向上させるために、問題のソースごとにカスタムHTMLパーサーを使用しています。これにより、問題テキスト内のLaTeX式、リスト、セクションを適切にフォーマットすることができます。また、必要に応じて、MathPix APIを用いて画像をLaTeXに変換し、重要な情報を画像に頼っている問題を削除しています。また、SVDによる次元削減とコサイン類似度を用いたtf-idf特徴量を用いて重複排除を行います。このデータセットは、複数の大学院生と学部生が半年間かけて磨き上げたもので、高品質な問題群を確保しています。我々がデータを入手したウェブサイトでは、人間のソリューションは、一般的なモジュールやライブラリのインポート文を含む、任意のコードを実行することができます。任意のPythonコードを実行して評価することは困難です。そのため、各Webサイトでは独自の判定システムを導入しています。そこで、複数のサイトの判定機能を統合したテストフレームワークを設計しました。また、テストケースのフォーマットを標準化しました。最終的には、ソリューションは任意のPythonコードを実行することができ、その結果は、与えられた問題のテストケースと比較されます。

データセットの難易度。各問題集では、難易度を測定するために別の尺度を使用しています。これを問題ソース間で3つのカテゴリに標準化します。例えば、Kattisの問題で難易度が3未満のものは「入門」、難易度が3～5のものは「面接」、難易度が5以上のものは「競技」と分類しています。

入門レベル。複雑なアルゴリズムを必要とせず、1〜2年の経験を持つほとんどのプログラマーが答えられる問題。例えば、ある部分文字列の出現回数を数えたり、ある文字列が回文であるかどうかを調べたりすることができる。入門レベルに分類された問題は3,639問、テストセットには1,000問あります。

2.面接レベル。よりアルゴリズム的に難しい問題で、難しい技術面接で聞かれるようなレベルの問題である。例えば、木やグラフなどのデータ構造に関わる問題や、一般的なアルゴリズムを修正する必要がある問題などが挙げられます。面接レベルに分類された問題は5,000問、テストセットには3,000問あります。

競技レベル。さらに難易度の高い問題で、USACO、IOI、ACMなど、高校や大学の最先端のプログラミングコンテストのレベルの問題です。競技レベルに分類された問題は1,361問、テストセットには1,000問あります。

問題の形式。様々な問題に対応できるように，APPSの問題は2つの形式で構成されています．

問題長さnの文字列s = s1s2 ... snが与えられ，この文字列には1, 2,..., 9の数字しか含まれていない． s の部分文字列 s[l . . . r] は，文字列 slsl+1sl+2 ... sr である． s の部分文字列 s[l . . . r] は，それが表す数字が偶数である場合，偶数と呼ばれる． sの偶数の部分文字列の数を求めよ。ただし、文字列としては同じでも、lとrが異なる部分文字列があっても、それらは異なる部分文字列として数えられる。 1行目には，文字列sの長さを表す整数n (1 ≤ n ≤ 65000)が入り，2行目には，長さnの文字列sが入ります。 s の偶数の部分文字列の数を表示せよ．

Model Output

コールベース形式の問題では、通常、関数ヘッダーの形で最初のスターターコードを提供し、関数の戻り値としてソリューションを提供することを求めます。
標準入力形式の問題は、一般的にスターターコードがありません。その代わり、モデルには問題のみが提供され、print文を使用するなどして、答えをSTDOUTストリームに出力しなければなりません。

呼び出しベースの形式の問題では、以下の入力を使ってモデルを促します。

"\nQUESTION:\n" + q_str + "\n" + starter_code_str + "\n" + "\nUse Call-Based Format\n\nANSWER:\n"

上記の両方のプロンプトについて、変数q_strは、問題文の生のテキストを表します。変数starter_code_strは、問題定義で与えられたスターターコードを表し、スターターコードが与えられていない場合は空の文字列を表します。標準入力フォーマットの問題では、以前と同様に入力文字列でモデルを促しますが、"Call-Based Format "を "Standard Input Format "に置き換えています。スターターコードが与えられた場合、それは入力の一部に過ぎないことに注意してください。つまり、スターターコードを使用するためには、モデルは問題を正解するために出力される答えの最初にスターターコードをコピーすることを学習しなければなりません。改良されたモデルであれば、難なくこれを実行できることがわかります。

4 実験

本節では、APPSベンチマークを使用して、様々なTransformer（Vaswani et al. その結果、微調整やモデルサイズの拡大によって精度が向上し、難易度が上がるにつれて精度が低下することがわかりました。さらに、シンタックスエラーは減少しており、生成されたコードは一見して定性的に妥当であることがわかります。モデルは、入門的なコーディング問題にも効果を発揮し始めています。

4.1 実験セットアップ

モデル GPT-2 (Radford et al., 2019)、GPT-3 (Brown et al., 2020)、GPT-Neo (Black et al., 2021)のモデルを使用します。 GPTアーキテクチャは、自己回帰的であるため、特にテキスト生成に適しています。ただし、GPT-2はコード上での事前学習が行われていなかったため、後に展開するようにGitHub上で事前学習を行います。逸話によると、GPT-3はコードを生成できるようです。どの程度のコード生成能力があるのかを判断するために、1750億個のパラメータを持つと推測される公開されている最大のモデル「davinci」(Instruct Series)を使用しています。最後に、GPT-NeoのアーキテクチャはGPT-3と同様に、GitHubを含むPile(Gao et al., 2020)を事前学習しています。GPT-3とは異なり、GPT-Neoの重みは公開されているため、APPSのトレーニングセットで微調整を行うことができます。

問題 2つの整数nとmが与えられた．両方の配列の長さがmに等しく，各配列の各要素が1からnまでの整数であり，1からmまでの任意の添字iに対してai≦biであり，配列aが非降順にソートされ，配列bが非昇順にソートされるような配列(a,b)の組の数を計算せよ．結果が非常に大きくなる可能性があるので，モジュロ10^9 + 7で表示すべきである．入力．唯一の行には，2つの整数 n と m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10) が入っている．出力します． 1つの整数-上で述べた条件を満たす配列aとbの数をモジュロ10^9 + 7で表示せよ。

GPT-2の事前学習。 GPT-2はコードではなく自然言語で訓練されているので、GPT-2をさらに事前に訓練するためにGitHubのコードを集めました。星の数が1つ以下のGitHubリポジトリはフィルタリングされ、一般的なプログラミング演習との重複を示す特定のキーワードにマッチするリポジトリもすべて除外されました。キーワードのリストは付録に掲載しています。また、多くのAPPS問題のスターターコードに含まれる関数と同じシグネチャを持つ関数を含むGitHubのコードもすべて捨てました。これにより，30GBのPythonコードが残りました．事前学習の効率を上げるために、事前学習用データセットに含まれる全てのPythonコードをスペースからタブに変換して処理し、モデルのトークナイザーを実行する際の文字変換を省きました。

ファインチューニング APPSを用いたファインチューニングでは、英語の問題文と問題のフォーマット（コールベースのフォーマットまたは標準入力フォーマット）の両方が与えられた場合に、コードソリューション全体を予測することを目的としています。スターターコードがある問題では、スターターコードをトレーニングロスから除外します。事前トレーニングと微調整の間で、AdamWオプティマイザー（Loshchilov and Hutter, 2019）、バッチサイズ256、ウェイトディケイ0.05を使用します。 10回のエポックで微調整を行います。大規模なモデルをトレーニングしている間のメモリ消費量を削減するために、DeepSpeedとその実装であるZeROオプティマイザーを使用します（Rasley et al.2020; Rajbhandari et al.2020）。特に指定のない限り、ビームサイズが5のビームサーチを使用することを除いて、デフォルトのHuggingFace生成パラメータを使用しています。

4.2 メトリクス

コード生成能力を総合的に評価するために，APPS が提供する膨大なテストケースとグラウンドトゥルースのソリューションを利用した．テストケースは，プログラムの可能性が組合せ的に大きいにもかかわらず，自動的に評価することができる．そのため、他の多くのテキスト生成タスクとは異なり、手動による分析は必要ありません。生成されたコードのテストケースに対する性能を、"test case average "と "strict accuracy "という2つの指標で集計します。

テストケースの平均。テストケースを通過した割合の平均を計算します。具体的には，テストセットに含まれる問題数をPとし，ある問題pに対して，問題pを解くために生成されたコードを，問題pのテストケースの集合を{(xp,c, yp,c)}_c=1^C_pとする．すると、テストケースの平均値は

多くの場合、ソリューションはテストケースのサブセットを成功させることができても、すべてのコーナーケースをカバーすることはできません。これにより、厳密な精度ではモデルの改善が見えなくなる可能性があるため、モデルの評価をそれほど厳しくしないことができます。

厳密な精度。最終的に、生成されたソリューションは、コーナーケースを含むすべてのテストケースに合格する必要があります。すべてのテストケースにプログラムが合格することを要求する厳密な精度を計算するために、モデルによって生成されたコードをすべての問題のすべてのテストケースで実行します。そして、すべてのテストケースを通過した解の数を、全問題数で割って厳密な精度を算出します。先ほどの表記法を使って、厳密な精度を1/ P Sum{p=1}^{P} Prod^{Cp}{c=1_ 1{eval((codep), x{p,c}) = y_{p,c}}と書くことができます。

4.3 モデル性能分析

定性的出力分析。モデルは，正しいコードや表面的にはもっともらしいコードを生成することがあります．図2は，GPT-2 1.5Bが生成したコードのうち，すべてのテストケースに合格したものです．モデルがテストケースを通過しない場合でも、生成されたコードが一見してもっともらしく見えることがあります。例えば、図3では、1.5Bのパラメータモデルが、問題文に関連するコードを生成し、その問題を解決しようとするもっともらしい試みを行っていることがわかります。

テストケースの評価主な結果を表2に示します。これは，生成されたプログラムの多くが，構文エラーがなく，入力されたテストケースを処理して正しい答えを生成できることを意味しています．入門問題では、GPT-Neoは約15%のテストケースを通過しています。

テストケースの平均値の結果を図4に示します。この結果は、コード生成において顕著な改善が見られ、コード生成においても人気が出始めていることを示しています。この結果は、モデル選択の重要性を示唆するものです。既存の少数ショットのGPT-3モデルが、2桁小さい微調整されたモデルよりもコード生成に優れているとは限りません。また、GPT-2 1.5BからGPT-Neo 2.7Bへの性能向上は、GPT-2 0.1BからGPT-2 1.5Bへの性能向上よりも大きい。 GPT-2モデルもGPT-Neoも、数十ギガバイトのGitHubコードでプリトレーニングされているので、モデルサイズの増加に伴ってコード生成の改善が加速しているか、GPT-Neoのアーキテクチャが優れていることを示唆しています。パフォーマンスが問題の難易度に追従していることから、暗記という説明は考えにくい。モデルが単に暗記しているだけなら、難易度に関係なく一様なパフォーマンスが期待できる。モデルにはまだ大きな改善の余地があるので、APPSベンチマークを無理な計算資源を使わずに解くには、アルゴリズムやアーキテクチャの改善が必要かもしれません。

構文エラー。ここでは、シンタックスエラーの頻度を評価します。シンタックスエラーとは、プログラムの解釈を妨げるエラーのことで、スペーシングの不一致、アンバランスなブラケット、コロンの欠落などがあります。図5は、シンタックスエラーの発生状況を視覚化したものです。 GPT-3が生成した入門問題の解答の約59%にシンタックスエラーがあるのに対し、GPT-Neoのシンタックスエラー頻度は約3%です。なお、Yasunaga and Liang (2020) などの最近の研究では、コンパイル時の問題を修正するためにソースコードを修復するモデルを別途作成していますが、今回の結果では、シンタックスエラー頻度が急激に減少しているため、将来的にはそのような努力は必要ないかもしれません。

BLEU BLEUを用いてモデルの性能を評価することは、テストケースを用いた評価の代わりにはならないことがわかりました。 BLEUを評価するためには、生成された解答を用いて、与えられた問題に対する人間が書いた解答とのBLEUを計算し、最も高いBLEUスコアを記録します。図6では、問題の難易度が高くなるにつれてBLEUが増加していることがわかります。さらに、悪いモデルでもBLEUスコアが同等かそれ以上の場合があります。例えば、GPT-2 0.1BのBLEUスコアは、入門問題、面接問題、競技問題でそれぞれ26.8、29.7、30.2となっています。一方、GPTNeo 2.7BのBLEUスコアは、それぞれ27.1、29.1、29.3となっています。したがって、BLEUはGPT-Neoの方が悪いモデルであると誤って示唆していることになります。

5 結論

1万件のPythonプログラミング問題のベンチマークであるAPPSを紹介しました。擬似コードからコードへの生成やプログラミング言語間の翻訳に焦点を当てた先行研究とは異なり、我々のベンチマークでは、自然言語の仕様が与えられたときに言語モデルがどれだけPythonコードを生成できるかを測定します。このベンチマークでは，広範囲な品質保証を行い，異なる難易度の数十万のテストケースとグランドトゥルースのソリューションを含めることで，モデルを評価するための包括的で厳密なテストベッドを作成しました．最先端の生成モデルをこのベンチマークで評価したところ，全体的な性能は低いことがわかりました．しかし、シンタックスエラーの有病率は、モデルの規模を大きくして微調整することで指数関数的に減少し、GPT-Neoのような最近のモデルは、多くの入門的な問題を解決しました。モデルのコード生成能力が向上すると、自動化や悪意のあるコードの生成に関する懸念が生じる可能性があります。 APPSベンチマークは、プログラム合成の進歩を追跡するための重要な指標となり得る。

e4exp / paper_manager_abstract