Learning to Generate Code Sketches

[e4exp]

• https://arxiv.org/abs/2106.10158
• 2021

従来の生成モデルは、末端トークンのシーケンスを予測することに限定されていた。 しかし、生成タスクに曖昧さがあると、誤った出力になる可能性がある。 この問題を解決するために、我々は、穴のあるトークンのシーケンスからスケッチを生成することを（明示的な監督なしに）学習する、変換器ベースの文法ガイドモデルであるGrammformersを導入する。 強化学習により、Grammformersは、ターゲットタスクに曖昧さがある場合、間違ったトークンの生成を避けるために、穴を導入することを学習する。 文章レベルのソースコード補完、すなわち、部分的なコードコンテキストのような曖昧なユーザの意図を与えてコードスニペットを生成するために、Grammformersを学習する。GrammformersをC#とPythonのコード補完で評価したところ、従来の生成モデルと比較して10-50%精度の高いスケッチを生成し、同様の技術で学習したスケッチ生成ベースラインと比較して37-50%長いスケッチを生成することがわかった。

[e4exp]

1 はじめに

機械学習モデルやツールは、完全に自律的な動作を目指すことが多いのですが、多くの場合、（人間の）ユーザーが何らかの目標を達成できるように、ユーザーと協力する必要があります。 近年の言語モデル（LM）の登場により、TransformerベースのLMが現実的なテキストを生成することが示されているが、特定の目標に向けてLMを誘導することは難しい場合が多い。 そのようなシナリオの1つが、ソースコードのLM（LMC）です。Hindleら[13]以来、Svyatkovskiyら[34]、Fengら[9]のような変換器ベースのものや、TabNineやSourceAIのような未発表の類似モデルなど、ますます洗練されたLMCが構築されている。 これらのモデルは、コードトークンの左から右への完全なシーケンスを生成し、任意のプレフィックスが（部分的な）ユーザーの意図として機能する。 LM は現実的な出力を生成する一方で、時折「幻覚」を起こすことが知られている [27, 22, 23, 19]。 幻覚を避けることは、モデルが人間と協調する必要がある場合に有効である。 ミスはユーザーを混乱させ、ユーザーの経験を悪化させ[14]、誤ったコードを導入することでユーザーを誤解させる可能性がある。 この問題を解決するために、我々はGRAMMFORMERを作成した。

GRAMMFORMERは、変換器ベースの文法ガイド付きコード生成モデルであり、コードスケッチ、すなわち穴（"■"で示される）のあるコードトークンのシーケンスを生成する。 GRAMMFORMERは、コードの実際のトークンが不確かな場合、穴を挿入するように訓練されています。 穴があることで、GRAMMFORMERはユーザーの意図の曖昧さ（例えば、部分的なコードの文脈や曖昧な自然言語の記述）をうまく扱うことができ、その結果、より正確ではあるが、部分的または抽象的な予測をすることができます。

例えば、図1（左）では、開発者がコードを入力し、次の行を入力しようとしています。 この文脈では、開発者の意図は曖昧ですが、GRAMMFORMERは正しくスケッチを提案しています（図1；右下） - 開発者は第3のフラグを宣言したいと合理的に推測しています。し かし、旗の名前を推測するのは時期尚早であるため、穴が開いています。 開発者は、モデルに潜在していた実際の意図に基づいて、この穴を埋めることができます。ここで、GRAMMFORMERは複数のトークンを生成しながらも、実際の表現について十分な確信が持てない場所に穴を生成し、結果的に有用なスケッチになっていることに注目してください。 これは、従来の生成モデル（例：図1；右上）では、導入された穴の位置に誤ったトークンを「幻覚」させる必要があったのと対照的です。 これを実現するために、GRAMMFORMERは、スケッチ生成のための決定空間を自然に構成することができる文法駆動型生成（図2）を使用しています。

貢献度

(1) プログラミング言語の文法に基づいてコードを生成する変換器ベースのモデルであるGRAMMFORMERを提示する。これは、コードトークンを左から右に生成したり、構文木を線形化したりするのではなく、文法に基づいてコードを生成する。 (2) GRAMMFORMERは、拡張する非終端記号を任意の順序で選ぶことができ、生成された出力の任意の位置に穴を作るコード生成を止めることができるので、穴のあるコードスニペット、すなわちスケッチを生成する能力を持つ。GRAMMFORMERの学習には、強化学習の手法を用いる。 (3) 最後に、PythonおよびC#コードの大規模コーパスを用いてGRAMMFORMERを評価し、左から右へのトークンレベルのモデルと比較して、より長く、より正確なステートメントレベルのスケッチ補完が可能であることを示す。

[e4exp]

2 GRAMMFORMER

GRAMMFORMERは、文脈自由文法（CFG）に従って、どの非終端をどのように展開するかを反復的に決定してテキストを生成します（図2）。 ほとんどのプログラミング言語は文脈自由です。 従来の文法ベースのテキスト生成[7]やコード生成[21, 38, 2, 5]では，CFGに従って，Rの生成規則の1つを用いて，最左端から最下端までの非終端記号を順次展開していた． GRAMMFORMERはこれを変更し，代わりにどの（もしあれば）非終端記号を展開するかを選択する． 最近の研究[38, 5, 16]と同様に，GRAMMFORMERはCFGの仮定を緩めているが，次のような多くの点を残している． Alg. 1はGRAMMFORMERの高レベルの説明です。 また，図2に生成例を示します． 確率モデル CFGはタプル(Σ, N , S, R)として定義される。ここでΣは終端記号の集合、Nは非終端記号の集合、S∈Nはルート記号、Rはプロダクション（またはプロダクションルール）の集合である。 具体的な非終端記号を「⟨NonTerminalName⟩」と表記する。GRAMMFORMERは、x0 = x0,1, x0,2, ..., x0,n (x0,i∈Σ∪N) 、すなわち、x0は、終端記号と非終端記号のシーケンスである、というシーケンスを入力として受け入れる。 図2の上段にx0の例を示す。

ここで，N（xt）＝ {i ∣ xt,i∈N }」∪ {⦸}、すなわちxt内の非終端記号の全ての位置と特別な"⦸"記号の集合である。 GRAMMFORMER は非終端記号展開モデル Pe(y∣x, i) と非終端記号選択モデル Ps(i∣x), i∈N(x) の 2 つのサブモデルから構成されています。 Alg. 1 のループの各反復において、Ps は確率を算出する。Ps は Alg.1 のループを繰り返すたびに、次に展開される非終端記号のインデックス it と特殊な停止記号をサンプリングした N(xt) 上の確率分布を生成します。 それが与えられると，Peは，選択された非終端記号xt,itの拡張シーケンスy = y1, y2,⋯を生成し，yi∈Σ∪Nを生成します． 最後に，展開された非終端記号xt,itの前の接頭辞xt,<itと，生成された展開yと，展開された非終端記号xt,itの後の接尾辞xt,>itとを連結することにより，次の配列xt+1を取り出す． 実際には、PsとPeを、次に説明する（ジョイント）ニューラルモデルとして定義します。

GRAMMFORMERを2つのモデル(Ps, Pe)に因数分解することは、重要なモデル化の決定であることに注意してください。 非terminalを正しく拡張する確率は、穴を導入すべきかどうかを決定する確率と「競合」しません(これらは分離したイベントではありません)。 しかし、これは標準的な（シーケンス）デコーダを使用した場合の話である。 Alg.1の最後のシーケンスxtが与えられた場合。NONTERMINALSTOHOLES(・)は、残りのすべての非終端記号を穴「」で置き換え、xoutをユーザに提示する。 図2は、小さなコードのスニペットを潜在的に（合成的に）生成する場合の、ループの反復に渡るxtを示している。 各ステップにおいて、非終端記号（最左端とは限らない）は、終端記号と非終端記号のシーケンスに展開され、展開された記号を置き換えます（図2では下線が引かれています）。 なお、GRAMMFORMERは文脈フリーではないので、非終端記号を展開する際には入力シーケンス全体を考慮します。 次に，多くの文法ベースの手法[38, 5]とは対照的に，任意の非終端記号を毎回展開することができる． 最後に、ルールセットRはルールの離散的なセットではなく、Peによって暗黙的にモデル化されている。

ニューラルモデル

GRAMMFORMERは，標準的なエンコーダ-デコーダモデルにいくつかの重要な変更を加えたものである． まず，変換エンコーダEは，入力シーケンスxtをn×Dの行列E(xt)にエンコードするが，ここでDは変換器の隠れた次元である[35]． その後，EはPsとPeの両方で使用される． 展開モデル Pe は標準的な自己回帰式、すなわち Pe(y∣xt , it) = ∏j=1...m Pdec(yj ∣E(xt), i, y<j ) に従いますが、さらに展開される非端末の位置である i を使用します。 Pdec(yj ∣E(xt), it , y<j )をWangら[36]と同様の(因果関係のある)関係変換器デコーダで実装する。 関係性変換は，要素間の事前定義された関係性を取り入れることで，注目メカニズムを補強するものである． GRAMMFORMERでは、現在展開されている非terminal xt,it のエンコードされた表現を示す関係を定義する。 すなわち、各ヘッドhに対して、クロスアテンション行列は

すなわち、学習可能なバイアスrhを非終端xiの符号化に加える。 したがって、入力トークンxt,mと出力トークンynの間のクロスアテンションはα (h) mn ∝ qn(WKE(x)m + I(m = it) ⋅ rh) ⊤となります。 最後に、Psを符号化された全ての非終端記号に対するポインタ型ネットワークとして定義すると、すなわち

ここで，fはフィードフォワード・ニューラルネットワークであり，E(xt)iは位置iにおける非終端記号の符号化表現である． xt,0は特別な開始記号[CLS]の表現であるため，E(xt)⦸ ≜ E(xt)0とした．EとデコーダPeに「標準的な」変換器を使うことにしたのは，NLPやコードにおける変換器ベースのモデルの素晴らしい結果を考慮してのことである[9]．

しかし，ここでは，biGRUエンコーダとGRUデコーダ[3]などの他のエンコーダ・デコーダモデルや，Longformers[4]などの効率的な変換器を採用することができます． この点については今後の課題とします。

損失

GRAMMFORMERを学習するために、強化学習を採用しました。 これは、監督者のいない離散的なitの選択によるものです。 Alg.1で定義された確率モデルの損失を計算するために、我々は、a - - tがあると仮定する。 1で定義された確率モデルの損失を計算するために、グランドトゥルースの端末シーケンスx ∗が与えられたときのスケッチxˆの品質を測定する-潜在的に非微分可能な-報酬関数r(xˆ, x ∗)があると仮定する。 このような関数については第3節で述べる。 Paulusら[26]にヒントを得て、我々は自己批判的な政策勾配トレーニング[28]を使用し、以下を最小化する。

ここで、tはAlg.1のループの反復におけるインデックス、I(・)は指標関数、x0は入力列、x ∗は端末のグランドトゥルース列、r〜(x0)はスナップショットからの予測によって得られる報酬である。 ここで、tはAlg.1のループにおけるインデックス、I(・)は指標関数、x0は入力シーケンス、x ∗はグランドトゥルースの端末シーケンス、r〜(x0)は、これまでのベストスコアを達成したPsとPeのスナップショットからの予測によって達成される報酬です。 なお，学習時にはPe(yˆt⊚it ∣xt , it)に対して厳密な監視を行いますが，これは it での非終端の展開が解析された学習例から既知であるためです． テスト時には解析は必要ありません。

事前学習

式2を直接最適化することは、CPU内のループ、itの不連続な選択、高価な変換器ベースのモデルのため、計算量が多くなります。 学習を高速化するために、PeとPsを2つのステップで事前学習します。 まず、Peは、Psで学習した拡張戦略とは無関係に、すべての非終端を拡張するように予習します。 これを行うために、入力された学習例を使用し、Alg.1に従います。 1に従いますが、Ps(・)の代わりに、(2行目)では、 Ñ(xt) = N(xt) ‾ {⦸}、すなわち、xtに含まれる特殊な停止記号を除く全ての非終端記号に対する一様分布からサンプリングします。 これにより、各非終端記号 i∈ Ñ(xt)に対して、入力 xt とそのグランドトゥルース展開 y ∗ t⊚i が得られます。 次に，各サンプルについて，次の式を最小化することで，エンコーダとデコーダのプレトレーニングを行う．

すなわち，xt のすべての非終端記号に対する正しい拡張の負の対数尤度である． この計算は，式2の計算と比べて，xtを符号化するためのコストがすべての拡張{y ∗ i }に対して償却され，強化学習を使用しないので，計算効率がよい． Peが前学習されたら、前のステップで前学習されたエンコーダEを固定し、Psの残りのパラメータを式2によって最適化することで、Psを前学習する。 これには、fのパラメータθのみが含まれます。 前学習したPeとPsができたら、式2を用いて、すべてのモデルの重みをエンドツーエンドで微調整します。