(57)【要約】【課題】  大量の学習データから効率的にデータベースを作成し、未知データに関連した情報をそのデータベースから高速に検索することは難しい。【解決手段】  直交変換部１０は入力データを直交行列によって変換し、分散表現生成部２０は、離散空間において変換後の入力データの近傍点（エレメントともいう）を求め、入力データの分散表現を生成する。辞書生成部３０は、入力データの分散表現における各エレメントを検索キーとした最近点探索用辞書１１０を生成し、入力データのラベルを検索キーに対応づけて登録する。検索部４０は、未知データの分散表現における各エレメントを検索キーとして最近点探索用辞書１１０を検索し、検索キーにリンクされた学習データのラベルを最近点候補として最近点候補テーブル１３０に格納する。検算部５０は、最近点候補の学習データと未知データの内積を計算し、内積値が最大の最近点候補を未知データの最近点として出力する。【選択図】図１
2005242562.tif 000002
【特許請求の範囲】
【請求項１】
入力データを略直交行列により変換するデータ変換部と、
離散空間において、変換後の入力データの少なくとも１つの近傍点を求めることにより、前記入力データの分散表現を生成する分散表現生成部と、
生成された前記分散表現における前記少なくとも１つの近傍点の各々を検索キーとする辞書を生成する辞書生成部とを含み、
前記データ変換部が、複数の異なる略直交行列により前記入力データを変換して、前記分散表現生成部に与えることにより、前記入力データに対して複数の分散表現が生成され、分散表現毎に前記辞書が生成されることを特徴とするデータベース生成装置。
【請求項２】
前記辞書生成部は、前記検索キーに前記入力データが分類されるべきカテゴリーの識別情報を対応づけた辞書を生成することを特徴とする請求項１に記載のデータベース生成装置。
【請求項３】
離散空間において、入力データの少なくとも１つの近傍点を求めることにより、前記入力データの分散表現を生成する分散表現生成部と、
生成された前記分散表現における前記少なくとも１つの近傍点の各々を検索キーとする辞書を生成し、前記検索キーに前記入力データの識別情報を対応づけて前記辞書に登録する辞書生成部とを含むことを特徴とするデータベース生成装置。
【請求項４】
離散空間において、入力データの少なくとも１つの近傍点を求めることにより、前記入力データの分散表現を生成する分散表現生成部と、
生成された前記分散表現における前記少なくとも１つの近傍点の各々を検索キーとする辞書を生成し、前記検索キーに前記入力データが分類されるべきカテゴリーの識別情報を対応づけて前記辞書に登録する辞書生成部と、
分類先のカテゴリーが既知である入力データの学習サンプル集合をもとに、前記辞書内の第ｉ番目の検索キーに第ｊ番目のカテゴリーが対応づけられる回数Ｐｉｊを集計し、Ｐｉｊに対して単調に増加する関数ｆ（Ｐｉｊ）を用いて、分類の際のスコアの加算係数を求め、この加算係数を前記辞書内の前記ｉ番目の検索キーに対応づけられた第ｊ番目のカテゴリーの識別情報に関連づけて登録する加算係数決定部とを含むことを特徴とするデータベース生成装置。
【請求項５】
離散空間において、入力データの少なくとも１つの近傍点を求めることにより、前記入力データの分散表現を生成する分散表現生成部と、
生成された前記分散表現における前記少なくとも１つの近傍点の各々を検索キーとする辞書を生成し、前記検索キーに前記入力データの識別情報を対応づけて前記辞書に登録する辞書生成部と、
前記辞書に新しい入力データの識別情報が検索キーに対応づけられて登録される際、その検索キーに既に登録されている入力データの識別情報との間で識別情報のペアを生成し、当該識別情報のペアをその出現回数とともにテーブルに格納する分析部とを含むことを特徴とするデータ分析装置。
【請求項６】
離散空間における登録データの少なくとも１つの近傍点の各々を検索キーとする辞書と、
入力データを略直交行列により変換するデータ変換部と、
離散空間において、変換後の入力データの少なくとも１つの近傍点を求めることにより、前記入力データの分散表現を生成する分散表現生成部と、
生成された前記分散表現における前記少なくとも１つの近傍点の各々を検索キーとして用いて、前記辞書を検索する検索部とを含み、
前記データ変換部が、複数の異なる略直交行列により前記入力データを変換して、前記分散表現生成部に与えることにより、前記入力データに対して複数の分散表現が生成され、分散表現毎に前記少なくとも１つの近傍点の各々を検索キーとして用いて、前記辞書が検索されることを特徴とするデータベース検索装置。
【請求項７】
前記辞書は、前記検索キーに前記登録データの分類先のカテゴリーの識別情報のリストが対応づけられたものであり、
前記検索部は、前記入力データの各分散表現における前記少なくとも１つの近傍点の各々を検索キーとする検索でヒットした前記リスト内の前記カテゴリーの識別情報を累積ヒット数とともにテーブルに格納することを特徴とする請求項６に記載のデータベース検索装置。
【請求項８】
離散空間における登録データの少なくとも１つの近傍点の各々を検索キーとして、前記検索キーに前記登録データの識別情報のリストを対応づけた辞書と、
離散空間において、入力データの少なくとも１つの近傍点を求めることにより、前記入力データの分散表現を生成する分散表現生成部と、
生成された前記分散表現における前記少なくとも１つの近傍点の各々を検索キーとして用いて、前記辞書を検索し、ヒットした前記リスト内の前記登録データの識別情報をテーブルに格納することを特徴とするデータベース検索装置。
【請求項９】
前記検索部による検索でヒットした前記登録データと前記入力データ間の距離に関する値を求め、その距離に関する値をヒットした前記登録データの識別情報とともに前記テーブルに格納する検算部をさらに含むことを特徴とする請求項８に記載のデータベース検索装置。
【請求項１０】
離散空間における登録データの少なくとも１つの近傍点の各々を検索キーとして、前記検索キーに、前記登録データの分類先のカテゴリーの識別情報と分類の際のスコアの加算係数とからなるペアのリストを対応づけた辞書と、
離散空間において、入力データの少なくとも１つの近傍点を求めることにより、前記入力データの分散表現を生成する分散表現生成部と、
生成された前記分散表現における前記少なくとも１つの近傍点の各々を検索キーとして用いて、前記辞書を検索し、ヒットした前記リスト内の前記カテゴリーの識別情報を前記加算係数の累積値とともにテーブルに格納することを特徴とするデータベース検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明はデータベース技術に関し、特にデータベース生成装置、データ分析装置およびデータベース検索装置に関する。
【背景技術】
【０００２】
従来のデータ検索技術としては、未知のデータが与えられたとき、それと完全に一致するデータを検索する方法については、良いアルゴリズムが知られており、高速に検索を行う技術が確立されている。例えば、アドレスマッピング、ハッシュコード、バイナリサーチ、２分検索木、Ｂ木などのアルゴリズムがある。これらのアルゴリズムをもとにしてデータベース構造を定義すれば、目的のデータと一致するものを高速に見つけ出すようなデータ検索処理が実現できる。また、検索範囲を指定した検索も可能であり、例えば、データベースの中から、データの属性Ａが１００以上２００未満、属性Ｂが１．５以下、かつ、属性ＣがＴＲＵＥであるという条件のものを全て探し出すというような技術は実現されている。
【０００３】
未知のデータに対して、データベースの中から最も近いデータを見つけ出す方法も従来から知られている。たとえば、最も簡単な方法として、データベースのデータ全てのデータとの距離計算を行うことにより、最も近いデータを見つけ出すことができる。計算幾何学においては、種々の最近点探索アルゴリズムにより、最も近い点を効率的に探す処理方法が提案されている。これは地図情報システムなどの２次元空間における類似データ検索技術として実用化されている。
【０００４】
また、パターン認識分野においては、あらかじめ学習データを用いて辞書を作り、認識処理は、入力データと辞書とを何らかの方法で照らし合わせを行う。学習データをたくさん用意すれば性能のよい辞書ができるので、正確に認識処理を行うことができる。例えば、最近接探索法を用いると、学習データを極限まで増やせば認識の誤りを最小にすることができることが理論的に知られている。
【０００５】
特許文献１には、手本パターンに対応した複数の要素からなる特徴ベクトルをもとに特徴集合を形成し、特徴集合とカテゴリーとを対応付けた辞書を作成して、その辞書を用いて入力パターンのカテゴリーを判定するパターン認識装置が開示されている。
【特許文献１】特許第２９３７７２９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、与えられたデータに対してなるべく近いデータを検索するための一般的に有効な効率のよいアルゴリズムを開発することは難しい。与えられたデータに対して、データベースを総当りして検索する方法は、データ数が多くなると検索時間が増大するという欠点がある。また、従来技術の範囲検索というのは、ある一定の条件を満たすデータを見つけ出すことができるが、条件に最も合うデータを見つけ出す処理に適しているわけではない。条件に最も近いものから順番に候補を出すことは処理時間がかかるため、データベースが大きくなると、そのような目的を実現することは困難となる。
【０００７】
また、パターン認識の分野では、大規模なパターン認識処理を行わせようとすると、学習空間が巨大なものになり、学習に膨大な時間がかかるか、あるいは、認識に多大な時間がかかるという問題が生じてしまう。また、最近点探索アルゴリズムにおいては、高次元のデータを対象とする高速な検索方法は提案されていない。
【０００８】
今日では、大量の情報を戦略的に生かすことが求められてきている。すなわち、与えられたデータに対して、過去の膨大な蓄積の事例の中から似通った事例データの候補を見つけ出し、それを参考にして意思決定をするというような情報ツールが必要とされており、本当の意味でのデータ検索とは、このような実際的な検索が行えるべきものと言うことができる。しかしながら、そのためには、似ているデータを大量データの中から高速に見つけ出す処理が必要であり、規模が大きくなると、このような処理を効率よく行う方法は知られていない。
【０００９】
また、一般に、高速な類似データ検索を実現しようとすると、あらかじめそのような検索用のデータベースを作成しておくための処理時間が多大にかかってしまうという問題がある。
【００１０】
類似データを高速に検索できる理論的なアルゴリズムとしては、全てのデータの値が取り得るだけのアドレスを用意するという、巨大なメモリ空間を使う方法があるが、これでは、データベースの作成に時間がかかり、また、指数関数的な記憶空間を必要とするので、大量データの場合には現実的ではない。
【００１１】
このように、似ているデータを高速に検索が行えるようなデータベースの高速な作成方法は知られていない。実際問題として、データベース作成時間が遅い場合、データ件数が多くなると、現実的には実現不可能となる。例えば、仮にデータベース作成時間が、データ件数の高々２乗に比例するとしても、データ件数が１００万件の場合、１兆単位の時間がかかる。
【００１２】
このような状況のもと、データベースの作成を高速に行うことができ、そのデータベースを利用して、似ているデータを高速に検索できる技術が求められている。
【００１３】
本発明はこうした課題に鑑みてなされたものであり、その目的は、大量のデータの中から近いデータを高速に見つけ出し、また、このような高速なデータ検索が行えるデータベースを効率よく作成するためのータベース生成装置、データ分析装置およびデータベース検索装置を提供することにある。また、別の目的は、高性能なデータマイニングや知識情報処理、パターン認識技術に応用できる技術を実現することにある。
【課題を解決するための手段】
【００１４】
本発明のある態様はデータベース生成装置に関する。この装置は、入力データを略直交行列により変換するデータ変換部と、離散空間において、変換後の入力データの少なくとも１つの近傍点を求めることにより、前記入力データの分散表現を生成する分散表現生成部と、生成された前記分散表現における前記少なくとも１つの近傍点の各々を検索キーとする辞書を生成する辞書生成部とを含み、前記データ変換部が、複数の異なる略直交行列により前記入力データを変換して、前記分散表現生成部に与えることにより、前記入力データに対して複数の分散表現が生成され、分散表現毎に前記辞書が生成される。この構成によれば、入力データの多数の分散表現を用いたデータベースを作成して、検索精度を向上させることができる。
【００１５】
前記辞書生成部は、前記検索キーに前記入力データが分類されるべきカテゴリーの識別情報を対応づけた辞書を生成してもよい。
【００１６】
本発明の別の態様もデータベース生成装置に関する。この装置は、離散空間において、入力データの少なくとも１つの近傍点を求めることにより、前記入力データの分散表現を生成する分散表現生成部と、生成された前記分散表現における前記少なくとも１つの近傍点の各々を検索キーとする辞書を生成し、前記検索キーに前記入力データの識別情報を対応づけて前記辞書に登録する辞書生成部とを含む。この構成によれば、入力データの分散表現を用いたデータベースを作成して、未知データと関連性のある入力データを効率よく検索することができる。
【００１７】
本発明のさらに別の態様もデータベース生成装置に関する。この装置は、離散空間において、入力データの少なくとも１つの近傍点を求めることにより、前記入力データの分散表現を生成する分散表現生成部と、生成された前記分散表現における前記少なくとも１つの近傍点の各々を検索キーとする辞書を生成し、前記検索キーに前記入力データが分類されるべきカテゴリーの識別情報を対応づけて前記辞書に登録する辞書生成部と、分類先のカテゴリーが既知である入力データの学習サンプル集合をもとに、前記辞書内の第ｉ番目の検索キーに第ｊ番目のカテゴリーが対応づけられる回数Ｐｉｊを集計し、Ｐｉｊに対して単調に増加する関数ｆ（Ｐｉｊ）を用いて、分類の際のスコアの加算係数を求め、この加算係数を前記辞書内の前記ｉ番目の検索キーに対応づけられた第ｊ番目のカテゴリーの識別情報に関連づけて登録する加算係数決定部とを含む。この構成によれば、分類の際のスコアの加算係数を調整することで、１つの辞書による認識により、多数の辞書を用いて認識をしたのと同じ効果をもたらすことができ、辞書を格納するための記憶容量を節約するとともに、検索時間も短縮することができる。
【００１８】
本発明のさらに別の態様はデータ分析装置に関する。この装置は、離散空間において、入力データの少なくとも１つの近傍点を求めることにより、前記入力データの分散表現を生成する分散表現生成部と、生成された前記分散表現における前記少なくとも１つの近傍点の各々を検索キーとする辞書を生成し、前記検索キーに前記入力データの識別情報を対応づけて前記辞書に登録する辞書生成部と、前記辞書に新しい入力データの識別情報が検索キーに対応づけられて登録される際、その検索キーに既に登録されている入力データの識別情報との間で識別情報のペアを生成し、当該識別情報のペアをその出現回数とともにテーブルに格納する分析部とを含む。この構成によれば、辞書を作成する過程で、互いに関連性のある入力データのペアを検出することができる。
【００１９】
本発明のさらに別の態様はデータベース検索装置に関する。この装置は、離散空間における登録データの少なくとも１つの近傍点の各々を検索キーとする辞書と、入力データを略直交行列により変換するデータ変換部と、離散空間において、変換後の入力データの少なくとも１つの近傍点を求めることにより、前記入力データの分散表現を生成する分散表現生成部と、生成された前記分散表現における前記少なくとも１つの近傍点の各々を検索キーとして用いて、前記辞書を検索する検索部とを含み、前記データ変換部が、複数の異なる略直交行列により前記入力データを変換して、前記分散表現生成部に与えることにより、前記入力データに対して複数の分散表現が生成され、分散表現毎に前記少なくとも１つの近傍点の各々を検索キーとして用いて、前記辞書が検索される。
【００２０】
前記辞書は、前記検索キーに前記登録データの分類先のカテゴリーの識別情報のリストが対応づけられたものであり、前記検索部は、前記入力データの各分散表現における前記少なくとも１つの近傍点の各々を検索キーとする検索でヒットした前記リスト内の前記カテゴリーの識別情報を累積ヒット数とともにテーブルに格納してもよい。
【００２１】
本発明のさらに別の態様もデータベース検索装置に関する。この装置は、離散空間における登録データの少なくとも１つの近傍点の各々を検索キーとして、前記検索キーに前記登録データの識別情報のリストを対応づけた辞書と、離散空間において、入力データの少なくとも１つの近傍点を求めることにより、前記入力データの分散表現を生成する分散表現生成部と、生成された前記分散表現における前記少なくとも１つの近傍点の各々を検索キーとして用いて、前記辞書を検索し、ヒットした前記リスト内の前記登録データの識別情報をテーブルに格納する。
【００２２】
前記検索部による検索でヒットした前記登録データと前記入力データ間の距離に関する値を求め、その距離に関する値をヒットした前記登録データの識別情報とともに前記テーブルに格納する検算部をさらに含んでもよい。
【００２３】
本発明のさらに別の態様もデータベース検索装置に関する。この装置は、離散空間における登録データの少なくとも１つの近傍点の各々を検索キーとして、前記検索キーに、前記登録データの分類先のカテゴリーの識別情報と分類の際のスコアの加算係数とからなるペアのリストを対応づけた辞書と、離散空間において、入力データの少なくとも１つの近傍点を求めることにより、前記入力データの分散表現を生成する分散表現生成部と、生成された前記分散表現における前記少なくとも１つの近傍点の各々を検索キーとして用いて、前記辞書を検索し、ヒットした前記リスト内の前記カテゴリーの識別情報を前記加算係数の累積値とともにテーブルに格納する。
【００２４】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００２５】
本発明によれば、効率よくデータベースを作成して、データ検索を高速に行うことができる。
【発明を実施するための最良の形態】
【００２６】
本発明のいくつかの実施の形態を説明する。実施の形態の説明にあたって、詳細な構成と動作については、後述の［１］〜［６］節の技術詳細を適宜参照する。
【００２７】
実施の形態１
図１は、実施の形態１に係る最近点探索装置１００の構成図である。この構成は、ハードウエア的には、任意のコンピュータのＣＰＵ、メモリ、その他のＬＳＩで実現でき、ソフトウエア的にはメモリにロードされたプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウエアのみ、ソフトウエアのみ、またはそれらの組み合わせによっていろいろな形で実現できることは、当業者には理解されるところである。
【００２８】
本実施の形態の最近点探索装置１００は、大量のデータの中から未知データに最も近いデータすなわち最近点を探索するために用いられる。学習フェーズにおいて、学習データの集合が与えられ、最近点探索用のデータベースが作成される。認識フェーズにおいて、未知データが与えられ、最近点探索用のデータベースを用いて最も近い学習データが検索される。最近点探索装置１００による処理は、［２］節で詳しく説明される。
【００２９】
最近点探索装置１００における直交変換部１０、分散表現生成部２０、辞書生成部３０、および最近点探索用辞書１１０を格納したデータベース７０の構成は、入力データとして学習データの集合が与えられたとき、学習データの集合から最近点探索用辞書１１０を作成するものであり、本発明のデータベース生成装置の一例である。
【００３０】
直交変換部１０は、Ｎ次元の入力データをランダムな直交行列によって直交変換し、変換後の入力データを分散表現生成部２０に与える。ここで直交行列は、Ｎ×Ｎの行列Ｒの転置行列をＲＴと表すときに、ＲＴＲ＝Ｅを満たすような要素を実数にもつ正方行列のことである。ただし、ＥはＮ次元の単位行列である。直交行列によって定まる線形変換を直交変換といい、直交変換ｆは計量ベクトル空間Ｖにおいて内積を変えない。すなわち、ｘ、ｙがＶの任意のベクトルであるとき、（ｆ（ｘ），ｆ（ｙ））＝（ｘ，ｙ）が成り立つ。ただし、（，）は内積を表す。ｘ，ｙがＮ次元の超球面上にあり、ベクトルの大きさが一定であるなら、内積はｘ，ｙ間の距離に相当し、直交変換ｆはｘ、ｙ間の距離を保存する変換であるということができる。
【００３１】
直交変換部１０は、複数の異なるランダムな直交行列により入力データを直交変換することで、複数種類の変換後の入力データを生成して、分散表現生成部２０に与える。直交行列は、Ｎ個の互いに直交する単位ベクトルを行ベクトルとする行列であるから、一様にランダムな直交行列を作るには、一様にランダムなＮ個の互いに直交する単位ベクトルを作成すればよい。それには、Ｎ個の線形独立なＮ次元実数ベクトルをランダムに作成し、Gram-Schmidtの直交化法でそれぞれを互いに直交させればよい。
【００３２】
このように複数の異なる直交変換により入力データを変換するのは、分散表現生成部２０において離散的な空間に変換して量子化する際に、できるだけたくさんの量子化データを得るためである。なお、直交行列は厳密な意味で上記の定義を満たすものでなくてもよく、変換後にほぼ内積が保存されるような略直交行列であってもよい。直交変換部１０は、後述の［１．２．２．２］節に記載の処理を行う。
【００３３】
分散表現生成部２０は、所定の離散空間において、直交変換部１０による変換後の入力データの１つまたは複数の近傍点を求めることにより、入力データの分散表現を生成し、辞書生成部３０に与える。ここで近傍点の数に比べて離散空間の点の数は非常に大きいものとする。これにより入力データが１つまたは複数の近傍点に量子化される。
【００３４】
分散表現生成部２０は、直交変換部１０から複数の異なる直交行列により変換された複数種類の入力データを受け取り、１つの入力データに対して複数の分散表現を生成する。仮に分散表現生成部２０による分散表現が１つの近傍点しかもたないものであったとしても、複数の異なる直交行列により入力データが変換されることによって、入力データは複数の量子化データにより分散表現されることになる。分散表現生成部２０による入力データの分散表現への変換を分散コーディングという。
【００３５】
以下、入力データの分散表現をエレメント表現とも呼び、その場合、近傍点をエレメントと呼ぶ。分散表現生成部２０によるエレメント表現の具体的な作成方法は、［１］節で詳述する。
【００３６】
辞書生成部３０は、入力データの分散表現における各エレメントを検索キーとした最近点探索用辞書１１０をデータベース７０内に生成し、入力データのラベルを検索キーに対応づけて登録する。複数の異なる直交行列による変換で１つの入力データに対して、複数種類の分散表現が作られるため、辞書生成部３０は、これらの複数種類の分散表現の各々について最近点探索用辞書１１０を生成することになる。分散表現毎に最近点探索用辞書１１０を分けてもよく、すべての種類の分散表現について１つにまとめた最近点探索用辞書１１０を設けてもよい。
【００３７】
辞書生成部３０は、学習データの集合に含まれるすべての入力データについて、最近点探索用辞書１１０に登録する処理を行う。最近点探索用辞書１１０は、学習データの分散表現に出現するすべてのエレメントを検索キーとしてもつテーブルであり、各検索キーには学習データのラベルがリスト構造でリンクされている。なお、リスト構造と同等の機能を実現する各種の方法を利用してもよい。辞書生成部３０による最近点探索用辞書１１０の生成処理、および最近点探索用辞書１１０のデータ構造は、［２．２．１］〜［２．２．５］節で詳述する。
【００３８】
次に、入力データとして未知データが与えられたとき、未知データに最も近いデータを学習データの集合の中から見つける。最近点探索装置１００における直交変換部１０、分散表現生成部２０、検索部４０、および最近点探索用辞書１１０を格納したデータベース７０の構成は、入力データとして未知データが与えられたとき、最近点探索用辞書１１０を検索して、未知データに近いデータを探索するものであり、本発明のデータベース検索装置の一例である。
【００３９】
直交変換部１０は、未知データを直交変換し、分散表現生成部２０に与える。このとき、直交変換部１０は、学習データの場合と同一の直交行列により未知データを直交変換し、分散表現生成部２０に与える。分散表現生成部２０も、学習データの場合と同一の離散空間において、直交変換部１０による変換後の未知データの１つまたは複数の近傍点を求め、未知データの分散表現を生成する。直交変換部１０が、学習データの場合と同じように、複数の異なる直交行列により未知データを変換することにより、分散表現生成部２０において、未知データに対する複数種類の分散表現が生成される。
【００４０】
検索部４０は、未知データのそれぞれの分散表現における各近傍点（または各エレメント）を検索キーとして、データベース７０に格納された最近点探索用辞書１１０を検索し、検索キーに用いたエレメントにリンクされている学習データのデータラベルのリストを参照し、そのリスト内のすべての学習データのデータラベルをその出現回数とともに最近点候補テーブル１３０に格納し、検索結果記憶部８０に記憶する。
【００４１】
検索部４０は、未知データの分散表現におけるすべてのエレメントを検索キーとして、最近点探索用辞書１１０を検索し、得られた学習データのデータラベルを最近点候補のデータラベルとして最近点候補テーブル１３０に格納していく。その際、すでに最近点候補テーブル１３０にデータラベルが格納されている場合は、データラベルの出現回数を累積加算する。
【００４２】
検索部４０により、未知データの分散表現におけるすべてのエレメントについて検索が終わると、検算部５０は、検索結果記憶部８０に記憶された最近点候補テーブル１３０を参照して、最近点候補テーブル１３０内にリストされている最近点候補のデータラベルに対応する学習データと未知データの間の距離に関する評価値を計算する。具体的には、最近点候補である学習データと未知データの内積を計算し、その内積値を最近点候補のデータラベルに対応づけて最近点候補テーブル１３０に格納する。検算部５０は、内積が最も大きい最近点候補を未知データの最近点として出力する。
【００４３】
検算部５０は、最近点候補テーブル１３０内にリストされた最近点候補のすべてについて内積値を計算してもよいが、最近点候補テーブル１３０に各最近点候補の出現回数が格納されている場合は、出現回数の多い最近点候補から順に内積値を計算し、所定の順位で計算を打ち切って、その時点で内積値が最も大きい最近点候補を未知データの最近点として出力してもよい。
【００４４】
なお、検算部５０による検算を行わないで、検索部４０は、未知データの分散表現におけるすべてのエレメントについて、検索が終わると、検索結果記憶部８０に記憶された最近点候補テーブル１３０を参照して、出現回数の多い順にデータラベルを並べ替え、各データラベルに対応する学習データを未知データの最近点候補のリストとして出力してもよい。また、精度は落ちるが、検算部５０は、検算することなく、出現回数の最も大きいデータラベルに対応する学習データを最近点として出力してもよい。
【００４５】
実施の形態２
図２は、実施の形態２に係るパターン認識装置２００の構成図である。本実施の形態のパターン認識装置２００は、入力データをカテゴリーに分類するものであり、パターン認識に用いられる。学習フェーズにおいて、分類先のカテゴリーが既知の入力データの集合が学習サンプルとして与えられ、パターン認識用のデータベースが生成される。認識フェーズにおいて、未知データが与えられ、パターン認識用のデータベースを用いて未知データがカテゴリーに分類される。パターン認識装置２００による処理は、［３］節で詳しく説明される。
【００４６】
パターン認識装置２００の直交変換部１０および分散表現生成部２０は、実施の形態１と同じであるから説明を省略する。辞書生成部３０は、入力データの分散表現における各エレメントを検索キーとするパターン認識用辞書２１０をデータベース７０内に作成し、その検索キーに入力データのカテゴリーのラベルを関連づけて登録する。辞書生成部３０は、入力データの分散表現におけるすべてのエレメントについてパターン認識用辞書２１０に登録する処理を行う。複数の入力データについて辞書登録処理が行われることにより、エレメントに入力データのカテゴリーのリストがリンクづけられた構造のパターン認識用辞書２１０が生成される。
【００４７】
分類先のカテゴリーが未知である未知データが直交変換部１０に入力されると、分散表現生成部２０において未知データの分散表現が生成される。検索部４０は、未知データの分散表現における各エレメントを検索キーとして用いて、データベース７０に格納されたパターン認識用辞書２１０を検索し、その検索キーにリンクされたカテゴリーのリスト内のすべてのカテゴリーをその出現回数とともにカテゴリー候補テーブル２３０に格納し、検索結果記憶部８０に記憶する。このとき、既にカテゴリーがカテゴリー候補テーブル２３０に格納されている場合は、カテゴリーの出現回数を１だけインクリメントする。この出現回数がカテゴリーのスコアとなる。
【００４８】
検索部４０により、未知データの分散表現におけるすべてのエレメントを検索キーとしたパターン認識用辞書２１０の検索が終了すると、検索部４０は、出現回数の最も多いカテゴリーを未知データの分類先カテゴリーとして出力する。検索部４０は、カテゴリー候補テーブル２３０に格納されたカテゴリーのリストを出現回数の多い順に並べ替え、上位の所定数のカテゴリーのリストを分類先候補カテゴリーとして出力してもよい。
【００４９】
上記の説明では、検索部４０による検索でヒットしたカテゴリーのスコアを単純に出現回数でカウントしたが、カテゴリーのスコアの最適な加算係数を算出してもよい。加算係数決定部３５は、パターン認識用辞書２１０内の検索キーにリンクされたカテゴリー毎に加算係数を算出し、カテゴリーと加算係数からなるペアのリストを検索キーに登録する処理を行う。加算係数決定部３５によるカテゴリーのスコアの加算係数の算出処理は、［３．２．２］節に詳述する。
【００５０】
カテゴリーのスコアの加算係数がパターン認識用辞書２１０に登録されている場合、検索部４０は、カテゴリー候補テーブル２３０にカテゴリーを格納する際、パターン認識用辞書２１０に登録された加算係数を用いてスコアを累積加算する。検索部４０は加算係数により累積加算されたスコアにもとづいて最もスコアの高いカテゴリーを未知データの分類先カテゴリーとして出力する。
【００５１】
実施の形態３
図３は、実施の形態３に係る最近点対探索装置３００の構成図である。本実施の形態の最近点対探索装置３００は、入力データの集合が与えられたとき、距離の近い２つの入力データのペアを出力するものであり、［４］節で具体的な処理を説明する。
【００５２】
最近点対探索装置３００の直交変換部１０、分散表現生成部２０、および辞書生成部３０の構成は、実施の形態１と同じであるが、辞書生成部３０により生成された最近点探索用辞書１１０はデータベースとして検索用に活用されるのではなく、一時的に辞書記憶部７２に記憶され、分析部６０において利用された後は、メモリ容量の有効活用のために、適宜消去される。
【００５３】
分析部６０は、辞書生成部３０により新しい入力データのラベルが最近点探索用辞書１１０の検索キーに対応づけられて登録される際、その検索キーに既に登録されている入力データのラベルとの間でペアを生成し、最近点対候補テーブル３３０にそのラベルのペアを格納し、分析結果記憶部８２に記憶する。最近点対候補テーブル３３０には、ラベルのペアの出現回数を合わせて記憶する。
【００５４】
分析部６０は、最近点対候補テーブル３３０に格納された最近点対のリストを出現回数の多い順に並べ替え、所定の距離以内にある最近点対のリストを出力する。
【００５５】
なお、分析部６０により最近点対候補テーブル３３０に格納された最近点対について、検算部５０が最近点対の入力データ間の距離すなわち内積を計算してもよい。検算部５０は、最近点対候補テーブル３３０に格納された最近点対のリストを内積値の大きい順に並べ替え、所定の距離以内にある最近点対のリストを出力してもよい。
【００５６】
さらに、最も距離の近い最近点対が分析結果として得られればよい場合は、検算部５０は、分析部６０により最近点対候補テーブル３３０に最近点対が格納される度に、その最近点対について内積を求め、その時点までに得られた最近点対の内積値よりも大きい場合のみ、その最近点対と内積値を分析結果記憶部８２に記憶し、そうでない場合は最近点対を破棄してもよい。その時点までに得られた最大の内積値よりも大きな内積値を与える最近点対が新たに得られた場合は、内積の最大値を更新するとともに、その新たな最近点対を記憶し、前の最近点対は消去する。これにより、最近点対候補テーブル３３０を設けることなく、その時点までに得られた最大の内積値を与える最近点対とその内積値だけを記憶しておけばよく、メモリ容量を節約できる。
【００５７】
以下、本発明の実施の形態で利用される技術の詳細を説明する。
【００５８】
［１］エレメント集合の作成方法
［１．１］準備
データは、数値、項目などから構成され、計算機内部では２進表現されている。データを、ベクトル、点などと呼ぶこともある。最近点探索方法、パターン認識方法においては、あらかじめ用意されているデータのことを、学習データ、学習点、学習ベクトルなどと呼ぶことにする。未知のデータを、未知入力、未知データなどと呼ぶことがある。
【００５９】
［１．１．１］データの型
計算機で表現されるデータには、２値データ、実数データなどがある。これは数学的には２進ベクトル、実数ベクトルに対応する。例えば、２進ベクトル（１，０，１，０，１，１，０，０）は、１０１０１１００２と、８ビットのデータとして表現することができる。実数ベクトル（１０．５，３０．１１，４．０２，−１．５）は計算機では一般に浮動小数点形式で３２バイトのデータで表すことができる。
【００６０】
・バイナリ空間
要素の取り得る値が０か１だけのベクトルが作る空間をバイナリ空間と呼び、｛０，１｝Ｎと表記することにする。バイナリ空間のベクトルは、計算機では、Ｎビットのデータとして表すことができる。
【００６１】
・コンビネーション空間
バイナリ空間で、かつ要素の値が１である個数がｋ個であるベクトルが作る空間をコンビネーション空間と呼び、ＮＣｋと表記することにする。コンビネーション空間のベクトルは、計算機では、Ｎビットのデータとして表すことができる。
【００６２】
・実数空間
要素が実数値を取るベクトルが作る空間を実数空間と呼び、ＲＮと表記することにする。実数空間のベクトルは、計算機では、Ｎ個の実数値のデータとして表すことができる。例えば、浮動小数点形式を使用すればでＮ×８バイトで表現できる。
【００６３】
・階乗空間
０，１，…，Ｎ−１のＮ個の整数が作る置換をベクトルとして、その全体を階乗空間と呼び、Ｎ！と表記することにする。例えば、５次元の階乗空間は、（０，１，２，３，４），（０，１，２，４，３），…，（４，３，２，１，０）の１２０個のベクトル全体が作る空間である。
【００６４】
階乗空間のベクトルは、Ｎ個の整数値のデータとして表すことができる。４バイトの整数型を使用すれば、Ｎ×４バイトで表現できる。ただし、もっと少ないビット数でも表すことができる。０からＮ−１までの整数を表現するのには、ｃｅｉｌ（ｌｏｇ２Ｎ）ビットあれば足りるから、階乗空間のベクトルはＮ×ｃｅｉｌ（ｌｏｇ２Ｎ）ビットで表すことができる。ここでｃｅｉｌは切り上げを行う関数である。
【００６５】
・球面空間
空間上の全てのベクトルが同じ大きさのとき、全てのベクトルは原点を中心とする超球面上に乗っている。このような空間を球面空間と呼ぶことにする。
【００６６】
・単位実数空間
実数空間で、全てのベクトルの大きさが１であるとき、これを単位実数空間と呼び、ＥＮで表記することにする。
【００６７】
・離散的な空間
空間上のベクトルの数が有限個のとき、これを離散的な空間と呼ぶことにする。この空間上のベクトルは有限長のビットデータで表すことができる。
【００６８】
・双極値による空間
バイナリ空間、コンビネーション空間は、ベクトルの要素値として０，１の代わりに＋１，−１を取るものも考えられる。これらは、原点を中心とする超球面上に乗っているので、球面空間である。これは、｛０，１｝値を持つ元の空間を伸縮し、平行移動することによって球面空間に変換できる。
【００６９】
同様に階乗空間も、要素の値をｋ＝０〜Ｎ−１の代わりに、２ｋ−（Ｎ−１）の値を取ることによって球面空間になる。例えば、（０，１，２，３，４，５）は（−５，−３，−１，＋１，＋３，＋５）に変換される。
【００７０】
［１．１．２］距離の計算
空間上の２つのデータ間の距離を測るには、ユークリッド距離を用いる。または、ユークリッド距離に準じるものでもよい。例えばハミング距離でもよい。もしデータが球面空間上の点であるならば、距離は内積値を求めることによって測ることができる。
【００７１】
［１．２］データのエレメント表現
ベクトルを、たくさんのベクトルの集合によって表現するとき、その集合を構成する個々のベクトルをエレメントと呼び、もとのベクトルをこのように表現することをエレメント表現と呼ぶことにする。エレメントは、もとのベクトルとのなす角がある程度小さい必要がある。また、エレメントはある程度均等に分布している必要がある。
【００７２】
それぞれのエレメントは、何らかの形でもとのデータの情報の一部を保持しており、全体としてもとのベクトルと等価な情報か、または、ほぼ等価な情報を持っている。
【００７３】
［１．２．１］離散的な空間からのエレメント作成方法
例を挙げて説明する。
（ａ）
いま、データの型が３２ビットの２値データであるとする。例えば、
0000 0000 0000 0000 0000 0000 0000 0000  （１）
とする。
このデータから距離が１のものは、
1000 0000 0000 0000 0000 0000 0000 0000
0100 0000 0000 0000 0000 0000 0000 0000
…
0000 0000 0000 0000 0000 0000 0000 0001
の、３２個である。
こうすることによって、もとのデータをこの３２個のデータで表現することができる。これはエレメント表現の１つの例である。もとのベクトルが、３２ビットの任意の値を取るとき、個々のエレメントの値は２３２通りの値を取り得る。
【００７４】
また、（１）のデータについて、距離が２のものは、
1100 0000 0000 0000 0000 0000 0000 0000
1010 0000 0000 0000 0000 0000 0000 0000
…
0000 0000 0010 0000 0000 0001 0000 0000
…
0000 0000 0000 0000 0000 0000 0000 0011
の、４９６個である。これもエレメント表現として使用することができる。
【００７５】
（ｂ）
また、データの型が３２ビットの２値データで、ビット＝１である数が１６個であるようなデータであるとする。例えば、
1111 1111 1111 1111 0000 0000 0000 0000  （２）
とする。
このデータから距離が３で、かつ、ビット＝１である数が１３個であるようなものは、例えば
1101 1011 1111 1110 0000 0000 0000 0000
のようなものであり、これは全部で５６０個ある。これもエレメント表現として使用することができる。
【００７６】
（ｃ）
また、いまデータの型が３２ビットの２値データであるとする。例えば、
1111 1110 1100 1000 0000 0001 0011 0111  （３）
とする。
３２ビットのうちの４ビットを選んで、そのビットを＊とする。
**** 1110 1100 1000 0000 0001 0011 0111
いま、ビット０〜３、ビット４〜７、ビット８〜１１、ビット１２〜１５、ビット１６〜１９、ビット２０〜２３、ビット２４〜２７、ビット２８〜３１のビットを選んで、それぞれ＊にすると、８個のエレメントが作成される。このとき、全てのビットが１回ずつ平等に選ばれている。この方法のバリエーションはたくさんある。例えば、もっとたくさんの個数のエレメントで表現することもできる。
【００７７】
（ｄ）
また、いまデータが、Ｎ次元階乗空間のベクトルであるとする。これは、Ｎ次元の整数ベクトルとして表すことができる。例えば、Ｎ＝３２として、
(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31)（４）
とする。
要素が１０以上のとき１、それ以外のとき０として、３２ビットのデータを作ると、
0000 0000 0011 1111 1111 1111 1111 1111
となる。
また、１７以上のとき１、それ以外を０とすると、
0000 0000 0000 0000 0111 1111 1111 1111
となる。
また、２５以上のとき２、１５以上のとき１、それ以外を０とすると、
0000 0000 0000 0001 1111 1111 1222 2222
となる。
このようなものをたくさん用意すれば、それはエレメント集合となる。その場合、均等に分布しているとはいえないこともあるが、他の方法と組み合わせることによって、大体均等にすることができる。
【００７８】
［１．２．２］実数ベクトルからのエレメント作成方法
［１．２．２．１］実数ベクトルから離散的な空間へのデータの変換
いまデータが、Ｎ次元の実数ベクトルであるとする。実数ベクトルから、それになす角が一番近いような、離散的な空間上のベクトルへ変換することができる。例えば、実数ベクトルから、バイナリ空間、コンビネーション空間、階乗空間などへの変換は容易にできる。
【００７９】
実数ベクトルを、ｖ＝（ｖｉ）（ｉ＝０〜Ｎ−１）とする。
ｖｉ＞０のとき、１
ｖｉ≦０のとき、０
とすると、バイナリ空間のデータとすることができ、Ｎビットのデータで表せる。
【００８０】
ｖｉ（ｉ＝０〜Ｎ−１）のうちの大きいものｋ個を選んでビットを１にし、それ以外のビットを０にすると、コンビネーション空間のデータとすることができ、Ｎビットのデータで表せる。
【００８１】
いま、ベクトルの要素の大きいものから順番に並べて、
ｖｉ０，ｖｉ１，ｖｉ２，…，ｖｉＮ−１
となったとすると、（ｉ０，ｉ１，…，ｉＮ−１）は階乗空間のベクトルであり、これはビットデータとして表すことができる。
【００８２】
その他にも、いろいろな離散的な空間のベクトルに変換することができる。例えば、２４次元の単位実数空間Ｅ２４では、
ｖｉ＞ｃｏｓ（８４．８°）≒0.09063のとき、２
ｖｉ＞ｃｏｓ（−８４．８°）≒−0.09063のとき、１
ｖｉ≦ｃｏｓ（−８４．８°）のとき、０
とすると、これもビットデータで表すことができる。このデータはおよそ２２４通りの値を取り得る。なお、この閾値はｉ軸に垂直な平面によって２４次元超球面の表面積を３等分する値となっている。他の任意の閾値がデータ変換のために使用できるが、どのような値が適当かは実際の問題に応じて選択すればよい。
【００８３】
また、Ｎ次元実数ベクトルを、ｖ＝（ｖｉ）（ｉ＝０〜Ｎ−１）とするとき、ｖｉ０＞ｖｉ１＞ｖｉ２＞…＞ｖｉＮ−１であるとする。このとき、
ａ０＝ｖｉ０−ｖｉ１
ａ１＝ｖｉ１−ｖｉ２
…
ａＮ−２＝ｖｉＮ−２−ｖｉＮ−１
とおく。それを大きいものから順番に並べて、
ａｊ０，ａｊ１，ａｊ２，…，ａｊＮ−２
となったとすると、（ｉ０，ｉ１，…，ｉＮ−１，ｊ０，ｊ１，…，ｊＮ−２）はある離散的な空間のベクトルである。
【００８４】
以上はごく一部の例に過ぎず、離散的な空間への変換方法はまだたくさんある。また、いままで述べた方法を部分的に組み合わせることもできる。そうすることによっても、離散的な空間のベクトルに変換できる。変換方法は無数にあることが推察できるであろう。
【００８５】
また、ランダムなＮ×Ｎ直交行列を用意し、これをＲとする。Ｎ次元実数ベクトルｖにＲをかけてこれをＲｖとする。すると、Ｒｖを離散的な空間へ変換することができる。ランダムな直交行列は無数に作れるので、このことからもやはり、離散的な空間への変換は無数にあるということが言える。
【００８６】
［１．２．２．２］複数の離散的な空間
いま、離散的な空間が複数あるとする。実数ベクトルからそれぞれの空間上のベクトルへ変換することで、これはエレメント表現となり得る。ただしエレメントがある程度均等に分布するような離散的な空間を選ぶことが望ましい。
【００８７】
例えば次のような方法は有効である。ある離散的な空間をＱとする。一様にランダムな直交行列を多数用意し、これをＲ０，Ｒ１，…，Ｒｒ−１とする。Ｑ上の各点にＲをかけてできる空間を、Ｒ０（Ｑ），Ｒ１（Ｑ），…，Ｒｒ−１（Ｑ）とする。実数ベクトルｖからＲ０（Ｑ），Ｒ１（Ｑ），…，Ｒｒ−１（Ｑ）への変換によって、エレメント表現とすることができる。これらのエレメントはｖの近くにランダムに存在するので、ある程度数が多くなると、偏りが少なくなり、ほぼ均等に分布すると見なすことができる。
【００８８】
［１．２．３］離散空間上の近傍
今までは、もとのベクトルから離散空間上のなす角が最も小さいベクトルただ１つへ変換することを説明してきたが、なす角の小さい複数のベクトルを選ぶことも可能である。
【００８９】
例えば、いまベクトルが、
（１，２，４，５，６，８，９，１０，１１，１２）であるとする。
これに近いバイナリ空間｛−１，＋１｝Ｎのベクトル上位１６個は、
( 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
(-1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
( 1,-1, 1, 1, 1, 1, 1, 1, 1, 1)
(-1,-1, 1, 1, 1, 1, 1, 1, 1, 1)
( 1, 1,-1, 1, 1, 1, 1, 1, 1, 1)
(-1, 1,-1, 1, 1, 1, 1, 1, 1, 1)
( 1, 1, 1,-1, 1, 1, 1, 1, 1, 1)
(-1, 1, 1,-1, 1, 1, 1, 1, 1, 1)
( 1,-1,-1, 1, 1, 1, 1, 1, 1, 1)
( 1, 1, 1, 1,-1, 1, 1, 1, 1, 1)
(-1,-1,-1, 1, 1, 1, 1, 1, 1, 1)
(-1, 1, 1, 1,-1, 1, 1, 1, 1, 1)
( 1,-1, 1,-1, 1, 1, 1, 1, 1, 1)
(-1,-1, 1,-1, 1, 1, 1, 1, 1, 1)
( 1,-1, 1, 1,-1, 1, 1, 1, 1, 1)
( 1, 1, 1, 1, 1,-1, 1, 1, 1, 1)
となる。これらは、ベクトルの各要素、要素の２項和、３項和の大小関係を調べることにより見つけることができる。
【００９０】
例えば、［１．２．１］の（ｂ）の例は、３２Ｃ１６空間から３２Ｃ１３空間での近い点上位５６０個を選ぶことに相当する。
【００９１】
［１．２．４］ベクトルが超球面上にない場合の扱い
ベクトルが超球面上に乗っていない場合について説明する。いま、ＸがＮ次元実数ベクトルであり、どの要素も０．０〜１０．０の範囲の値を取るとする。すなわち超立方体の中にある点である。
Ｘ＝（ｘ０，ｘ１，…，ｘＮ−１）  ０≦ｘｉ＜１０．０
【００９２】
このとき、適当なαを選んで、
Ｙ＝（ｙ０，ｙ１，…，ｙ２Ｎ−２，ｙ２Ｎ−１）
ｙ２ｉ＝ｃｏｓ（α×ｘｉ×２×π／１０）
ｙ２ｉ＋１＝ｓｉｎ（α×ｘｉ×２×π／１０）
とすると、Ｙは超球面上の点となり、このような変換をしてデータベース作成、データ検索を行えばよい。
【００９３】
なぜなら、近いデータを検索するという目的のためには、局所的な距離関係が保存されればよいから、Ｘ１とＸ２が近いとき、｜Ｙ１−Ｙ２｜≒α｜Ｘ１−Ｘ２｜であるので、このように変換すればよいことがわかる。
【００９４】
（∵）
（ｃｏｓαａ−ｃｏｓαｂ）２＋（ｓｉｎαａ−ｓｉｎαｂ）２
＝２−２（ｃｏｓαａ・ｃｏｓαｂ＋ｓｉｎαａ・ｓｉｎαｂ）
＝２−２ｃｏｓα（ａ−ｂ）
＝２−２（１−２ｓｉｎ２α（ａ−ｂ）／２）
＝（２ｓｉｎα（ａ−ｂ）／２）２
α（ａ−ｂ）／２が０に近いとき、ｓｉｎα（ａ−ｂ）／２≒α（ａ−ｂ）／２と近似できるから、
（２ｓｉｎα（ａ−ｂ）／２）２
≒（２α（ａ−ｂ）／２）２
＝α２（ａ−ｂ）２
【００９５】
よって、√Σ（ｙ１ｊ−ｙ２ｊ）２≒α√Σ（ｘ１ｉ−ｘ２ｉ）２
∴｜Ｙ１−Ｙ２｜≒α｜Ｘ１−Ｘ２｜
【００９６】
このように、一般の実数ベクトルの場合は、超球面上に距離関係が大体保存されるように写像すればよい。距離関係が大体保存されるような写像はこの他にもいろいろある。各種の方法を使用することができる。
【００９７】
［１．３］まとめ
いろいろなデータ型からエレメント集合を作成する方法を具体的に説明した。エレメント作成方法は、いろいろな方法が無数にあり、また、それらをいろいろと組み合わせることもできる。
【００９８】
エレメントの作成は、もとのデータからなす角が小さい位置にあり、エレメント全体は偏りなく大体均等に分布するように作成する必要がある。そうすることによって、与えられたデータから、それに近いデータ、あるいは近いカテゴリーを高速に、精度良く見つけ出す方法が実現できる。詳細についてはこれから説明する。
【００９９】
［２］最近点探索方法
［２．１］完全一致検索
あらかじめ多数のデータが与えられており、ある未知のデータが提示されたとき、データの中から一致するものを見つけ出すことを完全一致検索と呼ぶ。このような機能を実現する方法は良く知られており、高速な検索処理を行うための各種の方法が提案されている。
【０１００】
与えられているデータ集合に対して、あらかじめ、完全一致検索に向くようなデータ構造を構築してデータを格納しておく。これをデータベースと呼ぶ。データベースはディスク上にある場合やメモリ上にある場合がある。それぞれ完全一致検索を行うための各種の処理方法が存在する。
【０１０１】
メモリ上にデータベースがあるとき、完全一致検索を行う良く知られたアルゴリズムには、２分木、ハッシュ法、バイナリーサーチ、線形サーチ、アドレスを直接参照する方法などがある。そのうちの１つの、ハッシュ法について簡単に説明する。
【０１０２】
図４は、ハッシュテーブルの一例を説明する図である。いま、生年月日と氏名の組が多数あるとする。ハッシュ法では、十分な大きさのハッシュテーブルを用意しておいて、生年月日からハッシュ値を計算し、テーブルのそのアドレスに生年月日と氏名を格納する。同じ生年月日を持つ人のデータが発生した場合を考えて、一般的には、生年月日と氏名情報へのリンクを格納しておく。氏名は別の格納場所を確保しておいて、そこに保存する。こうすることにより、任意の生年月日が与えられたとき、その日付と一致する生年月日の人の氏名を調べられるようなデータ構造を実現できる。
【０１０３】
本発明の実施の形態では、完全一致検索手法を利用して、未知のデータが与えられたときに、大量のデータの中から近いデータを高速に検索する機能を実現する。本発明の実施の形態ではデータはベクトルで表現できるものとし、近さの尺度としてユークリッド距離を使用する。なおユークリッド距離に準じるものでもよい。
【０１０４】
［２．２］最近点探索方法
最近点探索方法について説明する。あらかじめ用意されているデータを、学習データ、学習点、学習ベクトルなどと呼ぶことにする。未知のデータを、未知入力、未知データなどと呼ぶことにする。
【０１０５】
［２．２．１］ＮＣｋ空間の最近点探索方法の１例の説明
いま全てのデータが、２進表現で３２ビットであるものとし、ビット＝１の数が１６個であるとする。学習データ数は２２０＝１０４８５７６個であるとする。それぞれの学習データには名前（ラベル）が付けられている。それをＬ０，Ｌ１，…，Ｌ１０４８５７５とする。学習データは、一様にランダムに分布しているものとする。
【０１０６】
このとき、学習データをデータベースに格納する方法は次のように行う。図６に示すように、データのビット＝１である１６個の場所のうち１４個を選んで、そこのみをビット＝１とした３２ビットのデータを作成する。このような作成の仕方は組み合わせの数として１２０通りあるので、１２０個のデータができる。これをエレメントデータとする。エレメントを検索キーとしてエレメントデータと学習データのラベルの組をデータベースに格納する。これを１０４８５７６個の学習データ全てに対して行う。図５に、学習データのエレメントを検索キーとして、そのエレメントに学習データのラベルのリストをリンクさせた最近点探索用辞書の基本的なデータ構造の一例を示す。
【０１０７】
未知のデータが与えられたとき、最近点探索は次のように行う。未知データは学習データと同じく、３２ビットで、ビットが１である数は１６個であるとする。未知データは一様ランダムに発生するものとする。未知データも学習データに対して行ったのと同様に、１２０個のエレメントを作成する。すなわち、１の数が１４個であるような３２ビットのデータが１２０個できる。
【０１０８】
そのエレメントをキーとして、データベースの検索を行う。それにより、一致するエレメントに対応する学習データのラベルを取得することができる。見つかった学習データは、未知データと距離が４以内である。すなわち、未知データと高々４ビットの違いしかない。
【０１０９】
未知データの１２０個のエレメント全てについてデータベースを検索することによって、距離が４以内のデータを全て見つけ出すことができる。
未知データと距離＝０のものは、１２０回の検索で１２０回出現する。
未知データと距離＝２のものは、１２０回の検索で  １５回出現する。
未知データと距離＝４のものは、１２０回の検索で    １回出現する。
従って、ラベルごとに出現回数を集計すれば、距離の近いデータ順に順位付けすることができる。
【０１１０】
検索を行ったがデータを１つも見つけられない確率、すなわち、未知データから距離が４以内のデータが１つも存在しない確率は、７．８６×１０−１２である。従って、近いデータが見つからない可能性はほとんどない。平均的には、２５．６個のデータが見つかる。検索回数は、１２０回で、検索ヒット回数の合計は平均的に約３２回である。
【０１１１】
このようにして、未知データが与えられたとき、それから近いデータの情報を順位付けして正確に、かつ、高速に得ることができる。
【０１１２】
［２．２．２］非対称検索
先の説明では、学習データと未知データの種類は同じで、エレメントの作成方法も同じであったが、学習データと未知データの種類が異なり、エレメントの作成方法も異なる場合でも検索が可能であることを説明する。
【０１１３】
いま、学習データについては、先に述べた例を利用する。未知データは３２ビットで、ビットが１である数が１７個であるとする。図６に示すように、１７個のうちの１４個のビットを１にした３２ビットのデータを作成する。これは６８０個ある。これをエレメントデータとする。これを用いてデータベースを検索する。こうすることによって、未知データから距離が５以内のデータ全てを、順位付けして、正確にかつ高速に見つけ出すことができる。
【０１１４】
また、先の説明で、未知データが３２ビットでビット＝１である数が１６個の場合で、１２０回の検索をしてもデータが見つからなかったとき、未知データと距離が２のデータを作成する。距離が２かつ、ビット＝１である数が１６個のものであるから、１６×１６＝２５６により、これは２５６個ある。このそれぞれに対して１２０個のエレメントを作成して検索を行う。こうすることにより、いわば非常に見つけにくいデータでも見つけることができるようになる。
【０１１５】
［２．２．３］｛０，１｝Ｎ空間の場合の最近点探索方法の１例の説明
学習データは、２進表現で３２ビットであるとする。学習データ数は２２０＝１０４８５７６個であるとする。学習データは、一様にランダムに分布しているものとする。データの分布が一様ランダムではない場合についての補足説明は後で行う。
【０１１６】
エレメント作成方法を図７を参照して説明する。データ自分自身と同じものをエレメントの１つとする。これを０−エレメントとする。次に、データと１ビットだけ異なるデータは３２種類ある。これもエレメントとする。これを１−エレメントとする。次に、データと２ビットだけ異なるデータは４９６種類ある。これもエレメントとする。これを２−エレメントとする。こうして、５２９個のエレメントが作成される。
【０１１７】
ここでは、データベースを３つに分離する。データベース０に、０−エレメントと学習データのラベルの情報を格納する。データベース１に、１−エレメントと学習データのラベルの情報を格納する。データベース２に、２−エレメントと学習データのラベルの情報を格納する。それぞれのデータベースでの格納の仕方は、すでに説明してきたとおりである。
【０１１８】
未知データはやはり３２ビットであるとし、一様ランダムに発生するものとする。検索は次のように行う。まず、０−エレメントを作成し、データベース０を検索する。もしデータが見つかったならば、それは未知データから距離＝０すなわち、未知データと同一のデータである。
【０１１９】
データが見つからなければ、データベース１を検索する。ここでデータが見つかったならば、それは距離＝１のデータである。見つからない場合は、データベース２を検索する。ここで見つかれば、それは距離＝２のデータである。
【０１２０】
いずれの場合も見つからないときは、次に３２個の１−エレメントを作成する。そしてデータベース２を検索する。もしデータが見つかったならば、それは距離＝３のデータである。
【０１２１】
見つからないときは、４９６個の２−エレメントを作成し、データベース２を検索する。もしデータが見つかったならば、それは距離＝４のデータである。
【０１２２】
もし見つからないときは、未知データに対して３ビットだけ異なる４９６０個のデータを作成する。すなわちこれは３−エレメントと呼ぶべきものである。そしてデータベース２を検索する。もしデータが見つかったならば、それは距離＝５のデータである。
【０１２３】
もし見つからないときは、同様にして、４−エレメント、５−エレメント、６−エレメント  …、と順次作成し、データベース２を検索する。それにより、距離＝６、距離＝７、距離＝８  …、のデータを探し出すことができる。
【０１２４】
この方法においては、最近点が複数あった場合、それらを全て列挙することができる。上記方法によって検索したときの検索回数を見積もることができる。例えば未知入力に対する最近点が距離＝４であった場合、検索回数は１＋１＋１＋３２＋４９６＝５３１回となる。最近点が距離＝４以内に存在しない確率は、１．７９×１０−２６である。従って、検索回数は最悪の場合でも、ほぼ確実に５３１回以下であることが保証される。また、平均検索回数を計算するとおよそ１６１．２である。
【０１２５】
［２．２．４］一様ランダムでない場合
ここまでは、データの分布が一様ランダムであるという仮定のもとで、検索回数が少なくできることを見積もっていた。
【０１２６】
分布が一様ランダムではなく、分布に偏りがある場合について説明する。学習データの分布が一様ランダムでなくても、学習データと未知データの確率的な出現分布は等しいと仮定することができる。多くの実用の場合ではそのような前提を用いてよい。
【０１２７】
未知データが、学習データが疎に分布している場所に発生した場合、検索回数は一様ランダムの場合よりも大きくなる。逆に、未知データが、学習データが密の場所に発生した場合には、検索回数は一様ランダムの場合よりも小さくなる。未知データの発生の全ての場合で平均すると、どのような分布の場合でも、一様ランダムの場合の検索回数より小さくなる。
【０１２８】
［２．２．５］ＥＮ空間の場合の最近点探索方法の１例の説明
学習データ、未知データとも３２次元実数ベクトルであるとする。これは一般に、計算機の内部表現では、２５６バイトまたは１２８バイトのビットデータとして表現することができる。全てのデータは、大きさは１に正規化されているものとする。学習データ数は２２０＝１０４８５７６個であるとする。学習データは、一様にランダムに分布しているものとする。学習データをｘｉ（ｉ＝０〜１０４８５７５）とする。
【０１２９】
ランダムな３２×３２直交行列を多数用意する。例えば１００個とする。これをＲ−０〜Ｒ−９９と名前を付けることにする。学習データに直交行列Ｒ−０をかける。これをｒ０ｘｉとする。ｒ０ｘから、３２Ｃ９空間のうちで最も近い３２個の点を選ぶ。これらは３２ビットでビット＝１の数が９個であるデータとして表現することができる。これをエレメントとする。
【０１３０】
学習データ全てに対してこの操作を行い、エレメントと学習データの情報をデータベース０に格納する。残りの全ての直交行列に対しても同様の操作を行い、それぞれ、データベース１〜データベース９９に情報を格納する。
【０１３１】
次に、図８を参照して、未知入力からデータを検索する方法を説明する。未知入力ベクトルをｘ＊とする。基本的に、未知データも同様に、エレメントを作成し、データベース０〜データベース９９から学習データのラベルを取り出すのであるが、今まで説明してきた検索方法と異なる部分があるので、そのことを以下に説明する。
【０１３２】
いま仮に、１回目のエレメントの検索で、ラベルＬ７，Ｌ２０が見つかったとする。図８（ａ）に示すように、ラベルＬ７，Ｌ２０を検索済みテーブルに追加する。ｘ＊とｘ７、ｘ＊とｘ２０の内積を計算する。それぞれ、０．７０、０，７５であるとする。図８（ａ）に示すように、順位テーブルに、１位＝Ｌ２０，０．７５、２位＝Ｌ７，０．７０が入る。
【０１３３】
次に、２回目のエレメントの検索で、ラベルＬ３，Ｌ７，Ｌ３５が見つかったとする。
図８（ｂ）に示すように、ラベルＬ３は検索済みテーブルにないので、これをテーブルに追加する。そして、ｘ＊とｘ３の内積を計算し、これが０．８０であるとする。図８（ｂ）に示すように、順位テーブルの１位にＬ３，０．８０が入り、２位以下の順位が繰り下がる。
【０１３４】
Ｌ７は検索済みテーブルにあるので、内積計算は行わない。Ｌ３５は検索済みテーブルにないので、図８（ｂ）に示すように、テーブルに追加する。そして、ｘ＊とｘ３５の内積を計算し、これが０．７２であるとするとき、図８（ｂ）に示すように、順位テーブルの３位に入り、以下の順位が繰り下がる。
【０１３５】
エレメント検索操作を何回か行った状態を図８（ｃ）に示す。検索回数が多くなるほど、順位テーブルの１位に正解が入る可能性が高くなるし、また、２位以下も正しい順位となっている可能性が高くなる。
【０１３６】
エレメント検索を３２０回行ったとき、最近接点が見つかる確率は５割程度である。１０２４回の検索では約９割であり、３２００回行ったときはおよそ０．９９９となる。
【０１３７】
この方法により、次のような機能を実現することができる。不正確な答えでも良いから、短い時間で未知入力に近い何らかのデータの情報が得たい場合には、検索を少ない回数で打ち切る。処理時間に余裕があるとき、あるいは、正確な答えを得たい場合には、検索回数を多く行う。時間をかけるほど精度の高い答えを得ることができる。このように、適応的に処理時間と精度を調節できる性質は実用的に有効である。
【０１３８】
［２．２．６］精度を高める方法
前述した方法において、精度をさらに高める手段について説明する。１つは、学習データに対するエレメントの作成方法を変えること、すなわち一般にはエレメント数を多くするようにすれば良い。また、直交行列の数を多くすることも有効である。デメリットとして、これはデータベースのサイズを大きくする要因になる。
【０１３９】
２つめの方法としては、未知データのエレメント数を多くすることである。非対称検索として説明した方法が利用できる。デメリットとして、これは処理時間を増大させる要因になる。
【０１４０】
実際の目的とする処理に合わせて適切なパラメータを選択すればよい。
【０１４１】
［２．２．７］一般的なパラメータを決定する方法
今までの説明では、具体的なデータ型、次元数、学習データ数を与えて、特定のエレメント作成方法を示して説明をしてきた。
【０１４２】
本発明は特定の問題の状態に限定されず、もっと一般的に、不特定の問題にそれぞれ対処することができる。それにはデータ型、次元数、学習データ数に応じて、適切なエレメント作成方法などのパラメータを決定させてやればよい。エレメント作成方法についてはすでに説明したとおり、無数の各種の方法がある。
【０１４３】
データ型、次元数、学習データ数が与えられて、データの分布が仮定できるとき、エレメント作成方法ごとに、データサイズ、検索時間などの値が理論的に計算できる。従って、目的とする処理に応じて適切なパラメータを選択すればよい。現実的な応用の場面においては、データの分布型がわからないことも多々ある。その場合には、実際のデータを用いて、実験的にパラメータを見つけ出すことができる。
【０１４４】
実際の問題に対して、要求される検索速度、検索の精度、使用可能データ容量に応じて、最適なパラメータを選択すればよい。
【０１４５】
［３］パターン認識方法
本発明により、大量のデータの中から最近点探索を高速に行えることを説明してきたが、この方法はパターン認識にも利用できる。パターン認識は、未知のデータが与えられたとき、そのデータがどのカテゴリーに一番近いかを判定する問題である。カテゴリーの集合はあらかじめ決まっている。
【０１４６】
一般的なパターン認識の方法は、たくさんのデータとカテゴリーのラベルの組（これを学習データ、教師信号などと呼ぶ）を入手しておいて、そのデータを使って精度の高い認識が行えるようなデータ構造をあらかじめ作っておく。
【０１４７】
［３．１］ＮＮ（Nearest Neighbor）法
ＮＮ法は、学習データを辞書に格納しておき、未知のパターンが与えられたとき、辞書を検索して、一番距離の近いデータを特定し、そのデータに対応するカテゴリーを答えとして返す。
【０１４８】
ＮＮ法では、学習データをたくさん辞書に格納しておくことにより、認識率を極限まで高くできることが理論的に明らかとなっている。しかしながら、学習データを大量に辞書に使用すると、検索に時間がかかるので、認識速度が遅くなるという欠点があることも良く知られている。
【０１４９】
本発明の実施の形態では、すでに説明したとおり、大量のデータに対して最近点探索が高速に行えるので、これによりＮＮ法の認識処理を高速にさせることができる。図９、図１０に、本発明の実施の形態においてＮＮ法を実現させるデータベース構造の一例を示す。図９は、学習データのエレメントを検索キーとして、そのエレメントにデータラベルのリストをリンクさせた最近点探索用辞書のデータ構造を示す。図１０は、学習データのデータラベルとカテゴリーの対応テーブルを示す。図９の最近点探索用辞書により最近点探索を行い、見つかった最近点について、図１０のテーブルを参照し、対応するカテゴリーを見つけることで、ＮＮ法を実現することができる。
【０１５０】
［３．２］単層識別構造
［３．２．１］データベース構造
上に説明した方法を変形することによって、パターン認識を実現する別の方法が構築できる。いままでは、エレメントからデータラベルへの情報をデータベースに格納していたが、データラベルの代わりにカテゴリーラベルを記憶させることができる。
【０１５１】
この方法のメリットをこれから説明する。あるエレメントｅ１からデータラベルへのリンク情報が次のものであるとする。
ｅ１→Ｌ１，Ｌ３，Ｌ６，Ｌ８
いま、データに対応するカテゴリー（カテゴリーラベル）が次の通りであるとする。
Ｌ１→Ｃ１
Ｌ３→Ｃ１
Ｌ６→Ｃ４
Ｌ８→Ｃ１
【０１５２】
データベースに、データラベルの代わりにカテゴリーラベルを格納させると、重複する情報を省略できるので、次のようにできる。
ｅ１→Ｃ１，Ｃ４
あるいは重複する数を保持しても良い。その場合は次のようになる。
ｅ１→Ｃ１×３，Ｃ４×１
【０１５３】
このようなデータ表現は、データベースのサイズを小さくさせる効果がある。平均的に１つのエレメントからたくさんのデータラベルの情報がリンクしているような状態は、検索回数よりも検索ヒット回数が多いので、最近点探索の場合には処理時間を増大させる要因になる。しかしながら、本発明における最近点探索のデータ件数は数万から数億を想定することができるが、パターン認識の場合は、普通はカテゴリー数は、２個〜数千個程度であるので、処理時間の問題はほとんどない。
【０１５４】
パターン認識方法においても、最近点探索のときと同じく、どのようなエレメント集合作成方法を用いるかは具体的な問題ごとに適切な方法を選択すればよい。
【０１５５】
［３．２．２］得点の計算方法
パターン認識の場合には、カテゴリーごとに得点を集計し、一番得点の高いカテゴリーを答えとして返す。あるいは、得点の順番にカテゴリーの列を返す。得点の計算方法は、エレメントを検索して、ヒットしたカテゴリーの得点を１点加算し、それをすべてのエレメントについて繰り返し行い、合計点を求めればよい。また、図１１に示すように、カテゴリーラベルと加算係数をペアでデータベースに格納しておけば、検索ヒットしたときに、その加算係数を加算するようにすればよい。
【０１５６】
［３．２．２．１］加算係数の決定方法
（ａ）
いま、あるエレメントからカテゴリー情報へのリンクが次のようであるとする。
ｅ１→Ｃ１，Ｃ４，Ｃ８
この表現は、加算係数を省略した形式で、この場合は、検索にヒットしたときは、カテゴリーＣ１，Ｃ４，Ｃ８にそれぞれ１点加算する。
（ｂ）
ｅ１→（Ｃ１，０．３），（Ｃ４，１．２），（Ｃ８，０．５）
カテゴリーと加算係数をペアにしてデータベースに格納してある。この場合は、ヒットしたカテゴリーごとに加算係数を加算する。
【０１５７】
一般に、（ｂ）の方が認識率をよくできるが、（ａ）の方法はデータベースサイズを縮小させる効果がある。実際の目的に応じて適切な方法を選択すればよい。
【０１５８】
加算係数は、認識性能が極大になるように、辞書作成時に学習データから決定する。加算係数の決定方法には各種ある。その方法の一例をこれから説明する。
【０１５９】
いま、学習用のデータは大量にあるものとする。いま辞書に使用するデータ数をある数ｎＬに固定して、学習用データからｎＬ個のデータをランダムに抽出し、（ａ）形式の辞書を作成するものとする。ｎＬ個のデータを抽出する操作はいくらでもできるので、たくさんの辞書を作成することができる。
【０１６０】
１つの辞書で認識させて得点を計算し、たくさんの辞書で同様にそれを行ない、カテゴリーごとに全ての辞書での得点を合計させて、その総得点によって認識結果を出すとき、一般に認識率はよくなる。このことの理論はアンサンブル学習と呼ばれ、理論的に説明されている。
【０１６１】
たくさんの辞書で認識させるということは、加算係数を調整して１つの辞書にまとめることができる。
【０１６２】
学習用のデータの中からカテゴリーＣ１のデータを１個を任意に選んだとき、あるエレメントｅ１に対してＣ１がリンクする確率をＰｒ（（ｅ１，Ｃ１））とする。
【０１６３】
ｎＬ個の学習データで辞書を作るとき、得点が加算される期待値は、１−（１−Ｐｒ（ｅ１，Ｃ１））ｎＬとなる。従ってたくさんの辞書で認識させたときは、平均的にこの値に近づく。
【０１６４】
全てのエレメントｅｊとカテゴリーＣｋについて確率Ｐｒ（（ｅｊ，Ｃｋ））を求める。実際には、手に入った学習データからその推定値を求めることができる。そして、１−（１−Ｐｒ（ｅｊ，Ｃｋ））ｎＬを加算係数として辞書を作る。テスト用データを用意して、ｎＬを変化させて認識率を調査する。認識率が最大となるところのｎＬを見つけることによって、最適な加算係数が決定できる。
【０１６５】
以下、確率Ｐｒ（（ｅｊ，Ｃｋ））を推定し、加算係数を決定する方法についてより詳しく説明する。
【０１６６】
いまＮ個の学習サンプルがあるとする。これを学習サンプルの母数とする。Ｎ個の学習サンプルから、第ｉ番目の検索キーに第ｊ番目のカテゴリー対応づけられる確率Ｐｉｊを推定する方法を説明する。
【０１６７】
Ｎ個の学習サンプルを使って、第ｉ番目の検索キーに第ｊ番目のカテゴリー対応づけられる回数を集計する。これをＫｉｊとする。
【０１６８】
推定値Ｐｉｊは、
Ｐｉｊ＝Ｋｉｊ／Ｎ
で与えられる。
統計学における大数の法則により、Ｎが大きいほど良い推定値となる。
【０１６９】
次にこのＰｉｊを使って辞書作成、認識を行なう方法を説明する。いま、母数Ｎの学習サンプルの集団の中からランダムにＭ個を取り出す。これを辞書作成用の学習サンプルとする。
【０１７０】
Ｍ個の学習サンプルを使って辞書を作成するとき、辞書内の第ｉ番目の検索キーに第ｊ番目のカテゴリーが対応づけられる確率は、１−（１−Ｐｉｊ）Ｍである。
【０１７１】
Ｍ個の学習サンプルで作成した辞書で認識をした場合、得点の期待値は、加算係数を１−（１−Ｐｉｊ）Ｍとしたときに等しい。
【０１７２】
Ｍ個の学習サンプルで作成した辞書で、加算係数を１とした場合の得点計算により認識をした場合と、母数Ｎの集団からＰｉｊを求め、加算係数を１−（１−Ｐｉｊ）Ｍとしたときの得点計算により認識をした場合では、一般に、後者の方が認識率は良くなる。これは単純アンサンブル学習の効果である。すなわち、一般に、正解のカテゴリーの得点がその他のカテゴリーの得点より低くなる確率を極限まで低くできる効果がある。
【０１７３】
加算係数を決定する１−（１−Ｐｉｊ）Ｍという式は、Ｐｉｊに対して単調増加関数であるから、現実的には、その代わりとなる何らかの単調増加関数ｆ（Ｐｉｊ）を用いることによっても、やはり認識率をよくすることができる。
【０１７４】
さて、いま加算係数が１−（１−Ｐｉｊ）Ｍであるとき、認識率は、Ｍを変化させると、上に凸の曲線を描き、極大値を取るところがある。従って、このときのＭの値を用いて、関数ｆ（Ｐｉｊ）＝１−（１−Ｐｉｊ）Ｍとすると、最も優れた認識性能を実現することができる。
【０１７５】
しかしながら、関数ｆとしては、もっと簡単な、
ｆ（Ｐｉｊ）＝Ｐｉｊ、
ｆ（Ｐｉｊ）＝Ｋｉｊ
のような線形関数、または、
ｆ（Ｐｉｊ）＝１  （Ｐｉｊ＞threshold＝０．３）
＝０  （Ｐｉｊ＜threshold＝０．３）
のようなしきい関数などを採用しても良い。これは計算時間を速くする効果や、辞書サイズを小さくする効果がある。
【０１７６】
加算係数の決定方法にはこの他にもいろいろある。各種の最適化問題を解くアルゴリズムを適用することができる。
【０１７７】
［４］最近点対探索方法
最近点対探索は、与えられた点集合の中から最も距離の近い２点を探す問題である。この派生として、ある距離以内の点の組を全て列挙するという問題もある。応用例について先に挙げておく。
【０１７８】
［４．１］点の相互距離を扱う問題の例
・点の均等配置問題
ある領域と点の数が与えられたとき、最近点対距離を最大にするようにその領域内に点を配置する問題
【０１７９】
・異常接近しているデータの発見
例えば、多数の飛行機が飛行しているとき、互いに接近しすぎないように管制官は監視しなければならない。これは３次元空間である距離以内の最近点対を全て発見する問題に相当する。実用的な問題で、もっと高次元の問題も存在する。
【０１８０】
・カオス性の検出
多数の多次元データから何らかの法則性を見つけようとする分析方法の１つとして、そのデータがカオスであるかどうかを判定する。ＧＰ法（Grassberger-Procaccia algorithm）はカオス性検出の１つの方法であり、相関積分法とも呼ばれる。ある点から、半径ｒ以内の点の数を数える。ｒを変化させると、半径ｒ以内の点の数はあるカーブで増加していく。Ｎ次元のデータで全くランダムであれば、Ｎ次曲線となる。それより小さい次数の増加曲線であれば、カオスである可能性がある。
【０１８１】
・クラスタリング
多数の点を、まとまりのあるいくつかのグループに分ける。
【０１８２】
［４．２］最近点対探索のアルゴリズム
最近点対探索の基本的な考え方は、意味としては、最近点探索方法と同じである。与えられた点集合から辞書を作り、与えられた点集合全てに対して、その辞書を使って最近点を探索し、最終的に最も距離の小さい点の組を求める。ただし、アルゴリズムの形は若干異なる。
【０１８３】
［４．２．１］３２Ｃ１６空間の場合の例
データの集合を｛ｘｉ｝とする。全てのデータは３２ビットでビット＝１の数は１６個であるとする。ｘｉからビット＝１である１６個の場所のうち１４個を選んで、そこのみビット＝１とした３２ビットのデータを作成する。１２０個のデータができる。全てのデータに対してこの操作を行なう。
【０１８４】
いま、空のデータベースを用意して、エレメントとデータラベルを順次格納する。図１２（ａ）〜（ｄ）は、最近点対探索の過程で生成される辞書と最近点対候補テーブルを説明する図である。
（１）いまｘ２はエレメント表現としてエレメントａを含んでいるとする。このとき、データベースの場所ａからデータラベルＬ２にリンクする（図１２（ａ））。
（２）ｘ４もエレメントａを含んでいるとする。場所ａはＬ２にリンクしている。このとき、Ｌ２とＬ４のペアをテーブルに記憶する。そして、Ｌ４はデータベースのＬ２の次にリンクする（図１２（ｂ））。
（３）ｘ５もエレメントａを含んでいるとする。場所ａからリンクを辿り、Ｌ２，Ｌ４を見つけることができるので、テーブルに（Ｌ２，Ｌ５）、（Ｌ４，Ｌ５）を記憶する（図１２（ｃ））。なお、テーブルに同じものがすでにある場合は、その出現回数を記録する。
【０１８５】
全てのデータについて同じ処理を行なっていく。図１２（ｄ）は途中経過を示す図である。全てのデータについて行なうと、テーブルにはデータのペアと出現回数の最終的な情報を得ることができる。
【０１８６】
３２Ｃ１６空間で３２Ｃ１４の１２０個のエレメントを作成した今の例では、距離≦４以内のデータのペアを全て列挙することができる。このとき、距離＝０のものは出現回数１２０、距離＝２のものは出現回数＝１５、距離＝４のものは出現回数＝１である。
【０１８７】
この場合は、一定の距離以内の点の組を全て見つけるタイプのアルゴリズムの説明である。
【０１８８】
［４．２．２］｛０，１｝３２の場合の例
データ集合｛ｘｉ｝は３２ビットデータとする。まず、ｘｉから距離＝０と１のものをエレメントとし、［４．２．１］で説明したようなアルゴリズムにより、データのペアを探す。このときに見つけることができるのは、距離＝０，１，２のものである。もし、データの組を見つけることができなかったならば、距離≦２以内の最近点対が存在しないということである。
【０１８９】
次に、ｘｉから距離＝１と２のものをエレメントとし、同様の操作を行なう。このときに見つけることができるのは、距離＝２，３，４のものである。
【０１９０】
データの組が見つからなかったならば、次は、ｘｉから距離＝２と３のものをエレメントとし、同様の操作を行なう。このときに見つけることができるのは、距離＝４，５，６のものである。
【０１９１】
この場合は、最近点対の距離は指定しないで、答えを必ず見つけ出すタイプのアルゴリズムということになる。
【０１９２】
［４．２．３］実数球面空間の場合の例
｛ｘｉ｝をＮ次元単位実数球面空間の点集合とする。適当な量子化空間Ｑを用意する。一様ランダムなＮ×Ｎ直交行列を多数用意する。これでＱを変換すれば、いくらでも量子化空間を作ることができる。実装上は、Ｑを変換するのではなくて｛ｘｉ｝を変換することがあるが、意味は同じである。
【０１９３】
各ｘｉに直交行列Ｒ１をかける。これをｒ１ｘｉとする。ｒ１ｘｉをＱで量子化する。これをｑ（ｒ１ｘｉ）とする。これはエレメントである。［４．２．１］と同様に、ｑ（ｒ１ｘｉ）とＬｉをデータベースに格納する。
【０１９４】
図１３（ａ）、（ｂ）は、最近点対探索の過程で生成される辞書と、内積値を格納した最近点対候補テーブルを説明する図である。図１３（ａ）に示すように、いま場所ａにＬ３１とＬ８９が格納されたとする。このとき、内積（ｘ３１，ｘ８９）を計算する。図１３（ｂ）に示すように、テーブルには、内積値が上位であるものの点のペアと内積値を記憶しておく。もし、ただ１つの最近点対の解を得ることが目的ならば、最大の内積値を示したペア１つだけを記憶する領域を用意しておけばよい。
【０１９５】
全てのｘｉについてここまでの処理が一通り終わったならば、別の直交行列Ｒ２を用いて、同様の処理をする。そのとき、それまで得られたテーブルの情報はそのまま保持しておいて引き続き使用する。
【０１９６】
Ｒ１，Ｒ２，Ｒ３，...と、統計的に十分信頼がおける回数を行なう。こうして得られた、内積が最大値を取る点のペアが最近点対となる。
【０１９７】
例えば、｛ｘｉ｝を２０次元の実数球面空間の点とする。Ｒを２０×２０直交行列とする。Ｒｘ１とＲｘ２は、｛０，１｝２０に量子化することによって、同じ２０ビットのデータになるかもしれないし、ならないかもしれない。ｘ１とｘ２の距離が近いほど、同じになる確率は高くなる。一様ランダムな直交行列をたくさん用意して、試行回数を多くすれば、最近点対のペアが一致する２０ビットのデータになるケースが１回以上生じる確率は１に非常に近くなる。
【０１９８】
［４．２．４］最近点対探索型のアルゴリズムの特徴
最近点対探索型のアルゴリズムで、最近点探索方法やパターン認識方法と大きく異なるのは、使用するデータ領域が、点の数のオーダーだけで済むことである。
【０１９９】
点の数をＮＰとすると、例えばハッシュテーブルを使用すれば、テーブルサイズはＮＰ×１．５〜２．０程度でよい。一方、最近点対探索方法においては、３２Ｃ１６空間で点数２２０のときは、２２０×１２０に比例したデータ領域が必要であった。
【０２００】
また、［４．２．３］のようなアルゴリズムでは、量子化空間を動的に変えることができる。一般に｜Ｑ｜の大きさが小さいほど、最近点対を見つけやすくなるが、たくさんのペアが見つかってしまう。処理の途中でＱを適当に変えれば、見つかるペアが少なくなるので、計算時間の削減につながる。
【０２０１】
［５］実施例
実施例として、分散コーディングによるパターン認識を説明する。分散コーディングによる学習・認識手法の１つのモデルを構築し、考察を与える。この手法では、認識時間は学習サンプル数に依存せず定数時間となり、この手法の最も単純なモデルでは、学習時間は学習サンプル数に比例する。そのため、大量のサンプルからの学習が可能で、複雑なパターン認識問題に適用が期待できる。
【０２０２】
［５．１］分散コーディングによるパターン認識の基本原理
［５．１．１］ベクトルの分散表現
パターンベクトル空間として、原点を中心とするＮ次元の超球面上の空間を考える。すなわち、パターン空間上の任意のベクトルの大きさは一定であるものとする。いま、パターンベクトルｘを複数のベクトルに分割して表現することを考える。すなわち、複数のベクトルによって、
ｘ＝αΣｅｊ  （ｊ=０，…，Ｎｅ−１）  （５．１）
となるような、ベクトルの集合｛ｅｊ｝による表現を考える。これをｘの｛ｅｊ｝による分散表現と呼ぶことにする。
【０２０３】
Ｑを離散的な超球面空間とする。Ｑの点でｘから近いもの上位ｐ個を選ぶ。これをｘのＱ上のｐ−近傍点と呼び、Ｑ（ｘ，ｐ）と表記することにする。近傍点を作成するためのこのような空間を複数個用意してもよい。いまＮＱ個の異なる空間Ｑ０，…，ＱＮＱ−１からそれぞれＱｋ（ｘ，ｐｋ）を作成すると、全体ではΣｐｋ個の点が選ばれる。
【０２０４】
近傍点は、意味としてはｘのまわりに分布している。これは式（５．１）で提示したｘの分散表現になっている（Ｎｅ＝Σｐｋとする）。
【０２０５】
後述するパターン認識の効果を高めるには、空間Ｑとしては、｜Ｑ｜が非常に大きな数であるようなものを選ぶ。ｐは小さな数を採用する。
【０２０６】
本手法では、高次元空間の直交傾向と、分布が密であるならばその近傍に点が統計的に安定して存在するという原理を、暗に使っている。このような性質を用いた連想記憶手法の１つが［６］で述べるカネルバの疎分散記憶である。
【０２０７】
［５．１．２］分散表現の例
分散表現を行うには、元のパターンベクトル空間は超球面上の空間であればどのようなものであってもよいし、Ｑとｐの選び方も無数にある。以下に単純な例を示す。なお、特定の空間を定義する下記の記号を使用する。
【０２０８】
・バイナリ空間：
｛０，１｝Ｎ≡｛ｘ｜ｘ＝（ｘｉ），ｘｉ∈｛０，１｝，ｉ＝０，…，Ｎ−１｝
｛−１，＋１｝Ｎ≡｛ｘ｜ｘ＝（ｘｉ），ｘｉ∈｛−１，＋１｝，ｉ＝０，…，Ｎ−１｝
【０２０９】
・コンビネーション空間：
ＮＣｋ≡｛ｘ｜ｘ∈｛０，１｝Ｎ，｜ｘ｜＝ｋ｝
ＮＣｋ±≡｛ｘ｜ｘ∈｛−１，＋１｝Ｎ，｜ｘ｜＝２ｋ−Ｎ｝
【０２１０】
・階乗空間：
Ｎ！＝｛ｘ＝（ｘ０，ｘ１，…，ｘＮ−１）｜
ｘｉ∈｛０，１，…，Ｎ−１｝，ｘｉ≠ｘｊ（ｉ≠ｊ）｝
Ｎ！±＝｛ｘ＝（ｘ０，ｘ１，…，ｘＮ−１）｜
ｘｉ∈｛２ｋ−Ｎ＋１｝（ｋ＝０，…，Ｎ−１），ｘｉ≠ｘｊ（ｉ≠ｊ）｝
【０２１１】
例１
ｘ∈ＮＣＮ／２，Ｑ＝ＮＣＮ／２−ｄ／２
ｘからＱの点でハミング距離＝ｄ／２であるものは、Ｎ／２ＣＮ／２−ｄ／２個存在するので、Ｑ（ｘ，Ｎ／２ＣＮ／２−ｄ／２）はｘの分散表現となる。
ｘ＝（２／Ｎ／２ＣＮ／２−ｄ／２）Σｅｊ，ｅｊ∈ＮＣＮ／２−ｄ／２
例えば、３２Ｃ１６のベクトルを１２０個の３２Ｃ１４のベクトルによる分散表現で表すことができる。
【０２１２】
例２
ｘ∈Ｎ！±，Ｑｋ＝ＮＣ１±，ＮＣ２±，…，ＮＣＮ−１±
ｘから、ＮＣ１，ＮＣ２，…，ＮＣＮ−１への最近傍点をそれぞれ求める。こうしてＮ−１個のベクトルによる分散表現となる。
【０２１３】
［５．１．３］パターン認識方法
本節では、前節で述べたような表現を用いたパターン認識の基本的な手法を示す。
【０２１４】
Ｑ（ｘ，ｐ）はＱの部分集合であるから、冪集合２Ｑの元である。つまり、Ｑ（ｘ，ｐ）を｛０，１｝｜Ｑ｜の元として表すことができる。ＮＱ個の空間Ｑｋからそれぞれこのようなものを作るとき、これらのベクトルの要素を全て並べて、非常に高次元の２値ベクトル：
ｂ＝（ｂｉ）∈｛０，１｝Σ｜Ｑｋ｜
を作ることができる。
【０２１５】
このことは、ｘを非常に高次元の空間に写像することに相当する。元のパターンの分布がどのようであっても、次元がサンプル数よりも高いような非常に高次元の空間に写像すれば必ず線形分離可能となる。従って、図１４に示すように、入力層がΣ｜Ｑｋ｜個、出力層がＮＣ個の仮想的な単層識別関数を構築することができる。ここで、カテゴリをＣｊ（ｊ＝０，…，ＮＣ−１)とする。
【０２１６】
未知パターンｘの認識は、ｘをｂに変換し、
ｓｃｏｒｅ（ｘ，Ｃｊ）＝Σｂｉｗｉｊ  （５．２）
を計算し、
ｋ＝ａｒｇｍａｘ｛ｓｃｏｒｅ（ｘ，Ｃｊ）｝
となるカテゴリＣｋが認識結果となる。ｓｃｏｒｅ（）は類似度に相当するものであり、ここでは得点と呼ぶことにする。
【０２１７】
この構造において、学習サンプルを完全に識別できるような重み係数ｗｉｊは簡単に決定できる。
【０２１８】
始めは全てのｗｉｊを０にしておく。カテゴリＣｊに属する学習サンプルｘをｂに変換する。ｂの要素ｂｉが１であるとき、ｗｉｊを１にする。これを全ての学習サンプルに対して行う。学習したパターンに対しては得点は必ず満点になるので、複数のカテゴリの得点が満点で同点の場合を除いては、必ず正解になる。
【０２１９】
辞書は、ｗｉｊ＝１となるところのｉ，ｊの情報だけ記憶できればよい。また、得点の計算はｂｉ＝１となっているところのｗｉｊが０であるか１であるかが判定できればよい。いま学習サンプル数をＮＬとすると、このような要件を満たす辞書を作成し、学習時間がＯ（Ｎｅ×ＮＬ）で、かつ認識時間がＯ（Ｎｅ）となるようなアルゴリズムが存在する。また、辞書サイズはＯ（Ｎｅ×ＮＬ)を下回る。すなわち学習時間は学習サンプル数に比例し、認識時間は辞書サイズに依存せず、定数時間である。
【０２２０】
［５．２］分散コーディングによる認識実験と学習法の改良
［５．２．１］  重み係数の改良
本手法の構造は、（５．２）式のような高次元の線形識別関数となっているから、重み係数ｗを調整することが考えられる。本節では単純アンサンブル学習の考え方を適用する。
【０２２１】
いま、サンプルは多数あるものとし、これらは真の分布に従っているものとする。この中からランダムにサンプルをＮＬ個取り出して辞書を作成する。ＮＬ個のサンプルを取り出す操作を独立に多数回繰り返すことにより多数の辞書ができる。それぞれの辞書で認識を行い、得られた得点を合計したものを最終的な認識結果とすれば、一般に、その認識率は１つの辞書で認識したときよりも良くなる。
【０２２２】
この場合の各カテゴリの得点の期待値を計算する。いま、ランダムにカテゴリＣに属する１個のパターンｘを取り出して辞書を作成したとき、ｗｉｊ＝１となる確率をｐｉｊとおくと、ｘをｂ＝（ｂｉ）に変換したとき、
ｐｉｊ＝Ｐｒ（ｂｉ＝１  ａｎｄ  Ｃ＝Ｃｊ）
となる。
【０２２３】
ＮＬ個のサンプルで辞書を作成したときｗｉｊ＝１となる確率は、ｐｉｊを使って１−（１−ｐｉｊ）ＮＬと書ける。
【０２２４】
従って、多数の辞書による認識結果を平均するときの極限は、入力パターンをｘ＊→Ｂ＊＝（ｂｉ＊）とすると、
Ｅ［ｓｃｏｒｅ（ｘ＊，Ｃｊ）］＝Σｂｉ＊Ｅ［ｗｉｊ］＝Σｂｉ＊（１−（１−ｐｉｊ）ＮＬ）
となる。
【０２２５】
結局、図１５のように、重み係数ｗｉｊを１−（１−ｐｉｊ）ＮＬとした１つの線形識別関数にすることができる。
【０２２６】
こうすることによって、記憶領域も増えず、認識速度もシンプルなアルゴリズムと同等することができる。
【０２２７】
現実には真の出現確率ｐｉｊを求めることはできないが、多数のサンプルから近似値ｐｉｊ＾を知ることができるのでこれを利用する。最適なＮＬを決定するためには、学習用サンプルデータの他にテスト用データを用意する。ＮＬを変化させると認識率の極大値を取る場所があるので、最適な値を探索することは容易である。
【０２２８】
なお、サンプル数を増やして推定値ｐｉｊ＾が真の値に近づくとき、最適なＮＬは単調に減少し、［５．１．３］節で示した基本アルゴリズムにおける学習の飽和点のサンプル数に収束する。このとき、学習サンプルの極限における認識率は、それ以上向上しない限界値に行きあたり、一般には最良の認識率までは到達することはできない。そうではあるが、現実の適用においてはある程度の有効性を認めることができる。このような、重み係数を出現頻度の関数で調節する構造を改良アルゴリズムと呼ぶ。
【０２２９】
［５．３］まとめ
分散コーディングによる一連のパターン認識のアルゴリズムを提示した。以下にアルゴリズムの性質をまとめる。
【０２３０】
・辞書は単層識別構造をしており、認識は高速に行える。全てのカテゴリに対して類似度が求められる。多数のカテゴリの識別問題に対して適用が可能である。
【０２３１】
・基本アルゴリズム：全学習サンプルを１回参照するだけで学習が行える。辞書は単層識別構造で、重み係数は０，１である。学習の飽和が起こることがある。
【０２３２】
・改良アルゴリズム：学習は高速である。重み係数はエレメントの出現頻度の関数で、実数値を取る。学習の頭打ちが起こることがある。
【０２３３】
認識速度は学習サンプル数に影響を受けず高速である。このことから、大量のサンプルを学習することによって、認識率が高く、かつ認識速度が高速なプログラムを実現することができる。
【０２３４】
［６］カネルバの疎分散記憶との違い
本発明の実施の形態で用いた分散コーディングによる手法と、カネルバ（Kanerva）による疎分散記憶（Sparse Distributed Memory）の違いについて補足する。疎分散記憶では、球面空間にランダムな多数の点を分散させておき、そのうちのｘから距離ｒ以内の点について、書き込んである情報を読み出して総合することによって、ｘの最近点を漸近的に想起していきます。疎分散記憶の詳細は、P. Kanerva, "Sparse Distributed Memory", MIT Press, November, 1988に記載されている。
【０２３５】
カネルバの疎分散記憶の例
ここでは、Ｎ，Ｎ'，Ｘを集合を表す記号とする。ｘ，ｙを点とする。
Ｎ＝｛０，１｝１０００とする。Ｎ上でランダムに１００万点を選んだ点の集合をＮ’とする。これをハードロケーションと呼ぶ。Ｎの点１万点の集合Ｘを学習データとする。
【０２３６】
［６．１］データの書き込み
ｘ∈Ｘなるｘからハミング距離４５１以内のＮ’の点全てにｘの情報を書き込む。複数のＸの点が同じハードロケーションに書き込みを行なうときは、その点の平均、正確には書き込まれる全ての点の平均に最も近い｛０，１｝１０００の点を書き込む。
【０２３７】
［６．２］データの読み出し
未知の点をｙとする。ｙからハミング距離４５１以内のＮ’の点全ての情報を読み出し、それを平均し、Ｗ１（ｙ）とする。Ｗ１（ｙ）に対して、同じことをする。これをＷ２（ｙ）とする。これを繰り返すと、Ｗｔ（ｙ）はある点に収束する。これはｙからＸで最も近い点である。
【０２３８】
［６．３］本発明の実施の形態と疎分散記憶との違い
（１）疎分散記憶では、ある点ｘから、書き込むべき、または読み出すべき距離４５１以内のＮ’の点全てを効率的に見つけ出すアルゴリズムが存在しない。通常の計算機では効率的に処理できず、並列的な処理が行なえるニューロコンピュータを必要とする。
【０２３９】
（２）ある点からハミング距離４５１以内のＮ’の点はおよそ１０００個ある。これは、ベクトルをＮ’の１０００近傍点で表現するエレメント表現に相当する。しかし、ハミング距離４５１は、Ｎ’の０．００１に相当する。これは１０００次元の空間としては非常に大きな数である。１０００次元でハミング距離４５１の点へは、なす角が約８４．３７６°に相当する。ある点ａからなす角が８４．３７６°以内である２つの点ｘ、ｙの相互位置関係は、なす角が０°〜１６８．７５２°でなる。すなわち、非常に離れた点どうしがエレメントを共有することになる。
【０２４０】
一方、本発明の実施の形態において、［２．２．１］の３２Ｃ１６空間の例では、エレメントは３２Ｃ１４空間のうちの１６Ｃ１４個であるから、120/471435600=0.000000254と小さい数になる。このような小さい比率にすることは、ヒットするデータを少なくする効果があり、計算時間を速くすることができる。なぜなら、入力データとエレメントのなす角は２８．９５５°であるので、エレメントを共有する２点のなす角は、０°〜５７．９１°の範囲であり、近い点としかエレメントを共有しないからである。
【０２４１】
（３）同じアドレスに複数のデータを書き込むとき、疎分散記憶では、全てのデータの平均値を書き込んでいる。それに対して本発明では、リンク形式により複数のデータを全て記憶させる。もっとも、「リンク形式」と言っているが、必ずしも狭い意味でのリンク形式を取るわけではない。例えば、ハッシュ法であればオープンアドレス法というものも存在する。意味はリンク形式と全く同じである。
【０２４２】
以上、本発明を実施の形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【０２４３】
そのような変形例を説明する。実施の形態では、分散コーディングの適用分野として、最近点探索、パターン認識、および最近点対探索を挙げたが、適用分野はこれに限られない。たとえば、本発明を連想記憶型のデータ検索方法に適用することができる。連想記憶型のデータ検索では、検索対象ベクトルをＸ（ｔ）とし、初期状態はＸ（０）＝Ｘとする。検索において、見つかったエレメント全ての平均ベクトルをＸ（ｔ＋１）とする。これを繰り返すと，Ｘ（ｔ）はあるベクトルに収束する。これを検索結果とする。連想記憶型検索では、新しく発生した事例に対して、過去の事例データを検索して、最適な行動を決定することができる。このとき、複数の候補の中から総合的に判断することができる。また、処理時間の制約に応じて、判断の精度を変えることができる。例えば、緊急の場合にも処理が破綻せず、適応的な行動をするロボットを作ることが可能となる。
【０２４４】
実施の形態では、入力データを複数の直交行列により変換して、入力データの多数の分散表現を生成したが、厳密な直交行列を使わずに、ランダムな行列により入力データを変換してもよい。精度は落ちるが、多数のランダムな行列で変換することにより、統計的に安定することが期待できる。
【０２４５】
最近点探索および最近点対探索における検算は、用途や目的により必要な場合と必要でない場合とがある。実数データの場合は、スコアで１位になったとしても、それが正解であるとは限らず、本当に正解であるかどうかは検算してみなければわからない。したがって、たいていの場合には検算をすることが必要であるが、目的によっては必要でない場合もある。たとえば、不完全な検索でもよいから、とにかく提示されたデータに近いデータを検索したい場合がある。連想記憶、発想支援のような目的が使われる場合や、限られた時間内で動的に判断しなければならないようなリアルタイム性のある処理系で使われる場合などである。
【０２４６】
また、１００回の試行で１位の得点が５０点、２位の得点が１点、３位以下は０点のような検索結果が得られた場合は、検算するまでもなく、統計的にほぼ絶対、得点１位のデータは正解であると判断することができる。
【０２４７】
また、点の相互距離を扱う問題では必ずしも検算をしないことがある。点の均等配置問題では、最初のうちは検算をしないで、２点間の距離が近いと思われるペアを多数見つけることが優先される。
【図面の簡単な説明】
【０２４８】
【図１】実施の形態１に係る最近点探索装置の構成図である。
【図２】実施の形態２に係るパターン認識装置の構成図である。
【図３】実施の形態３に係る最近点対探索装置の構成図である。
【図４】ハッシュテーブルの説明図である。
【図５】学習データのエレメントを検索キーとして、そのエレメントに学習データのラベルのリストをリンクさせた最近点探索用辞書の基本的なデータ構造を示す図である。
【図６】学習データからエレメントデータを作成する方法を説明する図である。
【図７】学習データからエレメントデータを作成する方法を説明する図である。
【図８】未知データに最も近い学習データを検索する方法を説明する図である。
【図９】学習データのエレメントを検索キーとして、そのエレメントにデータラベルのリストをリンクさせた最近点探索用辞書のデータ構造を示す図である。
【図１０】学習データのデータラベルとカテゴリーの対応テーブルを示す図である。
【図１１】学習データのエレメントを検索キーとして、そのエレメントにカテゴリーラベルと加算係数のペアのリストをリンクさせたパターン認識用辞書のデータ構造を示す図である。
【図１２】最近点対探索の過程で生成される辞書と最近点対候補テーブルを説明する図である。
【図１３】最近点対探索の過程で生成される辞書と、内積値を格納した最近点対候補テーブルを説明する図である。
【図１４】分散表現による高次元の単層識別関数モデルを説明する図である。
【図１５】多数の辞書と等価な辞書構造を説明する図である。
【符号の説明】
【０２４９】
１０  直交変換部、  ２０  分散表現生成部、  ３０  辞書生成部、  ３５  加算係数決定部、  ４０  検索部、  ５０  検算部、  ６０  分析部、  ７０  データベース、  ７２  辞書記憶部、  ８０  検索結果記憶部、  ８２  分析結果記憶部、  １００  最近点探索装置、  １１０  最近点探索用辞書、  １３０  最近点候補テーブル、  ２００  パターン認識装置、  ２１０  パターン認識用辞書、  ２３０  カテゴリー候補テーブル、  ３００  最近点対探索装置、  ３３０  最近点対候補テーブル。
【図１】
2005242562.tif 000003
【図２】
2005242562.tif 000004
【図３】
2005242562.tif 000005
【図４】
2005242562.tif 000006
【図５】
2005242562.tif 000007
【図６】
2005242562.tif 000008
【図７】
2005242562.tif 000009
【図８】
2005242562.tif 000010
【図９】
2005242562.tif 000011
【図１０】
2005242562.tif 000012
【図１１】
2005242562.tif 000013
【図１２】
2005242562.tif 000014
【図１３】
2005242562.tif 000015
【図１４】
2005242562.tif 000016
【図１５】
2005242562.tif 000017