さらなる Naive Bayes: UniversalSetNB と SelectiveNB の紹介

ちゃお……†

まいおり……†

こちらの記事は機械学習と数学 Advent Calendar 2017の23日目の記事となります。

qiita.com

以前、Naive BayesとComplement Naive Bayes, Negation Naive Bayesでの多クラス分類を比較しました。今回も別のNaive Bayes亜種での多クラス分類をみていこうと思います。なお多クラス分類とは、文書 $d$ がどのクラス $c$ に属しているかを求めることです。

それぞれの手法

Naive Bayes

Naive Bayesによる多クラス分類では、ベイズの定理を適用した事後確率 $\Pr(c|d)$ が最大となるクラス $ \tilde{c}$ を求めます。ただ、$\Pr(d|c)$ を直接推定するのは難しいので、文書 $d$ を文書 $d$ に含まれる単語列 $ w_1, w_2, ..., w_n$ で近似します。また、計算を簡単にするために各クラスで単語が独立に生起すると仮定します。 そして、最終的に以下の式によって文書 $d$ の属するクラス $\tilde{c}$ を求めます。

$$ \tilde{c} = argmax_c \Pr(c) \prod_{i=1}^{n} \Pr(w_i|c) $$

Complement Naive Bayes

上記のNaive Bayes分類器はクラス間の文書数に大きなばらつきがあると、文書数の小さいクラスで $Pr(w_i|c)$ が大きくなる傾向があり、小さなクラスに割り当てられやすくなる。また、文書数の少ないクラスでは、分類対象となる文書に含まれる単語が、そのクラスに含まれていないことが多くなり、モデルがスパースになりやすい。

これらの問題に対処するために改良したのが、Complement Naive Bayesです。Complement Naive Bayesでは、クラスに属さない単語 (補集合) を用いて分類を行います。

$$ \tilde{c} = argmax_c \Pr(c) \prod_{i=1}^{n} \frac{1}{\Pr(w_i|\overline{c})} $$

Naive Bayesのコードをちょっと変更するだけで実現できます ソース

くわしくは 新はてなブックマークでも使われてるComplement Naive Bayesを解説するよ - 射撃しつつ前転の説明がわかりやすいです。 あるいは、Tackling the poor assumptions of naive bayes text classifiers

Negation Naive Bayes

しかし、Complement Naive Bayesはヒューリスティックな解決法であって、事後確率最大化の式から導出することができないため、事後確率最大化の式から導出しつつ補集合を利用するNegation Naive Bayesが提案されました。

$$ \tilde{c} = argmax_c \frac{1}{1 - \Pr(c)} \prod_{i=1}^{n} \frac{1}{\Pr(w_i|\overline{c})} $$

こちらもNaive Bayesのコードをちょっと変更するだけで実現できます ソース

くわしくは、文書分類のための Negation Naive Bayes

Universal-set Naive Bayes

Naive Bayes や Complement Naive Bayes, Negation Naive Bayes は事後確率 $\Pr(c|d)$ の推定に $\Pr(d)$ は不要であるとしています。しかし、ここでは$\Pr(d)$について解くことで新たな分類器を考えます。$\Pr(c|d)$と$\Pr(\overline{c}|d)$を足し合わせた全体の確率に Bayes の定理を適用します。

{ \displaystyle
\Pr(全体|d) = \Pr(c|d) + \Pr(\overline{c}|d) = 1
}

最終的に Universal-set Naive Bayes は文書 $d$ の属するクラス $\tilde{c}$ を次の式で推定します。

$$ \tilde{c} = argmax_c \frac{\Pr(c)}{\Pr(\overline{c})} \prod_{i=1}^{n} \frac{\Pr(w_i|c)}{\Pr(w_i|\overline{c})} $$

Selective Naive Bayes

Negation Naive Bayes はばらつきを抑えて Naive Bayes より分類性能を向上させていますが、補集合を学習に用いることで逆に学習事例数を減らしてしまう場合があります。これを $\Pr(c)$ に基づいてクラスごとに式を選択し、文書分類を行ないます。このとき、0.5 をしきい値とすることで、学習する事例数がより大きくなるように選択します。

$$ \tilde{c} = argmax_c \begin{cases} \frac{\Pr(c)\Pi \Pr(w_i|c)}{\sum_{c} \Pr(c)\Pi \Pr(w_i|c)} & (\Pr(c) \ge 0.5) \\ 1 - (|C| - 1) \frac{\Pr(\overline{c})\Pi \Pr(w_i|\overline{c})}{\sum \Pr(\overline{c})\Pi \Pr(w_i|\overline{c})} & (otherwise) \end{cases} $$

比較

irisは萼の長さなどからあやめのクラス分類をするデータセットで、MNISTは0から9までの手書き文字認識のデータセットです。2つともDenseなデータセットとなっているのが特徴です。 20newsは、およそ20,000文書から20のニュースグループに分類するためのデータセットです。 Yahoo!Yahoo! Web Directory Topicsを、livedoorlivedoor ニュースコーパスを指します。ただし、極端なばらつきのあるデータでの結果も見たいのでlivedoor ニュースコーパスでは、独女通信と家電チャンネルとS-MAX以外のデータを大幅に間引いています。

結果

くわしくはこちらこちら

precision

NB CNB NNB UNB SNB
iris 0.93 0.54 0.54 0.85 0.54
MNIST 0.84 0.74 0.74 0.83 0.74
20news 0.82 0.87 0.89 0.85 0.89
Yahoo! 0.71 0.73 0.73 0.71 0.73
livedoor 0.47 0.39 0.79 0.77 0.77

recall

NB CNB NNB UNB SNB
iris 0.9 0.7 0.7 0.73 0.7
MNIST 0.83 0.72 0.72 0.83 0.72
20news 0.74 0.85 0.89 0.80 0.89
Yahoo! 0.69 0.72 0.71 0.69 0.71
livedoor 0.54 0.52 0.67 0.65 0.71

f1-score

NB CNB NNB UNB SNB
iris 0.9 0.59 0.59 0.66 0.59
MNIST 0.83 0.71 0.71 0.83 0.71
20news 0.73 0.84 0.88 0.80 0.89
Yahoo! 0.69 0.72 0.71 0.69 0.71
livedoor 0.41 0.38 0.62 0.59 0.67

わかったこと

クラス数が少ない場合あるいはデータが密な場合はNBがよい。一方でクラス数が多い場合やクラス間のデータに偏りがある場合はSNBやNNBがよい。UNBは論文のようにはうまくいきませんでした。

参考文献

  • 伊藤 裕佑、古宮嘉那子、小谷 善行, 文書分類における補集合を併用したNaive Bayes, 第一回コーパス日本語学ワークショップ予稿集, pp.109-112, (2012,03,05)
  • Kanako Komiya, Yusuke Ito, Yoshiyuki Kotani, New Naive Bayes Methods Using Data from All Classes,  International Journal of Advanced Intelligence, Vol. 5, Issue 1, pp.1-12, (2013.8)