スパムへの対策 ---A Plan for Spam

Paul Graham, August 2002

これは、Paul Graham:A Plan for Spam を、原著者の許可を得て翻訳・公開するものです。

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

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

2003/01/18 翻訳公開
2003/02/02 原文の改定(「ベイジアンフィルタの改善」へのリンク追加)を反映
2005/02/08 片方のコーパスにしか出てこない単語の扱いについて訳註を追加


(この記事は我々がArc を試用して書いているspam防止機能つきwebベースのメイルリーダに 使われているspamフィルタのテクニックを解説したものである。 より改善されたアルゴリズムに関しては ベイジアンフィルタの改善で述べている。)

spamを止めることは可能だ。 そして内容に基づいたフィルタリングがその方法だ。 spamを送る連中のアキレス腱は、彼らのメッセージだ。 あなたがどんな障壁を築こうとも、彼らはそれをすり抜ける方法を見つける。 少なくとも今まではそうだった。だが彼らは、何であれメッセージを 届けなければならない。彼らのメッセージを認識できるソフトウェアを 書くことができれば、彼らの道を絶つことができる。

_ _ _

メイルを受け取った人にとって、spamを識別するのはたやすい。 誰かを雇って自分宛に届くメイルのspamだけ捨ててくれるように 頼んだとしても、きっとうまくやってくれるだろう。 AIをまだ手にしていない現在、その手続きはどこまで自動化できるだろう。

私は、この問題はかなり単純なアルゴリズムで解決できるんじゃないかと 思っている。実際、個々の単語のspam確率を単純にベイズの結合確率で計算するだけで、 現在のspamのかなりの部分を取り除けることがわかった。 これから述べるような、ちょっとした改良を加えたベイジアンフィルタでは、 1000通のspam中で逃すspamが5通以下で、しかも誤検出は0通というところまで来ている。

spamフィルタを書こうとする人はあまり統計的手法を最初に試したがらない。 多くのハッカーは当初、直観的に、spamの個々の特徴を認識するソフトウェアを 書こうとする。spamを眺めてこう思う。 ふむ、こいつら厚かましい奴らは本文が "Dear Friend" で始まるか、 全部大文字で最後に!が8つくらい続く表題をつけてメイルを送ってきやがるな。 一行コードを書けばそのくらいは取り除けるさ。

そしてやってみると、最初のうちはうまく動く。 ほんの2〜3の簡単な規則でもって、spamの大部分は除けるんだ。 例えば "click" という単語を探すだけで、 私のspamコーパスの79.7%は捕まえられるし、誤検出は1.2%だ。

私は統計的手法を試す前に、spamの個々の特徴を抽出する ソフトウェアを書くのに6ヵ月ばかり費した。 そして分かったことは、最後の数%のspamを捕まえるのはとても大変になる ということと、規則を厳しくすればするほど誤検出が増えてしまうということだった。

誤検出とは、無害なメイルなのにspamと認識されてしまうメイルのことだ。 多くのユーザにとって、正しいメイルを失うことは spamを受け取るよりも何十倍もダメージが大きい。 誤検出をしてしまうフィルターは、まるで死の危険のあるニキビ薬みたいなものだ。

受け取るspamが増えれば増える程、 ユーザーは誤検出されてspamフォルダに行ってしまった無害なメイルに気づきにくくなる。 そして奇妙なことに、spamフィルタの性能が良くなればなるほど、 誤検出の危険は増して行くのだ。というのは、フィルタが十分に良ければ ユーザはそれに信頼を置いて、それがspamと判断したものは無視するようになるからだ。

どうして私は、なかなか統計的手法を試さなかったんだろう。 たぶん、自分でspamの特徴を見付けるゲームにはまっていたんだとおもう。 それはspam業者との一種の競争だった (ハッカーでない人は知らないかもしれないが、 大抵のハッカーは非常に競争好きだ)。 統計的手法を試してみたらすぐに、私はそれが自分よりずっと賢いことに気づいた。 統計的フィルタはもちろん "virtumundo" とか "teens" がspamの良い指標だと いうことを見付けたが、また "per" や "FL" や "ff0000" もそうだということも 見付けたのだ。実際、 "ff0000" (HTMLメイルで真っ赤の文字を表示するのに 使われる) はポルノ用語と同じくらい、spamの良い指標なのだ。

_ _ _

では私が使っている統計的フィルタリングの概略を説明しよう。 まず、spamメイルとspamでないメイルをそれぞれ集めたコーパスを作る。 今のところどちらにも4000通くらいのメッセージがある。 次に各集合中の全てのテキストを、ヘッダーも本文中のHTMLもjavascriptも いっしょくたにスキャンする。今のところは、 アルファベット、数字、ダッシュ、アポストロフィ、そして$マークを トークンの構成要素とみなしている (おそらくここは改善の余地があるだろう)[訳註1]。 全て数字のトークンと、HTMLのコメントは無視する。 後者はトークンの区切りともみなさない。

次に各トークンがそれぞれの集合に現われた回数を数える。 (今のところ大文字小文字は無視している)。 ここまでで、トークンから出現回数を得ることのできる大きなハッシュテーブルが、 両集合に対して得られたことになる。

次に、各トークンから、そのトークンが含まれるメイルがspamである確率を 得る第3のハッシュテーブルを次のようにして計算する[1]:

(let ((g (* 2 (or (gethash word good) 0))) (b (or (gethash word bad) 0))) (unless (< (+ g b) 5) (max .01 (min .99 (float (/ (min 1 (/ b nbad)) (+ (min 1 (/ g ngood)) (min 1 (/ b nbad)))))))))

ここで、wordは確率を計算する単語、 goodbadは 第一ステップで作ったハッシュテーブル、そして ngoodnbadは それぞれspamでないメイルとspamメイルの総数である。

ここでコードを見せたのは、いくつか重要な詳細を説明したいからだ。 まず、私は誤検出を避ける方向にバイアスをかけたかった。 試行錯誤の結果、goodの中の単語の生起回数を 2倍にするのが良いことがわかった。 これは、正当なメイル中にたまに出現し得る単語と、ほとんど全く出現しない 単語とを区別するのに役立つ。 また全体で5回以上出現していない単語は計算から外している (実際は正当なメイル中の単語は倍にしているので、正当なメイル中に3回 単語が現われていれば考慮されることになる)。 一方の集合にのみ現われる単語の確率はどうするかという問題もあるが、 これも試行錯誤から0.01と0.99とした[訳註2]。 ここには調整の余地があるかもしれないが、集合が大きくなればそのような調整は 自動的に行われるだろう。

注意深い人なら、私が単語の生起回数を数えるのには各集合をひと続きの 長いテキストストリームと見倣しているのに対し、 分母の方にはメイルの長さの合計ではなくメイルの数を使っていることに気づいただろう。 これも誤検出を避ける方向にバイアスとして働く。

新しいメイルが届くと、それはトークンへと分解され、 最も特徴的な15トークンが抽出され、それをもとにメイルがspamである 確率が計算される。 ここで特徴的とは、その単語のspam確率が0.5から遠く離れていることとする。 probsを15のトークンそれぞれの確率とした場合、 その結合確率は 次のように計算される。

(let ((prod (apply #'* probs))) (/ prod (+ prod (apply #'* (mapcar #'(lambda (x) (- 1 x)) probs)))))

もうひとつ、 一度も見たことのない単語、すなわち単語の確率のハッシュテーブルに 登録されていない単語に対していくら確率を割り当てるかという問題がある。 これも試行錯誤から、0.4が良いということがわかった。 一度もその単語を見たことが無ければ、その単語は無害なものであることが多い。 spamに出て来る単語はどれもどこかで見たようなものばかりだからだ。

付録にいくつかこのアルゴリズムを実際のメイルに適用した例をあげておく。

上記のアルゴリズムが0.9以上の確率を返した場合、私はそのメイルを spamと判断する。実際にはこの閾値はあまり問題ではない。 確率が中くらいになるメイルはほとんど無いからだ。

_ _ _

統計的手法の良いところのひとつは、たくさんのspamに目を通さなくても良いことだ。 過去6ヵ月に渡って私は文字通り何千というspamを読んで来たが、 げんなりするような体験だった。Norbert Wienerは 奴隷と競争するものは奴隷になると言ったが、 spam業者と競争するのもそれに似た点がある。 spamの特徴をとらえようとするには、spam業者の思考の中に入って行こうと する必要があるが、正直に言って私は出来る限りspam業者の思考からは 離れていたいのだ。

だがベイズ確率を使った方法の本当の利点は、自分が何を計測しているかが はっきりしていることだ。SpamAssassinのような特徴認識型のフィルタは 各メイルに「spamスコア」を与えようとする。 ベイズ確率を使った方法は、実際の確率を与える。 「スコア」の問題点は、誰もそれが本当は何を意味しているのかわからない点だ。 ユーザには当然わからないし、もっと悪いことに、開発者にもわからない。 例えばメイルに"sex"という語が入っていたとして、それに何ポイント与えるべきだ? 確率ももちろん間違った使われ方をすることはあるが、 少なくともそれが何を意味しているかに関して曖昧さはほとんどなく、 それぞれの証拠を結合する計算法も確立している。 私のメイルアーカイブにおいては、"sex"は、それを含んでいるメイルがspamである 確率が0.97であることを示しているし、"sexy" なら 0.99になる。 そしてベイズの規則を用いれば、他の証拠が無い場合 (普通はそんなことはないが)、 両方の単語を含んでいるメイルがspamである確率は 99.97% であることが確かに言えるわけだ。

確率を計測するために、ベイズ確率を使った方法では spamである証拠とspamでない証拠を両方とも考慮しなければならない。 "unsubscribe" や "opt-in" と言った単語がspamである確率を押し上げるのと 同じくらい、spam中にほとんど現われない、 "though"、"tonight"、"apparently"と言った単語はその確率を押し下げる。 したがって、正当なメイルがたまたま"sex"という語を含んでいたとしても それがspamと認識されることはない。

理想的には、この確率はユーザー毎に計算しておくべきだ。 私は "Lisp" という単語が含まれたメイルをたくさん受け取るが、 (少なくとも現在までは)"Lisp"を含むspamを受け取ったことはない。 こういった単語は、私にメイルを送るための一種のパスワードにもなるわけだ。 私が書いた初期のspamフィルタリングソフトでは、 ユーザーがそういった単語を登録できるようになっていて、 それらの単語を含んでいるメイルはフィルタを通らずに届くようにしていた。 私自身のリストには "Lisp" と私の郵便番号を登録しておき、 オンラインで注文した品物のレシート(それ自体はspamによく似ている) が私の元に届くようにしていた。その時は素晴らしいアイディアだと思っていたのだが。 ベイジアンフィルタは同じことをやってのけ、さらに私自身が気づきもしなかった 多くの他の単語も見つけ出してくれたのだ。

この記事の最初で、我々のフィルタは1000通中spamを通すのは5つ以下で、 しかも誤検出は0だと書いた。これは、私のメイルの集合を用いて私のメイルを 処理した場合の話だ。だがそれは的外れな数字ではない。 そういう使い方こそを私は強く推奨しているんだ:それぞれのユーザーが、 自分が受け取ったspamとspam以外のメイルの集合をもとにしてフィルタリングを行うんだ。 基本的なアイディアは、ユーザメイルに削除ボタンを2種類設けるというものだ。 通常の削除とspamとして削除だ。spamとして削除されたものはspam集合に追加され、 それ以外のメイルは正当な集合に追加される。

最初に初期値となるフィルタを与えておいたとしても、 いずれ各ユーザは自分が受け取ったメイルを元にした単語毎のspam確率のテーブルを 持つことになる。これによって (a)フィルタがよりうまく働くようになり (b)各ユーザが自分がspamと判断する基準を正確に持てるようになり、 (c)何よりも、spam業者にとってフィルタを回避するメイルを作成することをずっと困難にする。 フィルタの判断基準の多くが個人毎のデータベースに依っていたとしたら、 spamを初期フィルタの設定を回避するようにしただけでは、 そのメイルがユーザ毎に学習されたフィルタを通ることを保証できない。

内容を基にしたspamフィルタリングはしばしばホワイトリスト、 つまりフィルタが無条件で回避される差出人のリストと組み合わせて使われる。 そのようなホワイトリストを作成する簡単な方法の一つは、ユーザーが今まで 送ったことのあるメイルアドレスを保存しておくことだ。 もしメイルリーダーが「spamとして削除」ボタンを持っていれば、 さらにユーザーがspamでないごみとして捨てたメイルの差出人アドレスも 使うことができる。

私はホワイトリストの使用も推奨しているが、それはフィルタの性能を良くするため というより、計算負荷を減らすためだ。 以前は、ホワイトリストを使うことでフィルタリングが簡単になると思っていた。 今まで一度もメイルをやりとりしたことのないアドレスからのメイルだけを フィルタにかければ良いし、初めてのメイルのやりとりの内容には 決まりきった点が多々あるからだ。 あなたが既に知っている人は もしかするとセックスに関する話題をメイルしてくるかもしれないが、 初めてあなたにメイルを送ろうという人がセックスについて語ることは あまりありそうにない。しかしこの仮定には問題があった。 人はよく複数のメイルアドレスを持つので、差出人アドレスを初めて見るというだけでは あなたに初めてメイルを送る人かどうかの判断はできないのだ。 古くからの友人が(特に彼がハッカーである場合)突然新しいアドレスからメイルを よこすのは珍しいことではない。したがって知らないアドレスからというだけで spamと誤検出してしまうようなことは是非とも避けたい。

もちろん、ある意味では私のフィルタは自分で一種のホワイトリストを (そしてブラックリストも)実現していると言えるだろう。 ヘッダを含めた全てのメッセージを対象にしているからだ。 私のフィルタは信頼できる差出人のアドレスや、その配送経路さえも「知っている」。 同じく、spamを送るサーバー名、メイラーのバージョン、プロトコルさえも。

_ _ _

もし私が現在のspamフィルタリング率を将来に渡って保持できるとしたなら、 この問題は解決したと言えるだろう。 しかし、現時点でのspamを排除できたというだけではそうは言えない。 spamは進化するからだ。 実際、多くの アンチスパム技術は、より抵抗力の強い虫をつくり出すだけの殺虫剤としてしか 働いてこなかった。

私はベイジアンフィルタについてはずっと大きな希望を持っている。 ベイジアンフィルタはそれ自身がスパムと共に進化するからだ。 例えばspam業者が単純なスパムフィルタを回避するために "cock" のかわりに "c0ck" という語を使い始めたとしたら、 ベイジアンフィルタは自動的にそれに気づくだろう。 実際、"c0ck" は "cock" よりもずっと明確なスパムの証拠であり、 それがどのくらいより明確かということさえもベイジアンフィルタは知っている。

それでも、スパムフィルタリング手法を提案する人は次の質問に 答えられなければならない。もしspam業者があなたのアルゴリズムを正確に 知っていたとして、奴らはどれだけそれをすり抜けられるだろうか。 例えばチェックサムを使ったスパムフィルタが大きな障害になったとすれば、 spam業者はmad-lib[訳註3]を使ってメッセージを生成するようになるだろう。

ベイジアンフィルタを破るには、spam業者はメイルを特殊なものにしたり 怪しい単語を使うのを止めるだけでは不十分だ。 普通のメイルと区別がつかないようにspamを作らなくてはならなくなる。 そして、これは彼らの活動を厳しく制限するだろうと私は思う。 spamのほとんどは物を売り込む文句だから、あなたが通常のメイルとして 物を売り込む文句を常に受け取っているのでいない限り、どうしても 正当なメイルとは異なる特徴を持ってしまう。 更にspam業者達はシステムを変え続けなければならない。 メッセージ本文をいくら工夫しても、ベイジアンフィルタにヘッダを 検出されたらおしまいだ。私はspam業者がどんなシステムを使っているか 十分に知らないので、ヘッダを無難なものに細工するのがどのくらい彼らにとって 難しいかはわからないのだが、おそらくメッセージ本文を無害なものに装うよりも 困難なのではないか。

spam業者達がヘッダの問題を回避できたとすると、おそらく将来のspamは こんな感じになってしまうはずだ:

Hey there. Thought you should check out the following: http://www.27meg.com/foo

売り込み文句が内容を基にしたフィルタリングをすりぬける余地は このくらいしか残されていない。(実際はこれでもフィルタを通り抜けるのは 難しいかもしれない。というのは、他の全ての要素が中立ならばURLのspam確率が 効いて来るはずで、したがってURLも中立であるかのように装わねばならない。)

spam業者も、自分の身元を隠そうともしない、いわゆるオプトインリストを 使っているビジネスから、サーバを乗っ取ってポルノサイトの宣伝を送りつけるのまで、 様々だ。もしフィルタリングが上のようなspamしか通さないようになったとすると、 おそらく「合法な」領域のspam業者はやってゆけなくなるだろう。 彼らは様々な州法によって彼らのメイルが何故スパムではないか、 そしてどうやれば「購読」を停止できるか、等を書き連ねなければならず、 それらの文章は容易に認識できるからだ。

(私は以前はより厳しい法律がspamを減らすだろうと無邪気に信じていた。 今では、厳しい法律ではspam業者が送り出すspamの量は減らせないだろうと 思っている。が、法律のおかげでフィルタは有効に働き、受け取り人が目にする spamの量は確かに減るだろう)。

どんな種類のspam業者であれ、もし我々が彼らの売り文句をこのように制限できる ならば、いずれ彼らはビジネスをやめざるを得ないだろう。 ビジネスという言葉に注目して欲しい。spam業者はビジネスマンなんだ。 彼らがspamを送り出すのは、それが有効だからだ。 spamへの反応は信じられない程少ないが(カタログ送付の反応が 100万通あたり3000通であるのに対し、spamは良くて100万通あたり15通というところ)、 spamを送るコストはほとんどかからない。 受け取り人には、100万人がspamを削除するのに1秒かけたとして 総計5人週ものコストを強いているが、spam業者がそれを払っているわけではない。

それでもspam業者にはいくばくかのコストがかかる[2]。 だから、フィルタリングによって、あるいはフィルタリング回避のために 効果的な売り文句が使えなくなるかして、反応率が低くなれば、 ビジネス的なうまみは減って行くわけだ。

spam業者が売り文句 を使うのは、それが返信率を上げるからだ。 spam業者の思考に入って行くよりもさらに気色悪いかもしれないが、 spamに返信してしまう人間の思考をちょっと覗いてみよう。 おそらくその人物は、信じられない程だまされやすいか、 性的な関心を極端に抑圧しているのであろう。どちらにせよ、 我々が見て嫌悪感を感じたり間抜けにみえたりするspamが、 彼らにとっては興奮するものなのだろう。 そうでなければspam業者がそういう言葉を使うわけがないからだ。 すると、「このリンク先を見てみて」式の文句は、 現在のspamが使っている売り文句ほどには、 spamに返信してしまう人間の心を引っ張りそうにはない。 結果として、売り文句を含めることができなければ、spamはマーケティング方法としては 効率の悪いものとなり、それを使おうとするビジネスも減って行くだろう。

最後にそうなれば、我々の大きな勝利だ。 私は、自分がspamをもう見たくないからspamフィルタを書き始めた。 しかしspamフィルタの技術が十分に進歩すれば、spamの効果は無くなり、 spam業者達もそれを送るのをやめるだろう。

_ _ _

ソフトウェアから法律まで、spamと戦う全てのアプローチのうち、 ベイジアンフィルタリングは最も効果的なものであると私は思っている。 しかし我々が様々な種類の反spam活動をすればするほど、 状況は良くなるだろう。それらはspam業者に制約を課し、 結果としてフィルタリングを容易にするからだ。 そして内容に基づくフィルタリングの中だけでも、 様々な種類のソフトウェアが同時に使われて行くのが好ましい。 フィルタの種類が多ければ多い程、そのどれをも通過するspamを作り出すのは 困難になるからだ。

付録:フィルタリングの例

これはこの記事を書いている最中に私の元に届いたspamの例だ。 このspamの最も特徴的な15単語は次の通りだ。

qvp0045 indira mx-05 intimail $7500 freeyankeedom cdo bluefoxmedia jpg unsecured platinum 3d0 qves 7c5 7c266675

これらの単語はヘッダーからのものとメッセージ本文からのものが混ざっているが、 spamにはよくあることだ。 また、これもspamによくあることだが、上の全ての単語は私のデータベースでは spam確率0.99を与えられている。実はこのメッセージには確率0.99の単語は 15個以上含まれていて、上のものはただ最初の15個だったというだけなのだ。

残念ながらこのメイルはベイズの規則の使用例としてはおもしろいものではない。 確率がうまい具合に散っているものとしては、これも典型的なspamだが こういう例がある。

このspamの特徴的な15単語とそのspam確率は次の通りだ。

madam 0.99 promotion 0.99 republic 0.99 shortest 0.047225013 mandatory 0.047225013 standardization 0.07347802 sorry 0.08221981 supported 0.09019077 people's 0.09019077 enter 0.9075001 quality 0.8921298 organization 0.12454646 investment 0.8568143 very 0.14758544 valuable 0.82347786 今回は良い証拠と悪い証拠が混ざっている。 "madam"や"promotion"が有罪の有力な証拠であるのと同じくらい、 "shortest"といった単語は無罪の有力な証拠だ。 しかしこの場合でもまだ有罪の方が強力である。 これらの数字をベイズの規則で組み合わせれば、結果の確率は0.9027となる。

"Madam"はあきらかに、"Dear Sir or Madam" で始まっている spamから来たものだ。この文句自体はそれほど多く見られるものではないが、 "madam" は私の正当なメイル中には一回も出て来ない。そのためこれだけの 確率となった。

"Republic" が高いスコアを得ているのは、それがしばしばナイジェリア絡みの 詐欺のメイルに現われるからだ。また韓国や南アフリカのものも1〜2通あった。 それだけでこの単語がspamと判定されるのに使われるのは偶然だと思うかもしれない。 だが、spam確率をよく調べてみると、このような偶然は非常に多くあり、 それらが不思議と性能を悪いほうよりは良い方へと押し上げているのだ。 この場合、"Republic" がナイジェリア絡みの詐欺のspamとこのspamとの両方に 現われたのは必ずしも偶然とは言えない。発展途上国を舞台にした怪しいビジネスの 案内はspamの1ジャンルを作っていて、それらの国名には"Republic (共和国)" が明示的に含まれていることが多いからだ (何故なら、実際には共和制ではないからだ[3])。

一方、"enter" は本当のミスだ。 確かにこの単語は購読停止の案内に現われることが多いが、 このメイルの場合は全く罪の無い用法で使われている。 幸いなことに統計的なアプローチは頑健で、 相当多数のミスがあっても結果がおかしくなることはない。

比較のために、フィルタを通り抜けた非常に稀なspamとして これを紹介しておこう。 何故か? このspamはほんとうにたまたま、私の正当なメイルに含まれる単語を 多量に含んでいたのだ。

perl 0.01 python 0.01 tcl 0.01 scripting 0.01 morris 0.01 graham 0.01491078 guarantee 0.9762507 cgi 0.9734398 paul 0.027040077 quite 0.030676773 pop3 0.042199217 various 0.06080265 prices 0.9359873 managed 0.06451222 difficult 0.071706355

ここにも2つばかり、良いニュースはある。まず、このメイルは多分、 プログラミング言語を専門にしており、かつMorrisという友人がいる人で ない限り、フィルタを通ることは無いだろう。平均的なユーザにとっては ここの最初の5単語は中立の語であり、spam確率には貢献しないだろう。

第2に、単語のペアによるフィルタリングを使えば(後述)、 このメイルも捕まえられるかもしれない。 "cost effective"、"setup fee"、"money back" ---いかにもspamの臭いがする。 そして彼らが私に(あるいは私が参加しているネットワークに)spamを送り続けていれば、 "Hostex"という語自体がspam語として認識されるようになるだろう。

最後に、正当なメイルの例を上げておこう。 このメイルの特徴的な15語は次の通りだ。

continuation 0.01 describe 0.01 continuations 0.01 example 0.033600237 programming 0.05214485 i'm 0.055427782 examples 0.07972858 color 0.9189189 localhost 0.09883721 hi 0.116539136 california 0.84421706 same 0.15981844 spot 0.1654587 us-ascii 0.16804294 what 0.19212411

ほとんどの単語は無害なものだ。 二つばかり、臭い単語がある:"color" (spam業者は色付き文字が大好きだ)と "california" (保証書とフォームのメニューによく現われる)だ。 しかしそれらも、明らかに無害の単語である "continuation" や "example" を負かすには至らない。

"describe" がほぼ無害になっているのは興味深い。 私の4000通のspamの中の1通たりとも、この単語を含んではいなかった。 このような驚くデータがたくさんある。 spamテキストを分析していてわかることのひとつは、 spam業者の使う言語がどれだけ狭いかということだ。 だからこそ、個人のメイルに現われる同様に特徴的な単語と組み合わせることにより、 ベイジアンフィルタリングが効果的な方法となり得ているのだ。

付録:他のアイディア

私がまた試していないアイディアのひとつは、個々の単語だけではなく 単語のペア、あるいは3単語の組み合わせでフィルタリングを行うことだ。 そうすればさらに鋭い確率の評価ができるだろう。 例えば、私の現在のデータベースでは、"offers" は0.96の確率が付いている。 単語のペアを使えば、おそらく "special offers" や "valuable offers" は 0.99となり、一方で "approach offers" ("this approach offers" と言った句に 出て来る)はおそらく0.1かそれ以下の確率となるだろう。

まだ私がこれを試していないのは、個々の単語だけで十分に良い結果を得ている からだ。しかしspamの検出がより難しくなってきた時、 フィルタの性能をさらに上げる余地があるということだ。 (ちなみに、単語のペアに基づいたフィルタは、実質的に マルコフ連鎖のテキストジェネレータを逆に走らせているのと同じだ)。

spamの個々の特徴 (例えば受け取り人のアドレスがTo:フィールドに無い)も もちろんspamを認識するのに役立つ。そのような特徴は、 このアルゴリズム中で仮想単語として実装できるだろう。 将来のバージョンでは、最もはなはだしいspamの特徴のいくつかを 組み込んでみるつもりだ。特徴抽出型のspamフィルタは各論では正しい。 それに欠けているのは、得られた証拠を組み合わせるための原理だ。

spamでない特徴を見付けるのは、spamである特徴を見付けるのよりも重要だ。 誤検出は重大であり、特に慎重にならなければならない。 私は将来のバージョンに、誤検出を避けるために特別にデザインした 第2段階のテストを組み込むつもりだ。メイルが閾値以上のspam確率を 持っていても、それが第2段階のフィルタにひっかかったら、 それはspamではないと認識される。

第2段階のフィルタリングにはおそらくベイズ確率は使わないだろう。 多分それはアドホックなだけでなく、推測によるルールにならざるを得ないだろう。 誤検出はパターンを見付けられるようになるほど多くはないからだ。 (いずれにせよ、バックアップシステムには主システムとは異なる技術を 用いておくのは良いことだろう)。

もう一つ私が試したいと思っているのは、 メイルの特定の部分に注目することだ。 例えば、現在のspamのうち95%はあなたに訪れて欲しいURLを載せている (残りの5%は電話番号か、メイルでの返信か、郵送の住所か、 またまれに特定の株を買う、なんてのもある)。 その場合、そのURLを認識できればそのメイルがspamであると決定するのに十分だ。

ドメイン名は、(ドイツ語以外の)メイルの他のテキストと 違った特徴を持っている。いくつかの単語がくっついていることが多いという 特徴だ。一般的に計算するには計算量が多くなってしまうだろうが、 それらを個々の単語に分解してみるのは試してみる価値はあるかもしれない。 フィルタが "xxxporn" という単語を一度も見たことがなかったとすると それに確率0.4をつけてしまうだろうが、 "xxx" と "porn" はそれぞれ (私のデータでは) 0.9899と 0.99の確率を持っており、 その組み合わせ確率は 0.9998だ。

spam業者がメッセージ中に怪しい単語を避けるようになるにつれ、 ドメイン名を分解するのは重要になってゆくと私は思っている。 (IPアドレスのURLは、システム管理者宛のメイルでなければ、 真っ黒だと言えるだろう)。

spam業者が宣伝するURLのリストを協力して作成してゆくのは良い考えかもしれない。 但し、悪意ある登録や不正確な登録を防ぐための、 Raph Levienが研究したような信頼の指標が必要だろう。 だが、もしそういうものが得られれば、フィルタリングソフトウェアの 有効性は一気に高まる。それはまたボイコットをするためにも便利だろう。

怪しいURLを調べるもうひとつの方法は、ユーザーがそのURLを含む メイルを見る前にロボットに覗きに行かせるというものだ。 そしてメイルに適用するのと同じようにサイトのスコアをベイジアンフィルタを 使って計算し、それをメイルのspam確率の計算に含ませることができるだろう。 リディレクトされるURLなどはとても怪しい。

協力してやるプロジェクトとして非常に良いと私が考えるのは、 巨大なspamコーパスを蓄積してゆくことだ。 ベイジアンフィルタがうまく動く鍵は、大きく綺麗なコーパスにある。 そういうコーパスはベイジアンフィルタの入力としても使えるだけでなく、 その他のフィルタにもテスト用として利用できる。

そのようなコーパスを作るにはいくつか技術的な問題がある。 悪意ある登録や不正確な登録を防ぐための信頼の指標はもちろん必要だ。 また、個人情報を消去する方法も要る(ただto:とcc:を消すだけでなく、 例えば登録削除要請のURLの引数にもしばしばto:アドレスが エンコードされて含まれている)。 誰かがこのプロジェクトを始めたら、それは世界にとって良いものとなるだろう。

付録:spamの定義

spamとは何であるかについてだいたいの合意はあると思うが、 明確な定義を与えておくことも役に立つだろう。 集約されたspamのコーパスを作ったり、あるいはspamフィルタのフィルタ率の 意味有る比較をするためには明確な定義が必要になる。

まず、spamとは「頼まないのに送ってくる商用のメイル」ではない、 というところから始めよう。例えば私が古いレイリーの3段変速自転車[訳註4]の 状態のいいやつを欲しがっているのを私の近所の人が耳にはさんで、 手持ちのを売ってもいいよというメイルを送って来たとしたら、 このメイルは商用でありかつ頼んでいないわけだが、それでも私は喜ぶだろう。 spamを定義づけている特徴は、頼んでいないのに送ってくることではなく、 自動的に送ってくることなのだ (そしてそれがspamの存在意義でもある)。

また、spamに商用の内容が多いのも、たまたまそうなだけだと言える。 例えば誰かが何かの政治運動に関するメイルを大量に送り始めたとしたら、 それはポルノサイトの宣伝と同じくらいspamである。

私はspamの定義として、「頼んでいないのに自動的に送ってくるメイル」を 提案する。この定義は、法的にはspamに当たらないメイルも含んでいる。 おそらくロビイストに影響を受けたせいで、法的なspamの定義は 受け取り人と「既に関係がある」会社から送られてくるメイルはspamに含まれないものと することが多い。しかし、例えば何かをその会社から買うだけでは それ以降ずっとメイルを受け取ることを頼んだことにはならない。 もし私がオンラインで何かを注文して、相手の会社がその後継続して spamを送り付けて来たら、それはやっぱりspamなのだ。

spamを送ってくる会社はしばしば「購読停止」を行う方法を提供したり、 spamを止めたければ会社のサイトにいってあなたの「アカウントのオプション」を 変更するように書いてくる。だがこれだけではそのメイルがspamでないと するには足りない。オプトアウトでないということはオプトインであるという ことと同等にはならない。 受け取り人が、メイルを受け取る意志があると明示されたチェックボックス (デフォルトでoffになっている)をクリックしたというのでなければ、 それはspamなのだ。

ビジネスの関係によっては、暗黙のうちに何らかのメイルを送ってくれることを 頼んでいる場合がある。例えばオンラインで注文をすれば、 レシートや発送のお知らせを送ってくることを暗黙のうちに依頼したと 考えて良いだろう。 私は、Verisignが私のドメインネームがもうすぐ期限切れになるというメイルを 送って来たって気にしない (少なくとも彼らが 本当のレジストラならね)。 だがVerisignが「E-コマースウェブサイト構築の無料ガイド」の提供の知らせを メイルしてきたら、それはspamだ。


原註

[1] この記事の例は、(信じてくれないかもしれないが)より多くの人に わかりやすいようにCommonLispに書き直したものだ。 ここで述べたアプリケーションは新しいLisp方言 Arcをテストするために 書いたものだが、Arc自体はまだリリースされていない。

[2] 現在のところ、最も安いところで100万通あたり$200というのが 相場のようだ。これは大変に安い。spam一通あたり50分の1セントだ。 だが、95%のspamがフィルタされたとすると、ターゲットへとメイルを 届かせるためのspam業者のコストは20倍にはねあがることになる。 それだけ大きなマージンを確保しているspam業者はあまりいないだろう。

[3] おおざっぱな指針として、国の名前に付く修飾語が多ければ多い程、 その統治者は腐っていると言えるだろう。 ナントカ社会主義人民民主共和国というのは多分一番住みたくない国だ。

謝辞

Sarah Harlinはこの記事の草稿を 読んでくれました。Daniel Giffin (Arcのプロダクション用インタプリタを書いてくれて います)は我々のメイルシステムを作るに当たっていくつかの良いアイディアを出して くれました。Robert Morris、Trevor Blackwell、そしてErann Gatは spamに関して多くの議論をしてくれました。 Raph Levienは信頼の指標に関するアドバイスを寄せてくれました。 Chip ColdwellとSam Steingoldは統計に関するアドバイスを寄せてくれました。

更なる情報


訳註

訳註1

日本語の場合、トークンへの分解は英語のように単純ではない。 エンコーディングを正規化した上で、何らかの解析をする必要がある。

単純な辞書検索を使う、形態素解析をする、等のいろいろな方法が考えられるが、 日本語の多くの特徴的な単語が漢字2〜3文字であること、 不完全な区切りによるランダムな語句はコーパスが大きくなれば 中立の確率に近付くことが期待されること、等を考えると、 単純に文字のペアやtripletだけを取って統計的に処理しても何か意味ある 結果がでるかもしれない。ということで やってみた

日本語メイルと英語メイルの比率がspamとnospamのコーパスで大幅に違うため、 上記のような統計的な中立化を期待するなら言語毎に分けてテーブルを作らなければ ならなさそうだ。また、KakasiやChaSen、MeCabのようなまっとうなトーカナイザを 使って比較してみるのも面白い。

もしこの点に関する情報がありましたら訳者までお知らせ下さい。 こちらからリンクさせて頂きます。

訳註2

ここで定数で数値を切るのはPaul Grahamも暗に認めているようにkludgeである (続報では彼はこの数値をコーパスのサイズに よって調整していることを述べている)。 この点を以ってPaul Graham方式はベイズ統計から逸脱しているとの批判もある。

実際には、エビデンスの無い時点でのバックグラウンドの事前確率 (任意の 単語がスパムあるは非スパムに現れると考えられる信念の度合い) を設定する ことで、一方にしか表れない単語もベイズ統計で扱うことができる。 この点についてはGary Robinsonが次の記事で検討している: A Statistical Approach to the Spam Problem。 Gary Robinson方式はこれ以外にも特徴的な単語の選択方法など いくつかの点でPaul Graham方式を改良しており、 既存のベイジアンスパムフィルタに広く採り入れられている。

事前確率をどう設定すれば良いかについては、Greg Louisが複数のデータセットを 使って詳細な検討を行っている: Bogofilter Parameters: Effect of varying s and mindev, continued: Comparison of results from different email sources

訳者の経験では、Paul Graham方式で97〜98%の精度は比較的容易に達成されるが、 そこからさらに上にゆくのに事前確率の考慮は効いて来るだろう。 但し、総合的な成績はトーカナイゼーションの方法や、 メールメッセージの取扱い (multipartでbinaryが送られてきた場合や、 メッセージ本文の文字エンコーディングとヘッダのcharset指定が一致していない 場合の扱い) 等、ベイズ統計の本質とは異なる部分にも大きく影響されることに 注意しておく必要がある。

訳註3

Mad lib: テンプレート(通常は物語)に単語(「動詞」や「名詞」等の指定がある)を 与えて文章を作るシステム。 いわゆる吉野屋テンプレートみたいなものか、と思ったが、 mad libの方は最初に物語を知らせないでおいて、 適当に入れた単語でどんな物語が出て来るかを楽しむ趣向のものが多いようだ。

訳註4

Raleigh three-speed: 英国製のビンテージの自転車。 こんなの


[Practical Scheme]