gmail： 「スパム戦争： 前線からの報告」
googleウェブ検索の劣化に関する記事が多くの方から関心を頂いているなか、タイムリーにスパム駆逐戦略をまとめる簡単なレポートがgmailチームから公開された。
たった3ページの簡潔なまとめでアルゴリズムなどの詳細はない。でも面白い事実が垣間見れる。
「スパム対策はリアルワールドにおける機械学習の成功ストーリー」
gmailだと確かに殆どスパムがこない。また、まともなメールが誤認識されてスパムフォルダに入ることも稀だ。これはgmailのスパム認識の精度の高さを物語っていると自負している。
anti-abuseシステムの構成
- 伝統的なhard-wired(プログラマが書いた)なルール
- 学習機能によって割り出されたルール (ルールの自動発見をするのか!)
- クラスタリング (どんなソフト使っているのか知りたい…)
- 革新的な評判システム
あとプロトコルレベルでも工夫がなされている。グーグルはSPFやDKIMなどの送信者認証システムを一早く導入した。(確かにアプリケーションから自動的にメールを出してgmailに弾かれないためには上記の面倒な設定をしなくてはいけない)
- decision trees, parallel logistic regression, efficient optimisation methodsを融合させたアルゴリズム
- 巨大なフィーチャーセットと巨大なトレーニングセットを処理する能力。多数のプロセッサで動く分散機能
「Feature engineering」(エンジニアによるフィーチャーの発見、開発)は重要だが、フィーチャーの選択、組み合わせ、ウエイトの配分などの義務から機械学習がエンジニアを開放してくれる。学習により、スパムの確率が推測され、チューニングに役立つ。
abuseの種類: 広告だけじゃない
大量広告のいわゆる迷惑メール以外にもabuseはある。phishingに引っ掛かると迷惑ではすまない。なので、ユーザに与えるダメージが大きいphishingの方をより厳しく追求する。
一方で迷惑メールにも独特の難しさがある。これを受けたいユーザも存在するからだ。そこでユーザ毎にカスタマイズした処理が要される。
スパム発信対策
評判のよいメールサービスはSPF/DKIMなどに対応しているので、発信点としてスパマに魅力のあるターゲットになる。しかし、スパム発信を阻止するのは入ってくるものを弾くのより難しい。 … スパムを受けたユーザとそのメール管理者からの協力があれば対策は打てる。
驚くことにCAPTCHAがあるにもかかわらず、スパマは無料アカウントをロボットで制作してくる。スパマは人間に支払いをするか騙してCAPTCHAを破る方法を編み出した。(どうやらアダルトコンテンツでスケベ男を誘導してキャプチャを解かしているようだ。関心してしまう)
刻一刻と進化するゲーム
スパマは送信者認証システムを迂回するために、「評判の良い」メールサービス(つまりgmailなど)を発信地としてターゲットしはじめた。これはスパムの低速な進化だ。
しかし、あるスパム戦略が開始されると --例えばある銀行の客を狙ったphishing攻撃-- スパムの発信地とその内容は一時間単位で進化していく。スパマとメールサービスプロバイダとの攻防戦のになる。学習機能は比較的少数のサンプルからリアルタイムに対応しなくてはならない。
スケール
「ID3 for decision trees」のような機械学習アルゴリズムは比較的速い。(O(n*f^2) n=サンプルデータ数、f=フィーチャー数) しかし、中堅メールサービスでも一日数百万のサンプル(メール)とそれと同じぐらい(!)のフィーチャーを処理しなければならない。当然トレーニングメッセージは一つのマシンのメモリには収まらない。しかし大スケールになると、フィーチャーすら一つのマシンに入らなくなる。… これに対応するには分散モデル、分散データ、非同期フィーチャー進化が必要になる。(一般的に機械学習は全フィーチャを一つのプロセスが扱うが、これを分散化しなくてはいけないってことだろう。大変そう。非同期フィーチャー進化(asynchronous feature evaluation)は意味不明。もっと説明しろよ)
入手困難なトレーニングデータ
多くのユーザはスパム通告ボタンを押さない。これは新しい攻撃が始まった際に問題になる。(逆に言うと、ユーザがいつもマメにスパムボタンを押す習慣があるなら新攻撃にも対応することも可能だと惜しんでいるわけ) 「押し漏らし」とネガティブのを識別する対策が必要になる。…
機械学習の結果の理解
結果を信頼しデバッグするには機械学習の結果を解釈しなければならない。「何故」これがスパムなのかを説明できなければならない。「multi-layer perceptron」(neural netか？)は(結果は出るが)解釈が困難な手法だ。(解釈が困難というのはML実践者からよく聞く問題だ。グーグルも同じなんだな)
国際化
どの言語でも、またどんな言語のコンビネーションでもスパム対策をしたい。日本語でも英語でも同じように機能してほしい。しかしこれは驚くほど難しい。たとえばある言語では単語の境界を認識することすら困難なのだ。(西洋人エンジニアの素直な驚き)
リバースエンジニアリングを困難にする工夫
スパム度によってメールをソートして出すUIなどあったらユーザにはいいが、そうするとスパマにテストシステムを与えることなってしまう。
結論
グーグルは機械学習により殆どのスパムを排除するのに成功している…
"To conclude, Google does successfully use machine learning technology to filter out the vast majority of spam and other abuse."
元レポートのPDFではこの"does"が強調されている。「グーグルのアルゴリズムはスパマにやられた」との世論に意義を申し立てんばかりに。 一つ前のポストでも書いたようにこの見方は正しい。確かにグーグルのアルゴリズムによるスパム駆逐は凄い精度だ。これはgmailを使っていると歴然とする。 自分でメールサーバを運営しspamassasinなどで苦労した経験のある者は特にそう思うだろう。
gmailでこれだけの精度でスパム制御できるグーグルが何故ウェブ検索ではこんなにスパムされているのか？という疑問が避けられない。スパムメールをユーザに見せても一文にもならないというところにその違いがあるのだろうか。
