論文解説 Memory Networks (MemNN) - ディープラーニングブログ

概要

「メモリネットワーク」は代表的な記憶装置付きニューラルネットワークである．

本稿ではメモリモデル (記憶装置付きニューラルネットワーク) をいくつか概説し，論文 2 紙 (1) Memory Networks, (2) Towards AI-Complete Question Answering の理論的な記述を全文翻訳して補足説明している．

メモリモデルの概説

目次に戻る ↩︎

Memory Networks

Memory Networks (MemNN, 2014/10) は「巨大なメモリ (記憶装置)」と「メモリへの入出力などができる学習コンポーネント」から構成されるメモリ付きのニューラルネットワークである．メモリの配列に蓄えた知識への読み書きによって質問文に関連する情報 (サポート文) を連鎖的に選び出して推論に利用することで，質疑応答 (Question Answering, QA) など複雑なタスクを処理することができる．

Memory Networks [Jason Weston, last: Antoine Bordes, ICLR 2015, arXiv, 2014/10]

f:id:Ryobot:20170525175344p:plain

著者らは Memory Networks 系譜に対して，学習コンポーネントがメモリに対する注意と推論の役割を果たすことから，コンピュータの記憶装置である Random Access Memory (RAM) になぞらえて Reasoning with Attention over Memory (RAM, メモリを覆う注意付き推論) と呼んでいる．

Memory Networks では，メモリに対するハードな注意 (Hard Attention) でサポート文 (質問文に関連するメモリ) を選択する操作を複数回繰り返し，最後にそれらを統合して推論を行っている．ハードな注意とは，ベクトルの配列に対する 1-hot な重みづけで 1つのベクトルのみ出力することである．ただし，ハードな注意は微分不可能なので，なんらかの近似的な手法を使用するか，本稿のように学習データのサポート文をアノテーションして，サポート文の選択を別途に学習する必要がある．

f:id:Ryobot:20170525175239p:plain

End-To-End Memory Networks

亜種の End-To-End Memory Networks (MemN2N, 2015/03) では，サポート文の選択において微分可能な関数の組み合わせであるソフトな注意 (Soft Attention) を使用したモデルである．ソフトな注意とは，重みの和が ${1}$ になるような閉区間 ${[0,1]}$ の重みを配列の各ベクトルにかけて，それらの和を出力することである (仕組みはニューラル機械翻訳の RNNsearch と同様)．この重み (Alignment Weight Vector) がサポート文のアノテーションの役割を果たすように，それまでの行程のパラメータを学習する (実際に学習データのサポート文をアノテーションする必要がなくなる)．

このようにモデル全体を微分可能な関数のみで構成することで，損失関数の誤差のみで全パラメータを十把一からげに学習することを一気通貫学習 (End-to-End Learning) という．一気通貫学習の利点はモデルの見通しがよく，余分なアノテーションの必要がないため，より現実的なタスクに適応できることである．

MemN2N では多層化したメモリを使用することで連鎖的に複数のサポート文の参照を行っている．簡単にいうと「メモリ層への入力ベクトル ${u^k}$ (1層目は質問文のベクトル) とメモリ層からの出力ベクトル ${o^k}$ (サポート文のベクトル) を足して次の (上層の) メモリ層への入力ベクトル ${u^{k+1}}$ を生成する」という操作を層数の回数だけ繰り返している．よって，層を伝播するごとにサポート文のベクトルを足していくことになる．下図の左側のモデルは 1層の MemN2N，右側のモデルは 3層の MemN2N を表している．

End-To-End Memory Networks [Sainbayar Sukhbaatar, sec-last: Jason Weston, arXiv, 2015/03]

f:id:Ryobot:20170525175246p:plain

上図の 1層のモデルを簡単に説明しておく．

語彙数 ${V}$ としたとき，入力文ベクトル ${{x_i}}$ は ${V}$ 次元の BoW 表現のベクトルであり，複数個の入力文ベクトルを集めた配列 (Sentences) を用意する．入力文ベクトルはそれぞれ ${d \times V}$ 次元の埋め込み行列 (Embedding Matrix) A で ${d}$ 次元のメモリベクトル ${{m_i}}$ に写像し，メモリ (Input) に格納する．同様に， ${d \times V}$ 次元の埋め込み行列 C でも ${d}$ 次元のベクトル ${c_i}$ に写像し，メモリ (Output) に格納する．

次に ${V}$ 次元の質問文ベクトル ${q}$ を埋め込み行列 B で写像し，メモリ層への ${d}$ 次元の入力ベクトル ${u}$ を作る．入力ベクトル ${u}$ とメモリ (Input) 内の各メモリベクトル ${{m_i}}$ との内積をそれぞれ計算し，Softmax で正規化して重み ${p_i}$ のベクトル (いわゆる Alignment Weight Vector) を作る．

$p_i = softmax(u^T m_i)$

最後にソフトな注意を行う．重み ${p_i}$ をメモリ (Output) 内の対応する各ベクトル ${c_i}$ にかけて，それらの和を計算し，メモリ層からの出力ベクトル ${o}$ を出力する．ここで，サポート文 ${x_s}$ を写像したベクトル ${c_s}$ にかける重み ${p_s}$ だけが大きくなるように，それまでの学習パラメータ (埋め込み行列 A, B) を訓練できればよい．

$o = \sum_i p_i c_i$

Dynamic Memory Networks

別の亜種の Dynamic Memory Networks (DMN, 2015/06) では，入力文/質問文のベクトルやメモリ内部のベクトルを GRU (Gated recurrent unit) を使用してエンコードしている．

Ask Me Anything: Dynamic Memory Networks for Natural Language Processing [Ankit Kumar, last: Richard Socher, arXiv, 2015/06]

f:id:Ryobot:20170525175252p:plain

Input Module では，各入力文 ${w_1, \ldots ,w_{T_I}}$ ( ${T_I}$ 個の単語列) の単語を埋め込み行列 ${L}$ (辞書) で写像し，GRU に順に入力していき，文末の end-of-sentence トークンを入力した時の出力を入力文ベクトル ${s}$ として求める．よって， ${s}$ は入力文の数だけ得られる．

$h_t = GRU (L [w_t],h_{t-1})$

同様に GRU でエンコードした質問文をクエリ ${q}$ として，入力文ベクトル ${s}$ の配列をラップした注意 (Attention) のためのゲート ${g^i}$ (重み) を計算する．この時，スコア関数 ${G}$ は二層のフィードフォワードニューラルネットである．スコア関数への入力セット ${z(c,m,q)}$ は複雑な連結ベクトルである．

${g_t^i = G(s_t,m^{i-1},q)}$

${G(s,m,q) = \sigma \left( W^{(2)} \tanh (W^{(1)}z(s,m,q) + b^{(1)}) + b^{(2)} \right)}$

ただし ${z(s,m,q) = \left[ s,m,q, s \circ q, s \circ m, |s-q|, |s-m|, s^T W^{(b)} q, s^T W^{(b)} m \right]}$

Episodic Memory Module では，ゲート ${g^i}$ (重み) に応じて，各タイムステップ ${t}$ の GRU の出力をゲーティングしてメモリ ${e_t^i}$ を更新する．GRU の隠れ層は質問文ベクトルで初期化しておく．GRU の最後の出力 ${m^i}$ がサポート文の役割を果たすように，GRU のパラメータを学習すればよい．

${e_t^i = g_t^i GRU (s_t, e_{t-1}^i) + (1-g_t^i) e_{t-1}^i}$

${m^i = e_{T_s}^i}$

メモリは MemN2N のように階層的な構造になっており，層ごとにソフトな注意を行っている．下図では 2層のメモリを用いているが，層数はモデルに制御されている．

※ 1文の入力文か，入力文のリストかで ${T_c}$ ( ${T_s}$ に相当) の扱いが変わるらしく，入力文のリスト (上図のとおり) の場合だと，論文の式 (7), (8) が変わると思うので，ここでは訂正した式を記した．

Neural Turing Machines

他にも似たようなモデルに外部メモリをもつ Neural Turing Machines (NTM, 2014/10) や Differentiable Neural Computers (DNC, 2016/10) があるが，これらはソートやグラフ問題に焦点を当てて解法となるアルゴリズムを学習するモデルである．これらのモデルでもソフトな注意が重要な役割を果たしている．

Neural Turing Machines [Alex Graves, Greg Wayne, arXiv, 2014/10]
Hybrid computing using a neural network with dynamic external memory [Alex Graves, Greg Wayne, last: Demis Hassabis, Nature, 2016/10]

f:id:Ryobot:20170525175300p:plain

Neural Turing Machines は読み書き可能なメモリを有した LSTM (Long short-term memory) である．各タイムステップにおいて，メモリ内のすべてのベクトルに対して，ソフトな注意の重みに応じた読み取り (Reading) と書き込み (Writing) を行う．

Reading: タイムステップ ${t}$ において，ソフトな注意による重み ${\boldsymbol{w}_t}$ に応じてメモリ ${M_t}$ からベクトルを読み取り，生成した読み取りベクトル (read vector) ${\boldsymbol{r}_t}$ はタイムステップ ${t + 1}$ の LSTM に入力する．

$\boldsymbol{r}_t \leftarrow \sum_i w_t(i) M_t(i)$

Writing: タイムステップ ${t}$ の LSTM から出力した追加ベクトル (add vector) ${\boldsymbol{a}_t}$ は，ソフトな注意による重み ${\boldsymbol{w}_t}$ に応じてメモリ ${M_{t-1}}$ に書き込み，メモリ ${M_t}$ を生成する．

$M_t(i) \leftarrow w_t(i) \boldsymbol{a}_t + (1-\boldsymbol{a}_t) M_{t-1}(i)$

Attention and Augmented Recurrent Neural Networks [Distill, 2016/09]

f:id:Ryobot:20170525175225p:plain

ソフトな注意のための重み ${w_t}$ を求める手順は下図のとおり．

f:id:Ryobot:20170525175219p:plain

Content Addressing: キーベクトル (key vector) ${\boldsymbol{k}_t}$ とメモリ ${M_t}$ の内積 (ここではコサイン類似度) を計算し，softmax で正規化して，文脈ベースの重み ${\boldsymbol{w}_t^c}$ を求める． ${\beta_t}$ で内積の強弱を調整する．

$w_t^c(i) \leftarrow \frac{\exp \left( \beta_t K [\boldsymbol{k}_t, M_t(i)] \right)}{\sum_j \exp \left( \beta_t K [\boldsymbol{k}_t, M_t(j)] \right)}$

ただし， $K [\boldsymbol{u}, \boldsymbol{v}] = \frac{\boldsymbol{u} \cdot \boldsymbol{v}}{||\boldsymbol{u}|| \cdot ||\boldsymbol{v}||}$

Interpolation: ${[0,1]}$ の内挿ゲート ${g_t}$ の比率に従って，文脈ベースの重み ${\boldsymbol{w}_t^c}$ を前タイムステップの重み ${\boldsymbol{w}_{t-1}}$ で補間し，ゲート後の重み ${\boldsymbol{w}_t^g}$ を求める．

$\boldsymbol{w}_t^g \leftarrow g_t \boldsymbol{w}_t^c + (1-g_t) \boldsymbol{w}_{t-1}$

Convolutional Shift: 正規分布の畳み込みフィルタ ${\boldsymbol{s_t}}$ を平行移動してゲート後の重み ${\boldsymbol{w}_t^g}$ を畳み込み， ${\tilde{\boldsymbol{w}}_t}$ を作る．

$\tilde{w}_t (i) \leftarrow \sum_{j=0}^{N-1} w_t^g (j) s_t (i-j)$

Sharpening: スカラー ${\gamma_t \geq 1}$ でべき乗 (先鋭化) してソフトな注意の重み ${w_t}$ を求める．

$w_t (i) \leftarrow \frac{\tilde{w}_t (i)^{\gamma_t}}{\sum_j \tilde{w}_t (j)^{\gamma_t}}$

RNNsearch

RNNsearch (2014/09) はニューラル機械翻訳で用いられる Encoder-Dencoder Model にソフトな注意を取り入れたモデルである．Encoder の中間層 (hidden vector) を保持し，Decoder で出力を生成する毎に，Encoder の中間層をラップした注意によって Context Vector (文脈を考慮した単語ベクトル) を計算して Decoder の出力 (言語モデルが与える単語ベクトル) に加算/連結している．ここで，Encoder の中間層はメモリの役割を果たしている．

Neural Machine Translation by Jointly Learning to Align and Translate [Dzmitry Bahdanau, last: Yoshua Bengio, arXiv, 2014/09]

f:id:Ryobot:20170525175231p:plain

これに関しては以前に特大級な解説を書いたので，よければ参照されたい．ソフトな注意に限らず，RNN, LSTM, GRU 等の基礎的な仕組みから説明している．

以上の概説だけでも年を追うごとにメモリの構造がどんどん複雑化していることが見て取れるだろう．

Memory Networks (MemNN)

目次に戻る ↩︎

Memory Networks [Jason Weston, last: Antoine Bordes, ICLR 2015, arXiv, 2014/10]
Memory Networks for Language Understanding [Jason Weston の解説スライド]

MemNN の著者 Jason Weston 氏とはどんな方か？

Memory Networks 系譜の研究は Facebook AI Research (FAIR) の Jason Weston 氏が指揮している．同氏はニューヨークを拠点に 2003 ~ 2009年に NEC Labs America の研究者として働き，2009 ~ 2014年に Google の研究者を経て，現在は Facebook の研究職に就ている．最近では対話モデルの訓練/評価用フレームワーク ParlAI (パーレイ) の開発でも一役買っている．

f:id:Ryobot:20170525175307p:plain

1 メモリネットワークの概要

目次に戻る ↩︎

Memory Networks (MemNN) は 1つのメモリ ${{\bf m}}$ (ベクトルないし文字列 ${{\bf m}_i}$ の配列) と 4つの I, G, O, R コンポーネントから構成される．畢竟，4つのコンポーネントのパラメータを学習することになる．

I (入力特徴マップ, input feature map)
入力文字 (もしくは単語や文章) ${x}$ を BoW 等で内部特徴表現 ${I(x)}$ に変換する．
G (一般化, generalization)
新しい入力 ${I(x)}$ を使って古いメモリ ${{\bf m}_i}$ を更新する． ${{\bf m}_i = G({\bf m}_i, I(x), {\bf m}), \forall i}$
つまり将来的にメモリを利用できるようにネットワークがメモリを圧縮し一般化する．
O (出力特徴マップ, output feature map)
新しい入力 ${I(x)}$ と現在のメモリ状態 ${{\bf m}}$ を使って特徴表現空間に新しい出力特徴 ${o}$ を計算する． ${o = O(I(x), {\bf m})}$
R (応答, response)
出力特徴 ${o}$ を望ましい応答形式 ${r}$ (e.g., テキストの返答や行動) に変換する． ${r = R(o)}$

Memory Networks (MemNN) の全体像は次図のとおり．

f:id:Ryobot:20170525175344p:plain

テスト時もメモリは更新されるが，I, G, O, R コンポーネントのパラメータは更新されない．各コンポーネントには好きなモデルを使用できる (e.g., SVM, 決定木)．ちなみに I, G, O, R の名前の由来はフランケンシュタイン博士の助手イゴール (IGOR) である．

1.1 ${I}$ コンポーネント

入力 (文字や単語) からメモリへのエンコードには BoW 等のどんな前処理を使ってもよい．また特徴表現は密ベクトルでも疎ベクトルでもよい．

1.2 ${G}$ コンポーネント

簡易には ${I(x)}$ をメモリの「スロット」に格納すればよい．これは次式によって表される．

${{\bf m}_{H(x)} = I(x)}$

ここで ${H(\cdot)}$ はスロットを選択する関数である． ${G}$ はインデックス ${H(x)}$ の ${{\bf m}}$ を更新するが，メモリの他の部分はそのまま残す．

更に洗練された ${G}$ は現在の入力 ${x}$ に基づいて，以前に保存されたメモリを復元することができる．

メモリが巨大な場合 (e.g., Freebase, Wikipedia)，メモリを整理する必要がある．例えば ${H}$ を拡張し，入力をトピック毎のバケットにハッシュすることで， ${G}$ (及び ${O}$ ) はすべてのメモリに対して動作する必要はなく，検索された候補のバケット (正しいトピックのメモリ) でのみ動作すればよい．

メモリが飽和状態であれば最も役に立たないものを取り除く (忘却する) 必要がある．これには ${H}$ が各メモリの有用性を評価しなければならない．

1.3 ${O}$ と ${R}$ コンポーネント

${O}$ はメモリから読み取り推論を行う．例えば，良い応答を行うために関連するメモリが何かを計算する．

${R}$ には多クラス分類器や RNN を使用し， ${O}$ の出力素子 ${o}$ を入力して最終的な答え (文字や単語) を出力する．つまり，辞書内のすべての単語をランキングして最良の一単語を返す．

2 基本モデル

目次に戻る ↩︎

メモリネットワークの具体的な実装は，各コンポーネントにニューラルネットワーク (簡易には埋め込みモデル) を使用する．これを Memory Neural Networks (MemNN) という．

2.1 テキスト処理のためのメモリネットワーク実装

${I}$ モジュールは単語ベースの入力文を受け取る．つまり，入力文は事実 (fact, e.g., “John picked up the football”) の文か，質問 (question, e.g., “Where is the football ?”) の文のいずれかである．入力文はそのまま次の利用可能なメモリスロットに格納する．つまり， ${S(x)}$ は次の空きメモリスロット ${N}$ を返す．

${{\bf m}_N = x}$ ， ${N = N + 1}$

${G}$ モジュールはこの新しいメモリを格納するだけで古いメモリは更新しない．

技術的には BoW 等の埋め込みモデルを用いて入力文を埋め込みベクトルに変換してメモリに格納できる．しかし，学習時は埋め込みモデルのパラメータが変化してメモリの埋め込みベクトルが古くなる問題がある．テスト時は埋め込みモデルのパラメータが変化しないので埋め込みベクトルとして格納でき，元の単語を読み込んで繰り返し埋め込むよりも高速である．

${O}$ と ${R}$ モジュールは推論を行う．

${O}$ モジュールは ${x}$ を使ってサポートメモリ (supporting memory, 質問に答えるのに役立つ事実) を ${k}$ 個見つけ，出力特徴 ${o}$ を生成する．ここでは ${k}$ を ${2}$ まで使用する (つまり， ${2}$ 回すべてのメモリをループする) が，更に大きな ${k}$ でもよい．第1ホップ ( ${k = 1}$ ) では，次式によって第1のサポートメモリを見つける．ホップ (hop) はループと同義である．

$\begin{equation} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\argmax}{arg\,max} \displaystyle o_1 = O_1(x, {\bf m}) = \argmax_{i = 1, \ldots, N} s_O(x, {\bf m}_i) \end{equation}$

ここで ${s_O}$ は ${x}$ と ${{\bf m}_i}$ のマッチ率を評価するマッチ関数である．第2ホップ ( ${k = 2}$ ) では，前のホップで見つけたマッチを使って第2のサポートメモリを見つける．

$\begin{equation} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\argmax}{arg\,max} \displaystyle o_2 = O_2(x, {\bf m}) = \argmax_{i = 1, \ldots, N} s_O([x, {\bf m}_{o_1}], {\bf m}_i) \end{equation}$

ここで角括弧はリストを表す．つまり第2のサポートメモリ ${{\bf m}_i}$ は，元の入力 ${x}$ と第1のサポートメモリ ${{\bf m}_{o_1}}$ の双方に関してマッチ率のスコアが付けられる．ここでは 1つの Bag of Words モデルを使用するが， ${x}$ と ${{\bf m}_{o_1}}$ は 2つの異なる辞書による Bag で特徴表現されるので (詳細は後述)，次式のような和として表される．

${s_O([x, {\bf m}_{o_1}], {\bf m}_i) = s_O(x, {\bf m}_i) + s_O({\bf m}_{o_1}, {\bf m}_i)}$

とはいえ，入力の更に高度なモデリング (e.g., 非線形変換) は和でなくてもよい．

最終的な出力 ${o}$ は ${[x, {\bf m}_{o_1}, {\bf m}_{o_2}]}$ となり， ${R}$ モジュールに入力される．

${R}$ モジュールはテキストの返答 ${r}$ を生成する．簡易には得られた事実 ${{\bf m}_{o_k}}$ をそのまま返せばよい．代わりに RNN を用いると文章を生成できる．実験ではモデルに見られるすべての単語を次式によってランキングして一単語だけ返す手法を評価する．

$\begin{equation} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\argmax}{arg\,max} \displaystyle r = \argmax_{w \in W} s_R([x, {\bf m}_{o_1}, {\bf m}_{o_2}], w) \end{equation}$

ここで ${W}$ は辞書内のすべての単語の集合であり， ${s_R}$ はマッチ率を評価するマッチ関数である．

具体例として Figure 1 のようなシミュレーターによって生成された簡単な「物語」陳述の QA を挙げる．

“Where is the milk now?” という質問に答えるには，“picked up” と “left” という動作への理解が必要となる．また “where was Joe before the office?” という質問に答えるには，物語の時間要素への理解が必要となる．

Figure 1

Joe went to the kitchen. Fred went to the kitchen. Joe picked up the milk.
Joe travelled to the office. Joe left the milk. Joe went to the bathroom.
Where is the milk now? A: office
Where is Joe? A: bathroom
Where was Joe before the office? A: kitchen

${x =}$ “Where is the milk now?” というに答えるために， ${O}$ モジュールは第1ホップにて，すべてのメモリ (入力したすべての事実) と ${x}$ とのマッチ率のスコアを付けて， ${{\bf m}_{o_1} =}$ “Joe left the milk” という最も関連性の高い事実 (サポートメモリ) を見つける．次の第2ホップにて， ${[x, {\bf m}_{o_1}]}$ を使って ${{\bf m}_{o_2} =}$ “Joe travelled to the office” (つまり，Joe が牛乳を落とす前に行った最後の場所) という関連性の高い事実を見つける．

最後に， ${R}$ モジュールは ${[x, {\bf m}_{o_1}, {\bf m}_{o_2}]}$ を使って辞書内のすべての単語にスコアを付けて ${r =}$ “office” を出力する．

実験ではマッチ関数 (matching function) ${s_O}$ と ${s_R}$ はどちらも次式のような埋め込みモデル (embedding model) である．

$s(x, y) = \Phi_x (x)^T U^T U \Phi_y (y)$

ここで ${U}$ は単語の辞書であり， ${D}$ を特徴表現数， ${n}$ を埋め込み次元数とすると ${n \times D}$ 行列で表される．

${\Phi_x}$ と ${\Phi_y}$ は元の文章を ${D}$ 次元の特徴空間に写像する関数である．最も簡易な特徴空間は，Bag of Words 表現である．

${s_O}$ は ${D = 3 | W |}$ とする．ただし， ${W}$ は辞書内のすべての単語の集合なので ${|W|}$ は語彙数である．これは辞書内のすべての単語が 3つの異なる特徴表現を有することを意図する． ${\Phi}$ への入力引数の単語群が「入力由来」であるか「第1ホップ由来」であるか「第2ホップ由来」であるかに応じて，1つは ${\Phi_y (\cdots)}$ のために特徴表現され，2つは ${\Phi_x (\cdots)}$ のために特徴表現されるので 3つの異なる辞書をモデル化ができる．

埋め込みモデルは次図のとおり．

f:id:Ryobot:20170525175432p:plain

ちなみに，1つの辞書と線形埋め込みのみを使用した実験ではパフォーマンスの低下が見られた．1つの辞書のみでモデル化するには，文脈に応じて単語を変換できる更に深いネットワークが必要となる．

同様に， ${s_R}$ も ${D = 3 | W |}$ とする．

また ${s_O}$ と ${s_R}$ では異なる重み行列 ${U_O}$ と ${U_R}$ を使用する．

2.2 訓練

訓練は入力 (事実と質問) と応答のデータセットを用いた教師あり学習を行う．訓練データはサポート文 (supporting sentence) にそれがサポートメモリに相当するというラベルを付加するが，テストデータはラベルを付加しない．訓練中は ${O_1(x, {\bf m}), \, O_2(x, {\bf m})}$ の最良の選択がわかっているが，この情報は RNN や LSTM で簡単に使用できないことに留意されたい．

訓練はマージンランキング損失 (margin ranking loss) と確率的勾配降下法 (SGD) によって行われる．具体的には，真の応答 ${r}$ ，サポート文 ${{\bf m}_{o_1}}$ と ${{\bf m}_{o_2}}$ (ただし ${k = 2}$ )，質問 ${x}$ を使ってモデルパラメータ ${U_O}$ と ${U_R}$ を学習して次式の目的関数を最小化する．

$\displaystyle \sum_{\bar{f} \neq {\bf m}_{o_1}} \max (0, \gamma - s_O(x, {\bf m}_{o_1}) + s_O(x, \bar{f})) + \\ \\ \displaystyle \sum_{\bar{f}' \neq {\bf m}_{o_2}} \max (0, \gamma - s_O([x, {\bf m}_{o_1}], {\bf m}_{o_2}) + s_O([x, {\bf m}_{o_1}], \bar{f}')) + \\ \\ \displaystyle \sum_{\bar{r} \neq r} \max (0, \gamma - s_R([x, {\bf m}_{o_1}, {\bf m}_{o_2}], r) + s_R([x, {\bf m}_{o_1}, {\bf m}_{o_2}], \bar{r}))$

ここで $\bar{f}, \, \bar{f}', \, \bar{r}$ は正解ラベル以外のすべての選択肢であり，$\gamma$ はマージンである．正解の組のマッチ関数を最大化し，不正解の組のマッチ関数を最小化すれば目的関数が最小化されるのがわかる．Weston et al. (2011) に追随して，SGD の各ステップの $\bar{f}, \, \bar{f}', \, \bar{r}$ は各訓練データの総和を計算せずサンプリングする．

WSABIE: Scaling Up To Large Vocabulary Image Annotation [Jason Weston, AAAI, 2011]

MemNN の ${R}$ コンポーネントに RNN を使用する場合，上式の第3項を言語モデルに使用される対数尤度関数に置き換える．訓練時は RNN に文 ${[x, {\bf m}_{o_1}, {\bf m}_{o_2}, r]}$ を与え，テスト時は文 ${[x, {\bf m}_{o_1}, {\bf m}_{o_2}]}$ を使って予測値 ${r}$ を出力する．

対照的に最も簡易なモデルは ${k = 1}$ を使用し，応答 ${r}$ としてサポートメモリ ${{\bf m}_{o_1}}$ の位置を出力し，上式の第1項のみ使用して訓練する．

3 拡張モデル

目次に戻る ↩︎

3.1 単語列の入力

入力が文単位ではなく単語単位の場合，つまり RNN 等で為されるように 1つの入力ストリームから単語列を受け取り，まだ事実と質問のような文に区切られていない場合，2.1 節のアプローチを修正しなければならない．

まだ区切られていない最後の単語列を入力として受け取り，文章の区切り目を探す関数セグメンタ (segmenter) を追加し学習する．現在の単語列が 1つの文になったときセグメンタが起動し，その単語列をメモリに書き込み，2.1 節と同様に扱える．セグメンタは他のコンポーネントと同様に次式のような埋め込みモデルとして表される．

$\displaystyle seg(c) = W_{seg}^T U_S \Phi_{seg} (c)$

ここでベクトル $W_{seg}$ は埋め込み空間での線形分類器のパラメータであり，$c$ は別の辞書による BoW 表現の入力単語列である．$seg(c) > \gamma$ ($\gamma$ はマージン) のとき，単語列を1つの文として認識する．このように MemNN は書き込み操作に学習コンポーネントを有する．

訓練データの各質問に対して回答と入力ストリームからのサポート文が明示されているので，セグメンタもそれを教師データとして使用できる．

例えば “Where is Bill?” という質問に対してセグメンタは “Bill is in the Kitchen” のような既知のサポート文で起動したいが，“Bill is in the” のような中途半端な区切り文で起動したくない．これは次式のような目的関数の最小化として表すことができる．

$\sum_{f \in F} \max (0, \gamma - seg(f)) + \sum_{\bar{f} \in \bar{F}} \max (0, \gamma + seg(\bar{f}))$

ここで ${F}$ はラベリングされた訓練データのすべての既知のサポート文， ${\bar{F}}$ は訓練データのそれ以外の中途半端な区切り文である．

3.2 ハッシュによる効率的なメモリ

格納されたメモリが巨大な場合， ${O_1(x, {\bf m}), \, O_2(x, {\bf m})}$ のようにすべてのスコアを計算するのはコストが大きい．検索 (lookup) を高速化するためにハッシュトリック (hashing trick) を考える．入力 ${I(x)}$ を複数のバケットにハッシュし，同じバケットにあるメモリ ${{\bf m}_i}$ のみスコアを計算する．

ハッシュの方法には 2つある．

(i) ハッシュ単語 (hashing words) 経由のハッシュ
(ii) 埋め込み単語 (word embeddings) のクラスタリング経由のハッシュ

(i) 辞書にある単語と同数のバケットを用意し，入力文に含まれる単語に対応するすべてのバケットに対して入力文をハッシュ (格納) する．ただし，入力 ${I(x)}$ と少なくとも 1単語を共有するメモリ ${{\bf m}_i}$ しか考慮されないという問題がある．

(ii) 埋め込み行列 ${U_O}$ の訓練後，単語ベクトル ${(U_O)_i}$ をクラスタリングするK平均法 (K-means) を行い，K 個のバケットに対応させる．入力文を個々の単語に対応するすべてのバケットにハッシュ (格納) する．つまり同義語に近しい単語ベクトルを同じクラスタに分類し，近しいメモリのみスコアを計算する．速度と精度のトレードオフは K の取り方に依存する．

3.3 書き込みタイミングのモデル化

メモリスロットへの書き込みタイミングを考慮するモデルに拡張できる．

書き込みタイミングは “What is the capital of France?” のような既成事実に関する質問に答えるとき重要でないが，Figure 1 のような物語に関する質問に答えるとき重要である．MemNN は各メモリが書き込まれたタイミングを知っているので物語や対話を構成する文の順序を考慮できる．

書き込みタイミングは，文の時制 (e.g., 現在形や過去形) や時間表現 (e.g., 昨日〜した) とは異なることに留意されたい．これらは書き込みタイミング特徴を使わずテキストから直接モデル化できる．

メモリスロットへの上書きがなくメモリのインデックス ${j}$ が書き込みタイミングに従っている (つまり， ${j}$ が大きいほど書き込みが新しい) と仮定すると，明白な実装方法の 1つは，インデックス ${j}$ のメモリ ${{\bf m}_j}$ をエンコードする関数 ${\Phi_x, \, \Phi_y}$ に時間要素として新しい特徴を追加することである．2.1 節のマッチ関数 ${s_O}$ のように候補ペアを評価する関数の代わりに，次式 ${s_{O_t}(x, y, y')}$ のように 3つの引数 (triples) で評価する関数を学習する．

$s_{O_t}(x, y, y') = \Phi_x (x)^T U_{O_t}^T U_{O_t} \Bigl( \Phi_y (y) - \Phi_y (y') + \Phi_t (x, y, y') \Bigr)$

ここで ${\Phi_t (x, y, y')}$ は書き込みタイミングによって ${0}$ または ${1}$ の値をとる 3つの書き込みタイミング特徴 (write time features, 3つの ${1}$ 次元ベクトル) の連結 (concat) である．各特徴が ${0}$ になる場合は，第1特徴は ${x}$ が ${y}$ より古いとき，第2特徴は ${x}$ が ${y'}$ より古いとき，第3特徴は ${y}$ が ${y'}$ より古いときである．

従って，すべての ${\Phi}$ の埋め込み次元数を ${3}$ 次元拡張し，使用しない次元は ${0}$ で埋める．

書き込みタイミングを考慮した埋め込みモデルは次図のとおり．

f:id:Ryobot:20170525175438p:plain

ここでモデル $O_t$ は $O_1(x, {\bf m}), \, O_2(x, {\bf m})$ の ${\rm argmax}$ と同様，メモリ $i = 1, \ldots, N$ をループするアルゴリズムである．ただし $s_{O_t}(x, y, y') > 0$ のときモデルは $y'$ を $y$ で置き換えて第3引数を保持し，$s_{O_t}(x, y, y') < 0$ のときモデルは第3引数 $y'$ をそのまま保持する．つまり各ステップの勝利メモリ ($y$ または $y'$) を第3引数として保持して，現在の勝利メモリと次のメモリ ${\bf m}_i$ を常時比較する．

よってモデル ${O_t}$ は以下のような Algorithm 1 で定義される．推論時， ${k = 2}$ モデルの ${O_1(x, {\bf m}), \, O_2(x, {\bf m})}$ の ${{\rm argmax}}$ 関数は ${o_1 = O_t(x, {\bf m}), \, o_2 = O_t([x, {\bf m}_{o_1}], {\bf m})}$ に置き換えられる．

Algorithm 1: 書き込みタイミング特徴を使用した ${O_t}$ による ${{\rm argmax}}$ の置き換え

function ${O_t (q, {\bf m})}$
　　 ${t \leftarrow 1}$
　　for ${i = 2, \ldots, N}$ do
　　　　if ${s_{O_t} (q, {\bf m}_i, {\bf m}_t) > 0}$ then
　　　　　　 ${t \leftarrow i}$
　　　　end if
　　end for
　　return ${t}$
end function

前述のとおり， ${\Phi_t (x, y, y')}$ は， ${x}$ が ${y}$ より古いか， ${x}$ が ${y'}$ より古いか， ${y}$ が ${y'}$ より古いかによって ${0}$ または ${1}$ の値をとる 3つの書き込みタイミング特徴を使用する．

例えば ${O_t([x, {\bf m}_{o_1}], {\bf m})}$ を計算して第2のサポートメモリを見つけるときには，第1のサポートメモリ ${{\bf m}_{o_1}}$ の書き込みタイミングとの相対時間を得るために， ${{\bf m}_{o_1}}$ が ${y}$ より古いか， ${{\bf m}_{o_1}}$ が ${y'}$ より古いか， ${y}$ が ${y'}$ より古いかをエンコードする．ただし ${O_t(x, {\bf m})}$ を計算して第1のサポートメモリを見つけるときには， ${x}$ はメモリの最後の書き込みなので ${y, \, y'}$ は常に ${x}$ より古い書き込みである．つまり最初の 2つの書き込みタイミング特徴は不要であることに留意されたい．

3.4 書き込みタイミング特徴の訓練

書き込みタイミング特徴を使用したモデルを訓練するには，2.2 節の目的関数のヒンジ損失を Algorithm 1 の損失に置き換えて，次式の目的関数を最小化する．

$\displaystyle \sum_{\bar{f} \neq {\bf m}_{o_1}} \max (0, \gamma - s_{O_t}(x, {\bf m}_{o_1}, \bar{f})) + \sum_{\bar{f} \neq {\bf m}_{o_1}} \max (0, \gamma + s_{O_t}(x, \bar{f}, {\bf m}_{o_1})) + \\ \\ \displaystyle \sum_{\bar{f}' \neq {\bf m}_{o_2}} \max (0, \gamma - s_{O_t}([x, {\bf m}_{o_1}], {\bf m}_{o_2}, \bar{f}') + \sum_{\bar{f}' \neq {\bf m}_{o_2}} \max (0, \gamma + s_{O_t}([x, {\bf m}_{o_1}], \bar{f}', {\bf m}_{o_2}) + \\ \\ \displaystyle \sum_{\bar{r} \neq r} \max (0, \gamma - s_R([x, {\bf m}_{o_1}, {\bf m}_{o_2}], r) + s_R([x, {\bf m}_{o_1}, {\bf m}_{o_2}], \bar{r}))$

第5項は 2.2 節の目的関数の第3項と同じで，応答 ${r}$ を返すためのマージンランキング損失である．2.2 節と同じく，更に洗練されたモデルとして RNN に置き換えることができる．第1-4項は 2.2 節の目的関数の第1-2項を置き換えている．

2.2 節同様，SGD の各ステップの $\bar{f}, \, \bar{f}', \, \bar{r}$ は，各訓練データの総和を計算せずサンプリングする．

3.5 未知語のモデル化

テキストをたくさん読む人はよく未知語 (新しい単語) に遭遇することだろう．機械学習では言語モデルを使用して未知語に対処できる．つまり，近隣の単語から未知語の意味を推測し，未知語は推測された意味に似ていると仮定する．この未知語への対処は別のステップとして導入するのではなくネットワーク ${s_O, \, s_R}$ に組み込むことができる．

具体的には，出現した各単語ごとに共起した単語の Bag of Words を格納する．ただし 1つの Bag は左側の文脈 (左側にある単語) を格納し，もう 1つの Bag は右側の文脈を格納する．未知語はこれらの特徴によって表現できる．よって 2.1 節の特徴表現数 ${D}$ を ${3 | W |}$ から ${5 | W |}$ (ただし ${| W |}$ は語彙数 = 各 Bag の特徴数) に増やし，追加した ${2 | W |}$ で左右の文脈をモデル化する．

未知語の対処するためにドロップアウト (dropout, 隠れユニットを無視する手法とは異なる) を使用して訓練する．つまり ${d}$ % の時間，ある単語を以前に出現しなかった未知語として扱い，その単語は ${n}$ 次元の埋め込みベクトルを持たず，代わりに文脈から表現するようにする．

3.6 正確な単語の一致

例えば “Where is the football ?” という質問と “John picked up the football” というメモリから the や football という正確な単語の一致を評価したい．埋め込みモデルは次元数 ${n}$ が低いために正確な単語の一致に使用できない．

1つの解決策は代替として，候補ペア ${x, \, y}$ のスコアを次式のマッチ関数を使用して計算することである．つまり，混合パラメータ ${\lambda}$ の比率で学習した埋め込みモデルのスコアに Bag of Words の一致スコアを追加する．

$s(x, y) = \Phi_x (x)^T U^T U \Phi_y (y) + \lambda \Phi_x (x)^T \Phi_y (y)$

別の関連手法として， ${n}$ 次元の埋め込み空間を保ちつつ，特徴表現数 ${D}$ を 1語につき 1次元の一致特徴 (matching feature) 数に拡張する．一致特徴はある単語が ${x}$ と ${y}$ の両方に出現するかを表す．つまり， ${y}$ 内の単語の幾つかが ${x}$ 内の単語と一致する場合，一致した単語に対応する一致特徴の次元に ${1}$ を設定するような ( ${x}$ に条件付けされた) ${\Phi_y (y, x)}$ を用いて ${\Phi_x (x)^T U^T U \Phi_y (y, x)}$ のスコアを計算する．未知語は文脈の単語の一致特徴を使用して同様にモデル化できる．

4 実験

目次に戻る ↩︎

4.1 大規模な QA

ここでは Fader et al. (2013) の QA データセットを使用して実験を行う．これは 1400万個の (主語, 関係性, 目的語) の 3要素の陳述から成り，すべて Bag of Words 表現として MemNN のメモリに格納される．3要素の具体例は (milne, authored, winnie-the-pooh) や (sheep, be-afraid-of, wolf) 等である．3要素は ClueWeb09 コーパス (2009年に収集された 10億の Webページから構成されるデータセット) から多様なトピックをカバーした REVERB 抽出によって作成されている．

Fader et al. (2013) と Bordes et al. (2014b) に追随して「質問と関連する 3要素から成る擬似ラベルの QA ペア」と「“Who wrote the Winnie the Pooh books?” や “Who is poohs creator?” のような WikiAnswers の質問を言い換えた 3500万ペアの質問」の組み合わせで訓練する．

Paraphrase-driven learning for open question answering [Anthony Fader, ACL, 2013]
Open Question Answering with Weakly Supervised Embedding Models [Antoine Bordes, sec: Jason Weston, arXiv, 2014/04]

ここでは Bordes et al. (2014b) に追随して，テストデータで F1 スコアを計測する幾つかのシステムによって，上位に返された候補の回答を再ランキングする枠組みで実験を行った．これらの解答は人間によって正しいか間違っているかアノテーションされているが，テスト時はラベルが与えられないので解答は無視される． ${k = 1}$ のサポートメモリの MemNN を使用して Bordes et al. (2014b) と同様のアプローチを行った (ただし埋め込み次元は ${128}$ 以上，Fine Tuning なし)．また 3.6 節で述べた Bag of Words 表現の一致スコアを追加した．書き込みタイミングと未知語のモデル化は使用しなかった．

結果は Table 1 のとおり．大規模な QA において MemNN は実用的なパフォーマンスに達することが窺える．

f:id:Ryobot:20170525175332p:plain

しかし，検索 (look up) はメモリサイズに対して線形の速度なので，1400 万個の陳述は遅い．そこで 3.2 節のメモリのハッシュトリックを「ハッシュ単語経由のハッシュ」と「埋め込み単語のクラスタリング経由のハッシュ」の両方を使用して実装した．後者のクラスタは ${K = 1000}$ とした．

結果は Table 2 のとおり．「埋め込み単語のクラスタリング経由のハッシュ」を使用して同様のパフォーマンスを維持しながら大幅な高速化 (約 80倍) を達成することが窺える．一方，「ハッシュ単語経由のハッシュ」は更に高速であるが，単語を共有しない回答はまったくマッチしないのでパフォーマンスが低下する．

f:id:Ryobot:20170525175339p:plain

4.2 シミュレーション世界の QA

Bordes et al. (2010) のアプローチと同様に 4人物，3物体，5部屋の簡単なシミュレーションを作成した．このシミュレーションでは人物が移動して物体を拾ったり落としたりする．人物の行動は自動化された簡易な文法に従ってテキストに転記され，ラベル付きの質問も同様の方法で生成される．これは Figure 1 のような簡単な「物語」の QA タスクとして表される．物体がどこにあるのか尋ねるとき，複数の事実を使用して推論する必要があるほどタスクは難しいといえる．

Towards understanding situated natural language [Antoine Bordes, last: Jason Weston, AISTATS, 2010]

ここでは訓練用にシミュレーターから 7000文の事実と 3000文の質問を生成し，テスト用と RNN や LSTM との比較用に固有の番号を生成した．3.1 節のように単語列を入力としてテストする場合，Figure 2 のように複数の事実を含む可能性がある文を生成するために簡易な文法で事実を再結合する．

Figure 2: 単語列の入力と文の回答．回答文を生成するために MemNN の ${R}$ コンポーネントに LSTM を使用する．

Joe went to the garden then Fred picked up the milk; Joe moved to the bathroom and Fred dropped the milk, and then Dan moved to the living room.
Where is Dan? A: living room I believe
Where is Joe? A: the bathroom
Fred moved to the bedroom and Joe went to the kitchen then Joe took the milk there and Dan journeyed to the bedroom; Joe discarded the milk.
Where is the milk now ? A: the milk is in the kitchen
Where is Dan now? A: I think he is in the bedroom
Joe took the milk there, after that Mike travelled to the office, then Joe went to the living room, next Dan went back to the kitchen and Joe travelled to the office.
Where is Joe now? A: I think Joe is in the office

また訓練の質問データの数を変えた場合の ${k = 2}$ で書き込みタイミングを考慮した MemNN のテスト精度の結果は Table 4 のとおり．

f:id:Ryobot:20170525175419p:plain

質問で尋ねられた事柄について過去に言及した最後の事実までのタイムステップの数を制限する設定によってタスクの難易度を制御できる．

ここでは限界 ${1}$ と ${5}$ を使用して 2つの実験を試みる．たとえば限界 ${5}$ の場合，直近の過去の ${1}$ 〜 ${5}$ タイムステップ間の文からランダムに 1文を選ぶ．もし選択した文が “Bill is in the kitchen” のように人物にだけ言及していれば，“where is Bill?” や “where was Bill before the kitchen?” のような質問を生成する．もし選択した文が “Bill dropped the football” のように物体に言及していれば，“where is the football?” のような質問を生成する．物体の場合は，推論に必要なサポート文が最後の 5文に含まれない可能性があることに留意されたい．

回答方法は (i) “kitchen” のような一単語の回答 (ii) “He is in the kitchen I believe” のような文形式の回答を生成する簡易な文法の 2種類がある．また，(i) イージー: 人物についてのみ質問 (ii) ハード: 人物と物体について質問を尋ねる 2種類の実験も実施した．

ベースラインの RNN と LSTM では正解単語のところのみ Backpropagation Through Time (BPTT) を使用した言語モデルを実施した．ちなみに同様の質問で一般的な言語モデルを使用した場合は，やや悪い結果となった．各データセットに対して隠れ層のサイズ，BPTT のステップ数，学習率のようなハイパパラメータの最適化を行った．

MemNN はすべての実験で埋め込み次元を ${100}$ ，学習率を ${0.01}$ ，マージン ${\gamma}$ を ${0.1}$ ，epoch 数を ${10}$ に固定して訓練した．

一単語だけ回答する (i) の結果は Table 3 のとおり．“w/o before” は without before の略で，before を使用しない質問を表している．RNN は長期記憶を符号化できず性能が悪く，LSTM は更に洗練されたメモリモデルなので RNN より優れているが遠い過去の文を記憶するのは難しい．

f:id:Ryobot:20170525175406p:plain

MemNN は before 付きの質問や限界 ${> 1}$ の難易度で良い性能を発揮するために書き込みタイミング (“+time” で表記) を考慮する必要がある．さもなくば ${s_O}$ は人物の居場所に関する質問に対して移動後の場所に関する事実を選ぶ可能性がある．

また人物と物体に関する質問 (actor+object) の結果では ${k = 2}$ を使用した MemNN は二段階推論を正常に実行できるが， ${k = 1}$ を使用した MemNN や RNN, LSTM は推論に失敗する．

ちなみに単語列の入力ではなく文レベルの入力で同様の実験を試みた結果は Table 5 のとおり．文レベルの入力では MemNN への入力は単語ストリームではなく，あらかじめ陳述文と質問文に区切られたデータとなる．

f:id:Ryobot:20170525175400p:plain

また文形式で回答する (ii) でも MemNN は RNN, LSTM より優れた結果を得られた．テスト時のモデルの出力例は Figure 2 のとおり．

シミュレーション世界の QA における文形式の回答のテスト精度は Table 6 のとおり．従来の RNN, LSTM と ${R}$ モジュールに RNN ないし LSTM を使用した MemNN とを比較している (MemNN は ${I, \, G, \, O}$ モジュールの実行後， ${R}$ に特徴 ${[x, {\bf m}_{o_1}, {\bf m}_{o_2}]}$ を与える)．

f:id:Ryobot:20170525175355p:plain

ベースラインの RNN, LSTM には事実と質問を含む単語ストリームを入力し，MemNN の RNN, LSTM には ${O}$ モジュールの出力を入力した．ここでは ${k = 2}$ を使用した MemNN にて難易度 ${5}$ ，人物と物体に関する質問 (actor+object) の条件で実験を行った．

テストデータに対して文生成と次のような評価を行う．たとえば “Where is Bill?” という質問に対して，正しい回答は正しい場所と必要に応じて正しい主語や代名詞を含むので “Kitchen”, “In the kitchen”, “Bill is in the kitchen”, “He is in the kitchen”, “He is in the kitchen”, “I think Bill is in the kitchen” は正解である．一方，間違った回答は間違った場所や主語を含むので “Joe is in the kitchen”, “It is in the kitchen”, “Bill is in the bathroom I believe” は不正解である．

結果の Table 6 の数値は正解の文生成の割合である．

4.3 未知語付きの QA

3.5 節の未知語のモデル化を使用してテスト時の未知語を処理する MemNN の性能を評価する．

名詞が未知語であることを除いて 4.2 節と同様の方法で生成されたシミュレーションデータセットを使用して MemNN を訓練し，Figure 3 のような物語の問題でテストした．その結果，「ロード・オブ・ザ・リング」に登場する Bilbo, Frodo, Sauron 等の特定の単語が未知であるにも関わらず，MemNN は質問に正しく回答できた．

MemNN は (X, dropped, Y), (X, took, Y), (X, journeyed to, Y) のような簡易な言語パターンを発見し，未知語を使用して具体的な意味を一般化し，二段階推論を実行できる．3.5 節の未知語のモデル化がなければ，これは完全に失敗する．

Figure 3

Bilbo travelled to the cave. Gollum dropped the ring there. Bilbo took the ring.
Bilbo went back to the Shire. Bilbo left the ring there. Frodo got the ring.
Frodo journeyed to Mount-Doom. Frodo dropped the ring there. Sauron died.
Frodo went back to the Shire. Bilbo travelled to the Grey-havens. The End.
Where is the ring? A: Mount-Doom
Where is Bilbo now? A: Grey-havens
Where is Frodo now? A: Shire

4.4 シミュレーション世界の QA と大規模な QA の組み合わせ

設計したモデルの一般性を証明するために，4.1 節の大規模な QA で訓練したモデルと4.2 節のシミュレーション世界の QA で訓練したモデルのアンサンブルを実装した．両モデルに入力を与え，各質問に対して最高スコアの選択肢の応答を出力する．

この 2 つの MemNN を組み合わせたシステムは，一般的な知識に関する質問と以前の対話に関連した特定の事実に関する質問の両方に回答できるので，Figure 4 のように簡易な対話を実行できる．幾つかの回答は正しいが，他は無意味である．

今後の課題は 1 つのモデルでマルチタスク対応することである．

Figure 4

Fred went to the kitchen. Fred picked up the milk. Fred travelled to the office.
Where is the milk? A: office
Where does milk come from? A: milk come from cow
What is a cow a type of? A: cow be female of cattle
Where are cattle found? A: cattle farm become widespread in brazil
What does milk taste like? A: milk taste like milk
What does milk go well with? A: milk go with coffee
Where was Fred before the office? A: kitchen

りょぼっとの与太話

これらの実験から著者らの意図を汲み取ると Memory Networks は人間の脳でいうところの宣言的記憶 (Declarative Memory) に相当するモデルに思われる．

宣言的記憶とは記憶のモデルの中でも「長期記憶のうち言葉で表現できる記憶」を表している．宣言的記憶は更に「個人的な体験やイベントを記憶するエピソード記憶 (Episodic Memory)」と「一般的な常識や事実を記憶する意味記憶 (Semantic Memory)」に細分される．

著者らは実験で「シミュレーション世界の QA」と「大規模な QA」を同時に処理することを実証しているので，(内部の構造はともかく) 機能的には宣言的記憶を志向していると考えられる．

f:id:Ryobot:20170525175349p:plain

ちなみに YerevaNN の Dynamic Memory Networks (DMN) の実装では，より宣言的記憶を意識してエピソード記憶モジュールと意味記憶モジュールを備えた構造をしている．外部メモリから質問に関連する意味記憶を選択し，入力文に追加している．

f:id:Ryobot:20170525175328p:plain

人間の脳では宣言的記憶は大脳皮質の神経細胞群のコネクション (シナプス可塑性 = ニューラルネットでいう重み) を学習することで大域的に記憶を貯蔵していると云われる．しかし，大脳皮質では宣言的記憶なるものをエピソード記憶と意味記憶に領域的に分轄して貯蔵しているわけではないだろう [要出典]．つまり，人間が解釈しやすいように便宜的に分類しているだけかと．個々しか持たない記憶は「エピソード記憶」と呼び，個々がもつエピソード記憶がある集団内で一定数観測されれば「共通認識」と呼ばれ，それが全人類規模で観測されれば「常識」，つまり意味記憶と呼ばれるものに分類されるわけである．畢竟，エピソード記憶と意味記憶の違いとは，ある記憶の社会的な普遍性の違いというのが私の了解である．

Towards AI-Complete Question Answering (bAbI task)

目次に戻る ↩︎

ベイビータスク (bAbI task) は人工知能の言語理解を測るための QA データセットである．本旨は bAbI task の紹介であるが，筆者らは Memory Networks の拡張も提案している．

bAbI [Facebook AI Research]
Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks [Jason Weston, sec: Antoine Bordes, last: Tomas Mikolov, arXiv, 2015/02]

1 bAbI タスク

目次に戻る ↩︎

bAbI タスクは 20種の問題形式で構成されたトイタスクのデータセットである．

各タスクは人工知能の能力の一面を測るためにできるだけ他のタスクから独力している．各タスクは訓練データとテストデータが用意され，訓練データには教師信号として質問の解答と質問の回答に必要なサポート事実のセットが含まれる．タスクの回答形式は一単語ないし単語のリストに限定している．

すべてのタスクはノイズがなく人間が解けば精度 100% になるような単純で自然な問題で構成されている (意味論，機械学習，知識表現を必要としない)．

f:id:Ryobot:20170525175315p:plain

Task 1, 2, 3 (Supporting Facts) は質問に関連するサポート事実を選択して回答するタスクである．タスクの難易度はそれぞれ回答に必要なサポート事実の個数によって 1 < 2 < 3 の順に難しくなる．

Task 4 (Two Argument Relations) は主語と目的語の関係性を識別できるか，Task 5 (Three Argument Relations) は更に送り手と受け手の関係性を識別できるか，を確認するタスクである．このタスクでは語順を考慮しない bag-of-words では正しく回答できない．例えば，“What is north of the bedroom?” と “What is the bedroom north of?” はまったく同じ単語で構成されるが，語順が変わると回答が異なる．タスクの難易度は 4 < 5 の順に難しくなる．

Task 6 (Yes/No Questions) は 1個のサポート事実を選択して真偽を回答するタスクである．

Task 7 (Counting) は物体の個数を回答するタスク，Task 8 (Lists/Sets) はリスト形式で単語のセットを回答するタスクである．これらはデータベース検索に関する QA タスクとして解釈できる．

Task 9 (Simple Negation) は否定形のサポート事実を含むタスクである．これは Task 6 のように真偽を回答する．Task 10 (Indefinite Knowledge) は不定形のサポート事実を含むタスクである．よって確実ではないが可能性がある場合は “maybe” と回答する．

f:id:Ryobot:20170525175321p:plain

Task 11 (Basic Coreference) は代名詞が参照元を検出できるか共参照関係を確認するタスクである．Task 12 (Conjunction) は接続詞が複数の主語を参照できるか確認するタスクである．Task 13 (Compound Coreference) は代名詞が複数の人物を参照できるか複数の共参照関係を確認するタスクである．

Task 14 (Time Reasoning) は時間表現を含むサポート事実を理解できるか確認するタスクである．

Task 15 (Basic Deduction) は演繹法 (e.g., 三段論法) を，Task 16 (Basic Induction) は帰納法を実行できるか確認するタスクである．ここでは基礎的な演繹法と帰納法しか分析しないので，更に深い分析は今後の課題である．

Task 17 (Positional Reasoning) はカラーボックスの相対的な位置を推論するタスクである．Task 18 (Size Reasoning) は物体の相対的なサイズを推論するタスクである．

Task 19 (Path Finding) は出発地から目的地までの経路を発見するタスクである．

Task 20 (Agent’s Motivations) はエージェントが行動を起こす動機を回答するタスクである．

2 メモリネットワークの拡張

目次に戻る ↩︎

Memory Networks は bAbI タスクを実行する手法の 1つであるが，以下の理由で幾つかのタスクで失敗する可能性がある．

文を bag-of-words でモデル化すると Task 4, 5 (Argument Relations) のような関係性を識別するタスクに失敗する可能性がある．
${k = 2}$ のとき二段階推論は実行できるが， Task 3, 7 のような ${3}$ 以上のサポート事実を必要とする質問には対処できない．
${R}$ モジュールは RNN を使用しないと，Task 8 (Lists/Sets) や Task 19 (Path Finding) のような複数の回答を必要とするタスクに対処できない．

よって，本節ではモデルの改良を幾つか提案したい．

1.1 適応性メモリ (Adaptive Memory) と適応性応答 (Adaptive Response)

質問の尋ね方に応じて複数のサポート事実を自動選択したい．そこで特別な事実 ${m_{\phi}}$ を追加し， ${m_{\phi}}$ が予測されるまでホップ (ループ) を繰り返す．

サポートメモリの計算は次のとおり．

${i = 1}$
${o_i = O (x, {\bf m})}$
while ${o_i \neq m_{\phi}}$ do
　　 ${i \leftarrow i + 1}$
　　 ${o_i = O ([x, m_{o_1}, \ldots ,m_{o_{i - 1}}], {\bf m})}$
end while

各ステップで見つけた既出のサポート事実 ${i}$ (各ステップ) で条件付けして， ${m_{\phi}}$ を予測したらホップを止める． ${m_{\phi}}$ は固有の埋め込みベクトル (学習パラメータ) を持つ．実験では計算が終わらない ( ${m_{\phi}}$ を予測しない) 失敗パターンを避けるために，ループの最大回数 (ここでは ${10}$ ) を設定している．

複数の回答

同様の手法で，$R$ モジュールは複数の単語を出力できる．辞書に特別な単語 $w_{\phi}$ を追加し，各イテレーション $i$ で $w_i = R([x, m_{o_1},... ,m_{|o|}, w_i,... ,w_{i - 1}], w)$ のように既出の出力単語で条件付けして単語 $w_i$ を予測し，$w_{\phi}$ を予測したらホップを止める．

1.2 非線形による文のモデル化

bag-of-words 系譜で文をモデル化する最も単純な手法は bag-of-N-grams (NG) である．ここでは ${N = 1, 2, 3}$ の bag を考える．この手法は N の値にともなって指数オーダーで辞書サイズが大きくなる欠点があるので，多重線形写像 (multilinear map) と呼ばれる代替的なニューラルネットワークの導入を試みる．

文中の各単語は，文の長さを ${l}$ ，単語の位置を ${i}$ とおくと ${p(i, l) = \lceil \, (i P_{sz}) \, / \, l \, \rceil}$ ( ${\lceil \cdot \rceil}$ は切り上げ) に従って， ${P_{sz}}$ (position size．これは定数) 個の bin のうちの 1つに入れられる．bin は元々ヒストグラムの棒を表し，ここでは袋 (入れ物) のようなニュアンスである．つまり総数 ${P_{sz}}$ 個の bin があり，位置 ${i}$ の単語は ${p(i, l)}$ という bin に入れられる．そして，各 ${p(i, l)}$ に応じて ${n \times n}$ の行列 ${P_{p(i, l)}}$ を乗ずるとする．これによって擬似的に単語の位置関係を考慮している (私感的には N-grams と言い難いが結果は良いっぽい)．

よって，モデルのマッチ率のスコアは次式によって表される．

$\displaystyle s(q, d) = E (q) \cdot E(d); \, \, \, E(x) = \mbox{tan}\mbox{h} ( \, \sum_{i = 1,... ,l} P_{p (i, l)} \Phi_{x} (x_i)^T U \, )$

各単語に対して位置 ${i}$ に応じた線形写像 (linear map) ${P_{p(i, l)}}$ を適応し，写像 (mapping) の合計に対して非線形関数 ${\tanh}$ を適応している．この手法は N-grams と同様に機能するので，N-grams が辞書サイズを肥大にする実用的な問題への有効な対処法となる．

適応性メモリ (Adaptive Memory, AM) + 多重線形 (multilinear) 仕様の MemNN の平均正答精度は 93% に達し，3.2 節 Table 3 と比較すると AM + N-grams (NG) + Nonlinearities (NL) 仕様の MemNN と同等の結果である．

最後に，単語の位置をモデル化しない非線形写像 (nonlinear map) も評価するために，次式のような非線形埋め込み (nonlinear embedding) を考える．

${E (x) = \tanh (W \tanh(\Phi_{x} (x)^T U))}$

ここで ${W}$ は ${n \times n}$ の行列である．これは古典的な 2層のニューラルネットワークに似ているが， ${s(q, d)}$ の両サイド ${q, \, d}$ を適応することに注意されたい．

ここでは bag-of-N-grams と非線形性 (nonlinearity) を組み合わせたフォワードプロパゲーションも考える．

3 実験

目次に戻る ↩︎

ここでは次のベースライン手法と比較した．(i) N-gram 分類器, (ii) LSTM, (iii) MemNN, (iv) MemNN の拡張モデル, (v) 既存の NLP タスクから得たラベル付きのデータを組み込んだ Structured SVM の 5手法である．

これらの手法は 3 つの異なる状況で訓練される．

弱教師あり学習 (Weakly Supervision) では質問と解答のペアのみで訓練し，強教師あり学習 (strong supervision) では更にサポート事実のセットも加えて訓練する．よって同じモデルであれば，強教師あり学習は弱教師あり学習より精度が高いはずである．また，外部資源 (External Resource) の状況では訓練セット以外に他の資源 (e.g., 共参照関係や意味をラベル付けしたタスク) から得たラベル付きデータを使用できる．

各タスクは訓練に 1000個の質問を使用し，テストに 1000個の質問をした．ここではテスト精度 95% 以上でそのタスクを達成したと考えた．

3.1 手法

ベースラインの N-gram 分類器は Richardson et al. (2013) のベースラインを参考にしている．物語の陳述は質問文と共通の単語を少なくとも一単語以上含む文のみを bag-of-N-grams 表現に変換し，その特徴を用いて線形分類器を学習して解答を予測した．このとき共通の単語でフィルタリングした表現を使用せず，すべての文の N-gram 表現を使用すると結果は悪化した．

MCTest: A Challenge Dataset for the Open-Domain Machine Comprehension of Text [Matthew Richardson, EMNLP, 2013]

LSTM は質問文に達するまで物語の陳述を入力してから回答を出力する．

MemNN は物語の陳述を格納したメモリに対して “コントローラー” (“controller”) ニューラルネットワークを使用した推論を行う．

オリジナルの MemNN は ${2}$ ホップの推論を実行するが，次の 3点で MemNN を拡張できる．

適応性があるメモリ (Adaptive memory): ${2}$ 以上のホップ数を実行したとき，モデルがホップまたは “STOP” クラスを予測するように訓練する．同様の手続きで複数のトークンを出力することができる．
N-gram: 文の表現として bag-of-words ではなく bag-of-3-grams を使用する．両者とも MemNN ではベクトルの埋め込みに変換する．
非線形性 (Nonlinearity): マッチ関数に非線形関数 ${\tanh}$ を用いた 2層のニューラルネットワークを使用する．

最後に，Structured Support Vector Machine (Structured SVM) を使用して古典的な NLP システムのベースラインを作成した．前処理として大量の高価なラベル付きデータを用いて共参照関係 (Coreference) や意味のラベル (Semantic Role Labeling, SRL) を学習し，得られた特徴を Structured SVM に入力し，サポート事実を見つけるために強教師あり学習で訓練した．サポート事実を見つけたあと，チューニングした特徴を用いて別の Structured SVM で応答を生成した．また，学習率やハイパパラメータは訓練セットを使用して選択した．

3.2 結果

1000 訓練データにおける各タスクのテスト精度の結果は Table 3 のとおり．

2 節で述べた MemNN の拡張はそれぞれ 5-8 列目の適応性メモリ (Adaptive Memory, AM), N-grams (NG), 非線形マッチ関数 (Nonlinear matching function, NL), そしてそれらの組み合わせである．太字の数字はオリジナルの MemNN では精度が 95% 以下であったが，拡張することで 95% 以上を達成したタスクを表している．

最後の 2 列 (9-10 列目) は MemNN の更に深い分析結果である．9 列目は各タスクにおいて AM + NG + NL 付きの MemNN が 95% 以上の精度に達するのに必要な訓練データ量を表している．ただし，1000 訓練データでも 95% の精度に達しない場合は FAIL と明記した．10 列目はすべてのタスクの訓練データを同時に与えて学習した場合の MemNN の精度である．

Table 3

f:id:Ryobot:20170525175411p:plain

※ 参照すべき項目に背景色を付けた．

4 列目のオリジナルの MemNN は一般的にベースラインの N-gram, LSTM よりもテスト精度が優れているが， ${k = 2}$ のサポート事実，一単語の回答，bag-of-words 等の制約により Task 3, 4, 5, 7, 8, 18 で失敗している．また，Task 6 (Yes/No Questions), Task 10 (Indefinite Knowledge) 等も当初の予測に反して失敗している．このことから標準的な MemNN の線形マッチ関数では質問 (query), サポート事実と 3択の yes/no/maybe 質問のマッチをモデル化できないことが示唆される．

5 列目の適応性 (Adaptive) 手法は 2つ以上のサポート事実を必要とする Task 3, 16 の精度を大幅に向上でき，依然難しいままだが複数の回答を必要とする Task 8, 19 の精度を改善できる．

6 列目の N-grams をモデルした MemNN は語順が重要な Task 4, 15 の精度を大幅に向上できる．とはいえ，Task 6 (Yes/No Questions), Task 10 (Indefinite Knowledge) のように非線形埋め込みモデルが N-grams モデルを大きく上回るタスクがある (平均でも上回っている) ので，N-grams が非線形性の代用になるとは言えない．一方，7 列目の非線形性は語順をモデル化できないので，Task 4, 15 を失敗している．

8 列目の拡張的な手法をすべて組み合わせた AM + NG + NL モデルは，オリジナルの MemNN では失敗であったが拡張によって成功に転じた 9 タスクにおいて，すべての結果を改善できる．(すごい…)

9 列目は 95%以上の精度に達するのに必要な訓練データの最小量である．モデルを一般化するためには，タスクを正常に実行するだけでなく，より少ないデータを使用することが望ましい．多くのタスクでは 100-500 例が必要である．ちなみに，Task 8 (Lists/Sets) は 5000 例，Task 7 (Counting) は 10000 例が必要である (よって FAIL 表記)．Task 17 (Positional Reasoning) と Task 19 (Path Finding) に至っては 10000 例でもタスクを達成できない．より洗練された演繹法と帰納法と，より汎用的な検索アルゴリズムが推論の手続きに必要であると思われる．

10 列目はすべてのタスクの訓練データを同時に与えて学習した場合の MemNN の精度である．文章理解と推論を同時に学習する機能は，モデルの汎用性が高いことを示している．とはいえ，依然として幾つかのタスクで失敗しており，サポート事実を使用した強教師あり学習が必要であるという実用的な問題が残っている．

f:id:Ryobot:20170525175425p:plain

※ 参考までに，Neural Turing Machines (NTM), Differentiable Neural Computers (DNC), End-To-End Memory Networks (MemN2N), Dynamic Memory Networks (DMN) における bAbI task の結果を掲載しておく．それぞれ正解精度ではなくエラー精度であることに注意されたい．