サンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法
【課題】最適化タスクを簡略化する２値分類方法が必要であり、このため、超平面判別式によるデータ信号の２値分類の方法を提供する。
【解決手段】トレーニングサンプルの集合が取得され、各トレーニングサンプルは第１又は第２のクラスのいずれかに属するとしてラベル付けされる。２項サンプルの対が、各２項対の第１のサンプルが第１のクラスに属し各２項対の第２のサンプルが第２のクラスに属するように射影ベクトルにより結合され、超平面の集合が射影ベクトルに対し垂直な面を有するように形成され、超平面の集合から重み付き分類誤差を最小化する１つの超平面が選択される。そしてトレーニングサンプルの集合が選択された超平面による分類に従って重み付けされる。選択された超平面は結合され２値分類器となり、所定反復数、選択と重み付けと結合が繰返されることによりテストサンプルを第１及び第２のクラスに分類する最終分類器が取得される。
【解決手段】トレーニングサンプルの集合が取得され、各トレーニングサンプルは第１又は第２のクラスのいずれかに属するとしてラベル付けされる。２項サンプルの対が、各２項対の第１のサンプルが第１のクラスに属し各２項対の第２のサンプルが第２のクラスに属するように射影ベクトルにより結合され、超平面の集合が射影ベクトルに対し垂直な面を有するように形成され、超平面の集合から重み付き分類誤差を最小化する１つの超平面が選択される。そしてトレーニングサンプルの集合が選択された超平面による分類に従って重み付けされる。選択された超平面は結合され２値分類器となり、所定反復数、選択と重み付けと結合が繰返されることによりテストサンプルを第１及び第２のクラスに分類する最終分類器が取得される。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、概してデータおよび信号の分類に関し、特に、２値判別式による分類に関する。
【０００２】
【従来の技術】
信号およびデータ処理における頻繁な問題は、分類の問題である。多くの用途、たとえば、天文学、気象学、医学および画像処理において、入力信号または入力データ集合のサンプルを２つの別々のクラスに分離する必要がある。たとえば、画像から顔を認識する視覚システムにおいて、男性または女性のいずれかとして顔を分類することがしばしば望まれる。臨床試験において、統計データの分類を使用することにより、病気を調査することができる。この種の問題を解決するために、２値分類器（ｂｉｎａｒｙ ｃｌａｓｓｉｆｉｅｒ）または判別式が使用される。信号が複雑である、たとえばデータサンプルが高次元を有する信号であり、単純な分類器が直接的に明らかでない場合、まず、トレーニング信号またはデータサンプル自体から判別式を「学習する（ｌｅａｒｎ）」必要がある。
【０００３】
２値分類器の機械学習において、２つの技法、すなわちブーストおよびカーネルがもっとも一般的に使用される。１つの周知のブーストアルゴリズムはＡｄａｂｏｏｓｔである。Ｆｒｅｕｎｄ等の著「Ａ Ｄｅｃｉｓｉｏｎ−ｔｈｅｏｒｅｔｉｃ ｇｅｎｅｒａｌｉｚａｔｉｏｎ ｏｆ ｏｎ−ｌｉｎｅ ｌｅａｒｎｉｎｇ ａｎｄ ａｎ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ｂｏｏｓｔｉｎｇ」Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｓｙｓｔｅｍ Ｓｃｉｅｎｃｅｓ、５５、ｐｐ．１１９〜１３９、１９９５と、Ｓｈａｐｉｒｅ等の著「Ｂｏｏｓｔｉｎｇ ｔｈｅ ｍａｒｇｉｎ： ａ ｎｅｗ ｅｘｐｌａｎａｔｉｏｎ ｆｏｒ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｖｏｔｉｎｇ ｍｅｔｈｏｄｓ」Ｐｒｏｃ． １４ｔｈ Ｉｎｔｅｒ． Ｃｏｎｆ． ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ、ｐｐ． ３２２〜３３０、１９９７と、Ｓｃｈｏｌｋｏｐｆ等の著「Ｎｏｎｌｉｎｅａｒ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ ａｓ ａ ｋｅｒｎｅｌ ｅｉｇｅｎｖａｌｕｅ ｐｒｏｂｌｅｍ」Ｎｅｕｒａｌ−Ｃｏｍｐｕｔａｔｉｏｎ、１０、ｐｐ． １２９９〜１３１９、１９９８と、を参照のこと。
【０００４】
ブーストを使用して、通常偶然よりほんのわずかによく実行する弱分類器の集まりから強分類器が構築される。ＡｄａＢｏｏｓｔの分析と他の「投票（ｖｏｔｉｎｇ）」タイプ分類方法とにより、結果としての分類器においてマージンを最大化し、それにより過剰適合が避けられ汎化性能が向上する、というブーストの明白な傾向が説明されてきた。しかしながら、マージンを直接最大化することは、比較的複雑な最適化タスクである。
【０００５】
暗示的マッピングメカニズムとして、分類タスクに使用される場合に、変換された特徴空間における線形判別式を入力またはトレーニングデータ空間における複雑な非線形判断境界に対応させる、Ｍｅｒｃｅｒカーネルが使用されてきた。Ｂｏｓｅｒ等の著「Ａ ｔｒａｉｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｏｐｔｉｍａｌ ｍａｒｇｉｎ ｃｌａｓｓｉｆｉｅｒｓ」Ｐｒｏｃ． ５ｔｈ Ａｎｎｕａｌ ＡＣＭ Ｗｏｒｋｓｈｏｐ ｏｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｌｅａｒｎｉｎｇ Ｔｈｅｏｒｙ、ｐｐ． １４４〜１５２、１９９２を参照のこと。また、カーネル法は、主成分分析（ｐｒｉｎｃｉｐａｌ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ（ＰＣＡ））とＦｉｓｈｅｒの線形判別分析（ｌｉｎｅａｒ ｄｉｓｃｒｉｍｉｎａｎｔ ａｎａｌｙｓｉｓ（ＬＤＡ））とに対し、非線形特徴空間を構築するためにも使用されてきた。
【０００６】
カーネルマッピングの最もよく知られている例は、非線形サポートベクトルマシン（ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ（ＳＶＭ））で使用される。Ｖａｐｎｉｋの著「Ｔｈｅ ｎａｔｕｒｅｏｆ ｓｔａｔｉｓｔｉｃａｌ ｌｅａｒｎｉｎｇ ｔｈｅｏｒｙ」Ｓｐｒｉｎｇｅｒ、１９９５を参照のこと。ＳＶＭでは、分類マージン、それ故、汎化における境界が、すべてのトレーニングサンプルに関する同時最適化によって最大化される。ＳＶＭでは、サンプルを判断境界に極めて近接させることができ、サポートベクトルは、単に、判断境界を構築、すなわちサポートするために必要な最小数のトレーニングサンプルである。サポートベクトルは、ほぼ確実にいずれのクラスの「典型」または高可能性メンバではない。また、ＳＶＭの場合、通常、生成されるサポートベクトルの数を制御する直接の方法がない。
【０００７】
【発明が解決しようとする課題】
したがって、最適化タスクを簡略化する分類方法が必要である。また、分類中に使用される判別式の数を制限することも望ましい。
【０００８】
【課題を解決するための手段】
本発明は、超平面判別式によるデータ信号の２値分類の方法を提供する。これらの２項超平面は、対向するクラスからのトレーニングサンプルの対に基づく。本方法はさらに、Ｍｅｒｃｅｒの定理を満足させるカーネル関数を使用することにより非線形判別式に拡張される。
【０００９】
トレーニング中、信頼度付きブーストにより、２項超平面の集合が学習される。ブーストの各反復中に分類器の有限集合から最適な超平面が選択される。そして、選択された超平面が結合されて最終分類器となる。このため、あり得る分類器の数が制限される。
【００１０】
本発明による方法は、超平面判別式の重ね合せにより複雑な２値分類器を学習（求める）する。各判別式は、トレーニングサンプルの対向する対を結合するベクトル上への射影に基づく。すなわち、「２項（ｄｙａｄｉｃ）」対は、対抗するラベルを有する２つのサンプルからなる。たとえば、第１の集合のサンプルは−１にラベル付けされ、第２の集合のサンプルは＋１にラベル付けされる。学習プロセス自体は、ＡｄａＢｏｏｓｔの「ファジー」実数値型変形に基づき、超平面分類器は、分離不可能な問題を高次元非線形特徴空間に線形にマッピングする、ＳＶＭによって使用されるタイプのカーネルを使用する。
【００１１】
概念クラスが、線形判別式、すなわち超平面からなる場合、これは、２値対を結合するベクトルに対して直交する線形超平面を使用することになる。線形超平面の同じ概念を、Ｍｅｒｃｅｒタイプカーネルによって取得された非線形に変換された特徴空間に適用することにより、ＳＶＭと同様の形式の非線形判別式を提供することができる。
【００１２】
ブーストにより、候補超平面の探索は、すべての２項分類器の空間に及ぶ。このあり得る分類器の空間は、トレーニングデータの部分空間に及び、最適な超平面判別式は、この部分空間に存在しなければならない。この概念は、特徴空間において最適な判別式が変換されたデータのスパンに存在することを留意することにより、カーネル変換によって取得された非線形分類器に容易に拡張される。したがって、線形と非線形との両方の分類問題において、本発明による２項超平面は、すべての分類器の空間を探索する効率的な探索戦略を形成する。
【００１３】
最適な超平面に関するいかなる従来の知識もない場合、トレーニングデータはそれ自体の最良の判別式であり、従来技術によるｋ−ＮＮおよびＳＶＭ分類器に対する基礎も形成する原理である。
【００１４】
より詳細には、方法は、サンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習して求める。まず、トレーニングサンプルの集合が取得される。各トレーニングサンプルは、第１のクラスかまたは第２のクラスのいずれかに属するものとしてラベル付けされる。
【００１５】
２項サンプルの対が、各２項対の第１のサンプルが第１のクラスに属し、各２項対の第２のサンプルが第２のクラスに属するように、射影ベクトル（ｐｒｏｊｅｃｔｉｏｎ ｖｅｃｔｏｒｓ）によって結合される。
【００１６】
超平面の集合は、超平面が射影ベクトルに対し垂直な面を有するように形成される。超平面の集合から、重み付き分類誤差を最小化する１つの超平面が選択される。
【００１７】
そして、トレーニングサンプルの集合が、選択された超平面による分類にしたがって重み付けされる。選択された超平面は結合されて２値分類器となり、所定反復数、選択することと重み付けすることと結合することとが繰返されることにより、テストサンプルを第１および第２のクラスに分類する最終分類器が取得される。
【００１８】
【発明の実施の形態】
超平面判別式
図６は、本発明による２値分類器６０４を学習して求める（ｌｅａｒｎｉｎｇ）方法６００を示す。方法６００は、Ｍ個のトレーニングサンプルの集合６０１、すなわちベクトルＴ＝｛ｘ１，・・・，ｘＭ｝で開始する。トレーニングサンプルｘ∈ＲＮは対応するラベル｛ｙ１，・・・，ｙＭ｝、ここで（ｙ∈｛−１，＋１｝）を有する。ラベル＋１を有するＭｐ個のサンプルとラベル−１を有するＭｎ個のサンプルとがある。すなわち、トレーニングサンプル６０１は、２つのクラスにしたがってラベル付けされ、したがってＭ＝Ｍｐ＋Ｍｎである。入力トレーニングサンプル６０１の集合は、現実の物理的事象やデジタルイメージから測定することができ、また医学的研究等の統計データから収集することができる。
【００１９】
本発明による線形超平面分類器は、以下の形式の判別関数によって定義される。
【００２０】
ｆ｛ｘ｝＝＜ｗ，ｘ＞＋ｂ （１）
【００２１】
ただし、ｓｇｎ ｆ（ｘ）∈｛−１、＋１｝は２値分類を示す。いくつかの仮定、特にガウス性の下では、最適の超平面が射影ベクトルｗによって画定（定義）され、バイアスｂを線形分類器のためのクラス手段およびサンプル共分散に基づいて標準的な統計技法を使用して求めることができる。
【００２２】
本発明では、入力サンプルの分布ｐ（ｘ）に関しいかなる仮定も行わず、代りに最適な分類器６０４、すなわち判別誤差または経験的リスクを最小化する分類器を学習するために、すべてのあり得る超平面の空間を探索することが望まれる。
【００２３】
当然ながら、すべてのあり得る超平面の空間を探索することは実際的ではない。また、この空間のランダムサンプリングは、完全に見当違いである。最適な射影ベクトルｗ＊がトレーニングデータ集合自体のスパンにある、ということがわかる。
【００２４】
トレーニングデータ集合ＴのスパンがＳであり、その直交補空間が
【００２５】
【数２】
【００２６】
である場合、
【００２７】
【数３】
【００２８】
すなわち、空集合となる。これらの２つの部分空間に対する線形拡張により、
【００２９】
【数４】
【００３０】
となる。しかしながら、
【００３１】
【数５】
【００３２】
であるため、定義により、ｗＳ成分のみが判別式
【００３３】
＜ｗ・ｘ＞＋ｂ
【００３４】
に対して何らかの影響を及ぼす。したがって、すべての解が、最適な射影ベクトルｗ＊∈Ｓを含む入力データ集合Ｔのスパンになければならない。
【００３５】
線形超平面
ｗ＊を探索する場合、本方法６００は、対抗するクラスからのサンプルの対を結合する線分に対して垂直な面を有する超平面のみを考慮する。したがって、まず、２項トレーニングサンプル６０１の対を結合する６１０。
【００３６】
ｗｉｊ＝（ｘｉ−ｘｊ）／ｃ ｙｉ≠ｙｊ ｉ＜ｊ （２）
【００３７】
ただし、定義によりｙｉ≠ｙｊであり、一意性のためにｉ＜ｊである。項ｃは、一定のスケールファクタである。ｃ＝｜｜ｘｉ−ｘｊ｜｜と設定すると、ｗｉｊは、１−ノルム方向ベクトルとなる。いずれの場合も、射影ベクトルｗｉｊは対向するクラスからの任意の２つのサンプルｘｉおよびｘｊ、すなわち「２項対」を結合する線分に対して平行である。そして、結合する線分に対して垂直に集合６０２の超平面が形成される６２０。
【００３８】
図１は、２項トレーニングサンプル（ｘｉ，ｘｊ）１０３〜１０４の対向する対を結合する１−ノルム射影ベクトルｗｉｊ１０２によって形成される２項超平面ｈ（ｘ）１０１を示す。
【００３９】
適当なバイアス項ｂｉｊを用いて、式（１）の形式の超平面判別式を得る。２項判別式を使用することにより、ラベル無しテストサンプル６０５を２つのクラス６６１〜６６２に分離することができる。探索するべき存在しうる分類器の空間は、｜｛ｗｉｊ｝｜＝ＭｐＭｎ射影ベクトルの集合を含み、それらの各々は、後述するように一般に重み付き分類誤差を最小化することによって求められる自由パラメータｂｉｊを有する。
【００４０】
そして、各仮説または分類器ｈｉｊ（ｘ）は、以下のように、式（１）のような判別式の符号関数によって与えられる。
【００４１】
ｈｉｊ（ｘ）＝ｓｇｎ（＜ｗ・ｘ＞＋ｂｉｊ） （３）
【００４２】
本明細書では、｛ｈｉｊ｝＝｛ｗｉｊ，ｂｉｊ｝により、トレーニングデータ集合６０１に対し超平面６０２の完全集合を示す。厳密に言えば、この集合は、スカラｂｉｊ∈Ｒのテンソル積が無限となるため無数である。しかしながら、本明細書では、各超平面に対し常に単一の最適なバイアスパラメータを選択するため、実際にはＭｐＭｎの分類器のみで終わる。
【００４３】
図１は、２項サンプル対（ｘｉ，ｘｊ）によって画定され制約される超平面判別式を示す。これは、式（２）のように線形射影ベクトルｗｉｊをもたらす。この射影では、バイアスｂが、最適化すべき唯一のパラメータである。
【００４４】
分類誤差を最小化するために超平面１０１を結合線分１０２に沿ってシフトすることによって、最適化を行うことができる。この例では、この特定の２項対に対し１つのサンプル１１０を正しくラベル付けすることができないことが分かる。そして、誤差ε＝１／２０（０．０５）を有する結果としての分類器が、「最適な」超平面である。
【００４５】
なお、射影ベクトルｗｉｊが与えられると、「最適な」バイアスパラメータｂの推定は、しばしば単純な一次元線探索、もしくは必要な場合は、全数探索である。分類器が同じ最小誤差を有することができるｂ値の範囲または多様性は、この段階では無関係である。
【００４６】
一方、ブースト２００（図２参照）を使用して「強」超平面６０３を形成し、強超平面を結合する６５０ことにより最終超平面または分類器６０４のマージンを最大限にする。
【００４７】
最終分類器６０４を使用して、ラベル無しテストサンプル６０５の集合を２つのクラス６６１〜６６２に分類することができる６６０。
【００４８】
ブースト
ブースト２００は、選択された強分類器６０３を線形結合および閾値設定６５０により結合して単一の最終分類器６０４にする、実際的なフレームワークを提供する。ブーストは、分類の難易度に基づいてトレーニングサンプル６０１に対し、反復的に展開する分布、すなわち重みＤ（ｉ）を維持する。たとえば、分類が困難なサンプルほど、分類が容易なサンプルより大きい重みを有する。したがって、集合６０２における各分類器ｈ（ｘ）：ｘ→｛＋１，−１｝は、以下の重み付き分類誤差を有する。
【００４９】
【数６】
【００５０】
この場合、ブーストの各ラウンドｔにおいて、ＭｐＭｎ個の超平面ｈｉｊ６０２の完全集合から、重み付き分類誤差εを最小化するものを選択する６３０。これに続き、トレーニングサンプル６０１に、更新された分布Ｄｔ＋１を取得するためにそれらの分類または誤分類に基づいて再重み付けする６４０。
【００５１】
図２は、ブースト２００のプロセスを示す。ステップ２１０において、以下のように初期化する。
【００５２】
【数７】
【００５３】
そして、ｔ＝１，・・・，Ｔに対し、以下のステップを反復する。ステップ２２０において、ｈｔ＝ｈ＊ｉｊを設定する。ただし、ｈ＊ｉｊはεｔを最小化する｛ｈｉｊ｝６０２の要素である。ステップ２３０において、
【００５４】
【数８】
【００５５】
を設定する。そして、ステップ２４０において、分布
【００５６】
【数９】
【００５７】
（ＺｔはＤｔに対する正規化）を更新し、終了するまでｔの次の増分に対して繰返す。
【００５８】
最終分類器６０４は、選択された弱分類器ｈｔのα重み付き線形結合６５０であり、以下のように重み付き「投票（ｖｏｔｉｎｇ）」方式の形態を有する。
【００５９】
【数１０】
【００６０】
トレーニング誤差に対する結果としての上界は、以下のようになる。
【００６１】
【数１１】
【００６２】
ブーストの各ラウンドによるこの上界の倍数的に増加する縮小量（ｍｕｌｔｉｐｌｉｃａｔｉｖｅ ｓｈｒｉｎｋａｇｅ）は、ブーストプロセス２００の指数関数的収束と、しばしば急速なトレーニング誤差の低減（時に０まで）と、の証拠である。
【００６３】
ブーストは、ＳＶＭのようなマージン最大化（ｌａｒｇｅ ｍａｒｇｉｎ）分類プロセスのファミリに属する。ブーストにより、サンプル（ｘ，ｙ）のマージンは、範囲［−１，＋１］内にある
【００６４】
【数１２】
【００６５】
によって与えられ、Ｈがサンプルを正しく分類する場合にのみ正である。マージンは、しばしば、分類における信頼性の測度として解釈される。Ｓｃｈａｐｉｒｅ等の著「Ｉｍｐｒｏｖｅｄ ｂｏｏｓｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｕｓｉｎｇ ｃｏｎｆｉｄｅｎｃｅ−ｒａｔｅ ｐｒｅｄｉｃｔｉｏｎ」を参照のこと。分類器ｈｔ（ｘ）は、２進数とは対照的に実数値とすることができ、「信頼度付き予測（ｃｏｎｆｉｄｅｎｃｅ−ｒａｔｅｄ ｐｒｅｄｉｃｔｉｏｎ）」として解釈することができる。この場合、ｈｔ（ｘ）の符号は分類ラベルであり、絶対値｜ｈｔ（ｘ）｜は信頼度である。
【００６６】
かかる連続値または「ファジー」分類器の場合、
【００６７】
【数１３】
【００６８】
となり、このとき
【００６９】
【数１４】
【００７０】
であって、「相関」ｒｔはεｔ＝（１−ｒｔ）／２により誤差に反比例する。この場合、結果としての分類器Ｈの誤差は、
【００７１】
【数１５】
【００７２】
によって上から有界である。
【００７３】
非線形超平面
上述した線形分類器を越えた論理的拡張は、Ｂｏｓｅｒ等（上記参照）によって述べられているような正定「カーネル（ｋｅｒｎｅｌ）」を使用する非線形判別式に対する。ＳＶＭおよびカーネルＰＣＡ等の最近の非線形への発展、またはＳｃｈｏｌｋｏｐｆ等によって述べられているようなカーネルＦｉｓｈｅｒ判別式は、「カーネルＨｉｌｂｅｒｔ空間を再現する」特性に依存する。そこで、高次元マッピングΦ（ｘ）：Ｘ→Ｆによるドット積は、以下のＭｅｒｃｅｒカーネルを使用して評価される。
【００７４】
ｋ（ｘ、ｘ’）＝＜Φ（ｘ）・Φ（ｘ’）＞ （１１）
【００７５】
これは、たとえば式（３）における本発明による線形超平面分類器等、ドット積に基づくいかなるプロセスも、カーネルを使用して入力サンプルを非線形にマッピングし、変換された特徴空間において暗示的にドット積を実行することができる、という望ましい特性を有する。したがって、入力空間に戻る線形超平面解のプリイメージは非線形超平面である。
【００７６】
式（２）における上記カーネル特性を使用して、最初に、射影ベクトルが式（２）に形式が類似した
【００７７】
ｗｉｊ＝（Φ（ｘｉ）−Φ（ｘｊ）／ｃ ｙｉ≠ｙｊ ｉ＜ｊ （１２）
【００７８】
である変換された特徴空間Ｆにおいて線形分類器を検査することにより、式（３）における分類器を非線形形式に書換えることができる。ここでまた、最適な射影ベクトルｗ＊ｉｊがスパンΦ（ｘｉ）内になければならない、ということを留意する。したがって、それに応じて、たとえばペアワイズ射影ベクトルを考慮することにより、最適な非線形超平面に対する探索を制限する。
【００７９】
しかしながら、非線形マッピングの暗示的特質が与えられたｗｉｊを直接評価することはできない。しかしながら、変換された入力ベクトルΦ（ｘ）によるそのドット積のみがあればよい。式（１）における線形判別式を考慮し、上記を代入すると、以下の式が得られる。
【００８０】
【数１６】
【００８１】
ここで式（１１）におけるカーネル特性を適用することにより、以下の式が得られる。
【００８２】
【数１７】
【００８３】
ここで、定数ｃを、判別の範囲を正規化するように、たとえばｃ＝ｍａｘｉｊ｜ｋ（ｘｉ，ｘｊ）｜であるように設定することができる。
【００８４】
離散値超平面分類器は、以下の符号関数閾値によって与えられる。
【００８５】
ｈｉｊ（ｘ）＝ｓｇｎ（ｆｉｊ（ｘ）） （１５）
【００８６】
これに対し、範囲［−１，＋１］内の出力を有する「信頼度付き（ｃｏｎｆｉｄｅｎｃｅ−ｒａｔｅｄ）」分類器を、ｆｉｊ（）を以下の双曲線正接等、双極のシグモイド関数の非線形性に通すことにより取得することができる。
【００８７】
ｈｉｊ（ｘ）＝ｓｇｎ（βｆｉｊ（ｘ）） （１６）
【００８８】
ただし、βは、シグモイドの「傾き」を確定する。
【００８９】
範囲［−１，＋１］を適当に占める連続値分類器を取得するために、定数ｃおよびβを調整することができる。式（１４）に関し、スカラｃは、所与のトレーニングサンプルの範囲によって決まる。
【００９０】
また、非線形超平面を、それらのカーネルパラメータ、たとえばガウス（Ｇａｕｓｓｉａｎ）カーネルの幅または多項式カーネルの次数に関する最適化とすることができる。しかしながら、実際には、カーネルパラメータの適当な集合は、通常事前に求められ、学習およびブーストプロセス中に固定される。これは、実際に、カーネルパラメータに対する明示的探索および最適化に非常にコストがかかる（ｐｒｏｈｉｂｉｔｉｖｅ）、ＳＶＭおよび動径基底関数（ｒａｄｉａｌ ｂａｓｉｓ ｆｕｎｃｔｉｏｎ（ＲＢＦ））等の他のカーネルベース学習方法に関する場合である。しかしながら、本発明者らは、これを、個々の分類器のパラメータ設定の最適化ではなく「モデル選択」問題として見る。
【００９１】
適用例
本方法を周知のベンチマークに適用する前に、図３ａないし図３ｂに示すように、問題例に対する単純な２Ｄ非線形２項超平面について説明する。各クラスに１０個のサンプル「＋」および「○」がある２０個のサンプルのトレーニングデータ集合を使用した。
【００９２】
図３ａは、本発明による方法を用いたトレーニングデータの分類を示す。この適用例では、ガウスカーネルを使用する。本方法は、判別超平面３００を画定するために２回のみの反復、すなわち２つのベクトル３０１のみを使用することによりこの問題を解決する。超平面３００は、誤差のわずかなマージンを有し、一方の側に湾曲しているが、２項サンプル対が結合された破線３０１が判別境界３００を画定することが分かる。
【００９３】
図３ｂに示すような従来技術と比較するために、同じデータ集合を有するガウスカーネルＳＶＭを使用した。ＳＶＭ法は、４つのサポートベクトル３０２を用いてこの問題を解決する。ＳＶＭ法はよりよいマージンをもたらすが、本方法は、ブーストのラウンドを増大させて同様の結果をもたらす。
【００９４】
ＳＶＭ法と比較すると、本方法の計算負荷は、必要なカーネル評価の総数まで低減する。すべての超平面が２つのカーネル評価を必要とするため、本発明による分類器は、ＳＶＭ法が使用するサポートベクトルの数の半分の反復を使用する。実際に、サンプルｘｉを複数の射影ベクトルｗｉｊの一部とすることができ、対応するカーネルは１回だけ評価されるため、超平面分類器が必要とするカーネル評価の総数は、ブーストのｎ回の反復後、ｎ／２によって制限される。図３ａないし図３ｂの適用例では、本方法は、カーネル評価を３回しか必要としないが、従来技術の方法は４回必要とする。
【００９５】
実験結果
複数の現実のデータ集合に対する本方法の性能を評価し、本方法の性能を、従来技術による分類方法、すなわちガウスＲＢＦおよび線形カーネルを用いる非線形ＳＶＭおよびｋ−最近傍（ｋ−ＮＮ）と比較した。これらの方法のすべてが、実際のトレーニングサンプルから最終分類器を導出する。
【００９６】
機械学習データベースのＵＣＩリポジトリから４つのデータ集合を選択した。これらのデータベースは、Ｂｌａｋｅ， Ｃ．Ｌ．およびＭｅｒｚ， Ｃ．Ｊ．、Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｃａｌｉｆｏｒｎｉａ、Ｉｒｖｉｎｅ、Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ、１９９８による機械学習データベースのＵＣＩリポジトリのウェブサイトのファイル”ＭＬＲｅｐｏｓｉｔｏｒｙ．ｈｔｍｌ”において見ることができる。評価したデータ集合を、表Ａに示す。
【００９７】
表Ａ
データ集合 次元 サイズ
ソナー ３０ ２０８
電離層 ３４ ３５１
スタトログ心臓病 １３ ２７０
ウィスコンシン乳がん ３０ ５６９
【００９８】
評価の目的のために、各データ集合を、全データ集合の１／３サイズにそれぞれ等しい、トレーニング集合と、検査集合と、テスト集合と、にランダムに分割した。学習に使用するトレーニング集合とともに、検査集合に対する誤差率を最低にするために、従来技術による方法のパラメータ、すなわちＮＮの場合のｋおよびＲＢＦカーネルの場合のσを、選択した。これらの値を、ＲＢＦカーネル幅に対し２５個の値の範囲と、ｋ−ＮＮ分類器に対しｋ∈｛１，２，３，・・・，２５｝と、から引出した。検査テストによって選択されたｋの値は、ソナー（Ｓｏｎａｒ）の場合は１、電離層（Ｉｏｎｏｓｐｈｅｒｅ）の場合は３、乳がん（Ｂｒｅａｓｔ Ｃａｎｃｅｒ）の場合は７および心臓病（Ｈｅａｒｔ）の場合は１１であった。各試行において、ｎ／２およびｎ回（ｎは、その試行においてＳＶＭ法によって見つけられたサポートベクトルの数）の反復後に、本発明による超平面法がテストされた。なお、所定数の反復後にブーストプロセス２００を停止することにより、本分類器のサイズを制御することができ、それにより分類器の精度に影響を与えることができる。各試行において、ＳＶＭによるサポートベクトルの数ｎを基底として使用することにより、２つの超平面分類器に対し誤差を評価した。すなわち、１つは、ｎ／２個の超平面を有し、ＳＶＭ法と同じ数のカーネル評価を必要とするものであり、１つは、ｎ個の超平面を有し、２倍の計算を行うものである。
【００９９】
図４ａないし図４ｄのボックスプロット（箱髭図）は、誤差の分布を示す。各ボックスは、分布の四分位範囲にわたり、中心線は、分布の下位四分位と上位四分位との間の中央値を示す。伸びている「髭（ｗｈｉｓｋｅｒ）」は、値の全範囲を示す。なお、図４ｄは、よく見えるように拡大されている。
【０１００】
これらの経験的評価からの第１の観察結果は、ＲＢＦ超平面法が、ＳＶＭに匹敵し、通常はｋ−ＮＮ分類器より優れたテスト性能に達する、ということである。第２の観察結果は、ブーストのラウンドの初期に、サポートベクトルの半分に等しく時にそれより少ない数の超平面で、許容可能な性能に達する、ということである。また、しばしば性能は、後続する反復によって著しくは向上しない。
【０１０１】
図５は、電離層（Ｉｏｎｏｓｐｈｅｒｅ）データ集合に対する実験においてブースト反復の関数として試行誤差をプロットした、本発明による超平面法の進行の例を示す。水平の破線状の基線５０１は、この場合は１２０未満のトレーニング例から７４個のサポートベクトルを使用した、ＳＶＭ法の性能を示す。本方法の誤差５０２は、３０回の反復の後にこの基線５０１に近づき、そこに近接して留まり、最終的に同じ値に収束する。
【０１０２】
また、線形、すなわちドット積カーネルを用いた超平面により実験を行った。この場合、線形超平面の性能は、ＲＢＦカーネルを用いた方法よりわずかに低い。実際に、線形カーネル超平面は、式（１６）におけるソフトマージン出力関数により非線形判別式をもたらす。式（１６）におけるβ値がおよそ０である場合、平面の重ね合せにより線形境界がもたらされる。β値が有限である場合、滑らかな曲線状の超平面が得られる。βが無限である場合、信頼度値の無い堅固な分類器と同じである断片的線形（ｐｉｅｃｅ−ｗｉｓｅ ｌｉｎｅａｒ）境界が得られる。また、本発明による信頼度付き線形超平面は、本質的に、性能においてシグモイドカーネルを用いるＳＶＭと等価である。
【０１０３】
さらに、最適化戦略を、式（４）の分布Ｄｔ（ｉ）に基づくＭｐＭｎ個のあり得る超平面の仮定空間をサンプリングするために使用することにより、必ずしもトレーニングサンプルに基づいておらず、たとえばクラスタ重心または入力データ集合の分布に基づく他の導出されたサンプルに基づくことができる超平面を、形成することができる。
【０１０４】
【発明の効果】
本発明の効果には２つの要素がある。第１に、単純な判別式のファミリ、すなわち超平面を、対向するクラスからのトレーニングサンプルの対、すなわち２項対に基づいて提供し、Ｍｅｒｃｅｒタイプカーネルによる非線形マッピングを考慮することによってこのファミリをカーネル超平面まで拡張する。第２に、区間［−１，１］における連続的な出力をもたらす信頼度付きの実数値の超平面分類器によるブーストに基づく「貪欲な（ｇｒｅｅｄｙ）」選択プロセスを提供する。
【０１０５】
分類に対するこの新たなカーネルベースの方法が、大規模なＱＰ問題を解決する必要無しにＳＶＭを使用する方法と実質的に同様に実行することを示した。さらに、本方法により、計算複雑性またはモデル次数がユーザ選択可能であり、そのため計算の性能とトレードオフすることができる。また、ブーストプロセスにより指数関数的誤差縮小または収束の保証から利益を得る。ブーストのラウンドを増大させることにより、マージン最大化が保証される。
【０１０６】
複数の標準機械学習データ集合に対し、本方法の汎化性能を評価し、しばしば分類時間と分類器サイズとを低減して、確立された従来技術によるＳＶＭ法に匹敵する性能のレベルを示した。実際の適用では、トレーニング時間の増大を犠牲にしてでも複雑性を最小化することがしばしば望ましいため、この性能の利点を強調する。
【０１０７】
本発明を好ましい実施の形態の例として説明したが、本発明の精神および範囲内で他のあらゆる適応および変更を行うことができる、ということが理解されなければならない。したがって、併記の特許請求の範囲の目的は、かかる変形および変更のすべてを発明の真の精神および範囲内にあるものとして包含することである。
【図面の簡単な説明】
【図１】本発明におけるトレーニングサンプルによる超平面判別式を示す図である。
【図２】本発明によるブーストプロセスのフローチャートである。
【図３ａ】本発明による分類を示す図である。
【図３ｂ】従来技術による分類を示す図である。
【図４ａ】適用データ集合に対する分類誤差のボックスプロット（箱髭図）を示す図である。
【図４ｂ】適用データ集合に対する分類誤差のボックスプロット（箱髭図）を示す図である。
【図４ｃ】適用データ集合に対する分類誤差のボックスプロット（箱髭図）を示す図である。
【図４ｄ】適用データ集合に対する分類誤差のボックスプロット（箱髭図）を示す図である。
【図５】ブースト反復の関数としての分類誤差のグラフを示す図である。
【図６】本発明による２値分類器を学習する方法のフローチャートである。
【０００１】
【発明の属する技術分野】
本発明は、概してデータおよび信号の分類に関し、特に、２値判別式による分類に関する。
【０００２】
【従来の技術】
信号およびデータ処理における頻繁な問題は、分類の問題である。多くの用途、たとえば、天文学、気象学、医学および画像処理において、入力信号または入力データ集合のサンプルを２つの別々のクラスに分離する必要がある。たとえば、画像から顔を認識する視覚システムにおいて、男性または女性のいずれかとして顔を分類することがしばしば望まれる。臨床試験において、統計データの分類を使用することにより、病気を調査することができる。この種の問題を解決するために、２値分類器（ｂｉｎａｒｙ ｃｌａｓｓｉｆｉｅｒ）または判別式が使用される。信号が複雑である、たとえばデータサンプルが高次元を有する信号であり、単純な分類器が直接的に明らかでない場合、まず、トレーニング信号またはデータサンプル自体から判別式を「学習する（ｌｅａｒｎ）」必要がある。
【０００３】
２値分類器の機械学習において、２つの技法、すなわちブーストおよびカーネルがもっとも一般的に使用される。１つの周知のブーストアルゴリズムはＡｄａｂｏｏｓｔである。Ｆｒｅｕｎｄ等の著「Ａ Ｄｅｃｉｓｉｏｎ−ｔｈｅｏｒｅｔｉｃ ｇｅｎｅｒａｌｉｚａｔｉｏｎ ｏｆ ｏｎ−ｌｉｎｅ ｌｅａｒｎｉｎｇ ａｎｄ ａｎ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ｂｏｏｓｔｉｎｇ」Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｓｙｓｔｅｍ Ｓｃｉｅｎｃｅｓ、５５、ｐｐ．１１９〜１３９、１９９５と、Ｓｈａｐｉｒｅ等の著「Ｂｏｏｓｔｉｎｇ ｔｈｅ ｍａｒｇｉｎ： ａ ｎｅｗ ｅｘｐｌａｎａｔｉｏｎ ｆｏｒ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｖｏｔｉｎｇ ｍｅｔｈｏｄｓ」Ｐｒｏｃ． １４ｔｈ Ｉｎｔｅｒ． Ｃｏｎｆ． ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ、ｐｐ． ３２２〜３３０、１９９７と、Ｓｃｈｏｌｋｏｐｆ等の著「Ｎｏｎｌｉｎｅａｒ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ ａｓ ａ ｋｅｒｎｅｌ ｅｉｇｅｎｖａｌｕｅ ｐｒｏｂｌｅｍ」Ｎｅｕｒａｌ−Ｃｏｍｐｕｔａｔｉｏｎ、１０、ｐｐ． １２９９〜１３１９、１９９８と、を参照のこと。
【０００４】
ブーストを使用して、通常偶然よりほんのわずかによく実行する弱分類器の集まりから強分類器が構築される。ＡｄａＢｏｏｓｔの分析と他の「投票（ｖｏｔｉｎｇ）」タイプ分類方法とにより、結果としての分類器においてマージンを最大化し、それにより過剰適合が避けられ汎化性能が向上する、というブーストの明白な傾向が説明されてきた。しかしながら、マージンを直接最大化することは、比較的複雑な最適化タスクである。
【０００５】
暗示的マッピングメカニズムとして、分類タスクに使用される場合に、変換された特徴空間における線形判別式を入力またはトレーニングデータ空間における複雑な非線形判断境界に対応させる、Ｍｅｒｃｅｒカーネルが使用されてきた。Ｂｏｓｅｒ等の著「Ａ ｔｒａｉｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｏｐｔｉｍａｌ ｍａｒｇｉｎ ｃｌａｓｓｉｆｉｅｒｓ」Ｐｒｏｃ． ５ｔｈ Ａｎｎｕａｌ ＡＣＭ Ｗｏｒｋｓｈｏｐ ｏｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｌｅａｒｎｉｎｇ Ｔｈｅｏｒｙ、ｐｐ． １４４〜１５２、１９９２を参照のこと。また、カーネル法は、主成分分析（ｐｒｉｎｃｉｐａｌ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ（ＰＣＡ））とＦｉｓｈｅｒの線形判別分析（ｌｉｎｅａｒ ｄｉｓｃｒｉｍｉｎａｎｔ ａｎａｌｙｓｉｓ（ＬＤＡ））とに対し、非線形特徴空間を構築するためにも使用されてきた。
【０００６】
カーネルマッピングの最もよく知られている例は、非線形サポートベクトルマシン（ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ（ＳＶＭ））で使用される。Ｖａｐｎｉｋの著「Ｔｈｅ ｎａｔｕｒｅｏｆ ｓｔａｔｉｓｔｉｃａｌ ｌｅａｒｎｉｎｇ ｔｈｅｏｒｙ」Ｓｐｒｉｎｇｅｒ、１９９５を参照のこと。ＳＶＭでは、分類マージン、それ故、汎化における境界が、すべてのトレーニングサンプルに関する同時最適化によって最大化される。ＳＶＭでは、サンプルを判断境界に極めて近接させることができ、サポートベクトルは、単に、判断境界を構築、すなわちサポートするために必要な最小数のトレーニングサンプルである。サポートベクトルは、ほぼ確実にいずれのクラスの「典型」または高可能性メンバではない。また、ＳＶＭの場合、通常、生成されるサポートベクトルの数を制御する直接の方法がない。
【０００７】
【発明が解決しようとする課題】
したがって、最適化タスクを簡略化する分類方法が必要である。また、分類中に使用される判別式の数を制限することも望ましい。
【０００８】
【課題を解決するための手段】
本発明は、超平面判別式によるデータ信号の２値分類の方法を提供する。これらの２項超平面は、対向するクラスからのトレーニングサンプルの対に基づく。本方法はさらに、Ｍｅｒｃｅｒの定理を満足させるカーネル関数を使用することにより非線形判別式に拡張される。
【０００９】
トレーニング中、信頼度付きブーストにより、２項超平面の集合が学習される。ブーストの各反復中に分類器の有限集合から最適な超平面が選択される。そして、選択された超平面が結合されて最終分類器となる。このため、あり得る分類器の数が制限される。
【００１０】
本発明による方法は、超平面判別式の重ね合せにより複雑な２値分類器を学習（求める）する。各判別式は、トレーニングサンプルの対向する対を結合するベクトル上への射影に基づく。すなわち、「２項（ｄｙａｄｉｃ）」対は、対抗するラベルを有する２つのサンプルからなる。たとえば、第１の集合のサンプルは−１にラベル付けされ、第２の集合のサンプルは＋１にラベル付けされる。学習プロセス自体は、ＡｄａＢｏｏｓｔの「ファジー」実数値型変形に基づき、超平面分類器は、分離不可能な問題を高次元非線形特徴空間に線形にマッピングする、ＳＶＭによって使用されるタイプのカーネルを使用する。
【００１１】
概念クラスが、線形判別式、すなわち超平面からなる場合、これは、２値対を結合するベクトルに対して直交する線形超平面を使用することになる。線形超平面の同じ概念を、Ｍｅｒｃｅｒタイプカーネルによって取得された非線形に変換された特徴空間に適用することにより、ＳＶＭと同様の形式の非線形判別式を提供することができる。
【００１２】
ブーストにより、候補超平面の探索は、すべての２項分類器の空間に及ぶ。このあり得る分類器の空間は、トレーニングデータの部分空間に及び、最適な超平面判別式は、この部分空間に存在しなければならない。この概念は、特徴空間において最適な判別式が変換されたデータのスパンに存在することを留意することにより、カーネル変換によって取得された非線形分類器に容易に拡張される。したがって、線形と非線形との両方の分類問題において、本発明による２項超平面は、すべての分類器の空間を探索する効率的な探索戦略を形成する。
【００１３】
最適な超平面に関するいかなる従来の知識もない場合、トレーニングデータはそれ自体の最良の判別式であり、従来技術によるｋ−ＮＮおよびＳＶＭ分類器に対する基礎も形成する原理である。
【００１４】
より詳細には、方法は、サンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習して求める。まず、トレーニングサンプルの集合が取得される。各トレーニングサンプルは、第１のクラスかまたは第２のクラスのいずれかに属するものとしてラベル付けされる。
【００１５】
２項サンプルの対が、各２項対の第１のサンプルが第１のクラスに属し、各２項対の第２のサンプルが第２のクラスに属するように、射影ベクトル（ｐｒｏｊｅｃｔｉｏｎ ｖｅｃｔｏｒｓ）によって結合される。
【００１６】
超平面の集合は、超平面が射影ベクトルに対し垂直な面を有するように形成される。超平面の集合から、重み付き分類誤差を最小化する１つの超平面が選択される。
【００１７】
そして、トレーニングサンプルの集合が、選択された超平面による分類にしたがって重み付けされる。選択された超平面は結合されて２値分類器となり、所定反復数、選択することと重み付けすることと結合することとが繰返されることにより、テストサンプルを第１および第２のクラスに分類する最終分類器が取得される。
【００１８】
【発明の実施の形態】
超平面判別式
図６は、本発明による２値分類器６０４を学習して求める（ｌｅａｒｎｉｎｇ）方法６００を示す。方法６００は、Ｍ個のトレーニングサンプルの集合６０１、すなわちベクトルＴ＝｛ｘ１，・・・，ｘＭ｝で開始する。トレーニングサンプルｘ∈ＲＮは対応するラベル｛ｙ１，・・・，ｙＭ｝、ここで（ｙ∈｛−１，＋１｝）を有する。ラベル＋１を有するＭｐ個のサンプルとラベル−１を有するＭｎ個のサンプルとがある。すなわち、トレーニングサンプル６０１は、２つのクラスにしたがってラベル付けされ、したがってＭ＝Ｍｐ＋Ｍｎである。入力トレーニングサンプル６０１の集合は、現実の物理的事象やデジタルイメージから測定することができ、また医学的研究等の統計データから収集することができる。
【００１９】
本発明による線形超平面分類器は、以下の形式の判別関数によって定義される。
【００２０】
ｆ｛ｘ｝＝＜ｗ，ｘ＞＋ｂ （１）
【００２１】
ただし、ｓｇｎ ｆ（ｘ）∈｛−１、＋１｝は２値分類を示す。いくつかの仮定、特にガウス性の下では、最適の超平面が射影ベクトルｗによって画定（定義）され、バイアスｂを線形分類器のためのクラス手段およびサンプル共分散に基づいて標準的な統計技法を使用して求めることができる。
【００２２】
本発明では、入力サンプルの分布ｐ（ｘ）に関しいかなる仮定も行わず、代りに最適な分類器６０４、すなわち判別誤差または経験的リスクを最小化する分類器を学習するために、すべてのあり得る超平面の空間を探索することが望まれる。
【００２３】
当然ながら、すべてのあり得る超平面の空間を探索することは実際的ではない。また、この空間のランダムサンプリングは、完全に見当違いである。最適な射影ベクトルｗ＊がトレーニングデータ集合自体のスパンにある、ということがわかる。
【００２４】
トレーニングデータ集合ＴのスパンがＳであり、その直交補空間が
【００２５】
【数２】
【００２６】
である場合、
【００２７】
【数３】
【００２８】
すなわち、空集合となる。これらの２つの部分空間に対する線形拡張により、
【００２９】
【数４】
【００３０】
となる。しかしながら、
【００３１】
【数５】
【００３２】
であるため、定義により、ｗＳ成分のみが判別式
【００３３】
＜ｗ・ｘ＞＋ｂ
【００３４】
に対して何らかの影響を及ぼす。したがって、すべての解が、最適な射影ベクトルｗ＊∈Ｓを含む入力データ集合Ｔのスパンになければならない。
【００３５】
線形超平面
ｗ＊を探索する場合、本方法６００は、対抗するクラスからのサンプルの対を結合する線分に対して垂直な面を有する超平面のみを考慮する。したがって、まず、２項トレーニングサンプル６０１の対を結合する６１０。
【００３６】
ｗｉｊ＝（ｘｉ−ｘｊ）／ｃ ｙｉ≠ｙｊ ｉ＜ｊ （２）
【００３７】
ただし、定義によりｙｉ≠ｙｊであり、一意性のためにｉ＜ｊである。項ｃは、一定のスケールファクタである。ｃ＝｜｜ｘｉ−ｘｊ｜｜と設定すると、ｗｉｊは、１−ノルム方向ベクトルとなる。いずれの場合も、射影ベクトルｗｉｊは対向するクラスからの任意の２つのサンプルｘｉおよびｘｊ、すなわち「２項対」を結合する線分に対して平行である。そして、結合する線分に対して垂直に集合６０２の超平面が形成される６２０。
【００３８】
図１は、２項トレーニングサンプル（ｘｉ，ｘｊ）１０３〜１０４の対向する対を結合する１−ノルム射影ベクトルｗｉｊ１０２によって形成される２項超平面ｈ（ｘ）１０１を示す。
【００３９】
適当なバイアス項ｂｉｊを用いて、式（１）の形式の超平面判別式を得る。２項判別式を使用することにより、ラベル無しテストサンプル６０５を２つのクラス６６１〜６６２に分離することができる。探索するべき存在しうる分類器の空間は、｜｛ｗｉｊ｝｜＝ＭｐＭｎ射影ベクトルの集合を含み、それらの各々は、後述するように一般に重み付き分類誤差を最小化することによって求められる自由パラメータｂｉｊを有する。
【００４０】
そして、各仮説または分類器ｈｉｊ（ｘ）は、以下のように、式（１）のような判別式の符号関数によって与えられる。
【００４１】
ｈｉｊ（ｘ）＝ｓｇｎ（＜ｗ・ｘ＞＋ｂｉｊ） （３）
【００４２】
本明細書では、｛ｈｉｊ｝＝｛ｗｉｊ，ｂｉｊ｝により、トレーニングデータ集合６０１に対し超平面６０２の完全集合を示す。厳密に言えば、この集合は、スカラｂｉｊ∈Ｒのテンソル積が無限となるため無数である。しかしながら、本明細書では、各超平面に対し常に単一の最適なバイアスパラメータを選択するため、実際にはＭｐＭｎの分類器のみで終わる。
【００４３】
図１は、２項サンプル対（ｘｉ，ｘｊ）によって画定され制約される超平面判別式を示す。これは、式（２）のように線形射影ベクトルｗｉｊをもたらす。この射影では、バイアスｂが、最適化すべき唯一のパラメータである。
【００４４】
分類誤差を最小化するために超平面１０１を結合線分１０２に沿ってシフトすることによって、最適化を行うことができる。この例では、この特定の２項対に対し１つのサンプル１１０を正しくラベル付けすることができないことが分かる。そして、誤差ε＝１／２０（０．０５）を有する結果としての分類器が、「最適な」超平面である。
【００４５】
なお、射影ベクトルｗｉｊが与えられると、「最適な」バイアスパラメータｂの推定は、しばしば単純な一次元線探索、もしくは必要な場合は、全数探索である。分類器が同じ最小誤差を有することができるｂ値の範囲または多様性は、この段階では無関係である。
【００４６】
一方、ブースト２００（図２参照）を使用して「強」超平面６０３を形成し、強超平面を結合する６５０ことにより最終超平面または分類器６０４のマージンを最大限にする。
【００４７】
最終分類器６０４を使用して、ラベル無しテストサンプル６０５の集合を２つのクラス６６１〜６６２に分類することができる６６０。
【００４８】
ブースト
ブースト２００は、選択された強分類器６０３を線形結合および閾値設定６５０により結合して単一の最終分類器６０４にする、実際的なフレームワークを提供する。ブーストは、分類の難易度に基づいてトレーニングサンプル６０１に対し、反復的に展開する分布、すなわち重みＤ（ｉ）を維持する。たとえば、分類が困難なサンプルほど、分類が容易なサンプルより大きい重みを有する。したがって、集合６０２における各分類器ｈ（ｘ）：ｘ→｛＋１，−１｝は、以下の重み付き分類誤差を有する。
【００４９】
【数６】
【００５０】
この場合、ブーストの各ラウンドｔにおいて、ＭｐＭｎ個の超平面ｈｉｊ６０２の完全集合から、重み付き分類誤差εを最小化するものを選択する６３０。これに続き、トレーニングサンプル６０１に、更新された分布Ｄｔ＋１を取得するためにそれらの分類または誤分類に基づいて再重み付けする６４０。
【００５１】
図２は、ブースト２００のプロセスを示す。ステップ２１０において、以下のように初期化する。
【００５２】
【数７】
【００５３】
そして、ｔ＝１，・・・，Ｔに対し、以下のステップを反復する。ステップ２２０において、ｈｔ＝ｈ＊ｉｊを設定する。ただし、ｈ＊ｉｊはεｔを最小化する｛ｈｉｊ｝６０２の要素である。ステップ２３０において、
【００５４】
【数８】
【００５５】
を設定する。そして、ステップ２４０において、分布
【００５６】
【数９】
【００５７】
（ＺｔはＤｔに対する正規化）を更新し、終了するまでｔの次の増分に対して繰返す。
【００５８】
最終分類器６０４は、選択された弱分類器ｈｔのα重み付き線形結合６５０であり、以下のように重み付き「投票（ｖｏｔｉｎｇ）」方式の形態を有する。
【００５９】
【数１０】
【００６０】
トレーニング誤差に対する結果としての上界は、以下のようになる。
【００６１】
【数１１】
【００６２】
ブーストの各ラウンドによるこの上界の倍数的に増加する縮小量（ｍｕｌｔｉｐｌｉｃａｔｉｖｅ ｓｈｒｉｎｋａｇｅ）は、ブーストプロセス２００の指数関数的収束と、しばしば急速なトレーニング誤差の低減（時に０まで）と、の証拠である。
【００６３】
ブーストは、ＳＶＭのようなマージン最大化（ｌａｒｇｅ ｍａｒｇｉｎ）分類プロセスのファミリに属する。ブーストにより、サンプル（ｘ，ｙ）のマージンは、範囲［−１，＋１］内にある
【００６４】
【数１２】
【００６５】
によって与えられ、Ｈがサンプルを正しく分類する場合にのみ正である。マージンは、しばしば、分類における信頼性の測度として解釈される。Ｓｃｈａｐｉｒｅ等の著「Ｉｍｐｒｏｖｅｄ ｂｏｏｓｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｕｓｉｎｇ ｃｏｎｆｉｄｅｎｃｅ−ｒａｔｅ ｐｒｅｄｉｃｔｉｏｎ」を参照のこと。分類器ｈｔ（ｘ）は、２進数とは対照的に実数値とすることができ、「信頼度付き予測（ｃｏｎｆｉｄｅｎｃｅ−ｒａｔｅｄ ｐｒｅｄｉｃｔｉｏｎ）」として解釈することができる。この場合、ｈｔ（ｘ）の符号は分類ラベルであり、絶対値｜ｈｔ（ｘ）｜は信頼度である。
【００６６】
かかる連続値または「ファジー」分類器の場合、
【００６７】
【数１３】
【００６８】
となり、このとき
【００６９】
【数１４】
【００７０】
であって、「相関」ｒｔはεｔ＝（１−ｒｔ）／２により誤差に反比例する。この場合、結果としての分類器Ｈの誤差は、
【００７１】
【数１５】
【００７２】
によって上から有界である。
【００７３】
非線形超平面
上述した線形分類器を越えた論理的拡張は、Ｂｏｓｅｒ等（上記参照）によって述べられているような正定「カーネル（ｋｅｒｎｅｌ）」を使用する非線形判別式に対する。ＳＶＭおよびカーネルＰＣＡ等の最近の非線形への発展、またはＳｃｈｏｌｋｏｐｆ等によって述べられているようなカーネルＦｉｓｈｅｒ判別式は、「カーネルＨｉｌｂｅｒｔ空間を再現する」特性に依存する。そこで、高次元マッピングΦ（ｘ）：Ｘ→Ｆによるドット積は、以下のＭｅｒｃｅｒカーネルを使用して評価される。
【００７４】
ｋ（ｘ、ｘ’）＝＜Φ（ｘ）・Φ（ｘ’）＞ （１１）
【００７５】
これは、たとえば式（３）における本発明による線形超平面分類器等、ドット積に基づくいかなるプロセスも、カーネルを使用して入力サンプルを非線形にマッピングし、変換された特徴空間において暗示的にドット積を実行することができる、という望ましい特性を有する。したがって、入力空間に戻る線形超平面解のプリイメージは非線形超平面である。
【００７６】
式（２）における上記カーネル特性を使用して、最初に、射影ベクトルが式（２）に形式が類似した
【００７７】
ｗｉｊ＝（Φ（ｘｉ）−Φ（ｘｊ）／ｃ ｙｉ≠ｙｊ ｉ＜ｊ （１２）
【００７８】
である変換された特徴空間Ｆにおいて線形分類器を検査することにより、式（３）における分類器を非線形形式に書換えることができる。ここでまた、最適な射影ベクトルｗ＊ｉｊがスパンΦ（ｘｉ）内になければならない、ということを留意する。したがって、それに応じて、たとえばペアワイズ射影ベクトルを考慮することにより、最適な非線形超平面に対する探索を制限する。
【００７９】
しかしながら、非線形マッピングの暗示的特質が与えられたｗｉｊを直接評価することはできない。しかしながら、変換された入力ベクトルΦ（ｘ）によるそのドット積のみがあればよい。式（１）における線形判別式を考慮し、上記を代入すると、以下の式が得られる。
【００８０】
【数１６】
【００８１】
ここで式（１１）におけるカーネル特性を適用することにより、以下の式が得られる。
【００８２】
【数１７】
【００８３】
ここで、定数ｃを、判別の範囲を正規化するように、たとえばｃ＝ｍａｘｉｊ｜ｋ（ｘｉ，ｘｊ）｜であるように設定することができる。
【００８４】
離散値超平面分類器は、以下の符号関数閾値によって与えられる。
【００８５】
ｈｉｊ（ｘ）＝ｓｇｎ（ｆｉｊ（ｘ）） （１５）
【００８６】
これに対し、範囲［−１，＋１］内の出力を有する「信頼度付き（ｃｏｎｆｉｄｅｎｃｅ−ｒａｔｅｄ）」分類器を、ｆｉｊ（）を以下の双曲線正接等、双極のシグモイド関数の非線形性に通すことにより取得することができる。
【００８７】
ｈｉｊ（ｘ）＝ｓｇｎ（βｆｉｊ（ｘ）） （１６）
【００８８】
ただし、βは、シグモイドの「傾き」を確定する。
【００８９】
範囲［−１，＋１］を適当に占める連続値分類器を取得するために、定数ｃおよびβを調整することができる。式（１４）に関し、スカラｃは、所与のトレーニングサンプルの範囲によって決まる。
【００９０】
また、非線形超平面を、それらのカーネルパラメータ、たとえばガウス（Ｇａｕｓｓｉａｎ）カーネルの幅または多項式カーネルの次数に関する最適化とすることができる。しかしながら、実際には、カーネルパラメータの適当な集合は、通常事前に求められ、学習およびブーストプロセス中に固定される。これは、実際に、カーネルパラメータに対する明示的探索および最適化に非常にコストがかかる（ｐｒｏｈｉｂｉｔｉｖｅ）、ＳＶＭおよび動径基底関数（ｒａｄｉａｌ ｂａｓｉｓ ｆｕｎｃｔｉｏｎ（ＲＢＦ））等の他のカーネルベース学習方法に関する場合である。しかしながら、本発明者らは、これを、個々の分類器のパラメータ設定の最適化ではなく「モデル選択」問題として見る。
【００９１】
適用例
本方法を周知のベンチマークに適用する前に、図３ａないし図３ｂに示すように、問題例に対する単純な２Ｄ非線形２項超平面について説明する。各クラスに１０個のサンプル「＋」および「○」がある２０個のサンプルのトレーニングデータ集合を使用した。
【００９２】
図３ａは、本発明による方法を用いたトレーニングデータの分類を示す。この適用例では、ガウスカーネルを使用する。本方法は、判別超平面３００を画定するために２回のみの反復、すなわち２つのベクトル３０１のみを使用することによりこの問題を解決する。超平面３００は、誤差のわずかなマージンを有し、一方の側に湾曲しているが、２項サンプル対が結合された破線３０１が判別境界３００を画定することが分かる。
【００９３】
図３ｂに示すような従来技術と比較するために、同じデータ集合を有するガウスカーネルＳＶＭを使用した。ＳＶＭ法は、４つのサポートベクトル３０２を用いてこの問題を解決する。ＳＶＭ法はよりよいマージンをもたらすが、本方法は、ブーストのラウンドを増大させて同様の結果をもたらす。
【００９４】
ＳＶＭ法と比較すると、本方法の計算負荷は、必要なカーネル評価の総数まで低減する。すべての超平面が２つのカーネル評価を必要とするため、本発明による分類器は、ＳＶＭ法が使用するサポートベクトルの数の半分の反復を使用する。実際に、サンプルｘｉを複数の射影ベクトルｗｉｊの一部とすることができ、対応するカーネルは１回だけ評価されるため、超平面分類器が必要とするカーネル評価の総数は、ブーストのｎ回の反復後、ｎ／２によって制限される。図３ａないし図３ｂの適用例では、本方法は、カーネル評価を３回しか必要としないが、従来技術の方法は４回必要とする。
【００９５】
実験結果
複数の現実のデータ集合に対する本方法の性能を評価し、本方法の性能を、従来技術による分類方法、すなわちガウスＲＢＦおよび線形カーネルを用いる非線形ＳＶＭおよびｋ−最近傍（ｋ−ＮＮ）と比較した。これらの方法のすべてが、実際のトレーニングサンプルから最終分類器を導出する。
【００９６】
機械学習データベースのＵＣＩリポジトリから４つのデータ集合を選択した。これらのデータベースは、Ｂｌａｋｅ， Ｃ．Ｌ．およびＭｅｒｚ， Ｃ．Ｊ．、Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｃａｌｉｆｏｒｎｉａ、Ｉｒｖｉｎｅ、Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ、１９９８による機械学習データベースのＵＣＩリポジトリのウェブサイトのファイル”ＭＬＲｅｐｏｓｉｔｏｒｙ．ｈｔｍｌ”において見ることができる。評価したデータ集合を、表Ａに示す。
【００９７】
表Ａ
データ集合 次元 サイズ
ソナー ３０ ２０８
電離層 ３４ ３５１
スタトログ心臓病 １３ ２７０
ウィスコンシン乳がん ３０ ５６９
【００９８】
評価の目的のために、各データ集合を、全データ集合の１／３サイズにそれぞれ等しい、トレーニング集合と、検査集合と、テスト集合と、にランダムに分割した。学習に使用するトレーニング集合とともに、検査集合に対する誤差率を最低にするために、従来技術による方法のパラメータ、すなわちＮＮの場合のｋおよびＲＢＦカーネルの場合のσを、選択した。これらの値を、ＲＢＦカーネル幅に対し２５個の値の範囲と、ｋ−ＮＮ分類器に対しｋ∈｛１，２，３，・・・，２５｝と、から引出した。検査テストによって選択されたｋの値は、ソナー（Ｓｏｎａｒ）の場合は１、電離層（Ｉｏｎｏｓｐｈｅｒｅ）の場合は３、乳がん（Ｂｒｅａｓｔ Ｃａｎｃｅｒ）の場合は７および心臓病（Ｈｅａｒｔ）の場合は１１であった。各試行において、ｎ／２およびｎ回（ｎは、その試行においてＳＶＭ法によって見つけられたサポートベクトルの数）の反復後に、本発明による超平面法がテストされた。なお、所定数の反復後にブーストプロセス２００を停止することにより、本分類器のサイズを制御することができ、それにより分類器の精度に影響を与えることができる。各試行において、ＳＶＭによるサポートベクトルの数ｎを基底として使用することにより、２つの超平面分類器に対し誤差を評価した。すなわち、１つは、ｎ／２個の超平面を有し、ＳＶＭ法と同じ数のカーネル評価を必要とするものであり、１つは、ｎ個の超平面を有し、２倍の計算を行うものである。
【００９９】
図４ａないし図４ｄのボックスプロット（箱髭図）は、誤差の分布を示す。各ボックスは、分布の四分位範囲にわたり、中心線は、分布の下位四分位と上位四分位との間の中央値を示す。伸びている「髭（ｗｈｉｓｋｅｒ）」は、値の全範囲を示す。なお、図４ｄは、よく見えるように拡大されている。
【０１００】
これらの経験的評価からの第１の観察結果は、ＲＢＦ超平面法が、ＳＶＭに匹敵し、通常はｋ−ＮＮ分類器より優れたテスト性能に達する、ということである。第２の観察結果は、ブーストのラウンドの初期に、サポートベクトルの半分に等しく時にそれより少ない数の超平面で、許容可能な性能に達する、ということである。また、しばしば性能は、後続する反復によって著しくは向上しない。
【０１０１】
図５は、電離層（Ｉｏｎｏｓｐｈｅｒｅ）データ集合に対する実験においてブースト反復の関数として試行誤差をプロットした、本発明による超平面法の進行の例を示す。水平の破線状の基線５０１は、この場合は１２０未満のトレーニング例から７４個のサポートベクトルを使用した、ＳＶＭ法の性能を示す。本方法の誤差５０２は、３０回の反復の後にこの基線５０１に近づき、そこに近接して留まり、最終的に同じ値に収束する。
【０１０２】
また、線形、すなわちドット積カーネルを用いた超平面により実験を行った。この場合、線形超平面の性能は、ＲＢＦカーネルを用いた方法よりわずかに低い。実際に、線形カーネル超平面は、式（１６）におけるソフトマージン出力関数により非線形判別式をもたらす。式（１６）におけるβ値がおよそ０である場合、平面の重ね合せにより線形境界がもたらされる。β値が有限である場合、滑らかな曲線状の超平面が得られる。βが無限である場合、信頼度値の無い堅固な分類器と同じである断片的線形（ｐｉｅｃｅ−ｗｉｓｅ ｌｉｎｅａｒ）境界が得られる。また、本発明による信頼度付き線形超平面は、本質的に、性能においてシグモイドカーネルを用いるＳＶＭと等価である。
【０１０３】
さらに、最適化戦略を、式（４）の分布Ｄｔ（ｉ）に基づくＭｐＭｎ個のあり得る超平面の仮定空間をサンプリングするために使用することにより、必ずしもトレーニングサンプルに基づいておらず、たとえばクラスタ重心または入力データ集合の分布に基づく他の導出されたサンプルに基づくことができる超平面を、形成することができる。
【０１０４】
【発明の効果】
本発明の効果には２つの要素がある。第１に、単純な判別式のファミリ、すなわち超平面を、対向するクラスからのトレーニングサンプルの対、すなわち２項対に基づいて提供し、Ｍｅｒｃｅｒタイプカーネルによる非線形マッピングを考慮することによってこのファミリをカーネル超平面まで拡張する。第２に、区間［−１，１］における連続的な出力をもたらす信頼度付きの実数値の超平面分類器によるブーストに基づく「貪欲な（ｇｒｅｅｄｙ）」選択プロセスを提供する。
【０１０５】
分類に対するこの新たなカーネルベースの方法が、大規模なＱＰ問題を解決する必要無しにＳＶＭを使用する方法と実質的に同様に実行することを示した。さらに、本方法により、計算複雑性またはモデル次数がユーザ選択可能であり、そのため計算の性能とトレードオフすることができる。また、ブーストプロセスにより指数関数的誤差縮小または収束の保証から利益を得る。ブーストのラウンドを増大させることにより、マージン最大化が保証される。
【０１０６】
複数の標準機械学習データ集合に対し、本方法の汎化性能を評価し、しばしば分類時間と分類器サイズとを低減して、確立された従来技術によるＳＶＭ法に匹敵する性能のレベルを示した。実際の適用では、トレーニング時間の増大を犠牲にしてでも複雑性を最小化することがしばしば望ましいため、この性能の利点を強調する。
【０１０７】
本発明を好ましい実施の形態の例として説明したが、本発明の精神および範囲内で他のあらゆる適応および変更を行うことができる、ということが理解されなければならない。したがって、併記の特許請求の範囲の目的は、かかる変形および変更のすべてを発明の真の精神および範囲内にあるものとして包含することである。
【図面の簡単な説明】
【図１】本発明におけるトレーニングサンプルによる超平面判別式を示す図である。
【図２】本発明によるブーストプロセスのフローチャートである。
【図３ａ】本発明による分類を示す図である。
【図３ｂ】従来技術による分類を示す図である。
【図４ａ】適用データ集合に対する分類誤差のボックスプロット（箱髭図）を示す図である。
【図４ｂ】適用データ集合に対する分類誤差のボックスプロット（箱髭図）を示す図である。
【図４ｃ】適用データ集合に対する分類誤差のボックスプロット（箱髭図）を示す図である。
【図４ｄ】適用データ集合に対する分類誤差のボックスプロット（箱髭図）を示す図である。
【図５】ブースト反復の関数としての分類誤差のグラフを示す図である。
【図６】本発明による２値分類器を学習する方法のフローチャートである。
【特許請求の範囲】
【請求項１】
サンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法であって、
各々が第１のクラスかまたは第２のクラスのいずれかに属しているものとしてラベル付けされる、トレーニングサンプルの集合を獲得するステップと、
前記第１のクラスに属する第１のサンプルと前記第２のクラスに属する第２のサンプルからそれぞれなる２項サンプルの対を射影ベクトルにより結合するステップと、
前記射影ベクトルに対して垂直な面を有する超平面の集合を形成するステップと、
前記超平面の集合から、重み付き分類誤差を最小化する１つの超平面を選択するステップと、
前記選択された超平面による分類にしたがって前記トレーニングサンプルの集合に重み付けするステップと、
前記選択された超平面を結合して２値分類器にするステップと、
所定反復数、前記選択することと、重み付けすることと、結合することと、を繰返すことにより、テストサンプルを前記第１のクラスおよび第２のクラスに分類する最終分類器を取得するステップと、
を備えたサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【請求項２】
線形超平面を以下の形式の判別関数により定義し、
ｆ｛ｘ｝＝＜ｗ・ｘ＞＋ｂ
ただし、ｗは射影ベクトルｗであり、ｂはバイアスであり、ｆ（ｘ）∈｛−１，＋１｝は２値分類を示す請求項１記載のサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【請求項３】
前記射影ベクトルは、
ｗｉｊ＝（ｘｉ−ｘｊ）／ｃ
であり、ここで、ｘｉは前記第１のクラスからのサンプルであり、ｘｊは前記第２のクラスからのサンプルであり、ｃは定数のスケールファクタである請求項２記載のサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【請求項４】
Ｍ個のサンプルｘｉの各トレーニングは、重みＤ（ｉ）を有し、前記超平面の集合における各超平面ｈ（ｘ）：ｘ→｛−１，＋１｝は、重み付き分類誤差
【数１】
を有する請求項１記載のサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【請求項５】
前記最終分類器は、前記選択された分類器のα重み付き線形結合である請求項１記載のサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【請求項６】
カーネルを用いてドット積を実行して非線形超平面を生成することにより、カーネルを用いて前記トレーニングサンプルの集合をマッピングするステップをさらに含む請求項１記載のサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【請求項７】
前記射影ベクトルは
ｗｉｊ＝（Φ（ｘｉ）−Φ（ｘｊ））／ｃ
であり、ただし、ｘｉおよびｘｊは２項サンプルの特定の対であり、ｃは一定のスケールファクタであり、Φは前記カーネルを限定する請求項６記載のサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【請求項８】
前記カーネルはガウス関数である請求項６記載のサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【請求項９】
前記カーネルは動径基底関数である請求項６記載のサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【請求項１】
サンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法であって、
各々が第１のクラスかまたは第２のクラスのいずれかに属しているものとしてラベル付けされる、トレーニングサンプルの集合を獲得するステップと、
前記第１のクラスに属する第１のサンプルと前記第２のクラスに属する第２のサンプルからそれぞれなる２項サンプルの対を射影ベクトルにより結合するステップと、
前記射影ベクトルに対して垂直な面を有する超平面の集合を形成するステップと、
前記超平面の集合から、重み付き分類誤差を最小化する１つの超平面を選択するステップと、
前記選択された超平面による分類にしたがって前記トレーニングサンプルの集合に重み付けするステップと、
前記選択された超平面を結合して２値分類器にするステップと、
所定反復数、前記選択することと、重み付けすることと、結合することと、を繰返すことにより、テストサンプルを前記第１のクラスおよび第２のクラスに分類する最終分類器を取得するステップと、
を備えたサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【請求項２】
線形超平面を以下の形式の判別関数により定義し、
ｆ｛ｘ｝＝＜ｗ・ｘ＞＋ｂ
ただし、ｗは射影ベクトルｗであり、ｂはバイアスであり、ｆ（ｘ）∈｛−１，＋１｝は２値分類を示す請求項１記載のサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【請求項３】
前記射影ベクトルは、
ｗｉｊ＝（ｘｉ−ｘｊ）／ｃ
であり、ここで、ｘｉは前記第１のクラスからのサンプルであり、ｘｊは前記第２のクラスからのサンプルであり、ｃは定数のスケールファクタである請求項２記載のサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【請求項４】
Ｍ個のサンプルｘｉの各トレーニングは、重みＤ（ｉ）を有し、前記超平面の集合における各超平面ｈ（ｘ）：ｘ→｛−１，＋１｝は、重み付き分類誤差
【数１】
を有する請求項１記載のサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【請求項５】
前記最終分類器は、前記選択された分類器のα重み付き線形結合である請求項１記載のサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【請求項６】
カーネルを用いてドット積を実行して非線形超平面を生成することにより、カーネルを用いて前記トレーニングサンプルの集合をマッピングするステップをさらに含む請求項１記載のサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【請求項７】
前記射影ベクトルは
ｗｉｊ＝（Φ（ｘｉ）−Φ（ｘｊ））／ｃ
であり、ただし、ｘｉおよびｘｊは２項サンプルの特定の対であり、ｃは一定のスケールファクタであり、Φは前記カーネルを限定する請求項６記載のサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【請求項８】
前記カーネルはガウス関数である請求項６記載のサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【請求項９】
前記カーネルは動径基底関数である請求項６記載のサンプルを第１のクラスと第２のクラスとに分類する２値分類器を学習する方法。
【図１】
【図２】
【図３ａ】
【図３ｂ】
【図４ａ】
【図４ｂ】
【図４ｃ】
【図４ｄ】
【図５】
【図６】
【図２】
【図３ａ】
【図３ｂ】
【図４ａ】
【図４ｂ】
【図４ｃ】
【図４ｄ】
【図５】
【図６】
【公開番号】特開２００４−１２７２３８（Ｐ２００４−１２７２３８Ａ）
【公開日】平成１６年４月２２日（２００４．４．２２）
【国際特許分類】
【外国語出願】
【出願番号】特願２００３−１０８５１９（Ｐ２００３−１０８５１９）
【出願日】平成１５年４月１４日（２００３．４．１４）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
【公開日】平成１６年４月２２日（２００４．４．２２）
【国際特許分類】
【出願番号】特願２００３−１０８５１９（Ｐ２００３−１０８５１９）
【出願日】平成１５年４月１４日（２００３．４．１４）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
[ Back to top ]