(57)【特許請求の範囲】
【請求項１】
識別対象パターンのデジタル化された特徴および当該特徴に対応する目標値を含むラベル有りサンプルと、ラベル無しサンプルとを含み、デジタル化された特徴で表現される識別対象パターンのサンプルを半教師あり学習メカニズムによって識別するパターン識別装置であって、
入力された識別対象パターンのサンプルに基づき、識別対象パターンのマニホールド構造を構築するのに適する非ユークリッド空間のカーネル行列を構成する非ユークリッド空間カーネル構成部と、
前記非ユークリッド空間カーネル構成部によって構成された非ユークリッド空間のカーネル行列に基づき、識別対象パターンのサンプルに局部線形埋め込みを行って識別対象パターンのサンプルの再構成係数行列を生成する核空間内局部線形埋め込み部と、
前記核空間内局部線形埋め込み部によって生成された再構成係数行列と前記ラベル有りサンプルの目標値に基づき、入力されたすべての識別対象パターンのサンプルに対して評価値を生成する正則化部と、
を備えることを特徴とするパターン識別装置。
【請求項２】
前記非ユークリッド空間カーネル構成部は、入力されたすべての識別対象パターンのサンプルのｋ隣接行列に基づき、非ユークリッド空間のカーネル行列を生成することを特徴とする請求項１に記載のパターン識別装置。
【請求項３】
前記核空間内局部線形埋め込み部によって生成された再構成係数行列は、識別対象パターンのサンプルの内在幾何構造を表すことを特徴とする請求項１に記載のパターン識別装置。
【請求項４】
前記非ユークリッド空間は、ラプラシアン空間または再生核ヒルベルト空間であることを特徴とする請求項１に記載のパターン識別装置。
【請求項５】
識別対象パターンのデジタル化された特徴および当該特徴に対応する目標値を含むラベル有りサンプルと、ラベル無しサンプルとを含み、デジタル化された特徴で表現される識別対象パターンのサンプルを半教師あり学習メカニズムによってパターン識別装置が識別するパターン識別方法であって、
前記パターン識別装置が、
入力された識別対象パターンのサンプルに基づき、識別対象パターンのマニホールド構造を構築するのに適する非ユークリッド空間のカーネル行列を構成するステップと、
構成された非ユークリッド空間のカーネル行列に基づき、識別対象パターンのサンプルに局部線形埋め込みを行って識別対象パターンのサンプルの再構成係数行列を生成するステップと、
生成された再構成係数行列と前記ラベル有りサンプルの目標値に基づき、入力されたすべての識別対象パターンのサンプルに対して評価値を生成するステップと、
を実行することを特徴とするパターン識別方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターン識別装置およびパターン識別方法に関し、例えば、半教師あり学習（semi-supervised learning）メカニズムによって核空間内の識別対象パターンに対して線形埋め込みを行ってパターン識別をするパターン識別装置およびパターン識別方法に関する。
【背景技術】
【０００２】
パターンの識別、ソーティングおよび検索などを実現するために、従来の方法では、標識付けられた対象サンプルによってトレーニングし、学習により目標の関数を取得することによって、上記のような機能を実現していた。例えば、手書き数字を識別する際に、予め手書き数字の画像を集めてから、それらの画像サンプルに対し処理して学習することによって、分類関数が取得される。一例として、まずは画像に二値化処理を行ってから、筆画方向および構造情報の特徴を抽出して、最後にそれらの特徴に基づき数字の類別を判断し、すなわち分類関数を生成して、識別分類が可能となる。そのような学習過程において、各画像における数字の実際の値を対応付けること、すなわちそれらの画像サンプルに対してラベルを付ける必要がある。分類関数は、入力が手書き数字画像（もしくはそれに対応する特徴）であり、出力が当該画像における数字の値である。このようにして、新しい手書き数字画像を識別するときに、該手書き数字画像を上記分類関数に直接に入力すると、その数字の値を取得することができる。
【０００３】
しかしながら、実際の応用において、ラベル有りサンプル（labeled sample）を取得するには常に多くの時間と多大な労力が必要となり、専門家でなければラベル有りサンプルを取得することができないことがある。例えば、生物および計算科学分野では、タンパク質を分類するために、タンパク質の形状サンプルを取得して学習しておくが、結晶体の専業分析者が何ヶ月間をかけても１つのタンパク質サンプルしか得られない。逆に、ラベル無しサンプル（unlabeled sample）は、多数存在し且つ容易に入手できる。そのため、いかにラベル有りサンプルとラベル無しサンプルを組み合わせて、有用な情報を抽出するかは、機械学習分野における大切な課題となっている。
【０００４】
ラベル有りサンプルとラベル無しサンプルとの違いは、サンプルと対応する目標値が提供されているか否かである。ラベル無しサンプルは処理される対象に過ぎないが、ラベル有りサンプルは処理される対象のみならず、該処理される対象の目標値も含まれている。その例として、手書き数字の識別において、ラベル無しサンプルは手書き数字の画像であるのに対し、ラベル有りサンプルには当該画像以外に、該画像における数字の実際の値を更に含んでいる。
【０００５】
ラベル有りサンプルによってパターン分類を行う手法は２種類に分けることができる。すなわち、パターン分類には、教師あり学習を用いる手法と半教師あり学習を用いる手法とがある。教師あり学習とは、ラベル有りサンプルのみによって学習したりトレーニングしたりして分類関数を取得することを指し、半教師あり学習とは、ラベル有りサンプルとラベル無しサンプルとから同時に学習を行うことを指す。半教師あり学習の思想は、次のようなものである。すなわち、ラベル無しサンプルには原則として対象の目標値が含まれていないことから、ラベル有りサンプルのように直接学習したりトレーニングしたりすることができないが、ラベル無しサンプルには対象サンプルの空間分布に関する有用な情報が含まれている。そして、そのような有用な情報を抽出してラベル有りサンプルと組み合わせれば、分類、識別の機能向上に有利である。通常、パターン識別の課題に関して、十分なラベル有りサンプルが提供され、学習したりトレーニングしたりすることができれば、教師あり学習でも良好な識別結果を得ることができる。ところが、例えば上記のタンパク質サンプルの場合のようにラベル有りサンプルが少なければ、教師あり学習手法が失敗することがある。逆に、半教師あり学習手法ではラベル無しサンプルから有用な情報を抽出するので、識別の機能を大いに向上させることができる。
【０００６】
半教師あり学習メカニズムでは、ラベル有りサンプルとラベル無しサンプルとを備えるサンプル集（「部分ラベル有りサンプル集」といい、通常は少量のラベル有りサンプルと大量のラベル無しサンプルとを含む）について、まずサンプル集に含まれるサンプルの内在構造を解析して、その空間分布特徴を取得し、サンプルの空間分布およびラベル有りサンプルに基づく学習を行い、ラベル無しサンプルに対する分類およびソートを行う。
【０００７】
実際の応用では、入力した識別対象パターンのサンプルに常に多くの変数があり、サンプルが高次元の空間に位置することになる。例えば、手書き数字識別において、入力した対象サンプルが共に画像なので、対象サンプルの元の空間での次元数は画像における画素数とみなすことができる。しかしながら、それら画像サンプルの内在空間の次元数は、その元の空間の次元数よりはるかに低くすることができる。数字の０を例とすると、「０」の画像は、楕円で近似することができ、その内在空間の次元数は、中心座標と長短軸の半径との４つとすることができる。実際には、手書き数字の変形および楕円近似の歪みなどの要素を鑑み、「０」と対応する画像サンプルの内在次元数は、４よりも大きい値となるが、当該値はやはり画像の画素数よりずっと小さくなっている。このような現象から、半教師あり学習メカニズムは通常、（1）高次元空間におけるデータサンプルが内在の低次元空間構造を備え、その低次元空間において、サンプルの分布が滑らかであることを意味するマニホールド構造分布に従うことと、（2）マニホールド構造では、隣接したサンプル点が共通した種別や記号を有することとの２点を想定している。
【０００８】
近年、ラベル無しサンプルから情報を抽出して機能を向上させるために、半教師あり学習手法が多数提案されている。非特許文献１に示すように、ラプラシアン図（Laplacian Eigenmap）は代表的な半教師あり学習手法の一種である。この手法では、まずサンプル点（ラベル有りサンプルとラベル無しサンプルを含むすべてのサンプル）間のユークリッド距離 （Euclidean distance）とｋ近傍法によって近傍グラフ（Adjacency Graph）を作り上げることによって、そのラプラシアン行列を得る。近傍グラフとは、グラフでサンプル点の間の関係を表すものであり、図形のノードがサンプル点に対応し、図形の辺がｋ近傍法によって決まる。ｋ近傍法とは、サンプルごとにそれぞれのサンプルとのユークリッド距離が最も近いｋ番目までのサンプルを探し、近傍グラフにおいてそのサンプルおよびｋ番目までの隣接サンプルに対して辺を追加する方法であり、辺の属性値がサンプル間のユークリッド距離を表す。近傍グラフを作ることにより容易にそのラプラシアン行列を取得することができ、その後、該行列に対し特徴値の分解が行われる。最後に、特徴値が小さい特徴ベクトルおよびラベル有りサンプルに基づき、データセットにおけるラベル無しサンプルの分類が行われる。本質的には、該方法には三つの大切な特性を備えている。すなわち（1）該方法は入力したデータセットがマニホールド構造を有しており、元は高次元空間で表現されるデータの内在空間の次元数を低いと想定すること、（2）すべてのデータ（ラベル有りサンプルとラベル無しサンプルを含む）を利用してそのマニホールド構造を推定すること、および（3）ラプラシアン・ベルトラミ（Laplacian Beltrami）作用素によって高次元空間から低次元空間へのマッピングを実現すると共に分類する目的を達成していることの３点である。
【０００９】
ローカル隣接ラプラシアン図方法（特許文献１を参照）は、非特許文献１におけるラプラシアン図方法の拡張である。非特許文献１の方法では、サンプルセットにおけるあらゆるサンプル点に基づいてラプラシアン行列を構築して特徴量を分解しているので、サンプル点が多くなる場合、該方法を実行するには時間がかかる。その課題を解決するために、特許文献１では、分類しようとするサンプル点が位置する一つのサブ行列のみに対して特徴値の分解を行うようにするため、速度を大幅に向上させることができる。それと同時に、特許文献１の方法によって、新しいサンプル点の分類に関する課題も解決されている。
【００１０】
非特許文献２に示すように、マニホールドソーティング（Manifold Sorting）はよく用いられる半教師あり学習手法の他の一種である。該手法の思想は、主にサンプル点の内在構造に基づいてサンプル点をソートすることである。非特許文献１と同様に、該手法はまずサンプル点間のユークリッド距離（Euclidean Distance）に基づきｋ近傍グラフを構築し、その後でラベル有りサンプルの目標値をｋ近傍グラフに沿って繰り返して伝達し、最後にサンプル点ごとに評価値を取得する。それらの評価値は、最終的なソーティングの根拠となる。該手法の原理は、下記の電子回路網で説明することができる。
【００１１】
上述したように、サンプル点の関係は近傍グラフで表すことができ、近傍グラフのノードがサンプル点に対応し、図形の辺がｋ近傍法で決まっている。次に、その近傍グラフを電子回路網とみなすと、図形においてラベル有りサンプルと対応するノードがそれぞれ電極と接続しており、正サンプルがプラス電極に、負サンプルがマイナス電極にそれぞれ接続している。また、図形の辺が抵抗に相当し、辺の属性値（サンプル間のユークリッド距離）が抵抗の抵抗値と対応している。言い換えれば、サンプル間のユークリッド距離が小さくなるほど、対応するノード間の抵抗が小さいとみなすことができる。電源をオンにすると、電子回路網が平衡状態になることから、各ラベル無しサンプルとそれぞれ対応するノードにおいて電圧値が測定される場合、電圧値が高いほど、該サンプルが正サンプルに近づくことを意味するのに対し、電圧値が低いほど、該サンプルが負サンプルに近づくことを意味している。具体的な応用において、非特許文献２ではグラフの正則化という技術を利用して上記過程を実現していた。
【００１２】
非特許文献３において、ガウスフィールド調和関数（Gaussian Fields and Harmonic Functions）を用いて半教師あり学習を行う方法が提案されており、該方法は非特許文献２における方法と同一タイプに属しており、グラフの正則化を達成する手段が非特許文献２における方法とは異なる。すなわち、非特許文献３における方法では、補間正則化（Interpolated regularization）を利用してグラフの正則化が行われている。非特許文献４では、これらの異なる二つの方法に対する解析を行っており、論理上、誤差の上限が得られている。グラフの正則化に関し、非特許文献５では、最適化された目標関数を修正し、弛緩因子を導入することによって、グラフの正則化がベクトル機をサポートする標準的なフォーマットに変換されている。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】米国特許出願公開第２００６／０２３５８１２号明細書
【非特許文献】
【００１４】
【非特許文献１】Mikhail Belkin, Partha Niyogi, "Semi-Supervised Learning on Rimanian Manifolds", Machine Learning, Vol.56, pp.209-239, 2004
【非特許文献２】Dengyong Zhou, Olivier Bousquet, Thomas Navi Lal, Jason Weston, Bernhard Scholkopf, "Learning with Local and Global Consistency", Advances in Neural Information Processing System, Vol.16, pp.321-328, 2003
【非特許文献３】Xiaojin Zhu, Zoubin Ghahramani, John Lafferty, "Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions", Proceedings of the twentieth international conference on machine learning (ICML2003), pp.912-919, 2003
【非特許文献４】Mikhail Belkin, Irina Matveeva, Partha Niyogi, "Regularization and Semi Supervised Learning on Large Graphs", Proceedings of annual conference on learning theory (COLT), 2004
【非特許文献５】Zhili Wu, Chun-hung Li, Ji Zhu, Jian Huang, "A Semi-Supervised SVM for Manifold Learning", Proceedings of the 18th international conference on pattern recognition(ICPR'06), Vol.2, pp.490-493, 2006
【発明の概要】
【発明が解決しようとする課題】
【００１５】
上記方法と同様に、従来の半教師あり学習手法では、ほぼサンプル点のユークリッド距離に基づいて近傍グラフ（隣接行列）を構築し、近傍グラフがサンプル点の内在マニホールド構造を完全に反映することを想定している。すなわち、元の空間におけるサンプル点のユークリッド距離がマニホールド構造における「測定距離」に等しいものとされている。しかしながら、そのように想定は、しばしば適切ではなく、正確ではないことがある。この問題は、例えば上記の非特許文献５や参考文献１（Joshua B. Tenenbaum, Vin de Silva, John C. Langford, "A global geometric framework for nonlinear dimensionality reduction", Science, Vol.290, pp.2319-2323, 2000）などで述べられている。
【００１６】
図１−１と図１−２では、具体的に例を挙げてその問題を示している。図１−１は、三次元空間における「Ｓ」と似たような形状のマニホールド構造であり、図１−２は該マニホールド構造に対応するサンプル点、すなわちサンプルセットである。図１−２において、階調によってサンプル点の目標値を表すようにし、データサンプル点の階調値が近いほど、それらのデータサンプル点が互いに類似することと意味する（「Ｓ」形状の二つの端点を除く）。当該空間における二つのデータ点Ａ、Ｂのユークリッド距離は図１−２の実線で示されており、これらの二つの点のマニホールド構造における測定距離は図１−２の点線で示されている。図１−２からわかるように、ユークリッド距離によってデータ点の内在マニホールド構造を表すのは的確ではない。したがって、ユークリッド距離に基づいて構築された近傍グラフがサンプル点の内在マニホールド構造を完全に表現すると仮定することはできないため、この仮定の下で実施される従来の方法には不備が存在しており、その機能向上には限界がある。
【００１７】
開示の技術は、上記に鑑みてなされたものであって、ユークリッド距離に基づいて構成される近傍グラフによってサンプル点の内在マニホールド構造を的確に反映することができるパターン識別装置およびパターン識別方法を提供することを目的とする。
【課題を解決するための手段】
【００１８】
本願が開示するパターン識別装置は、一つの態様において、識別対象パターンのデジタル化された特徴および当該特徴に対応する目標値を含むラベル有りサンプルと、ラベル無しサンプルとを含み、デジタル化された特徴で表現される識別対象パターンのサンプルを半教師あり学習メカニズムによって識別するパターン識別装置であって、入力された識別対象パターンのサンプルに基づき、識別対象パターンのマニホールド構造を構築するのに適する非ユークリッド空間のカーネル行列を構成する非ユークリッド空間カーネル構成部と、前記非ユークリッド空間カーネル構成部によって構成された非ユークリッド空間のカーネル行列に基づき、識別対象パターンのサンプルに局部線形埋め込みを行って識別対象パターンのサンプルの再構成係数行列を生成する核空間内局部線形埋め込み部と、前記核空間内局部線形埋め込み部によって生成された再構成係数行列と前記ラベル有りサンプルの目標値に基づき、入力されたすべての識別対象パターンのサンプルに対して評価値を生成する正則化部と、を備える。
【００１９】
また、パターン識別方法は、一つの態様において、識別対象パターンのデジタル化された特徴および当該特徴に対応する目標値を含むラベル有りサンプルと、ラベル無しサンプルとを含み、デジタル化された特徴で表現される識別対象パターンのサンプルを半教師あり学習メカニズムによって識別するパターン識別方法であって、入力された識別対象パターンのサンプルに基づき、識別対象パターンのマニホールド構造を構築するのに適する非ユークリッド空間のカーネル行列を構成するステップと、構成された非ユークリッド空間のカーネル行列に基づき、識別対象パターンのサンプルに局部線形埋め込みを行って識別対象パターンのサンプルの再構成係数行列を生成するステップと、生成された再構成係数行列と前記ラベル有りサンプルの目標値に基づき、入力されたすべての識別対象パターンのサンプルに対して評価値を生成するステップと、を備える。
【発明の効果】
【００２０】
本願が開示するパターン識別装置およびパターン識別方法の一つの態様によれば、識別対象パターンのサンプルの内在マニホールド構造を的確に表すと共に、最終的に適正なパターン識別を実現することができるという効果を奏する。
【図面の簡単な説明】
【００２１】
【図１−１】図１−１は、三次元空間におけるマニホールド構造の一例を示す図である。
【図１−２】図１−２は、マニホールド構造に対応するサンプルセットの一例を示す図である。
【図２】図２は、実施形態におけるパターン識別装置の構成を示す機能ブロック図である。
【図３】図３は、ラプラシアンカーネル構成モジュールの構成を示す機能ブロック図である。
【図４】図４は、実施例１に係る対象サンプルの概念図である。
【図５】図５は、実施例１に係る対象サンプルの評価値の概念図である。
【図６】図６は、実施例２に係る入力画像の一例を示す図である。
【発明を実施するための形態】
【００２２】
以下に、本願の開示するパターン識別装置およびパターン識別方法の実施の形態および実施例を図面に基づいて詳細に説明する。なお、この実施の形態および実施例によりこの発明が限定されるものではない。
【００２３】
本実施の形態においては、入力される識別対象パターンにラベル有りサンプルおよびラベル無しサンプルが含まれており、それらサンプルに基づき、パターン識別装置がサンプルの空間分布特徴を解析してラベル無しサンプルの識別を完了する（分類およびソーティング）。パターン識別装置の特徴として、核空間に局部線形埋め込みで入力対象のマニホールド構造を推定し、推定されたマニホールド構造を基にグラフの正則化によって識別の機能を実現する。
【００２４】
まず、入力される対象サンプルの二つずつの間の距離を算出する。すなわち、任意の二つの対象サンプル間の距離を算出する。距離の算出は、入力対象サンプルの形式と種類に関連している。パターン識別において、通常は、入力対象サンプルに対して処理を行ってその主な特徴が抽出される。例えば、手書き数字の識別では、特徴が入力対象サンプルである画像の画素値であっても、筆画の方向のヒストグラムであってもよい。発話者の生体識別では、特徴が音声信号で得られたＭＦＣＣや基本周波数などであってもよい。入力対象サンプルの特徴がベクトルとして表現されれば、ユークリッド距離やその他の距離で対象サンプルの間の距離を測定して算出することができ、入力対象サンプルの特徴が構造化される特徴として表現されれば、当該特徴と対応する距離計算方式を使うことになる。
【００２５】
また、得られた入力対象サンプルの二つずつの間の距離に基づき、ｋ隣接方式でｋ近傍グラフが構築され、言い換えれば、図形で入力対象サンプルの間の関係が表される。
【００２６】
そして、近傍グラフに基づき例えばラプラシアン核空間（Laplacian Kernel Space）などの再生核ヒルベルト空間（Reproducing Kernel Hilbert Space）が構成され、構成された空間において局部線形嵌め込みが行われる。更に説明すると、それぞれのサンプルについて、核空間における隣接サンプルによる線形再構成が行われるようにし、すべてのサンプルの再構成係数によってサンプルの内在空間分布特徴を精度よく表す。
【００２７】
最後に、再構成係数およびラベル有りサンプルの目標値を使い、グラフの正則化の技術によって、ラベル無しサンプルに評価値を与える。この評価値は、ラベル無しサンプルを識別する根拠となる。
【００２８】
本実施形態の一つによれば、識別対象パターンのデジタル化された特徴および当該特徴に対応する目標値を含むラベル有りサンプルと、ラベル無しサンプルとを含み、デジタル化された特徴で表現され入力される識別対象パターンのサンプルを半教師あり学習メカニズムによって識別するパターン識別装置であって、入力された識別対象パターンのサンプルに基づき、識別対象パターンのマニホールド構造を構築するのに適する非ユークリッド空間のカーネル行列を構成する非ユークリッド空間カーネル構成部と、前記非ユークリッド空間カーネル構成部によって構成された非ユークリッド空間のカーネル行列に基づき、識別対象パターンのサンプルに局部線形埋め込みを行って識別対象パターンのサンプルの再構成係数行列を生成する核空間内局部線形埋め込み部と、前記核空間内局部線形埋め込み部によって生成された再構成係数行列と前記ラベル有りサンプルの目標値に基づき、入力されたすべての識別対象パターンのサンプルに対して評価値を生成する正則化部と、を備えるパターン識別装置が提供される。
【００２９】
本実施形態の他の一つによれば、識別対象パターンのデジタル化された特徴および当該特徴に対応する目標値を含むラベル有りサンプルと、ラベル無しサンプルとを含み、デジタル化された特徴で表現される識別対象パターンのサンプルを半教師あり学習メカニズムによって識別するパターン識別方法であって、入力された識別対象パターンのサンプルに基づき、識別対象パターンのマニホールド構造を構築するのに適する非ユークリッド空間のカーネル行列を構成するステップと、構成された非ユークリッド空間のカーネル行列に基づき、識別対象パターンのサンプルに局部線形埋め込みを行って識別対象パターンのサンプルの再構成係数行列を生成するステップと、生成された再構成係数行列と前記ラベル有りサンプルの目標値に基づき、入力されたすべての識別対象パターンのサンプルに対して評価値を生成するステップと、を備えるパターン識別方法が提供される。
【００３０】
図２は本実施形態に関するパターン識別装置１００の機能ブロック図である。
【００３１】
図２に示すように、パターン識別装置１００は、入力された対象サンプル（ラベル有りサンプルとラベル無しサンプルを含む）に基づき、ラプラシアンカーネル空間行列を構成するラプラシアンカーネル構成モジュール１１０と、ラプラシアンカーネル構成モジュール１１０で構成されたラプラシアンカーネル空間行列に基づき、入力された対象サンプルに対して局部線形埋め込みを行って、対象サンプルの再構成係数行列を生成する核空間内局部線形埋め込みモジュール１２０と、核空間内局部線形埋め込みモジュール１２０で生成された再構成係数行列とラベル有りサンプルの目標値に基づき、入力されたすべての対象サンプルに対して評価値を生成する正則化モジュール１３０と、を備える。
【００３２】
パターン識別装置１００は、上記ラプラシアンカーネル空間のほかにも、その他の再生核ヒルベルト空間を採用してもよい。これらの空間を構築するのは、入力された対象のマニホールド構造をよく反映することを目的としている。
【００３３】
入力対象は、画像識別における画像、音声識別における音声信号などのような処理される対象の集合となる。通常、入力対象は、複数の変数からなる数字の特徴で表される。数字の特徴は、これらの対象の特性を表すものであり、例えば画像識別においては、数字の特徴として、画像における各画素の色値、画像のテクスチャー特徴ベクトル、画像の色ヒストグラムなどがある。また、例えば発話者の生体識別においては、数字の特徴として音声信号に基づいて得られたＭＦＣＣ（mel-frequency cepstral coefficient）や基本周波数（fundamental frequency）などがある。入力対象にはラベル有りサンプルとラベル無しサンプルとが共に含まれている。ラベル有りサンプルとは、サンプルと対応する特徴に加え、サンプルと対応する目標値が含まれているものを指す。例えば、二種類の画像を識別する際に、第１の画像については、画像の目標値として１が設定され、第２の画像については、画像の目標値として−１が設定される。また、例えば発話者を生体識別する際には、目標値として発話者に対応する番号などが設定されていてもよい。一方、ラベル無しサンプルには、サンプルと対応する特徴のみが含まれている。
【００３４】
ラプラシアンカーネル構成モジュール１１０は、入力された対象サンプルからラプラシアンカーネル空間を構築するためものである。まずは、入力された対象サンプルの２つずつの間の距離を計算する。次に、ｋ近傍法に基づき近傍グラフを作成し、ラプラシアン空間行列を算出する。最後に、ラプラシアンカーネル空間行列を取得する。
【００３５】
核空間内局部線形埋め込みモジュール１２０は、ラプラシアンカーネル空間内において入力された対象サンプルの内在幾何構造を描くものである。更に、マニホールド構造を備えるデータセットにおいて、各対象サンプルは、無限小のエリアのいずれも線形なものなので、隣接サンプルの線形組み合わせによって再構成（もしくは近似）することができる。なお、再構成によって得られる再構成係数は、入力された対象サンプル集の幾何構造特徴を反映する。
【００３６】
正則化モジュール１３０は、ラベルが付けられていない対象サンプルの評価値を算出するものである。核空間内局部線形埋め込みモジュール１２０で得られた再構成係数に基づき、各対象サンプルがすべて隣接サンプルの線形組み合わせによって近似されるため、対象サンプルの評価値も再構成係数によって近似される。この原則により、グラフの正則化の下で最良な計算を行い、ラベル無しサンプルの評価値を取得する。
【００３７】
上記正則化モジュール１３０によって得られた評価値は、ラベル無しサンプルとラベル有りサンプルとの間の類似度を反映する。例えば、二種類のパターン識別において、第１のパターンのラベル有りサンプルの目標値を１とし、第２のパターンのラベル有りサンプルの目標値を−１とすれば、ラベル無しサンプルの評価値が１に近づくと、該サンプルが第１のパターンに属する確率が高く、逆に−１に近づくと、該サンプルが第２のパターンに属する確率が高いと考えられる。
【００３８】
次にパターン識別装置の各構成モジュールを具体的に説明する。
【００３９】
１．ラプラシアンカーネル構成モジュール１１０について
入力対象をＸ＝{ＸL,ＸU}とする。ただし、ＸL＝{(x1,y1),…,(xl,yl)}がラベル有りサンプル集であり、ｘ1,…,ｘlがそれぞれラベル有りサンプルの数字の特徴で、lがラベル有りサンプルの通し番号で、ｙ1,…,ｙlがそれらサンプルの目標値である。ＸU＝{xl+1,…,xn}がラベル無しサンプル集であり、ｘl+1,…,ｘnがそれぞれラベル無しサンプルの数字の特徴で、（ｎ−l）個のラベル無しサンプルがあり、ｎが入力サンプルの総数である。本明細書の他の部分においても、すべて同様に入力対象サンプル集を記載している。
【００４０】
図３は、ラプラシアンカーネル構成モジュール１１０の構成の機能ブロック図であり、ラプラシアンカーネル構成モジュール１１０は、隣接行列算出モジュール１１１と、ラプラシアン行列算出モジュール１１２と、ラプラシアンカーネル算出モジュール１１３との三つのモジュールを有している。
【００４１】
隣接行列算出モジュール１１１は、入力された対象サンプルの二つずつの間における距離に基づき、隣接行列を生成する。隣接行列は、サイズがｎ×ｎ（ｎは自然数）であり、任意の二つの対象サンプル間の類似度を記述するものである。
【００４２】
まず、任意の二つの入力対象サンプルに対して、それらの間の距離を算出する。距離の算出方式は、入力対象サンプルの表現方式に関連し、例えば、入力対象サンプルがベクトルとして表現される場合、ユークリッド距離という測定単位で距離が算出され、入力対象サンプルが構造化特徴として表現される場合、該特徴の具体的なフォーマットに従って距離が算出される。任意の二つの対象サンプルｘi、ｘjについて、それらの間の距離をｄ(i,j)とする。
【００４３】
次に、入力対象サンプルごとに、それぞれと最も近いｋ個の対象サンプルを探す。ｋは本実施形態におけるパターン識別装置１００を実現するための１パラメータであり、正の整数であり、経験的に適切な値が設定される。
【００４４】
隣接行列をＡ＝[ａij]、i,j＝1,2,…,nとする。隣接行列Ａにおける要素ａijの値は以下のように算出される。任意の二つの対象サンプルｘi、ｘjについて、ｘjがｘiに最も近いｋ個のサンプルの一つ、もしくはｘiがｘjに最も近いｋ個のサンプルの一つである場合は、ａij＝ａji＝exp（−ｄ(i,j)2／２σ2）となる。また、それ以外の場合には、ａij＝０となる。なお、ｉとｊの値が同じであれば、ａij＝０となる。σは本実施形態におけるパターン識別装置１００を実現するための他の１パラメータであり、入力対象サンプルの距離範囲を示す。σについては、あらゆる対象サンプル間の距離の平均値を設定してもよいし、経験的に適切な値を設定してもよい。
【００４５】
隣接行列を得てから、ラプラシアン行列算出モジュール１１２は、隣接行列に基づいてラプラシアン行列を生成する。Ｄをｎ×ｎの対角行列とし、対角線における各要素の値を
【数１】
0005115493.tif 000002
とすると、ラプラシアン行列Ｌは、Ｌ＝Ｄ−Ａによって算出される。正規化されたラプラシアン行列は、Ｌ~＝Ｄ-1/2ＬＤ-1/2＝Ｉ−Ｄ-1/2ＡＤ-1/2となる。ただしＩは単位対角行列である。
【００４６】
そして、正則化されたラプラシアン行列は、Ｐ＝ｒ(Ｌ~)＝Ｌ~＋ε・Ｉとなる。ただし、Ｉは単位対角行列である。また、εは本実施形態におけるパターン識別装置１００を実現するための１パラメータであり、通常は例えば１０-5のような非常に小さな値が設定される。
【００４７】
ラプラシアンカーネル算出モジュール１１３は、上記正則化されたラプラシアン行列に対してその逆行列を求め、ラプラシアンカーネルＫを取得する。正則化されたラプラシアン行列Ｐが逆行列を有さない場合には、擬似逆行列を算出する。
【００４８】
本実施形態におけるパターン識別装置１００は、ラプラシアンカーネル以外に、例えば拡散カーネル、反転余弦核などのその他の再生核ヒルベルト空間を採用することもできる。
【００４９】
拡散カーネルの構成過程は以下のようになる。
（1）上記ラプラシアンカーネルの構成過程と同じように、隣接行列算出モジュール１１１によって隣接行列Ａを算出する。
（2）上記ラプラシアンカーネルの構成過程と同じように、ラプラシアン行列算出モジュール１１２によって、隣接行列に応じて正規化されたラプラシアン行列Ｌ~を生成する。
（3）上記正規化されたラプラシアン行列Ｌ~に基づき拡散カーネルＫDを取得する。計算公式は、ＫD＝exp（−τ2／２Ｌ~）であり、τは本実施形態におけるパターン識別装置１００を実現するための１パラメータである。
【００５０】
反転余弦核の構成過程は以下のようになる。
（1）上記ラプラシアンカーネルの構成過程と同じように、隣接行列算出モジュール１１１によって隣接行列Ａを算出する。
（2）上記ラプラシアンカーネルの構成過程と同じように、ラプラシアン行列算出モジュール１１２によって、隣接行列に応じて正規化されたラプラシアン行列Ｌ~を生成する。
（3）上記正規化されたラプラシアン行列Ｌ~に基づき反転余弦核ＫCを取得する。計算公式は、ＫC＝cos（Ｌ~×π／４)である。
【００５１】
正則化ラプラシアン行列Ｐについては、内積が〈ｆ,ｆ〉H＝〈ｆ,Ｐｆ〉と定義される。Ｈは、再生核ヒルベルト空間（reproducing kernel hilbert spaces）であり、そのカーネルは、ｋ(i,j)＝[Ｐ-1]である。
【００５２】
その再生性を証明するためには、以下の条件を満たす必要がある。
ｆ(i)＝〈ｆ,ｋ(i,・)〉H
【００５３】
つまり、Ｈに属するすべてのｆについて、ｆ(i)＝〈ｆ,ｋ(i,・)〉H＝ｆTＰＫi,:、若しくはｆT＝ｆTＰＫとなる必要がある。
【００５４】
Ｋ＝Ｐ-1であれば、上記条件が満たされるのが明らかである。したがって、正則化されたラプラシアン行列の逆行列はラプラシアンカーネルである。
【００５５】
２．核空間内局部線形埋め込みモジュール１２０について
局部線形埋め込み（Locally Linear Embedding：一般に「ＬＬＥ」と略される）は、Sam T. Roweis氏らにより最初に提案されたものであり、詳細は参考文献２（Sam T. Roweis, Lawrene K. Saul, "Nonlinear dimensionality reduction by locally linear embedding", Science, Vol.290, pp.2323-2326, 2000）などに記載されている。ＬＬＥの基本的な思想は、対象サンプルごとに、その隣接点で局部線形モデルを構築することである。マニホールド構造のデータセットにおいて、各対象サンプルは、無限小のエリアのいずれも線形なものであるので、すべてのサンプル点がその隣接点の線形組み合わせによって再構成され、線形に埋め込まれる。そして、すべてのサンプル点の再構成係数が組み合わせられれば、データセットのマニホールド構造が描かれることになる。ＬＬＥは、元々、特徴次元の削減（Reduced Feature Dimension）に適用されていたが、Sam T. Roweis氏らは以下のことを発見した。回転、平行移動、拡縮などのような隣接関係を保留する変換において、ＬＬＥから得られた再構成係数が不変性という特性を備えているため、サンプル点が低次元のマニホールド構造空間における隣接関係と、その原始空間における隣接関係とは一致しており、言い換えれば、原始空間から得た再構成係数がマニホールド構造空間にも同じく適用される。この発見によれば、ＬＬＥが特徴次元の削減に適していることがわかる。
【００５６】
本実施形態におけるパターン識別装置１００は、その局部線形埋め込みが核空間において、より具体的には、ラプラシアンカーネル空間において行われる。
【００５７】
データサンプル集Ｘ＝{x1,・・・,xn}（該サンプル集には、ラベル有りサンプルとラベル無しサンプルが含まれる）とラプラシアンカーネル関数Ｋについて、カーネル関数Ｋは、実際にサンプル集Ｘにおけるマッピング関数φを定義しており、該関数によって、データサンプルが高次元の空間Ｆに投射される。すなわち、マッピング関数φによってφ：ｘi→φ(ｘi)となり、該マッピングはｋ(x,x')＝〈φ(x),φ(x')〉という内積関係を満たしている。
【００５８】
そして、空間Ｆにおける任意のφ(xm)とφ(xn)の二つのサンプルについて、それらのユークリッド距離は、‖φ(xm)−φ(xn)‖2＝ｋ(m,m)＋ｋ(n,n)−２ｋ(m,n)となる。
高次元空間Ｆにおいて、サンプルごとにその隣接サンプルの線形組み合わせを使って近似（すなわち再構成）する。この再構成の総誤差は、
【数２】
0005115493.tif 000003
となる。
【００５９】
上記の式において、Ｎ(φ(xi))は空間Ｆにおいてサンプルｘiに隣接するサンプルを表し、ｗijはサンプルｘiの再構成係数を表す。
【００６０】
サンプルｘiを例に挙げれば、高次元空間ＦにおけるサンプルｘiのＭ個の隣接サンプルを{xi1,・・・,xiM}とし、そのＭ個の隣接サンプルがｘiに対して再構成する際の係数をＷi＝[wi1,・・・,wiM]Tとすると、再構成誤差は
【数３】
0005115493.tif 000004
である。
【００６１】
ただし、Ｃiはφ(xi)のグラム行列（Gram Matrix）であり、そのサイズがＭ×Ｍである。また、行列Ｃiにおける各要素の値は、それぞれＣi(m,n)＝(φ(xi)−φ(xim))T(φ(xi)−φ(xin))＝ｋ(xim,xin)−ｋ(xi,xin)−ｋ(xim,xi)＋ｋ(xi,xi)である。
【００６２】
したがって、再構成誤差を最小にする再構成係数は、
【数４】
0005115493.tif 000005
であることが明らかである。
【００６３】
核空間内局部線形埋め込みモジュール１２０の入出力、およびそのモジュール１２０が実行する主なステップを以下に示す。
入力：データサンプル集ＸおよびラプラシアンカーネルＫ
出力：各データサンプルの再構成係数行列Ｗ
核空間内局部線形埋め込みモジュール１２０は、サンプルｘiごとに以下の動作を実行する。
（1）高次元空間Ｆにおいて該サンプルとその他のサンプルとのユークリッド距離を算出する。すなわち、上述した式‖φ(xi)−φ(xj)‖2＝ｋ(i,i)＋ｋ(j,j)−２ｋ(i,j)、j＝1,2,・・・,nを用いて、ユークリッド距離を算出する。
（2）上記ユークリッド距離に基づき、ｘiと最も近いＭ個のサンプル{xi1,・・・,xiM}を探す。Ｍは本実施形態におけるパターン識別装置１００を実現するための１パラメータであり、正の整数である。Ｍには、ラプラシアンカーネル構成モジュール１１０のパラメータｋと同一値を設定することができる。
（3）サイズがＭ×Ｍであるグラム行列Ｃiを算出する。
（4）グラム行列Ｃiに基づき再構成係数Ｗi＝[wi1,・・・,wiM]Tを算出する。
（5）再構成係数を正規化し、Ｗiのモード（mode）を１にする。
（6）再構成係数行列Ｗを生成する。該行列のサイズはｎ×ｎであり、行列の各行がそれぞれ一つのサンプルの再構成係数に対応しており、最も近いＭ個のサンプルについては、要素の値はＷiに対応する値であり、それ以外の要素の値は０となる。
【００６４】
３．正則化モジュール１３０について
入力対象サンプルＸ＝{x1,・・・,xl,xl+1,・・・,xn}およびラベル有りサンプルに対応する目標値{y1,・・・,yl}について、正則化モジュール１３０は、サンプルに対する評価値を生成するものである。言い換えれば、正則化モジュール１３０からマッピング関数のｆ：Ｘ→Ｒが取得され、該関数により入力された対象サンプルが実数の評価値になるように投射される。該関数は、ベクトルとして表すことができ、ｆ＝{f1,・・・,fn}となる。
【００６５】
上記核空間内局部線形埋め込みモジュール１２０は、入力された対象サンプルに対して一連の再構成係数を生成する。この再構成係数に基づき、各サンプルがその隣接サンプルの線形組み合わせによって近似されるようになる。さらに、再構成係数は、対象サンプルの内在幾何構造を反映しており、隣接関係を保留する変換において不変性を備えている。そのため、再構成係数は対象サンプルの評価値の再構成に適用され、再構成係数に基づいて、対象サンプルごとの評価値をその隣接サンプルの評価値の線形組み合わせによって近似することが可能である。
【００６６】
サンプルの評価値に対する再構成の誤差は
【数５】
0005115493.tif 000006
である。
【００６７】
ただし、Ｗijは、上記核空間内局部線形埋め込みモジュール１２０から得られ対象サンプルｘiに関連する再構成係数を表す。
【００６８】
なお、ラベル有りサンプルについては、正則化モジュール１３０によって得られた評価値は、それぞれの目標値と大きく相違しないはずである。{y1,・・・,yl}をラベル有りサンプルの目標値とし、{yl+1,・・・,yn}の値を０とした場合、ｙ＝{y1,・・・,yn}rとすれば、評価値の制限条件は
【数６】
0005115493.tif 000007
と表される。
【００６９】
この制限条件と再構成誤差の制限線形とを一体に組み合わせれば、
【数７】
0005115493.tif 000008
という式が得られる。ただし、Ｗは核空間内局部線形埋め込みモジュール１２０から得られた再構成係数行列を表し、μは本実施形態におけるパターン識別装置１００を実現するための１パラメータであり、通常、例えば１０-3のような非常に小さな実数を取る。また、Ｍは、Ｉを単位行列とすれば、Ｍ＝(Ｉ−Ｗ)T(Ｉ−Ｗ)を満たす。
【００７０】
関数ｆの値は、上記ε(f)の値を最小にする値である。すなわち、
【数８】
0005115493.tif 000009
である。
【００７１】
ε(f)の導関数を求めると、最終的にｆの値は、ｆ＝μ(Ｍ＋μＩ)-1ｙと得られる。
【００７２】
正則化モジュール１３０によって実行される主なステップを以下に示す。
入力：核空間内局部線形埋め込みモジュール１２０から出力されたサンプルの再構成係数行列Ｗおよびラベル有りサンプルの目標値{y1,・・・,yl}
出力：サンプルの評価値ベクトルｆ
（1）ベクトルｙ＝[y1,・・・,yn]Tを生成する。ただし、{y1,・・・,yl}はラベル有りサンプルの目標値で、{yl+1,・・・,yn}の値は０である。
（2）行列Ｍ＝(Ｉ−Ｗ)T(Ｉ−Ｗ)を算出する。
（3）評価値ベクトルｆ＝μ(Ｍ＋μＩ)-1ｙを算出する。
【００７３】
次に、さらに具体的な実施例について説明する。
【実施例１】
【００７４】
いずれも二次元ベクトルとして表現される１２個の入力された対象サンプルを以下に示す。
【数９】
0005115493.tif 000010
【００７５】
すなわち、一つ目のサンプルのベクトル値（座標値）は[0 10]で、二つ目のサンプルのベクトル値（座標値）は[3.1 9.5]で、以降のサンプルも同様である。
【００７６】
ただし、最初と最後の対象サンプルはラベル有りサンプルで、それらのラベル値がそれぞれ１と−１であり、残りの対象サンプルはラベル無しサンプルであり、すなわち、Ｙ＝[1 0 0 0 0 0 0 0 0 0 0 -1]である。
【００７７】
図４は、対象サンプルの概念図である。図４において、各点（dot）は、入力された対象サンプルに対応しており、各点の座標が対象サンプルのベクトルの値を示す。図４では、黒色の正方形と三角形が二つのラベル有りサンプルをそれぞれ表す。
【００７８】
本実施例は、すべてのラベル無しサンプルのラベル値を予測し、識別や類似検索などを実現することを目的としている。
【００７９】
ステップ１：ラプラシアンカーネル構成モジュール１１０は、入力された対象サンプルに対して処理を行って、ラプラシアンカーネルを構成する。
【００８０】
まず、任意の二つの入力された対象サンプル間の距離を算出する。本実施例では、入力された１２個の対象サンプルがすべて二次元ベクトルとして表されているので、ユークリッド距離でそれらの間の距離を算出する。例えば、一つ目と二つ目の対象サンプル間のユークリッド距離はｄ(1,2)＝{(3.1-0)2＋(10-9.5)2}0.5＝3.1である。
【００８１】
この方式によって得られる対象サンプルの二つずつの間の距離は、以下の行列で表される。
【数１０】
0005115493.tif 000011
【００８２】
これらの距離値に基づき、入力対象サンプルごとに、最も近いｋ個の対象サンプルを探す。本実施例においては、ｋの値を３とする。対象サンプルｘ1を例として説明すると、各入力対象サンプルのｘ1までの距離はそれぞれ、0、3.1、6.2、9.1、11.8、14.1、8.1、11.2、14.2、16.9、19.2、21.1であるので、ｘ1に最も近い３つの対象サンプルは、ｘ2、ｘ3、ｘ7となる。
【００８３】
その後、以下のような原則によって隣接行列を算出する。すなわち、二つの対象サンプルｘi、ｘjにつき、一方の対象サンプルが他方の対象サンプルと最も近いｋ個の対象サンプルに属する場合は、隣接行列において対応する要素はａij＝ａji＝exp（−ｄ(i,j)2／２σ2）となり、一方の対象サンプルが他方の対象サンプルと最も近いｋ個の対象サンプルに属さない場合は、対応する要素はａij＝０となる。また、隣接行列において、対角線上の要素の値を０とする。本実施例において、σはすべての対象サンプル間の距離の平均値と設定され、ここでは、上記で得られた対象サンプルの二つずつ間の距離に基づき、σの値が8.89となる。一つ目および二つ目の対象サンプルを例として説明すると、上記の計算からわかるように、二つ目の対象サンプルが一つ目の対象サンプルと最も近い３つの対象に属するため、隣接行列において対応する要素はａ12＝exp(-3.12／(2×8.892))＝0.94となる。
【００８４】
以上のような方式によって、隣接行列におけるあらゆる要素の値を算出することにより、下記の隣接行列が得られる。
【数１１】
0005115493.tif 000012
【００８５】
隣接行列を取得してから、ラプラシアン行列算出モジュール１１２は、隣接行列に基づきラプラシアン行列Ｌおよび正規化されたラプラシアン行列Ｌ~を生成する。
【００８６】
ラプラシアン行列Ｌを生成するために、まず対角行列Ｄを生成する必要がある。この対角行列の対角線における要素は、隣接行列における対応行の要素の和であり、例えば対角線における一つ目の要素は、隣接行列Ａの一行目の要素の和となる。すなわち、Ｄ(1)＝0.94＋0.79＋0.66＝2.39である。
【００８７】
対角行列Ｄと隣接行列Ａに基づき、ラプラシアン行列Ｌ、正規化されたラプラシアン行列Ｌ~および正則化ラプラシアン行列Ｐが容易に取得される。
【００８８】
最後に、正則化されたラプラシアン行列に対して逆行列を求め、ラプラシアンカーネルを取得する。本実施例においては、正則化されたラプラシアン行列におけるパラメータεの値が0.01と設定され、取得されたラプラシアンカーネルは下記のようになる。
【数１２】
0005115493.tif 000013
【００８９】
ステップ２：ラプラシアンカーネル空間において入力された対象サンプルに線形埋め込みを行う。
【００９０】
［ラプラシアンカーネル空間においてすべての対象サンプルの二つずつの距離の算出］
入力対象サンプルｘi、ｘjがラプラシアンカーネル空間において対応する距離はｋ(i,i)＋ｋ(j,j)−２×ｋ(i,j)である。一つ目および二つ目の対象サンプルを例とすると、これらの対象サンプルのラプラシアンカーネル空間における距離はｋ(1,1)＋ｋ(2,2)−２×ｋ(1,2)＝7.75＋10.40−2×8.19＝1.76である。
【００９１】
以上の方式によって得られる、それぞれ二つの入力対象に関するラプラシアンカーネル空間における距離は、下記のようになる。
【数１３】
0005115493.tif 000014
【００９２】
［核空間内線形埋め込み］
ラプラシアンカーネル構成モジュール１１０の動作と同様に、上記で得られた距離値に基づき、入力対象サンプルごとに、それぞれと最も近いＭ個の対象サンプルが見出される。本実施例では、Ｍの値をｋの値と同じくＭ＝３とする。入力対象サンプルｘ1を例とすると、それぞれの対象サンプルからｘ1までの距離は0、1.76、2.08、2.68、2.63、3.04、2.16、3.06、3.54、3.87、3.74、3.35なので、ｘ1と最も近い３つの入力対象サンプルはｘ2、ｘ3、ｘ7となる。
【００９３】
続いて、核空間内局部線形埋め込みモジュール１２０は、各入力対象サンプルの隣接対象サンプルを利用して入力対象サンプルを線形近似して、線形埋め込みを実現する。対象サンプルｘ1を例として説明する。上述したように、対象サンプルｘ1との距離が最も近い３つの対象サンプルがｘ2、ｘ3、ｘ7であるため、核空間内において、これらの３つの対象サンプルを使って対象サンプルｘ1を近似する。
【００９４】
まず、グラム行列Ｃを構築する。グラム行列はサイズが３×３で、行と列がそれぞれ入力対象サンプルｘ2、ｘ3、ｘ7に対応している。Ｃ(1,2)を例として計算すると、Ｃ(1,2)＝ｋ(x2,x3)−ｋ(x1,x2)−ｋ(x3,x1)＋ｋ(x1,x1)＝9.74−8.19−8.22＋7.75＝1.08となり、Ｃ(2,3)を例として計算すると、Ｃ(2,3)＝ｋ(x3,x7)−ｋ(x1,x7)−ｋ(x3,x1)＋ｋ(x1,x1)＝8.65−7.54−8.22＋7.75＝0.64となる。
【００９５】
以上の方式によって、以下のように入力対象サンプルｘ1と対応するグラム行列Ｃが取得される。
【数１４】
0005115493.tif 000015
【００９６】
そして、グラム行列に基づき、入力対象サンプルｘ1の再構成係数を取得すれば、その値は0.29、0.24、0.28であり、これらの３つの係数がそれぞれ入力対象サンプルｘ2、ｘ3、ｘ7に対応している。
【００９７】
［再構成係数行列の生成］
上述した処理によって入力対象サンプルごとの再構成係数が生成されると、その後、係数を正規化して再構成係数行列Ｗが生成される。
【００９８】
本実施例では、再構成係数行列のサイズは１２×１２である。再構成係数行列の各行には、それぞれ一つの入力対象サンプルが対応し、その中で対象サンプルと最も近い入力対象サンプルに対応する値が再構成係数と設定される。それ以外の値は０となる。入力対象サンプルｘ1を例として説明すると、対象サンプルｘ1の隣接対象サンプルはｘ2、ｘ3、ｘ7であり、対応する再構成係数は0.29、0.24、0.28である。再構成係数を正規化すれば、0.35、0.30、0.35となるので、再構成係数行列の一行目の内容は、0、0.35、0.30、0、0、0、0.35、0、0、0、0、0となる。
【００９９】
以上の動作に従って得られた再構成係数の行列Ｗは、
【数１５】
0005115493.tif 000016
となる。
【０１００】
ステップ３：正則化して入力対象サンプルの評価値を取得する。
【０１０１】
本実施例においては、一つ目および最後の入力対象サンプルをラベル有りサンプルとし、その標識値をそれぞれ＋１と−１とする。すなわち、入力対象サンプルの初期評価値は、Ｙ＝[1 0 0 0 0 0 0 0 0 0 0 -1]となる。
【０１０２】
まず、核空間内局部線形埋め込みモジュール１２０によって取得された再構成係数行列Ｗに基づき、以下のように行列Ｍが算出される。すなわち、Ｉを単位行列として、Ｍ＝(Ｉ−Ｗ)T(Ｉ−Ｗ)となる。結果を以下に示す。
【数１６】
0005115493.tif 000017
【０１０３】
本実施例においては、パラメータμの値を0.01とする。そして、ｆ＝ｕ(Ｍ＋ｕＩ)-1Ｙとして、各入力対象サンプルの評価値を算出する。ただし、Ｉは単位行列である。
【０１０４】
最終的に取得された入力対象サンプルの評価値は以下のようになる。
ｆ＝[0.061 0.074 0.071 0.064 0.044 0.005 -0.005 -0.044 -0.064 -0.071 -0.074 -0.061]
【０１０５】
図５は、本実施例における入力対象サンプルの評価値の概念図である。図５において、各入力対象サンプルが点で表されるほか、各点の階調が各対象サンプルの評価値に対応している。すなわち、データ点の階調値が近いほど、これらのデータ点に対応する入力対象サンプルが類似している。
【０１０６】
パターンの分類問題において、０を評価値の分類の境界とすると、前半の６個の入力対象サンプルが第１の種類に属し、後半の６個の入力対象サンプルが第２の種類にそれぞれ属するという分類結果が得られる。
【実施例２】
【０１０７】
本実施例におけるパターン識別装置１００は画像を識別するものであり、手書き数字画像の識別を例として説明を行う。
【０１０８】
本実施例におけるパターン識別装置１００については、入力が３０００個の手書き数字画像であり、すべでの画像が階調画像であり、画素の階調値が０から２５５の間に属し、各画像のサイズがいずれも１６×１６である。入力された３０００個の画像は、数字０から９のいずれかであり、それぞれの数字ごとに３００個の画像が含まれる。したがって、本実施例は１０種類の画像を分類する分類課題であり、それぞれの種類の画像には一つの数字が対応している。種類ごとの３００個のサンプルにおいては、最初の５つがラベル有りサンプルで、残りの２９５個がラベル無しサンプルであるものとする。
【０１０９】
図６に手書き数字の一部を例示している。本実施例では、入力画像における画素の階調値をそのまま入力対象サンプルの特徴量とするので、入力対象サンプルは、いずれも２５６次元のベクトルとして表すことができる。
【０１１０】
上記実施例１と同様に、本実施例の実現過程は以下のようになる。
【０１１１】
（1）ラプラシアンカーネル構成モジュール１１０が入力対象サンプルに対して処理を行い、ラプラシアンカーネルを構成する。
まず、入力対象サンプルにおける任意の二つの対象サンプル間の距離を算出して、サイズが３０００×３０００である行列を取得する。入力対象サンプルが２５６次元のベクトルとして表現可能であることから、ベクトルのユークリッド距離によって対象サンプル間の距離が算出される。
【０１１２】
そして、ｋ隣接原則に基づき、隣接行列Ａが算出される。本実施例では、ｋの値を１０とする。
【０１１３】
隣接行列Ａに基づき、ラプラシアン行列および正規化されたラプラシアン行列を取得することによって、カーネル行列のサイズが３０００×３０００であるラプラシアンカーネルＫを生成する。
【０１１４】
（2）ラプラシアンカーネル空間において入力対象サンプルに線形埋め込みをする。
この過程は上記実施例１の過程とほぼ同様である。ただし、核空間内線形埋め込みの動作においてパラメータＭの値を１０とする点が異なる。
【０１１５】
（3）正則化
実施例１の過程と同様に、核空間内局部線形埋め込みモジュール１２０によって得られた再構成係数行列Ｗに基づき、行列Ｍ＝(Ｉ−Ｗ)T(Ｉ−Ｗ)が算出される。ただし、Ｉは単位行列である。
【０１１６】
続いて、ラベル無しサンプルが各種類に属する確率をそれぞれ算出する。
【０１１７】
数字０に対応する第１の種類を例として説明を行う。まず、入力対象サンプルの初期評価値Ｙを生成する。Ｙは長さが３０００のベクトルであり、要素ごとに一つの入力画像が対応している。このベクトルにおいて、数字０のラベル有りサンプルに対応する要素の値は１となっており、残りの値は０となっている。次に、式ｆ0＝ｕ(Ｍ＋ｕＩ)-1Ｙによって、各サンプルが第１の種類に属する評価値を算出する。ただし、Ｉはサイズが３０００×３０００の単位行列であり、パラメータｕの値は５ｅ−４である。ｆ0は、長さが３０００であるベクトルであり、各入力対象サンプルと数字０との類似度を表す。
【０１１８】
数字１に対応する第２の種類を例として説明を行う。まず、入力対象サンプルの初期評価値Ｙを生成する。このベクトルにおいて、数字１のラベル有りサンプルに対応する要素の値は１となっており、残りの値は０となっている。次に、式ｆ1＝ｕ(Ｍ＋ｕＩ)-1Ｙによって、各サンプルが第２の種類に属する評価値を算出する。パラメータｕの値は、上記と同様に５ｅ−４である。ｆ1は、各入力対象サンプルと数字１との類似度を表す。
【０１１９】
以下同様に、数字０から９の１０種類に対してそれぞれ処理を行う。
【０１２０】
入力対象サンプルごとに１０個の評価値が得られ、それらの評価値は対象サンプルの１０個の数字に対する類似度を表している。対象サンプルを分類する際には、１０個の評価値のうち最大の評価値に対応する種類を対象サンプルの種類として選択する。
【０１２１】
本実施例によるパターン識別装置１００と非特許文献２の方法によってそれぞれ得られた識別率を次の表１に示す。
【表１】
0005115493.tif 000018
【０１２２】
この表１から、本実施例におけるパターン識別装置１００の方が識別率が高いことがわかる。
【実施例３】
【０１２３】
本実施例におけるパターン識別装置１００は発話者の生体識別に適用され、発話者の生体識別は、上記実施例２における手書き数字画像の識別とほぼ同様の処理で実現される。ただし、発話者の生体識別は、発話者の音声信号に基づいて行われると共に、発話者ごとに一つの種類が対応する点で異なる。
【０１２４】
まず、音声信号からＭＦＣＣ（mel-frequency cepstral coefficient）、差分のＭＦＣＣ、基本周波数（fundamental frequency）および差分の基本周波数という４種類の特徴を抽出して、その４種類の特徴からなるベクトルを入力音声信号のデジタル化表現特徴とする。
【０１２５】
そして、ラプラシアンカーネル構成、核空間内線形埋め込み、正則化などの過程をそれぞれ行うようにし、発話者の生体を識別する。そのような過程は実施例２における手書き数字についての識別の過程と類似しているため、ここでは説明を繰り返さない。
【０１２６】
上記の実施形態および実施例におけるパターン識別装置の各構成モジュールは、それぞれの機能を実現するコンピュータプログラムを備えるコンピュータやシングルボード機器と一体的に構成されても、独立した情報処理装置によってそれぞれ構成されてもよい。
【０１２７】
上記実施例においては、手書き数字の識別および発話者の生体識別を例として説明を行ったが、本発明はこれに限定されず、さまざまなパターン識別の場面に広く適用することができる。
【０１２８】
更に、本発明は、コンピュータやシングルボード機器に上記実施形態および実施例と同様の動作を実行させるコンピュータプログラムによって実現することも可能である。
【０１２９】
なお、各実施例において、専用の電子回路や線路（例えば連結して専門の機能を実行する離散論理ゲート）によって、一つ以上のプロセッサで実行されるプログラム指令によって、若しくは両者の組み合わせによって各動作が実行される。そのため、さまざまな異なった形式で変形された実施例を実施することが可能であり、これらの変形例は、いずれも本発明に属するとみなすことができる。そのような実施例は、いずれも「前記動作を実行するための論理を構成する」こと、または「前記動作を実行しまたは実行できる論理」とすることができる。
【０１３０】
また、本発明は、更にコンピュータで読み取り可能なプログラムが記憶された記録媒体によって実現することもできる。コンピュータで読み取り可能な記録媒体は、プログラムを記録することができ、実行システムや機器や装置で利用されるもの若しくは指令実行システムや機器や装置と結合されるいかなる媒体であってもよい。具体的な例として、コンピュータで読み取り可能な記録媒体には、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、記憶の消去・書き込みが可能な読み出し専用メモリ（ＥＰＲＯＭやフラッシュメモリ）、および光ディスク（ＣＤＲＯＭ）などが含まれる。
【０１３１】
上記の実施形態および実施例に関する説明は、例示および説明の目的に過ぎず、本発明をすべて列挙したものではなく、開示した具体的な形式によって本発明が制限されるものでもない。選択して記載された実施例は最良に本発明の原理およびその実応用を説明するものであり、当業者であれば、特許請求の範囲およびその均等物で限定される範囲から離れない状況でさまざまな修正や変形を行って実施例を応用することができると理解するはずである。
【符号の説明】
【０１３２】
１１０  ラプラシアンカーネル構成モジュール
１１１  隣接行列算出モジュール
１１２  ラプラシアン行列算出モジュール
１１３  ラプラシアンカーネル算出モジュール
１２０  核空間内局部線形埋め込みモジュール
１３０  正則化モジュール
【図１−２】
0005115493.tif 000019
【図２】
0005115493.tif 000020
【図３】
0005115493.tif 000021
【図４】
0005115493.tif 000022
【図５】
0005115493.tif 000023
【図６】
0005115493.tif 000024
【図１−１】
0005115493.tif 000025