モンテカルロ木探索を用いた確率文脈自由文法に基づくテキスト生成
熊谷 香織

1(指導教員：小林 一郎)はじめにられる構文木とし，エッジを適用される文法規則とする．モンテカルロ木探索を行うことにより，尤度の高い構文木を生成するような文法規則の適用手順を学習する．それにより統語的に妥当なテキストの生成を行う．また，UCB1 値における確率の取り方において，本研究では，探索木のルートノードが ‘S’ の時を除いて，親ノードを決定するまでに親ノードを経由したシミュレーションで得られた評価値の平均と比較して探索を行う．ルートノードが ‘S’ の時は全ての候補ノードを万遍なく探索し，評価値が高いノードを選択している．

視覚情報からのテキスト生成の多くの研究においては，n-gram モデルを用いたテキスト生成手法が用いられている．しかし，その手法は，文法規則を利用しないため，文法的に正しくない文が生成されることが多い．このことから，本研究では，文法規則に確率文脈自由文法を採用し，モンテカルロ木探索により尤度の高い構文木を探索することにより，文法規則を伴った尤もらしい文の生成を行うことを目的とする．

2モンテカルロ木探索

以下に PCFG を用いたテキスト生成アルゴリズムとして，MCTS を適用した処理の流れを示す．

モンテカルロ木探索（Monte Carlo Tree Search :MCTS）[2] は，ランダムシミュレーションと木構造に対する正確な探索を組み合わせたアルゴリズムである．
コンピュータ囲碁における MCTS の成功により，ゲームに対する課題だけではなく，状態と行動の対のデータを有する様々なドメインに適用され，シミュレーションによってその出力を予測することに用いられている．

step1.（初期設定）： ルートノードに文法規則 S が適用される．
step2.（選択）： ルートノードから適用可能な文法規則を一つ選択する．
step3.（拡張）： 新たなノードを生成する．
step4.（シミュレーション）： 生成されたノードから文法規則をランダムに適用し終端記号の文字列を生成する．
step5.（逆伝搬）： 生成された文字列の尤度が対象とするノードのひとつ上のノードにおける尤度の最大値を超えた場合，勝ちとして 1 の値を，辿ってきた全てのノードの勝率を更新する．
step6.（ルートノードの更新）： step2 から step5 を規定回数繰り返した後，ルートノードの子ノードの内，シミュレーション回数が最大のノードを次のルートノードとして，step2 へ戻る．

MCTS の基本アルゴリズムの概要を図 1 に示す．

4

図 1: MCTS アルゴリズムの概要

実験に使用したコーパスは，Microsoft ResearchVideo Description Corpus1 における，「人が銃で対象物を撃つ」という内容のビデオの，42 個の説明文を対象とする．使用する PCFG は，対象コーパスを Stanford
Parser2 を用いて構文解析し，その結果に基づき確率を付与し構築したものを用いる．総文法数 98，総語彙数 51 のものである．MCTS のシミュレーション回数は 10,000 回とした．生成文の評価値を PCFG によって生成された構文木の対数尤度とする．
実験設定として，(1) 制約を課さない場合（通常のMCTS の適用），(2) 文長制約を課す場合，(3) 語彙選択に制限を施した場合，(4) 言語モデルを導入した場
合の 4 つの段階において検証を行った．また，実験結果は，実験を何回か繰り返し，得られた 2 文を示すとする．
以下の節にそれぞれの場合を示す．

UCB1 値
MCTS においては，有望なノードをさらに深く探索する様に探索木を拡張していくが，探索が不十分なノードに対しても拡張の可能性を与えるように，「知識の適用（exploitation）」と「探査（exploration）」のバランスをとった探索を UCB(Upper Confidence Bounds)1値を用いて実現する．以下にその式を示す．
√logN
(1)
vi + Cnvi はそのノードの勝率，C は調整係数，N は全試行回数，n はそのノードを選択した回数を示す．UCB1
値における第 1 項が「知識の適用」を，第 2 項が「探査」を考慮している．

3

実験

MCTS を用いたテキスト生成

モンテカルロ木探索において，本研究では，ひとつのノードを確率文脈自由文法（PCFG）を適用して得1 http://research.microsoft.com/
2 http://nlp.stanford.edu/software/lex-parser.shtml

71

4.1

制約を課さない場合酬を与えることができる.bi-gram モデルによる評価はあくまで報酬としたいため, 構文木の対数尤度 : bi −gram モデルによる評価値 = α : 1 − α として，今回は α の値を 0.7 として実験した. 出力された文字列を以下に示す．また，文長 N =7，指定した 3 単語は ‘man’,‘shoots’,‘targets’ とした．

生成された文字列は以下の 2 通りに落ち着いた．

[firing][shoots]

文長が長くなる（適用する文法規則数が多くなる）につれ，計算回数が増えるため文全体の尤度は低くなる．
それにより，短い文しか出力されない結果となった．

4.2[a six targets shoots down man target][a six targets shoots up a man]

文長制約を課した場合以上のように語彙制約を施した場合から出力結果に進展は見られなかった．理由として考えられるのは，コーパスの文の内，先頭が a である文が圧倒的に多いため文の先頭に冠詞の a が出力されてしまう．
また，表現したい内容は [man shoots targets] だが，逆になってしまっている．このことは，コーパス中において動詞の隣に主語や目的語となる単語がくるとは限らないため，bi-gram モデルによって主語，述語，目的語の関係までは考慮出来なかったと考えられる．

文長制約を課す方法として，指定する文長を N とするとき，勝敗の決め方は文長 ̸= N のときはいずれも0 を返すとする．これにより，文長が N の時が評価が高いとする文法規則の適用の仕方を学習をする．
文長 N =7 で指定した時の，生成された文字列を以下に示す．

[a six targets shoot a six targets][a six targets is up a targets]

5

出現確率の高い単語が複数回使用されてしまうため，表現したい内容を表すことが出来ていない．このことから出現する単語に制約を課し，表現したい内容に近づけることを考える．

4.3

本研究では，文法規則に確率文脈自由文法を採用し，モンテカルロ木探索により尤度の高い構文木を探索することにより，文法規則を伴った尤もらしい文の生成を試みた．
実験では，MCTS を用いたテキスト生成において 4つの場合の検証を行った．制約を課さない場合，短い文しか生成されず，文長を指定したところ，少し長い文が生成されたが，同じ単語が複数回出現する文になった．そこで語彙選択に制限を施したところ，表現したい内容に近い文が生成されたが，コーパス中に出現しないような単語の並びを含む文が生成された．最後に，PCFG に加え，単語と単語のつながりを考慮するため，bi-gram モデルも導入したモデルを提案し，検証を行った．このとき，語彙選択に制限を施した場合から進展は見られなかった．理由として，文の先頭に a が出現する確率が高すぎるためと，主語，述語，目的語の関係までは bi-gram モデルでは考慮出来なかったためということがいえる．
今後の課題として，生成文がより表現したい内容に近づくために，生成文のみを対象に評価するのではな
く，生成された構文木の構造を評価し，適切な語彙選択を可能にすることが考えられる．

語彙選択に制限を施した場合

今回は，コーパス中に使用された主語，動詞，目的語，それぞれにおいて使用された回数が最大のものを指定し，その 3 単語を一つ含むにつき評価値となる対数尤度に log10 を加えた．これにより生成文は説明したい内容に近くなることが考えられる．また，この 3単語においては文における冗長性を避けるため，複数回出現しないように設定した．
文長 N =7，指定した 3 単語は，主語においては‘man’，述語においては ‘shoots’，目的語においては‘targets’ とした．この時の出力文字列を以下に示す．

[a six targets shoots up a man][a six targets shoots down a man]
単語のつながりは考慮していないため，a six targetsなど，コーパス中に出現していないような単語の語順となっている．このことから，単語と単語のつながりを考慮する必要がある．

4.4

おわりに

参考文献
[1] 小林瑞季，麻生英樹，小林一郎，人の動作を対象にした確率的言語生成への取り組み，言語処理学会第 20 回年次大会，pp.920-923，北海道大学，
2014.
[2] L.Kocsis and C.Szepesvári. Bandit basedMonte-Carlo planning. In 17th European Conf.
on Machine Learning(ECML 2006).
[3] 安田 宜仁，平尾 努，永田 昌明，文生成を題材とした両方向からのモンテカルロ木探索，第 27 回
人工知能学会全国大会，1B5-5，2013．

言語モデルを導入した場合

単語間のつながりを考慮する方法として，対象コーパスから生成された bi-gram モデルを導入した．bigram モデルによる評価値の初期値 を log(1/1000000)
× 2N(N = 文長) とし, 構文木の 尤度に加算する, 文長が N のときのみ bi-gram モデ ルの計算を行う.bigram モデルの計算では, 単語の 出現確率を 1/1000000と置き換え, 単語の遷移確率も コーパス中に出てきた単語のペアが生成文中に出てき た部分のみ 1/1000000と置き換えを行う. この置き換 えによって初期値に報72