Paragraph Vector DBOWの憂鬱

はじめに

この記事は Deep Learningやっていき Advent Calendar 2017 - Adventar の24日目の記事となります。

メリークリスマス。お久しぶりの投稿となります。本日はクリスマスイブとなりますが、皆さんはいかがお過ごしでしょうか。

私は一人寂しくクリスマスパーティーの準備(寿司を握る)をしたり、自分で設定した締め切りに追われながらもブログを書いたりして過ごしておりました。

不慣れなDeep LearningでAdvent Calendarに参加してみるというやや無謀な挑戦をしてみたわけですが、今回は『Analysis of the Paragraph Vector Model for Information Retrieval』を読んだので、自らの勉強の為にブログに書きます。

この記事はコツコツ書きためていたものなのですが、途中で「Paragraph VectorってDeepではなくね?」と思い、木構造のLSTMで書き始めましたが間に合いそうにないので、比較的間に合いそうなこちらを投稿することにしました。浅いのにDeepを語ってしまってごめんなさい。

本記事の内容ですが、論文の内容をできるだけ自分の感想を交えて書いただけなので、真面目に勉強したい方は論文を読んだほうが良いと思います。

Paragraph Vector

概要

Paragraph Vectorは『Distributed Representations of Sentences and Documents』で提案されている文書の特徴ベクトルを表現できるようにword2vecを拡張したアルゴリズム

この論文ではParagraph VectorのBag of Wordsバージョン(PV-DBOW)とParagraph VectorのDistributed Memoryバージョン(PV-DM)が提案されている。

gensimのDoc2Vecで実装されているアルゴリズムであり、こちらの名前の方が有名になってしまっているような気がする。『Analysis of the Paragraph Vector Model for Information Retrieval』の論文で取り上げられているのはPV-DBOWなので、今回はPV-DBOWのみを取り上げて簡単に説明する。

PV-DBOW

Word2Vecのおさらい

Paragraph VectorはWord2Vecの拡張とのことなので、一旦Word2Vecについておさらいする。下記の図を見ていただこう。

f:id:gat-chin321:20171224131110p:plain
(図は『Efficient Estimation of Word Representations inVector Space』より引用)

これはSkip-gramと呼ばれる学習方法で、今回取り上げるDBOWの元となっているアルゴリズムである。

下記の記事が直感的にわかりやすいので参考にしてほしい。

絵で理解するWord2vecの仕組み - Qiita

Word2Vec のニューラルネットワーク学習過程を理解する · けんごのお屋敷

Word2Vecでは純粋に学習させると結構な時間がかかってしまう。この問題を解決するため、階層的ソフトマックスや負例サンプリングのどちらかが用いられる。

今回は負例サンプリングのみを使うため、そちらのみを簡単に説明する。

負例サンプリングは「周辺単語の入力から単語を予測する」というタスクから「単語が実データの確率分布かノイズの確率分布かのどちらに生成されたものなのかを予測する」ように置き換えて、ニューラルネットワークを学習させることで高速化する。

これらの具体的な実装については下記のChainerのexampleで公開されている。
chainer/train_word2vec.py at master · chainer/chainer · GitHub

tensorflowは使ったことがないので、よくわからないがあるっぽい。
tensorflow/word2vec_basic.py at r1.2 · tensorflow/tensorflow · GitHub

PV-DBOWの概要

PV-DBOWは下図のようにニューラルネットワークが設計されている。

f:id:gat-chin321:20171224131417p:plain

(図は『Distributed Representations of Sentences and Documents』]より引用)
先ほどのSkip-gramとネットワークの形が似ていることがわかるかと思う。何が変わったのかというと入力部分が文書IDとなった点だ。

f:id:gat-chin321:20171224131537p:plain

つまり、文書IDを入力として、文書内の共起の情報をスライドさせながら埋め込んでいくことで最大公約数的な文書全体の意味を重みに埋め込んでいっているっぽい。
これにより、word2vecによりベクトル化した単語ベクトルのような形で文書のベクトル表現が得られることがわかる。

公式ではないが、PV-DBOWのChainerでの実装は下記のURLで公開されている。
GitHub - monthly-hack/chainer-doc2vec: A Chainer implementation of doc2vec

PV-DBOWの弱点

簡単に説明したところで、PV-DBOWのソフトマックスを用いた出力部分の式をみていこう。
 \begin{equation}
P(w|d) = \frac{exp(\vec{w} \cdot \vec{d})}{\sum_{\acute{w} \in V_w} exp(\vec{\acute{w}} \cdot \vec{d})}
\end{equation}

 P(w|d): ドキュメント dを与えられた時に単語 wが出力される確率

 w: 単語

 d: 文書

 \vec{w}: 単語のベクトル

 \vec{d}: 文書のベクトル

 V_w: 語彙集合

これを負例サンプリングで学習させる場合、下記のような式となる。

  \begin{equation}
l = \sum_{w \in V_w} \sum_{d \in V_d} \#(w, d) log(\sigma(\vec{w} \cdot \vec{d})) + \sum_{w \in V_w} \sum_{d \in V_d} \#(w, d) (k \cdot E_{w_N \sim P_{V}} )
\end{equation}

 \vec{w}: 単語のベクトル

 \vec{d}: 文書のベクトル

 V_w: 語彙集合

 V_d: 文書集合

 k: 負例サンプリングの数

 E_{w_N \sim P_{V}} : ノイズ分布  P_{V} が与えられた時の  log \sigma(- \vec{w_N} \cdot \vec{d}) の期待値

 \#(w, d): ある単語  w の文書  d 内での出現回数

 \sigma(x): シグモイド関数  \sigma(x) = \frac{1}{1+e^{-x}}

文の長さの偏りによる過学習に対する改善

PV-DBOWを検索モデルに適用した場合、Robust04のタイトルをクエリにした際に検索された上位の文書内の語数の傾向として、比較的短い文書が検索結果として表示されやすいという特徴があることが下記の図からみて取れる。

f:id:gat-chin321:20171224131629p:plain
(図は『Analysis of the Paragraph Vector Model for Information Retrieval』より引用)

また、この図ではepoch数が増れば増える分だけその傾向が強くなっていることもわかると思う。
なぜこのような結果になったのかを考えていこう。
まずepoch数が増えれば増えるほど短い文書が表示されやすいのは、勾配計算が原因であると考えるのが自然だと思う。そこで勾配の計算式がどうなっているのか考えてみよう。ある文書dに関する目的関数の偏微分は下記の式で計算される。

 \begin{equation}
\frac{\partial l}{\partial d} = \sum_{w \in V_{w}} \# (w, d) log (\sigma (-\vec{w_N} \cdot \vec{d}))\vec{w} - \sum_{w \in V_w} \# (w, d)(k \cdot E_{w_N \sim P_{V}} \vec{w_N})
\end{equation}

 w_N: ノイズ分布に従ってランダムにサンプリングされる単語

 \vec{w_N}: サンプリングされた単語のベクトル

この数式からdの勾配は単語ベクトルの加重和により求められていることがわかる。そのため、単語数の少ない短い文書の場合、その勾配が全ての単語ベクトルから遠くないところに収束してしまう。したがって、短い文書同士も遠くない方向に収束してしまっており、短い文書が出やすくなると考えられる。

また、epochが増えれば増えるほどその傾向が強くなるのは、epochが増えた分、短い文書は単語ベクトルとの距離がやや離れるが、長い文書については単語ベクトルとの距離が大幅に離れることになる。つまり、短い文書は検索用のクエリーのように短い文書との距離が近く、逆に長い文書は短い文書との距離が遠くなりやすいと言える。

学習のepoch数をそれぞれ異なる値にして学習してみて、文書ベクトルのノルムと文書の長さの関係をグラフにしたものが下記の図である。

f:id:gat-chin321:20171224131754p:plain
(図は『Analysis of the Paragraph Vector Model for Information Retrieval』より引用)

この図はx軸が文書の長さ(つまり、単語数)で、y軸が文書ベクトルのノルムを表しており、青の点はepoch数が5の結果、灰色の点はepoch数が20の結果、黄色の点はepoch数が80の結果となっている。

1000語以上の文書の場合は特に文書ベクトルのノルムはepochの回数による違いは多少黄色がバラついている点がちらほらある程度で、全体的にはあまり違いがないことがわかるかと思う。

その一方で、1000語未満の文書ではepochの回数が増えるにつれて、文書ベクトルのノルムが急速に増加していることが見て取れる。

このことから、PV-DBOWは1000語未満の文書での過学習の問題を抱えていて、文書が短ければ短いほどこの問題が深刻であることがわかった。

この過学習の問題は下記の式のように文書ベクトルにL2正則化を追加することで改善される。

  l'(w, d) = l(w, d) − \frac{\gamma}{|d|}||\vec{d}||^2

 l(w, d): PV-DBOWのための局所的な目的関数

 \gamma: ハイパーパラメーター。論文の実験では10が一番いい結果だったらしい。

 |d|: 文書dの単語の数

 ||\vec{d}||: 文書ベクトル  \vec{d} のノルム

正則化項がマイナスなのが何故なのかよくわからないが、元々の損失関数を最小化しつつ、その最小化をさらに加速させるために文書ベクトルのL2ノルムを大きくするような動きになりそう。

L2正則化の効果は主に下記の2点があるとのこと。

  • epochの回数が増えるにつれて、短い文書と長い文書の両方の文書ベクトルのノルムがほぼ同じになるため、epochの多い学習では短い文書に過学習することはほぼなくなる。
  • 文書ベクトルのノルムに制約がかかることにより、式(1)の確率分布が滑らかになり、検索モデルを平滑化する効果がある。

ノイズ分布に存在する問題と対策

次はPV-DBOWの目的関数について議論する。

『Neural Word Embedding as Implicit Matrix Factorization』のSkip-gramモデルの解析では、式(2)から特定の単語-文書対の局所的な目的関数を以下のように導出する。

  l(w, d)=\#(w, d) log \sigma (\vec{w} \cdot \vec{d}) + k \#(d)P_V(w)log \sigma (-\vec{w} \cdot \vec{d})

 \#(d): 文書 d中の全ての単語数

 \#(w, d): ある単語  w の文書  d 内での出現回数

 x=\vec{w} \cdot \vec{d} と定義すると、 xの目的関数の偏微分は次のようになる。

  \frac{\partial l(w, d)}{\partial x} = \#(w, d) \cdot \sigma (-x) - k \cdot \#(d) \cdot P_V(w) \cdot \sigma (x)

この偏導関数を0と置くと、この式の解は下記になる。

  \vec{w} \cdot \vec{d} = log(\frac{ \#(w, d) }{\#(d)} \cdot \frac{1}{P_V}) - log k

文書中の用語の重み付けは負例サンプリングのノイズ分布 P_Vにより決定される。元々のモデルでは負例サンプリングは全体のコーパスにおける経験的な単語分布を下記のように定義している。

  P_V(w_N) = \frac{\#w_N}{|C|}

 \#(w_N):  w_Nコーパス頻度

 |C|: コーパスのサイズ

この式において、 \frac{\#w_N}{|C|} dにおける wの正規化TFであり、 \frac{1}{P_V(w)} (すなわち、 \frac{|C|}{\#w_N}) は wICF値とみなせる。

ちなみにICFは色々種類(Inverse Community Frequency, Inverse Category Frequency, Inverse Corpus Frequency, Inverse Collection Frequencyなど)があってややこしいが、引用文献を追って行く限りだとおそらくInverse Collection Frequencyのことをさしていて、ICFの式は下記の通りである。

  icf_{t, d} = log (\frac{\Sigma_d dl_d}{\Sigma_d tf_{t,d}})

 tf_{t,d}: 文書 dにおける単語 tの出現数

 \Sigma_d tf_{t,d}: コーパス全体での単語 tが存在する文書の頻度(単語tのコーパス頻度)

 \Sigma_d dl_d: 全文書の長さの総和を求めることでコーパスの全体の単語の数を算出している(コーパスのサイズ)

したがって、負例サンプリングを使うオリジナルのPV-DBOWはTF-ICF重み付け方式に対して最適化される。

しかし、TF-ICFは情報検索における一般的な重み付け方式ではなく、ICFベースの用語の重み付けはコーパス内の単語の頻度に応じてのみ単語の識別能力を計算する仕組みのため、文書構造情報の形式を考慮していない。

経験的には小さな文書グループにしか現れない場合でもコーパス内での出現頻度が高くなる単語が特徴的であると見なされることもあり得るので、PV-DBOWは一般的なNLPのタスクではうまく動作するが、情報検索タスクではうまく動作しないらしい。

このあたりの議論は『Understanding Inverse Document Frequency: On theoretical arguments for IDF』に載っているらしいのでそのうち読みたい。

そこで、この論文ではPV-DBOWの問題に対処するために文書頻度(DF)ベースの負例サンプリング戦略を適用している。

具体的には、負例サンプリングの P_Vを次のように新しいノイズ分布 P_D に置き換える。

  P_D(w_N) = \frac{\#D(w_N)}{|N|}

 \#D(w_N):  w_N の文書頻度

 |N|: 語 w' を含む文書の数 ( |N|=Σ_{w’∈V_w}\#D(w’))

 P_V と一緒に P_D \vec{w} \cdot \vec{d} = log(\frac{\#(w, d)}{\#(d)} \cdot \frac{1}{P_V}) - log k に代入した新たな最適解が下記となる。

  \vec{w} \cdot \vec{d} = log(\frac{\#(w, d)}{\#(d)} \cdot \frac{N}{\#D(w)}) - log k

こうすることで、  \frac{1}{P_V} の部分は wの逆文書頻度(IDF)の変形である  \frac{|N|}{\#D(w)} となる。これで、DFベースのネガティブサンプリングを使用するPV-DBOWはTF-ICFよりも情報検索タスクに向いている重み付けであるTF-IDFの重み付けに対して最適化されるようになった。

(補足) TF-IDFの計算式
  tfidf_{t,d} = tf_{t,d} \cdot idf_{t} \
tf_{t,d} = \frac{n_{t,d}}{\Sigma_{s \in d} n_{s,d}} \
idf_{t} = log \frac{|D|}{df(t)} + 1

 n_{t,d}: ある単語  t の文書  d 内での出現回数

 \Sigma_{s \in d} n_{s,d}: 文書 d内のすべての単語の出現回数の和(文書 d中の全ての単語数)

 |N|: 全文書数

 df(t): ある単語  t が出現する文書の数

従来手法であるコーパス頻度( P_V)と提案手法である文書頻度ベース( P_D)の分布をそれぞれプロットしてみると下記の通りになったようだ。

f:id:gat-chin321:20171224132142p:plain
(図は『Analysis of the Paragraph Vector Model for Information Retrieval』より引用)

ちなみに横軸は単語頻度のログの値(基数は10)を表している。

この図をみると、 P_Vコーパス中での単語の出現頻度が上昇すればするほど指数関数的に増加していて、 P_Dよりもはるかに高い確率を割り当ているような傾向が見られる。

この性質からコーパス頻度 P_Vを利用した場合は言語モデルの学習を行う際に、頻出単語に対しては上手くいかなくなることがあるらしい。

この論文では頻出単語に対しては上手くいかなくなる例として、Robust04のクエリ339(“alzheimers drug treatment”)をあげて説明している。

例えば、“drug(薬)”が“alzheimers(アルツハイマー)”の2倍以上の頻度で出現する場合でも、コーパス頻度ベースの負例サンプリングを用いたPV-DBOWでの予測確率が“alzheimers”(0.042)は“drug”(0.002)よりも高くなってしまう。

これは「単語が実データの確率分布から生成された正解単語かノイズの確率分布から生成された不正解単語かを予測する」ための目的関数の最小化を行う負例サンプリングでは、おそらく正解単語には高い確率が割り当てられ、不正解単語には低い確率が割り当てられるような動きになるので、頻繁にサンプリングされてきやすい単語である“drug”は不正解として判断されやすいため、結果として"drug"の確率が下がるのだろうか?よくわからない。

正直なところ何で“alzheimers"に比べて"drug"の予測確率が低すぎるとダメなのかいまいち良い理解ができない。

ちなみに提案手法の文書頻度ベースの負例サンプリングでは、用語の重み付けが緩和され、より合理的な言語推定が行われるとのこと。例で出た“alzheimers”は0.056、“drug”は0.069となったらしい。

また、最後にコーパス頻度ベースの負例サンプリングの場合と同様に
 \#D(w)^{\eta}(0 \leq \eta \leq 1)
を使用する文書頻度のべき乗バージョンを採用して最終的に下記の通りとなる。

  P_D(w_N) = \frac{\#D(w_N)^{\eta}}{Σ_{w’∈V_w}\#D(w’)^{\eta}}

単語の言い換え関係の捕捉

『Learning Word Representations by Jointly Modeling Syntagmatic and Paradigmatic Relations』に示されているように、用語-文書行列上で分散情報を活用するモデルは主に単語の統語的関係を捕捉するが、語形変化関係を無視するとのこと。

統語的関係の論文中の解説はあまり腑に落ちなかったが、要は同じテキスト領域で共起する単語に関連しているような傾向があること。

例えば、「NBA」は「バスケットボール」と同じ文書中で共起するため、関係があるとのこと。

語形変化のように類似した文脈をもつが、文書では共起しない単語と意味が似ているものもある。

例えば、"subway"と"underground"は同義語であり、同様の状況で発生することもあるが、アメリカ人は通常"subway"を使用するのに対して、英国の人々は"underground"を使用する傾向があるなど。

元々のPV-DBOWは共起数が多い単語は類似の表現を持つ傾向がある。

しかし、これでは同じ文脈では発生するが、同じ文書では起こらない単語間の意味的類似性をモデル化することができない。

クエリ用語は平均で関連ドキュメントの40〜50%が用語の不一致であるので、用語の不一致は情報検索のタスクではよくあることらしいので、こういった単語の語形変化や単語置換関係や用語の不一致などの問題を緩和することは情報検索の分野では重要らしい。

この論文では、例としてRobust04クエリ361(“clothing sweatshops”)を取り上げている。

このクエリと関連する文書では「garment(衣服)」が頻繁に使用されているが、「clothing(衣服)」は関連する文書では使用されていない。

下記の表は文書頻度ベースのネガティブサンプリングおよびL2正則化(EPV-DR)やEPV-DRに joint objectiveを導入したもの(EPV-DRJ)を用いたParagraph Vectorでの検索モデルにおける「clothing」、「garment」および4つの関連ドキュメント間のcos類似度*1を列挙したものである。

f:id:gat-chin321:20171224132412p:plain
(図は『Analysis of the Paragraph Vector Model for Information Retrieval』より引用)

直感的に考えれば、"clothing"は"garment"と同義語であるため、"garment"と同様の確率を受け取って欲しい。しかし、EPV-DRでの結果では"clothing"に比べて"garment"のcos類似度がはるかに低くなり、結果としてこれらの関連文書の"clothing"の確率を低下させてしまっている。

単語の置換関係をモデル化するためにPV-DBOWのjoint learning objectiveを適用する。

下記の図に示すように、モデルの第1の層は文書ベクトルを使用して観測された単語を予測する。

f:id:gat-chin321:20171224132503p:plain
(図は『Analysis of the Paragraph Vector Model for Information Retrieval』より引用)

次に、モデルの第2層は、観測された単語を使用してその文脈を予測する。

PV-DBOWの目的関数を以下のように表現できる。

  l = log(\sigma(\vec{w_i} \cdot \vec{d})) + k \cdot E_{w_N \sim P_D} + \sum_{j=i-L, j \neq i}^{i+L} log \sigma(\vec{w_i} \cdot \vec{c_j}) + k \cdot E_{c_N \sim P_D}

 \vec{c_j}: 単語  \vec{w_j} の文脈ベクトル

 c_N: サンプリングされたコンテキスト

 L:コンテキストウィンドウサイズ

学習の観点から言えば、単語と文脈の間に予測目的を追加すると実際にPV-DBOWの学習目標が正則化される。

この正則化により、joint objectiveをEPV-DRに組み込んだEPV-DRJでは、"clothing"と4つの関連文書との間のcos類似度は大幅に高くなることがわかる。

LA112889-0108("clothing"が出現しない文書)でも、"clothing"と"garment"に類似したcos類似度を持つようになった。

したがって、EPV-DRJベースの検索モデルの言語推定は"clothing"の確率を高くし、最終的な検索性能を向上させる働きがあることがわかった。

実装について

chainer-doc2vecを参考にして、chainerを使って実装してみましたが、実装が正しい自信がない。

chainer-doc2vecのsearch.pyを使えば、学習後に文書間の類似度を算出できます。

あと安月給のため、お家にGPUがないのでちゃんとしたデータセットとかで検証できていません。

クラウド使えとのことですが、業務では消し忘れの実績があることからGPUインスタンスを消し忘れそうで怖いのでビビってできません。

今回は間に合わなかったのでやりませんでしたが、そのうちnardtreeさんの

Google Cloud FunctionをPythonで使う
Google Cloud FunctionをPythonで使う - にほんごのれんしゅう

のような感じで、インスタンスをいい感じに操作できるようにしてから試してみようかなとか考えています。

pythonを強引にインストールするのだるいので、Azureで同じようなことやってみようかと思っています。

その場合は正則化周りの内積計算をnumpyでやってしまっているので、cupyでやるかchainerでやるかしようかとは思います。

というか、そもそもbatchの中のinverseとnormの計算がかけて足せればいいかなと思って内積にしてしまったが、これでいいのだろうか。

あと、サンプルデータで実験したあとに気がついたが、ハイパーパラメーターの gammaを10ではなく1で実験してしまっていたのも悲しい。

#!/usr/bin/env python
import argparse
import collections

import numpy as np
from numpy import linalg as LA
import six

import chainer
from chainer import cuda
import chainer.functions as F
import chainer.initializers as I
import chainer.links as L
import chainer.optimizers as O
from chainer import reporter
from chainer import training
from chainer.training import extensions


parser = argparse.ArgumentParser()
parser.add_argument('--gpu', '-g', default=-1, type=int,
                    help='GPU ID (negative value indicates CPU)')
parser.add_argument('--unit', '-u', default=200, type=int,
                    help='number of units')
parser.add_argument('--window', '-w', default=5, type=int,
                    help='window size')
parser.add_argument('--batchsize', '-b', type=int, default=50,
                    help='learning minibatch size')
parser.add_argument('--epoch', '-e', default=20, type=int,
                    help='number of epochs to learn')
parser.add_argument('--negative-size', default=5, type=int,
                    help='number of negative samples')
parser.add_argument('--out', default='result',
                    help='Directory to output the result')
args = parser.parse_args()

if args.gpu >= 0:
    chainer.cuda.get_device_from_id(args.gpu).use()
    cuda.check_cuda_available()

print('GPU: {}'.format(args.gpu))
print('# unit: {}'.format(args.unit))
print('Window: {}'.format(args.window))
print('Minibatch-size: {}'.format(args.batchsize))
print('# epoch: {}'.format(args.epoch))
print('')


class DistributedBoW(chainer.Chain):

    def __init__(self, n_vocab, n_docs, n_units, loss_func, doc2word_func):
        super(DistributedBoW, self).__init__()
        with self.init_scope():
            self.embed = L.EmbedID(
                n_vocab + n_docs, n_units, initialW=I.Uniform(1. / n_units))
            self.doc2word_func = doc2word_func
            self.loss_func = loss_func

    def __call__(self, x, doc, context, doc_length):
        window = context.shape
        shape = doc.shape
        d = F.broadcast_to(doc[:, None], (shape[0], window[1]))
        d = F.reshape(d, (shape[0] * window[1],))
        e = F.reshape(context, (shape[0] * window[1],))
        d = self.embed(d)

        x = F.broadcast_to(x[:, None], (shape[0], window[1]))
        x = F.reshape(x, (shape[0] * window[1],))

        gamma = 1
        inverse = F.broadcast_to(gamma / doc_length[:, None], (shape[0], window[1]))
        inverse = F.reshape(inverse, (shape[0] * window[1],))
        regularization = np.dot(inverse, LA.norm(d.data, axis=1))
        loss = self.doc2word_func(d, x) - regularization
        x = self.embed(x)
        loss += self.loss_func(x, e)

        reporter.report({'loss': loss}, self)
        return loss


class SoftmaxCrossEntropyLoss(chainer.Chain):

    def __init__(self, n_in, n_out):
        super(SoftmaxCrossEntropyLoss, self).__init__()
        with self.init_scope():
            self.out = L.Linear(n_in, n_out, initialW=0)

    def __call__(self, x, t):
        return F.softmax_cross_entropy(self.out(x), t)


class WindowIterator(chainer.dataset.Iterator):
    def __init__(self, text, label, window, batch_size, docid2length, repeat=True):
        self.text = np.array(text, np.int32)
        self.label = np.array(label, np.int32)
        self.batch_size = batch_size
        self.epoch = 0
        self.is_new_epoch = False
        self._repeat = repeat
        self.window = window
        self.order = np.random.permutation(
            len(text) - window * 2).astype(np.int32)
        self.order += window
        self.current_position = 0
        self.docid2length = docid2length

    def __next__(self):
        if not self._repeat and self.epoch > 0:
            raise StopIteration

        i = self.current_position
        i_end = i + self.batch_size
        position = self.order[i: i_end]
        w = np.random.randint(self.window - 1) + 1
        offset = np.concatenate([np.arange(-w, 0), np.arange(1, w + 1)])
        pos = position[:, None] + offset[None, :]
        context = self.text.take(pos)
        doc = self.label.take(position)
        doc_length = np.array([self.docid2length[did] for did in doc], dtype=np.float32)
        center = self.text.take(position)

        if i_end >= len(self.order):
            np.random.shuffle(self.order)
            self.epoch += 1
            self.is_new_epoch = True
            self.current_position = 0
        else:
            self.is_new_epoch = False
            self.current_position = i_end

        return center, doc, context, doc_length

    @property
    def epoch_detail(self):
        return self.epoch + float(self.current_position) / len(self.order)

    def serialize(self, serializer):
        self.current_position = serializer('current_position',
                                           self.current_position)
        self.epoch = serializer('epoch', self.epoch)
        self.is_new_epoch = serializer('is_new_epoch', self.is_new_epoch)
        if self._order is not None:
            serializer('_order', self._order)


def convert(batch, device):
    center, doc, context, docid2length = batch
    if device >= 0:
        center = cuda.to_gpu(center)
        doc = cuda.to_gpu(doc)
        context = cuda.to_gpu(context)
        docid2length = cuda.to_gpu(docid2length)
    return center, doc, context, docid2length


if args.gpu >= 0:
    cuda.get_device_from_id(args.gpu).use()

with open('./sample/sample_text.txt', 'r') as f:
    text = []
    l_text = []
    vocab = {}
    count = 0
    documents = []
    for item in f:
        item = item.rstrip()
        tmp = item.split(' ')
        # 1行の単語数を追加
        l_text.append(len(tmp))
        # 文書をループ
        for word in tmp:
            # 単語とそのIDを格納する辞書を作成
            if word not in vocab:
                vocab[word] = count
                count += 1
        # 文書をそれぞれ単語IDのリストに変換
        text += [vocab[word] for word in tmp]
        documents.append([vocab[word] for word in tmp])

with open('./sample/sample_title.txt', 'r') as f:
    title = []
    docs = {}
    for doc in f:
        doc = doc.rstrip()
        if doc not in docs:
            # 文書IDは単語IDと重複しないようにしている
            docs[doc] = count
            count += 1
        # 文書IDを格納
        title.append(docs[doc])

len_label = sum(l_text)

# 文書の単語数分だけタイトルラベルを用意する
# 例: 文書0が3個、文書1が4個、文書2が2個の場合
# [0, 0, 0, 1, 1, 1, 1, 2, 2]
label = np.zeros((len_label,))
cursor_label = 0
for i, j in enumerate(l_text):
    tmp = np.broadcast_to(title[i], (j,))
    label[cursor_label:cursor_label + j] = tmp
    cursor_label += j

# 単語IDから単語を復元するための辞書の用意
index2word = {wid: word for word, wid in six.iteritems(vocab)}
# タイトルIDからタイトルを復元するための辞書の用意
index2doc = {did: doc for doc, did in six.iteritems(docs)}
# タイトルIDから文書の長さを復元するための辞書の用意
docid2length = {}
for index, did in enumerate(sorted(list(docs.values()))):
    docid2length[did] = l_text[index]

# np.arrayに変換
text = np.asarray(text).astype(np.int32)
label = label.astype(np.int32)

# 単語ごとの出現文書数をNegativeSamplingに渡す
df = {}
for wid in index2word.keys():
    df[wid] = 0
    for i in range(len(documents)):
        if wid in documents[i]:
            df[wid] += 1
for wid in index2doc.keys():
    df[wid] = 1

n_vocab = len(vocab)
n_docs = len(docs)

print('n_vocab: %d' % n_vocab)
print('n_docs: %d' % n_docs)
print('data length: %d' % len(text))

cs = [df[w] for w in range(len(df))]
loss_func = L.NegativeSampling(args.unit, cs, args.negative_size)
loss_func.W.data[...] = 0
doc2word_func = L.NegativeSampling(args.unit, cs, 1)
doc2word_func.W.data[...] = 0

model = DistributedBoW(n_vocab, n_docs, args.unit, loss_func, doc2word_func)

if args.gpu >= 0:
    model.to_gpu()

optimizer = O.Adam()
optimizer.setup(model)

train_iter = WindowIterator(text, label, args.window, args.batchsize, docid2length)
updater = training.StandardUpdater(
    train_iter, optimizer, converter=convert, device=args.gpu)
trainer = training.Trainer(updater, (args.epoch, 'epoch'), out=args.out)
trainer.extend(extensions.LogReport())
trainer.extend(extensions.PrintReport(['epoch', 'main/loss']))
trainer.extend(extensions.ProgressBar())
trainer.run()

with open('word2vec.model', 'w') as f:
    f.write('%d %d\n' % (len(index2word), args.unit))
    w = cuda.to_cpu(model.embed.W.data[:n_vocab])
    for i, wi in enumerate(w):
        v = ','.join(map(str, wi))
        f.write('%s,%s\n' % (index2word[i], v))

with open('doc2vec.model', 'w') as f:
    f.write('%d %d\n' % (len(index2doc), args.unit))
    w = cuda.to_cpu(model.embed.W.data[n_vocab:])
    for i, wi in enumerate(w, start=n_vocab):
        v = ','.join(map(str, wi))
        f.write('%s,%s\n' % (index2doc[i], v))

サンプルテキストでの出力結果

chainer-doc2vecに置いているsample_text.txtとsample_title.txtで試してみた。

PV-DBOWでの学習結果

>> Anarchism
query: Anarchism
A: 0.23314246535301208
Autism: 0.22692044079303741
Aristotle: 0.21999907493591309
An American in Paris: 0.19898760318756104
Abraham Lincoln: 0.19616368412971497
>> A
query: A
Albedo: 0.32056179642677307
Aristotle: 0.3158291280269623
Autism: 0.3155941367149353
An American in Paris: 0.2853461503982544
Achilles: 0.2599610686302185
>> Albedo
query: Albedo
Autism: 0.33208969235420227
A: 0.32056179642677307
Aristotle: 0.2921576499938965
Alabama: 0.2647320032119751
An American in Paris: 0.24834167957305908

今回のEPV-DRJの結果

>> Anarchism
query: Anarchism
Autism: 0.15463200211524963
A: 0.08547578752040863
Albedo: 0.07183104753494263
An American in Paris: 0.005674820393323898
Aristotle: -0.011234864592552185
>> A
query: A
Albedo: 0.3267810344696045
An American in Paris: 0.3043128550052643
Aristotle: 0.1921233981847763
Achilles: 0.10536286234855652
Academy Award for Best Production Design: 0.09257571399211884
>> Albedo
query: Albedo
A: 0.3267810344696045
An American in Paris: 0.268435537815094
Autism: 0.14453238248825073
Achilles: 0.12083987146615982
Abraham Lincoln: 0.09255712479352951

正直サンプルデータをちゃんと読んでいないから微妙だが、Anarchismから見てAとAlbedoが同じくらいの類似度になっているのは良い感じがする。
PV-DBOWの場合はよくわからないが、AとAlbedoとの距離が近いのにAnarchismから見てAとAlbedoの類似度が全然違う点が違和感がある。
なので、比較的うまく行っているようには見える。

やはりもっといい感じのデータセットを使って実験しないと実装があってそうか微妙だ…。

あとgensimのように既存のドキュメント間の類似度だけではなく、文書のクエリを投げつけたらそれっぽい文書が返ってくるようにしないと検索システムとしては使い物にならなさそう。

終わりに

気力の都合上、論文中の実験結果などは省きました。ごめんなさい。

実装がネット上で見当たらなかったので、泣く泣く実装もどきをしてみました。

数学が全くわかっていないまま、算数力だけで論文を読むのきついなという気持ちになっているので、情報系の学生の方はちゃんと数学を勉強しないと私のようになってしまうので、数学は頑張ってほしい。

特に『Neural Word Embedding as Implicit Matrix Factorization』のImplicit Matrix Factorizationがなんのことをなのかわからず、この記事では省いてしまいました。

さらに自然言語処理言語学的な知識もないと苦しいのかもしれない。統語的関係がどうのとかこの記事に書いているがいまいちよくわかっていない。

読んでいるだけだと理解できた気になっていたが、説明しようとすると全く自分が理解できていないことに気づいてしまい、締め切りも近づいていることに気がついて悲しいことになりました。

正直あまり理解できないところが多いので、間違いがあれば誰か教えてください。

参考文献

Analysis of the Paragraph Vector Model for Information Retrieval
https://ciir-publications.cs.umass.edu/getpdf.php?id=1242

Learning Word Representations by Jointly Modeling Syntagmatic and Paradigmatic Relations
https://pdfs.semanticscholar.org/3393/fc9456087efbe7b5375e7ea98d9067c4cc75.pdf

Neural Word Embedding as Implicit Matrix Factorization
https://papers.nips.cc/paper/5477-neural-word-embedding-as-implicit-matrix-factorization.pdf

chainer-doc2vec
https://github.com/monthly-hack/chainer-doc2vec

Efficient Estimation of Word Representations inVector Space
https://arxiv.org/pdf/1301.3781v3.pdf

Distributed Representations of Sentences and Documents
https://cs.stanford.edu/~quocle/paragraph_vector.pdf

Understanding Inverse Document Frequency: On theoretical arguments for IDF
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.438.2284&rep=rep1&type=pdf

Learning Word Representations by Jointly Modeling Syntagmatic and Paradigmatic Relations
https://pdfs.semanticscholar.org/3393/fc9456087efbe7b5375e7ea98d9067c4cc75.pdf

*1:完全に余談だが、頻繁に分散表現の類似度を測るのにcos類似度を使うことが多いが、cos類似度ってベクトルの角度しかみていないという理解なので、果たして角度だけの情報で本当に大丈夫なのだろうかと心配になる。

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

はじめに

随分久しぶりにブログを書いているが、前回投稿したのが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