(57)【要約】  改良された統計学的モデルを形成する方法及び装置が開示される。一実施形態において、電子通信媒体のための統計学的モデルが作成される。統計学的モデルは、電子通信の所定の１組の特徴に基づく。その後、統計学的モデルは、遺伝的アルゴリズム（ＧＡ）で処理されて、修正された統計学的モデルを作成する。一実施形態において、修正された統計学的モデルがクラシファイアに設けられて、到来する電子通信を分類する。一実施形態において、クラシファイアは、受け取った電子通信をスパムとして分類すべきか、正当なものとして分類すべきか決定する。
2007528544.tif 000002
【特許請求の範囲】
【請求項１】
電子通信媒体のための統計学的モデルを作成し、この統計学的モデルは、前記電子通信の所定の１組の特徴に基づくものであり、そして
前記統計学的モデルを遺伝的アルゴリズム（ＧＡ）で処理して、修正された統計学的モデルを作成する、
という段階を備えた方法。
【請求項２】
前記修正された統計学的モデルをクラシファイアに設けて、到来する電子通信を１つ以上の規定のカテゴリーで分類する段階を更に備えた、請求項１に記載の方法。
【請求項３】
前記１組の特徴は、前記電子通信の構造に関する特徴を含む、請求項２に記載の方法。
【請求項４】
前記電子通信は電子的ドキュメントである、請求項３に記載の方法。
【請求項５】
前記電子通信はｅメールである、請求項３に記載の方法。
【請求項６】
統計学的モデルを作成する前記段階は、前記統計学的モデルを第１組の電子通信に基づいたものとし、そして前記修正された統計学的モデルを個別の第２組の電子通信に基づいたものにすることを含む、請求項３に記載の方法。
【請求項７】
統計学的モデルをＧＡで処理する前記段階は、電子通信を、前記統計学的モデルで表わされた１つ以上の規定のカテゴリーに更に分類する修正された統計学的モデルを形成する、請求項１に記載の方法。
【請求項８】
統計学的モデルを処理する前記段階は、前記修正された統計学的モデルに対する電子通信の付加的な特徴を導出することを含む、請求項７に記載の方法。
【請求項９】
実行されたときに、システムが、
電子通信媒体のための統計学的モデルを作成し、この統計学的モデルは、前記電子通信の所定の１組の特徴に基づくものであり、そして
前記統計学的モデルを遺伝的アルゴリズム（ＧＡ）で処理して、修正された統計学的モデルを作成する、
という段階を備えた方法を実行するようにさせる１組のインストラクションが記憶されたマシン読み取り可能な媒体。
【請求項１０】
前記方法は、前記修正された統計学的モデルをクラシファイアに設けて、到来する電子通信を１つ以上の規定のカテゴリーで分類する段階を更に備えた、請求項９に記載のマシン読み取り可能な媒体。
【請求項１１】
前記１組の特徴は、前記電子通信の構造に関する特徴を含む、請求項９に記載のマシン読み取り可能な媒体。
【請求項１２】
前記電子通信は電子的ドキュメントである、請求項１１に記載のマシン読み取り可能な媒体。
【請求項１３】
統計学的モデルを作成する前記段階は、前記統計学的モデルを第１組の電子通信に基づいたものとし、そして前記修正された統計学的モデルを個別の第２組の電子通信に基づいたものにすることを含む、請求項１１に記載のマシン読み取り可能な媒体。
【請求項１４】
統計学的モデルをＧＡで処理する前記段階は、電子通信を、前記統計学的モデルで表わされた１つ以上の規定のカテゴリーに更に分類する修正された統計学的モデルを形成する、請求項９に記載のマシン読み取り可能な媒体。
【請求項１５】
統計学的モデルを処理する前記段階は、前記修正された統計学的モデルに対する電子通信の付加的な特徴を導出することを含む、請求項１７に記載のマシン読み取り可能な媒体。
【請求項１６】
プロセッサと、
前記プロセッサに結合されたネットワークインターフェイスと、
電子通信媒体のための統計学的モデルを作成する手段であって、この統計学的モデルが、前記電子通信の所定の１組の特徴に基づくものである手段と、
前記統計学的モデルを遺伝的アルゴリズム（ＧＡ）で処理して、修正された統計学的モデルを作成する手段と、
を備えたシステム。
【請求項１７】
前記修正された統計学的モデルをクラシファイアに設けて、到来する電子通信を１つ以上の規定のカテゴリーで分類する手段を更に備えた、請求項１６に記載のシステム。
【請求項１８】
前記１組の特徴は、前記電子通信の構造に関する特徴を含む、請求項１７に記載のシステム。
【請求項１９】
統計学的モデルを作成する前記手段は、前記統計学的モデルを第１組の電子通信に基づいたものとし、そして前記修正された統計学的モデルを個別の第２組の電子通信に基づいたものにする手段を含む、請求項１８に記載のシステム。
【請求項２０】
統計学的モデルをＧＡで処理する前記手段は、電子通信を、前記統計学的モデルで表わされた１つ以上の規定のカテゴリーに分類する修正された統計学的モデルを作成する、請求項１６に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、遺伝的アルゴリズムを使用して、改良された統計学的モデルを作成する方法及び装置に係る。
【背景技術】
【０００２】
本出願は、参考としてここに援用する２００４年３月２日に出願された「METHOD AND APPARATUS TO USE A GENETIC ALGORITHM TO GENERATE AN IMPROVED STATISTICAL MODEL」と題する出願中の米国プロビジョナル特許出願第６０／５４９，６８３号（代理人ドケットNo.６７４７.Ｐ００３Ｚ）の利益を請求する。
【０００３】
ここで使用する「スパム」という語は、要求されない及び／又は非合意の電子通信を指す。又、「求められていない商業的ｅメール」（ＵＣＥ、「求められていないバルクｅメール」（ＵＢＥ）、「グレーメール」及び単に平易に「ジャンクメール」としても知られているスパムは、通常、製品を広告するのに使用される。ここで使用する「電子通信」という語は、ボイスメール通信、ショートメッセージサービス（ＳＭＳ）通信、マルチメディアメッセージングサービス（ＭＭＳ）通信、ファクシミリ通信、等を含むいかなる形式の電子通信又はメッセージも包含するように広く解釈されるべきである。
【０００４】
スパムを使用して電子メールユーザに広告を送信することが益々普及してきている。文書に基づく対応物であるジャンクメールと同様に、スパムを受け取ることは、ほとんどの場合、望ましからぬことである。それ故、スパムがユーザのインボックスに到着する前にそれをフィルタリングする問題に関して著しい努力が払われている。
【０００５】
現在、スパムをフィルタするために書かれたルールを使用するルールベースのフィルタリングシステムを入手できる。ルールの一例として、次のルールが考えられる。
（ａ）「主題の行に“make money fast（早くお金になる）”というフレーズがある場合には、スパムとマークする」、及び
（ｂ）「送信者のファイルがブランクである場合には、スパムとマークする」
【０００６】
通常、ルールベースのフィルタリングシステムがスパムをフィルタリングするのに有効であるためには、何千ものこのような特殊なルールが必要となる。これらルールの各々は、通常、人間により書かれ、これは、ルールベースのフィルタリングシステムのコストを高める。
【０００７】
別の問題は、スパムの送信者（スパマー(spammer)）が、ルールを無効にするようにスパムを巧みに変更することである。例えば、前記ルール（ａ）について考える。スパマーは、主題の行に“make money fast”をもつスパムが阻止されることを観察し、そして例えば、スパムの主題の行を“make money quickly”と読むように変更することができる。主題の行のこの変更は、ルール（ａ）を無効にする。従って、主題の行に“make money quickly”をもつスパムをフィルタリングするように新たなルールを書くことが必要になる。更に、古いルール（ａ）は、システムにより依然として保持されねばならない。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
ルールベースのフィルタリングシステムでは、到来する各電子通信を、何千もの有効なルールに対してチェックしなければならない。それ故、ルールベースのフィルタリングシステムは、到来する各電子通信を何千もの有効なルールに対してチェックしなければならないという過酷な計算負荷をサポートするために非常に高価なハードウェアを必要とする。更に、ルールを書くという過酷な性質も、ルールベースシステムのコストを増大する。
【０００９】
スパムと戦う別の解決策は、統計学的なクラシファイアを使用して、到来する電子通信をスパムとして分類するか又は正当な電子通信として分類することを含む。この解決策は、ルールを使用するものではなく、むしろ、到来する通信がスパムであるかどうかを、スパムに頻繁に生じるワードの分析に基づいて予想するように、統計学的クラシファイアが同調される。統計学的クラシファイアの使用は、ルールベースのフィルタリングシステムに勝る改良をもたらすが、統計学的クラシファイアを使用するシステムは、スパムを正当な通信として誤って分類するように騙されることがある。例えば、スパマーは、電子通信の本文を中間の非包括的形態でエンコードすることがある。このエンコードの結果として、統計学的クラシファイアは、電子通信の本文内のワードを分析することができず、その電子通信を正当な電子通信として誤って分類してしまう。電子通信をワードの分析に基づいてスパムとして分類するシステムに伴う別の問題は、スパムに共通に見られるワードが正当な電子通信にも使用される場合には正当な電子通信が誤ってスパムとして分類され得ることである。
【課題を解決するための手段】
【００１０】
改良された統計学的モデルを形成する方法及び装置が開示される。一実施形態において、電子通信媒体のための統計学的モデルが作成される。統計学的モデルは、電子通信の所定の１組の特徴に基づく。その後、統計学的モデルは、遺伝的アルゴリズム（ＧＡ）で処理されて、修正された統計学的モデルを作成する。一実施形態において、修正された統計学的モデルがクラシファイアに設けられて、到来する電子通信を分類する。一実施形態において、クラシファイアは、受け取った電子通信をスパムとして分類すべきか、正当なものとして分類すべきか決定する。
【発明を実施するための最良の形態】
【００１１】
以下の説明では、本発明を完全に理解するために、説明上、多数の特定の細部を示す。しかしながら、当業者であれば、本発明は、これら特定の細部を伴わずに実施できることが明らかであろう。他の点については、本発明を不明瞭にしないために、構造及び装置をブロック図形態で示す。
【００１２】
本明細書において、「一実施形態」又は「実施形態」を言及するときには、その実施形態に関連して説明する特定の特徴、構造又は特性が本発明の少なくとも１つの実施形態に含まれることを意味する。本明細書の種々の場所で「一実施形態において」というフレーズが出てきたときには、必ずしも全て同じ実施形態を指すものでもないし、他の実施形態と相互排他的な個別の又は代替的な実施形態でもない。更に、ある実施形態では示されるが、他の実施形態では示されない種々の特徴も説明する。同様に、ある実施形態では要求されるが、他の実施形態では要求されない種々の要件についても説明する。
【００１３】
図１は、一実施形態により統計学的モデルを改良及び／又は最適化するプロセスを示すフローチャートである。ブロック１０でスタートして、制御された１組の通信が第１クラシファイアへ送り込まれて、頻度カウントトレーニングを実行し、初期統計学的モデルを作成する。一実施形態では、前記制御された組は、既知の量のスパムと、既知の量の正当な通信とを含む。
【００１４】
ブロック１０２において、１組の通信に対して頻度のカウントが実行されて、所定の１組の特徴がスパム通信に存在し且つ正当な通信に存在する頻度を識別する。一実施形態では、所定の特徴が、電子通信の構造（例えば、電子通信のヘッダ、及び／又は電子通信の本文）に対する変化又は変異（ミューテーション）に関係している。一実施形態では、これら特徴は、電子通信のコンテンツにおける個々のワードではなく、電子通信の構造に関係している。一実施形態では、各特徴に対して発生される１組の頻度（即ち、値）は、それらがスパム及び正当な通信において識別されるとき、初期の統計学的モデルを表わす。
【００１５】
ブロック１０４において、電子通信を複数のグループ又はカテゴリーの１つに分類するのに使用される統計学的モデルを改良し及び／又は最適化するためにアルゴリズムが使用される。一実施形態では、遺伝的アルゴリズムが使用される。
【００１６】
一実施形態において、処理ブロック１０２で作成された特徴の初期統計学的モデルが、既知のスパム及び正当な電子通信の第２コーパスと共に、アルゴリズムへ送り込まれる。このアルゴリズムは、電子通信の構造に関係した規定の特徴（「起源」、「変異」又は「異常」とも称される）の値を変更して、スパム又は正当な通信に対して各々青写真（blueprint）と考えることのできる改良された統計学的モデル（「スパムＤＮＡ」とも称される）を進化させる。
【００１７】
本発明の実施形態を実施するのに使用できるアルゴリズムの一例の詳細は、次の通りである。即ち、ｐ＿ｓｐａｍ及びｐ＿ｌｅｇｉｔは、各々、スパム及び正当な電子通信に見られる特定の特徴に対する頻度カウントである。５００スパムメッセージのコーパスにおいて２００スパムメッセージに特徴Ａ１が見つかったと仮定すれば、Ａ１のｐ＿ｓｐａｍパーセンテージは、４０．００％である。
【００１８】
一実施形態において、全体的精度及び偽の正の数より成る１組のフィットネス関数に基づいて特徴に対するｐ＿ｓｐａｍ及びｐ＿ｌｅｇｉｔ値を繰り返し進化するためのアルゴリズムが使用される。
【００１９】
最初に、フィットネス関数を使用せずに、見つかった特徴が２つのクラス、即ちスパム及び正当なものに分類される。一実施形態では、ｐ＿ｓｐａｍ＞ｐ＿ｌｅｇｉｔの場合に、特徴は、スパムの特徴として分類され、さもなければ、正当なものの特徴として分類される。ｎ個のスパムメッセージ及びｎ個の正当なメッセージのプールにおける各電子通信は、次いで、全ての特徴の存在についてチェックされる。特徴をチェックするプロセスの間に、一実施形態では、１組の頻度テーブル（ハッシュ／マップ／）が生成され、これらテーブルの実施形態の一例を以下に示す（テーブルは、本発明の範囲内で変更し得る）。
【００２０】
頻度テーブルＡ：スパムとして分類された正当なメッセージで見つかったスパムの特徴は、頻度テーブルＡに記憶される。
【００２１】
頻度テーブルＢ：正当なものとして分類されたスパムメッセージで見つかった正当なものの特徴は、頻度テーブルＢに記憶される。
【００２２】
頻度テーブルＣ：正当なものとして分類されたスパムメッセージで見つかったスパムの特徴は、頻度テーブルＣに記憶される。
【００２３】
頻度テーブルＤ：スパムメッセージとして分類された正当なメッセージで見つかった正当なものの特徴は、頻度テーブルＤに記憶される。
【００２４】
頻度テーブルＡ及び頻度テーブルＢにおける異なる特徴（例えば、Ａ１、Ａ２、Ａ３・・・）の一例を以下に示す。
頻度テーブルＡ：                    頻度テーブルＢ：
Ａ１−＞３５                        Ａ９  −＞８０
Ａ２−＞２７                        Ａ１０−＞３８
Ａ３−＞２０                        Ａ１１−＞２３
【００２５】
第２に、一実施形態において、例示的テーブルＡ−Ｄの各エントリーに対し、１組のフィットネス関数からのフィットネス関数を使用して：
１）ＦＴＡにおける各特徴のｐ＿ｓｐａｍからｙ％を減少する
２）ＦＴＢにおける各特徴のｐ＿ｌｅｇｉｔからｙ％を減少する
３）ＦＴＣにおける各特徴のｐ＿ｓｐａｍにｙ％を追加する
４）ＦＴＤにおける各特徴のｐ＿ｌｅｇｉｔにｙ％を追加する
但し、ｙ＝ｆｒｅｑ（ｆｅａｔｕｒｅ）／ｆｒｅｑｓｕｍ（ａｌｌ＿ｆｅａｔｕｒｅｓ）＊ｐａ＊ｒａｎｄ（１、ｐｍ）
ｐａ＝加速度
ｐｍ＝変異率
ｐａは、進化をスピードアップするための加速度値であり、そして変異は、１以上でなければならない変異率である。一実施形態では、加速度及び変異は、両方とも、デフォールトが１である。チェックのプロセスは、一実施形態では、ｐ＿ｓｐａｍ及びｐ＿ｌｅｇｉｔの新たな値を使用して１回以上繰り返される。最終的に、特徴に対する重みは、テーブルＡ及びＢにおけるエントリーの頻度が最小となる一方、テーブルＣ及びＤにおけるエントリーの頻度が最大となる点まで進化する。本発明の範囲内で別の技術、アルゴリズム及び変更を使用してもよい。
【００２６】
特徴の重みの繰り返し変更を使用する技術を、種々の統計学的分類技術に一般的に使用することができ、この場合、入力として選択された特徴の頻度が入力のカテゴリーを決定する。従って、ここに開示する技術は、電子通信の分類に限定されず、統計学的モデルに基づく他の入力の分類にも一般的に適用できる。
【００２７】
プロセスブロック１０４で作成された修正された統計学的モデルは、その後、クラシファイアの分類アルゴリズムへロードされ、これを使用して、到来する通信がスパムであるかどうかの信頼性レベルを与えることができる。一実施形態では、クラシファイアは、メールサーバーのような電子通信転送エージェントにロードすることができる。
【００２８】
図２を参照すれば、一実施形態において、統計学的クラシファイア２０２は、電子通信を配送する役割を果たすコンポーネント、例えば、電子通信転送エージェント２００へロードされる。明らかなように、統計学的クラシファイア２０２は、上述したアルゴリズムを使用して作成された改良された統計学的モデル２０２Ａを含む。電子通信転送エージェントにより受け取られた到来する電子通信は、改良された統計学的モデル２０２Ａを使用して、統計学的クラシファイア２０２により分類される。一実施形態において、電子通信記憶ファシリティ２０４が電子通信転送エージェント２００に結合され、このファシリティは、第１形式（例えば、スパム）として分類される通信のための隔離位置２０４ａと、第２形式（例えば、正当なもの）として分類される通信のための第２の到来位置２０４ｂとを含むことができる。電子通信記憶ファシリティ２０４は、電子通信を検索するために電子通信クライアントによりアクセスすることができる。
【００２９】
図３を参照すれば、参照番号３００は、一実施形態による電子通信転送エージェントサーバーを具現化するのに使用できるハードウェアを一般的に示す。このハードウェア３００は、通常、メモリ３０４に結合された少なくとも１つのプロセッサ３０２を備えている。プロセッサ３０２は、１つ以上のプロセッサ（例えば、マイクロプロセッサ）を表わしてもよく、そしてメモリ３０４は、ハードウェア３００のメイン記憶装置を構成するランダムアクセスメモリ（ＲＡＭ）、並びに補足的レベルのメモリ、例えば、キャッシュメモリ、不揮発性又はバックアップメモリ（例えば、プログラム可能な又はフラッシュメモリ）、リードオンリメモリ、等を表わしてもよい。更に、メモリ３０４は、ハードウェア３００のどこかに物理的に配置されるメモリ記憶装置、例えば、プロセッサ３０２のキャッシュメモリ、並びに仮想メモリとして使用され、例えば、大量記憶装置３１０に記憶される記憶能力を含むと考えられてもよい。
【００３０】
又、ハードウェア３００は、通常、外部と情報を通信するために多数の入力及び出力を受け取る。ユーザ又はオペレータとインターフェイスするために、ハードウェア３００は、１つ以上のユーザ入力装置３０６（例えば、キーボード、マウス、等）、及びディスプレイ３０８（例えば、陰極線管（ＣＲＴ）モニタ、液晶ディスプレイ（ＬＣＤ）パネル）を備えてもよい。
【００３１】
又、付加的な記憶装置として、ハードウェア３００は、１つ以上の大量記憶装置３１０、例えば、とりわけ、フロッピー又は他の除去可能なディスクドライブ、ハードディスクドライブ、直接アクセス記憶装置（ＤＡＳＤ）、光学ドライブ（例えば、コンパクトディスク（ＣＤ）ドライブ、デジタル多様性ディスク（ＤＶＤ）ドライブ、等）、及び／又はテープドライブを含んでもよい。更に、ハードウェア３００は、１つ以上のネットワーク３１２（例えば、とりわけ、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、ワイヤレスネットワーク、及び／又はインターネット）とのインターフェイスを含み、それらネットワークに結合された他のコンピュータと情報を通信することもできる。
【００３２】
上述したプロセスは、コンピュータシステムのメモリに、実行されるべき１組のインストラクションとして記憶することができる。更に、上述したプロセスを遂行するためのインストラクションは、磁気及び光学ディスクを含む他の形態のマシン読み取り可能な媒体に記憶することもできる。例えば、上述したプロセスは、ディスクドライブ（又はコンピュータ読み取り可能な媒体ドライブ）を経てアクセスできる磁気ディスク又は光学ディスクのようなマシン読み取り可能な媒体に記憶することができる。更に、インストラクションは、コンパイルされそしてリンクされたバージョンの形態でデータネットワークを経て計算装置へダウンロードすることもできる。
【００３３】
或いは又、上述したプロセスを遂行するためのロジックは、付加的なコンピュータ及び／又はマシン読み取り可能な媒体、例えば、個別ハードウェアコンポーネント、例えば、大規模集積回路（ＬＳＩ）、特定用途向け集積回路（ＡＳＩＣ）、ファームウェア、例えば、電気的に消去可能なプログラマブルリードオンリメモリ（ＥＥＰＲＯＭ）、並びに電気的、光学的、音響的及び他の形態の伝播信号（例えば、搬送波、赤外線信号、デジタル信号、等）、等々において実施することができる。
【００３４】
以上、特定の実施形態を参照して本発明を説明したが、特許請求の範囲に記載した本発明の広い精神から逸脱せずに、これらの実施形態に対して種々の変更や修正がなされ得ることが明らかであろう。従って、本明細書及び添付図面は、本発明を単に例示するもので、本発明をそれに限定するものではない。
【図面の簡単な説明】
【００３５】
【図１】本発明の一実施形態により改良された統計学的モデルを発生するプロセスを示すフローチャートである。
【図２】本発明の一実施形態により改良された統計学的モデルを使用する電子通信システムのグラフィック表示である。
【図３】一実施形態により改良された統計学的モデルを具現化することのできるハードウェアの高レベルブロック図である。
【図１】
2007528544.tif 000003
【図２】
2007528544.tif 000004
【図３】
2007528544.tif 000005
【国際調査報告】
2007528544.tif 000006
2007528544.tif 000007
2007528544.tif 000008