(57)【特許請求の範囲】
【請求項１】
入力ベクトルの各要素のクラスタ情報に基づいて、前記入力ベクトルの要素の順序を並べ替える並べ替え手段と、
前記並べ替え手段により並べ替えられた前記入力ベクトルの要素ごとに、前記入力ベクトルの要素と、多項式カーネルを展開して得られる係数と、前記クラスタ情報と、に基づいて、分類関数の値の中間データを演算する第１の演算手段と、
前記第１の演算手段により演算された前記中間データと、前記入力ベクトルと、前記係数と、に基づいて、前記分類関数の値を演算する第２の演算手段と、
を有する情報処理装置。
【請求項２】
前記並べ替え手段は、前記クラスタ情報に従って、前記入力ベクトルの各要素を、同一クラスタに属する要素が連続するように並べ替える請求項１記載の情報処理装置。
【請求項３】
前記並べ替え手段は、要素の順序を並べ替えた前記入力ベクトルを第１の格納部に格納し、
前記第１の演算手段は、前記第１の格納部から要素の順序を並べ替えられた前記入力ベクトルを取得し、第２の格納部から前記係数を取得し、前記中間データを第３の格納部に格納し、
前記第２の演算手段は、前記第３の格納部から前記中間データを取得し、取得した前記中間データと、前記入力ベクトルと、前記係数と、に基づいて、前記分類関数の値を演算する請求項１又は２記載の情報処理装置。
【請求項４】
前記第１の演算手段は、前記第１の格納部から前記並べ替え手段により要素の順序を並べ替えられた前記入力ベクトルであるｘを取得し、前記第２の格納部から前記係数を取得し、前記クラスタ情報に基づいて、クラスタｋに属するベクトル要素の番号の集合を式１のＣｌｕｓｔｅｒｋとして、２次項の演算に利用されるクラスタｋの番号ｋの集合を式２のＶｃｌｕｓｔｅｒとして、ベクトル要素番号ｎに対応するクラスタ番号をｋ（ｎ）として、ｋ（ｎ）に対応するクラスタ番号ｋ（ｎ）がＶｃｌｕｓｔｅｒに属するベクトル要素番号の集合を式２のＶｅｌｅｍｅｎｔとして、前記係数に含まれる前記分類関数の２次項の演算に利用される係数Ａｎｍ及び前記分類関数の１次項の演算に利用される係数Ｂｎと、ｘと、に基づいて、式３を利用して、ｘの要素ごとに前記中間データであるｇｎ（ｘ）を演算し、
前記第２の演算手段は、前記第１の演算手段により演算されたｇｎ（ｘ）と、ｘと、前記係数に含まれる前記分類関数の定数項である係数Ｃに基づいて、式４を利用して前記分類関数の値を演算する請求項３記載の情報処理装置。
【数１】
0006700843.tif 000028
【数２】
0006700843.tif 000029
【数３】
0006700843.tif 000030
【数４】
0006700843.tif 000031
【請求項５】
入力ベクトルの各要素のクラスタ情報に基づいて、多項式カーネルを展開して得られる係数のそれぞれの要素が、クラスタごとの演算に用いられるか否かを示す有効領域情報を生成する第１の生成手段と、
前記入力ベクトルの要素ごとに、前記入力ベクトルの要素と、前記係数と、前記第１の生成手段により生成された有効領域情報と、に基づいて、分類関数の値の中間データを演算する第１の演算手段と、
前記中間データと、前記入力ベクトルと、前記係数と、に基づいて、前記分類関数の値を演算する第２の演算手段と、
を有する情報処理装置。
【請求項６】
前記第２の演算手段により演算された前記分類関数の値の情報を出力する出力手段を更に有する請求項１乃至５何れか１項記載の情報処理装置。
【請求項７】
前記第２の演算手段により演算された前記分類関数の値に基づいて、前記入力ベクトルの分類結果を判定する判定手段と、
前記判定手段による判定結果を示す情報を出力する出力手段と、
を更に有する請求項１乃至５何れか１項記載の情報処理装置。
【請求項８】
多項式カーネル関数を用いて機械学習を行う学習手段と、
前記学習手段による学習の結果により多項式カーネルを展開して得られる係数を取得する取得手段と、
前記取得手段により取得される前記係数の値に基づいて、前記入力ベクトルの各要素をクラスタリングし、クラスタリングの結果を示す前記クラスタ情報を生成する第２の生成手段と、
を更に有する請求項１乃至７何れか１項記載の情報処理装置。
【請求項９】
前記第２の生成手段は、前記係数に基づいて、前記入力ベクトルの要素間の距離を取得し、取得した前記距離に基づいて、前記入力ベクトルの各要素をクラスタリングし、クラスタリングの結果に基づいて、前記入力ベクトルの各要素がどのクラスタに属するかを示す前記クラスタ情報を生成する請求項８記載の情報処理装置。
【請求項１０】
前記第２の生成手段による前記入力ベクトルの要素のクラスタリング処理の結果により定まるカーネル関数に基づいて、機械学習を行い、学習の結果に基づいて、前記係数を更新する更新手段を更に有する請求項８又は９記載の情報処理装置。
【請求項１１】
情報処理装置が実行する情報処理方法であって、
入力ベクトルの各要素のクラスタ情報に基づいて、前記入力ベクトルの要素の順序を並べ替える並べ替えステップと、
前記並べ替えステップで要素の順序を並べ替えられた前記入力ベクトルの要素ごとに、前記入力ベクトルの要素と、多項式カーネルを展開して得られる係数と、前記クラスタ情報と、に基づいて、分類関数の値の中間データを演算する第１の演算ステップと、
前記中間データと、前記入力ベクトルと、前記係数と、に基づいて、前記分類関数の値を演算する第２の演算ステップと、
を含む情報処理方法。
【請求項１２】
コンピュータを、請求項１乃至１０何れか１項記載の情報処理装置の各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法及びプログラムに関する。
【背景技術】
【０００２】
画像認識を始めとする様々な応用分野において、サポートベクトルマシン（ＳＶＭ）を用いた分類、又はサポートベクトル回帰（ＳＶＲ）を用いた回帰計算が用いられている。ＳＶＭの分類関数の演算における演算量を削減する技術には、特許文献１、２等の技術がある。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００３−３３１２５４号公報
【特許文献２】特開２０１０−８６４６６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１、２等の従来技術を用いても、演算回数の削減量が求められる値に達しなかったり、精度を向上させるために重要な演算を削減してしまい、分類処理・回帰処理等の精度が低下してしまったりするという問題がある。
本発明は、精度の低下を抑えつつ、演算処理の負担を軽減しつつ、分類関数を演算することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の情報処理装置は、入力ベクトルの各要素のクラスタ情報に基づいて、前記入力ベクトルの要素の順序を並べ替える並べ替え手段と、前記並べ替え手段により並べ替えられた前記入力ベクトルの要素ごとに、前記入力ベクトルの要素と、多項式カーネルを展開して得られる係数と、前記クラスタ情報と、に基づいて、分類関数の値の中間データを演算する第１の演算手段と、前記第１の演算手段により演算された前記中間データと、前記入力ベクトルと、前記係数と、に基づいて、前記分類関数の値を演算する第２の演算手段と、を有する。
【発明の効果】
【０００６】
本発明によれば、精度の低下を抑えつつ、演算処理の負担を軽減しつつ、分類関数を演算することができる。
【図面の簡単な説明】
【０００７】
【図１】２次多項式カーネルを用いた分類関数の演算回数の一例を示す図である。
【図２】情報処理装置のハードウェア構成等の一例を示す図である。
【図３】情報処理装置の機能構成の一例を示す図である。
【図４】クラスタリング処理を説明する図である。
【図５】クラスタ及び係数の決定処理の一例を示すフローチャートである。
【図６】演算順序を説明する図である。
【図７】分類処理の一例を示すフローチャートである。
【図８】有効領域情報を説明する図である。
【図９】情報処理装置の機能構成の一例を示す図である。
【図１０】演算順序を説明する図である。
【図１１】分類処理の一例を示すフローチャートである。
【図１２】３次係数のクラスタリングを説明する図である。
【発明を実施するための形態】
【０００８】
以下、本発明の実施形態について図面に基づいて説明する。
【０００９】
＜実施形態１＞
ＳＶＭの分類関数の演算量を削減するための技術には、例えば、以下のようなものがある。
分類対象の入力ベクトルをｘ、サポートベクトルをｘi（ｉ＝１、２、・・・、Ｎ）、ベクトルｘ、ｙに対するカーネル関数をＫ（ｘ、ｙ）とすると、ＳＶＭの分類関数ｆ（ｘ）は式１で表される。
【００１０】
【数１】
0006700843.tif 000002
【００１１】
ここで、ｙiは、ｘiに対応する教師ラベルである。αi、ｂは、機械学習により決定されるパラメータである。また、Ｎは、サポートベクトル数である。
カーネル関数Ｋ（ｘ、ｙ）としては、様々な種類の関数が利用されている。例えば、カーネル関数Ｋ（ｘ、ｙ）として、式２に示す多項式カーネルが利用されている。
【００１２】
【数２】
0006700843.tif 000003
【００１３】
ここで、ｃは、スカラ定数である。ｐは、多項式の次数（２、３、４、・・・）である。ｘ・ｙは、ベクトルｘ、ｙの内積であり、式３で表される。
【００１４】
【数３】
0006700843.tif 000004
【００１５】
ここで、ｘn、ｙnは、それぞれＤ次元ベクトルｘ、ｙのｎ番目の要素を表している。
多項式カーネルＳＶＭの分類関数ｆ（ｘ）を、式１、式２、式３を用いて式通りに計算すると、ベクトルの次元数やサポートベクトル数Ｎの増加に伴い、演算回数が非常に増加するという問題がある。そこで、演算量を減らすための計算上の工夫を開示する技術がある。なお、以下の説明では、数式の複雑化を避けるため、２次多項式カーネル（ｐ＝２）を例に説明する。
多項式カーネルＳＶＭの演算量を減らすための第１の技術は、特許文献１、特許文献２に開示されているように、式２の多項式を展開して、式１のサポートベクトルに関する和を予め計算しておく方法である。具体的には、式２を以下の式４のように展開した後に、式１に代入し、式変形を行うことで式５を得る方法である。
【００１６】
【数４】
0006700843.tif 000005
【００１７】
【数５】
0006700843.tif 000006
【００１８】
ここで、Ａnm、Ｂn、Ｃは、サポートベクトルｘi、教師ラベルｙi、パラメータαi、ｂを用いて、それぞれ式６、式７、式８のように計算される係数である。
【００１９】
【数６】
0006700843.tif 000007
【００２０】
【数７】
0006700843.tif 000008
【００２１】
【数８】
0006700843.tif 000009
【００２２】
サポートベクトル数Ｎ＝１０００、入力ベクトル次元数Ｄ＝１００である場合、２次多項式カーネルＳＶＭを用いた分類関数の演算回数は、図１のようになる。式１〜３を用いると、２０３０００回の乗算・加算が必要であるのに対し、展開式５を用いることで３０２００回に減らすことができる。
第１の技術を用いた上で、更に演算量を減らすための第２の技術は、展開後の係数の対称性を利用するものである。係数Ａnmは、式９に示すような対称性をもつため、対称な項の演算をまとめることで、式１０のようにｘnｘmの項に関する和をとる範囲を減らすことができる。
【００２３】
【数９】
0006700843.tif 000010
【００２４】
【数１０】
0006700843.tif 000011
【００２５】
ここで、Ａ'nmは、式１１で表される係数である。
【００２６】
【数１１】
0006700843.tif 000012
【００２７】
図１に示すように、式１０を用いることで、第１の技術を用いたときの乗算・加算回数３０２００回を、更に１５３５０回に減らすことができる。
第２の技術を用いた上で、さらに演算量を減らすための第３の技術は、式１０の演算順序を変更して乗算回数を減らすものである。式１０を式１２のように変形して計算することにより、図１に示すように、乗算・加算回数を１０３００回まで減らすことができる。
【００２８】
【数１２】
0006700843.tif 000013
【００２９】
第１〜第３の技術は、式１〜３と等価な式変形のみを利用する演算量削減方法である。式１〜３と等価でない式変形を利用する第４の技術としては、特許文献１に削除手段１２として示されている入力ベクトルの次元削減による方法がある。特許文献１の削除手段１２に開示されている方法は、Ａnm、Ｂnに相当する係数Ｗ'１［ｈ］、Ｗ３［ｈ、ｋ］、Ｗ３［ｋ、ｈ］の大きさを評価する関数Ｅ（ｈ）を用いて、Ｅ（ｈ）が設定された閾値θ未満の属性（入力ベクトル要素）を削除する方法である。これにより、入力ベクトルの次元数Ｄが減るため、演算量を削減できる。
例えば、入力ベクトル次元数Ｄ＝１００ならば、分類関数の計算には１０３００回の乗算・加算が必要となるが、演算回数を更に削減し、演算処理の負担を軽減したいという要望がある。演算回数は、特にＤが大きくなってくると、Ｄ2に比例して増加することになる。
一方、第４の技術により、入力ベクトルの次元削減を行った場合、第１〜第３までの技術を用いた場合よりも、演算回数を更に減らすことができる。しかし、精度を向上させるために重要なベクトル要素を削ってしまう場合があり、分類処理、回帰処理等の精度が低下するという問題がある。
本実施形態では、精度を向上させるために重要なベクトル要素の削減量を抑えることで、分類処理、第４の技術と比べて回帰処理等の精度の低下を抑えつつ、分類関数の演算量を削減する方法について説明する。
【００３０】
図２は、情報処理装置３０１のハードウェア構成の一例を示す図である。本実施形態の情報処理装置３０１は、入力された入力ベクトルに対して、後述する式１５、１６で表される分類関数ｆ（ｘ）を演算し、演算結果に基づいて、判定した分類結果を出力する装置である。情報処理装置３０１は、パーソナルコンピュータ（ＰＣ）、サーバ装置等の情報処理装置である。また、情報処理装置３０１は、例えば、組み込みデバイス、デジタルカメラ、ハンドヘルドデバイス等であってもよい。
情報処理装置３０１は、ＣＰＵ６０１、ＲＯＭ６０２、ＲＡＭ６０３、二次記憶装置６０４、を含む。ＣＰＵ６０１、ＲＯＭ６０２、ＲＡＭ６０３、二次記憶装置６０４、は、システムバス６０５を介して、相互に接続されており、相互に情報のやり取りを行う。
ＣＰＵ６０１は、図５、図７に示すフローチャートに対応する処理手順を含む各種プログラムを実行し、情報処理装置３０１の各部の制御を行う中央演算装置である。ＲＯＭ６０２は、不揮発性のメモリであり、情報処理装置を初期動作させる際に必要なプログラム等を記憶する。ＲＡＭ６０３は、ＣＰＵ６０１に対してワークエリアを提供し、二次記憶装置６０４から読み出されたプログラム等を一時記憶する。二次記憶装置６０４は、ＣＰＵ６０１が実行するプログラムや各種設定データ等を記憶する記憶装置である。
また、情報処理装置３０１は、システムバス６０５を介して、ディスプレイ６０６、キーボード６０７、マウス６０８、Ｉ／Ｏデバイス６０９と接続されている。ディスプレイ６０６は、処理結果や処理の途中経過等の情報を表示し、これらの情報をユーザに提示する表示装置である。キーボード６０７とマウス６０８とは、ユーザが指示を情報処理装置３０１に入力するのに用いられる入力装置である。Ｉ／Ｏデバイス６０９は、ネットワークを通じて外部と通信する通信装置との接続や、カメラ・スキャナ等の入力装置との接続、又はプリンタ等の出力装置との接続等に利用されるデバイスである。
ＣＰＵ６０１が、ＲＯＭ６０２又は二次記憶装置６０４に記憶されたプログラムに基づき処理を実行することによって、図３で後述する機能及び図５、図７で後述するフローチャートの処理が実現される。
【００３１】
図３は、情報処理装置３０１の機能構成の一例を示す図である。情報処理装置３０１は、並べ替え部３０２、入力ベクトル格納部３０３、入力ベクトル読み出し部３０４、演算部３０５、判定部３０６、クラスタ制御部３０７、係数読み出し部３０８、係数格納部３０９、中間データ格納部３１０を含む。
並べ替え部３０２は、入力された入力ベクトルの各要素や分類関数の係数を、後述する図４（ｂ）に示すように、同一のクラスタに属する要素が連続するように並べ替えて、入力ベクトル格納部３０３や係数格納部３０９等に格納する。
入力ベクトル格納部３０３は、並べ替え部３０２により、要素を並べ替えられた入力ベクトルを格納する。入力ベクトル格納部３０３は、二次記憶装置６０４等により構成される。入力ベクトル格納部３０３に格納された入力ベクトルは、入力ベクトル読み出し部３０４により複数回読みだされる。入力ベクトル格納部３０３は、入力ベクトルを格納する第１の格納部の一例である。
入力ベクトル読み出し部３０４は、クラスタ制御部３０７の指示に従って、演算部３０５による分類関数の演算に必要な入力ベクトルの要素を入力ベクトル格納部３０３から複数回、読み出し、演算部３０５に渡す。
係数格納部３０９は、分類関数の演算に必要な係数を格納している。係数格納部３０９は、二次記憶装置６０４等により構成される。係数格納部３０９は、多項式カーネルを展開して得られる係数を格納する第２の格納部の一例である。係数格納部３０９は、後述する式１５、１６の演算に必要な係数Ａnm、Ａ'nm、Ｂn、Ｃ等の情報を格納する。
【００３２】
係数読み出し部３０８は、クラスタ制御部３０７の指示に従って、分類関数の演算に必要な係数を係数格納部３０９から読み出し、演算部３０５に渡す。
演算部３０５は、クラスタ制御部３０７の指示に従って、入力ベクトル読み出し部３０４から渡されたデータと係数読み出し部３０８から渡された係数とに基づいて、分類関数の演算の中間データを演算し、中間データ格納部３１０に格納する。また、演算部３０５は、入力ベクトル読み出し部３０４から渡されたデータと、係数読み出し部３０８から渡された係数と、中間データ格納部３１０に格納される中間データ値と、に基づいて、分類関数の演算を実行する。
中間データ格納部３１０は、演算部３０５により演算された中間データを格納する。中間データ格納部３１０は、二次記憶装置６０４等により構成される。中間データ格納部３１０は、中間データを格納する第３の格納部の一例である。中間データ格納部３１０は、後述する式１６を用いて、演算部３０５により演算されるｇn（ｘ）の値を中間データとして格納する。
判定部３０６は、演算部３０５により演算された分類関数の値に基づいて、分類判定を行い、分類結果を出力する。
クラスタ制御部３０７は、入力ベクトル読み出し部３０４、係数読み出し部３０８、演算部３０５に対して、分類関数の中間データを演算するよう指示を出す。そして、クラスタ制御部３０７は、入力ベクトル読み出し部３０４、係数読み出し部３０８、演算部３０５に対して、分類関数の値を演算するよう指示を出す。
【００３３】
図４（ａ）は、式５のように展開された分類関数における２次項の係数Ａnm及びベクトルのクラスタリング処理を説明する図である。係数１０１は、式５のように展開された分類関数における２次項の係数Ａnmを示す。係数１０１の縦方向、横方向の軸は、それぞれベクトル要素番号ｎ、ｍに対応している。即ち、分類関数において、入力ベクトルｘの要素番号ｎの要素と、要素番号ｍの要素とにかけ合わされる係数は、係数１０１のｎ行目、ｍ列目の値となる。
また、Ａnmは、式９を満たす。そのため、対称軸１１１に対して、太枠内の下三角形の領域の値と太枠外の上三角形の領域の値とは、対称である。係数Ａnmの絶対値について、ｎ、ｍの組み合わせ全体を見渡すと、相対的に他の領域よりも大きな値をとる領域が偏っている場合がある。例えば、図４（ａ）の例では、ｎ、ｍの組み合わせに対して他の領域よりも係数Ａnmの絶対値が大きな値を取る第１の領域は、Ｃｌｕｓｔｅｒ１として、クロスハッチされた領域１０２、１０３、１０４、１０５で示されている。入力ベクトルの要素のうち、Ｃｌｕｓｔｅｒ１の領域に対応する要素（図４（ａ）の例では、Ｃｌｕｓｔｅｒ１の両矢印で示されている要素）は、Ｃｌｕｓｔｅｒ１に属する要素であるとする。
また、他の領域よりも係数Ａnmの絶対値が大きな値を取る第２の領域は、Ｃｌｕｓｔｅｒ２として網点で示された領域１０６、１０７、１０８、１０９で示されている。入力ベクトルの要素のうち、Ｃｌｕｓｔｅｒ２の領域に対応する要素（図４（ａ）の例では、Ｃｌｕｓｔｅｒ２の両矢印で示されている要素）は、Ｃｌｕｓｔｅｒ２に属する要素であるとする。
また、Ａnmの絶対値が相対的に他の領域よりも小さな値しか取らない領域は、白い領域で示されている。特に、十字型領域１１０については、特定のｎと任意のｍとの組み合わせ、特定のｍと任意のｎとの組み合わせについて、Ａnmの絶対値は、他の領域よりも小さな値しか取らない領域であり、この領域をＣｌｕｓｔｅｒ３とする。入力ベクトルの要素のうち、Ｃｌｕｓｔｅｒ３の領域に対応する要素（図４（ａ）の例では、Ｃｌｕｓｔｅｒ３の両矢印で示されている要素）は、Ｃｌｕｓｔｅｒ３に属する要素であるとする。領域のクラスタリングの方法については、図５で後述する。
【００３４】
本実施形態の処理は、従来、式５に従って、ｎ、ｍの全ての組み合わせについて係数Ａnmを用いて分類関数の２次項を演算していたところを、絶対値が他の領域よりも大きな値を取る領域に限定して係数Ａnmを用いて２次項を演算する処理である。それにより、演算量を減らすことができる。例えば、図４（ａ）の例では、Ｃｌｕｓｔｅｒ１、Ｃｌｕｓｔｅｒ２に限定してＡnmを用いて演算を行うことになる。この原理は、式５に限らず、Ａnmを利用する式１０、式１２にも適用できるため、以下、式１２を用いて本実施形態の処理の説明を行う。
本実施形態では、情報処理装置３０１は、入力ベクトルｘのベクトル要素ｘn（１≦ｎ≦Ｄ）を、オーバーラップせずに全ベクトル要素をカバーするＫ個のクラスタに分割するものとする。クラスタには、同じクラスタに属するベクトル要素ｎ、ｍの組み合わせに対して、係数Ａnmの絶対値が他の領域よりも大きな値を取る領域（図４（ａ）におけるＣｌｕｓｔｅｒ１、Ｃｌｕｓｔｅｒ２等）がある。一方、係数Ａnmの絶対値が他の領域よりも小さな値を取る領域（図４（ａ）ではＣｌｕｓｔｅｒ３等）が存在することもある。各クラスタについて、クラスタ番号ｋが割り当てられる。クラスタｋに属するベクトル要素の番号の集合は、式１３のＣｌｕｓｔｅｒｋで表される。
【００３５】
【数１３】
0006700843.tif 000014
【００３６】
また、絶対値が他の領域よりも大きな値を取る係数Ａnmの領域（図４（ａ）のＣｌｕｓｔｅｒ１、Ｃｌｕｓｔｅｒ２）、即ち、分類関数の２次項の演算に使用される係数の領域のクラスタ番号ｋの集合を、式１４のＶｃｌｕｓｔｅｒで表す。更に、ベクトル要素番号ｎに対応するクラスタ番号をｋ（ｎ）で表し、クラスタ番号ｋ（ｎ）のクラスタに属するベクトル要素番号の集合をＶｅｌｅｍｅｎｔで表す。
【００３７】
【数１４】
0006700843.tif 000015
【００３８】
図４（ａ）の例では、Ｃｌｕｓｔｅｒ１、Ｃｌｕｓｔｅｒ２は、Ｖｃｌｕｓｔｅｒに属し、Ｃｌｕｓｔｅｒ３は、Ｖｃｌｕｓｔｅｒに属さない。
情報処理装置３０１は、式１２を用いて、Ｖｃｌｕｓｔｅｒに属する各クラスタｋに対しては、同一のクラスタｋに属するｎ、ｍの組み合わせに対してのみ、式１１のＡ'nmを用いた２次項の演算を実行することにする。また、情報処理装置３０１は、Ｖｃｌｕｓｔｅｒに属さないクラスタに関してはＡ'nmを用いた２次項の演算を実行しないようにする。それにより、本実施形態の分類関数は、式１５、１６で表される。
【００３９】
【数１５】
0006700843.tif 000016
【００４０】
【数１６】
0006700843.tif 000017
【００４１】
ここで、式１５、１６の分類関数について、式５で行った展開の手順を逆にたどると、式１５、１６に対応するカーネル関数は、式１７の形で表されることになる。
【００４２】
【数１７】
0006700843.tif 000018
【００４３】
式４と式１７とを比較して分かるように、本来の２次多項式カーネル関数と本実施形態ののカーネル関数とは、第１項で２乗を取る範囲がベクトル要素全域か、Ｖｃｌｕｓｔｅｒに属する各クラスタ単位かという差異がある。
【００４４】
実施形態１におけるクラスタ及び係数の決定手順について、図５のフローチャートを用いて説明する。
Ｓ２０１において、ＣＰＵ６０１は、式２の２次多項式カーネルを用いてＳＶＭの機械学習を実行し、サポートベクトルｘｉとパラメータαｉ、ｂを算出する。
Ｓ２０２において、ＣＰＵ６０１は、２次多項式カーネルの展開で得られる式６を用いて、係数Ａnm（又はＡ'nm）、Ｂn、Ｃを算出し、算出したＡnm（又はＡ'nm）、Ｂn、Ｃの情報を二次記憶装置６０４等に記憶する。
Ｓ２０３において、ＣＰＵ６０１は、分類関数の２次項の係数Ａnm、及び入力ベクトルの各要素のクラスタリングを行うために、係数行列Ａnmから各要素間の距離を示す距離行列を算出する。ここで、ＣＰＵ６０１は、距離の計算方法として、Ａnmの値が大きくなる程、対応するｎ、ｍの組み合わせに対して値が小さくなるような距離を用いればよい。例えば、ＣＰＵ６０１は、Ａnmの各要素の絶対値の逆数を要素に持つ行列を距離行列とすればよい。
【００４５】
Ｓ２０４において、ＣＰＵ６０１は、Ｓ２０３で算出した距離行列を用いて、ベクトル要素を距離の差が設定された閾値以下になる要素が固まるようにクラスタリングする。ＣＰＵ６０１は、クラスタリングの手法として、ｋ−ｍｅａｎｓ法や階層クラスタリング等の手法を用いることができる。更に、ＣＰＵ６０１は、Ａnmの絶対値が他の領域よりも小さなクラスタに関しては、Ｖｃｌｕｓｔｅｒに属さないクラスタとして一つにまとめる。なお、ＣＰＵ６０１は、学習対象の性質や距離の計算方法、Ａnmの絶対値に関する閾値等により、クラスタ数が影響されるため、複数の条件でクラスタリングを行った上で、適切なクラスタリング結果を選択してもよい。
ＣＰＵ６０１は、Ａnmの要素についてクラスタリングした結果を示す情報を、二次記憶装置６０４等に記憶する。また、クラスタリング処理後のＡnmに対応するＡ'nmの情報を生成し、生成した情報を二次記憶装置６０４等に記憶することとしてもよい。また、ＣＰＵ６０１は、Ａnm内のあるクラスタに属する領域に対応する入力ベクトルの要素を、そのクラスタに属するものとして、入力ベクトルの各要素をクラスタリングする。そして、ＣＰＵ６０１は、入力ベクトルの各要素がどのクラスタに属するかを示す情報であるクラスタ情報を生成し、生成したクラスタ情報を二次記憶装置６０４等に記憶する。このように、情報処理装置３０１は、クラスタ情報を生成する機能を有する。クラスタ情報を生成する情報処理装置３０１の機能は、クラスタ情報を生成する第２の生成手段の一例である。
【００４６】
Ｓ２０５において、ＣＰＵ６０１は、式１７に、Ｓ２０４におけるクラスタリング結果をあてはめ、再度ＳＶＭの機械学習を実行する。
Ｓ２０６において、ＣＰＵ６０１は、Ｓ２０５で機械学習したサポートベクトルとパラメータとを用いて係数Ａnm（又はＡ'nm）、Ｂn、Ｃを再度算出し、算出した値でこれらの係数の値を更新する。なお、本実施形態では、再学習を行った上で係数を再計算する場合を示したが、ＣＰＵ６０１は、Ｓ２０４のクラスタリングまでの処理を行い、Ｓ２０２で計算した係数をそのまま使用して、式１５、１６を計算してもよい。
【００４７】
図４（ｂ）は、並べ替え部３０２により要素を並べ替えられた入力ベクトルに対応する分類関数の２次項の係数を示す図である。並べ替え部３０２は、Ｓ２０４で二次記憶装置６０４等に記憶された入力ベクトルの各要素がどのクラスタに属するかを示すクラスタ情報に基づいて、入力ベクトルの各要素を、同一のクラスタに属する要素が連続するように並べ替える。
また、並べ替え部３０２は、要素を並べ替えた入力ベクトルに対応して、分類関数の２次項の係数も同一のクラスタに属する要素を１つの領域に固めるように並べ替える。図４（ｂ）の例は、並べ替えの結果の一例を示す。図４（ｂ）において、クロスハッチされた領域１１２は、Ｃｌｕｓｔｅｒ１、網点で示された領域１１３は、Ｃｌｕｓｔｅｒ２、Ｌ字型の領域１１４は、Ｃｌｕｓｔｅｒ３を示している。この並べ替えにより、入力ベクトル読み出し部３０４によるクラスタ単位のデータ読み出しを連続して効率的に行うことができるようになる。
【００４８】
本実施形態では、クラスタ制御部３０７は、入力ベクトル読み出し部３０４、係数読み出し部３０８、演算部３０５に対して、分類関数の中間データである式１６のｇn（ｘ）を演算するよう指示を出す。クラスタ制御部３０７は、ｇn（ｘ）について、ｇ1（ｘ）、ｇ2（ｘ）、・・・・、ｇD（ｘ）の順番で、演算を行うように指示を出す。そして、クラスタ制御部３０７は、入力ベクトル読み出し部３０４、係数読み出し部３０８、演算部３０５に対して、演算した中間データｇn（ｘ）に基づいて、分類関数の値を演算するよう指示を出す。このときの演算順序について、図６を用いて説明する。
図６の係数１０１は、入力ベクトル要素の並べ替えに対応して、図４（ｂ）のように並べ替えられた係数Ａnmを示し、Ｃｌｕｓｔｅｒ１から順に同じクラスタに属する要素が連続するようになっている。中間データ４０３は、中間データ格納部３１０に格納された式１６を用いて算出されたｇn（ｘ）の値である。クラスタ制御部３０７は、まず、Ｃｌｕｓｔｅｒ１に属するｇ１（ｘ）を計算するために、矢印群４０１の中の一番上の矢印に相当する入力ベクトル要素を読み出すように入力ベクトル読み出し部３０４に指示する。また、クラスタ制御部３０７は、対応する係数Ａ'nm、Ｂnを読み出すように係数読み出し部３０８に指示する。
更に、クラスタ制御部３０７は、読出しを指示したデータと係数とを使用してｇ１（ｘ）を演算し、中間データ４０３の最初の要素として格納するように演算部３０５に指示する。クラスタ制御部３０７は、演算部３０５によるｇ１（ｘ）の演算が終わると、次に、矢印群４０１の中の上から２番目の矢印に相当する入力ベクトル要素の読み出しを、入力ベクトル読み出し部３０４に指示する。また、クラスタ制御部３０７は、対応する係数の読み出しを計数読み出し部３０８に指示する。そして、クラスタ制御部３０７は、読み出しを指示した係数及び要素からｇ２（ｘ）を計算、格納するよう、演算部３０５に指示する。
【００４９】
クラスタ制御部３０７は、矢印群４０１を上から順にたどってＣｌｕｓｔｅｒ１に属するｇn（ｘ）の演算に必要な入力ベクトルの要素の読み出しを入力ベクトル読み出し部３０４に指示する。また、クラスタ制御部３０７は、ｇn（ｘ）の演算に必要な係数の読み出しを計数読み出し部３０８に指示する。また、クラスタ制御部３０７は、ｇn（ｘ）の演算・格納を演算部３０５に指示する。
クラスタ制御部３０７は、Ｃｌｕｓｔｅｒ１に属するｇn（ｘ）の計算、格納が終わると、次に、矢印群４０２を順にたどってＣｌｕｓｔｅｒ２に属するｇn（ｘ）の演算に必要な入力ベクトルの要素の読み出しを入力ベクトル読み出し部３０４に指示する。また、クラスタ制御部３０７は、Ｃｌｕｓｔｅｒ２に属するｇn（ｘ）の演算に必要な係数の読み出しを計数読み出し部３０８に指示する。そして、クラスタ制御部３０７は、Ｃｌｕｓｔｅｒ２に属するｇn（ｘ）の演算・格納を演算部３０５に指示する。
【００５０】
クラスタ制御部３０７は、Ｃｌｕｓｔｅｒ２に属するｇn（ｘ）の計算、格納が終わると、Ｃｌｕｓｔｅｒ３に関して、以下の処理を行う。即ち、クラスタ制御部３０７は、Ｃｌｕｓｔｅｒ３の入力ベクトル要素がＶｅｌｅｍｅｎｔに属していないため、係数Ｂnを読み出すように係数読み出し部３０８に指示する。そして、クラスタ制御部３０７は、読み出しを指示した係数Ｂnをそのままｇn（ｘ）として中間データ４０３に格納するように演算部３０５に指示する。
クラスタ制御部３０７は、Ｃｌｕｓｔｅｒ３に属するｇn（ｘ）の格納が終わると、入力ベクトル要素を順に全て読み出すように入力ベクトル読み出し部３０４に指示し、係数Ｃを読み出すように係数読み出し部３０８に指示する。そして、クラスタ制御部３０７は、式１５の分類関数の値を演算して結果を判定部３０６に出力するように演算部３０５に指示する。演算部３０５は、順に読み出された入力ベクトルの要素ｘnと、対応する中間データｇn（ｘ）と、を積和して、積和結果と係数Ｃとを足し合わせることで、式１５の分類関数の値を演算して、演算結果を判定部３０６に出力する。
【００５１】
図７は、本実施形態での情報処理装置３０１の処理の一例を示すフローチャートである。図７を用いて、分類関数の演算処理を説明する。
Ｓ５０１において、並べ替え部３０２は、例えば、予め二次記憶装置６０４等に記憶されている入力ベクトルの情報を、二次記憶装置６０４等から取得することで、入力ベクトルを取得する。そして、並べ替え部３０２は、Ｓ２０４で二次記憶装置６０４等に記憶された入力ベクトルの各要素がどのクラスタに属するかを示すクラスタ情報に基づいて、取得した入力ベクトルの各要素を、同一のクラスタに属する要素が連続するように並べ替える。また、並べ替え部３０２は、要素を並べ替えた入力ベクトルに対応して、分類関数の２次項の演算に用いられる係数行列の要素を、同一のクラスタの要素が固まるように並べ替える。
Ｓ５０２において、演算部３０５は、図６の行方向の入力ベクトルの要素に関するインデックスｎを１とする。
Ｓ５０３において、クラスタ制御部３０７は、Ｓ２０４で二次記憶装置６０４等に記憶されたクラスタ情報に基づいて、インデックスｎの属するクラスタｋの範囲を取得する。
【００５２】
Ｓ５０４において、演算部３０５は、図６の列方向の入力ベクトルの要素に関するインデックスｍをｎの属するクラスタｋの最初の要素のインデックスとする。より具体的には、演算部３０５は、ｍの値を、Ｓ５０３で取得したクラスタｋの範囲の最初の要素のインデックスの値にする。
Ｓ５０５において、演算部３０５は、演算中のｇn（ｘ）の値に、入力ベクトルのｍ番目の要素ｘmと、係数Ａ'nmと、をかけ合わせた値を加える。また、演算部３０５は、現在のｎについて、初めてＳ５０５の処理を行う場合、演算中のｇn（ｘ）の値に、分類関数の１次項の係数Ｂnを加える。
Ｓ５０６において、演算部３０５は、ｍを１だけ増やす。
Ｓ５０７において、演算部３０５は、ｍ＞ｎか否かを判定する。演算部３０５は、ｍ＞ｎではないと判定した場合、Ｓ５０５の処理に進み、ｍ＞ｎであると判定した場合、Ｓ５０８の処理に進む。
以上のように、Ｓ５０１で同じクラスタの要素が連続するよう入力ベクトルの要素が並べ替えられたために、演算部３０５は、Ｓ５０４〜Ｓ５０７で、入力ベクトルの要素ｎについての分類関数の中間データを演算するために次のような処理を行うこととなる。即ち、演算部３０５は、ｍの値をｎの属するクラスタの最初の要素からｎまで順番に１ずつ増やしながら、Ａ'nm×ｘmの値を足し合わせていく処理を行う。これにより、演算部３０５は、要素ｍがｎと同じクラスタか否かを判定する処理を行う手間をかけずに、同じクラスタ同士で分類関数の２次項の演算を行うことができる。
Ｓ５０８において、演算部３０５は、現在のｎに対するｇn（ｘ）の計算が完了したとして、ｎを１だけ増やす。
Ｓ５０９において、演算部３０５は、ｎ＞Ｄか否かを判定する。演算部３０５は、ｎ＞Ｄではないと判定した場合、Ｓ５０３の処理に進む。また、演算部３０５は、ｎ＞Ｄであると判定した場合、全てのｎに対するｇn（ｘ）の計算が完了したとして、Ｓ５１０の処理に進む。ｇn（ｘ）を演算する演算部３０５は、分類関数の値の中間データを演算する第１の演算手段の一例である。
【００５３】
Ｓ５１０において、演算部３０５は、入力ベクトル要素インデックスｎを１とする。
Ｓ５１１において、演算部３０５は、現在のｎに対応するｇn（ｘ）と、現在のｎに対応する入力ベクトルの要素ｘnと、をかけ合わせた値を演算中の分類関数ｆ（ｘ）の値に加える。また、演算部３０５は、現在のｎについて、初めてＳ５１１の処理を行う場合、演算中の分類関数ｆ（ｘ）の値に、分類関数の定数項の係数Ｃを加える。
Ｓ５１２において、演算部３０５は、ｎを１だけ増やす。
Ｓ５１３において、演算部３０５は、ｎ＞Ｄか否かを判定する。演算部３０５は、ｎ＞Ｄではないと判定した場合、Ｓ５１１の処理に進む。また、演算部３０５は、ｎ＞Ｄであると判定した場合、ｆ（ｘ）の演算が完了したとして、演算結果を判定部３０６に送信し、Ｓ５１４の処理に進む。また、演算部３０５は、分類関数の演算結果の情報を二次記憶装置６０４等にファイル形式で記憶することで出力してもよい。また、演算部３０５は、演算結果の情報を外部の情報処理装置等に送信することで出力してもよい。ｆ（ｘ）を演算する演算部３０５は、分類関数の値を演算する第２の演算手段の一例である。
Ｓ５１４において、判定部３０６は、Ｓ５１３で送信された分類関数ｆ（ｘ）の値に基づいて、分類結果を判定する。判定部３０６は、判定結果の情報を、二次記憶装置６０４等にファイル形式で記憶することで出力することとしてもよいし、外部の情報処理装置に送信することで出力することとしてもよい。
【００５４】
以上、本実施形態の処理により、情報処理装置３０１は、式１５、１６で示す分類関数を第１〜第３の技術と比べて演算回数を削減できる。また、情報処理装置３０１は、分類関数の２次項の係数Ａnmの一部について演算を行わず、１次項の係数Ｂnの全てを計算している。即ち、情報処理装置３０１は、第４の技術と異なり、精度上重要な分類関数の１次項について演算を削除しておらず、分類精度の低下を抑えることができる。
なお、本実施形態では、情報処理装置３０１は、図６において、式９の対称性によりＡnmの下三角部分だけの計算を行っているが、逆に上三角部分だけの計算を行ってもよい。また、情報処理装置３０１は、式９の対称性を利用せずに、各クラスタの矩形領域全てに対して演算を行ってもよい。
また、本実施形態では、情報処理装置３０１は、判定部３０６を介して、分類関数の判定を行い、分類結果を出力しているが、判定処理を行わずに、分類関数の値を出力することで回帰装置としての機能を実現することもできる。
【００５５】
＜実施形態２＞
本実施形態では、実施形態１のように入力ベクトルの要素の並べ替えを行わない処理について説明する。なお、本実施形態における分類関数の係数の決定処理と、入力ベクトルの要素及び分類関数の２次項の係数のクラスタリング処理と、実施形態１と同様である。
本実施形態の情報処理装置８０１のハードウェア構成は、実施形態１の情報処理装置３０１と同様である。
【００５６】
本実施形態で用いられる有効領域情報について、図８を用いて説明する。図８は、図４（ａ）と同様の分類関数の２次項の係数Ａnmを示した図である。図８の領域７０１は、入力ベクトルの要素のうち、Ｃｌｕｓｔｅｒ１に属しているある要素に対応する分類関数の２次項の係数を示す領域である。領域７０１には、有効領域７０２、７０３の２つの有効領域が含まれている。有効領域とは、分類関数のある項の係数を示す領域のうち、他の領域よりも絶対値が大きく、分類関数の演算に利用される係数を示す領域である。また、有効領域ではない領域とは、他の領域よりも絶対値が小さく、分類関数の演算に利用されない係数を示す領域である。例えば、情報処理装置８０１は、有効領域７０２内のある係数と、この係数に対応する列に対応する入力ベクトルの要素と、領域７０１に対応する行に対応する入力ベクトルの要素と、を掛け合わせた値を、分類関数の演算に利用する。有効領域は、入力ベクトルの要素同士の組み合わせとして表される。入力ベクトルの要素の組み合わせと、その組み合わせに対応する係数と、が分類関数の演算に利用されるか否かを示す情報を有効領域情報とする。
ＣＰＵ６０１は、Ａnmのうち、他の領域よりも大きい値となる領域を有効領域であるとして決定する。ＣＰＵ６０１は、例えば、入力ベクトルの要素ｎに対応する２次項の係数を、Ｓ２０１〜Ｓ２０４の処理と同様の処理でクラスタリングすることで、他の領域よりも大きい値となる領域を有効領域として決定することとする。また、ＣＰＵ６０１は、Ａnmのうち、設定された閾値よりも大きい値をとる領域を有効領域として決定してもよい。ＣＰＵ６０１は、有効領域に対応する入力ベクトルの要素の組み合わせの情報を、有効領域情報として生成し、生成した有効領域情報を二次記憶装置６０４等に記憶する。このように、情報処理装置３０１は、有効領域情報を生成する機能を有する。有効領域情報を生成する情報処理装置３０１の機能は、有効領域情報を生成する第１の生成手段の一例である。
【００５７】
図９は、情報処理装置８０１の機能構成の一例を示す図である。情報処理装置８０１は、入力ベクトル格納部３０３、判定部３０６、係数読み出し部３０８、係数格納部３０９、中間データ格納部３１０、入力ベクトル読み出し部８０２、演算部８０３、クラスタ制御部８０４を含む。入力ベクトル格納部３０３、判定部３０６、係数読み出し部３０８、係数格納部３０９、中間データ格納部３１０は、実施形態１の図３のものと同様である。
情報処理装置８０１は、実施形態１の情報処理装置３０１と同様に、式１５、１６で表される分類関数ｆ（ｘ）を演算し、演算結果に基づいて、分類判定を行い、分類結果を出力する情報処理装置である。
入力ベクトル読み出し部８０２は、演算部８０３による演算処理に必要な入力ベクトルの要素を、入力ベクトル格納部３０３から複数回、読み出し、演算部８０３に渡す。
【００５８】
演算部８０３は、クラスタ制御部８０４の指示に従って、入力ベクトル読み出し部８０２から渡されたデータと係数読み出し部３０８から渡された係数とに基づいて、分類関数の演算の中間データを演算し、中間データ格納部３１０に格納する。また、演算部３０５は、入力ベクトル読み出し部８０２から渡されたデータと、係数読み出し部３０８から渡された係数と、中間データ格納部３１０に格納される中間データ値と、に基づいて、分類関数の演算を実行する。
中間データ格納部３１０は、演算部８０３により演算された中間データを格納する。中間データ格納部３１０は、演算部８０３により、式１６を用いて演算されたｇn（ｘ）の値を中間データとして格納する。
クラスタ制御部８０４は、入力ベクトル読み出し部８０２、係数読み出し部３０８、演算部８０３に指示を出して、まず、演算部８０３に式１６を用いて、各ｇn（ｘ）（ｎ＝１、２、・・・、Ｄ）を演算させる。次に、クラスタ制御部８０４は、演算部８０３に式１５の分類関数の演算を実行させる。
【００５９】
演算部８０３による演算処理の順序について、図１０を用いて説明する。図１０は、図８と同様に、クラスタリングされた分類関数の２次項の係数全体を示す。中間データ９０３は、中間データ格納部３１０に格納された式１６のｇn（ｘ）を示す。クラスタ制御部８０４は、まず、ｇ1（ｘ）を演算部８０３に演算させるために、矢印群９０１の中の一番上の矢印に相当する部分に対応する入力ベクトルの要素の全てを読み出すように入力ベクトル読み出し部８０２に指示する。また、クラスタ制御部８０４は、読み出しを指示した入力ベクトルの要素に対応する係数Ａ'nm、Ｂnを読み出すように係数読み出し部３０８に指示する。更に、クラスタ制御部８０４は、入力ベクトル読み出し部８０２により読み出されたデータのうち、どの部分が有効領域かを示す有効領域情報を演算部８０３に渡す。
演算部８０３は、渡された有効領域情報に示される入力ベクトルの要素の組み合わせについて、分類関数の中間データの演算を実行してｇ1（ｘ）を算出し、中間データ９０３の最初の要素としてＲＡＭ６０３等に格納する。演算部８０３は、ｇ１（ｘ）の計算が終わると、クラスタ制御部８０４は、矢印群９０１の中の上から２番目の矢印に相当する入力ベクトル要素の読み出しと対応する係数の読み出しと、ｇ２（ｘ）の演算、格納を指示する。クラスタ制御部８０４は、矢印群９０１を上から順にたどってＣｌｕｓｔｅｒ１又はＣｌｕｓｔｅｒ２に属するｇn（ｘ）の演算、格納を指示する。
クラスタ制御部８０４は、Ｃｌｕｓｔｅｒ３に属するｇn（ｘ）に関しては、入力ベクトル要素がＶｅｌｅｍｅｎｔに属していないため、係数Ｂnのみを読み出すように係数読み出し部３０８に指示する。更に、クラスタ制御部８０４は、Ｂnをそのままｇn（ｘ）として中間データ９０３に格納するように演算部８０３にも指示する。次に、クラスタ制御部８０４は、矢印群９０２に対しても矢印群９０１と同様にｇn（ｘ）の計算、格納を指示する。最後のｇn（ｘ）の格納が終わると、クラスタ制御部８０４は、入力ベクトル要素を順に全て読み出すように入力ベクトル読み出し部８０２に指示し、係数Ｃを読み出すように係数読み出し部３０８に指示する。そして、クラスタ制御部８０４は、式１５の分類関数の値を演算して結果を判定部３０６に出力するように演算部８０３に指示する。演算部８０３は、順に読み出された入力ベクトルの要素ｘnと、対応する中間データｇn（ｘ）と、を積和して、積和結果と係数Ｃとを足し合わせることで、式１５の分類関数の値を演算して、演算結果を判定部３０６に出力する。
【００６０】
図１１は、本実施形態の情報処理装置８０１の処理の一例を示すフローチャートである。なお、図１１の処理における演算部８０３による演算順序は、図１０で説明したとおりである。
Ｓ１００１において、演算部８０３は、図９の行方向の入力ベクトルの要素のインデックスｎを１とする。
Ｓ１００２において、演算部８０３は、クラスタ制御部８０４からｎに対応する有効領域情報を取得する。クラスタ制御部８０４は、予め計算され、二次記憶装置６０４等に記憶されている有効領域情報を、演算部８０３に渡すことになる。
Ｓ１００３において、演算部８０３は、図９の列方向の入力ベクトルの要素のインデックスｍを１とする。
【００６１】
Ｓ１００４において、演算部８０３は、Ｓ１００２で取得した有効領域情報に基づいて、現在のｍが有効領域に属するか（ｍがｎと同じクラスタに属するか）否かを判定する。演算部８０３は、現在のｍが有効領域に属すると判定した場合、演算中のｇn（ｘ）の値に、入力ベクトルのｍ番目の要素ｘmと、係数Ａ'nmと、をかけ合わせた値を加える。また、演算部８０３は、現在のｎについて、初めてＳ１００４の処理を行う場合、演算中のｇn（ｘ）の値に、分類関数の１次項の係数Ｂnを加える。このように、演算部８０３が有効領域情報に基づいて、入力ベクトルの要素の組み合わせのそれぞれについて、分類関数の２次項の演算を行うか否かを判定することで、演算量を削減する。情報処理装置８０１は、実施形態１と異なり、有効領域情報を利用することで、入力ベクトルの要素の並べ替えを行うことなく、演算量を削減できる。
Ｓ１００５において、演算部８０３は、ｍを１だけ増やす。
Ｓ１００６において、演算部８０３は、ｍ＞ｎか否かを判定する。演算部８０３は、ｍ＞ｎでないと判定した場合、Ｓ１００４の処理に進む。また、演算部８０３は、ｍ＞ｎであると判定した場合、現在のｎに対するｇn（ｘ）の計算が完了したとして、Ｓ１００７の処理に進む。
Ｓ１００７において、演算部８０３は、ｎを１だけ増やす。
Ｓ１００８において、演算部８０３は、ｎ＞Ｄか否かを判定する。演算部８０３は、ｎ＞Ｄではないと判定した場合、Ｓ１００２の処理に進む。また、演算部８０３は、ｎ＞Ｄであると判定した場合、全てのｎに対するｇn（ｘ）の計算が完了したとして、Ｓ１００９の処理に進む。
【００６２】
Ｓ１００９において、演算部８０３は、入力ベクトルの要素のインデックスｎを１とする。
Ｓ１０１０において、演算部８０３は、現在のｎに対応するｇn（ｘ）と、現在のｎに対応する入力ベクトルの要素ｘnと、をかけ合わせた値を演算中の分類関数ｆ（ｘ）の値に加える。また、演算部８０３は、現在のｎについて、初めてＳ１０１０の処理を行う場合、演算中の分類関数ｆ（ｘ）の値に、分類関数の定数項の係数Ｃを加える。
Ｓ１０１１において、演算部８０３は、ｎを１だけ増やす。
Ｓ１０１２において、演算部８０３は、ｎ＞Ｄか否かを判定する。演算部８０３は、ｎ＞Ｄではないと判定した場合、Ｓ１０１０の処理に進む。また、演算部８０３は、ｎ＞Ｄであると判定した場合、ｆ（ｘ）の演算が完了したとして、演算結果を判定部３０６に送信し、Ｓ１０１３の処理に進む。また、演算部８０３は、分類関数の演算結果の情報を二次記憶装置６０４等にファイル形式で記憶することで出力してもよい。また、演算部８０３は、演算結果の情報を外部の情報処理装置等に送信することで出力してもよい。
Ｓ１０１３において、判定部３０６は、Ｓ１０１２で送信された分類関数ｆ（ｘ）の値に基づいて、分類結果を判定する。判定部３０６は、判定結果の情報を、二次記憶装置６０４等にファイル形式で記憶することで出力することとしてもよいし、外部の情報処理装置に送信することで出力することとしてもよい。
【００６３】
以上、本実施形態の処理により、情報処理装置３０１は、式１５、１６で示す分類関数を第１〜第３の技術と比べて演算回数を削減できる。また、情報処理装置３０１は、分類関数の２次項の係数Ａnmの一部について演算を行わず、１次項の係数Ｂnの全てを計算している。即ち、情報処理装置３０１は、第４の技術と異なり、精度上重要な分類関数の１次項について演算を削除しておらず、分類精度の低下を抑えることができる。
なお、本実施形態では、情報処理装置３０１は、図１０において、式９の対称性によりＡnmの下三角部分だけの計算を行っているが、逆に上三角部分だけの計算を行ってもよい。また、情報処理装置３０１は、式９の対称性を利用せずに、各クラスタの矩形領域全てに対して演算を行ってもよい。
また、本実施形態では、情報処理装置３０１は、判定部３０６を介して、分類関数の判定を行い、分類結果を出力しているが、判定処理を行わずに、分類関数の値を出力することで回帰装置としての機能を実現することもできる。
【００６４】
＜実施形態３＞
実施形態１、２では、２次多項式カーネルの例を説明したが、本実施形態では、３次以上の高次多項式カーネルについても、分類関数の高次項の演算量を削減できる点について説明する。高次項とは２次以上の項のことを意味する。本実施形態では、３次多項式カーネルの例を説明する。本実施形態では、実施形態１と同様に情報処理装置３０１が分類関数の演算を行う。
３次多項式カーネルに関して、式１２に相当する分類関数ｆ（ｘ）の計算式を式変形で導出すると、式１８〜２２のようになる。なお、本実施形態では、情報処理装置３０１は、表記の複雑化を避けるために、係数の対称性は利用しないこととするが、対称性を利用してもよい。
【００６５】
【数１８】
0006700843.tif 000019
【００６６】
【数１９】
0006700843.tif 000020
【００６７】
【数２０】
0006700843.tif 000021
【００６８】
【数２１】
0006700843.tif 000022
【００６９】
【数２２】
0006700843.tif 000023
【００７０】
式１９の係数Ａnmlは、分類関数における３次項の係数である。情報処理装置３０１は、係数Ａnmlについて、各係数のクラスタリングを行い、クラスタリング結果に応じて、各係数に対応する入力ベクトルの各要素についてもクラスタリングを行う。並べ替え部３０２は、同一クラスタのベクトル要素が連続するように、入力ベクトルの要素、及び係数Ａnmlを並べ替える。
図１２は、並べ替え部３０２により並べ替えられた入力ベクトルの要素、及び係数Ａnmlを示す図である。図１２において、領域１１０１は、係数Ａnml全体を示す領域である。クロスハッチされた領域１１０２は、最初のクラスタに属する入力ベクトルの要素の組み合わせｎ、ｍ、ｌに対応する係数を示す領域である。網点で示された領域１１０３は、２番目のクラスタに属する入力ベクトルの要素の組み合わせｎ、ｍ、ｌに対応する係数を示す領域である。
図１２からわかるように、情報処理装置３０１は、係数Ａnmlに関する演算を、クラスタ内に属するベクトル要素の組み合わせに限定することで、３次多項式カーネルの演算量を大幅に減らすことができる。例えば、情報処理装置３０１は、図１２の領域１１０１内の無地の領域に対応する係数については、３次項の演算を行わない。３次項の係数Ａnml、２次項の係数Ｂnmに関する計算を、クラスタ内に属するベクトル要素の組み合わせに限定した場合の分類関数ｆ（ｘ）の計算式を式２３〜２５に示す。
【００７１】
【数２３】
0006700843.tif 000024
【００７２】
【数２４】
0006700843.tif 000025
【００７３】
【数２５】
0006700843.tif 000026
【００７４】
情報処理装置３０１は、式２３〜２５を用いて計算を行うことで、３次多項式カーネルに関しても、実施形態１の２次多項式カーネルの例と同様に、分類関数の演算量を削減することができる。
なお、情報処理装置３０１は、３次係数Ａnmlをクラスタリングする際のベクトル要素間の距離計算に関しては、例えば、次の方法で行う。情報処理装置３０１は、ベクトル要素の番号ｉ、ｊの各組み合わせ（ｉ≠ｊ）に対する距離Ｌijを、式２６を用いて、算出する。即ち、情報処理装置３０１は、ｎ、ｍ、ｌの各値がｉ、ｊだけからなる場合の係数Ａnmlの絶対値の和を算出し、算出した和の逆数をとることで、距離Ｌijを算出する。
【００７５】
【数２６】
0006700843.tif 000027
【００７６】
また、情報処理装置３０１は、３次項の係数Ａnmlだけでなく２次項の係数Ｂnmの値に基づいて、距離を算出してもよい。本実施形態では、情報処理装置３０１は、式２６を用いて算出した距離に基づいて、Ａnmlの各係数をクラスタリングする。
【００７７】
以上、本実施形態の処理により、情報処理装置３０１は、３次以上の高次多項式カーネルについても、分類関数の高次項の演算量を削減できる。
なお、情報処理装置３０１は、本実施形態で説明した３次多項式カーネルの例と同様の拡張を行えば、４次以上の多項式に関しても同様に、分類関数の演算量を削減することができる。
【００７８】
＜その他の実施形態＞
本発明は、上述の実施形態の１以上の機能を実現するプログラムを、ネットワーク又は記憶媒体を介してシステム又は装置に供給し、そのシステム又は装置のコンピュータにおける１つ以上のプロセッサがプログラムを読み出し実行する処理でも実現可能である。また、１以上の機能を実現する回路（例えば、ＡＳＩＣ）によっても実現可能である。
以上、本発明の好ましい実施形態について詳述したが、本発明は係る特定の実施形態に限定されるものではない。
例えば、上述した情報処理装置３０１の機能構成の一部又は全てをハードウェアとして情報処理装置３０１に実装してもよい。
【符号の説明】
【００７９】
３０１  情報処理装置、３０５  演算部、６０１  ＣＰＵ
【図１】
0006700843.tif 000032
【図２】
0006700843.tif 000033
【図３】
0006700843.tif 000034
【図４】
0006700843.tif 000035
【図５】
0006700843.tif 000036
【図６】
0006700843.tif 000037
【図７】
0006700843.tif 000038
【図８】
0006700843.tif 000039
【図９】
0006700843.tif 000040
【図１０】
0006700843.tif 000041
【図１１】
0006700843.tif 000042
【図１２】
0006700843.tif 000043