JP2004164481A - 情報処理方法 - Google Patents

Abstract

【課題】任意の多値パターンを認識する。
【解決手段】学習データおよび重みベクトルの情報が学習サンプル抽出ステップに供給され、部分集合である学習サンプルが抽出される。学習サンプルの重みは、のパーフェクト・ラーナ作成ステップで使用され、重みベクトルを参照しつつ、学習サンプルからパーフェクト・ラーナを生成する。生成されたパーフェクト・ラーナに基づいて、重み更新ステップが実行される。重み更新ステップは、重みベクトルを更新し、さらに認識フェーズで使用するパーフェクト・ラーナ加重係数を決定する。
【選択図】 図１

Description

【０００１】
【発明が属する技術分野】
本発明は画像、文字、音声等のパターンを認識する際に使用するアルゴリズム及び辞書を作成する方法及び装置に関するものである。
【０００２】
【従来の技術】
従来、ＵＳＰ５，８１９，２４７（従来例１という。）に開示されているいわゆるブースティングアルゴリズムによれば、複数のパターン認識方法及び装置を組み合わせて、より高い性能のパターン認識方法及び装置を実現できる。この方法によれば、あまり性能の高くないパターン認識方法の性能を向上できる。例えば、パターン認識対象と若干の相関を持つ程度の認識結果を生成する認識方法を寄せ集めて、パターン認識対象に対する認識率を１００％まで改良し得る。
【０００３】
【発明が解決しようとする課題】
しかしながら、従来例１に開示されているブースティングアルゴリズムは、２値のパターン認識対象に限定されており、多値のパターン認識問題に適用したときに途中で学習がストップすることがあった。すなわち、従来例１は多値パターン認識問題一般には適用できなかった。
【０００４】
この問題を克服するために、多値パターン認識問題をより大きな２値パターン認識問題に埋め込み、新たに設定される２値パターン認識問題を解くことによって、元の多値パターン認識問題を解く方法（従来例２という。）も提案されていた。しかしながら、従来例２は、新たに設定される２値パターン認識問題が巨大になるという欠点があり、学習に非常に時間がかかってしまうという実行上の重大な欠点が存在した。
【０００５】
本発明はこのような従来の問題点を解消すべく創案されたもので、任意の多値パターンを認識することを目的とする。
【０００６】
【課題を解決するための手段】
本発明は、認識対象のパターンの特徴抽出結果を変数によって定義し、前記変数に対応した認識結果を多値（２値を含む）のラベルとし、前記変数と前記ラベルとの対の集合を学習データとし、前記学習データにおける前記変数から前記パターンを認識する情報処理方法であって、前記前記変数と前記ラベルとの対にそれぞれ重みの初期値を設定して、前記重みの集合を重みベクトルとする重みベクトル初期値設定ステップと、前記重みに基づいて、前記学習データから前記前記変数と前記ラベルとの対を抽出して学習サンプルを生成する学習サンプル抽出ステップと、前記学習サンプル抽出ステップによって抽出された前記学習サンプルと前記重みベクトルよりパーフェクト・ラーナ（Ｐｅｒｆｅｃｔ−Ｌｅａｒｎｅｒ）を作成するパーフェクト・ラーナ生成ステップと、前記パーフェクト・ラーナ生成ステップにより生成されたパーフェクト・ラーナを用いて、前記学習サンプルを認識する学習サンプル認識ステップと、前記学習サンプル認識ステップにおける誤認識率に基づいてパーフェクト・ラーナの加重係数を算出するとともに、前記重みベクトルを更新する重みベクトル更新ステップと、前記作成するパーフェクト・ラーナ生成ステップと、学習サンプル認識ステップとを繰り返し、前記各パーフェクト・ラーナによって認識されたラベルにパーフェクト・ラーナ加重係数を乗じた結果の合計を比較し、合計値が最大のラベルを認識結果とする。これによって、任意の多値パターンを認識し得る。
【発明の実施の形態】
次に本発明に係る情報処理方法の一実施形態を図面に基づいて説明する。
【０００７】
図１は、本発明に係る情報処理方法の一実施形態における学習フェーズの処理の流れを示す図、図２は、本発明に係る情報処理方法の一実施形態が実施される情報処理装置の構成を示すブロック図、図３は、本発明に係る情報処理方法の一実施形態における認識フェーズの処理の流れを示す図、図４は、図１の実施形態における各ラウンドで、パーフェクト・ラーナによって全学習パターンを認識させる様子を示した図、図５は、図１の重み更新ステップの処理およびパーフェクト・ラーナ加重計数算出の処理の流れを示すフローチャート、図６は、図１の学習サンプル抽出ステップの処理の流れを示すフローチャートである。
【０００８】
情報処理装置は、入力装置２０１、表示装置２０２、中央処理装置（ＣＰＵ）２０３、およびメモリ２０４を有する。
【０００９】
入力装置２０１は、例えばオンライン文字認識ならば、デジタイザとペンを有し、デジタイザの上にペンによって入力された文字や図形の座標データ、認識対象のパターンのデータをＣＰＵ２０３に渡す。入力装置２０１は、認識対象となるパターンを入力し得る任意の装置、例えばスキャナー、マイク等である。
【００１０】
表示装置２０２は、入力装置２０１に入力されたパターンのデータや、ＣＰＵ２０３が認識した結果を表示する。
【００１１】
ＣＰＵ２０３は、入力されたパターンの認識を行い、また入力装置２０１、表示装置２０２、メモリ２０４、その他全ての装置を制御する。
【００１２】
メモリ２０４は、ＣＰＵ２０３が使用する認識プログラムや辞書を保存し、さらには、入力されたパターンデータや、認識プログラムが使用する変数等を一次的に記録する。
【００１３】
図１は、本発明の情報処理方法および装置、特にその学習フェーズの様子を極めて適切に表現している。学習フェーズにおける入力は「学習データ」であり、出力は複数の「パーフェクト・ラーナ」および「パーフェクト・ラーナ加重係数」である。パーフェクト・ラーナは、日本語で言えば完全認識機と呼べるものであり、与えられた学習サンプルを完全に認識、分類する方法、装置、または、プログラムのことを意味する。
【００１４】
図１において、学習用に用意された全てのサンプルよりなる学習データ１０１が学習サンプル抽出ステップ１０２に渡される。学習データ１０１は、認識対象の入力パターンから特徴抽出した結果の変数と、認識結果としての「ラベル」とを対応させ、全てのパターンについての、変数とラベルとの対を集合としたものである。従来のブースティングアルゴリズムでは、「ラベル」が２値であったが、本発明では、２値を含む多値である。
【００１５】
学習サンプル抽出ステップ１０２には重みベクトル１０４の情報が供給され、学習サンプル抽出ステップ１０２は、重みベクトル１０４の情報に基づいて学習データ１０１全体から、部分集合である学習サンプル１０３を抽出する。学習サンプル抽出ステップ１０２の詳細については後述する。
【００１６】
重みベクトル１０４は、学習データ１０１を構成する全ての学習サンプル１０３に対して付加された重みの集合を示し、学習過程において、どんどん更新されていく。なお、初期値では学習データ１０１の重みは全て等しく設定される。また注意すべきことは、学習データ１０１から抽出される学習サンプル１０３は、それぞれにも重みが付加される。各学習サンプル１０３の重みは、次のパーフェクト・ラーナ作成ステップ１０５で使用される。
【００１７】
パーフェクト・ラーナ作成ステップ１０５は、重みベクトル１０４を参照しつつ、学習サンプル１０３からパーフェクト・ラーナ１０６を生成する。パーフェクト・ラーナ１０６は、与えられた学習サンプルを認識、分類する。
【００１８】
パーフェクト・ラーナ１０６を実現する学習アルゴリズムは、与えられた学習サンプルに対して１００％の認識性能を示すものであれば基本的には何でも良い。例えば、線形分離関数、ニューラルネット、ベイズ学習アルゴリズム、Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒマッチングアルゴリズム、Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ Ｍａｃｈｉｎｅなど、パターン認識アルゴリズムならば何でもよい。パターン認識アルゴリズムをまとめた文献としては、ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ ＭａｃｈｉｎｅＩｎｔｅｌｌｉｇｅｎｃｅのＶｏｌ． ２２ Ｎｏ．１ Ｊａｎ． ２０００”Ｓｔａｔｉｓｔｉｃａｌ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ：Ａ Ｒｅｖｉｅｗ” Ａｎｉｌ Ｋ． Ｊａｉｎ， Ｒｏｂｅｒｔ Ｐ． Ｗ． Ｄｕｉｎ， ａｎｄ Ｊｉａｎｃｈａｎｇ Ｍａｏがある。
【００１９】
なお、パターン認識アルゴリズムの中でも、本発明の手法にもっとも適した方法は、学習サンプルの重み付けが変わることによって生成されるパターン認識機が変化する、いわゆるＵｎｓｔａｂｌｅ認識アルゴリズムである。このようなアルゴリズムの１つとして分類木がある。分類木に関しては例えば文献ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎ ｏｎ Ｓｙｓｔｅｍ， Ｍａｎ， ａｎｄ ＣｙｂｅｒｎｅｔｉｃｓのＶｏｌ． ２１， Ｎｏ．３， Ｍａｙ／Ｊｕｎｅ １９９１“Ａ Ｓｕｒｖｅｙ ｏｆ Ｄｅｃｉｓｉｏｎ ＴｒｅｅＣｌａｓｓｉｆｉｅｒ Ｍｅｔｈｏｄｌｏｇｙ”Ｓ． Ｒａｓｏｕｌ Ｓａｆａｖｉａｎ ａｎｄ Ｄａｖｉｄ Ｌａｎｄｇｒｅｂｅに詳しく記述されている。
【００２０】
なお、分類木にブースティングアルゴリズムの手法を取り入れてより高性能なパターン認識アルゴリズムを作成する方法そのものは、公知であり、例えば文献「ブースティング入門」人工知能学会誌Ｖｏｌ．１４ Ｎｏ．５， Ｓｅｐｔ．１９９９ Ｙｏａｖ Ｆｒｅｕｎｄ ａｎｄ Ｒｏｂｅｒｔ Ｓｃｈａｐｉｒｅ、安倍 直樹訳に詳しい記述がある。ここに述べられているような従来の分類木にブースティングアルゴリズムの手法を取り入れる方法と、本発明の決定的な違いは、分類木がパーフェクト・ラーナに限定されている点である。これを実現するために、通常は分類木の学習に際して枝きりを行うところを本発明で使用する分類木アルゴリズムでは、枝きりを全く行わない。この処理によって、任意の学習サンプルに対してパーフェクト・ラーナを作成することができる。
【００２１】
パーフェクト・ラーナ作成ステップ１０５は、本発明の学習過程において、複数回実行される。１回のパーフェクト・ラーナ作成ステップ１０５を「ラウンド」という単位で呼ぶことが多く、例えば「全体で１００ラウンドの学習を行う」というような言い方をする。１００ラウンドの学習を行うと、１００個（１００種類）のパーフェクト・ラーナ１０６が生成される。
【００２２】
生成されたパーフェクト・ラーナ１０６に基づいて、重み更新ステップ１０７が実行される。重み更新ステップ１０７は、重みベクトル１０４を更新し、さらに認識フェーズで使用するパーフェクト・ラーナ加重係数を決定する。重み更新ステップ１０７もラウンド数の回数だけ実行される。
【００２３】
図３の認識フェーズにおいて、入力は“認識データ”であり、出力は “認識結果”である。
【００２４】
認識データ３０１は、認識対象のパターンから特徴抽出した結果を記述する変数よりなる。認識データ３０１は、学習データ１０１内の１つの変数・ラベル対においてラベルを除去したデータと同一フォーマットであり、ラベルが未知の学習データということができる。認識フェーズ３０１は、ラベルが未知の学習データにラベルを割り当てる。従って認識フェーズ３０１の認識結果３０５はラベルよりなる。
【００２５】
認識データ３０１はパーフェクト・ラーナ３０２（パーフェクト・ラーナ１０５と同一のものである。）に入力され、パーフェクト・ラーナ３０２はラベルを認識結果集計ステップ３０４に入力する。
【００２６】
認識結果集計ステップ３０４には、パーフェクト・ラーナ加重係数３０３（パーフェクト・ラーナ加重係数１０８と同一のものである。）が入力される。前述の通り、学習過程が１００ラウンドならば、パーフェクト・ラーナおよびパーフェクト・ラーナ加重係数は１００個ずつ存在する。
【００２７】
認識結果集計ステップ３０４は、学習フェーズで得られた全てのパーフェクト・ラーナ３０２によって得られたラベルにパーフェクト・ラーナ加重係数をかけて足し合わせた合計の中で多数決を行い、もっとも得票数の多かったラベルを認識結果３０５とする。
【００２８】
パーフェクト・ラーナ３０２は完全にラベルを決定するアルゴリズムなので、１つのパーフェクト・ラーナから得られる認識結果は完全に確定した１つのラベルである。よって、１００ラウンドの学習を行うと、１００個のラベルが得られ、これらに重み付けをした多数決で最終的なラベルが得られることとなる。
【００２９】
図４において、重み更新ステップ１０７では、まず全学習データに対して現在のラウンドのパーフェクト・ラーナを適用し、認識処理を実行する。図４には四角形の枠内に大きな円が描かれ、この円の内部に小さな円が描かれている。四角形は認識対象となり得る全てのデータを示し、大きな円は全学習データ１０１、小さな円は抽出された学習サンプル１０３を示す。四角形は２つの領域（左側の左下りハッチングの領域と、右側の右下りハッチングの領域）に分割され、これにともなって全学習データ１０１も２つの領域に分割される。小さな円弧で示された学習サンプル１０３は、左側の左下りハッチングの領域に含まれる。左側の左下りハッチングの領域は認識に成功する学習データの領域であり、右側の右下りハッチングの領域は認識に失敗する学習データの領域である。
【００３０】
図１のパーフェクト・ラーナ作成ステップ１０５では、抽出された学習サンプル１０３をパーフェクト・ラーナ１０６に学習させるので、その結果生成されたパーフェクト・ラーナ１０６によって全学習データを認識させると、現在のラウンドで抽出された学習サンプル１０３は認識に成功する集合に完全に含まれる。一方、全学習データ１０１から抽出されなかった学習サンプル１０３の中には、認識に失敗する学習サンプルも含まれる。
【００３１】
図５において、重み更新ステップ１０７は以下の各ステップにより実行される。
【００３２】
ステップＳ５０１： 全学習データに対するパーフェクト・ラーナの認識結果における誤認識率「ｅ」を求める。誤認識率「ｅ」は、「誤認識した学習サンプルの重みを足し合わせたもの」を「全学習サンプルの重みの合計」で除算した値である。
【００３３】
ステップＳ５０２：重みベクトル、つまり全学習データの重みを更新する。その方法は、認識に失敗した学習サンプルの重みを｛（１−ｅ）／ｅ｝倍する。この値は、現在のラウンドのパーフェクト・ラーナの性能が高く、誤認識率が低ければ低いほど大きくなる。
【００３４】
ステップＳ５０３：ステップＳ５０１、Ｓ５０２の更新方法だと、重みが単調に増加して、処理可能は数値の上限を超える可能性がある。そこで、計算機等に実装する場合は、ラウンド毎に重みの合計が「１」になるように正規化する等の処理を行う。このような正規化を採用する場合、最初のラウンドの重みベクトルは、「１」を全学習データのサンプル数で割った数とする。
【００３５】
ステップＳ５０２に関して、認識に失敗した学習サンプルの重みに対する乗数を｛（１−ｅ）／ｅ｝としたが、実際の学習においては、厳密にこの値にする必要はなく、定性的に認識性能の高いパーフェクト・ラーナで誤認識したサンプルの重みを多くする方法であれば、本発明のアルゴリズムは十分機能する。但し、次に述べるパーフェクト・ラーナ加重係数とは異なり、全く重みを変更しないと良い結果が得られない。
【００３６】
ステップＳ５０４：図１のパーフェクト・ラーナ加重係数１０８を算出する。パーフェクト・ラーナ加重計数は誤認識率ｅの関数であり、｛ｌｏｇ（１−ｅ）−ｌｏｇ（ｅ）｝によって算出される。パーフェクト・ラーナ加重計数は、誤認識率ｅが小さければ小さいほど大となり、よって、パーフェクト・ラーナの性能が高ければ高いほど、加重平均の得票貢献は高くなることとなる。実際の学習においては、パーフェクト・ラーナ加重計数も厳密にこの式に従う必要はなく、定性的にパーフェクト・ラーナの性能が高ければ高い値になる式を用いても十分アルゴリズムは機能する。極端な場合、全てのパーフェクト・ラーナに対して加重係数を同じにしても、本発明のアルゴリズムは十分機能する。
【００３７】
なお、非常にまれではあるが、抽出された学習サンプルで学習させたパーフェクト・ラーナが全学習データに対して完全な認識性能を示す場合がある。この場合は、これまで述べてきた式が全てオーバーフローする。この場合は、学習フェーズは終了させることも可能であるし、誤認識率ｅを非常に小さい値に摩り替えて、パーフェクト・ラーナ加重係数の導出を行っても良い。なお、誤認識率ｅを非常に小さい値に摩り替えた場合は、誤認識をする学習データは存在しないので、重みベクトルは更新されない。
【００３８】
図６において、学習サンプル抽出ステップ１０２では、誤認識率ｅを所定値以下に抑えるように配慮しつつ、学習データを選択する。
【００３９】
図５の重み更新ステップで説明したとおり、誤認識率ｅは「誤認識したサンプルの重みの合計」を「全サンプルの重みの合計」で除算した値であるが、従来のブースティングアルゴリズムでは誤認識率ｅは１／２より小さいことが必須条件である。学習サンプル抽出ステップ１０２においても、誤認識率ｅ＜１／２の条件を満足するため、以下のステップを実行する。
【００４０】
ステップＳ６０１：学習サンプル抽出個数Ｓｎを設定する。
【００４１】
ステップＳ６０２：ステップＳ６０１で設定された個数の学習サンプルを学習データからランダムに抽出する。
【００４２】
ステップＳ６０３：「抽出したサンプルの重みの合計」を「全サンプルの重みの合計」で割った値が（１／２）を超えるか否か判断する。「抽出したサンプルの重みの合計」を「全サンプルの重みの合計」で割った値が（１／２）を超えるときはそのまま処理を終了し、「抽出したサンプルの重みの合計」を「全サンプルの重みの合計」で割った値が（１／２）を超えないときはステップＳ６０２に戻る。
【００４３】
図４からもわかるように、誤認識するサンプルの重みの合計は、必ず、認識に成功するサンプルの重みの合計より小さくなり、「誤認識したサンプルの重みの合計」を「全サンプルの重みの合計」で除算した値で計算される誤認識率ｅは１／２より小さい。
【００４４】
また本発明の趣旨と範囲は、本発明の特定の説明と図に限定されるものではなく、本願特許請求の範囲に述べられた内容の様々な修正および変更に及ぶことは当業者にとって理解されるであろう。
【００４５】
本発明の実施形態の例を以下に示す。
［実施形態１］
認識対象のパターンをカテゴリーに分類する情報処理方法において、学習データより重みベクトルを用いて学習サンプルをランダムに抽出する学習サンプル抽出ステップと、前記学習サンプル抽出ステップによって抽出された学習サンプルと重みベクトルよりパーフェクト・ラーナ（Ｐｅｒｆｅｃｔ−Ｌｅａｒｎｅｒ）を作成するパーフェクト・ラーナ作成ステップと、前記パーフェクト・ラーナ作成ステップにより作成されたパーフェクト・ラーナを用いて前記学習データを認識することによって重みベクトルを更新し、かつ、パーフェクト・ラーナの加重係数を決定する重み更新ステップと、を備えた情報処理方法。
［実施形態２］
実施形態１に記載の方法によって生成された複数のパーフェクト・ラーナの認識結果を前記重み更新ステップで求めたパーフェクト・ラーナ加重係数で重み付けし多数決を取ることによって最終的な認識結果を得ることを特徴とする情報処理方法。
［実施形態３］
前記パーフェクト・ラーナは分類木を用いて実現することを特徴とする実施形態１または２に記載の情報処理方法。
［実施形態４］
実施形態１に記載の学習サンプル抽出ステップにおいて、抽出する学習サンプルの確率の総和が１／２を超えることを特徴とする請求項１〜３に記載の情報処理方法。
［実施形態５］
前記重み更新ステップにおいて、最新のパーフェクト・ラーナで前記学習データを認識した結果、認識に失敗した学習パターンの重みを増すことを特徴とする実施形態１乃至４のいずれかに記載の情報処理方法。
［実施形態６］
前記重み更新ステップにおいて、最新のパーフェクト・ラーナで前記学習データを認識した結果、誤認識率がｅとして、そのパーフェクト・ラーナの加重係数を｛ｌｏｇ（１−ｅ）−ｌｏｇ（ｅ）｝の定数倍とすることを特徴とする実施形態１乃至５のいずれかに記載の情報処理方法。
【００４６】
【発明の効果】
本発明によれば、任意の多値パターンを認識し得る。
【図面の簡単な説明】
【図１】本発明に係る情報処理方法の一実施形態における学習フェーズの処理の流れを示す図である。
【図２】本発明に係る情報処理方法の一実施形態が実施される情報処理装置の構成を示すブロック図である。
【図３】本発明に係る情報処理方法の一実施形態における認識フェーズの処理の流れを示す図である。
【図４】図１の実施形態における各ラウンドで、パーフェクト・ラーナによって全学習パターンを認識させる様子を示した図である。
【図５】図１の重み更新ステップおよびパーフェクト・ラーナ加重計数算出の処理の流れを示すフローチャートである。
【図６】図１の学習サンプル抽出ステップの処理の流れを示すフローチャートである。
【符号の説明】
１０１ 学習データ
１０２ 学習サンプル抽出
１０３ 学習サンプル
１０４ 重みベクトル
１０５ パーフェクト・ラーナ生成
１０６ パーフェクト・ラーナ
１０７ 重み更新
１０８ パーフェクト・ラーナ加重計数

Claims (1)

1. 認識対象のパターンの特徴抽出結果を変数によって定義し、前記変数に対応した認識結果を多値（２値を含む）のラベルとし、前記変数と前記ラベルとの対の集合を学習データとし、前記学習データにおける前記変数から前記パターンを認識する情報処理方法であって、
   前記前記変数と前記ラベルとの対にそれぞれ重みの初期値を設定して、前記重みの集合を重みベクトルとする重みベクトル初期値設定ステップと、
   前記重みに基づいて、前記学習データから前記前記変数と前記ラベルとの対を抽出して学習サンプルを生成する学習サンプル抽出ステップと、
   前記学習サンプル抽出ステップによって抽出された前記学習サンプルと前記重みベクトルよりパーフェクト・ラーナ（Ｐｅｒｆｅｃｔ−Ｌｅａｒｎｅｒ）を作成するパーフェクト・ラーナ生成ステップと、
   前記パーフェクト・ラーナ生成ステップにより生成されたパーフェクト・ラーナを用いて、前記学習サンプルを認識する学習サンプル認識ステップと、
   前記学習サンプル認識ステップにおける誤認識率に基づいてパーフェクト・ラーナの加重係数を算出するとともに、前記重みベクトルを更新する重みベクトル更新ステップと、
   前記作成するパーフェクト・ラーナ生成ステップと、学習サンプル認識ステップとを繰り返し、前記各パーフェクト・ラーナによって認識されたラベルにパーフェクト・ラーナ加重係数を乗じた結果の合計を比較し、合計値が最大のラベルを認識結果とする情報処理方法。

Images