ナイーブベイズ分類器の仕組み

ナイーブベイズ(単純ベイズ)とは、あるデータがどのカテゴリに属するかを確率的に求める機械学習のひとつです。

特にナイーブベイズが多用されるのはテキスト分類で、例えばメールの文面がスパムか、スパムでないかを推定する「ベイジアンフィルタ」の仕組みに使われています。

しかし、そんな便利なナイーブベイズですが、一体どんな計算をして文章のカテゴリを推測しているのでしょうか?
実は、行っている計算自体はそんなに難しくはありません。

本記事では、そんなナイーブベイズ分類器の仕組みについて整理しました。

今回用いる例題

分類器を作るためには、学習データ(正解データ)が必要不可欠です。
先ほどのスパム判定の例で言えば、実際にスパムだったメールの文章と、スパムでなかったメールの文章が必要、という訳です。
理論上はカテゴリごとに最低1文章あれば良いのですが、データは多ければ多いほど、性能の良い分類器を作ることができます。
(もちろんデータが間違えていたらダメですし、同じデータを増やしても意味はありません。)

それでは、今回は例として、ある文章が「料理に関するものか、スポーツに関するものか」を判定する分類器を考えてみます。
分類器を作ったら、未知の文章が料理関連かスポーツ関連を判定してもらいましょう。

今、手元に以下の「学習データ」があるとします。

  • 料理カテゴリ
    • 「私はラーメンを食べるのが好きだ」
    • 「昼休みにカレーを食べた」
  • スポーツカテゴリ
    • 「私はサッカーが好きだ」
    • 「昨日、テニスをした」
    • 「夢は野球選手になることです」

このデータを元に分類器を作り、
「私は昨日お寿司を食べました。」
・・・という文章が料理関連なのか、スポーツ関連なのかを推定するまでの手続きを追ってみます。

ナイーブベイズ分類器の仕組み

さて、今回知りたいのは、「調べたい文章が”料理”カテゴリに属する可能性」「調べたい文章が”スポーツ”カテゴリに属する可能性」です。
この2つを数値化さえできれば、あとは数値の大小関係を比較するだけです。
この数値化のためには「ベイズの定理」という定理を使います。

「ベイズ」というと難しそう・・・というイメージがある気がしますが、そこまで難しく考える必要はありません。
何なら「公式だ!」と割り切ってしまってもとりあえずは問題ありません。

ということで、まずはベイズの定理の公式から。

\(P(X)\)を「Xが発生する確率」
\(P(X|Y)\)を「Yが発生した上でXが発生する確率」
とした時に、
\[P(A|B) = \frac{P(A) P(B|A)} {P(B)}\]
が成立する。

・・・数式で書くとなんだかややこしいのですが、この式における「A」を「料理カテゴリである」、「B」を「文章が入力された」としてみましょう。
すると、

\(P(A)\)・・・料理カテゴリである確率
\(P(B)\)・・・文章が入力された確率
\(P(A|B)\)・・・文章が入力された時、それが料理カテゴリである確率
\(P(B|A)\)・・・料理カテゴリである時、それが検索文章である確率

となります。左辺の\(P(A|B)\)が正に今知りたい値となっています。
つまり右辺の\(P(A)\)、\(P(B)\)、\(P(B|A)\)が計算できれば、自ずと「調べたい文章が”料理”カテゴリに属する可能性」が分かる、ということになります。
それでは、右辺の計算式を順番に見ていきます。

\(P(A)\)…料理カテゴリである確率

「料理カテゴリである確率」とは、単純に「全部の文章のうち、幾つが料理カテゴリのものか」という事です。
全文章が5つ。そのうち料理カテゴリに属する文章は2つなので、この値は\(2/5\)となります。

同様に、スポーツカテゴリについて調べたいならこの値は\(3/5\)となります。

\(P(B)\)…文章が入力された確率

「文章が入力された確率」ですが、これは入力された文章があるからこそ計算している訳ですので、常に「1」で問題ありません。
一般的にベイズの定理において\(P(B)\)は定数にしかならないので省略されることもしばしばあります。
(その場合は左辺と右辺は「=」でなく、”比例する”という意味の「∝」で繋ぎます。)

\(P(B|A)\)…料理カテゴリである時、それが検索文章である確率

「料理カテゴリである時、それが検索文章である確率」・・・これが一番意味がわかりませんね。
では、これを「料理カテゴリを構成する語句が、検索文章の語句である確率」と読み替えてみましょう。

ここで具体的な文章を考えてみます。
「料理カテゴリ」にはどんな単語が使われているでしょうか。

「私はラーメンを食べるのが好きだ」「昼休みにカレーを食べた」の2文ですから、
「私」「ラーメン」「食べる」「好き」「昼休み」「カレー」「食べる」の7単語ですね。
(一般的に、接続詞や「てにをは」はどんな文章にでも現れるので考慮に入れません。)

一方、検索文章にはどんな単語が使われているでしょうか。
「私は昨日お寿司を食べました。」なので、「私」「昨日」「お寿司」「食べる」ですね。

ここで「料理カテゴリを構成する語句が、検索文章の語句である確率」を更に細かく考えてみると、「料理カテゴリを構成する語句が『私』である確率」、かつ「料理カテゴリを構成する語句が『昨日』である確率」、かつ・・・となります。

「料理カテゴリを構成する語句が『私』である確率」ですが、これはもう分かりますね。
料理カテゴリを構成する語句は「私」「ラーメン」「食べる」「好き」「昼休み」「カレー」「食べる」でしたので、これは\(1/7\)です。
同様に、「料理カテゴリを構成する語句が『昨日』である確率」は\(0\)、「料理カテゴリを構成する語句が『お寿司』である確率」も\(0\)、「料理カテゴリを構成する語句が『食べる』である確率」は\(2/7\)となります。

これらの事象はすべて独立(同時に発生することは無い)ですので、単純に掛け算していけば「料理カテゴリを構成する語句が、検索文章の語句である確率」が計算できそうです。
今回の場合、\(1/7 \times 0 \times 0 \times 2/7\)です。

・・・しかし、これを掛け算するとゼロになってしまうようです。
そう、式の中にひとつでもゼロがあると\(P(B|A)=0\)になってしまい、ベイズの定理の左辺もゼロになってしまいます。

つまり「料理カテゴリ」の中に存在しない単語がひとつでも出てくると計算できなくなってしまうのです。
これでは困りますね。
ですが、このような問題は「ゼロ頻度問題」と呼び、きちんと対策が用意されています。

ゼロ頻度問題の対策

この対策は非常にシンプルで、「どんな単語でも、カテゴリ内に1つは出現していることにしちゃう」というものです。
ただし、使われていない単語だけ+1するのはフェアじゃないので、全単語の出現回数を+1します。
また、それにより分母と分子のバランスが変わってしまうので分母も少し大きくします。

分母の増やす数は1以上なら何でもいいような気もしますが、一般的には「学習データすべての重複を除いた全単語数」を使います。

今回の例では、出現する単語を重複を除いて並べると
「私」「ラーメン」「食べる」「好き」「昼休み」「カレー」「サッカー」「昨日」「テニス」「する」「夢」「野球」「選手」「なる」「こと」
・・・なので、15語のようです。

よって、全ての分子に1、全ての分母に15という数を足します。
すると先ほどの\(1/7 \times 0 \times 0 \times 2/7\)という計算が、\(2/22 \times 1/22 \times 1/22 \times 3/22\)となります。

この対策は「加重スムージング」と呼ばれ、ナイーブベイズ分類器には一般的にこの処理も実装されています。
分母と分子に足す数値にはバリエーションがありますが、よっぽどの事が無ければここに示した値で問題ないかと思います。

ただし、分母と分子に勝手な値を足しているので、計算される値はもう「確率」では無いことにご注意ください。
(なので、以降は「可能性」という言葉に変えます。)

ある文章があるカテゴリに属する可能性

さて、これでもう計算できます。ここまでの計算式を整理すると、

「文章が入力された時、それが料理カテゴリである可能性」=
「料理カテゴリである確率」×
「料理カテゴリを構成する語句が『私』である可能性」×
「料理カテゴリを構成する語句が『昨日』である可能性」×
「料理カテゴリを構成する語句が『お寿司』である可能性」×
「料理カテゴリを構成する語句が『食べる』である可能性」

です。

すると、「文章が入力された時、それが料理カテゴリである可能性」=\(2/5 \times 2/22 \times 1/22 \times 1/22 \times 3/22\)です。これは約0.0000102になります。

同様に「文章が入力された時、それがスポーツカテゴリである可能性」も計算できます。
スポーツカテゴリに出てくる単語数は「私」「サッカー」「好き」「昨日」「テニス」「する」「夢」「野球」「選手」「なる」「こと」の11語で、加重スムージングを考慮すると分母は26になります。

すると、「文章が入力された時、それがスポーツカテゴリである可能性」=\(3/5 \times 2/26 \times 2/26 \times 1/26 \times 1/26\)です。これは約0.0000053になります。

あとはこの値が大きいものを選ぶだけです。
今回の場合は、無事に入力された文章「私は昨日お寿司を食べました。」が料理カテゴリに属すると判別することができました。

計算式の補正(アンダーフロー対策)

さて、これで無事に計算できましたが、実はまだ問題があります。
結果として出てきた数値がとても小さい値になっていることにお気づきでしょうか。
1以下の値をどんどん掛け算していくので、結果はかなり小さな値になってしまいます。

今回の「私は昨日お寿司を食べました。」というような4語しかない短い文章でも0.0000…という値になってしまうくらいなので、更に長い文章だと0.00000000000…という途轍もなく小さな値になってしまうことが想像できます。

コンピュータの場合、処理できる桁数には限界があります。
あまりに巨大な数値やあまりに微小な数値は扱う事ができません。
値が大きすぎて処理できなくなる問題を「オーバーフロー」、小さすぎて処理できなくなる問題を「アンダーフロー」と言います。

そこで、数値が小さくなりすぎないために、すべて対数を取った値を用います。
logを取れば、数値の大小関係を変える事なく、微小な値をほどほどの大きさ数値で表現する事ができます。

先ほどの例で言えば約0.0000123は約-11.5。約0.0000082は約-12.2になります。
(logの底は何でも良いのですが、今回はeを用いました。)

入力される文章が必ず短いという保証はありませんし、使うコンピュータの性能によって扱える桁数も変わってきますので、この対策はしておいた方が安全でしょう。

まとめ

さて、以上の事を数式で整理しておきます。

\(P(cat)\)…入力文章が○○カテゴリである可能性
\(w_1,w_2,…w_n\)…入力文章の構成語句
\(r_{cat}\)…全学習データのうち○○カテゴリに属するデータの割合
\(N_w\)…○○カテゴリの中に出現する、ある語句\(w\)の数
\(N_{cat}\)…○○カテゴリの中に出現する、すべての語句の数
\(N_{all}\)…全学習データの中に出現する重複を除いた全語句の数

とすると、
\[P(cat) = \log{r_{cat}} + \sum_{k=1}^{n} \log \frac{N_{w_k} + 1} {N_{cat} + N_{all}}\]
と計算される。

カテゴリの数の分だけ上の式を用いて\(P(cat)\)を求めれば、今入力した文章が〇〇カテゴリである可能性が数値として出てくる訳です。
対数を取っているので、掛け算が足し算になっている点にご注意ください。

以上が、ナイーブベイズ分類器の仕組みでした。
ナイーブベイズ分類器やベイジアンフィルタを用いる際には、ただ既存のプログラムを引っ張ってくるだけではなく、この辺りの理論を理解しておくとシステムごとに最適なメンテナンスを施すことができるため望ましいと思います。