SPAM Filterling Using Statistical DATA Compression Models

参照

Bratko,A., Cormack, G.< Filipic, B., Lynam, T., and Zupan, B.
Spam filtering Using statistical data compression models.
Jounal of Machine Learning Research 7(Dec. 2006)
http://jmlr.csail.mit.edu/papers/topic/ml_sec.html

概要

適応型統計データ圧縮モデルの紹介

  • 文字列分類器の確率を用いる
  • characterやバイナリ列を用いる
  • 前処理を行わない

この例として次の２つを実験

効果の高さ、ノイズに対する強さが証明された。

関連研究

  • IBM's Chung Kwei
    • パターンの発生回数をもとに判断
  • Pampa pathi
    • 作成したsuffix treeデータ構造から外れた回数をもとに判断

エンコードの方法

  • Two part
    • 情報源の確率モデルを記述する
    • 記述されたモデルをもとにデータを記述
  • Adapting Coding
    • 空のモデルから始めて、１つ前のモデル、k個分のデータを用いて計算

アルゴリズム

現在の情報を更に豊かにする。
→現在の状態へつながっているすべての道上の最も長い文字列によって予測される。
→クローン状態を作る

初期状態は扱う内容で変化
→初期状態の各遷移カウントは小さくしておく
→これによってASCIIコードが来ても大丈夫

毎回更新する

頻度によって確率を決定
また既知の記号以外にエスケープ記号を作り、確率を割り当てておく。
→これによって未知の記号にも対応できる。
→エスケープ記号の確率はいろいろあるが今回はu/2nとする。(method D)
→(u=エスケープの数,n=出現したシンボルの総数)

各シンボルをエンコードした後、更新

最適モデルの選択方法

(各パラメータ自体の符号長+確率分布を用いたデータの記述長)を最小にする。
前半部分は、均一分布を用いる。　後半を最小にすることを考える。

  • MCE

ターゲット文書に対して、高確率を出すモデルを選択(static model)
エントロピーが小さくなるモデルを探索
→ここでは、エントロピーは各symbolの平均ビット数を表す

  • MDL(最小記述長)

ターゲット文書の追加による記述長の増加を基にモデルを選択(adaptive model)
記述長の増加が最小になるものを探索(つまり圧縮率の高いもの)

実験

cross validationで行い、false positiveを最小にする。
評価方法として使用するもの

  • SMP
  • FPR
  • ROCカーブ
    • 縦軸に検知率、横軸に誤検知率をとる。閾値を変化させた際の各点をプロットする。左上に点があれば性能が良い。
  • AUC
    • =P(score(positive) > score(negative))
    • 正常なもののと異常なものの分類器によって計算された各値を比較。

結果

MDLが良い結果をもたらした。
AUCの値も改善できた。

また圧縮法も他の方法と比べて精度が上昇(DMC,PPM)

  • 前後の事象を多く参照する事が出来る
  • 前処理が不必要

ノイズをいれた実験に関しても成功
→しかし、理由は解明されていない

まとめ

適応型統計データ圧縮モデルの良い点

  • 前処理がいらない
    • 前処理はspammerに攻撃されやすい部分。
  • 更新可能
  • 実験の結果、他のシステムより精度が高い
  • ノイズに対して強い
  • AUCに関しても適応型を用いる事で改善
    • 誤った際のコストを考えると必要

適応型統計データ圧縮モデルの改善点

  • メモリが多大に必要