(57)【特許請求の範囲】
【請求項１】
複数の基準ベクトルと入力ベクトルとを引数とするカーネル関数の値の和で表される識別関数を処理する情報処理装置であって、
複数の前記基準ベクトルを取得する取得部と、
複数の前記基準ベクトルに含まれる第１基準ベクトルおよび第２基準ベクトルを統合した統合ベクトルを生成する生成部と、
前記第１基準ベクトルおよび前記第２基準ベクトルを前記統合ベクトルで置き換えた近似関数と、前記識別関数と、の間の、前記入力ベクトルの確率分布に基づく近似誤差の期待値を表す評価値を算出する評価値算出部と、
前記評価値が最小となる前記第１基準ベクトルと前記第２基準ベクトルとを出力する出力制御部と、
を備える情報処理装置。
【請求項２】
前記基準ベクトルは、サポートベクトルマシンの学習により得られるサポートベクトルである、
請求項１に記載の情報処理装置。
【請求項３】
前記入力ベクトルの確率分布は、一様分布または正規分布である、
請求項１に記載の情報処理装置。
【請求項４】
前記入力ベクトルの確率分布は、学習データから推定される、
請求項１に記載の情報処理装置。
【請求項５】
前記入力ベクトルの確率分布は、識別境界からの距離が大きいほど確率密度の値が小さくなる分布である、
請求項１に記載の情報処理装置。
【請求項６】
前記出力制御部は、シミュレーティッド・アニーリング、タブーサーチ、遺伝的アルゴリズムを含むメタヒューリスティクスアルゴリズムにより、前記評価値が最小となる前記第１基準ベクトルと前記第２基準ベクトルとを選択し、選択した前記第１基準ベクトルと前記第２基準ベクトルとを出力する、
請求項１に記載の情報処理装置。
【請求項７】
前記取得部は、１以上のクラスを識別する１以上の識別関数をそれぞれ取得する、
請求項１に記載の情報処理装置。
【請求項８】
複数の基準ベクトルと入力ベクトルとを引数とするカーネル関数の値の和で表される識別関数を処理する情報処理装置で実行される情報処理方法であって、
複数の前記基準ベクトルを取得する取得ステップと、
複数の前記基準ベクトルに含まれる第１基準ベクトルおよび第２基準ベクトルを統合した統合ベクトルを生成する生成ステップと、
前記第１基準ベクトルおよび前記第２基準ベクトルを前記統合ベクトルで置き換えた近似関数と、前記識別関数と、の間の、前記入力ベクトルの確率分布に基づく近似誤差の期待値を表す評価値を算出する評価値算出ステップと、
前記評価値が最小となる前記第１基準ベクトルと前記第２基準ベクトルとを出力する出力制御ステップと、
を含むことを特徴とする情報処理方法。
【請求項９】
複数の基準ベクトルと入力ベクトルとを引数とするカーネル関数の値の和で表される識別関数を処理する情報処理装置を、
複数の前記基準ベクトルを取得する取得部と、
複数の前記基準ベクトルに含まれる第１基準ベクトルおよび第２基準ベクトルを統合した統合ベクトルを生成する生成部と、
前記第１基準ベクトルおよび前記第２基準ベクトルを前記統合ベクトルで置き換えた近似関数と、前記識別関数と、の間の、前記入力ベクトルの確率分布に基づく近似誤差の期待値を表す評価値を算出する評価値算出部と、
前記評価値が最小となる前記第１基準ベクトルと前記第２基準ベクトルとを出力する出力制御部、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法およびプログラムに関する。
【背景技術】
【０００２】
入力ベクトルとクラスのラベルの組から構成される学習データに基づいて識別関数を構成（学習）し、未知の入力ベクトルに対して所属クラスを予測する方法が考案されている。その１つとして、サポートベクトルマシン（以下、ＳＶＭと略記）が存在する。ＳＶＭでは、学習データにおけるサンプルと識別面の間のマージンを最大化することで、高い汎化性能が得られることが知られている。また、識別関数の学習が二次計画問題となるため解の大域最適性が保証され、ニューラルネットワークのような局所解への収束の問題がない、といった利点がある。
【０００３】
一方、ＳＶＭでは学習によって獲得されるサポートベクトル数に比例して、識別にかかる処理時間が増加するという問題がある。そこで、ＳＶＭの識別時の計算コストを低減する技術が考案されている。例えば、学習後に識別関数をより少ない基準ベクトルを用いて近似することで、識別性能の劣化を極力抑えた上で処理時間を低減するアプローチが考案されている。
【０００４】
非特許文献１は、２つのサポートベクトルを統合し、新しい１つのサポートベクトルで置き換える「統合」による方法を提案している。非特許文献２は、多クラス分類のＳＶＭに対するサポートベクトルの「削除」「射影」「統合」を行う方法を提案している。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
サポートベクトルの「削除」は、重みの小さいサポートベクトルが存在しない場合は識別関数を大きく変える可能性があり、識別精度の安定的な維持の点で課題がある。「射影」では、残ったサポートベクトルのすべての重みを更新するため、識別関数の近似に処理時間を要する。また、各々のサポートベクトルが特徴空間で離れている場合は射影による識別関数の変化の吸収には限界がある。「統合」は、２つのサポートベクトルのみを変更するので「射影」に対して計算コストが低く、また識別関数を大きく劣化させる可能性が低い。処理時間低減と識別精度の維持の観点で「統合」によるアプローチのバランスがよいといえる。
【０００６】
従来技術における「統合」のアプローチは、高次元の特徴空間での重みベクトルの変化量の最小化という評価基準を使用している。しかしこの方法は、入力ベクトルの分布が考慮されておらず、近似精度の劣化を招きやすいという問題がある。
【０００７】
本発明は、上記に鑑みてなされたものであって、識別関数の近似精度を向上させることを目的とする。
【課題を解決するための手段】
【０００８】
上述した課題を解決し、目的を達成するために、本発明は、複数の基準ベクトルと入力ベクトルとを引数とするカーネル関数の値の和で表される識別関数を処理する情報処理装置であって、複数の前記基準ベクトルを取得する取得部と、複数の前記基準ベクトルに含まれる第１基準ベクトルおよび第２基準ベクトルを統合した統合ベクトルを生成する生成部と、前記第１基準ベクトルおよび前記第２基準ベクトルを前記統合ベクトルで置き換えた近似関数と、前記識別関数と、の間の、前記入力ベクトルの確率分布に基づく近似誤差の期待値を表す評価値を算出する評価値算出部と、前記評価値が最小となる前記第１基準ベクトルと前記第２基準ベクトルとを出力する出力制御部と、を備える。
【発明の効果】
【０００９】
本発明によれば、識別関数の近似精度を向上させることができるという効果を奏する。
【図面の簡単な説明】
【００１０】
【図１】図１は、第１の実施形態にかかる情報処理装置の構成を示すブロック図である。
【図２】図２は、第１の実施形態における統合処理の一例を示すフローチャートである。
【図３】図３は、第２の実施形態にかかる情報処理装置の構成を示すブロック図である。
【図４】図４は、第３の実施形態にかかる情報処理装置の構成を示すブロック図である。
【図５】図５は、第４の実施形態にかかる情報処理装置の構成を示すブロック図である。
【図６】図６は、第４の実施形態における統合処理の一例を示すフローチャートである。
【図７】図７は、第５の実施形態にかかる情報処理装置の構成を示すブロック図である。
【図８】図８は、第５の実施形態における識別処理の一例を示すフローチャートである。
【図９】図９は、各実施形態にかかる情報処理装置のハードウェア構成例を示す説明図である。
【発明を実施するための形態】
【００１１】
以下に添付図面を参照して、この発明にかかる情報処理装置、情報処理方法およびプログラムの一実施形態を詳細に説明する。
【００１２】
下記の各実施形態は、ＳＶＭに代表されるような複数の基準ベクトルと入力ベクトルを引数としたカーネル関数の和（線形和）により識別関数を示す情報を処理する情報処理装置に関する。各実施形態の情報処理装置は、入力ベクトルの確率分布に基づく識別関数の期待近似誤差を最小化するように基準ベクトルを統合する。このように、識別関数をより少ない数の基準ベクトルで構成して近似することで、処理速度を向上させることができる。各実施形態の情報処理装置は、例えば、動画などの画像からの物体検出、画像を用いた物体追跡、文字認識、および、音声認識など、リアルタイムで学習をしながらパターンを識別する識別装置（アプリケーション）に適用することができる。
【００１３】
（第１の実施形態）
第１の実施形態では、ＳＶＭの識別関数を対象とする例を説明する。この場合、サポートベクトルが基準ベクトルとなる。また本実施形態では、一般的なカーネル関数を使用する例を説明する。適用可能な識別方式はＳＶＭに限られるものではない。
【００１４】
最初に原理を説明する。２クラス分類のＳＶＭで学習を行うと、Ｍ個（Ｍは正の整数）のサポートベクトルｓ（ｉ）∈ＲＤ（ｉ＝１，２，・・・，Ｍ）、対応する重みαｉ∈Ｒ（ｉ＝１，２，・・・，Ｍ）、および、オフセットｂ∈Ｒが求まり、入力ベクトルｘ∈ＲＤに対する以下の（１）式に示す識別関数ｆ（ｘ）が得られる。Ｄは入力空間および特徴空間の次元数を表す。
【数１】
0006676894.tif 000002
【００１５】
ここでＫ（，）はカーネル関数（ＲＤ×ＲＤ→Ｒ）である。ｆ（ｘ）の正負で入力ベクトルｘの属するクラスが予測される。（１）式に示されるように、識別関数ｆ（ｘ）の計算量はサポートベクトルの数Ｍに比例する。Ｍを低減したＬ（＜Ｍ）個のサポートベクトルにより、ｆ（ｘ）を（２）式のように近似すれば、計算量を低減することができる。
【数２】
0006676894.tif 000003
【００１６】
本実施形態では、２つのサポートベクトルを選択し、選択した２つのサポートベクトルを１つのサポートベクトルに統合することでサポートベクトル数を低減する。このような統合のアプローチは、例えば非特許文献１および２でも用いられている。非特許文献１および２では、「入力ベクトルを高次元に写像した特徴空間における重みの変化量の最小化」という基準でサポートベクトルを統合する。具体的には次の通りである。φをカーネルＫ（，）に対応した入力空間から特徴空間への写像とする。このとき（１）式は以下の（３）式のように書き直せる。
【数３】
0006676894.tif 000004
【００１７】
ここで、ｗは高次元の特徴空間での重みであり、以下の（４）式により表される。
【数４】
0006676894.tif 000005
【００１８】
以下の（５）式で表される重みを定義すると、（２）式は以下の（６）式のように表せる。
【数５】
0006676894.tif 000006
【数６】
0006676894.tif 000007
【００１９】
非特許文献１および２では、これらの重みの差分のＬ２ノルムであり、以下の（７）式で表されるＪを評価関数としている。
【数７】
0006676894.tif 000008
【００２０】
一方、（３）式および（６）式から、識別関数の近似誤差は以下の（８）式で表される。この式から分かるように、（７）式を最小化しても入力ベクトルｘの分布に対して近似誤差は最小化されない。ただし、近似誤差の上界は押さえられる（非特許文献２参照）。
【数８】
0006676894.tif 000009
【００２１】
例えば、φ（ｘ）が平均０、共分散Σの正規分布であったとすると、（８）式の期待値は以下の（９）式で表される。
【数９】
0006676894.tif 000010
【００２２】
Σが単位行列でなければ、（７）式の最小化と、この期待値の最小化とは異なる。本実施形態はこの点を鑑みたものであり、入力ベクトルｘの分布ｐ（ｘ）に対する近似誤差の期待値である以下の（１０）式を最小化するように、サポートベクトルを統合する。
【数１０】
0006676894.tif 000011
【００２３】
ｉ番目とｊ番目（ｊ＝１，２，・・・，Ｍ）のサポートベクトルを統合して新しいサポートベクトルｓと重みαを生成するものとする。このとき、（１０）式の評価関数は、以下の（１１）式で表せる。以降、期待値Ｅ［］はすべてｐ（ｘ）に対して算出するものとする。
【数１１】
0006676894.tif 000012
【００２４】
Ｊ（ｓ、α、ｉ，ｊ）をαで偏微分すると、以下の（１２）式のように表せる。
【数１２】
0006676894.tif 000013
【００２５】
極値条件からＪ（ｓ、α、ｉ，ｊ）を最小化するｓ、αは、以下の（１３）式を満たす。
【数１３】
0006676894.tif 000014
【００２６】
また、Ｊ（ｓ、α、ｉ，ｊ）をｓで偏微分すると、以下の（１４）式のように表せる。
【数１４】
0006676894.tif 000015
【００２７】
極値条件からＪ（ｓ、α、ｉ，ｊ）を最小化するｓ、αは、以下の（１５）式を満たす。
【数１５】
0006676894.tif 000016
【００２８】
（１３）式および（１５）式を連立させて解くことにより求められるｓ、αは、固定したｉ，ｊに対してＪ（ｓ、α、ｉ，ｊ）を最小化する。しかし、一般的なカーネル関数Ｋに対して（１３）式および（１５）式を解くことは容易ではない（特殊な場合の解法は後述する）。そこで、次のようなヒューリスティクスを用いる。まず、ｓをｓ（ｉ）およびＳ（ｊ）の線形結合で以下の（１６）式のように表す。
【数１６】
0006676894.tif 000017
【００２９】
高次元での特徴空間でのサポートベクトルはこのような線形結合となることから、入力空間においても同様の関係が近似的に成り立つと仮定する。近似精度はカーネル関数に依存する。（１３）式および（１５）式からαを消去して、条件式の二乗誤差を最小化するｕを一次元探索で求める。このようにして求めたｕから、（１６）式によりｓを求め、さらに（１３）式からαを求める。
【００３０】
カーネル関数によっては（１３）式および（１５）式中の期待値が解析的に求まらない場合がある。その場合は、モンテカルロ法（例えばマルコフ連鎖モンテカルロ法）を用いてｐ（ｘ）からｘを複数サンプリングし、近似的に期待値を求めることができる。
【００３１】
残った問題は、統合するサポートベクトルの選択、すなわち、ｉ，ｊの選択である。単純には、同じクラスに属するサポートベクトルに対してすべての組み合わせを試行し、Ｊ（ｓ、α、ｉ，ｊ）を最小化するｉ，ｊを求めることができる。サポートベクトルが極めて多い場合には、このような全探索では時間がかかる。このため、シミュレーティッド・アニーリング、タブーサーチ、および、遺伝的アルゴリズムに代表されるメタヒューリスティクスアルゴリズムにより最小化を行ってもよい。これにより、すべての基準ベクトルの組に対して探索を行うことを避け、識別関数の近似にかかる計算コストを低減することができる。
【００３２】
以上の原理を元に構成される本実施形態の詳細について以下に説明する。図１は、第１の実施形態にかかる情報処理装置１００の構成を示すブロック図である。
【００３３】
図１に示すように、本実施形態の情報処理装置１００は、記憶部２０と、取得部１０１と、選択部１０２と、生成部１０３と、重み算出部１０４と、評価値算出部１０５と、出力制御部１０６と、を備えている。
【００３４】
記憶部２０は、処理に用いる各種情報を記憶する。例えば記憶部２０は、学習により得られたサポートベクトル、重み、および、オフセットなどの、識別関数を示す情報を記憶する。記憶部２０を情報処理装置１００の外部に備えるように構成してもよい。記憶部２０は、ＨＤＤ（Hard  Disk  Drive）、光ディスク、メモリカード、ＲＡＭ（Random  Access  Memory）などの一般的に利用されているあらゆる記憶媒体により構成することができる。
【００３５】
取得部１０１は、処理対象とする情報を取得する。例えば取得部１０１は、サポートベクトルおよび重みなどの情報を記憶部２０から読み出すことにより取得する。
【００３６】
選択部１０２は、取得したサポートベクトルのうち処理対象とするサポートベクトルを選択する。例えば選択部１０２は、取得されたサポートベクトルのうち、同じクラスに属するｉ番目のサポートベクトル（第１基準ベクトル）と、ｊ番目のサポートベクトル（第２基準ベクトル）を取得する。
【００３７】
生成部１０３は、選択された複数のサポートベクトルを統合した統合ベクトルを生成する。例えば生成部１０３は、上述の原理に従い、ｉ番目のサポートベクトルと、ｊ番目のサポートベクトルとを統合した統合ベクトルｓを生成する。
【００３８】
重み算出部１０４は、生成された統合ベクトルｓの重みを算出する。例えば重み算出部１０４は、上述の原理に従い、統合ベクトルｓの重みαを算出する。
【００３９】
評価値算出部１０５は、統合する前の複数のサポートベクトル（ｉ番目のサポートベクトル、ｊ番目のサポートベクトル）を、統合ベクトルで置き換えた識別関数である近似関数と、識別関数と、の近似誤差を表す評価値を算出する。例えば評価値算出部１０５は、ｓ（ｉ）、ｓ（ｊ）を、ｓで置き換え、αｉ、αｊをαで置き換えた場合の評価関数（（１１）式）の値（評価関数値）を、評価値として求める。
【００４０】
出力制御部１０６は、情報処理の結果などの各種情報を出力する。例えば出力制御部１０６は、評価値（評価関数値）が最小となる第１基準ベクトルと第２基準ベクトルとを出力する。
【００４１】
取得部１０１、選択部１０２、生成部１０３、重み算出部１０４、評価値算出部１０５、および、出力制御部１０６は、例えば、ＣＰＵ（Central  Processing  Unit）などの処理装置にプログラムを実行させること、すなわち、ソフトウェアにより実現してもよいし、ＩＣ（Integrated  Circuit）などのハードウェアにより実現してもよいし、ソフトウェアおよびハードウェアを併用して実現してもよい。
【００４２】
次に、このように構成された第１の実施形態にかかる情報処理装置１００によるサポートベクトルの統合処理について図２を用いて説明する。図２は、第１の実施形態における統合処理の一例を示すフローチャートである。
【００４３】
取得部１０１は、記憶部２０からＳＶＭの学習で得られたサポートベクトルｓ（ｉ）（ｉ＝１，２，・・・，Ｍ）と、対応する重みαｉ（ｉ＝１，２，・・・，Ｍ）を取得する（ステップＳ１０１）。
【００４４】
選択部１０２は、取得されたサポートベクトルから、同じクラスに属するｉ番目とｊ番目のサポートベクトルを選択する（ステップＳ１０２）。選択部１０２は、例えば、ｉ＝１，ｊ＝１から始めて、順にｉとｊをインクリメントし、ｓ（ｉ）およびｓ（ｊ）が異なるクラスに属する場合はスキップして次の組み合わせを選択する。
【００４５】
生成部１０３は、選択されたサポートベクトルｓ（ｉ）およびｓ（ｊ）を統合して、統合ベクトルｓを生成する（ステップＳ１０３）。また重み算出部１０４は、生成された統合ベクトルｓの重みαを算出する（ステップＳ１０４）。
【００４６】
評価値算出部１０５は、ｓ（ｉ）、ｓ（ｊ）を、ｓで置き換え、αｉ、αｊをαで置き換えた場合の評価関数（（１１）式）の値である評価関数値を求める（ステップＳ１０５）。求めた評価関数値が、それ以前に求められた評価関数値の最小値よりも小さい場合、評価値算出部１０５は、統合するサポートベクトルのインデックスｉ，ｊ、ｓ、α、および、評価関数値を例えば記憶部２０に記憶する。
【００４７】
選択部１０２は、終了判定を行う（ステップＳ１０６）。例えば選択部１０２は、同じクラスに属するすべてのサポートベクトルの組が選択済みであれば処理が終了したと判定する。処理が終了していない場合（ステップＳ１０６：Ｎｏ）、ステップＳ１０２に戻り処理が繰り返される。
【００４８】
処理が終了した場合（ステップＳ１０６：Ｙｅｓ）、出力制御部１０６は、評価関数値が最小となるサポートベクトルのインデックスｉ，ｊ、ｓ、αを出力する（ステップＳ１０７）。
【００４９】
以上の処理により、入力ベクトルの分布に基づく近似誤差の期待値を最小化するサポートベクトルの統合が得られる。これにより、識別関数の近似精度を極力保った上で、識別にかかる処理時間を低減することができる。
【００５０】
上記の処理では、２つのサポートベクトルを１つに統合したが、これを複数回繰り返すことでサポートベクトルの数を任意の数まで低減することができる。繰り返しに際して、統合されたサポートベクトルを統合対象に含めてもよいし、統合されたサポートベクトル以外を統合対象としてもよい。統合を繰り返す場合、サポートベクトルの組ごとの評価関数値を最初の繰り返し時に記憶しておいてもよい。これにより、２回目以降の繰り返しでは評価関数値を計算する必要がなくなり、処理を高速化できる。サポートベクトル数をＢ個低減する場合は、それまでに選択されていないサポートベクトルの組の中で評価関数値が最小となるものを、順次Ｂ個選択していけばよい。
【００５１】
（変形例）
統合するサポートベクトルの最適化にメタヒューリスティクスアルゴリズム（シミュレーティッド・アニーリング、タブーサーチ、遺伝的アルゴリズム）を用いてもよい。この場合は、ステップＳ１０２において、最初の繰り返しでは、選択部１０２は初期値としてランダムにｉ，ｊを選択する。選択部１０２は、２回目以降の繰り返しでは前の繰り返し時に得られた識別関数値を用いてメタヒューリスティクスアルゴリズムに基づきｉ，ｊを選択する。このような変形例では、ｉ，ｊのすべての組み合わせに対して評価関数値を求める必要がないため、サポートベクトル統合の処理の高速化ができる。
【００５２】
また、ステップＳ１０６による繰り返しは行わず、ステップＳ１０２でｉ，ｊを選択するときにヒューリスティックな基準を用いてもよい。αｉ、αｊが小さく、ｓ（ｉ）、ｓ（ｊ）の距離が小さいときに、評価関数値（（１１）式）が小さくなる傾向がある。そこで、選択部１０２は、αｉ、αｊが特定閾値以下で、かつ、距離が最小となるｓ（ｉ）、ｓ（ｊ）（Ｋ（ｓ（ｉ）、ｓ（ｊ））が最大となるｓ（ｉ）、ｓ（ｊ））を選択する。例えばサポートベクトル数をＢ個低減する場合、選択部１０２は、αｉ、αｊが特定閾値以下で、かつ、距離が小さい組からＢ個の重複しないｓ（ｉ）、ｓ（ｊ）を選択すればよい。
【００５３】
また、ステップＳ１０３で統合ベクトルを生成する際、ｕを一次元探索せずに、以下の（１７）式に示すように、重みの比率で固定してもよい。
【数１７】
0006676894.tif 000018
【００５４】
このように計算を簡略化することで識別関数の近似精度が劣化する可能性があるが、サポートベクトルの統合にかかる処理時間を低減することができる。例えば、動画の各フレームでオンライン学習する場合では、サポートベクトルを統合する処理時間もリアルタイム性に寄与する。従ってこのような高速化が意味を持つ。
【００５５】
以上では、２クラス分類の例を扱ったが、多クラス分類にも容易に拡張ができる。多クラス分類の場合は、クラスの数だけ識別関数が用意されるが、この各々の識別関数の近似を同様に行えばよい。
【００５６】
（第２の実施形態）
第２の実施形態では、カーネル関数にＲＢＦ（Radial  Basis  Function）カーネルを使う場合を説明する。ＲＢＦカーネルは、以下の（１８）式により定義される。γはパラメータである。
【数１８】
0006676894.tif 000019
【００５７】
ＲＢＦカーネルを使用する場合は、期待値Ｅ［Ｋ（ａ，ｘ）Ｋ（ｂ，ｘ）］は以下の（１９）式により表される。
【数１９】
0006676894.tif 000020
【００５８】
入力ベクトルｘ∈ＲＤの分布ｐ（ｘ）として一様分布を仮定すると、以下の（２０）式が成り立つ。本実施形態では、一様分布に基づく期待値Ｅ［ｆ（ｘ）］は、領域全体に渡ったｆ（ｘ）の累積値（積分値）と定義する。
【数２０】
0006676894.tif 000021
【００５９】
従って、Ｅ［Ｋ（ａ，ｘ）Ｋ（ｂ，ｘ）］は以下の（２１）式で表せる。
【数２１】
0006676894.tif 000022
【００６０】
また、入力ベクトルｘの分布ｐ（ｘ）として平均μ、共分散Σの正規分布を仮定すると、以下の（２２）式が成り立つ。
【数２２】
0006676894.tif 000023
【００６１】
従って、Ｅ［Ｋ（ａ，ｘ）Ｋ（ｂ，ｘ）］は以下の（２３）式で表せる。
【数２３】
0006676894.tif 000024
【００６２】
いずれの場合も、Ｅ［Ｋ（ａ，ｘ）Ｋ（ｂ，ｘ）］は、ａおよびｂに依存しない定数Ｃを用いて以下の（２４）式のように表現できる。ただし、任意のｐ（ｘ）に対して（２４）式が成り立つわけではない。
【数２４】
0006676894.tif 000025
【００６３】
この結果を用いると（１３）式は、以下の（２５）式のように書き換えることができる。
【数２５】
0006676894.tif 000026
【００６４】
また、以下の（２６）式が成り立つ。
【数２６】
0006676894.tif 000027
【００６５】
入力ベクトルｘの分布ｐ（ｘ）に一様分布を仮定すると、（２６）式は以下の（２７）式のように表せる。Ｃ’はａおよびｂに依存しない定数である。
【数２７】
0006676894.tif 000028
【００６６】
この結果を用いると（１５）式は、以下の（２８）式のように書き換えることができる。
【数２８】
0006676894.tif 000029
【００６７】
ここで、ｕを以下の（２９）式で表す。
【数２９】
0006676894.tif 000030
【００６８】
このｕを用いると（２８）式は、以下の（３０）式で表される。第１の実施形態では（１６）式で人為的にｓをｓ（ｉ）およびｓ（ｊ）の線形結合で表現したが、ＲＢＦカーネルでは自然に線形結合の表現が得られる。
【数３０】
0006676894.tif 000031
【００６９】
（３０）式を（２９）式に代入してｓを消去すると、以下の（３１）式が得られる。
【数３１】
0006676894.tif 000032
【００７０】
（３１）式の右辺をｇ（ｕ）と置くと、ｕを求めることは関数ｇ（ｕ）の不動点を求める問題である。ｇ’（ｕ）＜１の領域に解が存在する場合（例えば閉区間［０  １］でｇ’（ｕ）＜１）は、適当な初期値（例えば（１７）式）から始めてｕ←ｇ（ｕ）（ｕへのｇ（ｕ）の代入）を繰り返すことで、解を求めることができる。ｇ’（ｕ）＜１の領域に解が存在しない場合は、ニュートン法で解くか、一次元探索により解くことができる。
【００７１】
ｕが求まると（３０）式からｓが求まり、さらに（２５）式からαが求まる。このときの評価関数値は、以下の（３２）式で表される。
【数３２】
0006676894.tif 000033
【００７２】
この評価関数値を最小化するサポートベクトルのインデックスｉ，ｊが求められる。
【００７３】
以上の原理を元に構成される本実施形態の詳細について以下に説明する。図３は、第２の実施形態にかかる情報処理装置２００の構成を示すブロック図である。
【００７４】
図３に示すように、本実施形態の情報処理装置２００は、記憶部２０と、取得部１０１と、選択部１０２と、生成部２０３と、重み算出部２０４と、評価値算出部２０５と、出力制御部１０６と、を備えている。
【００７５】
第２の実施形態では、生成部２０３、重み算出部２０４、および、評価値算出部２０５の機能が第１の実施形態と異なっている。その他の構成および機能は、第１の実施形態にかかる情報処理装置１００のブロック図である図１と同様であるので、同一符号を付し、ここでの説明は省略する。また第２の実施形態の統合処理の全体の流れは、第１の実施形態の統合処理を示す図２と同様であるため説明を省略する。以下では、第１の実施形態との相違部分を記載する。
【００７６】
図２のステップＳ１０３に対応する処理として、生成部２０３は、選択されたサポートベクトルｓ（ｉ）およびｓ（ｊ）を統合して、統合ベクトルｓを生成する。第１の実施形態の生成部１０３は、例えば（１３）式、（１５）式および（１６）式などを用いて統合ベクトルｓを生成した。本実施形態の生成部２０３は、例えば、（３０）式および（３１）式などを用いて統合ベクトルｓを生成する。
【００７７】
図２のステップＳ１０４に対応する処理として、重み算出部２０４は、生成された統合ベクトルｓの重みαを算出する。重み算出部２０４は、例えば（２５）式を用いて重みαを算出する。
【００７８】
図２のステップＳ１０５に対応する処理として、評価値算出部２０５は、ｓ（ｉ）、ｓ（ｊ）を、ｓで置き換え、αｉ、αｊをαで置き換えた場合の評価関数（（３２）式）の値である評価関数値を求める。求めた評価関数値が、それ以前に求められた評価関数値の最小値よりも小さい場合、評価値算出部２０５は、統合するサポートベクトルのインデックスｉ，ｊ、ｓ、α、および、評価関数値を例えば記憶部２０に記憶する。
【００７９】
本実施形態によれば、カーネル関数にＲＢＦカーネルを使う場合にも、入力ベクトルの分布に基づく近似誤差の期待値を最小化するサポートベクトルの統合が得られる。これにより、識別関数の近似精度を極力保った上で、識別にかかる処理時間を低減することができる。入力ベクトルの確率分布として一様分布または正規分布を用いることにより、入力ベクトルの一様性、または、入力ベクトルの偏りを反映した上で識別関数を近似することができる。
【００８０】
（第３の実施形態）
第３の実施形態では、カーネル関数に指数Ｂｈａｔｔａｃｈａｒｙｙａカーネルを使う場合を説明する。指数Ｂｈａｔｔａｃｈａｒｙｙａカーネルは、以下の（３３）式により定義される。β、γはパラメータである。なお入力ベクトルｘは各要素が０以上の実数で、総和が１になるように正規化されている。指数Ｂｈａｔｔａｃｈａｒｙｙａカーネルは、特にヒストグラム特徴を扱う場合に効果を発揮する。
【数３３】
0006676894.tif 000034
【００８１】
指数Ｂｈａｔｔａｃｈａｒｙｙａカーネルを使用する場合は、期待値Ｅ［Ｋ（ａ，ｘ）Ｋ（ｂ，ｘ）］は以下の（３４）式により表される。
【数３４】
0006676894.tif 000035
ここで、入力ベクトルｘの分布として領域［０  １］Ｄ内での一様分布を考える（厳密には入力ベクトルｘはＤ次元単体上に存在するが近似をする）。このとき、以下の（３５）式が成り立つ。
【数３５】
0006676894.tif 000036
【００８２】
ここでｅｘｐを二次の項までテーラー展開すると、以下の（３６）式が得られる。
【数３６】
0006676894.tif 000037
【００８３】
（３４）式および（３６）式より、以下の（３７）式が得られる。
【数３７】
0006676894.tif 000038
【００８４】
この（３７）式を用いると、（１３）式は以下の（３８）式のように書き換えることができる。
【数３８】
0006676894.tif 000039
【００８５】
また、以下の（３９）式が成り立つ。
【数３９】
0006676894.tif 000040
【００８６】
ここで、入力ベクトルｘの分布として領域［０  １］Ｄ内での一様分布を考え、ｅｘｐを二次の項までテーラー展開すると、以下の（４０）式が得られる。
【数４０】
0006676894.tif 000041
【００８７】
この結果を用いると、（１５）式は以下の（４１）式のように書き換えることができる。ただし、ｔ＝１，２，・・・，Ｄである。
【数４１】
0006676894.tif 000042
【００８８】
（３８）式および（４１）式の拘束式からｓおよびαを求めることができるが、これらの式を解くのは容易ではない。そこで、第１の実施形態と同じ近似解法を用いる。まず、ｓをｓ（ｉ）およびＳ（ｊ）の線形結合で以下の（４２）式のように表す。
【数４２】
0006676894.tif 000043
【００８９】
（３８）式を（４１）式に代入してαを消去して、条件式の二乗誤差を最小化するｕを一次元探索で求める。このようにして求めたｕから、（４１）式よりｓを求め、さらに（３８）式からαを求める。このときの評価関数値は、以下の（４３）式で表される。
【数４３】
0006676894.tif 000044
【００９０】
以上の原理を基に構成される本実施形態の詳細について以下に説明する。図４は、第３の実施形態にかかる情報処理装置３００の構成を示すブロック図である。
【００９１】
図４に示すように、本実施形態の情報処理装置３００は、記憶部２０と、取得部１０１と、選択部１０２と、生成部３０３と、重み算出部３０４と、評価値算出部３０５と、出力制御部１０６と、を備えている。
【００９２】
第３の実施形態では、生成部３０３、重み算出部３０４、および、評価値算出部３０５の機能が第１の実施形態と異なっている。その他の構成および機能は、第１の実施形態にかかる情報処理装置１００のブロック図である図１と同様であるので、同一符号を付し、ここでの説明は省略する。また第３の実施形態の統合処理の全体の流れは、第１の実施形態の統合処理を示す図２と同様であるため説明を省略する。以下では、第１の実施形態との相違部分を記載する。
【００９３】
図２のステップＳ１０３に対応する処理として、生成部３０３は、選択されたサポートベクトルｓ（ｉ）およびｓ（ｊ）を統合して、統合ベクトルｓを生成する。本実施形態の生成部３０３は、例えば、（４２）式および（３１）式などを用いて統合ベクトルｓを生成する。
【００９４】
図２のステップＳ１０４に対応する処理として、重み算出部３０４は、生成された統合ベクトルｓの重みαを算出する。重み算出部３０４は、例えば（３８）式を用いて重みαを算出する。
【００９５】
図２のステップＳ１０５に対応する処理として、評価値算出部３０５は、ｓ（ｉ）、ｓ（ｊ）を、ｓで置き換え、αｉ、αｊをαで置き換えた場合の評価関数（（４２）式）の値である評価関数値を求める。求めた評価関数値が、それ以前に求められた評価関数値の最小値よりも小さい場合、評価値算出部３０５は、統合するサポートベクトルのインデックスｉ，ｊ、ｓ、α、および、評価関数値を例えば記憶部２０に記憶する。
【００９６】
本実施形態によれば、カーネル関数に指数Ｂｈａｔｔａｃｈａｒｙｙａカーネルを使う場合にも、入力ベクトルの分布に基づく近似誤差の期待値を最小化するサポートベクトルの統合が得られる。これにより、識別関数の近似精度を極力保った上で、識別にかかる処理時間を低減することができる。
【００９７】
（第４の実施形態）
第４の実施形態では、学習データから入力ベクトルの分布を推定し、その推定分布に基づき識別関数の近似誤差を最小化するようにサポートベクトルを統合する例を説明する。図５は、第４の実施形態にかかる情報処理装置４００の構成を示すブロック図である。
【００９８】
図５に示すように、本実施形態の情報処理装置４００は、記憶部２０と、推定部４０１と、取得部１０１と、選択部１０２と、生成部１０３と、重み算出部１０４と、評価値算出部１０５と、出力制御部１０６と、を備えている。
【００９９】
第４の実施形態では、推定部４０１を追加したことが第１の実施形態と異なっている。その他の構成および機能は、第１の実施形態にかかる情報処理装置１００のブロック図である図１と同様であるので、同一符号を付し、ここでの説明は省略する。
【０１００】
推定部４０１は、記憶部２０などに記憶される学習データに含まれるＮ個の入力ベクトルｓ（ｉ）（ｉ＝１，２，・・・，Ｎ）を基に入力ベクトル分布ｐ（ｘ）を推定する。推定部４０１による入力ベクトル分布の推定処理の詳細については後述する。
【０１０１】
次に、このように構成された第４の実施形態にかかる情報処理装置４００によるサポートベクトルの統合処理について図６を用いて説明する。図６は、第４の実施形態における統合処理の一例を示すフローチャートである。
【０１０２】
推定部４０１は、記憶部２０から学習データを読み込み、学習データに含まれるＮ個の入力ベクトルｓ（ｉ）（ｉ＝１，２，・・・，Ｎ）を基に入力ベクトル分布ｐ（ｘ）を推定する（ステップＳ２０１）。
【０１０３】
ステップＳ２０２からステップＳ２０８までは、第１の実施形態にかかる情報処理装置１００におけるステップＳ１０１からステップＳ１０７までと同様の処理なので、その説明を省略する。
【０１０４】
次に、入力ベクトル分布の推定処理について説明する。推定部４０１は、例えば以下の（４４）式で示される経験分布を用いることができる。ここで、δはデルタ関数である。
【数４４】
0006676894.tif 000045
【０１０５】
入力ベクトル分布ｐ（ｘ）の推定方法はこれに限られるものではない。例えば推定部４０１は、ｐ（ｘ）にパラメトリックなモデルを仮定し、最尤推定によりそのパラメータを求めてもよい。例えばｐ（ｘ）に、正規分布、ラプラス分布、一様分布（領域限定）、ポアソン分布、ベータ分布、ガンマ分布、および、これらの混合分布を考えることができる。推定部４０１は、さらにパラメータに事前分布を仮定してＭＡＰ推定およびベイズ推定によって分布を推定してもよい。
【０１０６】
別のアプローチとして、推定部４０１は、学習データから得られた識別関数ｆ（ｘ）をもとに入力ベクトル分布を推定してもよい。例えば推定部４０１は、以下の（４５）式のようにｐ（ｘ）を設定する。
【数４５】
0006676894.tif 000046
【０１０７】
厳密に言えば、（４５）式の分布は入力ベクトルの推定分布ではなく、近似誤差の重み付けを行うための便宜的な分布である。ＳＶＭの目的はクラス分類であり、識別境界付近の識別関数の近似精度が重要である。そこで、（４５）式のようにｆ（ｘ）＝０となる識別境界付近に入力ベクトルが集中していると考えて近似誤差の期待値を取ることで、識別境界付近の近似精度を高めることができる。（４５）式に基づく近似誤差の期待値計算は、例えばマルコフ連鎖モンテカルロ法により実施することができる。
【０１０８】
（４５）式の分布は、識別境界からの距離が大きいほど、確率密度の値が小さくなる分布の例である。このような確率分布を用いることにより、識別精度への影響が大きい識別境界付近に重点を置いて識別関数を近似することが可能となる。
【０１０９】
なお、本実施形態は一般的なカーネルの場合だけでなく、第２の実施形態のＲＢＦカーネル、および、第３の実施形態の指数Ｂｈａｔｔａｃｈａｒｙｙａカーネルの場合にも同様に適用することができる。
【０１１０】
本実施形態によれば、学習データを基に入力ベクトルの分布を推定し、その分布に基づいた識別関数の近似誤差の期待値最小化を行うことで、識別関数の近似精度を高めることができる。また、学習データの分布を反映した上で識別関数を近似することができる。
【０１１１】
（第５の実施形態）
本実施形態では、基準ベクトルの統合により得られた識別関数を用いてパターン認識などを実行する識別装置として情報処理装置を実現する例を説明する。図７は、第５の実施形態にかかる情報処理装置５００の構成を示すブロック図である。
【０１１２】
図７に示すように、本実施形態の情報処理装置５００は、記憶部２０と、取得部１０１と、選択部１０２と、生成部１０３と、重み算出部１０４と、評価値算出部１０５と、出力制御部１０６と、認識部５０１と、を備えている。
【０１１３】
第５の実施形態では、認識部５０１を追加したことが第１の実施形態と異なっている。その他の構成および機能は、第１の実施形態にかかる情報処理装置１００のブロック図である図１と同様であるので、同一符号を付し、ここでの説明は省略する。
【０１１４】
認識部５０１は、第１の実施形態の方法で識別関数が近似されたＳＶＭを用いた識別（認識）処理を実行する。例えば認識部５０１は、識別の対象となる特徴量ベクトルがいずれのクラスに属するかを、ＳＶＭを用いて識別する。特徴量ベクトルは、例えば、画像の特徴、文字の特徴、および、音声の特徴を表すベクトルである。このように、本実施形態の識別装置は、画像認識、文字認識、および、音声認識などの任意の識別処理に適用できる。
【０１１５】
次に、このように構成された第５の実施形態にかかる情報処理装置５００による識別処理について図８を用いて説明する。図８は、第５の実施形態における識別処理の一例を示すフローチャートである。
【０１１６】
認識部５０１は、識別の対象となる特徴量ベクトルを、記憶部２０または外部装置などから入力する（ステップＳ３０１）。認識部５０１は、ＳＶＭを用いて特徴量ベクトルがいずれのクラスに属するかを識別する（ステップＳ３０２）。認識部５０１は、識別結果を出力し（ステップＳ３０３）、識別処理を終了する。
【０１１７】
なお、本実施形態は第１の実施形態だけでなく、第２〜第４の実施形態にも同様に適用することができる。本実施形態によれば、より少ない基準ベクトルを用いて近似された識別関数を用いることができるため、識別性能の劣化を極力抑えた上で処理時間を低減することが可能となる。
【０１１８】
次に、上記各実施形態にかかる情報処理装置のハードウェア構成について図９を用いて説明する。図９は、各実施形態にかかる情報処理装置のハードウェア構成例を示す説明図である。
【０１１９】
各実施形態にかかる情報処理装置は、ＣＰＵ（Central  Processing  Unit）５１などの制御装置と、ＲＯＭ（Read  Only  Memory）５２やＲＡＭ（Random  Access  Memory）５３などの記憶装置と、ネットワークに接続して通信を行う通信Ｉ／Ｆ５４と、各部を接続するバス６１を備えている。
【０１２０】
なお、本実施形態の情報処理装置で実行されるプログラムは、ＲＯＭ等に予め組み込まれて提供される。
【０１２１】
本実施形態の情報処理装置で実行されるプログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録してコンピュータ・プログラム・プロダクトとして提供するように構成してもよい。
【０１２２】
さらに、本実施形態の情報処理装置で実行されるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、本実施形態の情報処理装置で実行されるプログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。
【０１２３】
本実施形態の情報処理装置で実行されるプログラムは、上述した各部を含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵ（プロセッサ）が上記ＲＯＭからプログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、各部が主記憶装置上に生成されるようになっている。
【符号の説明】
【０１２４】
２０  記憶部
１００、２００、３００、４００、５００  情報処理装置
１０１  取得部
１０２  選択部
１０３、２０３、３０３  生成部
１０４、２０４、３０４  重み算出部
１０５、２０５、３０５  評価値算出部
１０６  出力制御部
４０１  推定部
５０１  認識部
【先行技術文献】
【非特許文献】
【０１２５】
【非特許文献１】D.  Nguyen，  T.  Ho，  “An  efficient  method  for  simplifying  support  vector  machines”，  ＩＣＭＬ，  ６１７−６２４，  ２００５．
【非特許文献２】Z.  Wang，  K.  Crammer，  S.  Vucetic，  “Ｍｕｌｔｉ−Ｃｌａｓｓ  Ｐｅｇａｓｏｓ  ＯＮ  ａ  Ｂｕｄｇｅｔ”，  Ｉｎ  Ｐｒｏｃ．  ＩＣＭＬ，  ２０１０．
【図１】
0006676894.tif 000047
【図２】
0006676894.tif 000048
【図３】
0006676894.tif 000049
【図４】
0006676894.tif 000050
【図５】
0006676894.tif 000051
【図６】
0006676894.tif 000052
【図７】
0006676894.tif 000053
【図８】
0006676894.tif 000054
【図９】
0006676894.tif 000055