パターン探索装置及びその方法
【課題】ハッシュ関数を用いた近似最近傍探索法において、高速かつ少ない誤差比で最近傍パターンを探索するパターン探索装置を提供する。
【解決手段】登録部２、累積確率分布獲得部３、ハッシュ関数部４、学習部５、探索部６から構成され、予め検索対象となるパターン集合を登録して学習パターン集合としておき、学習パターンの任意の軸上における累積確率分布をシグモイド関数で近似し、その累積確率分布を基に確率値を一定間隔で分割するハッシュ関数を複数個定義し、未知のパターンを入力すると各ハッシュ関数の出力であるハッシュ値によりバケット中の部分集合の和集合を求め、その集合中から最近傍パターンを探索する。
【解決手段】登録部２、累積確率分布獲得部３、ハッシュ関数部４、学習部５、探索部６から構成され、予め検索対象となるパターン集合を登録して学習パターン集合としておき、学習パターンの任意の軸上における累積確率分布をシグモイド関数で近似し、その累積確率分布を基に確率値を一定間隔で分割するハッシュ関数を複数個定義し、未知のパターンを入力すると各ハッシュ関数の出力であるハッシュ値によりバケット中の部分集合の和集合を求め、その集合中から最近傍パターンを探索する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、学習パターン集合中から入力パターンに対してハッシュ関数を用いて高速に最近傍パターンを探索するパターン探索装置及びその方法に関する。
【背景技術】
【０００２】
従来のハッシュ関数を用いた近似最近傍探索法には、非特許文献１と非特許文献２に開示されているものがある。この従来技術は、図５に示すように、学習パターン集合を任意ベクトル上に射影し、そのベクトル上での存在範囲を一定間隔で分割するハッシュ関数を定義し、入力パターンのハッシュ値により学習パターン集合中の限られた最近傍候補から最近傍パターンを探索するものである。
【非特許文献１】P. Indyk and R. Motwani, 「Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality,」 In Proceedings of the 30th ACM Symposium on Theory of Computing (STOC'98) , pp.604-613, May 1998.
【非特許文献２】M. Datar, P. Indyk, N. Immorlica, and V. Mirrokni,「Locality-Sensitive Hashing Scheme Based on p-Stable Distributions,」 In Proceedings of the 20th Annual Symposium on Computational Geometry(SCG2004), June 2004.
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上記したように、従来技術には、図５に示すように、登録済みパターンを任意ベクトル上に射影し、そのベクトル上での存在範囲を一定間隔で分割するハッシュ関数を用いるものがある。
【０００４】
しかし、ハッシュ関数により分割した空間領域（以下、バケットという）において探索対象である入力パターンを内包するバケット中に存在する学習パターンが、学習パターン集合の分布に応じてパターン数が異なり、学習パターンの密度が高いバケットでは探索時間が遅くなり、学習パターンの密度が低いバケットでは真の最近傍パターンと得られた近似最近傍パターンとの距離の誤差の比（以下、誤差比という）が高くなるという問題点がある。
【０００５】
また、探索対象である入力パターンを内包するバケット中に学習パターンが存在しない場合、探索することができないという問題点がある。
【０００６】
そこで本発明は、上記問題点を解決するためになされたものであって、探索速度の高速化と誤差比の低減を可能とするパターン探索装置及びその方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、ｄ次元の複数の学習パターンを記憶する記憶部と、前記複数の学習パターンから、前記ｄ次元の任意の次元軸上における前記学習パターンのそれぞれの存在確率の累積確率を表す累積確率分布を求める分布獲得部と、累積確率が分割された複数の確率区間のそれぞれに前記累積確率分布で対応する前記次元軸上の分布区間内の任意の点の値を、前記各確率区間に対応するハッシュ値に変換するハッシュ関数を求めるハッシュ関数獲得部と、前記ハッシュ関数を用いて前記各学習パターンのハッシュ値をそれぞれ求め、前記各学習パターンを前記ハッシュ値に対応するバケットに分類する学習部と、前記ハッシュ関数を用いて入力パターンのハッシュ値を求め、前記入力パターンのハッシュ値に対応するバケットに属する前記学習パターンの中から、前記入力パターンに最も類似する前記学習パターンを探索する探索部と、を有するパターン探索装置である。
【発明の効果】
【０００８】
本発明によれば、学習パターンの累積確率分布から、確率値を一定間隔で分割するハッシュ関数を定義するため、各バケット中のパターン数がほぼ一定になり、最近傍解を得る際の平均的な探索速度の高速化と誤差比の低減を可能とする。
【発明を実施するための最良の形態】
【０００９】
以下、本発明の実施形態について図面に基づいて説明する。
【００１０】
（第１の実施形態）
以下、第１の実施形態のパターン探索装置１について図１と図２に基づいて説明する。
【００１１】
本実施形態のパターン探索装置１は、図２に示すように、予め検索対象となる複数の学習パターンを学習パターン集合として登録する。ここで、学習パターン集合は正規分布（ガウス分布）で表現できると仮定する。
【００１２】
これら学習パターンの任意の軸上における累積確率分布をシグモイド関数で近似し、その累積確率分布を基に確率値を一定間隔で分割するハッシュ関数を複数個定義する。
【００１３】
そして、未知のパターンが入力されると各ハッシュ関数の出力であるハッシュ値によりバケット中に存在する学習パターン集合の各部分集合からの和集合を求め、その和集合中から入力パターンに最も類似する学習パターン（以下、最近傍パターンという）を探索する。
【００１４】
本実施形態のパターン探索装置１は、パターン認識に用いられるものであり、例えば、画像に写された物体認識（例えば、顔認識）やデータマイニングに適用できる。
【００１５】
（１）パターン探索装置１の構成
図１は、本実施形態に係わるパターン探索装置１を示すブロック図である。
【００１６】
パターン探索装置１は、登録部２、累積確率分布獲得部３、ハッシュ関数部４、学習部５、探索部６から構成されている。
【００１７】
各部２〜６の下記で説明する各機能は、コンピュータに格納されたプログラムによっても実現できる。
【００１８】
以下、順番に各部の機能を説明する。
【００１９】
（２）登録部２
登録部２は、予め検索対象となる顔画像などの複数の学習パターンを学習パターン集合として登録する。
【００２０】
そして、登録した学習パターンを累積確率分布獲得部３と学習部５に送る。
【００２１】
（３）累積確率分布獲得部３
累積確率分布獲得部３は、登録部２で登録した学習パターン集合の任意軸での累積確率分布を主成分分析で求める。
【００２２】
本実施形態では、学習パターン集合が正規分布（ガウス分布）であると仮定し、全ての次元での累積確率分布を求めるが、仮にｄ次元上での累積確率分布を推定し分布を求める場合、下記の（１）式のシグモイド関数により近似する。
【数１】
【００２３】
ここで、μは平均値、αは標準偏差である。この２つのパラメータは初期値としては前記学習パターン集合の平均値と標準偏差を用い、最小二乗近似により累積確率分布へのシグモイド関数当てはめの最適化を行う。
【００２４】
獲得した各累積確率分布をハッシュ関数部４に送る。
【００２５】
（４）ハッシュ関数部４
ハッシュ関数部４は、累積確率分布獲得部３により求めた累積確率分布のそれぞれについて、確率値が一定になるようにｎ個に分割するハッシュ関数を求める。
【００２６】
ハッシュ関数は、下記の（２）式で定義できる。
【数２】
【００２７】
ここで、ΔはＰｓ（ｘ）の値域［０，１］を［０，Δ］，［Δ，２Δ］，・・・［（ｎ−１）Δ，１］のようにｎ個に分割した際の１つのバケットの確率値である。
【００２８】
各次元でのハッシュ関数を獲得し、学習部５と探索部６に送る。
【００２９】
（５）学習部５
学習部５は、登録部２により登録した学習パターン集合とハッシュ関数部４により獲得した各ハッシュ関数により、学習パターン集合に属する各学習パターンを、各ハッシュ関数の出力値であるハッシュ値に対応する各バケットに振り分け、部分集合を構成して、リスト構造にする。
【００３０】
これら部分集合は、パターンの次元数がＤで、ｎ個に分割するハッシュ関数である場合、全部でＤｎ個生成する。
【００３１】
生成した部分集合は、探索部６に送る。
【００３２】
（６）探索部６
探索部６には、まず検索したい顔画像などの未知のパターンｑが入力される。そして、この入力パターンｑについての、学習パターン集合ＡＬＬの中から最も類似する学習パターン（すなわち、最近傍パターン）を探索する。
【００３３】
この探索は、ハッシュ関数部４により獲得した各ハッシュ関数と、学習部５によって生成した部分集合により探索する。
【００３４】
入力パターンｑを入力値としたときハッシュ関数の出力であるハッシュ値Ｈにより限定される部分集合ＢｉＨは、下記の（３）式で定義できる。
【数３】
【００３５】
ここでは、ランダムで選択したｍ個のハッシュ関数により得られる部分集合の和集合を最近傍候補Ｃ（ｑ）とする。
【数４】
【００３６】
このとき、最近傍候補Ｃ（ｑ）を獲得する際に、含まれたバケット数を重複度ｗ（ｘ）とし、これによりソートし最大となるパターンと入力パターンとの距離を暫定距離ｚとする。ｘ１とｘ２のＬｐ距離をｄｐ（ｘ１，ｘ２）と定義すると、暫定距離ｚは下記の（５）式のようになる。
【数５】
【００３７】
ここで、下記の（６）式を満たす候補ｘは最近傍にはなり得ないので最近傍候補Ｃ（ｑ）から除外できる。
【数６】
【００３８】
この性質に基づき、以下の手続きで絞込み探索を行う。
【００３９】
ステップ１において、ｉ：＝１とする。
【００４０】
ステップ２において、Ｃｉ−１（ｑ）内の各要素に対して上記の（６）式の条件を満足する候補を除外し、得られた候補集合をＣｉ（ｑ）とする。もし、ｉ＝ｍなら、ステップ４へ進む。もし、｜Ｃｉ（ｑ）｜＝１なら、その要素を最近傍パターンとして停止する。
【００４１】
ステップ３において、ｉ：＝ｉ＋１としてステップ２に戻る。
【００４２】
ステップ４において、Ｃｉ（ｑ）内の候補全てと入力パターンとの距離計算を行い、最小距離を与える学習パターンを最近傍パターンとして停止する。
【００４３】
最後に獲得した最近傍パターンをパターン探索装置１の外部に出力する。
【００４４】
（７）変更例
（７−１）変更例１
上記実施形態では、探索部６において最近傍候補Ｃ（ｑ）は重複度ｗ（ｘ）により並び替え、上位ｂ％のみとして探索してもよい。
【００４５】
（７−２）変更例２
上記実施形態では、探索部６においてハッシュ関数により得られる部分集合の和集合を最近傍候補Ｃ（ｑ）としているが、探索部６においてハッシュ関数により得られる部分集合の積集合、または、その積集合の近傍の和集合を最近傍候補Ｃ（ｑ）として探索してもよい。
【００４６】
（第２の実施形態）
本発明の第２の実施形態に係わるパターン探索装置１０１について図３に基づいて説明する。
【００４７】
本実施形態のパターン探索装置１０１と第１の実施形態のパターン探索装置１と異なる点は次の２点である。
【００４８】
第１の異なる点は、直交変換部１０７において学習パターン集合のそれぞれの学習パターンを部分空間に射影し、ベクトル空間内でのユークリッド距離に直交変換し、この直交変換した学習パターンを登録部１０２に登録する。
【００４９】
第２の異なる点は、累積確率分布獲得部１０３において、各学習パターンに関してシグモイド関数の重み付け和により累積確率分布を獲得する。
【００５０】
（１）パターン探索装置１０１の構成
図３は、本実施形態に係わるパターン探索装置１０１を示すブロック図である。
【００５１】
パターン探索装置１０１は、登録部１０２、累積確率分布獲得部１０３、ハッシュ関数部１０４、学習部１０５、探索部１０６、直交変換部１０７から構成されている。
【００５２】
なお、パターン探索装置１０１の動作のうち、第１の実施形態のパターン探索装置１と同様な処理については説明を省略する。
【００５３】
（２）直交変換部１０７
直交変換部１０７は、予め検索対象となる学習パターン集合を主成分分析する。そして、固有値の高い順に直交変換を行うためのＮ番目までの固有ベクトル、つまりＮ×Ｄの直交変換行列Ｏ＝｛φＴ１，φＴ２，・・・，φＴＮ｝を保存し、登録部１０２へ送る。
【００５４】
（３）登録部１０２
登録部１０２は、直交変換部１０７により獲得した固有ベクトルを用いて、予め検索対象となる学習パターン集合のそれぞれを直交変換した後、学習パターン集合として登録する。
【００５５】
そして、この直交変換した学習パターン集合を累積確率分布獲得部１０３と学習部１０５に送る。
【００５６】
（４）累積確率分布獲得部１０３
累積確率分布獲得部１０３は、登録部１０２で登録した学習パターン集合の各軸上での累積確率分布をそれぞれ求める。
【００５７】
ここでは各累積確率分布を、一般分布とし、この一般分布を混合ガウス分布と仮定し、シグモイド関数の重み付け和により推定する。実際には、ランダムで選択した学習パターンに対して、下記の（７）式により各学習パターンでのｈを最適化し最小二乗近似により累積確率分布を関数化する。
【数７】
【００５８】
ここでｈ’はｈｉの平均値である。ｎの個数は定数で与えるか、一般的な最適化手法により近似精度の許容範囲における最小数を求める。
【００５９】
（５）探索部１０６
探索部１０６は、まず検索したい顔画像などの未知の入力パターンｑが入力される。そして、この入力パターンｑについての、学習パターン集合ＡＬＬ中の最近傍パターンを探索する。この探索は、ハッシュ関数部１０４により獲得した各ハッシュ関数と、学習部１０５によって生成した部分集合により探索する。
【００６０】
直交変換部１０７により獲得した固有ベクトルにより入力パターンを直交変換し、直交入力パターンＯＴｑとする。直交入力パターンを入力値としたときハッシュ関数の出力であるハッシュ値Ｈにより限定される部分集合ＢｉＨを下記の（８）式で定義できる。
【数８】
【００６１】
ここでは、ランダムで選択したｍ個のハッシュ関数により得られる部分集合の和集合を最近傍候補Ｃ（ｑ）とする。
【数９】
【００６２】
このとき、最近傍候補Ｃ（ｑ）を獲得する際に、含まれたバケット数を重複度ｗ（ｘ）とし、これによりソートし最大となるパターンと入力パターンとの距離を暫定距離ｚとする。ｘ１とｘ２のＬｐ距離をｄｐ（ｘ１，ｘ２）と定義すると、暫定距離ｚは下記の（１０）式のようになる。
【数１０】
【００６３】
ここで、下記の（１１）式を満たす候補ｘは最近傍にはなり得ないので最近傍候補Ｃ（ｑ）から除外できる。
【数１１】
【００６４】
この性質に基づき、固有値の高い主軸への射影成分から順に、以下の手続きで絞込み探索を行う。
【００６５】
ステップ１において、ｉ：＝１とする。
【００６６】
ステップ２において、Ｃｉ−１（ｑ）内の各要素に対して上記の（１１）式の条件を満足する候補を除外し、得られた候補集合をＣｉ（ｑ）とする。もし、ｉ＝ｍなら、ステップ４へ進む。もし、｜Ｃｉ（ｑ）｜＝１なら、その要素を最近傍パターンとして停止する。
【００６７】
ステップ３においてｉ：＝ｉ＋１としてステップ２に戻る。
【００６８】
ステップ４において、Ｃｉ（ｑ）内の候補全てと入力パターンとの距離計算を行い、最小距離を与える学習パターンを最近傍パターンとして停止する。
【００６９】
このような計算を行う理由は、固有値の最も高い第一主成分は最も分散の大きい軸であり、Ｃ（ｑ）−Ｂ１ｈ１（ｑ）の殆どの要素が、｜φＴ１ｑ−φＴｘ｜ｐ＞ｚｐという条件を満足してしまうためφＴ１ｑ１の値を調べるだけで一挙に最近傍候補集合を小さくすることができる。第二主成分以降もそれ以降の主軸と比べた際に同様のことが言えるため、候補を絞り込む効率を考えると妥当な処理であるといえる。
【００７０】
最後に獲得した最近傍パターンをパターン探索装置１の外部に出力する。
【００７１】
（第３の実施形態）
本発明の第３の実施形態に係わるパターン認識装置２０１について図４に基づいて説明する。
【００７２】
本実施形態のパターン認識装置２０１と、第１の実施形態のパターン探索装置１及び第２の実施形態のパターン探索装置１０１と異なる点は次の点である。
【００７３】
第１の異なる点は、パターン認識装置２０１は、予め検索対象となる学習パターン集合を登録して学習パターン集合とする。この学習パターン集合に対応するクラスを登録し、入力パターンに対してパターン探索部２０８により最近傍パターンを探索し、クラス部２０９により出力した対応するクラスを認識結果として出力する。
【００７４】
第２の異なる点は、パターン探索部２０８は、累積確率分布獲得部２０３においてパターンを獲得する次元軸での値により、累積ヒストグラムを獲得し、それを累積確率分布とする。
【００７５】
（１）パターン認識装置２０１の構成
図４は、本実施形態に係わるパターン認識装置２０１を示すブロック図である。
【００７６】
パターン認識装置２０１は、登録部２０２、累積確率分布獲得部２０３、ハッシュ関数部２０４、学習部２０５、探索部２０６、直交変換部２０７、パターン探索部２０８、クラス部２０９から構成されている。
【００７７】
なお、パターン認識装置２０１の動作のうち、第１の実施形態のパターン探索装置１及び第２の実施形態のパターン探索装置１０１と同様な処理については説明を省略する。
【００７８】
（２）累積確率分布獲得部２０３
累積確率分布獲得部２０３は、登録部２０２で登録した学習パターン集合の各軸上での累積確率分布をそれぞれ獲得する。ここでは各累積確率分布を、学習パターン集合の各軸上での値により並び替えを行い、累積ヒストグラムを求めることにより推定する。
【００７９】
上記各実施形態における関数による分布表現との違いは、最適化パラメータがないため一意に求めることができる反面、学習パターンが少ないと学習パターン間の分布が線形で表現されるため誤差が大きくなる点である。
【００８０】
（３）パターン探索部２０８
パターン探索部２０８は、登録部２０２、累積確率分布獲得部２０３、ハッシュ関数部２０４、学習部２０５、探索部２０６、直交変換部２０７から構成され、入力パターンの最近傍パターンを、登録部２０２に登録した学習パターン集合の中から探索する。
【００８１】
（４）クラス部２０９
クラス部２０９は、学習パターン集合中の各パターンに対応するクラスを登録しておき、パターン探索部２０８により探索した入力パターンの最近傍パターンに対応するクラスを、入力パターンのクラスとしてパターン探索装置１の外部に出力する。
【００８２】
（変更例）
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。
【００８３】
また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【００８４】
【図１】本発明の第１の実施形態のパターン探索装置の構成を示すブロック図である。
【図２】第１の実施形態の概念の説明図である。
【図３】第２の実施形態のパターン探索装置の構成を示すブロック図である。
【図４】第３の実施形態のパターン探索装置の構成を示すブロック図である。
【図５】従来技術の概念の説明図である。
【符号の説明】
【００８５】
１・・・パターン探索装置
２・・・登録部
３・・・累積確率獲得部
４・・・ハッシュ関数部
５・・・学習部
６・・・探索部
【技術分野】
【０００１】
本発明は、学習パターン集合中から入力パターンに対してハッシュ関数を用いて高速に最近傍パターンを探索するパターン探索装置及びその方法に関する。
【背景技術】
【０００２】
従来のハッシュ関数を用いた近似最近傍探索法には、非特許文献１と非特許文献２に開示されているものがある。この従来技術は、図５に示すように、学習パターン集合を任意ベクトル上に射影し、そのベクトル上での存在範囲を一定間隔で分割するハッシュ関数を定義し、入力パターンのハッシュ値により学習パターン集合中の限られた最近傍候補から最近傍パターンを探索するものである。
【非特許文献１】P. Indyk and R. Motwani, 「Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality,」 In Proceedings of the 30th ACM Symposium on Theory of Computing (STOC'98) , pp.604-613, May 1998.
【非特許文献２】M. Datar, P. Indyk, N. Immorlica, and V. Mirrokni,「Locality-Sensitive Hashing Scheme Based on p-Stable Distributions,」 In Proceedings of the 20th Annual Symposium on Computational Geometry(SCG2004), June 2004.
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上記したように、従来技術には、図５に示すように、登録済みパターンを任意ベクトル上に射影し、そのベクトル上での存在範囲を一定間隔で分割するハッシュ関数を用いるものがある。
【０００４】
しかし、ハッシュ関数により分割した空間領域（以下、バケットという）において探索対象である入力パターンを内包するバケット中に存在する学習パターンが、学習パターン集合の分布に応じてパターン数が異なり、学習パターンの密度が高いバケットでは探索時間が遅くなり、学習パターンの密度が低いバケットでは真の最近傍パターンと得られた近似最近傍パターンとの距離の誤差の比（以下、誤差比という）が高くなるという問題点がある。
【０００５】
また、探索対象である入力パターンを内包するバケット中に学習パターンが存在しない場合、探索することができないという問題点がある。
【０００６】
そこで本発明は、上記問題点を解決するためになされたものであって、探索速度の高速化と誤差比の低減を可能とするパターン探索装置及びその方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、ｄ次元の複数の学習パターンを記憶する記憶部と、前記複数の学習パターンから、前記ｄ次元の任意の次元軸上における前記学習パターンのそれぞれの存在確率の累積確率を表す累積確率分布を求める分布獲得部と、累積確率が分割された複数の確率区間のそれぞれに前記累積確率分布で対応する前記次元軸上の分布区間内の任意の点の値を、前記各確率区間に対応するハッシュ値に変換するハッシュ関数を求めるハッシュ関数獲得部と、前記ハッシュ関数を用いて前記各学習パターンのハッシュ値をそれぞれ求め、前記各学習パターンを前記ハッシュ値に対応するバケットに分類する学習部と、前記ハッシュ関数を用いて入力パターンのハッシュ値を求め、前記入力パターンのハッシュ値に対応するバケットに属する前記学習パターンの中から、前記入力パターンに最も類似する前記学習パターンを探索する探索部と、を有するパターン探索装置である。
【発明の効果】
【０００８】
本発明によれば、学習パターンの累積確率分布から、確率値を一定間隔で分割するハッシュ関数を定義するため、各バケット中のパターン数がほぼ一定になり、最近傍解を得る際の平均的な探索速度の高速化と誤差比の低減を可能とする。
【発明を実施するための最良の形態】
【０００９】
以下、本発明の実施形態について図面に基づいて説明する。
【００１０】
（第１の実施形態）
以下、第１の実施形態のパターン探索装置１について図１と図２に基づいて説明する。
【００１１】
本実施形態のパターン探索装置１は、図２に示すように、予め検索対象となる複数の学習パターンを学習パターン集合として登録する。ここで、学習パターン集合は正規分布（ガウス分布）で表現できると仮定する。
【００１２】
これら学習パターンの任意の軸上における累積確率分布をシグモイド関数で近似し、その累積確率分布を基に確率値を一定間隔で分割するハッシュ関数を複数個定義する。
【００１３】
そして、未知のパターンが入力されると各ハッシュ関数の出力であるハッシュ値によりバケット中に存在する学習パターン集合の各部分集合からの和集合を求め、その和集合中から入力パターンに最も類似する学習パターン（以下、最近傍パターンという）を探索する。
【００１４】
本実施形態のパターン探索装置１は、パターン認識に用いられるものであり、例えば、画像に写された物体認識（例えば、顔認識）やデータマイニングに適用できる。
【００１５】
（１）パターン探索装置１の構成
図１は、本実施形態に係わるパターン探索装置１を示すブロック図である。
【００１６】
パターン探索装置１は、登録部２、累積確率分布獲得部３、ハッシュ関数部４、学習部５、探索部６から構成されている。
【００１７】
各部２〜６の下記で説明する各機能は、コンピュータに格納されたプログラムによっても実現できる。
【００１８】
以下、順番に各部の機能を説明する。
【００１９】
（２）登録部２
登録部２は、予め検索対象となる顔画像などの複数の学習パターンを学習パターン集合として登録する。
【００２０】
そして、登録した学習パターンを累積確率分布獲得部３と学習部５に送る。
【００２１】
（３）累積確率分布獲得部３
累積確率分布獲得部３は、登録部２で登録した学習パターン集合の任意軸での累積確率分布を主成分分析で求める。
【００２２】
本実施形態では、学習パターン集合が正規分布（ガウス分布）であると仮定し、全ての次元での累積確率分布を求めるが、仮にｄ次元上での累積確率分布を推定し分布を求める場合、下記の（１）式のシグモイド関数により近似する。
【数１】
【００２３】
ここで、μは平均値、αは標準偏差である。この２つのパラメータは初期値としては前記学習パターン集合の平均値と標準偏差を用い、最小二乗近似により累積確率分布へのシグモイド関数当てはめの最適化を行う。
【００２４】
獲得した各累積確率分布をハッシュ関数部４に送る。
【００２５】
（４）ハッシュ関数部４
ハッシュ関数部４は、累積確率分布獲得部３により求めた累積確率分布のそれぞれについて、確率値が一定になるようにｎ個に分割するハッシュ関数を求める。
【００２６】
ハッシュ関数は、下記の（２）式で定義できる。
【数２】
【００２７】
ここで、ΔはＰｓ（ｘ）の値域［０，１］を［０，Δ］，［Δ，２Δ］，・・・［（ｎ−１）Δ，１］のようにｎ個に分割した際の１つのバケットの確率値である。
【００２８】
各次元でのハッシュ関数を獲得し、学習部５と探索部６に送る。
【００２９】
（５）学習部５
学習部５は、登録部２により登録した学習パターン集合とハッシュ関数部４により獲得した各ハッシュ関数により、学習パターン集合に属する各学習パターンを、各ハッシュ関数の出力値であるハッシュ値に対応する各バケットに振り分け、部分集合を構成して、リスト構造にする。
【００３０】
これら部分集合は、パターンの次元数がＤで、ｎ個に分割するハッシュ関数である場合、全部でＤｎ個生成する。
【００３１】
生成した部分集合は、探索部６に送る。
【００３２】
（６）探索部６
探索部６には、まず検索したい顔画像などの未知のパターンｑが入力される。そして、この入力パターンｑについての、学習パターン集合ＡＬＬの中から最も類似する学習パターン（すなわち、最近傍パターン）を探索する。
【００３３】
この探索は、ハッシュ関数部４により獲得した各ハッシュ関数と、学習部５によって生成した部分集合により探索する。
【００３４】
入力パターンｑを入力値としたときハッシュ関数の出力であるハッシュ値Ｈにより限定される部分集合ＢｉＨは、下記の（３）式で定義できる。
【数３】
【００３５】
ここでは、ランダムで選択したｍ個のハッシュ関数により得られる部分集合の和集合を最近傍候補Ｃ（ｑ）とする。
【数４】
【００３６】
このとき、最近傍候補Ｃ（ｑ）を獲得する際に、含まれたバケット数を重複度ｗ（ｘ）とし、これによりソートし最大となるパターンと入力パターンとの距離を暫定距離ｚとする。ｘ１とｘ２のＬｐ距離をｄｐ（ｘ１，ｘ２）と定義すると、暫定距離ｚは下記の（５）式のようになる。
【数５】
【００３７】
ここで、下記の（６）式を満たす候補ｘは最近傍にはなり得ないので最近傍候補Ｃ（ｑ）から除外できる。
【数６】
【００３８】
この性質に基づき、以下の手続きで絞込み探索を行う。
【００３９】
ステップ１において、ｉ：＝１とする。
【００４０】
ステップ２において、Ｃｉ−１（ｑ）内の各要素に対して上記の（６）式の条件を満足する候補を除外し、得られた候補集合をＣｉ（ｑ）とする。もし、ｉ＝ｍなら、ステップ４へ進む。もし、｜Ｃｉ（ｑ）｜＝１なら、その要素を最近傍パターンとして停止する。
【００４１】
ステップ３において、ｉ：＝ｉ＋１としてステップ２に戻る。
【００４２】
ステップ４において、Ｃｉ（ｑ）内の候補全てと入力パターンとの距離計算を行い、最小距離を与える学習パターンを最近傍パターンとして停止する。
【００４３】
最後に獲得した最近傍パターンをパターン探索装置１の外部に出力する。
【００４４】
（７）変更例
（７−１）変更例１
上記実施形態では、探索部６において最近傍候補Ｃ（ｑ）は重複度ｗ（ｘ）により並び替え、上位ｂ％のみとして探索してもよい。
【００４５】
（７−２）変更例２
上記実施形態では、探索部６においてハッシュ関数により得られる部分集合の和集合を最近傍候補Ｃ（ｑ）としているが、探索部６においてハッシュ関数により得られる部分集合の積集合、または、その積集合の近傍の和集合を最近傍候補Ｃ（ｑ）として探索してもよい。
【００４６】
（第２の実施形態）
本発明の第２の実施形態に係わるパターン探索装置１０１について図３に基づいて説明する。
【００４７】
本実施形態のパターン探索装置１０１と第１の実施形態のパターン探索装置１と異なる点は次の２点である。
【００４８】
第１の異なる点は、直交変換部１０７において学習パターン集合のそれぞれの学習パターンを部分空間に射影し、ベクトル空間内でのユークリッド距離に直交変換し、この直交変換した学習パターンを登録部１０２に登録する。
【００４９】
第２の異なる点は、累積確率分布獲得部１０３において、各学習パターンに関してシグモイド関数の重み付け和により累積確率分布を獲得する。
【００５０】
（１）パターン探索装置１０１の構成
図３は、本実施形態に係わるパターン探索装置１０１を示すブロック図である。
【００５１】
パターン探索装置１０１は、登録部１０２、累積確率分布獲得部１０３、ハッシュ関数部１０４、学習部１０５、探索部１０６、直交変換部１０７から構成されている。
【００５２】
なお、パターン探索装置１０１の動作のうち、第１の実施形態のパターン探索装置１と同様な処理については説明を省略する。
【００５３】
（２）直交変換部１０７
直交変換部１０７は、予め検索対象となる学習パターン集合を主成分分析する。そして、固有値の高い順に直交変換を行うためのＮ番目までの固有ベクトル、つまりＮ×Ｄの直交変換行列Ｏ＝｛φＴ１，φＴ２，・・・，φＴＮ｝を保存し、登録部１０２へ送る。
【００５４】
（３）登録部１０２
登録部１０２は、直交変換部１０７により獲得した固有ベクトルを用いて、予め検索対象となる学習パターン集合のそれぞれを直交変換した後、学習パターン集合として登録する。
【００５５】
そして、この直交変換した学習パターン集合を累積確率分布獲得部１０３と学習部１０５に送る。
【００５６】
（４）累積確率分布獲得部１０３
累積確率分布獲得部１０３は、登録部１０２で登録した学習パターン集合の各軸上での累積確率分布をそれぞれ求める。
【００５７】
ここでは各累積確率分布を、一般分布とし、この一般分布を混合ガウス分布と仮定し、シグモイド関数の重み付け和により推定する。実際には、ランダムで選択した学習パターンに対して、下記の（７）式により各学習パターンでのｈを最適化し最小二乗近似により累積確率分布を関数化する。
【数７】
【００５８】
ここでｈ’はｈｉの平均値である。ｎの個数は定数で与えるか、一般的な最適化手法により近似精度の許容範囲における最小数を求める。
【００５９】
（５）探索部１０６
探索部１０６は、まず検索したい顔画像などの未知の入力パターンｑが入力される。そして、この入力パターンｑについての、学習パターン集合ＡＬＬ中の最近傍パターンを探索する。この探索は、ハッシュ関数部１０４により獲得した各ハッシュ関数と、学習部１０５によって生成した部分集合により探索する。
【００６０】
直交変換部１０７により獲得した固有ベクトルにより入力パターンを直交変換し、直交入力パターンＯＴｑとする。直交入力パターンを入力値としたときハッシュ関数の出力であるハッシュ値Ｈにより限定される部分集合ＢｉＨを下記の（８）式で定義できる。
【数８】
【００６１】
ここでは、ランダムで選択したｍ個のハッシュ関数により得られる部分集合の和集合を最近傍候補Ｃ（ｑ）とする。
【数９】
【００６２】
このとき、最近傍候補Ｃ（ｑ）を獲得する際に、含まれたバケット数を重複度ｗ（ｘ）とし、これによりソートし最大となるパターンと入力パターンとの距離を暫定距離ｚとする。ｘ１とｘ２のＬｐ距離をｄｐ（ｘ１，ｘ２）と定義すると、暫定距離ｚは下記の（１０）式のようになる。
【数１０】
【００６３】
ここで、下記の（１１）式を満たす候補ｘは最近傍にはなり得ないので最近傍候補Ｃ（ｑ）から除外できる。
【数１１】
【００６４】
この性質に基づき、固有値の高い主軸への射影成分から順に、以下の手続きで絞込み探索を行う。
【００６５】
ステップ１において、ｉ：＝１とする。
【００６６】
ステップ２において、Ｃｉ−１（ｑ）内の各要素に対して上記の（１１）式の条件を満足する候補を除外し、得られた候補集合をＣｉ（ｑ）とする。もし、ｉ＝ｍなら、ステップ４へ進む。もし、｜Ｃｉ（ｑ）｜＝１なら、その要素を最近傍パターンとして停止する。
【００６７】
ステップ３においてｉ：＝ｉ＋１としてステップ２に戻る。
【００６８】
ステップ４において、Ｃｉ（ｑ）内の候補全てと入力パターンとの距離計算を行い、最小距離を与える学習パターンを最近傍パターンとして停止する。
【００６９】
このような計算を行う理由は、固有値の最も高い第一主成分は最も分散の大きい軸であり、Ｃ（ｑ）−Ｂ１ｈ１（ｑ）の殆どの要素が、｜φＴ１ｑ−φＴｘ｜ｐ＞ｚｐという条件を満足してしまうためφＴ１ｑ１の値を調べるだけで一挙に最近傍候補集合を小さくすることができる。第二主成分以降もそれ以降の主軸と比べた際に同様のことが言えるため、候補を絞り込む効率を考えると妥当な処理であるといえる。
【００７０】
最後に獲得した最近傍パターンをパターン探索装置１の外部に出力する。
【００７１】
（第３の実施形態）
本発明の第３の実施形態に係わるパターン認識装置２０１について図４に基づいて説明する。
【００７２】
本実施形態のパターン認識装置２０１と、第１の実施形態のパターン探索装置１及び第２の実施形態のパターン探索装置１０１と異なる点は次の点である。
【００７３】
第１の異なる点は、パターン認識装置２０１は、予め検索対象となる学習パターン集合を登録して学習パターン集合とする。この学習パターン集合に対応するクラスを登録し、入力パターンに対してパターン探索部２０８により最近傍パターンを探索し、クラス部２０９により出力した対応するクラスを認識結果として出力する。
【００７４】
第２の異なる点は、パターン探索部２０８は、累積確率分布獲得部２０３においてパターンを獲得する次元軸での値により、累積ヒストグラムを獲得し、それを累積確率分布とする。
【００７５】
（１）パターン認識装置２０１の構成
図４は、本実施形態に係わるパターン認識装置２０１を示すブロック図である。
【００７６】
パターン認識装置２０１は、登録部２０２、累積確率分布獲得部２０３、ハッシュ関数部２０４、学習部２０５、探索部２０６、直交変換部２０７、パターン探索部２０８、クラス部２０９から構成されている。
【００７７】
なお、パターン認識装置２０１の動作のうち、第１の実施形態のパターン探索装置１及び第２の実施形態のパターン探索装置１０１と同様な処理については説明を省略する。
【００７８】
（２）累積確率分布獲得部２０３
累積確率分布獲得部２０３は、登録部２０２で登録した学習パターン集合の各軸上での累積確率分布をそれぞれ獲得する。ここでは各累積確率分布を、学習パターン集合の各軸上での値により並び替えを行い、累積ヒストグラムを求めることにより推定する。
【００７９】
上記各実施形態における関数による分布表現との違いは、最適化パラメータがないため一意に求めることができる反面、学習パターンが少ないと学習パターン間の分布が線形で表現されるため誤差が大きくなる点である。
【００８０】
（３）パターン探索部２０８
パターン探索部２０８は、登録部２０２、累積確率分布獲得部２０３、ハッシュ関数部２０４、学習部２０５、探索部２０６、直交変換部２０７から構成され、入力パターンの最近傍パターンを、登録部２０２に登録した学習パターン集合の中から探索する。
【００８１】
（４）クラス部２０９
クラス部２０９は、学習パターン集合中の各パターンに対応するクラスを登録しておき、パターン探索部２０８により探索した入力パターンの最近傍パターンに対応するクラスを、入力パターンのクラスとしてパターン探索装置１の外部に出力する。
【００８２】
（変更例）
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。
【００８３】
また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【００８４】
【図１】本発明の第１の実施形態のパターン探索装置の構成を示すブロック図である。
【図２】第１の実施形態の概念の説明図である。
【図３】第２の実施形態のパターン探索装置の構成を示すブロック図である。
【図４】第３の実施形態のパターン探索装置の構成を示すブロック図である。
【図５】従来技術の概念の説明図である。
【符号の説明】
【００８５】
１・・・パターン探索装置
２・・・登録部
３・・・累積確率獲得部
４・・・ハッシュ関数部
５・・・学習部
６・・・探索部
【特許請求の範囲】
【請求項１】
ｄ次元の複数の学習パターンを記憶する記憶部と、
前記複数の学習パターンから、前記ｄ次元の任意の次元軸上における前記学習パターンのそれぞれの存在確率の累積確率を表す累積確率分布を求める分布獲得部と、
累積確率が分割された複数の確率区間のそれぞれに前記累積確率分布で対応する前記次元軸上の分布区間内の任意の点の値を、前記各確率区間に対応するハッシュ値に変換するハッシュ関数を求めるハッシュ関数獲得部と、
前記ハッシュ関数を用いて前記各学習パターンのハッシュ値をそれぞれ求め、前記各学習パターンを前記ハッシュ値に対応するバケットに分類する学習部と、
前記ハッシュ関数を用いて入力パターンのハッシュ値を求め、前記入力パターンのハッシュ値に対応するバケットに属する前記学習パターンの中から、前記入力パターンに最も類似する前記学習パターンを探索する探索部と、
を有するパターン探索装置。
【請求項２】
前記複数の確率区間は、累積確率が一定の幅で分割された区間である、
請求項１記載のパターン探索装置。
【請求項３】
前記分布獲得部は、前記学習パターンの分布が正規分布であると仮定し、前記累積確率分布をシグモイド関数で近似する、
請求項２記載のパターン探索装置。
【請求項４】
前記分布獲得部は、前記累積確率分布を関数の重み付け和によって近似する、
請求項２記載のパターン探索装置。
【請求項５】
前記分布獲得部は、前記各次元軸に関して、前記学習パターンの値により累積ヒストグラムを獲得し、前記累積ヒストグラムを前記累積確率分布とする、
請求項２記載のパターン探索装置。
【請求項６】
前記複数の学習パターンのそれぞれを部分空間に射影し、ベクトル空間内でのユークリッド距離に直交変換する直交変換部をさらに有し、
前記登録部は、前記直交変換した学習パターンをそれぞれ登録する、
請求項２記載のパターン探索装置。
【請求項７】
前記直交変換部は、前記学習パターンを主成分分析により直交変換する、
請求項６記載のパターン探索装置。
【請求項８】
前記分布獲得部は、前記ｄ次元のうちの任意の複数の次元軸のそれぞれについての累積確率分布をそれぞれ求め、
前記ハッシュ関数獲得部は、前記各累積確率分布についてのハッシュ関数をそれぞれ求め、
前記学習部は、前記各ハッシュ関数を用いて前記各学習パターンのハッシュ値をそれぞれ求めて、前記各学習パターンを前記各ハッシュ値に対応するバケットに分類し、
前記探索部は、前記ハッシュ値に対応する前記バケット中の複数の前記学習パターンを求めるときに、前記各バケット中の前記学習パターンの和集合の中から前記探索を行う、
請求項２記載のパターン探索装置。
【請求項９】
前記探索部は、前記学習パターンのそれぞれが前記和集合に属する回数を求め、前記回数が上位のみの複数の前記学習パターンの中から前記探索を行う、
請求項８記載のパターン探索装置。
【請求項１０】
前記分布獲得部は、前記ｄ次元のうちの任意の複数の次元軸のそれぞれについての累積確率分布をそれぞれ求め、
前記ハッシュ関数獲得部は、前記各累積確率分布についてのハッシュ関数をそれぞれ求め、
前記学習部は、前記各ハッシュ関数を用いて前記各学習パターンのハッシュ値をそれぞれ求めて、前記各学習パターンを前記各ハッシュ値に対応するバケットに分類し、
前記探索部は、前記ハッシュ値に対応する前記バケット中の複数の前記学習パターンを求めるときに、前記各バケット中の前記学習パターンの積集合、または、前記積集合の近傍の中から前記探索を行う、
請求項２記載のパターン探索装置。
【請求項１１】
ｄ次元の複数の学習パターンを記憶する記憶ステップと、
前記複数の学習パターンから、前記ｄ次元の任意の次元軸上における前記学習パターンのそれぞれの存在確率の累積確率を表す累積確率分布を求める分布獲得ステップと、
累積確率が分割された複数の確率区間のそれぞれに前記累積確率分布で対応する前記次元軸上の分布区間内の任意の点の値を、前記各確率区間に対応するハッシュ値に変換するハッシュ関数を求めるハッシュ関数獲得ステップと、
前記ハッシュ関数を用いて前記各学習パターンのハッシュ値をそれぞれ求め、前記各学習パターンを前記ハッシュ値に対応するバケットに分類する学習ステップと、
前記ハッシュ関数を用いて入力パターンのハッシュ値を求め、前記入力パターンのハッシュ値に対応するバケットに属する前記学習パターンの中から、前記入力パターンに最も類似する前記学習パターンを探索する探索ステップと、
を有するパターン探索方法。
【請求項１２】
ｄ次元の複数の学習パターンを記憶する記憶機能と、
前記複数の学習パターンから、前記ｄ次元の任意の次元軸上における前記学習パターンのそれぞれの存在確率の累積確率を表す累積確率分布を求める分布獲得機能と、
累積確率が分割された複数の確率区間のそれぞれに前記累積確率分布で対応する前記次元軸上の分布区間内の任意の点の値を、前記各確率区間に対応するハッシュ値に変換するハッシュ関数を求めるハッシュ関数獲得機能と、
前記ハッシュ関数を用いて前記各学習パターンのハッシュ値をそれぞれ求め、前記各学習パターンを前記ハッシュ値に対応するバケットに分類する学習機能と、
前記ハッシュ関数を用いて入力パターンのハッシュ値を求め、前記入力パターンのハッシュ値に対応するバケットに属する前記学習パターンの中から、前記入力パターンに最も類似する前記学習パターンを探索する探索機能と、
をコンピュータによって実現するパターン探索プログラム。
【請求項１】
ｄ次元の複数の学習パターンを記憶する記憶部と、
前記複数の学習パターンから、前記ｄ次元の任意の次元軸上における前記学習パターンのそれぞれの存在確率の累積確率を表す累積確率分布を求める分布獲得部と、
累積確率が分割された複数の確率区間のそれぞれに前記累積確率分布で対応する前記次元軸上の分布区間内の任意の点の値を、前記各確率区間に対応するハッシュ値に変換するハッシュ関数を求めるハッシュ関数獲得部と、
前記ハッシュ関数を用いて前記各学習パターンのハッシュ値をそれぞれ求め、前記各学習パターンを前記ハッシュ値に対応するバケットに分類する学習部と、
前記ハッシュ関数を用いて入力パターンのハッシュ値を求め、前記入力パターンのハッシュ値に対応するバケットに属する前記学習パターンの中から、前記入力パターンに最も類似する前記学習パターンを探索する探索部と、
を有するパターン探索装置。
【請求項２】
前記複数の確率区間は、累積確率が一定の幅で分割された区間である、
請求項１記載のパターン探索装置。
【請求項３】
前記分布獲得部は、前記学習パターンの分布が正規分布であると仮定し、前記累積確率分布をシグモイド関数で近似する、
請求項２記載のパターン探索装置。
【請求項４】
前記分布獲得部は、前記累積確率分布を関数の重み付け和によって近似する、
請求項２記載のパターン探索装置。
【請求項５】
前記分布獲得部は、前記各次元軸に関して、前記学習パターンの値により累積ヒストグラムを獲得し、前記累積ヒストグラムを前記累積確率分布とする、
請求項２記載のパターン探索装置。
【請求項６】
前記複数の学習パターンのそれぞれを部分空間に射影し、ベクトル空間内でのユークリッド距離に直交変換する直交変換部をさらに有し、
前記登録部は、前記直交変換した学習パターンをそれぞれ登録する、
請求項２記載のパターン探索装置。
【請求項７】
前記直交変換部は、前記学習パターンを主成分分析により直交変換する、
請求項６記載のパターン探索装置。
【請求項８】
前記分布獲得部は、前記ｄ次元のうちの任意の複数の次元軸のそれぞれについての累積確率分布をそれぞれ求め、
前記ハッシュ関数獲得部は、前記各累積確率分布についてのハッシュ関数をそれぞれ求め、
前記学習部は、前記各ハッシュ関数を用いて前記各学習パターンのハッシュ値をそれぞれ求めて、前記各学習パターンを前記各ハッシュ値に対応するバケットに分類し、
前記探索部は、前記ハッシュ値に対応する前記バケット中の複数の前記学習パターンを求めるときに、前記各バケット中の前記学習パターンの和集合の中から前記探索を行う、
請求項２記載のパターン探索装置。
【請求項９】
前記探索部は、前記学習パターンのそれぞれが前記和集合に属する回数を求め、前記回数が上位のみの複数の前記学習パターンの中から前記探索を行う、
請求項８記載のパターン探索装置。
【請求項１０】
前記分布獲得部は、前記ｄ次元のうちの任意の複数の次元軸のそれぞれについての累積確率分布をそれぞれ求め、
前記ハッシュ関数獲得部は、前記各累積確率分布についてのハッシュ関数をそれぞれ求め、
前記学習部は、前記各ハッシュ関数を用いて前記各学習パターンのハッシュ値をそれぞれ求めて、前記各学習パターンを前記各ハッシュ値に対応するバケットに分類し、
前記探索部は、前記ハッシュ値に対応する前記バケット中の複数の前記学習パターンを求めるときに、前記各バケット中の前記学習パターンの積集合、または、前記積集合の近傍の中から前記探索を行う、
請求項２記載のパターン探索装置。
【請求項１１】
ｄ次元の複数の学習パターンを記憶する記憶ステップと、
前記複数の学習パターンから、前記ｄ次元の任意の次元軸上における前記学習パターンのそれぞれの存在確率の累積確率を表す累積確率分布を求める分布獲得ステップと、
累積確率が分割された複数の確率区間のそれぞれに前記累積確率分布で対応する前記次元軸上の分布区間内の任意の点の値を、前記各確率区間に対応するハッシュ値に変換するハッシュ関数を求めるハッシュ関数獲得ステップと、
前記ハッシュ関数を用いて前記各学習パターンのハッシュ値をそれぞれ求め、前記各学習パターンを前記ハッシュ値に対応するバケットに分類する学習ステップと、
前記ハッシュ関数を用いて入力パターンのハッシュ値を求め、前記入力パターンのハッシュ値に対応するバケットに属する前記学習パターンの中から、前記入力パターンに最も類似する前記学習パターンを探索する探索ステップと、
を有するパターン探索方法。
【請求項１２】
ｄ次元の複数の学習パターンを記憶する記憶機能と、
前記複数の学習パターンから、前記ｄ次元の任意の次元軸上における前記学習パターンのそれぞれの存在確率の累積確率を表す累積確率分布を求める分布獲得機能と、
累積確率が分割された複数の確率区間のそれぞれに前記累積確率分布で対応する前記次元軸上の分布区間内の任意の点の値を、前記各確率区間に対応するハッシュ値に変換するハッシュ関数を求めるハッシュ関数獲得機能と、
前記ハッシュ関数を用いて前記各学習パターンのハッシュ値をそれぞれ求め、前記各学習パターンを前記ハッシュ値に対応するバケットに分類する学習機能と、
前記ハッシュ関数を用いて入力パターンのハッシュ値を求め、前記入力パターンのハッシュ値に対応するバケットに属する前記学習パターンの中から、前記入力パターンに最も類似する前記学習パターンを探索する探索機能と、
をコンピュータによって実現するパターン探索プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２００９−２０７６９（Ｐ２００９−２０７６９Ａ）
【公開日】平成２１年１月２９日（２００９．１．２９）
【国際特許分類】
【出願番号】特願２００７−１８３７８８（Ｐ２００７−１８３７８８）
【出願日】平成１９年７月１３日（２００７．７．１３）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２１年１月２９日（２００９．１．２９）
【国際特許分類】
【出願日】平成１９年７月１３日（２００７．７．１３）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]