ナイーブベイズの改良版AODEを実装して実験してみる

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。

ナイーブベイズは自然言語処理の分類タスクで、実装がシンプルで高速でそれなりに精度が出るということで、はじめに試すモデルだよという方も多いかも知れません。

scikit learnにも実装があるので、サクッと試せて便利ですが、もう少し時間がかかってもいいので精度が欲しい！となった場合にナイーブベイズではどうするのが良いのでしょうか。

ナイーブベイズについてあまり詳しくなかったので、調べてみたところ、いくつか亜種があるそうです。

* [僕はもう、そんなにナイーブじゃないんだ - Qiita](https://qiita.com/cou_z/items/bca93fce0a08b521a3e8)
* [no_bayes_no_life_nb_keep_evolving](https://www.slideshare.net/phyllo/nobayesnolifenbkeepevolving)
* [不均衡データに対するNaive BayesとComplement Naive Bayes, Negation Naive Bayesの比較 - Debug me](https://yukinoi.hatenablog.com/entry/2016/06/07/121759)

今回は、この中で紹介されているAODE(Averaged One-Dependence Estimators)について興味を持ったので、論文を読みつつ実装し、軽く実験もしてみました。

## AODE

[僕はもう、そんなにナイーブじゃないんだ - Qiita](https://qiita.com/cou_z/items/bca93fce0a08b521a3e8)

ここで説明されているので、詳しくはこちらを参照していただきたいです。

ナイーブベイズ(NB)はその名の通りナイーブ、つまりクラスを条件付けた時の文章生成の確率を単語の生成確率の積に分解できるという単純な仮定を置いています。

本当は、単語同士は独立ではないはずなので、その仮定の部分を緩めて性能を向上させよう、というアイデアがAODEの元となっています。

通常のNBでは

$$P(y|x) \propto P(y)\prod_{i=1}^{n}P(x_i|y)$$

を考えますが、

AODEでは単語同士の関係を扱うために、ある単語$x_k$に対して、

$$P(y|x)\propto P(y,x_k)\prod_{i=1}^{n}P(x_i|y,x_k)$$

を考えます。
AODEのAはaveragedで、実際はこの$x_k$として「$m$個以上の文章に含まれている単語」すべてに対して上のスコアを計算して平均して、一番高いクラスと予測するという流れです。

通常のNBでは$P(x_i|y)$をどのような分布でモデリングするかに自由度があり、有名なものにベルヌーイ分布や多項分布を使ったものがあります。

この二つはscikit learnにも実装がありますね。

[1.9. Naive Bayes — scikit-learn 0.23.2 documentation](https://scikit-learn.org/stable/modules/naive_bayes.html)

今回のAODEはどのように$P(y,x_k)$や$P(x_i|y,x_k)$を推定しているかを論文を見てみると、
どうやらベルヌーイ分布を仮定しているようで、$x_i$の値自体は使っていなさそうでした。

これに多項分布を仮定したらどうなるのかを考えてみたのですが、
実際に分解していくと、

$$P(x_i|y,x_k) = \frac{P(x_i,y,x_k)}{P(y,x_k)} = \frac{P(x_i,x_k|y)P(y)}{P(y,x_k)}$$

となり、$P(x_i,x_k|y)$の部分をどうモデリングすればいいかわからず断念しました。

$P(x_i,x_k|y) = P(x_i|y)P(x_k|y)$としてしまうとNBと同じなので分解できず。元の論文では$x_i$と$x_k$が両方含まれている文章の個数を全体で割る、みたいなことをしている(もちろんスムージングはしている)ので$x_ix_k$がベルヌーイ分布に従うとして推定していると考えられます。

この辺りの問題について取り組まれた研究とかあるんでしょうか。

## 実装

というわけで、ベルヌーイ分布を仮定して、2値分類のAODEを実装しました。

[僕はもう、そんなにナイーブじゃないんだ - Qiita](https://qiita.com/cou_z/items/bca93fce0a08b521a3e8)

この記事の実装を参考にしましたが、一部論文の方を参照して修正して試しています。

ラプラススムージングや対数とるところなども気をつけて実装しています。

```python
class AODE:
    def __init__(self, minimum_word_count=30):
        self.v_i = 2  # binaryを仮定
        self.minimum_word_count = minimum_word_count
        self.all_categories = set()
        self.word_count = defaultdict(int)
        self.category_word_count = defaultdict(lambda: defaultdict(int))
        self.category_word_freq = defaultdict(lambda: defaultdict(int))
        self.category_word_pair_count = defaultdict(lambda: defaultdict(int))

def preprocess(self, X):
        """入力形式を合わせる"""
        result = []
        for i in range(X.shape[0]):
            d = X.getrow(i).todok()
            temp = {}
            for k, v in d.items():
                temp[k[1]] = v
            result.append(temp)
        return result

def fit(self, X, y):
        X = self.preprocess(X)
        assert len(X) == len(y)
        self.total_docs = len(X)
        self.category_nums = [sum(y == 0), sum(y == 1)]

for i in range(len(X)):
            category = y[i]
            document = X[i]
            for word, freq in document.items():
                self.word_count[word] += 1  # F(x_i)
                self.category_word_count[category][word] += 1  # F(y,x_i)

for word1, word2 in permutations(document, 2):
                self.category_word_pair_count[category][(
                    word1, word2)] += 1  # F(y,x_i,x_j)

def predict_proba(self, X):
        X = self.preprocess(X)
        pred = []
        for i in range(len(X)):
            scores = np.array([self._calc_score(X[i], category)
                               for category in [0, 1]])
            pred_proba = scores/(-sum(scores))+1
            pred.append(pred_proba)
        return np.array(pred)

def _calc_score(self, document, category):
        """documentがcategoryに属するスコアを算出する
        """
        score = 0.0
        for word in document:
            if self.word_count[word] < self.minimum_word_count:
                continue
            score += self._calc_one_dependence_score(document, category, word)
        if score == 0:
            # すべてm未満の時は、AODEではなく通常のNaive Bayesを用いる
            score = (self.category_nums[category]+1)/(self.total_docs + 2)
            for word in document:
                score += math.log((self.category_word_count[category][word] + 1)/(
                    self.category_nums[category] + 2))
        return score

def _calc_one_dependence_score(self, document, category, attribute):
        """attributeがペアレントの時に、documentがcategoryに属するスコアを算出する
        P(category, attribute) * ΠP(word|category, attribute)
        """
        # P(category, attribute)

# 本論文と同じ
        score = math.log((self.category_word_count[category][attribute] + 1.0) / (
            self.total_docs + self.v_i*len(self.all_categories)))

# ΠP(word|category, attribute)
        for word in document:
            score += math.log(self._calc_one_dependence_probability(word,
                                                                    category, attribute))
        return score

def _calc_one_dependence_probability(self, word, category, attribute):
        """P(word|category, attribute)
        """
        numerator = self.category_word_pair_count[category][(
            word, attribute)] + 1.0
        denominator = self.total_docs + self.v_i * \
            self.v_i*len(self.all_categories)
        return numerator / denominator
```

## 実験

scikit learnの

[sklearn.naive_bayes.BernoulliNB — scikit-learn 0.23.2 documentation](https://scikit-learn.org/stable/modules/generated/sklearn.naive_bayes.BernoulliNB.html#sklearn.naive_bayes.BernoulliNB)

[sklearn.naive_bayes.MultinomialNB — scikit-learn 0.23.2 documentation](https://scikit-learn.org/stable/modules/generated/sklearn.naive_bayes.MultinomialNB.html#sklearn.naive_bayes.MultinomialNB)

と比較しました。
データセットは

[5.6.2. The 20 newsgroups text dataset — scikit-learn 0.19.2 documentation](https://scikit-learn.org/0.19/datasets/twenty_newsgroups.html)

のラベルが0,1のデータに絞って用いました。

テストデータでAccuracyを算出しました。
結果はこちら。

|BNB|MNB|AODE|
|----|----|----|
|0.929|0.977|0.956|

ベルヌーイよりは改善していますが、MNBには負けてしまっています。
この結果も、より多項分布などの他のモデリングを試したくなる一因ですね...

ただ同じモデリングをしているベルヌーイNBよりは改善しているので、ひとまず効果はありそうです。

## おわりに

NBのあやふやだった部分も含めて復習して、論文も読んで再現したので勉強になりました。

[ナイーブベイズ：カテゴリ数が一般の場合の式展開 | SEEDATA | Tribe Driven Innovation](https://seedata.co.jp/blog/tech/2222/)

特に、ラプラススムージングについてあまり良くわかっていなかったのですが、上の記事ですっきり理解できたので良かったです。

NBは他にも改良版があるみたいなので、調べてみようと思います。

ありがとうございました。

このブログを検索

ぐぐりらにっき

ナイーブベイズの改良版AODEを実装して実験してみる

コメント

コメントを投稿

ナイーブベイズの改良版AODEを実装して実験してみる

この記事をシェアする

コメント

コメントを投稿