ベイジアンフィルタの改善 --- Better Bayesian Filtering

これは、Paul Graham： Better Bayesian Filtering を、原著者の許可を得て翻訳・公開するものです。

<版権表示>
本和訳テキストの複製、変更、再配布は、この版権表示を残す限り、自由に行って結構です。
(「この版権表示」には上の文も含まれます。すなわち、再配布を禁止してはいけません)。
Copyright 2002 by Paul Graham
原文: http://www.paulgraham.com/better.html
日本語訳：Shiro Kawai (shiro ＠ acm.org)
<版権表示終り>

Paul Graham氏のエッセイをまとめた『ハッカーと画家』の 邦訳版が出版されました。
出版社の案内ページ Amazon.co.jp サポートページ

2003/02/02 翻訳公開
2003/08/15 原文の改訂および武井伸光さんからの誤記の指摘を反映

(この記事は2003スパムカンファレンスで発表したものである。 私がスパムへの対策で述べたアルゴリズムを どう改善したか、そして今後やろうとしていることについて述べている。)

The first discovery I'd like to present here is an algorithm for lazy evaluation of research papers. Just write whatever you want and don't cite any previous work, and indignant readers will send you references to all the papers you should have cited. I discovered this algorithm after ``A Plan for Spam'' [1] was on Slashdot. -->

まずここで最初に発表したいのは、研究論文の遅延評価アルゴリズムの発見だ。 書きたいことをただ書いて、既存の研究を一切引用しないでおく。 すると、熱心な読者が全ての引用すべき文献への参照を送ってくれるんだ。 「スパムへの対策[1]」がSlashdotに取り上げられた後に、 私はこのアルゴリズムを発見した。

spamフィルタリングは、既に確立されているテキスト分類問題のサブセットである。 が、ベイズ確率を本質的に用いた最初の論文は、 1998年に行われた同じ会議で発表された2本の論文のようだ。 1本はPantelとLinによるもの[2]で、もう1本は マイクロソフトリサーチのグループのもの[3]であった。

このことを聞いた時、私はちょっと驚いた。 ベイジアンフィルタが4年も前から研究されていたなら、 なぜみんなそれを既に使っていないんだろう。 実際に論文を読んでみて理由がわかった。 PantelとLinの方が性能が良かったが、それでも92%のspamしか捕まえられず、 1.16%の誤検出があった。

私が書いたベイジアンフィルタは99.5%のspamを捕まえ、 誤検出は0.03%以下であった[4]。 同じ実験を複数の人間がやって結果が大きく異なる時は要注意だが、 ここではとりわけ警戒が必要だ。この二つの数字は、正反対の結論を導き出し得る。 ユーザーによって要求は異なるものの、 92%のフィルタ率と1.16%の誤検出というのは大多数の人に取って 受け入れがたい方法であり、 99.5%のフィルタ率と0.03%の誤検出なら受け入れられる、という数字では ないかと思う。

どうしてこんなに異なる数値が得られたのだろう。 私はPantelとLinの結果を再現しようとはしなかったが、 論文から、違いをもたらしたと思われる点を5つ見付けた。

一つは、彼らのフィルタを学習させるデータがあまりに少なかったという ことだ。160通のspamメイルと266通のspamでないメイルだ。 このくらいのデータセットでは、まだまだデータの大きさによりフィルタの性能が 向上する領域だ。したがって彼らの数字は彼らのアルゴリズムの性能さえ 正確に反映しているとは言えず、ましてやベイジアンフィルタ一般については 何も言えない。

だが、おそらく最も重要な違いは、彼らはメッセージヘッダを無視したという点だ。 spamフィルタを作ろうとしたことのある人なら誰でも、 この決定は筋が通っていないと感じるだろう。 実は、私も一番最初に書いたフィルタではヘッダを無視していた。何故だろう? 問題を小さくして置きたかったからだ。その頃私はメイルヘッダについて あまり詳しく知らず、そこにはでたらめなデータしかないように思えた。 フィルタを書く人への教訓がここにある。データは決して無視してはいけない。 この教訓はあたりまえすぎるように思えるかもしれないが、 私は幾度かそれを学び直さねばならなかった。

第3に、PantelとLinは単語の語幹を取っていた。つまり、 "mailing" と "mailed" を共に語幹である "mail" として扱っていた。 もしかすると、コーパスの小ささを補うためにそうする必要を感じたのかも しれないが、それは一種の不適切な最適化と呼べるものだろう。

第4に、彼らは異なる確率の計算法を使っていた。 私は最も重要な15単語しか使わなかったのに対し、彼らは全ての単語を使っていた。 全ての単語を使うようにすると、長いspamを逃しがちになる。 長々と彼らの人生の遍歴を語って、最後にマルチ商法で今ではこんなにリッチに なりましたとかいうやつだ。そして、全ての単語を使うアルゴリズムは spam送信者にとってごまかしやすい。spamの単語の効果を打ち消すように 単に大きなランダムなテキストを付け加えてやればいいからだ。

最後に、彼らは誤検出を減らす方向へのバイアスをかけていなかった。 どんなspamフィルタアルゴリズムも、たとえフィルタ率を犠牲にしても 誤検出を減らすことができる便利なつまみを持っているべきだと 私は思う。私のアルゴリズムでは、これはspamでないコーパスに出現する 単語の数を2倍にすることで行われていた。

spamフィルタリングを単なるテキスト分類問題ととらえるのはうまくない。 テキスト分類の手法を使うことはできる。が、解法は分類されるテキストが emailであること、それも特にspamであるという事実を反映したもので なければならない。emailは単なるテキストではない。それは構造を持っているんだ。 spamフィルタはただの分類ではない。誤検出のダメージが見逃しよりもはるかに 悪いため、それらを異なる誤りとして扱わなければならないからだ。 そして誤りの根源はランダムな変化ではなく、 あなたのフィルタを負かそうと熱心に研究しているspam送信者という人間であるからだ。

単語

Slashdotの記事の後で私が知ったもうひとつのプロジェクトは Bill YerazunisのCRM114だった [5]。 これはたった今私が述べた設計原理の正反対をゆくソフトウェアだ。 CRM114はまっとうなテキスト分類装置だが、 spamを取り除いているという意識さえ無しに spamをほぼ完璧に取り除くことができるほど、非常に効果的なものだ。

CRM114の動作原理を理解すると、 いずれは単独の単語に基づくフィルタリングからCRM114のような アプローチへと移ってゆくことは不可欠なように思えてきた。 だがまず私は単独の単語でどこまでいけるか試してみたかった。 そして実際、驚く程遠くまで行けたのだ。

私はもっぱら単語の切り出しを改良することに力を入れて来た。 現在のspamでは、CRM114に近いフィルタ率を得ている。 私の使っているテクニックはBillのものとほぼ直交するものであり、 最適な解法はおそらく両方の手法を採り入れたものになるだろう。

「スパムへの対策」では、単語の定義はごく単純なものだった。 文字、数字、ダッシュ、アポストロフィ、そしてドル記号が 単語を構成する文字であり、それ以外の全ては単語を区切る文字であった。 また、大文字小文字は無視していた。現在はもっと複雑な単語の定義を使っている。

1. 大文字小文字は区別される
2. エクスクラメーションマークは単語を構成する
3. ピリオドとコンマは数字に挟まれた場合は単語を構成する。 これによりIPアドレスや値段の数字がそのまま取り出せる。
4. 幅のある値段、$20-25 のようなものは $20と$25というふたつの単語となる。
5. To, From, Subject, Return-Path, そしてURL内に現われる 単語は、そのように属性がつけられる。例えばSubject行に現われる "foo" は "Subject*foo" となる (アスタリスクは、単語を構成しない文字なら何でも良い)。

このような計測法はフィルタの語彙を増やし、より区別をしやすくする。 例えば現在のフィルタでは、 "free" という単語はSubjectに現われた場合は 98%のspam確率を持つが、本文に現われた場合は65%の確率を持つに過ぎない。

これは現在の確率の例である [6]:

Subject*FREE      0.9999
free!!            0.9999
To*free           0.9998
Subject*free      0.9782
free!             0.9199
Free              0.9198
Url*free          0.9091
FREE              0.8747
From*free         0.7636
free              0.6546

「スパムへの対策」のフィルタでは、これらの単語には全て同じ確率、 0.7602が与えられていた。あのフィルタは約23,000語を認識した。 現在のフィルタは187,000語を認識する。

語彙を増やすことの欠点は、見逃しが増えることだ。 コーパスをより広い語彙空間に適用することは、 コーパスが小さくなるのと同様の効果をもたらす。 エクスクラメーションマークを単語と見倣した場合、 例えば "free" に2つエクスクラメーションマークがついた単語が spam確率99.99%を持っていたとしても、 "free" に7つエクスクラメーションマークがついた単語を見逃してしまうかもしれない。

この問題に対する一つの解決法は、私が還元^{[訳註1]}と呼んでいる ものだ。 もし単語に正確に一致するエントリが見付からなかった場合は、 それよりも特殊化の度合が少ない形態として扱うのだ。 ここで、終端のエクスクラメーションマーク、大文字、生起する文脈、 等が付くと、単語は特殊化されるものとする。 例えば "Subject*free!" に対する確率が見付からなかった場合、 "Subject*free", "free!", "free" といった語の確率を探し、 それらのうちで確率が最も0.5から遠いものを採用するのだ。

以下に示すのは、フィルタが "FREE!!!" をSubject行に見つけて、 しかしその確率が見付けられなかった場合に考慮する代用形態のリストである[7]。

Subject*Free!!!
Subject*free!!!
Subject*FREE!
Subject*Free!
Subject*free!
Subject*FREE
Subject*Free
Subject*free
FREE!!!
Free!!!
free!!!
FREE!
Free!
free!
FREE
Free
free

この方式を使うなら、全て大文字と全て小文字の場合以外に 最初だけ大文字の場合を考慮することを忘れないように。 spamは命令形を多用する傾向があり、その場合、動詞が文頭に使われることになる。 従って、最初だけ大文字の動詞は全て小文字のものよりも高いspam度に なりがちだ。私のフィルタでは、 "act" は62%のspam度だが、 "Act" だと98%になる。

フィルタの語彙をこのように増やして行くと、 (これまでの単語の定義によれば)同じ単語を複数回数えることになる。 論理的には、それらは既にこのアルゴリズムでは同じ単語ではないことになる。 だがどうしてもそれが気になるなら、複数回数えることになる 単語は実際そうしたくなるような単語ばかりだと、私の経験から言っておこう。

語彙を増やすことのもう一つの効果は、新たなメイルを調べる時に、 特徴的な単語、すなわち確率が0.5から離れている単語をより見付けやすくなるということだ。 私はもっとも特徴的な15単語を用いてspamかどうかの判定を行っている。 しかしこのように固定した数の単語を用いていると、問題が生ずる。 確率が0.5から最大限離れた単語ばかりがたくさん見付かってしまった場合、 同じように特徴的な単語が出現する順番によって結果が左右されてしまうからだ。 この問題を避けるには、特徴的な単語のうちでもいくつかをさらに 特徴的と扱うことだ。

例えば "dalco" という単語は私のspamメイル中に3回現われ、 正しいメイル中には一度も現われていない。一方、単語 "Url*optmails" (つまりurl中に現われた "optmail") は1223回出現している。 それでも以前の単語のspam確率の計算法では、 どちらも限界値である0.99となってしまっていた。

これはおかしい。これらの単語に大きく異なる確率を与える理論的な 議論はある (PantelとLinが行っている) が、私はまだそれは試していない。 ただ、少なくとも、片方のコーパスにしか出現しない単語が15個以上見付かった場合は 出現回数が多い方が優先されるべきだとは言えるだろう。 そこで、現在では2種類の閾値を使うようにしている。 spamメイル中にしか出現していない単語のうち、10回より多く出現したものは 確率を0.9999とし、10回以下のものは0.9998としている。 正式なメイル中にしか出現しない単語についても、確率の低いほうの端で 同様に処理している。

いずれはこれらの確率を大きく見直すかもしれないが、 この小さな修正によっても、少なくとも単語が正しくソートされるようには出来る。

別の可能性として、特徴的な15単語だけではなく、ある特徴値以上の 単語を全て考慮する方法も考えられる。Steven Hauserは 彼の統計的spamフィルタでこれを行っている[8]。 もしこの方法を取るなら、閾値は非常に高くとっておくべきだ。 でないとspam送信者は本文にたくさんの無害な言葉を紛れ込ませて フィルタを欺くだろう。

最後に、htmlをどう処理したらいいだろう。 私は全くそれを無視することから、全て構文解析することまで様々な方法を 試してみた。無視するのは得策ではない。その中には有用なspamのしるしが いっぱい詰まっているからだ。しかし全てを構文解析すると、フィルタは 単なるhtml認識器へと退化してしまう。最も有効な方法は、 いくつかのタグのみに着目するという、中道にあるようだ。 私は "a"、"img"、"font" タグのみを調べ、他のものは無視することにした。 リンクと画像は逃すべきではないだろう。それらはurlを含んでいるからだ。

htmlの処理に関してはもっとうまくやれるかもしれないが、 あまり時間をかける価値があるようにも思われない。 htmlでいっぱいのspamは大抵簡単に取り除ける。 賢いspam送信者は既にそれを避けるようになっている。 従って、将来のフィルタの性能はおそらくhtmlをどう処理するかにはあまり 影響を受けないだろう。

性能

2002年12月10日から2003年1月10までの期間に、私はおよそ1750通のspamを 受け取った。このうち、4通がフィルタをすり抜けた。 フィルタ率は99.75%となる。

捕まえ損ねた4通のうち2通は、たまたま私の正式なメイルに現われる単語を たくさん使っていた。

3通目のものは、安全でないcgiスクリプトを悪用して 第3者にメイルを送信するものだった。 この手のものは捕まえるのが難しい。ヘッダは無害に見えるし、 本文に使う単語もspam作成者は気を使っている。 それでも、普通はそういうspamは捕まえられるのだが、 この一通はspam確率0.88と、私の設定した閾値の0.9のぎりぎり下をすり抜けたのだった。

もちろん、複数の単語の連続を見るようにすればこういうのも 簡単に捕まえられるだろう。「以下はあなたのフィードバックフォームの 結果です」というのは一発でアウトだ。

4番目のspamは、私が「未来のspam」と呼ぶものだ。 私はspamがそういうものへと進化してゆくだろうと考えているからだ。 全く中立なテキストと、それに続くurl。 このメイルの場合は、ホームページをやっと作ったので見て下さい、 というメイルだった (そしてもちろんそのページはポルノサイトの広告なのだが)。

spam送信者がヘッダに注意を払い、かつ新しいurlを使うならば、 このような未来のspamに対してフィルタが注目出来る点はない。 もちろん我々はロボットにそのページを見に行かせることで反撃できる。 しかしその必要は無いかもしれない。 このような未来のspamの反応率は相当低いはずだ。 そうでなければ皆がそれをやっているはずだから。 そして、反応率が十分に低ければ、 spam送信者には割の合わない こととなり、結局フィルタが頑張らなくても良いことになるだろう。

さて、ここで衝撃的なニュースだ。この同じ1ヵ月の間に、 私のフィルタは3通の誤検出をした。

誤検出があってほっとした面もある。 私が「スパムへの対策」を書いた時点で誤検出は全くなかったので、 誤検出されるメイルがどんなものか見当がつかなかったのだ。 今、私はそのようなメイルを3通ばかり手にして、 恐れていたほど事態は悪くなかったことにほっとしている。 統計的フィルタが誤検出するメイルは確かにspamによく似たメイルであり、 無くしてしまってもあまり重大でないものでありがちだったからだ[9]。

誤検出されたメイルのうち2通は私が物を購入した会社からの ニュースレターであった。私はそんなものを送ってくれと頼んだ覚えは ないので、それらはspamであると言うことも出来るかもしれないが、 私は今までそれらをspamとして削除してこなったため、誤検出にカウントしておいた。 フィルタがそれらを捕まえた理由はどちらの会社も1月に 彼ら自身のメイルサーバーでなくメイル送信サービス会社を利用するように なっており、ヘッダも本文も共にspamっぽくなっていたからだった。

3通目の誤検出は、しかし、悪いものだった。 それはエジプト在住の人からのもので、全て大文字で書かれていた。 これは単語の大文字小文字を区別するようにしたことの結果だ。 「スパムへの対策」のフィルタはこれを捕まえはしなかっただろう。

全体の誤検出率がいくらかを言うのは、統計的な雑音の領域なので難しい。 フィルタを書いている人なら(少なくとも、それが有効なフィルタなら) この問題に気づいているだろう。 ある種のメイルはそれがspamであるかどうかを定義することが難しく、 フィルタをきつくしていけば結局調べなくてはならないのはそういうメイルに なってくるのだ。例えば現在のフィルタは、送信者の綴りを間違えて 私の元に送られた2通のメイルと、私を誰だか別の人間だと思って 送られたメイルを捕まえた。だが、それらはspamメイルでもspamでないメイルでも無いと も言える。

もう一つの誤検出はvirtumundoの副社長からのもので、 私が顧客を装って出したメイルへの返事だ。 返事はvirtumundoのメイルサーバから来たため、 想像し得る限り最悪のヘッダを持っていた。 これも誤検出かどうかに議論の余地がある。 これはハイゼンベルグの不確定性原理のようなものだ： 私がspamフィルタリングについて書いていたゆえにそれを受け取ったのだから。

これらを勘定に入れないと、私の7740通の正式なメイルのうち、 全部で5通の誤検出があった。誤検出率は0.06%となる。 他の2通のメイルは、私がオンライン購入した商品が入荷待ちになった お知らせと、Eviteからのパーティの通知であった。

この数値はそれほど信頼のおけるものではないと思っている。 サンプル数が少なすぎるし、一方で私はこれらを捕まえないように フィルタを改善できると思っているからだ。

私は誤検出は見逃しとは異なる誤りだと考えている。 フィルタ率は性能を測るが、誤検出はどちらかというとバグのようなものだ。 フィルタ率を上げることは最適化のようなものだが、 誤検出を減らすのはデバッグにあたる。

だから、これら5通の誤検出は私のバグリストにあるわけだ。 例えばエジプトからのメイルは、大文字の本文がフィルタにとっては ナイジェリア絡みのspamに似ているように見えたために捕まえられた。 これは確かにバグと言えるだろう。 htmlと同じように、全て大文字であるということは概念的には メイルの特徴のひとつにすぎず、各単語毎に考慮されるべきではない。 このような場合はより高度な方法で取り扱わねばならないだろう。

さて、この0.06%という数字はどうだろう。たいして大きくないと私は考える。 サンプル数の少なさを考慮に入れた上でも、上限値と考えて良いだろう。 しかしこの数字は現段階では私の実装のバグの量を示す値であって、 ベイジアンフィルタの原理的な誤検出率と考えられるべきではない。

未来

次はどうする? フィルタリングは最適化問題であり、 最適化の鍵はプロファイリングだ。 コードのどこが遅いかを推測してはならない、 なぜなら推測は間違うからだ。 どこが遅いかを実際に見て、そこを修正したまえ。 フィルタリングにおいてはこれは次のように翻訳できる： 逃したspamを見て、それを捕まえるにはどうしたら良いかを考えよ。

例えば、spam送信者は今ではフィルタを逃れる方法を非常に積極的に 模索しており、その一つの方法として彼らは単語を分割したりわざと 誤った綴りを使うことでフィルタがそれらの単語を見逃すように仕向けている。 しかしこの手法への対策は私に取っては重要ではない。これらのspamは まだ容易に捕まえられているからだ[10]。

私を現在悩ましているspamには2種類ある。 一つは女性からのメイルを装い、あなたを彼女とのチャットやデートサイトの 彼女のプロファイルへと誘うものだ。この種のメイルがフィルタをすり抜けるのは、 典型的な売り込み文句を使わずとも売り込むことができるものであるためだ。 それらは通常のメイルと同じ語彙を使っている。

もう一つ、取り除くのが難しいspamは、例えばブルガリアの会社から 送られて来る、プログラミングの契約仕事を請け負うというものだ。 私自身がプログラマであり、プログラマとして日常使うのと同じ単語をこれらのspamは 多く含んでいるため、フィルタを通り抜けてしまう。

まず最初に個人的なメイルを装うタイプに集中するつもりでいる。 おそらく、もっと注意深く調べればそれらのspamと正当なメイルの間に 統計的な差異が見付かるだろうと私は考えている。 確かに文体は異なるからだ。ただ、複数の単語を使うフィルタリングが必要になるかもしれない。 また、この手のspamはurlを繰り返すことが多いことにも気づいた。 正当なメイルはurlを含んでいたとしてもあまり繰り返すことはしない[11]。

契約仕事のタイプは捕まえるのが難しそうだ。 示されたサイトをロボットに見に行かせたとしても、たぶんそこには 煙を上げる統計的な銃は置いていないだろう。 唯一の回答はspamで広告されているドメインの集約されたリストかもしれない[12]。 だが、このタイプのspamはそれほど数は多くないだろう。 もし、受け取るspamがブルガリアからのプログラミングの契約仕事の話だけに なったら、おそらく我々はこの問題を離れることができるだろう。

統計的なフィルタによって我々はそこまで到達することができるだろうか? 私にはわからない。個人的には、現時点でspamは問題ではなくなった。 しかしspam送信者はまだ統計的フィルタを欺く本格的な努力をまだ始めていない。 彼らがそれを始めた時、どうなるだろう?

ネットワークレベルで動作するフィルタに関しては私はあまり楽観していない[13]。 乗り越えるに値する固定した障害があれば、spam送信者は極めてうまく それを乗り越えるだろう。既にあなたのメイルがフィルタされるかどうかを SpamAssasinを通すことで調べてくれるAssurance Systemsという会社がある。

ネットワークレベルのフィルタはしかし全く役に立たないという わけではない。おそらく全ての「オプトイン」spam、つまりVirtumundoや Equalamailがやっているような、オプトインリストを使っていると主張する spamに関しては、その息の根を止めることができるだろう。 本文で何と主張しようと、ヘッダだけでこれらのspamは排除できる。 しかし、ポルノのspam送信者のようにオープンリレーを使って ヘッダをごまかそうとする人間なら、やろうと思えばネットワークレベルの フィルタをすり抜けるメッセージを作れるだろう。 (彼らは何が何でもメッセージを通そうとする。それは侮れない)。

私が希望を持っているフィルタは、個々のユーザーのメイルに基づいて 確率を計算するものだ。それは誤検出を避けるというだけでなく、 spamをフィルタすることについても、ずっと効果的になるだろう。 例えばメッセージ中で受け取り人のemailアドレスにbase-64でエンコードされた 文字列があったら非常に良いspamの指標だという具合だ^{[訳註2]}。

だが、個人的なフィルタの本当の利点は、それらが全て異なるものになる ということだ。誰もが異なる確率を持つフィルタを持っていれば、 spam送信者の最適化は、プログラマがedit-compile-testサイクルと 呼んでいるループに陥り、それはひどく効率の悪いものになる。 彼らが自分のデスクトップで走らせているフィルタをすり抜けるように spamをいじるだけではだめで、何か修正する度にテストとしてメイルを 送信してみなければならないからだ。それはまるでインタラクティブな トップレベルが無い言語でプログラムを書くようなもので、 そんな作業をするはめになったらそれが誰であれ私は同情する。

原註

[1] Paul Graham. ``A Plan for Spam.'' August 2002. http://paulgraham.com/spam.html.

このアルゴリズムの確率は、ベイズの法則を簡略化したものに基づいている。 簡略化のために2つの仮定が置かれている。特徴 (例えば単語) の確率は 互いに独立しているということと、届いたメイルがspamであるかどうかの 事前確率を知らないということだ。

最初の仮定はテキスト分類の分野では広く使われている。 この仮定を使うアルゴリズムはナイーブベイジアンと呼ばれる。

2番目の仮定を置いたのは、私に届くメイルのうちのspam率が日によって (じっさいは時間によって)大きく変動するため、全体の事前確率は 役に立たないと考えたからだ。P(spam) と P(nonspam) が共に0.5ならば、 それらは打ち消し合うので計算から取り除くことができる。

spamとそうでないものの比率が常にひどく高いか(特に)低い場合は、 ベイジアンフィルタリングに事前確率を導入することで性能を上げることが 出来るだろう。正しくやるには、一日のうちの時刻ごとに比率を計測することだ。 spamと正当なメイルの量はそれぞれ一日の中で特有のパターンを描くからだ。

[2] Patrick Pantel and Dekang Lin. ``SpamCop-- A Spam Classification & Organization Program.'' Proceedings of AAAI-98 Workshop on Learning for Text Categorization.

[3] Mehran Sahami, Susan Dumais, David Heckerman and Eric Horvitz. ``A Bayesian Approach to Filtering Junk E-Mail.'' Proceedings of AAAI-98 Workshop on Learning for Text Categorization.

[4] この当時、私の4000通程の正当なメイルのうち、誤検出は0通であった。 もし次に届いたメイルが誤検出となったとしたら、誤検出率は0.03%と なったであろう。もちろんこのような誤検出率は後で説明されるように 信頼できるものではない。ここでは、誤検出率が何であれ1.16%よりは 小さいということを示すためにこの数字を使った。

[5] Bill Yerazunis. ``Sparse Binary Polynomial Hash Message Filtering and The CRM114 Discriminator.'' Proceedings of 2003 Spam Conference.

[6] 「スパムへの対策」では閾値として0.99 と0.01を使った。コーパスの大きさに比例する閾値を使うのは正しいことのように 思える。現在は各タイプのメイルを10000通のオーダーで持っているため、 閾値として0.9999と0.0001を使うようにした。

[7] ここには修正すべき問題がある。現在のところ、"Subject*foo" は単なる "foo" に還元される。これはつまり、 "foo" が本文中もしくはマークされた ヘッダ以外に現われた確率を取ることになる。 本来は、特殊化された確率を取ると同時に "foo" 全体としての確率を 取っておいて、 "Subject*foo" から "foo" ではなく "Anywhere*foo" へと還元 すべきなのだ。大文字小文字についても同じことが言える。 大文字から小文字へではなく、文字種を問わないという形式へと還元すべきだ。

これを値段についても行うと良いかもしれない。 例えば "$129.99" は "$--9.99"、"$--.99"、そして "$--" へと還元されるとか。

また、単語を語幹へと還元することもできるだろうが、 それがフィルタ率を改善するのはコーパスが小さい時だけだろう。

[8] Steven Hauser. ``Statistical Spam Filter Works for Me.'' http://www.sofbot.com.

[9] 誤検出は全て同じではない。spam防止法を比較するときはそのことを 頭に置いておかねばならない。 spamそっくりなために誤検出されたものは多分あまり気にならないだろうが、 例えばブラックリストにより誤検出されてしまったものは、 もしかするとISPの選択を間違った人からの正当なメイルかもしれない。 いずれもspamに近いメイルを捕まえているわけだが、 ブラックリストにおける距離の指標が物理的なものであるのに対し、 フィルタによるものは文体に基づくものだ。

公平のために、SBLのような新しい世代の責任あるブラックリストは、 MAPS RBLのような初期のブラックリストに比べ、 誤検出が遥かに少ないことを付け加えておくべきだろう。 多くの誤検出をわざと起こさせることは、ISPの注意を引き付ける。

[10] このことが問題になるくらいspam送信者がうまく単語をごまかす ことが出来るようになった場合、我々は単に空白やピリオド、コンマを 取り除いて、出来上がった文字列から辞書を使って単語を取り出すことで 対抗できるだろう。元の文に無い単語がこの方法で見付かったとすれば、 それはもちろんspamの良い証拠となる。

単語を取り出すのは単純ではない。 単語の境界を見付ける以上のことが必要になる。 spam送信者は文字を足したり (``xHot nPorn cSite'') 省略したり (``P#rn'') するだろうから。 画像認識の研究は使えるかもしれない。そのようなごまかしは どうがんばっても人間の画像認識能力に反することはできないからだ^{[訳註3]}。

[11] 一般的に、spamは正当なメイルよりも繰り返しが多い。 彼らはとにかくメッセージをあなたの脳天にねじこみたいのだ。 今のところ私は15個の特徴的な単語に重複を許していない。 もし送信者がたまたま悪い単語を複数回使った場合に誤検出となるのを 防ぐためだ。 (私の現在のフィルタでは "dick" は0.9999のspam確率を持っているが、 それは名前でもあり得る)。 しかし、少なくとも重複を検出することはやるべきだと思える。 Brian BurtonがSpamProbeでやっているように、2つまでは重複を許すというのも 試してみようと思っている。

[12] spam送信者がurl以外の文章をmad-libを使って生成するようになった場合、 Brightmailのようなアプローチはこのような手法を使うようにならざるを得ないだろう。

[13] しばしば、ネットワークレベルのフィルタリングに集中した方が 効率が良いのではないかという議論がされることがある。 つまり、ネットワークレベルのフィルタが既にあるのだから、 一からやり直すのは大変だということだ。 だが、回答に適合するように問題を述べることはできない。

歴史的に、ソフトウェアデザインの分野では、 資源が疎であるという議論は勢力を失ってきた。 人々は、他の理由による選択(特に「何かをしない」という選択)を正当化する ときのみ、その議論を持ち出すようだ。

この論文の下書きを読んでくれた Sarah Harlin、Trevor Blackwell、 Dan Giffinに感謝します。またDanはこのフィルタを走らせるための 基盤の多くを作ってくれました。

関連文献

• A Plan for Spam (和訳)
• Plan for Spam FAQ
• 2003 Spam Conference Proceedings
• これらの改善アイディアのテスト

訳註

訳註1：

還元： 原文ではdegeneration。 動詞のdegenerateの意味は文字通りde+generateである。 英和辞書には堕落とか退化、低下といった語が上げられているが、 何がdegenerateされるのかによって訳語は使い分けるべきだろう。 例えば神経学では「変性」という訳語が当てられているらしい。

ここでの用法だが、例えば "free" という基本形から "free!!!" や "Subject*free" が生成(generate)されるのは 特定の生成規則が適用されていると考えて、 そのプロセスを逆に行うわけだから、"degeneration" という語は確かにぴったりくる。 で、「生成」の逆を行う言葉を考えたのだが思い付かなかった。 テキスト分類の分野で定訳がありそうな気がもうれつにするので、 御存知の方は教えて頂けたら幸いである。

なお、「還元」は構文解析におけるreduceの訳語から取った。 あれも一応生成規則を逆に適用していると言えるわけで…

他に考えたのは、「逆生成」(そのまんま)、「退行変化」(長すぎ)、 「縮退」("degeneracy" の訳語として使われている)。

訳註2：

もちろんこれはPaul Grahamの個人的なコーパスに関してそうだというだけで、 日本人と日本語のメイルをやりとりする人にとってはFrom行にbase64エンコードされた 名前が入るのは珍しいことではない。というより、最初にヘッダのbase64エンコーディングを デコードしてからでないと処理にかけられない。

訳註3：

日本語の場合はそもそも単語のセグメンテーションが必須になるわけだ。 逆に日本語のspam送信者が統計的フィルタを誤魔化すことを考え始めたとすると、 見かけのよく似た誤字を使うことは考えられる (「末承諾広告」とかはすぐに 考え付くが、典型的なものはすぐにフィルタに認識されてしまうだろう)。 画像認識からのアプローチは日本語でも有効かもしれない。

日本語のメイルの処理で難しいもののひとつは、縦書きが含まれている メイルだ。個人的メイルでは滅多にないが、メルマガやニュースレターでは よくある。メイル中の装飾的な縦書きを認識するのは面白い問題だろう。