(57)【要約】【課題】分類関数の計算において、演算量及び演算に用いるルックアップテーブルのサイズを削減する。【解決手段】複数次元の入力ベクトルを取得する。入力ベクトルの各次元について、次元の要素値に対応する変換値を、対応関係を示すルックアップテーブルを参照して、補間演算により算出する。入力ベクトルの各次元について、算出された変換値と、次元に対応する、予め算出されている係数との積を求める。入力ベクトルの各次元について求めた積の合計を用いて算出した値を、入力ベクトルの分類を示す分類値として出力する。【選択図】図４
2014203136.tif 000002
【特許請求の範囲】
【請求項１】
複数次元の入力ベクトルを取得する取得手段と、
前記入力ベクトルの各次元について、該次元の要素値に対応する変換値を、第１の格納手段に格納された、該対応関係を示すルックアップテーブルを参照して、補間演算により算出する変換手段と、
前記入力ベクトルの各次元について、前記変換手段によって算出された変換値と、該次元に対応する、予め算出され第２の格納手段に格納されている係数との積を求める積算手段と、
前記入力ベクトルの各次元について前記積算手段が求めた積の合計を用いて算出した値を、前記入力ベクトルの分類を示す分類値として出力する出力手段と、
を備えることを特徴とする情報処理装置。
【請求項２】
前記変換手段は、前記入力ベクトルの各次元について共通の前記ルックアップテーブルを参照することを特徴とする、請求項１に記載の情報処理装置。
【請求項３】
前記入力ベクトルはＤ次元のベクトルであり、
前記格納手段はＭ個（１≦Ｍ＜Ｄ）の前記ルックアップテーブルを格納しており、前記Ｄ個の次元のそれぞれは、前記Ｍ個のルックアップテーブルの何れかに対応しており、
前記変換手段は、前記入力ベクトルの各次元について、該次元に対応する前記ルックアップテーブルを参照して前記変換値を算出する
ことを特徴とする、請求項１に記載の情報処理装置。
【請求項４】
前記ルックアップテーブルは、入力値のべき乗値を該入力値に対応する変換値として記録していることを特徴とする、請求項１乃至３の何れか１項に記載の情報処理装置。
【請求項５】
前記ルックアップテーブルは、式（２）で表されるカーネル関数に含まれている、２個のスカラ入力変数x及びyに対する値を与える関数k(x, y)を、一変数関数s(x)とs(y)との積で近似した場合における変数xと関数値s(x)との対応関係を示し、
式（２）において、xdはベクトルxのd次元目の要素であり、ydはベクトルyのd次元目の要素である
ことを特徴とする、請求項１乃至４の何れか１項に記載の情報処理装置。
2014203136.tif 000023
【請求項６】
各次元についての前記係数は、該次元についてのサポートベクトルの要素値と、学習結果と、教師ラベルとによって算出されることを特徴とする、請求項１乃至５の何れか１項に記載の情報処理装置。
【請求項７】
前記変換手段は、前記ルックアップテーブルに格納された値を用いた区分線形近似により前記変換値を算出することを特徴とする、請求項１乃至６の何れか１項に記載の情報処理装置。
【請求項８】
前記変換手段は、前記ルックアップテーブルに格納された値を用いた区分定数近似により前記変換値を算出することを特徴とする、請求項１乃至６の何れか１項に記載の情報処理装置。
【請求項９】
前記情報処理装置は、サポートベクトルマシンにより前記入力ベクトルを分類する分類装置であることを特徴とする、請求項１乃至８の何れか１項に記載の情報処理装置。
【請求項１０】
前記出力手段が出力した値を所定の閾値と比較し、該比較結果を前記入力ベクトルの分類結果として出力する分類手段をさらに備えることを特徴とする、請求項１乃至９の何れか１項に記載の情報処理装置。
【請求項１１】
前記情報処理装置は、サポートベクトル回帰による回帰値として前記分類値を算出することを特徴とする、請求項１乃至８の何れか１項に記載の情報処理装置。
【請求項１２】
複数次元の入力ベクトルを取得する取得工程と、
前記入力ベクトルの各次元について、該次元の要素値に対応する変換値を、第１の格納手段に格納された、該対応関係を示すルックアップテーブルを参照して、補間演算により算出する変換工程と、
前記入力ベクトルの各次元について、前記変換工程で算出された変換値と、該次元に対応する、予め算出され第２の格納手段に格納されている係数との積を求める積算工程と、
前記入力ベクトルの各次元について前記積算工程で求めた積の合計を用いて算出した値を、前記入力ベクトルの分類を示す分類値として出力する出力工程と、
を備えることを特徴とする情報処理方法。
【請求項１３】
コンピュータを、請求項１乃至１１の何れか１項に記載の情報処理装置の各手段として機能させるための、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法、及びプログラムに関する。
【背景技術】
【０００２】
画像認識を始めとする様々な応用分野において、ＳＶＭ（Support Vector Machine、サポートベクトルマシン）を用いた分類が用いられている。また、同様の分野において、ＳＶＲ（Support Vector Regression、サポートベクトル回帰）を用いた回帰計算が用いられている。分類対象である入力ベクトルをx、サポートベクトルをxi (i=1, 2, ..., n)、ベクトルx及びyに対するカーネル関数をK(x, y)とするとき、ＳＶＭの分類関数f(x)は式(1)で表される。
【数１】
2014203136.tif 000003
ここで、yiはxiに対応する教師ラベルであり、αi及びbは学習により決定されるパラメータである。
【０００３】
カーネル関数K(x, y)としては、線形カーネル、多項式カーネル、RBFカーネルなど様々な種類の関数が使われている。よく使われるカーネル関数として、非特許文献１に記載のintersection kernelのような、additive kernelと呼ばれるカーネル関数群がある。additive kernelは、式(2)で表される。
【数２】
2014203136.tif 000004
ここで、xd及びydはそれぞれD次元ベクトルであるx及びyのd次元目の要素を表す。また、k(x, y)は２個のスカラ入力変数x及びyから出力値を計算する関数である。
【０００４】
非特許文献２には、additive kernelの具体的な例が記載されている。例えば、式(3)はintersection kernelについてのk(x, y)を、式(4)はχ2 kernelに対するk(x, y)を、それぞれ表す。
【数３】
2014203136.tif 000005
【数４】
2014203136.tif 000006
【０００５】
式(1)の通りに分類関数f(x)を計算すると、サポートベクトル毎にカーネル関数K(x,xi)が計算される。このため、サポートベクトルが多い場合には、何度もカーネル関数の計算及び得られた値とパラメータの積和演算を行う必要があり、演算時間が非常に長くなってしまう。
【０００６】
非特許文献１には、intersection kernelの演算式を変形し、さらに式変形で得られた非線形関数hi(s)を区分線形近似することで、演算量を減らし、演算時間を短くする技術が開示されている。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Subhransu Maji, Alexander C. Berg, Jitendra Malik, "Classification using Intersection Kernel Support Vector Machine is Efficient", In IEEE Conference on Computer Vision and Pattern Recognition, 2008.
【非特許文献２】Andrea Vedaldi, Andrew Zisserman, "Efficient Additive Kernels via Explicit Feature Maps", In IEEE Conference on Computer Vision and Pattern Recognition, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
非特許文献１で開示された技術によれば、入力ベクトルの各次元の要素に対して、次元毎に異なる非線形関数hi(s)が適用される。そして、非線形関数の出力値の総和を求めることで、分類関数が計算される。このように、非特許文献１の技術によれば、次元毎に異なる非線形関数hi(s)を用意しておく必要があり、より大きな記憶容量が必要となる。特に非線形関数hi(s)を区分線形近似で計算する場合には、次元の数に等しいルックアップテーブル（ＬＵＴ、Lookup Table）が必要となるために、ルックアップテーブルを格納するためにより大きな記憶容量が必要であるという課題があった。また、非特許文献１で開示された技術は、intersection kernelを用いる場合を対象としたものであった。
【０００９】
本発明は、分類関数の計算において、演算量及び演算に用いるルックアップテーブルのサイズを削減することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の目的を達成するために、例えば、本発明の情報処理装置は以下の構成を備える。すなわち、
複数次元の入力ベクトルを取得する取得手段と、
前記入力ベクトルの各次元について、該次元の要素値に対応する変換値を、第１の格納手段に格納された、該対応関係を示すルックアップテーブルを参照して、補間演算により算出する変換手段と、
前記入力ベクトルの各次元について、前記変換手段によって算出された変換値と、該次元に対応する、予め算出され第２の格納手段に格納されている係数との積を求める積算手段と、
前記入力ベクトルの各次元について前記積算手段が求めた積の合計を用いて算出した値を、前記入力ベクトルの分類を示す分類値として出力する出力手段と、
を備えることを特徴とする。
【発明の効果】
【００１１】
本発明によれば、分類関数の計算において、演算量及び演算に用いるルックアップテーブルのサイズを削減することを目的とする。
【図面の簡単な説明】
【００１２】
【図１】χ2 kernelについてのk(x, y)の理論値と近似値とのグラフ。
【図２】s(x)及びＬＵＴ値の計算手順を示すフローチャート。
【図３】s(x)の区分線形近似関数であるsapp(x)のグラフ。
【図４】実施例１に係る分類装置の例示的な構成図。
【図５】実施例２に係る回帰装置の例示的な構成図。
【図６】実施例１に係る分類装置が行う例示的な処理のフローチャート。
【図７】実施例４に係る分類装置の例示的な構成図。
【図８】実施例３に係る情報処理装置の例示的な構成図。
【図９】ルックアップテーブルを生成する情報処理装置の例示的な構成図。
【発明を実施するための形態】
【実施例１】
【００１３】
実施例１に係る情報処理装置は、additive kernel SVM（サポートベクトルマシン）を用いた分類装置である。まず、分類関数f(x)の計算方法について説明する。
【００１４】
図１は、χ2 kernelに対するk(x, y)のグラフである。上述のように、k(x, y)は２個のスカラ入力変数x及びyから出力値を計算する関数である。図１において、実線は式(4)で示されるk(x, y)の値を示す。以下の説明では、入力ベクトルxの各要素の値は、0〜1の範囲に収まるよう正規化されているものとする。しかしながら、入力ベクトルの各要素の値が0〜1の範囲に収まるように正規化されていることは必須ではない。例えば、入力ベクトルの各要素の値は-1〜1に正規化されていてもよい。
【００１５】
図１に示すように、χ2 kernelをはじめとするカーネル関数についてのk(x, y)の形状は、通常x, yに関して対称である。ある程度の誤差を許容する場合には、k(x, y)は、入力変数毎の関数（変数分離可能な関数）の積として近似することができる。より具体的にはk(x, y)は、x及びyに共通の一変数関数s(x)を用いて、式(5)に示すように近似することができる。
【数５】
2014203136.tif 000007
【００１６】
図１において、破線は、式(5)においてs(x) = x0.5644とした場合の、k(x, y)の近似値である。このように、関数s(x)を用いて、式(4)のk(x, y)の形状をある程度の誤差で近似できていることがわかる。
【００１７】
k(x, y)を用いたadditive kernelに対する分類関数f(x)は、式(5)の近似を用いて、式(6)のように表すことができる。式(6)は、式(1)に式(2)及び式(5)を代入し、式変形することで得られる。この際、式(2)のベクトルy及びベクトルyのd次元目の要素ydとして、ベクトルxi及びベクトルxiのd次元目の要素xidが用いられる。
【数６】
2014203136.tif 000008
ここで、wdは式(7)に従って計算可能な係数である。
【００１８】
2014203136.tif 000009
【００１９】
式(5)の近似を用いる場合、分類関数f(x)の値は、式(6)に示すように、入力ベクトルxの各次元の要素に対して関数s(x)を適用した後、係数wdとの積和演算を行うことにより得られる。このため、式(5)の近似を用いずに式(1)に従って分類関数f(x)を計算する場合と比べ、演算量を大幅に減らすことができる。演算量を減少させる効果は、サポートベクトル数nが大きな場合に特に顕著である。s(x)は通常非線形な関数であるが、ルックアップテーブル（ＬＵＴ、lookup table）を用いた区分線形近似により、s(x)を求める際の演算量を抑えることができる。このルックアップテーブルは、変数xと関数値s(x)との対応関係を示し、この対応関係に従って入力値を変換値へと変換する。例えば、関数s(x)が式(8)のべき乗関数である場合には、ルックアップテーブルは入力値のべき乗値を変換値として記録している。
【００２０】
次に、additive kernelの関数k(x, y)が与えられた場合にs(x)を決定する方法、及びs(x)を区分線形近似により計算するために用いられるルックアップテーブルの生成方法について、図２を参照して説明する。図２に示す算出方法は、例えば、図９に示す情報処理装置900によって行われうる。
【００２１】
ステップS201において取得部910は、additive kernelを構成する関数k(x, y)を取得する。例えば取得部910は、ユーザが入力した、関数k(x, y)を示すデータを取得することができる。k(x, y)は、式(3)及び(4)に示すように数式として与えられてもよいし、関数値をサンプリングして得られた数値列として与えられてもよい。
【００２２】
ステップS202において選択部920は、式(5)の近似に用いる関数s(x)を選択する。例えば選択部920は、ユーザが入力した、関数s(x)を指定するデータを取得することにより、この選択を行うことができる。関数s(x)の例としては、パラメータβを含む式(8)のべき乗関数や、パラメータγを含む式(9)の２次関数が挙げられる。しかしながら、近似精度が十分であれば、他の関数を用いることもできる。
【数８】
2014203136.tif 000010
【数９】
2014203136.tif 000011
【００２３】
ステップS203において最適化部930は、s(x)・s(y)がk(x, y)を最もよく近似するように、関数s(x)のパラメータを最適化する。最適化方法としては、一般的なカーブフィッティングの技術を用いることができる。例えば最適化部930は、s(x)・s(y)とk(x, y)との２乗誤差を最小化するように、最小２乗法を用いてs(x)のパラメータ値を決定することができる。具体的な一例としては、式(8)のs(x)を用いて式(4)で与えられるk(x, y)を近似する場合、最小２乗法による最適なパラメータとしてβ=0.5644が得られうる。こうして、ステップS203において最適化部930は関数s(x)を決定する。
【００２４】
ステップS204において演算部940は、ステップS203において決定された関数s(x)を区分線形近似により計算するために用いられるルックアップテーブルを生成する。以下で図３を参照して、ルックアップテーブルを構成するＬＵＴ値の算出方法について説明する。図３には、関数s(x)と、s(x)を近似する関数sapp(x)との例が示されている。本実施例では、入力ベクトルの要素の値域がN分割され、それぞれの分割域について関数s(x)が直線近似される。図３の例においては、関数sapp(x)は複数の線分により構成されており、それぞれの線分は、N分割された値域のそれぞれにおいて関数s(x)を近似している。図３において、それぞれの線分の端点は黒丸で表されており、その座標は(i/N, s(i/N))及び((i+1)/N, s((i+1)/N))で表される。
【００２５】
sapp(x)の値は、対応する分割域、すなわちxを含む分割域、においてs(x)を近似する線分の端点を参照して求めることができる。本実施例において演算部940は、図３において黒丸で示される各線分の端点におけるs(x)の値を、ＬＵＴ値として算出する。
【００２６】
より具体的には、i番目(0≦i≦N)のＬＵＴ値であるLUT[i]は、式(10)により計算できる。
【数１０】
2014203136.tif 000012
【００２７】
ＬＵＴ値が式(10)で表される場合、式(11)の範囲にある入力値x0に対応するsapp(x0)の値は、i番目及びi+1番目のＬＵＴ値であるLUT[i]及びLUT[i+1]を用いて、式(12)により計算できる。
【数１１】
2014203136.tif 000013
【数１２】
2014203136.tif 000014
【００２８】
演算部940はそして、得られたＬＵＴ値を格納部（不図示）に格納する。こうして生成された一次元のルックアップテーブルには、N+1個のＬＵＴ値が格納される。このN+1個のＬＵＴ値を用いることにより、関数s(x)をN区間に分けて区分線形近似することができる。区間数Nは必要な近似精度、又は使用可能なルックアップテーブルのサイズにより決めればよい。例えば、Nの値は8、16、32、64、又は128でありうる。
【００２９】
本実施例においては、ステップS203で関数s(x)のパラメータを最適化した後に、ステップS204でＬＵＴ値を算出し、ルックアップテーブルを生成した。しかしながら、ＬＵＴ値が関数s(x)のパラメータを表していてもよい。例えば、各分割域に対応するＬＵＴ値が、分割域における線分の傾き及び切片を表していてもよい。この場合、ステップS203におけるパラメータの最適化によりＬＵＴ値が決定されるため、ステップS204は不要である。
【００３０】
また、ステップS203においては、s(x)・s(y)がk(x, y)を最もよく近似するようにパラメータの最適化を行った。しかしながら、関数の近似精度を最適化する代わりに、ＳＶＭ全体の分類性能が最適となるように、学習によりパラメータの最適化を行ってもよい。この場合、学習によりカーネルのパラメータを決定する技術が適用できる。
【００３１】
本実施例において演算部940は図３の方法でＬＵＴ値を算出したが、ＬＵＴ値の算出方法はこの方法に限られない。例えば、入力ベクトルの要素の値域は均等にN分割されなくてもよく、異なった大きさに分割されてもよい。さらに、各分割域においてs(x)を近似する線分を上述の方法で求める必要はなく、例えば最小２乗法によりs(x)を近似する線分を求めてもよい。さらには、区分近似を区分線形関数（１次関数）により行う必要はなく、区分定数関数による近似（区分定数近似）や、区分２次関数による近似などの、他の近似方法を用いてもよい。この場合、各分割域についての近似値の計算に必要なパラメータがルックアップテーブル上に保持される。この場合であっても、例えば後述する補間演算部402は、ルックアップテーブル上に保持されているパラメータを参照することにより、s(x)の近似値を算出することができる。
【００３２】
次に、実施例１に係る情報処理装置である、分類装置の構成及びその処理について説明する。本実施例に係る分類装置の構成を図４に示し、本実施例に係る分類装置が行う処理のフローチャートを図６に示す。分類装置401は、以上の手順で得られたルックアップテーブルと、式(7)に従って予め計算されたwdとを用いて入力ベクトルを分類する。より具体的には、分類装置401は入力ベクトルxを取得し、ルックアップテーブルを参照して、分類関数f(x)の値に相当する分類値を算出する。この分類値は、入力ベクトルの分類を示すものであり、分類装置401はこの分類値に従って入力ベクトルを分類し、分類結果を出力する。
【００３３】
分類装置401は、補間演算部402、ＬＵＴ403、積和演算部404、係数保持部405、及び分類判定部406を備える。
【００３４】
ステップS601において補間演算部402は、複数次元の入力ベクトルxを取得する（取得手段）。本実施例において入力ベクトルはＤ次元のベクトルであり、(x1, x2, ..., xD)で表される。補間演算部402は、入力ベクトルxをユーザ入力として取得してもよいし、他の装置から取得してもよい。
【００３５】
ステップS602において補間演算部402は、入力ベクトルの各次元の要素値に対応する変換値を、ＬＵＴ403を参照して、補間演算により算出する。より具体的には補間演算部402は、ＬＵＴ403を参照して、入力ベクトルの各次元の要素xd(1≦d≦D)に対応する近似関数値sapp(xd)を算出する。ＬＵＴ403は、s(x)を補間演算、例えば区分線形近似により計算するために用いられるルックアップテーブルであり、例えば式(10)に示す値を保持するルックアップテーブルである。このＬＵＴ403は、この要素値と変換値（近似関数値sapp(xd)）との対応関係を示している。一例としてのＬＵＴ403は、例えば図２に示す方法に従って算出されたＬＵＴ値を保持している。補間演算部402は、ＬＵＴ403を参照して、式(12)に従ってsapp(xd)を算出する。ＬＵＴ403は、分類装置401が有する格納部（第１の格納手段、不図示）に格納されている。
【００３６】
ステップS603において積和演算部404は、次元毎に、補間演算部402が出力した近似関数値sapp(xd)（変換値）と係数保持部405から読み出した係数wdとの積を算出する（積算手段）。また積和演算部404は、各次元について算出した積を累積することにより、各次元について算出した積の合計を求める。
【００３７】
ステップS604において積和演算部404は、ステップS603で得られた累積値にオフセットを示すパラメータ値bを加算する。ステップS603及びステップS604で行われる演算により、以下の式(13)に示す分類関数f(x)の値に相当する分類値が得られ、積和演算部404はこの分類値を分類判定部406へと出力する（出力手段）。
【数１３】
2014203136.tif 000015
【００３８】
係数保持部405は、入力ベクトルの各次元に対応する係数wdとオフセットを示すパラメータbとを保持している。係数wdは、式(7)に従って予め計算され、係数保持部405のような格納部（第２の格納手段）に格納されている。もっとも、ＬＵＴ403と、係数wd及びパラメータbとが、同じ格納部に格納されていてもよい。
【００３９】
上述のように係数wdは、学習により決定されるパラメータαi（学習結果）、次元dについてのサポートベクトルxiの要素値、及び教師ラベルyiから算出される。また、パラメータbも学習により決定された学習結果である。これらの値は、従来技術に従って算出することができる。積和演算部404は、これらの係数及びパラメータを係数保持部405から読み出して使用する。
【００４０】
ステップS605において分類判定部406は、ステップS604において積和演算部404が算出した分類値を所定の閾値と比較する。閾値としては、通常は０が用いられるが、これに限定されるわけではない。そしてステップS606において分類判定部406は、ステップS406における比較結果、すなわち閾値と分類関数f(x)の値との大小関係を、入力ベクトルxについての分類結果として出力する（分類手段）。
【００４１】
このように、本実施例に係る分類装置401によれば、近似を行わずに式(1)及び(2)をそのまま用いる場合と比べ、additive kernel SVMの分類関数f(x)の値を得る際の演算量を大幅に減らすことができる。また、非特許文献１の方法では次元毎に異なるルックアップテーブルが必要であったのに対し、本実施例に係る分類装置401は、次元毎に共通である１種類のルックアップテーブルを用いて分類関数f(x)の値を得ることができる。したがって、分類装置401が保持するルックアップテーブルの総サイズを大幅に減らすことができる。また、非特許文献１の方法はintersection kernelに対して適用される技術である。一方で本実施例に係る分類装置401は、式(5)の近似が許容できるのであれば、intersection kernelに限られない様々なadditive kernelを用いた分類において汎用的に用いることができる。
【実施例２】
【００４２】
以下に、実施例２に係る情報処理装置である、additive kernel SVR（サポートベクトル回帰）を用いて回帰値を算出する回帰装置について説明する。分類関数f(x)及びその近似方法は実施例１と同様であるため、説明を省略する。
【００４３】
実施例２に係る回帰装置501の構成を図５に示す。回帰装置501は、入力ベクトルxを取得し、分類関数f(x)の値を取得して、得られた値を回帰値として出力する。回帰装置501の構成は、実施例１の分類装置401から分類判定部406を取り除いたものに相当し、回帰装置501は、積和演算部404が算出した分類値を回帰値として出力する。補間演算部402、ＬＵＴ403、積和演算部404、及び係数保持部405の構成及び動作は実施例１と同じであるため、説明を省略する。
【００４４】
実施例２によれば、実施例１と同様の原理により、ＳＶＲを計算する回帰装置についても、演算量及びルックアップテーブルのサイズを削減することができる。
【００４５】
上述のように、実施例１に係る分類装置と実施例２に係る回帰装置との構成上の差異は、分類判定部406の有無だけである。したがって、実施例１に係る分類装置を、入力ベクトルxに対する回帰値を算出する回帰装置として用いることもできる。この場合、分類判定部406を用いるか否かを制御する切り替え部（不図示）を、実施例１に係る分類装置が有していてもよい。このような切り替え部を設けることにより、分類装置が分類結果又は回帰値を出力するように、実施例１に係る分類装置の動作を切り替えることができる。
【実施例３】
【００４６】
実施例３では、汎用の情報処理装置を用いて、実施例１に係る分類装置を実現する方法について説明する。分類関数f(x)及びその近似方法は実施例１と同様であるため、説明を省略する。
【００４７】
実施例３に係る情報処理装置のハードウェア構成の一例を図８に示す。なお、図８には、最も典型的な情報処理装置である、パーソナルコンピュータの構成を示している。しかしながら本実施例に係る情報処理装置は、例えば、組み込みデバイス、デジタルカメラ、又はハンドヘルドデバイスなどであってもよい。
【００４８】
ＣＰＵ801は、図６に示すフローチャートに対応する処理手順を含む各種プログラムを実行し、情報処理装置が有する各部の制御を行う。ＲＯＭ802は、不揮発性のメモリであり、情報処理装置の初期動作において必要なプログラムなどを記憶する。ＲＡＭ803は、ＣＰＵ801のワークエリアを提供し、２次記憶装置804から読み出されたプログラムなどを一時記憶する、揮発性のメモリである。２次記憶装置804は、ＣＰＵ801が使用するプログラムを記録する。より具体的には、２次記憶装置804のような記憶媒体からプログラムをＲＡＭ803へと読み出し、ＲＡＭ803へと読み出されたコンピュータプログラムに従ってＣＰＵ801が動作することにより、図４に示す各部の機能及び図６に示す各処理が実現される。
【００４９】
各デバイス801〜804は、システムバス805を通じて情報をやり取りする。また、情報処理装置は、システムバス805を介して、ディスプレイ806、キーボード807、マウス808、及びＩ／Ｏデバイス809と接続されている。ディスプレイ806は、ユーザに処理結果や処理の途中経過などの情報を表示するために使用できる。キーボード807及びマウス808は、ユーザからの指示を情報処理装置へと入力するために用いられる。Ｉ／Ｏデバイス809としては、外部との通信のインタフェースとなる通信装置、カメラ・スキャナなどの入力装置、又はプリンタなどの出力装置などが挙げられる。
【００５０】
実施例３によれば、ソフトウェアプログラムを用いて入力ベクトルxの分類を行う場合であっても、演算量及びルックアップテーブルのサイズを削減することができる。ルックアップテーブルのサイズが小さくなると、ソフトウェアプログラムの実行時にＣＰＵキャッシュのヒット率が高まるため、ルックアップテーブルのサイズが大きな場合と比較して実行速度が向上する。
【００５１】
実施例３では、汎用の情報処理装置を用いて実施例１に係る分類装置を実現する方法について説明した。しかしながら、図６のステップS605の処理を行わず、積和演算部404が算出した分類値を回帰値として出力することにより、ＳＶＲの計算を行うこと、すなわち実施例２に係る回帰装置を実現することも可能である。
【実施例４】
【００５２】
以下に、実施例４に係る情報処理装置である、additive kernel SVMを用いた分類装置について説明する。実施例１では、入力ベクトルの各次元に対して共通の関数k(x, y)及びsapp(x)を用いた。一方で実施例４では、複数の関数kj(x, y)及びsjapp(x)を使い分ける。
【００５３】
ここで、D次元の入力ベクトルの各次元を示すD個の次元インデックスd (d=1, 2, ..., D)を、Ｍ個の重ならない集合Sj (j=1, 2, ..., M)に分割する。ここで、後述するルックアップテーブルの数を削減する観点から、通常は1≦M＜Dである。次元インデックスdが集合Sjに属する場合は、additive kernelを構成する関数k(x, y)として、kj(x, y)を用いる。ここでそれぞれのjについてのkj(x, y)としては、異なる関数を用いることができる。
【００５４】
それぞれの集合Sjに属する次元ごとに、カーネル関数Kj(x, y)(j=1, 2, ..., M)が定義されているものと考える。この場合、Kj(x, y)は式(14)で表すことができる。
【数１４】
2014203136.tif 000016
【００５５】
Kj(x, y)の線形和を新たなカーネル関数とすると、K(x, y)は式(15)で表すことができる。
【数１５】
2014203136.tif 000017
ただし、重み係数βjは、次の条件を満たす。
【数１６】
2014203136.tif 000018
【数１７】
2014203136.tif 000019
【００５６】
式(15)〜(17)の形で表されるカーネル関数については、Multiple Kernel Learning技術による学習が可能である。以下では、学習により分類関数f(x)の計算に必要な係数が求まっているものとする。
【００５７】
それぞれの関数kj(x, y)については、関数kj(x, y)を近似するために用いる近似関数sj(xd)を、実施例１と同様に求めることができる。また、関数sj(xd)を近似する近似関数sjapp(x)も、実施例１と同様に求めることができる。さらに、近似関数sjapp(x)を計算するために用いられるルックアップテーブルLUTj(j=1 ,2 , ..., M)も、実施例１と同様に生成することができる。
【００５８】
この場合の分類関数f(x)は、式(20)の近似を用いて、式(18)及び(19)のように表すことができる。式(18)及び(19)は、実施例１の式(6)と同様に、式(1)に式(14)、(15)、及び式(5)を代入し、式変形することで得られる。
【数１８】
2014203136.tif 000020
【数１９】
2014203136.tif 000021
【数２０】
2014203136.tif 000022
【００５９】
LUTjは、それぞれのjについて、sjapp(xd)を計算するために必要な値を保持するルックアップテーブルである。こうして生成されたそれぞれのルックアップテーブルLUTjには、N+1個のＬＵＴ値が格納される。このN+1個のＬＵＴ値を用いることにより、関数sj(x)をN区間に分けて区分線形近似することができる。ルックアップテーブルの総数はM個（図７では４個）である。もっとも、全てのLUTjについて区間数Nが同一である必要はない。
【００６０】
以上のように、Ｄ個の次元のそれぞれには、M個のルックアップテーブルのうち何れかが対応付けられる。より具体的には、次元インデックスdが集合Sjに属する場合には、d番目の次元にはLUTjが対応付けられる。
【００６１】
以下に、実施例４に係る情報処理装置である、分類装置の構成及びその処理について説明する。本実施例に係る分類装置の構成を図７に示す。分類装置701は、補間演算部702、Ｍ個のルックアップテーブル703-1、703-2、703-3、703-4、積和演算部404、係数保持部405、及び分類判定部406を備える。
【００６２】
分類装置701は、上述のように得られたルックアップテーブルと、予め計算されたwdとを用いて入力ベクトルを分類する。実施例４で行われる処理は、図６に示される実施例１の処理と類似しており、以下では異なる点について説明する。本実施例においては、使用する関数kj(x, y)関数の種類は４種類(M=4)であるものとする。しかしながら本実施例の方法はM=4の場合に限定されるわけではない。
【００６３】
ステップS601において補間演算部702は、実施例１の補間演算部402と同様に、入力ベクトルxを取得する。
【００６４】
ステップS602において補間演算部702は、入力ベクトルxの各次元の要素xdについて、どのkj(x, y)関数を用いるかを判定する。言い換えれば、補間演算部702は、入力ベクトルxの各次元の要素xdについての次元インデックスdが、どの集合Sjに属するのかを判定する。この判定は、例えば、次元インデックスdがどの集合Sjに属するのかを示すデータを記憶している記憶部（不図示）を参照して行うことができる。
【００６５】
次に補間演算部702は、入力ベクトルxの各次元の要素xdについて、対応するルックアップテーブル703-jを参照して、近似関数値sapp(xd)を算出する。ルックアップテーブル703-jは、それぞれLUTjに対応し、LUTjのＬＵＴ値を格納している。また、M個のルックアップテーブル703-jは、分類装置701が有する格納部（不図示）に格納されている。ルックアップテーブル703-jを用いた近似関数値sapp(xd)の算出は、実施例１と同様に補間演算により行うことができる。
【００６６】
ステップS603において積和演算部404は、次元毎に、補間演算部702が出力した近似関数値sjapp(xd)と係数保持部405から読み出した係数wdとの積を算出し、各次元について得られた積を累積する。ステップS604において積和演算部404は、ステップS603で得られた累積値にオフセットを示すパラメータ値bを加算する。ステップS603及びS304で行われる演算により、式(18)に示す分類関数f(x)の値に相当する分類値が得られる。
【００６７】
係数保持部405は、入力ベクトルの各次元に対応する係数wdとオフセットを示すパラメータbとを保持している。これらの係数及びパラメータは、上述のように、従来技術に従って学習により算出することができる。
【００６８】
ステップS605及びステップS606において分類判定部406は、実施例１と同様に、ステップS604で得られた分類値を閾値と比較し、入力ベクトルxについての分類結果を出力する。
【００６９】
このように実施例４に係る分類装置701によれば、M個のルックアップテーブル703-jを用いることで、次元毎に複数のkj(x, y)関数を使い分けることができる。このため、実施例１と比べて、より分類精度を向上させることができる。実施例４では複数個（M個）のルックアップテーブルが使用されるが、Mの値を入力ベクトルの次元数Dよりも小さくすることにより、非特許文献１の方法を用いる場合よりもルックアップテーブルの総サイズを小さくすることができる。
【００７０】
実施例４においては分類装置について説明したが、実施例４と同様の構成を用いて、実施例２と同様にＳＶＲを計算する回帰装置を実現することもできる。
【図１】
2014203136.tif 000024
【図２】
2014203136.tif 000025
【図３】
2014203136.tif 000026
【図４】
2014203136.tif 000027
【図５】
2014203136.tif 000028
【図６】
2014203136.tif 000029
【図７】
2014203136.tif 000030
【図８】
2014203136.tif 000031
【図９】
2014203136.tif 000032