新はてなブックマークでも使われてるComplement Naive Bayesを解説するよ

　新はてブ正式リリース記念ということで。もうリリースから何週間も経っちゃったけど。
　新はてなブックマークではブックマークエントリをカテゴリへと自動で分類しているが、このカテゴリ分類に使われているアルゴリズムはComplement Naive Bayesらしい。今日はこのアルゴリズムについて紹介してみる。
　Complement Naive Bayesは2003年のICMLでJ. Rennieらが提案した手法である。ICMLというのは、機械学習に関する（たぶん）最難関の学会で、採択率はここ数年は30%を切っている。2003は119/371で、32.1%の採択率だったようだ。
　Complement Naive Bayesの位置づけは

• 実装が簡単
• 学習時間が短い
• 性能もそこそこよい

　という感じで、2003年段階にあっても、絶対的な性能ではSVMに負けていた。しかし、学習が早いというのは実アプリケーションでは非常に重要で、SVMは昔の実装だと学習にかなり時間がかかる。というか、データが大規模になってくると、場合によっては使えない。私も前職でデータを作ってたときに、SVMではデータを増やしていくと学習時間が平気で数時間とかになって、焦ったことがある。
　いきなりComplement Naive Bayesを説明してもたぶんわけがわからないと思うので、まずNaive Bayesを説明し、それからComplement Naive BayesがNaive Bayesとどう違うのかを説明したい。最初は真面目に全部説明しようと思ったんだけど、まじめに説明するとどうしてもベイズの定理とかを出さざるを得ないしわかりにくいので、今回は妥協して少し不正確な説明にしてしまった。もっと正確な情報を知りたい人は、教科書を読むかおうちの人に質問してね。もしくは朱鷺の杜Wikiの単純ベイズの項を参照してね。
　Naive Bayesでは（というか、ほぼ全ての機械学習アルゴリズムでは）、処理は学習とテストの2つのフェーズに分けられる。この場合、学習というのは、あらかじめカテゴリ分けされたデータを使って下準備を行うフェーズで、テストというのは(カテゴリが)未知の文書に対してカテゴリを推定するフェーズである。

Naive Bayesの学習フェーズ

　学習のフェーズでは、カテゴリ毎にあらかじめ文書を用意しておき、それを使ってカテゴリ毎に単語の出現確率を学習しておく。出現確率、と書くとなんだかぎょうぎょうしいけど、実際のところ、全体中でその単語が何回出現したか、その割合を記録しておくだけでよい。たとえば、カテゴリ「社会」に全部で150個の単語があった場合に、そのうち3回が「社長」という単語だったとしよう。この場合、「社長」という単語の出現確率は3 ÷ 150 × 100 = 2%となる。（学習データに含まれない単語の事を考慮したりするともっと複雑になるけど、そこは今回は省略する。）

Naive Bayesのテストフェーズ

　テストフェーズではカテゴリを推定したい文書に対して、それぞれのカテゴリでの単語の出現確率を使って、文書の出現確率を計算する。もっとも出現確率が高いカテゴリを、分類結果として返す。文書の出現確率だなんて抽象的なものは正しく求めようがないので、文章中の単語の出現確率の積で近似する。
　例として、「私は社長」という文章がカテゴリ「社会」とカテゴリ「おもしろ」のどちらに分類されるかを考える。この文章が「私/は/社長」の3つの単語に区切られたとし、カテゴリ「社会」でのそれぞれの単語の出現率が1%, 5%, 2%で、カテゴリ「おもしろ」でのそれぞれの単語の出現率が1%, 4%, 3%だったとしよう。すると、「私は社長」の出現確率は、カテゴリ「社会」では

0.01×0.05×0.02×100=0.001%

となる。また、カテゴリ「おもしろ」では

0.01×0.04×0.03×100=0.0012%

　となる。0.001と0.0012を比べ、「おもしろ」での数値の方が大きいことが分かる。このため、「私は社長」はカテゴリ「おもしろ」に分類される事になる。

Naive Bayesの特徴

　文書の出現確率を単語の出現確率の積で近似してしまうというのは、さらっと流したけれど、以下のように相当に大胆な近似である。

• 語順をまったく考慮しない
• 単語間の相関関係もまったく考慮しない

　つまり、文書を単なる単語の集合として扱っている事になる。この大胆な近似が、Naive Bayesが単純(Naive)と呼ばれる所以である。まぁ、SVMも線形SVMだとここら辺の条件は変わらなかったりする場合もあるんだけど。そこを深く突っ込むとカーネルがどうとか素性のオーバーラップがどうとか話がややこしくなるので省略する。
　Naive Bayesはあまりにも単純過ぎて、初見ではちょっとどうなのと感じてしまうが、実際には文書分類ではかなりうまくいく事が知られている。例えばスパムフィルタで一時期ベイジアンフィルタとかいうのがすごく流行ったけれど、これはNaive Bayes（や、Naive Bayesのちょっとした変種）である。
　かなりはしょったというかいい加減な説明だが、ここまでがNaive Bayesの解説になる。

Complement Naive Bayesの特徴

　次に、Complement Naive Bayesを説明する。Complementというのは補集合の事で、「ある集合に含まれない要素の集まり」という意味である。Naive Bayesでは、カテゴリ毎に「そのカテゴリに属する文書」を使って学習していたが、Complement Naive Bayesでは、カテゴリ毎に「そのカテゴリに属さない文書」を使って学習を行う。「属さない文書」を使って学習をするので、カテゴリを推定する際には、「属さない確率」が最も低いカテゴリを割り当てる事になる。これだけで、なんということでしょう、カテゴリ推定精度がアップするのです。
　この説明でいきなり納得してくれる人はたぶん10人に1人ぐらいしかいないと思うので、もう少し詳しく説明したい。いくつかのカテゴリに分類する、という問題では、通常、あるカテゴリに属する文書の数は大幅に違うことが多い。例えば、現段階のはてブのエントリでは、「コンピュータ・IT」カテゴリの記事はおそらく「生活・人生」カテゴリの記事よりも2倍以上多いだろう。こうなると、「コンピュータ・IT」カテゴリの方が記事が多くなる分だけ、どうしても文書の出現確率(=文書中の単語の出現確率)が高くなってしまう事が多くなる。カテゴリに含まれる文書数に関しては別途補正項があるし、このようなバラツキはあまりよろしくない。
　バラツキを減らすために、ある「カテゴリに含まれる」文書ではなく、その「カテゴリに含まれない」文書を使って学習を行う。含まれない文書を使った方がデータ量のばらつきが減る、という様子を表現したのが図1である。
　適当な図なのでちょっとわかりにくいが、カテゴリA, B, Cに属する文書がそれぞれ20, 20, 60文書であった場合に、Naive BayesとComplement Naive Bayesでどのようなデータ量の違いがあるか、というものを示したものである。Complement Naive Bayesの方が使っているデータ量が多く見えるが、これはカテゴリに含まれない文書を使って学習しているせいでデータに重複が発生しているせいなので、絶対的な分量は重要ではない。重要なのは、Naive Bayesではデータ量のばらつきが最大で3倍（20文書 vs. 60文書）であったのが、Complement Naive Bayesでは2倍（40文書 vs. 80文書）に抑えられている、という点である。
　このように、バラツキを抑えることで性能を上げるものなので、カテゴリを推定する、というような多値分類問題には有効であるが、スパムかそうでないかを分類するような二値分類問題にはまったく意味がない。また、多値分類問題であっても、カテゴリ間でのデータ量のバラツキが少ない場合は、あまり効果がない。
　論文では他にも重みベクトルに対して

• 頻出単語に引きずられ過ぎないように出現回数の対数を取る
• 一般的な単語の影響を減らすために単語が出現する文書数の対数で割る
• 文書長の影響を減らすために文書に出てくる単語総数で出現回数を補正する
• 複数語で一つの単語を形成するようなもの（New Yorkとか）の影響を減らすために、正規化を行う

　と、いろいろとヒューリスティクスな手法を入れて改良を行っている。これらの改良のうちどれが性能改善に影響したかのは書かれていないためよくわからないが、ともかくNaive Bayesもここまでいろいろとやると性能がよくなったよ、というお話。
　まとめると、Complement Naive Bayesというのはカテゴリ推定など多値分類問題の場合に、補集合を使って学習することでデータ量のバラツキを少し抑える方法である。また、論文では、他にもいくつかヒューリスティクスな改良を加えた場合、SVMと大差ない性能が出せる事を実証している。（はてぶ分類がこのヒューリスティクスをどこまで再現しているのかはわからないけど。）
　その他、書かなかったけど、実用する上では以下の2点も非常に大事かなと思うが、今回のエントリのスコープからは外れるというか、正直そんなところまで書いてると年内に書き上がらなさそうだったので、今回は省略した。

• 文書の単語への区切り方
• スムージング

　あと、やっぱり不正確な情報だけ書くのは辛いので、最後に朱鷺の杜Wikiの単純ベイズの項とWikipediaの単純ベイズ分類器の項へリンクを張っておく。興味を持った方はぜひこちらで正確な知識を勉強してください。
　追記：朱鷺の杜Wikiのcomplement naive Bayesの項にもリンクを張っておきます。