(57)【要約】      （修正有）【課題】情報ニーズは、サポートベクタマシン（ＳＶＭ）などの二値分類子によりモデル化できる。ＳＶＭは、情報ニーズをモデル化する際に非常に保守的な精度重視の挙動を示し得る。この保守的な挙動は超平面の位置、つまりＳＶＭの幾何学的表現を調整することにより克服できる。【解決手段】ベータ−ガンマ閾値化プロシージャ、相互フォールド検証及び改修に基づいてＳＶＭモデルの該位置を調整するための２、３の自動技法を説明する。この調整技法は、他の種類の学習方法にも適用できる。【選択図】  図１−１
2005316996.tif 000002
【特許請求の範囲】
【請求項１】
ラベルが付かない文書及びラベル付きの文書を受け取り、
各文書からフィーチャの集合を抽出し、
情報要求に関して正または負として印される標本文書からモデルを学習する、ことを含み、
前記モデルは、前記情報要求に応えてグループ内のメンバーシップの程度を評価するために文書にスコアをつけ、さらに、
標本文書においてモデル設定の性能を評価し、
閾値θnewを提供する調整アルゴリズムを適用し、
学習された前記モデルにより文書に割り当てられる値であるスコアを計算し、以下の式
【数１】
2005316996.tif 000036
の符号に基づいて前記文書を分類するスコアリング関数を適用する、
ことを含む、情報要求をモデル化するための方法。
【請求項２】
前記モデルは、ラベル付きの標本文書からの訓練データにより決定されるサポートベクタマシンである、請求項１に記載の情報要求をモデル化するための方法。
【請求項３】
前記モデルは、ラベル付きの標本文書から抽出されるターム（ｔｅｒｍｓ）および重みのリストを備える、請求項１に記載の情報要求をモデル化するための方法。
【請求項４】
前記モデルは、
正の文書及び負の文書からターム及びフィーチャを抽出し、
ターム及びフィーチャをランク付け、
ランク付けされた前記ターム及び前記フィーチャからターム及びフィーチャの部分集合を選択し、
ターム及びフィーチャごとに重みｗiを割り当て、
前記モデルのための閾値θをゼロに設定する、
ことによって決定されるターム及び対応する重み、及び閾値のリストを備える、請求項１に記載の情報要求をモデル化するための方法。
【請求項５】
前記ターム及びフィーチャは、Ｒｏｃｃｈｉｏスコアの降順でランク付けされ、Ｒｏｃｃｈｉｏスコアは、
【数２】
2005316996.tif 000037
として計算され、式中、
ＴＦi,Text：前記情報ニーズの前記テキスト記述中のフィーチャの頻度
ＴＦij：文書jの中のフィーチャの発生数
ＤR：正の文書集合
ＤN：負の文書集合
Ｒ：正の文書の数（つまりＤRのサイズ）
Ｎ：負の文書の数
である、請求項４に記載の情報要求をモデル化するための方法。
【請求項６】
前記ターム及びフィーチャは、式ｗi＝Ｒｏｃｃｈｉｏi・ｉｄｆiにより重みを割り当てられ、式中、Ｒｏｃｃｈｉｏiは、
【数３】
2005316996.tif 000038
として計算され、式中、
ＴＦi,Text：前記情報ニーズの前記テキスト記述中のフィーチャの頻度
ＴＦij：文書jの中のフィーチャの発生数
ＤR：正の文書集合
ＤN：負の文書集合
Ｒ：正の文書の数（つまりＤRのサイズ）
Ｎ：負の文書の数
であり、さらに、ｉｄｆiは、
【数４】
2005316996.tif 000039
として計算され、
式中、Ｓは前記集合内の文書の前記カウントであり、ｎiはｉ番目のフィーチャが発生する前記文書の前記カウントである、請求項４に記載の情報要求をモデル化するための方法。
【請求項７】
ネットワークに結合されるコンピュータを備え、前記コンピュータは、前記ネットワーク上で文書を受信し、前記ネットワーク上で個々のユーザに文書を送信し、前記コンピュータは、
ラベルが付かない文書及びラベル付きの文書を受け取り、
各文書からフィーチャの集合を抽出し、
カテゴリに関して正または負と印される前記標本文書からモデルを学習する、ことを備え、
前記モデルは、前記カテゴリ内でのメンバーシップの程度を評価するために文書にスコアをつけ、さらに
標本文書においてモデル設定の性能を評価し、
閾値θnewを提供する調整アルゴリズムを適用し、
学習された前記モデルにより文書に割り当てられる値であるスコアを計算し、以下の式
【数５】
2005316996.tif 000040
の符号に基づいて前記文書を分類するスコアリング関数を適用する、
ことを含む、文書をフィルタリングするためのシステム。
【請求項８】
前記モデルは、ラベル付きの標本文書からの訓練データによって決定されるサポートベクタマシンである、請求項７に記載の文書をフィルタリングするためのシステム。
【請求項９】
前記モデルは、ラベル付きの標本文書から抽出されるターム及び重みのリストを備える、請求項７に記載の文書をフィルタリングするためのシステム。
【請求項１０】
前記モデルは、
前記正の文書及び負の文書からターム及びフィーチャを抽出し、
ターム及びフィーチャをランク付け、
ランク付けされた前記ターム及び前記フィーチャからターム及びフィーチャの部分集合を選択し、
ターム及びフィーチャごとに重みｗiを割り当て、
前記モデルのための閾値θをゼロに設定すること、
によって決定されるターム及び対応する重み、及び閾値のリストを備える、請求項７に記載の文書をフィルタリングするためのシステム。
【請求項１１】
前記ターム及びフィーチャは、Ｒｏｃｃｈｉｏスコアの降順でランク付けされ、Ｒｏｃｃｈｉｏスコアは、
【数６】
2005316996.tif 000041
として計算され、式中、
ＴＦi,Text：前記情報ニーズの前記テキスト記述中のフィーチャの頻度
ＴＦij：文書jの中のフィーチャの発生数
ＤR：正の文書集合
ＤN：負の文書集合
Ｒ：正の文書の数（つまりＤRのサイズ）
Ｎ：負の文書の数
である、請求項１０の文書をフィルタリングするためのシステム。
【請求項１２】
前記ターム及びフィーチャは、式ｗi＝Ｒｏｃｃｈｉｏi・ｉｄｆiにより重みを割り当てられ、式中、Ｒｏｃｃｈｉｏiは、
【数７】
2005316996.tif 000042
として計算され、式中、
ＴＦi,Text：前記情報ニーズの前記テキスト記述中のフィーチャの頻度
ＴＦij：文書jの中のフィーチャの発生数
ＤR：正の文書集合
ＤN：負の文書集合
Ｒ：正の文書の数（つまりＤRのサイズ）
Ｎ：負の文書の数
であり、さらにｉｄｆiは、
【数８】
2005316996.tif 000043
として計算され、式中、Ｎは前記集合内の文書の前記カウントであり、ｎiは、ｉ番目のフィーチャが発生する前記文書の前記カウントである、請求項１０に記載の文書をフィルタリングするためのシステム。
【請求項１３】
ラベルが付かない文書及びラベル付きの文書を受け取り、
各文書からフィーチャの集合を抽出し、
要求に関して正または負として印される標本文書からモデルを学習する、ことを含み、
前記モデルは、前記要求に応えてグループ内のメンバーシップの程度を評価するために文書にスコアをつけ、さらに、
標本文書においてモデル設定の性能を評価し、
閾値θnewを提供する調整アルゴリズムを適用し、
学習された前記モデルにより文書に割り当てられる値であるスコアを計算し、以下の式
【数９】
2005316996.tif 000044
の符号に基づいて前記文書を分類するスコアリング関数を適用する、
ことを含む、要求に応えて情報を検索するための方法。
【請求項１４】
前記モデルは、ラベル付きの標本文書からの訓練データにより決定されるサポートベクタマシンである、請求項１３に記載の要求に応えて情報を検索するための方法。
【請求項１５】
前記モデルは、ラベル付きの標本文書から抽出されるターム及び重みのリストを備える、請求項１３に記載の要求に応えて情報を検索するための方法。
【請求項１６】
前記モデルは、
前記正の文書及び負の文書からターム及びフィーチャを抽出し、
ターム及びフィーチャをランク付け、
ランク付けされた前記ターム及び前記フィーチャからターム及びフィーチャの部分集合を選択し、
ターム及びフィーチャごとに重みｗiを割り当て、
前記モデルのための閾値θをゼロに設定する、
ことによって決定されるターム及び対応する重み、及び閾値のリストを備える、請求項１３に記載の要求に応えて情報を検索するための方法。
【請求項１７】
前記ターム及びフィーチャは、Ｒｏｃｃｈｉｏスコアの降順でランク付けされ、Ｒｏｃｃｈｉｏスコアは、
【数１０】
2005316996.tif 000045
として計算され、式中
ＴＦi,Text：前記情報ニーズの前記テキスト記述中のフィーチャの頻度
ＴＦij：文書jの中のフィーチャの発生数
ＤR：正の文書集合
ＤN：負の文書集合
Ｒ：正の文書の数（つまりＤRのサイズ）
Ｎ：負の文書の数
である、請求項１６に記載の要求に応えて情報を検索するための方法。
【請求項１８】
前記ターム及びフィーチャは、式ｗi＝Ｒｏｃｃｈｉｏi・ｉｄｆiにより重みを割り当てられ、式中、Ｒｏｃｃｈｉｏiは、
【数１１】
2005316996.tif 000046
として計算され、式中、
ＴＦi,Text：前記情報ニーズの前記テキスト記述中のフィーチャの頻度
ＴＦij：文書jの中のフィーチャの発生数
ＤR：正の文書集合
ＤN：負の文書集合
Ｒ：正の文書の数（つまりＤRのサイズ）
Ｎ：負の文書の数
であり、さらに、ｉｄｆiは、
【数１２】
2005316996.tif 000047
として計算され、式中、Ｓは前記集合内の文書の前記カウントであり、ｎiはｉ番目のフィーチャが発生する前記文書のカウントである、請求項１６に記載の要求に応えて情報を検索するための方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ化された情報サーチ及び検索システムの分野に関する。本発明は、概してテキスト情報を含むオブジェクトが、特定の１つのまたは複数のカテゴリに属するかどうかを判断するための方法および装置に関する。特に本発明は、学習されたサポートベクタマシンモデルの閾値スコアを設定・更新するための方法および装置に関する。
【背景技術】
【０００２】
特に分散型データベース上でのコンピュータシステムによりアクセス可能な膨大な量の情報を考えると、より効率的な情報管理方法が常に必要とされている。情報管理の一般型の一例が情報フィルタリングである。情報フィルタリングにおいては、システムは、ユーザの要件を満たす限られた数の文書（または情報）を検索する、あるいはユーザに提示する。情報フィルタリングの１つの形式では、システムへの送達に伴い、文書は、おそらく連続的に、ストリームまたはバッチで処理される。データベース検索では、データベース内のすべての文書が一度に使用可能であり、ユーザへの提示前に文書を互いに比較しランク付けすることができるが、データベース検索とは対照的に、この形式のフィルタリングでは、文書はシステムにより一度に１つ、あるいは小さな集合で評価され、文書の承認（この場合はユーザに文書を提示すること）、または文書の拒絶（ユーザに文書を提示しないこと）という二者択一が個々の文書について行われる。文書フィルタリングでは、情報ニーズが直接的に表明されず、該情報ニーズを満たすあるいは満たさない標本文書の集合としてシステムに提示される場合が多い。この集合は、トピックまたはカテゴリまたはクラスを表現していると見なすことができる。システムは情報ニーズモデルを導出するために文書のこの集合を処理しなければならない。通常、情報ニーズは、正の標本と負の標本の両方から学習できる二値文書分類子モデルとして表現できる。フィルタリング決定を下すとき、システムは文書中の情報と、ユーザのニーズまたはトピックを表す働きをする導出された（学習されたとも呼ばれる）情報モデルに含まれる情報とを比較する。文献では、情報フィルタリングはテキスト分類としても一般的に知られている。本明細書では、情報フィルタリングとテキスト分類の両方を特徴付けるために情報ニーズという用語を使用し、当該システムのユーザは人間または別のコンピュータシステムでありうる。
【０００３】
情報ニーズは、モデルとして知られる種々の表現を使用して計算機的に表現できる。一般的には情報管理システムは、ベクタ空間表現を使用して文書及び情報ニーズモデルを計算機的に特徴付ける。ベクタ空間モデルの生成に関する追加の背景技術は、引用により本文に組み込まれる米国特許第５，６１９，７０９号に、ＳａｌｔｏｎらによるＡＳＩＳのジャーナル、１９７５年１１月、１８：１１、６１３−６２０、「情報検索のためのベクタ空間モデル（Ａ  Ｖｅｃｔｏｒ  Ｓｐａｃｅ  Ｍｏｄｅｌ  Ｆｏｒ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｒｅｔｒｉｅｖａｌ）」に開示されている。
【０００４】
ベクタ−空間表現では、文書は、（フィーチャのベクタとしても知られる）タプルのリストとして概念的に表示できる。文書ベクタＤは、形式＜ｆi，ｗi＞のタプルのリストから構成され、ここでｆiは（単語、名詞句、または任意の言語学的にあるいは他の態様で導出されたフィーチャなどの）フィーチャを示し、ｗiはフィーチャｆiに関連付けられる重みを示す。ここでは、重み値ｗiは単なる二値であってもよく、その場合例えば、値１は、該フィーチャが文書で発生したことを示し、値０は、該フィーチャが文書で発生していないことを示す。以下に提示するＴＦ＿ＩＤＦなどの代替重み付け方式も使用できる。情報ニーズは、ベクタ空間表現を使用して表現することもできる。
【０００５】
自動技法を使用した情報ニーズのモデル化は、情報管理の研究及び応用の非常に活発な領域である。最近では、手書き文字認識、顔検出を含む種々の学習問題に関して優れた性能を示すサポートベクタマシン（ＳＶＭ）が情報ニーズのモデル化に応用されている。情報ニーズのモデル化のためのＳＶＭの性能は、精度の点では他の手法（例えば、Ｒｏｃｃｈｉｏ、ｎａｉｖｅ  Ｂａｙｅｓ）より優位であるが、改修（リコール／ｒｅｃａｌｌ）の点では優位性がない。
【０００６】
ＳＶＭモデルは、多次元フィーチャ空間内の２つのクラスのオブジェクトを２つの互いに素な部分集合に分割する超平面（または超曲面）として幾何学的に表現できる。本発明では、超平面は、情報ニーズを満たす文書に対応する正の集合と、情報ニーズを満たさない文書に対応する負の集合とに文書を分割する。数学的には、線形ＳＶＭ（非線形ＳＶＭは後に提示される）は、以下の２つの同等な形式で表現できる。つまり重みベクタ表現を使用するか、あるいはサポートベクタ表現を使用する。重みベクタ表現は、数学的にＳＶＭ（分離超平面）を1組のパラメータ＜Ｗ，ｂ＞として表現し、ここでＷは重みベクタを示し、ｂは閾値またはバイアスタームを表す。重みベクタＷは、形式＜ｆi，ｗi＞のタプルのリストから構成され、ここではｆiはフィーチャを示し、ｗiはフィーチャｆiに関連付けられる重みを示す。これは、重みベクタＷのベクタ空間表現に相当する。ここでは、各フィーチャｆiと関連付けられる重み値ｗi及び閾値ｂは、標準的なＳＶＭ学習アルゴリズムを使用して標本から学習される。この重みベクタ表現は原始（ｐｒｉｍａｌ）表現とも呼ばれる。二重表現としても知られるＳＶＭモデルのサポートベクタ表現は、数学的にＳＶＭ（該分離超平面）を1組のパラメータ＜ＳＶ，ｂ＞として表現し、ここで、ＳＶはサポートベクタとして知られる標本タプルのリストを示し、ｂは閾値を示す。サポートベクタリストは形式＜ＳＶi，αi＞のタプルから構成され、ここでＳＶiは既知の分類による標本文書を示し、αiは標本のＳＶiに関連付けられる重みを示す。超平面からサポートベクタまでのユークリッド（垂直）距離はサポートベクタマシンのマージンとして知られる。
【０００７】
サポートベクタマシンモデルのパラメータは、情報ニーズを特徴付ける訓練データセットとともに学習アルゴリズムを使用して決定される。ここで訓練データセットとは、正または負のラベルが付けられた文書のリストを指す。訓練アルゴリズムのいくつかは、後述される。抽象的には、線形ＳＶＭモデルの学習は、学習の間に使用される正の標本と負の標本とを分離する超平面の位置及び向きを決定することに帰着する。超平面の位置及び向きの決定はさらに、重みベクタ表現またはサポートベクタ表現のパラメータを決定することに帰着する。サポートベクタマシンの学習は、制約の満足とも最適化アルゴリズムとも見ることができ、第1の目的は、それぞれのラベルが付けられた訓練標本を正しく分類する超平面を決定することであり、第２の目的は、訓練データから最も遠い超平面を決定することである。ＳＶＭモデルを使用して標本を分類することは、標本が超平面のいずれの側に位置するのかを決定することに帰着する。標本が超平面の正の側に位置する場合には、標本には正のラベルが割り当てられ、それ以外の場合には、負のラベルが割り当てられる。学習されたＳＶＭのこの形式はハードＳＶＭとして知られている。第1の目的を緩和する他の形のＳＶＭも存在する。例えば、ＳＶＭによってすべての訓練標本を正しく分類することを要求しなければ、ソフトＳＶＭとして知られるものになる。ソフトＳＶＭのＳＶＭ学習アルゴリズムでは、モデルの精度が落ちるかわりにモデルのマージンが大きくなる。他の種類のＳＶＭ及びＳＶＭ学習アルゴリズムも存在し、その内のいくつかが後述される。
【０００８】
理論的には、ＳＶＭの汎化エラー（未知のデータに適用した場合のモデルのエラー）は、マージンの関数として上限付けることができる。マージンとは、（サポートベクタとして知られる）最も近いデータポイントから分離決定面（超平面）までの距離である。その結果、ＳＶＭ学習アルゴリズムは、マージンを最大にするモデルの検出に集中する。モデル選択に対するこの手法は、完全にデータ集中型であり、密度の高いデータ問題において極めて高い性能を示す。しかしながら、情報ニーズのモデル化のように、データがまばらで、クラスが偏在し完全に表現されていない領域では、この学習手法はより頻出するクラスの過剰適合につながることがある。つまり、これらの学習アルゴリズムは、精度は優れているが、リコールが不完全なモデルにつながる。緩和手法として知られる多様な手法がこの問題に対応するために提案されてきた。これらの手法は以下のように特徴付けることができる。つまり、学習アルゴリズムの中に緩和方法を組み入れる手法、緩和を学習ステップの回りのラッパー（ｗｒａｐｐｅｒ）として扱う手法、及び緩和を学習後閾値化ステップと見なす手法である。ここで、上記緩和手法のそれぞれについて主要な特徴、長所及び短所に注目して検討する。
【０００９】
組み入れ型緩和方法はソフトＳＶＭ（低誤り率を大きなマージンで釣り合わせるＳＶＭモデル）を元にし、それにより異なるつまり非対称なコストが偽の負（ｆａｌｓｅ  ｎｅｇａｔｉｖｅ）及び偽の正（ｆａｌｓｅ  ｐｏｓｉｔｉｖｅ）に関連付けられる。負の訓練文書と正の訓練文書との不均衡に対応するために、正の文書の誤分類に関連付けられるコストの方が負の文書に対するものよりも高くされるため、得られるＳＶＭモデルは、大きなマージンとほとんどないエラー（特に、正の誤分類がほとんどないこと）との釣り合いをとるものとなる。これは、一般的に、ハードＳＶＭ構築から生じる分離する超平面とは向き及び位置の異なる超平面を生じさせる。誤分類のコストを非対称に調整するため、このプロセスは非常に高価になりうるが、かなりの改善を提供できる。
【００１０】
第２の一般的な緩和手法は学習ステップの外で行われるが、異なった緩和レベルを選ぶための評価機能として学習アルゴリズムを使用する。このカテゴリは、例えば正のマージン及び負のマージンを使用するなど、不規則なマージンをベースにした学習を組み込む。正のマージン及び負のマージンの程度は、考えられるマージンの集合から相互検証を使用して経験的に決定される。不規則なマージンベースの学習からは、標準的なハードまたはソフトＳＶＭ学習アルゴリズムから得られる超平面とは向き及び位置が異なる分離超平面が得られる。不規則なマージンベースの学習は、今日まで、テキスト文書のルーティング／ランク付けの問題に限定されていた。この応用分野においては不規則なマージンベースの学習は、最先端の性能を発揮する。この緩和手法も、高価になる可能性がある。相互検証ステップそれぞれにおいて個別のＳＶＭの訓練が必要となる相互検証と（相互検証で決定されたマージン設定を使用する）最終的なＳＶＭ訓練ステップとから訓練が構成されるためである。
【００１１】
最後の緩和カテゴリは、ＳＶＭモデルが学習された後に適用される手法に関する。このカテゴリの手法は学習されたＳＶＭの出力値（またはマージン）の閾値化に基づく。一般的には、性能基準で大きな改善につながることがある安価な一次元最適化問題である。この手法では、分離超平面の位置が変化する（または並進する）が、（ハードまたはソフトＳＶＭ学習から生じるような）超平面の向きの変化は生じない。この閾値化ステップの性質が一般的であることに注意する必要がある。したがって、本発明のＳＶＭをコアモデルとして、それぞれ文書スコア及び確率を出力するＲｏｃｃｈｉｏモデルまたは確率的モデルなどの多くの一般的な種類の情報モデルのどれかと置き換えることができる。
【００１２】
閾値化で重要なステップは、閾値と呼ばれる値を決定することであり、閾値とは、その値を越えると、情報ニーズに対して文書を正とラベル付けするか、負とラベル付けするかの決定が変化する値である。情報検索（ＩＲ）などの他の分野において及び他の目的のために開発された閾値化手法の多くは、ＳＶＭのスコア出力の閾値化に直接応用できる。閾値化はＩＲの一分野である適応フィルタリングにおいて多くの注目を集めたが、閾値の最適化は依然難しい問題である。主要な問題は、ラベルを付けられた訓練データの欠如から生じる。訓練データの量が限られているため、標準的なＩＲモデル化手法では、モデル適合（学習）と閾値最適化の両方に同じデータを使用する。その結果、多くの場合、高精度に閾値にバイアスがかけられる、すなわち、閾値が訓練データに過剰適合（オーバーフィット）する。この問題に対処するために提案されるベータ−ガンマ閾値化アルゴリズム及びその背景技術は、引用により本文に組み込まれる米国特許第６，４３０，５５９号、第６，４６３，４３４号、第６，５３５，８７６号及び第６，５８７，８５０号にさらに詳細に説明されている。他の手法も使用されてきた。Ｙａｎｇは、テキストカテゴリ化のためにスコアをベースにした多様な閾値化アルゴリズムを提案、提示してきた（例えば、Ｙａｎｇ  Ｙ．の論文、「テキストカテゴリ化のための閾値化方法に関する研究（Ａ  ｓｔｕｄｙ  ｏｎ  ｔｈｒｅｓｈｏｌｄｉｎｇ  ｓｔｒａｔｅｇｉｅｓ  ｆｏｒ  ｔｅｘｔ  ｃａｔｅｇｏｒｉｚａｔｉｏｎ）」、情報検索研究開発ＡＣＭ  ＳＩＧＩＲ会議（ＳＩＧＩＲ‘０１）紀要（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＡＣＭ  ＳＩＧＩＲ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｒｅｓｅａｒｃｈ  ａｎｄ  Ｄｅｖｅｌｏｐｍｅｎｔ  ｉｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｒｅｔｒｉｅｖａｌ）、２００１年、１３７−１４５を参照）。Ｚｈａｎｇ及びＣａｌｌａｎはフィルタリング閾値の最大尤度推定を提示した（Ｙ．Ｚｈａｎｇ及びＪ．Ｃａｌｌａｎ、「ＴＲＥＣ−９でのＹＦｉｌｔｅｒ（ＹＦｉｌｔｅｒ  ａｔ  ＴＲＥＣ−９）」、第９回テキスト検索会議（ＴＲＥＣ−９）紀要（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｎｉｎｔｈ  Ｔｅｘｔ  ＲＥｔｒｉｅｖａｌ  Ｃｏｎｆｅｒｅｎｃｅ）（１３５から１４０ページ）、米国標準技術研究所、２００１年、特別出版５００−２４９）。Ａｒａｍｐａｔｚｉｓは、スコア分散ベースの閾値最適化アルゴリズムを提案した（例えばＡｒａｍｐａｔｚｉｓ  Ａ．の論文、適応文書フィルタリングのためバイアスをかけていないＳ−Ｄ閾値最適化、初期照会劣化、崩壊、及びインクリメンタリティ（Ｕｎｂｉａｓｅｄ  Ｓ−Ｄ  Ｔｈｒｅｓｈｏｌｄ  Ｏｐｔｉｍｉｚａｔｉｏｎ，Ｉｎｉｔｉａｌ  Ｑｕｅｒｙ  Ｄｅｇｒａｄａｔｉｏｎ，Ｄｅｃａｙ，ａｎｄ  Ｉｎｃｒｅｍｅｎｔａｌｉｔｙ，  ｆｏｒ  Ａｄａｐｔｉｖｅ  Ｄｏｃｕｍｅｎｔ  Ｆｉｌｔｅｒｉｎｇ）、第１０回テキスト検索会議（（Ｔｅｎｔｈ  Ｔｅｘｔ  Ｒｅｔｒｉｅｖａｌ  Ｃｏｎｆｅｒｅｎｃｅ）（ＴＲＥＣ−２００１）、２００２年、５９６−６０５を参照）。Ａｕｌｔ及びＹａｎｇは、適応フィルタリングのための最適な閾値を予測するためにマージンをベースにした局所的回帰を提案した（例えば、ＴＲＥＣ−１０、第１０回テキスト検索会議（Ｔｅｎｔｈ  Ｔｅｘｔ  Ｒｅｔｒｉｅｖａｌ  Ｃｏｎｆｅｒｅｎｃｅ）（ＴＲＥＣ−２００１）、２００２年、８４−９３の論文、Ａｕｌｔ  Ｔ．Ｙａｎｇ  Ｙ．ｋＮＮ、Ｒｏｃｃｈｉｏ及び情報フィルタリングのための評価指標（Ｒｏｃｃｈｉｏ  ａｎｄ  Ｍｅｔｒｉｃｓ  ｆｏｒ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｆｉｌｔｅｒｉｎｇ）を参照）。
【００１３】
これらのＩＲ手法のいくつかは、すでにＳＶＭの閾値を調整するために適用されている。例えば、Ｃａｎｃｅｄｄａら（例えば、論文、Ｃａｎｃｅｄｄａ  Ｎ．ら、「文書フィルタリングのためのカーネル方法（Ｋｅｒｎｅｌ  Ｍｅｔｈｏｄｓ  ｆｏｒ  Ｄｏｃｕｍｅｎｔ  Ｆｉｌｔｅｒｉｎｇ）」、第１１回テキスト検索会議（Ｅｌｅｖｅｎｔｈ  Ｔｅｘｔ  Ｒｅｔｒｉｅｖａｌ  Ｃｏｎｆｅｒｅｎｃｅ）（ＴＲＥＣ−１１）、２００３年を参照）は、カテゴリごとに正の文書及び負の文書のためのＳＶＭスコア（出力値）のガウスモデル化プロセスに基づいてＳＶＭの閾値を調整する手法を報告している。このガウスモデルはさらに、サンプル文書スコアを生成するために使用され、最適閾値は最適効用に対応するスコアに設定される。非対称学習と結合されたこの手法は、改善がどの程度まで非対称コスト学習方法に起因するのか、あるいは閾値化方法に起因するのかを識別することは困難であるが、リコール及び精度の多大な改善につながった。
【００１４】
ＳＶＭと組み合わせて閾値化を使用することの利点は、ユーザ効用モデルを自然に学習段階に組み込むことができるという点である。学習に効用モデルを組み込むことができると、標準情報検索方法についてシステム性能を測った場合、システム性能が改善されることが立証されている。（例えば、論文、Ｓｈａｎａｈａｎ  Ｊ．Ｇ．、Ｒｏｍａ  Ｎ．、「閾値調整によるＳＶＭテキスト分類性能の改善（Ｉｍｐｒｏｖｉｎｇ  ＳＶＭ  Ｔｅｘｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ  Ｐｅｒｆｏｒｍａｎｃｅ  ｔｈｒｏｕｇｈ  Ｔｈｒｅｓｈｏｌｄ  Ａｄｊｕｓｔｍｅｎｔ）」、機械学習に関する欧州会議（Ｅｕｒｏｐｅａｎ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ）（ＥＣＭＬ）２００３年を参照）。
【００１５】
したがって、効用モデルを組み込むＳＶＭの性能を高めるための代替閾値調整方式を開発することは有利となる。
【００１６】
【特許文献１】米国特許第５，６１９，７０９号
【特許文献２】米国特許第６，４３０，５５９号
【特許文献３】米国特許第６，４６３，４３４号
【特許文献４】米国特許第６，５３５，８７６号
【特許文献５】米国特許第６，５８７，８５０号
【特許文献６】米国特許第５，９０７，８４０号
【特許文献７】米国特許第５，９９９，９２５号
【特許文献８】米国特許第６，１１５，７０６号
【特許文献９】米国特許第６，２０５，４４３号
【特許文献１０】米国特許第６，３７７，９４７号
【特許文献１１】米国特許第６，３２７，５８１号
【非特許文献１】Ｓａｌｔｏｎら、ＡＳＩＳジャーナル、１９７５年１１月１８：１１、６１３−６２０、「情報検索のためのベクタ空間モデル（Ａ  Ｖｅｃｔｏｒ  Ｓｐａｃｅ  Ｍｏｄｅｌ  Ｆｏｒ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｒｅｔｒｉｅｖａｌ）」
【非特許文献２】Ｙａｎｇ  Ｙ．、「テキストカテゴリ化のための閾値化方法に関する研究（Ａ  ｓｔｕｄｙ  ｏｎ  ｔｈｒｅｓｈｏｌｄｉｎｇ  ｓｔｒａｔｅｇｉｅｓ  ｆｏｒ  ｔｅｘｔ  ｃａｔｅｇｏｒｉｚａｔｉｏｎ）」、情報検索研究開発ＡＣＭ  ＳＩＧＩＲ会議（ＳＩＧＩＲ‘０１）紀要（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＡＣＭ  ＳＩＧＩＲ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｒｅｓｅａｒｃｈ  ａｎｄ  Ｄｅｖｅｌｏｐｍｅｎｔ  ｉｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｒｅｔｒｉｅｖａｌ）、２００１年、１３７−１４５）
【非特許文献３】Ｙ．Ｚｈａｎｇ及びＪ．Ｃａｌｌａｎ、「ＴＲＥＣ−９でのＹＦｉｌｔｅｒ（ＹＦｉｌｔｅｒ  ａｔ  ＴＲＥＣ−９）」第９回テキスト検索会議（ＴＲＥＣ−９）紀要（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｎｉｎｔｈ  Ｔｅｘｔ  ＲＥｔｒｉｅｖａｌ  Ｃｏｎｆｅｒｅｎｃｅ）（１３５〜１４０ページ）、米国標準技術研究所、２００１年、特別出版５００−２４９）
【非特許文献４】Ａｒａｍｐａｔｚｉｓ  Ａ．、「適応文書フィルタリングのためバイアスをかけていないＳ−Ｄ閾値最適化、初期照会劣化、崩壊、及びインクリメンタリティ（Ｕｎｂｉａｓｅｄ  Ｓ−Ｄ  Ｔｈｒｅｓｈｏｌｄ  Ｏｐｔｉｍｉｚａｔｉｏｎ，Ｉｎｉｔｉａｌ  Ｑｕｅｒｙ  Ｄｅｇｒａｄａｔｉｏｎ，Ｄｅｃａｙ，ａｎｄ  Ｉｎｃｒｅｍｅｎｔａｌｉｔｙ，  ｆｏｒ  Ａｄａｐｔｉｖｅ  Ｄｏｃｕｍｅｎｔ  Ｆｉｌｔｅｒｉｎｇ）」、第１０回テキスト検索会議（（Ｔｅｎｔｈ  Ｔｅｘｔ  Ｒｅｔｒｉｅｖａｌ  Ｃｏｎｆｅｒｅｎｃｅ）（ＴＲＥＣ−２００１）、２００２年、５９６−６０５
【非特許文献５】Ａｕｌｔ  Ｔ．、Ｙａｎｇ  Ｙ．ｋＮＮ、「Ｒｏｃｃｈｉｏ及び情報フィルタリングのための評価指標（Ｒｏｃｃｈｉｏ  ａｎｄ  Ｍｅｔｒｉｃｓ  ｆｏｒ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｆｉｌｔｅｒｉｎｇ）」ＴＲＥＣ−１０、第１０回テキスト検索会議（Ｔｅｎｔｈ  Ｔｅｘｔ  Ｒｅｔｒｉｅｖａｌ  Ｃｏｎｆｅｒｅｎｃｅ）（ＴＲＥＣ−２００１）、２００２年、８４−９３
【非特許文献６】Ｃａｎｃｅｄｄａ  Ｎ．ら、「文書フィルタリングのためのカーネル方法（Ｋｅｒｎｅｌ  Ｍｅｔｈｏｄｓ  ｆｏｒ  Ｄｏｃｕｍｅｎｔ  Ｆｉｌｔｅｒｉｎｇ）」、第１１回テキスト検索会議（Ｅｌｅｖｅｎｔｈ  Ｔｅｘｔ  Ｒｅｔｒｉｅｖａｌ  Ｃｏｎｆｅｒｅｎｃｅ）（ＴＲＥＣ−１１）、２００３年
【非特許文献７】Ｓｈａｎａｈａｎ  Ｊ．Ｇ．、Ｒｏｍａ  Ｎ．、「閾値調整によるＳＶＭテキスト分類性能の改善（Ｉｍｐｒｏｖｉｎｇ  ＳＶＭ  Ｔｅｘｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ  Ｐｅｒｆｏｒｍａｎｃｅ  ｔｈｒｏｕｇｈ  Ｔｈｒｅｓｈｏｌｄ  Ａｄｊｕｓｔｍｅｎｔ）」、機械学習に関する欧州会議（Ｅｕｒｏｐｅａｎ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ）（ＥＣＭＬ）２００３年
【発明の開示】
【発明が解決しようとする課題】
【００１７】
文書フィルタリングにおいては、通常、情報ニーズは、情報ニーズを満たすか（正とラベルが付けられる）、または満たさないか（負とラベルが付けられる）どちらかのラベルが付けられた標本文書から学習できる二値文書分類子モデルとして表現できる。サポートベクタマシン（ＳＶＭ）は、情報ニーズの非常に有用な計算モデルとしての機能を果たす。ＳＶＭモデルは、多次元フィーチャ空間内の２つのクラスのオブジェクトを２つの互いに素な部分集合に分割する超平面（または超曲面）として幾何学的に表示できる。本発明の場合には、超平面は、情報ニーズを満たす文書に対応する正の領域と、情報ニーズを満たさない文書に対応する負の領域とに文書を分割する。ラベル付けされた標本からＳＶＭモデルを学習するための指針は、概してユーザ要件及びテキストデータの特異性（テキストフィルタリング用の訓練データは１つのクラスに偏りがちである、つまり正の標本はほとんどなく、負の標本が多くなる傾向がある）を無視しつつ、訓練データから最も遠い超平面を見つけることであるため、学習の結果得られるのは保守的な超平面モデルである。学習されたモデルは高い精度を示すが、リコールは非常に低い傾向にある。
【００１８】
保守的になりすぎず、ユーザの期待するモデルに対処するＳＶＭモデルをどのように作成するのが最良かを決定するための原則に基づいた自動的な方法を有することは極めて望ましい。実証的研究は、これが超平面を並進させることにより達成できることを示した。これを達成する最も簡略な方法の１つが、ユーザモデルを組み込んだ原則に基づいた方法で、学習されたＳＶＭと関連付けられた閾値パラメータをリセットすることである。
【課題を解決するための手段】
【００１９】
本発明により、ＳＶＭモデルの閾値を設定する／リセットするための方法が提供される。閾値を設定するためには、ラベル付き文書の集合、ユーザ効用モデル、及び訓練済ＳＶＭが必要とされる。ここに提案する方法は、ＳＶＭの優れたランク付け能力を相互検証とともに閾値調整手段として利用する。訓練中、ＳＶＭの閾値は、間隔及びベータ−ガンマ閾値化手順の欠くことのできない部分を形成する２つのパラメータ、ベータとガンマによって抽象的に表される。この枠組みの中で、それぞれのラベル付き訓練文書がＳＶＭモデルを使用して分類され、マージン値（分離超平面からの距離）を得る。ラベル付き訓練文書は、次に、マージン値の降順にランク付けされる／並べ替えられる。分類された訓練文書に対する情報ニーズに基づいたユーザの満足度は効用基準により表されてよい。各ラベル付き文書のマージンがＳＶＭモデルにとって考えられる閾値となるであろうと仮定すると、効用は候補閾値ごとに計算できる。各候補閾値で該効用を使用すると、最高の効用点及びゼロ効用点が決定される。ＳＶＭモデルのための閾値は、次に最高効用に関連付けられるマージンとゼロ効用に関連付けられるマージンとの間での補間／補外によって計算される。この間隔に関する補間／補外の程度は、離散閾値調整アルゴリズム及び連続閾値調整アルゴリズムとして既知の、本明細書内で開示される種々の手法を使用して決定される。さらに、ベータ−ガンマ閾値化で使用される間隔を決定するための代替手法が開示される。新規に計算された閾値は、以後、テキストオブジェクトを分類する、またはフィルタリングするためのＳＶＭモデルと共に使用される。代替実施形態では、情報ニーズのＳＶＭベースのコアモデルは、従来の情報検索モデルなどの代替モデルに置換できる。
【発明を実施するための最良の形態】
【００２０】
本発明のこれらの及び他の態様は、同じ参照番号が類似した部分に適用されている添付図面とともに読まれる以下の説明から明らかになる。
【００２１】
文書フィルタリングでは、情報検索システムに対するクエリの場合とは異なり、情報ニーズが直接的に表現されず、むしろ該情報ニーズを満たすまたは満たさない標本文書の集合としてシステムに提示される場合が多い。この集合は、トピックまたはカテゴリまたはクラスを表現すると見なすことができる。システムは情報ニーズモデルを導出するために文書のこの集合を処理しなければならない。通常、情報ニーズは、正の標本と負の標本の両方から学習できる二値文書分類子モデルとして表現できる。
【００２２】
本発明にかかる情報フィルタリング手法は、ラベル付きの標本からの確率的なモデルまたはサポートベクタマシンなどの任意の（統計的または数学的）モデルの構築を伴い、かかる構築プロセスの１つのステップでは、モデル用に閾値を設定する手段として、離散閾値化または連続閾値化と呼ばれる開示されている閾値設定機構のいずれかを使用する。本発明は、構築されたモデルを使用して、文書がカテゴリに属するのか、あるいはクラスに属するのか（または情報ニーズを満たしているのか）を決定することにも関する。
【００２３】
開示されている閾値化手法は、一般的に種々の機械学習手法とともに使用することができ、加えて種々の問題領域に適用できるが、本明細書では、２つの機械学習手法に関連付けて開示されている手法を説明する。つまり、サポートベクタマシン及び従来の情報検索フィルタの手法である。該手法は、テキスト分類及びフィルタリングに関連して情報ニーズをモデル化することに対する特別な応用をもってさらに説明される。
【００２４】
図１−１は、文書の集成１０１または文書のストリーム１３０から関連する情報をフィルタリングするための一般的な方法を図示しており、情報ニーズはサポートベクタマシン１４０によりモデル化される。情報フィルタリングの１つの形式では、システムへの送達とともに、文書は、ストリームまたはバッチでおそらくは連続的に処理される。ここでは情報ニーズは、情報ニーズを表す正の標本と負の標本の両方から学習される二値文書分類子モデル（線形ＳＶＭ）１４０として表される。ＳＶＭモデル２０１は、多次元フィーチャ空間内の２つのクラスのオブジェクトを２つの互いに素な部分集合に分割する超平面２１０（または超曲面）として幾何学的に表示できる。本発明のケースでは、超平面は、情報ニーズを満たす文書に対応する正の領域２４０と情報ニーズを満たさない文書に対応する負の領域２４１とに文書を分割する。フィルタリング決定を下すとき、ＳＶＭシステム１４０は、文書中の情報と、ユーザのニーズまたはトピックを表現する役割を果たす導出された（学習されたとも呼ばれる）情報モデル（ターム重みベクタ１０３及び閾値１０４）に含まれる情報とを比較する。新しい／ラベルが付けられていない文書が超平面の正側に該当する場合、文書は承認され、それ以外の場合、文書は情報を満足していないとして拒絶される。
【００２５】
本発明の１の実施形態に従い、文書は、さらに複雑な構築物を形成するために使用される１つまたは複数の文字列または記号列を含むテキストファイルである。例えば、文字列は、単語、句、文、及び段落を形成してよい。文書中に含まれる構築物は、いかなる特定の言語に関連付けられる構築物または形式にも限定されない。さらに、使用されてよいフィーチャタイプは言語学上の文字列または記号に限定されず、他のフィーチャタイプを含んでよい。他のフィーチャタイプとは、例えば、文書中のフィールドまたはセクションまたは段落または表の数などの構造上のフィーチャ、文書の画像中の「白」領域と「黒」領域との割合またはカラーパターンなどの物理的なフィーチャ、注釈フィーチャ、すなわち、人間による処理もしくは機械処理による注釈が存在するか否か、または文書中の特定のフィールド内に注釈が記録されているか否か、もしくはその価値、潜在的な意味解析及び他のフィーチャの組み合わせなどの変換機能から生じるフィーチャなどの導出されたフィーチャ、及び当業者にとって明らかである他の多くのフィーチャタイプなどである。
【００２６】
文書は前処理１３１され、確実に文書のフィーチャが特定され、モデル１４０が解釈できる形式となる。（文書のデータベースに対する反転インデックスの場合のように）システムによる効率的なアクセスのためにフィーチャを記憶するためまたは効率的な処理のためにフィーチャを並べ替えるもしくはランク付けするためだけではなく、フィーチャを抽出し、表現するための多くの代替技法も当技術分野で既知である。好ましい実施形態では、文書の集成１０１またはストリーム１３０の中の文書は一度に１文書ずつ処理される。文書ごとに、タームベクタを取得するためにフィーチャが抽出される。一代替実施形態では、文書の集成１０１は文書の小さい部分集合に分割でき、また、文書のストリーム１３０を収集もしくはバッファして、文書の部分集合を形成することができる。文書のこのような部分集合は、効率を上げるためにともに処理できる。このような部分集合は、例えば、同じトピックに関する文書であるなど、特定の特徴を共有する集合に属する文書を反映するなど、新しい超文書処理単位を定義するためにも使用できる。当業者は、かかる超文書群の確立のために使用できる多くの代替方法及び技法を容易に理解できる。さらに、引用により本文に組み込まれる米国特許第５，９０７，８４０号、第５，９９９，９２５号、第６，１１５，７０６号、第６，２０５，４４３号及び第６，３７７，９４７号の方法を使用して、あらゆる文書をサブ文書に解析でき、文書のスコアリングのためフィルタが文書のサブ文書の１つまたは複数のフィーチャを使用できるよう、文書の各サブ文書を処理できる。
【００２７】
本発明では、処理を目的とした文書は、ソース文書としてシステムが利用できる文字通りの文書と定義でき、例えば、任意のサイズのサブ文書、単一エンティティ（文書）として処理される単一のソース文書または多数のソース文書から導出されたサブ文書の集合、単一のエンティティ（文書）として処理されサブ文書が混在してよい文書群の集合、および上記の任意の組み合わせである。
【００２８】
好ましい実施形態では、フィルタリングシステムは、ベクタ空間表現を使用して文書またはサポートベクタマシン１４０を計算機的に特徴付ける。ベクタ空間モデルの生成に関係する追加の背景技術は、引用により本文に組み込まれる米国特許米国特許第５，６１９，７０９号に開示されている。
【００２９】
ベクタ−空間表現の元で、文書は、単語、名詞句、及び他の言語学的に導出されるフィーチャ（例えば、解析木フィーチャ）などのフィーチャのベクタとして概念的に表示できる。通常、フィーチャ抽出モジュール１３１は、文書をフィーチャのベクタ、Ｄ＝＜ｆｅａｔｕｒｅ1／ｆ1．．．，ｆｅａｔｕｒｅn／ｆn＞に変形させる。ｆiは各々フィーチャ、ｆｅａｔｕｒｅiの（正規化された）統計学上の重要性を示す。文書Ｄｏｃに関連付けられる各重みｆiを計算する１つの共通した方法は、以下のとおりである。
【数１】
2005316996.tif 000003
【００３０】
上式中、ｆｒｅｑ（ｆi,Ｄｏｃ）は、文書Ｄｏｃ中のフィーチャｆiの頻度を表し、ｉｄｆ（ｆi）は処理済みのすべての使用可能な単位（例えば文書）全体でのｆiの分散カウントの逆数の対数を表す。ｉｄｆ（ｆi）係数はｉ番目のフィーチャの累乗を区別するコンテンツに相当する。つまり、集合体の中でめったに現れないフィーチャは高いｉｄｆ値を有する。ｉｄｆ（ｆi）係数は以下のように計算される。
【数２】
2005316996.tif 000004
上式中、Ｎは集合の中の文書の数であり、ｎfiはｉ番目のフィーチャｆiが発生する文書の数である。
【００３１】
通常、情報フィルタリングのベクタ空間モデルでは、正規化された文書ベクタ、Ｄ＝＜ｎｆ1，．．．，ｎｆn＞が使用され、各ｎｆiは以下のように取得される。
【数３】
2005316996.tif 000005
【００３２】
このベクタ空間表現はＴＦ＿ＩＤＦ表現として知られている。同様に、ベクタ−空間表現の下では、線形ＳＶＭ情報ニーズが、単語、名詞句、及び他の言語学的に導出されたフィーチャ（例えば解析木フィーチャ）などのフィーチャのベクタとして概念的に表示できる。ＳＶＭ情報ニーズモデルと関連付けられる重みは、下記に概略する学習アルゴリズムを使用して導出される。
【００３３】
情報ニーズは、それらが人間中心的（情報フィルタリング）であろうと機械中心的（テキスト分類）であろうと、モデルとして知られる種々の表現を使用して計算機的に表現できる。情報ニーズをモデル化するための好ましい実施形態はサポートベクタマシン（ＳＶＭ）である。概して、ＳＶＭは当技術分野でよく知られている。サポートベクタマシン２０１は、多次元フィーチャ空間内の２つのクラスのオブジェクトを２つの互いに素な部分集合に分割する超平面２１０（または超曲面）として幾何学的に表示できる。この分離超平面２１０は、その最も簡略な形式で、重みベクタ表現を使用して表現できる。重みベクタ表現は、１組のパラメータ＜Ｗ，ｂ＞として数学的にＳＶＭを表現し、ここではＷ１０３は重みベクタを示しｂ１０４（２３０）は閾値を表す。重みベクタＷ（２３０）は、形式＜ｆi，ｗi＞のタプルのリストから構成され、ここではｆiはフィーチャを示し、ｗiはフィーチャｆiと関連付けられる重みを示す。これは重みベクタＷのベクタ空間表現に相当する。ここでは、重み値ｗi及び閾値ｂは標準的なＳＶＭ学習アルゴリズムを使用して標本から学習される。この重みベクタ表現はＳＶＭの原始（ｐｒｉｍａｌ）表現として知られている。図２−１は、ＳＶＭモデル、つまり（正のクラスに属し、情報ニーズを満たす文書に対応する）正の標本の集合と（負のクラス、つまり情報ニーズを満たさない文書である）負の標本の集合とを分離する超平面２１０を幾何学的に示す。図２−１の超平面モデルは、仮想上の二次元テキスト問題に相当し、ここではＨ２１０は正のクラス標本（「＋」によって示される。２１１は正の標本を示す）と負のクラス標本（「−」によって示される。２１２は負の標本を示す）とを分離する超平面である。ｘ軸２１６は、以下に定められるようにフィーチャＷｏｒｄ1のＴＦ−ＩＤＦ値に相当する。ｙ軸２１５はフィーチャＷｏｒｄ2について同様に定義できる。数学的には、超平面２１０は以下のように表現できる。
【数４】
2005316996.tif 000006
【００３４】
上式中、ｗiはＳＶＭモデル内のフィーチャｆｅａｔｕｒｅiの重みに相当し、ｘiは分類される文書の中のｆｅａｔｕｒｅiの値に相当し、ｂはスコアリング（ｓｃｏｒｉｎｇ）閾値であり、ｎは入力変数またはフィーチャの数を表現する。テキストの場合には、文書を表現するために使用される単語（または句等）の数と見ることができる。より簡潔には、ベクタフォーマットで＜Ｗ，Ｘ＞＋ｂ＝０と書くことができ、該式中＜．＞は上に定義したようにドット積または内積を示し、Ｗは重みベクタであり、分離超平面Ｈ２１０に対する法線ベクタ２３０に相当し、Ｘは入力ベクタまたは文書であり、ｂは超平面Ｈ２１０から原点２２０までの垂直距離を示す。パラメータｂは、超平面のバイアスタームまたは閾値タームとしても知られることがある。提示を容易にするために、ＳＶＭの説明は線形ＳＶＭに限定される。線形ＳＶＭは通常タプル＜Ｗ，ｂ＞を使用して表現され、ここではＷ及びｂは上に定義したとおりである。
【００３５】
分離超平面（Ｗ，ｂ）とともに線形サポートベクタマシンを使用する、ラベルが付けられていない文書Ｘのための分類規則は以下のとおりである。
【数５】
2005316996.tif 000007
ここではドット積演算＜．＞は上に定義されるとおりである。代わりに、正規化したドット積を使用することができ、以下のように定義される。
【数６】
2005316996.tif 000008
【００３６】
上式は、以下のようにＳｉｇｎ（．）関数を使用してさらに簡潔に書くことができる。
【数７】
2005316996.tif 000009
【００３７】
ＳＶＭ分類技法は、以下のＳＶＭモデル及び文書のサンプル集合を使用して図示できる。この例では、各文書は犬、猫等の単一の単語フィーチャによって表現されると仮定する。
【表１】
2005316996.tif 000010
【００３８】
この表では、用語欄には２つの文書Ｄ1とＤ2に記載されるすべての用語の一意の和集合が一覧表示される。Ｄ1及びＤ2の下に一覧表示される値は、それの用語が文書の中に表示される頻度を指す。上表の場合では各フィーチャのｉｄｆは１に設定される。Ｍの下に一覧表示される値は、用語が情報ニーズに対応する学習済ＳＶＭモデルに表示されるときの用語の重みを指す。ＳＶＭモデルＭに関する文書Ｄ1の分類は以下のように計算される。
【数８】
2005316996.tif 000011
【００３９】
文書Ｄ1の出力マージンスコアはゼロ未満であるため、その分類は負である（つまり情報ニーズを満たしていない）。同様に、文書Ｄ2についてのＳＶＭモデルＭの出力マージンスコアはＳ（Ｍ，Ｄ2）＝０．３２として計算される。この場合、文書Ｄ2は、情報ニーズを満たすことを示す正として分類される。
【００４０】
ＳＶＭは、通常、ラベル付きの標本からの学習のプロセスを通して獲得される。テキストフィルタリングシナリオでは、ラベルつきの標本は情報ニーズを表す文書に相当する。一般的には、これらの標本は正の標本または負の標本としてラベルが付けられる。数学的には、標本はタプル＜Ｘ，ｙ＞として表現され、Ｘは（前述されたように）フィーチャベクタであり、ｙはＸの分類を示す。ｙは、＋１（つまり、文書Ｘが、情報ニーズを満たす文書に対応する正のクラスに属する）または−１のどちらかの値をとりうる。図２−１はＳＶＭ学習問題の仮想上の二次元例を描いている。ここでは、正のクラス標本が「＋」で描かれ（２１１は標本の正の文書を示し）、負のクラス標本が「−」で描かれている（２１２は負の標本を示す）。訓練標本はＳＶＭ学習アルゴリズムに提示される。学習の結果、超平面＜Ｗ，ｂ＞２１０が得られる。超平面２１０から最も近い正（例えば２１７）の標本または負の標本までの距離はＳＶＭのマージン２１６として知られている。
【００４１】
線形ＳＶＭを学習することは、データを最大のマージンで分離する超平面（つまり重み値及びバイアス値）をサーチすることと簡単に特徴付けることができる。その結果、直線状に分離可能なデータについて学習することは、以下の最適化問題として表すことができる。
【数９】
2005316996.tif 000012
【数１０】
2005316996.tif 000013
【００４２】
上式中、Ｘiはラベルｙi付きの訓練標本であり、｜｜Ｗ｜｜は重みベクタのユークリッド長である（つまり、｜｜Ｗ｜｜＝√（（ｗ1）2＋．．（ｗn）2である）。Ｌは訓練標本の数を示す。学習後、超平面２１０に最も近い標本はサポートベクタ２１７、２１８（正のクラスサポートベクタ）、２１９（負のクラスサポートベクタ）に相当する。学習されたＳＶＭに相当する超平面は、以下に示すようにサポートベクタに関して同等に特徴付けることができる。
【数１１】
2005316996.tif 000014
【００４３】
上式中、｜ＳＶ｜はサポートベクタの数を示し、ｉは該サポートベクタ上のインデックスであり、ａiはサポートベクタＸiに関連付けられるラグランジュ乗数を示す（ａiは該分離超平面に対するサポートベクタＸiの重要性の重みとして直感的に表現できる）。これは多くの場合ＳＶＭの二重空間表現と呼ばれるのに対し、重みベクタ表現＜Ｗ，ｂ＞は原始（ｐｒｉｍａｌ）表現と呼ばれる。
【００４４】
この二重表現を使用すると、ＳＶＭについての二重学習問題は、（原始問題と同じ解決策を生じさせる）この二重フォーマットでこの最大マージン超平面（つまり、データから最も遠い超平面）を決定するために以下のように特徴付けることができる。
【数１２】
2005316996.tif 000015
【数１３】
2005316996.tif 000016
【００４５】
非線形分離性（つまり、超平面は２つのクラスを分割するには不十分である）の場合、２つの代替構成が提案されてきた。一方はスラック変数に基づき、他方は非線形カーネルを使用することに基づく。スラック変数またはＳＶＭ学習のソフト構成では、支えている超平面（Ｈ+1  ２１４及びＨ-1  ２１３を参照）の誤った側に標本が振り分けられることが許される、つまり偽の正または偽の負が許されるが、これらの標本にはペナルティが課せられる。
【００４６】
より正式には、スラック変数、ξi（「ｘｉ」と発音される）は訓練標本（Ｘi，ｙi）に関連付けられる変数であり、その値は以下に示すように超平面（Ｗ，ｂ）及び（正の固定値を有する）ターゲットマージンγに関して計算される。
【数１４】
2005316996.tif 000017
【００４７】
直感的に、この量は、訓練データポイントがどれほど多く超平面（Ｗ，ｂ）からマージンγを有することができないのかを測定する。エラーに対処するために、（上記に概略された）最大マージン超平面二次計画法（ＱＰ）問題に小さな変更を加える必要がある。非負スラックまたはエラー変数ξiが各制約に加えられ、目的関数に加重されたペナルティタームとしても追加され、（原始形式の）以下のソフトマージンＳＶＭ二次計画法問題が得られる。
【数１５】
2005316996.tif 000018
【数１６】
2005316996.tif 000019
【００４８】
上式の係数Ｃは、訓練エラーとモデルの複雑さのトレードオフを可能にするパラメータである。Ｃの値が小さいと、訓練エラーの数が増加するが、Ｃの値が大きいとハードＳＶＭの挙動に類似した挙動となる。この最適化問題のラグランジュ二重は以下のとおりである。
【数１７】
2005316996.tif 000020
【数１８】
2005316996.tif 000021
【００４９】
異なるまたは非対称のコストは偽の負または偽の正に関連付けることができる。
【００５０】
数学的なプログラミング文献から既知であるように、及び実際問題として、ＳＶＭ学習は、二重空間表現においてより効率的に実現される。ＳＶＭ学習のための好ましい実施形態は、引用により本文に組み込まれる米国特許第６，３２７，５８１号に開示されている二重空間ＳＭＯ（連続最小最適化）アルゴリズムである。本明細書に説明されるアルゴリズムは以下のように修正された。つまり、２つの閾値パラメータｂlow及びｂupを停止基準に組み込む。書き直されたＫａｒｕｓｈ−Ｋｕｈｎ−Ｔｕｃｋｅｒ違反条件とともにａをベースにした分割（ラグランジュベース）を使用する（（つまりＳＭＯにより利用される無作為選択技法とは異なり）更新するための標本のアルファのより効率的な選択につながる）。その結果、アルゴリズムを学習するためのＳＭＯＫ１及びＳＭＯＫ２という２つの好ましい実施形態が得られる。これらの実施形態もソフトＳＶＭ、非対称ＳＶＭ、非線形ＳＶＭ（現在対処されている）及びこれらの組み合わせを学習するための機構を含む。
【００５１】
ＳＶＭが、多項式カーネルまたは半径方向ベースのカーネルなどの非線形カーネル（またはマッピング関数）を使用して非線形分離を提供するために拡張できることは当業者により理解される。
【００５２】
情報ニーズをモデル化するためのＳＭＶの性能は、精度の点では他の手法（例えば、Ｒｏｃｃｈｉｏ、ｎａｉｖｅ  Ｂａｙｅｓ）より優位であるが、リコールの点では優位性がない。
【００５３】
理論的には、汎化エラー（見えないデータでのモデルのエラー）をマージンの関数、すなわち、最も近いデータポイントから分離決定面（超平面）までの距離の関数として上限付けることができることを考慮すると、ＳＶＭ学習アルゴリズムはマージン最大化モデルの検出に集中する。モデル選択に対するこの手法は完全にデータ集中型であり、密度の高いデータ問題において極めて高い性能を提供する。しかしながら、情報ニーズのモデル化のように、データがまばらで、クラスが偏在し完全に表現されていない領域では、この学習手法は訓練データが多いクラスの過剰適合につながることがある。モデル化情報ニーズのケースでは、これによって改修（リコール）が大きく減少する。テキスト分類文脈における精度に悪影響を及ぼさずにＳＶＭのリコールを改善するためにいくつもの試みがなされてきた。これらは前述された。すべての手法は、分離超平面の位置または向き（あるいは両方）を調整する緩和方法を使用する。
【００５４】
ＳＶＭ学習により（例示は線形ＳＶＭのみだが、非線形ＳＶＭに拡張可）、加重タームのリストまたはベクタ及びマージンに対して最適の閾値ｂが得られる。既に含意したように、これによって、リコールよりも精度を高める非常に保守的な挙動につながる場合がある。この保守的な性質を克服するために、後に詳述される超平面調整ステップが実行される。このステップはＳＶＭ超平面表現の閾値成分を調整することに集中する。
【００５５】
本発明の好ましい実施形態は、閾値を調整することにより超平面の位置を調整するために、離散閾値化と呼ばれる超平面調整方法を使用する。これが現在開示されている。この方法の結果、分離超平面２１０は、支持する超平面２１４または２１３の一方に向かって平行に並進する。この緩和プロセスの仮想上の例では、超平面２１０が−１という距離だけ並進する。この結果、この場合に得られる新しい分離超平面は、支持する超平面２１３と一致する。要するに、この結果、ＳＶＭモデルの閾値またはバイアスタームが（この例では−１だけ）リセットされる。閾値調整として知られるこのステップは、ＳＶＭモデルが標本データから学習された後に実行される。離散閾値化方法は、ＳＶＭモデルのランク付け能力を利用し、効用モデル及びベータ−ガンマ閾値化方法に依存している。効用モデルとベータ−ガンマ閾値化方法の両方が最初に説明される。
【００５６】
従来のテキスト分類及びフィルタリングシステムは、各文書が指定されたクラスに属しているかどうかに関して、他のすべての文書とは無関係に文書ごとに決定を下すという点で、性質が二値的である。大部分のケースでは、決定は文書が到達するとすぐに必要とされるため、ランク付けされたリストは可能ではなく、各決定は独立して行われる。このようなシステムでは、ユーザの満足度は効用基準として表されてよく、結果的に、分類システムの目標はこの基準を最適化することである。線形効用基準はこれを達成する効果的且つ直感的な手段を提供する。以下では、説明のため、特定の情報−理論基準に基づいた特定のタイプの効用関数を説明するが、本発明の実施形態は任意の１つのこのような特定の効用基準の使用に依存しない。特に、メモリに記憶されるときのフィルタ（モデル）のサイズ、ステップ数という点でのフィルタ（モデル）の複雑さ、またはデータ処理に要する処理時間等、及びプロセスの他のこのような実利的な基準またはこのような基準の組み合わせなどを考慮した、他の効用基準が適切な場合があることを認識する。本発明の好ましい実施形態は、いくつかの可能性のある線形効用機能のひとつを利用する。これらの効用関数は以下の形を取る。
【数１９】
2005316996.tif 000022
上式中、Ｒ+はフィルタリングされた（送達された）集合中の正の（「関連する」）文書の数であり、Ｎ+は送達された集合中の負の（「関連していない」）文書の数であり、Ｒ-は見失われた（データベースまたはストリームに関して送達されていない）正の文書の数であり、Ｎ-は（正しく）送達されていない負の文書の数であり、ａ、ｂ、ｃ及びｄはパラメータである。Ｔ１０Ｕはこのような基準の１つであり、以下のように定義される。つまり、Ｔ１０Ｕ＝２Ｒ+−Ｎ+である。Ｔ１０Ｕは、情報検索設定でユーザをモデル化する手段を提供し、それにより、モデルＭにより承認された実際の正のラベルの付いた各文書、つまりＲ+として示される各真−正の文書が効用２点を受け取るが、モデルにより承認される各負の文書、つまりＮ+として示される偽−正文書はマイナス１という効用を受け取る。
【００５７】
経験的結果は、効用の大部分が非対称である線形効用のための最適化は、リコール、精度及びＦｂｅｔａなどの従来の情報検索基準の性能の向上につながることを示す。閾値化は効果に大きく影響を及ぼし、すべての効用基準を満たす閾値は一つもない。したがって、効用という概念を学習に組み込むことは重大である。効用モデルをＳＶＭに組み込むのは、（非対称コストにより）埋め込まれた学習方法を通して発見的に、及びここに開示されている手法などの閾値化方法を通してより直接的に達成することができる。
【００５８】
ベータ−ガンマ閾値化アルゴリズムは、フィルタモデルに閾値を設定するために従来の情報検索フィルタを使用する適応フィルタリング及びバッチフィルタリングに関連して適用できる。閾値設定は、通常、フィルタリングについてユーザが所望する結果または好みのなんらかのモデルまたは基準に対する参照を必要とする。このような基準の１つが上に略述されたような線形効用基準である。当業者に既知の多くのこのような関数がある。
【００５９】
文書のラベルが付けられたデータセット及び例えばＳＶＭなどの情報ニーズモデルを考慮すると、該情報ニーズモデルはマージン（類似性）スコアに基づいて該文書をランク付けするために使用される。マージン（距離ベースのスコア）は、該モデルに基づいて各文書を評価することにより得られる。情報ニーズの好ましい実施形態はＳＶＭ２００である。該ＳＶＭ２００を使用すると、マージンスコアは標本ごとに計算される。マージンは、標本から分離超平面２１０までの垂直距離（ユークリッド距離）に相当する。例えば、文書２３０ａは、分離超平面２１０までの３（２３１ａ）という垂直距離である。図２−２では、文書２５０ａの集合はその対応するマージンスコア（または略してマージン）２５２ａ及びそれらの対応する分類ラベル２５３ａとともに一覧表示され、ここでは「＋」エントリは対応する文書が情報ニーズを満たしたことを示し、「−」エントリは、対応する文書が情報ニーズを満たしていないことを示す。文書２３０ａは、２７０ａに図像的に示され、その対応するマージン２５２ａはマージン軸２７１ａを使用して容易に視覚化できる。文書２３０ａはマージン２５２ａの降順でランク付けされる。累積効用は、ＵｔｉｌｉｔｙRank＝２Ｒ+−Ｎ+のような線形効用関数を使用してランクごとに計算することができ、式中、Ｒ+は、現在のランクＲａｎｋに至りこれを含む正のラベル「＋」の付いた文書の数を表現し、Ｎ+は現在のランクＲａｎｋに至りこれを含む負のラベル「−」の付いた文書の数を表現する。２５１ａは対応するランクでの累積効用を提示するが、２５４ａは各ランクでの効用の計算を提示する。マージン２５２ａは、（ｘ軸、つまり水平軸３１１に相当する）ランク２３０ａの関数として曲線形にプロットでき、それによってデータマージン曲線３２１が得られる。同様に、累積効用値２５４ａは、（ｘ軸つまり水平軸３１１に相当する）ランク２３０ａの関数として曲線形にプロットでき、それによってデータ効用曲線３２０が得られる。
【００６０】
以下、効用曲線３２０上の値が最大３３０であるランク付けでの点を注記できる。これがランク値に相当する。効用が３３０であるランクをｉOpt３５２で示す。また、累積効用曲線３２０が、ｉOpt３５２で発生する文書より下のランクで発生する文書について、最初に０（ゼロ）以下に達する、ランク付け３３２内の点も注記できる。これもランクに相当する。効用３３２の付いたランクをｉZero３３４と示す。ランクｉOpt３５２及びｉZero３３４を使用すると、マージン曲線３２１上の２つの対応する点を特定できる。これらの対応するマージンが最適マージンθOpt３３３（３５０）及びゼロマージンθZero３３４（３５１）として知られている。実証的研究は、最適マージン（つまり、未処理のサンプルまたは提供されたサンプル上で最適効用を生じさせる閾値）が、一般的にはθOpt３３３（３５０）、最適効用マージンとθZero３３４（３５１）、ゼロ効用マージンとの間隔にくることを示す。実際の最適マージン（閾値）は、これらの間隔境界点の補間（または補外）によって決定できる。
【００６１】
最適効用マージンθOpt３３３（３５０）及びゼロ効用マージンθZero３３４（３５１）を使用すると、以下に示すように、閾値化データセット上で実証的な最適効用マージンと実証的なゼロ効用マージン間の補間を行うことで、新しい閾値が計算される
【数２０】
2005316996.tif 000023
【数２１】
2005316996.tif 000024
式中、
θOpt３３３（３５０）は、ランク３５２でのマージン曲線上のマージンであり、効用曲線３２０上の最高効用点３３０に相当し、
θZero３３４（３５１）は、ランク３３４でのマージン曲線上のマージンであり、効用曲線３２０上のゼロ効用点３３２に相当し、
ｐは閾値化データセットの中の正の（つまり関連した）文書の数であり、
α、β、γはパラメータである。
【００６２】
過去には、補間の程度（つまり、β、γパラメータの値）は、他の問題領域での経験を使用して経験的に求められた。以下では、補間（または補外）の程度を自動的に計算する多様な手段を開示する。
【００６３】
閾値を設定するこの方法は、以下ベータ−ガンマ閾値化アルゴリズム（または「ベータ−ガンマ」法）と呼ばれている。アルゴリズムのパラメータを図３−２に概略的に示す。このアルゴリズム及びその背景技術は、引用により本文に組み込まれる米国特許第６，４３０，５５９号、第６，４６３，４３４号、第６，５３５，８７６号及び第６，５８７，８５０号にさらに詳細に説明されている。
【００６４】
擬似符号記述形式で以下に示されるベータ−ガンマプロシージャＳｅｔＴｈｒｅｓｈｏｌｄＵｓｉｎｇＢｅｔａＧａｍｍａは、以下を入力として必要とする。つまり、情報ニーズまたはカテゴリラベルＣ、Ｃの正の標本及び負の標本の両方から構成される文書のラベル付きデータセットＴ、カテゴリＣをモデル化する（例えば情報ニーズモデルなどの）学習されたモデルＭ、β及びγ、つまり閾値調整パラメータ、効用基準ＵｔｉｌｉｔｙＭｅａｓｕｒｅ、及び閾値化データセットＴ内の正の（つまり関連した）文書の数ｐである。
【００６５】
ＳｅｔＴｈｒｅｓｈｏｌｄＵｓｉｎｇＢｅｔａＧａｍｍａ（Ｃ，Ｔ，Ｍ，β，ＵｔｉｌｉｔｙＭｅａｓｕｒｅ，ｐ）
１．ランク付け関数としてモデルＭを使用して閾値化データセットＴをランク付けし、それによりタプル＜Ｄｏｃｕｍｅｎｔi，Ｓｃｏｒｅi＞から構成される、つまり文書スコア、Ｓｃｏｒｅiの降順でランク付けされた文書リストＲを生じさせる。
２．ランクの関数として対応するスコア曲線を作成する。
３．ランクの関数として、Ｒの累積効用曲線を作成する。つまりランク付けされたリストＲの中の文書ごとに、効用基準ＵｔｉｌｉｔｙＭｅａｓｕｒｅを使用して累積効用を計算する。
４．累積曲線上の最大効用点のランク、及び該最大効用点に続く第１のゼロ効用点のランクを決定する。これらをそれぞれｉOptとｉZeroとして示す。
５．それぞれランクｉOpt及びｉZeroに対応するスコア曲線上のスコアを、変数θOpt及びθZeroに割り当てる。β＝無効である場合、終了し、変数θOpt及びθZeroを戻す。
６．以下のように計算される閾値、□を戻す。
【数２２】
2005316996.tif 000025
【数２３】
2005316996.tif 000026
【００６６】
ベータ−ガンマ閾値化アルゴリズムの前記実施形態では、（モデルの閾値を計算するために使用される）間隔境界値、最適効用マージンθOpt３３３（３５０）及びゼロ効用マージンθZero３３４（３５１）は、提供されたデータセットから直接的に導出された効用曲線及びマージン曲線を使用して決定された。これらの曲線に基づいた計算は、誤ったデータ値（平滑ではない）に対して弱い場合があり、したがって保守的すぎる、あるいは自由すぎるかどちらかである閾値につながる。
【００６７】
ベータ−ガンマ閾値化アルゴリズムの代替実施形態では、効用曲線及びマージン曲線の代替曲線表現は間隔境界値を導出するために使用できる。これらの代替曲線表現は、円滑化アルゴリズムまたは適合アルゴリズムによって達成できる。結果として生じる円滑化されたあるいは適合された曲線はデータの局所的な特異性に対してあまり弱くない。ある代替実施形態では、効用データ曲線は、適合が好ましいと判断されると適合された効用曲線で置換される。適合された効用曲線は、種々の周知の技法のどれかを使用して統計または機械学習から計算できる。例えば、多項式曲線は、以下の式を使用することによりデータ効用曲線２５１ａ上の点を通して最小二乗適合を使用して計算できる。
【数２４】
2005316996.tif 000027
式中、ｂ及びｃ1．．．ｃnは曲線適合アルゴリズムにより決定される定数であり、ｎは多項式の次数であり、ｒａｎｋは変数である。ｎの値がさらに高くなると、元のデータ曲線にさらに密接に近似する曲線が得られる。標本のデータセット２６０ａについてのデータ効用曲線３２０（ｂ）は、次数３の多項式曲線３３０ｂにより近似できる。対応するデータ曲線の式は３４０ｂに示され、各データポイントと曲線の間の誤差の二乗の合計は３４１ｂに示される。この誤差が大きすぎる場合には、元のデータ曲線を使用できる、あるいは代わりにより高次の多項式を適合し、使用できる。以後、ベータ−ガンマプロシージャの間隔境界値θOpt３３３（３５０）及びθZero３３４（３５１）の計算は前記に提示されるとおりであり、データ効用曲線は適合された効用曲線で置換される。元のデータ効用曲線を使用して計算されるθOpt３５０ｂ（３５０）が、どの程度、適合された効用曲線を使用して計算されるθOpt３５１ｂと異なるのかに注目する。この例では、θZero３５２ｂはいずれの場合も同じ値に一致する。
【００６８】
代替実施形態では、ベータ−ガンマ閾値化アルゴリズムのデータに基づくマージンスコア曲線３２１ｃは、適合された曲線３６０ｃで置換される。やはり、適合曲線はデータの局所的な特異性に対してあまり弱くない。種々の曲線のいずれでも使用できる。以後、ベータ−ガンマプロシージャでの間隔境界値θOpt３３３（３５０）、及びゼロマージン、θZero３３４（３５１）の計算は前記に提示されたとおりであり、スコア曲線は適合されたスコア曲線で置換される。図３−４では、マージン曲線３２０ｃ（３２０）は三次の多項式曲線３６０ｃで適合された。この曲線のための式は３６１ｃであり、二乗誤差の合計は３６２ｃである。
【００６９】
代替実施形態では、データ効用曲線とマージン効用曲線の両方とも対応する適合曲線で置換され、新しい閾値の計算が、適合されたマージン曲線及び効用曲線とともに上に概略されたベータ−ガンマ閾値化アルゴリズムを使用して実行される。これは、図３−５に図像的に示されている。
【００７０】
当業者は、（適合方法または円滑化方法を使用して）代替曲線を導出するために使用する可能性がある多くの代替方法及び技法を容易に理解できる。
【００７１】
好ましい実施形態では、閾値を調整しなければならない量を決定するために、値β、γは、ｎフォールド相互検証に基づいたプロシージャを使用して自動的に決定される。この実施形態は離散閾値調整アルゴリズムとして知られている。
【００７２】
この手法のおもな新しい点は、ベータ−ガンマアルゴリズムのパラメータを経験的に最適化するために相互検証を用いるという点である。ユーザは、β及びγの考えられる値を提供し、そこから訓練データセットに対して相互フォールド検証を使用して最適な組み合わせを選択する。
【００７３】
離散閾値調整アルゴリズムは、以下のステップから構成され、入力として、カテゴリラベル、Ｃ（例えば＋１）、Ｃの正の標本及び負の標本の両方から構成される文書のラベル付きデータセット、Ｔ（例えば、Ｔは部分集合または完全な訓練データセットであろう）、カテゴリＣをモデル化する学習されたモデルＭ、閾値調整パラメータβ、ユーザの期待をモデル化する効用基準ＵｔｉｌｉｔｙＭｅａｓｕｒｅ、考えられるベータ値の集合βｓ（βの有効な値は正の実数または負の実数である）、考えられるガンマ値の集合γｓ、及びパラメータ選択で使用されるフォールドｎを使用する。
【００７４】
ＤｉｓｃｒｅｔｅＴｈｒｅｓｈｏｌｄ（Ｃ，Ｔ，Ｍ，ＵｔｉｌｉｔｙＭｅａｓｕｒｅ，βｓ，γｓ，ｎ）
１．正の文書と負の文書の両方ともがそれぞれのフォールドまたは部分集合内に存在することを保証するデータのｎ個の重複しない部分集合にデータを分割する。具体的には、ＰがＴ内の正の文書の数を示す場合、各フォールドはほぼＰ／ｎ個の正の文書を強制的に持たされる。
２．βｓ及びγｓの中のβ値及びγ値の各組み合わせについて、Ｆｏｒｅａｃｈ。
３．Ｕｔｉｌｉｔｙβγ＝０
４．フォールド／部分集合ｎにつき、Ｆｏｒｅａｃｈを実行する。
・Ｔnをｎ−１フォールドに設定する（つまり部分集合ｎを除くすべての部分集合）。
・θ＝ＳｅｔＴｈｒｅｓｈｏｌｄＵｓｉｎｇＢｅｔａＧａｍｍａ（Ｃ，Ｔn，Ｍ，β，γ，ＵｔｉｌｉｔｙＭｅａｓｕｒｅ，ＰTn）を設定する。
・Ｕｔｉｌｉｔｙβγn、、フォールドｎ上でＭの効用及び閾値θを計算する。
・Ｕｔｉｌｉｔｙβγ＝Ｕｔｉｌｉｔｙβγ＋Ｕｔｉｌｉｔｙβγn
５．Ｆｏｒｅａｃｈを終了する。
６．以下のように平均効用を計算する。Ｕｔｉｌｉｔｙβγ＝Ｕｔｉｌｉｔｙβγ／ｎ
７．Ｆｏｒｅａｃｈを終了する。
８．以下のように、最高平均効用Ｕｔｉｌｉｔｙβγを有するβ及びγの組み合わせを使用して最適閾値θnewを計算する。ＳｅｔＳＶＭＴｈｒｅｓｈｏｌｄＵｓｉｎｇＢｅｔａＧａｍｍａ（Ｃ，Ｔ，Ｍ，β，γ，ＵｔｉｌｉｔｙＭｅａｓｕｒｅ，ＰT）
９．θnewを戻す。
【００７５】
上のアルゴリズムでは、ＰXはデータベースＸ内の正の標本の数を示す。戻される値またはＤｉｓｃｒｅｔｅＴｈｒｅｓｈｏｌｄ（．）の出力は、以下のように文書分類に使用される。
【数２５】
2005316996.tif 000028
【００７６】
非線形ＳＶＭ用の修正された分類規則は以下のとおりである。
【数２６】
2005316996.tif 000029
式中、Ｋ（．）はドット積などの相似関数を示す。
【００７７】
図４−１は、離散閾値化アルゴリズムの概略図であり、フォールドは４に設定される（つまり、訓練データセット４１０は、４つの重複しない部分集合に分割される）。この例では、ベータ及びガンマ（β、γ）の多様な値４２０を検討した後、それぞれ０．１、０．１２５の最終値が最適と判断される。
【００７８】
代替実施形態では、β、γの値は改善及び相互検証の組み合わせに基づいたプロシージャを使用して自動的に決定される。この実施形態は、連続閾値調整プロシージャとして知られている。
【００７９】
この手法のおもな新たな点とは、ベータ−ガンマアルゴリズムのパラメータを経験的に最適化するために改善及び相互検証の組み合わせを適用し、それによりアプローチパラメータを未定のままにする（つまり、ユーザは閾値化パラメータを指定する必要がない）点である。ベータパラメータは、訓練データがｎ個のフォールド／部分集合に分割されたと仮定すると、以下のように決定される。フォールドごとに、以下のステップを使用してベータ値βnを決定する。ｎ−１の残りのフォールドから（上に概略された）ベータ−ガンマアルゴリズムを使用してθMax及びθZeroを決定する。他の提出されたフォールドｎでは、最適な効用点を決定し、単純にθMaxとθZeroとの間隔に基づいて提出された最適効用に対応するスコアを導くβnの値を計算する。各フォールドにつきβをベータ値の平均に設定する。このベータ値は閾値緩和にとって重大なパラメータであり、他方、γはトピック及び集成全体でより安定しており発見的に設定される。γの有用な設定値は０．０２である。γは、ベータステップ後に行われるか、または並列して実行される相互検証ステップを通して決定できる。
【００８０】
連続閾値調整プロシージャは、以下のステップから構成され、以下を入力として使用する。つまり、カテゴリラベルＣ、Ｃの正の標本と負の標本の両方から構成される文書のラベル付きデータセットＴ、カテゴリＣをモデル化する学習されたモデルＭ、Ｔ１０Ｕなどのユーザをモデル化する効用基準ＵｔｉｌｉｔｙＭｅａｓｕｒｅ、及びパラメータ選択で使用されるフォールドｎである。
【００８１】
ＣｏｎｔｉｎｕｏｕｓＴｈｒｅｓｈｏｌｄ（Ｃ，Ｔ，Ｍ，ＵｔｉｌｉｔｙＭｅａｓｕｒｅ，ｎ）
１．正の文書と負の文書の両方ともがそれぞれのフォールドまたは部分集合内に存在することを保証するデータのｎ個の重複しない部分集合にデータＴを分割する。具体的には、ＰがＴ内の正の文書の数を示す場合、各フォールドはほぼＰ／ｎ個の正の文書を強制的に持たされる。
２． βsum＝０
３．フォールド／部分集合ｎにつきＦｏｒｅａｃｈ。
１．１  Ｔnを残りのｎ−１フォールドに設定する（つまりフォールドｎを除くすべてのフォールド）。
１．２  ＳｅｔＴｈｒｅｓｈｏｌｄＵｓｉｎｇＢｅｔａＧａｍｍａ（Ｃ，Ｔn，Ｍ，無効、無効、ＵｔｉｌｉｔｙＭｅａｓｕｒｅ，ＰTn）を呼び出し、変数θOpt及びθZeroにＳｅｔＴｈｒｅｓｈｏｌｄＵｓｉｎｇＢｅｔａＧａｍｍａルーチンのステップ５の対応する値を割り当てる。
１．３  モデルＭを使用して提供されたフォールドｎで文書をランク付けし、このランク付けされたリストＲについて累積効用曲線を作成する。つまり、ランク付けされたリストＲ内の文書ごとに、効用基準ＵｔｉｌｉｔｙＭｅａｓｕｒｅを使用して累積効用を計算する。
１．４  ｉMaxとして示される累積効用曲線上の最大効用点のランクを決定する。
１．５  変数θnに、ランクｉMaxに対応するスコア曲線上の出力スコアを割り当てる。
１．６  以下のとおりにβnを改善する。
【数２７】
2005316996.tif 000030
１．７  βsum=βsum＋βn
４．Ｆｏｒｅａｃｈを終了する。
５．以下のようにフォールドごとに決定されるβｓの上でβを平均に設定する。β＝βsum／ｎ
６．以下のように、（前のステップを使用して決定された）βを使用して最適閾値θnewを計算する。ＳｅｔＴｈｒｅｓｈｏｌｄＵｓｉｎｇＢｅｔａＧａｍｍａ（Ｃ，Ｔ，Ｍ，β，γ，ＵｔｉｌｉｔｙＭｅａｓｕｒｅ，ＰT）
７．θnewを戻す。
【００８２】
前記アルゴリズムでは、ＰXはデータベースＸ内の正の標本の数を示す。戻される値またはＣｏｎｔｉｎｏｕｓＴｈｒｅｓｈｏｌｄ（．）の出力は、以下のように文書分類に使用される。
【数２８】
2005316996.tif 000031
【００８３】
非線形ＳＶＭ用の修正された分類規則は以下のとおりである。
【数２９】
2005316996.tif 000032
【００８４】
式中、Ｋ（．）はドット積のような相似関数を示す。
【００８５】
図４ｂは、フォールドが４に設定される（つまり、訓練データセット４１０は、４つの重複しない部分集合に分割される）連続閾値化アルゴリズムの概略図である。ベータ（β）の別の値がフォールドごとに決定され、以後平均化され、βの最適値０．３を導く。ここではγ値は０．０２に固定された。
【００８６】
前記実施形態では、情報ニーズの基本モデルはＳＶＭモデルであった。ここでは、情報ニーズの基本モデルが従来の情報検索（ＩＲ）ベクタ空間モデルである好ましい代替的実施形態を略述する。情報検索モデルは、１組のパラメータ＜Ｗ，θ＞として表現することができ、ここではＷは重みベクタを示し、θは閾値を表現する。重みベクタＷは、形式＜ｆi，ｗi＞のタプルのリストから構成され、ここではｆiはフィーチャを示し、ｗiはフィーチャｆiに関連付けられる重みを示す。これは重みベクタＷのベクタ空間表現に相当する。重み値ｗi及び閾値θは、情報検索学習アルゴリズムを使用して標本から学習される。これらのアルゴリズムは、フィーチャ用のスコアリング関数（通常はドット積ベースの関数）及び効用関数を参照しつつ、標本文書からのフィーチャ抽出ステップ、フィーチャ加重ステップ、及び閾値設定ステップを含む。スコアリング関数は、モデル内のフィーチャと共通の文書のフィーチャに基づいて文書のスコア（類似性）を決定する。前述したような効用関数は、ユーザによって、またはユーザのために決定されるように、間違って分類される（「偽の正」）送達された文書に対する、正しく分類される（「真の正」）送達された文書の相対値を示す。閾値は、閾値のまたは閾値を超えるスコアの文書がシステムにより受け入れられるようなスコアである。理想的には、閾値は期待効用を最大化するスコアに設定される。
【００８７】
ＩＲモデルで使用されるフィーチャまたはタームは、ユーザまたはシステムがフィルタリングされるトピックまたはカテゴリの特徴付けとして提供した、標本文書及び他のテキストから導出される。本発明の１つの実施形態では、ＩＲモデルのタームは正の標本及び負の標本（ならびにその他の背景テキスト）から、最初にテキストの中のフィーチャを特定すること、及び第２に選択原則に従って考えられるフィーチャの部分集合を選択することを含む２ステッププロセスで抽出される。文書ごとに、前述された技法を使用してタームが抽出される。次に重みは、ＴＦ＿ＩＤＦなどの重み付け関数を使用してフィーチャごとに計算される。以後、情報ニーズモデルで使用されるタームが選択される。多くの考えられるターム−選択関数を使用することができ、当業者には既知である。１つの好ましい実施形態では、よく知られている「Ｒｏｃｃｈｉｏ」スコアリング手法から導出される以下のスコアリング関数がタームをランク付けするために使用できる。Ｒｏｃｃｈｉｏ重み付け手法は、以下のように定義される。
【数３０】
2005316996.tif 000033
式中、
ＴＦi,Text：情報ニーズのテキスト記述の中のフィーチャｆiの頻度
ＴＦij：文書j中のｆｅａｔｕｒｅiの発生数
ＤR：正の文書集合
ＤN：負の文書集合
Ｒ：正の文書の数（つまりＤRのサイズ）
Ｎ：負の文書の数
α、β：経験的に決定されなければならない係数（αは多くの場合０．７５に設定され、βは多くの場合０．２５に設定される）
【００８８】
いったんスコアがフィーチャに割り当てられると、ここではＲｏｃｃｈｉｏ関数を使用して、フィーチャはランク付けすることができ、情報ニーズのＩＲベースのモデルで使用するためにフィーチャのすべてまたは部分集合を選ぶことができる。本発明の好ましい実施形態では、標本文書からのフィーチャが、フィルタ構造で使用されるアルゴリズムにより指定されるランク（例えば１０、２０または５０）までスコアの降順で選ばれ、それらの上位にランクされたタームだけがフィーチャプロファイルに使用される。
【００８９】
ＩＲモデルの中の各タームに関連付けられる重みは、（この例では）Ｒｏｃｃｈｉｏ重みとＴＤ＿ＩＤＦの積となる場合がある。
【数３１】
2005316996.tif 000034
式中、Ｒｏｃｃｈｉｏiは上に定義した通りであり、ｉｄｆiは処理済みのすべての使用可能な単位（例えば文書）全体でのｆiの分散カウントの逆数の対数を表す。
【００９０】
モデル閾値θ（この値を超えてスコアする文書は正と分類される）は、上に略述した離散閾値化プロシージャまたは連続閾値化プロシージャを使用して確立できる。
【００９１】
その重みベクタＷ及びその閾値θにより表現されるＩＲモデル（Ｗ，θ）を使用する文書Ｘの分類は、以下の決定規則を使用して達成される。
【数３２】
2005316996.tif 000035
式中、＜．＞はドット積演算を示し、Ｗ及びθはＩＲモデルのパラメータである。
【００９２】
当業者は、モデル（例えば、確率的モデル）を構築するために使用する可能性があり、閾値を調整または設定のため上に略述した閾値化プロシージャを使用できる多くの代替方法及び技法を容易に理解できる。加えて、好ましい実施形態は、モデル化情報ニーズだけではなく、顔分類などの他の問題領域にも適用できる。
【００９３】
多くのフィルタリング用途では、フィルタまたは分類子は静的なままではありえず、経時的に発生する新しい条件（例えば、データ及びユーザの好み）に基づいて修正、再作成、または再学習されなければならない。例えば、ニュースフィルタは、関心のある特定の話が最初に報告されるときにはうまく作動するだろうが、その話が古くなるあるいはよく知られるようになると記事を過剰に送達する（ｏｖｅｒ−ｄｅｌｉｖｅｒ）可能性がある。これは、ユーザの関心が、例えばその話に関するすべてのニュースを欲することから、話の重大な新しい展開だけを欲するように、変化するため、及び（新しい単語または名前、省略語、句のパターン等を含む）記事の中の情報が経時的に変化し、元のフィルタの中のフィーチャがもはや有効な弁別器として働かないための両方の理由から発生する場合がある。適応フィルタリングシステムの重大な要件とは、ユーザからフィードバックを受け取り、おそらくフィルタが過去にユーザに送達した情報とともにそのフィードバックを解釈し、そのフィルタを改訂し、（時間で前方に進行し）処理されているテキストの条件変化及びユーザの関心の変化に適合する情報を送達するする能力である。このような場合、図１−２に示されるようにシステム及びシステム・ユーザ間関係のさらに複雑なモデルが必要である。図１−２は具体的に、ユーザにフィルタリングの結果を提示するためのインタフェースであるユーザインタフェース要素１０７ａと、ユーザがフィルタリング決定が正しかったかどうかに関する判定を表示できるようにする対話型インタフェース要素１０８ａとを備える適応フィルタリングシステムを提示する。フィードバックは暗示的なものでもよい（例えば、関連性があるとしてユーザに送達され、ユーザによって関連性なしの印をつけられなかった文書は関連性があると推測できる）。そして、性能改善のため、新しい文書は、そのクラス割り当てとともに１１０ａでクラスモデルに適用される。
【００９４】
閾値設定及び調整の開示されている方法は、以下に示すように、送達される情報に対するユーザの応答に基づいた増分更新のプロセスを通じて適応フィルタモデルに適用できる。
【００９５】
文書のストリームの適応フィルタリングは、以下のステップを含む。
１．学習アルゴリズム（ＳＶＭ）とモデルのための既知の標本のなんらかの初期集合とを使用してモデルＭを作成すること。
２．分類されなければならない一定量の文書をフィルタリングすること。システムのユーザは、このシナリオでは（文書のクラスを示すことにより明示的に、あるいはそのケースでは文書が正であると仮定される、クラスを示さないことにより暗示的にのどちらかで）送達された文書に関する判定を行い、それにより情報ニーズモデルの更新のために使用できる判定された標本のプールを増加させる。
３．（例えば、新しい正の標本が現れるたびなどの）特定の間隔で、モデルＭは判定された（及び未判定の）文書の拡大リストを使用して、以下のように更新される。
・再訓練によってＳＶＭモデルを更新する。
・ＤｉｓｃｒｅｔｅＴｈｒｅｓｈｏｌｄまたはＣｏｎｔｉｎｕｏｕｓＴｈｒｅｓｈｏｌｄを使用して情報モデルの閾値を更新する。
・この閾値化パスは、新規に獲得された訓練情報を組み込み、それによってフィルタを動的に改善する。
４．ユーザがフィルタリングの終了を要求しない限り、ステップ２に戻る。
【００９６】
図５は、本発明の実施形態を実現できるコンピュータシステム５００のブロック図である。コンピュータシステム５００は、バス５０２または情報を伝達するための他の通信機構、及び情報を処理するためにバス５０２と結合されるプロセッサ５０４を含む。コンピュータシステム５００は、プロセッサ５０４により実行される情報及び命令を記憶するためのバス５０２に結合される、ランダムアクセスメモリ（ＲＡＭ）または他の動的記憶装置などのメインメモリ５０６も含む。メインメモリ５０６は、プロセッサ５０４により実行される命令の実行中に一時的な変数または他の中間情報を記憶するために使用されてもよい。コンピュータシステム５００は、さらに、読取専用メモリ（ＲＯＭ）５０８またはプロセッサ５０４向けの静的な情報及び命令を記憶するためにバス５０２に結合される他の静的記憶装置を含む。磁気ディスクまたは光ディスクなどの記憶装置５１０が、情報及び命令を記憶するためにバス５０２に結合されて設けられる。
【００９７】
コンピュータシステム５００は、バス５０２を介して、コンピュータユーザに情報を表示するための陰極線管（ＣＲＴ）などのディスプレイ５１２に結合されてよい。英数字他のキーを含む入力装置５１４は、情報及びコマンドの選択をプロセッサ５０４に伝達するためにバス５０２に結合される。別のタイプのユーザ入力装置は、方向情報及びコマンド選択をプロセッサ５０４に伝達するため、及びディスプレイ５１２上のカーソルの動きを制御するためのマウス、トラックボールまたはカーソル方向キーなどのカーソルコントロール５１６である。この入力装置は、通常、２つの軸、つまり装置が平面内の位置を指定できるようにする、第１の軸（例えばｘ）及び第２の軸（例えばｙ）で自由度２を有する。
【００９８】
本発明は、文書をフィルタリングするためのコンピュータシステム５００の使用に関する。フィルタリングプロセスは、メインメモリ５０６に記憶されている命令のシーケンスを実行するプロセッサ５０４に応えてシステム５００によって提供される。このような命令は、記憶装置１３１０などの別のコンピュータ読み取り可能媒体からメインメモリ５０６の中に読み込まれてよい。しかしながら、コンピュータ読み取り可能媒体は記憶装置５１０などの装置に限定されない。例えば、コンピュータ読み取り可能媒体はフロッピー（登録商標）ディスク、フレキシブルディスク、ハードディスク、磁気テープもしくは他の磁気媒体、ＣＤ−ＲＯＭ、任意の他の光媒体、ＲＡＭ、ＰＲＯＭ、及びＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、他のメモリチップもしくはカートリッジ、またはコンピュータがそこから読み取ることができる他の媒体を含んでよい。メインメモリ５０６に記憶される命令のシーケンスが実行されると、プロセッサ５０４は上述されたプロセスステップを実行する。代替的実施形態では、配線で接続された回路構成要素が、本発明を実現するためにソフトウェア命令の代わりに、あるいはソフトウェア命令と組み合わされて使用されてよい。したがって、本発明の実施形態はハードウェア回路構成要素及びソフトウェアの特定の組み合わせに限定されない。
【００９９】
コンピュータシステム５００は、バス５０２に結合される通信インタフェース５１８も含む。通信インタフェース５１８は、ローカルネットワーク５２２に接続されるネットワークリンク５２０に双方向データ通信結合を提供する。例えば、通信インタフェース５１８は、対応する型の電話回線にデータ通信接続を与えるために総合デジタル通信網（ＩＳＤＮ）カード、またはモデムであってよい。別の例として、通信インタフェース５１８は、互換性のあるＬＡＮにデータ通信接続を提供するためにローカルエリアネットワーク（ＬＡＮ）カードであってよい。無線リンクも実現できる。このような実装形態では、通信インタフェース５１８は、多様な種類の情報を表現するデジタルデータストリームを搬送する電気信号、電磁信号または光信号を送受する。
【０１００】
ネットワークリンク５２０は、通常、他のデータデバイスに１つまたは複数のネットワークを通してデータ通信を提供する。例えば、ネットワークリンク５２０は、ローカルネットワーク５２２を通してホストコンピュータ５２４に、またはインターネットサービスプロバイダ（ＩＳＰ）５２６によって運用されるデータ装置に接続を提供してよい。ＩＳＰ５２６は、これに対して、現在一般的に「インターネット」５２８と呼ばれている世界中のパケットデータ通信網を通してデータ通信サービスを提供する。ローカルネットワーク５２２及びインターネット５２８は、ともに、デジタルデータストリームを搬送する電気信号、電磁信号、または光信号を使用する。コンピュータシステム５００との間でデジタルデータを搬送する、多様なネットワークを通る信号、ならびにネットワークリンク５２０上及び通信インタフェース５１８を通る信号は、情報を運ぶ搬送波の例示的な形式である。
【０１０１】
コンピュータシステム５００は、ネットワーク（複数の場合がある）、ネットワークリンク５２０及び通信インタフェース５１８を通してメッセージを送信し、プログラムコードを含むデータを受信する。例えばインターネット５２８では、サーバ５３０はアプリケーションプログラムのための要求されたコードを、インターネット５２８、ＩＳＰ５２６、ローカルネットワーク５２２及び通信インタフェース５１８を通して送信する可能性がある。本発明に従って、１つのこのようにダウンロードされたアプリケーションは、本明細書に説明されるように大量のテキストを使用して情報の検索またはフィルタリングを行う。ネットワーク上で受信されるプログラムコードは、受信されるとともにプロセッサ５０４により実行されてもよく、および／または、後で実行するために記憶装置５１０または他の不揮発性記憶装置に記憶されてもよい。このようにして、コンピュータシステム５００は搬送波の形でアプリケーションコードを取得してよい。
【０１０２】
本発明の構成要素は、全体としてまたは部分的に複数の場所でメモリにまたはディスクに記憶されてよく、アプリケーションにより同期してまたは非同期でアクセスされてよく、構成要素形式では、文書の検索またはフィルタリングに必要とされる情報を提供するためにメモリ内で再構成されてよい。
【０１０３】
本発明を特定の実施形態に関して具体的に説明、図示したが、本発明の精神または範囲から逸脱することなく、上の説明または図の形式または詳細に、変更を加え得ることが当業者は理解されよう。
【図面の簡単な説明】
【０１０４】
【図１−１】サポートベクタマシン（ＳＶＭ）を使用して文書の集成またはストリームから関連する情報をフィルタリングするための本発明にかかる方法のフローチャートである。
【図１−２】サポートベクタマシン（ＳＶＭ）を使用して文書の集成またはストリームから関連する情報をフィルタリングするための本発明にかかる方法のフローチャートである。
【図２−１】数学的に＜Ｗ，Ｘ＞＋ｂ＝０と表現される、超平面Ｈにより示される二次元入力空間Ｗｏｒｄ１×Ｗｏｒｄ２におけるＳＶＭの図であり、各訓練標本文書は１つのカテゴリ（「＋」または「−」）に関連付けられ、サポートベクタは超平面Ｈ+1及びＨ-1上の例に対応する図である。
【図２−２】数学的に＜Ｗ，Ｘ＞＋ｂ＝０と表現される、超平面Ｈにより示される二次元入力空間Ｗｏｒｄ１×Ｗｏｒｄ２におけるＳＶＭの図であり、訓練標本文書も提示され、各訓練標本はカテゴリ（「＋」または「−」）、マージンスコア、効用値、ランク、及び各ランクでの効用の計算詳細と関連付けられ、これらの情報は、表形式で（及び適切な場合には図像形式で）提示される図である。
【図３−１】対応するマージンスコア及び効用曲線を用いてランク付けされた文書のリストのグラフである。
【図３−２】ベータ−ガンマ閾値化アルゴリズムのパラメータを描くグラフである。
【図３−３】対応するマージンスコア、効用、及び適合効用曲線を用いてランク付けされた文書リストのグラフである。
【図３−４】対応するマージンスコア、効用、及び適合マージン曲線を用いてランク付けされた文書リストのグラフである。
【図３−５】対応するマージンスコア、効用、適合マージン曲線、及び適合効用曲線を用いてランク付けされた文書のリストのグラフである。
【図４−１】離散閾値化アルゴリズムの概略図である。
【図４−２】連続閾値化アルゴリズムの概略図である。
【図５】本発明の実施形態を実現できるコンピュータシステムのブロック図である。
【符号の説明】
【０１０５】
１０１    文書の修正
１０３    ターム重みベクタ
Ｗ１０３    重みベクタ
１０４    閾値
１３０    文書のストリーム
１３１    フィーチャ抽出モジュール
１４０    サポートベクタマシン（ＳＶＭ）
１４０    二値文書分類子モデル（線形ＳＶＭ）
２００    ＳＶＭ
２０１    ＳＶＭモデル
２１０    超平面
Ｈ２１０    正のクラス標本
２１１    正の標本
２１２    負の標本
２１３、２１４    支持する超平面
２１５    ｙ軸
２１６    Ｘ軸
２１６    ＳＶＭのマージン
２１７    ２１０から最も近い正（サポートベクタ）
２１８    正のクラスサポートベクタ
２１９    負のクラスサポートベクタ
２２０    原点
２３０    閾値（重みベクタＷ、法線ベクタ）
２３０ａ    文書
２３１ａ    垂直距離
２４０    正の領域
２４１    負の領域
２５０ａ    文書
２５２ａ    マージンスコア
２５４ａ    累積効用値
２６０ａ    データマージンセット
２７１ａ    マージン軸
３２０    効用曲線
３２１    データマージン曲線
３３２    効用
１０７ａ    ユーザインタフェース要素
１０８ａ    インタフェース
５００    コンピュータシステム
５０２    バス
５０４    プロセッサ
５０６    メインメモリ
５０８    読取専用メモリ
５１０    記憶装置
５１２    ディスプレイ
５１４    入力装置
５１８    通信インタフェース
５２０    ネットワークリンク
５２２    ローカルネットワーク
５２４    ホストコンピュータ
５２６    インターネットサービスプロバイダ（ＩＳＰ）
５２８    インターネット
５３０    サーバ
１３１０    記憶装置
【図１−１】
2005316996.tif 000048
【図１−２】
2005316996.tif 000049
【図２−１】
2005316996.tif 000050
【図２−２】
2005316996.tif 000051
【図３−１】
2005316996.tif 000052
【図３−２】
2005316996.tif 000053
【図３−３】
2005316996.tif 000054
【図３−４】
2005316996.tif 000055
【図３−５】
2005316996.tif 000056
【図４−１】
2005316996.tif 000057
【図４−２】
2005316996.tif 000058
【図５】
2005316996.tif 000059
【外国語明細書】
2005316996000001.pdf