(57)【特許請求の範囲】
【請求項１】
記憶媒体に記憶されている制御プログラムを実行することによりパターン認識に用いるための分類木を作成するように該情報処理装置を制御するための情報処理方法であって、
パターンの特徴を段階的に縮退する際の縮退ルールを設定する設定ステップと、
入力された複数の学習用パターンそれぞれについて、該学習用パターンの特徴を前記設定された縮退ルールに従って段階的に縮退することにより、各学習用パターンの階層構造を作成する階層化前処理ステップと、
前記階層化前処理ステップで作成された各学習用パターンの階層構造に基づいて、前記分類木のノードに対応付けされた前記縮退された特徴のうち最も分類効率が高くなる少なくとも１つの特徴を選択し、当該選択された特徴を複数の特徴に展開し、当該展開された複数の特徴それぞれに対応する学習用パターンのカテゴリの数に基づき該ノードから下位のノードまたは葉へ伸びる枝を決定することによって、前記分類木を上位のノードから順に作成する分類木作成ステップと
を有することを特徴とする情報処理方法。
【請求項２】
前記分類木作成ステップにおいて、前記展開された特徴に対応する学習用パターンのカテゴリの数がゼロのときは当該特徴に対応する枝を削除し、前記展開された特徴に対応する学習用パターンのカテゴリの数が１つの場合はそのカテゴリを葉とする枝を決定し、前記展開された特徴に対応する学習用パターンのカテゴリの数が複数の場合はそのカテゴリをノードとする枝を決定することによって、前記分類木を作成することを特徴とする請求項１に記載の情報処理方法。
【請求項３】
前記分類効率は、前記ノードから展開される枝１つあたりのエントロピーの減少量に基づいて定められることを特徴とする請求項１に記載の情報処理方法。
【請求項４】
更に、前記作成された分類木を用いて、認識対象の入力パターンを認識する認識ステップを有することを特徴とする請求項１に記載の情報処理方法。
【請求項５】
更に、前記作成された分類木を基に認識用のテンプレートを作成し、該テンプレートを用いて、認識対象の入力パターンを認識する認識ステップを有することを特徴とする請求項１に記載の情報処理方法。
【請求項６】
前記認識対象の入力パターンは、手書き文字パターン、もしくは光学的に読み取った文字パターン、もしくは音声パターンのいずれかであることを特徴とする請求項４又は５のいずれかに記載の情報処理方法。
【請求項７】
前記縮退ルールは、下の層の所定数の特徴の中で１つ以上の特徴がＯＮとなっていれば、対応する縮退された真上の層の特徴をＯＮにする第１のルール、または、下の層の所定数の特徴の中で２つ以上の特徴がＯＮとなっていれば、対応する縮退された真上の層の特徴をＯＮにする第２のルールのいずれかであることを特徴とする請求項１に記載の情報処理方法。
【請求項８】
パターン認識に用いるための分類木を作成する情報処理装置であって、
パターンの特徴を段階的に縮退する際の縮退ルールを設定する設定手段と、
入力された複数の学習用パターンそれぞれについて、該学習用パターンの特徴を前記設定された縮退ルールに従って段階的に縮退することにより、各学習用パターンの階層構造を作成する階層化前処理手段と、
前記階層化前処理手段で作成された各学習用パターンの階層構造に基づいて、前記分類木のノードに対応付けされた前記縮退された特徴のうち最も分類効率が高くなる少なくとも１つの特徴を選択し、当該選択された特徴を複数の特徴に展開し、当該展開された複数の特徴それぞれに対応する学習用パターンのカテゴリの数に基づき該ノードから下位のノードまたは葉へ伸びる枝を決定することによって、前記分類木を上位のノードから順に作成する分類木作成手段と
を有することを特徴とする情報処理装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は画像、音声、文字等のパターンをカテゴリーに分類する情報処理方法に関するものである。
【０００２】
【従来の技術】
従来、パターン認識を行う１方法として、ニューラルネットを用いた認識方法が存在した。ニューラルネットの大きな特徴としては、誤差逆伝播アルゴリズムに代表される強力な学習アルゴリズムが存在することが挙げられる。この特徴のため、これまで広い分野のパターン認識においてニューラルネットが適用されてきた。
【０００３】
また、パターン認識を行うもう１つの方法として、分類木を用いて段階的にパターンをカテゴリーに選別していく方法がある。例えば、特公平６−５２５３７号公報に記載されているパターン認識方式は、特徴軸に順番を付けて、その順番に従ってカテゴリー分けを行っている。
【０００４】
また、特徴変数の１次結合を元に、カテゴリー分けを行う方法があった。なお、一般に特徴軸を１つ１つ用いるより特徴変数の１次結合を用いた方が良い結果が得られている。
【０００５】
【発明が解決しようとしている課題】
しかしながら、上記従来の技術では以下の様な欠点があった。
【０００６】
１．ニューラルネットが適用できる特徴変数の範囲は、１０のオーダーであり、それ以上の高次元の特徴を入力変数とする場合には、何等かの事前カテゴリー分離、または、特徴抽出が必要である。しかも、事前カテゴリー分離、または、特徴抽出等の前処理を行うと、前処理で誤識誤差が生じる可能性があって、ニューラルネットをいくら精度よく作成できたとしても、最終的な認識率が良くならないという現象が起こる（図９参照）。
【０００７】
２．分類木が適用できる特徴変数の範囲も、１０のオーダーであり、それ以上多くの特徴変数を扱おうとすると、分類木の作成が事実上不可能となる。
【０００８】
３．実際のパターン認識において、生データの特徴変数の次元は１００から１０００のオーダーになるので、１０のオーダーしかとれない既存のニューラルネット、分類木をそのままの形で実際のパターン認識に使用することは不可能である。
【０００９】
【課題を解決するための手段】
上記課題を解決するために、本発明の情報処理方法は、記憶媒体に記憶されている制御プログラムを実行することによりパターン認識に用いるための分類木を作成するように該情報処理装置を制御するための情報処理方法であって、パターンの特徴を段階的に縮退する際の縮退ルールを設定する設定ステップと、入力された複数の学習用パターンそれぞれについて、該学習用パターンの特徴を前記設定された縮退ルールに従って段階的に縮退することにより、各学習用パターンの階層構造を作成する階層化前処理ステップと、前記階層化前処理ステップで作成された各学習用パターンの階層構造に基づいて、前記分類木のノードに対応付けされた前記縮退された特徴のうち最も分類効率が高くなる少なくとも１つの特徴を選択し、当該選択された特徴を複数の特徴に展開し、当該展開された複数の特徴それぞれに対応する学習用パターンのカテゴリの数に基づき該ノードから下位のノードまたは葉へ伸びる枝を決定することによって、前記分類木を上位のノードから順に作成する分類木作成ステップとを有することを特徴とする。
【００１０】
上記課題を解決するために、本発明の情報処理装置は、パターン認識に用いるための分類木を作成する情報処理装置であって、パターンの特徴を段階的に縮退する際の縮退ルールを設定する設定手段と、入力された複数の学習用パターンそれぞれについて、該学習用パターンの特徴を前記設定された縮退ルールに従って段階的に縮退することにより、各学習用パターンの階層構造を作成する階層化前処理手段と、前記階層化前処理手段で作成された各学習用パターンの階層構造に基づいて、前記分類木のノードに対応付けされた前記縮退された特徴のうち最も分類効率が高くなる少なくとも１つの特徴を選択し、当該選択された特徴を複数の特徴に展開し、当該展開された複数の特徴それぞれに対応する学習用パターンのカテゴリの数に基づき該ノードから下位のノードまたは葉へ伸びる枝を決定することによって、前記分類木を上位のノードから順に作成する分類木作成手段とを有することを特徴とする。
【００１７】
【実施例】
以下、図面に基づいて本発明の好適な実施例を説明する。
【００１８】
〈実施例１〉
図２は本発明のパターン認識方法が適用される情報処理装置の構成の一例を示すブロック図である。
【００１９】
パターン認識装置は、パターン入力装置２０１、表示装置２０２、中央処理装置（ＣＰＵ）２０３、メモリ２０４から構成される。
【００２０】
パターン入力装置２０１は、例えばオンライン文字認識ならば、デジタイザとペンを有し、デジタイザの上にペンによって入力された文字や図形の座標データをＣＰＵ２０３に渡す。このパターン入力装置は、デジタイザとペンに限らずこれから認識しようとするパターンが入力できるものならば、スキャナー（２値のパターンデータを入力）でもマイク（音声パターンを入力）でも何でもよい。表示装置２０２はパターン入力手段２０１より入力した生のパターンデータやＣＰＵ２０３が認識した結果を表示する。ＣＰＵ２０３は入力されたパターンの認識を行ったり、後述するフローチャートに示す処理等をメモリ２０４に格納されている制御プログラムに従って実行し、すべての装置の制御を行う。メモリ２０４はＣＰＵ２０３が使用する認識プログラムや辞書を記憶したり、入力されたパターンデータ、認識プログラムの使用する変数パラメータや認識処理中に生ずるデータ等を記憶する。
【００２１】
図１は、本実施例のパターン認識用の辞書作成方法、及びパターン認識方法をよく表す図画であり、１０１は「生の学習用パターン」、１０２は「生の学習用パターン」をニューラルネットに通す「階層化前処理ステップ」、１０３はニューラルネットで処理された後の「階層化された学習用パターン」、１０４は「階層化された学習用パターン」を元に分類木を作成する「分類木作成ステップ」、１０５は「分類木作成ステップ」が分類木を作成する過程で使用する「展開変数判別ステップ」、１０６は最終的な「分類木」である。
【００２２】
本実施例におけるインプットは「生の学習用パターン」であり、アウトプットは「分類木」である。
【００２３】
以下、図３から図７に基づいて、本発明の動きを詳細に述べる。
【００２４】
まず、入力パターンの種類（カテゴリー）としては、１６×１６のメッシュ上に書かれた「０」から「９」までの１０種の数字を想定する。「０」の１入力パターンを図５に示す。辞書作成用に入力する学習パターンは「０」から「９」まで各カテゴリーそれぞれ１００個存在すると仮定する。つまり、１つのカテゴリーに１００個のテンプレートが作成できることになる。これらの学習パターンから作成するテンプレートを、ＬＴｉ，ｊ（＝Ｌｅａｒｎｉｎｇ  Ｔｅｍｐｌａｔｅ  ｉ，ｊ）（ｉはカテゴリーを表すサフィックスで、０＜＝ｉ＜＝９の範囲の値をとる。ｊはテンプレートナンバーを示すサフィックスで、１＜＝ｊ＜＝１００の範囲の値をとる。）と名付ける。
【００２５】
以上の仮定の元に、図３に示すような４階層のニューラルネットワークが構成されることになる。図３の４階層はそれぞれ上から２×２、４×４、８×８、１６×１６個のニューロン群からできている。
【００２６】
本件に係わるパターン認識用辞書作成処理は図４のフローチャトに示すように、ニューラルネット展開フェーズ、分類木作成のフェーズの２段階のステップを経て実行される。以下、各フェーズを順に説明する。
【００２７】
（１）ニューラルネット展開フェーズ
まず、学習用テンプレートは図３の最下層の１６×１６個のニューロンとして入力される。この時、入力パターン（ＬＴｉ，ｊ）の白の部分はニューロンがＯＦＦで、黒の部分はニューロンがＯＮになると仮定する（以下の説明において、「黒」と「ニューロンのＯＮ」／「白」と「ニューロンのＯＦＦ」を同一視する）。
【００２８】
ニューラルネットの構造は極めて単純である。つまり、下の層のある２×２のニューロンの中で、ＯＮとなっているものが１つでもあれば、真上の層の対応する１つのニューロンはＯＮとなる。というルールで入力パターンを上の階層に向かって処理していく。図５に示すある一つの学習用テンプレートをニューラルネット展開処理し、第１層から第４層からなるニューラルネットを作成した結果を図６に示す。
【００２９】
結局、入力パターンの特徴空間は２５６次元の超立方格子（２２５６  ）をなしている。これが、第３層では２６４、第２層では２１６、第１層では２４  に縮退するわけである。
【００３０】
なお、このニューラルネットの構造＝ルールはこれに限ったものではない。
【００３１】
（２）分類木作成フェーズ
（１）のニューラルネット展開フェーズによって、学習用テンプレート（ＬＴｉ，ｊ）の全て（１０カテゴリ、各１００パターン）が、図３に示すようなニューラルネットに展開される。分類木の作成にはこのニューラルネットの展開とは逆に、上（第１層）から下（第４層）へ行われる。
【００３２】
ルートのノードは、図３の最上位の層（第１層、２×２）のさらに上に仮想的に存在するニューロンから始まる。
【００３３】
学習用テンプレート（ＬＴｉ，ｊ）を展開した結果、図３の最上位の層（２×２）のどれかはＯＮとなっている（真っ白い学習用テンプレートが存在しない限り最上位の層（２×２）は全てＯＦＦにはならない）。よって、全ての学習用テンプレート（ＬＴｉ，ｊ）に対して、仮想的に存在する最上位ニューロンの活動はＯＮとなっている。
【００３４】
最上位の層（２×２）の状態は２の４乗＝１６個存在するので（正確には、上記説明のように、全てＯＦＦの状態はないので、１５個）、ルートノードから１６本の枝が伸びることとなる（図７参照）。
【００３５】
この時、各枝に存在する学習用テンプレート（ＬＴｉ，ｊ）の数を数える。この結果によって、以後の処理が３つにわかれる。
▲１▼学習用テンプレート（ＬＴｉ，ｊ）が１つも存在しない場合
この場合は、その枝を削除する。
▲２▼学習用テンプレート（ＬＴｉ，ｊ）の中で、あるカテゴリー（例えば「１」）のテンプレートのみ存在する場合
この場合は、この枝が判断される場合はカテゴリーが唯一に定まるとして、この枝を葉とし、カテゴリーの番号（例えば「１」）を割り振る。
▲３▼上記１、２以外の場合＝複数カテゴリーのテンプレートが混合して存在する場合
【００３６】
この場合、この枝をノードとして、更に分類木作成を続ける。
【００３７】
図７にこの処理の結果を示す。枝の状態は、図３の最上位の層＝第１層のニューロンの発火状況を図示することによって示してある（黒はＯＮで、白はＯＦＦを表す）。
【００３８】
存在するカテゴリーの種類の欄が「×」となっている枝は、上記▲１▼学習用テンプレート（ＬＴｉ，ｊ）が１つも存在しない場合に相当し、削除される（なお、厳密には、全白のパターンは存在しないことが初めからわかっているので、一番左の枝はルートからは出ていない）。
【００３９】
左から８番目の枝は「１」のカテゴリーの学習用テンプレートしか存在しない。これは、上記▲２▼学習用テンプレート（ＬＴｉ，ｊ）の中で、あるカテゴリー（例えば「１」）のテンプレートのみ存在する場合に相当し、葉となる。
【００４０】
例えば、左から１２番目の枝には「２」「４」「５」「６」のカテゴリーの学習用テンプレートが存在し、上記▲３▼上記１、２以外の場合＝複数カテゴリーのテンプレートが混在して存在する場合に相当し、ノードとなる。
【００４１】
次に、このノードから枝を作成する方法について述べる。
【００４２】
ノードから枝を作成する際に、最も効率の良い枝の作成を行いたい。最も効率が良いとは、結局、枝を展開したときに、最も多くカテゴリーに関する情報が得られるということである。
【００４３】
仮にこのノードから展開する枝を、このノードにおいて、ＯＮとなっているニューロンを下の層に展開した枝に限ってみる。例えば、図７の左かに１２番目の枝の場合、図３の第１層における左上、右下の３つのニューロンの中から１つ選び、そのニューロンの下、つまり図３の第２層の下４つのニューロンの状態に関する枝の展開を行う。
【００４４】
こうすることによって、枝の展開に要する計算時間を大幅に削減できるし、このような制限をしても、本質的に分類木の分類性能に大きなダメージは与えない。
【００４５】
では次に、このノードにおいて、ＯＮとなっているニューロンの内で、展開したときに最も効率の良くなるニューロンを選ぶ方法を説明する。
【００４６】
あるノードに存在する学習用テンプレート（ＬＴｉ，ｊ）の中で、カテゴリー番号がｉである学習用テンプレートの数をＮｉで表し、このノードに存在する学習用テンプレートの総数をＮとすると、このノードにおけるそれぞれのカテゴリーの存在確率ｐｉはｐｉ＝Ｎｉ／Ｎで表される。なお
【００４７】
【外１】
0003630734.tif 000002
よって、このノードの情報が得られたときのエントロピーは、以下の式で表される。
【００４８】
【外２】
0003630734.tif 000003
【００４９】
次に、このノードにおいて、ＯＮとなっているニューロンの１つを選択して、そこから枝を展開したときのエントロピーの減少量を計算する。
【００５０】
上述の通り、１つのニューロンを下の層に向かって展開したときの枝の数は１６本である。この１６本の枝に学習用テンプレート（ＬＴｉ，ｊ）がどのように分布するかを、展開したときの枝に存在する学習用テンプレート（ＬＴｉ，ｊ）の数＝Ｎｉ，ｂで表す。Ｎｉ，ｂのｉはカテゴリー番号を示し、ｂは枝（ｂｒａｎｃｈ）の番号を示す。この時、それぞれの枝の情報が得られたときのエントロピーは、上の議論と同じく、
【００５１】
【外３】
0003630734.tif 000004
この式で、
【００５２】
【外４】
0003630734.tif 000005
は枝に存在する学習用テンプレート（ＬＴｉ，ｊ）の総数を表す。
【００５３】
それぞれの枝にいく確率は、
【００５４】
【外５】
0003630734.tif 000006
（Ｎは（１）式のＮと同じ）なので、結局、枝を展開したときの平均エントロピーは、
【００５５】
【外６】
0003630734.tif 000007
となる。
【００５６】
結局、エントロピーの平均減少数値は、
【００５７】
【外７】
0003630734.tif 000008
となる。
【００５８】
そして、この値を枝の数で割った値
【００５９】
【外８】
0003630734.tif 000009
が、枝を展開したときの分類効率を表すことになる。
【００６０】
この値が最高となるニューロンを選び、枝を展開していく。
【００６１】
なお、１つのニューロンのみを展開するのではなく、複数のニューロンのグループに関して枝を展開してもよい。
【００６２】
この場合、（５）式のＢｒａｎｃｈＮｕｍｂｅｒは、ニューロンの数×１６となる（厳密には展開する下の層のニューロンが全てＯＦＦということは有り得ないので、ＢｒａｎｃｈＮｕｍｂｅｒは、ニューロンの数×１５が正しい）。
【００６３】
また、本実施例においては、（５）式で表される値を枝を展開したときの分類効率を表す値として採用したが、例えば文献「Ｃｌａｓｓｆｉｃａｔｉｏｎ  ａｎｄ  Ｒｅｇｒｅｓｓｉｏｎ  Ｔｒｅｅｓ」に記載されている“Ｇｉｎｉ  ｃｒｉｔｅｒｉｏｎ”等の枝の展開効率を表す関数ならば（５）式に限らず何でもよい。
【００６４】
以上、展開するニューロン、またはニューロンの組みが決定されれば、それに従って、枝を展開し、葉及びノードを作成していく。そして、最後、全部、葉になったところで、分類木作成を完了する。
【００６５】
図８に実際作成された分類木の内容を示す。
【００６６】
図８は図７を詳しくしたもので、削除された枝は省いてある。図８の○で囲ってある枝は葉であることを示す。
【００６７】
葉以外の全ての枝はノードとなるので、更に深く枝の展開が行われるわけであるが、図８においては右から３番目のノードのみ、更なる枝の展開結果を図示した。右から３番目のノードは、「１」「７」「９」の３種類のカテゴリーが共存しており、枝の展開が必要となっている。ここで、この右から３番目のノードにおいて、第１層のどのニューロンを展開すべきかについて、「展開変数判別ステップ」が第１層の右上のニューロンという答を出したとする。すると、右上のニューロンの状態に関して、図７と同様に２４  ＝１６本の枝が展開され、上述の▲１▼〜▲３▼の条件に基づいてある枝は削除され、ある枝は葉となり、ある枝はノードとなる。
【００６８】
ノードとなった枝は更に枝を展開しなければならなく、最終的に全ての枝の末端は葉となる。
【００６９】
図８では、右から３番目のノードの展開結果を、簡単のため、第１層と第２層を重ね書きすることによって示して有る。実際は、図３に示したニューラルネットの第１層の４つのニューロンと第２層の右上４つのニューロンに、これらの状態が表現されている。
【００７０】
実際の認識処理は、以上の通り作成された分類木にそって、行ってもよいし、分類木で作成された葉をテンプレートの形にして行ってもよい。
【００７１】
〈実施例２〉
実施例１の（１）のニューラルネット展開フェーズにおいて、ニューラルネットの構造＝ルールを以下のように設定する。
【００７２】
「下の層の２×２のニューロンの中で、２個以上のニューロンがＯＮとなっていれば、真上の層の１つのニューロンはＯＮで、それ以外はＯＦＦ」。
【００７３】
この場合、必ずしも実施例１のようにＯＮとなっているニューロンのみが、情報が退化しているわけではない。よって、（２）分類木作成フェーズにおいて、ＯＦＦになっているニューロンも含めて、展開するターゲットとなるニューロンまたは、ニューロン群を選択しなくてはいけない。しかし、その方法は実施例１と全く同様に実施できる。
【００７４】
このように、ニューラルネット構造＝ルールに対する制限はほとんどなく、ある程度の連続性が保証されていればよい。
【００７５】
例えば、図７の枝の状態で説明すると、実施例１では下の４つのニューロンの状態が一番左の１つの場合ＯＦＦ、それ以外ＯＮとなるルールであり、本実施例では、左から５つ目までがＯＦＦ、それ以外ＯＮとなるルールである。
【００７６】
例えばここで、ＯＦＦとＯＮの境目を図７の状態並びの中で任意に設定しても、ルール＝写像の連続性は保証されているので、よいわけである。
【００７７】
【発明の効果】
以上説明したように、本発明によれば、高次元の特徴空間の中に分布するパターンを効率的にカテゴリー化し、分類木を作成できる。
【００７８】
以上説明したように、本発明によれば、実スケールのパターン分類問題が特別な特徴抽出、または、カテゴリー分離等の前処理をすることなく、容易に解けるようになるという効果がある。
【図面の簡単な説明】
【図１】本実施例のパターン認識用の辞書作成法を表す図。
【図２】本実施例の情報処理装置の構成を示すブロック図。
【図３】本実施例で使用するニューラルネットの構造図。
【図４】本実施例のパターン認識用辞書作成処理の流れを示すフローチャート。
【図５】学習用パターンの例示図。
【図６】階層化された学習用パターンの例示図。
【図７】本実施例の分類木作成過程を示す図。
【図８】本実施例の分類木の様子を示す図。
【図９】従来のニューラルネットの適用例を示す図。
【図１】
0003630734.tif 000010
【図２】
0003630734.tif 000011
【図３】
0003630734.tif 000012
【図４】
0003630734.tif 000013
【図５】
0003630734.tif 000014
【図６】
0003630734.tif 000015
【図７】
0003630734.tif 000016
【図８】
0003630734.tif 000017
【図９】
0003630734.tif 000018