ニューラルネットワークを使用した対話システム （１）〜Knowledge Base質問応答システム〜
対話システムは、QAチャットや音声アシスタントなど、様々なところで使用されており、 また、GoogleのDialogflowを始め多くの独自対話システムを構築できるプラットフォームが数年前から続々と登場してきています。
しかし、これらの公開されているシステムは、たくさんある対話システム構成の中でもタスク指向型（特にスロットフィリング型）の設計にのっとっているものが多いのが現状で、作りたいシステムをそのまま構成することが難しいケースが存在します。
この記事シリーズは、ニューラルネットワークを使用している対話システムについて、どのようなシステム設計がありうるのか、どのように機械学習でそのシステムを実現しようとしているのかを、「Neural Approaches to Conversational AI*1」を元に、元資料の引用だけでなく、中で説明されている論文についても、可能な限り概観できるようにまとめたものです。
第一回目は、質問応答対話システムのうち、Knowledge Baseを元に応答を返すシステムについてまとめています。
前提として、元資料では対話システムは、質問応答システム、タスク指向型システム、雑談システムの3つに分けられていて、質問応答システムはさらに、Knowledge Baseを参照して答えるものとドキュメントを参照して（機械読解の技術を使用して）答えるものに2つに分類されています。
目次
- Knowledge Base質問応答システムとは何か
- Knowledge Baseとは何か
- Knowledge Baseへの入力を理解する
- Knowledge Baseから情報を引き出す
- Knowledge Base質問応答システムの構造
- まとめ
Knowledge Base質問応答システムとは何か
Knowledge Base質問応答システムは、下記のようにKnowledge Baseをデータソースにして、ユーザーからの「日本の首都はどこ？」のような質問に、「東京です」のように答えるシステムのことを指します。
Knowledge Baseについては詳しくは次節に記載しますが、大量の知識を保管しているDBのようなものだと一旦考えてもらえれば差し支えありません。
言ってしまえば、このKnowledge Base内の大量の知識から答えを探して出力するだけなのですが、下記のように難しい点がいくつかあります
- ユーザーが入力した自然文を元にユーザーが何について質問しているかを理解する必要がある
- 理解した入力文をもとにKnowledge Baseから情報を抽出する必要がある
- 情報が足りない場合はユーザーに追加の情報を入力するように促す必要がある
1は対話システム全体に言えることですが、Knowledge Base質問応答システムの場合は、Knowledge Baseのクエリを生成することとほぼ等価な処理を行う必要があります。この時に使用される技術のことを一般に Semantic Parsing と呼びます。
2は同じ質問応答システムであるテキスト質問応答システムでも必要な技術ですが、テキスト質問応答システムは非構造な大量のテキストから情報を抽出する必要があるのに対し、Knowledge Base質問応答システムは構造化されたデータから情報を抽出します。
そのため、1でうまいことクエリに変換することができればテキストから情報を抽出するより難易度が低く、大規模なデータソースを効率よく扱え、ピンポイントで質問されたことを答えることが容易であるという利点があります。
一方で、大規模なKnowledge Baseを構築することは非常にコストがかかるため、データ収集の面ではテキスト質問応答システムの方が大いに有利な点となります。
3はタスク指向型対話システムの一つであるスロットフィリング型システムで同じような処理が必要になりますが、スロットフィリング型システムとは異なり、答えを返すために必要な情報がシステム開発者により明示的に定義されていないことがほとんどです。そのため、Knowledge Baseを元に答えを絞り込むためにどのような情報を必要とするかをシステム自身で導出する必要があります。
一方、上記の点は必ずしも悪いことではなく、スロットフィリング型システムよりもかなり柔軟に絞り込み条件を設定する事ができ、ユーザーがどのような質問をしてくるかわからないようなシステムとは非常に相性の良い仕組みになります。
Knowledge Baseとは何か
Knowledge Baseとは、知識を保持しそれをコンピューターを用いて検索、演算できるようなものを指します。
RDBが用いられることもありますが、一般的にはエッジとノードをつなげたグラフ構造によりノード間の関係として「知識」を表現したものが使用されます。
具体的には、以下のようなトリプルと呼ばれる3つの値を持つデータの組として一つの知識を表現します。
triple(h, r, t)
hはhead、rはrelation、tはtailを表しており、headとtailはエンティティー（グラフのノード）、relationはリレーション（グラフのエッジ）を表します。リレーションには方向があり、エンティティーがリレーションのどこにつながっているかによって意味が変わる有向グラフとなります。
例えば、以下のようなトリプルを考えることができます。
triple(日本, 首都, 東京)
これは、日本の首都は東京であるということを表すトリプルで、このように一つのトリプルが一つの知識を表すことになります。
このようなKnowledge Baseを使用した質問応答システムは、主に以下の2つのモジュールから構成されることになります。
- 自然言語を理解しKnowledge Baseのクエリに変換するモジュール
- クエリを元にKnowledge Baseから情報を引き出すモジュール
Knowledge Baseへの入力を理解する
自然言語を理解しKnowledge Baseのクエリに変換する分野は Semantic Parsing と呼ばれ、それだけで一つの研究分野として独立するほどには活発で難しい分野です。
この分野では、
日本の首都はどこ？
というような自然文の入力を元に、
SELECT 首都 FROM 首都一覧 WHERE 国='日本'
もしくは
triple(日本, 首都, ?)
のようなコンピューターがKBから情報を取得できる形式のクエリを出力することが目的となります。
元々は自然文と変換語のクエリのペアを元に、機械学習やルールベースによりクエリの生成が試みられていましたが、近年ではより容易に集めることができる、自然文と答えのペアを収集して教師あり学習や強化学習でクエリを生成するような手法も提案されています。
Berant*2らの提案手法では、ヒューリスティックと構文解析の結果を元に候補クエリを大量に作成し、候補クエリの枝数や自然文の特定の単語のPOSタグ情報など特徴量にして、入力文の変換結果が出力文である妥当性を予測するように学習します。
YaoおよびVan Durme *3らの手法では、Berantらの手法と同じように候補クエリをまず大量に生成し入力文と候補クエリのマッチングを予測するように学習しますが、外部のAPIを利用した自然文のトピックや質問に使用されている疑問詞を特徴量として使用することにより、10%以上F1値を向上させました。
Bao*4らの手法は、上記2つと異なりまず質問文をヒューリスティックにより複数の部分質問に分割し、それぞれをクエリとなるトリプルに分割し最終的にマージすることによりSemantic Parsingを実現します。
Yih*5らは、強化学習を用いて逐次的にグラフ上を答えのエンティティーに進んでいくことで、答えの選択とSemantic Parsingを同時に達成する方法を提案しました。
このように一口にSemantic Parsingといってもアプローチは様々です。より詳細に知りたい方は、 ACL2018のSemantic Parsingのチュートリアル資料がとても参考になります。
Knowledge Baseから情報を引き出す
さて上記のSemantic Parsingにより、自然文をクエリの形式に変換する事ができたとします。
一般的なRDBを思い浮かべれば、後はクエリをシステムに問い合わせればよいだけのように思えますが、Knowledge Baseの問題設定においては残念ながらそこまでスムーズにことは運びません。
Knowledge Baseは実は不完全であり、必ずしもクエリから直接答えを応答できないようなケースが十分に想定できます。
例えば、以下のようなクエリがあった時に
triple(東京駅, ある国, ?)
Knowledge Baseにはそのトリプルがある可能性はとても低いでしょう。その場合、下記の2つのクエリをつなぎ合わせて答えを返すことになります。
triple(東京駅, ある場所, 東京)
triple(日本, 首都, 東京)
人間であれば上記の2つの知識を結びつけて、東京駅が日本にあることは簡単に推測できますが、コンピューターでそれを実現することは一筋縄では行きません。
Link Prediction と呼ばれるこの研究分野の問題をナイーブに解こうとすると、
あるリレーションとあるリレーションの組み合わせを、別のリレーションに変換するためのルールをを作ったり、その変換ルールを適用できるエンティティーのタイプを制限するなど、膨大なルールを設計する必要があります。
これに対して、埋め込み表現やニューラルネットを使用した方法により、これらの問題を効率よく解く手法が提案されています。
埋め込み表現を用いたLink Prediction
埋め込み表現を利用した手法として、まず代表として挙げられるのがTransEとNeural Tensor Networks（NTN）です。
TransE*6はBordesらが提案した手法で、エンティティーとリレーションをいずれもベクトルとして表し、Link Predictionを既存手法より10ポイント以上改善しました。
Neural Tensor Networks*7は同時期に（全く同じ会議で！）Socherらによって提案された手法で、エンティティーをベクトルで、リレーションを行列で表現した手法で、こちらもベースラインを上回る結果を示しました。
Neural Tensor Networksは双線形モデル（Bilinear model）と呼ばれる式をカスタマイズした式でスコアを計算し、 の?の部分に入る可能性のある全てのエンティティーについてそのスコアを比較、最も高いスコアのエンティティーを答えとするランキング形式で答えを探索するアプローチを取ります。
TransEもスコア関数の形こそ違うものの基本的な考えは同じで、スコアに基づいたランキングで最終的なエンティティーを決定します。
両手法は様々な派生系が提案され、現在では主要なデータセットで80〜90%近いMRRを達成するようになってきています。
ニューラルネットを用いたLink Prediction
ニューラルネットベースの手法は、スコアを計算することなく、エンドツーエンドで対象のエンティティーを出力する構成が多く提案されています。
特に、強化学習ベースの手法は最終的な答えのエンティティーだけでなく、どういう経路をたどってそのエンティティーを答えと判断したのかがわかり、エンドツーエンドなシステムの中では説明性の非常に高い手法となっています。
DeepPath*8はXiongらが提案した、初期の強化学習を利用したKnowledge Baseの探索手法です。下記のようにKnowledge Baseの位置をステート、次にどのエンティティーに移動するかをアクションと捉えるシンプルな問題設計で、REINFORCEというシンプルな強化学習手法をLink Predictionに適用し、（当時の）埋め込み表現ベースの手法を上回る性能を示しました。
MINERVA*9はDasおよびDhuliawalaおよびZaheerらが提案した手法で、大規模なKnowledge BaseデータセットでDeepPathを含む既存のLink Prediction手法を上回る性能を示しました。
M-Walk*10はShenおよびChenおよびHuangらが提案した強化学習ベースのグラフ探索手法で、Alpha Goのようにモンテカルロ木探索とQ学習を使用し、埋め込み表現ベースの手法にはやや及ばないものの（発表当時はほぼ同じだったのですが）、他の強化学習ベースの手法を上回る性能を示しました。
これらのニューラルネットベースの手法は、エンドツーエンドで計算するため探索するエンティティーの数によらず一定の速度で推論することができ、通常、埋め込み表現を使用した手法に比べ3~4倍の速度で答えとなるエンティティーを出力することができます。
Knowledge Base質問応答システムの構造
さてここまでで、最初に示した以下2つのモジュールを準備できたことになります。
- 自然言語を理解しKnowledge Baseのクエリに変換するモジュール
- クエリを元にKnowledge Baseから情報を引き出すモジュール
後はこれをつなげればKnowledge Baseを元に質問応答を行うシステムを構成できるかに思われますが、さらに2つの壁に阻まれることになります。
1つ目は、Semantic ParsingとLink Predictionの二つのモジュールがそれぞれに誤った処理をしてしまうことに起因し、モジュール単独の誤りよりも不正解が蓄積し増幅される問題があります。
2つ目は、通常の会話は複雑なクエリを一回の自然文で発話されることはなく、複数のターンで少しずつ最終的な答えの範囲を絞るようなクエリとなるという点です。Semantic ParsingやLink Predictionのデータセットは、一つの複雑なクエリに焦点が当てられることが多く、そのままでは対話システムとしては扱いにくいという課題があります。
1つ目の問題にはエンドツーエンドなニューラルネットの構成で、2つ目の問題にはRNNや強化学習などのマルチステップの問題に適用しやすいモデルや学習方法を使用することにより、問題を解決しようという試みが多く見られます。
KB-InfoBot*11はDhingraらが提案した、マルチターンなKnowledge Baseを利用する質問応答システムを、エンドツーエンドなニューラルネットと強化学習により構成することを試みたシステムです。
このシステムは下図のように、Belief Trackersでユーザーが入力した自然文を擬似的にSemantic Parsingを行い、DBのアクセスもニューラルネットの出力を元にユーザーが注目しているだろうと推定するDB内のレコードの分布を更新し、その情報を元に最終的にPolicy Networkで応答すべき内容（追加の質問or出力する答え）を決定します。このように全てを確率的な構造で扱うことにより、ルールベースの手法を上回る対話成功率を達成しました（最も大規模なKnowledge Baseで60%ほどの成功率）。
CSQA*12はSahaおよびPahujaらが提案したマルチターンの処理が必要で、複雑な質問が含まれるKnowledge Baseを利用した質問応答システム用のデータセットです。
このデータセットはKnowledge Baseからの単純な情報抽出だけでなく、条件に合うトリプルの統計情報や複数のトリプルを比較した答えを返す必要があり、また平均8ターンという非常に長いコンテキストを扱う必要があり、非常に難しいデータセットとなっています。
データセットの検証用として、下図のようなモジュールをリニアに結合した構成で実験が行われています。まずRNNで過去の質問文や応答文も含めてエンコードを行い、その後メモリーネットワークで擬似的にエンティティーの検索が行われ、デコーダーで最終的な応答を生成します。
既存のDeep Learningの手法をナイーブにつなげた構成ということもありますが、質問種類ごとの正答率が最大30%ほどと非常に低く、Knowledge Baseを利用した自然な会話を行う質問応答システムを構成することが難しい問題であることを示す結果となっています。
まとめ
Knowledge Baseを利用した質問応答システムは、Semantic ParsingとLink Predictionというそれぞれに難しい二つのキーとなる技術に支えられ、その二つを、マルチターンでの質問応答という自然な会話を実現するためにうまく接続する必要がある非常に難しいシステムであることをここまで見てきました。
一方で、シングルターンかつシンプルな質問であれば、Semantic ParsingおよびLink Prediction、それぞれの精度も非常に高く、ナイーブに接続してもそれなりの性能が出るシステムを構成する事ができます。
Knowledge Baseそのものを構成するという重い作業がありますが、一度構成してしまえば「じゃがいもが使われている評価が4以上のレシピを教えて」や「今のアメリカの大統領は誰？」などの質問に答えることはそこまで難しくない状況と言えるでしょう。
Knowledge Base質問応答システムを作成できる既存サービスを残念ながら知らないのですが（次回説明するテキスト質問応答システムを構築できるサービスはWatson DiscoveryやQnA Maker、Dialog Flow Knowledge Connectorsなど各社出していますが）、スロットフィリング型対話システムのスロットのような変数を取りうる質問に、ドキュメントを元にしたシステムよりも柔軟に応えることができる構成であることは間違いありません。
Knowledge Baseを構築することがどうしてもボトルネックになってしまいますが、Knowledge Base質問応答システムは堅実に使い勝手の良い対話システムを構成できるアプローチなのです。
*1:[1809.08267] Neural Approaches to Conversational AI
*2:Semantic Parsing on Freebase from Question-Answer Pairs - ACL Anthology
*3:Information Extraction over Structured Data: Question Answering with Freebase - ACL Anthology
*4:Knowledge-Based Question Answering as Machine Translation - ACL Anthology
*5:Semantic Parsing via Staged Query Graph Generation: Question Answering with Knowledge Base - ACL Anthology
*6:Translating Embeddings for Modeling Multi-relational Data
*7:Reasoning With Neural Tensor Networks for Knowledge Base Completion
*8:DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning - ACL Anthology
*9:Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning | OpenReview
*10:M-Walk: Learning to Walk over Graphs using Monte Carlo Tree Search
*11:Towards End-to-End Reinforcement Learning of Dialogue Agents for Information Access - ACL Anthology
*12:Complex Sequential Question Answering: Towards Learning to Converse Over Linked Question Answer Pairs with a Knowledge Graph
