sonoshouのまじめなブログ

情報系大学生からのウェブ見習い人生の記録

文章のカテゴリ分け

集合知プログラミング第6章を参考にしています。
集合知プログラミングのソースコードはこちらで公開されています。
http://examples.oreilly.com/9780596529321/

本エントリーでは、文章の内容に応じて文章をカテゴライズ(分類する)方法についてです。
自動タグ付けやスパムメールの分類などで用いられます。

単語/カテゴリのカウント

<サンプル文章>
('This is a pen', 'good')
('That pen is very good', 'good')
('This pen is so short', 'bad')
('This pencil is mine', 'bad')

<'pen'が'good'の文章に出てきた回数>
('pen', 'good') => 2.0
<'pen'が'bad'の文章に出てきた回数>
('pen', 'bad') => 1.0

<'pen'が文章に出てきた回数>
=> 3.0

<'good'文章の個数>
('good') => 2.0
<'bad'文章の個数>
('bad') => 2.0

<全ての文章の数>
=> 5.0

<カテゴリのリスト>
('bad', 'good')

単語/カテゴリの確率

<'good'文章だったとき'pen'が出現する確率> =
<'pen'が'good'と文章に出てきた回数> / <'pen'が文章に出てきた回数>
したがって、
0.666666666667 = 2.0 / 3.0

推測を始める

以上のやり方は、サンプル文章に対する正しい確率を算出する。
しかし、トレーニングの初期の間や、まれにしか出現しない単語については注意を要する。
例えば、'pencil'という単語は、サンプル文章中に1回しか存在しない。
にもかかわらず、'pencil'という単語が出現したら、現時点では100%で
'bad'であると判断されてしまう。
しかし、今回はサンプル文章が少ないため、たまたま'pencil'は'bad'であると
判断されただけであるにもかかわらず、100%の確率で'bad'であると
判断するのは極端すぎる。
これよりも、単語が他のカテゴリの文章で見つかるに連れて、
値をだんだんと0に近づけるやり方の方が現実的である。

そこで、単語に関する情報が無い場合は仮の確率を決めておくことで、
これらの問題を解決することができる。

ここでは、事前確率を0.5(50%)として推測を行うこととする。
すなわち、'pencil'がどの文章にも出ていない場合は、
'pencil'が'bad'である確率は50%であり、
'pencil'が'bad'であると1回判断された場合は、
'pencil'が'bad'である確率は75%である。

これは次のような計算式から算出される。
(重み * 仮確率 + 出現回数 * 実確率) / (重み + 出現回数)
= (1 * 0.5 + 1 * 1.0) / (1.0 + 1.0)
= 0.75

加重平均(重みがある平均)は、WIkipediaの平均が詳しいので、参照して欲しい。
Wikipedia:平均

また、'good'文章だったとき'pen'が出現する確率は、
確率の表記では、 Pr('pen'|'good') と表記される。

単純ベイズ分類器

以上までで、ある文章中のそれぞれの単語('pen','pencil'など)が
それぞれのカテゴリ('good', 'bad'など)に属する確率を求めた。
次は、丸ごと一つの文章が与えられたときに、カテゴリの属する確率を
求める必要がある。

ドキュメント

例えば、'apple'という単語が20%で'good'にカテゴライズされ、
'banana'という単語が80%で'good'にカテゴライズされるとする。
その場合、'apple'と'banana'の両方の単語が'good'の文章に出現する確率は、
0.2 * 0.8 = 0.16
と計算される。
確率の表記では、 Pr('apple' & 'banana' | 'good') として表記される。

これにより、 Pr(文章|カテゴリ)を計算することができる。
しかし、これはあまり役に立たない。
私たちが知りたいのは、
カテゴリが与えられたとき、任意の文章である確率ではなく、
文章が任意のカテゴリに属する確率を求めることである。
すなわち、 Pr(カテゴリ|文章)を求める必要がある。

ベイズの定理

ベイズの定理は条件付き確率を逆にする方法である。
Pr(A|B) = Pr(B|A) * Pr(A) / Pr(B)
と表記される。
Wikipediaが詳しいので、参考にして欲しい。
Wikipedia:ベイズの定理

ここで、現在の文章とカテゴリの問題に当てはめると、
Pr(文章|カテゴリ)は既に上で求めた。
Pr(カテゴリ)は、文章がこのカテゴリの属する確率なので、
そのカテゴリ中に含まれている文章の数を文章の総数で割れば良い。
すなわち、 Pr(カテゴリ) = カテゴリ中に含まれている文章 / 文章の総数
pr(文章)は、全ての文章からその文章が選ばれる確率である。
繰り返しになるが、私たちが求めたいのは Pr(カテゴリ|文章) である。
すなわち、 Pr('good'|文章)やPr('bad'|文章)を求めたいわけだが、
文章自体は変わらないので、両者を求める際、Pr(文章)の確率は変わらない。
従って、Pr(文章)はPr(カテゴリ|文章)の大小には影響しないので無視できる。

つまり、
Pr(カテゴリ|文章) = Pr(文章|カテゴリ) * Pr(カテゴリ)
となる。

この計算を各カテゴリに行い、
最も大きい数値を出したカテゴリが属すべきカテゴリである。

すなわち、
属すべきカテゴリ = argmax Pr(文章|カテゴリ) * Pr(カテゴリ)
とも書けるでしょう。

フィッシャー法

フィッシャー法は単純ベイズよりも複雑であるが、
精度が高い場合が多いので、よく用いられる。
フィッシャー法では、文章中のそれぞれの特徴のあるカテゴリでの確率を算出し、
それらをまとめた確率の集合がランダムな集合と比較して高いか低いかをテスト
してカテゴリを決定する。
つまり、 
Pr(カテゴリ|特徴) =
(その特徴を持つ文章がこのカテゴリ中に存在する数) / (その特徴を持つ文章の総数)

尚、この方法がうまくいく場合は、それぞれのカテゴリ中の文章の数が
将来的には同数になる場合である。

ただ、フィッシャー法は、
数学的に理解できなかったので、この辺で終了。無念...