周波数特徴を選択する方法
【課題】計算複雑度が極度に高い処理を、高い分類性能を達成しながら、データ分類にかかる時間を低減できる、サポートベクターマシンを用いたデータ分類方法を提供する。
【解決手段】線形分類器を用いたデータの二項分類に用いられる周波数特徴が、ｄ次元のラベル付けされたトレーニングデータを用いてｄ次元空間において仮説のセットを求めることによって選択される。仮説ごとにマッピング関数が構築される。マッピング関数がトレーニングデータに適用されて周波数特徴が生成され、周波数のサブセットが反復的に選択される。次に、周波数特徴のサブセットおよびトレーニングデータのラベルを用いて線形関数がトレーニングされる。
【解決手段】線形分類器を用いたデータの二項分類に用いられる周波数特徴が、ｄ次元のラベル付けされたトレーニングデータを用いてｄ次元空間において仮説のセットを求めることによって選択される。仮説ごとにマッピング関数が構築される。マッピング関数がトレーニングデータに適用されて周波数特徴が生成され、周波数のサブセットが反復的に選択される。次に、周波数特徴のサブセットおよびトレーニングデータのラベルを用いて線形関数がトレーニングされる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはデータを分類することに関し、より詳細には、線形サポートベクターマシンを用いて二項分類の非線形特徴を選択することに関する。
【背景技術】
【０００２】
サポートベクターマシン（ＳＶＭ）は、多くの場合にデータの二項分類に用いられる。ＳＶＭは、線形カーネルまたは非線形カーネルとともに機能することができる。ＳＶＭは、高次元空間または無限次元空間において、分類、回帰、または他のタスクに用いることができる超平面または超平面のセットを構築する。良好な分離は、最も近いトレーニングデータへの最も大きい距離を有する超平面が存在する場合、該超平面によって達成される。なぜなら、一般に、マージンが大きくなるほど、分類器の汎化誤差が低くなるためである。放射基底関数ＳＶＭは、分離超平面を、より高い、場合によっては無限の次元空間にリフティングするので、２つのクラス間の任意の判定境界を近似することができる。
【０００３】
しかしながら、ＳＶＭは、トレーニングデータ量が非常に多いときに非線形カーネルに対し良好にスケーリングしない。放射基底関数ＳＶＭ等の非線形ＳＶＭをトレーニングすることには数日かかる可能性があり、非線形ＳＶＭを用いた未知のデータのテストは、実際の用途に組み込むには極めて低速となる可能性がある。これは、線形カーネルが用いられる場合、特にデータの次元数が小さいときにはあてはまらない。
【０００４】
カーネルがガウス放射基底関数を用いる場合、対応する特徴空間は、無限次元のヒルベルト空間である。非線形カーネルの場合、ここではＮ（サポートベクトル数）個のカーネル評価を用いて、再生カーネルヒルベルト空間（ＲＫＨＳ）における超平面の法線ベクトルに対する未知のデータの射影を求めなくてはならない。これは、無限次元となる可能性があるＲＫＨＳへの直接アクセスではなく、カーネル関数によって提供された内積を通じた間接アクセスを有するためである。
【０００５】
１つの可能な解決法は、カーネル行列を因数分解し、因子行列の列を、線形カーネルを有する特徴として用いて、非線形カーネルの計算が複雑になるのを回避することである。線形カーネルを用いた未知のデータの分類は、２つのデータクラス間の分離超平面の法線ベクトルを射影しさえすればよいので、高速である。
【０００６】
別の解決法は、ランダムでデータ盲目的なフーリエ特徴の空間内のカーネルを、変換データの内積として近似することであり、これらの特徴に対し、線形カーネルをトレーニングすることができる。この手法では、必要なフーリエ特徴数が比較的小さく、すなわち、フーリエ特徴の空間の次元数が低く、かつ線形カーネルを用いたトレーニングが非線形カーネルを用いたトレーニングよりもかなり高速であることが知られている。しかしながら、トレーニングされたＳＶＭは、盲目的であり、事前データを一切用いることができず、分類性能が限られている。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
いくつかの用途の場合、分類の計算複雑度が極度に高い。したがって、非線形カーネルのような高い分類性能を達成しながら、データ分類にかかる時間を低減することが望ましい。
【課題を解決するための手段】
【０００８】
本発明の実施の形態は、サポートベクターマシンを用いて元の領域の代わりに周波数領域においてデータを分類する方法を提供する。
【０００９】
周波数特徴のセットがトレーニングデータから選択される。特徴のセットは、連続したシフト不変のカーネルを表すのに十分である。次に、特徴選択、例えば、ＬｏｇｉｔＢｏｏｓｔプロセスを適用して、特徴のセットのサブセットを反復的に選択し、分類正確度を直接最適化する。
【００１０】
本発明では、以下のマッピングを構築する。二項分類タスクの場合、ラベルｙｉを有するトレーニングデータｘｉ、すなわち｛ｘｉ，ｙｉ｝（ここでｘｉ∈Ｒｄおよびｙｉ∈｛−１，＋１｝である）を所与とすると、ＳＶＭリフティング関数Φ：Ｒｄ→Ｒｍは、入力データ点ｘを、Φによって規定された周波数特徴空間に、
【数１】
となるようにマッピングする。
【００１１】
ここで、周波数特徴は、ｚω（ｘ）ｊである。本発明の１つの焦点は、周波数特徴の選択である。二項データ分類タスクのためのＳＶＭのトレーニングフェーズおよび分類フェーズの双方を加速するために、入力データを周波数特徴のデータ駆動型低次元空間にマッピングする。
【００１２】
データを｛ｘｉ，ｙｉ｝→｛ｚ（ｘｉ），ｙｉ｝に変換した後、線形分類器をトレーニングする。この線形分類器は、１つの実施の形態では、低次元周波数特徴空間における線形カーネルを有するＳＶＭである。ｍは、ｄよりも大幅に小さいので、トレーニングおよび分類の双方の観点で、ＳＶＭの計算複雑度の劇的な低減が得られ、分類性能は、より良好にならないにしても劣っていない。
【００１３】
まず、変換データの内積が、仮説特徴を介して、所定の連続したシフト不変カーネルの再生カーネルヒルベルト空間内の内積に概ね等しくなるように、ラベル付けされたトレーニングデータを用いて特徴のセットを生成する。これらの特徴のサブセットを、カーネル関数を近似するのと対照的に、分類正確度を直接ターゲットにする特徴選択プロセスによって選択する。特に、ＬｏｇｉｔＢｏｏｓｔプロセスを特徴選択プロセスとして用い、次に、線形分類器を適用する。線形分類器には、線形カーネルを有するＳＶＭを用いる。
【００１４】
役に立たないか、冗長であるか、または無関係の特徴を除去するために、特徴選択を適用する。特徴選択は、正確なモデルを構築するための関連する特徴のサブセットを選択する。データから最も無関係で冗長な特徴を取り除くことによって、特徴選択は、次元の呪いの影響を軽減し、汎化能力を高め、トレーニングプロセスを高速化し、モデル解釈可能性を改善することによってモデルの性能を改善するのに役立つ。特徴選択は、重要な特徴およびそれらの関係も示す。
【００１５】
トレーニングプロセスを高速化するために、特徴選択のための元の周波数ベースのサブセットを求める。最適なサブセットを求めることは、組合せ問題であるため非常に困難である。このため、本発明の特徴選択では、反復的な解法に従う。このようにして、有用な特徴のみが線形ＳＶＭをトレーニングするために選択される。カーネル関数を内積として近似し、分類の観点から非判別的な特徴を除去することによって、トレーニングおよび分類の双方の観点からカーネルマシンの計算複雑度の大幅な低減が得られる。
【００１６】
特徴は、トレーニングデータおよびそれらの対応するラベルを用いて選択される。このため、本方法は、教師あり法である。さらに、本方法は、カーネル関数を近似しない。代わりに、新たなカーネルを内積として構築する。このため、本方法は、カーネル設計として特徴付けられ、このため、本方法の分類正確度は、あらかじめ設定されたカーネル関数によって制限されない。
【００１７】
計算負荷を大きく低減するために、周波数空間内への非線形カーネルのデータ駆動型表現が開示されるのは、これが初めてである。
【発明の効果】
【００１８】
サポートベクターマシンを用いて二項分布の最適な性能を提供するために、データの周波数特徴を抽出して分類境界を表す。特徴をブースティングして冗長な特徴を除去し、関連する特徴のみを用いる。
【００１９】
このようにして、データの非常にコンパクトな表現であるが、依然として２つのクラスを分離する力が十分ある表現が得られる。このため、これによって分類およびカーネルマシンのトレーニングフェーズの測度が改善する。本方法は、結果として大きな速度改善をもたらす。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施の形態によって用いられるサポートベクターマシンの概略図である。
【図２】本発明の実施の形態によって用いられる放射カーネル基底関数サポートベクターマシンの概略図である。
【図３】本発明の実施の形態によって用いられるマッピング関数の概略図である。
【図４】本発明の実施の形態による、周波数空間へのマッピングの概略図である。
【図５】本発明の実施の形態による、周波数マッピングおよびデータ分離の概略図である。
【図６】従来のＳＶＭの性能を本発明の実施の形態によるＳＶＭと比較するグラフである。
【図７】データの二項分類に用いられる周波数特徴を選択する方法の流れ図である。
【発明を実施するための形態】
【００２１】
サポートベクターマシン（ＳＶＭ）
図１は、本発明の実施の形態によって用いられるサポートベクターマシン（ＳＶＭ）１００の基本概念を示している。２つのクラスに分類されることになるデータが、原点１１０に対し黒丸１０１および白丸１０２によって示されている。トレーニングデータから構築された超平面１０３は、２つのクラスを分離する。超平面は、サポートベクトル１０５によってサポートされる。超平面Ｈ１とＨ２との間の分離量は、マージン１０４であり、ｗは、超平面に垂直なベクトルである。
【００２２】
トレーニングデータｘｉおよび対応するラベルｙｉ（ここで、ｘｉ∈Ｒｄおよびｙｉ∈｛−１，＋１｝）を所与とすると、トレーニング手順は、判定関数を構築し、該判定関数によって未知データのクラスが決まる。判定関数は、トレーニングデータの構造に依拠して線形境界または非線形境界を規定することができる。最適な分類がデータの線形関数を通じたものである場合、線形カーネルを用い、そうでない場合、非線形カーネルを用いる。
【００２３】
トレーニングデータは、全てのｉについて
【数２】
となるようなベクトルｗ∈Ｒｄ、転置演算子Ｔ、および実数ｂ∈Ｒが存在する場合、分離可能であり、そうでない場合、データ線形に分離可能でないと判断する。
【００２４】
分離可能データの線形ＳＶＭ
最も単純な事例から始める。分離可能なトレーニングデータ｛ｘｉ，ｙｉ｝（ここで、ｘｉ∈Ｒｄおよびｙｉ∈｛−１，＋１｝）を有し、全てのｉについて、ｙｔ（ｗＴｘｔ＋ｂ）−１≧０となるような少なくとも１つの対（ｗ，ｂ）が存在する。分離可能性を満たす法線ベクトルｗを有する任意の超平面を分類器として用いることができる。理論的に、無限数の超平面が存在する。最適な分離超平面を選択する。
【００２５】
所与の分離超平面について、超平面に対する正のクラス（負のクラス）の点からの最も短い垂直距離が、ｓ＋（ｓ−）とされ、マージンは、ｓ＋＋ｓ−である。
【００２６】
分離超平面について、適切に選択されたｗおよびｂを用いて、いくつかのデータ点について、以下の等式を有することができる。
【００２７】
【数３】
【００２８】
このとき、
【数４】
である。
【００２９】
このように、最適な分離超平面を、マージンを最大にする分離超平面として見つけることができる。分離可能トレーニングデータの線形ＳＶＭは、以下の主最適化を解く。
【００３０】
【数５】
【００３１】
ただし、すべてのｉについて
【数６】
である。上記の最適化の制約を満たすデータがサポートベクトル１０５であり、これを取り除くことによって解が変化する。
【００３２】
問題のラグラシアン定式化に切り換えることによって、結果として凸二次計画問題が生じる。この凸二次計画問題によって、ウォルフ双対定式化を利用することにより、上記の主最適化が、以下のように書き換えられることになる（双対形式最適化）。
【００３３】
【数７】
【００３４】
ただし、
【数８】
である。ここで、αｉは、双対定式化におけるラグランジュパラメーターである。
【００３５】
双対最適化および主最適化によって同じ一意の解、すなわち、最適分離超平面が得られる。双対最適化問題において、αｉ＞０を有するトレーニングセット内のデータは、サポートベクトルである。１つのサポートベクトルであっても取り除くと解が完全に変わる可能性があり、サポートベクトルでない全てのデータを取り除いても問題に対する解が変わらないので、サポートベクトルは、トレーニングデータセットの最も重要な要素である。サポートベクトルは、分離超平面に最も近いデータであるので、サポートベクトルは、トレーニングデータの小さなサブセットでしかない。Ｎ個のサポートベクトルが存在する場合、
【数９】
となる。
【００３６】
ＳＶＭの最適化問題は、重要な態様を有する。制約は、常に線形であり、かつ凸である。これは、カルシュ−キューン−タッカー（ＫＫＴ）条件として知られ、ｗ＊、ｂ＊、ａ＊が最適解となるための必要十分条件である。ＳＶＭ問題のＫＫＴ条件に対する解を求めることは、主双対最適化の数値法を展開する際に中心的な役割を果たす。さらに、双対定式化では、バイアス解ｂ＊は、明確に求められないが、ＫＫＴ条件が成り立たなくてはならないという知識により、バイアスを容易に求めることができる。
【００３７】
分離不可能データの線形ＳＶＭ：ソフトマージンおよびハードマージン
ほとんどの実データについて、データの２つのクラスを完全に分離する超平面は、存在しないため、上記の分離可能性の前提は、緩和される必要がある。まず、分類されるデータが分離不可能なデータである場合、解は、存在しない。このため、次に、これを変更したい。緩和させたいのは、以下である。
【００３８】
【数１０】
【００３９】
これは、誤差が許容されるときに達成することができる。候補超平面の誤った側にあるデータは、データと超平面との間の距離に比例する量だけペナルティを付けられる。この概念を上記の定式化に組み込むために、スラック変数ψを用いる。
【００４０】
【数１１】
【００４１】
このため、誤差が発生するには、対応するψｉが１を超えなくてはならない。このとき、Σψｉを全ての誤差にわたって規定されたコスト関数として最小化するのが当然である。このとき、ＳＶＭ問題の主定式化は、以下となる。
【００４２】
【数１２】
【００４３】
ただし、
【数１３】
である。ここで、Ｃは、誤差最小化とマージン最大化との間のトレードオフを表すパラメーターであり、Ｃが大きくなるとハードマージン分類器が導かれ、結果として過剰適合が生じる可能性があり、Ｃが小さくなるとソフトマージン分類器が導かれる。
【００４４】
それに応じて、双対定式化は以下となる。
【００４５】
【数１４】
【００４６】
ただし、
【数１５】
である。
【００４７】
このため、唯一の違いは、ここで、αｉがＣによって上界を設けられていることである。上述したように、ＫＫＴ条件は、この分離不可能な場合にも容易に適用することができる。
【００４８】
カーネルＳＶＭおよび非線形判定境界
データのクラスを分離することができる超平面が存在しない場合、非線形境界が用いられる。線形ＳＶＭの双対定式化を考えると、データに対する依存性は、ドット積ｘｉ・ｘｊによってのみ生じる。マッピングΦ：Ｒｄ→Ｈ，ｘ→Φ（ｘ）を介して別のユークリッド空間Ｈ（無限次元の可能性がある）にデータをマッピングすることができる。
【００４９】
Ｈ内の線形ＳＶＭをトレーニングする場合、カーネル関数
【数１６】
が既知であるとき、情報Φ（ｘｉ）・ｘｉを提供しさえすればよい。換言すれば、Φのカーネルを有するとき、関数Φを知る必要はない。Ｈ内の線形ＳＶＭをトレーニングするために、以下に従って双対式を変更する。
【００５０】
【数１７】
【００５１】
ただし、
【数１８】
である。
【００５２】
１つの観測は、ｗ∈Ｈであるため、分類のためにｗを明示的に知る必要があるように見える場合がある。しかしながら、関係Ｋ（ｘｉ，ｘｊ）＝Φ（ｘｉ）Φ（ｘｊ）を利用することによって、Ｈにおけるドット積の観点から判定関数を表すことができ、このため、分類は、以下となる。
【００５３】
【数１９】
【００５４】
分類器を未知のデータに適用するために、ＮＳ個のカーネル評価が必要である。これは、用途またはタスクによっては実際的でなく、計算的に過度に複雑になり適用不可能になる可能性がある。これは、以下に起因するＳＶＭの主要な制限のうちの１つである。サポートベクトル数に対し制御がされていない。サポートベクトルは、トレーニングデータから選択されなくてはならない。サポートベクトルが全体空間から選択される場合、サポートベクトルのセットは、はるかに小さくなる。
【００５５】
１つの可能な解決法は、同じ形式の展開を減らしてカーネル分類関数を近似する。すなわち、ＮＳは、ＮＺとなり、ＮＺ＜＜ＮＳである。別の解決法は、サポートベクトルのサブセットのみを用いることである。しかしながら、この解決法の結果、分類性能が著しく低減する。この意味で、サポートベクトルのセットは、最小セットである。
【００５６】
最も一般的に用いられているカーネルは、あるｇについての、よく知られたガウスカーネルまたは放射基底関数（ＲＢＦ）
【数２０】
である。この特定の例では、Ｈは、無限次元である。マッピングΦが明確に知られている場合であっても、無限次元オブジェクトをＳＶＭ定式化に組み込むことは、非常に困難であろう。しかしながら、これは、ＲＢＦカーネルを通じて、トレーニングおよび分類の双方の観点で非常に簡単になる。
【００５７】
図２は、上述したようなマッピング関数Φ（ｘ）２０３を用いた、第１の空間２０１から、第２の、無限次元である可能性がある空間２０２へのＳＶＭのマッピングの全体的な概念を示している。
【００５８】
ＳＶＭにカーネルを用いるという概念は、入力データ２０１を、線形分離可能性を予期する非常に高次元の空間２０２にマッピングする（２０３）ことである。この場合、線形ＳＶＭは、高次元空間内でトレーニングされ、返される超平面は、非線形判定境界に対応する。カーネルを選択することにより、新たな相関構造、すなわち、高次元空間内のドット積が線形分離を可能にするように、非線形カーネルを通じて入力空間の元の相関構造が乱されるので、非線形判定境界が得られる。線形カーネル
【数２１】
を用いる場合、線形ＳＶＭが得られる。
【００５９】
マーセル条件
全ての関数Ｋ：Ｒｄ×Ｒｄ→Ｒが、Ｋ（ｘｉ，ｘｊ）＝Φ（ｘｉ）Φ（ｘｊ）となるように空間ＨおよびマッピングΦ（ｘ）：Ｒｄ→Ｈに対応するとは限らない。換言すれば、全てのＫがカーネルであるとは限らない。関数Ｋがカーネルであるか否かを判断するために、マーセル条件を用いることができる。ここで、Ｋは、全ての二乗可積分関数について
【数２２】
である場合にのみ、カーネルである。
【００６０】
周波数特徴
ターゲット画像領域の検出は、車両ナビゲーションを含む多くの用途において、重要なタスクである。この目的で、走査ウィンドウを入力画像にわたって適用することによって、ＳＶＭ分類器を用いて、例えば、道路標識を検出することが可能である。道路標識の大きさは、未知であるので、走査は、異なる大きさのウィンドウを用いて、複数のスケールで行われなくてはならない。
【００６１】
１つの用途では、１０，０００個の正の画像からなる第１のセットと、１，０００，０００個の負の画像からなる第２のセットとを用いて分類器をトレーニングし、ＮＳ個〜７００個のサポートベクトルを有するカーネル（ＲＢＦ）ＳＶＭ分類器を得る。低レベルの特徴として、全ての画像について勾配方向ヒストグラム（ＨＯＧ）を抽出する。これは
【数２３】
を意味する。本発明の実験によれば、良好な正確度（９０％）では、高精細画像の分類に約２０分かかる。これは、リアルタイムの道路標識検出の場合、計算量が多すぎる。このため、分類時間を低減しなくてはならず、そのためには、カーネルＳＶＭの計算複雑度を低減しなくてはならない。
【００６２】
ここで、非線形カーネルマシンのテストを劇的に高速化する新規の方法を説明する。カーネル関数自体を因数分解するが、この因数分解は、好都合にはデータ駆動型であり、バイナリクラスラベルの分布によって求められた比較的低次元の特徴空間にデータをマッピングすることによって、カーネルマシンのトレーニングおよび評価を線形マシンの対応する動作に変換することが可能になる。
【００６３】
まず、データ点の２つのクラス間の分離境界を近似するのに十分に豊富な周波数特徴のセット、および暗黙的に課す連続したシフト不変のカーネルを生成する。カーネルトリックによって与えられるリフティングに依存する代わりに、変換された点の対間の内積が、それらのカーネル評価ｋ（ｘ，ｙ）＝（φ（ｘ），φ（ｙ））≒ｚ（ｘ）Ｔｚ（ｙ）を近似するように、データ駆動型特徴マップｚ：Ｒｄ→Ｒｍを用いて、データを低次元ユークリッド内積空間に明示的にマッピングする。カーネルのリフティングφｉｚが低次元であるのと異なる。このように、ｚへの周波数マッピングを用いて入力を単に変換することができ、次に線形法を適応して、非線形カーネルを通じて確立された判定境界を近似することができる。
【００６４】
１つの実施の形態では、カーネル関数近似をターゲットにするのとは対照的に、トレーニングにおいて、超平面法線に対するロジスティック回帰である既知のＬｏｇｉｔＢｏｏｓｔプロセスを用いて、分類正確度を直接最適化しながら、このセットから特徴を選択する。仮説のセット、すなわち、ラベル付けされたトレーニングデータから構築される周波数特徴から始める。次に、各仮説についてデータをベクトル上にマッピングする。マッピングデータに対しラベルの加重最小二乗適合を適用し、回帰誤差を計算する。最小回帰誤差を与える仮説を選択する。重みを調整した後、次の仮説を選択する。
【００６５】
このようにして、有用な周波数特徴のみを集めて、線形マシンをトレーニングする。特徴が完全にランダムに独立して集められる従来技術と比較して、本発明では、教師あり設定において利用可能なトレーニングデータおよび対応するラベルを利用する。
【００６６】
非線形分離境界を周波数変換特徴の内積として近似し、特徴選択により非記述的な特徴を除去することによって、これらのデータ駆動型特徴マップにより、分類器を迅速に評価する極めて高速な方法が得られる。例えば、カーネルトリックを用いて、テスト点ｘにおいて放射基底関数サポートベクターマシンを評価することは、境界が単純かつスパースでない限り、データセットの多くを計算し保持するのに、Ｏ（Ｎｄ）個の演算を必要とする。ここで、Ｎは、トレーニング点の数である。これは、大きなデータセットの場合、多くの場合に受入不可能である。他方で、超平面ωを学習した後、線形マシンは、単にｆ（ｘ）＝ωＴｚ（ｘ）によって評価することができる。これは、Ｏ（ｍ（ｄ＋１））個の演算およびストレージしか必要としない。ここで、ｍは、選択された特徴の数である。ほとんどの問題について、ｍ＜＜ｄ＜Ｎであることに留意されたい。
【００６７】
これは、カーネルを近似するのと対照的に、データ駆動型カーネルを当然構築するカーネル設計とみなすこともできる。したがって、本方法の分類正確度は、固定カーネル関数によって上界を設けられない。実際に、計算負荷を大幅に減らすことに加えて、いくつかのデータセットにおいて、より良好な分類結果が得られる。
【００６８】
グループに対する調和解析からのボクナーの定理は、正の有限測度のフーリエ変換を特徴付ける。実線Ｌに対する正の有限ボレル測度μを所与とすると、μのフーリエ変換ｆ（ω）は、連続関数
【数２４】
である。
【００６９】
関数ｆ（ω）は、正定関数であり、すなわち、カーネルｋ（ｘ，ｙ）＝ｆ（ｘ−ｙ）は、正定値である。ボクナーの定理は、逆も真であることを述べており、すなわち、全ての正定関数ｆ（ω）は、正の有限ボレル測度μのフーリエ変換である。
【００７０】
Ｒｄに対する連続カーネルｋ（ｘ、ｙ）＝ｆ（ｘ−ｙ）は、ｆ（ｘ−ｙ）が非負測度のフーリエ変換である場合にのみ正定値である。
【００７１】
カーネルｋ（ｘ，ｙ）が適切にスケーリングされているとき、ボクナーの定理は、そのフーリエ変換ｆ（ω）が適切な確率分布であることを保証する。
【００７２】
【数２５】
【００７３】
ここで、Ｔは、転置演算子である。
【００７４】
換言すれば、
【数２６】
は、ωがフーリエ変換ｆから導き出されたときの、ｋ（ｘ，ｙ）のバイアスされていない推定値である。カーネルは、偶数であり、かつ実数値であり、確率分布ｆ（ω）は、純実数であるので、被積分関数
【数２７】
は、ｃｏｓ（ωＴ（ｘ−ｙ））と置き換えることができる。ｚω（ｘ）Ｔｚω（ｙ）＝ｃｏｓ（ωＴ（ｘ−ｙ））であるので、
【数２８】
を定義することによって、条件Ｅ［ｚω（ｘ）Ｔｚω（ｙ）］＝ｋ（ｘ，ｙ）を満たす実数値マッピングが得られる。換言すれば、各ωは、
【数２９】
としてデータ点を２つの係数にマッピングする。
【００７５】
また、
【数３０】
および
【数３１】
を定義することによっても、この場合は、単一の係数に対し、条件Ｅ［ｚ（ｘ）Ｔｚ（ｙ）］＝ｋ（ｘ，ｙ）を満たす実数値マッピングが得られることを示すことも可能である。ここで、ｎは、セットωｉの濃度であり、ｂは、位相パラメーターであり、データに関して設定することもできるし、［０，２π］から一様に導き出すこともできる。適切に導き出されたベースのセット｛ωｉ｝について、大数の法則により、ｚ（ｘ）Ｔｚ（ｙ）≒ｋ（ｘ，ｙ）である。
【００７６】
換言すれば、ガウスカーネルおよび任意のシフト不変の連続カーネルを、周波数特徴の期待値として書くことができる。ここで、ベースは、確率測度に対してランダムであり、確率測度は、カーネルの逆フーリエ変換である。
【００７７】
この近似によって、非常に興味深い特性が明らかとなる。これは、ガウスカーネル、および任意のシフト不変の連続カーネルを、周波数特徴の空間内のマッピングされた点の内積として近似することができるということである。これは、カーネルトリックとして知られるものと全く同じである。すなわち、データを非常に高次元の空間にマッピングし、該空間において新たな共分散構造がカーネルを通じて生じる。このため、上記の導出によって、周波数特徴の空間内で線形ＳＶＭをトレーニングすることができ、かつ依然としてガウスカーネルの場合と同じ分類正確度を期待することができる。本方法の計算量の低減および高速化は、この結果からもたらされる。
【００７８】
上記では、周波数特徴は、任意の偶数で実数値である非線形カーネルを近似することができることを説明した。しかしながら、このプロセスは、クラスラベル情報または点の密度分布を利用しないので、内容および所与のトレーニングデータを考慮に入れない。
【００７９】
本発明の目標は、プレフィックスされたカーネルを近似することではなく、分類性能を最適化する周波数特徴を介して、複雑な分離境界の線形表現を見つけることである。ここで、問題は、最終分類性能が最適化されるようなωのセットをどのように選択するかということになる。オブジェクト検出タスクのために、クラスメンバーシップを示すバイナリラベルを有するトレーニングデータセットが、多くの場合に利用可能である。これらの追加の事前データを最大限に利用することが望ましい。
【００８０】
これを達成するために、以下のセクションにおいて検討するような、データの負の二項対数尤度を最小にする顕著な周波数特徴を選択する。
【００８１】
ブースティングされた特徴選択
反復的にブースティングすることによって、弱い分類器（仮説）を組み合わせて強い分類器にする。このブースティングは、前の仮説によって誤って分類されたインスタンスを優先する。「ブースティング」において、用語「弱い」および「強い」は、当該技術分野においてよく知られたものとして定義される。各ラウンドにおいて、データ点重みの分布が更新される。誤って分類された各データ点の重みが増やされ、正しく分類された各データ点の重みが減らされ、新たな分類器が、これらの例により集中するようにする。
【００８２】
二項分類問題の場合、ｙｉ∈｛−１，１｝を有する。全てのｎ＝１，．．．，Ｎについて、第１のラウンド
【数３２】
におけるデータ点の重みを初期化する。重み付けされたデータ点に関して弱い分類器ｈｔを選択する。ｘがクラス１にある確率は、
【数３３】
よって表され、全体の応答は、
【数３４】
によって得られる。
【００８３】
ＬｏｇｉｔＢｏｏｓｔプロセスは、ニュートン反復を通じて
【数３５】
によってデータの負の二項対数尤度を最小にすることによって、回帰関数のセットｈｔ（ｘ）｛ｔ＝１，．．．，Ｌ｝を学習する。プロセスのコアにおいて、ＬｏｇｉｔＢｏｏｓｔは、トレーニング点ｘｎの加重最小二乗回帰ｈｔ（ｘ）を適合し、値λｎおよび重みβｎに以下のように応答する。
【００８４】
【数３６】
【００８５】
ここで、
【数３７】
である。
【００８６】
分類器の最終応答は、
【数３８】
である。
【００８７】
各反復において、仮説のセットＳＭ：｛ω１，．．．，ωＭ｝がテストされる。負の指数損失を最も低減する仮説は、仮説Ｓｍのサブセット内に含まれる、現在の弱い分類器としてブースティングされた分類器に結合され、性能レベルが達成されるかまたは計算負荷の上限に達するまで、ｍ個の反復が繰り返される。ここで、ｍは、変換空間の次元数であり、セットの濃度Ｓｍ⊂ＳＭである。
【００８８】
重要な問いは、仮説のセットＳＭ、したがってトレーニングデータに適応するＳｍをどのように求めるかということである。各仮説ωは、周波数特徴
【数３９】
に対応し、２つのクラス間の分離超平面に対する法線となることが望ましい。このベクトルの大きさは、空間合成周波数を表す。
【００８９】
１つの実施の形態では、仮説のセットＳＭを得るために、発生モデルに基づく選択方式を適用する。双方のクラス｛−１，＋１｝の局所密度を示す別個の確率分布関数ｐ−およびｐ＋を抽出する。これらの分布のそれぞれからＭ個の点をサンプリングし、点対｛（ｘ−，ｘ＋）｝｛１，．．．，Ｍ｝を構築する。各仮説は、
【数４０】
となるような対に対応し、合成周波数は、｜ω｜＝π｜ｘ＋−ｘ−｜−１であり、対応する位相シフトは、ｂ＝−ωＴｘ＋である。換言すれば、
【数４１】
かつ
【数４２】
となるように、サンプリングされた対の点を補正されたノルムに連結するベクトルとして、ωを割り当てる。
【００９０】
図５に示すように、分離境界５０１（余弦関数は、無限に多くの符号変化を有するので、複数の分離境界）のうちの１つを、図５に示すような双方の点の中央に配置する。
【００９１】
より密に適合するために確率密度関数ｐ−、ｐ＋を抽出するときに、点重みを組み込むことによって各反復において加重判別制約を適用することも可能である。
【００９２】
ＬｏｇｉｔＢｏｏｓｔ特徴選択後、分類の観点でｍ個の有用な周波数特徴しか有しない。このマッピングは、周波数ベースの性質上、非線形であり、用いる手順は、セットＳＭからｍ個の特徴を選択する。したがって、この新たな変換空間において、線形方法をトレーニングすることができ、
【数４３】
が、ブースティングされた特徴選択によって返される。
【００９３】
周波数マッピングに基づく特徴選択は、冗長で分類に無関係の特徴を除去するのに役立つ。加えて、周波数マッピングに基づく特徴選択は、汎化能力を高め、トレーニングプロセスおよびテスト負荷の双方を高速化する。計算上、上記の変換は、ｍ個のドット積しか必要としない。有用な特徴しか用いないので、セットＳＭは、最小であり、このため、このプロセスにより高速化が生じる。
【００９４】
最適なサブセットを求めることは、性質上、組合せ問題上に射影されるので、ＮＰ困難であることに留意すべきである。しかし、貪欲ブースティングによる解決法は、特にＭ〜Ｎのときにテストフェーズのスピードに影響を及ぼすことなく、満足な性能を与える。
【００９５】
図３は、本発明の実施の形態によって用いられるデータ点４０１のマッピング関数を示している。
【００９６】
図４に示すように、マッピングｘ→ｚω（ｘ）＝［ｃｏｓ（ωＴ（ｘ））ｓｉｎ（ωＴ（ｘ））］Ｔ４００は、データ点４０１を２ｍ’次元空間４０２にマッピングし、他方で、マッピングｘ→ｚω（ｘ）＝ｃｏｓ（ωＴｘ＋ｂ）は、データをｍ次元空間にマッピングする。このため、計算的に、第２のマッピングがよりコンパクトである。このマッピングは、２つのパラメーターおよびさらなる自由度を有する。後続のデータ分布についてｂが固定の場合、１つの単一周波数特徴であっても良好な分類正確度を得るのに十分である。
【００９７】
１つの既知の方法は、ラベルと選択された特徴との間の統計的依存度が最大になるように、貪欲形式で１つずつ特徴を求めることに基づく。しかしながら、依存度最大化を用いることは、選択の測度としての統計的依存性が、ラベルとのデータの非線形関係も考慮するので、本発明の目的に適していない。本発明では、周波数特徴によって非線形特性を既に得ているので、選択後に線形法を適用したいだけである。このため、選択の測度として、線形法である共分散最大化を用いる。
【００９８】
別の実施の形態では、ランダム周波数ベースのセットから始める。次に、このセットからの各基底について、まず本発明の一次元の変換データを生成する。次に、変換データにラベルの加重最小二乗適合を適用する。これによって回帰誤差が与えられる。最小の回帰誤差を与える基底を選択する。重みを調整した後、次の基底を選択する。このプロセスは、本発明の分類に用いる特徴のセットを返す。このセットを構築した後、本発明の最終的な非線形変換を規定する。このため、元のデータのこの最終非線形変換により、分類の観点で有用な周波数特徴のみを有する。
【００９９】
図６は、本方法の性能６０１を、２次元の分離不可能なデータセットの次元数の関数として、従来のＳＶＭ６０２と比較する。
【０１００】
方法
図７は、線形分類器を用いたデータの二項分類に用いられる周波数特徴を選択する本方法の基本ステップを示している。ｄ次元のラベル付けされたトレーニングデータ７０１を用いて、ｄ次元空間内で仮説のセット７１１を求める（７１０）。各仮説についてマッピング関数７２１を構築する（７２０）。
【０１０１】
マッピング関数をトレーニングデータのｄ次元データ点に適用して、周波数特徴７３１を生成し（７３０）、次に、最適な分類性能が得られるｍ個の周波数特徴のサブセットを反復的に選択する（７５０）。選択された特徴は、メモリ内に格納することができる。
【０１０２】
周波数特徴のサブセットおよびトレーニングデータのラベルを用いて、線形分類器ｆ７６１をトレーニングする（７６０）。
【０１０３】
続いて、動作中、テストデータ２０２の周波数特徴を求めることができ（７５５）、線形分類器をテストデータの周波数特徴に適用して（７７０）、テストデータを分類する最終ラベル７７１を得ることができる。
【０１０４】
本方法のステップは、当該技術分野において既知のメモリおよび入力／出力インターフェースに接続されたプロセッサにおいて実行することができる。
【技術分野】
【０００１】
本発明は、包括的にはデータを分類することに関し、より詳細には、線形サポートベクターマシンを用いて二項分類の非線形特徴を選択することに関する。
【背景技術】
【０００２】
サポートベクターマシン（ＳＶＭ）は、多くの場合にデータの二項分類に用いられる。ＳＶＭは、線形カーネルまたは非線形カーネルとともに機能することができる。ＳＶＭは、高次元空間または無限次元空間において、分類、回帰、または他のタスクに用いることができる超平面または超平面のセットを構築する。良好な分離は、最も近いトレーニングデータへの最も大きい距離を有する超平面が存在する場合、該超平面によって達成される。なぜなら、一般に、マージンが大きくなるほど、分類器の汎化誤差が低くなるためである。放射基底関数ＳＶＭは、分離超平面を、より高い、場合によっては無限の次元空間にリフティングするので、２つのクラス間の任意の判定境界を近似することができる。
【０００３】
しかしながら、ＳＶＭは、トレーニングデータ量が非常に多いときに非線形カーネルに対し良好にスケーリングしない。放射基底関数ＳＶＭ等の非線形ＳＶＭをトレーニングすることには数日かかる可能性があり、非線形ＳＶＭを用いた未知のデータのテストは、実際の用途に組み込むには極めて低速となる可能性がある。これは、線形カーネルが用いられる場合、特にデータの次元数が小さいときにはあてはまらない。
【０００４】
カーネルがガウス放射基底関数を用いる場合、対応する特徴空間は、無限次元のヒルベルト空間である。非線形カーネルの場合、ここではＮ（サポートベクトル数）個のカーネル評価を用いて、再生カーネルヒルベルト空間（ＲＫＨＳ）における超平面の法線ベクトルに対する未知のデータの射影を求めなくてはならない。これは、無限次元となる可能性があるＲＫＨＳへの直接アクセスではなく、カーネル関数によって提供された内積を通じた間接アクセスを有するためである。
【０００５】
１つの可能な解決法は、カーネル行列を因数分解し、因子行列の列を、線形カーネルを有する特徴として用いて、非線形カーネルの計算が複雑になるのを回避することである。線形カーネルを用いた未知のデータの分類は、２つのデータクラス間の分離超平面の法線ベクトルを射影しさえすればよいので、高速である。
【０００６】
別の解決法は、ランダムでデータ盲目的なフーリエ特徴の空間内のカーネルを、変換データの内積として近似することであり、これらの特徴に対し、線形カーネルをトレーニングすることができる。この手法では、必要なフーリエ特徴数が比較的小さく、すなわち、フーリエ特徴の空間の次元数が低く、かつ線形カーネルを用いたトレーニングが非線形カーネルを用いたトレーニングよりもかなり高速であることが知られている。しかしながら、トレーニングされたＳＶＭは、盲目的であり、事前データを一切用いることができず、分類性能が限られている。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
いくつかの用途の場合、分類の計算複雑度が極度に高い。したがって、非線形カーネルのような高い分類性能を達成しながら、データ分類にかかる時間を低減することが望ましい。
【課題を解決するための手段】
【０００８】
本発明の実施の形態は、サポートベクターマシンを用いて元の領域の代わりに周波数領域においてデータを分類する方法を提供する。
【０００９】
周波数特徴のセットがトレーニングデータから選択される。特徴のセットは、連続したシフト不変のカーネルを表すのに十分である。次に、特徴選択、例えば、ＬｏｇｉｔＢｏｏｓｔプロセスを適用して、特徴のセットのサブセットを反復的に選択し、分類正確度を直接最適化する。
【００１０】
本発明では、以下のマッピングを構築する。二項分類タスクの場合、ラベルｙｉを有するトレーニングデータｘｉ、すなわち｛ｘｉ，ｙｉ｝（ここでｘｉ∈Ｒｄおよびｙｉ∈｛−１，＋１｝である）を所与とすると、ＳＶＭリフティング関数Φ：Ｒｄ→Ｒｍは、入力データ点ｘを、Φによって規定された周波数特徴空間に、
【数１】
となるようにマッピングする。
【００１１】
ここで、周波数特徴は、ｚω（ｘ）ｊである。本発明の１つの焦点は、周波数特徴の選択である。二項データ分類タスクのためのＳＶＭのトレーニングフェーズおよび分類フェーズの双方を加速するために、入力データを周波数特徴のデータ駆動型低次元空間にマッピングする。
【００１２】
データを｛ｘｉ，ｙｉ｝→｛ｚ（ｘｉ），ｙｉ｝に変換した後、線形分類器をトレーニングする。この線形分類器は、１つの実施の形態では、低次元周波数特徴空間における線形カーネルを有するＳＶＭである。ｍは、ｄよりも大幅に小さいので、トレーニングおよび分類の双方の観点で、ＳＶＭの計算複雑度の劇的な低減が得られ、分類性能は、より良好にならないにしても劣っていない。
【００１３】
まず、変換データの内積が、仮説特徴を介して、所定の連続したシフト不変カーネルの再生カーネルヒルベルト空間内の内積に概ね等しくなるように、ラベル付けされたトレーニングデータを用いて特徴のセットを生成する。これらの特徴のサブセットを、カーネル関数を近似するのと対照的に、分類正確度を直接ターゲットにする特徴選択プロセスによって選択する。特に、ＬｏｇｉｔＢｏｏｓｔプロセスを特徴選択プロセスとして用い、次に、線形分類器を適用する。線形分類器には、線形カーネルを有するＳＶＭを用いる。
【００１４】
役に立たないか、冗長であるか、または無関係の特徴を除去するために、特徴選択を適用する。特徴選択は、正確なモデルを構築するための関連する特徴のサブセットを選択する。データから最も無関係で冗長な特徴を取り除くことによって、特徴選択は、次元の呪いの影響を軽減し、汎化能力を高め、トレーニングプロセスを高速化し、モデル解釈可能性を改善することによってモデルの性能を改善するのに役立つ。特徴選択は、重要な特徴およびそれらの関係も示す。
【００１５】
トレーニングプロセスを高速化するために、特徴選択のための元の周波数ベースのサブセットを求める。最適なサブセットを求めることは、組合せ問題であるため非常に困難である。このため、本発明の特徴選択では、反復的な解法に従う。このようにして、有用な特徴のみが線形ＳＶＭをトレーニングするために選択される。カーネル関数を内積として近似し、分類の観点から非判別的な特徴を除去することによって、トレーニングおよび分類の双方の観点からカーネルマシンの計算複雑度の大幅な低減が得られる。
【００１６】
特徴は、トレーニングデータおよびそれらの対応するラベルを用いて選択される。このため、本方法は、教師あり法である。さらに、本方法は、カーネル関数を近似しない。代わりに、新たなカーネルを内積として構築する。このため、本方法は、カーネル設計として特徴付けられ、このため、本方法の分類正確度は、あらかじめ設定されたカーネル関数によって制限されない。
【００１７】
計算負荷を大きく低減するために、周波数空間内への非線形カーネルのデータ駆動型表現が開示されるのは、これが初めてである。
【発明の効果】
【００１８】
サポートベクターマシンを用いて二項分布の最適な性能を提供するために、データの周波数特徴を抽出して分類境界を表す。特徴をブースティングして冗長な特徴を除去し、関連する特徴のみを用いる。
【００１９】
このようにして、データの非常にコンパクトな表現であるが、依然として２つのクラスを分離する力が十分ある表現が得られる。このため、これによって分類およびカーネルマシンのトレーニングフェーズの測度が改善する。本方法は、結果として大きな速度改善をもたらす。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施の形態によって用いられるサポートベクターマシンの概略図である。
【図２】本発明の実施の形態によって用いられる放射カーネル基底関数サポートベクターマシンの概略図である。
【図３】本発明の実施の形態によって用いられるマッピング関数の概略図である。
【図４】本発明の実施の形態による、周波数空間へのマッピングの概略図である。
【図５】本発明の実施の形態による、周波数マッピングおよびデータ分離の概略図である。
【図６】従来のＳＶＭの性能を本発明の実施の形態によるＳＶＭと比較するグラフである。
【図７】データの二項分類に用いられる周波数特徴を選択する方法の流れ図である。
【発明を実施するための形態】
【００２１】
サポートベクターマシン（ＳＶＭ）
図１は、本発明の実施の形態によって用いられるサポートベクターマシン（ＳＶＭ）１００の基本概念を示している。２つのクラスに分類されることになるデータが、原点１１０に対し黒丸１０１および白丸１０２によって示されている。トレーニングデータから構築された超平面１０３は、２つのクラスを分離する。超平面は、サポートベクトル１０５によってサポートされる。超平面Ｈ１とＨ２との間の分離量は、マージン１０４であり、ｗは、超平面に垂直なベクトルである。
【００２２】
トレーニングデータｘｉおよび対応するラベルｙｉ（ここで、ｘｉ∈Ｒｄおよびｙｉ∈｛−１，＋１｝）を所与とすると、トレーニング手順は、判定関数を構築し、該判定関数によって未知データのクラスが決まる。判定関数は、トレーニングデータの構造に依拠して線形境界または非線形境界を規定することができる。最適な分類がデータの線形関数を通じたものである場合、線形カーネルを用い、そうでない場合、非線形カーネルを用いる。
【００２３】
トレーニングデータは、全てのｉについて
【数２】
となるようなベクトルｗ∈Ｒｄ、転置演算子Ｔ、および実数ｂ∈Ｒが存在する場合、分離可能であり、そうでない場合、データ線形に分離可能でないと判断する。
【００２４】
分離可能データの線形ＳＶＭ
最も単純な事例から始める。分離可能なトレーニングデータ｛ｘｉ，ｙｉ｝（ここで、ｘｉ∈Ｒｄおよびｙｉ∈｛−１，＋１｝）を有し、全てのｉについて、ｙｔ（ｗＴｘｔ＋ｂ）−１≧０となるような少なくとも１つの対（ｗ，ｂ）が存在する。分離可能性を満たす法線ベクトルｗを有する任意の超平面を分類器として用いることができる。理論的に、無限数の超平面が存在する。最適な分離超平面を選択する。
【００２５】
所与の分離超平面について、超平面に対する正のクラス（負のクラス）の点からの最も短い垂直距離が、ｓ＋（ｓ−）とされ、マージンは、ｓ＋＋ｓ−である。
【００２６】
分離超平面について、適切に選択されたｗおよびｂを用いて、いくつかのデータ点について、以下の等式を有することができる。
【００２７】
【数３】
【００２８】
このとき、
【数４】
である。
【００２９】
このように、最適な分離超平面を、マージンを最大にする分離超平面として見つけることができる。分離可能トレーニングデータの線形ＳＶＭは、以下の主最適化を解く。
【００３０】
【数５】
【００３１】
ただし、すべてのｉについて
【数６】
である。上記の最適化の制約を満たすデータがサポートベクトル１０５であり、これを取り除くことによって解が変化する。
【００３２】
問題のラグラシアン定式化に切り換えることによって、結果として凸二次計画問題が生じる。この凸二次計画問題によって、ウォルフ双対定式化を利用することにより、上記の主最適化が、以下のように書き換えられることになる（双対形式最適化）。
【００３３】
【数７】
【００３４】
ただし、
【数８】
である。ここで、αｉは、双対定式化におけるラグランジュパラメーターである。
【００３５】
双対最適化および主最適化によって同じ一意の解、すなわち、最適分離超平面が得られる。双対最適化問題において、αｉ＞０を有するトレーニングセット内のデータは、サポートベクトルである。１つのサポートベクトルであっても取り除くと解が完全に変わる可能性があり、サポートベクトルでない全てのデータを取り除いても問題に対する解が変わらないので、サポートベクトルは、トレーニングデータセットの最も重要な要素である。サポートベクトルは、分離超平面に最も近いデータであるので、サポートベクトルは、トレーニングデータの小さなサブセットでしかない。Ｎ個のサポートベクトルが存在する場合、
【数９】
となる。
【００３６】
ＳＶＭの最適化問題は、重要な態様を有する。制約は、常に線形であり、かつ凸である。これは、カルシュ−キューン−タッカー（ＫＫＴ）条件として知られ、ｗ＊、ｂ＊、ａ＊が最適解となるための必要十分条件である。ＳＶＭ問題のＫＫＴ条件に対する解を求めることは、主双対最適化の数値法を展開する際に中心的な役割を果たす。さらに、双対定式化では、バイアス解ｂ＊は、明確に求められないが、ＫＫＴ条件が成り立たなくてはならないという知識により、バイアスを容易に求めることができる。
【００３７】
分離不可能データの線形ＳＶＭ：ソフトマージンおよびハードマージン
ほとんどの実データについて、データの２つのクラスを完全に分離する超平面は、存在しないため、上記の分離可能性の前提は、緩和される必要がある。まず、分類されるデータが分離不可能なデータである場合、解は、存在しない。このため、次に、これを変更したい。緩和させたいのは、以下である。
【００３８】
【数１０】
【００３９】
これは、誤差が許容されるときに達成することができる。候補超平面の誤った側にあるデータは、データと超平面との間の距離に比例する量だけペナルティを付けられる。この概念を上記の定式化に組み込むために、スラック変数ψを用いる。
【００４０】
【数１１】
【００４１】
このため、誤差が発生するには、対応するψｉが１を超えなくてはならない。このとき、Σψｉを全ての誤差にわたって規定されたコスト関数として最小化するのが当然である。このとき、ＳＶＭ問題の主定式化は、以下となる。
【００４２】
【数１２】
【００４３】
ただし、
【数１３】
である。ここで、Ｃは、誤差最小化とマージン最大化との間のトレードオフを表すパラメーターであり、Ｃが大きくなるとハードマージン分類器が導かれ、結果として過剰適合が生じる可能性があり、Ｃが小さくなるとソフトマージン分類器が導かれる。
【００４４】
それに応じて、双対定式化は以下となる。
【００４５】
【数１４】
【００４６】
ただし、
【数１５】
である。
【００４７】
このため、唯一の違いは、ここで、αｉがＣによって上界を設けられていることである。上述したように、ＫＫＴ条件は、この分離不可能な場合にも容易に適用することができる。
【００４８】
カーネルＳＶＭおよび非線形判定境界
データのクラスを分離することができる超平面が存在しない場合、非線形境界が用いられる。線形ＳＶＭの双対定式化を考えると、データに対する依存性は、ドット積ｘｉ・ｘｊによってのみ生じる。マッピングΦ：Ｒｄ→Ｈ，ｘ→Φ（ｘ）を介して別のユークリッド空間Ｈ（無限次元の可能性がある）にデータをマッピングすることができる。
【００４９】
Ｈ内の線形ＳＶＭをトレーニングする場合、カーネル関数
【数１６】
が既知であるとき、情報Φ（ｘｉ）・ｘｉを提供しさえすればよい。換言すれば、Φのカーネルを有するとき、関数Φを知る必要はない。Ｈ内の線形ＳＶＭをトレーニングするために、以下に従って双対式を変更する。
【００５０】
【数１７】
【００５１】
ただし、
【数１８】
である。
【００５２】
１つの観測は、ｗ∈Ｈであるため、分類のためにｗを明示的に知る必要があるように見える場合がある。しかしながら、関係Ｋ（ｘｉ，ｘｊ）＝Φ（ｘｉ）Φ（ｘｊ）を利用することによって、Ｈにおけるドット積の観点から判定関数を表すことができ、このため、分類は、以下となる。
【００５３】
【数１９】
【００５４】
分類器を未知のデータに適用するために、ＮＳ個のカーネル評価が必要である。これは、用途またはタスクによっては実際的でなく、計算的に過度に複雑になり適用不可能になる可能性がある。これは、以下に起因するＳＶＭの主要な制限のうちの１つである。サポートベクトル数に対し制御がされていない。サポートベクトルは、トレーニングデータから選択されなくてはならない。サポートベクトルが全体空間から選択される場合、サポートベクトルのセットは、はるかに小さくなる。
【００５５】
１つの可能な解決法は、同じ形式の展開を減らしてカーネル分類関数を近似する。すなわち、ＮＳは、ＮＺとなり、ＮＺ＜＜ＮＳである。別の解決法は、サポートベクトルのサブセットのみを用いることである。しかしながら、この解決法の結果、分類性能が著しく低減する。この意味で、サポートベクトルのセットは、最小セットである。
【００５６】
最も一般的に用いられているカーネルは、あるｇについての、よく知られたガウスカーネルまたは放射基底関数（ＲＢＦ）
【数２０】
である。この特定の例では、Ｈは、無限次元である。マッピングΦが明確に知られている場合であっても、無限次元オブジェクトをＳＶＭ定式化に組み込むことは、非常に困難であろう。しかしながら、これは、ＲＢＦカーネルを通じて、トレーニングおよび分類の双方の観点で非常に簡単になる。
【００５７】
図２は、上述したようなマッピング関数Φ（ｘ）２０３を用いた、第１の空間２０１から、第２の、無限次元である可能性がある空間２０２へのＳＶＭのマッピングの全体的な概念を示している。
【００５８】
ＳＶＭにカーネルを用いるという概念は、入力データ２０１を、線形分離可能性を予期する非常に高次元の空間２０２にマッピングする（２０３）ことである。この場合、線形ＳＶＭは、高次元空間内でトレーニングされ、返される超平面は、非線形判定境界に対応する。カーネルを選択することにより、新たな相関構造、すなわち、高次元空間内のドット積が線形分離を可能にするように、非線形カーネルを通じて入力空間の元の相関構造が乱されるので、非線形判定境界が得られる。線形カーネル
【数２１】
を用いる場合、線形ＳＶＭが得られる。
【００５９】
マーセル条件
全ての関数Ｋ：Ｒｄ×Ｒｄ→Ｒが、Ｋ（ｘｉ，ｘｊ）＝Φ（ｘｉ）Φ（ｘｊ）となるように空間ＨおよびマッピングΦ（ｘ）：Ｒｄ→Ｈに対応するとは限らない。換言すれば、全てのＫがカーネルであるとは限らない。関数Ｋがカーネルであるか否かを判断するために、マーセル条件を用いることができる。ここで、Ｋは、全ての二乗可積分関数について
【数２２】
である場合にのみ、カーネルである。
【００６０】
周波数特徴
ターゲット画像領域の検出は、車両ナビゲーションを含む多くの用途において、重要なタスクである。この目的で、走査ウィンドウを入力画像にわたって適用することによって、ＳＶＭ分類器を用いて、例えば、道路標識を検出することが可能である。道路標識の大きさは、未知であるので、走査は、異なる大きさのウィンドウを用いて、複数のスケールで行われなくてはならない。
【００６１】
１つの用途では、１０，０００個の正の画像からなる第１のセットと、１，０００，０００個の負の画像からなる第２のセットとを用いて分類器をトレーニングし、ＮＳ個〜７００個のサポートベクトルを有するカーネル（ＲＢＦ）ＳＶＭ分類器を得る。低レベルの特徴として、全ての画像について勾配方向ヒストグラム（ＨＯＧ）を抽出する。これは
【数２３】
を意味する。本発明の実験によれば、良好な正確度（９０％）では、高精細画像の分類に約２０分かかる。これは、リアルタイムの道路標識検出の場合、計算量が多すぎる。このため、分類時間を低減しなくてはならず、そのためには、カーネルＳＶＭの計算複雑度を低減しなくてはならない。
【００６２】
ここで、非線形カーネルマシンのテストを劇的に高速化する新規の方法を説明する。カーネル関数自体を因数分解するが、この因数分解は、好都合にはデータ駆動型であり、バイナリクラスラベルの分布によって求められた比較的低次元の特徴空間にデータをマッピングすることによって、カーネルマシンのトレーニングおよび評価を線形マシンの対応する動作に変換することが可能になる。
【００６３】
まず、データ点の２つのクラス間の分離境界を近似するのに十分に豊富な周波数特徴のセット、および暗黙的に課す連続したシフト不変のカーネルを生成する。カーネルトリックによって与えられるリフティングに依存する代わりに、変換された点の対間の内積が、それらのカーネル評価ｋ（ｘ，ｙ）＝（φ（ｘ），φ（ｙ））≒ｚ（ｘ）Ｔｚ（ｙ）を近似するように、データ駆動型特徴マップｚ：Ｒｄ→Ｒｍを用いて、データを低次元ユークリッド内積空間に明示的にマッピングする。カーネルのリフティングφｉｚが低次元であるのと異なる。このように、ｚへの周波数マッピングを用いて入力を単に変換することができ、次に線形法を適応して、非線形カーネルを通じて確立された判定境界を近似することができる。
【００６４】
１つの実施の形態では、カーネル関数近似をターゲットにするのとは対照的に、トレーニングにおいて、超平面法線に対するロジスティック回帰である既知のＬｏｇｉｔＢｏｏｓｔプロセスを用いて、分類正確度を直接最適化しながら、このセットから特徴を選択する。仮説のセット、すなわち、ラベル付けされたトレーニングデータから構築される周波数特徴から始める。次に、各仮説についてデータをベクトル上にマッピングする。マッピングデータに対しラベルの加重最小二乗適合を適用し、回帰誤差を計算する。最小回帰誤差を与える仮説を選択する。重みを調整した後、次の仮説を選択する。
【００６５】
このようにして、有用な周波数特徴のみを集めて、線形マシンをトレーニングする。特徴が完全にランダムに独立して集められる従来技術と比較して、本発明では、教師あり設定において利用可能なトレーニングデータおよび対応するラベルを利用する。
【００６６】
非線形分離境界を周波数変換特徴の内積として近似し、特徴選択により非記述的な特徴を除去することによって、これらのデータ駆動型特徴マップにより、分類器を迅速に評価する極めて高速な方法が得られる。例えば、カーネルトリックを用いて、テスト点ｘにおいて放射基底関数サポートベクターマシンを評価することは、境界が単純かつスパースでない限り、データセットの多くを計算し保持するのに、Ｏ（Ｎｄ）個の演算を必要とする。ここで、Ｎは、トレーニング点の数である。これは、大きなデータセットの場合、多くの場合に受入不可能である。他方で、超平面ωを学習した後、線形マシンは、単にｆ（ｘ）＝ωＴｚ（ｘ）によって評価することができる。これは、Ｏ（ｍ（ｄ＋１））個の演算およびストレージしか必要としない。ここで、ｍは、選択された特徴の数である。ほとんどの問題について、ｍ＜＜ｄ＜Ｎであることに留意されたい。
【００６７】
これは、カーネルを近似するのと対照的に、データ駆動型カーネルを当然構築するカーネル設計とみなすこともできる。したがって、本方法の分類正確度は、固定カーネル関数によって上界を設けられない。実際に、計算負荷を大幅に減らすことに加えて、いくつかのデータセットにおいて、より良好な分類結果が得られる。
【００６８】
グループに対する調和解析からのボクナーの定理は、正の有限測度のフーリエ変換を特徴付ける。実線Ｌに対する正の有限ボレル測度μを所与とすると、μのフーリエ変換ｆ（ω）は、連続関数
【数２４】
である。
【００６９】
関数ｆ（ω）は、正定関数であり、すなわち、カーネルｋ（ｘ，ｙ）＝ｆ（ｘ−ｙ）は、正定値である。ボクナーの定理は、逆も真であることを述べており、すなわち、全ての正定関数ｆ（ω）は、正の有限ボレル測度μのフーリエ変換である。
【００７０】
Ｒｄに対する連続カーネルｋ（ｘ、ｙ）＝ｆ（ｘ−ｙ）は、ｆ（ｘ−ｙ）が非負測度のフーリエ変換である場合にのみ正定値である。
【００７１】
カーネルｋ（ｘ，ｙ）が適切にスケーリングされているとき、ボクナーの定理は、そのフーリエ変換ｆ（ω）が適切な確率分布であることを保証する。
【００７２】
【数２５】
【００７３】
ここで、Ｔは、転置演算子である。
【００７４】
換言すれば、
【数２６】
は、ωがフーリエ変換ｆから導き出されたときの、ｋ（ｘ，ｙ）のバイアスされていない推定値である。カーネルは、偶数であり、かつ実数値であり、確率分布ｆ（ω）は、純実数であるので、被積分関数
【数２７】
は、ｃｏｓ（ωＴ（ｘ−ｙ））と置き換えることができる。ｚω（ｘ）Ｔｚω（ｙ）＝ｃｏｓ（ωＴ（ｘ−ｙ））であるので、
【数２８】
を定義することによって、条件Ｅ［ｚω（ｘ）Ｔｚω（ｙ）］＝ｋ（ｘ，ｙ）を満たす実数値マッピングが得られる。換言すれば、各ωは、
【数２９】
としてデータ点を２つの係数にマッピングする。
【００７５】
また、
【数３０】
および
【数３１】
を定義することによっても、この場合は、単一の係数に対し、条件Ｅ［ｚ（ｘ）Ｔｚ（ｙ）］＝ｋ（ｘ，ｙ）を満たす実数値マッピングが得られることを示すことも可能である。ここで、ｎは、セットωｉの濃度であり、ｂは、位相パラメーターであり、データに関して設定することもできるし、［０，２π］から一様に導き出すこともできる。適切に導き出されたベースのセット｛ωｉ｝について、大数の法則により、ｚ（ｘ）Ｔｚ（ｙ）≒ｋ（ｘ，ｙ）である。
【００７６】
換言すれば、ガウスカーネルおよび任意のシフト不変の連続カーネルを、周波数特徴の期待値として書くことができる。ここで、ベースは、確率測度に対してランダムであり、確率測度は、カーネルの逆フーリエ変換である。
【００７７】
この近似によって、非常に興味深い特性が明らかとなる。これは、ガウスカーネル、および任意のシフト不変の連続カーネルを、周波数特徴の空間内のマッピングされた点の内積として近似することができるということである。これは、カーネルトリックとして知られるものと全く同じである。すなわち、データを非常に高次元の空間にマッピングし、該空間において新たな共分散構造がカーネルを通じて生じる。このため、上記の導出によって、周波数特徴の空間内で線形ＳＶＭをトレーニングすることができ、かつ依然としてガウスカーネルの場合と同じ分類正確度を期待することができる。本方法の計算量の低減および高速化は、この結果からもたらされる。
【００７８】
上記では、周波数特徴は、任意の偶数で実数値である非線形カーネルを近似することができることを説明した。しかしながら、このプロセスは、クラスラベル情報または点の密度分布を利用しないので、内容および所与のトレーニングデータを考慮に入れない。
【００７９】
本発明の目標は、プレフィックスされたカーネルを近似することではなく、分類性能を最適化する周波数特徴を介して、複雑な分離境界の線形表現を見つけることである。ここで、問題は、最終分類性能が最適化されるようなωのセットをどのように選択するかということになる。オブジェクト検出タスクのために、クラスメンバーシップを示すバイナリラベルを有するトレーニングデータセットが、多くの場合に利用可能である。これらの追加の事前データを最大限に利用することが望ましい。
【００８０】
これを達成するために、以下のセクションにおいて検討するような、データの負の二項対数尤度を最小にする顕著な周波数特徴を選択する。
【００８１】
ブースティングされた特徴選択
反復的にブースティングすることによって、弱い分類器（仮説）を組み合わせて強い分類器にする。このブースティングは、前の仮説によって誤って分類されたインスタンスを優先する。「ブースティング」において、用語「弱い」および「強い」は、当該技術分野においてよく知られたものとして定義される。各ラウンドにおいて、データ点重みの分布が更新される。誤って分類された各データ点の重みが増やされ、正しく分類された各データ点の重みが減らされ、新たな分類器が、これらの例により集中するようにする。
【００８２】
二項分類問題の場合、ｙｉ∈｛−１，１｝を有する。全てのｎ＝１，．．．，Ｎについて、第１のラウンド
【数３２】
におけるデータ点の重みを初期化する。重み付けされたデータ点に関して弱い分類器ｈｔを選択する。ｘがクラス１にある確率は、
【数３３】
よって表され、全体の応答は、
【数３４】
によって得られる。
【００８３】
ＬｏｇｉｔＢｏｏｓｔプロセスは、ニュートン反復を通じて
【数３５】
によってデータの負の二項対数尤度を最小にすることによって、回帰関数のセットｈｔ（ｘ）｛ｔ＝１，．．．，Ｌ｝を学習する。プロセスのコアにおいて、ＬｏｇｉｔＢｏｏｓｔは、トレーニング点ｘｎの加重最小二乗回帰ｈｔ（ｘ）を適合し、値λｎおよび重みβｎに以下のように応答する。
【００８４】
【数３６】
【００８５】
ここで、
【数３７】
である。
【００８６】
分類器の最終応答は、
【数３８】
である。
【００８７】
各反復において、仮説のセットＳＭ：｛ω１，．．．，ωＭ｝がテストされる。負の指数損失を最も低減する仮説は、仮説Ｓｍのサブセット内に含まれる、現在の弱い分類器としてブースティングされた分類器に結合され、性能レベルが達成されるかまたは計算負荷の上限に達するまで、ｍ個の反復が繰り返される。ここで、ｍは、変換空間の次元数であり、セットの濃度Ｓｍ⊂ＳＭである。
【００８８】
重要な問いは、仮説のセットＳＭ、したがってトレーニングデータに適応するＳｍをどのように求めるかということである。各仮説ωは、周波数特徴
【数３９】
に対応し、２つのクラス間の分離超平面に対する法線となることが望ましい。このベクトルの大きさは、空間合成周波数を表す。
【００８９】
１つの実施の形態では、仮説のセットＳＭを得るために、発生モデルに基づく選択方式を適用する。双方のクラス｛−１，＋１｝の局所密度を示す別個の確率分布関数ｐ−およびｐ＋を抽出する。これらの分布のそれぞれからＭ個の点をサンプリングし、点対｛（ｘ−，ｘ＋）｝｛１，．．．，Ｍ｝を構築する。各仮説は、
【数４０】
となるような対に対応し、合成周波数は、｜ω｜＝π｜ｘ＋−ｘ−｜−１であり、対応する位相シフトは、ｂ＝−ωＴｘ＋である。換言すれば、
【数４１】
かつ
【数４２】
となるように、サンプリングされた対の点を補正されたノルムに連結するベクトルとして、ωを割り当てる。
【００９０】
図５に示すように、分離境界５０１（余弦関数は、無限に多くの符号変化を有するので、複数の分離境界）のうちの１つを、図５に示すような双方の点の中央に配置する。
【００９１】
より密に適合するために確率密度関数ｐ−、ｐ＋を抽出するときに、点重みを組み込むことによって各反復において加重判別制約を適用することも可能である。
【００９２】
ＬｏｇｉｔＢｏｏｓｔ特徴選択後、分類の観点でｍ個の有用な周波数特徴しか有しない。このマッピングは、周波数ベースの性質上、非線形であり、用いる手順は、セットＳＭからｍ個の特徴を選択する。したがって、この新たな変換空間において、線形方法をトレーニングすることができ、
【数４３】
が、ブースティングされた特徴選択によって返される。
【００９３】
周波数マッピングに基づく特徴選択は、冗長で分類に無関係の特徴を除去するのに役立つ。加えて、周波数マッピングに基づく特徴選択は、汎化能力を高め、トレーニングプロセスおよびテスト負荷の双方を高速化する。計算上、上記の変換は、ｍ個のドット積しか必要としない。有用な特徴しか用いないので、セットＳＭは、最小であり、このため、このプロセスにより高速化が生じる。
【００９４】
最適なサブセットを求めることは、性質上、組合せ問題上に射影されるので、ＮＰ困難であることに留意すべきである。しかし、貪欲ブースティングによる解決法は、特にＭ〜Ｎのときにテストフェーズのスピードに影響を及ぼすことなく、満足な性能を与える。
【００９５】
図３は、本発明の実施の形態によって用いられるデータ点４０１のマッピング関数を示している。
【００９６】
図４に示すように、マッピングｘ→ｚω（ｘ）＝［ｃｏｓ（ωＴ（ｘ））ｓｉｎ（ωＴ（ｘ））］Ｔ４００は、データ点４０１を２ｍ’次元空間４０２にマッピングし、他方で、マッピングｘ→ｚω（ｘ）＝ｃｏｓ（ωＴｘ＋ｂ）は、データをｍ次元空間にマッピングする。このため、計算的に、第２のマッピングがよりコンパクトである。このマッピングは、２つのパラメーターおよびさらなる自由度を有する。後続のデータ分布についてｂが固定の場合、１つの単一周波数特徴であっても良好な分類正確度を得るのに十分である。
【００９７】
１つの既知の方法は、ラベルと選択された特徴との間の統計的依存度が最大になるように、貪欲形式で１つずつ特徴を求めることに基づく。しかしながら、依存度最大化を用いることは、選択の測度としての統計的依存性が、ラベルとのデータの非線形関係も考慮するので、本発明の目的に適していない。本発明では、周波数特徴によって非線形特性を既に得ているので、選択後に線形法を適用したいだけである。このため、選択の測度として、線形法である共分散最大化を用いる。
【００９８】
別の実施の形態では、ランダム周波数ベースのセットから始める。次に、このセットからの各基底について、まず本発明の一次元の変換データを生成する。次に、変換データにラベルの加重最小二乗適合を適用する。これによって回帰誤差が与えられる。最小の回帰誤差を与える基底を選択する。重みを調整した後、次の基底を選択する。このプロセスは、本発明の分類に用いる特徴のセットを返す。このセットを構築した後、本発明の最終的な非線形変換を規定する。このため、元のデータのこの最終非線形変換により、分類の観点で有用な周波数特徴のみを有する。
【００９９】
図６は、本方法の性能６０１を、２次元の分離不可能なデータセットの次元数の関数として、従来のＳＶＭ６０２と比較する。
【０１００】
方法
図７は、線形分類器を用いたデータの二項分類に用いられる周波数特徴を選択する本方法の基本ステップを示している。ｄ次元のラベル付けされたトレーニングデータ７０１を用いて、ｄ次元空間内で仮説のセット７１１を求める（７１０）。各仮説についてマッピング関数７２１を構築する（７２０）。
【０１０１】
マッピング関数をトレーニングデータのｄ次元データ点に適用して、周波数特徴７３１を生成し（７３０）、次に、最適な分類性能が得られるｍ個の周波数特徴のサブセットを反復的に選択する（７５０）。選択された特徴は、メモリ内に格納することができる。
【０１０２】
周波数特徴のサブセットおよびトレーニングデータのラベルを用いて、線形分類器ｆ７６１をトレーニングする（７６０）。
【０１０３】
続いて、動作中、テストデータ２０２の周波数特徴を求めることができ（７５５）、線形分類器をテストデータの周波数特徴に適用して（７７０）、テストデータを分類する最終ラベル７７１を得ることができる。
【０１０４】
本方法のステップは、当該技術分野において既知のメモリおよび入力／出力インターフェースに接続されたプロセッサにおいて実行することができる。
【特許請求の範囲】
【請求項１】
線形分類器を用いたデータの二項分類に用いられる周波数特徴を選択する方法であって、
ｄ次元のラベル付けされたトレーニングデータを用いて、ｄ次元空間において仮説のセットを求めるステップと、
前記仮説ごとにマッピング関数を構築するステップと、
周波数特徴を生成するために、前記マッピング関数を前記トレーニングデータに適用するステップと、
前記周波数特徴のサブセットを反復的に選択するステップと、
前記周波数特徴のサブセットおよび前記トレーニングデータのラベルを用いて前記線形分類器をトレーニングするステップと、
を含み、前記ステップのそれぞれは、プロセッサにおいて実行される
線形分類器を用いたデータの二項分類に用いられる周波数特徴を選択する方法。
【請求項２】
前記トレーニングデータは、正のラベルを有する正のトレーニングデータの第１のサブセットと、負のラベルを有する負のトレーニングデータの第２のサブセットとを含み、基底ベクトルが、前記トレーニングデータの前記第１のサブセットと前記第２のサブセットとの間の分離境界を規定する
請求項１に記載の方法。
【請求項３】
前記各仮説は、前記トレーニングデータのベクトルωである
請求項１に記載の方法。
【請求項４】
前記各仮説は、前記トレーニングデータの２つのクラスを分離する超平面に対し垂直なベクトルである
請求項１に記載の方法。
【請求項５】
各仮説ベクトルの大きさは、空間合成周波数である
請求項１に記載の方法。
【請求項６】
前記トレーニングデータから別個の確率分布関数Ｐ＋およびＰ−を抽出するステップであって、Ｐ＋は、正のラベル付けされたデータの前記確率分布関数であり、Ｐ−は、負のトレーニングデータ点のサブセットの前記確率分布関数である、抽出するステップと、
前記分布のそれぞれについてＭ個のデータ点をサンプリングするステップであって、点対
【数１】
を構築し、ここでｘ−は前記分布ｐ−からのデータ点であり、ここでｘ＋は前記分布ｐ＋からのデータ点である、サンプリングするステップと、
前記仮説ωを、前記点対を連結する前記ベクトルとして割り当てるステップと
をさらに含む請求項４に記載の方法。
【請求項７】
前記確率密度関数ｐ＋およびｐ−を抽出する間、加重判別制約を適用する
請求項６に記載の方法。
【請求項８】
マッピング関数が
【数２】
によって規定され、ここで、Ｔは、ベクトル転置演算子であり、ｂは、位相シフトパラメーターである
請求項６に記載の方法。
【請求項９】
Ｒｄ→Ｒ２からの前記マッピング関数は、
【数３】
によって規定され、ここで、Ｔは、ベクトル転置演算子である
請求項６に記載の方法。
【請求項１０】
前記位相シフトは、ｂ＝−ωＴｘ＋である
請求項８に記載の方法。
【請求項１１】
前記周波数特徴のサブセットをブースティング法によって選択する
請求項１に記載の方法。
【請求項１２】
前記選択を、前記線形分類器の所望の性能レベルに達するまで繰り返す
請求項１１に記載の方法。
【請求項１３】
前記選択を、計算負荷の上限に達するまで反復する
請求項１１に記載の方法。
【請求項１４】
前記線形分類器は、線形カーネルを有するサポートベクターマシンである
請求項１に記載の方法。
【請求項１５】
前記仮説のセットをランダムサンプリングによって選択する
請求項１に記載の方法。
【請求項１６】
前記トレーニングデータは、複数のクラスを有する
請求項１に記載の方法。
【請求項１７】
テストデータの前記周波数特徴を求めるステップと、
前記テストデータを分類する最終ラベルを得るために、前記周波数特徴に前記線形分類器を適用するステップと
をさらに含む請求項１に記載の方法。
【請求項１】
線形分類器を用いたデータの二項分類に用いられる周波数特徴を選択する方法であって、
ｄ次元のラベル付けされたトレーニングデータを用いて、ｄ次元空間において仮説のセットを求めるステップと、
前記仮説ごとにマッピング関数を構築するステップと、
周波数特徴を生成するために、前記マッピング関数を前記トレーニングデータに適用するステップと、
前記周波数特徴のサブセットを反復的に選択するステップと、
前記周波数特徴のサブセットおよび前記トレーニングデータのラベルを用いて前記線形分類器をトレーニングするステップと、
を含み、前記ステップのそれぞれは、プロセッサにおいて実行される
線形分類器を用いたデータの二項分類に用いられる周波数特徴を選択する方法。
【請求項２】
前記トレーニングデータは、正のラベルを有する正のトレーニングデータの第１のサブセットと、負のラベルを有する負のトレーニングデータの第２のサブセットとを含み、基底ベクトルが、前記トレーニングデータの前記第１のサブセットと前記第２のサブセットとの間の分離境界を規定する
請求項１に記載の方法。
【請求項３】
前記各仮説は、前記トレーニングデータのベクトルωである
請求項１に記載の方法。
【請求項４】
前記各仮説は、前記トレーニングデータの２つのクラスを分離する超平面に対し垂直なベクトルである
請求項１に記載の方法。
【請求項５】
各仮説ベクトルの大きさは、空間合成周波数である
請求項１に記載の方法。
【請求項６】
前記トレーニングデータから別個の確率分布関数Ｐ＋およびＰ−を抽出するステップであって、Ｐ＋は、正のラベル付けされたデータの前記確率分布関数であり、Ｐ−は、負のトレーニングデータ点のサブセットの前記確率分布関数である、抽出するステップと、
前記分布のそれぞれについてＭ個のデータ点をサンプリングするステップであって、点対
【数１】
を構築し、ここでｘ−は前記分布ｐ−からのデータ点であり、ここでｘ＋は前記分布ｐ＋からのデータ点である、サンプリングするステップと、
前記仮説ωを、前記点対を連結する前記ベクトルとして割り当てるステップと
をさらに含む請求項４に記載の方法。
【請求項７】
前記確率密度関数ｐ＋およびｐ−を抽出する間、加重判別制約を適用する
請求項６に記載の方法。
【請求項８】
マッピング関数が
【数２】
によって規定され、ここで、Ｔは、ベクトル転置演算子であり、ｂは、位相シフトパラメーターである
請求項６に記載の方法。
【請求項９】
Ｒｄ→Ｒ２からの前記マッピング関数は、
【数３】
によって規定され、ここで、Ｔは、ベクトル転置演算子である
請求項６に記載の方法。
【請求項１０】
前記位相シフトは、ｂ＝−ωＴｘ＋である
請求項８に記載の方法。
【請求項１１】
前記周波数特徴のサブセットをブースティング法によって選択する
請求項１に記載の方法。
【請求項１２】
前記選択を、前記線形分類器の所望の性能レベルに達するまで繰り返す
請求項１１に記載の方法。
【請求項１３】
前記選択を、計算負荷の上限に達するまで反復する
請求項１１に記載の方法。
【請求項１４】
前記線形分類器は、線形カーネルを有するサポートベクターマシンである
請求項１に記載の方法。
【請求項１５】
前記仮説のセットをランダムサンプリングによって選択する
請求項１に記載の方法。
【請求項１６】
前記トレーニングデータは、複数のクラスを有する
請求項１に記載の方法。
【請求項１７】
テストデータの前記周波数特徴を求めるステップと、
前記テストデータを分類する最終ラベルを得るために、前記周波数特徴に前記線形分類器を適用するステップと
をさらに含む請求項１に記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１２−２１６１９１（Ｐ２０１２−２１６１９１Ａ）
【公開日】平成２４年１１月８日（２０１２．１１．８）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１２−５２８３１（Ｐ２０１２−５２８３１）
【出願日】平成２４年３月９日（２０１２．３．９）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【公開日】平成２４年１１月８日（２０１２．１１．８）
【国際特許分類】
【出願番号】特願２０１２−５２８３１（Ｐ２０１２−５２８３１）
【出願日】平成２４年３月９日（２０１２．３．９）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
[ Back to top ]