プログラムを書く Deep Learning の現状

先日 Deep Learning でプログラムのエラー修正ができるという論文の紹介記事¹が話題になりました。 他にはすこし前ですが、 DeepCoder² と呼ばれるコード生成の記事もよく見かけました。 若干煽りっぽいタイトルもあって、 Deep Learning によって訪れるコーディング環境の変化やプログラマの未来像に思いを馳せた人もいるのではないでしょうか。 ですが、これらの記事では論文によって実現できたこと、できていないことが明示されていません。 ここではこれらの手法をより具体的に掘り下げて紹介したいと思います。

DeepFix: Fixing Common C Language Errors by Deep Learning³

上記の「RNN でプログラミング言語の構文エラーを自動修復する衝撃」で紹介された論文です。 閉じカッコやセミコロンの書き忘れのような、不注意による文法エラーを自動で修正することを試みています。 現状でも C 言語のコンパイラは文法エラーを検知できますが、プログラムのどこが間違えているのかを正しく指摘することはできません。 コンパイラはプログラムのパースに失敗した箇所を指摘するためです。 この論文は自動的にプログラムのエラー位置を特定し、それを修正する手法を提案しています。

手法

Attention 機構を導入した Recurrent Neural Network (Seq2seq) を用います。 基本的にはエラーを含むプログラムを入力系列とし、エラーが解消されたプログラムを出力系列として学習すれば自動エラー修正が実現します。 しかし、プログラムのように長く、かつ正確性が求められる系列を RNN に学習させるのは難しいようです。 そこで、プログラムを文（sentence）ごとに分割し、行番号を用いて (修正すべき行番号, 修正後の文) のペアを出力とするように学習させます。 入力プログラムに対して修正すべき箇所と修正内容が出力される RNN というわけです。 出力された行番号に対応する部分の入力系列を上書きし、修正済みプログラムとすれば自動修正となります。

この方法では 1 度に 1 つのエラーしか修正できないので、1 つのプログラムを繰り返し RNN に適用する（Iterative Repair）必要があります。 RNN で 1 箇所を修正するごとにコンパイルし、エラーが減るかを確認しながら全体の修正を進めていくので、1 度にすべてのエラーを修正するよりも確実性の高いエラー修正が可能となります。 また、文を修正するだけではなく、新たな行に対して出力したり特定の行に対して空文字列を出力したりすることで文の追加・削除も可能です。

実験

エラーのないプログラム 9230 個を編集し、コンパイルエラーが発生するようにしたものを学習データとして用意します。 1 つのプログラムの長さは平均 206 token （FizzBuzz の 2~3 倍くらい？）。 プログラムごとに最大 5 箇所を編集しており、そのうち 1 つめのエラーを修正するように RNN を学習させます。

テストデータは C 言語の授業で課題として提出されたプログラム 6971 個で、プログラム長は平均 203 token、コンパイルすると全体で 16742 個のエラーが発生します。 学習後の RNN を用いて修正した結果、1881 個のプログラム（27%）を完全に修正することができ、1338 個（19%）を部分的に修正することができました。 エラー数でいうと全体の 32% が解消されています。

自動修正ではなく、問題のある箇所を指摘するツールとして用いる場合は「修正できたか」の精度ではなく「エラー箇所が特定できたか」の精度が重要になりそうです。 これを人為的な編集でエラーを発生させたデータに対して調べたところ、全体の 78.68% のエラーの発生原因を正しく特定できていました。 候補を 5 つ提示してそのなかに正解があるかを確かめる方式（top-5）だと 87.50% の正解率となります。

DeepCoder: Learning to Write Programs⁴

マイクロソフトの新しい AI は、他のプログラムのコードを拝借してコードを書く という記事で紹介されている論文です。 「他のプログラムのコードを拝借」とありますが論文によるとプログラムの拝借は一切行われません。 タイトルが煽り過ぎているのでは（もしくは自分が読む論文間違えている可能性もある）。

この論文で扱う問題は "Inductive Problem Synthesis" と呼ばれるもので、 与えられた入出力要件を満たすプログラムを生成する問題です。 競技プログラミングの問題を自動で解くようなイメージです。 ただし問題文のような自然言語による情報は用いず、入出力ペアのみからプログラムを構築します。

DeepCoder は以下のようにプログラムを生成します。

1. 入出力要件を満たすプログラムに必要な制御構文や命令、数値リテラルの出現確率を DNN で予測
2. 予測した出現確率に基づいてプログラムを全探索
3. 入出力要件を満たすプログラムが発見できたら終了

先に紹介した論文では RNN がプログラムを出力するモデルでしたが、 DeepCoder は基本的にプログラムを（深さ有線探索のような）全探索で求めます。 DNN が必要だと判断した言語機能を優先的に探索することで、プログラム生成が高速化できるというわけです。

C 言語などの汎用言語で用いられる構文やリテラルをすべて出力可能にすると探索空間が広いので、 ここでは SQL-like な簡易 DSL を用いています。 この DSL は一般的な言語と比べて記述力がかなり限られており、たとえばループを含むアルゴリズムが記述できません。 探索方法は深さ有線探索や "Sort and add enumeration"、$\lambda^2$ などを実験で試しています。

実験

DNN を導入したことによる探索の高速化を実証します。 まず長さ 5 のプログラム（5 命令?）とそのプログラムが満たす入出力を自動生成し、これを学習データとして DNN を学習します。 次に同様の方法で生成した入出力要件から DeepCoder でプログラムを探索し、DNN を用いずに探索した場合とどれくらい処理速度に差があるかを確かめます。 DNN を導入した場合も探索空間は変わらないので（探索順序が変わる）、ワーストケースでは同じ時間がかかることになります。 そこで、論文では 100 個の問題のうち 20%、40%、60% を解くことができた時刻がどれくらい早くなったかを計測することで評価としています。 結果、どの探索方法でも 2~1000 倍の高速化が達成できたとのことです。

実際のプログラミング問題に適用して解けた問題のサンプルが論文にありましたので、ひとつ紹介します。

まとめ

DeepFix と DeepCoder を紹介しました。

1 つめの DeepFix を実用できるかの視点で考えた場合、プログラムを修正するツールとして使うにはまだまだ及ばないのが現状と思います。 エラー箇所を正しく参照するためのツールとしてなら使えるのかもしれません。 ただし今回の実験は小規模な C プログラムを対象としたものなので、中規模以上のプログラムではどのようになるか不明です。 エラーの原因らしき部分をハイライトするような入門者向けの補助ツールとしては現状でも十分に便利そうです。

疑問点としては、エラーを自動で修正するツールとして見た場合、ロジックが変更されうる修正を採用してしまう可能性が残っていることです。 たとえばエラーがある行を修正ではなく削除してしまえばコンパイルが通るようになることもあると思われます。 このことは論文でも言及されており、詳しくはわかりませんでしたが、Iterative Repair の際にコンパイルの成否に加えテストケースをパスできるかを確かめているのかもしれません。

2 つめの DeepCoder は入出力要件からプログラムを生成する手法でした。 これは「プログラマの職を奪う」ような文脈で語られるのを見かけますが、そもそもプログラマの職を奪うような問題設定になっていない気がします。 入出力要件を満たす機能がほしいのであればそれを満たすニューラルネットを構築して学習させればよくて、わざわざプログラムを生成する必要はありません。 プログラムを生成するのは生成結果が妥当かどうかをプログラマが判断するためのものであるように思います。 やはりプログラマの補助ツールとしての活用に期待するべきものではないでしょうか。 ちょっと考えるのが面倒になるような Rx とかが生成できたら面白いと思います。

紹介した論文はどちらも 2017 年の学会で発表されたものですが（論文が公開されたのはもっと前）、 近年の機械学習の進歩は著しく、さらに発展した論文がすでに現れています。 たとえば "A Syntactic Neural Model for General-Purpose Code Generation"⁵ では、 英文から Python のコード（実際は抽象構文木）を直接生成する RNN を試みています。 プログラミングの環境が一変するような未来は近づいてきているのかもしれません。