(57)【特許請求の範囲】
【請求項１】
記憶装置に格納されたコンピュータ実行可能命令をコンピュータの処理装置が実行することによって実施される、文字情報のトレーニングセットから、文字情報が所与のカテゴリに属するか否かを判断するための分類器のパラメータを生成するコンピュータ実施方法であって、前記分類器は、文字情報を、所与のカテゴリｉについての単調関数、
【数１】
0004514082.tif 000035
によって分類し、
ａ）前記トレーニングセットの各文字情報の、多数の特徴を有する特徴ベクトルを生成するステップと、
ｂ）各特徴ベクトルの特徴数を削減し、前記トレーニングセットの各文字情報の簡約済み特徴ベクトルｘを生成するステップと、
ｃ）支持ベクトルマシンを前記トレーニングセットの各文字情報でトレーニングすることにより、前記分類器のための重みベクトルｗを決定するステップと、
ｄ）前記分類器が使用する前記単調関数のパラメータＡ及びＢを、前記簡約済み特徴ベクトルｘ及び前記重みベクトルｗを適用した単調関数の出力から、ｔｉを、ｙをトレーニングの目標とし、Ｎ+を前記所与のカテゴリｉ内のトレーニングセットの文字情報の数とし、Ｎ-を前記所与のカテゴリｉ内にない文字情報の数とする、式
【数２】
0004514082.tif 000036
によって定義された目標値とし、ｎｔｅを前記トレーニングセットの数とし、ｘｉをｉ番目の入力ベクトルとし、ｙｉを、＋１または−１であるすでにわかっている結果とし、ｆを確立分布とすると、式
【数３】
0004514082.tif 000037
によって算出される、文字情報のトレーニングセットの尤度を最大化することにより決定するステップと
を備えることを特徴とする方法。
【請求項２】
前記特徴数を削減するステップは、
ｉ）Ｚｉｐｆの法則に基いて特徴数を削減するサブステップと、
ｉｉ）（ａ）相互情報、（ｂ）情報ゲイン、（ｃ）ベイズスコア、（ｄ）カイ二乗、（ｅ）相関関数、（ｆ）特異値分解からなる基準群から選択した少なくともひとつの基準に基いて、特徴の数をさらに削減するサブステップと
を含むことを特徴とする請求項１に記載の方法。
【請求項３】
コンピュータ実行可能命令を格納した記憶装置を有し、該コンピュータ実行可能命令を処理装置が実行することによって、文字情報のトレーニングセットから、文字情報が所与のカテゴリに属するか否かを判断するための分類器のパラメータを生成する装置であって、前記分類器は、文字情報を、所与のカテゴリｉについての単調関数、
【数４】
0004514082.tif 000038
によって分類し、
ａ）前記トレーニングセットの各文字情報の、多数の特徴を有する特徴ベクトルを生成する特徴ベクトル生成器と、
ｂ）各特徴ベクトルの特徴数を削減し、前記トレーニングセットの各文字情報の簡約済み特徴ベクトルを生成する特徴簡約装置と、
ｃ）支持ベクトルマシンを前記トレーニングセットの各文字情報でトレーニングすることにより、前記分類器のための重みベクトルを決定する支持ベクトルマシントレーニング装置と、
ｄ）前記分類器が使用する前記単調関数のパラメータＡ及びＢを、前記簡約済み特徴ベクトルｘ及び前記重みベクトルｗを適用した単調関数の出力から、ｔｉを、ｙをトレーニングの目標とし、Ｎ+を前記所与のカテゴリｉ内のトレーニングセットの文字情報の数とし、Ｎ-を前記所与のカテゴリｉ内にない文字情報の数とする、式
【数５】
0004514082.tif 000039
によって定義された目標値とし、ｎｔｅを前記トレーニングセットの数とし、ｘｉをｉ番目の入力ベクトルとし、ｙｉを、＋１または−１であるすでにわかっている結果とし、ｆを確立分布とすると、式
【数６】
0004514082.tif 000040
によって算出される、文字情報のトレーニングセットの尤度を最大化することにより決定する関数生成器と
を備えることを特徴とする装置。
【請求項４】
記憶装置に格納されたコンピュータ実行可能命令をコンピュータの処理装置が実行することによって実施される、文字情報が所与のカテゴリに属するか否かを判断して、該文字情報を分類するコンピュータ実施方法であって、
ａ）文字情報の特徴ベクトルを生成するステップと、
ｂ）前記特徴ベクトルの特徴数を減らし、簡約された特徴ベクトルｘを生成するステップと、
ｃ）前記簡約された特徴ベクトルｘと重みベクトルｗを、請求項１の方法によりパラメータＡおよびＢが決定された単調関数
【数７】
0004514082.tif 000041
にあてはめることによって、前記文字情報がカテゴリｉに属する確率を出力するステップであって、前記重みベクトルｗは、支持ベクトルマシントレーニング装置に適用された所定の分類を有する文字情報のトレーニングセットから決定されるステップと
を備えることを特徴とする方法。
【請求項５】
コンピュータ実行可能命令を格納した記憶装置を有し、該コンピュータ実行可能命令を処理装置が実行することによって、文字情報が所与のカテゴリに属するか否かを判断して、該文字情報を分類する装置であって
ａ）文字情報の特徴ベクトルを生成する特徴ベクトル生成器と、
ｂ）前記特徴ベクトルの特徴数を簡約し、簡約された特徴ベクトルｘを生成する特徴簡約装置と、
ｃ）前記簡約された特徴ベクトルｘと重みベクトルｗを、請求項３の装置によりパラメータＡおよびＢが決定された単調関数
【数８】
0004514082.tif 000042
にあてはめることによって、前記文字情報がカテゴリｉに属する確率を出力する分類器であって、前記重みベクトルｗは、支持ベクトルマシントレーニング装置に適用された所定の分類を有する文字情報のトレーニングセットから決定される分類器と
を備えることを特徴とする装置。
【発明の詳細な説明】
【０００１】
（§１．発明の背景）
（§１．１  発明の属する技術分野）
本発明は、例えばテキスト情報などのオブジェクトが、１つの特定のカテゴリーあるいは複数のカテゴリーに属するか否かを判定することに関する。この判定は、例えばテキスト分類器などの分類器により行なわれる。また、本発明は、(テキスト)分類器に対して適切なパラメータを決定することにより(テキスト)分類器を構築することに関する。
【０００２】
（§１．２  関連する技術）
（§１．２．１  テキスト分類器の必要性）
コンピュータのような機械の有用性と性能を高めるために、オブジェクトを分類(あるいは認識)することの重要性がますます高まっている。例えば、コンピュータでは、手書きのまたは走査された数字や文字を分類するために光学的な文字認識を行なったり、顔や指紋、戦闘機などを分類するためにパターン認識を行なったり、あるいは音や声などを分類するために音声認識を行なったりしている。
【０００３】
また、例えば、コンピュータのテキストファイルや文書のような文字情報オブジェクトを分類するためのマシンが必要とされている。テキスト分類の応用は多様であり重要である。例えば、テキスト情報のオブジェクトを、予め定められたクラスまたはカテゴリの階層に編成するためにテキスト分類を用いることができる。このようにすることにより、特定の主題に関連するテキスト情報のオブジェクトを見出す(あるいは探り出す)ことを容易に行なうことができる。テキスト分類により、適切な文字情報オブジェクトを、適切な人あるいは適切な場所に送り届けることができる。このようにして、情報サービスを行なえば、様々な主題(例えば、ビジネス、スポーツ、株式市場、フットボール、特定の企業、特定のフットボールチームなど)に関する文字情報オブジェクトを様々な異なる興味を持つ人々に送り届けることができる。テキスト分類を利用すれは、文字情報オブジェクトをフィルタして、望まないテキスト情報(望まない、必要としないeメールで、ジャンクeメールあるいはスパムと呼ばれるものなど)にわずらわされずに済む。以上に述べたいくつかの例からも分かるように、テキスト分類には、目をみはる、重要な応用分野が数多くある。
【０００４】
（§１．２．２  従来知られているテキスト分類方法）
このセクションにおいては、これまでに知られているテキスト分類方法について、いくつかの例を紹介する。さらに、これらの分類方法の、確認されている限界あるいは想定される限界についても紹介する。まず、以下の§１．２．２．１において、ルールベースの分類について論じる。次に、§１．２．２．２において、学習要素と性能要素を使用する分類について論じる。
【０００５】
（§１．２．２．１  ルールベースによる分類）
ある場合には、テキスト情報は、何らかの容認されている論理に基づいて絶対的に確実な分類がなされなければならない。このようなタイプの分類を行なうには、ルールベースによるシステムを用いることができる。基本的に、ルールベースによるシステムは次のような形のプロダクションルールによる。
もし、（条件）であれば、（事実）である。
【０００６】
この条件としては、テキスト情報がある語や句を含んでいるか、ある構文を持っているか、あるいは、ある属性を持っているかなどである。例えば、テキスト情報に、「終わる」、「ナスダック」という言葉と数字を含んでいれば、この情報は「株式市場」に関するテキストととして分類される。
残念ながら、ルールベースによるシステムは使いにくいことが多い。特に、測定値または入力値（あるいは特性や特徴）の数が多く、条件やルールの組合わせの論理が複雑になる場合や、可能性のあるクラスの数が大きくなる場合にはそうである。テキスト情報は多様な特性や複雑な意味を持っているので、単純な応用以外には、ルールベースによるシステムをテキスト分類に応用することは、上記の制約により適当でない。
【０００７】
過去約１０年にわたって、他のタイプの分類法が次第に用いられるようになった。これらの分類器は、ルールベースによる分類器が採用するような、静的で事前定義された論理を用いるものではないが、多くの応用例において、ルールベースによる分類器よりも優れた性能を示している。このような分類器については、以下の§１．２．２．２において論じるが、典型的なものとしては、学習要素と性能要素を含んでいる。このような分類器には、ニューラルネットワーク、ベイズネットワーク、支持ベクトルマシンなどがある。これらの分類器については、それぞれ一般的に知られているところであるが、読者の便宜のために、以下に簡単に紹介する。
【０００８】
（§１．２．２．２  学習要素と性能要素を持つ分類器）
前セクションの最後に述べた通り、学習要素と性能要素を持つ分類器は多くの応用例において、ルールベースによる分類器よりも優れた性能を示している。繰返して述べると、これらの分類器には、ニューラルネットワーク（読者の便宜のために、以下の§１．２．２．２．１に紹介する）と、ベイズネットワーク(読者の便宜のために、以下の§１．２．２．２．２に紹介する)と、支持ベクトルマシン(読者の便宜のために、以下の§１．２．２．２．３に紹介する)とがある。
【０００９】
（§１．２．２．２．１  ニューラルネットワーク）
ニューラルネットワークは、基本的には、ニューロンと呼ばれる同一の作用要素が多層状に階層をなして配列されたものである。各ニューロンは１個またはそれを超える数の入力を受け入れることができるが、出力は１個しかできない。各ニューロンに対する入力は係数によって重み付けが行なわれる。ニューロンの出力は、一般的に、重み付けが行なわれた入力値とバイアス値の合計の関数である。この関数は、また、活性化関数ともいわれ、通常S字形関数である。すなわち、活性化関数はＳ字形であり、入力が正または負の無限大に近づくに従って、単調増加して一定の値(例えば、＋１、０、−１など)に漸近する。このＳ字形関数と、重みおよびバイアス値によって、入力シグナルに対する応答、すなわち興奮の度合が決まるのである。
【００１０】
階層的なニューロンの配列において、ある層のニューロンの出力が次の層の１個またはそれを超えるニューロンの入力として伝達される。典型的なニューラルネットワークにおいては、一つの入力層と、別個の二つの層、すなわち、一つの入力層と、中間ニューロン層と、出力ニューロン層とが存在する。入力層の節はニューロンでないことに注意しなければならない。入力層の節は、基本的には入力が1個のみであって、その入力を処理せずに次の層に入力する。例えば、２０×１５のピクセルの配列の数字文字の認識にニューラルネットワークを使用するとすると、入力層は３００ニューロン(すなわち、入力の各ピクセルに対して１個)となり、出力配列は１０ニューロン(すなわち、数字１０個毎に１個)となる。
【００１１】
ニューラルネットワークは、一般的に、連続する二つのステップにより行なわれる。第一のステップでは、ニューラルネットワークの初期設定が行なわれ、既知の出力値(あるいは分類)を持つ入力によりトレーニングが行なわれる。ニューラルネットワークのトレーニングが行なわれると、それを利用して未知の入力を分類することができる。ニューラルネットワークは、ニューロンの重みとバイアスを、通常ガウス分布により生成する無作為な値に設定することにより、初期設定することができる。次いで、ニューラルネットワークは、既知の出力値(あるいはクラス)を持つ連続した入力によりトレーニングを受ける。トレーニング用入力がニューラルネットワークに入力されると、各トレーニングパターンに対するニューラルネットワークの出力が、既知の出力に近づくか、対応するようにニューロンの重みとバイアスが調整される (例えば、既知の逆伝播法（back-propagation technique）によって)。基本的には、重み空間における勾配降下（a gradient descent）により、出力エラーを最少化する。このようにして、連続したトレーニング入力を学習することにより、局部的な重みとバイアスが最適化される。すなわち、エラーが最少になるように重みとバイアスが、調整される。
【００１２】
実際には、最適解に収束するまでシステムのトレーニングを行なうことはできない。そうでなければ、システムがトレーニング過剰の状態となって、トレーニング用のデータに特化され過ぎて、トレーニング用の入力とはある程度異なる入力の分類を満足に行なうことができなくなってしまうからである。このように、トレーニングの期間中、しばしば、一連の実証データについてシステムの検定を行なう。システムにより実証検定の結果がこれ以上改善されない所に達した時にトレーニングを終了する。
【００１３】
トレーニングが完了すると、トレーニング期間中に決められた重みとバイアスに従って、未知の入力を分類するためにニューラルネットワークを使用することができる。ニューラルネットワークが、未知の入力を確実に分類することができる場合には、出力層のニューロンの出力の一つが、他の出力よりも格段に高いということである。
【００１４】
重みとバイアスの項が発散するのを防ぐために、アルゴリズムは小規模のステップにより進められる。さらに、ニューラルネットワークのトレーニングに使用する逆伝播(勾配降下（a gradient descent）)法(back-propagation technique)は、比較的遅いものである。(例えば、シュッツらによる次の文献参照。"A Comparison of Classifiers and Document Representations for the Routing Problem"、International ACM SIGIR Conference on Research and Development in Information Retrieval、セクション5(1995)、以後シュッツの文献という。)したがって収束の速度は遅い。また、隠された層のニューロンの数を演繹的に決定することは容易ではない。したがって、隠された層のニューロンの数を決定するには、時間をかけて、何回も実験することが必要である場合が多い。
【００１５】
（§１．２．２．２．２  ベイズネットワーク）
ニューラルネットワークは以上の通りであるが、次にベイズネットワークについて簡単に説明する。
通常、ベイズネットワークでは、データ(例えば、入力された特性ベクトル)と予測(例えば、分類)との中間値として、仮説を使用する。データ("P(仮説|データ)")が与えられた場合、各仮説に対する確率を推定することができる。仮説の予測を重み付けするための経験的確率を使用して、仮説から予測を行なう。データＤが与えられた時の、予測Ｘの確率は次のように表すことができる。
【００１６】
【数１５】
0004514082.tif 000002
【００１７】
ここで、Hiはｉ番目の仮説である。Ｄ（Ｐ（Hi｜Ｄ））が与えられた時に、Hiの確率が最大となるような最も可能性がある仮説Hiは、最大経験的確率(または、HMAP)と呼ばれ、次のように表すことができる。
【００１８】
【数１６】
0004514082.tif 000003
【００１９】
ベイズの公式を使って、データDが与えられた場合の仮説Hiの確率は、次のように表すことができる。
【００２０】
【数１７】
0004514082.tif 000004
【００２１】
データDの確率は一定である。したがって、HMAPを求めるためには、分子を最大にしなければならない。
【００２２】
分子の最初の項は仮説ｉが与えられた時に観測されるであろう確率を表している。第二の項は与えられた仮説ｉに当てられる経験的確率を表す。
【００２３】
ベイズネットワークには、変数と変数間の指向されたエッジが含まれ、これによって有向型の非輪状グラフ（ＤＡＧ）が定義される。各変数は、互いに独立した状態の任意の有限値を取ることができる。親変数Ｂ１、・・・Ｂｎを持つ変数Aのそれぞれに対して、確率表（Ｐ（Ａ｜Ｂ１、・・・Bn)が添付されている。ベイズネットワークの構造では、親変数が与えられた場合、各変数は非子孫（non-descendants）に対しては条件付きで独立であるという前提をコード化している。
【００２４】
ベイズネットワークの構造が既知であり、変数を観測することができると仮定すれば、条件付きの確率表のセットを学習しさえすればよい。これの表は、一連の学習用見本の統計を利用して直接算定することができる。構造は既知であるが1部の変数が隠れている場合には、上述したニューラルネットワークの学習と類似の方法で学習を行なう。
【００２５】
次に、簡単なベイズネットワークの例を示す。変数“MML”は、“我が家の芝生の湿度”を表すものとし、“濡れている”状態および"乾いている"状態を取ることができるとする。また、“MML”変数は、親変数として、それぞれ“はい”と“いいえ”の状態を持つ、“雨”と“我が家のスプリンクラーが働いている”とを取るものとする。他の変数として“MNL”は、“隣の芝生の湿度”を表すものとし、“濡れている”状態および“乾いている”状態を取ることができるとする。“MNL”変数は、“雨”を共通の親変数として持つことができるとする。この例において、予測は我が家の芝生が“濡れている”か“乾いている”かである。この予測は次の二つの仮定に依存する。（ｉ）もし、雨が降れば、我が家の芝生は（ｘ１）の確率で濡れるであろう。（ｉｉ）もし、我が家のスプリンクラーが働けば、我が家の芝生は（ｘ２）の確率で濡れるであろう。雨が降ったのか我が家のスプリンクラーが働いたかの確率は、他の変数により決まることになる。例えば、隣の芝生が濡れていて、隣の家にはスプリンクラーがないとすれば、雨が降った確率の方が高い。“濡れた芝生”によるベイズネットワークの例は、ジェンセンの“An Introduction to Bayesian Networks”Spinger-Verlag社、ニューヨーク(1997)の22ページ〜25ページに紹介されている。
【００２６】
これまでに論じたように、ベイズネットワークにおける条件付き確率表も、ニューラルネットワークの場合と同じようにトレーニングを行なうことができる。経験的な知識が与えられれば、学習課程を短縮できるので有利である。しかし、残念なことに、条件付き確率に対する経験的な確率は、通常、不明である。このような場合には、一定の経験的が使用される。
【００２７】
（§１．２．２．２．３  支持ベクトルマシン）
支持ベクトルマシン（“ＳＶＭ”）も、トレーニング可能な分類器の一つである。例えば、テキスト分類のような応用に対しては、ＳＶＭの方が単純なベイズネットワークよりも正確な分類ができるといわれている。（例えば、次のヨアヒム文献を参照。“Text Categorization with Support Vector Machines: Learning with Many Relevant Features”、LS-8, Report 23、ドルトムント大学、コンピュータサイエンス学部、1997年11月。）また、例えば、手書きの文字を読取るような応用に対しては、ＳＶＭの方がニューラルネットワークよりも正確であるといわれている。（例えば、次のルカンらの文献を参照。“Learning Algorithms for Classification: A Comparison on Handwritten Digit Recognition”, Neural Networks: The Statistical Mechanics Perspective, Oh et al. (Eds.) World Scientific （１９９５）、２５１ページ〜２７６ページ。）しかし、残念なことに、ＳＶＭは、単純なベイズネットワークよりも、トレーニングに長い時間を必要とするといわれている。ＳＶＭをより効率的なやり方で構築する（あるいはトレーニングする）方法と装置が、ジョン・プラットにより1998年4月6日に出願された米国特許出願第09/055,477号「支持ベクトル分類器を構築する方法と装置」に開示されている。これは、参照することによりこの特許に組み込まれているものとする。
【００２８】
ＳＶＭは、当業者には知られているが、読者の便宜のためにその理論と運用法について説明する。
【００２９】
分類するオブジェクトは、いくつかの特性により表すことができる。例えば、分類するオブジェクトが二つの特性で表されるとすれば、それは、2次元空間内の点として表すことができる。同様にして、分類するオブジェクトがn個の特性で表され、それを特性ベクトルとすれば、それは、ｎ次元空間内の点として表すことができる。ＳＶＭの最も単純な形では、あるクラスに入っているオブジェクトの特性ベクトルの点と、そのクラスに入っていないオブジェクトの特性ベクトルの点を分けるｎ次元空間の平面（超平面とも呼ばれる）を定義する。ある数の超平面を定義することによりある数のクラスを定義することができる。トレーニングを受けたＳＶＭが定義する超平面では、超平面から“クラス内”および"クラス外"それぞれの最も近い点（“支持ベクトル”とも呼ばれる）までの距離（ユークリッド距離とも呼ばれる）を最大にする。支持ベクトルと超平面との距離が最大になるような超平面を求めるのである。そのようにすれば、入力のノイズによる影響を受け難くなる。超平面（または超表面）はトレーニングの過程で定義されるが、これについては以下の§４．２．１．４．１において記述する。
【００３０】
（§１．２．２．２．４  学習要素および性能要素を持つテキスト分類用の分類器の試み）
上述したように、ルールベースによる分類は最も単純なテキスト分類にしか適用することができないが、学習要素および性能要素を持つシステム（学習マシンとも呼ばれる）をテキスト分類に使用することを試みることには重要な意義がある。重要な意義があると思われる試みについては以下の§１．２．２．２．４．１から§１．２．２．２．４．３で述べる。
【００３１】
（§１．２．２．２．４．１  特性ベクトルのサイズ）
テキスト分類のために学習マシンをトレーニングするに際して、一連の学習見本が使用される。それぞれの学習見本には文字情報オブジェクトに関連する特性ベクトルが含まれている。ある種の応用では、このような特性ベクトルは108オーダーの特性を持っている。ある単語が文書の中に存在するかしないかが特性であると考えると、多量の特性が容易に発生する。あるコーパスのすべての単語が特性になり得ると考えれば、独立した特性が何百万にもなってしまう。例えば、ウェブページには多くの独立したストリングがあり、何百万もの特性が発生される。単語や句の二つあるいはそれを超える組み合わせをを考慮したり、単語の出現頻度を考慮したりすれば、特性の数は更に増大する。特性ベクトルの特性の数は、いわゆる"特性簡約（feature reduction）"あるいは"特性選択（feature selection）"により縮小することができ、その結果、元の特性ベクトルの特性のサブセットを持つ特性ベクトルが生成される。実際、一部の人達は、学習マシンによるテキスト分類器が使用できるようになるためには、特性選択が必要であると考えている。
【００３２】
これまでに知られている特性選択技術としては、ＤFスレッショルディング（例えば、ヤンとピーターソンによる次の文献参照。“A Comparative Study of Feature Selection in Text Categorization”, International Conference on Machine Learning、1997、以後ヤン・ピーターソの文献という）、カイ二乗検定（例えば、シュッツの文献参照）、項強度基準（例えば、ヤンとウィルバーによる次の文献参照。“Using Corpus Statistics to Remove Redundant Words in Text Categorization”, Journal of the American Society for Information Science, Vol. ４７, No.５、１９９６、３５９ページ〜３６９ページ、以後ヤン・ウィルバーによる文献という）、情報ゲイン基準（例えば、ヤン・ウィルバーによる文献参照）、カイ二乗測定値の二乗根である相関係数（例えば、ヌグらによる文献：“Feature Selection, Perceptron Learning, and a Usability Case Study for Text Categorization”, Proceedings of SIGIR ９７、１９９７、６７ページ〜７３ページ参照）、ならびに、直行するインデックシング変数の低次元線形結合により特性を表す技術である、特異値分解（SVD）を使用するレイテント・セマンティック・インデックシング（LSI）（例えば、シュッツの文献参照）などがある。
【００３３】
しかし、一部の人達は特性選択を行なうべきでないとしている。例えば、テキスト分類にＳＶＭを使用することを支持するヨアヒムの文献では、特性選択を行なうと情報のロスが発生するので、性能が劣化すると結論している（例えば、ヨアヒムの文献の3ページ参照）。さらに、ヨアヒムの文献では、ＳＶＭが高次元特性空間において充分に一般化されるので、特性選択の必要はなくなり、テキストのカテゴリー化が容易になると結論づけている(例えば、ヨアヒムの文献の１１ページ参照) 。このようにして、この分野における一部の人達は、ＳＶＭをテキスト分類に使用する場合に、特性選択が有用であると考えているが、場合によっては、特性選択が採用されていない。
【００３４】
（§１．２．２．２．４．２ 過剰適合）
学習マシンをレーニングする場合には、特性ベクトルのセットからなるトレーニング用見本に基づいて行なわれる。一般的に、学習マシンの性能は、トレーニングに使用する見本の数にある程度影響される。トレーニング用見本が多数ある場合であっても、あるカテゴリに属するトレーニング用見本は少ないかもしれない。
【００３５】
多くの学習マシンは、Ｓ字曲線関数(すなわち、S字型をした単調関数)を使用し、入力(例えば、未知のオブジェクトの特性ベクトル)に基づいて出力(例えば、あるオブジェクトがあるカテゴリに入っているか否かという決定)を決定する。残念ながら、あるカテゴリに対するトレーニング用のデータがほとんど存在しない場合には、Ｓ字曲線関数のパラメータを充分に定義することができない。したがって、あるカテゴリに対して充分なトレーニング用のデータが存在しない場合には、Ｓ字曲線関数が過去のデータに過剰適合することがある。このような過剰適合が発生すると、学習マシンの出力の確からしさが失われるので、避けなければならない。
【００３６】
（§１．２．２．２．４．３  分類の速度）
トレーニングに要する時間と応答(例えば分類)に要する時間は、学習マシンの二つの重要な特性である。例えば、テキストの分類に学習マシン、特にＳＶＭが有用であることを支持する人達でも、ＳＶＭの学習時間が他の方法のそれよりも長時間を要することを認めている。この問題については、ジョン・プラットにより１９９８年４月６日に出願され、共通の譲受人に権利が与えられる、「支持ベクトル分類器構築のための方法と装置」という題名の特許出願第09/055,477号(引用することにより特許の一部として組み込まれるものとする)に説明されているので、ここでは細部に立入らない。
【００３７】
次に、応答(分類)時間の問題が残る。この発明の発明者は、ヨアヒムの論文で論じられているＳＶＭ分類器が、次の式に従って未知のオブジェクトを分類できるといることを前提として考えている。
【００３８】
【数１８】
0004514082.tif 000005
【００３９】
ここで、Ｏ＝分類の出力、ｎｔｅ＝トレーニング用見本の数、αｉ＝トレーニング用見本ｉのラグランジュ乗数、ｘｉ＝トレーニング用見本ｉの特性ベクトル、ｘｊ＝未知のオブジェクトｊの特性ベクトル、ｙｉ＝トレーニング用見本ｉの既知の出力であり、（１）式を使用して出力を決定するには、比較的時間を要する。当然のことながら、より大きな速度を持つ分類器が望まれることになる。
【００４０】
シュッツによる文献では、最大尤度とニュートン−ラフソン法による数値最適化を用いて導き出される重みベクトル(β)を利用するロジスティック回帰分類器について論じている。この分類器は、ヨアヒムの論文で述べられているＳＶＭ分類器よりも大きな速度でオブジェクトを分類できると考えられているが、このようにして決定された重みベクトル(β)から、最良の結果を得ることはできないと考えられる。
【００４１】
（§２．  発明の概要）
この発明は、分類器に対するパラメータを生成することと、文字情報オブジェクトのようなオブジェクトを分類するという、二つの基本的な機能の内の少なくとも一つの機能を果すことができる。
【００４２】
基本的に、分類器に対するパラメータは、一連のトレーニング見本に基づいて生成される。一連の特性ベクトルは、一連のトレーニング見本から生成される。特性ベクトルのセットの特性は縮小することができる。生成されるパラメータには、定義された単調な(例えばＳ字曲線)関数と重みベクトルを含むことができる。重みベクトルは、ＳＶＭトレーニング(あるいはその他の既知の技術)により決定することができる。単調な(例えばＳ字曲線)関数は、最適化法により定義することができる。
【００４３】
テキスト分類器には、重みベクトルと定義された単調な(例えばＳ字曲線)関数を含むことができる。基本的に、この発明によるテキスト分類器の出力は、次のように表すことができる。
【００４４】
【数１９】
0004514082.tif 000006
【００４５】
ここで、Ｏｃ＝カテゴリｃに対する分類出力、ｗｃ＝カテゴリｃに関する重みベクトルパラメータ、ｘ＝未知の文字情報オブジェクトに基づいた（簡約された）特性ベクトル、ＡおよびＢは、単調な（例えばＳ字曲線）関数の調節可能なパラメータ、式（２）からの出力の計算は、式（１）からの出力の計算よりも迅速に行なうことができる。
【００４６】
分類するオブジェクトの形式によっては、分類器は、（ｉ）情報オブジェクトを特性ベクトルに変換し、（ｉｉ）特性ベクトルをより少ない要素を持つ簡約された特性ベクトルに縮小することができる。
【００４７】
（§４.  発明の詳細な説明）
この発明は、テキスト分類器のような新しい分類器と、このような(テキスト)分類器の構築に関する。以下に述べる記述は、当業者がこの発明を構築し、使用できるようにすることを目的とするものであり、特定の応用オブジェクトとそれに対する必要事項について述べるものである。ここに開示する実施形態に様々な変形を加えることが可能であることは、当業者であれば容易に理解できるところであり、以下に提示される一般的な原理は他の実施形態や応用にも適用できるものである。したがって、この発明は、示されている実施形態により制限されるものではない。
【００４８】
この明細書で用いる表記法として、ベクトルは、頭部に矢印をつけるか太字の活字で示している。
【００４９】
この発明により実行できる機能については、以下の§４．１で述べる。次に、典型的な方法とその方法を実行する構造について以下の§４．２で述べる。
【００５０】
（§４．１  機能）
この発明は、二つの基本的な機能の内の少なくとも一つの機能を実行することができる。第一の基本的な機能、すなわち分類器に対してパラメータを発生する機能は、以下の§４．１．１に述べる。第二の基本的機能、すなわちテキストを分類する機能は、以下の§４．１．２に述べる。
【００５１】
（§４．１．１  分類器に対するパラメータの生成）
基本的に、分類器に対するパラメータは、一連のトレーニング見本に基づいて生成される。この発明は、一連のトレーニング見本から一連の特性ベクトルを生成する機能を持っている。また、この発明は、一連の特性ベクトルの特性を減少させる機能を持っている。発生されるパラメータには、定義された単調な(例えばＳ字曲線)関数と重みベクトルを含んでいる。重みベクトルは、ＳＶＭトレーニングによって決定することができる。単調な(例えばＳ字曲線)関数は、最適化法により定義することができる。この最適化法には、過剰適合を避けるために特殊な目標関数を使用することができる。
【００５２】
（§４．１．２  テキストの分類）
この発明により、テキストを分類することができる。テキスト分類器は、重みベクトルと定義された単調な(例えばＳ字曲線)関数を含むことができる。基本的に、テキスト分類器の出力は、次のように表すことができる。
【００５３】
【数２０】
0004514082.tif 000007
【００５４】
ここで、Ｏｃ＝カテゴリｃに対する分類出力、ｗｃ＝カテゴリｃに関する重みベクトルパラメータ、ｘ＝未知の文字情報オブジェクトに基づいた（簡約された）特性ベクトル、ＡおよびＢは、単調な（例えばＳ字曲線）関数の調節可能なパラメータ、繰返して言えば、式（２）からの出力の計算は、式（１）からの出力の計算よりも迅速に行なうことができる。
【００５５】
分類するオブジェクトの形式によっては、分類器は、（ｉ）情報オブジェクトを特性ベクトルに変換し、（ｉｉ）特性ベクトルをより少ない要素を持つ簡約された特性ベクトルに縮小することができる。
【００５６】
（§４．２  典型的な構造と方法）
分類器のパラメータを生成する典型的な行程と方法について以下の§4.2.1でで説明する。テキストを分類する典型的な行程と方法については§4.2.2で説明し、最後に、記述した行程と方法を実施するための典型的な装置(あるいは構造)について§４．２．３で説明する。
【００５７】
（§４．２．１  分類器のパラメータを生成する行程と方法）
図１は、この発明によりテキスト分類器のパラメータを発生するための行程とデータを示す図である。一連のトレーニング用データ１１５(例えば、文字情報オブジェクトとカテゴリラベル)が準備されれば、トレーニング用セットの各文字情報オブジェクトに対応する特性ベクトルが、特性抽出行程(より一般的には特性エクストラクタ)１１０により生成される。特性ベクトルは記憶場所１２５に記憶することができる。典型的な特性抽出行程に点いては、以下の§４．２．１．１において説明する。
【００５８】
図３は、特性ベクトル３１０およびカテゴリベクトル３２０を含むトレーニングオブジェクトの典型的なデータ構造３００を示す。特性ベクトル３１０は、文字情報オブジェクトから導かれた特性(あるいは属性)に対応するフィールド３１２を含んでいる。この例においては、特性ベクトル３１０が、“ｎ”個の特性を持っている。特性ベクトル３１０の特性(あるいは属性)フィールド３１２は、文字情報オブジェクトから導かれた対応する値を含んでいる。例えば、テキストオブジェクトが２５０万語の語彙から選ばれたものと仮定すると、特性ベクトル３１０は、それぞれのフィールドが語彙中の一語に対応する２５０万のフィールドを持つことができる。あるフィールドに記憶された値は、語彙中の特定の語が文字情報オブジェクトの中に出現する回数とすることができる。
【００５９】
文字情報オブジェクトの特性ベクトルの値は、多くの場合ゼロであるから、スパースベクトル技法を使用して、大きな一つの配列ではなく、二つの小さな配列によって特性ベクトルを表すことができる。第一の配列は、ゼロでない値を持つ特性にインデックスを付ける。第二の配列には、第一の配列によりインデックスを付けられた特性値を含む。例えば、図３Ｂを参照して、特性ベクトルの内、第１、第５０、第５７、第１０１、および第２２０番目の特性だけがゼロでない値を持っているとすると、スパースデータ構造３１０'を、図3に示した特性ベクトル310の代りに用いることができるであろう。スパースデータ構造３１０'は、ゼロでない特性に対するインデックス(例えば、１、５０、５７、１０１、２２０)を含む第一の配列３５０とインデックスを付けられた特性の数値を含む第二の配列３６０とを含む。図３Ｃは、他のスパースデータ構造３１０''で、ゼロでない特性に対するインデックス付けを行なうフィールドと、ゼロではない特性に対応する数値フィールドを交互に持っている。
【００６０】
カテゴリベクトル３２０は、“ｍ”個の異なるカテゴリに対応するフィールドを含んでいる。カテゴリベクトル３１０のフィールド３２２は、文字情報オブジェクトが特定のカテゴリに属するか否かを示す２値数を持つことができる。文字情報オブジェクトは、一つを超えるカテゴリに属することができる。
【００６１】
トレーニング用セットの各文字情報オブジェクトに対応するデータ構造３００は、記憶領域１２５に記憶することができる。特性簡約行程(あるいは、より一般的には、特性簡約機能)１２０は、記憶領域１２５或いは特性抽出行程１１０からデータ構造３００を受入れ、特性ベクトル３１０の特性を、“ｎ”から“z”に縮小する。ここで、“z”は“n”よりも小さな数であって、“n”よりも3桁小さい数となる場合がある。図４に示すように、特性簡約行程１２０によって、新たなデータ構造４００が生成される。データ構造４００は、データ構造３００のカテゴリに対応するカテゴリベクトル３２０を含む。また、データ構造４００は、特性簡約行程１２０において比較的重要な特性であると決定されたトレーニング用セットの文字情報オブジェクトの特性(あるいは属性)に対応するフィールド４１２を持つ、簡約された特性ベクトル４１０を含む。また、特性簡約行程１２０は、特性ベクトルの“n”個のフィールド４１２のどの“z”個のフィールドが比較的重要であると考えられるかを定義する簡約された特性のセットを生成する。典型的な特性簡約行程１２０については、以下の§４．２．１．２で論じる。
【００６２】
これまで、各文字情報オブジェクトは単独の、比較的大きい特性ベクトルの配列であるとして記述してきたが、実際には上述したようにスパース配列技法を使用して、各文字情報オブジェクトが、一つの大きな配列ではなく、二つの小さな配列によって表されるようにする。図４Ｂの例を参照して、第１と第５７番目の特性が重要でないと考えられると、スパースデータ構造４１０'が結果として得られる。スパースデータ構造４１０'は、選択された、ゼロでないインデックス(例えば、５０、１０１、２２０)を含む第一の配列と、第一の配列４５０によりインデックス付けされた特性の値を含む第二の配列４６０を含む。図４Ｄは、他のスパースデータ構造４１０''を示すものであって、選択されたゼロでない特性に対応するインデックス付けを行なうフィールドと数値フィールドを交互に持っている。
【００６３】
オプションとして(破線で示されている)２進数化行程１５０を使用して、トレーニング用セットの各オブジェクトの簡約された特性ベクトルの各フィールド４１２の各値を２値数に変換することができる。この数値の２値数への変換は、各フィールド４１２に対して、予め定められた(あるいは誘導された)しきい値をあてはめることにより行なうことができる。したがって、フィールド４１２のそれぞれに対して、しきい値が異なってもよい。もちろん、単一のしきい値をすべてのフィールド４１２にあてはめることもできる。図５は、２値数５１０を含む簡約された特性ベクトルを表すデータ構造を示す。ベクトル５１０は、図４に示したデータ構造４００のベクトル４１０と同じ“ｚ”個のフィールドを持つ。しかし、この場合には、各フィールド５１２は、より一般的な数値ではなく、２値数（例えば１ビットで表された）を含んでいる。データ構造５００のカテゴリベクトル３２０は、データ構造３００および４００のものと同じである。典型的な２進数化の行程については、以下の§４．２．１．３で述べる。
【００６４】
図５Ｂにおいて、選択されたゼロでない特性１０１および２２０がしきい値を通過するが、ゼロでない特性５０は通過しない場合には、スパースデータ構造５１０’は、しきい値を通過する選択された、ゼロでない、インデックス(例えば、１０１と２２０)を含む第一の配列５５０と、インデックス付けされた特性の数値を含む第二の配列５６０を含む。図５Ｃに示したように、しきい値を通過する、選択された、ゼロでない２進数化された特性は、すべて“１”であるので、インデックス配列５５０のみを含むスパースデータ構造５１０”'を代りに使用することができるであろう。
【００６５】
当然、他の量子化器を使用して、２値数化の代りにq (ここでq>2) 値数化を行なうことができる。
【００６６】
簡約された特性ベクトル(あるいは、２進数化された、簡約された特性ベクトル)は、記憶装置１３５に記憶することができる。
【００６７】
一般的なテキスト分類器は、“ｍ”個の異なるカテゴリの各々に対する分類器を含む。重みベクトルパラメータと、調整可能なパラメータAおよびBを持つ単調な（例えばＳ字形）関数は、“ｍ”個の分類器の各々に対して決定されるということを思い起こされたい。したがって、“ｍ”個の行程１４０（これは、支持ベクトルマシン用トレーニング機能と関数発生器を含むことができる）は、簡約された特性ベクトル（あるいは、２進数化された、簡約された特性ベクトル）を、記憶装置１３５あるいは特性簡約行程１２０（あるいは２進数化行程150）から受入れる。図1には、平行する“ｍ”個の行程１４０が示されているが、単一の行程１４０を使用して、“ｍ”個の連続したカテゴリを処理することもできる（あるいはｐの行程をｍ／ｐ回実施する）。何れにせよ、重みベクトルパラメータと単調な（例えばＳ字形）関数が、“ｍ”個のカテゴリのそれぞれに対して生成される。テキスト分類器のパラメータを生成する典型的な行程については、以下の§４．２．１．４にて述べる。
【００６８】
（§４．２．１．１  特徴抽出）
図１から、特徴抽出行程１１０が、１セットの特徴ベクトル（たとえば、データ構造３００に格納されたもの）を、１セットのトレーニング用文字情報オブジェクトから生成することを、想起されたい。
【００６９】
図６は、典型的な特徴抽出処理１１０’の流れ図である。ステップ６１０で、文字情報オブジェクトへのインデックスとして使用されるＣＯＵＮＴ値が、１に設定されることによって初期化される。次に、ＣＯＵＮＴ値によってインデックス付けされたような、文字情報オブジェクトが、ステップ６２０に示すように受け入れられる。ステップ６３０に示すように、ＦＥＡＴＵＲＥ＿ＣＯＵＮＴ値が１に初期化され、ＦＥＡＴＵＲＥ＿ＣＯＵＮＴ値によってインデックス付けされ、数値（ＦＥＡＴＵＲＥ＿ＣＯＵＮＴ）が０に初期化される。次に、ステップ６４０に示すように、ＣＯＵＮＴ値によってインデックス付けされ、ＦＥＡＴＵＲＥ＿ＣＯＵＮＴ値によってインデックス付けされ、文字情報オブジェクトの数値（ＦＥＡＴＵＲＥ＿ＣＯＵＮＴ）が決定される。たとえば、５番目の特徴が「スポーツ」という意味であり、「スポーツ」が第１の文字情報オブジェクトにおいて３回現れる場合、オブジェクト（１）の数値（５）が３である。ステップ６５０および６６０に示すように、所与のオブジェクトの各特徴についての値が決定される。ステップ６７０および６８０に示すように、あるオブジェクトの特徴値が決定された後、次のオブジェクトの特徴値が決定される。すべてのオブジェクトに対するすべての特徴値が決定されたとき、行程１１０’が戻りノード６９０を介して終了する。
【００７０】
繰り返しによって、ステップ６４０が文字情報オブジェクトの特徴値を決定する。この決定を、以下のように実行することができる。テキスト解析器を使用して、各文字情報オブジェクトを成分トークンに解析することができる。トークンは、語、文字、内部句読点記号など、いかなるも文字構成要素でもあり、空白（白い）スペースまたは先頭（後続）句読点記号によって別のこのような構成要素から分離される。構文上の句、および、時間および日付について正規化された表現も、テキスト解析モジュールによって抽出される。ドメイン特有の特徴を、適切なように定義して抽出することもできる。各特徴は、語、句または文字のグループ化を定義することができる。したがって、特徴ベクトルが、各文字情報オブジェクトに関連付けられる。
【００７１】
インデックス配列および配列値（たとえば、図３Ｂを参照）を有するか、あるいは、交替索引フィールドおよび値フィールドを有する配列（たとえば、図３Ｃを参照）を有する、スパースデータ構造が使用される場合、ステップ６４０で、数値（ＦＥＡＴＵＲＥ＿ＣＯＵＮＴ）がゼロでない場合、（ｉ）インデックス配列の次の要素（または次の索引フィールド）がＦＥＡＴＵＲＥ＿ＣＯＵＮＴに設定され、（ｉｉ）配列値の次の要素（または次の値フィールド）が数値（ＦＥＡＴＵＲＥ＿ＣＯＵＮＴ）に設定される。
【００７２】
（§４．２．１．２  特徴簡約（高レベル））
上述のように、特徴ベクトルは文字情報オブジェクトに関連付けられ、多数の特徴要素を含むことができる。テキスト分類器のトレーニングをより実現可能にするため、特徴ベクトルをより少ない要素に簡約することができる。図７は、本発明で使用することができる、典型的な特徴簡約行程１２０’（「特徴簡約」は「特徴選択」と呼ばれることもある）の、より高いレベルの流れ図である。最初に、ステップ７１０に示すように、本発明は、カテゴリーに依存しないの特徴簡約ステップ（ＺＩＰＦまたは度数など）を使用することができる（公知であるが、読者の便宜上、ＳＳ４．２．１．２．１で以下に論じる）。次いで、ステップ７２０に示すように、カテゴリーに属する特徴簡約技術（そのうちのいくつかを、ＳＳ４．２．１．２．２で以下に論じる）を実行することができる。次いで、処理１２０’が、戻りノード７３０を介して終了する。
【００７３】
（§４．２．１．２．１  カテゴリーに依存しないの特徴簡約）
いくつかのトレーニング例文字情報オブジェクトの特徴ベクトルの行列を、収集幅度数統計量（collection-wide frequency statistics）を適用することによって縮小することができる。Ｚｉｐｆの法則は当技術分野で公知であり、テキストにおける異なる語の分布に関係し、本質的に、語の順序（ｒ）および度数（ｆ）が定数（Ｃ）であり、すなわち、度数および出現の数（Ｎ）の積（ｆ＊Ｎ＝Ｃ）であるように、（ｒ＊ｆ＝Ｃ）であると述べる。つまり、多数の語が、収集において一度だけ出現し、その数の半分が２度出現し、その数の３分の１が３回出現するというようになる。少ない回数だけ出現する語は、新しい項を分類することにおいてあまり有用ではないものと規定され、これらはしばしば省略される。スペクトルの他の端において、しばしば出現する語は、カテゴリーの間でよい弁別を提供する可能性が高くなく、時として省略される。Ｚｉｐｆ度数しきい値を適用することによって、簡約された特徴ベクトルが、各文字情報オブジェクト・トレーニング例について生じる。Ｙａｎｇ−Ｐｅｄｅｒｓｅｎの記事によって提案された文書度数しきい値処理(the document-frequency thresholding)は、このＺｉｐｆ選択に類似している。しかし、Ｙａｎｇ−Ｐｅｄｅｒｓｅｎの記事において論じられた方法は異なる選択基準を使用し、もっとも度数の高い項のみを保つ。
【００７４】
（§４．２．１．２．２  カテゴリーに属する特徴簡約）
トレーニング例の文字情報オブジェクトの特徴ベクトルが、たとえばＺｉｐｆの法則など、カテゴリーに依存しないの特徴簡約技術に基づいて簡約された後、これらをさらに、カテゴリーに属する特徴簡約技術によって簡約することができる。このようなカテゴリーに属する特徴簡約は、ＳＳ４．２．１．２．２．１で以下に論じる相互情報技術、またはＳＳ４．２．１．２．２．２で以下に論じる情報ゲイン技術など、公知の技術を使用することができる。カイ二乗、相関係数、およびＳＶＤ（すべて公知であり、本明細書では論じない）など、他の公知のカテゴリーに属する特徴簡約技術を、代りに使用することができる。カテゴリーに属する特徴簡約は、ＳＳ４．２．１．２．２．３で以下に論じるベイズ・スコア技術など、メーカ独自の技術に従って実行することもできる。
【００７５】
（§４．２．１．２．２．１  相互情報）
相互情報は、特徴がクラスに関連付けられる範囲、この場合はテキストカテゴリーの測度である。高い相互情報測度（high mutual information measures）を提示する特徴は、クラスのよい識別器であり、したがって選択される。典型的な実施形態では、特徴を語にすることができ、クラスを類別にすることができる。このような場合、所与のカテゴリーｃiにおける所与の特徴（ｆi）についての相互情報「ＭＩ」、たとえば語などを、以下のように表すことができる。
【００７６】
【数２１】
0004514082.tif 000008
【００７７】
ただし、Ｐ（ｆ+ｃ+）は、文書が特徴ｆを有してカテゴリーｃに属する確率であり、Ｐ（ｆ-ｃ+）は、文書が特徴ｆを有さないが、カテゴリーｃに属する確率であり、Ｐ（ｆ+ｃ-）は、文書が特徴ｆを有するが、カテゴリーｃに属さない確率であり、Ｐ（ｆ-ｃ-）は、文書が特徴ｆを有さず、カテゴリーｃに属さない確率である。
【００７８】
図９は、特徴「ｆ」９５０およびカテゴリー「ｃ」９６０の双方向分割表９００を示す。
【００７９】
各文字情報オブジェクトが、以下の４個の特性のうち１つを提示する。すなわち、（ｉ）特徴「ｆ」９５０を有してカテゴリー「ｃ」９６０に属し（ｆ+ｃ+９１０）、（ｉｉ）特徴「ｆ」９５０を有するがカテゴリー「ｃ」９６０に属さず（ｆ+ｃ-９２０）、（ｉｉｉ）特徴「ｆ」９５０を有さないがカテゴリー「ｃ」９６０に属し（ｆ-ｃ+９３０）、あるいは（ｉｖ）特徴「ｆ」９５０を有さずカテゴリー「ｃ」９６０に属さない（ｆ-ｃ-９４０）。Ａが、特性ｆ+ｃ+９１０を提示する文字情報オブジェクトの数であり、Ｂが、特性ｆ+ｃ-９２０を提示する文字情報オブジェクトの数であり、Ｃが、特性ｆ-ｃ+９３０を提示する文字情報オブジェクトの数であり、Ｄが、特性ｆ-ｃ-９４０を提示する文字情報オブジェクトの数であり、Ｎが文字情報オブジェクトの合計数である場合、相互情報（ＭＩ）を以下のように表すことができる。
【００８０】
【数２２】
0004514082.tif 000009
【００８１】
特徴（たとえば、語）を、相互情報が最高であるこれらの特徴（語）に簡約することができる。
【００８２】
トレーニング用集成資料が与えられると、相互情報が各ユニークな項について計算される。相互情報がある所定のしきい値未満であるこれらの項を、特徴ベクトルから除去することができる。別法として、特徴の数が所定の数「ｘ」に簡約される場合、ｘ個の最高相互情報値を有する特徴が保たれ、他の特徴は考慮されない。
【００８３】
（§４．２．１．２．２．２  情報ゲイン）
情報ゲインは、文書における項の存在または不在を知ることによって、カテゴリーの予測について得られた情報のビット数を測定する、項選択基準である。二元分類作業（すなわち、カテゴリーにあるもの（ｃ+）対カテゴリーにないもの（ｃ-））および２つの特徴値（すなわち、特徴存在（ｆ+）対特徴不在（ｆ-））の場合、特徴（ｆ）の情報ゲイン（Ｇ（ｆ））は以下のように定義される。
【００８４】
【数２３】
0004514082.tif 000010
【００８５】
ただし、Ｐ（ｃ+）は、文書がカテゴリーｃに属する確率であり、Ｐ（ｃ-）は、文書がカテゴリーｃに属さない確率であり、Ｐ（ｆ+）は、文書が特徴ｆを含む確率であり、Ｐ（ｆ-）は、文書が特徴ｆを含まない確率であり、Ｐ（ｆ+ｃi）は、文書が特徴ｆを有して、カテゴリーｃiに属する確率であり、二元分類ではｉが値＋および−を持つようになり、Ｐ（ｆ-ｃi）は、文書が特徴ｆを有さず、カテゴリーｃiに属する確率であり、二元分類ではｉが値＋および−を持つようになる。
【００８６】
この測度を、Ｍ個の可能なカテゴリーを合計することによって、ｍ配列の分類に汎用化することができる。
【００８７】
トレーニング用集成資料が与えられると、情報ゲインが各ユニークな特徴について計算される。情報ゲイン値がある所定のしきい値未満であるこれらの特徴を、特徴ベクトルから除去することができる。別法として、特徴の数が所定の数「ｘ」に簡約される場合、ｘ個の最高情報ゲイン値を有する特徴が保たれ、他の特徴は考慮されない。
【００８８】
（§４．２．１．２．２．３  ベイズ・スコア）
特徴ベクトルを、ベイズ・スコア（ＢＳ）に基づいて簡約することができる。ベイズ・スコアの決定が、特許出願第０８／２４０，０１９号、「Ｍｅｔｈｏｄ  ｆｏｒ  Ｉｍｐｒｏｖｉｎｇ  Ｂｅｌｉｅｆ  Ｎｅｔｗｏｒｋｓ」（参照により本明細書に組み込む）に記載されている。ｉ番目の特徴ｆのベイズ・スコア（ＢＳ）を、以下のように定義することができる。
【００８９】
【数２４】
0004514082.tif 000011
【００９０】
ただし、Γ(n)＝nΓ(n-1)であり、すべてのn>0、Γ(1)＝１、Γ(n+1)＝n！、ｎ＝０，１，２，...である。
【００９１】
Ａは、特性ｆ+ｃ+９１０を提示する文字情報オブジェクトの数であり、Ｂは、特性ｆ+ｃ-９２０を提示する文字情報オブジェクトの数であり、Ｃは、特性ｆ-ｃ+９３０を提示する文字情報オブジェクトの数であり、Ｄは、特性ｆ-ｃ-９４０を提示する文字情報オブジェクトの数であり、Ｎは文字情報オブジェクトの合計数である。
【００９２】
特徴数が所定の数「ｘ」に簡約される場合、ｘ個の最高ベイズ・スコアを有する特徴が保たれ、他の特徴は考慮されない。ベイズ・スコアしきい値を使用して、特徴の数を簡約することもできる。
【００９３】
（§４．２．１．３  簡約された特徴ベクトルの２進数化）
簡約された特徴ベクトルにおいて保持された値を、１つのしきい値に、あるいは、特徴に対応するしきい値に適用して、簡約された特徴ベクトルの値を２進数化することができる。別法として、特徴ベクトルにおける値を直接分類器に適用することができ、あるいは、ｑに関する（ただしｑ＞２）コードとして、量子化を通じて符号化することができ、これはニューラル・ネットワークの技術分野で周知である。
【００９４】
（§４．２．１．４  分類パラメータ生成）
前述のステップ（すなわち、特徴抽出、特徴簡約、および２進数化）を、ＳＶＭテキスト分類器など、テキスト分類器のパラメータをより容易に決定可能にするための前処理ステップと見なすことができる。本質的に、分類器は、簡約された特徴ベクトルｘを有する文字情報オブジェクトを、以下に基づいて分類する。
【００９５】
【数２５】
0004514082.tif 000012
【００９６】
ただし、ｆ（ｚ）はｚの単調（たとえば、Ｓ字状）関数であり、ｗは重みベクトルである。
【００９７】
したがって、分類器は重みベクトル・パラメータを有し、その決定が§４．２．１．４．１で以下に記載され、調整可能なパラメータを有する単調関数を有し、その決定が§４．２．１．４．２で以下に記載される。したがって、図８に示した、分類エンジンのためのパラメータを生成するための典型的な処理１４０’の流れ図を参照すると、ステップ８１０に示すように、重みベクトルｗが決定され、ステップ８２０に示すように、単調関数（およびその調整可能なパラメータ）が決定される。行程１４０’が、戻りノード８２０を介して終了される。
【００９８】
（§４．２．１．４．１  重みベクトル決定）
各カテゴリーの分類器が重みベクトル・パラメータを有する。各カテゴリーについて、重みベクトル・パラメータは、支持ベクトルマシンをトレーニングに使用する方法によって、生成することができる。上述のように、かつ当技術分野で公知であるように、支持ベクトルマシン（または「ＳＶＭ」）を、既知の分類を有する既知のオブジェクトでトレーニングして、超平面または超表面を定義することができ、これがｎ次元の特徴ベクトル空間における点を分離し、これらはカテゴリーにあるものおよびカテゴリーにないものである。１対の調整可能なパラメータ、ｗ（「重みベクトル」）およびｂ（「しきい値」）を、既知の分類ｙを有するすべてのトレーニング・データｘが以下の制約を満たすように、定義することができる。
【００９９】
【数２６】
0004514082.tif 000013
【０１００】
ただし、ｉ＝１，．．．，トレーニング例の数であり、ｘiはｉ番目の入力ベクトルであり、ｗは重みベクトル・パラメータであり、ｂはしきい値パラメータであり、ｙiはｉ番目のトレーニング例に関連付けられた既知の分類であり、例が「クラスにある」場合は＋１、トレーニング例が「クラスにない」場合は−１である。
【０１０１】
方程式（７）および（８）の不等号条件を、方程式の両側にｙおよび＋１または−１を掛けて両側から１を引くことによって、以下の不等号条件に結合することができる。
【０１０２】
【数２７】
0004514082.tif 000014
【０１０３】
方程式（７）の等価部分が保持する点が、超平面ｘi・ｗ＋ｂ＝１上にあり、正規のｗで、原点までの垂直距離（１−ｂ）／｜｜ｗ｜｜であり、ただし｜｜w｜｜がベクトルｗのユークリッド・ノルムである。同様に、方程式（８）の等価部分が保持する点が、超平面ｘi・ｗ＋ｂ＝−１上にあり、原点までの垂直距離（−１−ｂ）／｜｜ｗ｜｜である。したがって、限界は両方の距離の和、すなわち２／｜｜ｗ｜｜である。したがって、｜｜w｜｜2を最小化することによって、方程式（９）の制約を条件として、最大限界を提供する超平面を決定することができる。
【０１０４】
したがって、ＳＶＭをトレーニングすることで、制約付き最適化（たとえば、最小化）の問題が提示される。つまり、１つまたは複数の制約を条件として、関数が最小化される（「目的関数」と呼ばれる）。当業者は、制約付き最適化問題を解く方法（たとえば、Fletcherによるテキスト「Practical Methods of Optimization」２nd de．，pp．195-224，John Wiley & Sons (1987)を参照）に精通しているが、読者の便宜上、関連した方法を以下に紹介する。
【０１０５】
すべての制約を満たす点が「実現可能点(feasible point)」と呼ばれ、「実現可能領域(feasible region)」に位置する。制約付き最適化（たとえば、最小化）問題は、実現可能な下り方向を有していない実現可能点によって解かれる。したがって、制約付き最小化問題を解くための方法が、値のシーケンスが極小に収束するように、たびたび反復的される。
【０１０６】
当業者は、ラグランジュ乗数が等価制約付き最適化問題を制約なし極化問題に変換する方法を提供することを認識している。ラグランジュ乗数（α）を使用して、制約ｇ（ｘ）を条件として、関数ｆ（ｘ）の極値を見つけることができる。すなわち、０＝∇ｆ（ｘ）＋α∇ｇ（ｘ）、ただし∇は勾配関数である。したがって、ｆ（ｗ）＝｜｜ｗ｜｜2かつｇ（ｗ）＝ｙi（ｘi・ｗ＋ｂ）−１である場合、ラグランジュ関数は以下のようになる。
【０１０７】
【数２８】
0004514082.tif 000015
【０１０８】
ただし、「ｎｔｅ」はトレーニング例の数、結果である。
【０１０９】
数理計算法の文献から知られるように、「双対性」の概念により、数理計算法問題の代替公式化の提供が可能となり、これはたとえば計算的に好都合である。方程式（１０）を最小化することは、「アルファ」が負でないものでなければならないという制約を条件として、「一次」（または最初の）問題と呼ばれる。「双対」（すなわち、変換された）問題は、ｗおよびｂに関するLpの勾配がゼロになり、「アルファ」が負でないものでなければならないという制約を条件として、方程式（１０）を最大化する。この変換は、「ウルフ双対（Wolfe dual）」として公知である。双対制約を、以下のように表すことができる。
【０１１０】
【数２９】
0004514082.tif 000016
【０１１１】
方程式（１１）および（１２）の条件を、方程式（１０）へ代用すると、以下のラグランジュ関数を生じる。
【０１１２】
【数３０】
0004514082.tif 000017
【０１１３】
双対二次計画問題の解を、ラグランジュ関数双対問題Lpを最大化することによって決定することができる。
【０１１４】
したがって、双対ラグランジュ関数二次計画問題を解くことによって、支持ベクトルマシンをトレーニングすることができる。トレーニング・セットの各例ｉ毎にラグランジュ乗数αiがある。αiがゼロより大きい点が「支持ベクトル」である。これらの支持ベクトルは、決定境界にもっとも近いところに存在し、したがって決定境界からの限界を定義するので、トレーニング・セットの重要な要素である。
【０１１５】
残念ながら、方程式（１３）の二次計画問題は、方程式（７）および（８）の問題よりもより管理可能な形式による制約付きの最適化問題しか表現しない。制約付き共役上り勾配(constrained conjugate decomposition ascent)、投射方法(projection methods)、Ｂｕｎｃｈ−Ｋａｕｆｍａｎ分解(Bunch-Kaufman decomposition)、および内側点方法(interior points methods)などの数値方法を使用して、二次問題を解くことができる。これらの数値方法は、特に多数の例ｉがトレーニング・セットにあるときに、ありふれているものではないと言えば十分である。方程式（１３）を参照すると、二次問題を解くことに、「ｎｔｅ」行列による「ｎｔｅ」が含まれる（ただし、「ｎｔｅ」はトレーニング・セットの例の数である）。
【０１１６】
二次計画問題を、チャンキング・アルゴリズム(a chunking algorithm)で解くこともできる。Ｖｌａｄｉｍｉｒ  Ｖａｐｎｉｋは、ＳＶＭの開発の功績があるとされており、「チャンキング」と呼ばれる反復トレーニング方法を導入した。ＳＶＭをトレーニングする「チャンキング」方法は当業者によって理解されているが、読者の便宜上、本明細書に説明する。各ステップで、以前のステップからのゼロでないラグランジュ乗数、および、キューン−タッカー条件を破るいくつかの最悪のトレーニング例の結合からなる下位の問題が解かれる。これらのステップは、すべての例がキューン−タッカー条件を満たすまで繰り返される。このようにして、トレーニング例の数の平方のサイズの行列で演算する代りに、各ステップの行列が、ゼロでないラグランジュ乗数の数の順序で、平方される。行列がより小さいので、アルゴリズムがより高速にすることができる。チャンキングによりトレーニングＳＶＭが扱いやすくなるが、なおいくつかの応用例には低速過ぎる。たとえば、ゼロでないラグランジュ乗数の数がなお、ある応用例では数千に増大することがある。二次問題がなお、数値二次計画技術で解かれ、各反復には時間がかかる。
【０１１７】
ＳＶＭ向けのよりよいトレーニング・アルゴリズムが、Ｅ．Ｏｓｕｎａ  ｅｔ  ａｌ．，の論文「Ａｎ  Ｉｍｐｒｏｖｅｄ  Ｔｒａｉｎｉｎｇ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｓｕｐｐｏｒｔ  Ｖｅｃｔｏｒ  Ｍａｃｈｉｎｅｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＥＥＥ  ＮＮＳＰ  ’９７（１９９７年９月）（以下で「Ｏｓｕｎａの方法」と呼ぶ）で紹介されたようである。Ｏｓｕｎａの方法は、ゼロでないラグランジュ乗数の数で増大する行列ではなく、固定サイズの行列を格納する。固定数のラグランジュ乗数が、あらゆるステップで最適化される。新しい各ステップで、古いラグランジュ乗数の１つが考慮から除去され、出力がキューン−タッカー条件を破る新しい例が追加される。Ｏｓｕｎａの論文は、Ｏｓｕｎａの方法が解に収束するように、二次問題があらゆるステップで減少するという証明を提供する。しかし、Ｏｓｕｎａの方法はなお、各ステップで数値の解を必要とするので不都合である。これは解に収束するが、Ｏｓｕｎａの方法は数値二次計画問題全体を使用して、キューン−タッカー条件を破る１つのラグランジュ乗数を単に「固定」する。
【０１１８】
重みベクトルを決定するためのより高速な方法は、Ｊｏｈｎ  Ｐｌａｔｔによる米国特許出願第０９／０５５，４７７号、「Ｍｅｔｈｏｄｓ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｂｕｉｌｄｉｎｇ  ａ  Ｓｕｐｐｏｒｔ  Ｖｅｃｔｏｒ  Ｍａｃｈｉｎｅ  Ｃｌａｓｓｉｆｉｅｒ」、１９９８年４月６日出願で開示された方法を使用することによるものであり、これを参照により本明細書に組み込む。Ｐｌａｔｔの方法のうち最初に開示された方法（「ＱＰ１」とも呼ばれる）では、しきい値ｂがゼロ（０）である。最初に、トレーニング・セットの各例に対応するラグランジュ乗数が初期化される。たとえば、すべてのラグランジュ乗数を、ゼロ（０）に設定することによって初期化することができる。
【０１１９】
トレーニング例のセットからの各トレーニング例について、解がこの例について最適化されるかどうかが決定される。各例の最適さが、キューン−タッカー条件が破られるかどうかを決定することによって、検査される。解が最適でない場合（たとえば、キューン−タッカー条件が破られる場合）、ｎ番目のトレーニング例のための新しいラグランジュ乗数が決定される。具体的には、ｎ番目のトレーニング例のための新しいラグランジュ乗数を、以下の式によって決定することができる。
【０１２０】
【数３１】
0004514082.tif 000018
【０１２１】
方程式（１４）では、キューン−タッカー（ＫＴ）エラーを以下のように表すことができる。
【０１２２】
【数３２】
0004514082.tif 000019
【０１２３】
方程式（１４）では、識別器がカーネル関数であり、線形支持ベクトルマシンの場合、これはｎ番目のトレーニング例の特徴ベクトルｘのドット積である。
【０１２４】
次いで、新しいラグランジュ乗数が以下のように制限（あるいはクリップ）される。
【０１２５】
【数３３】
0004514082.tif 000020
【０１２６】
不等制約が満たされるようにする。
【０１２７】
１セットのトレーニング例を通じた掃引が完了した後、いずれかのラグランジュ乗数が掃引中に変化したかどうかが決定される。そうである場合、このとき、他の例がキューン−タッカー条件を破る可能性がある。具体的には、ラグランジュ乗数が調節されるので、ＳＶＭの分離した超平面（または超曲面）が変化する。したがって、データを通じた別の掃引が実行される。ラグランジュ乗数が変更されなかった場合、すべての例がキューン−タッカー条件を満たさなければならず、ＱＰ１処理が終了される。
【０１２８】
最初の掃引が、トレーニング・セットのすべての例を処理する。ラグランジュ乗数が変更されたと仮定すると、次の掃引が、トレーニング・セットの非境界例のみを処理する。後続の掃引も、ラグランジュ乗数が変化しなくなるまで、非境界ラグランジュ乗数のみを処理する。次いで、次の掃引が、トレーニング例のセット全体を処理する。ラグランジュ乗数が変更されなかった場合、処理が終了する。他方では、ラグランジュ乗数が変更された場合、処理が上述のように継続する。当然、代替のものでは、各掃引が、トレーニング例のすべてを処理することができる。
【０１２９】
線形ＳＶＭの場合、ＳＶＭ全体の状態を、カーネルの重み付けされた和ではなく、重みベクトルとして格納することができる。この場合、ラグランジュ乗数が変更されるとき、重みベクトルが直接更新される。つまり、以下のようになる。
【０１３０】
【数３４】
0004514082.tif 000021
【０１３１】
キューン−タッカー条件は、区間演算を使用して検査することができる。すなわち、ある許容差内で条件がほぼ満たされる場合、条件が満たされる。許容差を、ｌｅ−３に設定することができる。これは、認識マシンのために十分正確にするべきであり、この方法で、ラグランジュ乗数における不必要な精度を生成する大量の計算的リソースを費やすことが防止される。
【０１３２】
入力点がスパースバイナリベクトル(sparse binary vectors)からなるとき（たとえば、分類されるオブジェクトが、多数の可能な特徴のうち相対的に少ないものを有する）、ドット積のスパース評価を使用することによって、図示の実施形態の速度を劇的に向上させることができる。すなわち、重みと入力点の間のドット積が、ゼロでない入力次元に対応する重み要素の和である。これを、以下のように表すことができる。
【０１３３】
【数３５】
0004514082.tif 000022
【０１３４】
この最適化は、線形ＳＶＭをテキスト分類のために使用するようにトレーニングするために有用である。これは、大抵のテキスト・オブジェクトが、スパース特徴ベクトルによって表現されるからである（たとえば、テキスト・オブジェクトが、特徴ベクトルについてのすべての語のうち相対的に少ないものを有する）。
【０１３５】
アルファ・ベクトルは、すべてのトレーニング例のためのラグランジュ乗数の値を含み、トレーニング・セットのサイズに等しい長さのベクトルとして格納することができる。つまり、以下のようになる。
【０１３６】
【数３６】
0004514082.tif 000023
【０１３７】
ただし、「ｎｔｅ」はトレーニング例の数である。
上述のように、大抵のラグランジュ乗数はゼロ（０）になるので、アルファ・ベクトルを、ゼロでないラグランジュ乗数の数に等しい長さの２つのベクトルとして格納することができ、一方がゼロでないラグランジュ乗数の識別（索引）を格納するもの、他方がゼロでないラグランジュ乗数の値を格納するものである。
【０１３８】
Ｐｌａｔｔの方法のうち第２に開示された方法（「ＱＰ２」とも呼ばれる）では、二次計画問題処理が、線形等価制約を条件とする（すなわち、しきい値ｂは必ずしもゼロ（０）に等しくない）。
【０１３９】
最初に、トレーニング・セットの各例に対応するラグランジュ乗数が初期化される。大抵のラグランジュ乗数がゼロ（０）になることができるので、すべてのラグランジュ乗数を、ゼロ（０）に設定することによって初期化できることを想起されたい。トレーニング例のセットからの各トレーニング例について、キューン−タッカー条件が破られるかどうかが決定される。キューン−タッカー条件が破られる場合、別の例がトレーニング・セットから選択され（以下で論じるように）、それにより、結合して最適化される１対のラグランジュ乗数を作成する。これらの例が結合して最適化されるように、新しいラグランジュ乗数を決定するための試みが行われる。これらの例が最適化されたかどうかが決定される。これらが最適化されなかった場合、別の特徴ベクトルがトレーニング・セットから選択され、それにより、別の対のラグランジュ乗数を作成する。
【０１４０】
２つのラグランジュ乗数の結合最適化の最初のステップは、変数の１つの範囲を決定することである。第１または第２の乗数のいずれかの境界を付けることができる。ここでは、第２のものが選択される。Ｌを第２のラグランジュ乗数の下限とし、Ｈを第２のラグランジュ乗数の上限とする。ｙ1を第１の例の所望の出力とし、ｙ2を第２の例の所望の出力とする。α1を第１のラグランジュ乗数の現在値とし、α2を第２のラグランジュ乗数の現在値とする。ｙ1がｙ2と同じである場合、以下の範囲が計算される。
【０１４１】
【数３７】
0004514082.tif 000024
【０１４２】
ｙ1がｙ2と反対の符号である場合、範囲が以下のように計算される。
【０１４３】
【数３８】
0004514082.tif 000025
【０１４４】
値Ｌが値Ｈと同じである場合、進行を行うことができず、トレーニング例が最適化されなかったと決定される。
【０１４５】
α2の新たに最適化された値を、以下の公式を介して計算することができる。
【０１４６】
【数３９】
0004514082.tif 000026
【０１４７】
第２のラグランジュ乗数の新しい値がＬ未満である場合、これがＬに設定される。逆に、第２のラグランジュ乗数の新しい値がＨより大きい場合、これがＨに設定される。第２のラグランジュ乗数の新たにクリップされた（あるいは制限された）値が古い値と同じである場合、最適化が可能ではなく、トレーニング例が最適化されなかったと決定される。そうでない場合、次いで、第１のラグランジュ乗数の新しい値が、第２のラグランジュ乗数のクリップされた（あるいは制限された）値から、以下のように導出される。
【０１４８】
【数４０】
0004514082.tif 000027
【０１４９】
支持ベクトルマシンが線形である場合、重みおよびしきい値が更新されて新しいラグランジュ乗数が反映され、キューン−タッカー条件の他の違反を検出することができるようにする。
【０１５０】
第２のラグランジュ乗数の対を、以下のヒューリスティック（heuristic）に基づいて選択することができる。理想的な第２のラグランジュ乗数は、結合最適化において大部分を変更する。最適化における変化への容易な近似は、第２のラグランジュ乗数における変化における分子の絶対値である。
【０１５１】
【数４１】
0004514082.tif 000028
【０１５２】
第１のラグランジュ乗数の真のエラー（Ｏ1−ｙ1）が正である場合、大きい負の真のエラー（Ｏ2−ｙ2）を有する第２のラグランジュ乗数が、結合最適化のためのよい候補となる。第１の真のエラーが負である場合、大きい正の真のエラーを有する第２のラグランジュ乗数が、最適化のためのよい候補となる。したがって、ＱＰ２処理が、第１のラグランジュ乗数の真のエラーのもっとも逆である真のエラーを有する、非境界ラグランジュ乗数（α≠０またはＣ）を探し出す。
【０１５３】
異なる例が同じ入力特徴ベクトルを有するという、いくつかの縮重した場合がある。これは、結合最適化が進行することを妨げる可能性がある。これらの冗長例をフィルタリングすることができる。別法として、ヒューリスティックの階層を使用して、第２の例を発見して、結合最適化のステップを前進させることができる。上述の第１のヒューリスティックが失敗する場合、ＱＰ２処理が、非境界ラグランジュ乗数を、結合して最適化される対の他方のラグランジュ乗数として選択する。このヒューリスティックがすべての非境界ラグランジュ乗数について失敗する場合、いずれかの他のラグランジュ乗数を、対の他方のラグランジュ乗数として選択することができる。
【０１５４】
トレーニング例のセットを通じた掃引が完了した後、１つまたは複数のラグランジュ乗数が全体のデータ・セットを通じた掃引で変化した場合、非境界ラグランジュ乗数が最適化される。他方では、掃引中にラグランジュ乗数が変化しなかった場合、すべての例がキューン−タッカー条件に従い、ＱＰ２処理が終了される。
【０１５５】
理解できるように、ＱＰ２処理が最初にトレーニング・セットのすべてのトレーニング例を通じて掃引する。ラグランジュ乗数が変更されたと仮定すると、次の掃引が、トレーニング・セットの非境界トレーニング例のみを処理する。後続の掃引も、ラグランジュ乗数が変化しなくなるまで、非境界ラグランジュ乗数のみを処理する。次いで、次の掃引が、トレーニング例のセット全体を処理する。ラグランジュ乗数が変化しない場合、処理が終了する。他方では、ラグランジュ乗数が変化する場合、処理が上述のように継続する。当然、代替方法では、トレーニング・セットのすべてのトレーニング例をあらゆる掃引で処理することができる。
【０１５６】
ラグランジュ乗数を、トレーニング例の数に対応するサイズを有する１つの配列（「完全配列」とも呼ばれる）、または、より大きいスパース配列を表す２つの配列のいずれかとして、格納することができる。
【０１５７】
１対のラグランジュ乗数を結合最適化するときに使用された、上述の実際のエラーは、ＳＶＭの実際の出力未満のＳＶＭの所望の出力（ｙi−Ｏi）である。これらの実際のエラーを、非境界（すなわち、ゼロでないか、あるいはＣでない）ラグランジュ乗数を有する例についてキャッシュすることができる。実際のエラーをキャッシュすることにより、第２の例を統合に選択することができる。
【０１５８】
線形ＳＶＭについては、線形ＳＶＭを、１セットの入力点の線形重ね合わせとしてではなく、１つの重みベクトルとして格納することができる。入力ベクトルがスパースである場合、重みベクトルへの更新を、公知のスパース方法（sparse  manner）で実施することもできる。
【０１５９】
したがって、所与のカテゴリーｃのための重みベクトルｗは、ＳＶＭを、たとえば前述（たとえば、チャンキング、ＯｓｕｎａおよびＰｌａｔｔ）の方法の１つに基づいてトレーニングすることによって、決定することができる。
【０１６０】
（§４．２．１．４．２  単調関数パラメータの決定）
上述のように、テキスト分類器は、単調(例えばＳ字型曲線)関数を使って文字情報オブジェクトを分類する。Ｓ字曲線関数は、以下のように表わすことができる。
【０１６１】
【数４２】
0004514082.tif 000029
【０１６２】
Ｓ字曲線関数の特徴は、次のように定数AとBを使って調整することができる(「調整可能なパラメータ」ともいう)。
【０１６３】
【数４３】
0004514082.tif 000030
【０１６４】
単調関数のAとBを解く方法を以下に説明する。
【０１６５】
（§４．２．１．４．２．１  最適化(最尤)）
定数A，Bは、文字情報オブジェクトのトレーニングサンプルセットに関する最尤法を使って決定できる。Ｓ字曲線をトレーニングデータにフィットさせるために、トレーニングサンプル同士が独立しているものとして、トレーニングの目標yが確率分布fによって発生される尤度の対数を計算する。尤度の対数は以下のように表わされる。
【０１６６】
【数４４】
0004514082.tif 000031
【０１６７】
ただし、ｙｉはすでにわかっている結果(+1または−1)、nteはトレーニングサンプルの数である。
最適なＳ字曲線のパラメータは次に、考えられるＳ字曲線パラメータに対して対数尤度を最大化することにより得られる。
【０１６８】
（§４．２．１．４．２．１．１  既知の最適化法）
式（２８）は、勾配下降(gradient descent)、Levenberg-Marquardt、ニュートン・ラフソン(Newton-Raphson)、複合勾配(conjugate gradient)、可変メトリクス法等(variable metric methods)、既知の無制約最適化法に基いて最大化される。
【０１６９】
（§４．２．１．４．２．１．２  遷移に関するラプラスの法則）
ある実施例において、上記の式（２８）の値ｙｉを目標値ｔｉと置換し、以下のようにすることができる。
【０１７０】
【数４５】
0004514082.tif 000032
【０１７１】
ただし、Ｎ+はそのクラスのトレーニングセットの文字情報オブジェクト数、Ｎ-はそのクラスに入らないトレーニングセットの文字情報オブジェクト数である。
【０１７２】
ｙｉではなく、目標値ｔｉを使うことにより、結果として得られるＳ字曲線はこれを決定するために使用したデータ以上に精密であることはない。つまり、Ｓ字曲線は、特にトレーニングデータの少ないカテゴリにおいて、過去のデータに「オーバーフィット」しない。このように、すべての確率が同等の可能性を持つという事前確率から、未知のデータにマッチするＳ字曲線が決定される。テキスト分類器について、式（３０）に目標関数ｔｉを使用したものを示したが、別の分類器にも適用することができる。当然、プラスおよびマイナス分類におけるトレーニングサンプル数によって異なる他の目標関数を、式（２９）で定めた目標関数の代わりに使用できる。
【０１７３】
Ｓ字曲線をトレーニングデータに当てはめるひとつの実施例において、以下の式で表わされる目標値（ｔｔｉ）を使用する。
【０１７４】
【数４６】
0004514082.tif 000033
【０１７５】
このような目標関数は、真の目標ｙより０．０１以上離れないように、遷移に関するラプラスの法則の効果を限定する。これは、経験的に望ましいことがわかっている。
【０１７６】
（§４．２．２  テキスト分類器の構成例）
図２は、本発明に基くテキスト分類器が使用する行程図である。図２に示されているように、分類すべき文字情報オブジェクト２０５は、特徴抽出行程(より一般的には特徴抽出機)２１０に送られる。以下、§４．２．２．１で述べるように、この特徴抽出行程２１０は、§４．２．１．１で述べた特徴抽出行程１１０と同じとすることができる。次に、以下§４．２．２．２で述べる特徴簡約行程(より一般的には、特徴簡約設備)２２０は、上記§４．２．１．２で述べる特徴簡約行程１２０によって発生された簡約済みの特徴群を使い、文字情報オブジェクト２０５に関わる特徴ベクトルの大きさを簡約する。このように、文字情報オブジェクト２０５に関わる簡約済み特徴ベクトルが発生される。図２に示すように、次にこの簡約済み特徴ベクトルには、2進数化行程２３０が加えられる。
【０１７７】
特徴簡約行程２２０によって発生された簡約済み特徴ベクトル(あるいは2進数化行程２３０によって発生された2進数簡約済み特徴ベクトル)は、１つまたは複数の分類器２５０に送られる。これらの分類器２５０は、以下の§４．２．２．４で述べる分類行程を使用する。各分類器２５０の重量パラメータｗとパラメータ化可能な単調関数のパラメータは、上記§４．２．１．４で述べた分類エンジンパラメータ発生行程によって決定されたものである。文字情報オブジェクト２０５が特定のクラスに属する確率が出力される。
【０１７８】
（§４．２．２．１  特徴抽出）
特徴抽出行程２１０は、図１と図６について§４．２．１．１ですでに述べた特徴抽出行程１１０と同様である。
【０１７９】
（§４．２．２．２  特徴簡約）
特徴簡約行程２２０の例を説明する。すでに説明した特徴簡約行程１２０は、(例えばカテゴリ独立型あるいはカテゴリ依存型テクニックに基き)、トレーニングサンプル群１１５の文字情報に対応する特徴ベクトルを簡約する。この行程１２０はまた、簡約された特徴群を作り、これがテキスト分類にとって関係がある、あるいは重要であるとみなされる特徴のインデックスとなる。例えば、簡約された特徴群には、ベクトルの特徴の第２、５、２０、２１、８９番目の要素に対するインデックスを含む場合がある。したがって、１００要素の特徴ベクトルは、５要素の簡約済み特徴ベクトルに簡約することができる。一般に、特徴ベクトルと簡約済み特徴ベクトルの要素数は、この例で用いられているものよりずっと大きい。
【０１８０】
一例としての特徴簡約行程２２０は、関連する、または重要な特徴のインデックスを使って特徴の数値をマッピングし、簡約済み特徴ベクトルの一連のインデックスを作る。上記の簡略化した例によれば、第２番目の要素の値は簡約済み特徴ベクトルの第1の要素に、第５番目の要素の値は簡約済み特徴ベクトルの第2番目の要素に、第２０番目の要素の値は簡約済み特徴ベクトルの第３番目の要素に、第２１番目の要素の値は簡約済み特徴ベクトルの第４番目の要素に、また第８９番目の要素の値は簡約済み特徴ベクトルの第５番目の要素にそれぞれ入る。
【０１８１】
上記§４．２．１で述べたように、実際において、文字情報オブジェクトはひとつの特徴ベクトル配列で表わすことはできず、当業者にとっては周知のスパーステクニック（sparse techniques）を用いることにより、より小さな特徴インデックスと数値の配列により表わすことができる。
【０１８２】
簡約済み特徴群は、特徴抽出行程２１０に供給することができるが、この場合、特徴抽出行程は簡約済み特徴群に属する特徴だけを抽出する。このように、特徴簡約は、特徴が抽出される間に行われる。
【０１８３】
（§４．２．２．３  2進数化）
オプションによる2進数化行程２３０は、図１に関して§４．２．１．３ですでに述べた2進数化行程１５０と同様とすることができる。
【０１８４】
（§４．２．２．４  分類）
分類行程２５０は、以下のように実行される。文字情報オブジェクト２０５(簡約済み特徴ベクトルxで表わされる)がカテゴリiに属する確率は以下のように表わすことができる。
【０１８５】
【数４７】
0004514082.tif 000034
【０１８６】
このテキスト分類器には多くの利点がある。まず、各種カテゴリの分類器から出力された確率を異なるカテゴリ間で比較することができる。第二に、§４．２．１．４．２．１．２ですでに説明した目標テクニックを使って単調関数とその調整可能なパラメータを決定する場合、特定のカテゴリについて得られるトレーニングデータの量が比較的少ない時にもその関数がオーバーフィットしない。
【０１８７】
（§４．２．３  アーキテクチャの一例）
図１１Ａと以下の説明は、本発明の少なくとも一部の態様が実現されている装置の例についての簡単かつ一般的な説明である。パーソナルコンピュータによって実行されるプログラムモジュール等のコンピュータで実行可能な命令という一般的な内容において、本発明を説明する。
【０１８８】
しかしながら、本発明による方法は、他の装置による影響を受けることがある。プログラムモジュールには、あるタスクを実行したり、あるいは特定の抽象的データタイプを実行する、ルーチン、プログラム、オブジェクト、コンポーネント、データ構成等がある。さらに、当業者にとって、本発明の少なくとも一部の態様は、ハンドヘルド型デバイス、マルチプロセサシステム、マイクロプロセサに基く、あるいはプログラム可能な消費者向け電子機器、ネットワークコンピュータ、ミニコンピュータ、セットトップボックス、メインフレームコンピュータ等、他の構成でも実現できることは明らかである。本発明の少なくとも一部の態様は、コミュニケーションネットワークを通じて連結されたリモートプロセシングデバイスによってタスクが実行される分散型コンピューティング環境でも実現できる。分散型コンピューティング環境では、プログラムモジュールをローカルおよび／またはリモートメモリデバイスに配置してもよい。
【０１８９】
図１１Ａについて、本発明の少なくとも一部の態様を実現するための装置例１１００は、汎用コンピュータデバイスとしての従来のパーソナルコンピュータ１１２０を含む。パーソナルコンピュータ１１２０は、処理ユニット１１２１、システムメモリ１１２２、システムメモリ等の各種のシステムコンポーネントを処理ユニット１１２１に接続するシステムバス１１２３からなる。システムバス１１２３は、さまざまなバスアーキテクチャを使い、メモリバスまたはメモリコントローラ、周辺バス、ローカルバス等、数種のバス構成のどれをとってもよい。システムメモリは、リードオンリーメモリ（ROM）１１２４および／またはランダムアクセスメモリ(RAM)１１２５からなる。基本的入力／出力システム１１２６(BIOS)は、パーソナルコンピュータ１１２０内の要素間で情報を転送するのに役立つ基本的ルーチンを含み、セットアップ時等にROM１１２４内に記憶される。パーソナルコンピュータ１１２０はまた、ハードディスク(図示せず)からデータを読み取ったり、これに書き込むためのハードディスクドライブ、(例えば取り外し可能な)磁気ディスク１１２９からデータを読み取ったり、書き込むための磁気ディスクドライブ１１２８、およびコンパクトディスクまたはその他の(磁気)光学媒体等の取り外し可能な(磁気)光学ディスク１１３１の読み書きに用いる光学ディスクドライブ１１３０を有するものでもよい。ハードディスクドライブ１１２７、磁気ディスクドライブ１１２８、(磁気)光学ディスクドライブ１１３０は、それぞれハードディスクドライブインタフェース１１３２、磁気ディスクドライブインタフェース１１３３、(磁気)光学ドライブインタフェース１１３４によってシステムバス１１２３に接続される。デバイスとそれぞれに関連する記憶媒体は、機械読取可能な命令、データ構成、プログラムモジュールおよびパーソナルコンピュータ１１２０用のその他データの不揮発性メモリとなる。ここで例として挙げる環境ではハードディスク、取り外し可能な磁気ディスク１１２９および取り外し可能な光学ディスク１１３１を使っているが、当業者にとって、磁気カセット、フラッシュメモリカード、デジタルビデオディスク、ベルヌーイカートリッジ、ランダムアクセスメモリ(RAM)、リードオンリーメモリ(ROM)等、その他のタイプの記憶媒体も、上記の記憶装置の代わり、あるいはこれに加えて使用することができることは明らかである。
【０１９０】
オペレーティングシステム１１３５、ひとつまたは複数のアプリケーションプログラム１１３６、その他のプログラムモジュール１１３７および／またはプログラムデータ１１３８等、多数のプログラムモジュールが、ハードディスク１１２３、磁気ディスク１１２９、(磁気)光学ディスク１１３１、ROM１１２４またはRAM１１２５に記憶される。ユーザはキーボード１１４０およびポインティングデバイス１１４２等の入力デバイスを通じて、パーソナルコンピュータ１１２０にコマンドや情報を入力することができる。マイクロフォン、ジョイスティック、ゲームパッド、サテライトディッシュ、スキャナ等、その他の入力デバイス(図示せず)も使用できる。これらおよびその他の入力デバイスはしばしば、システムバスに連結されたシリアルポートインタフェース１１４６を通じて処理ユニット１２２１に接続される。しかし、入力デバイスはパラレルポート、ゲームポートまたはユニバーサルシリアルバス(USB)等、その他のインタフェースによっても接続できる。モニタ１１４７またはその他のディスプレイデバイスもまた、ビデオアダプタ１１４８等のインタフェースを通じて、システムバス１１２３に接続可能である。モニタに加え、パーソナルコンピュータ１１２０には、スピーカやプリンタといったその他の周辺出力機器(図示せず)も搭載できる。
【０１９１】
パーソナルコンピュータ１１２０は、遠隔（リモート）コンピュータ１１４９等、１つまたは複数の遠隔（リモート）コンピュータへの論理的接続を決定するネットワーク環境で動作してもよい。リモートコンピナータ１１４９は、別のパーソナルコンピュータ、サーバ、ルータ、ネットワークPC、ピアデバイスまたはその他の一般的なネットワークノードであってもよく、図１１Ａではメモリデバイス１１５０しか描かれていないものの、パーソナルコンピュータ１１２０について上述した素子の多くまたは全部を含めることができる。図１１Ａに示した論理接続には、ローカルエリアネットワーク(LAN)１１５１とワイドエリアネットワーク(WAN)１１５２、イントラネット、インターネットがある。
【０１９２】
LAN  １１５１で使用する場合、パーソナルコンピュータ１１２０は、ネットワークインタフェースアダプタ(NIC)１１５３を通じてLAN  １１５１に接続される。インターネット等のWANの場合、パーソナルコンピュータ１１２０にはモデム１１５４をはじめとする、ワイドエリアネットワーク１１５２上での通信を可能にするための手段を搭載させる。モデム１１５４は、内蔵か外付けかを問わず、シリアルポートインタフェース１１４６を通じてシステムバス１１２３に接続される。ネットワーク環境において、パーソナルコンピュータ１１２０に関連して書かれているプログラムモジュールのうち少なくとも一部がリモートメモリデバイスに記憶される。図示されるネットワーク接続は一例であり、コンピュータ間の通信リンクを実現するその他の手段も利用できる。
【０１９３】
図１１Ｂは、上述した行程のひとつまたは複数を実行する、より一般的なマシン１１００である。マシン１１００は基本的に、プロセサ１１０２、入力／出力インタフェース１１０４、記憶デバイス１１０６、および連結された素子間のデータおよびコントロールコミュニケーションを行うためのシステムバスまたはネットワーク１１０８からなる。プロセサ１１０２は、機械実行可能な命令を実行し、本発明のひとつまたは複数の態様を実現する。機械実行可能な命令の少なくとも一部は、記憶デバイス（１１０６）に（一次的あるいはより永久的に）記憶するか、あるいは入力インタフェースユニット１１０４を通じて外部のソースから受け取ってもよい。
【０１９４】
（§４．２．４  結論）
以上のように、テキストを分類し、テキスト分類器を構成する方法と装置について説明した。これらの方法と装置はその利点として、（ｉ）分類に重要な特徴を残しながら、文字情報オブジェクトを表わす特徴ベクトルのサイズを縮小し、（ｉｉ）比較的トレーニングデータが少ない場合にオーバーフィットするような分類器の作成を防止し、（ｉｉｉ）比較的早くトレーニングし、および／または（ｉｖ）比較的早く分類する。
【図面の簡単な説明】
【図１】  この発明の第一の実施形態により実行できる行程を示す高レベル図である。
【図２】  この発明の第二の実施形態により実行できる行程を示す高レベル図である。
【図３】  文字情報オブジェクトのトレーニング見本の典型的なデータ構造である。
【図３Ａ】  文字情報オブジェクトの別の典型的なデータ構造であって、スパースデータ構造を示すものである。
【図３Ｂ】  文字情報オブジェクトの別の典型的なデータ構造であって、スパースデータ構造を示すものである。
【図４】  図３のトレーニング見本の典型的なデータ構造であって、特性ベクトルが簡約されたものである。
【図４Ｂ】  別の典型的なスパースデータ構造であって、特性ベクトルが縮小されたものである。
【図４Ｃ】  別の典型的なスパースデータ構造であって、特性ベクトルが縮小されたものである。
【図５】  図４のトレーニング見本の典型的なデータ構造であって、簡約された特性ベクトルの値が２進数化されたものである。
【図５Ｂ】  別の簡約され、２進数化された特性ベクトルの典型的なスパースデータ構造である。
【図５Ｃ】  別の簡約され、２進数化された特性ベクトルの典型的なスパースなデータ構造である。
【図６】  典型的な特性抽出行程のフロー図である。
【図７】  典型的な特性簡約行程のフロー図である。
【図８】  分類エンジン用にパラメータを生成する典型的な行程のフロー図である。
【図９】  一部の特性簡約技術で使用する情報を示す図である。
【図１０】  様々なＳ字曲線関数を示すした図である。
【図１１Ａ】  この発明により実行される行程を可能にするために使用できるコンピュータ環境のブロック図である。
【図１１Ｂ】  この発明により実行される行程を可能にするために使用できるマシンのブロック図である。
【図１】
0004514082.tif 000043
【図２】
0004514082.tif 000044
【図３】
0004514082.tif 000045
【図３Ｂ】
0004514082.tif 000046
【図３Ｃ】
0004514082.tif 000047
【図４】
0004514082.tif 000048
【図４Ｂ】
0004514082.tif 000049
【図４Ｃ】
0004514082.tif 000050
【図５】
0004514082.tif 000051
【図５Ｂ】
0004514082.tif 000052
【図５Ｃ】
0004514082.tif 000053
【図６】
0004514082.tif 000054
【図７】
0004514082.tif 000055
【図８】
0004514082.tif 000056
【図９】
0004514082.tif 000057
【図１０】
0004514082.tif 000058
【図１１Ａ】
0004514082.tif 000059
【図１１Ｂ】
0004514082.tif 000060