2007-06-04

Gary Robinson方式

tokenごとのspam確率を求める方法

Gary Robinson方式でのtokenごとのspam確率をf(w)とする。以下のように求める。

token出現回数にバイアスをかけずに、tokenごとのspam確率p(w)を求める。
全tokenでのp(w)の平均値をrobx、tokenの出現回数をn、ある定数(例えば0.001)をrobsとして、

f(w) = ((s * robx) + (n * p(w))) / (robs + n)
とする。過去に出会ったことのないtokenのf(w)も、この式でカバーされる。

メールのspam確率を求める方法

Gary Robinson方式では、以下で求めたSをメールのspam確率とする(確率を[0,1]で表示する場合にはS2)

P = 1　- ( (1-f(w1))* (1-f(w2))*…*(1-f(wn))) ^ (1/n)
Q = 1 - (f(w1)*f(w2)* … *f(wn)) ^ (1/n)
S = (P - Q) / (P + Q)
S2 = (1 + S) / 2

2007-05-21

DMC(Dynamic Markov Coding)によるデータ圧縮

参照

G. V. Cormack and R.N.S.Horspool.
Data Compression Using Dynamic Markov Modeling.
The Computer Journal, 30(6) :541-550, 1987.

概要

DMC

メッセージのバイナリ表現の性質を表す
先のメッセージを予測することで、データ圧縮する(Guazzoの方法を用いる)
適応型

- 結果、効率的な圧縮に成功

はじめに

データ圧縮法

ソースデータの構造に関するアプリオリな仮定をもとにしている。
- 例)Huffman coding

今回は、ソースデータを離散マルコフ連鎖モデルによって作られたビットの流れと仮定する。

研究の方向性

データを表すマルコフ連鎖モデルを発見する
メッセージの初めでモデルを構築して、予測する
各状態が次の遷移確率を保持する

Guazzoのアルゴリズム

まず、
Huffman codeの欠点

文字の出現が2のn乗の時だけ、減らせる
グループ化したビット間だけ、相互関係が有利になる

Guazzoはこれを修正

[0.000… , 0.11111…]　→　遷移確率を基に分割して行く。
↓
[0.000… , 0.0111…]
↓
…
↓
[0.011100110101 , 0.01110100101111]
(0111001で始まるソースメッセージを表している)

適応型

今までは,two-pass

メッセージの性質を発見する(各確率を計算)
それをもとに圧縮(エンコード)

今回は,
適応型

動的に行う
- 前準備がいらない(k-1個のデータと１つ前のモデルを用いる)

マルコフ連鎖モデル

確率の設定

動的に圧縮する上で、0%になるとまずいので、0の時は(n0+c)/(n0+n1+2c)、1の時は(n1+c)/(n0+n1+2c)と設定する。

グラフの構造
- cloningする。
  - 前後の情報をよりわかりやすくする。
  - 遷移回数に閾値を用いる。(すべてにクローンを作ると無駄が多い)

また、

状態数がある一定の値を超えたら、初期状態に戻す(最後のk個の要素を使って新たに状態を作る)。

Guazzoアルゴリズムの実用

範囲の上限下限を正確に決めなければならない
- 正確さの必要性を弱めた
  - 正確に分割できなくても圧縮率にはあまり影響が無い
- 正確さの基準を決めた。

各intervalが表す列がわからない。
- 0111010に関しては,[0.0111010000…,0.01110101111…]と表すようにする。

結果

他の技術は,
均一されたデータに対して強い。
しかし、不均一なものにうまく対応しきれていない。→これが重要。
DMCだとObject codeの結果を見れば、対応できている事が分かる。

ただ、
状態数＆計算時間　⇔　圧縮率(トレードオフな関係)

2007-05-07

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やバイナリ列を用いる
前処理を行わない

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

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

エンコードの方法

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

アルゴリズム

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

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

毎回更新する

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

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

最適モデルの選択方法

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

ターゲット文書に対して、高確率を出すモデルを選択(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に関しても適応型を用いる事で改善
- 誤った際のコストを考えると必要

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

メモリが多大に必要

2007-04-24

■

DKIM(DomainKeys Identified Mail)の仕組み
→DomainKeysとIIM(Identified Internet Mail)を統一したもの。

例)usr1@a.com から　usr2@b.com　へメールを送信する場合(a.com , b,com :ドメイン名)
　
1. a.comのDNSサーバに電子署名で使用する公開鍵を公開
2. a.comのメールサーバがメールに下のような電子署名を付与する。(送出メール本文とヘッダを基に)

DKIM-Signature:d-a.com : h=…
(これがDomainKeysと違うところ。これによって認証の対象を限定できる。)
from:usr1@a.com
to:usr2@b.com

3. メールをb.comのメールサーバへ送信
4. ヘッダのdタグの値であるa.comのDNSサーバへ公開鍵を問い合わせる。
5. 電子署名を照合する。更に、From:ヘッダのドメイン部とdタグが同じかどうか調べる(IIMと同じ)。両方OKなら認証成功。

yoshida4の日記