ナイーブベイズを用いたテキスト分類 - 人工知能に関する断創録

今までPRMLを読んで実装を続けてきましたが、~~10章からは難しくて歯が立たなくなってきたので~~ここらで少し具体的な応用に目を向けてみようと思います。機械学習の応用先としては画像の方が結果を見ていて面白いんですが、当面は自然言語処理を取り上げます。そんなわけで一番始めの応用は機械学習と自然言語処理の接点として非常に重要なテキスト分類（Text Classification, Text Categorization）の技法たちを試していきたいと思います。テキスト分類は文書分類（Document Classification）という呼び方もあります。テキストと文書は同じ意味です。最初なので自分の知識の整理と入門者への紹介のためにちょっと丁寧にまとめてみました。

テキスト分類とは

テキスト分類とは、与えられた文書（Webページとか）をあらかじめ与えられたいくつかのカテゴリ（クラス）に自動分類するタスクです。テキスト分類は対象とするテキストによって幅広い応用が可能です。たとえば、すでに実用化されて身近でお世話になっている機能としては、

電子メールを「スパム」と「それ以外」というカテゴリへ自動分類して「スパム」をゴミ箱へ捨てる（スパムフィルタ）
Webページを「政治・経済」「科学・学問」「コンピュータ・IT」「ゲーム・アニメ」などのカテゴリへ自動分類（はてなブックマーク）
ニュース記事を「興味あり」「興味なし」というカテゴリへ自動分類して「興味あり」のニュース記事だけおすすめ（情報推薦・情報フィルタリング）

などがあります。それぞれ、電子メール、Webページ、ニュース記事がテキストに当たります。たとえば、私も愛用しているはてなブックマークですが、人間がWebページの内容を読んで、このページは「コンピュータ・IT」だなとか分類しているわけではなく、機械学習の手法を用いた分類プログラム（分類器と呼ぶ）が自動的に分類しています。

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

大量のWebページが毎日毎日出てくるのにこんなの人手でできるはずないですよねー（Yahoo!は昔これを人手でやってましたが今はどうなんでしょうね？）。

教師あり学習

仕組みはこうです。まず、人間が教師となって分類器を訓練します。こんな感じ。

Webページ1は「IT」
Webページ2は「科学」
Webページ3は「IT」
Webページ4は「政治」
Webページ5は「ゲーム」
・・・

このような（テキスト,人間が与えた正解カテゴリ）を組としたデータを訓練データと呼びます。分類器はこの訓練データをもとに各カテゴリの文書の特徴を自動学習します。たとえば、

「iPhone」「Apple」「Twitter」などの単語が含まれるテキストは「IT」カテゴリである確率が高い
「民主党」「菅直人」などの単語が含まれるテキストは「政治」カテゴリである確率が高い
「研究」「JAXA」「遺伝子」などの単語が含まれるテキストは「科学」カテゴリである確率が高い

などです。このように訓練した分類器を用いて、カテゴリがわからない新しい文書、たとえば、「Apple」「iPhone」が含まれる文書のカテゴリは？と分類器に聞くと「IT」である確率が高いと返してくれます。一般的に訓練データは多ければ多いほど分類器は正確なテキスト分類ができるようになります。このように、人間が正解カテゴリを訓練データとして与える機械学習手法は教師あり学習と呼びます。

Bag-of-words

一般的にテキストは単語の集合として与えます。集合なので並び順は無視されます。つまり、単語が文書内にどこに出てくるかは考慮しません。このようなテキスト表現はbag-of-wordsと呼ばれます。単語をバッグの中にぐちゃぐちゃ詰め込むイメージでしょうか。たとえば、

テキスト分類とは、与えられたテキストをあらかじめ与えられているカテゴリに「自動で」分類するタスクです。

という文書は、bag-of-wordsで表すと

テキスト テキスト カテゴリ タスク 自動 分類 分類

みたいに単語の集合で表されます。タスクにもよりますが、形態素解析（2009/4/15）で名詞だけ抽出して使うことが多いんじゃないかと思います。話はそれますが、Visual Wordsを用いた類似画像検索（2010/2/27）で取り上げたbag-of-visual wordsはbag-of-wordsの画像版です。bag-of-visual wordsもbag-of-wordsと似ていて画像における単語（局所特徴量のセントロイド）が画像上のどこにあるかは考慮しません。このような単純化のおかげで学習アルゴリズムがシンプルになります。

テキスト分類の技法

テキスト分類は非常に多くの研究があり、そのアルゴリズムも大量にあります。ちょっと思いつくだけでも、ナイーブベイズ、決定木、Rocchio分類法、k-最近傍法、ロジスティック回帰、ニューラルネットワーク、サポートベクトルマシン、ブースティングなどなど。それぞれやり方はだいぶ違っています。また、テキストをベクトルへ変換する手法（TF-IDFとか）や次元削減の方法（LSIとか）もたくさん提案されており、その組み合わせを考えると結局どれ使えばいいの？って感じです。一般的には、サポートベクトルマシンやブースティングが他の手法と比べて高精度な分類ができると言われています。これから実際に試していきます。今回取り上げるのは、よく使われていて実装も簡単、しかも高速というナイーブベイズです。精度評価のベースラインとしてよく使われてます。

ナイーブベイズ

ナイーブベイズの中心となる式はベイズの定理を応用した下の式で表せます。

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

事後確率P(cat|doc)は文書docが与えられたときカテゴリcatである確率です。カテゴリを予測したい未知の文書は、事後確率がもっとも高いカテゴリへ分類します（MAP推定）。この確率を計算するためには、右辺の事前確率P(cat)と尤度P(doc|cat）が必要になります。P(doc)はどのカテゴリにも共通なので無視できます。事後確率P(cat|doc)と尤度P(doc|cat)はややこしいのですが違うものです。私はこの違いを理解するのにだいぶ苦労した覚えがありますが・・・

まず、P(cat)ですがこれは簡単です。訓練データの各カテゴリの文書数の総文書数に占める割合を計算するだけです。たとえば、

訓練データ100文書中
IT      50文書  →  P(cat=IT)   = 50 / 100 = 0.5
科学    30文書  →  P(cat=科学）= 30 / 100 = 0.3
政治    20文書  →  P(cat=政治) = 20 / 100 = 0.2

のようになります。P(doc|cat)はちょっと複雑です。カテゴリcatが与えられたときに文書docが生成される確率です。ここで、文書docはbag-of-wordsで単語の集合 [word_1,word_2,...,word_k] として表され、単語間の独立性を仮定するとすると下のように計算できます。

$P(doc|cat) = P(word_{1} \wedge \; \cdots \; \wedge word_{k} | cat) = \displaystyle \prod_i P(word_i | cat)$

上の式で第2式から第3式へは単語の出現確率の間に独立性を仮定しないと成り立ちません。同時確率をそれぞれの確率の積で表せるってのが確率論的独立性の定義です。本来、単語の出現に独立性は成り立ちません。たとえば、「人工」と「知能」は共起しやすいし、「機械」と「学習」は共起しやすいです。これを無視して単語の出現は独立と無理矢理仮定して文書の確率を単語の確率の積で表して単純化するのがナイーブベイズのナイーブたる所以です。単語間の依存関係を仮定したナイーブベイズとしてTAN（Tree-Augmented Naive Bayes）というのも提案されていますが、あまり広まってないところを見ると労多くして功少なしって感じでしょうか？

で、今度はP(word_i|cat)の確率が必要です。これは、単語の条件付き確率と呼びます。カテゴリの中でその単語がどれくらいでてきやすいかを表します。これは簡単で、訓練データのカテゴリcatに単語word_kが出てきた回数をカテゴリcatの全単語数で割ればOKです。T(cat,word)をカテゴリcatに単語wordが出てきた回数、Vを訓練データ中の全単語集合（ボキャブラリ）とすると、

$\displaystyle P(word_i | cat) = \frac{T(cat, word_i)}{\sum_{word' \in V} T(cat, word')}$

となります。分母はVのすべての単語に関して足し合わせますが、実際は対象カテゴリcatに出てくる単語に絞っても結果は同じです。そのカテゴリに出てこなかった単語はT(cat,word)=0となるからです。

対数

以上の結果をまとめると最終的に分類されるカテゴリcat_mapは

$cat_{map} = \arg \max_{cat} P(cat|doc) = \arg \max_{cat} P(cat) \displaystyle \prod_i P(word_i | cat)$

となります。argmaxf(x)ってのはf(x)が最大になるようなxを返すっていう意味です。P(word|cat)というのは非常に小さい数な上に文書中にはたくさんの単語が含まれるのでかけ算部分がアンダーフローを起こす可能性があります。そこで、対数をとってかけ算を足し算化します。事後確率の大小関係は対数をとっても変化しない（結果となるcat_mapは変化しない）ので問題ありません。

$cat_{map} = \arg \max_{cat} \log P(cat|doc) = \arg \max_{cat} \Bigl( \log P(cat) + \displaystyle \sum_i \log P(word_i | cat) \Bigr)$

ゼロ頻度問題

P(doc|cat)は単語の条件付き確率P(word|cat)の積で求まったのですが、アンダーフロー以外にもう1つ大きな問題があります。それは、未知の文書のカテゴリを予測する際、訓練データのボキャブラリに含まれない単語を1つでも含んでいると単語の条件付き確率P(word|cat)は0となり、単語の条件付き確率の積で表されるP(doc|cat)も0となってしまうことです（対数のときはlog 0となり計算できなくなります）。つまり、その新しい文書が生成される確率は0になってしまいます。

たとえば、文書にiPhone、Appleなどの単語が含まれており、「おっ、これはカテゴリITから生成された可能性が高くなってきた」と思っていても、訓練時には含まれなかった新単語iPadが含まれてしまうとP(doc|cat) = 0となり、この文書がカテゴリITから生成された確率は0になってしまいます。iPhoneとAppleが出てるのだからカテゴリはITの可能性が高いだろ！これはおかしい！ってことになります。この問題は、ゼロ頻度問題と呼ばれています。ゼロ頻度問題は、スムージングという方法で緩和できます。よく使われるのが単語の出現回数に1を加えるラプラススムージング（Laplace Smoothing）です。新しい単語が出てくると確率は低くなりますが、0にはなりません。

$\displaystyle P(word_i|cat) = \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|}$

Pythonで実装

上のを素直にPythonで実装すると下のようになります。対数をとり、ラプラススムージングを使っています。単語の条件付き確率P(word|cat)の分母は、引数の単語によらないため訓練時に事前に一括計算しています。これを単語の条件付き確率を求めるたびに計算しようとするとものすごく遅くなります。

#coding:utf-8
import math
import sys
from collections import defaultdict

class NaiveBayes:
    """Multinomial Naive Bayes"""
    def __init__(self):
        self.categories = set()     # カテゴリの集合
        self.vocabularies = set()   # ボキャブラリの集合
        self.wordcount = {}         # wordcount[cat][word] カテゴリでの単語の出現回数
        self.catcount = {}          # catcount[cat] カテゴリの出現回数
        self.denominator = {}       # denominator[cat] P(word|cat)の分母の値
    
    def train(self, data):
        """ナイーブベイズ分類器の訓練"""
        # 文書集合からカテゴリを抽出して辞書を初期化
        for d in data:
            cat = d[0]
            self.categories.add(cat)
        for cat in self.categories:
            self.wordcount[cat] = defaultdict(int)
            self.catcount[cat] = 0
        # 文書集合からカテゴリと単語をカウント
        for d in data:
            cat, doc = d[0], d[1:]
            self.catcount[cat] += 1
            for word in doc:
                self.vocabularies.add(word)
                self.wordcount[cat][word] += 1
        # 単語の条件付き確率の分母の値をあらかじめ一括計算しておく（高速化のため）
        for cat in self.categories:
            self.denominator[cat] = sum(self.wordcount[cat].values()) + len(self.vocabularies)
    
    def classify(self, doc):
        """事後確率の対数 log(P(cat|doc)) がもっとも大きなカテゴリを返す"""
        best = None
        max = -sys.maxint
        for cat in self.catcount.keys():
            p = self.score(doc, cat)
            if p > max:
                max = p
                best = cat
        return best
    
    def wordProb(self, word, cat):
        """単語の条件付き確率 P(word|cat) を求める"""
        # ラプラススムージングを適用
        # wordcount[cat]はdefaultdict(int)なのでカテゴリに存在しなかった単語はデフォルトの0を返す
        # 分母はtrain()の最後で一括計算済み
        return float(self.wordcount[cat][word] + 1) / float(self.denominator[cat])
    
    def score(self, doc, cat):
        """文書が与えられたときのカテゴリの事後確率の対数 log(P(cat|doc)) を求める"""
        total = sum(self.catcount.values())  # 総文書数
        score = math.log(float(self.catcount[cat]) / total)  # log P(cat)
        for word in doc:
            # logをとるとかけ算は足し算になる
            score += math.log(self.wordProb(word, cat))  # log P(word|cat)
        return score
    
    def __str__(self):
        total = sum(self.catcount.values())  # 総文書数
        return "documents: %d, vocabularies: %d, categories: %d" % (total, len(self.vocabularies), len(self.categories))

if __name__ == "__main__":
    # Introduction to Information Retrieval 13.2の例題
    data = [["yes", "Chinese", "Beijing", "Chinese"],
            ["yes", "Chinese", "Chinese", "Shanghai"],
            ["yes", "Chinese", "Macao"],
            ["no", "Tokyo", "Japan", "Chinese"]]
    
    # ナイーブベイズ分類器を訓練
    nb = NaiveBayes()
    nb.train(data)
    print nb
    print "P(Chinese|yes) = ", nb.wordProb("Chinese", "yes")
    print "P(Tokyo|yes) = ", nb.wordProb("Tokyo", "yes")
    print "P(Japan|yes) = ", nb.wordProb("Japan", "yes")
    print "P(Chinese|no) = ", nb.wordProb("Chinese", "no")
    print "P(Tokyo|no) = ", nb.wordProb("Tokyo", "no")
    print "P(Japan|no) = ", nb.wordProb("Japan", "no")
    
    # テストデータのカテゴリを予測
    test = ["Chinese", "Chinese", "Chinese", "Tokyo", "Japan"]
    print "log P(yes|test) =", nb.score(test, "yes")
    print "log P(no|test) =", nb.score(test, "no")
    print nb.classify(test)

上のプログラムでは、Introduction to Information Retrieval（IIR）のTable 13.1の例題を使っています。訓練データは、リストのリストで渡します。内側のリストが1つの訓練データです。リストの0番目の要素がカテゴリになります（よく使われる形式）。たとえば、1つめの訓練データは、bag-of-words表現で[Chinese, Beijing, Chinese]という文書がカテゴリyesであることを意味しています。4つの訓練データを与えてナイーブベイズ分類器を学習し、[Chinese, Chinese, Chinese, Tokyo, Japan]という文書のカテゴリを分類器で予測してます。IIRの結果と同じくyesに分類されます。以下、出力結果です。

documents: 4, vocabularies: 6, categories: 2
P(Chinese|yes) =  0.428571428571
P(Tokyo|yes) =  0.0714285714286
P(Japan|yes) =  0.0714285714286
P(Chinese|no) =  0.222222222222
P(Tokyo|no) =  0.222222222222
P(Japan|no) =  0.222222222222
log P(yes|test) = -8.10769031284
log P(no|test) = -8.906681345
yes

まとめ

ナイーブベイズには2つの代表的なモデルがあります。多項モデル（Multinomial Model）とベルヌーイモデル（Bernoulli Model）です。今回、実装したのは多項モデルです。私の印象では、多項モデルの方がよく使われている気がします。ベルヌーイモデルはあまり見かけません。2つの分類精度を比較した論文（McCallum,1998）によるとボキャブラリ数が多い場合は多項モデルの方が精度が高いことが示されています。ベルヌーイモデルは出現しない単語の確率も考慮するので計算量も大きいです。

今回はもっとも基礎的なテキスト分類のアルゴリズムであるナイーブベイズを実装してみました。用いた例題がすごく単純でありがたみがなかったので、次はスパムメールの分類やこのブログの記事カテゴリ（左にカテゴリーメニューってのがあります）を分類してみようと思います。

参考文献

Introduction to Information Retrieval (通称IIR）13章 (PDF) - Webで全文公開されています
F. Sebastiani: Machine Learning in Automated Text Categorization, ACM Computing Surveys, 34(1), 2002. - テキスト分類の包括的なサーベイ。ただし、ちと古い。
A. McCallum and K. Nigam: A Comparison of Event Models for Naive Bayes Text Classification (PDF), AAAI-98 Workshop on Learning for Text Categorization, 1998. - ナイーブベイズの多項モデルとベルヌーイモデルの比較をした有名な論文。
ベイジアン (bayesian)、ベイズ (bayes)、ナイーブベイズ (naive bayes) ってなんですか？ - ナイーブベイズを用いたスパムフィルターで有名なPOPFileの解説
ナイーブベイズによるテキスト分類体験アプリ
新はてなブックマークでも使われてるComplement Naive Bayesを解説するよ

補足

対数をとって大小を比較することで分類結果を出すことはできますが、分類結果を出すだけでなく、テストデータの各カテゴリへの事後確率 P(cat|doc) を求めたいときは下のようにします。

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

の式でP(cat|doc)を計算すればいいわけですが、正規化係数（確率の和が1になるように調整するための係数）の分母のp(doc)を求めるのがけっこう大変です。そのため下のようなよく知られた裏技があります。

    def postProb(self, doc, cat):
        """文書が与えられたときのカテゴリの「正規化していない
       （=p(doc)で割らない）」事後確率 P'(cat|doc) を求める"""
        total = sum(self.catcount.values())  # 総文書数
        pp = float(self.catcount[cat]) / total  # 事前確率P(cat)
        # 尤度 P(doc|cat) = P(word1|cat) * p(word2|cat) * ...
        # 対数をとらないので掛け算になる（非常に小さな値！）
        for word in doc:
            pp *= self.wordProb(word, cat)
        return pp

    # テストデータの各カテゴリへの事後確率を求める
    test = ["Chinese", "Chinese", "Chinese", "Tokyo", "Japan"]
    p1 = nb.postProb(test, "yes")  # 正規化されていないので確率ではない！
    p2 = nb.postProb(test, "no")   # 正規化されていないので確率ではない！
    # 下のようにすると足して1になる確率になる
    print "P(yes|test) =", p1 / (p1 + p2)
    print "P(no|test)  =", p2 / (p1 + p2)

結果は、

P(yes|test) = 0.689758611763
P(no|test)  = 0.310241388237

となり、テストデータがyesである確率は69%、noである確率は31%となり、足すと1になる確率になってます。

もちろん、分母のp(doc)をp(cat1)p(doc|cat1) + p(cat2)p(doc|cat2) + ...のように展開して式どおりに計算しても同じ結果になります。