言語処理学会 第24回年次大会 発表論文集 (2018年3月)

プログラミングコンテスト問題からのプログラム生成用データセットの作成
Panyam Chandrasekarasastry Nagesh∗
小田 悠介 ∥ 渡部 有隆 ∗∗江原 遥 †徳永 拓之 ‡鶴岡 慶雅 §高村 大也 †

コードに直接翻訳できない性質に富む．

1

直接的な翻訳ではないという性質に加えて，AIZU

はじめには自然言語によるプログラミング言語への容易なアク

プログラミングは習得に長い時間がかかり，人間にセスという当初の目的にふさわしい次の性質を持つ．

とって負担の大きい作業である．一方，自然言語は人テキスト部分が人手でチェックされており，プログラ間にとってなじみ深く，母語であれば特段大きな負担

ミング言語で明確な解答が存在するように作られていなくコミュニケーションをとることが可能である．こる点，また，他のデータセットと異なり，１つのテキスうした状況から，自然言語を介してプログラミング言トに対して，多くのコードが提出されている点である．

語にアクセスする研究が盛んにおこなわれている．例

本研究の貢献は以下のとおりである．

えば，自然言語からプログラムを生成したり検索した• コード生成・コード検索という挑戦的な課題のための，非翻訳的なデータセット AIZU を提案する．
• この挑戦的課題の研究のため，公に入手可能なAIZU データセットを作成したこと1 ．
• コード検索の設定でベースラインとなる実験結果を示したこと．

りする研究があげられる．こうした研究を遂行するため，既存では，プログラムコード（以下，単にコード）とテキストの組を集めたデータセットが作成されてきている [7, 6]．
しかし，これらの多くのデータセットでは，プログラミング言語を自然言語からより扱いやすくするという初期の目的とは裏腹に，テキスト部分はコードの直接の翻訳になっていることが多い．例えば，表 1 に示

2

関連研究

す StackOverflow データセット [3] では，テキスト部

テキストとコードの対をなすデータセットの構築時分の表現が，コードがどのように動作すべきかまで事に問題となるのは，コードに自然言語によるアノテー細かに指示していることが見て取れる．現実的な状況

ションを行う作業，またその逆にテキストに対応する

では，計算機がどのような動作をすべきかという手続コードを書く作業の負担が大きいという点である．しきが逐一わかっているわけではないことがよくある．

たがって，既存の研究では，この作業負担の問題をどもしそうした手続きが仔細に分かるのであれば，そのう解決するかに焦点が当たった．

手続きをプログラミング言語で明確に表現することが作業負担を減らす代表的な方法は，何らかの別の目可能であるので，自然言語でプログラミング言語にア的でテキストとコードの対が蓄積される既存の仕組みクセスすることの有用性は低い．

を探し，それをデータセット作成に転用しようという本研究では，テキスト部分が翻訳的でも手続き的で試みである．例えば，[7] では IFTTT という，自然言もないデータセットを提案する．表 1 の “AIZU” 部分

語と，多数のユーザが作成したショートカットキーのに，提案するデータセット（以下 AIZU）の例を示す．

ようなコマンド列（例：メール送信，ファイルを送る，提案するデータセットは，プログラミングコンテストなど）の組を用いた．しかし，この方法では，やはり練習用のジャッジメントシステムに蓄積されたデータ翻訳に近いデータしか収集できていない．もう一つのを活用している．プログラミングコンテスト用の問題

典型的な方法は，GitHub（http://github.com/）であるため，AIZU はより挑戦的で，プログラミングのような大規模なオープンソースのコード集合を用いて，コードに埋め込まれた自然言語によるコメントを∗メルボルン大学．† 産業技術総合研究所．‡ スマートニュース
株式会社．§ 東京大学．¶奈良先端科学技術大学院大学/情報通信研
究機構．∥ 会津大学．

1 https://aistairc.github.io/plu/ にて原則無償で公開予定．

― 694 ―

Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.

Dataset
AIZU
AIZU

ProblemAnswer

文字列集合を Find palindromes amongst given

filter ( lambda x : x ==set of String“”.join(reversed(x)) , list strings )Given the vertices of a triangle and a point, find if

def inside ( ax, ay, bx, by, cx, cy, x, y ) :it is inside the triangle?

...

StackOver-

What’s the idiomatic syntax for prepending to aflow

short python list?

StackOver-How can python return the filename currently

flow

being processed under Windowss.insert(0, x)
import os
filename = os.path.basename( file )print (filename)

表 1: 問題-コードペアの例

活用する方法である [1]．しかし，この方法では，文Stack-

書化の遅れなどによって，自然言語で表現されたコー性質

ドの機能と，実際のコードの機能に差があることが多

コード数55, 8821, 987

問題数55, 8826655, 8821, 98755, 8821, 987

問題の平均トークン数

915

回答の平均トークン数

20154

く，しかもそれを実際に確認する現実的な方法がないという問題がある．

妥当な (問題・コード)

その他のアプローチとしては，作業負担の問題に人的対の数労力で対応するものである．例えば，[4] は Hearthstone

不妥当な (問題・コーというカードゲームにおけるカードの操作だけにタド) 対の数スクを限定しつつ，人手でデータセットを作成した．
また，[6] はクラウドソーシングを用いて，Python のDjango という大規模なソフトウェアの各行に自然言語によるアノテーションを施すことで，データセットを作成した．

Overflow

AIZU

表 2: 各データセットの性質．妥当とは，コード部分が実際に問題部分で示された問題を解くことが確認されたことを示す．

3 Dataset
提案するデータセットである AIZU は，AIZU Onlineのあるサイトであり，日本語の問題を多く含む．オンJudge(AOJ)2 から取得した．AIZU Online Judge は，オラインジャッジサイトでは，プログラミング問題に一ンラインジャッジサイトと呼ばれる，プログラミング律の番号を振って問題を特定しやすくすることが行わコンテストの練習用のウェブサイトである．ユーザは，れており，AOJ でも 4 桁の番号で管理されている．問多数の問題からプログラミングの問題を選び，その問題文は一部英語に翻訳されているものの，大部分は日題を解くコードを投稿することができる．投稿された本語である．データセット作成の目的のため，公開部

コードが実際に問題に対する回答になっているかの判分のデータセットについては，すべて人手の翻訳者に定（ジャッジ）は，あらかじめ問題作成者によって問題よる問題の英語訳を付けた．

とともに用意されたテスト用入出力を用いて自動的に表 2 に，提案するデータセットの性質を示す．既存確認できる．オンラインジャッジサイトは，投稿されたのデータセットで典型的な StackOverflow データセッ

コードをコンパイルしてプログラムを実行し，テストトに比べて，AIZU データセットでは，問題の平均トー用の入力を与える．プログラムの出力が実際にテストクン数が大きいことがわかる．これは，AIZU データ出力と同一であったら，妥当，そうでなければ不妥当セットにおいては，より長い自然文の文脈をコード生と判定される．コードは，Python や C/C++など，様々成のために理解しなければならず，このデータセットなプログラミング言語で投稿することが可能である．

における問題が挑戦的であることを示唆している．

こうしたオンラインジャッジサイトは AOJ 以外にもまた，我々は，データセット中の問題のうち 100 問多数あり，Peking Online Judge(http://poj.org/)を実際に人手で分析して表 3 に示した．実際に人間などが有名である．AOJ は，日本では長期の運用実績が問題を解いた場合でも，正しいコードを提出できる

2 http://judge.u-aizu.ac.jp/onlinejudge/

ケースが半数を下回ることからも，このデータセット― 695 ―

Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.

における問題が挑戦的であることがわかる．また，こスの問題は，問題からコードに到達するまで推論と翻のデータセットでは，妥当な回答の数以外にも，提出訳の 2 段階を要する種類の課題とみなすことができるされたコードの数も，問題の難しさを示唆しているこのに対して，StackOverflow コーパスの問題は，問題とも，表 3 からわかる．簡単な区分けの問題に対してからコードに到達するまで翻訳の 1 段階のみを要する提出されたコードの数は，難しい区分けの問題に対し種類の課題とみなせる．そこで，これらの課題の性能て提出されたコードの約 2 倍にのぼる．

差をみるため，次の２つの設定を用意した．

4実験

4.1

比較対象のデータセット• 妥当なペアの識別: 与えられた問題-コードのペアに対して，コード部分が問題を解くコードか否かを識別する，二値分類タスクである．このタスク

AIZU 問題は AOJ のうち，特に簡単なパソコン甲子は，コード生成のサブタスクとみなすことができ園の問題を選んで用いた．これは，高校生が解くことる．コード部分が問題を解くかどうかを正確に判を想定したプログラミングの問題である．AOJ では複定できたとする．この場合，問題に対して多数の数のプログラミング言語で投稿することが可能である

正解コード候補を用意して，コードが問題を解くが，今回は，Python 言語に限定して実験を行った．こ

かどうかを識別する方法で，正しいコードを得る

れは，Python 言語によるコードが Java 言語や C 言語ことが期待できる．などと比較して短く，また，コードの構文解析も容易• コード検索: 一方で，妥当なペアの識別タスクは，であり，Python 言語の利用者が多く十分な投稿数があコード検索の観点からも有用である．コード検索

ること，などが理由としてあげられる．の観点からは，まず，GitHub のような大規模なStackOverflow 比較対象のデータセットとしては，コードベースが与えられた状況を想定する．そうStackOverflow[3] を用いた．これは，プログラミングしたコードベースには多数のコードが含まれていの質問サイトである StackOverflow から，質問とコーる．コード検索は，そうした多数のコードの中を，ドを自動抽出したものである．StackOverflow は質問サ与えられた問題を解いていそうな順にコードを並イトであり，質問者や他の読者が理解できればよいた

び変える，というタスクとみなせる．

め，自然言語を用いて回答しても良い点が，AOJ などのオンラインジャッジシステムと大きく異なる．その実験設定ため，コード中に自然文が含まれていたり，コード部解くコードの対を含む．これらの対は，前述の識別問

AIZU も StackOverflow も，問題とそれを分が一部の抜粋であるなどの理由で，投稿されたコー題における正例とみなすことができる．負例について

ドの 3 割は実行できなかった．

は，問題に対して，他の問題を解くコードを対にしてどちらのデータセットも，テキストとコードの対形作成した．正例対と負例対の数が同数になるように設式であることは共通しているが，問題の性質が異なる．

定した．どちらのコーパスでも，訓練/開発セットとテAIZU コーパスの問題は，論理や推論，アルゴリズム

ストセットを 60 : 40 の比率で分割した．この分割のなどの知識を必要とするものがほとんどである．一方，際には，訓練セットとテストセットに同じ問題が含ま

StackOverflow では，そのような問題もないわけではれることのないようにした．

ないものの，Python 言語の文法やライブラリの使いテキストと画像といったような，異なる２種のドメ方に関する質問が大半を占めており、質問に対応するインでの対に対する二値分類タスクに有効な手法としコードがパターン化しており、推論などの知識を使わて，Siamese Neural Network[5] が提案されている．本ないという意味で直訳的である．

研究ではこの研究を参考に，図 1 に示す構造のニュー4.2

ラル識別器を作成した．実装は Keras で行い，クロス評価

こうした挑戦的な課題におけるコード生成は，推論と翻訳の 2 つの段階に分割して考えることができる．
まず，自然言語で与えられている問題に対して，論理的推論を用いて，問題を解く解答を，擬似コードのような自然言語の枠組みに収まる言語で記述する段階である．次に，自然言語とプログラミング言語という異なる言語間で，翻訳を行う段階である．AIZU コーパ

エントロピー損失を Adam を用いて 20 エポックで減少させた．
コード検索の設定では，[3] と似た評価設定を用いた．ここでは，問題に対して，コード集合から正しいコードを取得する性能を測定したい．そこで，テストセットの各問題に対して，1 個の正しいコードと 49個の無関係なコードからなる 50 個のコード集合を用意し，上記の識別器を用いたときの検索性能を測定す― 696 ―

Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.

妥当な投難しさ

問題数

総投稿数

例

Hard

1918, 625

42%

Find if a given rectangle is convex ?

Medium1922, 865

48%

Find the reflection of a point over a line.

Simple2832, 663

50%Count palindromes amongst given strings.

稿数

表 3: AIZU データセットの複雑さ.

InputLayer
in:

out:

(N, 512)(N, 512)

InputLayer
in:

out:

(N, 512)(N, 512)Bi-LSTM
in:

Embed
in:

out:

(N, 512)(N, 512, 300)

Dense

out:

(N, 512, 300)

(N, 64)in:out:(N, 64)(N, 32)Bi-LSTM
in:

Dense

out:

(N, 512, 300)

Concatin:(N, 64)[(N, 32), (N, 32)]

in:

out:

(N, 64)(N, 32)Dense
out:(N, 64)

Dense

in:

out:

in:

out:

(N, 64)(N, 32)(N, 32)(N, 2)

図 1: 作成した二値分類器の構成図.

る．検索性能の指標としては，“Mean Reciprocal Rank

懸念がある．この懸念を確認するため，変数名をラン(MRR)” を用いた．これは，正例を高く順位付ける性ダム化した設定でも実験を行ったところ，識別設定で能を表す指標であり，値が高いほどよい．1.0 で，正は正解率が 53%にまで低下した．しかし，図 1 にお例より高く順位付けられている負例が存在しないこと

ける “Bi-LSTM” の層の直後に Batch Normalization[2]を表す．

を入れることにより，正解率は 55% にまで向上した

4.3（片側二項検定で有意水準 0.01 で統計的有意）．

結果と考察

識別器としては，前述の二値識別器を用いた．Sup-5

おわりにport Vector Machines などの古典的な識別器でも同様

本研究では，自然文によるコード生成・コード検索との設定で性能を評価したが，前述の二値識別器より低いう挑戦的課題の研究を遂行するためのデータセット

い正解率しか得られなかったので，本稿では割愛する．

を提案した．提案するデータセットは，プログラミン

表 4 に実験結果を示す．識別設定では正解率 (Accu-

グコンテストから取得した挑戦的な問題に富み，公開racy) を，コード検索設定では MRR を性能指標に用いされているため誰でも自由にダウンロードして利用すた．正解率については，ベースラインとなる 0.5 からることができる．本稿では，コード検索の設定におい有意に高い正解率であるかを，片側二項検定で検定してベースラインとなる性能を提示した．より広くデーた．有意水準 0.05 において，どちらのデータセットタセットを使っていただき，この分野の研究が進むこでも統計的有意な結果を得た．とを望む．

これらの実験においては，コード中の変数名が性能を向上させている可能性がある．例えば，問題に “ball”

謝辞
この成果は，国立研究開発法人新エネルギー・産業技術総という語が含まれていたら，“ball” という変数を含むコードを探すことによって高い性能が得られてしまう

合開発機構 (ＮＥＤＯ) の委託業務の結果得られたものです．
参考文献

二値分Corpus

類正解

P値率AIZU

Code 検索設
定での MRR

55%

0.017

0.16

65%

0.010

0.08

StackOverflow

表 4: 識別設定，コード検索設定での性能評価.

[1] Antonio Valerio Miceli Barone and Rico Sennrich. A parallel corpus ofPython functions and documentation strings for automated code documentation and code generation. arXiv:1707.02275 [cs], July 2017.
[2] S. Ioffe and C. Szegedy. Batch normalization: Accelerating deep network
training by reducing internal covariate shift. In ICML, pp. 448–456, 2015.
[3] Srinivasan Iyer, Ioannis Konstas, Alvin Cheung, and Luke Zettlemoyer. Summarizing source code using a neural attention model. In ACL, 2016.
[4] Wang Ling, Phil Blunsom, Edward Grefenstette, Karl Moritz Hermann,Tomáš Kočiský, Fumin Wang, and Andrew Senior. Latent Predictor Networks for Code Generation. In ACL, pp. 599–609, 2016.
[5] Jonas Mueller and Aditya Thyagarajan. Siamese recurrent architectures forlearning sentence similarity. In AAAI, pp. 2786–2792, 2016.
[6] Y. Oda, H. Fudaba, G. Neubig, H. Hata, S. Sakti, T. Toda, and S. Nakamura.
Learning to Generate Pseudo-Code from Source Code Using Statistical Machine Translation (T). In ASE, pp. 574–584, November 2015.
[7] C. Quirk, R. Mooney, and M. Galley. Language to Code: Learning Semantic
Parsers for If-This-Then-That Recipes. In ACL-IJCNLP, pp. 878–888, 2015.

― 697 ―

Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.