ナイーブベイズ分類器(Naive bayes classifier)を用いたテキスト分類を理解する(理論編)

#はじめに
ナイーブベイズ分類器によるテキスト分類について勉強した内容をまとめました。
ベイジアンフィルタリングとも呼ばれ、スパムメールのフィルタリングにもよく使用される手法です。

##参考
ナイーブベイズの理解に当たって下記を参考にさせていただきました。

• 言語処理のための機械学習入門 (自然言語処理シリーズ)　高村 大也 (著), 奥村 学 (監修)　出版社; コロナ社
• ナイーブベイズを用いたテキスト分類　
• sklearnのナイーブベイズについてのドキュメント　

#ナイーブベイズ分類器概要
##ナイーブベイズ分類器とは何か
ナイーブベイズ分類器はベイズの定理という性質を用いた分類アルゴリズムです。
非常に古典的なアルゴリズムではあるのですが他アルゴリズムに比べて高速であるというメリットがあり、現在でも使用されています。分類アルゴリズム自体はサポートベクタマシーンやブースティング等の様々な手法があり、それらの方が精度が良いとされていますが、ナイーブベイズは高速かつ実装も簡単なため精度のベースライン指標としてよく用いられます。

##ナイーブベイズ分類器の利用
ナイーブベイズ分類器が実際にテキスト分類を行うタスクに使用されるのは、「そのメールがスパムがスパムではないのかを分類する」(このタスクの場合ベイジアンフィルタリングと呼ばれることが多い)という場合や**「そのニュース記事が政治カテゴリなのか経済カテゴリなのか、それともスポーツカテゴリなのかを分類する」**という場合などがあります。

#ナイーブベイズ分類器の理論
##ベイズの定理の利用
ナイーブベイズ分類器はベースとして下記ベイズの定理という性質を利用しています。

P(cat|doc) = \frac{P(cat) P(doc|cat)}{P(doc)} 

数式の各項目を、テキスト分類の具体例に当てはめて記載するとこのような感じです。

• $P(cat)$はその文書がカテゴリ$cat$である確率
• $P(doc)$はその文書が、文書$doc$である確率
• $P(cat|doc)$はある文書$doc$が与えられた時、その文書がカテゴリ$cat$である確率
• $P(doc|cat)$はカテゴリ$cat$が与えれれた時、文書$doc$が生成される確率

今回テキスト分類タスクとして行いたいのは、その文書がどのカテゴリに属するのか判定することでした。それはつまり**$P(cat|doc)$が最大となるようなカテゴリ$cat$は何なのかを判定するタスク**であると言い換えることができます。

また、分母の$P(doc)$はカテゴリ$cat$に依存する数値ではないので、最大値を求めるというタスクには不要です。そうすると解くべきタスクは下記のようにまとめられます。

\newcommand{\argmax}{\mathop{\rm arg~max}\limits}
\newcommand{\argmin}{\mathop{\rm arg~min}\limits}

cat_{max} = \argmax_{cat}{P(cat) P(doc|cat)} 

こちらの右辺を求めることができればOKなのですが$P(doc|cat)$をどう求めるか、というのがこのアルゴリズムの肝になります。ナイーブベイズ分類器では文書$doc$に簡略化したモデルを仮定して$P(doc|cat)$を求めます。そのモデルは大きく分けて多変数ベルヌーイモデルと多項モデルの2種類があります。

本記事では多項モデルにフォーカスして解説します。

##多項モデル
###多項モデルの概要
文書$doc$内の単語数を$k$で表し、全ての語彙(ここでは一旦、対象とする文書群に出現するユニークの単語とする)を$V$と置きます。
上記定義の上で多項モデルというものを一言で説明すると、文書$doc$は語彙$V$の中から単語を選ぶ操作を$k$回繰り返して生成されたものであると仮定するモデルです。

###多項分布について
上記概要で記載した内容を言い換えると、$P(doc|cat)$を多項分布でモデル化するという話をしています。では、そもそも多項分布とは何なのでしょうか。

####まず二項分布の話
まずは二項分布の話を少しさせていただきます。二項分布は、$n$個の独立なベルヌーイ試行(①試行は必ず成功か失敗である②各試行は独立である③成功の確率は試行を通じて一定 の3条件を満たす)の「成功」の数の確率分布のことです。

####そして多項分布の話

この二項分布を一般化したのが多項分布です。多項分布というのは、

①各試行の結果は固定の有限個（$k$個）の値をとる　
②それぞれの値をとる確率は $p_1, …, p_k$（すなわち、$i = 1, …, k$ について $p_i ≥ 0$ であり、 $ \sum_{i=1}^k p_i = 1$ が成り立つ）である　
③$n$回の独立した試行が行われる

という条件において確率変数$X = (X_1, …, X_k)$ は$n$と$p$をパラメータとする特定の分布従うというものです。

上記を今回の多項モデルのタスクに当てはめて記載すると、

①→有限個で固定の語彙$V$の中から単語を選ぶ
②→語彙$V$の中からそれぞれの単語を選び取る確率は$p_1, …, p_k$
③→文書の長さ分だけ、単語を選び取るというこの独立した試行をくり返す。

となります。ここで一点重要なのが③の独立した試行の箇所です。

実はこれがナイーブベイズ分類器のナイーブたる所以です。

**本来、文章中の各単語が出現する確率が独立である、というのは有り得ません。**例えば、「AI」という単語と「機械学習」という単語は同一文書中に出てきやすい、と直感的にわかるように、本来単語の共起性があるはずなのですがそれを無視してモデルと化しています。にも関わらず一定程度の精度が出るのがナイーブベイズ分類器の凄いところです。(なぜそれでも精度が出るのかを検証した論文もあるようなので、興味のある方はご確認ください。)

###多項分布を用いたモデルの導入
多項分布自体は、前項記載の条件のもとで下記のように表されます。

P(n_1,\cdots,n_k)=\dfrac{n!}{n_1!\cdots n_k!}p_1^{n_1}\cdots p_k^{n_k} 

※　$n_1+ \cdots +n_k = n$ かつ、$p_1^{n_1}\cdots p_k^{n_k} = 1$

多項モデルは文書$doc$は語彙$V$の中から単語を選ぶ操作を$k$回繰り返して生成されたものであると仮定するモデルでした。それを当てはめると、

P(doc|cat) = P(K=n_{doc})\dfrac{n_{doc}!}{n_{word1,doc}!\cdots n_{wordk,doc}!}p_{word1,cat}^{n_{word1,doc}}\cdots p_{wordk,cat}^{n_{wordk,doc}}

• $n_{doc}$はその文書の総単語数(文書の長さ)
• $P(K=n_{doc})$はその文書の総単語数が$n_{doc}$である確率(文書の長さはカテゴリに依存しないと仮定)
• $n_{word,doc}$はその文書中の単語$word$の出現回数
• $p_{word,cat}^{n_{word,doc}}$はその文書のカテゴリが$cat$であった時、単語$word$が$n_{word,doc}$回選ばれる確率

このような感じになります。
また、$p_{word,cat}^{n_{word,doc}}$自体は下記のような数式で求めることができます。

p_{wordi,cat}^{n_{wordi,doc}} = \frac{T(cat, word_i)}{\sum_{word \in V} (T(cat, word))} = \frac{T(cat, word_i) + 1}{(\sum_{word \in V} T(cat, word)) + |V|}
 

• $T(cat, word_i)$はそのカテゴリに含まれる単語$word_i$の数

###多項分布を用いたナイーブベイズ分類器
再度ナイーブベイズ分類器が解くべきタスクを思い出します。

\newcommand{\argmax}{\mathop{\rm arg~max}\limits}
\newcommand{\argmin}{\mathop{\rm arg~min}\limits}

cat_{max} = \argmax_{cat}{P(cat) P(doc|cat)} 

こちらの右辺に多項モデルを当てはめていきます。

\newcommand{\argmax}{\mathop{\rm arg~max}\limits}
\newcommand{\argmin}{\mathop{\rm arg~min}\limits}

\argmax_{cat}{P(cat) P(doc|cat)} =  \argmax_{cat} P(cat) P(K=n_{doc})\dfrac{n_{doc}!}{n_{word1,doc}!\cdots n_{wordk,doc}!}p_{word1,cat}^{n_{word1,doc}}\cdots p_{wordk,cat}^{n_{wordk,doc}} \\
= \argmax_{cat} P(cat)(p_{word1,cat}^{n_{word1,doc}}\cdots p_{wordk,cat}^{n_{wordk,doc}})\\
= \argmax_{cat} P(cat)(\prod_{word \in V}p_{word,cat}^{n_{word,doc}})

ということで、$cat_{max}$を見つけるためには$P(cat)(\prod_{word \in V}p_{word,cat}^{n_{word,doc}})$を計算すればOKということがわかりました。

###対数をとって計算する
文書中には多くの単語が含まれているため、$\prod_{word \in V}p_{word,cat}^{n_{word,doc}}$のそれぞれの値が非常に小さくなり、掛け算部分でアンダーフローを起こしてしまう可能性があります。
そこで対数と取ることで掛け算を足し算化します。対数を取っても本確率の大小関係は変化しないためこの手法が有効です。

\argmax_{cat} P(cat)(\prod_{word \in V}p_{word,cat}^{n_{word,doc}})
= \argmax_{cat} \Bigl( \log P(cat) + \displaystyle \sum_i \log p_{word_i,cat}^{n_{word_i,doc}} \Bigr)

こちらを計算することで、その文書が属するカテゴリの導出が可能になります。
これがナイーブベイズ分類器の多項モデルです。

###ゼロ頻度問題
ナイーブベイズ分類器を用いて未知の文書のカテゴリを予測する際、訓練データの語彙に含まれない単語を1つでも含んでいると$P(doc|cat)$の値が$0$なってしまい、計算ができません。このような問題をゼロ頻度問題と言います。このような問題への対処方法として、ラプラススムージングと呼ばれる手法がよく用いられます。

p_{wordi,cat}^{n_{wordi,doc}} = \frac{T(cat, word_i) + 1}{\sum_{word \in V} (T(cat, word) + 1)} = \frac{T(cat, word_i) + 1}{(\sum_{word \in V} T(cat, word)) + |V|}

未知の文書に訓練データの語彙に含まれない単語が出現すると$T(cat, word_i)$の値が$0$になってしまいます。それを放置してしまうと$P(doc|cat)$自体が$0$になってしまうため、上記のように全ての単語に対して出現回数$1$を加える手法を用います。

#Next
ナイーブベイズ分類器の多項モデルについては概ね理解できました。
多変量ベルヌーイモデルの方もちゃんと理解していきたいのですが、次回はナイーブベイズ分類器(多項モデル)の自力実装に挑戦したいと思います。

ここまでお読みいただきありがとうございました！