(57)【特許請求の範囲】
【請求項１】
トレーニングサンプルあるいは認識すべきサンプルから特徴ベクトルを抽出する特徴ベクトル抽出ステップと、
前記特徴ベクトル抽出ステップにより抽出された前記トレーニングサンプルの特徴ベクトルからなるトレーニングサンプルセットに基づいて学習し、複数のスパースサポートベクターマシン分類器を得るトレーニングステップと、
前記スパースサポートベクターマシン分類器ごとに、前記特徴ベクトル抽出ステップにより抽出された認識すべきサンプルの特徴ベクトルに対する出力を計算し、前記認識すべきサンプルと対応するパターンを決定する認識ステップと、
を含み、
前記トレーニングステップでは、前記スパースサポートベクターマシン分類器の目標関数に０-ノルム正則化項を導入することにより前記スパースサポートベクターマシン分類器の決定関数におけるサポートベクトルの数を減少させること、
を特徴とするパターン認識方法。
【請求項２】
前記スパースサポートベクターマシン分類器は二クラススパースサポートベクターマシン分類器であり、前記トレーニングステップは、多クラストレーニングサンプルセットから二クラストレーニングサンプルセットを構成するステップをさらに含むことを特徴とする請求項１に記載のパターン認識方法。
【請求項３】
前記トレーニングステップはさらに前記スパースサポートベクターマシン分類器ごとにSigmoid関数をフィッティングするステップを含み、前記認識ステップはさらに前記Sigmoid関数により前記スパースサポートベクターマシン分類器の出力に基づいて二クラスの認識事後確率を計算するステップを含み、前記認識ステップはさらに前記二クラスの認識事後確率から多クラスの認識事後確率を計算するステップを含み、前記認識ステップでは前記多クラスの認識事後確率に基づいて前記認識すべきサンプルと対応するパターンを決定することを特徴とする請求項１に記載のパターン認識方法。
【請求項４】
前記トレーニングステップでは前記スパースサポートベクターマシン分類器の決定関数をトレーニングサンプルのカーネル項と偏差項との線形結合式として設定し、展開係数を実数として設定することを特徴とする請求項２に記載のパターン認識方法。
【請求項５】
前記トレーニングステップでは、繰り返し回数、係数ベクトル、解ベクトルを初期化すること、係数ベクトルにおけるすべての非零要素を検索し、対角行列を計算すること、正則化されたカーネル行列を再計算すること、前記スパースサポートベクターマシンと対応する２次計画問題を求解し、解ベクトルから係数ベクトルを計算すること、終了条件を満足しているかどうかを判断し、満足していないと判断される場合、非零要素を検索する処理に戻り、また、満足すると判断される場合、決定関数の偏差項を計算し、決定関数を出力すること、を繰り返し実行することによって、前記スパースサポートベクターマシン分類器の最適化をすることを特徴とする請求項４に記載のパターン認識方法。
【請求項６】
トレーニング文字画像あるいは認識すべき文字画像から特徴ベクトルを抽出する特徴ベクトル抽出手段と、
前記特徴ベクトル抽出手段により抽出された前記トレーニング文字画像の特徴ベクトルからなるトレーニングサンプルセットに基づいて学習し、複数のスパースサポートベクターマシン分類器を得るトレーニング手段と、
前記トレーニング手段によるトレーニング結果を記憶する記憶手段と、
前記スパースサポートベクターマシン分類器ごとに、前記特徴ベクトル抽出手段により抽出された認識すべき文字画像の特徴ベクトルに対する出力を計算し、前記認識すべき文字画像と対応する文字を決定する認識手段と、を備え、
前記トレーニング手段は、前記スパースサポートベクターマシン分類器の目標関数に０-ノルム正則化項を導入することにより前記スパースサポートベクターマシン分類器の決定関数におけるサポートベクトルの数を減少させること、
を特徴とする文字認識装置。
【請求項７】
前記スパースサポートベクターマシン分類器は二クラススパースサポートベクターマシン分類器であり、前記トレーニング手段は、多クラストレーニングサンプルセットから二クラストレーニングサンプルセットを構成するサンプルセット生成手段をさらに備えたことを特徴とする請求項６に記載の文字認識装置。
【請求項８】
前記トレーニング手段はさらに前記スパースサポートベクターマシン分類器ごとにSigmoid関数をフィッティングし、前記認識手段はさらに前記Sigmoid関数により前記スパースサポートベクターマシン分類器の出力に基づいて二クラスの認識事後確率を計算し、前記認識手段は前記二クラスの認識事後確率から多クラスの認識事後確率を計算する確信度手段をさらに備え、前記認識手段は前記多クラスの認識事後確率に基づいて前記認識すべき文字画像と対応する文字を決定することを特徴とする請求項６に記載の文字認識装置。
【請求項９】
前記トレーニング手段は前記スパースサポートベクターマシン分類器の決定関数をトレーニングサンプルのカーネル項と偏差項の線形結合式として設定し、展開係数を実数として設定することを特徴とする請求項７に記載の文字認識装置。
【請求項１０】
前記トレーニング手段は、繰り返し回数、係数ベクトル、解ベクトルを初期化すること、係数ベクトルにおけるすべての非零要素を検索し、対角行列を計算すること、正則化されたカーネル行列を再計算すること、前記スパースサポートベクターマシンと対応する２次計画問題を求解し、解ベクトルから係数ベクトルを計算すること、終了条件を満足しているかどうかを判断し、満足していないと判断される場合、非零要素を検索する処理に戻り、また、満足すると判断される場合、決定関数の偏差項を計算し、決定関数を出力すること、を繰り返し実行することによって、前記スパースサポートベクターマシン分類器の最適化をすることを特徴とする請求項９に記載の文字認識装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は光学式文字認識（Optical Character Recognition，OCR）に関する。特に、高速かつ高い精度で小さい文字セット（例えば、「０」〜「９」の１０個数字だけを対象とする「手書き数字認識」、又は、「a」、…、「z」、「A」、…、「Z」の５２個のアルファベットだけを対象とする「印刷体の英文字認識」）を認識する方法および装置に関する。
【背景技術】
【０００２】
光学式文字認識が多くの領域の中で広く利用されている。いわゆる光学式文字認識は、書類、新聞雑誌、本、原稿及びその他の印字されたものにおける文字を、スキャナなど光学的入力手段により読み取って画像情報に変換し、さらに、文字認識手段によりこの画像情報をコンピュータに使えるデータに変換する。
【０００３】
文字認識においては、あらかじめ認識用辞書を用意しておく必要がある。そして、パターン認識により画像が辞書の中のどのパターンと最もマッチするかを決定し、それによって該当する文字を認識する。
【０００４】
従来、文字認識の領域においては、テンプレートマッチング法、弾性テンプレートマッチング法、k-最近傍法、混合ガウスモデル法、ニューラルネットワーク法及びサポートベクターマシン（Support Vector Machine，SVM）などの種々なパターン認識方法が提案されている。その中で、サポートベクターマシンは統計学習に基づく方法であり（非特許文献１を参照）、現在文字認識の最も良い方法の１つであると考えられる（非特許文献２を参照）。
【０００５】
サポートベクターマシンには主に３つの特徴がある。１つ目の特徴は、非線型分類問題に対処することができることである。サポートベクターマシンは異なるカーネル関数を採用することができる。つまり、線形カーネルを採用すれば、線形分類器となり、２次多項式のカーネルを採用すれば、２次分類器となり、ガウスカーネルを採用すれば、動径基底（Radial Basis）分類器となる。
【０００６】
２つ目の特徴は、小さい規模の標本の高次元データを処理することができることである。文字認識において、正規化された階調あるいは二値画像を入力ベクトルとして扱う。
【０００７】
３つ目の特徴は、良い汎用性を具備することである。サポートベクターマシンは、トレーニング誤差を最小化するとともに、マージンを最大化する。そして分類器の分類誤り率を低く抑えることを前提として、境界面の複雑度をできるだけ小さくし、汎用性を高める。
【０００８】
ところで、サポートベクターマシンと、k-最近傍法、ニューラルネットワーク法などの従来の方法とを比べると、認識速度がかなり遅いという欠点がある。サポートベクターマシンの処理時間は、サポートベクターの数と比例している。一般には、サポートベクターの数が非常に大きい。特に、文字のトレーニングサンプルの数が大きく、一部分の文字クラスの分布が重なる場合は、認識速度が非常に遅くなる。
【０００９】
テキストスキャン認識などリアルタイム性を高く要求される応用においては、光学式文字認識に高い識別精度が求められるばかりでなく、認識速度の速さも要求されている。そこで、サポートベクターマシン分類器を使う光学式文字認識装置の認識速度を向上させるために、簡易化セット（トレーニングサンプルセットの一つのサブセット）のカーネル関数項の線形結合式により、サポートベクターマシン決定関数を近似する方法（非特許文献３と非特許文献４を参照）が提案されている。
【００１０】
しかし、このような方法は、サポートベクターマシンのトレーニング結果を対象としたポスト処理であり、決定関数の近似であるので認識速度は速くなるが、その代わりサポートベクターマシン分類器の分類性能が部分的に損なわれる。
【００１１】
【非特許文献１】V. Vapnik, The Nature of Statistical Learning Theory, Springer Verlag, 1995
【非特許文献２】C. Cortes, V. Vapnik. Support vector networks. Machine Learning, 20 (1995) 273-297
【非特許文献３】C. J. C. Burges, Simplified Support Vector Decision Rules. International Conference on Machine Learning, ICML, Bari, Italy, 1996, 71-77
【非特許文献４】B. Scholkopf, S. Mika, et al., Input Space Versus Feature Space in Kernel Based Methods. IEEE Trans. on Neural Networks, 10 (1999) 1000-1017
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明は上記問題点に鑑みてなされたものである。本発明は、認識速度が速く、かつ、認識精度が優れる光学式文字認識装置及びその方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明の目的を達成するために、次のような実施案を提供する。
【００１４】
パターン認識方法の一観点によれば、トレーニングサンプルあるいは認識すべきサンプルから特徴ベクトルを抽出する特徴ベクトル抽出ステップと、
前記特徴ベクトル抽出ステップにより抽出された前記トレーニングサンプルの特徴ベクトルからなるトレーニングサンプルセットに基づいて学習し、複数のスパースサポートベクターマシン分類器を得るトレーニングステップと、
前記スパースサポートベクターマシン分類器ごとに、前記特徴ベクトル抽出ステップにより抽出された認識すべきサンプルの特徴ベクトルに対する出力を計算し、前記認識すべきサンプルと対応するパターンを決定する認識ステップと、
を含み、
前記トレーニングステップでは、前記スパースサポートベクターマシン分類器の目標関数に０-ノルム正則化項を導入することにより前記スパースサポートベクターマシン分類器の決定関数におけるサポートベクトルの数を減少させる。
【００１５】
文字認識装置の一観点によれば、トレーニング文字画像あるいは認識すべき文字画像から特徴ベクトルを抽出する特徴ベクトル抽出手段と、
前記特徴ベクトル抽出手段により抽出された前記トレーニング文字画像の特徴ベクトルからなるトレーニングサンプルセットに基づいて学習し、複数のスパースサポートベクターマシン分類器を得るトレーニング手段と、
前記トレーニング手段によるトレーニング結果を記憶する記憶手段と、
前記スパースサポートベクターマシン分類器ごとに、前記特徴ベクトル抽出手段により抽出された認識すべき文字画像の特徴ベクトルに対する出力を計算し、前記認識すべき文字画像と対応する文字を決定する認識手段と、を備え、
前記トレーニング手段は、前記スパースサポートベクターマシン分類器の目標関数に０-ノルム正則化項を導入することにより前記スパースサポートベクターマシン分類器の決定関数におけるサポートベクトルの数を減少させる。
【００１６】
文字認識方法の一観点によれば、トレーニング文字画像あるいは認識すべき文字画像から特徴ベクトルを抽出する特徴ベクトル抽出ステップと、
前記特徴ベクトル抽出ステップにより抽出された前記トレーニング文字画像の特徴ベクトルからなるトレーニングサンプルセットに基づいて学習し、複数のスパースサポートベクターマシン分類器を得るトレーニングステップと、
前記スパースサポートベクターマシン分類器ごとに、前記特徴ベクトル抽出ステップにより抽出された認識すべき文字画像の特徴ベクトルに対する出力を計算し、前記認識すべき文字画像と対応する文字を決定する認識ステップと、
を含み、
前記トレーニングステップでは、前記スパースサポートベクターマシン分類器の目標関数に０-ノルム正則化項を導入することにより前記スパースサポートベクターマシン分類器の決定関数におけるサポートベクトルの数を減少させる。
【００１７】
コンピュータプログラムの一観点によれば、トレーニング文字画像や認識すべき文字画像から特徴ベクトルを抽出する特徴ベクトル抽出ステップと、
前記特徴ベクトル抽出ステップにより抽出された前記トレーニング文字画像の特徴ベクトルからなるトレーニングサンプルセットに基づいて学習し、複数のスパースサポートベクターマシン分類器を得るトレーニングステップと、
前記スパースサポートベクターマシン分類器ごとに、前記特徴ベクトル抽出ステップにより抽出された認識すべき文字画像の特徴ベクトルに対する出力を計算し、前記認識すべき文字画像と対応する文字を決定する認識ステップと、
を含み、
前記トレーニングステップでは、前記スパースサポートベクターマシン分類器の目標関数に０-ノルム正則化項を導入することにより前記スパースサポートベクターマシン分類器の決定関数におけるサポートベクトルの数を減少させる文字認識方法をコンピュータに実行させる。
【発明の効果】
【００１８】
本明細書に開示された方法、装置、プログラムによれば、スパースサポートベクターマシーンを認識に使われ、目標関数に０-ノルム正則化項を導入することにより、決定関数におけるサポートベクトルの数を減少させる。
【００１９】
スパースサポートベクターマシーンはサポートベクターマシーンの改良されたものである。依然として最大マージンクラスタリングを採用されるので、境界面関数の複雑度が低く、良い汎用性を持つ。それに、スパースサポートベクターマシーンのサポートベクトルは学習によりトレーニングセット全体から選択されたものであり、サポートベクトルに冗長性が存在しないので、その数が極めて少ない。なお、サポートベクトルの数が極めて少ないため、スパースサポートベクターマシンの決定関数の計算が簡単になり、速度が従来のサポートベクターマシンに比べ大きく向上される。
【発明を実施するための最良の形態】
【００２０】
以下の詳しい説明と図面により、本発明の特徴とメリットを一層理解することができる。また、図面に示す要素・特徴は、その他の図面に示す要素・特徴と組み合わせることが可能である。また、すべての図面において、同じまたは類似の符号は同じまたは類似の要素を指す。以下、図面を参照しながら本発明の具体的な実施例を説明する。
【実施例１】
【００２１】
図１は、本発明の実施例１にかかる文字認識装置１０の概略ブロック図である。図１に示すように、本発明の実施例１にかかる文字認識装置１０は、入力装置２０と出力装置３０とに接続されている。
【００２２】
入力装置２０は、トレーニングサンプルとしての文字画像あるいは認識すべき文字画像を文字認識装置１０に入力するものであり、スキャナなどの画像読み取り装置であってもよいし、手書きパネルなどの手書き入力装置、あるいは磁気ディスクなどの画像記録媒体のドライブインタフェースであってもよい。
【００２３】
文字認識装置１０は、入力装置２０により入力されたトレーニングサンプルとしての文字画像に基づいて学習を行い、複数のスパースサポートベクターマシン分類器を得る。これら複数のスパースサポートベクターマシン（sparse support vector machine: SSVM）分類器によって、入力装置２０により入力された認識すべき文字画像を認識し、この認識すべき文字画像に該当する文字を決定する。
【００２４】
文字認識装置１０の認識結果は、出力装置３０により利用者に出力される。出力装置３０は例えばディスプレイ、記憶媒体のドライブインタフェースであってもよいし、手書き入力装置のインタフェースであってもよい。
【００２５】
文字認識装置１０は、入力された文字画像を正規化処理し、正規化された文字画像に対して特徴を抽出する特徴ベクトル抽出部１１と、トレーニングサンプルセットに基づいて複数のスパースサポートベクターマシン分類器を学習して得るトレーニング部１２と、各SSVMの決定関数
【数１】
0005176773.tif 000002
、すなわち、カーネル関数
【数２】
0005176773.tif 000003
、サポートベクトル
【数３】
0005176773.tif 000004
、対応係数αiおよび偏差項bを記憶する記憶部１３と、記憶部１３に記憶されたトレーニング結果に基づいて、SSVM決定関数ごとに認識すべき文字画像の出力値を得、この出力値に基づいて認識すべき文字画像と対応する文字を決定する認識部１４と、を含む。ここで、文字認識装置１０は、適当に組まれたプログラムを実行するCPUで構成される。
【００２６】
以下、「０」〜「９」の１０個の数字の認識を例として、図２により、文字認識装置１０の各部による処理を詳しく説明する。
【００２７】
図２は、実施例１にかかる文字認識装置１０による処理を概略的に示すフローチャートである。図２において、左側半分はトレーニングのプロセスを示す。右側半分は認識のプロセスを示す。ただし、トレーニングのプロセスと認識のプロセスに関して、文字画像正規化処理と特徴抽出処理は共通のものである。
【００２８】
まず、トレーニングのプロセスについて説明する。図２に示すように、ステップ２０１では、特徴ベクトル抽出部１１は文字画像を正規化する。詳しく言えば、特徴ベクトル抽出部１１は、文字画像を含む最小の四角形の範囲を検索する。そして、検索された四角形の範囲の横縦比率を保持しながら、双線形補間によって四角形の範囲内の文字画像を所定のサイズ（たとえば、ｎ×ｎ）に正規化する。そして、正規化された文字画像を(ｎ＋２)×(ｎ＋２)の空白画像の中心に配置する。
【００２９】
つぎに、ステップ２０２では、特徴ベクトル抽出部１１は正規化された文字画像の文字特徴を抽出する。詳しく言えば、以下の処理を含む。まず、画像筆画画素を垂直方向に投影し、水平ヒストグラムを得て、この水平ヒストグラムをｍ個の列に等分する。また、画像筆画画素を水平方向に投影し、垂直ヒストグラムを取得し、この垂直ヒストグラムをｍ個の行に等分する。そうすると、ｍ×ｍ個のサイズが異なるセルが得られる。
【００３０】
そして、文字画像全体のチェインコードを取得し、各チェインコードにおける方向を求める。なお、求める方向は８種類のあり得る方向中の一つの方向である。そして、セルごとに８種類の方向でのチェインコードの数を積算し、最終的に８×ｍ×ｍ次元の文字特徴ベクトルが取得される。
【００３１】
トレーニング文字画像ごとに、１つのクラスラベル(０,１,…,９のいずれか)を設定しておく。抽出される特徴ベクトルをｘ、設定されるクラスラベルをｙとすると、該当文字画像は１つの入力出力対(x,y)と対応付けられる。複数のトレーニング文字画像の入力出力対で、トレーニング集合{(x1, y1), (x2, y2), …, (xl,yl)}、すなわち多クラスサンプルトレーニングセット
【数４】
0005176773.tif 000005
を構成する。ただし、
【数５】
0005176773.tif 000006
は特徴ベクトルであり、
【数６】
0005176773.tif 000007
はクラス番号であり、lは総トレーニングサンプル数である。
【００３２】
ステップ２０３では、トレーニング部１２が、多クラスサンプルトレーニングセットから二クラスサンプルトレーニングセットを構成する。「一対一」というルールを適用する場合、(‘0',‘1’), …, (‘0’,‘9’), (‘1’,‘2’), …, (‘8’,‘9’)のように
【数７】
0005176773.tif 000008
種類のあり得るケースにおける二クラスサンプルトレーニングセットを考える必要がある。
【００３３】
まず、４５個のサッブセット
【数８】
0005176773.tif 000009
（ただし、i = 0, …, 8，j = 1, …, 9）を抽出し、その後、すべてのサッブセットに対してクラス番号を yk = i から yk = +１に書き換え、クラス番号 yk = j を yk = -１ に書き換える。
【００３４】
また、「一対多」というルールを適用する場合に、(‘0’, 非‘0’), (‘1’, 非‘1’), …, (‘9’, 非‘9’)の１０種類のあり得るケースにおける二クラスサンプルトレーニングセットを考える必要がある。
【００３５】
すなわち、
【数４】
0005176773.tif 000010
において、クラス番号がiであれば +１ に書き換え、iでなければ -１ に書き換える。ただし、i = 0, …, 9である。
【００３６】
つぎに、ステップ２０４では、トレーニング部１２は、以上に示す複数のケースごとに、二クラスサンプルトレーニングセットに基づいて１つのスパースサポートベクターマシン（SSVM）分類器を学習により得る。
【００３７】
そして、ステップ２０５では、全部のケースについて、トレーニングが完成したがどうかを判断する。完成したと判断される場合、トレーニングを終了し、つぎのステップ２０６において、トレーニング結果を記憶部１３に出力して保存する。完成していないと判断される場合、ステップ２０３に戻って、つぎのケースに関する処理に進む。
【００３８】
つぎに、文字認識プロセスについて概略的に説明する。まず、ステップ２０７とステップ２０８では、特徴ベクトル抽出部１１は、認識すべき文字画像を正規化して、特徴ベクトルを抽出する。ステップ２０７、２０８の処理はステップ２０１、２０２の処理とまったく同じであるため、詳しい説明を省略する。
【００３９】
ステップ２０９では、認識部１４は、当該特徴ベクトルの全部のSSVM分類器における出力値を計算し、それによって認識すべき文字画像と最もマッチしている文字を決定する。
【００４０】
具体的に言えば、「一対一」というルールを適用する場合、投票法（多数決）を採用する。このときSSVM分類器の数が多いので、二クラス分類器ごとの出力に基づいて、対応文字に対して投票する。そして、文字ごとに投票数を積算し、投票数が最も多い文字を当該認識すべき文字画像の対応文字として決定する。
【００４１】
これに対して、「一対多」というルールを適用する場合、最大出力法を採用する。このとき、SSVM分類器の数は文字セット中の文字数に等しい。認識部１４は、どのSSVMの出力が最大かを判断し、出力値が最大となるSSVM分類器に対応する文字を当該認識すべき文字画像の対応文字として決定する。
【００４２】
本発明の文字認識においては、スパースサポートベクターマシン（SSVM）分類器が採用されるので、決定関数がきわめて少ない数のサポートベクトルで済む。それによって、決定関数の計算時間を短縮し、高速で高い精度の文字認識が実現される。
【００４３】
つぎに、スパースサポートベクターマシン（SSVM）及びトレーニング部１２が採用するEM学習アルゴリズムについて詳しく紹介する。
【００４４】
周知のように、二クラスサンプルトレーニングセットが
【数９】
0005176773.tif 000011
である場合、従来のサポートベクターマシン（SVM）の決定関数は、
【数１０】
0005176773.tif 000012
の形になる。ただし、カーネル関数項
【数１１】
0005176773.tif 000013
の直前の係数
【数１２】
0005176773.tif 000014
、偏差項
【数１３】
0005176773.tif 000015
である。
【００４５】
係数αiが全部ラグランジュ乗算子であるため、最終解ベクトル
【数１４】
0005176773.tif 000016
の中の要素がほぼ０である。すべての非零係数
【数１５】
0005176773.tif 000017
と対応するトレーニングサンプル
【数１６】
0005176773.tif 000018
をサポートベクトルと呼ぶ。
【００４６】
決定関数をサポートベクトルのカーネル関数項の展開式だけで表すことができる。すなわち、
【数１７】
0005176773.tif 000019
である。ただし、
【数１８】
0005176773.tif 000020
はサポートベクトルのサフィックスインデックスセットを表す。
【００４７】
これより分かるように、決定関数の計算時間とサポートベクトルの数とが比例する関係となっている。決定関数がきわめて少ない数のサポートベクトルを使うために、当発明のSSVMの決定関数は次の通りの形式となる。
【数１９】
0005176773.tif 000021
【００４８】
ただし、カーネル関数項
【数２０】
0005176773.tif 000022
の直前の係数
【数２１】
0005176773.tif 000023
、偏差項
【数２２】
0005176773.tif 000024
である。係数αiがもうラグランジュ乗算子ではないため、最終解ベクトル
【数２３】
0005176773.tif 000025
の中の要素が全部０とならない。最終解ベクトル
【数２３】
0005176773.tif 000026
の中の要素がほぼ正確に０に等しくなるように、すなわち解ベクトル
【数２３】
0005176773.tif 000027
を非常にスパース化させるために、本発明においてはSSVMの目標最適化問題の中にベクトル
【数２３】
0005176773.tif 000028
の０-ノルム正則化項を取り入れている。SSVMは次のような原始問題に対して最適化をおこなう。
【数２４】
0005176773.tif 000029
【００４９】
ただし、二ノルム項
【数２５】
0005176773.tif 000030
を最小化すると、最大マージンの分類器が得られる（二クラスの間のクラスマージンの大きさは
【数２６】
0005176773.tif 000031
である）。０-ノルム項
【数２７】
0005176773.tif 000032
（
【数２８】
0005176773.tif 000033
は特性関数（Indicator Function）である）を最小化することは、非零係数の総数、すなわちサポートベクトルの総数を最小化することに等しい。
【００５０】
弛緩因数項
【数２９】
0005176773.tif 000034
を最小化してトレーニング誤りをできるだけ低く抑えることである。二つの常数Ｃξ、Ｃαはそれぞれトレーニング誤差項とサポートベクトル数項の直前の懲罰因数である。
【００５１】
SSVMの原始的な最適化問題には特性関数を含んでいるので、目標関数が連続しない。そうすると、通常の最適化アルゴリズムにより求解することができないが、期待値最大化EM（Expectation Maximization）アルゴリズムにより漸近的に実現することができる。EMアルゴリズムの第t回繰り返しの際に、SSVMは次のような原始問題に対して最適化を行う。
【数３０】
0005176773.tif 000035
ただし、対角行列
【数３１】
0005176773.tif 000036
である。
【００５２】
そして、この最適化問題の双対問題（dual problem）が導き出される。
【数３２】
0005176773.tif 000037
【００５３】
ただし、行列
【数３３】
0005176773.tif 000038
，
【数３４】
0005176773.tif 000039
は正則化されたカーネル行列
【数３５】
0005176773.tif 000040
の要素であり、変数βiはラグランジュ乗算子である。
【００５４】
図３では、実施例１にかかる文字認識装置１０のトレーニング部１２による処理を概略的に示す。図３に示すように、トレーニング部１２は、サンプルセットを生成する処理（ステップ１２１）と、パラメータ設定処理（ステップ１２２）と、EM学習処理（ステップ１２３）と、結果出力処理（ステップ１２４）を繰り返して実行する。
【００５５】
そのうち、ステップ１２１では、二クラストレーニングサンプルセットを生成する。ステップ１２２では、カーネル関数を選択し、選択されたカーネル関数のパラメータを設定する。
【００５６】
たとえば、ガウスカーネル
【数３６】
0005176773.tif 000041
を選択し、パラメータσを設定するとともに、SSVMの二つのトレーニング定数Ｃξ、Ｃαを設定する。定数Ｃξが大きいほど、トレーニング誤差が小さくなる。また、定数Ｃαが大きいほど、決定関数がまばら（スパース）になる。すなわち、サポートベクトルの数が少なくなる。ステップ１２３では、スパースサポートベクターマシン（SSVM）をトレーニングさせる。そして、ステップ１２４では、この二クラストレーニングサンプルセットでの学習結果、すなわちSSVM決定関数を出力する。
【００５７】
EM学習を実施するステップ１２３では、繰り返しEステップとMステップを実行する。その中で、EステップではSSVMの対応する２次計画問題を更新する、すなわち、正則化されたカーネル行列を再計算する。Mステップでは改良された逐次最小最適化MSMOアルゴリズムを用い、更新後の２次計画問題、すなわちSSVMの前記双対問題を求解する。
【００５８】
図４は本発明のスパースサポートベクターマシンEM学習方法を示すフローチャートである。図４に示すように、ステップ１２３１では、ステップ１２１、１２２において設定された二クラストレーニングサンプルセット、カーネル関数、トレーニング定数Ｃξ、Ｃαに基づいて、繰り返す回数 t = 0、係数ベクトル
【数３７】
0005176773.tif 000042
および解ベクトルを初期化する。
【００５９】
ステップ１２３２では、係数ベクトルにおけるすべての非零要素を検索し、それらのサフィックスにより集合
【数３８】
0005176773.tif 000043
を組成する。ただし、εは非常に小さい正定数であり、例えば0.0001である。
【００６０】
ステップ１２３３では、現在の係数ベクトル
【数３９】
0005176773.tif 000044
に基づいて、対角行列
【数４０】
0005176773.tif 000045
を計算する。
【００６１】
ステップ１２３４は、Eステップであり、対角行列
【数４１】
0005176773.tif 000046
により、正則化されたカーネル行列
【数４２】
0005176773.tif 000047
を再計算する。
【００６２】
この計算式は
【数４３】
0005176773.tif 000048
と等価であり、数値計算上の問題点（零要素の逆数を求める）を回避できるとともに、逆行列を求めるときの計算量（l×lからm(t)×m(t)に減少し、m(t)は現在の係数ベクトル
【数４４】
0005176773.tif 000049
における非零要素の数、すなわちサポートベクトルの数である。）を減少させることができる。
【００６３】
ステップ１２３５はMステップであり、改良された逐次最小最適化MSMOアルゴリズムを用い、SSVMに対応する２次計画問題を求解する。ステップ１２３６では、更新式
【数４５】
0005176773.tif 000050
を用い、新たな解ベクトル
【数４６】
0005176773.tif 000051
により、新たな係数ベクトル
【数４７】
0005176773.tif 000052
を計算する。
【００６４】
ステップ１２３７では、現在の状態が終了条件を満たしているかどうかを判断する。ここで、終了条件とは、繰り返し回数が所定最大値 t < T となるか、あるいは係数ベクトルがもう変化しない
【数４８】
0005176773.tif 000053
という条件である。
【００６５】
終了条件を満足すると、EM繰り返しループであるステップ１２３２から１２３７までの処理を終了し、ステップ１２３８に進む。そうでなければ、ステップ１２３２に戻り、新たな繰り返しループを開始する。
【００６６】
ステップ１２３８では、計算式
【数４９】
0005176773.tif 000054
を採用して決定関数の偏差項を計算する。ただし、サフィックスセットは
【数５０】
0005176773.tif 000055
であり、
【数５１】
0005176773.tif 000056
はカーネル行列
【数５２】
0005176773.tif 000057
の第i目の列ベクトルである。
【００６７】
最後に、SSVMの決定関数を出力する。
【数５３】
0005176773.tif 000058
，ただし、
【数５４】
0005176773.tif 000059
である。
【００６８】
決定関数の中のサポートベクトルの数（すなわち、サフィックスセットISVにおける要素の数）がとてもまばら（スパース）なので、決定関数の計算が簡単となり、分類器の認識速度がとても速くなる。
【００６９】
図５は、Mステップに使われるSMO最適化アルゴリズムを詳しく示すフローチャートである。図５に示すように、ステップ１２３４において確定された最適化すべき２次計画問題
【数５５】
0005176773.tif 000060
に対して、ステップ１２３５１では、繰り返し回数 t = 0、解ベクトル
【数５６】
0005176773.tif 000061
及び勾配ベクトル
【数５７】
0005176773.tif 000062
を初期化する。なお、解ベクトル
【数５６】
0005176773.tif 000063
は前回Mステップ１２３５にて得られた解ベクトルで初期化してもよい。
【００７０】
ステップ１２３５２では、目標関数の下がり勾配が可能解方向において最速となるように、二つの最適化すべきなラグランジュ乗算子
【数５８】
0005176773.tif 000064
を検索する。これらのサフィックスは以下に示す方法で得られる。
【数５９】
0005176773.tif 000065
【数６０】
0005176773.tif 000066
【００７１】
サフィックスの検索が失敗した場合、あるいは変数
【数５８】
0005176773.tif 000067
に対する目標関数の勾配ベクトルが十分に小さい、すなわち、
【数６１】
0005176773.tif 000068
（ここで、εは例えば0.0001をとる）の場合に、目標関数が最小値としての安定点にあると判断され、さらに現在の解
【数６２】
0005176773.tif 000069
が最適解であると判断される。
【００７２】
ステップ１２３５３では、検索ができた場合に、ステップ１２３５４に移行し、選択された二つの変数
【数５８】
0005176773.tif 000070
を最適化する。そうではない場合、ループを終了し、最適解
【数６２】
0005176773.tif 000071
を出力する。
【００７３】
ステップ１２３５４では、選択された二つの変数
【数５８】
0005176773.tif 000072
に対して最適化処理を行うが、その他の変数はそのまま保持する。そうすると、新たなベクトル
【数６３】
0005176773.tif 000073
が得られる。
【００７４】
具体的な最適化方法には公知のものを使う。例えば、“J.C. Platt. Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines, Microsoft Research, Technical Report MSR-TR-98-14, 1998”に記載されるSMOアルゴリズムを利用してもよい。
【００７５】
ステップ１２３５５では、変数の変化量
【数６４】
0005176773.tif 000074
により、勾配ベクトルを更新する。
【００７６】
具体的に言えば、
【数６５】
0005176773.tif 000075
を計算する。ここで、
【数６６】
0005176773.tif 000076
はそれぞれ行列
【数６７】
0005176773.tif 000077
の第i1列と第i2列である。
【００７７】
ステップ１２３５６では、繰り返し回数 t が所定最大値 T より小さいかどうかを判断する。所定最大値より小さいと判断されると、ステップ１２３５２に戻り、再び繰り返しループを開始する。そうでなければ、繰り返しループの処理を終了し、現在の解ベクトルをそのまま出力する。
【００７８】
以上に述べた本発明の実施例１にかかる文字認識装置１０によれば、スパースサポートベクターマシン分類器を採用したため、認識速度が大きく向上された。
【００７９】
図６（a）は、従来のサポートベクターマシン（SVM）に基づく文字認識装置による分割可能な文字サンプルに対する認識例を示す図である。図６（ｂ）は、本発明のスパースサポートベクターマシン（SSVM）に基づく文字認識装置による分割可能な文字サンプルに対する認識例を示す図である。
【００８０】
図６（a）及び図６（ｂ）において、二クラスデータのトレーニングサンプル点をそれぞれ標記“＋”と標記“△”で表す。図面からわかるように、この二クラスデータの分布は分割可能である。図６(a)のSVMと図６(ｂ)のSSVMにおいては、いずれもガウスカーネルが採用され、同じパラメータＣξが設定されている。しかし、本発明のSSVMにおいては、SVMにないパラメータＣαを具備する。
【００８１】
図においては、３本の線が示されている。中間の線はクラスリング決定面
【数６８】
0005176773.tif 000078
を示し、両側の線はそれぞれサポートプレーン
【数６９】
0005176773.tif 000079
を示す。また、標記“○”はサポートベクトルを示す。
【００８２】
図６（a）では、SVMに７つのサポートベクトルが必要なことに対し、図６（ｂ）では、SSVMに４つのサポートベクトルが必要となる。それに、SVMのサポートベクトルはサポートプレーンに位置するに対し、SSVMのサポートベクトルの位置には特に制限がない。
【００８３】
図６（ｃ）は、従来のサポートベクターマシン（SVM）に基づく文字認識装置による分割不可能な文字サンプルに対する認識例を示す図である。図６（ｄ）は、本発明のスパースサポートベクターマシン（SSVM）に基づく文字認識装置による分割不可能な文字サンプルに対する認識例を示す図である。
【００８４】
図６（ｃ）及び図６（ｄ）においては二クラスデータの重なる領域が多く、データ分布が分割不可能となる。SVMとSSVMにおいては、いずれもガウスカーネルを採用され、同じパラメータＣξが設定されている。
【００８５】
図においては、クラスリング決定面、サポートプレーン、サポートベクトルが示されている。SVMに１０８個サポートベクトルが必要なのに対し、SSVMに４つしか必要としない。それにも関わらず、両者のクラスリング境界面の位置はほぼ一致している。
【００８６】
SVMのサポートベクトルは必ず二つのサポートプレーン以内（二つのサポートプレーン自身を含む）のサンプル、または、二つのサポートプレーン以外でかつ間違って分類されるサンプルであるのに対し、SSVMのサポートベクトルの位置には特に制限がない。
【００８７】
この例からわかるように、二クラスが分割不可能の場合に、SVMのサポートベクトルの中に大量な冗長性が存在する。SSVMはこの冗長性を解決するものであり、トレーニングサンプルセットから４つのサンプルだけをサポートベクトルとして選択し、クラスリング面を構成することによって冗長性を除去する。
【００８８】
以上に述べた実施例１においては、スパースサポートベクターマシンを採用して僅かな数のサポートベクトルを利用することにより決定関数が簡単になり、認識速度を大きく向上できるとともに、従来のサポートベクターマシンに基づく文字認識とほぼ同等な分類性能を得られる。
【実施例２】
【００８９】
以下に本発明の他の実施例について説明する。実施例２においては、さらに各スパースサポートベクターマシンの分類結果に対するクラス事後確率を算出し、このクラス事後確率に基づいて最終の認識結果を決定する。以下の説明では、主に実施例１との違う所について説明する。なお、同じまたは対応する構成については同じまたは対応する符号をつけて説明を省略する。
【００９０】
図７は、本発明の実施例２にかかる文字認識装置１０'の概略ブロック図である。実施例２にかかる文字認識装置１０'は、実施例１に係る文字認識装置１０と同様に、入力装置２０と出力装置３０とに接続されている。入力装置２０は、トレーニングサンプルとしての文字画像あるいは認識すべき文字画像を文字認識装置１０'に入力するものである。
【００９１】
文字認識装置１０'は、入力装置２０により入力されたトレーニングサンプルとしての文字画像に基づいて学習を行い、目標文字と対応する複数のスパースサポートベクターマシン分類器を得る。そして、これら複数のスパースサポートベクターマシン分類器によって、入力装置２０により入力された認識すべき文字画像を認識し、認識すべき文字画像に該当する文字を決定する。出力装置３０により、文字認識装置１０'の認識結果を利用者に対して出力する。
【００９２】
文字認識装置１０'は、特徴ベクトル抽出部１１'（実施例１の特徴ベクトル抽出部１１とまったく同じだから、具体的な説明を省略する。）と、トレーニングサンプルセットに基づいて複数の二クラススパースサポートベクターマシン分類器を学習することにより得て、最大尤度法によりSSVMの決定関数ごとに一つのSigmoid関数をフィッティングさせるトレーニング部１２'と、SSVMごとの決定関数
【数７０】
0005176773.tif 000080
、すなわち、カーネル関数
【数７１】
0005176773.tif 000081
、サポートベクトル
【数７２】
0005176773.tif 000082
、対応係数αi及び偏差項bを記憶するとともに、Sigmoid関数
【数７３】
0005176773.tif 000083
、すなわち、定数AとBを記憶する記憶部１３'と、記憶部１３'に記憶されたトレーニング結果に基づいて、認識すべき文字画像の各SSVM決定関数における出力値および対応するSigmoid関数における出力値を得る認識部１４'と、複数の二クラスのクラス事後確率に基づいて多クラスのクラス事後確率を算出し、最終認識結果、すなわち認識すべき文字画像の文字カテゴリおよびその事後確率を決定する確信度部１５'と、を含む。
【００９３】
以下、また「０」〜「９」の１０個数字の認識を例として、図８により文字認識装置１０'の各部による処理を詳しく説明する。
【００９４】
図８は、実施例２にかかる文字認識装置１０'による処理を概略的に示すフローチャートである。実施例２にかかる文字認識装置１０'による処理は実施例１に係る文字認識装置１０による処理とほぼ同様であり、違う所は以下の点である。
【００９５】
ステップ２０４のつぎに、トレーニング部１２'は、二クラスサンプルトレーニングセットに対するSSVM決定関数の出力に基づいて、最大尤度法によりSigmoid関数を推定し、二クラスの事後確率を求める（ステップ２１０）。
【００９６】
認識部１４'は、ステップ２０９以後、すべてのケースのSigmoid関数の出力値を計算する（ステップ２１１）。確信度部１５'は、ステップ２１１以後、複数の二クラス事後確率から多クラス事後確率を計算し、最大事後確率と対応する文字を出力する（ステップ２１２）。
【００９７】
ステップ２０１〜２０９は実施例１と完全に同じなので、以下、ステップ２１０、２１１、２１２のみを詳しく説明する。まず、ステップ２１０について説明する。二クラスサンプルトレーニングセットを
【数７４】
0005176773.tif 000084
と、新たなトレーニングセットを
【数７５】
0005176773.tif 000085
と定義する。ただし、
【数７６】
0005176773.tif 000086
である。
【００９８】
最大尤度推定によりパラメータAとBが得られる。
【数７７】
0005176773.tif 000087
ここで、
【数７８】
0005176773.tif 000088
である。
【００９９】
Sigmoid関数をフィッティングさせる方法は周知のものを使う。例えば、“H.T. Lin, C.J. Lin, R.C. Weng. A Note on Platt’s Probabilistic Outputs for Support Vector Machines. National Taiwan University, 2003, http://www.csie.ntu.edu.tw/~cjlin/libsvmtools”に記載される方法を採用する。
【０１００】
ステップ２１１では、スパースサポートベクターマシンの出力に基づいて、Sigmoid関数により二クラスのクラス事後確率を計算する。ステップ２１２では、複数の二クラスのクラス事後確率から多クラスのクラス事後確率を計算する。以下、詳しく説明する。
【０１０１】
仮に、k個の文字クラスを有するとする。piはクラスiの事後確率を示す。
“一対一”というルールを採用すると、
【数７９】
0005176773.tif 000089
個の二クラス分類器が必要になる。
【０１０２】
Sigmoid関数の出力を
【数８０】
0005176773.tif 000090
と標記する。ここで、SSVM分類器
【数８１】
0005176773.tif 000091
は文字クラスiと文字クラスjを区別するために用いられる。前記二クラスのクラス事後確率rijと多クラスのクラス事後確率piは
【数８２】
0005176773.tif 000092
という近似関係を持ち、従って、
【数８３】
0005176773.tif 000093
となる。
【０１０３】
ここで、rji = 1 - rij である。これらの関係を満足する最適解を求めるために、以下の問題を最適化する。
【数８４】
0005176773.tif 000094
【０１０４】
この問題が
【数８５】
0005176773.tif 000095
と等価であることが証明できるものなので、さらに線形システムの求解に簡略化できる。
【０１０５】
この処理は周知のものを使う。例えば、“T.F. Wu, C.J. Lin, R.C. Weng. Probability Estimates for Multi-class Classification by Pairwise Coupling. Journal of Machine Learning Research 5 (2004) 975-1005”に記載される方法を採用する。
【０１０６】
これに対して、“一対多”というルールを採用すると、
【数８６】
0005176773.tif 000096
個の二クラス分類器が必要になる。二クラスのクラス事後確率
【数８７】
0005176773.tif 000097
と多クラスのクラス事後確率piは
【数８８】
0005176773.tif 000098
という近似関係を持つ。
【０１０７】
これらの関係を満足する最適解を求めるために、以下の問題を最適化する。
【数８９】
0005176773.tif 000099
これは簡単な２次計画問題であり、周知の方法で容易に求められる。
【０１０８】
本発明の実施例２に拠れば、Sigmoid関数によりスパースサポートベクターマシンの出力を二クラスのクラス事後確率に変換し、複数の二クラスのクラス事後確率からさらに多クラスのクラス事後確率を求めて出力する。これにより、複数の二クラス分類器の出力をうまく融合して（その効果は投票法よりよい）認識の精度が向上するばかりではなく、各クラスごとの確信度を提供し、続く認識拒否処理または後処理に根拠を提供できる。
【０１０９】
以上では本発明の具体的な実施例について説明したが、以上の内容は本発明を限定するものではなく、請求範囲で限定される範囲以内で各種の変更、改良または前記各要素の組み合わせが可能である。
【０１１０】
以上の説明において、文字認識装置により本発明を説明したが、文字認識装置だけではなく、文字認識装置が実行する文字認識方法としても実施できる。また、この文字認識方法を実現するプログラムおよびこのプログラムを記憶した記憶媒体として実施することもできる。
【０１１１】
また、文字認識により本発明を説明したが、パターン認識、サンプルクラスリングなどの領域にも本発明の原理を適用することが可能である。
【０１１２】
（付記１）トレーニングサンプルあるいは認識すべきサンプルから特徴ベクトルを抽出する特徴ベクトル抽出ステップと、
前記特徴ベクトル抽出ステップにより抽出された前記トレーニングサンプルの特徴ベクトルからなるトレーニングサンプルセットに基づいて学習し、複数のスパースサポートベクターマシン分類器を得るトレーニングステップと、
前記スパースサポートベクターマシン分類器ごとに、前記特徴ベクトル抽出ステップにより抽出された認識すべきサンプルの特徴ベクトルに対する出力を計算し、前記認識すべきサンプルと対応するパターンを決定する認識ステップと、
を含み、
前記トレーニングステップでは、前記スパースサポートベクターマシン分類器の目標関数に０-ノルム正則化項を導入することにより前記スパースサポートベクターマシン分類器の決定関数におけるサポートベクトルの数を減少させること、
を特徴とするパターン認識方法。
【０１１３】
（付記２）前記スパースサポートベクターマシン分類器は二クラススパースサポートベクターマシン分類器であり、前記トレーニングステップは、多クラストレーニングサンプルセットから二クラストレーニングサンプルセットを構成するステップをさらに含むことを特徴とする付記１に記載のパターン認識方法。
【０１１４】
（付記３）前記トレーニングステップはさらに前記スパースサポートベクターマシン分類器ごとにSigmoid関数をフィッティングするステップを含み、前記認識ステップはさらに前記Sigmoid関数により前記スパースサポートベクターマシン分類器の出力に基づいて二クラスの認識事後確率を計算するステップを含み、前記認識ステップはさらに前記二クラスの認識事後確率から多クラスの認識事後確率を計算するステップを含み、前記認識ステップでは前記多クラスの認識事後確率に基づいて前記認識すべきサンプルと対応するパターンを決定することを特徴とする付記１に記載のパターン認識方法。
【０１１５】
（付記４）前記トレーニングステップでは前記スパースサポートベクターマシン分類器の決定関数をトレーニングサンプルのカーネル項と偏差項との線形結合式として設定し、展開係数を実数として設定することを特徴とする付記２に記載のパターン認識方法。
【０１１６】
（付記５）前記トレーニングステップでは、繰り返し回数、係数ベクトル、解ベクトルを初期化すること、係数ベクトルにおけるすべての非零要素を検索し、対角行列を計算すること、正則化されたカーネル行列を再計算すること、前記スパースサポートベクターマシンと対応する２次計画問題を求解し、解ベクトルから係数ベクトルを計算すること、終了条件を満足しているかどうかを判断し、満足していないと判断される場合、非零要素を検索する処理に戻り、また、満足すると判断される場合、決定関数の偏差項を計算し、決定関数を出力すること、を繰り返し実行することによって、前記スパースサポートベクターマシン分類器の最適化をすることを特徴とする付記４に記載のパターン認識方法。
【０１１７】
（付記６）トレーニング文字画像あるいは認識すべき文字画像から特徴ベクトルを抽出する特徴ベクトル抽出手段と、
前記特徴ベクトル抽出手段により抽出された前記トレーニング文字画像の特徴ベクトルからなるトレーニングサンプルセットに基づいて学習し、複数のスパースサポートベクターマシン分類器を得るトレーニング手段と、
前記トレーニング手段によるトレーニング結果を記憶する記憶手段と、
前記スパースサポートベクターマシン分類器ごとに、前記特徴ベクトル抽出手段により抽出された認識すべき文字画像の特徴ベクトルに対する出力を計算し、前記認識すべき文字画像と対応する文字を決定する認識手段と、を備え、
前記トレーニング手段は、前記スパースサポートベクターマシン分類器の目標関数に０-ノルム正則化項を導入することにより前記スパースサポートベクターマシン分類器の決定関数におけるサポートベクトルの数を減少させること、
を特徴とする文字認識装置。
【０１１８】
（付記７）前記スパースサポートベクターマシン分類器は二クラススパースサポートベクターマシン分類器であり、前記トレーニング手段は、多クラストレーニングサンプルセットから二クラストレーニングサンプルセットを構成するサンプルセット生成手段をさらに備えたことを特徴とする付記６に記載の文字認識装置。
【０１１９】
（付記８）前記トレーニング手段はさらに前記スパースサポートベクターマシン分類器ごとにSigmoid関数をフィッティングし、前記認識手段はさらに前記Sigmoid関数により前記スパースサポートベクターマシン分類器の出力に基づいて二クラスの認識事後確率を計算し、前記認識手段は前記二クラスの認識事後確率から多クラスの認識事後確率を計算する確信度手段をさらに備え、前記認識手段は前記多クラスの認識事後確率に基づいて前記認識すべき文字画像と対応する文字を決定することを特徴とする付記６に記載の文字認識装置。
【０１２０】
（付記９）前記トレーニング手段は前記スパースサポートベクターマシン分類器の決定関数をトレーニングサンプルのカーネル項と偏差項の線形結合式として設定し、展開係数を実数として設定することを特徴とする付記７に記載の文字認識装置。
【０１２１】
（付記１０）前記トレーニング手段は、繰り返し回数、係数ベクトル、解ベクトルを初期化すること、係数ベクトルにおけるすべての非零要素を検索し、対角行列を計算すること、正則化されたカーネル行列を再計算すること、前記スパースサポートベクターマシンと対応する２次計画問題を求解し、解ベクトルから係数ベクトルを計算すること、終了条件を満足しているかどうかを判断し、満足していないと判断される場合、非零要素を検索する処理に戻り、また、満足すると判断される場合、決定関数の偏差項を計算し、決定関数を出力すること、を繰り返し実行することによって、前記スパースサポートベクターマシン分類器の最適化をすることを特徴とする付記９に記載の文字認識装置。
【０１２２】
（付記１１）トレーニング文字画像あるいは認識すべき文字画像から特徴ベクトルを抽出する特徴ベクトル抽出ステップと、
前記特徴ベクトル抽出ステップにより抽出された前記トレーニング文字画像の特徴ベクトルからなるトレーニングサンプルセットに基づいて学習し、複数のスパースサポートベクターマシン分類器を得るトレーニングステップと、
前記スパースサポートベクターマシン分類器ごとに、前記特徴ベクトル抽出ステップにより抽出された認識すべき文字画像の特徴ベクトルに対する出力を計算し、前記認識すべき文字画像と対応する文字を決定する認識ステップと、
を含み、
前記トレーニングステップでは、前記スパースサポートベクターマシン分類器の目標関数に０-ノルム正則化項を導入することにより前記スパースサポートベクターマシン分類器の決定関数におけるサポートベクトルの数を減少させること、
を特徴とする文字認識方法。
【０１２３】
（付記１２）前記スパースサポートベクターマシン分類器は二クラススパースサポートベクターマシン分類器であり、前記トレーニングステップは、多クラストレーニングサンプルセットから二クラストレーニングサンプルセットを構成するステップをさらに含むことを特徴とする付記１１に記載の文字認識方法。
【０１２４】
（付記１３）前記トレーニングステップはさらに前記スパースサポートベクターマシン分類器ごとにSigmoid関数をフィッティングするステップを含み、前記認識ステップは前記Sigmoid関数により前記スパースサポートベクターマシン分類器の出力に基づいて二クラスの認識事後確率を計算するステップをさらに含み、前記認識ステップは前記二クラスの認識事後確率から多クラスの認識事後確率を計算するステップをさらに含み、前記認識ステップでは前記多クラスの認識事後確率に基づいて前記認識すべき文字画像と対応する文字を決定することを特徴とする付記１１に記載の文字認識方法。
【０１２５】
（付記１４）前記トレーニングステップでは前記スパースサポートベクターマシン分類器の決定関数をトレーニングサンプルのカーネル項と偏差項の線形結合式として設定し、展開係数を実数として設定することを特徴とする付記１２に記載の文字認識方法。
【０１２６】
（付記１５）前記トレーニングステップでは、繰り返し回数、係数ベクトル、解ベクトルを初期化すること、係数ベクトルにおけるすべての非零要素を検索し、対角行列を計算すること、正則化されたカーネル行列を再計算すること、前記スパースサポートベクターマシンと対応する２次計画問題を求解し、解ベクトルから係数ベクトルを計算すること、終了条件を満足しているかどうかを判断し、満足していないと判断される場合、非零要素を検索する処理に戻り、また、満足すると判断される場合、決定関数の偏差項を計算し、決定関数を出力すること、を繰り返し実行することによって、前記スパースサポートベクターマシン分類器の最適化をすることを特徴とする付記１４に記載の文字認識方法。
【０１２７】
（付記１６）トレーニング文字画像や認識すべき文字画像から特徴ベクトルを抽出する特徴ベクトル抽出ステップと、
前記特徴ベクトル抽出ステップにより抽出された前記トレーニング文字画像の特徴ベクトルからなるトレーニングサンプルセットに基づいて学習し、複数のスパースサポートベクターマシン分類器を得るトレーニングステップと、
前記スパースサポートベクターマシン分類器ごとに、前記特徴ベクトル抽出ステップにより抽出された認識すべき文字画像の特徴ベクトルに対する出力を計算し、前記認識すべき文字画像と対応する文字を決定する認識ステップと、
を含み、
前記トレーニングステップでは、前記スパースサポートベクターマシン分類器の目標関数に０-ノルム正則化項を導入することにより前記スパースサポートベクターマシン分類器の決定関数におけるサポートベクトルの数を減少させる文字認識方法をコンピュータに実行させることを特徴とするコンピュータプログラム。
【０１２８】
（付記１７）前記スパースサポートベクターマシン分類器は二クラススパースサポートベクターマシン分類器であり、前記トレーニングステップは、多クラストレーニングサンプルセットから二クラストレーニングサンプルセットを構成するステップをさらに含むことを特徴とする付記１６に記載のコンピュータプログラム。
【０１２９】
（付記１８）前記トレーニングステップは前記スパースサポートベクターマシン分類器ごとにSigmoid関数をフィッティングするステップをさらに含み、前記認識ステップは前記Sigmoid関数により前記スパースサポートベクターマシン分類器の出力に基づいて二クラスの認識事後確率を計算するステップをさらに含み、前記認識ステップは前記二クラスの認識事後確率から多クラスの認識事後確率を計算するステップをさらに含み、前記認識ステップでは前記多クラスの認識事後確率に基づいて前記認識すべき文字画像と対応する文字を決定することを特徴とする付記１６に記載のコンピュータプログラム。
【０１３０】
（付記１９）前記トレーニングステップでは前記スパースサポートベクターマシン分類器の決定関数をトレーニングサンプルのカーネル項と偏差項の線形結合式として設定し、展開係数を実数として設定することを特徴とする付記１７に記載のコンピュータプログラム。
【０１３１】
（付記２０）前記トレーニングステップでは、繰り返し回数、係数ベクトル、解ベクトルを初期化すること、係数ベクトルにおけるすべての非零要素を検索し、対角行列を計算すること、正則化されたカーネル行列を再計算すること、前記スパースサポートベクターマシンと対応する２次計画問題を求解し、解ベクトルから係数ベクトルを計算すること、終了条件を満足しているかどうかを判断し、満足していないと判断される場合、非零要素を検索する処理に戻り、また、満足すると判断される場合、決定関数の偏差項を計算し、決定関数を出力すること、を繰り返し実行することによって、前記スパースサポートベクターマシン分類器の最適化をすることを特徴とする付記１９に記載のコンピュータプログラム。
【図面の簡単な説明】
【０１３２】
【図１】本発明の実施例１にかかる文字認識装置の概略ブロック図である。
【図２】実施例１にかかる文字認識装置による処理を概略的に示すフローチャートである。
【図３】実施例１にかかる文字認識装置のトレーニング部による処理を概略的に示すフローチャートである。
【図４】文字認識装置が実行するスパースサポートベクターマシンEM学習方法を概略的に示すフローチャートである。
【図５】Mステップに使われるMSMO最適化方法のフローチャートである。
【図６】文字認識装置の認識例を示す図である。
【図７】本発明の実施例２にかかる文字認識装置の概略ブロック図である。
【図８】実施例２にかかる文字認識装置による処理を概略的に示すフローチャートである。
【符号の説明】
【０１３３】
１０，１０’    文字認識装置
１１，１１’    特徴ベクトル抽出部
１２，１２’    トレーニング部
１３，１３’    記憶部
１４，１４’    認識部
１５’    確信度部
２０    入力装置
３０    出力装置
【図１】
0005176773.tif 000100
【図２】
0005176773.tif 000101
【図３】
0005176773.tif 000102
【図４】
0005176773.tif 000103
【図５】
0005176773.tif 000104
【図６】
0005176773.tif 000105
【図７】
0005176773.tif 000106
【図８】
0005176773.tif 000107