(57)【要約】２進のベクトルマシン(SVM)アルゴリズムを使用して例を多カテゴリに分類する改良された方法。1つの好ましい実施例では、方法は以下のステップを含んでいる: コンピュータのメモリに多くのユーザ定義テゴリを記憶し、各カテゴリに関連づけられた1つ以上の特徴を確認するように各カテゴリに関する多くのトレーニング例を分析し、各例について少なくとも1つの特徴ベクトルを計算し、すべてのトレーニング例に関する情報を反映するように少なくとも1つの特徴ベクトルの各々を変換し、多くのカテゴリの各１つについてSVM分類機を構築し、SVM分類機を構築する処理が：第１のカテゴリにおける各例を第１のクラスに、かつ他のカテゴリに属するすべての他の例を第２のクラスに割当て、いずれか1つの例が第１のカテゴリと同様に別のカテゴリに属するなら、そのような例が第１のクラスのみに割当てられ、第１のカテゴリのためのSVM分類機の少なくとも1つの調整可能なパラメタを最適化し、SVM分類機は第１および第２のクラスを使用して訓練され、２進のSVM分類機の出力をカテゴリメンバーシップの確率に変換する関数を最適化することを含む。
2006511000.tif 000002
【特許請求の範囲】
【請求項１】
２進のSVMアルゴリズムを使用して多カテゴリ分類機をトレーニングする、コンピュータベースシステムの方法であって、
多くのユーザ定義カテゴリをコンピュータのメモリに記憶し、
各カテゴリに関連づけられた1つ以上の特徴を確認するように各カテゴリに関する多くのトレーニング例を分析し、
前記各例について少なくとも1つの特徴ベクトルを計算し、
前記トレーニング例の各々に関する所望の情報を提供するように、第1の数学関数を使用して前記少なくとも1つの特徴ベクトルの各々を変換し、
前記多くのカテゴリの各１つについてSVM分類機を構築することを含み、前記SVM分類機を構築する処理が、
第１のカテゴリにおける前記各例を第１のクラスに、かつ他のカテゴリに属するすべての他の例を第２のクラスに割当て、いずれか1つの前記例が前記第１のカテゴリおよび別のカテゴリの両方に属するなら、そのような例が第１のクラスのみに割当てられ、
前記第１のカテゴリのためのSVM分類機の少なくとも1つの調整可能なパラメタを最適化し、前記SVM分類機は第１および第２のクラスを使用して訓練され、
２進のSVM分類機の出力をカテゴリメンバーシップの確率に変換する第2の数学関数を最適化することを含む方法。
【請求項２】
前記第1のカテゴリがそれに割当てられたトレーニング例の予め定められた数より多くを有するかどうか決定することをさらに含み、前記第1のカテゴリに割当てられたトレーニング例の数が前記予め定められた数を超えないならば、前記第1のカテゴリのためのSVM分類機を構築する処理が中止される請求項1の方法。
【請求項３】
訓練されたSVM分類機が最適化されたかどうかをテストすることをさらに含み、前記SVM分類機が最適化されることができなかったならば、前記第1のカテゴリのための前記SVM分類機が捨てられる請求項1の方法。
【請求項４】
前記第1のカテゴリに割当てられたトレーニング例の部分集合を“ホールドアウト”組に分配し、トレーニング例の前記部分集合は前記トレーニングステップから除外され、
前記少なくとも1つの調整可能なパラメタのために予め定められた初期値を使用して第1のカテゴリについてSVM分類機の解を計算し、
解がオーバーゼネラライゼーションかオーバーメモライゼーションのどちらかによって特徴付けられるかどうかを決定するために、前記第1のカテゴリについて前記解をテストする、
ステップを含む方法を使用して、前記SVM分類機の少なくとも1つの調整可能なパラメタが最適化される請求項1の方法。
【請求項５】
前記第1のカテゴリのための前記SVM分類機の解がオーバーゼネラライゼーションかオーバーメモライゼーションのどちらかによって特徴付けられるかどうかを決定する前記テストが、前記SVM分類機によって生成される左右対称のSVM分類機の点数(例えば、sと-s)間の関係に基づいており、クラスメンバーシップの第1の推定確率指示とSVM分類機の点数sを有するトレーニング例についての非クラスメンバーシップの第2の推定確率指示が、それぞれ確率式q(C|s)と1.0-q(C|-s)により提供される請求項4の方法。
【請求項６】
前記第1のカテゴリのための前記SVM分類機の解がオーバーゼネラライゼーションかオーバーメモライゼーションのどちらかによって特徴付けられるかどうかを決定するテストが、一方では前記第１および第2の推定確率の調和平均、および他方では前記第１および第2の推定確率の算術平均間の差に基づいている請求項5の方法。
【請求項７】
前記少なくとも1つの調整可能なパラメタが、前記SVM分類機のために2つの調整可能なパラメタ、即ち、正のクラスのために１つおよび負のクラスのために１つを含む請求項4の方法。
【請求項８】
前記SVM 分類機が２つのコストファクタ(正のクラスについて１つ、負のクラスについて１つ)を有する以下の定式化に基づく請求項4の方法：
【数１】
2006511000.tif 000009
ここに、αiは例ｘiのためのラグランジュ乗数である、
ｙi=ｘiが正のクラスであるなら+1、ｘiが負のクラスであるなら-1、
Φ(x)は入力ベクトルを特徴ベクトルに写像する関数である、
K(xi，xj)= Φ(xi)・ Φ(xj)
制約条件として、
【数２】
2006511000.tif 000010
ここに、C＋とC−がユーザ定義可能な2つのコストファクタである。
【請求項９】
前記SVM 分類機が２つのコストファクタ(正のクラスについて１つ、負のクラスについて１つ)を有する以下の定式化に基づく請求項4の方法：
【数３】
2006511000.tif 000011
ここに、αiは例ｘiのためのラグランジュ乗数である、
ｙi=ｘiが正のクラスであるなら+1、ｘiが負のクラスであるなら-1、
Φ(x)は入力ベクトルを特徴ベクトルに写像する関数である、
【数４】
2006511000.tif 000012
制約条件として、
【数５】
2006511000.tif 000013
ここにｗは超平面に直角な重さベクトル、C＋とC−がユーザ定義可能な2つのコストファクタである。
【請求項１０】
前記解を計算し、および前記解をテストするステップが単体最適化方法に基づく数値最適化ルーチンに従って必要に応じて繰り返される請求項4の方法。
【請求項１１】
前記第1のカテゴリのための前記SVM分類機が前記第1のカテゴリのための点数sを計算し、前記点数はSVM点数を確率推定値に変換するS字状関数におけるスロープパラメタに合うように最適化される請求項1の方法。
【請求項１２】
SVM点数の較正が無限のサポートベクトルトレーニング例を使用して実行される請求項1の方法。
【請求項１３】
SVM点数の較正がホールドアウト組に分配されたトレーニング例を使用して実行される請求項1の方法。
【請求項１４】
SVM点数の較正が無限のサポートベクトルトレーニング例とホールドアウト組に分配されたトレーニング例の両方を使用して実行される請求項1の方法。
【請求項１５】
前記トレーニング例がテキストを含む文書を含む請求項1の方法。
【請求項１６】
新しい例を少なくとも1つの多カテゴリに分類する方法であって、
前記新しい例について特徴ベクトルを発生させるように新しい例を分析し、
２進のSVM分類機を使用して特徴ベクトルを第1のカテゴリに分類し、
少なくとも1つの確率推定値を発生させるようにS字状関数を使用して前記第1のカテゴリのための計算されたSVM点数を変換し、
前記少なくとも1つの確率推定値を変換するために誤分類コストマトリクスを使用し、
前記少なくとも1つの変換された確率推定値のどれかが確率閾値を超えているかどうかを決定することを含む方法。
【請求項１７】
前記変換S字状関数が前記第1のカテゴリについてトレーニング中に最適化されるスロープパラメタ含む請求項16の方法。
【請求項１８】
新しい例を少なくとも1つの多カテゴリに分類する方法であって、
前記新しい例について特徴ベクトルを発生させるように新しい例を分析し、
２進のSVM分類機を使用して特徴ベクトルを第1のカテゴリに分類し、
少なくとも1つの確率推定値を発生させるようにS字状関数を使用して前記第1のカテゴリのために計算されるSVM点数を変換し、
前記少なくとも1つの確率推定値を変換するためにカテゴリの前のマトリクスを使用し、
前記少なくとも1つの変換された確率推定値のどれかが確率閾値を超えているかどうかを決定することを含む方法。
【請求項１９】
前記変換S字状関数が前記第1のカテゴリについてトレーニング中に最適化されるスロープパラメタを含む請求項18の方法。
【請求項２０】
前記カテゴリの前のマトリクスに含まれる値が、前記第1のカテゴリにおける例の数を計数しかつすべてのカテゴリにおける例の数により割り算することにより、前記SVM分類機のトレーニング中に推定される請求項18の方法。
【請求項２１】
コンピュータによって実行されるとき、２進のSVMアルゴリズムを使用して多カテゴリ分類機を訓練する方法を実行する指示を記憶するためのコンピュータ読み出し可能な媒体であって、方法が、
多くのユーザによって定義されたカテゴリをコンピュータのメモリに記憶し、
各カテゴリに関連づけられる1つ以上の特徴を確認するように各カテゴリに関する多くのトレーニング例を分析し、
それぞれの前記例のために少なくとも1つの特徴ベクトルを計算し、
前記トレーニング例の各々に関して所望の情報を提供するように第1の数学関数を使用して前記少なくとも1つの特徴ベクトルの各々を変換し、
前記多数のカテゴリの各１つについてSVM分類機を構築することを含み、SVM分類機を構築する処理が、
第1のカテゴリにおける前記例の各々を第1のクラスに、および別のカテゴリに属するすべての他の例を第2のクラスに割当て、前記例のいずれか1つが前記第1のカテゴリおよび他のカテゴリの両方に属するなら、そのような例が第1のクラスにのみ割当てられ、
前記第1のカテゴリのためにSVM分類機の少なくとも1つの調整可能なパラメタを最適化し、前記SVM分類機が前記第１および第2のクラスを使用して訓練され、
２進のSVM分類機の出力をカテゴリメンバーシップの確率に変換する第2の数学関数を最適化することを含む、コンピュータ読み出し可能な媒体。
【請求項２２】
前記方法は、前記第1のカテゴリがそれに割当てられたトレーニング例の予め定められた数より多いかどうかを決定することをさらに含み、前記第1のカテゴリに割当てられたトレーニング例の数が前記予め定められた数を超えないなら、前記第1のカテゴリのためのSVM 分類機を構築する処理が中止される請求項21のコンピュータ読み出し可能な媒体。
【請求項２３】
前記方法は、訓練されたSVM分類機が最適化されたかどうかをテストすることをさらに含み、SVM 分類機が最適化されることができないなら、前記第1のカテゴリのための前記SVM分類機は捨てられる請求項21のコンピュータ読み出し可能な媒体。
【請求項２４】
前記第1のカテゴリに割当てられたトレーニング例の部分集合を“ホールドアウト”組に分配し、前記トレーニング例の部分集合が前記トレーニングステップから除外され、
前記少なくとも1つの調整可能なパラメタのための予め定められた初期値を使用して第1のカテゴリのためのSVM分類機の解を計算し、
解がオーバーゼネラライゼーションかオーバーメモライゼーションのどちらかによって特徴付けられるかどうか(すなわち、特定であり過ぎる)を決定するため、前記第1のカテゴリについて前記解をテストする、
ことを含む方法を使用して前記SVM分類機の前記少なくとも1つの調整可能なパラメタが最適化される、請求項21のコンピュータ読み出し可能な媒体。
【請求項２５】
前記第1のカテゴリのための前記SVM分類機の解がオーバーゼネラライゼーションかオーバーメモライゼーションのどちらかによって特徴付けられるかどうかを決定する前記テストが、前記SVM分類機によって生成される左右対称のSVM分類機の点数(例えば、sと-s)間の関係に基づいており、クラスメンバーシップの第1の推定確率指示とSVM分類機の点数sを有するトレーニング例についての非クラスメンバーシップの第2の推定確率指示が、それぞれ確率式q(C|s)と1.0-q(C|-s)により提供される請求項24のコンピュータ読み出し可能な媒体。
【請求項２６】
前記SVM分類機の解がオーバーゼネラライゼーションかオーバーメモライゼーションのどちらかによって特徴付けられるかどうかを決定する前記テストが、一方では前記第１および第2の推定確率の調和平均、および他方では前記第１および第2の推定確率の算術平均間の差に基づいている請求項 25のコンピュータ読み出し可能な媒体。
【請求項２７】
前記少なくとも1つの調整可能なパラメタが前記SVM分類機のための2つの調整可能なパラメタ、即ち、正のクラスのために１つおよび負のクラスのために１つを含む請求項24のコンピュータ読み出し可能な媒体。
【請求項２８】
前記SVM 分類機が２つのコストファクタ(正のクラスについて１つ、負のクラスについて１つ)を有する以下の定式化に基づく請求項24のコンピュータ読み出し可能な媒体：
【数６】
2006511000.tif 000014
ここに、αiは例ｘiのためのラグランジュ乗数である、
ｙi=ｘiが正のクラスであるなら+1、ｘiが負のクラスであるなら-1、
Φ(x)は入力ベクトルを特徴ベクトルに写像する関数である、
K(xi，xj)= Φ(xi)・ Φ(xj)
制約条件として、
【数７】
2006511000.tif 000015
ここに、C＋とC−がユーザ定義可能な2つのコストファクタである。
【請求項２９】
前記SVM 分類機が２つのコストファクタ(正のクラスについて１つ、負のクラスについて１つ)を有する以下の定式化に基づく請求項24のコンピュータ読み出し可能な媒体：
【数８】
2006511000.tif 000016
ここに、αiは例ｘiのためのラグランジュ乗数である、
ｙi=ｘiが正のクラスであるなら+1、ｘiが負のクラスであるなら-1、
Φ(x)は入力ベクトルを特徴ベクトルに写像する関数である、
【数９】
2006511000.tif 000017
制約条件として、
【数１０】
2006511000.tif 000018
ここにｗは超平面に直角な重さベクトル、C＋とC−がユーザ定義可能な2つのコストファクタである。
【請求項３０】
前記解を計算し、および前記解をテストするステップが単体最適化方法に基づく数値最適化ルーチンに従って必要に応じて繰り返される請求項24のコンピュータ読み出し可能な媒体。
【請求項３１】
前記第1のカテゴリのための前記SVM分類機が前記第1のカテゴリのための点数sを計算し、前記点数はSVM点数を確率推定値に変換するS字状関数におけるスロープパラメタに合うように最適化される請求項21のコンピュータ読み出し可能な媒体。
【請求項３２】
SVM点数の較正が無限のサポートベクトルトレーニング例を使用して実行される請求項31のコンピュータ読み出し可能な媒体。
【請求項３３】
SVM点数の較正がホールドアウト組に分配されたトレーニング例を使用して実行される請求項31のコンピュータ読み出し可能な媒体。
【請求項３４】
SVM点数の較正が無限のサポートベクトルトレーニング例とホールドアウト組に分配されたトレーニング例の両方を使用して実行される請求項31のコンピュータ読み出し可能な媒体。
【請求項３５】
前記トレーニング例がテキストを含む文書を含む請求項21のコンピュータ読み出し可能な媒体。
【請求項３６】
コンピュータにより実行されるとき、新しい例を少なくとも1つの多カテゴリに分類する方法を実行するコンピュータ実行可能な指示を含むコンピュータ読み出し可能な媒体であって、方法が、
前記新しい例について特徴ベクトルを発生させるように新しい例を分析し、
２進のSVM分類機を使用して特徴ベクトルを第1のカテゴリに分類し、
少なくとも1つの確率推定値を発生させるようにS字状関数を使用して前記第1のカテゴリのための計算されたSVM点数を変換し、
前記少なくとも1つの確率推定値を変換するために誤分類コストマトリクスを使用し、
前記少なくとも1つの変換された確率推定値のどれかが確率閾値を超えているかどうかを決定することを含むコンピュータ読み出し可能な媒体。
【請求項３７】
前記変換S字状関数が前記第1のカテゴリについてトレーニング中に最適化されるスロープパラメタ含む請求項36のコンピュータ読み出し可能な媒体。
【請求項３８】
コンピュータにより実行されるとき、新しい例を少なくとも1つの多カテゴリに分類する方法を実行するコンピュータ実行可能な指示を含むコンピュータ読み出し可能な媒体であって、方法が、
前記新しい例について特徴ベクトルを発生させるように新しい例を分析し、
２進のSVM分類機を使用して特徴ベクトルを第1のカテゴリに分類し、
少なくとも1つの確率推定値を発生させるようにS字状関数を使用して前記第1のカテゴリのために計算されるSVM点数を変換し、
前記少なくとも1つの確率推定値を変換するためにカテゴリの前のマトリクスを使用し、
前記少なくとも1つの変換された確率推定値のどれかが確率閾値を超えているかどうかを決定することを含むコンピュータ読み出し可能な媒体。
【請求項３９】
前記変換S字状関数が前記第1のカテゴリについてトレーニング中に最適化されるスロープパラメタを含む請求項38のコンピュータ読み出し可能な媒体。
【請求項４０】
前記カテゴリの前のマトリクスに含まれる値が、前記第1のカテゴリにおける例の数を計数しかつすべてのカテゴリにおける例の数により割り算することにより、前記SVM分類機のトレーニング中に推定される請求項38のコンピュータ読み出し可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
付録１としてここに添付されたものは、それらの全体を本明細書に組み入れられる参照文献のリストを含む表である。それぞれの参照文献は付録１の表に示されるようにその参照名(例えば、“Platt1”) によってここに参照される。
付録２として添付されたものは、二項分布のパラメタを最適化するための擬似コードの例である。
【０００２】
本発明は多カテゴリへの分類を実行するのに有効にサポートベクトルマシン（Support Vector Machine(SVM)）を使用するためのシステムと方法に関連する。特に、本発明は現実の世界の問題を計算上解決するためにSVM多分類の技術を適用するための改良されたシステムと方法に関連する。
【背景技術】
【０００３】
多クラス分類問題はさまざまな論点を提出し、特に多クラス分類問題へのSVMの適用は多くの困難を提示する。オリジナルな“ハードマージン” アルゴリズムは、“最大マージン超平面”として知られている2つのクラス間で単一の超平面を決定するように設計される。しかしながら、分類問題が多くの現実の世界の問題のためにそれを不適当にしている、重ね合わせ分布を用いたトレーニングデータを含んでいるならば、このアルゴリズムはそのような超平面を効率的かつ確実に定義しない。“ソフトマージン”アルゴリズムがこの制限を解くために後で開発されたが、これは新しい問題を導入した。ソフトマージンアルゴリズムは“ユーザが定義可能な”パラメタを含んでいる。“コストファクタ”として知られているこのパラメタは、メモライゼーションとゼネラライゼーションの間で正しいトレードオフでアルゴリズムに提供するためにSVMトレーニングアルゴリズムの外で設定されなければならない。コストファクタの概念はSVM分類問題に唯一ではないが、むしろパターン認識の機械の学習に関連するより一般的な概念である。SVM分類に関する文脈では、コストファクタを決定または計算することは、そうでなければ、最大マージン超平面を訓練するために必要とするより多くの情報を通常必要とする。
【０００４】
従来技術の方法とシステムは、これらのアルゴリズムを多クラスの場合に広げるためにSVMアルゴリズムへのいくつかの小さな改良と変更を提供した。しかしながら、これまで知られていた多クラスアルゴリズムは、上で議論したソフトマージン定式化さえよりも計算上徹底的である。したがって、これらの多クラスアルゴリズムを計算上より処理しやすくするようにするために、多くの仕事が残っている。さらに、これらの多クラスアルゴリズムの理論上の性質に関する多くの研究がなかったので、それらの精度と信頼性に関していくつかの疑問が持ち上がっている。例えば、多クラスアルゴリズムによってモデル化される一般化の性質または漸近の振舞いが、オリジナルなハードマージンとソフトマージンSVMアルゴリズムと同じ程度まで研究されて、確かめられていない。
【０００５】
共通の代替手段は、多クラス決定が多くの２進問題に細分されるところに存在している。例えば、単一の(２進) SVM分類機はそれぞれ2つのクラス問題に使用されて、次に結果は最終的な決定をするように一緒に結合される。この結合をするために当業者に知られている多くのアルゴリズムがある--最もポピュラーな2つは“1対残り”および“すべて対にする”アプローチとして知られている。“1対残り”アプローチは、あらゆるカテゴリを他のすべてのカテゴリから切り離すのに分類機を使用することを含む。そのアイデアは個別にクラスメンバーシップを示す一組のSVMを発生させることである。多カテゴリ分類を解く問題は少しあいまいであるが、知られているさまざまな束縛破壊方式がある。同様に、“すべて対にする”アプローチは、クラスのすべての対にSVMを使用して、分類される新しい項目の最終的な目的地を決定するためにあらゆるSVMに投票させる。また、当業者に知られている様々な投票方式がある。例えば、Allwein1，Bishop1，Dietterich1，Platt3，Zadrozny2参照。
【０００６】
SVM分類機の出力は、真の確率と比べてSVMの外側で小さい値を有する“点数”である。正の点数は、SVMが新しい例を1つのクラスに割当てることを意味し、負の点数は他のクラスへの割当を示す。これは２進分類機によって考えられる2つのクラスについて議論するのに使用される“負のクラス”および“正のクラス”の名前を動機づける。点数の符号がどのクラスを決定するかに役割を果たしている間、SVMは新しい例を割当て、点数の大きさは確率ほど情報を与えない。例が他の例よりもそのクラスに“より多く属する”なら、点数はさらに大きくなり、例が他のクラスに“より多く属する”なら、それはより小さくなるだろう。したがって、高い負の点数は、例が負のクラスに属するとSVMが本当に信じる高い信頼を意味し、高い正の点数は、例が正のクラスに属する高い信頼を意味する。
【０００７】
しかしながら、クラスメンバーシップの分類機の出力確率を持っているのがはるかにより役に立って効果的であることが一般的に知られているので、これはSVMのより広いアプリケーションには容認できない。例えば付録 1の表に記載されているBishop1を参照。SVM点数を確率に変換する方法があり、そして、これらの方法はPlatt1，Zadrozny1，Zadrozny2およびSollich1で説明されるように当業者に知られている。
【０００８】
使用される特徴とクラスメンバーシップとの関係が時々線形でないということが最終的な問題である。これは非常に豊かな表現を表す非線形の空間に特徴を写像することを許容するSVMのカーネル部品を動機づける。これはどのように現在の表現の適切さを測定するか、そして、現在の組の特徴が良いものであるかどうかをどのように知るかに関する問題を持ち上げる。そうでなければ、他の何かが試みられるべきであるか、または最小限、システムは問題へのその適合における信頼の不足を示す診断の特徴を報告すべきである。分類アルゴリズムは、工業用に考慮されるためにこの種のフィードバックなしで実験室を出ることに困難な時間を有する。
【０００９】
サポートベクトルマシンは他の分類機よりも、特に多くの特徴を有する希薄な問題(例えば、トレーニング文書または例のわずかな数)について繰り返しより正確である。例えば、Joachims1，Platt1，Sollich1，Dumais1，Hearst1参照。さらに、それらのトレーニング時間を早くすることにおける多くの進歩があり、進歩はトレーニングコンピュータの要件を抜本的に改良した。例えば、Platt2，Keerthi1およびJoachims2参照。
【００１０】
“1対すべて”および“1対残り”アプローチを使用する多クラス分類は既に当業者によく知られている。例えば、Bishop1参照。線形分類機を使用するとき、誤り訂正出力コード(ECOC)がより正確な分類を提供するために示された。例えば、Dietterich1参照。より最近、このECOCパラダイムは他のコードマトリクス表現を含むように広げられて、より正確さを示し、２進分類機を使用する多クラス分類へのアプローチを統一した。例えば、Allwein1，Zadrozny2参照。
【００１１】
分類機能の出力を較正することが役立つことは当業者に一般的に知られている。例えば、RL1，Bishop1参照。分類機の出力をどのように較正するかは、実施に依存すべきであることが示され、また、有効になるように分類アルゴリズムに依存することが示された。例えば、Platt1，Sollich1，PriceKnerr1，Bishop1，Zadrozny1参照。
【００１２】
事実上、最近の仕事は多クラス分類コードマトリクス表現を確率出力の較正に結合するのに集中されさえした。例えば、Zadrozny2参照。
また、問題の表現への核（カーネル）の適合を判断するのは、多くの最近の研究の焦点であった。しかしながら、この研究の大部分は、よりよく問題に適応させるため、かつカーネルのアプリケーションが適切であるか否かを判断することなく設計することを含む。十分なトレーニング例が利用可能であるならば、問題のカーネルの有効性を判断することは提供または確認を使用することにより比較的よく扱うことができる。例えば、Bishop1参照。選ばれたカーネルが不十分な性能判断基準を提供するならば、我々はカーネルがこの問題に効力がないことを知る。しかしながら、効果のない源を決定することは依然としてするのが困難であり、より多くのトレーニング例が問題を解決するかどうかは未知である。
【００１３】
用語“超平面”はここで普通の技術的な意味に従って使用され、当業者によって知られているように、ことによると多次元の一次方程式を云う。二次元の超平面はまた、しばしば直線と呼ばれ、三次元の超平面はしばしば平面と呼ばれる。三次元以上が含まれるとき、超平面は通常超平面と呼ばれるだけである。
【００１４】
ここに使用される用語“最適化”は、機能の出力値に関して所望の値、値の範囲、または極端な値(例えば、最小または最大)をもたらす機能のパラメタを発見することの、当業者に知られているプラクチスを云う。
ここに使用されるように、“カーネル”は非常に一般的なマーサー（Mercer）状態に従って距離を定義する2つのベクトル間の関数であるマーサーカーネル（Mercer Kernel）を云う。関数のこのクラスは当業者によく知られている。例えば、Vapnik1参照。１つの特定の種類のカーネルは連続した間隔にその領域を“押しつぶす”当業者に知られている“S字状関数”である。用語“S字状”は“S形”を意味する。2種類のS字状関数の詳細な記述はBishopにある。
【００１５】
ここに使用される用語“特徴ベクトルの変換”は当業者により理解されるようなその普通の意味に従って使用され、所望の数学の関数に従って特徴ベクトルを変化することを云う。
【発明の開示】
【課題を解決するための手段】
【００１６】
本発明は、選択されたカーネルが与えられたタスクによく適合し、かつ例の多クラス割当を有効に取り扱うかどうかを決定する多クラスSVM分類に含まれる問題を有効に扱う方法である。本発明に従って多クラスSVM分類機を構築するための出発点として、一実施例において、伝統的な２進のSVMトレーニングと分類アルゴリズムがそれらの多くの利益を梃子作用するために使用されるかもしれない。これらのSVMアルゴリズムは、それらがメモライゼーション/ゼネラライゼーション学習トレードオフをよく取り扱うことにおいて、計算上効率的で、よく理論的に理解されていて、正確で、かつ“合理的な複雑さ”である。それらがよく研究されるので、それらの実施は効率的かつ有効になされることができ、最終的な答えを構築する際に使用されるトレーニング例に含まれる情報の効率的使用を許容する。
【００１７】
好ましい実施例では、本発明の多クラスSVM分類機からの出力点数は、クラスメンバーシップ確率になるS字状関数を使用してそれらを変換することによって変更される。これらの点数は、以下の詳細でさらに説明される多くの実施によるほんのわずかなトレーニング例を使用して、真のクラス確率分布関数とよく相関するように較正することができる。これらの出力が確率であるので、それらは前のコストとカテゴリに関するベイズ（Bayes）最適決定を作るために使用することができる。さらに、オリジナルなSVM点数を変換し、より複雑にする分類問題を再定式化しないことによって、本発明はほかの場所で報告されたSVM解利益(例えば、希薄性と精度)を維持する。
【００１８】
また他の実施例では、本システムは、あるカテゴリが分類するのが難しく、かつ困難の源を検出することさえできるとき、少なくとも現在のアルゴリズムが現在の分類タスクのために十分適合しているかどうか、または十分な例がトレーニングのために存在しているかどうかを検出する。したがって、本発明の方法とシステムは新しい分類問題で展開されることができ、分類問題を解決するためにシステムを使用している統計の専門家を必要としない。
【発明を実施するための最良の形態】
【００１９】
図を参照して以下で詳細に説明されるように、発明は２進のSVMアルゴリズムを使用する改良された多カテゴリの、または多クラスの分類機を提供する方法とシステムを提供する。発明の特定の実施例は以下で説明されるが、発明がこれらの特定の実施例に制限されないこと、実施例は例だけとして提供されることが理解される。
【００２０】
本発明はコンピュータシステムか他の処理システムのソフトウェアを使用して実行されるかもしれない。図1はここに説明される発明の機能性を実行することができる模範的コンピュータ100のブロックダイアグラムである。各コンピュータ100はサンタクララ，カリフォルニア，米国のインテル社からの利用可能なマイクロプロセッサと関連集積回路チップ“ペンティアム”（登録商標）のような、1個以上の中央プロセッサユニット(CPU)102のコントロールの下で動作する。コンピュータはキーボードとマウス104から命令とデータを入力することができ、入力とコンピュータ出力を表示106で見ることができる。通常、表示はビデオモニターか平坦なパネルディスプレイ装置である。コンピュータ100はまた、固定ハード・ディスク・ドライブなどの直接アクセス記憶装置(DASD)107を含んでいる。メモリ108は通常揮発性の半導体ランダムアクセスメモリー(RAM)を含む。望ましくは、各コンピュータはプログラム製品記憶装置112を受け入れるプログラム製品読取器110を含み、そこからプログラム製品読取器がデータを読み取ることができる(そして、それはそこへ任意にデータを書き込むことができる)。プログラム製品読取器は、例えばディスクドライブを含み、プログラム製品記憶装置はフロッピー（登録商標）ディスク、光学CD-Romディスク、CD-Rディスク、CD-RWディスク、DVDディスク、または同様のものなどの可搬記憶媒体を含むことができる。各コンピュータ100は、ネットワークとコンピュータとの間を接続116上で通信可能にするネットワークインタフェース114を通して、ネットワーク113上で他の接続コンピュータと通信することができる。これらの装置は通信バス117を通して他の装置と通信する能力を有する。
【００２１】
CPU102はコンピュータ100のメモリ108に一時記憶されるプログラミングステップの制御下で作動する。プログラミングステップが実行されるとき、適切なシステムの部品はその機能を実行する。したがって、プログラミングステップはここに説明されるシステムの機能性を実施する。プログラミングステップはプログラム製品112、またはネットワーク接続116を通してDASD107から受け取ることができる。記憶ドライブ110はプログラム製品を受け取り、そこに記録されるプログラミングステップを読み出し、プログラミングステップをCPU102により実行するためにメモリ108に移すことができる。上で述べたように、プログラム製品記憶装置は磁気フロッピー（登録商標）ディスク、CD-RomおよびDVD記憶ディスクを含む、コンピュータ読み出し可能な指示を有する多可搬媒体の任意の1つを含むことができる。他の適当なプログラム製品記憶装置は磁気テープおよび半導体メモリチップを含むことができる。このように、発明に従って作動の必要な処理ステップはプログラム製品上に具体化されることができる。
【００２２】
代わりに、プログラムステップはネットワーク113上で作動メモリ108に受信することができる。ネットワーク方法において、さらなる説明なしに当業者により理解されるよく知られている方法によって、ネットワーク通信がネットワーク接続116上で確立された後に、コンピュータはネットワークインタフェース114を通してメモリ108にプログラムステップを含むデータを受け取る。そして、プログラムステップはシステムの処理を実施するためCPU102によって実行される。当業者に知られているように、代替のアーキテクチュアと構造を持っている他のコンピューティングマシンとシステムがここに説明される発明の様々な機能をサポートするために実施されるかもしれない。
【００２３】
本発明は、多クラス分類における使用のため多クラス問題を２進分類手順に分解する以下の手順をもたらす。
図2は発明の一実施例に従って単一の２進SVMを訓練する過程のフローチャートダイヤグラムを示す。以下の議論の目的のために、我々は例が多カテゴリに属する多くのテキスト文書を含むと仮定する。しかしながら、発明はテキスト文書を分類することに制限されないが、多くの異なったタイプの情報、グラフィックス、パターンなどを分析および類別／分類するのに利用されるかもしれないことが理解される。201で始まって、すべての例が正または負のクラスのいずれかに割当てられると仮定される。極大の超平面を発見するために使用される例はステップ202で選択される。一般に、例の数は文書の総数の大きい百分率であり、一実施例では、例の数は予め定められた閾値よりも大きくなくてはならない。文書の残りはステップ203でホールドアウト(確認として知られているように)の組に割当てられる。ステップ204では、負および正のクラスのコストファクタのために初期の推測が使用され、次に、ステップ500(図5に関してさらに詳細に説明される)では、SVMトレーニングアルゴリズムが極大マージンの超平面を発見するために使用される。いったん超平面が発見されると、テストは解が良いものであるかどうか決定するためにステップ205で実行される。“良い”超平面が発見されたかを決定するためにこのテストを実行する詳細は、発明の一実施例に従って以下で説明される。
【００２４】
解が良いものであるならば、最適化手順はステップ209で解を出して戻る。解が良いものでないならば、最適化中に取られる繰り返しの数がステップ207で決定される何らかの実用的な限界を超えていない限り、最適化のステップは
数値の最適化ルーチン208に従って取られる。最適化のそのような方法は当業者に知られている。例えば、NumRecipies1参照。取られる繰り返しの数が何らかの実用的な限界よりも大きいならば、ステップ210で過程はシステムが最適化された解を発見できなかったことを示すメッセージを発生させる。
【００２５】
1つ以上のカテゴリに属する例が２進SVMを訓練するのにしばしば問題になる。したがって、この問題に対処するための方法と手順が必要である。4つの可能な解がある: 例を正のクラスに割当てる、例を負のクラスに割当てる、例を両方のクラスに割当てる、または例をどちらのクラスにも割当てない(例えば、例の組から例を取り除く)。例を両方のクラスに割当てるのは多くの理由で問題が多い。しかしながら、最も実用的なレベルでは、2次導関数情報を使用するのが効率的に最適のSVM 超平面解を発見するために重要であり、２次導関数はこの点で未定義になるだろう。例をどちらのクラスにも割当てないことは2つの理由で不運である: それは2つのカテゴリの各々についてトレーニング情報を浪費する、およびそれは例が両方のカテゴリにあるようにサポートされることに関する情報を浪費する。
【００２６】
したがって、1つの好ましい実施例では、本発明は例を正のクラスに置く。これは２進SVMタスクを非常に明らかにする幸運な効果がある: このカテゴリに例が属するかどうかを予測する。例が他のカテゴリに属するか否かは無関係である。多クラス分類の答えはほかの場所で扱うことができる。したがって、1つの好ましい実施例では、どんな例も現在のカテゴリを含んでいる1つ以上のカテゴリに属すならば、例は正のクラスに割当てられる。
【００２７】
一実施例において、ソフトマージンの２進SVMアルゴリズムが使用される。他の実施例では、使用されるソフトマージンアルゴリズムは負および正のクラスのため別々のコストファクタ(v)を有する。これが持っている主要な効果は、２進分類機の観点から独自にクラスに関連づけられる前の確率(“プライオアス”)を表すことである。これは“1対残り”多クラス分解で古典的な問題である; 負のクラスのためのプライオアスは、それが他のカテゴリのすべてから成るので、比較的高い場合がある。両方のカテゴリを等しい基盤以上に置くために、各クラスのコストファクタは独自に異なることが許され得る。“二元的なコストファクタ”分析のこの方法は技術で知られ、例えば、Morik1でさらに説明される。さらに、コストファクタを最適化することはメモライゼーションとゼネラライゼーションに関して最適の解を発見するのを助ける。コストファクタが特定のタスクのためそれらの最適値に近く選ばれるとき、SVM点数を与えられるクラスの実験確率はしばしばq(C||s|)=1-q(C|-|s|)であり、ここにsは生のSVM分類点数である。
【００２８】
２進の解をテストするとき、必要な効果は超平面ができるだけバイエス最適判断境界（Bayes Optimal Decision Boundary）の近くにあることを強要することである。例えば、Bishop1参照。これらの2つの確率がそれらのそれぞれのクラスプライオアスなしで推定されなければならない。
【００２９】
“良い”超平面が発見されると、それは最適判定限界p(C|s=0)=1-p(C|s=0)=0.5の近くに横たわるだろう。超平面がこの解の近くにないならば、問題は本来現在の特徴空間において線形分類機のためによく表されない。使用された特徴またはカーネルのどちらかが変化しなければならない。他方、ポイントが到達されることができるが、分類機の精度がこのカテゴリのために低いならば、より多くのトレーニングデータが支障をきたしていることに関してさらに決定するために使用される。より多くのトレーニングデータの追加は分類機が最適化の後に正しい判断境界を発見するのを助けるか、またはそれは分布が使用中の特徴/カーネルに不十分に適合することを決定するだろう。しかしながら、より多くのトレーニングデータを加えることは、一般に人の応答または本発明の外の処理であるので、これらの状態はカテゴリを取り除きかつ問題をシステムのユーザに報告する原因となると考えられる。
【００３０】
概要では、コストファクタを最適化して、良い判断境界が発見されることを確実にして、あいまいな文書を正のクラスにのみ割当てる組み合わせは、しばしば単調なp(C|s=0)=0.5，p(C|s)= 1-p(C|-s)である点数を与えられる実験クラス確率分布に導き、SVM点数sがいずれかの制限に行くときクラスメンバーシップの確率が0と1に行く。データがしばしばこれらの特性を果たす（またはきっちりと果たす）事実は、わずかな数のトレーニング文書のみで有効かつ正確に点数を較正させることを許容する。
【００３１】
先に述べたように、正が1つのクラスにおけるメンバーシップを示し、かつ負が他のクラスにおけるメンバーシップを示す判断関数を学ぶとして線形分類機が定式化されることができる。これは以下の通り引き出される:
【００３２】
【数１１】
2006511000.tif 000003
線形分類機のこの特性は当業者によく知られている。例えば、Bishop1，Platt1，Sollich1参照。しかしながら、SVMアルゴリズムは一般にこれらの確率値にうまく較正されない点数を出力する。これは、あらゆるクラスにおいて、確率カーブのスロープが再スケーリングされなければならなくて、その結果本発明が最適化することができるスロープパラメタAを導入することを意味する。したがって、使用される実際の変換は1／（1＋e-As）である。SVMが新しい例を分類
するとき、報告される点数は再スケーリングされたスロープでこのS字状を使用して変換される。上の変換関数などの二項分布を最適化する効率的な方法は当業者に知られている。例えば、Bishop1，Platt1参照。以下にさらに詳細に説明されるように、一実施例において、Platt1で言及された２次パラメタBが使用されないことを除いて、Platt1で説明されるように二項分布を最適化する方法が実施される。したがって、Bにかかわるすべての計算またはその導関数は取り除かれる。
【００３３】
さらに、SVM解が正確に1.0または-1.0であるように多くのトレーニング例の整列を強制するので、最大マージン超平面を発見するために使用されたトレーニング例のスロープパラメタを最適化することが、S字状パラメタを最適化する際に重要なバイアスを導入することができることに注意すべきである。例えば、Platt1参照。しかしながら、無限のサポートベクトルだけがこの振舞いを表示することがSVMの特性である。したがって、無限のサポートベクトルによって特徴付けられるそれらのトレーニング文書を除いて、すべてのトレーニング文書を最適化手順に追加することによって、このバイアスは少なくとも部分的に軽減されることができる。
【００３４】
S字状関数のパラメタ(A)はこの点で比較的制約される。最適化ルーチンが作動されるのを確実にすることによって、バイアス（オフセット）はその“正しい” ポイント(このパラメタが再最適化されない理由である)の近くに設定される。さらに、S字状関数のエンドポイントは構成により0と1に固定され、上で議論したように、最適化された確率分布(すなわち、これらは無限のサポートベクトルも持っていない)における重要なバイアスを導入しないそれらのトレーニング文書だけが最適化手順に追加される。これらの要素は、良い解を発見する最適化手順を提供するためにすべて寄与し、あるいはそれが持たれていないとき比較的わずかな例で知ることができる。
【００３５】
新しい例が分類されるべきであるときに、それは最初に特徴ベクトルに変換される。そして、この特徴ベクトルは標準の方法と手順を通してすべてSVMの２進の分類機を使用して分類される。例えば、Dumais1，Joachims1参照。点数は各カテゴリのために最適化されたS字状関数を使用してすべて変換され、出力(確率である)は呼者(caller)に返される。呼者は各カテゴリについて分類確率に基づくカテゴリを自由に受け入れるか、または拒絶することができる。すべての誤分類がコスト的に等しいなら、最大の精度は一般に0.5の閾値を選ぶことによって達成されるだろう。例を0.5以上の出力点数ですべてのカテゴリに置くことによって、分類誤りが最小値になることが期待される。
【００３６】
しかしながら、誤分類がコスト的に等しくないならば、調整がなされなければならない。さらに、例のデータのカテゴリプライオアスが真の分布プライオアスを表すなら、それらのカテゴリプライオアスは分類判断で使用されるべきである。すべての分類機の出力が確率であるときに、これらは当業者への両方の共通の手順である。例えば、Bishop1参照。カテゴリプライオアスとコストマトリクスは原理化された方法で最終的な判断関数を調整するのに使用することができる。さらに、クラスプライオアスはしばしばかなり推定することが容易 (カテゴリメンバーシップ確率と対照的に) であるので、簡単な計数がそれらを推定するために効果的な方法であるかもしれない。
【００３７】
図3は発明の一実施例に従って、有効な多カテゴリ分類システムを得るために一組の２進のSVM分類機を訓練する過程のコントロールフローチャートを示す。各カテゴリは過程300の中で独自に処理される。処理はステップ301およびステップ302で始まり、処理するいくつかのカテゴリがあるかどうか決定する。そうだとすれば、事前に定義された評価基準(例えば、アルファベット順、例の最大のNo.など)に従って、次のものが選ばれる。代わりに、すべてのカテゴリを処理されたならば、トレーニングの過程はステップ311で終わる。ステップ304では、現在のカテゴリに関する例の数が閾値を超えているかどうかの決定がなされる。この閾値のための適切な値はタスク特定であるが、典型的な値は5-100である。例の数がこの予め定められた閾値よりも少ないならば、ステップ305において、処理は不十分な数のトレーニング例のため取り除かれたカテゴリのリストにカテゴリを加える。ステップ305の後、カテゴリはステップ306により取り除かれ、処理はステップ302で次のカテゴリのために繰り返される。例の数が閾値を超えるか等しいならば、発明の一実施例に従って上で図2に関して説明されたように、このカテゴリのために２進のSVM分類機を最適化するための手順を実行することにより、処理はステップ200で続く。
【００３８】
最適化がいったん完了すると、それは最適化が成功したかどうかに関して指示を返す。ステップ307は、最適化が成功していたならばステップ309へコントロールを渡し、またはそれが成功しなかったならステップ308に渡す。ステップ308では、システムはこのカテゴリが成功裏に最適化されなかったリストに記録する。このリストはステップ305によって維持されたものと異なっている。リストを更新した後に、カテゴリはステップ306によって取り除かれ、処理は上で説明されたステップ302の次のカテゴリのために繰り返す。
【００３９】
最適化が成功したならば、ステップ309はクラスメンバーシップの確率になるように２進のSVM分類機の出力を較正する関数を最適化する。この処理はすべての実数から範囲(0，1)に点数の領域を変換するS字状関数を使用して実行される。S字状関数は技術のそれらに知られている(例えば、Bishop1，Platt1，Sollich1，Dumais1参照)が、便利のために以下に書かれている。
【００４０】
1／(1＋e-As)
変数sは２進のSVM分類機の点数であり、eは自然対数の底であり、AはS字状関数のスロープを調整するために最適化されるパラメタである。当業者はこの式がPlatt1，Sollich1およびDumais1で説明される式と異なることに注意するだろう。1つのより少ない自由度があるので、それは異なっている。明確に、S字状のオフセットを調整するために、追加バイアス項がない。
【００４１】
二項分布を最適化する効率的な方法は当業者に知られている。例えば、Bishop1，Platt1参照。一実施例では、ステップ309の手順は、Platt1で説明された２次パラメタBが使用されないことを除いて、Platt1で説明されたように二項分布を最適化する方法を実行する。したがって、Bにかかわるすべての計算またはその導関数が取り除かれる。二項分布のスロープだけを最適化するための変更された擬似コードに関する1つの例が付録 2として添付される。これらのタイプの擬似コードは技術で知られている。例えば、Platt1参照。
【００４２】
発明の他の実施例では、上で議論したように分類機トレーニングの完成の後に、結果としての分類機は新しいテキストオブジェクトを分類するために採用され、分類機は予め指定された値tを超えた閾値で最高N点数を返す。Nとtの両方が呼の時点で供給される。カテゴリと確率のアレイが呼者に返される。
【００４３】
他の実施例では、誤分類コストを調整するか、または分布の先の情報を加えるために、分類システムのユーザはこれらの調整を実行するために周知の技術を実施することができ、従ってその後、各カテゴリのために容認閾値(例えば、上で議論したパラメタt)を調整することができる。模範的方法は各クラスのために前の確率とコストマトリクスを構成し、この前とコストマトリクスによりクラス確率推定値を乗算し、結果としてのクラス点数マトリクスを生成することを含む。例えばBishop1を参照。
【００４４】
ステップ310で、上で議論されたようなクラスメンバーシップ確率になるようにSVM分類機の出力を較正した後に、処理は現在のカテゴリを成功裏に最適化されたカテゴリのリストに追加する。この3番目のリストは上で説明されようにステップ305と308で発生するリストと異なっている。このリストを更新した後に、処理はステップ302で次のディレクトリ上で繰り返される。最終的にステップ311で、過程300は図4に関して以下でさらに詳細に議論するようにステップ404に動くことによって終わる。図4は発明の一実施例に従って多クラス分類問題を始めるコントロールフローチャートを示す。一組のカテゴリが利用可能であり、各カテゴリの一組の例が利用可能であると仮定し、それらはステップ401でシステムに入力される。次に例はステップ402でタスクの特定の方法を使用して“特徴”に変換される。例えば、タスクがテキスト文書を分類することを含むならば、各特徴は唯一の語であることができ、特徴の値はそれぞれの語が文書に現れる回数である。ステップ403では、例のデータのグローバルな特性が考慮に入れられて、変換と選択された特徴に使用される。特徴を変換して選択するための模範的方法は以下にさらに詳細に議論する。
【００４５】
ステップ403が完了した後に、発明の一実施例に従って上で図3に関して説明されたように、処理は多クラストレーニング手順を実行するためのステップが実行されるステップ300に動く。このトレーニング手順が完了した後に、処理はステップ404として終わる。
【００４６】
図5は発明の一実施例に従って単一の２進のSVM分類機を訓練するコントロールフローチャートを示す。これをする手順は当業者によく知られており、例えば、Dumais1，Joachims1，Platt2，Hearst1，Keerthi1およびJoachims2で徹底的に議論される。処理はステップ501で始まる。ステップ502では、カテゴリの特定の特徴選択と変換が実行される。例えばDumais1で議論されたような特徴選択のための模範的方法は、共通の情報（Mutual Information）、情報利得(Information Gain)、クロスエントロピイ（Cross Entropy）および主成分分析（Principal Component Analysis）を含んでいる。特徴変換のための模範的方法は、例えば、Dumais1とJoachims1で議論されたテキスト分類のために尺度化する逆文書頻度（Inverse Document Frequency (IDF) ）である。当業者に知られている別の特徴変換技術は、すべての特徴値がより公正に同等にするゼロ平均値と単位変化を有することを意味するZ-点数にすべての特徴値を変換することである。例えば、これはBishop1で議論される。
【００４７】
上で説明された特徴選択と変換手順がいったん完了すると、結果はカテゴリ特定の特徴ベクトルとして表される。それらは採用されたカテゴリ特定の特徴選択と変換のためにオリジナルな特徴ベクトルと異なっている。例えば、テキスト分類に関する文脈では、特徴ベクトル(例えば、唯一の語) は、対応するIDF値によって語頻度を分割することにより変換されるかもしれない。一実施例では、例えば、ベクトルの多くの要素が非ゼロ値を有するとき、コンピュータの効率を高めるために、希薄なベクトル表現の代わりに稠密なベクトルを使用して、特徴ベクトルの内部表現を変えることは便利である。ステップ502の結果に基づくカテゴリ特定の特徴ベクトルのこの構成はステップ503で実行される。ステップ504はSVMに関して最大マージン超平面を発見するための手順を実行する。これをする方法は当業者に知られており、Dumais1，Platt2，Joachims1，Joachims2，Keerthi1，およびHearst1参照。最終的に、ステップ505で解(例えば、最大マージン超平面)は返され、コントロールは図2のステップ205で再開する。
【００４８】
図6に関するコントロールフローチャートは、発明の一実施例に従ってテキスト多クラス分類問題を開始するための模範的手順と方法を示す。現在の実施例はC++に書かれていて、その結果、コントロールフローは呼び出し手順を通して管理される。好ましい実施例では、データ構造はRAMと補助記憶装置(例えば、ハード・ディスク・ドライブ)の両方に記憶される。
【００４９】
一実施例では、発明はテキスト分類領域で使用されるかもしれない。好ましい実施例では、テキスト分類機は語表現(例えば、多項表現) のバッグを使用し、そこでは各特徴が唯一の語であり、特徴の値は文書の中でそれが起こった回数である。特徴はそれらの技術にありふれたそれらの逆文書頻度に従って再スケーリングされる。次に、特徴ベクトルが各特徴ベクトルについてL2ノルム=1.0のように再スケーリングされ、ここにL2ノルムは特徴ベクトルの大きさを表す。この技術もまた、当業者によく知られている。例えば、Platt1，Dumais1，Joachims1参照。特徴ベクトルは希薄なベクトルとして記憶されるが、生成された最終的な重さベクトルが稠密ベクトル(即ち、ほとんど非ゼロ値を持っているベクトル)として記憶される。
【００５０】
一組のカテゴリが利用可能であり、そして、各カテゴリのための一組の例のテキストオブジェクト(例えば、テキストファイル)が利用可能であると仮定して、それらはステップ601でシステムに入力される。これは各カテゴリについて“オン-ディスク”ディレクトリを定義して、それらが属する各ディレクトリにテキスト文書を入れることにより行われる。次に、C++プログラムはディレクトリツリーを移動し、メモリに全体の組のディレクトリとファイルをロードして各ファイルを処理する。ツリー構造はあらゆるテキスト文書をあらゆるカテゴリに関連づけながら作成される。ステップ602では、各例の文書は、例えばJoachims1，Joachims2，Platt1，Dumais1，およびHearst1で説明されるように当業者に知られている“語のバッグ”方法を使用して語頻度ベクトルに変換される。一実施例では、全体の例の組で少なくとも二度現れないすべての語がステップ603で取り除かれる。ステップ604では、残っている語についてのIDF値の表が当業者に知られている方法を使用して構築される。例えば、Dumais1，Joachims1参照。最終的に、多クラストレーニング手順300は、図3に関して上で説明されたように多クラス分類のための一組のSVM分類機を構築するために使用される。
【００５１】
図3で例証されて、上で議論したサブルーチンステップの完成の後に、手順は、処理600に制御を返し、ステップ605で終わる。この手順は次に、ディスクか他のメモリに訓練されたパラメタを保存して、プログラム制御を外部のソフトウェアプログラム(例えば、Windows NT(C)などのオペレーティングシステム)に返す。
【００５２】
図7は発明の一実施例に従って単一のテキスト分類の2進のSVM分類機を訓練するのに用いられる模範的手順を示す。テキスト分類のためのこの手順は、図5に表現されるより一般的な手順500の特定の実施例である。したがって、一実施例では、204-500-205までのステップは204-700-205までのコントロールフローにより取り替えられる。
【００５３】
ステップ702において、それらが正のカテゴリで持っている共通の情報（Mutual Information）の量に従って、特徴は格付けされる。これは特徴がクラスメンバーシップをいかによく予測するかを表す。ステップ703では、共通の情報の最高量を有する特徴の予め定められた数(例えば、1,000)が保たれ、残っている特徴は使用されない。ステップ704は、1,000エントリーで稠密ベクトルを構成し、選択された1,000の特徴のために値を記憶する。ステップ705では、1,000の語の各特徴値が、ステップ604で組立てられたIDF表における対応する語のIDF値により乗算される。ステップ706は、1のL2ノルムを持つように特徴ベクトルを再スケーリングする。これは各特徴値の二乗の合計の平方根により各特徴値を分割することにより行われる。
【００５４】
ステップ707では、L2ノルムのソフトマージン線形SVMのための最大マージン超平面が得られる。双対(例えば、正と負)コストファクタを有するSVMを最適化する1つの方法がPlattのSequential Minimal Optimization(SMO)手順に基づくアルゴリズムである。例えば、Platt2，Dumais1参照。一実施例では、よく知られている技術に従って、アルゴリズムの収束速度とコンピュータの効率を高めるために変更がなされる。例えば、Keerthi1参照。さらに、テキスト分類に関する文脈では、線形カーネルは計算上効率的であって、かつ正確であるように思える。したがって、一実施例では、分類機は最適化手順を高速にするためにSMO手順の内部に当業者に知られている変更を使用する。例えば、Platt2参照。この手順は、各サポートベクトルのために線形係数だけを維持するのと対照的に、メモリに明白な重さベクトルを維持することを含む。線形カーネルが使用されているならば、この最適化は利用可能である。
【００５５】
本発明の一実施例では、方法は、トレーニング集団を使用してホールドアウト集団のF1判断基準推定値をξαF1判断基準推定値と結合することにより、ステップ205で学習的判断境界の品質を推定し、ここにF1判断基準推定値は精度と再現(また知られているように、統計におけるType IとType II誤り) の間の調和平均である。Joachims2に記述されたξαF1判断基準は潜在的に誤分類されたトレーニング例の数を計算することを含む。これらはトレーニング集団における誤分類であるか超平面への接近である例であり、その結果、“同様な”新しい例が誤分類される十分な見込みがあるだろう。技術の完全な記述のためにJoachims2を参照。これらの2つの推定値は加重平均を使用して結合される。各推定値の重さは推定値を計算するために使用された文書の数に等しく、したがって、結果は両方の推定値を作成するのに使用された文書の総数によって分割される。
【００５６】
好ましい実施例では、この品質判定基準はステップ205で正および負のクラスの両方について作成される。他の実施例では、ステップ206は2つの推定値間の調和平均を算術平均と比較することによって実行される。相対的な差が0.05より大きいならば、それは不十分な解であると考えられ、差がこの閾値よりも小さいならば、許容できる解であると考えられる。
【００５７】
本発明の一実施例に従って、プログラムは産業および学問の標準テキスト分類データセットで実行された。このデータセットはロイター（Reuters）21578と呼ばれ当業者に知られている。特に、テストとトレーニング分割を発生させるために、Mod-Apte分割が訓練に使用され、現在の実施例のための性能を得る。Dumais2によって発表された結果は以下の表に提供される。また、含まれているのは本発明の一実施例に従って得られた結果である。
【００５８】
【表１】
2006511000.tif 000004
上の表１はロイター21578mod-apte分割のための分類精度-再現ブレークイーブンポイントを提供する。記載された各カテゴリのブレークイーブンポイントはカテゴリの精度と再現のためのブレークイーブンポイントである。“トップ10”結果の平均はマイクロ平均された精度と再現を使用して測定された結合(多クラス)判断関数の性能のためのブレークイーブンポイントである。
【００５９】
上で説明されたように、発明は確かに効率的に情報(例えば、文書)の多クラス分類を実行する改良された方法とシステムを提供する。当業者は、好ましい実施例の上の記述が模範的のみであり、発明は上述された技術の変更または変化で実行されるかもしれないことを認識するであろう。当業者は慣例の実験だけを使用して、ここに記述された発明の特定の実施例に対する多くの均等物を知り、または確かめることができるだろう。そのような変更、変化および均等物は、以下の請求項で示されるように本発明の精神と範囲の中にあると考えられる。
【００６０】
【表２】
2006511000.tif 000005
2006511000.tif 000006
【００６１】
【表３】
2006511000.tif 000007
2006511000.tif 000008
【図面の簡単な説明】
【００６２】
【図１】本発明に従って使用されるかもしれない模範的コンピュータシステムのブロックダイアグラムの表現を示す。
【図２】発明の一実施例に従って、単一の２進SVMのコストファクタを最適化するコントロールフローチャートを示す。
【図３】発明の一実施例に従って、一組のSVM分類機を訓練するコントロールフローチャートを示す。
【図４】発明の一実施例に従って、多クラス分類問題を開始するコントロールフローチャートを示す。
【図５】発明の他の実施例に従って、単一の２進のSVM分類機を訓練するコントロールフローチャートを示す。
【図６】発明の一実施例に従って、テキスト多クラス分類問題を開始するコントロールフローチャートを示す。
【図７】発明の一実施例に従って、単一のテキスト分類の２進のSVM分類機を訓練するコントロールフローチャートを示す。
【図１】
2006511000.tif 000019
【図２】
2006511000.tif 000020
【図３】
2006511000.tif 000021
【図４】
2006511000.tif 000022
【図５】
2006511000.tif 000023
【図６】
2006511000.tif 000024
【図７】
2006511000.tif 000025
【国際調査報告】
2006511000.tif 000026