読者です 読者をやめる 読者になる 読者になる

進捗のためにできること

この記事はklisアドベントカレンダーの24日目の記事として作成されました.

こんにちは,まつのきです. 今年ももうクリスマスです.いなふくんの進捗はどうでしょうか?気になって夜も眠れません.


12/22は知識情報・図書館学類の卒業論文の提出期限です.

Twitterのklis13リストを見ると、締め切り1週間まえくらいから少しずつ余裕がなくなっていく4年生の様子を眺めることができます.

締め切り直前にデスマーチをするのも楽しいのかもしれませんが、筆者はあまり徹夜が得意ではありません.

根を詰めすぎて身体を壊しては元も子もありません.計画的な進捗作りが必要です.

筆者はとても怠け者です.授業の課題に取り組む際は大量に時間を確保してグダグダ作業をしてきました.

安全マージンを十分にとって作業をするため締め切りを落とすことはありませんでしたが、大変効率が悪いやりかたです.

しかし、4年生になり諸般の事情でそれまでよりも忙しい日々を過ごすようになり、大量の時間を確保できなくなりました.

これまでのやり方で作業を進めていては締め切りを落としてもう一度4年生を楽しむ権利を得ることになります.

それはそれで面白いですが指導教員が悲しみます.

指導教員を悲しませてはいけません.やはり計画的な作業スタイルの確立が必要です.

良い作業スタイルを探す過程で、「こうすれば計画的に/効率的に作業が進められそうだ」と思えるいくつかの知見を得たので、この場を借りてみなさんに共有します.

筆者は情報系の学生です.そのため、知見の中には情報系の学生を対象にしたものもあります.

まずは専門に関わらず使えそうな知見を、そのあとで情報系の学生を対象にした知見を紹介します.

専門不問な話題

すべての大学生にとって有益そうな知見の紹介を始めます.

1週間のうち,作業をする曜日,時間帯,達成目標を決める

できる研究者の論文生産術という本があります.

できる研究者の論文生産術 どうすれば「たくさん」書けるのか (KS科学一般書)

できる研究者の論文生産術 どうすれば「たくさん」書けるのか (KS科学一般書)

この本は、雑務におわれ思うように論文を執筆できない大学教員・大学院生に向け、論文を執筆するための時間の作り方などを指南しています.

大学教員・大学院生だけではなく、様々な人にとって役に立つ作業術であると思いました.

中でも、「1週間のうちに作業する曜日・時間帯、その日の達成目標を決める」ということは、筆者の作業能率を大きく向上させてくれました.

なんだそれだけかと思うかもしれませんが,徹底することで生産性がかなり上がります.

筆者は毎週の月・火・水曜日の午前9時〜午前11時を卒業論文の執筆に使う時間としました.

この時間以外には基本的に卒業論文の執筆をしませんでした.

週に6時間しか執筆の時間がないわけで、これでは到底時間が足りないのではないかと思っていましたが、不思議なことに作業は順調に進みました.

大量にマージンをとって1日がかりで作っていた進捗とほぼ同等の進捗が1日のたった2時間のうちに終わるようになりました.

グダグダ作業をすると作業効率が極めて悪いということを改ためて実感し、「俺はなんて無駄な時間を...」と思ったのでした.

また、その日の作業の到達目標を定めることも重要です.

ゴールなしで走るよりもゴールが定まった状態で走るほうが精神的な負担が少なく済みます.

ただ、良い目標を立てることは簡単ではありません.

仕方がないので、筆者は「1日に最低1000字は書く」ことを目標にしました.

より良い到達目標の設定が可能になれば、より作業スピードが上がる気がします.

目標設定をきちんと行うことを、後輩のみなさんは心がけるべきです(自戒).

予定を第三者と共有する

作業をする曜日・時間帯を決定しても、遊びにいく予定やミーティングなどに阻まれてしまっては意味をなしません..

できる限り作業をする時間帯には予定が入らないように工夫したいと考えるのは自然なことですね.

筆者は、作業時間とその他の予定がバッティングしないように、自分のGoogleカレンダーを公開し、頻繁に一緒に行動する人たちとカレンダーを共有しました.(http://himkt.github.io/ の下の方にあります)

これによって作業時間に予定が入ることがほとんどなくなりましたし、日程調整の手間がかなり減って良い感じでした.

知られても良い予定については他人に共有する、ぜひ試してみて欲しいです.

記録について:ノートを使う?

継続的に作業をするための工夫は終わりで、ここからは作業中の具体的なあれこれについてお話します.

まずは作業の記録の取りかたについてです.

尊敬する大先輩であるところのるーめりさんの記事によると、研究ノートを作ることは研究の様々な側面において重要です.

筆者も研究ノートを作ることにしました.

紙のノートの方が「頑張ってきた積み重ね」が目に見えるので良いということだったので、紙のノートを購入して作業を記録しました.

f:id:himkt:20161223213906j:plain

紙ノートに記録をとっていたのは夏休みの2ヶ月間です.

ノートの冊数が増えるにつれて、過去の記録の検索に時間がかかるようになり、最終的にはパソコンでノートをとることにしました.

GitHub上にリポジトリを作成し、issueなどの機能を使っています.まぁまぁ快適です.

GitHubについて、もう少し詳しい話を後述します.

インターネット接続について

「執筆中はインターネット接続を切るべし」という教えをよく耳にします.

Twitterをしながら作業をするのはダメだと思いますが、情報系の人間が作業中にインターネット接続を断つのは必ずしも得策ではないように思います.

例えば、手法の実装をするにあたり,ウェブ上のドキュメントは重要な情報源です.

ドキュメントへのアクセスを制限するとかえって作業効率が落ちます.

一方で,Twitterをみながら執筆したり課題をしたりするのが非効率的であることも半ば自明です.

誘惑に弱い人はSite Blockなどを使ってTwitterなどへのアクセスに制限をかけましょう.

情報系学生にとって有益そうなことがら

ここからはより情報系な人に向けたトピックになります.

Git、GitHub

なにかしらのシステムを実装することになった場合,プログラムのソースコードなどを管理する必要があります.

Gitというツールは、ソースコードをコミットと呼ばれる単位で管理します.

コミットとは、ゲームにおけるセーブに似たものです(多分).

ソースコードを手元の計算機だけで管理しているとあるとき計算機が壊れてストレージからデータを復旧できなくなった!というときに詰みます.

また、コミット単位でコードを管理することで、予期せぬバグがプログラムに入り込んでしまったときにバグが含まれたコミットを取り消すことができます.

Gitの初歩的な知識をゲームを通して学ぶサイトがあります、Gitって何?という方はのぞいてみると良い気がします.

GitHubソースコード管理において非常に強力なサービスです.GitHubはGitを用いた開発のインターフェースを提供します.

コードの管理には気を遣うべきです.

また,GitHubはチームで開発を行う際にも非常に役に立ちます.

プルリクエストと呼ばれる機能を通して,研究室の他のメンバーに自分の書いたソースコードをレビューしてもらうことができます.

GitHubを使いこなすためにはGitの使い方を知る必要があります.

慣れないうちは多少戸惑うこともあるかもしれませんが,学ぶ価値は十二分にあると思います.

さらに,GitHubにはソースコードを管理する機能の他に,進捗管理を行うための機能も備わっています.

この機能に関してはMakkyの記事が詳しいです.

システム系以外の人にとっても便利な機能です.ぜひ読んでみてください.

まだGitHubのアカウントを持っていない人はぜひアカウントを作成してhimktをフォローしましょう(?).

プロジェクトの構成

システム系の研究(特に実験メインの研究)では,実験コードや実験結果(数値,図)や前処理をするスクリプト,前処理後のデータ,テストなどを1つのプロジェクトの中で管理する必要があります.

実験スクリプト、実験データ、実験結果などは別々のフォルダに置くようにして管理すると良い気がします.

また、ファイルの命名規制などを決めて置くとより管理が楽になります.

以下に筆者のプロジェクトのディレクトリ構成を示します.

適切かどうかにあまり自信はありませんが、1つのディレクトリにあらゆるファイルを設置するよりは見通しが良いはずです.

root
 ├── figure
 ├── data
 ├── model
 ├── result
 ├── test
 ├── util
 └── work

参考になりそうな資料へのリンクを以下に示しておきます.

テストを書く

テストを書くことはバグを発見し、対処する作業を劇的に楽にします.

複数のプログラムを組み合わせて行う実験において,エラーが出たときに「このモジュールがおかしい」ということがわかるとデバッグがとても効率的に行えます(強く自戒).

テストに関してはNLPチュートリアルの21ページ目あたりを読んだり「単体テスト」で検索すると色々と資料が見つかります.

まとめ

卒業研究に取り組むにあたって,生産性を高める/維持するために試してみたことについてまとめました.

来年卒業研究に取り組む人はもちろん,授業の課題をなかなか計画的にこなせない人にもぜひ試してみて欲しいです.

進捗管理術は一生ものの財産です、大学生のうちに洗練させるために試行錯誤する価値があると思います.

また,生産性を高めるために使えるTipsがあったらぜひ教えてください.

それではみなさん、良いクリスマスを.

Research and reviews in question answering system

走り書きです.

  • conference CIMTA 2013
  • Sanjay and Vaishali

概要

QAのサーベイ. QAは現在のクエリを投入したら適合文書のリストが渡されて,そこから正確な情報をクエリ投入者が探すというパラダイムを超える可能性を持っている.

QAシステムは時間をかけて大変進歩してきたが,まだ幾つかの挑戦的な課題を残している.

  1. 自然文の質問を理解すること
  2. 質問タイプの分類
  3. 適切なクエリ化
  4. 曖昧性解消
  5. 意味的類似語の検出
  6. identification of temporal relationship in complex questions

  7. QAシステムの3つのステップ

  8. 質問解析
    • パージング
    • 質問分類
    • クエリ構築
  9. 文書解析
    • 候補抽出
    • 解答特定
  10. 解答解析

    • 解答候補のランク付け
  11. QAシステムの分類

  12. Linguistic Approach

    • tokenization and parsing
      • 異なる分野では異なる文法が必要になるなど,可搬性に乏しい
      • 適切なKBを作るのは時間がかかる
    • knowledge information is organized in the form of production rules, logics, frames, templates(triple relations), ontologies and semantic networks
  13. Statistical Approach

    • 近年の爆発的な情報の増加を背景に発展してきたアプローチ
    • 大規模,不均質なデータをうまく扱うことができる
    • 特定のクエリ言語に依存しないし,自然言語でクエリをかける
    • 言語に依存しないし新しいドメインにも適応しやすいが,語彙的に意味のあるフレーズなどに弱い
  14. Pattern Matching Approach

Ling

データベースに問い合わせるための自然言語インターフェース

自然言語文をクエリにする

  • BASEBALL
  • LUNAR

DIALOG

  • ELIZA
  • GUS

これらの手法では,データを構造化データベースに格納するため,解答能力に制約がある.

これらの制約を許容して,構造化データベースから得られる情報をもとに推論を行うタイプの質問応答システムが現れた.

STARTはWEBを知識源としている.経験則的な情報を用いてWeb上の情報を知識ベースに格納する.

Rule

Auarc,Carqは経験則にもとづいて質問文中から質問のタイプを分類する語彙的,意味的なヒントを探す.

  • who, what, which, where,...
  • others

Statistical

Answer finding task(クエリに対応する解答を統計的に探す)に使ってみたところ,パフォーマンスはデータセットの語彙数に依存することがわかった.

IBMが作った質問応答システムでは,Okapi(BM25?)とTREC-9のQAコーパスを使ったクエリの拡張の2つを採用していた.

Statistical methodでは,クエリと文書,もしくは一文との類似度をどのように計算するかがキモになっていて,キーワードの類似度やクエリや文書の長さ,出現単語の語順の類似など,様々な尺度が考えられ適用されている.

Pattern Matching

「Where was Cricket World Cup 2012 held ?」という質問に対して,「where was held ?」というテンプレートをマッチさせる(同時に,解答タイプが「場所」であることも予め定義しておく),というアプローチを取るものたち.

現在の質問応答システムの多くは上記のようなパターンをテキストから自動的に学習することが多い(言語学的な知識やオントロジー,言語資源(WordNetなど)を用いる複雑な手法は採用されない傾向がある).

あまり複雑な質問に応答することはできない(パターンが膨大になる)ため,小-中規模の比較的簡単かつ限られた質問をされるような場面で使いやすい.

Surface Pattern based

大量の正規表現を使って解答を抽出する.

正規表現を大量に作成するのは非常に手間のかかる作業であるが,それらによって抽出される解答は非常に精度が高い.

得られた解答の信頼度を定量的に示すためにsurface patternを用いる手法もある.それらは高精度かつ低再現度である.

Template based

slotを埋めていくアプローチ.slotを埋めるタイプの質問応答は音声系の研究で多いと指導教官に教えてもらった記憶がある.

新しいデータが入ってきたとき,新しいテンプレートを作らなくてはそのデータに対応することができない.

Summary

linguistic approachは限定的なドメインをスコープに持つときにきわめて良いパフォーマンスを発揮する. 知識ベースを人でで作るのは分野の専門家が必要であり,手間もかかる. 最近の研究では,Webを知識源とすることによって知識ベースを強化したりオープンドメイン質問応答をしようという試みがある.

Statistical approachは充分な語彙数の大規模なデータ(= データ間が比較可能)が得られているときに良いパフォーマンスを発揮する. Statisticalなアプローチを取るときには,充分な訓練データがなければいけないが,一度適切に学習することができれば複雑な質問に対しても良い解答を生成することができる.

Pattern based approachは言語学的な分析をする代わりにテキストの特徴的な表現を活用する.Pattern basedな手法はその「浅さ」(表面情報しか加味しない点)ゆえに失敗することもあるが,Webをデータ源として活用するための効率的なテクニックでもある.Pattern basedな手法は,言語学的な情報への依存を減少させるだけでなく,不均質なデータをうまく扱える.だが,しばしばこの手法は意味的におかしい解釈や判断を行うことがある)(「浅さ」ゆえに).

これらの基本的なアプローチは,単体ではそれぞれに異なる制約がある.これらの手法を組み合わせることでより精度,再現率の良いシステムを構築する試みもあり,ASQAやIBM Watsonなどが有名.

結び

QAシステムを実装するにあたって,どの技術を用いるべきかは想定される問題のタイプにきわめて強く依存している. 複数のアプローチのハイブリッドが良い結果を出しているが,以前として基本的な手法の研究も重要であり続けるだろう.

Python文法詳解メモ

www.oreilly.co.jp

Python文法詳解という本がある. 読むととてもためになる.自分がおおと思ったものをメモしている.

気になったら実際に読んでみると良いと思います.上記のリンクはオライリーの商品詳解ページを指していますが,このリンクを経由して本書を購入することで私に金銭的な利益が発生することはないので安心してください.

適当な値を要素に持つ配列を作る

こうしてた

[1 for _ in range(N)]

こうできる

[1] * N

罠があります(前者で作るのかな). 後者の書き方でリストを作ると実行時間が劇的に短い.なんでかは考えてみてください.

qiita.com

算術演算

これは

a ** b % c

こっちのほうが高速

pow(a, b, c)

powって第三引数取れたんですね...

リストの展開

def spam(ham, egg):
    return (ham, egg)

a = [1, 2]
spam(*a)

辞書の展開

def spam(ham, egg):
    return (ham, egg)

a = {'ham': 1, 'egg': 2}
spam(**a)

ちなみに辞書を展開して変数にする(?)ので,キーは文字列でなければなりません(1 = 2みたいなことになってしまう).

要素の分解

a, b, *c = list(range(10))

右辺の要素の数が足りないとき,cは空のリストになる(ただし,a, bは値がないといけないので,以下はエラーになる.

a, b, *c = list(range(1))

#=> Traceback (most recent call last):
#     File "<stdin>", line 1, in <module>
#     ValueError: not enough values to unpack (expected at least 2, got 1)

shallow copydeep copy

>>> a = [1,2,3]
>>> b = a
>>> a.append(1)
>>> a
[1, 2, 3, 1]
>>> b
[1, 2, 3, 1]
>>> 
>>> a = [1,2,3]
>>> b = a.copy()
>>> a.append(1)
>>> b
[1, 2, 3]
>>> a
[1, 2, 3, 1]

よく見ると新しくオブジェクト作ってるやつ

>>> a = 1
>>> b = a
>>> a += 1
>>> b
1

list.extend(iterable)

>>> a = [1,2,3]
>>> a.extend([1,2,3])
>>> a
[1, 2, 3, 1, 2, 3]
>>> a.extend('spam')
>>> a
[1, 2, 3, 1, 2, 3, 's', 'p', 'a', 'm']
>>> 

リストの末尾にイテラブルオブジェクトのすべての要素を追加する.

list.sort(key=int)

>>> a = ['1', '10', '2', 3]
>>> a.sort(key=int)
>>> a
['1', '2', 3, '10']

なにこれすごい.

str.center(w)

>>> 'a'.center(10)
'    a     '
>>> 'a'.center(10, '*')
'****a*****'
>>>

プログラミング演習でつかえそう(内輪ネタ).

辞書内包

>>> {x+y:1 for x in 'abc'
             for y in '123'}
{'a3': 1, 'c2': 1, 'c1': 1, 'c3': 1, 'a2': 1, 'b3': 1, 'b2': 1, 'a1': 1, 'b1': 1}
>>>

集合内包

{i for i in range(10)}
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
>>> 

set(i for i in range(10))って書いてた.

そういえば,set([i for i in range(10)])って書かなくて良いのも最近知りました.

例外の送出

raise ValueError('不正な値です')

print('不正な値です')ってやってた.

関数アノテーション

>>> def spam(ham: "ハムの枚数") -> int:
...     return ham
>>> spam(2)

きちんと書くとIDEが良い感じにしてくれるらしい(伝聞).

ラムダ式

>>> f = lambda x, y, z: 1
>>> f(1, 2, 3)
1
>>>

続パタの前向き・後ろ向きアルゴリズムについてのメモ

8章で解説されている前向きアルゴリズムに関するメモです. 私が勉強していてつまずいたところを,本文に即する形で補足します.


求めたいのは,サイコロの目の系列 $ \mathbf{x} = x_1x_2 \dots x_n $ が得られる確率 $ P( \mathbf{x} ) $ です.

この確率は潜在変数を用いて

\begin{align} P( \mathbf{x} ) = \sum_{ \mathbf{s} } P(\mathbf{x}, \mathbf{s}) \end{align}

と表すことができます.

\begin{align} \sum_{ \mathbf{s} } \end{align}

は一見普通の和に見えますが,実は

\begin{align} \sum_{ \mathbf{s} } = \sum_{s_1} \sum_{s_2} \sum_{s_3} \dots \sum_{s_n } \end{align}

という恐ろしい形の和です.

\begin{align} P( \mathbf{x}, \mathbf{s}) = \Pi_{ \mathbf{s} } a(s_{t-1}, s_{t}) b(s_t, x_t) \end{align}

この同時確率から $ \mathbf{x} $ のみに関する確率を得るためには,上で述べた恐ろしい $ \mathbf{s} $ に関する周辺化を行う必要があり, $ s_n $ の $ n $ が大きくなると現実的ではありません($ O(2nc^{n}) $ になります).

ここで,

\begin{align} P( \mathbf{x}, s_t = w_i ) \end{align}

について考えてみましょう.

\begin{align} P( \mathbf{x}, s_t = w_i ) &= P( x_1 x_2 \dots x_t, s_t = w_i ) P( x_{t+1} x_{t+2} \dots x_{n} | x_1 x_2 \dots x_t, s_t = w_i) \\ &= P(x_1 x_2 \dots x_t, s_t = w_i ) P( x_{t+1} x_{t+2} \dots x{n} | s_t = w_i ) \end{align}

最後の式で,2つ目の確率の条件の部分から $ x{1} x{2} \dots x_t $ が消えていることに気づくと思います.

この消去は条件付き独立の定義によって行われています.

問題文の条件に従ってグラフィカルモデルを書いてみると, $ x_n $ は $ x_1 \dots x_{n-1} $ の値とは独立であることがわかります.

ここで,

\begin{align} \alpha_t (i) = P(x_1 x_2 \dots x_t, s_t = w_i) \end{align}

とします.

$ \alpha_n (i) $ を $ \alpha_{n-1} (i) $を用いて表すことができないか考えてみます.

(唐突感がありますが, $ t = n-1 $とおいて考えてみたらこうなりました)

\begin{align} \alpha_n (i) = \left[ \sum_{j=1}^{c} \alpha_{n-1} (j) a(s_{n-1}, s_n) \right] b(s_{n}, x_{n}) \end{align}

ただし.$ t = 1 $のときは $ \alpha_{1} (i) = \rho_i b(w_i, x_1) $ とします.

得られた確率をよく見ると, $ \alpha_{n} (i) $ は $ P( \mathbf{x}, s_t = w_i ) $であることに気づきます.

つまり,これを $ i $ について周辺化すれば求めたい確率 $ P( \mathbf{x} ) $ を得ることができます.

よって,

\begin{align} P( \mathbf{x} ) = \sum_{i = 1}^c \alpha_{n} (i) \end{align}

となります.

おつかれさまでした.

Nonparametric-Bayesian-Word-Sense-Induction

  • conference: TextGraphs-6 (conference? journal?)
  • authors: Xuchen Yao, Benjamin Van Durme

概要

語義推定タスクに対して,ノンパラメトリックな手法を適用する研究.

前提知識の中で知らなかったこととしては,WSI(word sense induction)とWSD(word sense disambiguous)は違うということ.

後者はあらかじめ決められた語義集合の中で議論を行うが前者は特定の語義集合を仮定していない.

階層ディリクレ過程(以後HDP)を用いて推定した語義と,既存研究で行なわれている潜在的ディリクレ配分法(以後LDA)によって推定した語義の比較を行う.

あらかじめ語義の種類がわかっているデータセットに対してHDPを用いて語義の推定を行い,推定された語義の種類数が実際の語義の種類数とどの程度近いかを確認することで,HDPがこのタスクに対して有効かどうかがわかる.

手法

Feature

Context-Windowを設けてBag-of-Wordsで表現したベクトルを使う.

アーキテクチャ

LDA HDP
トピック数が固定 トピック数が可変

実験

モデル

  • LDAを使ったBrody+ [2009]のモデル
  • HDPを使ったモデル(提案手法)

なお,両方とも文脈窓幅は10で固定.

構文的な情報とかを使った複雑なモデルは対してパフォーマンスの向上に寄与しなかったから普通のLDAを使ったヨみたいなことが書いてある気がする...

テスト

名詞の語義を推定する.

SemEval-2007データセットのWSIデータ(Wall Street Journalのデータから作成されたデータ)を使う.

評価方法

データをMapping, Dev, Testの3つに分割して,Mappingのデータで語義の割り当て(単語に対してCluster IDが割り当てられる)を行う.

そのあと,Cluster IDと語義の対応付けを行う.

学習

語義を推定する名詞の数は35.

モデルの学習に使うデータは2種類(in-domainとout-of-domainとあるが,これはなんだろう(特定のドメインのデータかそうじゃないか?).)

Wall Street Journal(以後WSJ): in-domain

British National Corpus(以後BNC): out-of-domain

実験結果

WSJ(in-domainなデータ)では,B&Lの手法と同等のパフォーマンスであったが,BNC(out-of-domainなデータ)に対しては提案手法の方が有意に良いパフォーマンスを発揮した.これは,語義が多いデータに対しても,提案手法であれば対応できることを示している.

結論

「語義推定をLDAを用いて行った研究は存在するが,LDAは語義の種類の数をあらかじめ決定する必要がある.そこで,我々はデータから語義の種類の数も学習するHDPを用いたモデルを提案し,LDAを用いたモデルとの比較を行った.結果として,HDPとLDAはほぼ同等のパフォーマンスが得られることがわかった.」


本文中の画像は原論文より抜粋している.

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として本体から切り出している(もはや本体とはな状況だが)のもウリの1つらしい.

知識表現

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).

アブストで「今までの文章類似度を計算する手法は似ている部分だけ着目していて,似ていない部分は無視しているが,似ていない部分の情報も重要だよ」みたいなことを言っていてなるほど確かにと思った.

まず,著者は既存の文章類似度の計算の3つの問題点の指摘から始める.

  • 意味的に類似しているが,異なる語彙が用いられている場合に正確に類似度を計算できない

    • Milkov+ (2013)の研究を例としてあげている.論文中でembeddingの手法についての詳しい言及がない(気がする)ので,word2vecを単語ベクトルを獲得するために使っているのかなと思った.
  • 単語レベルではなく,フレーズレベル,構文レベルでも類似度を計算しなければいけない

    • "not related"は単語に分割すべきではなく,フレーズとしてみれば"irrelevant"と似た表現とみなすことができる.
  • 「類似している」という情報ではなく,「類似していない」という情報も活用しなければならない

これらを踏まえ (これらの問題に対処して) モデルを設計する.

手法

  1. 単語を低次元のベクトルで表現する
  2. すべての単語について,semantic matching vectorを計算する(よく分からない)
  3. semantic matching vectorを用いて,単語ベクトルをsimilar componentsとdissimilar componentの2つに分解する(Decompose)
  4. CNNを使って1つの特徴空間に射影する(Compose)
  5. 類似度は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"という1つの単語が"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}

によって,単語ベクトルを類似部分と非類似部分の2つに分解する.

分解を行う関数はRigitな関数(なんて訳せば良いのかわからない,全か無をとる関数)か線形な関数,あと直行ベクトルを使う関数の三種類が挙げられている.

composition

\begin{align} \vec{S} = f_{comp} (S^{+}, S^{-}) \\ \vec{T} = f_{comp} (T^{+}, T^{-}) \end{align}

がっちゃんこ.

CNNによって,2種類のベクトルを1つのベクトル空間に射影する.

畳み込みのフィルターを $$ {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を使ったと書かれていた).

すごい (小学生並の感想).