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

強化学習によるプログラム⽣成のためのプログラム系列分析
佐藤 拓海 1

大内 啓樹 2,1

松田 耕史 1

12

東北大学

鈴木 正敏 1

鈴木 潤 1,2

乾 健太郎 1,2

理化学研究所 AIP センター

{takumi.sato,matsuda,m.suzuki,jun.suzuki,inui}@ecei.tohoku.ac.jp
hiroki.ouchi@riken.jp
1

はじめに

Rank

NationGold

SilverBronze

Total

1

Cuba

43292

Canada4217の表とそれに関連する質問が与えられ，適切な応答を3United States

2024返すタスクである．図1はその例を表している．一つの4Mexico1102

表とそれに関する質問 “Who is ranked #1?” が与えら

...

...

...

...

...

...

表形式データに基づく質問応答 (TableQA) は，一つれ，“Cuba” と答えられれば正解となる．正解応答を導Q: “Who is ranked #1?”

くには，表に対する何らかの操作が必要となる．そのた

A: “Cuba”

め，SQL のクエリのように表の操作を実行可能なプロ

P1 : (first all_rows)

グラムを出力するのが一般的である．出力されたプロ
グラムはインタプリタによって実行され，表に基づい(hop v0 r.nation-str)
P2 : (filterin all_rows [“1”] r.rank-str)て値を返す．図1中の P1 がその例である．まず，“(first(hop v0 r.nation-str)

all_rows)” によって，全ての行のうち最初の行を取り出す．次に，“(hop v0 r.nation-str)” によって，取り出した行の “Nation” 列の文字列 “Cuba” を取り出す．

TableQA に用いられるデータセットでは，各質問に対する正解応答のアノテーションのみが与えられ，正解応答を導くプログラム (正解プログラム) のアノテーシ
ョンはないことが多い [4, 6, 7]．その理由として，質問と応答のペアは人手でのアノテーションコストが低いが，正解プログラムのアノテーションはコストが高いことが挙げられる．最先端の手法では強化学習を用いて，正解応答にたどり着くプログラムに高い報酬を設定し，繰り返し探索することによって尤もらしいプログラムを導出する [2]．
ここで問題となるのは，正解プログラムのアノテーシ
ョンがないため，モデルが生成したプログラムの分析が困難な点である．実際に多くの先行研究 [4, 8] では，最終的に出力した応答の正解率のみでモデルを評価するに留まり，誤った応答を出力するに至ったプログラムの分析などが行われていない．その結果，モデルの挙動に関する詳細が未だ明らかではない．
そこで本稿では，(i) 質問と応答のアノテーションのみから正解プログラムを獲得する方法と，(ii) それに基づく詳細な評価・分析が可能なフレームワークを提案する．本提案手法を用いることにより，モデルが出力した

図1: WikiTableQuestions データセットの例．表と，質問 (Q)，正解の応答 (A)，および本提案手法で生成した正解プログラム群 (P ).

プログラム内の個々の関数の正解率など詳細な分析が可能であることを示す．

関連研究

2

これまでもいくつかの研究において，モデルの出力したプログラムに関する分析が行われている. Pasupat ら[6] は，TableQA の WikiTableQuestions データセット
内の質問を四つに分類し，誤りの割合を算出している．
この研究は正解の応答に基づいたものであり，出力されたプログラムがどの程度誤っていたのかなどの詳細な分析には踏み込んでいない．Krishnamurthy ら [1] は同様のデータセットを用いて，seq2seq モデルの出力するプログラムに関する分析を行っている．開発データにおいて正解の応答を出力できなかったプログラム 100 件について，生成候補を見てエラーの原因の分類を行なっている. この研究のように，正解プログラムのアノテーションがないため，出力された少数のプログラムを人手で一つ一つ見ていくといったコストの高い方法が取られている．本稿で提案する分析手法では，正解プログラムを自動で獲得するため，出力されたプログラムの分析を大幅に効率化できる．

― 1010 ―Copyright(C) 2019 The Association for Natural Language Processing.
All Rights Reserved.

①正解プログラム
開発データの生成
Q,②実験ログラムも容易に獲得できる．

,A

正解プログラムの曖昧性: 前述した手法で，多くの質問

訓練

正解プログラム

プログラム
生成モデル

{P1, P2, …}

開発データ

Q,多くの質問に対して正解の応答が予測できるので正解プに対する正解プログラムが獲得できる．ここで一つ問題となるのは，図1の P1 と P2 のように，正解プログラムは複数ありうるということである．例えば，データ内の各質問・応答に対して，正解プログラムを一つ用意する

学習データ

③評価
Q,開発データ

訓練
プログラム
生成モデル

Q,（評価対象）グラムと異なるため不正解としてしまうという問題を引予測プログラム

き起こしうる．

P̂

このような曖昧性に対処するため，本稿では，複数の

図2: 提案手法の概略図.

異なる学習済みモデルを用意し，複数の正解プログラム提案⼿法3を獲得する．各モデルはニューラルネットワークを用い

本節では，プログラムの評価・分析手法を提案する．
1 正解プログラムの図2にその概要を示す．ここでは，⃝3 評価の 3 つのステップを踏む．以降の2 実験，⃝生成，⃝節に詳述する．

3.1ているため，パラメータのランダム初期化の際に，ランダムシード値が変われば，それに伴って異なるモデルが構築される．この性質を利用し，ランダムシードの異なる複数のモデルを用意し，それぞれ独立に学習する．これによって，複数の異なる正解プログラムが獲得可能で分析対象のタスク

TableQA タスクを分析対象とする (図1)．このタスク
では，与えられた表に関する質問 (Q) に対し，適切な応答 (A) を出力することがもとめられる．その解法として，質問と表を入力とし，SQL のクエリなどの表上で実行可能なプログラムを出力するモデルを構築し，モデルの出力であるプログラムを表上で実行することで解答を得るのが一般的である. 本タスクで用いられるデータセットの多くは，各質問に対する正解の応答のみがアノテーションされており，正解プログラムのアノテーションは存在しない．本提案手法はそのようなデータセットに対し，正解プログラムを自動獲得することを目的とする．

3.2

場合を考える．モデルが実際に生成したプログラムを評価する際，本当は正解であるはずが，用意した正解プロ,A正解プログラムの⽣成法モデルが予測したプログラムを分析するにあたり，比較対象となる正解プログラムを用意する必要がある．
正解プログラムの定義: 各質問に対して正解の応答を導くプログラムを「正解プログラム」と定義する．
1 に概略を示す. ま
正解プログラムの⽣成⽅法: 図2の⃝ず，正解プログラムを付与したい質問・応答アノテーシ
ョン付きデータを用いて，正解の応答を予測できるようにモデルを学習する．次に，この学習済みモデルを用いて，学習に用いたデータ内の各質問に対するプログラムを出力する．ここで，学習に用いたデータとプログラムを出力するデータは同一のデータである．つまり，学習に用いたデータに対してプログラムの予測を行うため，あり，曖昧性が引き起こす問題を軽減できる (実験結果は5.1節を参照)．

3.3

正解プログラムの評価法

正解プログラムとモデルの予測プログラムを比較する
ことによって，予測プログラムがどの程度適切なものか3 の出力)．具体的には，(i)BLEU スコ評価する (図2の⃝ア [5] を用いてプログラム全体の評価をする．さらに詳細な分析のため，(ii) プログラム内の関数の N-gram 一
致率を算出し，各関数別の評価も行う.

(i) プログラム全体の評価: BLEU スコアの算出では，
まず，予測プログラム P̂ とそれぞれの正解プログラム{P1 , P2 , · · · } 間の BLEU スコアを算出する．これらの中で，BLEU スコアが最大となる正解プログラムを「最類似正解プログラム」とする. 最類似正解プログラムのBLEU スコアを全 QA 対について平均した値を最終スコアとする.

(ii) 関数ごとの評価: 予測プログラムに含まれる各関数を評価する．まず，予測プログラムと最類似正解プログ
ラムから，引数を無視し関数名のみの系列を作る. 引数を無視する理由は，プログラム内で中心的な役割を果たす関数に焦点を絞った量的評価を行いやすくするためである. 次に，予測プログラムの関数名系列の N-gram が，最類似正解プログラムの関数名系列に含まれているかどうかに基づいて F1 値を算出する.

― 1011 ―Copyright(C) 2019 The Association for Natural Language Processing.
All Rights Reserved.

表1: モデル数を変化させた場合の正解プログラムとの一致数と正解応答をカバーできていない正解プログラム数．

実験

4

本提案手法の有用性を検証するための実験を行う．本

モデル数

節では，実験に用いるデータセットとモデルについて詳述する．

4.1

データセットWikiTableQuestions データセット [6] を用いる．こtotal(t)eq(t,p)neq(t,p)error(t,p)

1
2,186
836
1,350
358

2
2,221
951
1,270
243

3
2,235
1,011
1,224
183

42,241
1,067
1,174
127

5
2,253
1,0931,160
101のデータセットの質問と応答は人手で作成されており，人間が実際に行う質問応答により近いものとなってい5

結果・考察る．このデータセットには，QA 対が 22,033 個，表が5.1

正解プログラムの正解カバー率2,108 個存在する. QA 対のうち 11,321 個を学習デー

3節で述べたように，正解の応答を出力可能なプログ

タ，2,831 個を開発データとして用いており，両データラムは複数存在する．そのため，モデルが予測したプロ間で用いられる表は互いに異なるものである. 一方で，グラムが本当は正解であるはずが，用意された正解プロ正解プログラムはアノテーションされていない．そこでグラムと一致しないため，誤った正解・不正解判定をし本提案手法を用いて，開発データに正解プログラムを付てしまう恐れがある．そこで，本提案手法によって獲得2 に示すように，学習データで与する．そして，図2中⃝された正解プログラムが，実際にモデルが出力した予測学習した評価対象のモデルが予測したプログラムに対しプログラムをどの程度適切に正解判定できているかを調て評価・分析を行う．

査する．

4.2

分析に⽤いるモデル

表1に実験結果を示す．total(t) は，最低一つの正解

本提案手法は任意のモデルを評価・分析可能である．

プログラム t を獲得できた QA 対の総数 total(t) を本稿では，WikiTableQuestions データセットにおいて最表す．eq(t,p) は，最低一つの正解プログラム t と完全高精度を達成しているモデル [2] を用いる．
このモデルは，一致した予測プログラム p の総数を表す．neq(t,p) は，強化学習の枠組みである Memory Augmented Policy

全正解プログラム t と不一致である予測プログラムの数

Optimization (MAPO) を Neural Symbolic Machinesを表す．error(t,p) は，本来正解と判定されるべきで(NSM)[3] モデルに適用したものである.

あった予測プログラムの総数を表す.

MAPO は方策勾配法 (policy gradient algorithm) に一つのモデルの正解プログラムと予測プログラムを基づいて，モデルのパラメータを学習する．高報酬な行完全一致基準で判定した際，予測プログラムの 358 個動軌跡をメモリバッファに保存し，期待報酬をメモリ(2,186 中) は本来正解と判定されるべきだが正解プログバッファ内外の各行動軌跡の重み付き和とすることで，ラムと一致しないため不正解と判定されている．このよ

高報酬な行動軌跡を記憶・利用することが特徴である.

うな誤った判定数は，モデルの数を増やして正解プログ

NSM は質問と表の情報を入力とし，表上で実行可能なラムの数を増やすと徐々に減っていく．五つのモデルにプログラムを出力する seq2seq と，入力されたプログラよる正解プログラムを使った場合，この数は 101 個 (全ムを表上で実行し，応答を出力するインタープリタを合体の約 4.5%) にまで減少する．以上の結果から，提案しわせたモデルである. その特徴は，seq2seq のデコードた正解プログラムの出力方法によって複数の正解プログ

時に質問や表のエンティティ，すでに生成され実行可能ラムを用意することによって，モデルの予測したプログな関数の実行結果をメモリに保持しておくことで，それラムのほとんど (95% 以上) を正確に正解・不正解判定らを利用しつつプログラムを生成できる点である.

できるということがわかった．

このモデルが生成するプログラムは図1に示すように，丸括弧で区切られる関数の系列となっており，各関数は5.2

予測プログラムの評価・分析

3.3節で述べた評価方法に基づいて，学習済みの最先関数名と引数からなるトークンの系列となっている. ハ

端のモデルが出力したプログラムを評価・分析する.

イパーパラメータの設定は [3] と同様のものを用いる．

プログラム全体に対する評価： 各予測プログラムの学習ステップ (training step) 数の上限は，正解プログBLEU 値を算出することによって，各プログラムがどのラムの生成を行うモデルに対しては 10 万回，実験に用程度正解プログラムと異なっていたかがわかる．結果といるモデルには 3 万回と設定した．

して，予測プログラムの BLEU スコアの平均値は 77.0

― 1012 ―Copyright(C) 2019 The Association for Natural Language Processing.
All Rights Reserved.

表2: 関数別の事例数と F1 値．

であった．この中でも，BLEU スコアが 20 を下回ってunigramいる予測プログラムとそれに対応する QA 対について分析したところ，質問文中と表中の単語間に表記ゆれがbigram

事例数

F1

事例数

F1ある事例が多いことがわかった．例えば，質問文 “howhop

1,528

92.2

1,445

70.1

many of the candidates were females?” を考える．こargmax

340

68.0

101

56.8の質問文に付随する表中には “female” を “F” と略してargmin

203

62.4

120.0表している．このように，質問文中の単語とそれに対応

filter>4863.230.0

する表中の単語の表記ゆれが，プログラムの予測を困難

filter≥6153.1130.0なものとしていることが示唆された．

filter<2757.110.0

関数ごとの評価： 提案手法を用いることによって，各関

filter≤00.000.0

数の精度が詳細に分析可能である．表2は，正解プログ

filter=6763.01150.0

ラム中に含まれている各関数の事例数と F1 値を示してfilter̸=140.090.0いる. unigram の列は，各関数単体の事例数と F1 値をfilterin

1,26991.7

15064.1示している．全体の傾向として，事例数の多い関数 (hopfilter!in3866.72360.0

や filterin ，count) の F1 値は高く，予測しやすいことがfirst20263.27743.5

わかる．bigram の列は，当該関数とその直前の関数のlast

8768.63142.1

ペアに対する事例数と F1 値を示している．つまり，直previous

9379.19375.8前に出力される関数とセットでの精度である．結果としnext

11574.2

11571.7て，関数 previous や next は，unigram と bigram でのcount627

83.855965.8

F1 値がほぼ同等である．これは，直前の関数とセットで0.0100.0max24正解できていることを示唆している．一方，関数 filterin

min150.030.0は，unigram での F1 値よりも bigram の F1 値が顕著

average1042.9916.7に低い．これは，正解の応答を導くためには関数 filterin

sum2332.4

1113.3が必要であることをモデルが正しく認識してはいるが，mode

4551.140.0

直前に用いる関数として適切な関数を選べていないこと

same_as3476.9

3476.9diff7877.77877.7を表している．

おわりに

6[2]

本稿では，TableQA において生成されたプログラムの評価・分析フレームワークを提案した．実験の結果，本[3]

提案手法の妥当性の評価と，実際に最先端の TableQAモデルに適用した際の評価・分析を行った．今後の課題[4]として，より幅広いデータセットとモデルに対して本提案手法を適用し，評価・分析を行うことが挙げられる．

謝辞

[5]

[6]

本研究の一部は JST CREST（JPMJCR1301）および日本電信電話株式会社の支援を受けて行った．

[7]

参考⽂献
[1]

Jayant Krishnamurthy, Pradeep Dasigi, and Matt Gardner. “Neural Semantic Parsing with Type Constraints
for Semi-Structured Tables”. In: Proceedings of EMNLP.
2017, pp. 1516–1526.

[8]― 1013 ―Chen Liang et al. “Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing”. In:
Proceedings of NIPS. 2018, pp. 10014–10026.
Chen Liang et al. “Neural Symbolic Machines: Learning
Semantic Parsers on Freebase with Weak Supervision”.
In: Proceedings of ACL. Vol. 1. 2017, pp. 23–33.
Arvind Neelakantan, Quoc V. Le, and Ilya Sutskever.
“Neural Programmer: Inducing Latent Programs withGradient Descent”. In: CoRR abs/1511.04834 (2015).
Kishore Papineni et al. “Bleu: a Method for Automatic
Evaluation of Machine Translation”. In: Proceedings ofACL. 2002.
Panupong Pasupat and Percy Liang. “Compositional Semantic Parsing on Semi-Structured Tables”. In: Proceedings of ACL-IJCNLP. 2015, pp. 1470–1480.
Pengcheng Yin et al. “Neural Enquirer: Learning toQuery Tables in Natural Language”. In: Proceedings ofthe Workshop on Human-Computer Question Answering.
2016, pp. 29–35.
Yuchen Zhang, Panupong Pasupat, and Percy Liang.
“Macro Grammars and Holistic Triggering for Efficient
Semantic Parsing”. In: Proceedings of EMNLP. 2017,
pp. 1214–1223.

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