最近話題のベイズ理論を用いたフィルタについて整理してみました．まず，ベ イズ理論が注目され始めたというニュースを最初にみたのが，ＭＳも注目する “ベイズ”って何だ(oricom.co.jp)でした．
このときは対して気にもとめていませんでしたが，再度興味をそそられ出した のが，グーグル、インテル、MSが注目するベイズ理論(CNET)のニュース． MSだけならまだしも，Googleが，というのが自分的には大きかったです．しか し，このニュースだけでは，この技術が具体的にどのように採用されるのか， 特に検索エンジンのような大規模なものに適用可能かどうかは大きな疑問でし た．
そもそも，このベイズ理論がどこに聞いてくるのかということを考えるとその 疑問は自然だと思います．ベイズ理論（ベイズ推定）は，過去に起きた事象の 確率を利用して未来を予測する手法です．そのため，直感的にはユーザごとの 最適化という方向に対して有力に働くというのは明らかでしょう．また，検索 エンジンのような情報提供システムでは，提供した情報に対するフィードバッ ク（クリック）を検索順位に用いるというのもある意味ではこのベイズ理論を 用いたことになるのかもしれません．
ベイズ理論を用いた応用例にはこの時点では漠然として特にイメージは持って いませんでした．
身近なアプリケーションとして登場した最初のものが，（私の知る限り）スパ ムフィルタです．スパムフィルタとして有効な理由は，スパムとノンスパムの データ系列（単語）に大きな違いがあるからです．スパムメールはその性質上， 商品なりサービスの宣伝を行っています．そのため，使用される単語に一定の 特徴がでてくることになり，過去の情報を有効に利用すればスパムメールを判 定することが可能になるわけです．
スパム判定のアルゴリズム自体は様々な手法が提案されており，複数の実装がでてい ます．Webで探した中で有効な情報源として，A Plan for Spamおよび，Better Bayesian Filtering(shiro.dreamhost.com)があります．Spam Detection(radio.weblogs.com)も英語ですが，参考になるでしょう．
詳細なアルゴリズムは各ページに譲りますが，大筋のストーリは以下のように なります．
ここで肝となるのは，スパム確率をデータベースに格納するところと，最終的 な確率の計算の式でしょう．
Paul Graham方式では，トークンごとのスパム確率を pg(w)$ とおいています．ノンスパムへの判定にバイアスをかけるために，ノンスパム 中に登場したトークンの登場個数を2倍にしています．つまり，あるトークン wがスパムとして登場した回数を b, ノンスパムとして登場した回数を g と します．また，スパムのメール総数を nbad, ノンスパムのメール総数を ngood とします．このとき，w のスパム確率 pg(w) は，
b ----- nbad pg(w) = ---------------- 2*g b ----- + ----- ngood nbad
で与えられることになります．スパムにしか登場しないものは確率0.99，ノン スパムにしか登場しないものは確率0.01が与えられます．また，b+2*g が5よ り小さいものについても計算しないことにしています．
最終的なスパム判定は，各トークンのスパム確率が0.5から離れているもの 15個を選んで，複合確率を計算します．また，このときデータベースにないトー クンのスパム確率として0.4を使用します．複合確率は，いまパラメータが3つ (a, b, c)の場合，以下のようになります．
abc --------------------------- abc + (1 - a)(1 - b)(1 - c)
最終的に計算された複合確率が0.9を超えた場合にスパムと判定されます．
Gary Robinson方式は Paul Graham 方式の改良といわれています． トークンごとのスパム確率をf(w)とすると，f(w) は以下のように求めます．
まず，トークンごとのスパム出現確率 p(w) をバイアスをかけずに求めます． また，全トークンの p(w) の平均値を x とし，トークンの出現回数をn，ある 定数（たとえば0.001）をsとしたときに，f(w) は，
(s * x) + (n * p(w)) f(w) = --------------------- s + n
で与えられます．データベースにない新しく遭遇したトークンの確 率も同様に計算します．このとき，あるメールのスパムである確率は
P = 1 - (1 - f(w1)) * (1 - f(w2)) *...* (1 - f(wn) )^(1 / n) [spamminess] Q = 1 - (f(w1) * f(w2) *...* f(wn))^(1 / n) [nonspamminess] S = (P - Q) / (P + Q) [combined indicator] S2 = (1 + S) / 2
の S2 で与えられます．
ここまでは，既存のアルゴリズムについて簡単な紹介をしました．これを実際 に日本語について適用しようと考えて場合には，トークンをなににするかとい う問題が必ず発生します．日本語対応のスパムフィルタの中には，形態素解析 をしているものもありますし，bi-gramやtri-gramで対応しているものもあり ます．しかし，n-gram方式では，日本語のひらがな同士の結合で多量のトーク ンをはき，スパム確率を計算する際によけいな情報になりかねません．そのた め，形態素解析が比較的適しているといえます．しかし，形態素解析を施す対 象がメールということもあり，正しい日本語でない場合もしばしばあります． 特に間柄が親しければ親しいほど形態素解析しづらい日本語になるでしょう．
そこで，個人的な考えですが，2文字以上連続する漢字，カタカナ，英数字を トークンとして扱う方法はどうかな，と考えています．実証実験したわけでは ないので，データはありませんが，文章の特徴を表すトークンとしては十分な ものになるのではないかと考えています．
また，ベイジアンフィルタを別のシステムに適用した場合にどうなるかという ことについても今後いろいろと考えていかなければなりません．個人的試行錯 誤してみます．