(57)【要約】【課題】高次元特徴空間での識別処理による識別率の低下、計算量の増大、使用メモリの増大を解決するために、高精度、高速、省メモリを目的とした効率的な特徴空間の次元削減を行う。【解決手段】辞書生成用特徴パターン群を用いて、多項式ニューラルネットワークにより二次関数を学習し、二次関数の主要成分を保存する部分空間を選択することにより、特徴空間の次元を削減する。初期係数設定ステップ４２、係数修正ステップ４３では、二次関数を識別関数として用いた場合の損失関数の値が小さくなるように、勾配降下法又は確率的勾配降下法により係数を修正する。基底ベクトル導出ステップ４４は、二次関数の二次の項の二次形式の行列の固有ベクトルと、一次の項の係数ベクトルを導出する。次に、射影行列導出ステップ４５は、固有ベクトルと係数ベクトルとの中から主成分となる１つ以上のベクトルを選択し、選択されたベクトルによって生成される部分空間を新たな特徴空間として生成する。【選択図】図４
2010039778.tif 000002
【特許請求の範囲】
【請求項１】
特徴空間上の辞書生成用特徴パターン群を入力する特徴パターン群入力ステップと、
ｃ個（ｃは自然数）のカテゴリの各々に対応する前記特徴空間上の二次関数の係数の値を設定する初期係数設定ステップと、
前記二次関数を識別関数として前記辞書生成用特徴パターン群の各々の所属カテゴリを判定したときの誤識別による損失を表す損失関数の値が小さくなるように、前記二次関数の係数を勾配降下法、又は確率的勾配降下法により修正する係数修正ステップと、
前記ｃ個のカテゴリの各々について、前記二次関数の二次の項の二次形式の対称行列の固有ベクトルと、前記二次関数の一次の項の係数ベクトルとの中から一つ以上のベクトルを選択する基底ベクトル導出ステップと、
前記ｃ個のカテゴリの各々について、前記基底ベクトル導出ステップにおいて選択されたベクトルによって張られる辞書部分空間への射影行列を生成する射影行列導出ステップと、
前記ｃ個のカテゴリの各々に対応するｃ個の前記辞書部分空間への前記射影行列、又は、前記ｃ個のカテゴリの各々に対応する前記射影行列と前記二次関数の係数とを出力する射影行列出力ステップと、
を有することを特徴とする特徴空間の次元削減方法。
【請求項２】
請求項１記載の特徴空間の次元削減方法において、前記特徴空間はベクトル空間であり、前記辞書生成用特徴パターン群は、前記ベクトル空間上の所属カテゴリを示すラベル付きベクトル値の集合であることを特徴とする特徴空間の次元削減方法。
【請求項３】
請求項１記載の特徴空間の次元削減方法において、前記初期係数設定ステップでは、前記ｃ個のカテゴリの各々に対応する前記二次関数の係数に乱数により生成した値を設定することを特徴とする特徴空間の次元削減方法。
【請求項４】
請求項１記載の特徴空間の次元削減方法において、前記係数修正ステップでは、前記二次関数を識別関数として前記辞書生成用特徴パターン群の各々の所属カテゴリを判定したときの二乗誤差関数を損失関数とすることを特徴とする特徴空間の次元削減方法。
【請求項５】
請求項１記載の特徴空間の次元削減方法において、前記射影行列導出ステップでは、前記係数ベクトルと前記対称行列の固有値の絶対値が大きい上位n個に対応する前記固有ベクトル、又は、前記係数ベクトルと前記対称行列の固有値の絶対値が閾値ｈよりも大きい上位ｎ個に対応する前記固有ベクトルとによって生成される特徴空間の部分空間への射影行列を生成することを特徴とする特徴空間の次元削減方法。
【請求項６】
請求項１記載の特徴空間の次元削減方法において、前記射影行列導出ステップでは、前記対称行列の固有値の絶対値が大きい上位ｎ個に対応する前記固有ベクトル、又は、前記対称行列の固有値の絶対値が閾値ｈよりも大きい上位ｎ個に対応する前記固有ベクトルによって生成される特徴空間の部分空間への射影行列を生成することを特徴とする特徴空間の次元削減方法。
【請求項７】
辞書生成用パターン群を入力する入力部と、
前記辞書生成用パターン群からｃ個（ｃは自然数）のカテゴリの各々に対応する特徴空間上の辞書生成用特徴パターン群を抽出する特徴抽出部と、
前記特徴空間上の前記辞書生成用特徴パターン群を入力する特徴パターン群入力処理、ｃ個のカテゴリの各々に対応する前記特徴空間上の二次関数の係数の値を設定する初期係数設定処理、前記二次関数を識別関数として前記辞書生成用特徴パターン群の各々の所属カテゴリを判定したときの誤識別による損失を表す損失関数の値が小さくなるように、前記二次関数の係数を勾配降下法、又は確率的勾配降下法により修正する係数修正処理、前記ｃ個のカテゴリの各々について、前記二次関数の二次の項の二次形式の対称行列の固有ベクトルと、前記二次関数の一次の項の係数ベクトルとの中から一つ以上のベクトルを選択する基底ベクトル導出処理、前記ｃ個のカテゴリの各々について、前記基底ベクトル導出処理において選択されたベクトルによって張られる辞書部分空間への射影行列を生成する射影行列導出処理、前記ｃ個のカテゴリの各々に対応するｃ個の前記辞書部分空間への前記射影行列、又は、前記ｃ個のカテゴリの各々に対応する前記射影行列と前記二次関数の係数とを出力する射影行列出力処理、を含む特徴空間の次元削減処理により辞書部分空間への前記射影行列を生成する辞書部分空間生成部と、
前記射影行列により前記辞書生成用特徴パターン群を前記辞書部分空間に射影した学習用特徴パターン群を生成する学習用特徴パターン群生成部と、
前記学習用特徴パターン群を用いて前記ｃ個のカテゴリを識別する識別関数を生成する識別関数生成部と、
前記射影行列と前記識別関数のパラメータとを出力する出力部と、
を有するパターン認識用辞書生成装置。
【請求項８】
請求項７記載のパターン認識用辞書生成装置において、前記識別関数生成部は、前記ｃ個のカテゴリの各々について、前記二次関数を前記辞書部分空間に制限した制限二次関数を生成し、前記制限二次関数を識別関数として前記学習用特徴パターン群の各々の所属カテゴリを判定したときの二乗誤差関数を損失関数として、前記二乗誤差の値が小さくなるように、勾配降下法、又は、確率的勾配降下法により前記制限二次関数の係数を修正したものを識別関数として生成することを特徴とするパターン認識用辞書生成装置。
【請求項９】
請求項７記載のパターン認識用辞書生成装置において、前記識別関数生成部は、前記ｃ個のカテゴリの各々について、前記二次関数を前記辞書部分空間に制限したものを識別関数として生成することを特徴とするパターン認識用辞書生成装置。
【請求項１０】
請求項７記載のパターン認識用辞書生成装置において、前記特徴空間はベクトル空間であり、前記辞書生成用特徴パターン群は、前記ベクトル空間上の所属カテゴリを示すラベル付きベクトル値の集合であることを特徴とするパターン認識用辞書生成装置。
【請求項１１】
請求項７記載のパターン認識用辞書生成装置において、前記初期係数設定処理は、前記ｃ個のカテゴリの各々に対応する前記二次関数の係数に乱数により生成した値を設定することを特徴とするパターン認識用辞書生成装置。
【請求項１２】
請求項７記載のパターン認識用辞書生成装置において、前記係数修正処理は、前記二次関数を識別関数として前記辞書生成用特徴パターン群の各々の所属カテゴリを判定したときの二乗誤差関数を損失関数とすることを特徴とするパターン認識用辞書生成装置。
【請求項１３】
請求項７記載のパターン認識用辞書生成装置において、前記射影行列導出処理は、前記係数ベクトルと前記対称行列の固有値の絶対値が大きい上位ｎ個に対応する前記固有ベクトル、又は、前記係数ベクトルと前記対称行列の固有値の絶対値が閾値ｈよりも大きい上位ｎ個に対応する前記固有ベクトルとによって生成される特徴空間の部分空間への射影行列を生成することを特徴とするパターン認識用辞書生成装置。
【請求項１４】
請求項７記載のパターン認識用辞書生成装置において、前記射影行列導出処理は、前記対称行列の固有値の絶対値が大きい上位ｎ個に対応する前記固有ベクトル、又は、前記対称行列の固有値の絶対値が閾値ｈよりも大きい上位ｎ個に対応する前記固有ベクトルによって生成される特徴空間の部分空間への射影行列を生成することを特徴とするパターン認識用辞書生成装置。
【請求項１５】
特徴空間上の辞書生成用特徴パターン群を入力する特徴パターン群入力処理、ｃ個（ｃは自然数）のカテゴリの各々に対応する前記特徴空間上の二次関数の係数の値を設定する初期係数設定処理、前記二次関数を識別関数として前記辞書生成用特徴パターン群の各々の所属カテゴリを判定したときの誤識別による損失を表す損失関数の値が小さくなるように、前記二次関数の係数を勾配降下法、又は確率的勾配降下法により修正する係数修正処理、前記ｃ個のカテゴリの各々について、前記二次関数の二次の項の二次形式の対称行列の固有ベクトルと、前記二次関数の一次の項の係数ベクトルとの中から一つ以上のベクトルを選択する基底ベクトル導出処理、前記ｃ個のカテゴリの各々について、前記基底ベクトル導出処理において選択されたベクトルによって張られる辞書部分空間への射影行列を生成する射影行列導出処理、前記ｃ個のカテゴリの各々に対応するｃ個の前記辞書部分空間への前記射影行列、又は、前記ｃ個のカテゴリの各々に対応する前記射影行列と前記二次関数の係数とを出力する射影行列出力処理、を含む特徴空間の次元削減処理により生成された前記辞書部分空間上の識別関数のパラメータと前記射影行列とを格納する認識用辞書格納部と、
認識対象の入力パターンを入力する入力部と、前記入力パターンから特徴空間上のベクトル値を抽出する特徴抽出部と、
前記ｃ個のカテゴリの各々について、前記射影行列により入力パターンを辞書部分空間に射影した射影ベクトルを生成する射影ベクトル生成部と、
前記ｃ個のカテゴリの各々について、前記識別関数の前記射影ベクトルが表す点での値を算出し、それに基づいて入力パターンが属するカテゴリを識別する識別部と、
前記識別部での識別結果を出力する出力部と、
を有することを特徴とするパターン認識装置。
【請求項１６】
請求項１５記載のパターン認識装置において、前記特徴空間はベクトル空間であり、前記辞書生成用特徴パターン群は、前記ベクトル空間上の所属カテゴリを示すラベル付きベクトル値の集合であることを特徴とするパターン認識装置。
【請求項１７】
請求項１５記載のパターン認識装置において、前記初期係数設定処理は、前記ｃ個のカテゴリの各々に対応する前記二次関数の係数に乱数により生成した値を設定することを特徴とするパターン認識装置。
【請求項１８】
請求項１５記載のパターン認識装置において、前記係数修正処理は、前記二次関数を識別関数として前記辞書生成用特徴パターン群の各々の所属カテゴリを判定したときの二乗誤差関数を損失関数とすることを特徴とするパターン認識装置。
【請求項１９】
請求項１５記載のパターン認識装置において、前記射影行列導出処理は、前記係数ベクトルと前記対称行列の固有値の絶対値が大きい上位ｎ個に対応する前記固有ベクトル、又は、前記係数ベクトルと前記対称行列の固有値の絶対値が閾値ｈよりも大きい上位ｎ個に対応する前記固有ベクトルとによって生成される特徴空間の部分空間への射影行列を生成することを特徴とするパターン認識装置。
【請求項２０】
請求項１５記載のパターン認識装置において、前記射影行列導出処理は、前記対称行列の固有値の絶対値が大きい上位ｎ個に対応する前記固有ベクトル、又は、前記対称行列の固有値の絶対値が閾値ｈよりも大きい上位ｎ個に対応する前記固有ベクトルによって生成される特徴空間の部分空間への射影行列を生成することを特徴とするパターン認識装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特徴空間の次元削減方法、パターン認識用辞書生成装置、パターン認識装置に関する。
【背景技術】
【０００２】
パターン認識装置は、パターン認識用辞書の情報を用いて、入力パターンの属するカテゴリを識別することを目的とする。パターン認識用辞書は、予め、パターン認識用辞書生成装置により辞書生成用パターン群を用いて作成される。パターン認識用辞書は、入力パターンと各カテゴリとの類似度を計算するための情報を保持するものであり、具体的には、識別関数のパラメータと、入力パターンを識別関数が定義されるベクトル空間上のベクトル値に変換するための情報を保持している。
【０００３】
パターン認識装置は、パターン認識用辞書を保持し、それを用いて入力パターンの識別処理を行う。パターン認識装置は、前記パターン認識用辞書を用いて入力パターンと各カテゴリとの類似度を計算し、その計算結果に基づいてパターンの属するカテゴリを識別する。このようなパターン認識装置については、非特許文献１を参照。
【０００４】
以下、パターン認識用辞書生成装置による一般的な辞書生成手順について説明する。
パターン認識用辞書生成装置は、辞書生成用パターン群を用いて、パターン認識用辞書を作成する。まず、パターン認識用辞書生成装置は、特徴抽出により、辞書生成用パターン群をベクトル空間上のベクトル群である辞書生成用特徴パターン群に変換する。特徴抽出により抽出されるベクトルを特徴ベクトル、特徴ベクトルが属するベクトル空間を特徴空間とよぶ。特徴抽出手法としては、例えば、画素特徴、輪郭特徴、勾配特徴等が広く用いられている（非特許文献２）。
【０００５】
次に、パターン認識用辞書生成装置は識別処理における、高精度、高速、省メモリを目的として、特徴空間の次元削減（特徴選択）を行う場合が多い。次元削減では、特徴空間でのカテゴリの分布を近似する特徴空間の部分空間を選択する。部分空間の情報は、特徴空間から部分空間への射影行列として保存される。部分空間は、一般には、各カテゴリごとに異なるが、全カテゴリで共通の部分空間を選択する場合もある。したがって、部分空間の次元もカテゴリごとに異なる場合がある。以下、次元削減により生成した部分空間を改めて特徴空間、部分空間上のベクトルを改めて特徴ベクトルとよぶことにする。
【０００６】
次に、パターン認識用辞書生成装置は、辞書生成用特徴パターン群を特徴空間上の学習用特徴パターン群に射影する。
【０００７】
次に、パターン認識用辞書生成装置は、学習用特徴パターン群を用いて、特徴空間上でカテゴリを識別するための識別関数を学習により生成する。識別関数はカテゴリごとに存在し、特徴空間上の特徴ベクトルが示す点での値が、識別関数が対応するカテゴリと特徴ベクトルとの類似度となる。各カテゴリの識別関数は、誤識別による損失を表す損失関数が小さくなるように学習用特徴パターン群を用いた学習により作成する。識別関数の学習手法については、様々な方法があるが、例えば、非特許文献１〜４などが詳しい。
【０００８】
次に、パターン認識装置がパターン認識用辞書を用いて入力パターンを識別する手順について説明する。パターン認識装置は、入力パターンの各カテゴリに対する類似度を計算し、その結果に基づいてパターンが属するカテゴリを識別する。
【０００９】
パターン認識装置は、まず、パターン認識用辞書生成装置と同様に、特徴抽出により入力パターンをベクトル値に変換する。その後、パターン認識用辞書に保存されている射影行列を用いて、より低次元の特徴空間上の特徴ベクトルに変換する。次に、パターン認識用辞書に保存されている識別関数のパラメータを用いて、前記特徴ベクトルが表す点における識別関数の値を計算し、入力パターンの各カテゴリに対する類似度を求める。その計算結果に基づいて認識結果を出力する。
【００１０】
次に、パターン認識用辞書作成における次元削減（又は特徴選択）について説明する。次元削減によって得られる特徴空間は、各カテゴリに属するパターンの分布を良く近似し、カテゴリ同士を分離して識別に有利な元の特徴空間の部分空間として選択するのが良い。次元削減の手法は、主成分分析、線形判別法等の統計的手法が広く用いられる。主成分分析、線形判別法などの次元削減手法については、例えば、非特許文献２を参照。
【００１１】
主成分分析法による次元削減では、分散最大基準によって部分空間を選択するので、分析対象のパターン分布を良く近似することができる。具体的には、特徴空間における学習パターンの全部又は一部の共分散行列の固有値問題を解くことで、部分空間が得られる。次元削減後の特徴空間は、前記共分散行列の大きい固有値の上位p個に対応する固有ベクトルを基底とするp次元部分空間として得られる。全カテゴリに共通な部分空間を選択する場合には、学習パターン全部を分析対象する。カテゴリごとに異なる部分空間を選択する場合には、カテゴリごとに当該カテゴリに属する学習パターンのみを選択し、分析対象としても良い。
【００１２】
線形判別法は、他カテゴリとの識別を考慮した次元削減手法である。これは、カテゴリ内分散・カテゴリ間分散比を最大にする部分空間を選択する手法である。
【００１３】
【非特許文献１】パターン認識、石井健一郎・上田修功・前田英作・村瀬洋著、オーム社、１９９８.
【非特許文献２】Character Recognition Systems: A Guide for Students and Practitioners, Mohammed Cheriet, Nawwaf Kharma, Cheng-lin Liu and Ching Suen, Wiley-Interscience, 2007.
【非特許文献３】Pattern Classification: A Unified View of Statistical and Neural Approaches, J. Schurmann, Wiley-Interscience, 1996.
【非特許文献４】Class-specific feature polynomial classifier for pattern classification and its application to handwritten numeral recognition, Cheng-Lin Liu and Hiroshi Sako, Pattern Recogn., 2006.
【発明の開示】
【発明が解決しようとする課題】
【００１４】
従来の次元削減手法には、主成分分析、線形判別分析等の統計的手法が広く用いられている。しかしながら、以下のような課題がある。
【００１５】
主成分分析法は、分散最大基準によって部分空間を選択する手法である。したがって、選択された部分空間は、分析対象の分布の情報を良く保存する部分空間である。しかし、主成分分析法は、分析対象の統計的分布のみを用いて部分空間を選択している。そのため、選択された部分空間は必ずしも識別に有利なものであるとは限らない。したがって、他カテゴリとの識別のための次元削減が必要となる場合には、有効な手法であるとは限らない。
【００１６】
また、線形判別分析法は、ｃ個のカテゴリの分類問題の場合、最大ｃ−１個の判別軸しか選択することができない。したがって、識別に有効な判別軸を柔軟に選択することができないという問題がある。
【課題を解決するための手段】
【００１７】
本発明の次元削減方法は、特徴空間上の辞書生成用特徴パターン群を入力する特徴パターン群入力ステップと、ｃ個のカテゴリの各々に対応する特徴空間上の二次関数の係数の値を設定する初期係数設定ステップと、前記二次関数を識別関数とした辞書生成用特徴パターン群の識別による損失関数の値が小さくなるように、二次関数の係数を勾配降下法、又は確率的勾配降下法により修正する係数修正ステップと、ｃ個のカテゴリの各々について、前記二次関数の二次の項の二次形式の対称行列の固有ベクトルと、前記二次関数の一次の項の係数ベクトルとの中から一つ以上のベクトルを選択する基底ベクトル導出ステップと、ｃ個のカテゴリの各々について、基底ベクトル導出ステップにおいて選択されたベクトルを基底とする特徴空間の部分空間である辞書部分空間への射影行列を生成する射影行列導出ステップと、ｃ個のカテゴリの各々に対応するｃ個の辞書部分空間への前記射影行列、又は、ｃ個のカテゴリの各々に対応する前記射影行列と前記二次関数の係数とを出力する射影行列出力ステップと、を有する。
【００１８】
本発明の次元削減方法では、ｃ個のカテゴリの各々に対応する特徴空間と辞書生成用特徴パターン群を入力とする特徴パターン群入力ステップを備えても良い。また、ｃ個のカテゴリに共通の１つの特徴空間と１つの辞書生成用特徴パターン群を入力とする特徴パターン群入力ステップを備えても良い。特徴空間はベクトル空間であり、辞書生成用特徴パターン群が、ベクトル空間上の所属カテゴリを示すラベル付きベクトル値の集合であっても良い。ｃ個のカテゴリの各々に対応する特徴空間と辞書生成用特徴パターン群を入力とする場合については、例えば、非特許文献４を参照のこと。
【００１９】
本発明の次元削減方法では、係数修正ステップで、辞書生成用特徴パターン群の各々を、二次関数を用いて識別したときの二乗誤差関数を損失関数とし、損失関数の値が小さくなるように、勾配降下法、又は、確率的勾配降下法により修正しても良い。
【００２０】
射影行列導出ステップでは、係数ベクトルと対称行列の固有値の絶対値が大きい上位ｎ個に対応する固有ベクトル、又は、係数ベクトルと対称行列の固有値の絶対値が閾値ｈよりも大きい上位ｎ個に対応する固有ベクトルとによって生成される特徴空間の部分空間への射影行列を生成してもよい。あるいは、対称行列の固有値の絶対値が大きい上位ｎ個に対応する固有ベクトル、又は、対称行列の固有値の絶対値が閾値ｈよりも大きい上位ｎ個に対応する固有ベクトルによって生成される特徴空間の部分空間への射影行列を生成しても良い。
【００２１】
本発明のパターン認識用辞書生成装置は、辞書生成用パターン群を入力する入力部と、辞書生成用パターン群からｃ個のカテゴリの各々に対応する特徴空間上の辞書生成用特徴パターン群を抽出する特徴抽出部と、特徴空間上の辞書生成用特徴パターン群を入力する特徴パターン群入力処理、ｃ個のカテゴリの各々に対応する特徴空間上の二次関数の係数の値を設定する初期係数設定処理、前記二次関数を識別関数とした辞書生成用特徴パターン群の識別による損失関数の値が小さくなるように、前記二次関数の係数を勾配降下法、又は確率的勾配降下法により修正する係数修正処理、ｃ個のカテゴリの各々について、前記二次関数の二次の項の二次形式の対称行列の固有ベクトルと、前記二次関数の一次の項の係数ベクトルとの中から一つ以上のベクトルを選択する基底ベクトル導出処理、ｃ個のカテゴリの各々について、基底ベクトル導出処理において選択されたベクトルを基底とする特徴空間の部分空間である辞書部分空間への射影行列を生成する射影行列導出処理、ｃ個のカテゴリの各々に対応するｃ個の辞書部分空間への前記射影行列、又は、ｃ個のカテゴリの各々に対応する前記射影行列と前記二次関数の係数とを出力する射影行列出力処理、を含む特徴空間の次元削減処理により辞書部分空間への前記射影行列を生成する辞書部分空間生成部と、前記射影行列により辞書生成用特徴パターン群を辞書部分空間に射影した学習用特徴パターン群を生成する学習用特徴パターン群生成部と、学習用特徴パターン群を用いてｃ個のカテゴリを識別する識別関数を生成する識別関数生成部と、前記射影行列と識別関数のパラメータとを出力する出力部と、を有する。
【００２２】
識別関数生成部は、ｃ個のカテゴリの各々について、前記二次関数を辞書部分空間に制限した制限二次関数を生成し、制限二次関数を識別関数として学習用特徴パターン群の各々の所属カテゴリを判定したときの二乗誤差関数を損失関数として、二乗誤差の値が小さくなるように、勾配降下法、又は、確率的勾配降下法により制限二次関数の係数を修正したものを識別関数として生成しても良い。また、ｃ個のカテゴリの各々について、二次関数を辞書部分空間に制限したものを識別関数として生成してもよい。
【００２３】
本発明のパターン認識装置は、特徴空間上の辞書生成用特徴パターン群を入力する特徴パターン群入力処理、ｃ個のカテゴリの各々に対応する特徴空間上の二次関数の係数の値を設定する初期係数設定処理、前記二次関数を識別関数とした辞書生成用特徴パターン群の識別による損失関数の値が小さくなるように、前記二次関数の係数を勾配降下法、又は確率的勾配降下法により修正する係数修正処理、ｃ個のカテゴリの各々について、前記二次関数の二次の項の二次形式の対称行列の固有ベクトルと、前記二次関数の一次の項の係数ベクトルとの中から一つ以上のベクトルを選択する基底ベクトル導出処理、ｃ個のカテゴリの各々について、基底ベクトル導出処理において選択されたベクトルを基底とする特徴空間の部分空間である辞書部分空間への射影行列を生成する射影行列導出処理、ｃ個のカテゴリの各々に対応するｃ個の辞書部分空間への射影行列、又は、ｃ個のカテゴリの各々に対応する射影行列と前記二次関数の係数とを出力する射影行列出力処理、を含む特徴空間の次元削減処理により生成された辞書部分空間上の識別関数のパラメータと前記射影行列とを格納する認識用辞書格納部と、認識対象の入力パターンを入力する入力部と、入力パターンから特徴空間上のベクトル値を抽出する特徴抽出部と、ｃ個のカテゴリの各々について、前記射影行列により入力パターンを辞書部分空間に射影した射影ベクトルを生成する射影ベクトル生成部と、ｃ個のカテゴリの各々について、識別関数の射影ベクトルが表す点での値を算出し、それに基づいて入力パターンが属するカテゴリを識別する識別部と、識別部での識別結果を出力する出力部と、を有する。
【発明の効果】
【００２４】
本発明による特徴空間の次元削減手法は、パターン認識装置において、高精度、高速性、省メモリを目的とした識別に有利な特徴空間の部分空間を選択することができる。これによって、パターン認識装置において、容量の小さいパターン認識用辞書を作成することができる。また、パターン認識用辞書を用いた識別処理において、高認識率、高速性、省メモリを実現できる。
【発明を実施するための最良の形態】
【００２５】
以下、本発明の実施に形態について説明する。
［実施例１］
図１は、本発明の次元削減方法を用いてパターン認識用辞書を生成するパターン認識用辞書生成装置の一例を示す構成図である。パターン認識用辞書生成装置は、入力装置１１、演算装置１２、パターン認識用の認識辞書１３、表示装置１５、パターンデータベース（ＤＢ）１６を備える。演算装置１２は、本発明による次元削減方法を用いてパターン認識用辞書を生成するパターン認識用辞書作成手段を備える。
【００２６】
入力装置１１は、コマンド等を入力するためのキーボードやマウス、及び画像入力のためのスキャナ等の装置である。演算装置１２はＣＰＵ、メモリ、記憶装置等を備え、入力された画像、音声等の辞書生成用パターン群を読み取り、パターン認識用辞書を生成し、認識辞書１３に格納する。演算装置１２は具体的には、特徴抽出部１７、辞書部分空間生成部１８、学習用特徴パターン群生成部１９、及び識別関数生成部２０を備え、これら各部の機能はプログラムによって実行される。認識辞書１３は、演算装置１２が作成したパターン認識用辞書を保存する辞書データベースである。表示装置１５は、演算装置１２による処理内容を適宜表示するディスプレイ等の装置である。表示装置１５はなくてもよい。パターンＤＢ１６は、入力装置１１によって入力されたパターンを格納する。パターンＤＢ１６には、パターン認識用辞書を作成するために演算装置１２が用いる辞書生成用パターン群等が格納されている。
【００２７】
図２は、演算装置１２によって実行されるパターン認識用辞書作成手段の概略を示すフロー図である。なお。本発明の特徴は、辞書部分空間生成ステップ２３にある。辞書部分空間生成ステップ２３では、本発明の次元削減方法により特徴空間の次元を削減する。辞書部分空間生成ステップ２３における詳細な処理フローは図４に示す。
【００２８】
入力ステップ２１では、ユーザ又は、演算装置１２により実行されるプログラムによって、辞書生成用パターン群が入力される。辞書生成用パターン群は、画像や音声などのパターンとその所属カテゴリを示すラベルの組の集合であり、予め辞書生成用に準備しておく。以下、カテゴリの数をｃ（ｃは自然数）とおく。ここで、カテゴリとは、例えば、数字認識の場合、０〜９の数字となる。このとき、ｃ＝１０である。
【００２９】
特徴抽出ステップ２２では、入力パターンをベクトル値に変換する。特徴抽出ステップ２２は特徴抽出部１７によって実行される。パターン認識用辞書生成装置は、特徴抽出ステップ２２の処理により、辞書生成用パターン群の各々をベクトル空間上のベクトル値に変換する。これによって、辞書生成用パターン群をベクトル空間上のベクトル値とその所属ラベルのセットの集合に変換する。このベクトル空間を特徴空間、ベクトル値を特徴ベクトルとよび、辞書生成用パターン群から生成された特徴ベクトルとその所属ラベルのセットの集合を辞書生成用特徴パターン群とよぶ。変換後の辞書生成用特徴パターン群は、記憶装置などに保存してもよい。特徴空間は、全カテゴリに共通の１つの特徴空間として得られる場合と、カテゴリごとに特徴空間が存在し合計ｃ個の特徴空間が得られる場合がある。特徴空間がカテゴリごとに存在する場合には、入力パターンも各々の特徴空間上での特徴ベクトルに変換される。したがって、ｃ個のカテゴリの場合には、１つのパターンに対して、ｃ個の特徴空間上の特徴ベクトルとしての表現が得られる。また、特徴空間がカテゴリごとに存在する場合には、特徴空間の次元数もカテゴリごとに異なる場合がある。
【００３０】
以下では、パターンをベクトル値に変換する方法の典型的な例について説明する。但し、パターンをベクトル値に変換する方法は、この典型例に限らず、様々な方法が用いられる。ここで挙げるのは一例である。ここでの例における処理は、パターンの正規化、特徴抽出、原特徴空間の次元削減を経て、特徴空間上の特徴ベクトルを得る流れである。
【００３１】
まず、画像、音声等のパターンは、個々のパターンのばらつきを抑え、パターンの条件を揃えるために正規化を行う。その後、特徴抽出手法によりベクトル空間上のベクトルに変換される。但し、正規化は省略してもよい。前記ベクトル空間を原特徴空間、前記ベクトルを原特徴ベクトルと呼ぶ。例えば、文字認識の場合には、正規化法として、線形正規化、非線形正規化、モーメント正規化等、特徴抽出手法として画素特徴抽出、輪郭特徴抽出、勾配特徴抽出等が用いられる。詳しくは、非特許文献２を参照のこと。次に、予め準備しておいた辞書生成用パターン群の一つ一つのパターンから特徴を抽出し、原特徴ベクトルを生成する。辞書生成用パターン群から生成された原特徴ベクトルとその所属カテゴリを示すラベルのセットの集合を辞書生成用原特徴パターン群とよぶことにする。
【００３２】
次に、主成分分析法、線形判別法などの従来型の次元削減方法を用いて、原特徴空間の次元削減を行う。但し、この次元削減は省略してもよい。省略した場合には、原特徴空間を特徴空間、原特徴ベクトルを特徴ベクトルとし、次の処理である辞書部分空間生成ステップ２３に移る。ここで、主成分分析法を用いた従来型の次元削減方法の例を二つ挙げる。
【００３３】
一つ目は、カテゴリごとに特徴空間を得る次元削減の例である。辞書生成用原特徴パターン群のカテゴリｋに所属するパターンのみを対象に主成分分析を行うことにより、カテゴリｋの分布を近似する部分空間が得られる。この部分空間をカテゴリｋに対応する特徴空間とし、原特徴空間上の辞書生成用原特徴パターン群の全てを特徴空間に射影したものをカテゴリｋに対応する辞書生成用特徴パターン群とする。この場合、特徴空間と辞書生成用特徴パターン群は、ｃ個のカテゴリの各々に対応して存在する。これについては、例えば、非特許文献４参照のこと。
【００３４】
二つ目は、次元削減の結果、全カテゴリに共通の１つの特徴空間が得られる例である。この特徴空間は、辞書生成用原特徴パターン群全体を対象とした主成分分析を行うことにより、パターン全体の分布を近似する部分空間として得られる。その部分空間を特徴空間とし、原特徴空間上の辞書生成用原特徴パターン群を特徴空間に射影したものを辞書生成用特徴パターン群とする。この場合、特徴空間は、全カテゴリに共通の１つである。
【００３５】
次に、画像中の０〜９の数字を認識する文字認識問題を例に、特徴抽出ステップ２２の処理の一例を具体的に説明する。辞書生成用パターン群は、数字が描かれた画像と、画像中に描かれている数字を表す正解ラベルのセットのN個（Nは自然数）からなる集合とする。まず、辞書生成用パターン群に含まれる各画像は、特徴抽出手法により、ｄ次元ベクトル空間（原特徴空間）上のベクトル値に変換される。ここでは、特徴抽出手法の一例として、画素特徴について説明する。文字画像が、例えば、縦横１６×１６ピクセルのグレイスケール画像で、１ピクセルが０から２５５の整数値の２５６階調で表されているとする。このとき、画像は、１６×１６＝２５６個の整数値で表されるので、画像は各ピクセルの値を成分とする２５６次元ベクトルで表すことができる。この２５６次元ベクトル空間が原特徴空間、２５６次元ベクトルが原特徴ベクトルとなる。これによって、辞書生成用パターン群は、式(1)に示すように、２５６次元ベクトルｘiと正解ラベルωiのセット（ｘi、ωi）からなる集合に変換される。例えば、ベクトルｘjが数字３が描かれた画像パターンから変換されたベクトルである場合には、ωj＝３となる。この集合を辞書生成用原特徴パターン群と呼ぶ。
【００３６】
【数１】
2010039778.tif 000003
【００３７】
次に、主成分分析法や線形判別法など、従来型の次元削減方法によって、原特徴空間の次元を削減する。但し、この従来型の次元削減方法による次元削減は行わず、原特徴空間を特徴空間、原特徴ベクトルを特徴ベクトルとして、次の処理である辞書部分空間生成ステップ２３に移ってもよい。ここでは、カテゴリごとの当該カテゴリに所属する辞書生成用原特徴パターン群を対象とした主成分分析によりカテゴリごとに特徴空間を得る次元削減方法と、辞書生成用原特徴パターン群全体を対象とした主成分分析により全カテゴリ共通の一つの特徴空間を得る次元削減法の二つの例を述べる。
【００３８】
まず、一つ目の例であるカテゴリごとに、当該カテゴリに所属する辞書生成用原特徴パターン群を対象とした主成分分析による次元削減方法について述べる。カテゴリごとの主成分分析では、当該カテゴリに所属する辞書生成用原特徴パターン群のみを対象として、主成分分析を行う。これは、当該カテゴリに所属するパターンの分布の分散が大きい部分空間を選択することを意味し、当該カテゴリの分布の様子を良く近似するような部分空間が得られる。具体的には、式(2)に示すカテゴリｋに対応するパターンの共分散行列Σkの固有値問題を解くことにより得られる。ここで、式(2)の中のμkは、式(3)により定義される当該カテゴリのパターン分布の平均ベクトルである。固有値問題を解くアルゴリズムについては、Numerical Recipes in C: The Art of Scientific Computing, William H. Press, Brian P. Flannery, Saul A. Teukolsky and William T.Vetterling, Cambridge University Press; 2nd ed., 1992（参考文献１）などを参照のこと。共分散行列Σkの上位ｍ個の固有値に対応する固有ベクトルを式(4)のようにΦki（ｉ＝１，２、…ｍ）とおく。このとき、カテゴリｋに対応する特徴空間としてΦki（ｉ＝１，２、…ｍ）によって張られる部分空間を選択する。この部分空間への射影行列は式(5)により定義されるｍ×ｄ行列Ｑkとなる。ここで、式(5)において、Ｑkの右上のｔはＱkの転置行列であることを示す。以下の式でも同様。原特徴空間上の原特徴ベクトルｘは、Ｑkを用いて式(6)のように、カテゴリｋに対応する特徴空間上の特徴ベクトルｙkに射影される。
【００３９】
【数２】
2010039778.tif 000004
【００４０】
以上により、カテゴリｋに対応する特徴空間は、ｍ×ｄの射影行列Ｑkにより定義されるｍ次元特徴空間となる。ｄ次元原特徴空間上のベクトルｘは、式(6)により、各々のカテゴリｋに対して、対応するｍ次元特徴空間上のベクトルにより計ｃ通りに表現される。ここで、式(6)のＣkは、分布のスケールを正規化するための定数である。
【００４１】
次に、二つ目の例である辞書生成用原特徴パターン群全体を対象とした主成分分析による次元削減法について述べる。この場合には、辞書生成用原特徴パターン群の全てを対象として主成分分析を行う。これは、辞書生成用原特徴パターン群の全ての分布の分散が大きい成分を表現する部分空間を選択することを意味し、パターン全体の分布の様子を良く近似するような部分空間が得られる。具体的には、式(7)に示す共分散行列Σの固有値問題を解くことにより得られる。ここで、式(7)の中の平均μは、式(8)により定義される。共分散行列Σの上位ｍ個の固有値に対応する固有ベクトルを式(9)のようにΦi（ｉ＝１，２、…ｍ）とする。このとき、特徴空間としてΦi（ｉ＝１，２、…ｍ）によって張られる部分空間を選択する。この部分空間への射影行列は式(10)により定義されるｍ×ｄ行列Ｑとなる。原特徴空間上の原特徴ベクトルｘは、Ｑを用いて式(11)のように、特徴空間上のベクトルｙとして表される。以上により、次元削減後の特徴空間は、ｍ×ｄの射影行列Ｑにより定義される特徴空間となる。ここで、式(11)のＣは、分布のスケールを正規化するための定数である。
【００４２】
【数３】
2010039778.tif 000005
【００４３】
二つ目の例による辞書生成用特徴パターン群全体を対象とした主成分分析による次元削減法で得られる次元削減後のｍ次元特徴空間は、ｍ×ｄの射影行列Ｑにより定義される。一方、一つ目の例による辞書生成用特徴パターン群を対象とした主成分分析による次元削減方法で得られる次元削減後の特徴空間は、数字カテゴリ０〜９に対応する１０個のカテゴリごとに存在し、各カテゴリに対応する特徴空間は、射影行列Ｑ0、Ｑ1、…、Ｑ9によって定義される。
【００４４】
二つ目の例による次元削減法は、一つ目の例において、Ｑ＝Ｑ0＝Ｑ1＝…＝Ｑ9となる特別な場合と看做すことができる。
【００４５】
上述のように、カテゴリに共通の１つの特徴空間をもつ場合は、ｃ個のカテゴリの各々に対して特徴空間が存在する場合の特別な場合と看做すことができる。そのため、以降では、ｃ個のカテゴリの各々に対して特徴空間が存在する場合をもとに、説明を続け、カテゴリに共通の１つの特徴空間の場合は、その特別な場合として扱う。原特徴空間を特徴空間、原特徴ベクトルを特徴ベクトルとする場合には、射影行列Ｑは、Ｑ＝Ｉ（単位行列）となる。
【００４６】
以上により、特徴抽出ステップ２２の処理の典型例の説明を終わる。
特徴抽出ステップ２２において、パターンを特徴ベクトルに変換するために必要な情報は、パターン認識用の認識辞書１３に保存する。パターン認識装置では、この情報を用いて、同じ方法により入力パターンを特徴ベクトルに変換する。パターン認識用の認識辞書１３に保存する情報は、例えば、用いた正規化法、特徴抽出手法や、原特徴空間から特徴空間に射影するための射影行列などである。
【００４７】
次に、辞書部分空間生成ステップ２３において、本発明による次元削減手法を用いて、各カテゴリの特徴空間の次元を削減する。辞書部分空間生成ステップ２３は、辞書部分空間生成部１８において実行される。
【００４８】
辞書部分空間生成ステップ２３は、辞書生成用特徴パターン群を入力として、本発明による次元削減方法により、ｃ個のカテゴリの各々について、特徴空間の次元削減を行い、各々のカテゴリに対応する特徴空間の部分空間を得る。この部分空間を辞書部分空間と呼ぶ。辞書部分空間生成ステップ２３では、特徴空間から辞書部分空間への射影行列を出力として得る。出力した射影行列は、パターン認識用の認識辞書１３に保存する。
【００４９】
本発明の第一の特徴は、この辞書部分空間生成ステップ２３にあり、特徴空間の次元削減方法が従来とは異なる。辞書部分空間生成ステップ２３では、特徴空間の部分空間の中から識別に有利な部分空間を辞書部分空間として選択することができる。
【００５０】
図４は、演算装置１２によって実行される辞書部分空間生成ステップ２３の処理の概略を示すフロー図である。
【００５１】
本発明の特徴は、従来の主成分分析法や線形判別法などとは異なる手法により、特徴空間の次元を削減する次元削減部分にある。図４に示した処理フローの説明を行う前に、まず、本発明の特徴を、二次元空間上の２カテゴリ判別問題を例に簡単に説明する。また、その後、ニューラルネットワークの概念図を用いて、本発明のアイデアを説明する。
【００５２】
説明を簡単にするため、例として、２次元空間上に分布する図５に示すカテゴリ５１と図６に示すカテゴリ６１の２カテゴリの識別問題において、１次元の特徴空間を選択する問題を考える。
【００５３】
まず、従来手法である主成分分析法による次元削減例を示す。カテゴリ６１を対象に主成分分析を行うと、共分散行列の固有ベクトルが示す方向として、図６に示すｘ軸とｙ軸が得られる。カテゴリ６１の分散はｘ軸方向の方が大きいので、主成分分析による次元削減では、図６のｘ軸が判別軸として選択される。このとき、２カテゴリを分離する判別面はｘ軸に垂直な直線となる。例えば、図７の直線７１を判別面として選択することができる。しかし、この場合判別面７１の左右両方にカテゴリ６１のパターンが多く分布することになり、２カテゴリの識別には有効でないことがわかる。
【００５４】
次に、本発明による次元削減例を示す。本発明による手法では、まず２カテゴリを分離する二次曲面を作成する。両カテゴリを分離する二次曲面は、例えば、図８に示すような二次曲線８１のようになる。前記二次曲面は、二次関数の等高面によって表される。この二次関数は、両カテゴリを識別する二次関数として、ニューラルネットワークによる学習により作成される。次に、学習により作成した二次関数の二次の項の二次形式の行列の固有ベクトルと、一次の項の係数ベクトルを導出する。次に、得られた二次関数の二次の項の二次形式の行列の固有ベクトルと一次の項の係数ベクトルとの中から、一定の基準により、１つ以上のベクトルを選択する。この例では、前記固有ベクトルの中から１つを選択することを考えることにする。二次曲線８１の場合、前記固有ベクトルが表す方向は、図９の直線９１と直線９２が表す方向である。二次関数の性質により、直線９１と直線９２は、二次関数の等高面８１の対称軸となっている。
【００５５】
例として、直線９１を選択したとする。この場合、直線９１が判別軸となり、これに垂直な直線が識別面となる。例えば直線９１に垂直な図１０の直線１０１を識別面とできる。このとき、識別面１０１は、カテゴリ５１、カテゴリ６１を分離する識別面とすることができる。このとき、識別面１０１の上部にカテゴリ５１のパターンが、下部にカテゴリ６１のパターンが多く分布することとなり、主成分分析の場合よりも有利な識別を行うことができる。
【００５６】
次に、本発明による次元削減法の基本的なアイデアを、ニューラルネットワークを用いて説明する。まず、各々のカテゴリに対応する特徴空間上で、当該カテゴリに所属するパターンと当該カテゴリに所属しないパターンとを識別する式(12)のような二次関数ｆk(ｘ)を構成する。ここで、ｙk＝Ｑkｘ（式(13)）である。二次関数はニューラルネットワークにより図１１のように表現できる。
【００５７】
【数４】
2010039778.tif 000006
【００５８】
まず、二次関数の重みｗkij、ｗki、ｗkc（ｉ、ｊ＝１、…、ｍ）を学習する。このとき、原特徴ベクトルｘに対して、ｆ1(ｘ)、…、ｆc(ｘ)の値を全て計算し、この中で値が最も大きいものがｆk(ｘ)であるとき、原特徴ベクトルｘが表すパターンはカテゴリｋに所属すると判定する。この判定において、辞書生成用パターン群を識別し、誤識別したときの損失を表す損失関数の値が小さくなるように重みｗkij、ｗki、ｗkc（ｉ、ｊ＝１、…、ｍ）を学習する。具体的な学習の例は、後述の係数修正ステップ４３の処理の説明で行う。
【００５９】
次に、特徴ベクトルを式(14)に示すようにある行列Ｒkを用いて変換することで、ニューラルネットワークの出力を変えることなく図１２のように、ニューラルネットワークを再構成することができる。行列Ｒkの導出方法は後述する。
【００６０】
【数５】
2010039778.tif 000007
【００６１】
図１２の重みλiとｚiは、カテゴリを示すｋに依存するため、実際には、λki、ｚkiと表されるべきものであるが、煩雑さを避けるために、添え字ｋは省略した。後の図１３でも同様に省略した。
【００６２】
次に、ニューラルネットワークの出力に影響が少ない結合を取り除く。その一例を挙げる。いま、結合の重みλk1、…、λkmが絶対値の大きい順に並んでいるとする。ここで、図１３の白丸部分の下位のλkn+1からλkmまでの結合は弱い結合であると考えられる。このとき、この結合を削除しても、ニューラルネットワークの出力に対する影響は少ないと仮定する。そこで、この部分の結合を除くと、ニューラルネットワークは、ｚk1、…、ｚkn、ｚk0、１に対応する入力ユニットに繋がる部分だけで、もとのニューラルネットワークの構造を近似できると考えられる。このことは、ｎ＋１個の特徴ｚk1、…、ｚkn、ｚk0だけで、識別に十分な情報を保持していることを意味する。次元削減では、ｍ次元から、このｎ＋１個の特徴に対応する特徴次元に次元を削減する。
【００６３】
以下、図４に基づいて、処理のフローを説明する。特徴パターン群入力ステップ４１では、ユーザ又は、演算装置１２により実行されるプログラムによって、ｃ個のカテゴリの各々に対応する特徴空間上の所属カテゴリラベル付き特徴ベクトル群、すなわち、辞書生成用特徴パターン群が入力される。但し、前記特徴空間が全カテゴリで共通の場合には、前記辞書生成用特徴パターン群も全カテゴリで共通の１つの特徴空間上の特徴ベクトル群である。
【００６４】
初期係数設定ステップ４２は、ｃ個のカテゴリの各々について、当該カテゴリに対応する特徴空間上の二次関数を生成する。例えば、カテゴリｋの特徴空間上の特徴ベクトルｙkを式(15)のように表すと、特徴空間上の二次関数は式(16)のように表される。ここで、ｋはカテゴリを示す添え字で、ｍは、カテゴリｋに対応する特徴空間の次元数である。式(17)に示されるものが、二次関数（式(16)）の係数である。式(17)に示される係数を設定することにより式(16)の二次関数を定義することができる。この二次関数は、ニューラルネットワークにより、図１１のように表現することができる。
【００６５】
【数６】
2010039778.tif 000008
【００６６】
式(16)で表される二次関数の係数（式(17)）は、乱数により生成した値を設定してもよい。例えば、予め、特徴空間上の辞書生成用特徴パターン群の平均が特徴空間の原点に、辞書生成用特徴パターン群の分散が１となるように特徴空間の原点を設定し、スケール変換をしておいたとする。このとき、例えば、式(17)に示される係数を、−０．０５から０．０５の範囲で一様分布により生成した乱数により設定する。または、０を中心とする分散０．１のガウス分布により乱数を生成し、その値を式(17)に示される係数に設定してもよい。乱数は、各々の係数ごとに生成し、係数の初期値に設定する。
【００６７】
係数修正ステップ４３は、前記二次関数を用いた識別による損失関数の値が小さくなるように、勾配降下法により二次関数の係数を修正する。以下、式(15)から式(29)までを用いて、係数の修正過程を説明する。
【００６８】
まず、二次関数を用いたカテゴリの識別の例について説明する。画像、音声等の入力パターンから抽出した原特徴空間上の原特徴ベクトルをカテゴリｉに対応する特徴空間に射影した特徴ベクトルをｙi（式(15)）として表現する。次に、パターンを各カテゴリの特徴空間上で表現した特徴ベクトルにおける二次関数ｆ1(ｙ1)、…、ｆc(ｙc)（式(16)）の値を計算する。特徴ベクトルｙi（式(15)）における二次関数ｆi(ｙi)（式(16)）の値を、入力パターンのカテゴリｉに対する類似度であるとみなして識別を行う。計算したｃ個の値ｆ1(ｙ1)、…、ｆc(ｙc)のうち最大のものがｆk(ｙk)であったとき、入力パターンの所属カテゴリがｋであると識別する。
【００６９】
損失関数は、部分損失関数の和である。部分損失関数は、辞書生成用パターン群に含まれる１つのパターンを識別したときの誤識別による損失を表す関数であり、辞書生成用パターン群の各々のパターンに対して定義される。部分損失関数は、重みｗkij、ｗki、ｗkc（ｉ、ｊ＝１、…、ｍ）に依存する関数である。損失関数の例について説明する。Ｎ個のパターンを含む辞書生成用パターン群を原特徴空間上で表現した原特徴ベクトルと正解ラベルのセットの集合は式(1)により与えられる。また、目標変数ｌks（式(18)）をｓ番目のパターンがカテゴリｋに所属するとき１、それ以外の場合に０となるようにおく。このとき、ｓ番目のパターンの誤識別による部分損失関数は、例えば、式(19)により定義される。式(19)のｕkは、式(21)のシグモイド関数を用いて式(20)により定義される。これは、ｓ番目のパターンｘsがカテゴリｋに所属するとき、カテゴリｋに対応する関数ｕk（式(20)）のｓ番目のパターンにおける値ｕk(ｘs)が１に近い場合に正しく識別できたとみなし、０に近い場合に誤って識別したとみなすことに相当する。また、正則化項を加えた式(22)を部分損失関数としてもよい。ここで、ｂは荷重減衰とよばれる。損失関数Ｅkは、式(23)のように部分損失関数の和によって与えられる。式(23)は二乗誤差関数とよばれる。
【００７０】
【数７】
2010039778.tif 000009
【００７１】
次に、二次関数の係数の修正式について述べる。係数の修正は、損失関数（式(23)）が小さくなるように、勾配降下法、又は、確率的勾配降下法により行われる。
【００７２】
まず、勾配降下法の例について説明する。勾配降下法は、辞書生成用特徴パターン群から計算した損失関数（式(23)）が小さくなるように、勾配法により繰り返し係数を修正する。係数をまとめたベクトルを式(24)のようにおくと、ｔ＋１回目の修正による係数の値θk(ｔ＋１)は、式(25)で与えられる。ここで、ａは、学習率レートである。ａは、例えば、ｔ＝０のとき分散のスケールと同程度の値をとり、最後の修正に相当するｔにおいて、０となるように一定数ずつ小さくなるようにとる。式(25)の右辺は、辞書生成用特徴パターン群全てを用いて計算するため、勾配降下法は、辞書生成用特徴パターン群を全て用いたバッチ学習である。
【００７３】
【数８】
2010039778.tif 000010
【００７４】
次に、確率的勾配降下法の例について説明する。前記の勾配降下法では、式(25)の右辺は損失関数（式(23)）の導関数が現れるので、辞書生成用特徴パターン群全てを用いて式(25)の右辺を計算しなければならない。確率的勾配降下法では、損失関数ではなく部分損失関数を用いて、式(26)により係数修正を行う。そのため、辞書生成用特徴パターン群の１つ１つのパターンについて逐次修正が行われる。修正は、辞書生成用特徴パターン群がランダム、又は、順番に与えられるたびに、式(26)により行われる。修正の回数は、辞書生成用特徴パターン群全体を、例えば、４０回程度巡回するようにとる。式(26)における部分損失関数の導関数を、各係数について具体的に書き下すと式(27)、(28)、(29)のようになる。
【００７５】
【数９】
2010039778.tif 000011
【００７６】
以下では、煩雑さを避けるため、カテゴリを示すためにつけた添え字ｋは省略する場合がある。
【００７７】
基底ベクトル導出ステップ４４では、ｃ個のカテゴリの各々に対して、初期係数設定ステップ４２、係数修正ステップ４３で作成した二次関数の二次の項の二次形式の行列の固有ベクトルと、一次の項の係数ベクトルを導出する。二次関数を式(16)のように表したとき、二次の項、一次の項は、それぞれ式(30)、(31)のようになる。また、二次関数（式(16)）の二次の項（式(30)）の二次形式の行列は式(32)に示す対称行列により与えられ、一次の項（式(31)）の係数ベクトルは式(33)によって与えられる。式(32)、(33)を用いると、二次関数（式(16)）は、式(34)のように表すことができる。
【００７８】
【数１０】
2010039778.tif 000012
【００７９】
次に、式(16)の二次関数を上述の式(32)に示す行列の固有ベクトルを基底とした表現で与えておく。式(32)の固有ベクトルを式(35)のようにｐk1、ｐk2、…ｐkmで表し、行列Ｐkを式(36)のように与える。式(32)を式(35)のベクトルを基底として表現すると式(37)のような対角行列になる。行列Ｐkは直交行列であるため、式(16)は、式(37)、(38)を用いて、式(39)のように表される。式(37)、(38)、(39)を用いると、式(16)は式(40)のようになる。また、式(41)のようにおき、式(42)を用いると、式(16)は式(43)のように表すこともできる。対称行列（式(32)）の固有ベクトルの導出アルゴリズムについては、例えば、参考文献１が詳しい。図９の例の場合、二次関数(16)の二次の項の二次形式の行列の固有ベクトルは、直線９１と直線９２である。
【００８０】
【数１１】
2010039778.tif 000013
【００８１】
射影行列導出ステップ４５は、カテゴリごとに、基底ベクトル導出ステップ４４で求めた二次関数の二次の項の二次形式の行列の固有ベクトル（式(35)）と一次の項の係数ベクトル（式(33)）との中から１つ以上のベクトルを選択し、選択したベクトルによって生成される部分空間を辞書部分空間として生成する。辞書部分空間は、カテゴリごとに存在する。射影行列導出ステップ４５では、カテゴリの各々に対して、特徴空間から辞書部分空間への射影行列を求める。
【００８２】
以下では、まず、選択の基準例を示す。その後、選択したベクトル群によって生成される辞書部分空間への射影行列を求める方法を説明する。
【００８３】
射影行列導出４５におけるベクトル選択の基準例を示す。
まず、二次関数の二次の項の二次形式の行列の固有ベクトル（式(35)）の中からの選択基準例を示す。
【００８４】
例１：式(43)の二次の項における第i番目の係数（式(44)）の絶対値が、式(45)に示すようにあらかじめ定めておいた閾値ｈ以上となるときに、それに対応するベクトルｐkiを全て選択する。閾値ｈは、削減したい次元数に応じて、例えば、分散のスケールを１としたとき、０．０１から０．５程度の値として定めてもよい。
【００８５】
【数１２】
2010039778.tif 000014
【００８６】
例２：式(43)の二次の項における第i番目の係数（式(44)）の絶対値が大きいものから順にｎ個選択し、例１と同様に、それに対応する固有ベクトルｐkiを選択する。自然数ｎの値は予め定めておいてもよい。
【００８７】
例３：式(43)の二次の項における第i番目の係数（式(44)）が正のものと負のものとで分け、正と負の重みを交互に絶対値の大きいものからｎ個選択する。
【００８８】
これらの意味することを例１の場合について説明する。例１の場合、式(46)のように係数λiiが小さい項を認識への寄与が少ないとして無視し、主要部分だけで近似することに相当する。但し、この近似は、係数ベクトルを選択しない場合の近似である。後述の基準により係数ベクトルを選択した場合には、式(47)のように近似される。
【００８９】
【数１３】
2010039778.tif 000015
【００９０】
次に、二次関数の一次の項の係数ベクトルｗ1（式(33)）を選択する基準例を示す。但し、式(33)が零ベクトルとなる場合には、係数ベクトルの選択は行わない。
【００９１】
例１：まず、二次関数の二次の項の二次形式の行列の固有ベクトルを上記のいずれかの基準により選択する。その後、選択した固有ベクトルによって生成される部分空間に直交する係数ベクトルの成分を求める。前述の直交成分が一定の閾値ｈ以上となるときに、係数ベクトルを選択する。閾値ｈの値は予め定めておいてもよい。また、閾値ｈは、上述の二次関数の二次の項の二次形式の行列の固有ベクトルの中からのベクトル選択基準例１におけるｈとは、一般に異なる。
例２：全てのカテゴリに対して、係数ベクトルを選択する。
例３：全てのカテゴリに対して、係数ベクトルを選択しない。
【００９２】
以上が、係数ベクトル選択の基準例である。二次関数の二次の項の二次形式の行列の固有ベクトルは、式(32)の固有ベクトルであるので、ｍ個存在する。また、二次関数の一次の項の係数ベクトルは、式(33)によって与えられ、１つである。これらｍ＋１個のベクトルは、一般に異なる。射影行列導出ステップ４５では、上記に示したような選択の基準や、その他の基準によって、二次関数の二次の項の二次形式の行列の固有ベクトルと一次の項の係数ベクトルとの中から１つ以上のベクトルを選択する。選択した１つ以上のベクトルによって生成される部分空間が、辞書部分空間となる。
【００９３】
次に、射影行列導出ステップ４５において、選択したベクトル群によって生成される部分空間への射影行列を求める方法を説明する。以下では、選択された固有ベクトルを式(48)のようにｑk1、ｑk2、…、ｑknとおく。これらは、対称行列の固有ベクトルなので、正規直交系を成している。但し、係数ベクトル（式(33)）は、これらに正規直交しているとは限らないので、固有ベクトル（式(48)）に直交する係数ベクトル（式(33)）の成分を正規化したベクトルを求める。式(49)が０でない場合、係数ベクトルの前記固有ベクトルによって生成される空間に直交する成分を正規化したものは、式(50)によって与えられる。
【００９４】
まず、係数ベクトルが選択されなかった場合、求める部分空間は式(48)のベクトルｑk1、ｑk2、…、ｑknによって生成される空間であるので、射影行列は式(51)によって与えられる。式(49)が０の場合も同様に式(51)の行列Ｒkが射影行列となる。
【００９５】
【数１４】
2010039778.tif 000016
【００９６】
次に、係数ベクトルが選択され、式(49)が０でない場合、求める部分空間は式(48)のベクトルｑk1、ｑk2、…、ｑknと式(50)のベクトルｒkによって生成される。したがって、射影行列は式(52)の行列Ｒkによって与えられる。
【００９７】
【数１５】
2010039778.tif 000017
【００９８】
射影行列出力ステップ４６は、ｃ個のカテゴリの各々について、特徴空間のベクトルを辞書部分空間に射影するための情報をパターン認識用辞書１３に保存、又は出力する。例えば、射影行列（式(51)又は式(52)）を保存する。さらに、射影行列出力ステップ４６は、ｃ個のカテゴリの各々について、初期係数設定ステップ４２、係数修正ステップ４３において生成した二次関数を辞書部分空間に射影した二次関数の係数をパターン認識用認識辞書１３に保存、又は出力してもよい。
【００９９】
原特徴ベクトルから特徴ベクトルへの変換が、式(13)のように射影行列Ｑkによって表現される場合には、行列の積ＲkＱkを計算しておき、これを認識辞書１３に保存しておく。これによって、識別時には、原特徴ベクトルｘを抽出後、ＲkＱkｘを計算することにより、辞書部分空間上の射影ベクトルを得ることができる。
【０１００】
図２に戻って、学習用特徴パターン群生成ステップ２４は、辞書生成用特徴パターン群の各々をカテゴリごとに、前記射影行列により辞書部分空間上に射影する。これによって生成される辞書生成用特徴パターン群の各々のカテゴリの辞書部分空間への射影を学習用特徴パターン群とよぶ。ステップ２４は学習用特徴パターン群生成部１９で実行される。
【０１０１】
識別関数生成ステップ２５は、カテゴリごとに生成された辞書部分空間上で学習用特徴パターン群を用いて識別関数を学習する。識別関数はカテゴリごとに作成される。識別関数は、パターンを当該カテゴリの辞書部分空間上で表現したベクトルでの値が、対応するカテゴリに対するパターンの類似度となるように学習により生成される。識別関数の学習方法は、例えば、最近傍法、学習ベクトル量子化法、投影距離法、サポートベクトルマシン、ニューラルネットワーク等の方法を用いることができる。詳しくは、非特許文献２などを参照のこと。ステップ２５は識別関数生成部２０にて実行される。
【０１０２】
出力ステップ２６は、識別関数生成ステップ２５により作成された識別関数のパラメータをパターン認識用認識辞書１３に保存する。
【０１０３】
以下、本発明のパターン認識用辞書生成装置の特徴について説明する。本発明では、図２における辞書部分空間生成ステップ２３での次元削減手法が従来のものとは異なる。従来型のパターン認識用辞書生成装置では、主成分分析法や線形判別法などの手法により次元削減を行う。しかし、本発明によるパターン認識用辞書生成装置では、図４に示す一連の処理によって特徴空間の次元を削減する。これらの一連の処理に先立って、特徴抽出ステップ２２において、従来型の次元削減手法を用いた次元削減を実行してもよい。従来型の次元削減は省略してもよいが、従来型の次元削減を実行し、予めある程度次元を削減することによって後の処理を高速化することができる。
【０１０４】
以下に示すのは、手書きカナ認識実験において、従来型の次元削減方法である主成分分析法による次元削減方法と、本発明の次元削減方法で、認識率と１文字あたりの識別に要する時間を測定し、比較したものである。実験には、７５，０００個の学習サンプルと、学習サンプルとは異なる２２，６３１個のテストサンプルを用いた。テストサンプルの一部を図１５に示す。識別器には、クラス特有特徴を用いた多項式識別器で投影距離を除いたものを用いた。これについては、非特許文献４を参照のこと。
手法                特徴次元      認識率（％）    識別時間（ｍｓ）
従来型の次元削減方法          ６０        ９８．１０        ２．５４４
従来型の次元削減方法        １００        ９８．４３        ７．３４２
従来型の次元削減方法        ２００        ９８．７２      １８．１６４
本発明による次元削減方法      １５        ９８．６３        ０．８７３
本発明による次元削減方法      １０        ９８．４７        ０．６２９
【０１０５】
本発明による次元削減方法により、従来よりも低次元の特徴空間で、高速、高精度に認識できることが分かる。
【０１０６】
［実施例２］
本実施例におけるパターン認識装置の構成図は、実施例１における図１と同様である。入力装置１１は、コマンド等を入力するためのキーボード及びマウス等の装置及び、スキャナやカメラ等のパターン入力装置である。演算装置１２は、入力された画像、音声等パターンを読み取り、パターン認識用認識辞書１３に保存されている情報を用いて、入力パターンが予め定められたどのカテゴリに近いかを判定し、判定結果に基づいて認識する。演算装置１２は、実施例１のパターン認識用辞書作成手段を備えていてもよい。演算装置１２は、ＣＰＵ、メモリ、記憶装置等を備える。
【０１０７】
パターン認識用認識辞書１３は、演算装置１２が入力パターンを認識する際に参照する辞書データベースである。パターン認識用認識辞書１３に保存されているパターン認識用辞書は、本発明の次元削減手法を用いて作成されたパターン認識用辞書である。表示装置１５は、演算装置１２による入力パターンの認識結果を表示するディスプレイ等の装置である。
【０１０８】
パターンＤＢ１６は、入力装置１１によって入力されたパターンを格納する。パターンＤＢ１６には、パターン認識用認識辞書１３を作成するために演算装置１２が用いる辞書生成用パターン群ＤＢ、演算装置１２が認識対象とするパターンのデータ等が格納されていてもよい。また、入力装置から直接パターン入力される場合にはなくてもよい。
【０１０９】
図３は、本実施例の演算装置１２によって実行されるパターン認識手段の処理フローである。
【０１１０】
入力ステップ３１では、認識対象となるパターンがユーザ又は、演算装置１２で実行されるプログラムにより入力される。特徴ベクトル抽出ステップ３２では、入力パターンを特徴空間上の特徴ベクトルに変換する。入力パターンを特徴ベクトルに変換する入出力は、実施例１の図２における特徴抽出ステップ２２で、入力パターンを特徴ベクトルに変換する入出力と同じである。すなわち、入力されたパターンに対する出力は、入力パターンに対する特徴抽出ステップ２２の出力と同じものを得る。変換に必要な情報が、認識辞書１３に保存されている場合もある。例えば、実施例１の例において、原特徴空間から特徴空間への射影行列がＱkとして得られている場合には、パターンから原特徴ベクトルｘを抽出し、その後、射影行列Ｑkによって、出力として特徴ベクトルＱkｘを得る。
【０１１１】
射影ベクトル生成ステップ３３は、カテゴリごとに、特徴ベクトル抽出ステップ３２により作成された特徴ベクトルを辞書部分空間生成ステップ２３によって生成された辞書部分空間へ射影する。辞書部分空間へ射影する際の射影行列は、辞書部分空間生成ステップ２３により作成され、パターン認識用認識辞書１３に保存されている。射影ベクトル生成ステップ３３によって、各カテゴリに対して、辞書部分空間上の射影ベクトルが作成される。本実施例のパターン認識装置の特徴は、本発明の次元削減方法によって生成された辞書部分空間への射影ベクトルを用いる点にある。
【０１１２】
原特徴ベクトルから特徴ベクトルへの変換が、式(13)のように射影行列Ｑkによって表現されており、特徴空間から辞書部分空間への射影行列Ｒkとの積ＲkＱkが認識辞書１３に保存されている場合には、原特徴ベクトルｘからＲkＱkｘを求めることにより、辞書部分空間上の射影ベクトルを得ることができる。
【０１１３】
識別ステップ３４は、射影ベクトル生成ステップ３３により作成された各カテゴリの射影ベクトルと、識別関数生成ステップ２５で作成され、パターン認識用辞書１３に保存されているカテゴリごとの識別関数のパラメータを使い、入力パターンの各カテゴリに対する類似度を求める。各カテゴリに対する類似度は、当該カテゴリ上の辞書部分空間に射影された入力パターンの射影ベクトルが表す点における当該カテゴリの識別関数の値として算出される。
【０１１４】
全てのカテゴリに対する類似度を計算した後、入力パターンの所属カテゴリを判定する。通常、入力パターンは、最も類似度が高いカテゴリに所属すると判定される。また、棄却を行う場合もある。例えば、全カテゴリのうち最も類似度が高いカテゴリをパターンが所属するカテゴリと判定する。また、類似度のうち最も高い値である第一類似度が或る閾値以下の場合には、どのカテゴリにも属さないと判定して棄却する手法もある。また、類似度の上位２番目の値を第二類似度として、第一類似度と第二類似度が或る閾値以下の場合にも、いずれのカテゴリに属するか曖昧であるとして棄却する手法もある。
【０１１５】
本発明のパターン認識装置は、本発明の辞書作成装置により作成された辞書に保存されている識別関数を用いて類似度を計算する。その識別関数は、本発明による次元削減手法により生成された辞書部分空間上の関数である。
【０１１６】
出力ステップ３５では、識別ステップ３４での認識結果をディスプレイなどの表示装置１５への出力、記憶装置などへの保存等を行う。
【０１１７】
［実施例３］
実施例１のパターン認識用辞書生成装置において、辞書部分空間生成ステップ２３の部分を変更した実施形態の一例について述べる。装置構成は、実施例１と同様に図１によって示される。
【０１１８】
実施例１の辞書部分空間生成ステップ２３において、小さい次元数の削減を繰り返すことによって、特徴空間の次元を緩やかに削減することができる。これによって、認識精度に大きな影響を与えることなく、大幅に次元を削減することができる。
【０１１９】
具体的な方法を説明する。辞書部分空間生成ステップ２３における１回目の特徴パターン群入力ステップ４１から射影行列出力ステップ４６までの一連の処理により生成される辞書部分空間を第１次辞書部分空間とよぶことにする。まず、１回目の処理では、射影行列出力ステップ４６において、特徴空間から第１次辞書部分空間への射影行列（Ａ1とする）を保存する。次に、第１次辞書部分空間を特徴空間とみなして、初期値設定ステップ４２に戻り、射影行列出力ステップ４６までの処理を続ける。これにより、第１次辞書部分空間の次元削減が行われる。これにより生成される第１次辞書部分空間の部分空間を第２次辞書部分空間とよぶことにする。射影行列の保存ステップ４５において、第１次辞書部分空間から第２次辞書部分空間への射影行列（Ａ2とする）を保存する。再度、第２次辞書部分空間を特徴空間とみなし、初期値設定ステップ４２に戻り、処理を継続してもよい。このとき、例えば、一定数ずつ次元数を落としていくことによって、緩やかな次元削減を行うことができる。これをｔ回繰り返し、最終的に生成される第ｔ次辞書部分空間を辞書部分空間とする。辞書部分空間への射影行列は、行列Ａt、…、Ａ1の積により得られる。また、二次関数を保存、又は出力する場合には、第ｔ回目の処理で生成した二次関数を辞書部分空間に制限した二次関数の係数を保存、又は出力する。
【０１２０】
［実施例４］
実施例１のパターン認識用辞書生成装置において、辞書部分空間生成ステップ２３で生成した二次関数を識別関数として用いる実施例について説明する。装置構成は、実施例１と同様に図１によって示される。
【０１２１】
実施例１の辞書部分空間生成ステップ２３で求めた二次関数（式(16)）を辞書部分空間に制限したものを識別関数として用いることができる。例えば、固有ベクトルの選択に、実施例２の射影行列導出ステップ４５の固有ベクトル選択基準例１を採用すると、二次関数（式(16)）を辞書部分空間に制限した二次関数は、式(46)又は式(47)のようになり、これは、もとの二次関数（式(16)）を近似したものである。
【０１２２】
したがって、辞書部分空間に制限した二次関数を識別関数とみなし、射影行列の保存ステップ４６の後、出力ステップ２６に直接処理を移してもよい。これによって、パターン認識用辞書作成の処理時間を大幅に削減することができる。また、辞書部分空間生成ステップ２３によって低次元の辞書部分空間を選択することができるので、パターン認識装置における高精度、高速、省メモリが実現できる。
【図面の簡単な説明】
【０１２３】
【図１】本発明のパターン認識用辞書生成装置、及び、パターン認識装置の構成を示す図。
【図２】本発明のパターン認識用辞書生成装置の処理フローを示す図。
【図３】本発明のパターン認識装置の処理フローを示す図。
【図４】本発明の次元削減方法の処理フローを示す図。
【図５】次元削減例を説明するための２カテゴリ分類問題における第一カテゴリパターンの分布図。
【図６】次元削減例を説明するための２カテゴリ分類問題における第二カテゴリパターンの分布図。
【図７】次元削減例を説明するための２カテゴリ分類問題における従来手法による判別面を示した図。
【図８】次元削減例を説明するための２カテゴリ分類問題において、本発明の次元削減方法に用いる二次関数の等高面を示した図。
【図９】次元削減例を説明するための２カテゴリ分類問題において、本発明の次元削減方法における二次関数の二次の項の二次形式の固有ベクトルを示した図。
【図１０】次元削減例を説明するための２カテゴリ分類問題における本発明による判別面を示した図。
【図１１】二次関数をニューラルネットワークにより表現した図。
【図１２】特徴空間の基底を変換した後のニューラルネットワークの図。
【図１３】次元削減した後のニューラルネットワークの図。
【図１４】手書きカナ文字のサンプルを示す図。
【符号の説明】
【０１２４】
１１  入力装置
１２  演算装置
１３  認識辞書
１５  表示装置
１６  パターンＤＢ
２１  入力
２２  特徴抽出
２３  辞書部分空間生成
２４  学習用特徴パターン群生成
２５  識別関数生成
２６  出力
３１  入力
３３  射影ベクトル生成
３４  識別
３５  出力
４１  特徴パターン群入力
４２  初期係数設定
４３  係数修正
４４  基底ベクトル導出
４５  射影行列導出
４６  射影行列出力
５１  カテゴリ５１
６１  カテゴリ６１
７１  判別面
８１  二次関数の等高面
９１  固有ベクトル
９２  固有ベクトル
１０１  判別面
【図１】
2010039778.tif 000018
【図２】
2010039778.tif 000019
【図３】
2010039778.tif 000020
【図４】
2010039778.tif 000021
【図５】
2010039778.tif 000022
【図６】
2010039778.tif 000023
【図７】
2010039778.tif 000024
【図８】
2010039778.tif 000025
【図９】
2010039778.tif 000026
【図１０】
2010039778.tif 000027
【図１１】
2010039778.tif 000028
【図１２】
2010039778.tif 000029
【図１３】
2010039778.tif 000030
【図１４】
2010039778.tif 000031