(57)【特許請求の範囲】
【請求項１】
トレーニングサンプルｘｔと学習ラベルｊｔからなるトレーニングデータＺを用いてスコア関数のパラメタベクトル集合Λを推定するパターン識別方法であって、
ｍは基底ベクトルの番号を表し、ｊは学習ラベルの番号を表し、ｔはトレーニングデータの番号を表すとして、
基底ベクトル集合記憶部に、基底ベクトルｙｍが記憶されており、
結合係数記憶部に、学習ラベルｊに対するパラメタベクトルλｊの結合係数βｊ，ｍが記憶されており、
トレーニングデータ記憶部に、トレーニングデータＺが記憶されており、
直交化行列記憶部に、正規直交化行列Ｑが記憶されており、
直交化勾配ベクトル算出部が、前記基底ベクトルｙｍを用いて、前記正規直交化行列Ｑを生成する初期化ステップと、
結合係数決定部が、前記トレーニングサンプルｘｔと前記基底ベクトルｙｍから、前記結合係数βｊ，ｍを求める結合係数決定ステップと、
直交化勾配ベクトル算出部が、前記トレーニングサンプルｘｔと前記基底ベクトルｙｍと前記結合係数βｊ，ｍから、勾配ベクトルの結合係数ｄｊ，ｔと勾配ベクトルの結合係数ｒｊ，ｍを算出するｒ算出ステップと、
直交化勾配ベクトル算出部が、前記トレーニングサンプルｘｔと前記基底ベクトルｙｍと前記結合係数ｒｊ，ｍと前記正規直交化行列Ｑから、直交化勾配ベクトルの結合係数ｒ＾ｊ，ｍを算出するｒ＾算出ステップと、
新規基底ベクトル決定部が、前記トレーニングサンプルｘｔと前記結合係数ｄｊ，ｔと前記結合係数ｒ＾ｊ，ｍから、直交化勾配ベクトルを前記基底ベクトルｙｍで近似することにより、新規基底ベクトルｙｅを求め、当該新規基底ベクトルｙｅを前記基底ベクトルｙｍに追加することにより、前記基底ベクトルｙｍを更新する新規基底ベクトル決定ステップと、
直交化勾配ベクトル算出部が、前記基底ベクトルｙｍを用いて、前記正規直交化行列Ｑを更新する直交化行列更新ステップと、
を有することを特徴とするパターン識別方法。
【請求項２】
請求項１に記載のパターン識別方法であって、
前記ｒ＾算出ステップと前記新規基底ベクトル決定ステップと前記直交化行列更新ステップは、所定の回数繰り返し実行され、
前記結合係数決定ステップと前記ｒ算出ステップと前記ｒ＾算出ステップと前記新規基底ベクトル決定ステップと前記直交化行列更新ステップは、前記結合係数βｊ，ｍが収束するまで繰り返し実行される
ことを特徴とするパターン識別方法。
【請求項３】
請求項１又は２に記載のパターン識別方法であって、
φは入力サンプルに非線形処理を施した超高次元に写像する特徴抽出関数であり、Ｋは特徴抽出後の空間における内積を示すカーネル関数であり、Ｉは単位行列であり、Φはφ（ｙｍ）をｍ行目に持つ行列であるとして、
前記勾配ベクトルは、
【数２７】
0005486569.tif 000028
であり、
前記直交化勾配ベクトルは、
【数２８】
0005486569.tif 000029
であり、
前記正規直交化行列Ｑは、
【数２９】
0005486569.tif 000030
を満たすような行列であり、
前記ｒ＾算出ステップは、前記トレーニングサンプルｘｔと前記基底ベクトルｙｍと前記結合係数ｒｊ，ｍから、前記勾配ベクトルへの射影ｋｊ，ｍを、
【数３０】
0005486569.tif 000031
のように、算出し、前記正規直交化行列Ｑと前記射影ｋｊ，ｍから、修正項ηｊ，ｍを、
【数３１】
0005486569.tif 000032
のように、算出し、前記結合係数ｒｊ，ｍと前記修正項ηｊ，ｍから、前記結合係数ｒ＾ｊ，ｍを、
【数３２】
0005486569.tif 000033
のように、算出する
ことを特徴とするパターン識別方法。
【請求項４】
トレーニングサンプルｘｔと学習ラベルｊｔからなるトレーニングデータＺを用いてスコア関数のパラメタベクトル集合Λを推定するパターン識別装置であって、
ｍは基底ベクトルの番号を表し、ｊは学習ラベルの番号を表し、ｔはトレーニングデータの番号を表すとして、
基底ベクトルｙｍを記憶する基底ベクトル集合記憶部と、
学習ラベルｊに対するパラメタベクトルλｊの結合係数βｊ，ｍを記憶する結合係数記憶部と、
トレーニングデータＺを記憶するトレーニングデータ記憶部と、
正規直交化行列Ｑを記憶する直交化行列記憶部と、
直交化勾配ベクトル算出部と、
前記トレーニングサンプルｘｔと前記基底ベクトルｙｍから、前記結合係数βｊ，ｍを求める結合係数決定部と、
前記トレーニングサンプルｘｔと勾配ベクトルの結合係数ｄｊ，ｔと直交化勾配ベクトルの結合係数ｒ＾ｊ，ｍから、直交化勾配ベクトルを前記基底ベクトルｙｍで近似することにより、新規基底ベクトルｙｅを求め、当該新規基底ベクトルｙｅを前記基底ベクトルｙｍに追加することにより、前記基底ベクトルｙｍを更新する新規基底ベクトル決定部と、
を備え、
前記直交化勾配ベクトル算出部は、
前記基底ベクトルｙｍを用いて、前記正規直交化行列Ｑを生成する初期化手段と、
前記トレーニングサンプルｘｔと前記基底ベクトルｙｍと前記結合係数βｊ，ｍから、前記結合係数ｄｊ，ｔと前記結合係数ｒｊ，ｍを算出するｒ算出手段と、
前記トレーニングサンプルｘｔと前記基底ベクトルｙｍと前記結合係数ｒｊ，ｍと前記正規直交化行列Ｑから、前記結合係数ｒ＾ｊ，ｍを算出するｒ＾算出手段と、
前記基底ベクトルｙｍを用いて、前記正規直交化行列Ｑを更新する直交化行列更新手段と、
を有することを特徴とするパターン識別装置。
【請求項５】
請求項４に記載のパターン識別装置であって、
φは入力サンプルに非線形処理を施した超高次元に写像する特徴抽出関数であり、Ｋは特徴抽出後の空間における内積を示すカーネル関数であり、Ｉは単位行列であり、Φはφ（ｙｍ）をｍ行目に持つ行列であるとして、
前記勾配ベクトルは、
【数３３】
0005486569.tif 000034
であり、
前記直交化勾配ベクトルは、
【数３４】
0005486569.tif 000035
であり、
前記正規直交化行列Ｑは、
【数３５】
0005486569.tif 000036
を満たすような行列であり、
前記ｒ＾算出手段は、前記トレーニングサンプルｘｔと前記基底ベクトルｙｍと前記結合係数ｒｊ，ｍから、前記勾配ベクトルへの射影ｋｊ，ｍを、
【数３６】
0005486569.tif 000037
のように、算出し、前記正規直交化行列Ｑと前記射影ｋｊ，ｍから、修正項ηｊ，ｍを、
【数３７】
0005486569.tif 000038
のように、算出し、前記結合係数ｒｊ，ｍと前記修正項ηｊ，ｍから、前記結合係数ｒ＾ｊ，ｍを、
【数３８】
0005486569.tif 000039
のように、算出する
ことを特徴とするパターン識別装置。
【請求項６】
請求項１から３のいずれかに記載されたパターン識別方法の各ステップをコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、トレーニングサンプルと学習ラベルからなるトレーニングデータを用いて、最適なスコア関数のパラメタベクトルを推定するパターン識別方法、パターン識別装置、およびプログラムに関する。
【背景技術】
【０００２】
従来、カーネル法に基づくパターン識別装置は、トレーニングデータからパラメタを推定する訓練時間に、トレーニングサンプル数の二乗に比例する時間が必要であった。また、パラメタ推定が適切であっても、識別結果を算出する際に、トレーニングサンプル数に比例する時間が必要であった。近年のカーネル法の進展により、パラメタ推定を、トレーニングサンプル数に比例する、いわゆる線形時間を実現する方式として、Ｓｕｐｐｏｒｔ  Ｖｅｃｔｏｒ  Ｍａｃｈｉｎｅ（以下、ＳＶＭ）との組み合わせにおいて線形時間を実現するＣｕｔｔｉｎｇ  Ｐｌａｎｅ  Ｓｕｂｓｐａｃｅ  Ｐｅｒｓｕｉｔ法（以下、ＣＰＳＰ法）（非特許文献１）や、ＳＶＭ以外でのカーネル法に基づく識別装置においても線形時間を達成するＫｅｒｎｅｌ  Ｇｒａｄｉｅｎｔ  Ｍａｔｃｈｉｎｇ  Ｐｕｒｓｕｉｔ法（以下、ＫＧＭＰ法）（非特許文献２）が考えられてきた。
【０００３】
以下、非特許文献２に記載されたＫＧＭＰ法に基づく従来のパターン識別装置について説明する。従来のパターン識別装置は、入力サンプルと同じ空間にある少数の任意の点を基底ベクトルとして、その特徴の線形結合を利用してパラメタベクトルを表現する。このような表現を用いることにより、パラメタを推定することを、結合係数と基底ベクトルを推定することに置き換えて考えている。
【０００４】
従来のパターン識別装置は、勾配ベクトル算出部と結合係数決定部と新規基底ベクトル決定部と基底ベクトル集合記憶部と結合係数記憶部とトレーニングデータ記憶部を備える。基底ベクトル集合記憶部は、既存の基底ベクトルを記憶する。結合係数記憶部は、全ての結合係数を記憶する。トレーニングデータ記憶部は、トレーニングサンプルと学習ラベルからなるトレーニングデータを記憶する。結合係数決定部は、既存の基底ベクトルを用いて、結合係数を最適化する。勾配ベクトル算出部は、最適化された結合係数から、勾配ベクトルを算出する。新規基底ベクトル算出部は、最小二乗誤差基準を用いて、勾配ベクトルを所定の数の基底ベクトルで近似することで、所定の数の新規基底ベクトルを求め、既存の基底ベクトルに新規基底ベクトルを追加する。これらの処理を収束するまで繰り返し実行することにより、最適なパラメタを推定する。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】T. Joachims and C.-N. John Yu. Sparse kernel SVMs via cutting-plane training. Machine Learning Journal, 76(2-3):179-193, 2009.
【非特許文献２】Y. Kubo, S. Wiesler, R. Schlueter, H. Ney, S. Watanabe, A. Nakamura, and T. Kobayashi. Subspace pursuit method for kernel-log-linear models. In Proc. International Conference on Acoustics, Speech and Signal Processing, pages 4500-4503, 2011.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来のパターン識別装置は、新規基底ベクトルを追加する際に、局所解を多く含む複雑な同時最適化問題を解いていたため、一つの勾配ベクトルから複数の新規基底ベクトルを取得する場合に、非常に近い挙動を示す基底ベクトルが複数選ばれ、冗長な基底ベクトル集合を得てしまうことがあった。
【０００７】
本発明はこのような点に鑑みてなされたものであり、より少ない基底ベクトルで、より精密なパラメタを推定することで、識別性能を向上し、訓練処理と識別処理を高速化することができるパターン識別装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の課題を解決するために、本発明のパターン識別装置は、トレーニングサンプルｘｔと学習ラベルｊｔからなるトレーニングデータＺを用いてスコア関数のパラメタベクトル集合Λを推定する。まず、ｍは基底ベクトルの番号を表し、ｊは学習ラベルの番号を表し、ｔはトレーニングデータの番号を表すとする。基底ベクトル集合記憶部には、基底ベクトルｙｍが記憶される。結合係数記憶部には、学習ラベルｊに対するパラメタベクトルλｊの結合係数βｊ，ｍが記憶される。トレーニングデータ記憶部には、トレーニングデータＺが記憶される。直交化行列記憶部には、正規直交化行列Ｑが記憶される。直交化勾配ベクトル算出部は、初期化手段と、ｒ算出手段と、ｒ＾算出手段と、直交化行列更新手段と、を有する。初期化手段は、基底ベクトルｙｍを用いて、正規直交化行列Ｑを生成する。ｒ算出手段は、トレーニングサンプルｘｔと基底ベクトルｙｍと結合係数βｊ，ｍから、結合係数ｄｊ，ｔと結合係数ｒｊ，ｍを算出する。ｒ＾算出手段は、トレーニングサンプルｘｔと基底ベクトルｙｍと結合係数ｒｊ，ｍと正規直交化行列Ｑから、結合係数ｒ＾ｊ，ｍを算出する。直交化行列更新手段は、基底ベクトルｙｍを用いて、正規直交化行列Ｑを更新する。結合係数決定部は、トレーニングサンプルｘｔと基底ベクトルｙｍから、結合係数βｊ，ｍを求める。新規基底ベクトル決定部は、トレーニングサンプルｘｔと勾配ベクトルの結合係数ｄｊ，ｔと直交化勾配ベクトルの結合係数ｒ＾ｊ，ｍから、直交化勾配ベクトルを基底ベクトルｙｍで近似することにより、新規基底ベクトルｙｅを求め、当該新規基底ベクトルｙｅを基底ベクトルｙｍに追加することにより、基底ベクトルｙｍを更新する。
【発明の効果】
【０００９】
本発明のパターン識別装置は、より少ない基底ベクトルで、より精密なパラメタを推定することが可能になるため、識別性能が向上する。また、冗長な基底ベクトル集合を得ることがなく基底ベクトル数を少なくすることが可能になるため、訓練処理と識別処理を高速化することができる。
【図面の簡単な説明】
【００１０】
【図１】従来のパターン識別装置の構成を示すブロック図。
【図２】従来のパターン識別装置の動作を示すフローチャート。
【図３】実施例１のパターン識別装置の識別処理に関する構成を示すブロック図。
【図４】実施例１のパターン識別装置の構成を示すブロック図。
【図５】実施例１のパターン識別装置の動作を示すフローチャート。
【図６】手書き数字認識（２値分類タスク）の実験結果。
【図７】手書き数字認識（マルチクラス分類タスク）の実験結果。
【図８】トレーニングサンプル数を変化させた際の訓練時間の実験結果。
【図９】連続音素認識の実験結果。
【発明を実施するための形態】
【００１１】
＜カーネル法に基づく識別装置の説明＞
まず、カーネル法に基づく識別装置について説明する。パターン識別装置では、一般に、ある入力サンプルｘに内在する概念のラベルｊを、スコア関数ｆ（ｘ，ｊ）を最大にするラベル変数ｊを用いて、以下のように推定する。
【００１２】
【数１】
0005486569.tif 000002
【００１３】
パターン識別装置の訓練処理とは、トレーニングサンプルｘｔと学習ラベルｊｔをＴ個集めたトレーニングデータＺ＝｛（ｘ１，ｊ１），…，（ｘｔ，ｊｔ），…，（ｘＴ，ｊＴ）｝を用いて、スコア関数ｆを推定することである。以降の説明では、トレーニングサンプルｘｔがＤ次元実ベクトルで表されることと、Ｊ通りのラベルが１からＪの自然数であらわされることを仮定する（ｘ∈ＲＤ，ｊ∈｛１，…，Ｊ｝）。最も単純なスコア関数ｆのデザインとして、式（２）のような、ラベルｊに対するパラメタベクトルλｊでパラメトライズした線形関数に基づくものがある。
【００１４】
【数２】
0005486569.tif 000003
【００１５】
このようなスコア関数ｆでは、スコアが入力サンプルｘの線形関数で表現できることが仮定されているため、表現力が不足しており、多くの問題で十分な精度を得ることができない。
【００１６】
カーネル法に基づく識別装置では、非線形のスコア関数を実現するため、入力サンプルｘを、特徴抽出関数φ（ｘ）∈ＲＤ’を用いて、非線形処理を施した超高次元に写像する。一例としては、式（３）のような多項式写像が用いられる。
【００１７】
【数３】
0005486569.tif 000004
【００１８】
ここで、ｖｅｃＡは集合Ａの全要素を列挙して作成したベクトルを表し、ｘｄはＤ次元ベクトルで表現されている入力サンプルｘのｄ次元目の要素を表す。
【００１９】
この写像を用いた場合、写像先の空間ＲＤ’の次元数はＤ’＝（Ｄ＋１）（Ｄ＋２）／２である。カーネル法では、このようにして抽出された特徴ベクトルの空間で、式（４）のような線形のスコア関数ｆを構築する。
【００２０】
【数４】
0005486569.tif 000005
【００２１】
このようにして得たスコア関数ｆは、変数ｘｔ，ｄに対する二次式となる。この例のように、予め入力サンプルを高次元空間に非線形写像しておくことによって、高度なスコア関数を単純に表現することができる。
【００２２】
カーネル法に基づくパターン識別装置では、パラメタベクトルの表現として、リプリゼンタ定理によって導出される、トレーニングサンプルの特徴の線形結合による表現を利用する。リプリゼンタ定理は、先述したようなパラメタベクトルλｊを一般的なアルゴリズムで推定した場合、得られるパラメタベクトルλｊは必ずトレーニングサンプルｘｔに対応する特徴ベクトルφ（ｘｔ）の線形結合で表現されるということを示す（詳しくは「B. Scholkopf and A.J. Smola. Learning with kernels. The MIT Press, 2002.」参照）。
【００２３】
【数５】
0005486569.tif 000006
【００２４】
ここでαｊ，ｔはラベルｊとｔ番目のトレーニングサンプルに対応する結合係数である。
【００２５】
例えば、式（４）のような線形関数に基づくスコア関数ｆの場合、リプリゼンタ定理に基づく表現を導入することで、式（６）のように変形することができる。
【００２６】
【数６】
0005486569.tif 000007
【００２７】
さらに、特徴抽出後の空間における内積を示すカーネル関数Ｋ（ｘ，ｘｔ）＝φ（ｘ）Τφ（ｘｔ）を導入すると、式（７）のように変形することができる。
【００２８】
【数７】
0005486569.tif 000008
【００２９】
リプリゼンタ定理とカーネル関数を用いる利点は、カーネル関数Ｋさえ高速に計算可能であれば、超高次元の特徴抽出関数φを直接計算しなくても同様の処理が実行できる点にある。式（３）のような二次の多項式特徴では、明示的に特徴抽出をして内積計算を行う場合、Ｄ’（＝（Ｄ＋２）（Ｄ＋１）／２）次元の内積計算が必要になるが、二次多項式特徴の内積関数に対して成り立つ恒等式を利用すれば、式（７’）のようにＤ次元の内積計算を行った後、それに１を加えて二乗するだけで計算することが可能である。
【００３０】
【数８】
0005486569.tif 000009
【００３１】
同様に、従来の方法では計算が非常に困難であった三次元以上の多項式特徴を用いる場合や、計算が原理上不可能であった関数空間（無限次元ヒルベルト空間）に特徴を写像する場合も同じ計算量で扱うことが可能である。
【００３２】
＜カーネル法に基づく識別装置の問題点＞
カーネル法に基づく識別装置では、特徴抽出関数φの直接計算を避けるため、パラメタベクトルλｊの全要素を推定する代わりに、式(５)の形で表現する結合係数αｊ，ｔを推定する。結合係数αｊ，ｔはトレーニングデータ数に比例する個数だけ存在するため、全てのトレーニングサンプルに対応する結合係数を求めるためには、少なくともトレーニングサンプル数の二乗に比例する計算量が必要であることが知られている。このような制限から、カーネル法を大規模なトレーニングデータを用いた問題に適用することは困難であった。
【００３３】
＜従来のＫＧＭＰ法の説明＞
次に、図１、図２を参照して、従来のＫＧＭＰ法によるパターン識別装置１０の動作を詳細に説明する。図１は従来のパターン識別装置１０の構成を示すブロック図である。図２は従来のパターン識別装置１０の動作を示すフローチャートである。
【００３４】
従来のＫＧＭＰ法では、パラメタベクトルの表現として、リプリゼンタ定理によって導出されるトレーニングサンプルの特徴の線形結合による表現ではなく、Ｍ個の入力サンプルと同じ空間ＲＤにある任意の点の特徴の線形結合を利用することを考える。そのため、従来のＫＧＭＰ法では、パラメタベクトルλｊを式（８）のように表現する。
【００３５】
【数９】
0005486569.tif 000010
【００３６】
リプリゼンタ定理の場合と異なり、式（８）の表現は厳密な等式ではなく近似となっている。しかし、Ｍを十分に大きく取り、適切なｙｍを選択できた場合は、厳密解と一致する。例えば、Ｍ＝Ｔと置き、ｙｍ＝ｘｔ（１≦ｍ＝ｔ≦Ｍ）と設定した場合、リプリゼンタ定理でαｊ，ｔで示されるところをβｊ，ｍで置き換えることによって等価な表現を得ることができる。このような表現を用いた場合、パラメタベクトルλｊの推定問題は、結合重み係数βｊ，ｍと基底ベクトルｙｍの推定問題に置き換えて考えることができる。さらに、識別処理に用いる式（４）（７）のスコア関数ｆ（ｘ，ｊ）も結合重み係数βｊ，ｍと基底ベクトルｙｍを用いて式（９）のように変形できる。
【００３７】
【数１０】
0005486569.tif 000011
【００３８】
最適なパラメタベクトル集合Λ＝｛λ１，…，λｊ，…｝の推定は、一般的にトレーニングデータＺを用いて目的関数ｇ（Λ；Ｚ）を最大化するパラメタベクトル集合Λを見つけることで行われる。
【００３９】
【数１１】
0005486569.tif 000012
【００４０】
目的関数ｇの具体例としては、式（１１）のＳＶＭ型や、式（１２）のｌｏｇ−ｌｉｎｅａｒ型等がある。
【００４１】
【数１２】
0005486569.tif 000013
【００４２】
ここでｃは正則化定数と呼ばれるチューニングパラメタである。
【００４３】
従来のＫＧＭＰ法では、式（１３）のように、目的関数の勾配ベクトル（以下、単に「勾配ベクトル」と呼ぶ）が各トレーニングサンプルの線形結合とパラメタベクトル自身の線形結合で書けるものと仮定する。
【００４４】
【数１３】
0005486569.tif 000014
【００４５】
ここで、トレーニングサンプル重み関数ｄｊ，ｔ(Λ)および正則化重み関数ｒｊ，ｍ(Λ)は実際にどの目的関数を選ぶかによって変わってくるスカラ関数である。
【００４６】
上記二種類の目的関数を含めて、多くのパラメタ推定アルゴリズムにおける目的関数はこの仮定を満たす。例えば、目的関数として式（１２）のｌｏｇ−ｌｉｎｅａｒ型を選んだ場合、その勾配ベクトルは、トレーニングサンプル重み関数ｄｊ，ｔ(Λ)と正則化重み関数ｒｊ，ｍ(Λ)を式（１４）のように設定したときの式（１３）に等しい。
【００４７】
【数１４】
0005486569.tif 000015
【００４８】
同様の推論を、パラメタベクトル集合Λを直接扱う場合ではなく、式（８）に基づく表現の上で行うことを考える。一例として式（１２）のｌｏｇ−ｌｉｎｅａｒ型の目的関数を挙げると、式（８）を式（１２）に代入することにより、式（１５）のような結合係数βｊ，ｍに関する目的関数が得られる。
【００４９】
【数１５】
0005486569.tif 000016
【００５０】
ここでΒは全てのβｊ，ｍを含む集合｛βｊ，ｍ｜∀ｊ，∀ｍ｝である。
【００５１】
基底ベクトルが固定された上で、最適なΒは式（１６）のような最適化を解くことによって得られる。
【００５２】
【数１６】
0005486569.tif 000017
【００５３】
この結合係数βｊ，ｍに関する最適化は、例えば最急勾配法やその変形等のような様々なアルゴリズムで実行することができる。
【００５４】
従来のＫＧＭＰ法では、適切な基底ベクトルの持つべき性質として勾配ベクトルに近いという性質を取りあげる。目的関数のパラメタベクトル集合Λにおける勾配ベクトル∇λｊ（Λ）は、パラメタベクトルλｊを微小に動かした時に、最も目的関数を大きくすることのできる方向を示すベクトルであり、勾配ベクトルが基底ベクトルで表現できない場合、結合係数βｊ，ｍの最適化のみではそれ以上目的関数の値を向上させることはできない。反面、与えられた基底ベクトルで結合係数βｊ，ｍの最適化が終わってしまっても、勾配ベクトルに近いベクトルを新たな基底ベクトルとして加えることができれば、さらに目的関数の値を向上させることができる。ただし、勾配ベクトルそのものを基底ベクトルとして利用するのは、式（１３）にあるように、勾配ベクトルそのものの表現に全てのトレーニングサンプルを用いる必要があるため、効率が悪い。そこで勾配ベクトルを、Ｒ個の基底ベクトルで近似することを試み、以下の二乗誤差関数を考える。
【００５５】
【数１７】
0005486569.tif 000018
【００５６】
勾配ベクトルの近似に用いるＲ個の基底ベクトルは式（１８）のような二乗誤差最小化の最適化で得ることができる。
【００５７】
【数１８】
0005486569.tif 000019
【００５８】
この新規基底ベクトルの最適化は、結合係数βｊ，ｍの最適化と同様、線形時間で実行可能である。
【００５９】
以下、実際に行われる手続きの順に説明してゆく。従来のＫＧＭＰ法によるパターン識別装置１０は、勾配ベクトル算出部１００、結合係数決定部２００、新規基底ベクトル決定部３００、基底ベクトル集合記憶部９００、結合係数記憶部９１０、トレーニングデータ記憶部９２０を備える。勾配ベクトル算出部１００は、初期化手段１１０、ｒ算出手段１２０を有する。
【００６０】
基底ベクトル集合記憶部９００は、Ｍ個の基底ベクトルｙｍを記憶する。結合係数記憶部９１０は、全ての結合係数βｊ，ｍを記憶する。トレーニングデータ記憶部９２０は、トレーニングサンプルｘｔと学習ラベルｊｔをＴ個集めたトレーニングデータＺを記憶する。
【００６１】
勾配ベクトル算出部１００は、初期化手段１１０により、基底ベクトル集合記憶部９００からＭ個の基底ベクトルｙｍを読み出す（Ｓ１１０）。
【００６２】
結合係数決定部２００は、トレーニングデータＺとＭ個の基底ベクトルｙｍを用いて、結合係数βｊ，ｍの最適化を行う（Ｓ２００）。
【００６３】
勾配ベクトル算出部１００は、ｒ算出手段１２０により、結合係数βｊ，ｍを用いて、トレーニングサンプル重み関数ｄｊ，ｔ(Λ)および正則化重み関数ｒｊ，ｍ(Λ)を計算し、勾配ベクトルの結合係数ｄｊ，ｔと結合係数ｒｊ，ｍの算出を行う（Ｓ１２０）。
【００６４】
新規基底ベクトル決定部３００は、最小二乗誤差基準を用いて、勾配ベクトルをＲ個の基底ベクトルで近似することで、Ｒ個の新規基底ベクトルｙｅを求める（Ｓ３０１）。続いて、既存の基底ベクトルｙｍに新規基底ベクトルｙｅを追加する（Ｓ３０２）。
【００６５】
そして、収束が得られた場合には処理を終了し、収束が得られない場合にはＳ２００〜Ｓ３０２を繰り返し実行する（Ｓ９９１）。
【００６６】
＜従来のＫＧＭＰ法の問題点＞
従来のＫＧＭＰ法は、内部で用いられているアルゴリズムが全て線形時間で実行可能であることから、全体として線形時間で実行可能である。
【００６７】
ただし、新規基底ベクトルｙｅの最適化に用いる式（１８）は、複雑な最適化問題であり局所解を多く含む。経験的に、この最適化は多くの場合で、冗長な基底ベクトル集合を得てしまうことがわかっており、勾配ベクトル近似の精度の観点から効率が悪かった。
【００６８】
＜本発明の概要＞
本発明は、従来のＫＧＭＰ法をベースにして、より高度な新規基底ベクトル追加アルゴリズムを導入したものである。本発明では、従来のＫＧＭＰ法で新規基底ベクトルｙｅを最適化する際に用いる勾配ベクトルを、基底ベクトルと直交になるように修正した直交化勾配ベクトルに置き換える。これによって、チューニングパラメタを追加することなく、基底ベクトルの直交性を保つようなアルゴリズムを実現しており、一つの勾配ベクトルから複数の基底ベクトルを取得するような場合においても、相互になるべく直交した基底ベクトル集合を得ることができる。
【００６９】
なお、本発明は、パターン識別装置の訓練処理の改良であるため、基底ベクトル集合が得られた後の識別処理に係る部分の構成は、従来例と差異はない。図３に本発明のパターン識別装置の内、識別処理に係る部分の構成を示す。
【実施例１】
【００７０】
次に、図４、図５を参照して、本発明の実施例１に係るパターン識別装置２０の動作を詳細に説明する。図４は本発明の実施例１に係るパターン識別装置２０の構成を示すブロック図である。図５は本発明の実施例１に係るパターン識別装置２０の動作を示すフローチャートである。
【００７１】
本発明では、新規基底ベクトル探索に着目するため、既にＭ個の基底ベクトルｙｍと、対応する結合係数βｊ，ｍが得られていることを前提とする。
【００７２】
本発明で導入する「直交化勾配ベクトル」は、既存の基底ベクトルでは表現できない要素のみによって構成された勾配ベクトルである。直交化勾配ベクトルは、従来例で用いられてきた、式（１３）で表される勾配ベクトルから既存の基底ベクトルと同じ方向に対応する要素を減算していくことによって得られる。
【００７３】
【数１９】
0005486569.tif 000020
【００７４】
式（１９）のように、直交化勾配ベクトルを導入しても、式（１３）で表される従来例の勾配ベクトルと同様の形を保っており、修正項ηｊ，ｍさえ求めることができれば、従来例のアルゴリズムで結合係数ｒｊ，ｍを用いていた部分をｒ＾ｊ，ｍ（Λ）＝ｒｊ，ｍ（Λ）＋ηｊ，ｍに置き換えるだけで、直交化勾配ベクトルを再現する基底ベクトルの追加を行うことができる。すなわち、本発明が従来例と異なる部分は、新規基底ベクトル決定部が、従来例の勾配ベクトルから直交化勾配ベクトルに変換する際に用いる修正項ηｊ，ｍを算出する手段を含んでいる点である。
【００７５】
以下、実際に行われる手続きの順に説明してゆく。本実施例のパターン識別装置２０は、直交化勾配ベクトル算出部１５０、結合係数決定部２００、新規基底ベクトル決定部３５０、基底ベクトル集合記憶部９００、結合係数記憶部９１０、トレーニングデータ記憶部９２０、直交化行列記憶部９３０を備える。直交化勾配ベクトル算出部１５０は、初期化手段１６０、ｒ算出手段１７０、ｒ＾算出手段１８０、直交化行列更新手段１９０を備える。
【００７６】
基底ベクトル集合記憶部９００は、Ｍ個の基底ベクトルｙｍを記憶する。結合係数記憶部９１０は、全ての結合係数βｊ，ｍを記憶する。トレーニングデータ記憶部９２０は、トレーニングサンプルｘｔと学習ラベルｊｔをＴ個集めたトレーニングデータＺを記憶する。直交化行列記憶部９３０は、正規直交化行列Ｑを記憶する。
【００７７】
直交化勾配ベクトル算出部１５０は、初期化手段１６０により、基底ベクトル集合記憶部９００からＭ個の基底ベクトルｙｍを読み出す（Ｓ１６１）。次に、基底ベクトルｙｍから、正規直交化行列Ｑを生成し、当該正規直交化行列Ｑを直交化行列記憶部に記憶する（Ｓ１６２）。
【００７８】
正規直交化行列Ｑの生成について詳細に説明する。簡単のため、φ（ｙｍ）をｍ行目に持つ行列Φを導入する。また、各基底ベクトルｙｍ間の相関関係を除去する効果を持つ性質を持つ行列Ｑを正規直交化行列と呼ぶ。正規直交化行列Ｑは、式（２０）を満たす行列として定義する。
【００７９】
【数２０】
0005486569.tif 000021
【００８０】
ここで、Ｉは単位行列である。
【００８１】
式（２０）は、式（２１）の基底ベクトルｂｉ（ｉ∈｛１，…，Ｍ｝）が互いに正規直交、すなわち、ｉ＝ｊの時のみｂｉΤｂｊ＝１であり、ｉ≠ｊの時はｂｉΤｂｊ＝０であることを意味している。
【００８２】
【数２１】
0005486569.tif 000022
【００８３】
ここで、ｑｉ，ｍは正規直交化行列Ｑのｉ行目ｍ列目の要素である。
【００８４】
正規直交化行列Ｑは、式（２２）のように、各行毎に計算することで算出可能である。
【００８５】
【数２２】
0005486569.tif 000023
【００８６】
ここで、ｑｉは正規直交化行列Ｑのｉ番目の行に対応するベクトルを表しており、ｅｉは、ｉ番目の要素だけが１で、他の要素が０のベクトルである。また、グラム行列Ｇは、式（２３）のように算出される。
【００８７】
【数２３】
0005486569.tif 000024
【００８８】
グラム行列Ｇおよび正規直交化行列Ｑは、新しい基底ベクトルが追加されるたびに、追加された基底ベクトルに対応する部分だけ再計算を行うことができる。
【００８９】
次に、結合係数決定部２００は、トレーニングデータＺとＭ個の基底ベクトルｙｍを用いて、結合係数βｊ，ｍの最適化を行う（Ｓ２００）。
【００９０】
直交化勾配ベクトル算出部１５０は、ｒ算出手段１７０により、結合係数βｊ，ｍを用いて、トレーニングサンプル重み関数ｄｊ，ｔ(Λ)および正則化重み関数ｒｊ，ｍ(Λ)を計算し、勾配ベクトルの結合係数ｄｊ，ｔと結合係数ｒｊ，ｍの算出を行う（Ｓ１７０）。結合係数ｄｊ，ｔと結合係数ｒｊ，ｍは、結合係数βｊ，ｍと基底ベクトルｙｍが定まっていれば、一意に定まり計算可能である。例えば、式（１２）のＬｏｇ−Ｌｉｎｅａｒ型目的関数を用いる場合は、式（１４）を計算することで求めることができる。
【００９１】
次に、直交化勾配ベクトル算出部１５０は、ｒ＾算出手段１８０により、基底ベクトルｙｍと結合係数ｒｊ，ｍから、勾配ベクトルへの射影ｋｊ，ｍを算出する（Ｓ１８１）。既存の基底ベクトルφ（ｙｍ）の射影ｋｊ，ｍは、式（２４）のようにトレーニングデータｘｔと基底ベクトルｙｍとカーネル関数Ｋを用いて算出可能である。
【００９２】
【数２４】
0005486569.tif 000025
【００９３】
この値は、線形時間で計算可能である。また、多くの場合、別の計算ステップ（例えば、結合係数βｊ，ｍの最適化）の副産物として得られているため、それを利用することもできる。
【００９４】
続いて、直交化勾配ベクトル算出部１５０は、ｒ＾算出手段１８０により、正規直交化行列Ｑと射影ｋｊ，ｍから、式（２５）のように、修正項ηｊ，ｍを算出する（Ｓ１８２）。
【００９５】
【数２５】
0005486569.tif 000026
【００９６】
さらに、直交化勾配ベクトル算出部１５０は、ｒ＾算出手段１８０により、結合係数ｒｊ，ｍと修正項ηｊ，ｍから、式（２６）のように、結合係数ｒ＾ｊ，ｍを算出する（Ｓ１８３）。
【００９７】
【数２６】
0005486569.tif 000027
【００９８】
新規基底ベクトル決定部３５０は、最小二乗誤差基準を用いて、直交化勾配ベクトルを基底ベクトルで近似し、式（１８）を用いて、新規基底ベクトルｙｅを求める（Ｓ３５１）。続いて、既存の基底ベクトルｙｍに新規基底ベクトルｙｅを追加する（Ｓ３５２）。
【００９９】
Ｓ２８１〜Ｓ２９０をＲ回繰り返し実行することで、Ｒ個の新規基底ベクトルｙｅを既存の基底ベクトルｙｍに追加する（Ｓ９９２−９９４）。
【０１００】
そして、収束が得られた場合には処理を終了し、収束が得られない場合にはＳ２００〜Ｓ２９０を繰り返し実行する（Ｓ９９５）。
【０１０１】
このように、本実施例のパターン識別装置２０は、基底ベクトルと直交になるように修正した直交化勾配ベクトルを用いることで、従来のＫＧＭＰ法では一つの勾配ベクトルから複数の新規基底ベクトルを算出する際に冗長な基底ベクトル集合が得られてしまうという問題を解決した。そのため、より少ない基底ベクトルで、より精密なパラメタを推定することが可能になり、識別性能が向上している。また、冗長な基底ベクトル集合を得ることがなく基底ベクトル数を少なくすることが可能になり、訓練処理と識別処理を高速化することができる。
【０１０２】
＜実験結果＞
本発明の有効性を確認するために、手書き数字認識実験および連続音素認識実験を行った。また、トレーニングサンプル数を変化させた際の訓練時間の推移を計測した。
【０１０３】
手書き数字認識実験では、ＭＮＩＳＴ手書き数字データセットを用いて、０〜４の数字と、５〜９の数字に分ける２値分類タスクと、それぞれの数字に分けるマルチクラス分類タスクを行った。どちらのタスクでもトレーニングサンプルとして規定されている６０，０００サンプルのうち、最初の５０，０００サンプルをトレーニングに用い、残りの１０，０００サンプルをハイパーパラメタや最適化の繰り返し回数のチューニングに用いた。トレーニングサンプルの表現としては画像の各画素の濃度値を０から１の実数であらわしたものを用いた（２８×２８＝７８４次元）。
【０１０４】
図６は手書き数字認識実験における２値分類タスクの識別エラー率である。図７は手書き数字認識実験におけるマルチクラス分類タスクの識別エラー率である。いずれのタスクでも本発明のパターン識別装置が最も識別エラー率が低いことが示された。
【０１０５】
図８に、トレーニングサンプル数を変化させた際の訓練時間の平均を示す。試行回数は５回である。“Ｎａｉｖｅ”は、Ｋｅｒｎｅｌ−ｌｏｇ−ｌｉｎｅａｒモデルを単純なカーネル法で認識した場合である。“Ｏｒｔｈｏｇｏｎａｌ  ＫＧＭＰ”は、本発明である。単純なカーネル法では、トレーニングサンプル数の二乗に比例するように計算時間がかかっているが、本発明では、ほぼトレーニングサンプル数に比例する形で訓練時間が増えていっていることがわかる。この特性は従来のＫＧＭＰ法でも同一であるが、図６，７と併せると、本発明では従来例と比較して同程度の訓練時間でより高精度の識別性能を発揮することが読み取れる。
【０１０６】
連続音素認識実験では、ＴＩＭＩＴコーパスを用いた。ＴＩＭＩＴコーパスのうち、コアテストセットとして規定されている１９２発話（５７，９１９フレーム）を評価に、トレーニングセットとして規定されている３，６０６発話（１，１２４，８２３フレーム）を訓練に、バリデーションセットとして規定されている１，１１４発話（３５０，３４３フレーム）をハイパーパラメタと繰り返し回数の手動チューニングに利用した。
【０１０７】
“従来法（ＨＭＭ）”は、従来一般的に用いられてきた音素認識装置である（詳細は「S. Kapadia, V. Valtchev, and S.J. Young. MMI training for continuous phoneme recognition on the TIMIT database. In Proc. International Conference on Acoustics, Speech and Signal Processing, volume 2, pages 491{494, Orlando, FL, USA, 2002.」参照）。“従来法（ｌｏｇ−ｌｉｎｅａｒ）”は、本発明で用いる枠組みと同じ枠組みを、本発明の手段を用いずに利用した場合である。
【０１０８】
表３に連続音素認識実験における音素エラー率を示す。本発明は音声認識においても有効であることが示された。
【０１０９】
＜プログラム、記録媒体＞
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１１０】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１１１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１１２】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１１３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１１４】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【０１１５】
本発明は、手書き文字の認識装置や音声パターンの認識装置の適切なパラメタを推定するために利用することができる。
【符号の説明】
【０１１６】
１０、２０  パターン識別装置
１００  勾配ベクトル算出部              １５０  直交化勾配ベクトル算出部
１１０、１６０  初期化手段              １２０、１７０  ｒ算出手段
１８０  ｒ＾算出手段                    １９０  直交化行列更新手段
２００  結合係数決定部                  ３００、３５０  新規基底ベクトル決定部
８０１〜８０Ｎ  スコア計算部
９００  基底ベクトル集合記憶部          ９１０  結合係数記憶部
９２０  トレーニングデータ記憶部        ９３０  直交化行列記憶部
【図１】
0005486569.tif 000040
【図２】
0005486569.tif 000041
【図３】
0005486569.tif 000042
【図４】
0005486569.tif 000043
【図５】
0005486569.tif 000044
【図６】
0005486569.tif 000045
【図７】
0005486569.tif 000046
【図９】
0005486569.tif 000047
【図８】
0005486569.tif 000048