より良いベイズ式フィルタリング
Original2003年1月
(この記事は2003年のスパムカンファレンスで講演されたものです。 A Plan for Spamで説明されているアルゴリズムのパフォーマンスを改善するための取り組みと、 今後の計画について述べています。)
ここで紹介したい最初の発見は、研究論文の遅延評価のためのアルゴリズムです。 好きなことを書いて、以前の研究を引用しなければ、 憤慨した読者があなたが引用すべきだった論文の参考文献を送ってくれます。 私はこのアルゴリズムを「A Plan for Spam」[1]がSlashdotに掲載された後に発見しました。
スパムフィルタリングはテキスト分類の一部門ですが、 ベイズ式スパムフィルタリングに関する最初の論文は1998年の同じカンファレンスで発表されたものと思われます。 一つはPantelとLinによるもの[2]、 もう一つはMicrosoft Researchのグループによるものです[3]。
この研究について聞いたときは少し驚きました。 4年前からベイズ式フィルタリングが使われていたのに、 なぜみんなが使っていないのだろうと。 論文を読んでわかったのは、PantelとLinのフィルタが2つの中で より効果的でしたが、スパムの92%しか検知できず、 1.16%の誤検知率でした。
私が書いたベイズ式スパムフィルタは、 スパムの99.5%を検知し、0.03%未満の誤検知率でした[4]。 同じ実験を2人が行って大きく異なる結果が出るのは 常に警戒すべきことです。 特にここでは、その2つの数値が正反対の結論を導きかねません。 ユーザーによって要求は異なりますが、 多くの人にとって、92%の検知率と1.16%の誤検知率では フィルタリングは受け入れられない解決策だと思いますが、 99.5%の検知率と0.03%未満の誤検知率なら 受け入れられる解決策だと思います。
では、なぜこれほど違う結果が出たのでしょうか。 PantelとLinの結果を再現していないので断言はできませんが、 論文を読んで5つの要因が違いの原因だと考えられます。
1つ目は、彼らのフィルタの学習に使ったデータが非常に少ないことです。 スパムメールが160通、非スパムメールが466通しかありません。 このデータ量では、フィルタのパフォーマンスはまだ向上し続けるはずです。 つまり、彼らの数値は、アルゴリズム自体の性能を正確に反映していないかもしれません。
おそらく最も重要な違いは、彼らがメッセージヘッダを無視したことです。 スパムフィルタを作ったことのある人なら、 これは奇妙な決断だと感じるでしょう。 しかし、私が最初に書いたフィルタでも、 ヘッダを無視していました。なぜでしょうか。 きれいな問題設定にしたかったからです。 メールヘッダについてはよく知らなかったし、 無秩序なものだと思えたからです。 ここには、フィルタ作成者への教訓があります。 データを無視してはいけません。 これは当たり前のようですが、私も何度も学ばされました。
3つ目は、Pantelとリンがトークンをステミングしたことです。 例えば「mailing」と「mailed」を「mail」のルート形に 統一しています。データ量が少ないため、 やむを得ない選択だったのかもしれませんが、 これは早期最適化の一種と言えます。
4つ目は、確率の計算方法が違うことです。 彼らはすべてのトークンを使用しましたが、 私は最も重要な15個のトークンしか使いません。 すべてのトークンを使うと、長いスパムを見逃しがちです。 そういったスパムでは、マルチレベルマーケティングで 金持ちになった経緯を長々と書いているからです。 このようなアルゴリズムは、スパマーにとって 簡単にだまされるでしょう。スパムのキーワードに ランダムなテキストを大量に追加すれば、 それを相殺できるからです。
最後に、彼らは誤検知率を抑えるバイアスをかけていませんでした。 スパムフィルタリングのアルゴリズムには、 誤検知率を下げる代わりに検知率を下げられる 調整ノブがあるべきだと思います。 私は、非スパムコーパスのトークン出現数を 2倍カウントすることでこれを実現しています。
メールスパムフィルタリングは、単純なテキスト分類問題として 扱うべきではありません。テキスト分類の手法は使えますが、 メールというデータ構造の特性や、 誤検知がはるかに深刻な誤りであるという スパムフィルタリング固有の性質を反映した ソリューションを考える必要があります。 そして、エラーの原因は単なるランダムな変動ではなく、 フィルタを打ち負かそうと積極的に働きかける 生身のスパマーなのです。
トークン
Slashdotの記事の後に知ったもう1つのプロジェクトが、 Bill YerazunisのCRM114[5]です。 これは、私が述べた設計原則の逆例と言えるでしょう。 単純なテキスト分類器ですが、スパムフィルタリングをしているとは 知らずに、ほぼ完璧にスパムをフィルタリングできるのです。
CRM114の仕組みを理解すると、 単語ベースのフィルタリングから、 このようなアプローチに移行せざるを得なくなるのは 必然的だと感じました。 しかし、まずは単語ベースでどこまでいけるか試してみようと思いました。 そして、驚くべきことに、かなり高い性能が出せることがわかりました。
主に、私はよりスマートなトークン化に取り組んできました。 現在のスパムに対しては、CRM114に迫る フィルタリング率を達成できるようになりました。 これらの手法はBillのアプローチとおおむね直交しているので、 最適なソリューションには両方を組み合わせることが できるかもしれません。
「A Plan for Spam」では、トークンの定義がとてもシンプルでした。 文字、数字、ハイフン、アポストロフィ、ドル記号が構成文字で、 それ以外はすべてトークン区切りでした。 また、大文字小文字は区別しませんでした。
現在は、トークンの定義をより複雑にしています。
大文字小文字を保持する。
感嘆符も構成文字とする。
ピリオドとカンマは、数字の間にある場合に構成文字とする。 これにより、IPアドレスや価格を完全に取得できる。
$20-25のような価格範囲は、$20と$25の2つのトークンとする。
To、From、Subject、Return-Pathの各行内、 またはURLの中にあるトークンには、 それを示すマークをつける。 例えば、Subjectの「foo」は「Subject*foo」となる。 (アスタリスクは、構成文字として使えない任意の文字)
このような措置により、フィルタの語彙が増え、 より識別力が高くなります。 現在のフィルタでは、Subjectの「free」は スパム確率98%なのに対し、本文の同じトークンは 65%しかありません。
現在の主な確率は以下の通りです[6]:
件名FREE 0.9999 free!! 0.9999 Tofree 0.9998 件名free 0.9782 free! 0.9199 Free 0.9198 Urlfree 0.9091 FREE 0.8747 From*free 0.7636 free 0.6546
スパムフィルターの計画では、これらすべてのトークンが同じ確率、.7602を持っていました。そのフィルターは約23,000のトークンを認識していました。現在のものは約187,000を認識しています。
トークンの宇宙が大きくなる欠点は、見落としが増える可能性があることです。 コーパスを多くのトークンに広げるのは、それを小さくするのと同じ効果があります。 感嘆符を構成要素と見なす場合、たとえば、2つの感嘆符しかない「free」の99.99%の確率を持っているにもかかわらず、7つの感嘆符を持つ「free」の確率を持っていないことになる可能性があります。
これに対する1つの解決策は、私が退化と呼ぶものです。正確な一致が見つからない場合は、より一般的なバージョンとして扱います。 私は、末尾の感嘆符、大文字、5つのマーク付きのコンテキストのいずれかで発生することをトークンをより具体的なものと見なします。 たとえば、「Subjectfree!」の確率が見つからない場合は、「Subjectfree」、「free!」、「free」の確率を探し、.5から最も遠いものを使います。
フィルターが「Subject」行に「FREE!!!」を見つけ、それに対する確率がない場合に検討される代替案は以下のとおりです。
SubjectFree!!! Subjectfree!!! SubjectFREE! SubjectFree! Subjectfree! SubjectFREE SubjectFree Subjectfree FREE!!! Free!!! free!!! FREE! Free! free! FREE Free free
これを行う場合は、大文字と小文字の両方のバージョンを考慮してください。スパムには命令形の文が多く、その場合、最初の単語は動詞になります。したがって、すべて小文字の場合よりも、頭文字が大文字の動詞の方がスパムの確率が高くなります。私のフィルターでは、「Act」のスパムの確率は98%で、「act」は62%です。
フィルターの語彙を増やすと、古い「同じ」の定義に従って同じ単語が複数回カウントされる可能性があります。論理的には、もはや同じトークンではありません。しかし、これでまだ気になる場合は、私の経験から、重複してカウントされているように見えるのは、まさに重要なものだと付け加えましょう。
語彙が大きくなる別の影響は、受信メールを見ると、.5から大きく離れた確率を持つ、より多くの興味深いトークンが見つかることです。私は、スパムを判断するのに最も興味深い15個のトークンを使います。 しかし、固定数を使うと問題が生じる可能性があります。多くの最大限の興味深いトークンが見つかった場合、等しく興味深いトークンの順序を決める要因次第で結果が決まってしまうのです。 これに対処する1つの方法は、一部のトークンをより興味深いと扱うことです。
例えば、「dalco」というトークンはスパムコーパスに3回出現し、正規のコーパスには一度も出現しません。一方、「Url*optmails」(URLの中の「optmails」)というトークンは1223回出現します。 しかし、私がトークンの確率を計算していた方法では、両方とも.99というスパムの確率しか持っていませんでした。
これは適切ではありません。トークンに大幅に異なる確率を与えるための理論的な議論はありますが(PantelとLinがそうしています)、私はまだ試していません。 少なくとも、1つのコーパスにしか出現しないトークンが15個以上見つかった場合は、頻度の高いものに優先順位を与えるべきだと思います。 そこで、2つのしきい値を設けました。スパムコーパスにしか出現しないトークンは、10回以上出現する場合は確率.9999、それ以外は.9998とします。正規のコーパスにしか出現しないトークンについても同様です。
後で、トークンの確率をかなり調整する可能性がありますが、この小さな調整により、少なくともトークンが正しい順序で並びます。
別の可能性は、興味深さのしきい値を超えるすべてのトークンを考慮することです。Steven Hauserはこれを自身の統計的スパムフィルターで行っています。 しきい値を使う場合は、非常に高くする必要があります。そうしないと、スパマーがより無害な単語で大量のメッセージを詰め込んで欺くことができます。
最後に、HTMLをどのように扱うべきでしょうか。無視するから完全に解析するまで、さまざまなオプションを試してきました。HTMLを無視するのは悪い考えです。有用なスパムの兆候がたくさんあるからです。しかし、すべてを解析すると、フィルターがHTMLの認識器に退化してしまう可能性があります。最も効果的なアプローチは中道で、一部のトークンを認識し、他は無視することです。私はa、img、fontタグを見ていますが、それ以外は無視しています。 リンクと画像は確実に見る必要があります。URLが含まれているからです。
HTMLの扱いについてもっと賢明になれるかもしれませんが、これに多くの時間を費やす価値はないと思います。HTMLが多いスパムはフィルタリングが簡単です。賢いスパマーはすでにそれを避けています。したがって、将来のパフォーマンスはHTMLの扱い方にはあまり依存しないはずです。
パフォーマンス
2002年12月10日から2003年1月10日の間に、約1750件のスパムを受け取りました。 そのうち4件が通過しました。これは99.75%のフィルタリング率です。
見逃した4件のスパムのうち2件は、私の正規のメールで頻繁に使われる単語を使っていたため通過しました。
3件目は、第三者にメールを送信するために不安全なCGIスクリプトを悪用するものでした。 ヘッダーが無害で、使う単語に気をつけているため、コンテンツだけでフィルタリングするのは難しいです。 しかし、通常はキャッチできます。この件は.88の確率で通過したのは、.9のしきい値をわずかに下回っただけでした。
もちろん、複数のトークンシーケンスを見れば簡単に検出できます。「以下はフィードバックフォームの結果です」は即座にバレます。
私が「未来のスパム」と呼ぶ第4のスパムは、中立的なテキストに続いてURLが付いているというものでした。この場合、誰かがついにホームページを完成させたと言って、それを見てほしいと言っていました。(もちろんそのページはポルノサイトの広告でした。)
スパマーが慎重にヘッダーを扱い、新しいURLを使えば、フィルターが気づくようなものは何もありません。もちろん、クローラーを送って見てもらうこともできます。でも、それは必要ないかもしれません。「未来のスパム」の反応率は低いはずです。そうでなければ、誰もがそれをやっているはずです。反応率が十分に低ければ、スパマーにとって採算が取れなくなり、フィルタリングに苦労する必要もなくなるでしょう。
今回の本当に驚くべき知らせは、その1か月の間に3つの誤検知があったということです。
ある意味では、誤検知があるのは安心できます。「スパム対策計画」を書いた時は、まだ誤検知がなく、それがどのようなものかわかりませんでした。今では数件経験したので、恐れていたほど悪くないことがわかりました。 統計的フィルターによる誤検知は、スパムに似たメールが引っかかるのですが、それらは見逃しても問題ないようなものが多いようです。
2つの誤検知は、私が以前から購入しているcompanies からのニュースレターでした。それらは私が購読を申し込んでいないものですが、以前はスパムとして削除していなかったので、誤検知と見なしています。フィルターがそれらを引っかけたのは、1月にそれらの企業がコマーシャルのメールサービスに切り替えたため、ヘッダーとボディがよりスパム臭くなったからです。
3つ目の誤検知は深刻なものでした。エジプトの人から送られてきた、すべて大文字のメールです。これは、トークンの大文字小文字を区別したことによる直接の結果です。「スパム対策計画」のフィルターではこれを引っかけなかったでしょう。
全体の誤検知率を正確に言うのは難しいです。統計的にはノイズの中にいるからです。 効果的なフィルターを作ったことのある人なら、この問題を知っているはずです。 ある程度のメールでは、スパムかどうかの判断が難しく、フィルターを厳しくすればするほど、これらのメールを見なければならなくなります。例えば、これまでフィルターが引っかけたメールの中には、タイプミスで私のアドレスに送られてきたものや、私が別の人だと思われて送られてきたものがあります。これらは私のスパムでも非スパムでもありません。
別の誤検知は、Virtumundoの副社長からのものでした。私がお客様になりすまして彼らに書いたところ、Virtumundoのメールサーバーを経由して返信が来たので、最も不審なヘッダーがついていました。これも本当の誤検知ではなく、ある種の「ハイゼンベルクの不確定性」のようなものかもしれません。スパムフィルタリングについて書いていたからこそ、このメールを受け取ったのです。
これらを除いて、これまでに合計5件の誤検知がありました。約7,740通の正常なメールの中での誤検知率は0.06%です。残りの2件は、注文した商品の入荷遅延の通知と、Eviteからのパーティー招待でした。
この数字は信頼できないと思います。サンプルが小さいことと、いくつかのケースについてはフィルターを改善できると思うからです。
誤検知は、偽陰性とは性質が違うと考えています。フィルタリング率は性能の指標ですが、誤検知はバグのようなものです。フィルタリング率の向上は最適化の問題として、誤検知の減少はデバッグの問題として取り組んでいます。
つまり、この5件の誤検知がバグリストなのです。例えば、エジプトからのメールが引っかかったのは、すべて大文字だったためにナイジェリアのスパムのように見えたからです。これは本当にバグのようなものです。HTMLの場合と同様に、メールがすべて大文字なのは、単語ごとの特徴ではなく、1つの特徴として扱うべきです。大文字小文字の扱いをもっと洗練させる必要があります。
では、この0.06%をどう捉えればよいでしょうか。上限と見なすことはできますが、サンプルが小さいことを考慮する必要があります。現時点では、ベイズ filtering の本質的な誤検知率ではなく、実装上のバグの問題だと考えています。
今後の展望
次は何をするべきでしょうか。フィルタリングは最適化の問題であり、最適化のカギはプロファイリングです。コードのどこが遅いかを推測するのではなく、実際に見てそこを直すべきです。フィルタリングでは、見逃したスパムを見て、それをどうやって捕まえられるかを考えることが重要です。
例えば、スパマーたちは今、フィルターを回避するために積極的に取り組んでおり、単語を分断したり間違って綴ったりしてフィルターが認識できないようにしています。しかし、これに取り組むのは私の最優先事項ではありません。なぜなら、私はまだこれらのスパムを簡単に捕まえられるからです。
現在、私が苦労しているスパムには2種類あります。 1つは、女性からの招待状を装ったものです。セールストークを使わずに、デートサイトのプロフィールを見るよう誘うものです。これらは、一般的なメールと同じ語彙を使うため、引っかからないのです。
もう1つは、ブルガリアの企業から送られてくる、プログラミングサービスの勧誘メールです。これらは、私も programmer なので、本物のメールと同じ単語が使われているため、引っかからないのです。
まずは、個人広告型のスパムに取り組むことにします。もっと詳しく見れば、これらと本物のメールの統計的な違いが見つかるはずです。文体の違いは明らかですが、それを捉えるには複数の単語を組み合わせたフィルタリングが必要かもしれません。また、これらのスパムはURLを繰り返し記載する傾向がありますが、本物のメールではそうではありません。
アウトソーシング型のスパムは捕まえるのが難しいでしょう。クローラーを送ってサイトを見ても、決定的な証拠は見つからないかもしれません。唯一の解決策は、スパムに含まれるドメインのリストを作ることかもしれません。しかし、この種のメールはそれほど多くないはずです。最後に残るのが、ブルガリアからの unsolicited プログラミングサービス の申し出だけだとしたら、私たちは別の問題に取り組むことができるでしょう。
統計的フィルタリングが本当にその点まで私たちを導いてくれるのでしょうか? 私にはわかりません。現時点では、私個人としては、スパムは問題ではありません。しかし、スパム送信者たちは統計的フィルタを欺くための本格的な取り組みをまだしていません。彼らがそうした時にどうなるでしょうか?
ネットワークレベルのフィルタ[13]については、私は楽観的ではありません。 静的な障壁を乗り越える価値があれば、スパム送信者たちはそれを効率的に突破します。すでに「Assurance Systems」という会社があり、メールをSpamAssassinに通して、フィルタリングされるかどうかを教えてくれます。
ネットワークレベルのフィルタが全く役立たずというわけではありません。「オプトイン」スパム、つまり、VirtumundoやEqualmailのようなオプトインリストを運営していると主張する企業からのスパムを排除するのに十分かもしれません。ヘッダーだけで判断できるからです。しかし、ヘッダーを偽造したり、オープンリレーを使う者、おそらくほとんどのポルノスパマーたちは、ネットワークレベルのフィルタを何とか突破できるはずです。(ただし、彼らが送りたいメッセージを送れるわけではありません)
私が期待しているのは、各ユーザーの受信メールに基づいて確率を計算するフィルタです。これらのフィルタは、偽陽性を避けるだけでなく、フィルタリングの効果も高くなります。例えば、メッセージ内にベースー64でエンコードされた受信者のメールアドレスが見つかるのは、スパムの非常に良い指標です。
個別のフィルタの真の利点は、それぞれが異なることです。ユーザーそれぞれのフィルタが異なる確率を持っていれば、スパム送信者の最適化ループ、つまりプログラマーが言う「編集-コンパイル-テスト」サイクルが非常に遅くなります。デスクトップ上のフィルタのコピーを使ってスパムを少し調整するだけでは済まず、各調整ごとにテストメールを送らなければならなくなります。対話型のトップレベルがない言語でプログラミングするようなものですから、誰もそれを望まないでしょう。
注記
[1] Paul Graham. ``A Plan for Spam.'' 2002年8月. http://paulgraham.com/spam.html.
このアルゴリズムの確率は、ベイズの定理の退化した場合で計算されています。2つの単純化された仮定があります。特徴(つまり単語)の確率は独立しているという仮定と、メールがスパムである事前確率を知らないという仮定です。
最初の仮定は、テキスト分類では広く使われています。この手法は「ナイーブベイズ」と呼ばれます。
2つ目の仮定は、受信メールに占めるスパムの割合が日によって(時間によっても)大きく変動するため、全体としての事前確率は予測に役立たないと判断したからです。スパムとスパムでない両方の事前確率を0.5と仮定すれば、それらが相殺されて公式から取り除くことができます。
スパムとスパムでない比率が非常に高い、あるいは(特に)非常に低い状況でベイズフィルタリングを行う場合は、事前確率を組み込むことで、フィルタの性能を改善できるかもしれません。これを適切に行うには、スパムと正常なメールの量がともに一日の中で特定のパターンを持つため、時間帯ごとの比率を追跡する必要があります。
[2] Patrick Pantel and Dekang Lin. ``SpamCop-- A Spam Classification & Organization Program.'' 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.'' AAAI-98 Workshop on Learning for Text Categorization.
[4] 当時、約4,000通の正常なメールの中で、偽陽性は0件でした。次の正常なメールが偽陽性だった場合、これは0.03%になります。これらの偽陽性率は信頼できるものではありません。後述するように説明します。ここでは1.16%未満であることを強調するために数値を引用しています。
[5] Bill Yerazunis. ``Sparse Binary Polynomial Hash Message Filtering and The CRM114 Discriminator.'' 2003年 Spam Conference.
[6] 「A Plan for Spam」では、しきい値を0.99と0.01に設定しました。コーパスのサイズに比例したしきい値を使うのが適切だと思われます。現在約10,000通ずつのメールを持っているので、0.9999と0.0001を使っています。
[7] ここに修正すべき欠陥があります。現在、「Subjectfoo」が単に「foo」に縮退した場合、それは本文やヘッダー行以外の「foo」の出現統計を意味しています。 私が行うべきなのは、「foo」全体の統計と特定のバージョンの統計を別々に保持し、「Subjectfoo」を「foo」ではなく「Anywhere*foo」に縮退させることです。大文字小文字についても同様で、大文字から小文字ではなく、任意の大文字小文字に縮退させるべきです。
価格についても同様のことができるでしょう。例えば、「$129.99」を「$--9.99」、「$--.99」、「$--」に縮退させるなどです。
単語をステムに縮退させることもできますが、これは初期の小さなコーパスの段階でしか性能向上にはつながらないかもしれません。
[8] Steven Hauser. ``Statistical Spam Filter Works for Me.'' http://www.sofbot.com.
[9] 偽陽性は全て同じではありません。スパム対策の手法を比較する際にはこれを覚えておく必要があります。 フィルタによる偽陽性の多くは、見逃しても問題ない微妙なスパムですが、ブラックリストによる偽陽性は、単に間違ったISPを選んだ人からのメールです。両者ともスパムに近いメールをキャッチしますが、ブラックリストの場合は物理的な近さ、フィルタの場合はテキスト的な近さです。
[10] トークンを隠蔽するのが上手になれば問題になるかもしれませんが、スペース、ピリオド、コンマなどを取り除いて辞書を使ってワードを抽出するようにすれば対応できます。 元のテキストに見えなかったワードを見つけるのは、ワード境界の再構築以上のことが必要です。スパム送信者は文字を追加(「xHot nPorn cSite」)したり省略(「P#rn」)したりします。 ここでは視覚研究が役立つかもしれません。人間の視覚が、そのような手口に近づく限界を示しているからです。
[11] 一般的に、スパムは定期的なメールよりも反復的です。 彼らはそのメッセージを押し付けようとしています。 現在、上位15トークンの重複を許可していませんが、送信者が悪い単語を複数回使用する場合、偽陽性が発生する可能性があります。 (現在のフィルターでは、「dick」はスパム確率が0.9999ですが、名前でもあります。) 重複を少なくとも認識すべきだと思われるので、Brian BurtonがSpamProbeで行っているように、最大2つまでのトークンを許可するかもしれません。
[12] これは、スパマーがメッセージの他の部分を生成するためにマッドリブ技術を使うように押し込まれると、Brightmailのようなアプローチが退化していくことになります。
[13] ネットワークレベルでのフィルタリングに取り組むべきだと主張されることがあります。 より効率的だからです。 人々が通常この言葉を使うときの意味は、現在ネットワークレベルでフィルタリングしており、最初から始め直したくないということです。 しかし、問題を解決策に合わせて決めることはできません。
歴史的に、希少リソースの議論は、ソフトウェア設計に関する議論の中で敗北側でした。 人々はそれを、他の理由で行った選択(特に不作為)を正当化するためにのみ使うようです。
このペーパーの草稿を読んでくれたSarah Harlin、Trevor Blackwell、Dan Giffinに感謝します。そして、このフィルターの大部分のインフラを提供してくれたDanにも感謝します。
関連:
SubjectFREE 0.9999 free!! 0.9999 Tofree 0.9998 Subjectfree 0.9782 free! 0.9199 Free 0.9198 Urlfree 0.9091 FREE 0.8747 From*free 0.7636 free 0.6546
SubjectFree!!! Subjectfree!!! SubjectFREE! SubjectFree! Subjectfree! SubjectFREE SubjectFree Subjectfree FREE!!! Free!!! free!!! FREE! Free! free! FREE Free free