True Knowledge: Open-Domain Question Answering Using Structured Knowledge and Inference
- journal: AI Magazine2010 (published by AAAI)
- author: William Tunstall-Peadoe
質問応答システムTrue Knowledgeの論文．Eviっていうとわかる人が多いんだろうか（私は恥ずかしながら両方知らなかった）． 著者はTrue KnowledgeのfounderのWilliam氏．
概要
True Knowledgeの全体像を説明している．昔ながらのシステム構想で作られた本格的な質問応答システム(だと思う)． いくつかのコンポーネントをAPIとして本体から切り出している(もはや本体とはな状況だが)のもウリの１つらしい．
知識表現
KBでは様々な知識をグラフ構造を用いて表現している． また，ちゃんと説明できる自信がないので気になる人は論文を読んでいただきたいのだが，知識の表現にオントロジー的アプローチを採用している(論文のfig4)．
推論
KBを構築するにあたって，あらゆる知識をKBに格納していくとKBが非常に重たくなってしまう．そのため，基本的な知識によって推論することが可能な知識の一部はKBには格納されておらず，推論という枠組みで動的に生成される． 例えば，
\begin{align} \mbox{(Big Ben is in London.)}, \mbox{(London is in UK.)} \to \mbox{Big Ben is in UK.} \end{align}
といった具合．推論をどの程度行うかというのはシステムによって異なっていて，システムによってはパフォーマンスを上げるために上記のような知識もすべてKBに格納していることもあるそうだ(推論にはある程度時間がかかる)．
推論は，generatorと呼ばれる規則の集合を用いて行われる．True Knowledgeでは現在1500程度の推論規則が使われているらしい．
また，Computationと呼ばれる推論もサポートしている(例えば，1863年の3日目は何曜日？といった質問に対して金曜日と解答する際に行われる演算機構)． こちらはSmart Generatorと呼ばれ，別のWebサービスとして独立しているらしい．
翻訳
ユーザから送られてくる質問文を知識ベースに対して投入するクエリに変換するコンポーネント． テンプレートの集合によって実装しているとあるので書き換え規則とアライメントを使った手法なのかな．
知識獲得
知識資源としては，いろいろな構造化データベース(is 何)はKBにインポートしていて，異なる分野をまたぐ知識を提供するためにFreebaseも使っている．
また，データとしてはWikipediaのデータとユーザが追加するデータも利用している．フィードバックを活用できる枠組みが確立しているということは検索エンジンや質問応答システムを構築するにあたって非常に良いことだろうなぁと思った．
NLP技術を活用した知識獲得も同様に行っている(Sentence extraction, Simplification, Translation, Bootstraping(?))．
とここまで読んだところで，手法に関する記載はあまりない印象を受けたので打ち切り． こういう動かせるレベルのシステムを作れるのは本当にすごいなぁ．
Sentense-similarity-learning-by-lexical-decomposition-and-composition
- publish: arXiv
- author: Zhiguo Wang, Haitao Mi, Abraham Ittycheriah
概要
QAでCNNな研究．現在のWikiQAとQASentのstate-of-the-art (ACL Anthology wiki調べ, 2016/03/16)．
アブストで「今までの文章類似度を計算する手法は似ている部分だけ着目していて，似ていない部分は無視しているが，似ていない部分の情報も重要だよ」みたいなことを言っていてなるほど確かにと思った．
まず，著者は既存の文章類似度の計算の３つの問題点の指摘から始める．
意味的に類似しているが，異なる語彙が用いられている場合に正確に類似度を計算できない
- Milkov+ (2013)の研究を例としてあげている．論文中でembeddingの手法についての詳しい言及がない(気がする)ので，word2vecを単語ベクトルを獲得するために使っているのかなと思った．
単語レベルではなく，フレーズレベル，構文レベルでも類似度を計算しなければいけない
- "not related"は単語に分割すべきではなく，フレーズとしてみれば"irrelevant"と似た表現とみなすことができる．
「類似している」という情報ではなく，「類似していない」という情報も活用しなければならない
これらを踏まえ (これらの問題に対処して) モデルを設計する．
手法
- 単語を低次元のベクトルで表現する
- すべての単語について，semantic matching vectorを計算する(よく分からない)
- semantic matching vectorを用いて，単語ベクトルをsimilar componentsとdissimilar componentの２つに分解する(Decompose)
- CNNを使って１つの特徴空間に射影する(Compose)
- 類似度はsumをとってsigmoid関数を適用するだけ
何回か読んだけどsemantic matching vectorがなんなのかよく分からない(代表ベクトルみたいなもの?)．
semantic matching
we need to check whether each semantic unit in one sentence is covered by the other sentence, or vice versa.
包含関係を調べる必要がある．"irrelevant"という１つの単語が"not related"というフレーズでカバーされていることを知る必要がある．どうするかというと，
\begin{align} \hat{s_i} &=& f_{match} (s_i, T) & \forall s_i \in S \\ \hat{t_i} &=& f_{match} (t_j, S) & \forall t_j \in T \end{align}
とするらしい(よくわかりません)．
第3章で $$ f_{match} (s_i, T) $$についてはより詳細な定義が述べられている． 文書Sのサイズ x 文書Tのサイズの行列 $$ A $$ の $$i, j$$要素を
\begin{align} a_{i,j} = \frac{s_iT t_j}{|| s_i || \cdot || t_j ||} &&& \forall s_i \in S ，\forall t_j \in T \end{align}
として，
\begin{align} f_{match} (s_i, T) = \begin{cases} \frac{\sum_{j=0}^{n} a_{i,j} t_j}{\sum_{j=0}^{n} a_{i,j}} & global \\ \frac{\sum_{j=k-w}^{k+w} a_{i,j} t_j}{\sum_{j=k-w}^{k+w} a_{i,j}} & local-w \\ t_k & max \end{cases} \end{align}
誰かこれがなんなのか教えて下さい．．．
decomposition
$$ \hat{s_i} $$ と $$ \hat{t_j} $$は文章 $$ T $$ と $$ S $$に対する"意味的な適用範囲"(semantic coverage)と解釈できる．
\begin{align} \left[ s_i^{+}; s_i^{-} \right] = f_{decomp} (s_i, \hat{s_i}) \\ \left[ t_j^{+}; t_j^{-} \right] = f_{decomp} (t_j, \hat{t_j}) \end{align}
によって，単語ベクトルを類似部分と非類似部分の２つに分解する．
分解を行う関数はRigitな関数(なんて訳せば良いのかわからない，全か無をとる関数)か線形な関数，あと直行ベクトルを使う関数の三種類が挙げられている．
composition
\begin{align} \vec{S} = f_{comp} (S^{+}, S^{-}) \\ \vec{T} = f_{comp} (T^{+}, T^{-}) \end{align}
がっちゃんこ．
CNNによって，２種類のベクトルを１つのベクトル空間に射影する．
畳み込みのフィルターを $$ {w_o} (d × h)$$ とする( $$d$$ は単語ベクトルの次元， $$ h $$ はwindow size)．
\begin{align} c_{o,i} = f( w_o * S_{\left[ i:i+h \right]}^{+} + w_o * S_{\left[ i:i+h \right]}^{-} + b_o) \end{align}
最適化にはAdam (Kingma+, 2014)を使っている．
評価実験
MAP (mean average precision) とMRR (mean reciprocal rank) を使って評価する．評価タスクは質問応答ではQASentとWikiQA．QASentはTREC QA trackで作られたデータで，QASentはWikipediaとBingに実際に入力されたクエリによって構成されている．言い換えではMSRP corpus (MSRP) で実験する(こちらはあまり追っていない)．$$ d = 300 $$ (d = 単語次元)でembeddingを行う(ここでword2vecを使ったと書かれていた)．
すごい (小学生並の感想)．
Resource Analysis for Question Answering
なにこれ
質問応答システムを構築するとき，様々なリソースを知識源とする． この論文では，それらのリソースの比較を行っている． 質問応答初心者なので，どのリソースがどういう特徴を持っているか・またどのタイプの質問に対して有効かをよく知らなかったので読みました．
Gazatteer
Gazetteer(地名集)．
「X(地名)の人口は?」，「Yの首都は?」と言った調子のファクトイド型の質問を扱うデータベース． CIA World Factbookは世界中の国々の地理的，政治的，経済的な特徴を収録している．
天文学に関する情報を収録しているAstronomyやアメリカの50州の情報を収録した50Statesなんかもある．
Gazatteerは常にデータを最新に保っているので，ある時点でのデータは別の時点のデータとは別物である可能性がある(=再現性のない実験結果が得られる可能性がある)． また，「太陽との距離は?」といった質問のように，時期によって解答が異なる質問も時期によって異なる解答が得られる．
Gazatteerの特徴として，非常に精度の高い情報が収録されているという特徴がある(そのかわり再現率はあまり高くならない)． TREC(質問文と解答文のデータセット)の質問のうち，Gazatteerの情報をそのまま利用できるタイプの問題に対しては非常に高い正解率を誇る．
WordNet
WordNetは概念辞書と呼ばれるもので，単語に関する説明を収録している．プリンストン大学で開発された． Web上インターフェースが公開されているので，試しに使ってみると良い． 日本版はないのって話だが，ある．こちらはNICT(国立研究開発法人情報通信研究機構)が提供している．
概念を整理し記述する，オントロジー．
Structured Data Sources
百科事典や辞書，その他のWeb上の資料は主に「Xって何?」，「Xって誰?」と言った定義を問うタイプの質問の解答を得るために用いられる． TRECで最も良い成績を収めたXuら(2003)のDefinitional System(日本語でなんて言えば良いんだろう?)では，WordNet(Miller et al., 1990))，the Marriam-Webstar dictionary，the Columbia Encyclopedia，Wikipedia，biography dictionary，そしてGoogle(これ資料って言うのか?)などの構造化・半構造化されたリソースを用いていた．
質問文からのN-gramをwikipediaやgoogleで検索するだけでもそこそこ解答が見つかることも多い(TRECの質問文での議論が論文中にあるので興味があったら読んでみてください)．
Answer Type Coverage
自分の構築したシステムがどれくらい広範な質問に対応しているのかをテストしたいときには，JAVELINシステム(Nyberg et al., 2003)を使うと良い． 「viscosityって何?」とか「Lacanって誰?」とか「クレオパトラはどのように死んだ?」といった広範な知識を問う問題が収録されている．
Answer Typeは以下のように区分される．
- object
- lexicon
- definition
- person-bio
- process
- temporal
- numeric
- location
- proper
The Web as a Resource
Webはローカルに構築したコーパスよりも極めて巨大なので(web is orders of magnitude larger than local coporaってどういう意味だろう．．．)，簡単な質問とそれに対する解答はより頻繁に出現する． そのため，正しい解答を得るためにとても有用である．
Web上のリソースはパターン獲得や文書文書検索，構造化データの抽出，そして解答の検証のために使われることが多い．
Web Documents
ローカルに構築したコーパスを探索するかわりに，Web上の資料を探索して解答を見つけることを試みる質問応答システムも存在する(Xu et al., 2003::たぶんStructured Data Sourceの章で言及した研究)．
検索エンジンに対して質問文をtokenizeしたものをそのまま投げつける実験してみたら結構精度よかったみたいなことがその後に書かれています(google apiの話していたので読み飛ばした)．
Web Based Query Expansion
擬似適合フィードバックとかみたいな，クエリを拡張する手法もあるよーって話をしている．
まとめ
QAに使えそうなリソースを紹介してもらいました． 手法自体は当時からかなり色々変わっているけれど，データの重要性は変わっていないと思うので，調べてみる価値はあったと思っている．
次に読むべきかもしれない論文
Question Answering with Subgraph Embeddings
- conference: EMNLP2014
- author: Antoine Bordes, Sumit Chopra, Jason Weston
どんなもの?
Facebook AI研の方々の研究．
オープンドメイン質問応答システム．分散表現を使う．
先行研究と比べてどこがすごい?
質問応答システムは，KBに対してはスケーラビリティが高い一方で語彙や文法に関する知識やKBのスキーマなどに関しては熟練の技術者が注意深く設計しなくてはならなかった．
Faderら(2013)はほとんど人手のアノテーションを必要としないシステムを作ったが，このモデルはBordesら(2014)の分散表現を用いたモデルに負けた．
しかし，このモデルも十分な汎用性を持っているとは言えない．
そこで，この手法ではBordesらのモデルを改良する．
- より洗練された推論手続き
- 解答の符号化がよりリッチになった(よく分からなかった)
Barent，Liang(2014)のstate-of-the-artなモデルと同等のベンチマーク結果を出した(語彙に関する知識やその他の情報を用いていないにもかかわらず！)．
技術や手法のキモはどこ?
質問文とEntity(KBの中身?)とFREEBASEのrelation types(FREEBASEは知識をグラフの形で保持しているので，relation typeはエッジの属性に相当するのかなと思う)に出現する単語のembeddingsを学習する．
質問文を$$q$$，解答を$$a$$として，スコア関数$$S(q, a) = f(q)T g(a)$$と定義する．
質問文と解答文が正しい組み合わせであればスコア関数が大きくなるんだと思う．
$$f()$$は質問文をEmbedding空間にマッピングする関数で，$$g()$$は解答をマッピングする関数．
$$f(q) = \bf{W}\phi(q$$，$$g(a) = \bf{W}\psi(a)$$であり，重み行列である$$\bf{W}$$を最適化する．
$$\phi$$と$$\psi$$は文章をバイナリエンコーディングする関数だと思う．
どうやって有効だと検証した?
WebQuestionを用いてベンチマークテストを行った．
ベースラインと同等くらいの正解率(40%くらいだけど)．
語彙とか文法とかの情報なしで同等の精度を出せるのは結構すごいと思った．
MLNとかと比較してどうなんだろう(そういえばMLNもEMNLP2014だったっけ)．
次に読むべき論文は?
- Freebase: a collaboratively created graph database for structuring human knowledge
- Paraphrase-driven learning for open question answering
- Semantic parsing via paraphrasing
zatsu
- 自然言語を解釈するのがそもそも難しくて，そのせいもあって質問応答は難しい
- 質問応答のstate-of-the-artは二つのアプローチがある
- information retrieval base
- KBへのアクセス重視
- semantic parsing base
- KBに投げるクエリ重視
- information retrieval base
筑波大学の科目を検索するやつ「きりのは」を作った
つくった
毎年この時期になると科目検索アプリを作る病気にかかっているまつのきです（去年作ったのはこちら）
というわけで，今年も作りました．今年は「桐の葉」という名前のアプリです．
このアプリは大学が作成したものではなく，私が個人的に作成した非公式のアプリです．
科目の詳細画面にツイートボタンを設置しておきました． 友達と「この授業とろうぜ！」というノリで科目情報を共有していただけたら嬉しいです．
筑波大学では，科目を検索する手段として，
- Twinsの科目検索機能
- KDB
の２つが利用可能です． KDBの出現により，我々学生は格段に科目を検索しやすくなりました．
もう少し柔軟にクエリを書きたいなぁと思うことが何度かあり，ちょうど新年度だったので作ってみました．
例えば，「数学」に関する科目で，3単位以上，3A棟で開講されている講義を検索したいとすると，桐の葉の検索フォームに
title: 数学 credits >= 3 location: 3A
と入力して検索をすることができます．
ちなみに，検索フィールドは
- code (文字)
- title (文字)
- credits (数値)
- terms (文字(スペース区切り))
- instructors (文字(スペース区切り))
- daytimes (文字(スペース区切り))
- info (文字)
- grades (文字(スペース区切り)(本当は数値の配列にしたい))
- location (文字)
があります． 全文検索エンジン(Apache SolrとかElasticsearchとか)にデータを格納することを念頭にテーブルを作ったので，RDB的にはダメなフィールドが幾つか存在します．
全文検索エンジンを使いたいんですが，お金がないのでいつかやりたいです．今はHerokuの無料枠で頑張ってます．無料枠なので負荷に耐えられないかもしれません．優しくしてください．
また，大学院科目はデータベースに登録していませんので検索されません． Herokuの無料枠ではデータベースに登録できるレコードは10000万件までで，大学院科目を含めると科目データが18000件ほどになるので諦めました．誰かが僕に月に900円くれれば大学院科目も検索できるようになります．
すこしだけ実装の話もしましょう．
今回は全文検索を実現するにあたり，以下のRubygemを用いました．
特別なことはほぼ必要なく，モデルファイルに「このフィールドを全文検索の検索対象にする」ことを記述してやれば（see: kirinoha/subject.rb at master · himkt/kirinoha · GitHub）全文検索が可能になる，驚愕の一品です．
本当に気軽でとても良いのですが，問題もあります．
- 検索結果のリランキングができない（多分
- パフォーマンスが良くない（多分
Apache SolrやElasticsearchでは，特定の検索語やフィールドに対して重みをつけて検索結果をスコアリングし，ランク順で出力することが可能ですが，このsearch_copではそれは不可能です（当たり前だ
また，すべての検索リクエストはRDBに対して行なわれているので，ちゃんとした全文検索エンジンを使ったシステムよりもパフォーマンスは悪いはず？（データが高々10000件なのでそこそこの速度で検索できてるけど
以上，科目検索システム桐の葉の紹介でした． ちゃんとお金をかけて作り直したい気もしますが，大貧民学生にはちょっとしんどい．石油当てたら作り直します．
何か分からない点（たくさんありそう）がありましたら， 松之木 (@himkt) | Twitter までお気軽にお問い合わせください． プルリクエスト待ってます．．．（チラ github.com
