2020-02-29

Keras Loss Behavior with Language Model

KerasのModelクラスを使用した際のロスの計算は、Paddingで追加した余計な値を勾配の計算から除外する処理は自動でやってくれるのですが、
historyに記録されるlossの平均値を求める際に、maskを部分的にしか考慮しておらず、padding数が多くなればなるほど、実際のロスより小さくなってしまうという現象が発生します。

この記事は、KerasのModelクラスでLossを利用する、
特にEmbedding層で、mask_zeroをTrueにした場合に、Paddingで追加した余計な値を、勾配の計算に使用しない、ロスの計算から完全に除外する方法についてのメモです。

検証用のコードはこちらです。

マスクを使用したロスの計算は、TensorFlowのチュートリアルを参考にしています。

KerasのLossの種類と種類毎の処理の違い
- tf.keras.losses.Lossの派生クラスの場合の処理
- 独自定義したcallableなLossオブジェクトの場合の処理
Embedding層でmask_zeroをTrueにした場合のLossの挙動

KerasのLossの種類と種類毎の処理の違い

Kerasのmodel.compileで指定できるLossの種類は大きく分けると以下の3つがあります。
※ 参考：compile内で呼ばれているtf.keras.Model.prepare_loss_functions

tf.keras.losses.Lossの派生クラス
独自定義したloss関数
独自定義したcallableなLossオブジェクト

このうち、「独自定義したloss関数」は、prepare_loss_functions内でtf.keras.losses.Lossの派生クラスであるLossFunctionWrapperクラスに変換されるため、実質は2種類のLossオブジェクトが使い分けられることになります。

Lossを含んだ計算グラフの構築は、tf.keras.Model._prepare_total_loss内で行われます。
この関数の中で、上記2つのオブジェクトは別々の処理が行われことになります。

tf.keras.losses.Lossの派生クラスの場合の処理

tf.keras.losses.Lossの場合は、Kerasの内部関数であるtf.keras.utils.losses_util.compute_weighted_loss内で、以下の処理が行われます。

ロス関数の呼び出しによるロスの計算
tf.keras.utils.losses_util.scale_losses_by_sample_weightでロス×sample_weightsを計算
Lossオブジェクトのreductionに応じた集計をtf.keras.utils.losses_util.reduce_weighted_lossで計算。大体の場合は、ロスの平均値を計算する処理

これから、sample_weightsを使用しない場合は、独自定義のロス関数でどんなshapeの値を返しても良いことがわかります。

ただし、sample_weightsとしてEmbedding層で計算したmaskが暗黙的に使用される場合があるので後述のように注意が必要です。

独自定義したcallableなLossオブジェクトの場合の処理

正解ラベルとニューラルネットワークの出力だけでなく、sample_weightsも引数に渡されて、Lossオブジェクトのcall関数が呼ばれます。
ベクトル値を返した場合、ベクトルの平均値が最終のロスとして使用されます。

Embedding層でmask_zeroをTrueにした場合のLossの挙動

Embedding層でmask_zeroをTrueに指定した場合、sample_weightsとしてEmbedding層で計算したmaskが暗黙的に使用されます。
maskはpadding処理で0埋めした部分はFalse、それ以外はTrueとなり、paddingで埋めた部分の計算に勾配が伝わらないようにしてくれます。

ただし、あくまで勾配が伝わらないようにしてくれるだけで、ロスの平均を取る際の分母の数をmask分減らしてはくれません。
このため、Perplexity等の計算をこのLossが出力した値を元に行うと、paddingで埋める長さが長いほど小さい値になってしまいおかしくなります。

例えば、正解ラベルとして $[1, 1, 2, 0, 0$ ] の系列データがあるケースを考えます。

この時、ネットワークの出力として、各時点でのラベルの予測確率が $[0.2, 0.2, 0.2, 0.2, 0.2$ ]と得られたとします。

0は計算処理の都合上いれているだけのデータで、実際の処理では無視するため、このデータに対するクロスエントロピーロスは下記のようになります。

$-(log(0.2) + log(0.2) + log(0.2)) / 3. = 1.60943...$

しかしKerasのModelクラスを使用して計算すると

$-(log(0.2) + log(0.2) + log(0.2)) / 5. = 0.96566...$

という値になってしまい、実際の値に比べてかなり小さくなってしまいます。

これを避けるためには、検証コード内LOSS_MODEが2の場合のように、独自定義したLossオブジェクトで、padiding部分の値を元にした処理に勾配が行かないように、かつ平均計算時の分母からの除去するように必要があります。

ちなみにMetoricsはレートに直す際に、sample_weightsの合計で割るような実装になっているため、maskの場合も意図した動作になります。

2020-01-27

Microsoft Academic Search APIで自分専用の論文検索エンジンを作る

論文ツール

サーベイなどで論文検索をする時によく困るのが、キーワードをこねくり回さないと以外と読むべき論文に出会えないという点です。

特に「Dialogue System」や「Image Captioning」などのように、母数が少ないニッチな分野になると、学術用検索エンジンにキーワードを入力するだけでは、キーワードにマッチするものがトップに上がってくるだけで、必ずしもその分野を代表するような論文がヒットしてくれるわけではありません。

ホットな分野であれば、サーベイ論文、学会のチュートリアル資料など、人工知能学会の「私のブックマーク」を漁ると良さそうな情報が見つかることもありますが、なかなか新しい情報がまとまっていないということも多くあります。

その点で検索しやすいなと思っているのが、Microsoft Academicです。

下記の記事にもまとまっていますように、文献に紐付けられたトピックで論文を絞り込める、類似の論文のサジェストの性能がまあまあ良い、Saliencyなどのどのような論文から引用されているかでランキングできるという点が、論文を探す際に非常に便利で、特にあまり馴染みのない、体系的に理解できていない分野の論文を探す時に重宝しています。

個人的なオススメは、「キーワード入力」→「トピックで絞り込み」→「Saliencyでランキング」で検索すると、割といい感じに論文を見つけることができます。

ただやはり難点があって、特にトピックにまではなっていないような時に、下記のうまくいかないケースが発生します。

検索キーワードと論文中のワーディングや語順が違うと引っかからないことがある
分野内で、最近よく利用されている技術や引用されている考え方を知りたい

前者については検索キーワードを変えながら、後者については自分で網羅的に文献を読むことにより、なんとか達成する事もできますが、分野のことをろくに知らない状態でワーディングを考えたり、ざっととはいえ論文を読むことは結構辛いものです。

「ヒットした文献内でよく参照されている論文」などを簡単に探すことができれば、上記の要望を満たせそうですが、残念ながらそのような要望を満たしてくれるような検索エンジンは僕の知る限り存在しません。

ならば自分で作ればよいのでは！？と考えたすえ、Microsoft Research APIsの中のAcademic Search APIを使用して論文検索エンジンを自作してみました。

自作したサイトはこちらです（APIの使用制限やエラー処理が適当なため動かないことがありますので、あしからず）。

ソースコードは下記。

中で使用しているクエリの書き方は以下2つの記事か、本記事内の「クエリ構文の書き方」をご参考ください。

以降は主にAcademic Search APIの使い方について記載していきます。

Academic Search APIとは
- APIの種類と使い方
- クエリ構文の書き方
自分専用の論文検索エンジンを作る
- 複雑なクエリをプログラムで実現する
まとめ

Academic Search APIとは

Academic Search APIは、Microsoft Academicで使用されている論文データベースに、Microsoft Academicで使用されている自然言語による検索や内部的に使用されているクエリ構文でアクセスできるように提供されているAPIです。

月に10,000トランザクションまでという制限がありますが、無料で使用することができます。APIキーはこちらのページの「Subscribe」から簡単に取得することができます。

他にも上記の論文データベースにアクセスする方法がいくつか用意されていますす。

Microsoft Academic GraphというデータベースAzure上でホストして使用する方法
Microsoft Academic Knowledge Exploration Serviceという形で、APIサーバーをAzure上でホストして使用する方法
Open Academic Graphの形で公開されている情報を使用して、自身でデータベースから自作する方法

いずれの方法も利用回数無制限で使用できますが、手続きが必要であったりとAcademic Search APIに比べると気軽さが落ちますので、データをAggregationした結果を大量に使用する、というような重たいクエリを大量に発行するような使い方をする場合に検討してみるのがオススメです。

APIの種類と使い方

APIにはいくつかメソッドがありますが、主に使用するのはInterpetとEvaluateです。

Interpet
Microsoft Academic上の検索窓に入力するようなクエリを投げると、「Evaluate」メソッドで使用できるクエリの形式に変換したテキストが取得できるメソッドです。
「query」に検索したいキーワードを入力し、「complete」を1に設定すると、検索窓で表示されるクエリ候補が返されるようなイメージです。
Evaluate
専用のクエリ構文で記述したクエリに基づいて、各論文の情報を取得できるメソッドで、主に今回使用するのはこのメソッドです。
「expr」にクエリ構文で記述したクエリ、「attributes」に取得したい論文に関する情報、「count」に取得したい論文の数（1000が上限）を指定します。

Evaluateメソッドは、「expr」と「attributes」には共通の表現を使用するなど、グラフ上のデータということもあり使い勝手はなんとなくGraph QLに似ています。

ただし、参照している文献のタイトルなども指定してまとめて引っ張ってくる、といったような使い方はできませんので、このあたりはプログラムで自分でカバーしてやる必要があります。

クエリ構文の書き方

クエリ構文のポイントは、①論文の属性で絞り込む、②Compositeを使用して論文の複合属性を絞り込む、③And/Orで複雑な条件を実現するの3つです。以下それぞれについて説明していきたいと思います。

論文の属性で絞り込む

論文の属性とよんでいるのが、この属性一覧に記載されている属性のうち、「.」が含まれていないもののことです。例えば、論文のタイトルである「Ti」や出版年である「Y」などです。

主に絞り込みで使用するのは、「W」や「Y」あたりです。

「W」は、論文のタイトルに含まれていて欲しい文字列を指定します。例えば「W='text'」といったように指定します。また、後で説明する「And」や「Or」と組み合わせることにより、「And(W='text',W='generation')」といった複数のキーワードを指定した検索を実現することができます。

「Y」は、上述しましたように論文の出版年のことで、「Y=2010」のようにクエリを指定します。数値なのでもちろん範囲指定や上限・下限を指定することができ、「Y<=2015」で2015年以前の論文、「Y=[2010, 2012]」で2010年から2012年に出版された論文を検索することができます。

Compositeを使用して論文の複合属性を絞り込む

ここで論文の複合属性と読んでいるのが、「.」が含まれている属性のことで、「AA.AuN」（著者名）や「F.FN」（分野名）のことです。

これらは上記のシンプルな属性とは異なり「Composite(AA.AuN='james')」のようにクエリを書く必要があります。論文を絞り込むための属性そのものが、一意に決定できないようなケースがあるため、このような特殊な書き方をします。

また、この性質のため、And/Or検索時の挙動には少し注意が必要です。本サイトの記事からの引用となりますが、例えば、「Composite(And(AA.AuN='mike smith',AA.AfN='harvard university'))」は「ハーバード大学に所属するmike smithが著者にいる」論文が検索されますが、「And(Composite(AA.AuN='mike smith'),Composite(AA.AfN='harvard university'))」は、「ある著書がmike smithで、ある著者がハーバード大学に所属する」論文を検索されます。

検索条件としてよく使用するのは、

And/Orで複雑な条件を実現する

And/Or検索はさして難しくなく、And()やOr()内に、有効なクエリを「,」で区切ることで実現できます。

例えば、「And(W='text',Y<=2015)」は、タイトルに「text」が含まれる2015年以前の論文を表しますし、「And(Or(W='text',W='sentence'),Y<=2015)」は、タイトルに「text」か「sentence」が含まれる2015年以前の論文を表します。

もちろん複合属性をクエリに含めることもでき、「And(Composite(F.FN='computer vision'),Y<=2015)」は、Computer Vision分野の2015年以前の論文を表します。

自分専用の論文検索エンジンを作る

上記までで、かなり複雑なクエリを実現できるようになりましたが、特に「分野内で、最近よく利用されている技術や引用されている考え方を知りたい」を見つけてきたい場合は、クエリ検索だけではいまいちなことがあります。

下記は、「And(W='dialogue',W='generation',Y>=2015)」（2015年以降の「dialogue」と「generation」をタイトルに含む論文）から上位10件をAPIを使用して検索した結果になります。重複した結果は、学会で発表された論文とarxivなどのプリプリント論文が別のものとして扱われているために発生しています。

- Semantically Conditioned LSTM-based Natural Language Generation for Spoken Dialogue Systems
- Semantically Conditioned LSTM-based Natural Language Generation for Spoken Dialogue Systems
- Adversarial Learning for Neural Dialogue Generation
- Adversarial Learning for Neural Dialogue Generation
- Deep Reinforcement Learning for Dialogue Generation
- How NOT To Evaluate Your Dialogue System: An Empirical Study of Unsupervised Evaluation Metrics for Dialogue Response Generation
- How NOT To Evaluate Your Dialogue System: An Empirical Study of Unsupervised Evaluation Metrics for Dialogue Response Generation
- Deep Reinforcement Learning for Dialogue Generation
- Multiresolution Recurrent Neural Networks: An Application to Dialogue Response Generation.
- Multiresolution Recurrent Neural Networks: An Application to Dialogue Response Generation

この検索結果はいくつか難点があります。1つは、明示的に検索クエリ（この場合は「dialogue」）が含まれる論文しか検索結果に含まれない点。その結果、分野に関連する代表的な論文を必ずしも見つけるができない、というのが2点目です。

「Computer Vision」や「Natural Language Processing」のようなトピックとして整理されているレベルのものであればもっとマシな結果が得られますが、サブタスクのような実際に興味のある範囲や、新しく振興してきた分野については適当な結果が得られないことが多くあります。

複雑なクエリをプログラムで実現する

上記のようなケースで最も効果的なのが、「ヒットした文献内でよく参照されている論文」を見つけることです。基本的にはこれらは自力で論文を読む中で見つけてくるものですが、できれば最初から重要そうな論文を見つけたいというのが本音です。

Academic Search API一発では上記を実現できませんが、応答を元に集計処理を行えば簡単に上記のような論文を見つけることができます。

方針としては下記です。

クエリにマッチするような論文を最大件数（1000件）検索する
応答内の各論文の「RId」属性を参照し、その論文が引用している論文を抽出する
抽出した引用されている論文を、引用数が多い順にソートする
引用数が多い上位N件の論文の情報を、Academic Search APIで再度取得する

この手順で先程と同じ「And(W='dialogue',W='generation',Y>=2015)」で論文を検索した結果が下記です。Seq2SeqやAttentionのような要素技術や、この分野で近年注目されている論文を効果的に取得することができています。

- Sequence to Sequence Learning with Neural Networks
- Neural Machine Translation by Jointly Learning to Align and Translate
- Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation
- Bleu: a Method for Automatic Evaluation of Machine Translation
- Long short-term memory
- Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
- A Neural Conversational Model
- A Diversity-Promoting Objective Function for Neural Conversation Models
- A Hierarchical Latent Variable Encoder-Decoder Model for Generating Dialogues
- A Network-based End-to-End Trainable Task-oriented Dialogue System

まとめ

この記事では、Academic Search APIの紹介とそれをもとに作成した自作の論文検索エンジンについて紹介しました。

検索できるクエリは紹介したもの以外にも色々ありますし、プログラムを使用することも考えるとより複雑なクエリを実現することができます。

また、プログラムで論文管理ツールやスプレッドシートと連携することも簡単にできますし、APIがあるだけでサーベイ作業をだいぶ効率化できそうだなと考えています。

ぜひ皆さんも自分専用の論文検索エンジンを作ってみてください。

2019-12-24

VariationalでEnd2EndなDialogue Response Generationの世界

機械学習生成モデル自然言語処理 Deep Learning 対話システム

この記事は、自然言語処理 #2 Advent Calendar 2019の24日目の記事です。

Open-Domain Dialogueや非タスク指向対話、雑談対話と呼ばれる領域において、発話データのみを使用したEnd2Endな対話応答生成を試みる歴史はそこまで古くなく、[Ritter et al+ 11]や[Jafarpour+ 10]がまず名前をあげられるように、比較的最近始まった研究テーマとなります。

これらは、Twitterなどの登場により、ユーザー間で行われる、ほとんどドメインを限定しない、もしくは多様なドメインにまたがる、大量の対話データを、容易に収集できるようになったことにより、活発に研究されるようになってきました。

初期の研究である[Ritter+ 11]や[Jafarpour+ 10]では、統計的機械翻訳ベースや情報検索ベースの手法でEnd2Endな対話システムを構成していました。

これらの研究は、複数のモジュールをつなぎ合わせ、対話データだけでなく、人がアノテーションしたデータを元にシステムの学習を行う、従来の対話システム研究にパラダイムシフトをもたらしました。しかし、下記のような雑談対話システムの特性のため、初期の研究では扱える処理に限界がありました。

一つのクエリー（ユーザー発話）に対して、複数の応答（システム発話）が可能である点
クエリー自体はそこまで長いものでないため、長期的なコンテキスト（対話履歴など）を考慮した応答生成を行う必要がある点

それを受けて現れたのが、ニューラルネットワークを使用した対話システムです。[Sordoni+ 15][Vinyals+ 15][Shang+ 15]

これらの論文はほぼ同時期に登場することになりますが、いずれも、ニューラルネットワークの表現学習能力を利用して、対話の長いコンテキストを一定次元の潜在表現に圧縮し、それを元にRNNを使用したデコーダーにて応答を生成することを試みています。

また、[Serban+ 16]にて提案されたHREDモデルは、発話文のエンコーダーと、コンテキストのエンコーダーを分けることにより、より効率的に長い対話コンテキストを利用できることを示し、構成の簡単さもあり、現在ではEnd2Endな対話応答生成のベースラインとしてよく使用されるモデルとなっています。

しかし、単純にニューラルネット化しただけでは、長期的なコンテキストを考慮しやすくはなっても、「I'm OK」や「I don't know」のような、どのようなコンテキストにも合いやすい文を生成してしまうという問題は解決しませんでした。

[Li+ 16]では、相互情報量（Mutual Information）を目的関数にすることにより、出現頻度の高い文を応答として使用することに対し、ペナルティーを与えるような設定でそれを克服しようとしました。

[Li+ 17]では、GANベースの学習方法を使用して、生成される対話を、実際のデータセットに含まれるような対話に近づけることにより、この問題を克服することを試みています。

そして、[Serban+ 17]および[Zhao+ 17]では、VAE、特にCVAEのテクニックを対話応答生成に応用して、潜在変数のサンプリングによって多様な応答生成が行えるようになることを示しています。

本記事では、特にこのVAEベースの手法に注目して、どのように発展してきたか、現在はどのような部分にスポットが当たっているかについて記載していきたいと思います。

End2End対話システムの基本
VariationalでEnd2Endな対話応答生成
- VAE（Variational Auto-Encoder）とテキスト生成
- CVAEを利用した対話応答生成
VariationalでEnd2Endな対話応答生成の現在
- 生成される発話の多様性の改善
  - VHCR
  - CVAE+VAE
  - DialogWAE
- ユーザーの特性を考慮した応答文生成への応用
  - SSVN
  - VHUCM
まとめ
参考文献

End2End対話システムの基本

End2Endな対話応答生成の問題設定

End2Endな対話応答生成は、N個の単語（もしくはトークンおよび文字）からなるユーザー発話文 $x = \{w_1^{x}, w_2^{x}, ..., w_N^{x} \}$ と、L個のユーザー発話とシステム発話の履歴であるコンテキスト $C = \{c_1 = \{w_1^{c_1}, w_2^{c_1}, ..., w_{N'}^{c_1}\}, c_2, ..., c_L\}$ が与えられた際に、適当なシステム発話文 $y = \{w_1^{y}, w_2^{y}, ..., w_M^{y} \}$ を生成することが目的となります。

ここでは、一般的な問題設定を紹介していますが、ユーザー発話やシステム発話は必ずしもテキストのみである必要はありません。またコンテキストとして、対話履歴だけでなく、注目している画像や、文章、知識ベースなど、多様な周辺情報が含まれるケースも考える事ができます。

ここで、モデル $P_\theta (y | x, C)$ を考えた場合、自動で応答を生成することができるように、データセット $D = \{x_i, y_i, C_i \}$ を元にモデルのパラメーター $\theta$ を学習することが、End2Endな対話応答生成システムに機械学習システムを適用する際の基本的な考え方となります。

データセットにそもそも含まれないような状況には、対応することができないという課題もありますが、それはルールベースやアノテーションデータをもとに学習するような既存の対話システムでも同様です。

End2Endな対話システムは、ユーザー発話の理解から応答の生成までを一貫して行うことにより、データセットに含まれるような対話とは多少異なるような状況であっても、コンテキストやユーザー発話の違いを考慮して、より柔軟な応答が生成されることを期待しているものと考えることができます。

RNNを利用した対話応答生成

DCGM（Dynamic-Context Generative Model）

[Sordoni+ 15a]では、ユーザー発話文 $x$ とコンテキスト $C$ に含まれる単語を元にbag-of-words表現を生成し、それをもとにRNNを使用したデコーダーにより、システム発話文 $y$ を生成するシステムが提案されています。

直前のユーザー発話文とコンテキストのBOWのベクトルを分けるケースと、まとめたBOWを使用する2パターンが提案されていますが、以降の処理は共通で、BOWベクトルを元に多層のニューラルネットワークを元にコンテキストベクトル $c_l$ を生成した後、RNNの各ステップで $c_l$ を使用するようにシンプルなRNNを改良した層を元に、 $y$ を構成する各単語を次々に生成していくようなアーキテクチャです。

$\begin{align} h_t &= \sigma (h_{t-1} W_h + c_l + w_{t-1}^{y} W_{in}) \\ p_\theta &(w_{t}^{y} | w_{1}^{y}, ..., w_{t-1}^{y}, x, C) = \sigma(h_t W_{out}) \\ \end{align}$

ここで $W _ h, W _ {in}, W _ {out}$ は学習により最適化するNNのパラメーターです。以降も大文字の $W$ で表す行列は基本的に学習対象のパラメーターとします。

このように、RNNの計算中に逐次コンテキストを考慮するように計算を行うことにより、既存の機械翻訳ベース、情報検索ベースの手法と比較して、SNSでのやり取りを元にした対話応答生成タスクにおいて、高い性能で応答生成が行えることが示しています。

Seq2Seqを利用した対話応答生成

Neural Conversational Model

Seq2Seqは、[Sutskever+ 14]にて提案された、RNNを利用したEncoder-Decoderを持つネットワーク構造のことです。

この構造の一番大きな特徴は、そのシンプルさです。Encoderは、入力文ををもとにどんどん自身の隠れ層を更新していき、入力が完了した際の隠れ層のベクトル $h _ {N}^{E}$ を出力とします。デコーダーは、この $h _ N^{E}$ を自身の隠れ層の初期値（ $h _ 0^{D}$ ）とした上で、スタートトークンから逐次的に $w_{t}^{y}$ をRNNの出力層を元に生成してきます。

f:id:KSKSKSKS2:20191222180159p:plain — [Luong+ 15]より

このモデルは、このようなシンプルな構造ながら当時の機械翻訳の最高性能モデルに匹敵する性能を示し、テキスト生成界隈を驚かせました。

[Vinyals+ 15]は、このSeq2Seqを対話応答生成に素直に応用した手法で、直前のユーザー発話文を含む対話履歴（つまり、 $x$ と $C$ ）をエンコーダーに入力し、システム発話文をデコーダーにより生成することを試みました。

この論文の結果は非常に衝撃的で、大量の対話データさえあれば、このようなシンプルな構造のモデルでも、対話システムとして成立する可能性を示しました。

一方で、同じ対話中であっても、コンテキストをうまく考慮できず、似たような質問に異なる応答を返してしまう問題があり、この一貫性（Consistency）については、以降の対話応答生成手法においても、重要なキーワードの一つになっていきます。

Neural Responding Machine

Seq2Seqにはほぼセットで使用される機構にAttentionがあります。Attentionは、デコーダーの注目している隠れ層のベクトルを元に、エンコーダーのどのステップの隠れ層に注目するかを決定し、注目した隠れ層のベクトルの値をデコーダーが生成する出力の計算に利用します。

確率的に注目するエンコーダーのステップを決定するソフトアテンションと呼ばれる機構を、[Luong+ 15]ではさらにグローバルアテンションとローカルアテンションに分類しており、よく使用されるのはグローバルアテンションです。

グローバルアテンションの計算は、 $h_t^{D}$ をデコーダーの隠れ層のベクトル、 $h_t^{E}$ をエンコーダーの隠れ層のベクトルとした場合、下記のように表せます。RNNが複数層スタックされている場合は、一般に最終層の隠れ層のベクトルを使用します。

$\begin{align} a_{it} &= \frac {score(h_t^{D}, h_i^{E})} {\sum_j^{N} score(h_t^{D}, h_j^{E}) } \\ c_t &= \sum_i^{N} a_{it} h_i^{E} \\ p_\theta &(w_{t}^{y} | w_{1}^{y}, ..., w_{t-1}^{y}, x, C) = softmax([c_t; h_t^D] W_{out}) \\ \end{align}$

$score$ は隠れ層のベクトル同士の類似度を計算する関数で、一般にはドット積（ $h_t^{D} h_j^{E}$ ）や $h_t^{D} W_a h_j^{E}$ がよく使用されます。

f:id:KSKSKSKS2:20191222184629p:plain — [Luong+ 15]より

主に機械翻訳分野にて使われだしたアテンション機構ですが、[Shang+ 15]ではこの仕組みを対話応答生成に利用しました。

一つ前のデコーダー隠れ層のベクトルを元にアテンションを計算する部分と、アテンションを元に最新の隠れ層のベクトルを更新する部分以外は、前述のグローバルアテンションと同じような機構を使用し、Weiboで収集した大量の対話データを元に、既存の検索ベース、統計的機械翻訳ベースのシステムを上回る、対話応答生成性能を示しました。

このように、Seq2Seqベースの手法と大量の雑談対話データとの相性の良さが様々な研究によって示され、End2Endな対話応答生成においては、ニューラルネット、特にRNNを使用したSeq2Seqベースの構造は非常に良く使用されるようになっていきます。

階層構造を利用した対話応答生成

HRED（Hierarchical Recurrent Encoder-Decoder）

階層型の応答生成アーキテクチャであるHREDは、[Sordoni+ 15b]にて、まずはマルチターンの質問応答タスクにおいて採用されたSeq2Seqの拡張手法です。通常のSeq2Seqとの大きな違いは、エンコーダーが発話エンコーダーとコンテキストエンコーダーの2つに分かれる点です。 $h_t^{UE}$ を発話エンコーダーの隠れ層のベクトル、 $h_l^{CE}$ をコンテキストエンコーダーの隠れ層のベクトルとすると、下記の用に表現する事ができます。

$\begin{align} h_t^{UE} &= UtteranceEncoder(x) \\ h_l^{CE} &= ContextEncoder(h_{l-1}^{CE}, h_t^{UE}) \\ p_\theta(y | x, C) &= Decoder(h_l^{CE}) \\ \end{align}$

UtteranceEncoder、ContextEncoder、Decoderは基本的にRNNを使用することが多く、コンテキストエンコーダーの隠れ層のベクトルは、一層のニューラルネットワークで次元数をそろえる処理をした後、デコーダーの隠れ層の初期値として使用されることが一般的です。

f:id:KSKSKSKS2:20191222193446p:plain — [Sordoni+ 15b]より

[Sordoni+ 15b]でマルチターンの質問応答タスクで応用されたHREDは、[Serban+ 16]で対話応答生成に応用され、映画シナリオを元に作成したデータセットにおいて、直前のユーザー発話だけでなく、対話履歴中の発話も考慮した発話生成が行える傾向が見られることを示しました。

HREDは、長いコンテキストを扱うことになる対話応答生成と相性が良いと考えられており、現在では対話応答生成のベースラインモデルとして頻繁に参照されています。

VariationalでEnd2Endな対話応答生成

上記までで、大量の対話データとニューラルネットを使用することにより、長いコンテキストを考慮したEnd2Endな対話応答生成処理を実現できそうであることがわかりました。

しかし、これらの対話応答生成には、特に確率的に最も有り得そうな文をデコーダーからサンプルすると、「I'm OK」や「I don't know」のような、どのようなコンテキストにも合う文を生成してしまうという課題がありました。[Serban+ 16][Li+ 16]

f:id:KSKSKSKS2:20191224111954p:plain — [Li+ 16]より

上の表は、Seq2Seqベースの手法で学習したEnd2End対話システムにて、各ユーザー発話文を与えた際に、尤度の高い順にBeam Searchでデコードしたシステム発話文を並べたものです。

ユーザ発話に対する固有の応答よりも、どのユーザー発話にでもある程度使いまわしのきく文が、生成されてしまいやすいという問題が見えてきます。

非常に限定された情報しか含まない対話データを使用して、最尤推定により生成モデルを作成する以上、上記は避けることが難しい問題でもあるため、目的関数を相互情報量ベースのものや、GAN・強化学習ベースのものに置き換えることにより、これらを解決しようとも試みられています。

一方で、学習の安定性が高い最尤推定の枠組みのままこの問題を解決しようという方向性もあります。それが、VAEを応用した対話応答生成手法です。VAEを応用した手法では、潜在変数をサンプリングすることにより、生成される文の多様化を試みます。

以降では、対話応答生成にどのようにVAEが応用されているのかについて記載していきます。

VAE（Variational Auto-Encoder）とテキスト生成

変分近似の基本

VAE（Variational Auto-Encoder）は、[Kingma+ 14a]にて提案された、ニューラルネットワークを使用した生成モデルの一種です。

VAEは、他の最尤推定ベースの生成モデルと同様、データ $x$ が与えられた際に、尤度 $P_\theta(x)$ が最大となるモデルのパラメーター $\theta$ を推定することを考えます。

この時、一般に潜在変数 $z$ を用いて、下記のようにモデル化します。

$\begin{align} P_\theta(X) &= \int P_\theta(x, z) dz \\ &= \int P_\theta(x | z)P(z) dz \\ \end{align}$

一般的には、このままでは最適なパラメーター $\theta$ を解析的に求める事はできないため、別のパラメーターを持つ事前分布 $Q_\phi(z)$ を用いて、以下のように対数尤度を変形します。

$\begin{align} log P_\theta(x) &= log \int P_\theta(x, z) dz \\ &= log \int Q_\phi(z) \bullet P_\theta(x, z) / Q_\phi(z) dz \\ & \ge \int Q_\phi(z) \bullet log (P_\theta(x, z) / Q_\phi(z)) dz \\ & = \int Q_\phi(z) \bullet log (P_\theta(x | z)P(z) / Q_\phi(z)) dz \\ & = \int Q_\phi(z) \bullet log (P(z) / Q_\phi(z)) + Q_\phi(z) \bullet log P_\theta(x | z) dz \\ & = E_{z \sim Q_\phi(z)}[ log P_\theta(x | z) ] - KL[Q_\phi(z) \parallel P(z)] \\ &= L(x, z) \end{align}$

$L(X, z)$ を変分下限と呼ばれるもので、文字通り尤度の下限に当たる値です。尤度を最大化することを考える場合、この変分下限の値が最大となるようなパラメーター $\theta$ を求めればよいわけです。

ここで、 $KL[Q _ \phi(z) \parallel P(z)$ ]は、 $Q _ \phi(z)$ と $P(z)$ のKLダイバージェンス、 $E _ {z \sim Q _ \phi(z)}[ log P _ \theta(x | z)$ ]は、 $Q _ {\phi}(z)$ を考えた時の $log P _ {\theta}(x | z)$ の期待値です。

一般的な最尤推定（EMアルゴリズム）では、 $P(z)$ を標準正規分布として、 $KL[Q _ {\phi}(z) \parallel P(z)$ ]を最小化するような $\phi$ を選んだ後（Eステップ）、 $E _ {z \sim Q _ \phi(z)}[ log P _ \theta(x | z)$ ]を最大化する $\theta$ を選ぶ処理（Mステップ）を繰り返して、最適なパラメーターを求めます。

VAEの基本

VAEでは、事後分布の近似である $Q _ {\phi}(z)$ をデータ $x$ の識別モデルである $Q _ {\phi}(z | x)$ に拡張し、 $P _ \theta(x | z)$ とともにニューラルネットに置き換えてモデル化します。

この時、 $Q _ \phi(z | x)$ を識別モデル（Discriminator）や事後分布（Posterior）、 $P(z)$ を事前分布（Prior）、 $P _ \theta(x | z)$ を生成モデル（Generator）と一般的に呼ばれます。

また、変分下限は、 $L(x, z) = E _ {z \sim Q _ \phi(z | x)}[ log P _ \theta(x | z) ] - KL[Q _ \phi(z | x) \parallel P(z)]$ となります。

VAEでは、上記のような変更を行うことで、以下のような効果を期待します。

パラメーター $\theta$ を最適化する際に用いる $z$ の効率的な獲得
データを反映した潜在表現である $z$ の獲得
$P _ \theta(x | z)$ からサンプリングの簡易化

ここで、生成モデルをニューラルネットにするにあたり、全てのモデルは微分可能な関数として置く必要があります。 $P(z)$ を標準正規分布として置く場合、 $Q _ {\phi}(z \mid x)$ も正規分布となるように置くと、KLダイバージェンスを解析的に求めることができるようになるため、 $\theta$ については微分可能となります。

しかし、 $Q _ {\phi}(z | x)$ を直接確率分布としてモデル化しまうと、 $z$ が確率変数となるため $\phi$ について微分することができません。

そこで、下記のようにReparameterization Trickを用いて、 $z$ を決定変数として扱えるようにします。

確率変数 $\epsilon$ を $N(0, I)$ からサンプリングする
$z = \mu _ \phi(x) + \sigma _ \phi(x) \bullet \epsilon$ と $z$ を定義する
$E _ {z \sim Q _ \phi(z | x)}[ log P _ \theta(x | z)$ ]が $E _ {\epsilon \sim P(\epsilon)}[ log P _ \theta(x | \mu _ \phi(x) + \sigma _ \phi(x) \bullet \epsilon)$ ]と考えられるようになる

$\mu _ \phi(x)$ および $\sigma _ \phi(x)$ は、 $x$ から正規分布の平均と分散を推定するモデルで、一般的に途中までは一つのCNNやRNNで構成され、それらの出力をMLPでそれぞれように変換する処理を行います。

これにより、 $\phi$ についても微分できるようになり、変分下限をSGDを使用して最大化できるようになります。

VAEを利用したテキスト生成

VAEをSeq2Seqを利用してテキストの生成に利用したモデルはいくつかありましたが、[Bowman +16]では、潜在変数をより生成するテキストに反映できるようにし、VAEによるテキスト生成の有効性を示した点で画期的でした。

Seq2Seqを用いたモデルでは、特にAttentionを利用しないような状態では、エンコーダーで捉えた情報をほとんど使わずに、デコーダーが入力された単語の情報を元にテキストを生成してしまうという問題がありました。

VAEでは、潜在変数 $z$ に格納される情報に価値がなくなり、KL項が早々に0になってしまうという形で問題が現れます（KL-Vanishing Problem や KL Collapse Problem 、 Posterior Collapse Problem と呼ばれることもあります）。

このようなVAEの弱点に対し、[Bowman +16]では、KLコストアニーリングやWord Dropoutという手法を提案し、入力文を復元できるような潜在表現をエンコーダーによって獲得でき、デコード時に全く単語の情報を与えない状況でも、デコーダーは潜在表現をもとに出力文を生成できるようになることを示しました。

f:id:KSKSKSKS2:20191223124628p:plain — [Bowman +16]より

また、事後分布からサンプルした潜在変数で文を再構成した場合、意味的に同一だが表現が多少異なるような文を生成できること、それぞれの文の事後分布からサンプルした潜在変数の調和平均を取った潜在変数をデコードした場合、それぞれの文を混ぜたような意味や表現の文が生成されるなど、潜在表現を元にデコードしていると考えられる実験結果をいくつも提示しています。

f:id:KSKSKSKS2:20191223124649p:plain — [Bowman +16]より

この成果を受けて、多様な文を生成したい際に、VAEを使用して実現するというアプローチが広く行われるようになっていきます。

CVAEを利用した対話応答生成

CVAEの基本

CVAE（Conditional Variational Auto-Encoder）は、[Sohn+ 15]にて提案された、VAEをConditional情報を含んだ状態に拡張し、Conditional情報が与えられた際に学習データが生成される条件付き尤度、 $P _ \theta(x | C)$ を最大化するように学習する手法です。

似たような定式化を行っている[Kingma+ 14b]では、 $P _ \theta(x, C)$ や、コンディショなる情報を非自明とした上で $P _ \theta(x)$ を最大化する事を考えますが、[Sohn+ 15]では条件付き尤度である $P _ \theta(x | C)$ を最大化するように最適化します。

変分下限は、コンディショナル情報を加えた形で、下記のように定義します。

$L(x, C, z) = E_{z \sim Q_\phi(z | x, C)}[ log P_\theta(x | C, z) ] - KL[Q_\phi(z | x, C) \parallel P_\theta(z | C)]$

事前分布にも、事後分布にも、生成モデルにもコンディショナル情報の条件が含まれるようになる点がポイントです。 $P _ \theta(x | C)$ の条件付き尤度の式からも分かるように、CVAEはコンディショナル情報からデータ $x$ を生成することに使用することを主な利用目的としています。

[Sohn+ 15]では、不完全なデータをコンディショナル情報 $C$ として、 $x$ を復元するためにCVAEを使用しています。

以降で述べるように、対話応答生成では、対話履歴と直前のユーザー発話をコンディショナル情報として、そこから次のシステム発話を生成することを試みることになります。

VHRED

VHREDは、[Serban+ 17]にて提案されたHREDをCVAE化した手法です。ContextEncoderが出力した隠れ層のベクトルの値を元に、事後分布 $Q_\phi(z | y, C)$ から潜在変数 $z$ をサンプリングして、それを元に出力文を生成するように学習します。

$\begin{align} h_t^{UE} &= UtteranceEncoder(x) \\ h_l^{CE} &= ContextEncoder(h_{l-1}^{CE}, h_t^{UE}) \\ h_{t+1}^{UE} &= UtteranceEncoder(y) \\ z &\sim Q_\phi(z | h_{t+1}^{UE}, h_l^{CE}) \\ P_\theta(y | x, C) &= Decoder(z, h_l^{CE}) \\ \end{align}$

実際に利用する際は、事前分布 $P _ \theta(z | C)$ から潜在変数 $z$ をサンプリングして、次のシステム発話を生成することを試みます。コンディショナル情報 $C = \{x, C \}$ は、対話履歴と直前のユーザー発話から構成される前提です。

f:id:KSKSKSKS2:20191223130321p:plain — [Serban+ 17]より

VHREDは、SNS上の対話データや具体的な技術に関する対話データにおいて、特に数ターンと長いコンテキストを持つ際の対話応答生成、および生成される文の多様性で、通常のSeq2SeqベースのモデルおよびHREDと比較し、大幅に性能が向上することを示しました。

VAEの利点である、データを反映した潜在表現を得られるようになる点、サンプリングすることで生成結果の多様性に影響を与えることができる点が、対話応答生成において有効に機能する結果を示した論文です。

CVAE/kgCVAE

[Zhao+ 17]では、VHREDとほぼ同時期にほぼ同じようなモデルを提案しています。

VHREDと異なる点は、学習時にWord Dropoutの代わりに、(1)新たに提案したAuxiliary LossであるBag-of-Words Lossを用いて、潜在変数から生成する文のBOWベクトルを復元できるように学習できるようにした点と、(2)潜在変数だけでなく何かしらのラベル（[Zhao+ 17]ではダイアログアクト）もコンディショナル情報から推定し、推定した潜在変数とラベルをもとにデコーダーで文を生成するkgCVAE（Knowledge-Guided CVAE）という拡張手法を提案している点です。

f:id:KSKSKSKS2:20191223150228p:plain — [Zhao+ 17]より

ラベル情報を $a$ と置くと、ラベル情報を追加した場合の変分下限は下記のように定式化できます（図中では、ラベル情報が $y$ 、生成対象のテキストが $x$ と表現されていますが、同じことを表しています）。

$\begin{align} L(y, C, a, z) &= E_{z \sim Q_\phi(z | y, C, a)}[ log P_\theta(y | C, a, z) ] - KL[Q_\phi(z | y, C, a) \parallel P_\theta(z | C)] \\ &+ E_{z \sim Q_\phi(z | y, C, a)}[ log P_\theta(a | C, z) ] \end{align}$

式の通り、識別モデル $Q _ \phi$ は、生成対象の文とコンディショナル情報だけでなく、真のラベル情報も元にして潜在変数 $z$ を推定するように学習します。一方デコーダー $P _ \theta(y)$ は、コンディショナル情報、潜在変数、推定した（もしくは陽に与えた）ラベル情報から対象の文を生成します。

f:id:KSKSKSKS2:20191223145900p:plain — [Zhao+ 17]より

よりグラフィカルに書くと、上図のようになります。 $MLP _ y$ と記載されている部分が、 $P _ \theta(a | C, z)$ に、 $MLP _ b$ と記載されている部分がBOW Lossに対応します。

青いラベル情報に関する処理を抜くとただのCVAEであり、基本的にVHREDと同様になります。

実験では、特にkgCVAEは、対話履歴を考慮するだけでなく、指定したラベルに基づいた応答を生成できることを示し、様々な情報を追加することにより、コントロール性と生成する文の多様性の両方を兼ね備えた、対話応答生成の可能性を示しました。

VariationalでEnd2Endな対話応答生成の現在

VHREDやCVAEで一通り基本的なモデルは出尽くしたきらいがありますが、より有用な対話応答生成を行うための拡張手法の提案が日々行われています。

その方向性の一つが、潜在変数をよりデコーダーが参照するように、デコーダーが参照しやすいようによりリッチな潜在変数表現を獲得するように学習し、今まで以上に多様な応答生成を可能にしようという方向性です。

も一つが、単純に、対話応答を生成するだけでなく、ある制約ある条件下のもとで対話応答を生成したいという方向性です。

以降では、多様な応答生成を可能にするためにどのようにVHREDが改良されていっているか、制約条件として発話するユーザーを指定して応答を生成したいというケースに、どのように対応することが試みられているかについて紹介していきたいと思います。

生成される発話の多様性の改善

VHCR

[Park+ 18]では、VHREDに対話全体の潜在変数である $z^{conv}$ を追加したVHCRモデルとUtterance Dropテクニックを元に、より潜在変数を考慮した対話の生成が行える方法を提案しています。

$\begin{align} h^{conv} &= ConvEncoder(all\_dialogue) \\ z^{conv} &\sim Q_\phi(z | h^{conv}) \\ h_t^{UE} &= UtteranceEncoder(x) \\ h_l^{CE} &= ContextEncoder(h_{l-1}^{CE}, h_t^{UE}, z^{conv}) \\ h_{t+1}^{UE} &= UtteranceEncoder(y) \\ z &\sim Q_\phi(z | h_{t+1}^{UE}, h_l^{CE}, z^{conv}) \\ P_\theta(y | x, C) &= Decoder(z, h_l^{CE}, z^{conv}) \\ \end{align}$

$z^{conv}$ は全ての対話データから事後分布を元に推定され、コンテキストエンコーダーおよびデコーダーで使用されます。

f:id:KSKSKSKS2:20191224121827p:plain — [Park+ 18]より

変分下限は論文中には明記されていませんが、下記のようになります。

$\begin{align} L(y, C, z) &= E_{z^{conv}\sim Q_\phi(z^{conv} | all\_dialogue)}[E_{z \sim Q_\phi(z | y, C, z^{conv})}[ log P_\theta(y | C, z, z^{conv}) ] - KL[Q_\phi(z | y, C, z^{conv}) \parallel P_\theta(z | C, z^{conv})]] \\ &- KL[Q_\phi(z^{conv} | all\_dialogue) \parallel P(z^{conv})] \end{align}$

Utterance Dropは、コンテキストエンコーダーにわたす $h_t^{UE}$ をランダムに事前定義済みのUnknown Vectorに変更することにより、 $z^{conv}$ をもとにシステム発話文が生成されることを狙うテクニックです。

この二つの改良により、VHCRは発話一つずつではなく、対話全体を一つの潜在変数によりコントロールすることを試みており、実験では、 $z^{conv}$ をもとに対話全体を実際にサンプリングすることができることを示しています。

CVAE+VAE

[Shen+ 18]では、KL項が消失してしまう問題の原因を、潜在変数の表現力が正規分布に制限されてしまうことであると考え、VHREDにAAE（Adversarial Auto-Encoder）[Makhzani+ 16]を応用し、潜在変数 $z$ がより多様な形を取りうるように改良した手法です。

AAEはVAEのKL項をGANのスキームに置き換えることにより、多様な分布を事前分布として仮定できるようにした枠組みですが、[Shen+ 18]ではGANをさらにCVAEに置き換えることにより、コンディショナル情報も踏まえた上で、事前分布と事後分布を比較する枠組みに改良した手法を提案しました。

f:id:KSKSKSKS2:20191223163832p:plain — [Shen+ 18]より

上図のM1はほぼVAEと等価な構成で、対話履歴とシステム発話文yをエンコードした情報から、システム発話文yを再構成するようにパラメーターを最適化します。

VAEとの大きな違いは、(1)潜在変数を直接サンプリングするのではなく $\epsilon$ という緩衝材となるパラメーターを用いて決める点と、(2) $\epsilon$ を潜在変数に変換するモデル $G _ \phi(\epsilon)$ はすでに学習済みのものを使用するという点、(3)KL項はM2モデルで別途最適化を行うという点です。

$\begin{align} \tilde{z} &= UtteranceEncoder(y) \\ z &= (1 -p) G_\phi(\epsilon) + p \tilde{z} \\ L_{M1}(y, z, C) &= E _ {z \sim Q _ \phi(z | \tilde{z}, C)}[ log P _ \theta(y | z, C) ] \\ \end{align}$

$\epsilon$ を潜在変数に変換するモデル $G _ \phi(\epsilon)$ は、上図のM2に当たるCVAEパートにより学習を行います。対話履歴のみから $\epsilon$ を推定する事前分布 $P _ \theta(\epsilon | C)$ と、システム発話文yの情報も利用して $\epsilon$ を推定する事後分布 $Q _ \phi(\epsilon | \tilde{z}, C)$ の出力が近づくように学習を行います。

また、発話エンコーダーがシステム発話文 $y$ をエンコードしたベクトル $\tilde{z}$ を、 $\epsilon$ から再構成できるように学習することにより、事前分布の形状によらない潜在変数を対話履歴のみから得ることを試みます。

$\begin{align} &\tilde{z} = UtteranceEncoder(y) \\ &L_{M2}(\tilde{z}, C, \epsilon) = E_{\epsilon \sim Q_\phi(\epsilon | \tilde{z}, C)}[ log P_\theta(z | C, \epsilon) ] - KL[Q_\phi(\epsilon | \tilde{z}, C) \parallel P_\theta(\epsilon | C)] \\ &E_{\epsilon \sim Q_\phi(\epsilon | \tilde{z}, C)}[ log P_\theta(z | C, \epsilon) ] = \frac {1} {2} E_{\epsilon \sim Q_\phi(\epsilon | \tilde{z}, C)}[ \parallel \tilde{z} - G _ \phi(\epsilon) \parallel_2^{2} ] \end{align}$

[Shen+ 18]では、M1モデルとM2モデルの学習交互に行うことにより、事前分布と事後分布の形状が近接するようになること、自動評価でも既存手法と比較して良い性能を得られることを示しました。

DialogWAE

[Gu+ 19]で提案されたDialogWAEは、上記の[Shen+ 18]が検討したより自由な事前分布を対話応答生成に適用するという発想を、別のアプローチを用いてCVAEベースのモデルに適用した手法です。

[Tolstikhin+ 18]で提案され、[Zhao+ 18]でラベル情報も利用するように拡張された、Wasserstein Auto-Encodersの枠組みを使用することにより、事前分布を複数のモードを表現できるガウス混合分布として表現できるようCVAEを拡張しています。

Wasserstein Auto-Encodersでは、Wasserstein GANの式を利用してVAEの潜在変数を最適化するというAAEを拡張したような手法で、自由度の高い潜在空間から潜在変数をサンプリングすることを試みています。

f:id:KSKSKSKS2:20191223172207p:plain — [Gu+ 19]より

オリジナルのWasserstein Auto-Encodersでは、事後分布からは特にサンプリングは行わず、エンコーダーが変換した値をそのまま潜在変数として使用しますが、[Gu+ 19]ではエンコーダーが変換した値をもとに事後分布 $Q _ \phi(\epsilon | y, C)$ のパラメーターを推定し、そこからサンプリングした値をさらにニューラルネットワーク $G _ \phi(\epsilon)$ で変換したベクトルを潜在変数 $z$ として用いるような構成になっています。

$\begin{align} \epsilon &\sim Q _ \phi(\epsilon | y, C) \\ z &= G_\phi(\epsilon) \\ L_{rec}(y, z, C) &= E _ {z \sim Q _ \phi(z | y, C)}[ log P _ \theta(y | z, C ] \\ \end{align}$

KL項に当たる部分は、Discriminatorとのmin maxゲームで最適化します。具体的には下記の $L _ {disc}$ を最小化するようにパラメーター $\psi$ を、最大化するようにパラメーター $\theta$ と $\phi$ を学習します。

$\begin{align} \epsilon &\sim Q _ \phi(\epsilon | y, C) \\ z &= G_\phi(\epsilon) \\ \tilde{\epsilon} &\sim P _ \theta(\epsilon | C) \\ \tilde{z} &= G_\theta(\tilde{\epsilon}) \\ L_{disc}(y, C, z, \tilde{z}) &= E_{z \sim Q _ \phi(z | y, C)}[ D_\psi(z) ] - E_{\tilde{z} \sim P _ \theta(z | C)}[ D_\psi(\tilde{z}) ] \\ \end{align}$

また事前分布には、Gumbel-Softmax[Jang+ 17]を応用して、一つの値のみが1、それ以外はほぼ0となるような重み係数 $v _ k$ を取得することにより、ガウス混合分布を仮定し、対話履歴によりサンプルに利用されるガウス分布が変更されるように学習することを試みています。

$\begin{align} P _ \theta(\epsilon | C) = \sum_{k=1}^{K} v_k N(\epsilon; \mu_k, \sigma_k^2 I) \end{align}$

実験では、事前分布の形状によらずとも、コンテキストに則した文が生成されやすくなるという方向で、生成されるシステム発話文の多様性が大幅に向上することが示されています。

また、事前分布をガウス混合分布とした際には、構成する正規分布のうち特定の正規分布を使用して生成される応答が、肯定よりか否定よりかといったような、別々のモードの文が生成されることが可能せることを示しました。

ユーザーの特性を考慮した応答文生成への応用

発話するユーザーを指定して、応答を生成したいというケースに対して、Seq2Seqベースの手法は複数提案されており、比較的初期の手法である[Li+ 16]では、デコーダーに毎ステップ発話するユーザーの情報を与えることにより、指定するユーザーによって生成される応答を変更できることを示しています。

[Bhatia+ 17]では、[Li+ 16]の手法を拡張し、ユーザーを示す埋め込み表現を、SNSのソーシャルグラフから取得するnode2vecをもとに生成したものを使用する手法が提案されています。

[Luan+ 17]では、デコーダーをSeq2SeqとAutoEncoderで共有し、次の発話の予測と元の発話の復元を同じデコーダーを使用して行うことにより、対話以外のデータからも、ユーザーに特徴的な発話を学習できる手法を提案しました。

現在では、これらのベーシックな手法をCVAE系のモデルに応用したものが、複数登場しています。

SSVN

[Chang+ 19]で提案されたSSVN（Semi-Supervised Stable Variational Network）は、[Zhao+ 17]で提案されたkgCVAEを拡張し、ダイアログアクトの代わりに、対話履歴に含まれる以前のシステム発話を元にVAEを用いて生成したユーザーベクトルをと使用し、発話するユーザーに合った発話応答を生成しようというものです。

f:id:KSKSKSKS2:20191223180929p:plain — [Chang+ 19]より

ユーザーベクトル $z^{replier}$ は、対話履歴 $C$ のうち、 $replier$ （ようするにシステム）が発話した履歴のみ $C^{replier} = \{ c _ 2^{replier}, c _ 4^{replier}, ..., c _ L^{replier} \}$ を入力として、それを復元するVAEの潜在変数として構築されます。

$\begin{align} L_{VAE}(z^{replier}, C^{replier}) &= E _ {z^{replier} \sim Q _ \phi(z | C^{replier})}[ log P _ \theta(C^{replier} | z^{replier}) ] \\ &- KL[Q _ \phi(z | C^{replier}) \parallel P(z) ] \\ \end{align}$

CVAEパートは、上述のように、kgCVEのラベル情報をユーザーベクトルに変えたものと考えることができ、下記のように変分下限を定式化できます。この二つの変分下限が最大になるように、パラメーターを最適化していきます。これにより、以前のシステム発話を通常のCVAE以上に考慮した応答生成が行われることを試みます。

$\begin{align} z^{replier} &\sim Q _ \phi(z | C^{replier}) \\ L_{CVAE}(y, C, z, z^{replier}) &= E_{z \sim Q_\phi(z | y, C, z^{replier})}[ log P_\theta(y | C, z, z^{replier}) ] \\ &- KL[Q_\phi(z | y, C, z^{replier}) \parallel P_\theta(z | C, z^{replier})] \\ \end{align}$

もう一点特徴的なのは、各事前分布および事後分布の確率分布としてvon Mises-Fisher分布を仮定しているところです。

von Mises-Fisher分布を用いたVAEは、[Kingma+ 14a]で提案されているベーシックなReparameterization Trickでは対応することはできませんが、[Naesseth + 17]で提案されている棄却サンプリングを応用してノイズ項をサンプリングするアプローチを用いることにより、VAEにおいて使用することができるようになります（余談ですが、Reparameterization Trickの幅広い分布への応用は、[Figurnov+ 18]などでより高速な手法が提案されるなど、こちらも年を追うごとに使い勝手が良くなっていっています）。

[Chang+ 19]では、[Naesseth + 17]が提案したアプローチを、von Mises-Fisher分布に応用した[Davidson+ 18]と[Xu+ 18]のアプローチを踏襲しています。von Mises-Fisher分布を使用したVAEは、定式化によってはKL項の値を定数にすることができるため、潜在変数にデコーダーが使用する情報を格納しやすくなる点がメリットとなります。

実験では、以前までのシステム発話をより考慮しやすくなったため、既存手法と比較して大幅に生成される文の多様性が大幅に向上し、対話履歴内の以前の発話にも合った表現で文が生成されるようになることが示されています。

VHUCM

[Bak+ 19]で提案されたVHUCM（Variational Hierarchical User-based Conversation Model）は、[Park+ 18]が提案したVHCRを、対話中の二人のユーザーベクトルをコンディショナル情報として $z^{conv}$ を生成すように、二重のCVAEを使用するように改良した手法です。

f:id:KSKSKSKS2:20191223183251p:plain — [Bak+ 19]より

ユーザーベクトルは、[Bhatia+ 17]でも使用されているSNSのソーシャルグラフを元にnode2vecを用いたもの使用することにより、ユーザーおよびユーザーの組み合わせにより、発話内容が変更されることを試みます。

$\begin{align} h^{conv} &= ConvEncoder(all\_dialogue) \\ z^{conv} &\sim Q_\phi(z | h^{conv}, u^a, u^b) \\ h_t^{UE} &= UtteranceEncoder(x) \\ h_l^{CE} &= ContextEncoder(h_{l-1}^{CE}, h_t^{UE}, z^{conv}) \\ h_{t+1}^{UE} &= UtteranceEncoder(y) \\ z &\sim Q_\phi(z | h_{t+1}^{UE}, h_l^{CE}, z^{conv}, u^{s_t}) \\ P_\theta(y | x, C) &= Decoder(z, h_l^{CE}, z^{conv}) \\ \end{align}$

実験では、リファレンス文と生成される文の一致度合いが向上すること、対話ペアによって同じ質問でも受け答えの意味が変化することを示し、事前学習済みの情報をコンディショナル情報として使用することにより、生成する文の内容をうまく制約できるようになることを示しています。

まとめ

この記事では、Seq2Seqの応用から進化してきたEnd2Endな対話応答生成タスクについて、特にVAE/CVAEを応用した手法に注目して、その変遷、および模索されている方向性について紹介しました。

VHREDなどのCVAE派生手法の登場で、基本のアーキテクチャについては落ち着いてきているものの、VHREDで実現できないレベルでの更なる発話文の多様性の追求や、実用上重要となる発話内容のコントロールを行うための方法が検討されている状況です。

いずれのアプローチも、構造が複雑化してきており、データセットの分量やパラメーターの最適化の難易度も考えると、思っている以上に難しい定式化になっていそうというのが正直な感想です。

また、以前の記事でも書きましたが、対話応答生成の分野にて自動評価指標が確立されていないという問題の弊害が非常に大きく、レポートされている数字だけでは、実際にどれくらい改善されているのか、どのように改善されているのかがイマイチつかみづらいのが現状です。

一方で、同じEnd2Endな対話システムでも、Knowledge Baseや文書を参照しながらマルチターンな質問応答に答えるようなシステムは、この記事で紹介したものとはアーキテクチャが大きく異なり、Attentionを有効に活用し、正解部分を効率よく見つけて文を生成することが大きなモチベーションとなっています。

さらに、完全に文を生成するのではなく、部分的な構造を指定した上で文を生成する方法は近年注目を集めており、検索ベースのような生成とは全く違ったアプローチもまだまだ根強い人気があります。

どのようなアプローチがどのような条件下で適切なのか、対話応答生成だけでもややタスク設定が細分化してきているきらいもありますが、対話以外の分野、機械翻訳や文書要約、画像キャプション生成なども含めて、これからも追っていければと思います。

参考文献

全体

[Gao and Galley and Li 18] Neural Approaches to Conversational AI

Seq2Seq

VAE

End2End Dialogue Response Generation

User-based Dialogue Response Generation

2019-12-02

End2Endな対話システムの評価指標

Deep Learning 機械学習自然言語処理

この記事は、Qiita 自然言語処理アドベントカレンダーの2日目です。

1日目は jojonki さんによるゼロから作った形態素解析器Taiyakiで学ぶ形態素解析でした。

この記事では、End2Endな対話システムの評価指標、特に応答文生成の自動評価指標に注目して、どのような指標があるのか、どのような点が問題と考えられているのかに注目して、現在の動向やどのような課題があると考えられているかについて記載しています。

自然言語処理分野、特にその応用分野へのDeep Learningへの適用は、特にSeq2SeqとAttention機構によって進んできたと言っても過言ではありません、

対話システムでも、機械翻訳や文書要約といったその他の自然言語処理の応用分野と同じく、End2Endなモデルで対話システムを構築しようという試みが多く行われています。

Deep Learning応用の比較的初期の頃からEnd2Endな対話システムの構築という問題は取り組まれており、手法としては、言語モデルベース、GANベース、VAEベースのもの、そしてそれらの様々な派生手法が提案されています。

一方で、End2Endな対話システムのための評価指標については、新たに提案されるものはそこまで多くはないものの、既存の自然言語処理分野で使用されていた評価指標も含めて、決定版と考えられているものがない状態です。

本記事では、現在主にどのような評価指標が使われているのかを概観した後、それらの指標がどのような問題点をもちどのような解決案が提示されているかの順で、記載していきます。

対話システムの評価指標
- 自動評価
- 人間評価
評価指標の課題
- 既存指標の課題
- 対話のコンテキストを考慮した評価指標
  - ADEM(Automatic Dialogue Evaluation Model)
  - RUBER(Referenced metric and Unreferenced metric Blended Evaluation)
まとめ
参考文献

対話システムの評価指標

対話システムの評価指標は、機械翻訳や文書要約といった、自然言語処理の他のテキスト出力型のタスクと同様な指標が使用されることが一般的です。

Facebookが公開している、対話システムの学習・評価環境であるParlAIでも、メトリクスとしてはBLEUおよびROUGEといった、伝統的なn-gramベースのリファレンステキストとのマッチング指標が使用されています。*1

一方で、End2Endな生成型の対話システムが一般化してきたタイミングで、対話システム独自の評価指標も用いられるようになり始めました。

1つは、Embeddingベースと呼称される評価指標の一群で、テキストを構成する単語そのものではなく、テキストをEmbedding表現に変換した状態で、生成文とリファレンス文を比較する指標です。

もう1つが、Distinct-Nと呼ばれる、システムが生成する文の多様性を評価するための指標です。

これらの指標は対話分野以外では使用されないこともあり（対話分野でも応答文生成以外では一般的でないため）、NLP系の各種ツール（NLTKやAllenNLP）には実装がなく、nlg-evalやneural-dialogue-metricsなど、対話システム向けのリポジトリにまとめられたものが公開されています。

手動評価指標としても、対話システムに独特な指標が使用されるようになってきています。

以降では、BLEUなどの伝統的な指標を含めて、どのような評価指標があるのかについて説明していきます。

自動評価

BLEU(Bilingual Evaluation Understudy)

BLEUは、名前が示す通り機械翻訳で使用され始めた評価指標です。

Modified n-gram precisionとBest match lengthを計算し、最終的な評価スコアを出力する、n-gramベースの単純なPrecisionを置き換える指標です。

センテンスベースのBLEUは下記の用に表されます。

$Precision = exp(\sum_{n=1}^N w_n log p_n)$

$BP = 1 (c \gt r), exp(1 - \frac {r} {c}) (c \le r)$

$BLEU-N := BP * Precision$

$p_n$ は生成文に含まれるn-gramの数で、リファレンス文にも含まれるn-gramをn-gramにつき1つと数え上げた数で割った値です。

例えば、一般のUnigramのPrecisionでは、 I work on machine learningというreferenceがあった際、

ⅰ. He works on machine learningは60%、
ⅱ. He works on on machine machine learning learningは75%

がPrecisionとなりますが、ⅰの方がどう考えても良い文章です。

この問題を解決するため、BLEUではn-gramの出現回数を一回しかカウントしないことにより、同じ単語が複数回登場するだけの文の評価をあげないように工夫されています。*2

$w_n$ は重みパラメーターで、一様になるように $w_n = \frac {1} {N}$ と置かれる事が一般的です。*3

BPは短すぎる文にペナルティーを課す項で、 $c$ は生成文の合計の長さ、 $r$ は基準の長さ、一般的にはリファレンス文の平均長が使用されます。

ROUGE(Recall Oriented Understudy for Gisting Evaluation)

ROUGEは、BLEUとは異なり、n-gramベースのPrecisionだけでなくRecallにも注目する手法で、文書要約の分野で登場してきた指標です。

計算方法によっていくつかの種類が提案されています。

ROUGE-Nは、生成文中に現れるn-gramがリファレンス文中に出現する回数をもとに、RecallとPrecisionを計算する指標です。RecallとPrecisionを合わせて評価するため、F1まで計算しそこで比較することが一般的です。

ROUGE-Lは、LCS(Longest Common Subsequence) という関数を用いて、以下の式で表現される。

$R = \frac {LCS(target, reference)} {m}$

$P = \frac {LCS(target, reference)} {n}$

$ROUGE-L := \frac {R * P} {(1 - \alpha)R + \alpha * P}$

LCSは、与えられた二つの文で最も長い一致部分の長さを返す関数で、mがリファレンス文の長さ、nが生成文の長さ、 $\alpha$ は、調整用パラメーターで一般的には0.5が使用されます。

LCSを拡張したような、ROUGE-WやROUGE-Sも同じ論文の中で提案されていますが、一般的にROUGE-NやROUGE-Lがよく使用されます。

Embedding Base

Embedding Baseの評価指標は、How NOT To Evaluate Your Dialogue System: An Empirical Study of Unsupervised Evaluation Metrics for Dialogue Response Generation[Liu 2016]にて、対話応答生成・応答選択向けにまとめられた評価指標です。

上記の論文自体は対話システムの文脈では比較的よく参照されており、2019/11/10現在で401件の論文で引用されています。*4

後述しますが、上記の論文でもEmbedding Baseの指標と人間評価の間には相関はないと結論付けられていますが、語彙が異なっていても意味的な近さを既存指標よりも評価しやすいという期待からたびたび使用されています。

上記の論文では、Embedding Baseの指標として以下の3種類があげられています。

Embedding Averageは、生成文に含まれる単語のベクトルの和と、リファレンス文に含まれる単語のベクトルの和とのコサイン類似度をスコアとしたものです。

Vector Extremaは、文に含まれる各単語の単語ベクトルのうち、各次元ごとに最大値もしくは最小値を、文のベクトルの対応する次元の値として、リファレンス文と生成文のコサイン類似度をスコアとしたものです。

Greedy Matchingは、リファレンス文と生成文に含まれる単語ベクトルと比較した際に、最もコサイン類似度が高くなる単語のコサイン類似度の平均をスコアとしたものです。

いずれの指標でも、学習済みのベクトルとして、word2vecのリポジトリ *5で公開されているGoogleのNews Corpusで作成されたものを使用することが多いようです。

Distinct

A Diversity-Promoting Objective Function for Neural Conversation Models[Li 2016]にて、対話応答生成向けに、生成された文の多様性評価指標としして提案された指標です。

生成型の対話システムでは、 "I don’t know" や "I’m OK" といった無難で前後の文脈にも合うが、システムの挙動としては期待しない文が生成されることが問題なっており、上記の論文はその解決策の走りとして提出されたもので、他の論文からの参照も多く、2019/11/10現在で495件の論文で引用されています。*6

Distinctは、上記の論文内にてあくまで提案手法の評価用に定義されただけのものですが、生成文の多様性はEnd2Endな対話システムでは大きな課題として考えられており、同じような課題意識を持つ論文では幅広く使用されています。

定義は非常に簡単で、Distinct-Nは、生成された複数文中で登場したn-gramの種類数を、複数文中に登場する全てのn-gramの数で割った値として定義されます。*7

人間評価

人間による評価では、システム全体の良さ、もしくは評価軸に基づいて、直接2つのシステムを比較したり、5段階評価で点数つけしてもらうことにより評価を行います。

評価軸に基づいた評価は、FluencyやNaturalnessといった文生成一般に使用される評価軸以外にも、以下の二つの評価軸が対話システムの評価としてよく使用されます。

Interest (Informative, Richness): 対話として情報のある文かどうか。Distinctを同じ用に、常に I don’t know 等で返す場合低い評価となる

Relevance (Consistency): 直前のユーザー発話文や対話履歴との関連性がある文かどうか

後述するように、End2Endな対話システムの評価では決定的な自動評価指標はなく、必ずと言ってよいほど人間による評価を行うことが一般的です。

特に、上記の二つのように、対話として有意味か、前後の文脈を評価できているかについては、自動評価による評価が難しく、特に評価指標としてよく用いられています。

評価指標の課題

既存指標の課題

対話システムの応答生成は、他の文生成タスクと比較して、以下の2点の特徴があるため自動評価が難しいと考えられています。

コンテキストにあえば多様な応答が正解となりえ、リファレンス文と使用されている単語が違っていても正解となる
単語が一致しないだけでなく、意味的にリファレンス文と全く異なっていても、コンテキストにあえば正解となる

Liu 2016では、検索型および生成型の応答生成タスクで、それぞれ複数のモデルを用いて、非タスク指向対話の2つのコーパスを使用にて、各種評価指標と人間評価の相関を検証しています。

各対話システムが生成した応答文を、25人の評価者に5段階で評価してもらい、平均スコアを算出。その値と、自動評価指標の評価結果の値の相関を見るというのが主なアプローチです。

下記グラフは、2つのコーパスにて、人間の評価と、BLEU、Embedding Average、2グループの評価者の評価の対応関係を散布図で表したものです。

f:id:KSKSKSKS2:20191116154708p:plain — Liu 2016より

グラフの通り、人間同士の評価の相関はいずれのコーパスでも非常に高い（0.9以上）一方、自動評価指標はBLEUもEmbedding Averageも、いずれのコーパスでもほぼ相関がないようなグラフとなっています。

実際、Twitter コーパスでは、BLEUは相関が0.35ほど（さらに、ストップワードを抜いた場合は0.2ほど）、Embedding Averageも0.2ほど、Ubuntu コーパスでは、どちらもほぼ0付近の相関値となっています。

この問題に対応する方法として、論文中では以下の3つのアプローチが可能なのではないかと示唆されています。

タスク指向対話システムのように、ポリシーがが決定したアクションをもとに応答を生成するなど、正解のバリエーションがすくなるなるようにタスク設計する
それぞれのコンテキストにおいて、正解と考えられる発話文を複数用意したデータセットを構築する
リファレンス文と生成文の意味や、コンテキストと生成文の関係性を評価できる新しい評価指標を検討する

1番目は、Relevance of Unsupervised Metrics in Task-Oriented Dialogue for Evaluating Natural Language Generation[Sharma 2017]にて検討されており、非タスク指向対話に比べるとかなり高い相関が見られることを報告していますが、相関が見られる範囲および使用しているデータセットが限定できである点について考慮が必要です。*8

2番目は、残念ながら対話というジャンルの性質上構築が難しいのか、複数の応答が正解として用意されているようなデータセットはまだ見かけません。

3番目は、BERTScoreやSentence Mover’s Similarityのような、事前学習済みのEmbeddingを使用した新しい評価指標が、対話以外の分野から続々と登場してきています。

また後述するように、対話システムの分野でも、対話のコンテキストを考慮した複数の評価指標が提案されています。

対話のコンテキストを考慮した評価指標

ADEM(Automatic Dialogue Evaluation Model)

ADEM[Lowe 2017]は、最初期のコンテキストを考慮した対話システムの評価指標で、対話履歴、リファレンスの応答文、システムが生成した応答文をもとにスコアを出力します。

スコアを出力するモデルは、ベースラインシステムが生成（選択）した対話応答文を、人間が評価した値を集めたデータセットを学習して構築します。

上記のデータセットのテストセットで評価した結果、人間評価との相関値がBLEUやROUGEなどの既存の指標を大幅に上回ることを示しています。

f:id:KSKSKSKS2:20191123172728p:plain — Lowe 2017より

一方で、上記データセットに含まれる該当システムへの人間評価を学習時に取り除いた場合、該当システムが生成した応答文への評価の相関値が大幅に低下する実験結果も示されており、扱いには注意が必要です。

RUBER(Referenced metric and Unreferenced metric Blended Evaluation)

RUBER[Tao 2018]は、生成した応答文と、リファレンスの応答文との一致率と、対話コンテキストの一致率を別々に計算し統合することにより、人間評価に近い評価を得られる指標の構築を試みた指標です。

生成した応答文とリファレンスの応答文との一致率(Referenced Metric)は、Embedding Baseの指標と同様、既存の事前学習済み単語ベクトルを使用します。

生成した応答文と対話コンテキストの一致率(Unreferenced Metric)は、ニューラルネットを使用して、学習データに含まれるコンテキスと応答文の組み合わせでは高く、学習データに含まれない組み合わせでは低くなるように、スコアを出力するモデルを学習します。

Referenced MetricとUnreferenced Metricの統合方法は、最小値を用いるケース、算術平均を用いるケース、幾何平均を用いるケース、最大値を用いるケースで検証されており、最大値以外は、概ね人間評価との相関値が0.45前後と比較的高い数値を得られることを示しています。

f:id:KSKSKSKS2:20191123174639p:plain — Tao 2018より

一方で、上記の結果は対話システムと同じデータを用いてUnreferenced Metricを算出するモデルを学習した場合の値であり、異なるデータで学習した対話システムが生成した応答文の評価においては、人間評価との相関値が0.35ほどと10%ほど下がってしまうことが示されています。

また、Referenced MetricとUnreferenced Metricともに、単語をベクトルに使用する事前学習済みのモデルとして、word embeddingではなくBERTなどのContextual Embedingにするなど、いくつか改良を加えた方が、人間評価との相関値がより良くなるという報告も存在しています。

まとめ

本記事では、End2Endな対話システムの自動評価指標として、言語処理分野で一般的なものから、対話の応答生成用に独自で使用されている指標についても紹介しました。

また、人間評価との乖離という問題についても、どのような議論が行われているかを紹介しました。

残念ながら決定的な自動評価指標がないのがまだまだ現状です。

ここで紹介されていないけど、こんな評価指標あるよなどがあれば、ぜひ教えていただければ幸いです。

参考文献

*1:https://github.com/facebookresearch/ParlAI/blob/master/parlai/core/metrics.py

*2:https://github.com/nltk/nltk/blob/14c701fbc99ce2242a2c912b6c82177b03fad744/nltk/translate/bleu_score.py#L336

*3:https://github.com/nltk/nltk/blob/14c701fbc99ce2242a2c912b6c82177b03fad744/nltk/translate/bleu_score.py#L201

*4:https://scholar.google.com/scholar?um=1&ie=UTF-8&lr&cites=9769435644141907733

*5:https://code.google.com/archive/p/word2vec/

*6:https://scholar.google.com/scholar?um=1&ie=UTF-8&lr&cites=6301775661806157248

*7:論文中では、Table 2の説明中に "distinct-1 and distinct-2 are respectively the number of distinct unigrams and bigrams divided by total number of generated words." と記載されている

*8:https://openreview.net/forum?id=r17lFgZ0Z

2019-09-15

CNNの精度向上手法のモデルサイズによる効果の違いを調べてみた

CNN Deep Learning 機械学習画像認識

画像認識タスクはDeep Learningにより大幅に精度が向上してきた分野です。
1クラス500枚・100クラスの分類を行う必要がある、比較的難易度が高めのCIFAR-100ベンチマークでも、最新の手法であるGPipeやEfficientNetでは、テストセットにて90%を超えるAccuracyを達成しています。

paperswithcode.com

しかし、これらの最高精度を叩き出すような手法はパラメーター数が600Mや、60Mと大量のパラメーターが必要になります。
このように、パラメーター数が多いモデルは、精度を向上させやすい分、推論や学習にパラメーター数に応じた時間が必要な問題があります。

一方で、多くのモデル構造では、パラメーター数が数Mにいくかいかないかの、より小さいモデルを構築することができます。

このようなモデルは、深いモデルに比べ精度面では劣るものの、処理速度は圧倒的に高速で、実用面においてはどのようなアプローチが有効かを試行錯誤するために非常に使い勝手が良い一面もあります。

しかし、非常に小さいモデルは、通常の論文では報告対象になっていないことが多く、一般的なサイズのモデルで効果が出ているような手法でも、必ずしも効果がある保証はありません。

この記事では、ネットワーク構造としてResNet、データセットとしてCIFAR-100を使用して、ネットワーク構造の微変更およびデータ拡張手法が、非常に小さいモデルでもどのくらいの精度向上が可能か、非常に小さなモデルでの精度向上の効果は、一般的なモデルの効果をどのくらい相関があるのかを調べてみました。

その結果、ResNet164とResNet29の比較において、以下のように、精度向上手法の効果は、非常に小さいモデルと一般的なサイズのモデルとの間で相関が見られることがわかりました。

実験条件
ResNet164での結果
通常のResNet29による学習
- ResNet29での結果
- 各精度向上手法を適用した結果
まとめ
参考

実験条件

この記事では、ResNetのうちCIFAR-100を学習したモデルでの精度の比較対象によく使用される、ResNet164をベースラインとして扱います。

ResNet164は本家論文の設定ではなく、一般的によく使われているpre-activtionを含む設定を利用します。

比較対象としては、ResNet164からResBlock数が6分の1と非常に小さい、ResNet29を使用しました。

ベースのデータ拡張手法として、ランダムな水平方向への反転、上下左右4ピクセルのパディングを入れた上でのランダムクリッピングを使用しています。

入力するデータは、学習データすべてのチャネルごとの平均と分散を使用して正規化した状態でモデルに入力しています。

Weight Decayは1e-4、学習は160エポック行い、Learning Rateは最初は0.1、80エポック以降は0.01、120エポック以降は0.001としています。

報告しているテストデータのAccuracyは、各組み合わせそれぞれ一回のみ行った実験の結果で、最終エポック時点での学習済みモデルでの結果をそのまま記載しています。

ResNet164での結果

通常のResNet164による学習

まず上記の実験設定の記載のまま、ResNet164により学習した結果は下記のとおりでした。

f:id:KSKSKSKS2:20190915172020p:plain — ResNet164通常版

テストデータのAccuracyは75.09%と、論文に記載されている75.67%より若干低い結果ですが、概ね論文と同等の性能が出ることを確認できました。

Squeeze and Excitationを追加

Squeeze and Excitationは、各Residual層の出力に、チャネル単位でAttentionのような働きをする重みを計算した後、Identity層の出力と合計するように処理を加えたものです。

実装は、こちらにあるように非常に簡単に実現できますが、ResNet-164を使用したCIFAR-100では、3ポイントほどテストデータでのAccuracyが向上し、78.69%であったと論文で報告されています。

今回の実験では、前述の通常のResnet164より1.5ポイントほど向上し76.7%のAccuracyを実現しました。論文で報告されているほどの精度ではありませんでしたが、確かにAccuracyがベースモデルより向上することを確認できました。

f:id:KSKSKSKS2:20190915172711p:plain — ResNet164 SEBlock追加版

mixupを追加

mixupはデータ拡張手法の一つで、二つのクラスの画像を重み付きで合成した画像を入力とし、クラスラベルも同じ重みを使用して合成し、それをもとにモデルのロスを計算します。

CIFAR-100では、ResNet18のpre-activationモデル（今回使用しているモデルとは各層のチャネル数が異なり非常に多い）を使用した場合、テストセットでベースラインを4.5ポイント上回る78.9%のAccuracyが報告されています。

こちらを参考に実装し試した所、テストデータで78.47%とベースラインを3.4ポイントほどと、論文の報告よりは小さいものの大きく向上することを確認できました。

f:id:KSKSKSKS2:20190915173338p:plain — ResNet164 mixup追加版

Squeeze and Excitationおよびmixupの両方を追加

最後に、Squeeze and Excitationおよびmixupの両方を追加したものを試した見た結果が下記となります。
参考になる論文はありませんが、テストデータでのAccuracyが79.40%と、mixupのみを追加した際に比べて0.9ポイントほど上昇していることから、それぞれの手法が効果を発揮しよりよい性能を実現できていることがわかります。

f:id:KSKSKSKS2:20190915174045p:plain — ResNet164にSEBlockおよびmixupを追加した版

通常のResNet29による学習

さて、上記までではResNet164を用いて既存の論文の再現実験を行い、概ね実験結果が再現でき、少なくともベースラインよりはテストデータのAccuracyが向上することは、論文の報告どおりであることを見てきました。

ここからは、ResNet164より大幅に小さいResNet29でどのくらい上記の精度向上手法が有効かをみていきます。

ResNet29での結果

ResNet164のブロック数を6分の1にして作成したResNet29にて、同じ実験条件で学習を行いResNet29での性能確認を行いました。

下記のように、テストデータで71.19%とResNet164に比べて3.9ポイント低い性能でした。

f:id:KSKSKSKS2:20190915175215p:plain — ResNet29通常版

ResNetの本家論文では、CIFAR-10において同じ6分の1のブロック数の違いのあるResNet110とResNet20の比較において、2.3ポイントほどの差が見られたことを報告していますので、比較的妥当な結果であると考えられます。

各精度向上手法を適用した結果

ResNet29にSqueeze and Excitationのみ追加した場合、テストデータデータでのAccuracyが71.62%と、ベースラインを0.4ポイントほど上回る結果を示しました。

f:id:KSKSKSKS2:20190915175632p:plain — ResNet29 SEBlock追加版

ResNet29にmixupのみ追加した場合、テストデータデータでのAccuracyが72.34%と、ベースラインを1.1ポイントほど上回る結果を示しました。

f:id:KSKSKSKS2:20190915175437p:plain — ResNet29 mixup追加版

ResNet29にSqueeze and Excitationとmixupの両方を追加した場合、テストデータデータでのAccuracyが74.72%と、ベースラインを3.5ポイントほど上回る結果を示しました。

f:id:KSKSKSKS2:20190915175812p:plain — ResNet29にSEBlockおよびmixupを追加した版

まとめ

それぞれの精度向上手法と、テストセットでの最終エポックまで学習した際のAccuracyは下記の通りでした。

	ResNet29 pre-activation	ResNet164 pre-activation
精度向上手法適用なし	75.09	71.19
Squeeze and Excitationのみ	76.70	71.62
mixupのみ	78.47	72.34
Squeeze and Excitationおよびmixupのみ	79.40	74.72

ここから、ResNet29で精度向上が見られた手法は、ResNet164でも同等以上の精度向上が見られること、上昇の仕方の傾向は概ねResNet29とResNet164で同じであることが読み取れます。

ResNet29はResNet164に比べてパラメーター数が約6分の1と非常に小さいモデルです。
また学習に要した時間は、GeForce2080を使用した今回の実験においては、ResNet29で40分ほど、ResNet164で3時間20分ほどと、約5分の1でした。

単純に計算すると、ResNet29はResNet164の30分の1ほどのリソースの専有量で一回の実験が行えると考えられます。

今回は、非常に限られた実験条件で測定した結果ですが、モデルサイズによらず既存の精度向上手法は同じような傾向の実験結果が得られることがわかりました。

タスクの内容やベースモデル、使用するデータセット、行う精度向上手法によって、大きく変わるとは思いますが、
小さいモデルで有効そうなアプローチをピックアップした後、大きいモデルで実際に使用するモデルを学習させ最終結果を得るという方法が、現実的に意味がありそうなアプローチであることは、
より多くのパターンをより少ないリソースで試行錯誤するためには、非常に重要な仮定となります。

リソースが少ない環境で実験をせざるを得ない身としては、このような小さくて高速なモデルでの実験結果や条件を変更したときの効果の相関性なども、ぜひ公開していって欲しいなと思う所です。

参考

2019-05-26

ニューラルネットワークを使用した対話システム（２）〜機械読解質問応答システム〜

Deep Learning 機械学習自然言語処理人工知能

本記事は、「Neural Approaches to Conversational AI*1」を元に、ニューラルネットワークを使用した対話システムについて解説する記事の二回目です。

前回の記事では、対話システムの概要とKnowledge Base質問応答システムについて説明しました。

ksksksks2.hatenadiary.jp

今回は、二つ目の質問応答システムである、機械読解質問応答システムについて説明します。

機械読解を利用した質問応答システムは、Watsonに代表されるような、大量の文書をもとにユーザーの質問に対して応答を返すシステムのことを指します。

まず、機械読解とは何か、それをどのようにニューラルネットにより実現するかについて説明します。

続いて、機械読解を組み込んだ質問応答システムをどのように実現するかについて、システムの例も見ながら説明していきます。

機械読解をニューラルネットで実現する
機械読解質問応答システム
- 機械読解質問応答システムの問題設定
- 機械読解質問応答システムの例
まとめ

機械読解をニューラルネットで実現する

機械読解とは何か

機械読解とは、パッセージ $P$ と質問文 $Q$ から応答 $A$ を返すようなタスクを指します。

パッセージ $P$ は、SQuAD*2のように一つの文書で構成されることが一般的です。一方で、MS MARCO *3のように複数の文書から構成されることもあります。

質問文 $Q$ や応答 $A$ はこちらも一般的には一つずつですが、質問と応答の繰り返しを扱い、対話のコンテキストを考慮した応答を行うことに注目したデータセットもあります。

応答の形式としては、パッセージ内に含まれる文や単語を選択することにより応答を返すものが一般的です。
CNN/Daily Mail*4のように選択肢があらかじめ指定されている場合や、パッセージ内の特定の範囲を選択肢する場合があります。

システムの応答をより自然に、より実用的にするために、応答の形式には様々な例外が提案されています。例えば、下記のような応答を行うシステムがあります。

Yes/Noといった質問文への肯定や否定を返すもの
与えられているパッセージだけでは答えが返せないというNo Answerという形式を返すもの
回答が含まれていそうな文書を並べかえるもの
自然な対話になるように応答文を生成することを求めるもの

これらの機械読解システムは、ニューラルネットの登場により飛躍的な発展を遂げました。
BERT*5に代表される文理解モデルにより、パッセージと質問文のマッチングで応答可能なデータセットでは、精度が大幅に向上したのです。

その性能は驚愕に値するもので、SQuADデータセットにおいて完全一致および部分一致のいずれでも、人間の成績を大きく上回るものでした。

機械読解をニューラルネットで実現する方法

以降では、ニューラルネットワークを用いて、どのように機械読解を実現しているかを、下記二つの観点から説明します。

パッセージおよび質問文を、どのようにしてニューラルネットが扱いやすい形式に変換しているか
変換したパッセージおよび質問文を、どのようにマッチングして応答を選択しているか

ニューラルネットで自然言語を扱う場合、一般的に文字や単語を、埋め込み表現と呼ばれるベクトルの形式に変換したものを使用します。

BiDAF*6と呼ばれる機械読解のベースラインモデルでは、単語単位のCharacter Embeddingと、文字単位のWord Embeddingの両方を使用しています。
ベクトルに変換した文字列および単語列を結合し、ネットワークの入力とします。

次に、上記で作成した埋め込み表現をニューラルネットモデルに入力して、文章全体のコンテキストも加味したベクトル表現に変換します。

一般的にこのフェーズでは双方向RNN（Bidirectional RNN）がよく使用されます。BERTのようにTransformerライクなself-attentionを含む層を利用することもあります。

ここまででの流れで、パッセージおよび質問文をニューラルネットで扱いやすいベクトル表現に変換していくことができました。

続いて、このベクトル表現を用いて応答を選択していきます。

ここで非常に重要になるのが、attentionと呼ばれる、コンテキストの重要度を決定する機構です。

attentionは、seq2seqモデルでにおいて、入力文の各語の影響度合いを、出力文として生成される単語のポジションによって変更するために誕生したものです。

機械読解モデルでは、質問文に含まれる単語をもとに、パッセージに含まれる単語の重要度を計算したり、逆にパッセージに含まれる単語をもとに質問文に含まれる単語の重要度を計算したりするために使用されます。

また、Transformerのようなself-attentionを利用する層では、パッセージならパッセージ自身の、質問文なら質問文自身の、文全体のコンテキストを考慮して文に含まれる各単語の重要度を計算します。

このattentionの仕組みによって、パッセージと質問文をニューラルネットが自動的にマッチングしているものと考えられます。

最後に、attentionを考慮したあとのコンテキストベクトルを使用して出力を選択します。

単語選択式の回答の場合は、上記のコンテキストベクトルをもとに別のニュールネットに通して、それぞれの選択肢の尤度を計算します。

範囲選択式の回答の場合は、開始位置と終了位置、それぞれの尤度を上記のコンテキストベクトルをもとに計算します。

解答を選択するためのニューラルネットワークとしても、一般的に双方向RNNがよく使用されます。他には、線形モデルやTransofrmerのエンコーダー層を使用するケースもあります。

様々な機械読解モデル

ここまで、機械読解の一般的なモデルについて説明してきました。
ここからは、上記で紹介した一般的な構成では対応が難しい問題に対する、様々なモデル構成についてみていきたいと思います。

まず最初に紹介するのは、DrQA*7です。
DrQAは、Wikipediaの全ドキュメントを対象に、ユーザーからの質問に応答するために設計されたモデルです。

WikipediaベースのデータセットであるSQuADと、追加のデータセットを使用したマルチタスクラーニングで、最大36.5%の精度で完全一致の応答を返すことを実現しました。

DrQAは、Document RetrieverとDocument Readerの二つのコンポーネントからなります。

Document Retrieverでは、大量のWikipediaドキュメントから、5つの候補ドキュメントを抽出します。
このコンポーネントにはニューラルネットは使用されておらず、質問文と似通ったバイグラム構造を持つドキュメントを抽出します。

Document Readerでは、抽出されたドキュメントをパラグラフ単位で質問文とマッチングします。

パラグラフベクトルは、Word Embeddingや種々の特徴量を結合して構成されます。
質問文ベクトルは、Word Embeddingを一層のRNNに通し、その出力をself-attentionでならしたものを使用します。

上記のように作成したパラグラフベクトルと質問文ベクトルから、パラグラフ単位で開始位置と終了位置の尤度を計算します。
最後に、最も尤度の高い開始位置と終了位置の組み合わせを答えとして出力するという仕組みです。

f:id:KSKSKSKS2:20190516001715p:plain — Chen 2017より

ReasonNet*8およびReasonNet++*9のように、パッセージと質問文を複数回マッチングするモデルもあります。人間が文章を読むときのように、重要そうな部分を繰り返し読解し答えを生成することを試みているモデルです。

これらのモデルは、Memory Networks*10を拡張したもので、Memoryに保存されたパッセージと、マッチングに重要そうな質問文のコンテキストを繰り返し更新しながらマッチングします。

ReasonNetとReasonNet++は、さらにターミネーションフラグを内部に持ちます。このターミネーションフラグがTrueになる、もしくは規定された最大回数に達するまでマッチングを行います。
動的な回数マッチングすることにより、問題に合わせたマッチングを実現することを試みているのです。

パッセージと質問文のベクトル化は、前述した埋め込み表現、双方向RNN（もしくはTransformer）、attention機構を使用して生成します。
その後、パッセージベクトルをメモリーに、質問文ベクトルを答えを探索する（Reasoningを行う）RNNの初期状態に設定し、終了されるまでRNNの状態を更新しながらマッチングを行います。

ターミネーションフラグを持つ場合、学習は通常のSGDでは無理であるため、強化学習の枠組みを利用してニューラルネットでのモデリングを行っています。

応答は、最終ステップのマッチング結果を利用して、開始位置と終了位置の尤度を計算することにより生成します。
一方、SAN*11やR.M-Reader*12のように、マルチステップのマッチングを行いつつ、各ステップで計算した尤度を総合して最終的な出力を行うモデルもあります。

f:id:KSKSKSKS2:20190519114354p:plain — Shen 2017 より

機械読解質問応答システム

機械読解質問応答システムの問題設定

機械読解を利用した質問応答システムは、まだまだ新しい分野です。2018年ごろから続々と専用のデータセットが提案され、今盛り上がりを見せだしている分野でもあります。

複数のデータセットがあり、それぞれ細かい部分では異なりますが、共通する問題設定は下記のようになります。

質問者は、パッセージを見ずに、周辺情報のみを与えられて質問を行う
回答者は、パッセージを見ながら、抽出もしくは極力語彙を変えない形で応答を行う
質問者は、以前の質問の情報を必要とする質問を行う
上記を数ターン繰り返し、一つの対話データとする

対話というほど自然で流暢なやり取りではありませんが、数ターン前までの履歴を考慮して応答ができるかを問うています。
具体的には、直前の質問文や回答文への参照が含まれているような文が質問文に含まれることになります。

その他の機械読解データセットと比較して、タスクとしての難しさは主にこの参照解析にあると考えられています。
以前の質問および回答のどの部分を参照しているのかを把握する必要があり、単純なパターンマッチだけでは解けない問題が現れるためです。

一方で、データセットの分析結果は必ずしもこの仮説に沿わない結果となっています。
質問に応答するために参照解析が必要かどうかに関係なく回答精度はあまり変わらないという結果や、参照解析とは別の要因で回答精度が変化するという結果が示されています。

機械読解質問応答システムの例

CoQA*13は、パッセージからの範囲抽出だけでなく、それを要約した形式で応答を行うことを要求するデータセットです。
質問文や応答文が、それぞれ平均5.5単語および2.7単語とSQuAD並に短いのも特徴の一つです。

CoQAの論文の中では、上記で紹介したDrQAによる回答範囲選択と、Pointer-Generator Network*14を利用した回答文の要約を組み合わせた手法を、最も性能の良かったモデルとして提示しています。
最も性能の良かったモデルでもF1が65.1%と、人間の88.8%という性能を大きく下回ることが示されています。

CoQAは、登場して約一年ほど経過した2019年5月現在、性能が大幅に向上しました。LeaderBoard上では、人間に匹敵する性能のモデルが登場しています。
BERTの登場が大きく影響しており、その他の範囲選択型、抽出型の機械読解タスクでも同様の現象が発生しています。

QuAC*15は、範囲選択型の応答と、応答の意図をダイアログアクトとして指定した、二種類の応答を返すことを要求するデータセットです。

ダイアログアクトは、範囲選択だけでは意図が取りづらい応答を、質問者が理解するために付与しているものです。
このデータセットでは、ダイアログアクトとして、答えの自信度を示すフラグ、Yes/No、No Answerを示すフラグの3種類のフラグを組み合わせたものを応答します。

またQuACは、パッセージの長さが396.8単語、応答の長さが平均14.6単語と、SQuADに比べて3倍以上長めであることも特徴です。

QuACの論文では、コンテキストを考慮するように改造したBiDAF++を最も性能が良かったモデルとして提示しています。
人間のF1値が80.8%だったところ、モデルの性能は60.6%ほどでだいぶ開きがあります。

ダイアログアクトのうち、Yes/NoフラグのF1は、人間の性能と近く86.1%の性能を示しました。一方、答えの自信度を示すフラグのF1は61.6%程度でした。

QuACは、CoQAと同じ時期に登場したデータセットですが、LeaderBoard上は、BERTを応用したモデルでも、まだまだ人間の性能には及ばない状態です。論文内で提示された性能をまあまあ改善する程度に留まっているのです。

QuAC論文の分析では、以前の質問と現在の質問の応答の選択範囲が離れていればいるほど、応答選択のF1が最低40%ほどにも下がることが示されています。
また、答えが含まれる文章が分かっている場合のF1は72.4%と大幅に向上することも示されています。

このことから、QuACに含まれるパッセージが他のデータセットより非常に長く、マッチングする文を適切に選択できていないことにより、識別精度がなかなか向上しないのではないかと考えられます。

まとめ

本記事では、機械読解というタスク、そして機械読解を利用した質問応答システムについて説明してきました。

機械読解というタスク自体は、昨年のBERTの登場以降、特定の文章に対するシンプルな質問に対して、範囲指定型の応答を行う問題では、非常に高精度で回答を生成できることが示されています。

一方で、質問応答システム用の機械読解は、昨年ようやくデータセットが出てき始めたという状態です。それゆえ、機械読解を単純にマルチターンに拡張したような問題形式であっても、人間の精度に到達できていないようなケースも存在します。

さらに、複数の文書を参照したり、応答を生成する必要がある問題は、まだまだ人間の精度に達していないというのが現状です。

上記を考慮すると、実用レベルの機械読解型の質問応答システムを構築することは、まだまだ先の話になりそうです。

しかし、根拠となる文書と、質問・回答のペアさえあればシステムが構築できるという利点は、今まで人間のオペレーターが応答してきた回答が大量にあるような環境にとっては、喉から手が出るほどほしいシステムであることは間違いないでしょう。

機械読解は研究領域でも非常に注目を集めており、昨年だけで10数個の新たなデータセットが提案されています。
対話システムだけでなく、マルチモーダルな意図理解、高度なNLIが必要なタスクなど、人間でも少し難しいタスクを、ニューラルネットでも行えるのではないかという期待が高まっています。

設定を物語形式で与えることにより、雑談に回答するような対話システムも構築できるかもしれません。

機械読解を利用した質問応答システムが、いたるところで利用される日まで、さほど時間がかからないのではと期待できます。

*1:[1809.08267] Neural Approaches to Conversational AI

*2:SQuAD: 100,000+ Questions for Machine Comprehension of Text

*3:MS MARCO: A Human Generated MAchine Reading COmprehension Dataset

*4:Teaching Machines to Read and Comprehend

*5:BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding

*6:Bidirectional attention flow for machine comprehension

*7:Reading Wikipedia to Answer Open-Domain Questions

*8:ReasoNet: Learning to Stop Reading in Machine Comprehension

*9:An empirical analysis of multiple-turn reasoning strategies in reading comprehension tasks

*10:Memory Networks

*11:Stochastic answer networks for machine reading comprehension

*12:Reinforced Mnemonic Reader for Machine Reading Comprehension

*13:CoQA: A conversational question answering challenge

*14:Get to the point: Summarization with pointer generator networks

*15:QuAC: Question answering in context

2019-05-04

トポロジカルソートと強連結成分分解でWikipediaの特定カテゴリー配下のページをすべて取得する

グラフ理論

Wikipediaの特定カテゴリー配下のページをすべて取得するためには、整理されていないグラフデータ特有のいくつかの問題に向き合う必要があります。

一つは、Category:カツラ科と糸井の大カツラのように、サブカテゴリーにはページへのリンクが含まれているが、カテゴリー本体にはページへのリンクが含まれていないケースがあるという問題。

もう一つは、Category:インフォグラム・エンターテインメントームソフトとCategory:アタリのゲームソフトのように、お互いがお互いのサブカテゴリーに含まれてしまっているケースがあるという問題です。

これらの問題は、以下の手順を踏むことで解決できます。

カテゴリーにリンクされているページだけでなく、サブカテゴリー内のリンクを順にたどって含まれるすべてのページを収集する
ただし、一度たどったカテゴリーに再度到達した場合、それ以上はそのルートを探索しない

日本語Wikipediaのカテゴリー数は21万以上あります。ナイーブに上記のアプローチを実行すると、配下のサブカテゴリーの深さや数量に応じて時間がかかってしまいます。

そこで、事前にカテゴリー - サブカテゴリーのリンク構造を洗い出しておくことを検討します。グラフに関するアルゴリズムである、トポロジカルソートと強連結成分分解を使用することにより、シンプルにこの処理を実装することができます。

以下では、Wikipediaデータからカテゴリーリンクの一覧を取得する方法から、トポロジカルソートと強連結成分分解を使用して、カテゴリー配下の全てのページを取得するアプローチについて紹介します。

紹介する処理の実装は、下記のリポジトリの category.py にまとめています。

Wikipediaからカテゴリーリンク一覧データを取得する
カテゴリーリンク一覧データから配下のページ一覧を洗い出す
まとめ

Wikipediaからカテゴリーリンク一覧データを取得する

まず、Wikipediaのカテゴリーリンク構造を表すデータを取得します。Wikipediaのカテゴリー関係のデータには2種類あります。

1つ目は、カテゴリーとページ、カテゴリーとカテゴリーの親子関係を表したカテゴリーリンクデータ。
2つ目は、ページIDとページ名の一覧を含むページ一覧データです。

詳細は後述しますが、カテゴリーリンクデータだけではカテゴリーの親子関係を完全にたどることはできません。ページ一覧データも使用することにより、ようやくカテゴリーの親子関係を洗い出せます。

カテゴリーリンクデータの取得

カテゴリーリンクデータは、Wikipedia内のカテゴリーとページ、カテゴリーとサブカテゴリーのリンク関係を表すデータです。*1
SQLのテーブルデータとして提供されており、3つの重要なカラムを持ちます。

cl_from はリンク元（配下のページもしくはサブカテゴリー）を示すカラムで、ページIDが格納されている
cl_to はリンク先（親カテゴリ）を示すカラムで、カテゴリーの名称が格納されている
cl_type はリンク元のページ種類を示すカラムで、ページかサブカテゴリーかを示す値が格納されている

注意が必要なのは、 cl_from と cl_to とでは格納されている値の種類が異なる点です。このままでは、サブカテゴリー配下のページおよびサブカテゴリーを探索する際に問題がでてしまいます。

そこで、下記のページ一覧データを使用することにより、 cl_from と cl_to に格納されている値のマッチングを行います。

ページ一覧データの取得

ページ一覧データは、Wikipedia内のページに関する基本情報を表すデータです。このページ一覧データにはカテゴリーページのデータも含まれています。*2
カテゴリーリンクデータと同じくSQLのテーブルデータとして提供されており、2つの重要なカラムを持ちます。

page_id は各ページのページIDを示すカラムで、カテゴリーリンクデータの cl_from に対応する値が格納されている
page_titleは各ページのタイトルを示すカラムで、カテゴリーリンクデータの cl_to に対応する値が格納されている

上記からわかるように、ページ一覧データを使用してページIDとページタイトルの対応関係を取得することができます。

この情報を利用して、カテゴリーリンクデータに含まれる cl_from をページタイトルに（もしくは、 cl_to をページIDに）変換することにより、カテゴリーの親子関係をたどることができます。

カテゴリーリンク一覧データの生成

上述のカテゴリーリンクデータとページ一覧データを用いて、カテゴリーリンク一覧データを作成します。

このとき、カテゴリーからサブカテゴリーへのリンクを示すデータと、カテゴリーからページへのリンクを示すデータを別々に作成することがポイントです。理由は2つあります。

一つ目の理由は、ページとカテゴリーの名称が重複することがあるためです。
Wikipediaでは、名前空間内の名称の一意性は担保されています。しかし、ページ名称とカテゴリー名称とは、お互いに独立の名前空間を持つ運用が行われているため、名称が衝突する可能性があります。
実際に、Category:カツラ科とカツラ科のように衝突している例が多く存在します。

二つ目の理由は、後述するトポロジカルソートと強連結成分分解の計算量を削減するためです。
これらのアルゴリズムは、ノード数とエッジ数の合計に比例した計算量がかかります。また、入口も出口もあるようなノードを整理するために使用されるものです。
このため、確実に処理の対象にならいないことが分かっているページを表すノードは、トポロジカルソートと強連結成分分解の対象になるカテゴリーを表すノードとは、分けて管理しておく方が効率よく扱う事ができます。

GitHubの実装では、カテゴリー名からそのカテゴリー配下のページのセットを返す categorypages オブジェクトと、カテゴリー名からそのカテゴリー配下のサブカテゴリーのセットを返す categorygraph オブジェクトを生成するようにしています。

def show_category_directlinks(categorypages, category):
    if category in categorypages:
        print("Pages:", categorypages[category])

現時点では、上記の show_category_directlinks 関数を使用し、 category に「カツラ科」と入力すると、配下のページとして「カツラ_(植物)」と「カツラ科」が取得できるだけです。
「カツラ科」カテゴリーのサブカテゴリーである、「著名なカツラ」に配下のページは残念ながら取得することはできません。

def show_category_alllinks_with_dfs(categorypages, categorygraph, category):
    class Node(object):
        def __init__(self):
            self.visited = False

    V = defaultdict(Node)
    pages = set()

    def visit(v):
        nonlocal pages

        if V[v].visited:
            return
        V[v].visited = True
        if v in categorypages:
            pages |= categorypages[v]
        if v in categorygraph:
            for m in categorygraph[v]:
                visit(m)

    visit(category)
    print("Pages:", pages)

一方、深さ優先探索ですべての配下のサブカテゴリーを探索する show_category_alllinks_with_dfs 関数を使用することにより、すべての配下のページにアクセスすることができます。
しかしこの方法では、「科学」カテゴリーのようなサブカテゴリーおよび後述するSCCが大量にあるカテゴリーの探索に、それなりの時間を要してしまいます。

実際、手元のMBP環境では20秒ほどかかりました。これでは、頻繁にカテゴリー配下のページを取得する必要がある際には使い物になりません。配下のサブカテゴリー一覧を事前に洗い出しおくことを検討する必要があります。

カテゴリーリンク一覧データから配下のページ一覧を洗い出す

以下では、カテゴリーリンク一覧データから配下のページ一覧を取得する方法について説明していきます。方針は、下記の2ステップのみです。

トポロジカルソートを利用して、カテゴリーをサブカテゴリーが親カテゴリーより後ろにくるようなリストに並び替える
上記で作成したリストを後ろから順に処理し、サブカテゴリーのページ一覧を親カテゴリーのページ一覧にマージする

このとき、Wikipediaのカテゴリーリンクに巡回が存在することが大きな壁として立ちはだかります。
そこで強連結成分分解を使用して、この巡回するルートを削除することにより、処理が問題なく実現できるように試みます。

グラフの基礎

グラフとは、ノードとエッジの組で表せるデータ構造のことを指す用語です。

ノードは、グラフ内の要素を表し、Wikipediaのデータではページやカテゴリーに相当します。
エッジは、ノード間の接続情報を表し、Wikipediaのデータではカテゴリーリンクデータに相当します。

グラフは、エッジに向きがあるか否かで大きく二つに分けられます。有向グラフと無向グラフです。

有向グラフは、連絡網やTwitterのフォロー関係のように、エッジに向きがあるグラフのことです。この記事で扱っているカテゴリーリンク一覧データも、まさに有向グラフの一つです。

一方、無向グラフは、路線図のように、エッジに向きがないグラフのことです。

有向グラフは、閉路と呼ばれる巡回構造を持つものがあります。一方で閉路を持たない有向グラフも存在し、このようなグラフを有向非巡回グラフ（DAG：Directed Acyclic Graph）と呼びます。

このDAGには非常に便利な性質があり、下記で説明するトポロジカルソートを適用できることもその一つです。

トポロジカルソートによるノードの並び替え

トポロジカルソートは、上述のDAGに適用することにより、グラフ内のノードを子ノードが親ノードより後ろにくるように並べ替えることができるアルゴリズムです。*3
お気持ちだけ簡単に説明すると、下記の手順でソートを実現します。

グラフ内の探索されていない任意のノードを選択する
選択したノートからたどれるルートを深さ優先で探索する
子ノードがないノードは、グラフから除きリストの前方に追加する
すべての子ノードをグラフから取り除いたノードも、グラフから除きリストの前方に追加する
グラフからノードがなくなるまで、上記1-4の作業を繰り返す

このトポロジカルソートを、カテゴリー名からそのカテゴリー配下のサブカテゴリーのセットを返す categorygraph に適用します。期待値はソートされたカテゴリー一覧が返されることですが、残念ながらそのままではうまくいきません。

なぜなら、 categorygraph オブジェクトには、Category:インフォグラム・エンターテインメントームソフトとCategory:アタリのゲームソフトのように、お互いがお互いのサブカテゴリーであるケースを含むためです。

つまり、グラフに閉路が存在するため、非巡回なグラフにのみ適用できるトポロジカルソートが上手く機能しないのです。

この問題を解決するためには、なんとかしてグラフ内から閉路を検出して取り除いてやる必要があります。その方法として、下記の強連結成分分解を使用します。

強連結成分分解による閉路の検出と除去

強連結成分（SCC：Strongly Connected Components）分解は、有向グラフ内の強連結成分を検出し、それらを一つにまとめるために用いることができる手法です。

強連結とは、互いから互いにたどり着くためのルートが存在するノードのペアを指す用語です。SCCは、強連結である全てのノードを含んだノード群のことを指します。

つまり、グラフ内に閉路がある場合、その閉路上の任意のノードのペアは強連結になります。また、お互いが強連結なノード同士を集めたものがSCCに当たります。

そして、グラフ上のすべてのSCCをもれなく洗い出す方法が強連結成分分解です。*4簡単に説明すると、下記の手順でSCCを洗い出します。

グラフ内の探索されていない任意のノードを選択する
選択したノートからたどれるルートを深さ優先で探索し、マークを付けていく
ノードを探索中にすでに探索済みのノードを検出した場合、ノードのマークを更新してそのルートの探索を終了する
ルートをたどれるノードがなくなった場合、同じマークのついたノードをSCCとしてリストに追加する
上記1-4の手順を、探索されていないノードがなくなるまで繰り返す

By LynX - Own work, CC BY-SA 3.0, Link

SCCと閉路は異なる概念ですが、すべての閉路は何らかのSCCに含まれます。そのため、SCCをすべて抽出できれば、すべての閉路を構成するノード群を抽出できます。

また、このSCCを一つのノードとして扱うことにより、有向グラフを閉路の存在しないDAGに変換できます。

振り返りになりますが、上記のトポロジカルソートで問題になっていたのは、有向グラフに閉路が含まれているせいで、アルゴリズムがうまく機能しないことでした。

つまり、強連結成分分解を適用しDAGに変換した後の有向グラフであれば、トポロジカルソートを問題なく適用することができるのです。

配下のページ一覧の取得

ここまでくればあと一息です。下記の手順でカテゴリーリンク一覧データを変換することにより、配下のページをいつでも簡単に引き出す事ができるようになります。

カテゴリーリンク一覧データを、強連結成分分解する
カテゴリーリンク一覧データを、強連結成分分解した結果を元にDAGに変換する
変換したDAGのノードを、トポロジカルソートする
カテゴリーリンク一覧データを、トポロジカルソートの結果を元に更新する

GitHubコード内の update_categorygraph 関数を呼び出すことによりこれらの処理を実現できます。

この関数では3つのオブジェクトを出力とします。

Wikipediaに記載のカテゴリー名から、内部的に付与したカテゴリーIDに変換する category2indices オブジェクト
カテゴリーIDから、すべての配下のサブカテゴリーセットを返すように更新した categorygraph オブジェクト
カテゴリーIDから、カテゴリー配下のページセットを返す categorypages オブジェクト

categorypages オブジェクトはWikipediaに記載の情報のままです。しかし、 categorygraph オブジェクトで簡単に全てのサブカテゴリーを取得できるため、すべての配下のページに短い時間でアクセスすることができます。

def show_category_alllinks(categorypages, categorygraph, category2indices, category):
    if category in category2indices:
        index = category2indices[category]
        pages = [categorypages[index]]
        for sub_c in categorygraph[index]:
            pages.append(categorypages[sub_c])
        pages = set().union(*pages)
        print("Pages:", pages)

上記の show_category_alllinks 関数を使用し、 category に「カツラ科」と入力すると、「カツラ_(植物)」と「カツラ科」だけでなく、サブカテゴリーである「著名なカツラ」の配下のページも取得できます。

また、大量にサブカテゴリーやSCCが存在する「科学」カテゴリーでも、一瞬で配下のページすべてを取得できるようになっています。
手元のMBP環境では500msほどで処理が完了します。これは、深さ優先探索を逐一適用していた時に比べ、40分の1程度の時間です。

まとめ

この記事では、トポロジカルソートと強連結成分分解を使用することにより、Wikipediaの特定カテゴリー配下のサブカテゴリーを洗い出す方法を紹介しました。

また、洗い出したサブカテゴリー情報を使用することにより、現実的な時間でカテゴリー配下のすべてのページを洗い出す事ができることも示しました。

今回、紹介した方法は任意の有向グラフに適用することができます。巡回構造がある、入口と出口が入り組んでいるような有向グラフに出会った際はぜひ活用してみてください。

*1:カテゴリーリンクデータの最新版はこちら

*2:ページ一覧データの最新版はこちら

*3:深さ優先探索によるトポロジカルソートアルゴリズムの詳細はこちら

*4:Tarjan's algorithm による強連結成分分解の詳細はこちら