今回は、前回の最後で説明したナイーブベイズの応用である「ベイジアンフィルタ」をPythonで実装しながら、実際に確率の計算がどのように行われるかをみていきましょう。

ベイジアンフィルタとは

ベイジアンフィルタとは、ナイーブベイズ（Naive Bayes）というアルゴリズムを利用して、テキストの自動分類などに応用することのできるフィルタの総称です。

このベイジアンフィルタは、現在では様々なところで応用されているのをご存知ですか？　有名なところではメールのスパム判定やブログのカテゴリ分類に利用されています。

例えばベイジアンフィルタによるスパム判定では、事前に手動でメールをスパムとハムというカテゴリに分類しておきます。これにより、メールの傾向を学習し出現する単語から自動的に新しく届いたメールが「スパムメールか否か」と分類できるようになります。つまり、スパムメールに含まれている文字集合と通常のメールに含まれる文字集合の確率を計算し、スパムメールか否かを判断しているのです。

ベイジアンフィルタがメールのスパム判定として利用される契機となったのは『ハッカーと画家』（⁠オーム社）の執筆でも有名なPaul Graham氏が2002年に発表した「A Plan for Spam（スパムへの対策）」という論文です。この論文によって、スパム判定に統計的なアプローチが用いられることが注目されるようになりました。

先述のようにベイジアンフィルタは、事前に与えられたパターン（情報）にしたがって未知の文章を分類します。事前に正しいデータを与え学習を行うので、「⁠教師あり学習（Supervised Leaning⁠）⁠」と呼ばれる機械学習の手法の一つになります。

「教師あり学習」があるということは「教師なし学習」もありそうですよね？　今後の連載の中で「教師なし学習」も紹介する機会があると思いますので楽しみにしていてください。

環境構築

本連載では基本的にプログラミング言語にPythonを使って実装していきます。バージョンは2.6.1を利用します。

Pythonでは大規模な多次元配列や行列をサポートしている拡張モジュール「Numpy」の提供する高水準の数学関数ライブラリ、それを基礎として統計や最適化、線形代数などのモジュールを提供する科学技術計算のためのライブラリ「SciPy」などの数値解析モジュールが充実しているため、数値計算をとても簡単に行えます。

また、グラフモジュールとして「Matplotlib」なども存在しているため、可視化も簡単に行うことができます。

bag-of-wordsを利用したテキスト分類

それでは早速、ベイジアンフィルタの実装を始めていきましょう。ベイジアンフィルタを実現するのは、何度も言及しているナイーブベイズというアルゴリズムです。

ナイーブベイズは簡単な計算でよい結果のでる「いいモデル」と前回紹介されていますが、実装も計算と同じようにそう難しくありません。

今回は、ベイジアンフィルタを利用して文章をそれぞれのカテゴリに分類してみたいと思います。ベイジアンフィルタを文章と文章が属するカテゴリで訓練して、受け取った文章がどのカテゴリに分類されるかを見ていきます。

一般的に文章を分類するためには何が必要になるでしょうか。それは文章に含まれている特徴になります。 今回は文章の中に出現する単語を出現する順番を意識せずに特徴として扱います。このように文脈に依存しない、単語が文章内のどこに登場するか考慮しないようなテキスト表現をbag-of-wordsと呼びます。バッグの中にごちゃごちゃと単語が入っているようなイメージです。

例えば、以下の文章を考えてみます。

これらは「機械学習」という技術を使って実現されているのです。

この文章ををbag-of-wordsで表現すると、以下のような単語の集合になります。

「これら」、「機械」、「学習」、「技術」、「実現」

文章を形態素に分割する

今回は日本語を含む文章から単語の集合を作るにあたって「形態素解析」を用いることにします。

英文の場合は単語がスペースによって分割されているため、スペースで区切られた文字列を抽出することで単語を取得できます。しかし、日本語にはそのような「わかち書き」の習慣がありません。そこで、形態素解析を用いて文脈の解析や単語の分解を行う必要があります。

形態素解析ライブラリとしてはMeCabやChaSenなどが有名ですが、今回はYahoo!デベロッパーズネットワークの日本語形態素解析を利用してみます。利用するにあたって、Yahoo!デベロッパーネットワークのアプリケーションIDを取得する必要があります。Yahoo!のIDさえ持っていれば、こちらから登録するだけで利用できます。

また、今回はXMLの解析にBeautifulSoupというライブラリを利用しています。BeautifulSoupでは特定のタグの抽出やソートを簡単に行え、多少の文法の誤りを修正してくれるなど比較的柔軟に使うことができます。BeautifulSoupはここからダウンロードすることができます。本稿ではBeautifulSoup-3.0.8を使います。

# -*- coding: utf-8 -*-
import urllib
import urllib2
from BeautifulSoup import BeautifulSoup

appid = 'Yahoo!デベロッパーズネットワークのアプリケーションIDを入力して下さい'
pageurl = "http://jlp.yahooapis.jp/MAService/V1/parse";

# Yahoo!形態素解析の結果をリストで返します。
def split(sentence, appid=appid, results="ma", filter="1|2|3|4|5|9|10"):
  sentence = sentence.encode("utf-8")
  params = urllib.urlencode({'appid':appid, 'results':results, 'filter':filter,'sentence':sentence})
  results = urllib2.urlopen(pageurl, params)
  soup = BeautifulSoup(results.read())
  
  return [w.surface.string for w in soup.ma_result.word_list]

リスト1のコードをmorphological.pyという名前で保存します。保存時の文字コードにはutf-8を指定してください。このコードではYahoo!JAPANの日本語形態素解析サービスに入力された文章を渡しています。そして、XMLで返される結果をBeautifulSoupでパースしています。

引数のfilterで解析する品詞の種類を指定することができます。filterに指定可能な品詞番号は以下のようになっています（表1⁠）⁠。

さらに詳細な利用方法が知りたい方は、Yahoo!デベロッパーズネットワークのマニュアルを参照してください。

ベイジアンフィルタの実装

ここから本格的にベイジアンフィルタの実装に入っていきます。

その前に、まずは先程のリスト1のコードを利用して入力された文章をわかち書きし、単語の集合を返す関数を作成しnaivebayes.pyとして保存しましょう。こちらも先程のmorphological.pyと同様にutf-8で保存してください。

# -*- coding: utf-8 -*-
import math
import sys
#yahoo!形態素解析
import morphological

def getwords(doc):
    words = [s.lower() for s in morphological.split(doc)]
    return tuple(w for w in words)

それでは、これから訓練と推定を行なう NaiveBeyse クラスを実装していきましょう。訓練フェーズでは入力された文章とカテゴリからナイーブベイズに必要な値に変換し、クラス内部に保持します。

具体的には確率値を計算することになるため、カテゴリの登場回数や単語の出現回数などを保持することになります。この訓練フェーズにより、入力された文章のカテゴリを推定することが可能になります。

そして、推定フェーズでは入力された単語が各カテゴリでどの程度出現しているかを訓練フェーズで保存した情報を元に計算します。訓練の結果に対して最も高い確率だったカテゴリが推定結果となります。

ナイーブベイズのアルゴリズム

ここで、ナイーブベイズのアルゴリズムを確認しましょう。ナイーブベイズは確率論に基づいたアルゴリズムになりますので簡単な確率式を使って説明していきます。

ナイーブベイズにおいてのカテゴリの推定とは、ある文章が与えられた時にその文章がどのカテゴリに属するのが「もっともらしいか」を単語の出現確率から求めます。この「もっともらしい」度合いを統計学などでは尤度（ゆうど）と呼びます。

今回は文章（doc）が与えられた時、カテゴリ（cat）に属する確率 P(cat|doc) を求める問題になります。入力された複数のカテゴリの中でもっとも高い値となったカテゴリが最終的に選択されることになります。この条件付き確率を直接計算するのは難しいのですが、「⁠ベイズの定理」を使うことにより簡単に計算することができます。

前回と同じように確率の乗法定理を使って展開してみましょう。

P(cat, doc)
= P(cat|doc)P(doc)
= P(doc|cat)P(cat)

第2式と第3式を使うことで、P(cat|doc) は以下の式で求められることが分かります。

P(cat|doc) = P(doc|cat)P(cat) / P(doc)

カテゴリの推定では、具体的な確率の値ではなく与えられた複数のカテゴリの中でどのカテゴリになる確率が一番高い順位であるかという情報が必要になります。分母の P(doc) は文章が生起[1]する確率になりますが、こればどのカテゴリでも同じ値になるので今回は分子を比較するだけで事足ります。

では、次に分子の P(doc|cat)P(cat) について考えてみましょう。P(cat) はカテゴリが生起する確率になります。ここでも色々なモデルを考えることができますが、今回は「訓練データとしてカテゴリが与えられた件数/総文書数」で求めることにしましょう。そのため、ナイーブベイズの訓練フェーズではカテゴリの登場回数を保存しておけばよいのです。

次に P(doc|cat) ですが、これはあるカテゴリが与えられた時の文章の生起確率になります。ここで先ほど文章をbag-of-wordsの形にしたことを思い出してください。単語をbag-of-wordsの形にすることで、文脈や単語の出現位置を無視しましたよね。本来は「python」は「プログラム」と共起[2]しやすいし「機械」と「学習⁠」⁠」も共起しやすいはずです。 しかし、これを無視して単語の独立性を仮定します。この大胆な仮定により、文章の確率を単語の確率の積として単純化するのがナイーブベイズを「ナイーブ（単純な⁠）⁠」と呼ばれる理由です。

文章は分割した単語（word）の集合であるので単語の独立性を仮定すると、以下のように近似することができます。

P(doc|cat) = P(word1|cat) P(word2|cat) ... P(wordn|cat)

P(wordn|cat) の確率は分割した単語があるカテゴリに属する確率（単語の条件付き確率）を求めることで文章の生起確率が分かります。これはあるカテゴリに単語が出現した回数をカテゴリに出現した全単語数で割ることで求められます。

したがって、訓練フェーズでは出現した単語があるカテゴリに分類された回数を保存しておけばいいことが分かります。つまり、ナイーブベイズでは各カテゴリの登場回数と、ある文章があるカテゴリに分類された回数を保存しておけばいいのです。推定を行う時は、以上の保存された情報から P(doc|cat)P(cat) をカテゴリ毎に計算します。

訓練フェーズの実装

アルゴリズム全体の概要を把握したところで、訓練フェーズで何をすればいいのか理解できたはずです。訓練フェーズでは train() メソッドを使って、カテゴリの出現回数とあるカテゴリの中に単語が現れた回数を保存します。

まずはコンストラクタと訓練フェーズの実装について見てみましょう（リスト3⁠）⁠。入力として、文章とカテゴリを受け取ります、入力された文章を分割し変数 wordcount にカテゴリに各単語が分類された回数を、変数 catcount にカテゴリの登場回数を保存しています。また、変数 vocabularies には重複を削除した単語の総数を保存しています。これは後述するスムージングに利用します。

class NaiveBayes:
  def __init__(self):
    self.vocabularies = set() # 単語の集合
    self.wordcount = {}       # {category : { words : n, ...}}
    self.catcount = {}        # {category : n}

  def wordcountup(self, word, cat):
    self.wordcount.setdefault(cat, {})
    self.wordcount[cat].setdefault(word, 0)
    self.wordcount[cat][word] += 1
    self.vocabularies.add(word)

  def catcountup(self, cat):
    self.catcount.setdefault(cat, 0)
    self.catcount[cat] += 1

  def train(self, doc, cat):
    word = getwords(doc)
    for w in word:
      self.wordcountup(w, cat)
    self.catcountup(cat)

推定フェーズの実装

続けて、推定フェーズの実装を見ていきましょう。最終的には推定したカテゴリを返すclassifier()メソッドを見ることになるのですが、それに必要な P(cat) や P(wordn|cat) を算出するためのメソッドを確認していきます。

まずは、P(cat) の生起確率を求めていきます（リスト4⁠）⁠。先ほど説明したように、cat の生起確率 P(cat) は「訓練データとしてカテゴリが与えられた件数/総文書数」で算出することができます。priorprob()は P(cat) を求めるメソッドです。

  def priorprob(self, cat):
    return float(self.catcount[cat]) / sum(self.catcount.values())

次に、cat に word が含まれる条件付き確率 P(word|cat) を求めます（リスト5⁠）⁠。ここでは、先ほどのカテゴリの中に単語が現れた回数とカテゴリに出現した単語の総数で算出することができます。

しかし、ここで1つ大きな問題があります。このままでは訓練データに出現しなかった特徴 word_i が現れたときに出現確率 P(word_i|cat) が0になってしまいます。この問題をゼロ頻度問題やスパースネスの問題と呼びます。

普通に考えて、単語の出現頻度が0だからといって世の中にその単語がカテゴリに属する確率が0にならないことは分かりますよね。この時、ゼロ頻度問題を回避するために、訓練データから得られる単純な推定値を用いるのではなく、何らかの形で補正する必要があります。この補正操作のことをスムージング（smoothing）と呼びます。

今回のように一様な値を加えるスムージングを加算スムージングと呼びます。加算スムージングでは単語の出現回数に一定数の値を加え、出現回数0の単語をなくす方法です。なかでも、今回のように1を加えるものをラプラス法、実数に一般化したものをリッドストーン法と呼びます。加算スムージングは単純であり簡単に実現できますが、一般的に精度が悪いことが知られています。精度の高いスムージングの方法としては線形補間法やヘルドアウト補間法などがあります。

  def incategory(self, word, cat):
    #あるカテゴリの中に単語が登場した回数を返す
    if word in self.wordcount[cat]:
      return float(self.wordcount[cat][word])
    return 0.0

  def wordprob(self, word, cat):
    # P(word|cat) が生起する確率を求める
    prob = \
      (self.incategory(word, cat) + 1.0) / \
          (sum(self.wordcount[cat].values()) + \
           len(self.vocabularies) * 1.0)
 
   return prob

しかし、ゼロ頻度問題を解決してもまだ1つ問題があります。確率値は1以下の非常に小さな値であり、しかも文章の中にはたくさんの単語が含まれています。そのため P(word|cat) の積を求めていくと、とても小さな値になってしまい、アンダーフローを起こす可能性があるのです。

それに対応するために対数をとり、積の計算を和の計算に変換します。ここで最終的に求めたいものは確率の値そのものではなく、事後確率の大小関係なので対数をとってもその関係は変化しないので問題はありません。リスト6の score() メソッドでスコア（＝確率値の対数）を算出しています。

  def score(self, word, cat):
    score = math.log(self.priorprob(cat))
    for w in word:
      score += math.log(self.wordprob(w, cat))
    return score

カテゴリの推定

あとは、そのカテゴリに属する確率の中からもっとも高い確率のものを決定すればいいでしょう（リスト7⁠）⁠。以上でベイジアンフィルタの実装は完了します。

  def classifier(self, doc):
    best = None # 最適なカテゴリ
    max = -sys.maxint
    word = getwords(doc)
    
    # カテゴリ毎に確率の対数を求める
    for cat in self.catcount.keys():
      prob = self.score(word, cat)
      if prob < max:
        max = prob
        best = cat

    return best

実行してみよう

それでは、実際に動かして確認してみましょう。実行のためにnaivebayes.pyに以下のコードを追加しましょう（リスト8⁠）⁠。

今回、訓練データとして入力する文章はWikipediaにあるそれぞれの概要の文章を抜粋しました。この文章をそれぞれの項目「Python」「⁠Ruby」「⁠機械学習」のカテゴリとして分類したあとにカテゴリの推定を行います。

if __name__ == "__main__":
  nb = NaiveBayes()

  nb.train(u'''Python（パイソン）は、オランダ人のグイド・ヴァンロッサムが作ったオープンソースのプログラミング言語。
オブジェクト指向スクリプト言語の一種であり、Perlとともに欧米で広く普及している。イギリスのテレビ局 BBC が製作したコメディ番組『空飛ぶモンティパイソン』にちなんで名付けられた。
Python は英語で爬虫類のニシキヘビの意味で、Python言語のマスコットやアイコンとして使われることがある。Pythonは汎用の高水準言語である。プログラマの生産性とコードの信頼性を重視して設計されており、核となるシンタックスおよびセマンティクスは必要最小限に抑えられている反面、利便性の高い大規模な標準ライブラリを備えている。
Unicode による文字列操作をサポートしており、日本語処理も標準で可能である。多くのプラットフォームをサポートしており（動作するプラットフォーム）、また、豊富なドキュメント、豊富なライブラリがあることから、産業界でも利用が増えつつある。''', 'Python')

  nb.train(u'''Ruby（ルビー）は、まつもとゆきひろ（通称Matz）により開発されたオブジェクト指向スクリプト言語であり、従来 Perlなどのスクリプト言語が用いられてきた領域でのオブジェクト指向プログラミングを実現する。Rubyは当初1993年2月24日に生まれ、 1995年12月にfj上で発表された。名称のRubyは、プログラミング言語Perlが6月の誕生石であるPearl（真珠）と同じ発音をすることから、まつもとの同僚の誕生石（7月）のルビーを取って名付けられた。''', 'Ruby')

  nb.train(u'''豊富な機械学習（きかいがくしゅう、Machine learning）とは、人工知能における研究課題の一つで、人間が自然に行っている学習能力と同様の機能をコンピュータで実現させるための技術・手法のことである。ある程度の数のサンプルデータ集合を対象に解析を行い、そのデータから有用な規則、ルール、知識表現、判断基準などを抽出する。データ集合を解析するため、統計学との関連も非常に深い。
機械学習は検索エンジン、医療診断、スパムメールの検出、金融市場の予測、DNA配列の分類、音声認識や文字認識などのパターン認識、ゲーム戦略、ロボット、など幅広い分野で用いられている。応用分野の特性に応じて学習手法も適切に選択する必要があり、様々な手法が提案されている。それらの手法は、 Machine Learning や IEEE Transactions on Pattern Analysis and Machine Intelligence などの学術雑誌などで発表されることが多い。''', u'機械学習')

#Python
words = u'ヴァンロッサム氏によって開発されました.'
print u'%s => 推定カテゴリ: %s' % (words ,nb.classifier(words))

words = u'豊富なドキュメントや豊富なライブラリがあります.'
print u'%s => 推定カテゴリ: %s' % (words ,nb.classifier(words))

#Ruby
words = u'純粋なオブジェクト指向言語です.'
print u'%s => 推定カテゴリ: %s' % (words ,nb.classifier(words))

words = u'Rubyはまつもとゆきひろ氏(通称Matz)により開発されました.'
print u'%s => 推定カテゴリ: %s' % (words ,nb.classifier(words))

#機械学習
words = u'「機械学習 はじめよう」が始まりました.'
print u'%s => 推定カテゴリ: %s' % (words ,nb.classifier(words))

words = u'検索エンジンや画像認識に利用されています.'
print u'%s => 推定カテゴリ: %s' % (words , nb.classifier(words))

以下の結果のように、期待していたカテゴリに分類されました（リスト9⁠）⁠。

% python naivebayes.py
ヴァンロッサム氏によって開発されました. => 推定カテゴリ: Python
豊富なドキュメントや豊富なライブラリがあります. => 推定カテゴリ: Python
純粋なオブジェクト指向言語です. => 推定カテゴリ: Ruby
Rubyはまつもとゆきひろ氏(通称Matz)により開発されました. => 推定カテゴリ: Ruby
「機械学習 はじめよう」が始まりました. => 推定カテゴリ: 機械学習
検索エンジンや画像認識に利用されています. => 推定カテゴリ: 機械学習

「オブジェクト指向言語」のように複数のカテゴリに登場している単語でも、それ以外の単語の出現によって正しく分類されているのが分かると思います。

今回は訓練データとして各カテゴリに対して1件ずつしか用意していませんが、冒頭で説明したスパム判定ではだいたい4,000件のデータを使ってトレーニングしているようです（訓練データが増えることによって、より正確な分類ができるようになるので興味のある方はご自身で試してみてください⁠）⁠。

今回実装したベイジアンフィルタはとても簡単なものです。ベイジアンフィルタは色々な言語のオープンソースプロジェクトでも開発されているので見比べてみるのも面白いかもしれません。

次回のお知らせ

次回の理論編では正規分布を説明します。