情報を探す能力が著しく欠如しているため情報検索に入門した

はじめに

随分久しぶりにブログを書いているが、前回投稿したのが3月15日だったので、すでに5ヶ月以上も経過しているということになる。5ヶ月あっても僕の知り合いのニートは技術はあっても社会に還元せず、家族に視線がれいとうビームされながらも田舎で親のスネを齧り、悠々自適なフリーター生活を続けている。羨ましい。
どうでも良いが、今回のブログでは情報検索(Information Retrieval)を取り扱う。また、筆者は自然言語処理にも情報検索にも詳しくなく、数学はおろか算数も怪しい。そのため、解釈や内容に間違いがあった場合は優しく指摘していただけると幸いです。

導入

近年、Google検索は利用者に使いやすいようにと日々進化を続けている。それにも関わらず、僕のような無能にはGoogle検索はオーバーテクノロジーだ。気がついたら検索したい内容を上手く言語化できず「なんかあれ」とか「最高」とか検索キーワードに入れて検索している。そして、僕がオプションで上手く使えるのは「filetype:pdf」だけだが、「Google Scholarを使った方が良くね」と言われるレベルの情弱さである。そこで、そもそもの検索の仕組みを理解した気になることでGoogle検索も使えるようになるのではと考えた。申し訳ないが、読者の方々には私の自慰行為に付き合ってもらう。今回は下記の書物を主な教科書にして勉強を進めていく。

『情報検索と言語処理』
http://amzn.asia/5YazRgz
ブログ更新しなさすぎてamazonアフィリエイトの審査に落ちたの悲しすぎる。

情報検索とは

情報検索と何となくそれっぽい学問を選んだが、果たして情報検索とは何なのか。
『情報検索と言語処理』のP7にはこう書かれている。

情報検索(information retrieval)(広義)
ユーザの持つ問題(情報要求)を解決できる情報を見つけ出すこと

情報検索(information retrieval)(狭義)
ユーザの検索質問(query)に適合する文書(document)を文書集合(document collection)の中から見つけ出すこと

狭義の情報検索は今の検索エンジン(Google, yahoo, bingなど)が当てはまると言える。
ここで、情報要求という言葉が出てきたが、こちらは『情報検索と言語処理』のP3に定義が書かれている。

情報要求(information need)
ユーザがある目的を達成するために現在持っている知識では不十分であると感じている状態

例えば、今AKBにいるのかわからないが「小嶋陽菜」の画像を全て集めたいというユーザの目的を達成するためには「こじはる にゃんにゃん こじぱ ニャロ こじまる こじまるさん 小嶋さん 陽菜 陽菜ちゃん ぱる ぱるさん にゃん なんにゃん」などの愛称(AKB48メンバー 愛称から引用)を全て知らないといけないと感じているという状態だろうか。
もう少し情報要求の段階を細かい分類をTaylorさんが1968年に"Question-Negotiation and Information Seeking in Libraries"という論文で提案していて、下記がその分類となる。(これもP3に書いてある)

 Q_1:直観的要求(visceral need)
現状に満足していないことは認識しているが、それを具体的に言語化して上手く説明できない状態
 Q_2:意識された要求(conscious need)
頭の中では問題を意識できるが、曖昧な表現やまとまりのない表現でした言語化できない状態
 Q_3:形式化された要求(formalized need)
問題を具体的な言語表現で言語化することができる状態
 Q_4:調整済みの要求(compromised need)
問題を解決するために必要な情報の情報源が同定できるくらい問題が具体化された状態

先ほどの「小嶋陽菜」の例でいうと、愛称が分からないということが分かっているのであれば、あとはgoogle先生に「小嶋陽菜 愛称」とでも打って愛称を探して、個々の愛称を画像検索すればいい。そのため、この場合は問題が同定できて、具体的に問題解決の方法が見えている状態なので、 Q_4にあたる。

情報要求が分かったので、情報検索の広義の意味は理解できたと思いたい。次に情報検索の基本的なモデルの図(P7)が整理されていてよかったため、一部手を加えて記載する。

f:id:gat-chin321:20170624161038p:plain
図:情報検索の基本モデル

現実世界の情報とユーザの情報要求の2つがあり、この2つは直接比較することが現状不可能である。
現実世界の情報を解釈した結果が文書として存在していると仮定し、ユーザはユーザの情報要求を検索質問という形で表現する。
どちらもそのままではコンピュータで扱うことが難しいので、内部表現という形に落としこむこと(索引付け)で比較を可能にして、最もマッチする情報を見つけ出す。
狭義の情報検索では、検索質問という形式で与えられることを仮定しているため、ユーザ側の情報要求そのものを考慮していない。
例えば、「なんかまるいやつ」という検索質問が与えられたときに、ユーザが「卵」を想像していても、検索エンジンはそれを考慮して検索を行わない。
検索エンジンに能力がないことを言いたいわけではなく、ユーザ自身の情報要求に対する解釈の精度が検索に大きな影響を与えてしまうため、検索は難しいことが言いたかったわけである。
あまり人の文章を引用するのは好きではないのだが、この辺の定義については勝手に解釈を述べてしまうと大変なことになると考えたため、ほとんど引用という形になってしまった。これらを踏まえた上で学習を進めていく。

今までは具体的にどうやって検索を実現してきたのか?

当時(2012年周辺)では、「文書の内容を表していると考えられる要素(索引語)を文書から取り出して、その集合を使って文書の内容を近似する」ことが一般的なアプローチとして用いられていたらしい。
索引語を取り出す際に問題となるのが、日本語の場合、英語とは違って単語間に空白がないため、機械的に単語を分割することが難しい。
そこで、形態素解析という処理を行って、単語の分割を行う。ただ、形態素解析も精度は100%というわけにも行かないという問題がある。
漢字のように一つの文字が意味を持っている日本語や中国語の場合は、1文字を1つの索引語として使うこともあったらしいが、この場合、意味が多様すぎるため、記事の内容を表現することが難しい。

人手での索引付けの場合

当初は文書から形態素解析で索引語を機械的に抽出した後、人の手で索引語を追加・編集したり、削除したりして、上手く内容を表現できていそうな形に修正する索引付けを行っていたようだ。
しかし、索引付けを人手で行っても、索引付けに一貫性を持たせることが困難(特に複数人の場合)である。複数人で同じ文書の索引付けを行う実験を行ったところ、それぞれの索引付けの一致度はせいぜい30%程度という結果(Cleverdon,1984)になった。

機械的な索引付けの場合

一方で索引付けを機械的に行う方法では同じ一貫性は保つことができるが、機械は意味を理解しない。何の工夫もなければ、同義語や重要度の高い語句が出た時に優先的に結果に表示するなどの対応が難しい。だが、精度に関しては人が行うのと同等かそれ以上の精度を叩き出していたようなので、徐々に一般的になり始めたようだ。
そのため、大まかには下記の流れで典型的な自動索引付けは行われてきた。

(1) 形態素解析による単語の分割
(2) 不要語(stop word)の削除
(3) 接辞の処理
(4) 検索質問拡張
(5) 語の頻度をもとにして索引語に重み付け

上記だけを見ても、自然言語処理の知識のない方からすると、ピンとこないと思う。少なくとも私にはピンと来なかった。そのため、より具体的に説明していく。

(1) 形態素解析による単語の分割

形態素解析Wikipediaにおける定義は下記の通りである。

文法的な情報の注記の無い自然言語のテキストデータ(文)から、対象言語の文法や、辞書と呼ばれる単語の品詞等の情報にもとづき、形態素(Morpheme, おおまかにいえば、言語で意味を持つ最小単位)の列に分割し、それぞれの形態素の品詞等を判別する作業である。
形態素解析 - Wikipediaより引用

定義を見ても良く分からないかもしれないが、形態素解析で行うことは、主に下記の3種類の処理である。
・単語分割
 単語になる位置(単語の境界)を判別し、その場所で文字を区切ることで分割を行う。
 例)「大きな栗の木の下で」->「大きな / 栗 / の / 木 / の / 下 / で」
また、形態素解析の一部である具体的なPython+MeCabを用いた分かち書き(単語分割)の処理の実装例を下記に示す。

import MeCab

document = '労働は人類史上最大の悪であり、我々はこの悪に立ち向かわなければならない。'
tagger = MeCab.Tagger("-Owakati")
# 分かち書きしたら、改行コード\nが後ろに挿入されるので消す。
wakati = tagger.parse(document).strip()
print(wakati)

・品詞推定
 単語分割された文における単語の品詞を当てる。
 例) 「人生に悩み、苦しむ」の悩みは動詞、「悩みのない人生」の悩みは名詞。

・語義の推定
 単語のうち、表記上意味が曖昧な語を特定する。
 例) 「さんぽ」は「散歩」、「三歩」などの漢字への変換により違う意味を持つ語がどれに当てはまるのかを判断する。
 参考資料:形態素解析の過去・現在・未来

また、この他にも形態素解析で行う処理は存在するらしいが、形態素解析という枠組みではどこまでやるのかは曖昧なようだ。

(2) 不要語(ストップワード)の削除

不要語の削除についてだが、不要語とは文字通り、内容を表現するにあたり、不要な語句のことである。
例えば、「、」や「。」、「を」、「ある」などの文の内容に影響を与えないものを取り除く。
理解を進めるため、これを実装した簡易的なソースコードを下記に記述する。

# ストップワードの削除を行うメソッド 
def remove_words(words, stop_words):
    return [word for word in words if word not in stop_words]

stop_words = ['、', '。']
result = remove_words(wakati.split(" "), stop_words)
print(result)

pythonのライブラリでもストップワードの削除を行う機能がついているものもある。有名なものだとscikit-learnとかgensimには引数にリストを渡すとストップワードの削除をしてくれる機能がある。
「なぜ、ストップワードを削除するのか」という点が気になる方もいるかもしれない。この理由は分類する上で余計な単語を削除することにより、メモリの消費を抑えたり、処理を効率化できたり、精度が上がったりするためである。

ストップワードを削除したあとは、ジップの法則(Zipf's law)を用いて全文書において、稀にしか出現しない低頻度語や逆にほぼ全ての文書で存在する高頻度語を削除するのが一般的とされている。なぜこんなのことをするのかというと、実際にデータを分析すると、ストップワードだけでは網羅できない検索を行う上で不要な単語が何かしら出現するはずであり、それらの語に対して対応するためである。低頻度語と高頻度語を削除する理由についてより詳細に説明していく。

・低頻度語について
稀にしか出現しない単語が索引語として用いられたときを考えてみる。3万件の文書中で1回しか出てこない単語があるとすると、その文書集合の中で1つしか出ないことはあまり文書の内容を表現する際に重要でない語であり、網羅性に欠けることから索引語として適切でないとされている。例えば、読んだことはないが、女性誌の記事であまり出現しなさそうな「ディープラーニング」という単語の場合、女性誌の文書を検索する場合「ディープラーニング」は文書を特徴づける単語ではない。一方、「ギャル」という単語なら一部雑誌ではそこそこ出てくると思うので、ギャル系雑誌(?)というような文書群を特徴付ける単語と言えると考えられる。
また、索引語の頻度を索引語の重み(大きいと重要度が高い)として用いる場合、低頻度の索引の重みは自動的に小さくなるため、無視しても検索にはあまり影響がない。そして、索引語の数は少ない方が計算量が少なくなり、メモリ上に配置するデータ量も少なくなるため、システムを構築する際には無視した方が良いとも考えられる。

・高頻度語について
どの文書にでも良く用いられるような頻度で出現するような単語を索引語として使うと、検索する際にどの文書にでも存在する単語なので検索結果としてはどの文書でも表示してしまうことになるため、網羅性が高くなりすぎる。そのため、索引語としては適切でないと考えられる。例えば、先ほどの女性誌の例でいくと「可愛い」という単語はどの雑誌でも出てくると思うので、該当の女性誌がどういう内容なのかを特徴付ける単語ではないと考えられる。

具体的に中程度の頻度をどのような基準で判断するのかというと、下記の2つのZipfの法則(Zipf's law)というものが使われる。

Zipfの第1法則:
 \begin{eqnarray}
r \cdot f = C
\end{eqnarray}
 r: 出現頻度の順位
 f: 単語の出現頻度
 C: 定数
細かい内容は省くが、Zipfの第1法則は文書中の語を出現順位順に並べたときに順位 rと頻度 fの積が定数 Cになるということを経験的に主張したものである。
この式(1)は高頻度の単語には当てはまるが、低頻度の単語については同順位の語が多くなるため、うまく当てはまらない。

下記の図は私が趣味で収集しているとあるクラスタのツイート3万件(一部だけ使った)のデータにおいて、単語ごとの出現頻度を左から降順にソートしたものがある。
x軸のラベルを単語にしているのだが、単語数が多すぎて、真っ黒になってしまっているところは気にしないで欲しい。
f:id:gat-chin321:20170902235845p:plain

from collections import Counter
import matplotlib.pyplot as plt
import matplotlib as mpl

def zipf1(frec, rank):
    c = frec * rank
    return c

# datasetの中の単語を数え上げ
counter = Counter(dataset)
for word, cnt in counter.most_common():
    words.append(word)
    counts.append(cnt)

# 出現頻度の順位をつける
ranks = []
for index, v in enumerate(types.values()):
    ranks += [index+1 for _ in v]

# zipfの第一法則の計算
zipf1_score = [zipf1(cnt, rank) for cnt, rank in zip(counts, ranks)]

# 描画の処理
mpl.rcParams['font.family'] = 'AppleGothic' # 日本語のフォントを読み込む(フォントインストールするの面倒だったので、AppleGothicにした)
fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_xticks([i for i in range(1,len(words)+1)])
ax.set_xticklabels(words, rotation=90,fontsize='small')
# zipfの第一法則の計算結果を描画
ax.plot(zipf1_score)
plt.show()

また、実際にこのデータでZipfの第1法則の Cを計算してみると下記となった。
f:id:gat-chin321:20170701125426p:plain

頻度の低い単語と比べて、頻度が高い単語が少ないためわかりづらいが、左端の部分に一部 Cの値が比較的一定なところがあるため、その部分を拡大してみたものがこちらとなる。
f:id:gat-chin321:20170701131510p:plain

さらに拡大してみたものがこちら。
f:id:gat-chin321:20170701125950p:plain

綺麗に一直線になってくれるのを期待していたが、そうはならなかった。
部分部分で結構な上下はあるが、比較的一定なところが見つかった。不穏な単語が多いが気にしないで欲しい。
実は見つけられていないだけでもっといい感じの場所はあるのかもしれない。

Zipfの第2法則:
 \begin{eqnarray} \frac{F_1}{F_f}=\frac{f(f+1)}{2} \end{eqnarray}
 f: 単語の出現頻度
 F_f: 単語の出現頻度 fの語の異なり数

Zipfの第2法則は低頻度語に対して成り立つ。頻度 fの語の異なり数というのが何なのか分からなかったので、調べたところ、異なり語数とも呼ばれていて、
単語の種類数のことを指しているようだった。*1
つまり、頻度1の異なり語数を出現頻度 fの異なり語数で割った値が \frac{f(f+1)}{2}に等しくなるということだろう。

という訳で実際に計算してプロットして行ってみよう。左辺と右辺をそれぞれプロットすることにした。
f:id:gat-chin321:20170701153936p:plain

この図だとほとんどの語で左辺と右辺が等しくなっているように見えているが、これはy軸の単位が大きすぎるためだ。
そこで、少し拡大してみる。
f:id:gat-chin321:20170701162512p:plain

図をみていくと、高頻度のものはかなり左辺と右辺が離れているが、頻度が低くなるにつれて徐々に値が近づいていくのがわかる。
また、さらに拡大してみたものを下記に示す。
f:id:gat-chin321:20170701154503p:plain

最終的に1.0で一致するが、1.0は式(2)の右辺から考えると頻度1の単語となっていることがわかる。

ちなみにこれらの図は下記のソースにより計算した。

from collections import Counter
import matplotlib.pyplot as plt
import matplotlib as mpl

# zipfの第2法則の関数(left_sideに左辺、right_sideに右辺)
def zipf2(f1_type, frec, ff_type):
    left_side = f1_type/ff_type
    right_side = frec*(frec+1)/2
    return left_side, right_side

words = []
counts = []

# datasetの中の単語を数え上げ
counter = Counter(dataset)
for word, cnt in counter.most_common():
    words.append(word)
    counts.append(cnt)

# 単語の出現頻度ごとの語の異なり数の算出
types = {cnt:[] for cnt in counts}
for cnt, word in zip(counts, words):
    types[cnt].append(word)

# zipfの第二法則の計算
left_sides = []
right_sides = []
for cnt in counts:
    left, right = zipf2(len(types[1]), cnt, len(types[cnt]))
    left_sides.append(left)
    right_sides.append(right)

# 描画の処理
mpl.rcParams['font.family'] = 'AppleGothic'
fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_xticks([i for i in range(1,len(words)+1)])
ax.set_xticklabels(words, rotation=90, fontsize='small')

# 左辺の描画
ax.plot(left_sides, 'b', label='left')

# 右辺の描画
ax.plot(right_sides, 'r', label='right')

plt.show()

Zipfの第1法則は高頻度語に、第2法則は低頻度語に対して成り立つので、両方の式が成り立つ語は中頻度語であると考えようというのが基本的な考え方である。
ただ、この2つの法則をどう反映すれば、中頻度語が抽出できるのかというと、下記の式によってある程度の目安を算出することができる。
 \begin{eqnarray} f =\frac{\sqrt{8F_1+1}-1}{2} \end{eqnarray}
式(1)は同じ順位の語がないという仮定を置いているため、式(1)と式(2)の両方が成り立つ境界を求める場合、式(2)では頻度 fの異なり語数が1であるもののみを考慮すれば良い。つまり、 F_f=1であるから、式(2)より、
 \begin{equation} F_1 =\frac{f(f+1)}{2} \end{equation}
これを fについて解いていく。
 \begin{equation} F_1 =\frac{f^2+f}{2} \end{equation}
 \begin{equation} 2F_1 =f^2+f \end{equation}
左辺と右辺を入れ替えて、右辺を左辺に移行すると
 \begin{equation} f^2+f - 2F_1 = 0 \end{equation}
これを二次方程式の解の公式*2に当てはめると、
 \begin{equation} f = \frac{-1 \pm \sqrt{1-8F_1}}{2} \end{equation}
 F_1 \geq 1であることと頻度に負の値はありえないことから、整理すると
 \begin{equation} f =\frac{\sqrt{8F_1+1}-1}{2} \end{equation}
となり、式(3)が導出される。

今回使ったデータで式(3)を下記のプログラムを使って計算してみたところ、371.88201887460326となった。

from collections import Counter
import matplotlib.pyplot as plt
import matplotlib as mpl

import math
# zipfの法則で中頻度を算出する関数
def zipf(f1_type):
    freq = math.sqrt(8 * f1_type + 1) - 1
    return freq

# 単語の出現頻度ごとの語の異なり数の算出
types = {cnt:[] for cnt in counts}
for cnt, word in zip(counts, words):
    types[cnt].append(word)

# 頻度1の語の異なり数を渡すと、計算結果が返ってくる
print(zipf(len(types[1])))

頻度372周辺が中頻度ということになる。どこまでの範囲を考慮するのかは特に記述はなかったが、
これを参考に任意で境界線を決めてくれということだろうか。

用途がよくわからなかったので、いくつかの論文に目を通してみた。
下記の論文では、ベイズ情報量基準(BIC)を用いて単語の上限と下限を調整した上限・下限の値をzipfの法則で算出した中頻度と見比べた時に、上限と下限の真ん中あたりに中頻度がきていて、最良推定で行ったものよりもうまくバランスが取れていれば良いというような答え合わせに使うような使い方がされている。
http://db-event.jpn.org/deim2009/proceedings/files/B6-6.pdf

下記の論文では、出現数1位から中頻度語までの単語を取り出し、出現数1位から中頻度語までの単語数と同じ数分だけ中頻度語以降の頻度の単語を取り出して使うことで、低頻度語をうまく弾くために使用されている。
http://www.ieice.org/iss/de/DEWS/proc/2004/paper/3-C/3-C-02.pdf

下記の論文では、zipfの法則を中頻度の算出に使うというよりかはデータの性質の説明のために記載されている感じがする。
https://ipsj.ixsq.nii.ac.jp/ej/?action=pages_view_main&active_action=repository_view_main_item_detail&item_id=11187&item_no=1&page_id=13&block_id=8

調査してみた感じでは、特にカチッと良い感じの語を取り出せるような便利なものではないような印象となった。そんな便利なものなら前処理が不要になってるはずなので当たり前といえば当たり前だ。

前処理の全体の話題については下記が詳しいので、ご参考ください。
自然言語処理における前処理の種類とその威力 - Qiita

接辞の処理

語形の多様性を正規化する処理。日本語での接辞処理は形態素解析とほぼ同義となるため、語の境界が曖昧な日本語ではあまり意識されない。しかし、英語のように語の境界が明確で、語が屈折したり、接辞により派生する言語では問題になるらしい。例えば、英語では"Bob plays soccer very well"と"Bob is a good soccer player "という文章では、サッカーをする内容を"player"(名詞)、"plays"(動詞)などのそれぞれ別の品詞で表現することができる。どのような品詞で表現できる。この場合、"player"と"plays"は両方とも"play"に正規化するらしい。
この正規化を行う方法で紹介されているのは下記の3つである。
・Lovinsの方法
・Porterの方法
・Paice/Huskの方法
このうち、『情報検索と言語処理』では、Paice/Huskの方法が取り上げられて詳しく説明されていた。
私としては日本語の文書を検索したいので、ここについてはこの辺で切り上げて次に行きたいと思う。

検索質問拡張

例えば、「お母さん」、「母親」、「ママ」などの表現の多様性(語選択の多様性)に対応するための処理。
『情報検索と言語処理』では、具体的なアプローチについては触りだけだが、ルールベースによる方法とLSI(latent semantic indexing)が紹介されている。
これについては今回は触れないこととする。

語の頻度をもとにして索引語に重み付け

索引語の重要度を付与するために重み付けを行うが、重み行列Wは行列の形で下記のような表現される。
\[
W = \left(
\begin{array}{cccc}
w^1_{1} & w^1_{2} & \ldots & w^1_{n} \\
w^2_{1} & w^2_{2} & \ldots & w^2_{n} \\
\vdots & \vdots & \ddots & \vdots \\
w^m_{1} & w^m_{2} & \ldots & w^m_{n}
\end{array}
\right)
\]
『情報検索と言語処理』では、列が文書 dで行が単語 tで表されている。
 wを決めるための重み付けのアプローチについては下記の方法が紹介されている。
・索引頻度(term frequency)
・IDF(Inverse Document Frequency)
・信号/雑音比(singnal-noise ratio)
・索引語の識別値(term discrimination value)
これらをより具体的に説明していく。

索引頻度(term frequency)

文書 dに出現する索引語 tの頻度 tf(t, d)を重み w^d_{t}として使う方法。つまり、
 \begin{eqnarray} w^d_{t} = tf(t, d) \end{eqnarray}

この重みづけには文書が長くなった場合に他の短い文書と比べて、索引語に対する重みが大きくなってしまうという問題がある。
そのため、下記の計算で正規化することが考えられる。
 \begin{eqnarray} w^d_t = \frac{tf(t, d)}{\sum_{s \in d}tf(s, d)} \end{eqnarray}
式(5)では何をしているのかというと、例えば、「労働 は 人類 史上 最大 の 悪」という文であれば、「労働」という索引語の重みを求める際に、「労働」という索引語の出現頻度(=1)から該当の文書全ての索引語の出現数(=7)で割った相対頻度を求めている。
この例で言えば、「労働」の重みは \frac{1}{7}となる。

IDF(Inverse Document Frequency)

索引語頻度による重み付けは各文書中の索引語の頻度については考慮しているが、全体の文書における索引語の分布を考慮していない。
どの文書でも出現している索引語があった場合、その索引語はそれぞれの文書の内容を表現するのに重要ではないと考えられる。
そこで、下記のIDFの重み付けが利用されることもある。
 \begin{eqnarray} w^d_t = idf(t) = log \frac{N}{df(t)}+1 \end{eqnarray}
 N: 検索対象になる文書集合中の全文書数
 df(t): 索引語 tが出現する文書数
ここで、対数をとっている理由は文書の規模に対してIDFの値の変化を小さくするためである。
この対数をとる効果の検証のため、実際に文書数10件,100件,1000件,10000件の4パターンでのIDFの値を実験して確認する。*3

信号/雑音比(singnal-noise ratio)

情報理論エントロピー(entropy)という尺度を用いることで、ある索引語が文書集合中の各文書における出現数にどれくらい偏って出現するかを数値化する方法。
エントロピー H(P)ある確率変数 Pが事象 {E_1, E_2, ..., E_n}を値でとり、それぞれの事象の生起確率*4 {p_1, p_2,...,p_n}である時、下記の式で定義される。
 \begin{eqnarray} H(P) = - \sum^n_{i=1} p_i log_2 p_i \end{eqnarray}
エントロピーは各事象が一様分布にしたがって生起する時に最大となり、生起確率が偏ると小さくなる。
ちなみに一様分布にしたがって生起する時に最大になることはラグランジュの未定乗数法を用いることで求められる。*5
直感的にはエントロピーが高くなるのは情報を全く含まない最も普遍的な分布である。つまり、全ての事象の生起確率が等しいような生起する事象を予測するのが困難な情報ほどエントロピーが大きくなる。
より具体的な説明については『情報検索と言語処理』の例がとても分かりやすかったので、ぜひ買って読んで欲しい。

では、どうやってエントロピーを索引語の重みに応用していくのか。
まず、ある索引語 tが文書 d_k = {d_1, d_2, ..., d_N}に出現する確率を p^k_tで表す。
この場合、式(7)から確率変数のエントロピー n_tは下記で定義される。
 \begin{eqnarray} n_t = - \sum^N_{t=1} p_t log_2 p_t \end{eqnarray}

この確率 p^k_tは索引語 tの総出現数と文書 d_k中の出現数の相対頻度で推定できるので、
 \begin{eqnarray} n_t = - \sum^N_{t=1} \frac{tf(t, i)}{\sum^N_{j=1} tf(t, j)} log_2 \frac{tf(t, i)}{\sum^N_{j=1} tf(t, j)} \end{eqnarray}
となる。 \frac{tf(t, i)}{\sum^N_{j=1} tf(t, j)}は微妙に式(5)で計算している内容と似ているが、別物であることに注意したい。
式(5)ではある文書での索引語の出現数を文書中の全ての索引語の出現数で割っているのに対し、式(9)ではある文書
での索引語の出現数を文書全体での索引語 tの総出現数で割っている。つまり、式(5)では分母がある文書の全ての索引語の出現数を求めているのに対し、式(9)では文書全体でのある索引語 tの出現数を求めているため、別の計算をしていることを留意しておく必要がある。

これでエントロピーの計算ができたが、これ単体ではある索引語がどれだけその索引語が出現する文書を当てることが難しいのかということが分かるようになった。
ただこれをそのまま何もせず重みとして使うと、エントロピーが大きい索引語が出現する文書ほど当てることが困難になることから、重要でないと考えられる索引語の重みが大きくなってしまうので、あまり好ましくない。そこで、この式(9)の n_tを索引語 tの雑音と呼び、索引語の重みは下記で計算する。
 \begin{eqnarray} w^d_t = s_t = log_2 \sum^N_k=1 tf(t,k) - n_t =  log_2 \sum^N_k=1 tf(t,k) + \sum^N_{t=1} \frac{tf(t, i)}{\sum^N_{j=1} tf(t, j)} log_2 \frac{tf(t, i)}{\sum^N_{j=1} tf(t, j)} \end{eqnarray}
これにより、全文書中の索引語の総和という重みから索引語のエントロピーを引くことで、索引語の重要度が低いものは重みが小さくなり、逆の場合は重みが大きくなるように調整される。

索引語の識別値(term discrimination value)

重みを出したい索引語を入れた時と除いた時の2つの文書 d_i d_jの平均類似度の差を使うことで、索引語の重みを算出する方法。
ここで用いる類似度は0〜1の間の値をとるように正規化されていることを前提にしている。
 \begin{eqnarray} d_{v_t} = \delta(+t) - \delta(-t) \end{eqnarray}
 \sigma(+t): 索引語 tを追加した場合の平均類似度
 \sigma(-t): 索引語 tを取り除いた場合の平均類似度
また、 \sigmaそのものは下記の数式により定義する。
 \begin{eqnarray} \delta = \frac{1}{N(N-1)}\sum^{N}_{i=1} \sum^N_{j=1(i \neq j)} \sigma(d_i, d_j) \end{eqnarray}
 N: 文書集合中の総合文書数
内積
 \begin{eqnarray} \sigma (d_x, d_y) = \sum^T_{i=1}x_i \cdot y_i \end{eqnarray}
・Dice 係数 (Dice coefficient)
 \begin{eqnarray} \sigma (d_x, d_y) = \frac{2\sum^T_{i=1}x_i \cdot y_i}{\sum^T_{i=1}x^2_i + \sum^T_{i=1}y^2_i} \end{eqnarray}
・Jaccard 係数 (Jaccard coefficient)
 \begin{eqnarray} \sigma (d_x, d_y) = \frac{\sum^T_{i=1}x_i \cdot y_i}{\sum^T_{i=1}x^2_i + \sum^T_i y^2_i - \sum^T_{i=1} x_i \cdot y_i} \end{eqnarray}
余弦
 \begin{eqnarray} \sigma (d_x, d_y) = \frac{\sum^T_{i=1} x_i \cdot y_i}{\sqrt{\sum^T_{i=1}x^2_i \times \sum^T_{i=1} y^2_i }} \end{eqnarray}
 x_i: 文書 d_xの索引語 iに対する重みもしくは索引語の有無の2値変数(索引語がある時に1, ない時に0とする重み)
 T: 索引語の総数

この式をそのまま全ての文書ペアに対して計算すると文書の量が多いとかなりの計算量になってしまうため、下記の式で全ての文書の重心と比較する。
 \begin{eqnarray} \bar{tf}(t,c) = \frac{1}{N} \sum^N_{i=1} tf(t, d_i) \end{eqnarray}

TF-IDF重み付け

現在でも簡単な文書の分類などに用いられる索引頻度とIDFを掛け合わせることで組み合わせた重み付けの方法。おそらくこの中では一番有名だろう。
 \begin{eqnarray} w^d_t = tf(t, d) \cdot idf(t) \end{eqnarray}
他にも同様に索引頻度と組み合わせた下記のような重み付けも存在する。
 \begin{eqnarray} w^d_t = tf(t, d) \cdot s(t) \end{eqnarray}
 \begin{eqnarray} w^d_t = tf(t, d) \cdot dv(t) \end{eqnarray}

検索モデルについて

ブーリアンモデル(Boolean retrieval)

論理式で検索に使う質問を表現して検索するアプローチでいわゆる世に出回っているAND検索やらOR検索やらである。これは論理検索(logical retrieval)とも呼ばれる。
例えば、 t_1 AND t_2で検索したいとして、 t_1 t_2がそれぞれを含む文書が下記の通りの時を考える。
 t_1を含む文書集合: {d_1, d_2, d_3, d_4, d_5}
 t_2を含む文書集合: {d_2, d_5, d_8}
この場合、論理式のANDで検索しているため、両方を含む文書を探す。この場合だと {d_2, d_5}が検索結果となる。
高速化したくなった場合は、B木構造やTrie構造などを使ったりして高速化するらしい。
ブーリアンモデルにおける欠点は索引語の重要度を扱えないため、検索結果をスコアリングして順位付けができないという点である。

ベクトル空間モデル

下記のような縦が文書、横が単語として対応しているように索引付けを行った重みの行列で表現して、文書のベクトルと質問文(クエリ)のベクトルの間の類似度を用いtることで検索質問に似ているものを提示するアプローチ。
\[
W = \left(
\begin{array}{cccc}
w^1_{1} & w^1_{2} & \ldots & w^1_{n} \\
w^2_{1} & w^2_{2} & \ldots & w^2_{n} \\
\vdots & \vdots & \ddots & \vdots \\
w^m_{1} & w^m_{2} & \ldots & w^m_{n}
\end{array}
\right)
\]

確率モデル

確率モデルのアプローチとして提示された下記の3パターンが紹介されている。

MaronとKuhnsのアプローチ

下記の2点を仮定したアプローチ。

  • ある文書がある検索質問に対して適合するかどうかが確率的に決定されること
  • ある文書が検索質問に適合するかどうかは他の文書がその検索質問に適合するかどうかとは独立であること(文書間の独立性)

もし、ある文書がある検索質問に適合する確率を調べたければ、ある検索質問を使ったユーザーのうち、その文書がその検索質問に適合すると判断したかで求められる。ただ、検索質問のバリエーションは無数にあるので、全ての検索質問を数え上げることは現実的ではないため、文書に人手でつけたディスクリプタ(discripter)と呼ばれる一種の索引語に対して推測されるものにのみ絞って確率を推定する。
ディスクリプタが何なのかよく分からなかったので軽く調べたら下記のサイトでそれっぽい定義が見つかった。

ディスクリプタとは、実際の索引に使用される語のことです。ある概念を表す用語が複数存在する場合には、それぞれの用語で表現された情報を一箇所に集めるためにディスクリプタが選定されます。それ以外の同義語(略語や異表記も含む)は、ディスクリプタに関連付けて登録されています。
索引情報(キーワードなど)|医中誌データベース情報|医中誌ユーザ向け情報|医学中央雑誌より参照

また、『図書館情報学用語辞典』(ISBN:4621043625)では下記の通り定義されているらしい。

シソーラスにおいて、ある概念を索引付けする際、一貫して用いると決められた語その他の記号。シソーラスにおける優先語であり、索引の一貫性保持、検索の再現率向上を目的に設定される。
ディスクリプタとは - はてなキーワードより参照

色々と定義を見たところ、文書の内容を表していると考えられる重要語をディスクリプタとして登録しているということだと理解したけど、あってるのだろうか。

そして、MaronとKuhnsは考えたこのアプローチは一貫性を持って推定することは困難であり、実験により有効性が試されることはなかったらしい。
ただ、なぜこのアプローチが一貫性を持って推定することは困難なのか説明がなく分からなかったが、多分ディスクリプタを人手でつけるからだろうなという想像をした。

元の論文はこちらにあるけど、29ページと量が多く諦めた。暇な時に読もうと思った。

On Relevance, ProbabiUstic Indexing and Information Retrieval
http://ctp.di.fct.unl.pt/~jmag/wamse/papers/1960.On%20Relevance,%20Probabilistic%20Indexing%20and%20Information%20Retrieval.pdf

RobertsonとSparck Jonesのアプローチ

下記2つの仮定を置いて、検索質問中の索引語を基礎として確率を計算するアプローチ。

  • 文書が検索質問に適合しようがしまいが、個々の索引語の出現は独立の事象である。
  • 文書が検索質問に適合する確率は全ての索引語の情報を用いて計算されるべきである。

上記の仮定から
 g(d) = log \frac{P(R|d)}{P(\bar{R}|d)}
が導出できる。これをベイズの公式 P(Y|X)=\frac{P(Y)P(X|Y)}{P(X)}を使うと
 P(R|d) = \frac{P(d)P(d|R)}{P(R)} P(\bar{R}|d) = \frac{P(d)P(d|\bar{R})}{P(R)}より、
これを代入すると
 g(d) = log \frac{P(d)P(d|R)}{P(R)} \cdot \frac{P(\bar{R})}{P(d)P(d|\bar{R})}
整理して
 g(d) = log \frac{P(d|R)}{P(d|\bar{R})} + log \frac{P(R)}{P(\bar{R})}
となる

そのあと色々あって、文書 dの適合度は下記が導出される。*6
 g(d) = \sum_{t_i \in T} log \frac{p_i(1-\bar{p_i})}{\bar{p_i}(1-p_i)}
 t_i:索引語
 T:検索質問に含まれる索引語集合の部分集合
 p_i:検索質問に適合する文書に索引語 t_iが付与されている確率
 \bar{p_i}:検索質問に適合しない文書に索引語 t_iが付与されている確率

終わりに

情報検索の基礎的な内容について実践を踏まえて、気の赴くままに書き綴った。
当初の予想通り、ある程度情報検索について知ることができたが、情報を探す能力が強化された気は全くしない。
ただ、情報検索については興味が湧いてきたので、もっと最新の研究を調べたいという気持ちは高まった。
まだあまり調べられていないが、おそらく分散表現が主流になっていそうな気がしている。
『Analysis of the Paragraph Vector Model for Information Retrieval』を読んでみたら割と面白かったので、気が向いて実装できれば記事をまた書きたい。(書くとは言っていない)

*1:統計的テキスト解析(5)~統計法則と指標~とかhttp://www.jaist.ac.jp/~kshirai/lec/i223/10.pdf

*2:二次方程式 ax^2+bx+c(a \neq 0)の解は \frac{-b \pm \sqrt{b^2-4ac}}{2a}

*3:もっといい実験の仕方があれば、教えてください。

*4:その事象が起こる確率のこと

*5:解説はこのページが詳しい 情報がない - あざらしとペンギンの問題

*6:導出についての詳しい情報は『情報検索と言語処理』を買ってください。

アホが自動運転をしたら盛大に事故るので気をつけたほうがいい

はじめに

最近は社会的にも自動運転という技術が注目されており、多くの自動車メーカーが必死で研究開発を行なっている。
Googleも手を出してはいたが、諦めた的なニュースをどこかで見たのも記憶に新しい現時点では色々な課題があり、まだまだ実現が難しいと考えられている分野だと思う。
私は免許こそ持ってはいるが、自分への自信が全くないので人をはねてしまうのではないかと不安になってしまうため、車を運転することが大の苦手だ。そんな私にとっては自動運転とは夢の技術であり、マイスイートハニーと私を乗せ、綺麗な海岸沿いを華麗に自動運転してくれる超クールな車を手に入れたいと思うのは仕方がないことだと思う。
そこで、今回は車の購入なしでかつ、年間8万円の自動車保険に入らずに自動運転を楽しめる超エキサイティンなツール(?)を紹介する。

udacity drive講座

udacity driveとは

知っている人は知っているかとは思うが、現在udacity driveという下記の講座があり、そこでは自動運転とそれに必要な機械学習の技術を学べるような内容となっているっぽい(受ける予定も特にないので、あまり詳しく調べていない)
www.udacity.com
この講座の受講料は800ドルと比較的お安い講座な方ではあると思うが、日々クレジットカードの引き落としで毎月15000円くらいしか手持ちに残らない極貧民には少しお高い。
だが、現在この講座で使用されるっぽい自動車シミュレーターのソースコードが一部github(下記)にて公開されている。本当に素晴らしい。
github.com

講座で使う機械学習の環境構築

環境構築は極めて簡単。下記でanacondaの環境は整う。
(参照:https://github.com/udacity/CarND-Term1-Starter-Kit/blob/master/doc/configure_via_anaconda.md)

git clone https://github.com/udacity/CarND-Ter​​m1-Starter-Kit.git
cd CarND-Ter​​m1-Starter-Kit
conda env create -f environment.yml
conda info --envs
source activate carnd-term1

anacondaが嫌な方向けにdockerイメージも用意されている。
dockerはあまりよくわからないので、やり方は下記を参照して欲しい。
CarND-Term1-Starter-Kit/configure_via_docker.md at master · udacity/CarND-Term1-Starter-Kit · GitHub

講座で使う自動車シミュレーターのインストール

さて、次は自動車シミュレーターのインストールに移りたいと思う。
下記にインストールの仕方が載っている。コンパイル済みのものもあるが、Mac初心者なので「身元がわからないから開いてやらねー」という感じのエラーが出てよくわからなかったので、ここでは説明しない。
github.com

1. 下記のgit lfsをインストールしてローカルにダウンロードする。
Git Large File Storage - Git Large File Storage (LFS) replaces large files such as audio samples, videos, datasets, and graphics with text pointers inside Git, while storing the file contents on a remote server like GitHub.com or GitHub Enterprise.

git lfs clone https://github.com/udacity/self-driving-car-sim.git

2. Unityを使っているので、インストールがまだなようであれば、Unityをインストールする。
3. Unityを起動して、self-driving-car-simフォルダを選択してロードする。
4. 左下の[プロジェクト]タブに移動し、Asset/1_SelfDrivingCar/Scenesフォルダに移動してSceneをロードします。
湖トラックを走りたい場合は、LakeTrackTraining.unityファイルをロードする。
5. 再生ボタンのようなものをクリックすると、ゲームがスタートする。

とここまでで簡単にゲームができるまでにはなっていると思う。
ちなみに操作方法は上矢印で進む、下矢印でバック&ブレーキ、左右で曲がるというシンプルなものになっている。

運転データの作り方

ゲームを開始すると、右上にRECORDと記載された赤丸がある。そこをクリックすると運転データの保存先の選択画面が出る。
ここで、保存したい場所を選択して、[select]ボタンを押し、もう一度右上の赤丸をクリックすると赤丸が一時停止のアイコンに変わる。そうなったら、運転データの保存が開始されている状況となっている。
ある程度運転データが取れたら、右上の一時停止のアイコンをクリックする。すると、リプレイみたいなのが流れ始めて、順次ファイルへと保存されていく。

自動運転とは?

自動運転をさせるためのスクリプト

この自動車シミュレーターを用いて、自動運転を実現するためのスクリプトは下記にある。
github.com

具体的には、次の2つのファイルがアップロードされている。
・video.py(録画用のスクリプト
・drive.py(車を運転するスクリプト

video.pyを動かすには下記のパッケージが必要なので、インストールすべし。
Installing imageio — imageio 2.1.2dev documentation
インストールしたら、pythonを起動して、下記を実行する。

>>> import imageio
>>> imageio.plugins.ffmpeg.download()

README.mdを読む限りはこの2つだけではなく、下記のファイルを作ってもらいたいらしい。
・model.py(モデルの作成と訓練に使用されるスクリプト
・model.h5(訓練されたKerasモデル)

このmodel.pyとmodel.h5をどのようにして作ればいいのかを考える。
drive.pyを確認してみると、何やらそれっぽいmodel.predictがある。

@sio.on('telemetry')
def telemetry(sid, data):
    if data:
        # The current steering angle of the car
        steering_angle = data["steering_angle"]
        # The current throttle of the car
        throttle = data["throttle"]
        # The current speed of the car
        speed = data["speed"]
        # The current image from the center camera of the car
        imgString = data["image"]
        image = Image.open(BytesIO(base64.b64decode(imgString)))
        image_array = np.asarray(image)
        steering_angle = float(model.predict(image_array[None, :, :, :], batch_size=1))

        throttle = controller.update(float(speed))

        print(steering_angle, throttle)
        send_control(steering_angle, throttle)

send_controlに操舵角度(steering_angle)とスロットル(throttle)の情報を送れば動くっぽいことがわかる。
READMEにも画像データから操舵角度を予測するモデルを設計、訓練、検証すると書いているし、drive.pyにmodel.predictによる予測値が格納されているのは操舵角度だけなので、操舵角度を予測するのが目的で正しいはず。
※操舵角度だけでなく、スロットルとかも予測させることで難易度を高めることはできそうだが、ここでは取り扱わないことにする。

KerasどころかChainerもろくに触っていない初心者がとりあえず、書いてみたのが下記のコードとなる。

import numpy as np
from PIL import Image
import csv

from keras import backend as K
from keras.models import Sequential
from keras.layers import Dense, Dropout, Activation, Flatten
from keras.layers import Convolution2D, MaxPooling2D
from keras.optimizers import Adam
from keras.preprocessing.image import load_img, img_to_array

batch_size = 32
nb_classes = 1
nb_epoch = 5 

# 入力画像の大きさ
img_rows, img_cols = 160, 320
# 畳み込みフィルタの値
nb_filters = 32
# max poolingのサイズ
pool_size = (2, 2)
# 畳み込みカーネルのサイズ
kernel_size = (3, 3)

imgs = []
val = []
# とりあえずcsvのログを開く
with open("./data/driving_log.csv","r") as f:
  reader = csv.reader(f)
  for row in reader:
    # リストで画像を格納する
    imgs.append(np.array(Image.open(row[0])))
    # 操舵角度の情報を格納する
    val.append(np.float32(row[3]))
# numpyでappendを頑なに拒み、ここで変換するアプローチをとった
val = np.array(val)
imgs = np.array(imgs)

input_shape = (img_rows, img_cols, 3)

# この辺はKerasのチュートリアルのCNNの実装をパクった記憶がある
model = Sequential()
model.add(Convolution2D(nb_filters, kernel_size[0], kernel_size[1],
                        border_mode='valid',
                        input_shape=input_shape))
model.add(Activation('relu'))
model.add(Convolution2D(nb_filters, kernel_size[0], kernel_size[1]))
model.add(Activation('relu'))
model.add(MaxPooling2D(pool_size=pool_size))
model.add(Dropout(0.25))

model.add(Flatten())
model.add(Dense(128))
model.add(Activation('relu'))
model.add(Dropout(0.5))
# よくわからんけどとりあえず、Denseで1次元の出力作ればいいだろと思った結果
model.add(Dense(nb_classes))
# よくわからんけど(ry
model.add(Activation('linear'))
adam = Adam()
model.compile(loss='mean_squared_error', optimizer=adam)
# なんか画像のCNNで正規化してるのを見つけたので、なんとなく追加した気がする
imgs = imgs.astype('float32')
imgs /= 255

model.fit(imgs, val, batch_size=32, nb_epoch=nb_epoch)
model.save('model_data.h5') 

ログはdriving_log.csvという名前のcsvファイルとして指定した場所に保存され、中身の要素は多分下記のように並んでいる。

列の情報 左側のカメラ 中央のカメラ 右側のカメラ 多分操舵角 わからん わからん 多分速度
データの型 画像ファイルへの絶対パス(文字列) 画像ファイルへの絶対パス(文字列) 画像ファイルへの絶対パス(文字列) 数値 数値 数値 数値

7000枚程度の画像データをCPUで走らせて、待つこと約4日。モデルが完成!
実際に走らせてみる。走らせる方法は簡単で、シミュレーターを起動し、[ESC]キーを押して、AUTONOMOUS MODEを選択し、下記のコマンドを実行する。(順序は逆でも問題ない)

python drive.py [作成したKerasのモデル] [ここにディレクトリを指定すると正面のカメラ画像が出力される]

python video.py [正面カメラの画像を置いてあるディレクトリ]を指定することで、mp4の動画データを作成できる。

結果

出来上がった録画データをGoogleフォトにアップロードした結果がこれである。
https://goo.gl/photos/pXqraNuZz24CV5W98

心なしか左に曲がってはいる気がするが、最終的には急カーブを曲がり切れず、湖にドボンしてしまった。
ディープラーニング弱者には自動運転なんて夢のまた夢ということがわかったので、これから精進していきたいと思った。
とりあえず、皆さんもチャレンジしてみてはいかがだろうか。私はもうDeep Learningはいいです。GPU買ったらやります。

参考文献

Kerasのドキュメント
Keras Documentation

機械学習モデルの予測結果を説明するための力が欲しいか...?

はじめに

最近はAIや機械学習などの単語がビジネスで流行っていて、世はAI時代を迎えている。QiitaやTwitterを眺めているとその影響を受けて、世の多くのエンジニアがAIの勉強を始め出しているように見受けられる。

さらに、近年では機械学習のライブラリも充実しており、誰でも機械学習を実装することができる良い時代になってきた。

その一方で、特徴選択を行い精度を向上させたり、機械学習の出した答えがどの特徴に基づいて判断されたのかを理解したりするには、モデルに対する理解やテクニックが必要となる場合も多々ある。複雑なモデルになると人間には解釈が困難で説明が難しい。近頃流行りのDeep Learning系のモデルだと頻繁に「なんかよくわからないけどうまくいきました」となっていると思う。

一般的なエンジニアとしては、この点が割と課題なんじゃないかと勝手に思っている。というか、私が課題に感じている。(特に実業務で機械学習していない上に、エンジニアでもないが)

そんなわけで、今回はこの課題を解決するためのツールであるLIME(Local Interpretable Model-agnostic Explainations)が興味深かったので、紹介していこうかと思う。
※本記事はLIMEのアルゴリズムの説明となるため、LIMEを実際に利用したい方はGitHub - marcotcr/lime: Lime: Explaining the predictions of any machine learning classifierpythonのライブラリインストール方法とチュートリアルが載っているので、そちらをご参照ください。

モデルの説明とは何か

LIMEの紹介に移る前に機械学習モデルを説明するとはどういうことなのか整理していきたい。
機械学習モデルの説明には下記の説明の2種類が考えられる。

  • explaining prediction(予測の説明)

データ一つに対する機械学習モデルの分類器による予測結果に対して、どうして分類が行われたのかを説明すること。(下記の図はイメージ)
f:id:gat-chin321:20170107164420p:plain
(出典: https://arxiv.org/pdf/1602.04938.pdf)

  • explaining models(モデルの説明)

分類器がどういう性質を持っているのかを説明すること。
https://d3ansictanv2wj.cloudfront.net/figure2-802e0856e423b6bf8862843102243a8b.jpg
(出典: Introduction to Local Interpretable Model-Agnostic Explanations (LIME) - O'Reilly Media)

LIMEはこのうち、explaining predictionを行うためのアルゴリズムである。
explaining modelsについては、SP-LIMEと呼ばれるアルゴリズムが論文に記載されているので、そちらを参照されたし。(気が向けば、SP-LIMEについても記事を書く)

LIME(Local Interpretable Model-agnostic Explainations)の紹介

LIMEとは?

KDD2016で採択された『“Why Should I Trust You?” Explaining the Predictions of Any Classifier』というタイトルの論文で発表されたアルゴリズム。分類器がどのように判断してラベリングを行なったのかを人間でも解釈できるような形で提示してくれる。
このアルゴリズムはあるデータを分類した結果、それぞれの特徴がどの程度分類に貢献しているかを調べることで分類器の予測結果を説明している。また、分類器の予測結果を用いるため、任意の分類器に適用できる特徴がある。

LIMEのアイデア

データxの周辺からサンプリングしたデータを用いて、説明したい分類器の出力と近似するように解釈可能な(かつ単純な)モデルを学習させる。その後、得られた分類器を用いて分類結果の解釈を行う。下記がイメージ図(論文から抜粋した図を編集)。

f:id:gat-chin321:20170106191925p:plain
(出典: https://arxiv.org/pdf/1602.04938.pdf)

説明用分類器の学習方法

説明用分類器 gはデータxの周辺でfの結果と近似するようにしたい。
そうするために、下記の目的関数を利用して学習する。

{\displaystyle 
\DeclareMathOperator*{\argmin}{arg\,min}
\begin{equation}
\xi(x) = \argmin_{g \in G} L(f, g, \pi_x) + \Omega(g)
\end{equation}
}

  • G : 解釈可能なモデルの集合
  • g : Gのうちの一つのモデル。例えば、線形モデルなど
  • f : 説明したい分類器
  • \pi_x : データxとの距離
  • {\displaystyle L(f, g, \pi_x)} : データxの周辺でfgの結果がどれだけ違っているか(Lは損失関数ともいう)
  • {\displaystyle \Omega(g)} : 説明用分類器gの複雑さ

上記の内容から、\xi(x)はデータxの周辺でfgの結果についての食い違い{\displaystyle L(f, g, \pi_x)}と説明用分類器gの複雑さの和を最小にする g の集合を求めるものであると言える。
ここで、{\displaystyle \Omega(g)}はテキスト分類の場合、解釈可能なモデルの特徴表現を単語の有無{0,1}のBag-of-Words法(単語袋詰め)とし、単語の数(次元数)に限度Kを設定することで、説明が解釈可能であることを保証するためのものらしい。
画像データの場合はsuper-pixelsと呼ばれる任意のアルゴリズムを使用して計算されるものを用いて解釈可能なモデルの特徴表現とする。
ここで、この特徴表現は{0,1}の2値で表され、1は元のsuper-pixels、0はグレーアウトされたsuper-pixelsを示す。
ここまでで\xi(x)について、何となくというレベルでは理解ができたと思いたい。
そこで、次は{\displaystyle L(f, g, \pi_x)} の数式についても見ていこう。

{\displaystyle 
L(f, g, \pi_x) = \sum_{z,z' \in Z } \pi_x (z) (f(z) - g(z'))^2
}

  •  Z :  xの周辺のデータの集合
  •  z' : 非ゼロ要素を一部だけ含むサンプリングにより生成された2値のスパースな点。

  z' \in \{0,1\}^dで定義される

  •  z :  z'を用いて復元された元のサンプルの特徴表現。 z \in R^dで定義される

この式を見る限り、 xの周辺のデータにおける\pi_x (z)で重み付けした残差平方和を出している。
残差平方和自体は正解データ(今回の場合、説明したい分類モデルの予測結果)と推定モデルの予測結果との間の不一致を評価する尺度なので、わかりやすいかと思う。
また、\pi_x (z)で重み付けしている理由について理解するため、\pi_x (z)の式を見ていこう。

{\displaystyle 
\pi_x (z) = exp\Bigl(\frac{-D(x,z)^2}{\sigma^2}\Bigr)
}

  •  D(x,z) :  x zとの距離関数(例えば、テキストならコサイン類似度、画像ならL2ノルムなどを利用する)
  •  \sigma : 指数カーネルカーネル

\pi_x (z)の式はカーネル関数であり、xとzの2変数間の類似度を算出している。\pi_x (z)はテキトーに0から1までの値を入れて見て計算すればわかると思うが、サンプルが近ければ近いほど値が小さくなる。これで重み付けすることで、 x zとの距離が近いサンプルの場合は損失{\displaystyle L(f, g, \pi_x)}が小さくなりやすくなり、逆に距離が遠いサンプルの場合は損失が高くなる。この重み付けのおかげで、ロバストなモデルとなっている。
最後は\Omega(g)について掘り下げていく。\Omega(g)の式を見ていこう。

{\displaystyle 
\Omega(g) = \infty \mathbb{1} [||w_g||_0 > K ]
}

\Omega(g)は利用する特徴がたかだか単語数(もしくはsuper-pixels)K程度だけとすることを示しているっぽい。
利用する特徴\Omega(g)の選択は、方程式\xi(x)から直接解くことで実現することは難しい。
そのため、まず著者らがK-Lassoと呼んでいる、Lassoで正則化パスを使用して利用する特徴をK個選択し、最小二乗法を介して重みを学習する方法によって、利用する特徴\Omega(g)の選択についての解と近似させる。
これにより、方程式\xi(x)を解くことができるようになるため、線形モデル(Githubのコードを読む限りではRidge回帰)で学習を行う。
この学習した線形モデルの偏回帰係数を確認することで、選択された特徴について、どれだけ分類に貢献しているかの説明を行うことができる。

ここまで、説明した内容が下記の図のAlgorithm 1 である。
f:id:gat-chin321:20170107152919p:plain
(出典: https://arxiv.org/pdf/1602.04938.pdf)

Algorithm 1 は個々の予測についての説明を生成するので、その複雑さはデータセットのサイズに依存するのではなく、 f(x)を計算する時間とサンプル数 Nに依存するらしい。

検証と考察

検証もどき

今回はマルウェアと正常なプログラムのAPIコールのデータセットが手元にあったので、著者らのLIMEパッケージを使ってみることにした。
データセットは下記からとってきたものだ。
Malicious datasets * - Csmining Group

データセットの内容はファイル形式がcsvマルウェアの数が320検体、正常なプログラムの数が68検体という微妙な数となっている。

簡単な検証の結果は下記の通りだった。
github.com

検証用にランダムフォレストを使ってマルウェアと正常なプログラムを分類した。
ランダムフォレストを選んだ理由は、直線ではない分離境界を引いてくれてかつ、そのモデル自体が重視している特徴を出せるからだ。他にいい分類器があれば教えていただきたいところ。
脳細胞が死んでいるので、データを学習用(マルウェアが310検体と正常なプログラム68検体)とテスト用(マルウェアが10検体)に手で分けた。
そのテスト用の予測結果はf1_scoreが1.0となった。マルウェアと正常なプログラムのAPIコールを用いた分類は割と線形分離可能なものが多い印象なので、交差検証とかしていない上に、テスト数も少ないのでこんなもんではあるとは思う。

考察もどき

結果の考察だが、LIMEで出力された "GetFileAttributesW"、"GetFullPathNameW"、"GetLongPathNameW"
などの特徴が、ランダムフォレストの特徴ランキングの上位に食い込んでいることがわかる。
LIMEで出力されるのは、そのデータ単体のどの特徴を重視して分類したかであるexplaining predictionsにあたり、ランダムフォレストの特徴ランキングは多分explaining modelsなので、厳密に比較すべきではないかもしれない。
しかし、モデル自体が重視している特徴はexplaining predictionsの上位に来ても直感的にはおかしくないと思うので、いい感じになんか説明できている気がする。

参考文献

LIME論文:

“Why Should I Trust You?” Explaining the Predictions of Any Classifier
https://arxiv.org/pdf/1602.04938.pdf

LIMEコード:

github.com