(57)【要約】      （修正有）【課題】超平面が原点を通るものとして計算を実行するアルゴリズムを利用する場合において、認証精度を向上させる。【解決手段】認証方法は、（ｎ＋ｐ）次元空間（ｎ及びｐは自然数）の原点を通る１又は複数の超平面の法線ベクトルを算出し、第１のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより第１の（ｎ＋ｐ）次元特徴ベクトルを生成し、当該第１の（ｎ＋ｐ）次元特徴ベクトルを、１又は複数の超平面の法線ベクトルを用いて第１のビット列に変換し、データ格納部に格納されている検索対象のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより検索対象の（ｎ＋ｐ）次元特徴ベクトルを生成し、当該検索対象の（ｎ＋ｐ）次元特徴ベクトルを、１又は複数の超平面の法線ベクトルを用いて第２のビット列に変換し、第１のビット列と第２のビット列との距離を算出する処理を含む。【選択図】図３
2014074964.tif 000002
【特許請求の範囲】
【請求項１】
ビット列間の距離に基づき認証を行うコンピュータに、
（ｎ＋ｐ）次元空間（ｎ及びｐは自然数）の原点を通る１又は複数の超平面の法線ベクトルを算出し、
第１のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより第１の（ｎ＋ｐ）次元特徴ベクトルを生成し、当該第１の（ｎ＋ｐ）次元特徴ベクトルを、前記１又は複数の超平面の法線ベクトルを用いて第１のビット列に変換し、
データ格納部に格納されている検索対象のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより検索対象の（ｎ＋ｐ）次元特徴ベクトルを生成し、当該検索対象の（ｎ＋ｐ）次元特徴ベクトルを、前記１又は複数の超平面の法線ベクトルを用いて第２のビット列に変換し、
前記第１のビット列と前記第２のビット列との距離を算出する
処理を実行させるための認証プログラム。
【請求項２】
前記法線ベクトルを算出する処理において、
（ｎ＋ｐ）次元の初期ベクトルを生成し、
前記超平面が原点を通るものとして計算を実行するアルゴリズムを用いて、前記初期ベクトルから前記法線ベクトルを算出する
ことを特徴とする請求項１記載の認証プログラム。
【請求項３】
ビット列間の距離に基づき認証を行うコンピュータが、
（ｎ＋ｐ）次元空間（ｎ及びｐは自然数）の原点を通る１又は複数の超平面の法線ベクトルを算出し、
第１のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより第１の（ｎ＋ｐ）次元特徴ベクトルを生成し、当該第１の（ｎ＋ｐ）次元特徴ベクトルを、前記１又は複数の超平面の法線ベクトルを用いて第１のビット列に変換し、
データ格納部に格納されている検索対象のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより検索対象の（ｎ＋ｐ）次元特徴ベクトルを生成し、当該検索対象の（ｎ＋ｐ）次元特徴ベクトルを、前記１又は複数の超平面の法線ベクトルを用いて第２のビット列に変換し、
前記第１のビット列と前記第２のビット列との距離を算出する
処理を実行する認証方法。
【請求項４】
ビット列間の距離に基づき認証を行う認証装置であって、
検索対象のｎ次元特徴ベクトルを格納するデータ格納部と、
（ｎ＋ｐ）次元空間（ｎ及びｐは自然数）の原点を通る１又は複数の超平面の法線ベクトルを算出する算出部と、
第１のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより第１の（ｎ＋ｐ）次元特徴ベクトルを生成する第１生成部と、
前記データ格納部に格納されている検索対象のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより検索対象の（ｎ＋ｐ）次元特徴ベクトルを生成する第２生成部と、
前記第１の（ｎ＋ｐ）次元特徴ベクトルを、前記１又は複数の超平面の法線ベクトルを用いて第１のビット列に変換する第１変換部と、
前記検索対象の（ｎ＋ｐ）次元特徴ベクトルを、前記１又は複数の超平面の法線ベクトルを用いて第２のビット列に変換する第２変換部と、
前記第１のビット列と前記第２のビット列との距離を算出する算出部と
を有する認証装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、認証技術に関する。
【背景技術】
【０００２】
生体認証として、生体情報の入力に加えてＩＤ等の入力を要する１対１認証と、ＩＤ等の入力を要さず生体情報の入力だけで認証を行うことが可能な１対Ｎ認証とが知られている。
【０００３】
１対Ｎ認証においては、入力された生体情報から抽出された特徴量を成分とする特徴ベクトルと、予めデータベース等に登録された複数個の特徴ベクトルの各々との間の距離を算出する処理を実行する。そのため、予め登録された特徴ベクトルの数が多くなるほど認証に要する時間が長くなる。
【０００４】
従来、特徴ベクトルをバイナリ化し、バイナリデータ間の距離を算出することにより認証に要する時間を短くする技術が存在する。バイナリ化には、例えばローカリティセンシティブハッシング（Locality-Sensitive Hashing）が用いられる。ローカリティセンシティブハッシングにおいては、データ空間における超平面の法線ベクトルと特徴ベクトルとの内積を算出し、内積の正負に応じて０又は１を割り当てることにより特徴ベクトルをバイナリデータに変換する。すなわち、データ空間を超平面により切り分け、切り分けにより得られた各領域にバイナリデータを割り当て、特徴ベクトルをその特徴ベクトルが属する領域に割り当てられたバイナリデータに変換する。なお、ここで考える超平面は、データ空間のどこに存在していてもよい。
【０００５】
ここで、高次元のアフィン空間であるデータ空間の１点を固定し、その点を原点とするベクトル空間としてデータ空間をとらえる。このデータ空間をＶとする。この場合、法線ベクトルｎ（数式（１）においては、ｎの上に矢印を付している）及び原点からのオフセットｂを用いて、超平面Ｈ（ｎ，ｂ）を以下のように記述することができる。
【０００６】
【数１】
2014074964.tif 000003
【０００７】
全ての超平面が原点を通る場合に切り分けにより得られる領域の数はＯ記法でＯ（ビット数（次元数−１））であるのに対し、超平面がオフセットを有している場合に切り分けにより得られる領域の数はＯ記法でＯ（ビット数（次元数））である。すなわち、超平面がオフセットを有している方が、切り分けにより得られる領域の数は多くなる。
【０００８】
図１及び図２に、超平面による領域の切り分けの具体例を示す。図１及び図２が示す空間は２次元空間である。図１及び図２において、１１乃至１３は超平面である。超平面１１より下側に特徴ベクトルが存在する場合には１桁目のビットを１とし、上側に存在する場合には０としている。超平面１２より上側に特徴ベクトルが存在する場合には２桁目のビットを１とし、下側に存在する場合には０としている。超平面１３より右側に特徴ベクトルが存在する場合には３桁目のビットを１とし、左側に存在する場合には０としている。
【０００９】
図１の例のように超平面１１乃至１３が原点を通っている場合、２次元空間は６つの領域に切り分けられる。具体的には、ビット列「０００」が割り当てられた領域と、ビット列「０１０」が割り当てられた領域と、ビット列「０１１」が割り当てられた領域と、ビット列「１１１」が割り当てられた領域と、ビット列「１０１」が割り当てられた領域と、ビット列「１００」が割り当てられた領域とに切り分けられる。
【００１０】
これに対し、図２の例のように原点を通らない超平面１３が存在する場合、２次元空間は７つの領域に切り分けられる。具体的には、ビット列「０００」が割り当てられた領域と、ビット列「０１０」が割り当てられた領域と、ビット列「０１１」が割り当てられた領域と、ビット列「１１０」が割り当てられた領域と、ビット列「１１１」が割り当てられた領域と、ビット列「１０１」が割り当てられた領域と、ビット列「１００」が割り当てられた領域とに切り分けられる。
【００１１】
切り分けにより得られる領域の数が多いほど特徴ベクトルをより厳密に分類することができるようになるため、認証精度が高くなる。よって、認証精度を高くするためには、超平面がオフセットを有している方が好ましいということになる。
【００１２】
しかし、従来技術において利用されている、超平面の法線ベクトルを求めるアルゴリズムは、超平面が原点を通るものとして計算を実行するアルゴリズムである。よって、新たにアルゴリズムを開発しなければ、超平面がオフセットを有しているものとして計算を実行することはできない。また、超平面がオフセットを有しているものとして計算を実行するアルゴリズムは、超平面が原点を通るものとして計算を実行するアルゴリズムと比べて複雑であるため、計算量が多くなるという問題がある。以上のような点に鑑みると、新たにアルゴリズムを開発することは好ましくない。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】M. Datar, N. Immorlica, P. Indyk, V. S. Mirrokni, "Locality-Sensitive Hashing Scheme Based on p-Stable Distributions", Proceedings of the twentieth annual symposium on Computational geometry (SCG), 2004, p.253-262
【非特許文献２】Y. Weiss, A. Torralba, R. Fergus, "Spectral Hashing", Advances in Neural Information Processing Systems (NIPS), 2008, p.1753-1760
【非特許文献３】M. Norouzi, D. J. Fleet, "Minimal Loss Hashing for Compact Binary Codes", International Conference in Machine Learning (ICML), 2011, p.353-360
【発明の概要】
【発明が解決しようとする課題】
【００１４】
１つの側面では、本発明の目的は、超平面が原点を通るものとして計算を実行するアルゴリズムを利用する場合において、認証精度を向上させるための技術を提供することである。
【課題を解決するための手段】
【００１５】
本発明に係る認証方法は、（ｎ＋ｐ）次元空間（ｎ及びｐは自然数）の原点を通る１又は複数の超平面の法線ベクトルを算出し、第１のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより第１の（ｎ＋ｐ）次元特徴ベクトルを生成し、当該第１の（ｎ＋ｐ）次元特徴ベクトルを、１又は複数の超平面の法線ベクトルを用いて第１のビット列に変換し、データ格納部に格納されている検索対象のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより検索対象の（ｎ＋ｐ）次元特徴ベクトルを生成し、当該検索対象の（ｎ＋ｐ）次元特徴ベクトルを、１又は複数の超平面の法線ベクトルを用いて第２のビット列に変換し、第１のビット列と第２のビット列との距離を算出する処理を含む。
【発明の効果】
【００１６】
超平面が原点を通るものとして計算を実行するアルゴリズムを利用する場合において、認証精度を向上させることができるようになる。
【図面の簡単な説明】
【００１７】
【図１】図１は、超平面による領域の切り分けの一例を示す図である。
【図２】図２は、超平面による領域の切り分けの一例を示す図である。
【図３】図３は、認証装置の機能ブロック図を示す図である。
【図４】図４は、クエリデータ格納部に格納されているクエリデータの一例を示す図である。
【図５】図５は、検索対象データ格納部に格納されている検索対象データの一例を示す図である。
【図６】図６は、第１持ち上げ部が実行する処理の処理フローを示す図である。
【図７】図７は、第１データ格納部に格納されているデータの一例を示す図である。
【図８】図８は、第１変換部が実行する処理の処理フローを示す図である。
【図９】図９は、第１バイナリデータ格納部に格納されているデータの一例を示す図である。
【図１０】図１０は、第２持ち上げ部が実行する処理の処理フローを示す図である。
【図１１】図１１は、第２データ格納部に格納されているデータの一例を示す図である。
【図１２】図１２は、第２変換部が実行する処理の処理フローを示す図である。
【図１３】図１３は、第２バイナリデータ格納部に格納されているデータの一例を示す図である。
【図１４】図１４は、初期化部が実行する処理の処理フローを示す図である。
【図１５】図１５は、第１の実施の形態における設定処理の処理フローを示す図である。
【図１６】図１６は、初期値格納部に格納されているデータの一例を示す図である。
【図１７】図１７は、変換規則生成部が実行する処理の処理フローを示す図である。
【図１８】図１８は、検索部が実行する処理の処理フローを示す図である。
【図１９】図１９は、検索結果格納部に格納されているデータの一例を示す。
【図２０】図２０は、ビット数と再現率との関係を示す図である。
【図２１】図２１は、ビット数と適合率との関係を示す図である。
【図２２】図２２は、第２の実施の形態における設定処理の処理フローを示す図である。
【図２３】図２３は、第３の実施の形態における設定処理の処理フローを示す図である。
【図２４】図２４は、第４の実施の形態における設定処理の処理フローを示す図である。
【図２５】図２５は、第５の実施の形態における設定処理の処理フローを示す図である。
【図２６】図２６は、第６の実施の形態における設定処理の処理フローを示す図である。
【図２７】図２７は、第７の実施の形態における設定処理の処理フローを示す図である。
【図２８】図２８は、第８の実施の形態における設定処理の処理フローを示す図である。
【図２９】図２９は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１８】
以下では、超平面がオフセットを有しているものとして計算を実行するアルゴリズムを新たに検討するのではなく、超平面が原点を通るものとして計算を実行するアルゴリズムを利用して認証の精度を向上させる方法について説明する。この方法においては、データをｐ次元（ｐは自然数）大きい空間に写像し、その空間において、超平面が原点を通るものとして計算を実行するアルゴリズムを利用して超平面の法線ベクトルを求める。
【００１９】
データ空間Ｖの次元をＮ（Ｎは自然数）とし、データ空間Ｗの次元を（Ｎ＋１）とする。そして、以下の埋め込み写像を考える。
【００２０】
【数２】
2014074964.tif 000004
【００２１】
なお、説明を簡単にするためｐ＝１としているが、ｐ＞１の場合もｐ＝１の場合と概念として同等である。
【００２２】
Ｗの第（Ｎ＋１）成分をｚと呼べば、これは、Ｗにおけるｚ＝１の超平面へのＶの埋め込みに相当する。なお、説明を簡単にするためＷの第（Ｎ＋１）成分の値を１としているが、１に限られるわけではない。
【００２３】
そして、Ｗの原点を通る超平面は、法線ベクトルが（０，０，．．，０，１）に比例しなければｚ＝１の平面と交差する。その共通集合の次元は（Ｎ−１）次元である。また、共通集合は必ずしもＶの原点を通るとは限らない。つまり、Ｗの原点を通る超平面は、Ｖにおいてオフセットを有する超平面へマッピングされる。ｎ（ｎは自然数）次元空間における超平面の法線ベクトルの自由度は（ｎ−１）であるから、Ｗの原点を通る超平面の自由度はＮであり、Ｖにおいてオフセットを有する超平面の自由度も（Ｎ−１）＋１＝Ｎである。
【００２４】
ここで、上で述べた超平面間の写像を具体的に考える。
【００２５】
Ｗの原点を通る超平面の法線ベクトルを以下のように表す。
【００２６】
【数３】
2014074964.tif 000005
【００２７】
Ｗにおけるｚ＝１の平面上の点を以下のように表す。
【００２８】
【数４】
2014074964.tif 000006
【００２９】
すると、超平面とｚ＝１の平面との共通集合は、以下のようになる。
【００３０】
【数５】
2014074964.tif 000007
【００３１】
これは、Ｖにおいてオフセットを有する超平面の方程式に相当する。
【００３２】
［実施の形態１］
図３に、本実施の形態における認証装置１の機能ブロック図を示す。認証装置１は、クエリデータ格納部１０１と、第１持ち上げ部１０３と、第１データ格納部１０５と、第１変換部１０７と、第１バイナリデータ格納部１０９と、検索対象データ格納部１１１と、第２持ち上げ部１１３と、第２データ格納部１１５と、第２変換部１１７と、第２バイナリデータ格納部１１９と、学習データ格納部１２１と、初期化部１２３と、初期値格納部１２５と、第３持ち上げ部１２７と、第３データ格納部１２９と、変換規則生成部１３１と、規則データ格納部１３３と、検索部１３５と、検索結果格納部１３７と、出力部１３９とを含む。
【００３３】
第１持ち上げ部１０３は、クエリデータ格納部１０１に格納されているクエリデータを用いて処理を実行し、処理結果を第１データ格納部１０５に格納する。第１変換部１０７は、第１データ格納部１０５に格納されているデータ及び規則データ格納部１３３に格納されているデータを用いて処理を実行し、処理結果を第１バイナリデータ格納部１０９に格納する。
【００３４】
第２持ち上げ部１１３は、検索対象データ格納部１１１に格納されている検索対象データを用いて処理を実行し、処理結果を第２データ格納部１１５に格納する。第２変換部１１７は、第２データ格納部１１５に格納されているデータ及び規則データ格納部１３３に格納されているデータを用いて処理を実行し、処理結果を第２バイナリデータ格納部１１９に格納する。
【００３５】
初期化部１２３は、学習データ格納部１２１に格納されている学習データを用いて処理を実行し、処理結果を初期値格納部１２５に格納する。第３持ち上げ部１２７は、学習データ格納部１２１に格納されている学習データを用いて処理を実行し、処理結果を第３データ格納部１２９に格納する。変換規則生成部１３１は、初期値格納部１２５に格納されているデータ及び第３データ格納部１２９に格納されているデータを用いて処理を実行し、処理結果を規則データ格納部１３３に格納する。
【００３６】
検索部１３５は、第１バイナリデータ格納部１０９に格納されているデータ及び第２バイナリデータ格納部１１９に格納されているデータを用いて処理を実行し、処理結果を検索結果格納部１３７に格納する。出力部１３９は、検索結果格納部１３７に格納されているデータを用いて処理を行い、処理結果を例えば表示装置に出力する。
【００３７】
図４に、クエリデータ格納部１０１に格納されているクエリデータの一例を示す。図４の例では、ユーザから入力された又はネットワークを介して受信した、生体データから抽出された特徴量を成分とするｎ次元（ｎは自然数）の特徴ベクトルのデータが格納されている。特徴ベクトルは、生体データが画像データである場合、例えば画像中の特定の領域における隆線の方向、長さ及び勾配等の特徴量をベクトル化したものである。生体データが音声データである場合、特徴ベクトルは、例えば周波数成分の分布、強度及びピーク値等の特徴量をベクトル化したものである。
【００３８】
図５に、検索対象データ格納部１１１に格納されている検索対象データの一例を示す。図５の例では、データＩＤと、生体データから抽出された特徴量を成分とするｎ次元の特徴ベクトルのデータとが格納されている。検索対象データ格納部１１１には、複数人分の特徴ベクトルのデータを予め格納しておく。
【００３９】
本実施の形態においては、クエリデータ格納部１０１に格納されている特徴ベクトルと一致する特徴ベクトルを検索対象データ格納部１１１から検索することにより、１対Ｎ認証を行う。
【００４０】
学習データ格納部１２１には、検索対象データ格納部１１１に格納されている検索対象データの少なくとも一部が格納されている。学習データ格納部１２１に格納されている学習データのフォーマットは、検索対象データ格納部１１１に格納されている検索対象データのフォーマットと同じである。学習データ格納部１２１に格納されている学習データは、変換規則Ｗの生成に用いられる。変換規則Ｗは、１又は複数の超平面の法線ベクトルを行ベクトルとする行列である。
【００４１】
次に、図６乃至図１９を用いて、認証装置１の動作について説明する。まず、図６乃至図９を用いて、クエリデータ格納部１０１に新たに特徴ベクトルのデータが格納された場合に実行する処理について説明する。
【００４２】
第１持ち上げ部１０３は、クエリデータ格納部１０１に新たにｎ次元特徴ベクトルのデータが格納されたことを検出すると、新たに格納されたｎ次元特徴ベクトルのデータをクエリデータ格納部１０１から読み出す（図６：ステップＳ１）。
【００４３】
第１持ち上げ部１０３は、ｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分（ｐは自然数）を追加することにより、（ｎ＋ｐ）次元特徴ベクトルを生成する（ステップＳ３）。生成される（ｎ＋ｐ）次元特徴ベクトルは、第１成分から第ｎ成分までは元のｎ次元特徴ベクトルと同じであり、第（ｎ＋１）成分から第（ｎ＋ｐ）成分までが新たに追加された成分である。第（ｎ＋１）成分から第（ｎ＋ｐ）成分までには、任意の値を設定することができる。
【００４４】
第１持ち上げ部１０３は、生成された（ｎ＋ｐ）次元特徴ベクトルのデータを第１データ格納部１０５に格納する（ステップＳ５）。そして処理を終了する。
【００４５】
図７に、第１データ格納部１０５に格納されているデータの一例を示す。図７の例では、（ｎ＋ｐ）次元特徴ベクトルの各成分の値が格納されている。
【００４６】
以上のような処理を実行すれば、入力された生体データから抽出された特徴量を成分とするｎ次元の特徴ベクトルから、次元の持ち上げによって、（ｎ＋ｐ）次元の特徴ベクトルを生成できる。
【００４７】
そして、第１データ格納部１０５に（ｎ＋ｐ）次元特徴ベクトルのデータが格納されると、第１変換部１０７は以下のような処理を実行する。第１変換部１０７が実行する処理については、図８及び図９を用いて説明する。
【００４８】
まず、第１変換部１０７は、変換規則Ｗのデータを規則データ格納部１３３から読み出し、また、（ｎ＋ｐ）次元特徴ベクトルのデータを第１データ格納部１０５から読み出す（図８：ステップＳ１１）。変換規則Ｗは、ｍ行（ｎ＋ｐ）列の行列である（ｍは自然数）。変換規則Ｗについては後で詳細に説明する。
【００４９】
第１変換部１０７は、変換規則Ｗと（ｎ＋ｐ）次元特徴ベクトルとの積演算を実行し、実行結果をメインメモリ等の記憶装置に格納する（ステップＳ１３）。
【００５０】
ステップＳ１３においては、以下のような行列の積演算を実行する。
【００５１】
【数６】
2014074964.tif 000008
【００５２】
第１変換部１０７は、ステップＳ１３の処理によって得られた列ベクトル（ｙ１，ｙ２，．．．，ｙｍ）の成分の各々を、正負に応じて０又は１に変換し（ステップＳ１５）、ｍ桁のビット列を生成する。
【００５３】
第１変換部１０７は、生成されたｍ桁のビット列を、第１バイナリデータ１０９に格納する（ステップＳ１７）。そして処理を終了する。
【００５４】
図９に、第１バイナリデータ格納部１０９に格納されているデータの一例を示す。図９の例では、ｍ桁のビット列が格納されている。
【００５５】
以上のような処理を実行すれば、入力された生体データからｍ桁のビット列を生成することができる。
【００５６】
次に、図１０乃至図１３を用いて、検索対象データ格納部１１１に格納されている特徴ベクトルのデータをバイナリ化する処理について説明する。
【００５７】
まず、第２持ち上げ部１１３は、検索対象データ格納部１１１から未処理のｎ次元特徴ベクトルを１つ特定する（図１０：ステップＳ２１）。
【００５８】
第２持ち上げ部１１３は、ステップＳ２３において特定されたｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を追加することにより、（ｎ＋ｐ）次元特徴ベクトルを生成する（ステップＳ２３）。生成される（ｎ＋ｐ）次元特徴ベクトルは、第１成分から第ｎ成分までは元のｎ次元特徴ベクトルと同じであり、第（ｎ＋１）成分から第（ｎ＋ｐ）成分までが新たに追加された成分である。第（ｎ＋１）成分から第（ｎ＋ｐ）成分までには、任意の値を設定することができる。
【００５９】
第２持ち上げ部１１３は、生成された（ｎ＋ｐ）次元特徴ベクトルのデータと当該（ｎ＋ｐ）次元特徴ベクトルのデータＩＤとを第２データ格納部１１５に格納する（ステップＳ２５）。
【００６０】
第２持ち上げ部１１３は、未処理のｎ次元特徴ベクトルが検索対象データ格納部１１１に有るか判断する（ステップＳ２７）。未処理のｎ次元特徴ベクトルが有る場合（ステップＳ２７：Ｙｅｓルート）、次のｎ次元特徴ベクトルについて処理するため、ステップＳ２１の処理に戻る。一方、未処理のｎ次元特徴ベクトルが無い場合（ステップＳ２７：Ｎｏルート）、処理を終了する。
【００６１】
図１１に、第２データ格納部１１５に格納されているデータの一例を示す。図１１の例では、データＩＤと、（ｎ＋ｐ）次元特徴ベクトルの各成分の値とが格納されている。
【００６２】
以上のような処理を実行すれば、予め登録された生体データから抽出された特徴量を成分とするｎ次元の特徴ベクトルから、次元の持ち上げによって、（ｎ＋ｐ）次元の特徴ベクトルを生成できる。
【００６３】
そして、第２データ格納部１１５に（ｎ＋ｐ）次元特徴ベクトルのデータが格納されると、第２変換部１１７は以下のような処理を実行する。第２変換部１１７が実行する処理については、図１２及び図１３を用いて説明する。
【００６４】
まず、第２変換部１１７は、第２データ格納部１１５から未処理の（ｎ＋ｐ）次元特徴ベクトルのデータを１つ分読み出す（図１２：ステップＳ３１）。
【００６５】
第２変換部１１７は、規則データ格納部１３３から変換規則Ｗのデータを読み出す（ステップＳ３２）。変換規則Ｗは、ｍ行（ｎ＋ｐ）列の行列である。変換規則Ｗについては後で詳細に説明する。
【００６６】
第２変換部１１７は、変換規則Ｗと（ｎ＋ｐ）次元特徴ベクトルとの積演算を実行し、実行結果をメインメモリ等の記憶装置に格納する（ステップＳ３３）。ステップＳ３３において実行する行列の積演算は、ステップＳ１３において説明したとおりである。
【００６７】
第２変換部１１７は、ステップＳ３３の処理によって得られた列ベクトルの成分の各々を、正負に応じて０又は１に変換し（ステップＳ３４）、ｍ桁のビット列を生成する。
【００６８】
第２変換部１１７は、生成されたｍ桁のビット列と当該ビット列のデータＩＤとを第２バイナリデータ格納部１１９に格納する（ステップＳ３５）。
【００６９】
第２変換部１１７は、未処理の（ｎ＋ｐ）次元特徴ベクトルが第２データ格納部１１５に有るか判断する（ステップＳ３６）。未処理の（ｎ＋ｐ）次元特徴ベクトルが有る場合（ステップＳ３６：Ｙｅｓルート）、次の（ｎ＋ｐ）次元特徴ベクトルについて処理するため、ステップＳ３１の処理に戻る。一方、未処理の（ｎ＋ｐ）次元特徴ベクトルが無い場合（ステップＳ３６：Ｎｏルート）、処理を終了する。
【００７０】
図１３に、第２バイナリデータ格納部１１９に格納されているデータの一例を示す。図１３の例では、データＩＤと、ｍ桁のビット列とが格納されている。
【００７１】
以上のような処理を実行すれば、予め登録されているｎ次元特徴ベクトルの各々からｍ桁のビット列を生成することができる。
【００７２】
次に、図１４乃至図１７を用いて、変換規則Ｗを生成する処理について説明する。まず、変換規則Ｗの初期値を設定する処理について説明する。
【００７３】
初期化部１２３は、設定処理を実行する（図１４：ステップＳ４１）。設定処理については、図１５を用いて説明する。
【００７４】
初期化部１２３は、図示しないデータ格納部等に登録されている複数の（ｎ＋ｐ）次元分布から、最小値を−１とし、且つ最大値を１とする一様分布を特定する（図１５：ステップＳ５１）。なお、本実施の形態において考える分布は、特に断りが無い限り正規化されているものとする。
【００７５】
初期化部１２３は、変換規則Ｗの各成分ｗｉｊ（ｉは１≦ｉ≦ｍを満たす自然数。ｊは１≦ｊ≦（ｎ＋ｐ）を満たす自然数。）の値を、特定された分布から（例えばランダムに）抽出した値に設定する（ステップＳ５３）。抽出方法については、第９の実施の形態乃至第１２の実施の形態において詳細に説明する。そして元の処理に戻る。
【００７６】
図１４の説明に戻り、初期化部１２３は、変換規則Ｗにおける各行の（ｎ＋ｐ）次元行ベクトルが単位ベクトルになるように正規化を実行する（ステップＳ４３）。初期化部１２３は、変換規則Ｗの各成分の初期値を初期値格納部１２５に格納する。そして処理を終了する。
【００７７】
図１６に、初期値格納部１２５に格納されているデータの一例を示す。図１６の例では、行列の各成分の値が格納されている。行列の各成分の値は、例えば浮動小数点数である。行列は、ｍ行（ｎ＋ｐ）列の行列である。
【００７８】
以上のような処理を実行すれば、変換規則Ｗの各成分に適切な初期値を設定することができる。なお、ステップＳ４３の処理を実行しなくてもよい。
【００７９】
一方、第３持ち上げ部１２７は、学習データ格納部１２１に格納されている学習データに対し、第２持ち上げ部１１３と同様の処理を実行することにより、（ｎ＋ｐ）次元特徴ベクトルのデータを第３データ格納部１２９に格納する。
【００８０】
そして、変換規則生成部１３１は、初期値格納部１２５に格納されているデータ及び第３データ格納部１２９に格納されているデータを用いて、変換規則Ｗを生成する。変換規則Ｗを生成する処理については、図１７を用いて説明する。
【００８１】
まず、変換規則生成部１３１は、変換規則Ｗの初期値を初期値格納部１２５から読み出し、また、第３データ格納部１２９に格納されている（ｎ＋ｐ）次元特徴ベクトルのデータを読み出す（図１７：ステップＳ６１）。
【００８２】
変換規則生成部１３１は、ステップＳ６１において読み出したデータ及び所定のアルゴリズムを用いて、変換規則Ｗを生成する（ステップＳ６３）。所定のアルゴリズムとは、例えば上で示した非特許文献１乃至３に記載されている、超平面が原点を通るものとして計算を実行するアルゴリズムである。生成された変換規則Ｗは、ｍ行（ｎ＋ｐ）列の行列であり、また、ｍ個の超平面の法線ベクトルを行ベクトルとする行列である。
【００８３】
変換規則生成部１３１は、変換規則Ｗのデータを規則データ格納部１３３に格納する（ステップＳ６５）。そして処理を終了する。規則データ格納部１３３に格納されているデータのフォーマットは、初期値格納部１２５に格納されているデータのフォーマットと同様である。
【００８４】
以上のような処理を実行すれば、（ｎ＋ｐ）次元の特徴ベクトルをｍ桁のビット列に変換する変換規則Ｗを生成することができる。
【００８５】
次に、図１８及び図１９を用いて、検索部１３５が実行する処理について説明する。
【００８６】
まず、検索部１３５は、クエリのビット列（すなわち、第１バイナリデータ格納部１０９に格納されているビット列）を読み出す（図１８：ステップＳ７１）。
【００８７】
検索部１３５は、第２バイナリデータ格納部１１９に格納されている検索対象のビット列のうち未処理のビット列を１つ特定する（ステップＳ７３）。
【００８８】
検索部１３５は、クエリのビット列とステップＳ７３において特定されたビット列とのハミング距離を算出し、メインメモリ等の記憶装置に格納する（ステップＳ７５）。
【００８９】
検索部１３５は、データＩＤ及びステップＳ７３において特定されたビット列とハミング距離とを対応付けて検索結果格納部１３７に格納する（ステップＳ７７）。
【００９０】
検索部１３５は、未処理のビット列が第２バイナリデータ格納部１１９に有るか判断する（ステップＳ７９）。未処理のビット列が有る場合（ステップＳ７９：Ｙｅｓルート）、次のビット列について処理するため、ステップＳ７３の処理に戻る。
【００９１】
一方、未処理のビット列が無い場合（ステップＳ７９：Ｎｏルート）、検索部１３５は、ハミング距離が昇順になるように検索結果格納部１３７におけるデータＩＤ及びビット列を並び替える（ステップＳ８１）。
【００９２】
図１９に、ステップＳ８１の処理の後に検索結果格納部１３７に格納されているデータの一例を示す。図１９の例では、データＩＤと、ビット列と、ハミング距離とが格納されている。
【００９３】
検索部１３５は、ハミング距離が所定の閾値以下であるビット列のデータＩＤを特定する（ステップＳ８３）。ステップＳ８３においては、ハミング距離が上位所定数又は上位所定割合であるビット列のデータＩＤを特定するようにしてもよい。
【００９４】
検索部１３５は、マッチング処理を実行し（ステップＳ８５）、処理結果をメインメモリ等の記憶装置に格納する。マッチング処理とは、ステップＳ８３において特定されたデータＩＤに対応するｎ次元特徴ベクトルとクエリデータ格納部１０１に格納されているｎ次元特徴ベクトルとを厳密に比較することにより、一致するｎ次元特徴ベクトルを探索する処理である。そして、検索部１３５は、マッチング処理の結果を出力部１３９に出力させる。そして処理を終了する。
【００９５】
以上のような処理を実行すれば、超平面がオフセットを有するものとして計算を実行するアルゴリズムを利用しなくても、超平面が原点を通るものとして計算を実行した場合と同程度に認証精度を向上させることができるようになる。よって、新たにアルゴリズムを開発せずに済み、また計算量の増加を抑制することができるようになる。
【００９６】
図２０に、ビット数と再現率との関係を示す。図２０において、横軸はビット数を表し、縦軸は検索の再現率を表している。「Ｅｕｃ」は、特徴ベクトル間のユークリッド距離に基づき検索を実行した場合を示している。そのため、ビット数に関係なく再現率は一定である。「ＬＳＨ」は、単純にローカリティセンシティブハッシングを利用して検索を実行した場合を示している。「ＬＳＨ＿ＬＩＦＴ」は、本実施の形態の方法を利用して検索を実行した場合を示している。このグラフが示すように、本実施の形態の方法を利用すると、特にビット数が約１００以上である場合には、単純にローカリティセンシティブハッシングを利用するよりも再現率が向上している。
【００９７】
図２１に、ビット数と適合率との関係を示す。図２１において、横軸はビット数を表し、縦軸は検索の適合率を表している。「Ｅｕｃ」は、特徴ベクトル間のユークリッド距離に基づき検索を実行した場合を示している。そのため、ビット数に関係なく適合率は一定である。「ＬＳＨ」は、単純にローカリティセンシティブハッシングを利用して検索を実行した場合を示している。「ＬＳＨ＿ＬＩＦＴ」は、本実施の形態の方法を利用して検索を実行した場合を示している。再現率と同様に、本実施の形態の方法を利用すると、特にビット数が約１００以上である場合には、単純にローカリティセンシティブハッシングを利用するよりも適合率が向上している。
【００９８】
［実施の形態２］
第２の実施の形態においては、設定処理の他の例について説明する。
【００９９】
図２２を用いて、第２の実施の形態における設定処理の処理フローを示す。まず、初期化部１２３は、図示しないデータ格納部等に登録されている複数の（ｎ＋ｐ）次元分布から、標準正規分布を特定する（図２２：ステップＳ９１）。
【０１００】
初期化部１２３は、変換規則Ｗの各成分ｗｉｊ（ｉは１≦ｉ≦ｍを満たす自然数。ｊは１≦ｊ≦（ｎ＋ｐ）を満たす自然数。）の値を、特定された分布から（例えばランダムに）抽出した値に設定する（ステップＳ９３）。抽出方法については、第９の実施の形態乃至第１２の実施の形態において詳細に説明する。そして元の処理に戻る。
【０１０１】
以上のような処理であっても、変換規則Ｗの初期値を適切な値に設定することができるようになる。
【０１０２】
［実施の形態３］
第３の実施の形態においては、設定処理の他の例について説明する。
【０１０３】
図２３を用いて、第３の実施の形態における設定処理の処理フローを示す。まず、初期化部１２３は、学習データに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を追加したデータに対し主成分分析を実行し、各主成分の標準偏差σｊ（ｉは１≦ｊ≦（ｎ＋ｐ）を満たす自然数）を算出する（図２３：ステップＳ１０１）。第（ｎ＋１）成分から第（ｎ＋ｐ）成分に追加する値は、任意の値でよい。
【０１０４】
初期化部１２３は、変換規則Ｗの各成分ｗｉｊ（ｉは１≦ｉ≦ｍを満たす自然数）の値を、最小値を−σｊとし、且つ最大値をσｊとする（ｎ＋ｐ）次元の一様分布から（例えばランダムに）抽出した値に設定する（ステップＳ１０３）。抽出方法については、第９の実施の形態乃至第１２の実施の形態において詳細に説明する。そして元の処理に戻る。
【０１０５】
以上のような処理であっても、変換規則Ｗの初期値を適切な値に設定することができるようになる。
【０１０６】
［実施の形態４］
第４の実施の形態においては、設定処理の他の例について説明する。
【０１０７】
図２４を用いて、第４の実施の形態における設定処理の処理フローを示す。まず、初期化部１２３は、学習データに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を追加したデータに対し主成分分析を実行し、各主成分の標準偏差σｊ（ｉは１≦ｊ≦（ｎ＋ｐ）を満たす自然数）を算出する（図２４：ステップＳ１１１）。第（ｎ＋１）成分から第（ｎ＋ｐ）成分に追加する値は、任意の値でよい。
【０１０８】
初期化部１２３は、変換規則Ｗの各成分ｗｉｊ（ｉは１≦ｉ≦ｍを満たす自然数）の値を、平均値を０とし、且つ標準偏差値をσｊとする（ｎ＋ｐ）次元の正規分布から（例えばランダムに）抽出した値に設定する（ステップＳ１１３）。抽出方法については、第９の実施の形態乃至第１２の実施の形態において詳細に説明する。そして元の処理に戻る。
【０１０９】
以上のような処理であっても、変換規則Ｗの初期値を適切な値に設定することができるようになる。
【０１１０】
［実施の形態５］
第５の実施の形態においては、設定処理の他の例について説明する。
【０１１１】
図２５を用いて、第５の実施の形態における設定処理の処理フローを示す。まず、初期化部１２３は、図示しないデータ格納部等に登録されている複数の（ｎ＋ｐ）次元分布｛μλ｝λ∈Λの各々について、学習データに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を追加したデータに対する赤池情報量基準を算出する（図２５：ステップＳ１２１）。Λは集合を表し、λは集合Λの元である。第（ｎ＋１）成分から第（ｎ＋ｐ）成分に追加する値は、任意の値でよい。
【０１１２】
初期化部１２３は、複数の（ｎ＋ｐ）次元分布｛μλ｝λ∈Λの中から、赤池情報量基準が最小となるμλを特定する（ステップＳ１２３）。
【０１１３】
初期化部１２３は、変換規則Ｗの各成分ｗｉｊ（ｉは１≦ｉ≦ｍを満たす自然数。ｊは１≦ｊ≦（ｎ＋ｐ）を満たす自然数。）の値を、ステップＳ１２３において特定されたμλから（例えばランダムに）抽出した値に設定する（ステップＳ１２５）。抽出方法については、第９の実施の形態乃至第１２の実施の形態において詳細に説明する。そして元の処理に戻る。
【０１１４】
以上のような処理であっても、変換規則Ｗの初期値を適切な値に設定することができるようになる。
【０１１５】
［実施の形態６］
第６の実施の形態においては、設定処理の他の例について説明する。
【０１１６】
図２６を用いて、第６の実施の形態における設定処理の処理フローを示す。まず、初期化部１２３は、図示しないデータ格納部等に登録されている複数の（ｎ＋ｐ）次元分布｛μλ｝λ∈Λの各々について、学習データに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を追加したデータに対するベイズ情報量基準を算出する（図２６：ステップＳ１３１）。第（ｎ＋１）成分から第（ｎ＋ｐ）成分に追加する値は、任意の値でよい。
【０１１７】
初期化部１２３は、複数の（ｎ＋ｐ）次元分布｛μλ｝λ∈Λの中から、ベイズ情報量基準が最小となるμλを特定する（ステップＳ１３３）。
【０１１８】
初期化部１２３は、変換規則Ｗの各成分ｗｉｊ（ｉは１≦ｉ≦ｍを満たす自然数。ｊは１≦ｊ≦（ｎ＋ｐ）を満たす自然数。）の値を、ステップＳ１３３において特定されたμλから（例えばランダムに）抽出した値に設定する（ステップＳ１３５）。抽出方法については、第９の実施の形態乃至第１２の実施の形態において詳細に説明する。そして元の処理に戻る。
【０１１９】
以上のような処理であっても、変換規則Ｗの初期値を適切な値に設定することができるようになる。
【０１２０】
［実施の形態７］
第７の実施の形態においては、設定処理の他の例について説明する。
【０１２１】
図２７を用いて、第７の実施の形態における設定処理の処理フローを示す。まず、初期化部１２３は、図示しないデータ格納部等に登録されている複数の（ｎ＋ｐ）次元分布｛μλ｝λ∈Λの各々について、学習データに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を追加したデータの度数分布から求めた分布に対するカルバックライブラー情報量を算出する（図２７：ステップＳ１４１）。ここで、「度数分布から求めた分布」とは、各範囲の度数の積分が１になるように正規化した分布のことである。第（ｎ＋１）成分から第（ｎ＋ｐ）成分に追加する値は、任意の値でよい。
【０１２２】
初期化部１２３は、複数の（ｎ＋ｐ）次元分布｛μλ｝λ∈Λの中から、カルバックライブラー情報量が最少となるμλを特定する（ステップＳ１４３）。
【０１２３】
初期化部１２３は、変換規則Ｗの各成分ｗｉｊ（ｉは１≦ｉ≦ｍを満たす自然数。ｊは１≦ｊ≦（ｎ＋ｐ）を満たす自然数。）の値を、ステップＳ１４３において特定されたμλから（例えばランダムに）抽出した値に設定する（ステップＳ１４５）。抽出方法については、第９の実施の形態乃至第１２の実施の形態において詳細に説明する。そして元の処理に戻る。
【０１２４】
以上のような処理であっても、変換規則Ｗの初期値を適切な値に設定することができるようになる。
【０１２５】
［実施の形態８］
第８の実施の形態においては、設定処理の他の例について説明する。
【０１２６】
図２８に、第８の実施の形態における設定処理の処理フローを示す。まず、初期化部１２３は、図示しないデータ格納部等に登録されている複数の（ｎ＋ｐ）次元分布｛μλ｝λ∈Λの各々について、学習データに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を追加したデータの度数分布から求めた分布に対するジェンセンシャノン情報量を算出する（図２８：ステップＳ１５１）。ここで、「度数分布から求めた分布」とは、各範囲の度数の積分が１になるように正規化した分布のことである。第（ｎ＋１）成分から第（ｎ＋ｐ）成分に追加する値は、任意の値でよい。
【０１２７】
初期化部１２３は、複数の（ｎ＋ｐ）次元分布｛μλ｝λ∈Λの中から、ジェンセンシャノン情報量が最少となるμλを特定する（ステップＳ１５３）。
【０１２８】
初期化部１２３は、変換規則Ｗの各成分ｗｉｊ（ｉは１≦ｉ≦ｍを満たす自然数。ｊは１≦ｊ≦（ｎ＋ｐ）を満たす自然数。）の値を、ステップＳ１５３において特定されたμλから（例えばランダムに）抽出した値に設定する（ステップＳ１５５）。抽出方法については、第９の実施の形態乃至第１２の実施の形態において詳細に説明する。そして元の処理に戻る。
【０１２９】
以上のような処理であっても、変換規則Ｗの初期値を適切な値に設定することができるようになる。
【０１３０】
［実施の形態９］
設定処理において（ｎ＋ｐ）次元分布から値を抽出する場合には、ランダムサンプリングによりｍ点を抽出し、抽出されたｍ点の各成分の値を変換規則Ｗの各成分に設定してもよい。このようにすれば、偏り無く値を設定できるようになる。
【０１３１】
［実施の形態１０］
設定処理において（ｎ＋ｐ）次元分布から値を抽出する場合には、以下のようにしてもよい。まず、（ｎ＋ｐ）次元分布から（ｎ＋ｐ）個の周辺分布を算出し、（ｎ＋ｐ）個の周辺分布の各々から所定のパーセンタイルを求める。そして、求めたパーセンタイルの直積によって点を決定し、その点の各成分の値を変換規則の各成分に設定する。これをｍ回繰り返す。このような方法であっても、妥当な値を設定できるようになる。
【０１３２】
［実施の形態１１］
設定処理において（ｎ＋ｐ）次元分布（以下、μとする）から値を抽出する場合には、（ｎ＋ｐ）次元分布（１−μ）からランダムサンプリングによりｍ点を抽出し、抽出されたｍ点の各成分の値を変換規則Ｗの各成分に設定してもよい。このような方法であっても、偏り無く値を抽出できるようになる。
【０１３３】
［実施の形態１２］
設定処理において（ｎ＋ｐ）次元分布から値を抽出する場合には、以下のようにしてもよい。まず、（ｎ＋ｐ）次元分布から（ｎ＋ｐ）個の周辺分布μｉ（ｉは１≦ｉ≦（ｎ＋ｐ）を満たす自然数）を算出し、（１−μｉ）の各々から所定のパーセンタイルを求める。そして、求めたパーセンタイルの直積によって点を決定し、その点の各成分の値を変換規則の各成分に設定する。これをｍ回繰り返す。このような方法であっても、妥当な値を設定できるようになる。
【０１３４】
以上本発明の一実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、上で説明した認証装置１の機能ブロック構成は実際のプログラムモジュール構成に対応しない場合もある。
【０１３５】
また、上で説明した各テーブルの構成は一例であって、上記のような構成でなければならないわけではない。さらに、処理フローにおいても、処理結果が変わらなければ処理の順番を入れ替えることも可能である。さらに、並列に実行させるようにしても良い。
【０１３６】
なお、上で述べた認証装置１は、コンピュータ装置であって、図２９に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本発明の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１３７】
以上述べた本発明の実施の形態をまとめると、以下のようになる。
【０１３８】
本実施の形態に係る認証方法は、（Ａ）（ｎ＋ｐ）次元空間（ｎ及びｐは自然数）の原点を通る１又は複数の超平面の法線ベクトルを算出し、（Ｂ）第１のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより第１の（ｎ＋ｐ）次元特徴ベクトルを生成し、当該第１の（ｎ＋ｐ）次元特徴ベクトルを、１又は複数の超平面の法線ベクトルを用いて第１のビット列に変換し、（Ｃ）データ格納部に格納されている検索対象のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより検索対象の（ｎ＋ｐ）次元特徴ベクトルを生成し、当該検索対象の（ｎ＋ｐ）次元特徴ベクトルを、１又は複数の超平面の法線ベクトルを用いて第２のビット列に変換し、（Ｄ）第１のビット列と第２のビット列との距離を算出する処理を含む。
【０１３９】
このようにすれば、超平面がオフセットを有するものとして計算を実行するアルゴリズムを利用しなくても、超平面が原点を通るものとして計算を実行した場合と同程度に認証精度を向上させることができるようになる。
【０１４０】
また、上で述べた第１のビット列に変換する処理及び第２のビット列に変換する処理において、（ｂ１，ｃ１）第１の（ｎ＋ｐ）次元特徴ベクトル及び検索対象の（ｎ＋ｐ）次元特徴ベクトルの第（ｎ＋１）成分から第（ｎ＋ｐ）成分の値は、任意の値であってもよい。上で述べた認証方法は、値の大きさ等に関係なく、認証精度を向上させることができる。
【０１４１】
また、（Ｅ）第１のビット列と第２のビット列との距離が所定の閾値以下である場合に、第１のｎ次元特徴ベクトルと第２のビット列に対応する特徴ベクトルとが一致するか判断してもよい。このようにすれば、比較対象の特徴ベクトルを絞り込んだ上で特徴ベクトルが一致するか否かを厳密に判断できるので、計算量を削減できるようになる。
【０１４２】
また、上で述べた第１のビット列に変換する処理において、（ｂ２）１又は複数の超平面の法線ベクトルと生成された第１の（ｎ＋ｐ）次元特徴ベクトルとの内積を算出し、当該内積により得られるベクトルの各成分の値が正か否かに基づき当該第１の（ｎ＋ｐ）次元特徴ベクトルをビット列に変換し、上で述べた第２のビット列に変換する処理において、（ｃ２）１又は複数の超平面の法線ベクトルと生成された検索対象の（ｎ＋ｐ）次元特徴ベクトルとの内積を算出し、当該内積により得られるベクトルの各成分の値が正か否かに基づき当該検索対象の（ｎ＋ｐ）次元特徴ベクトルをビット列に変換してもよい。内積を利用すれば、特徴ベクトルが表す点と超平面との位置関係がわかるので、位置関係に応じて０又は１を割り当てることができる。よって、上で述べたように、特徴ベクトルをビット列に変換できるようになる。
【０１４３】
また、上で述べた法線ベクトルを算出する処理において、（ａ１）（ｎ＋ｐ）次元の初期ベクトルを生成し、（ａ２）超平面が原点を通るものとして計算を実行するアルゴリズムを用いて、初期ベクトルから法線ベクトルを算出してもよい。このようにすれば、従来のアルゴリズムを利用して超平面の法線ベクトルを算出できるようになる。
【０１４４】
また、上で述べた法線ベクトルを算出する処理において、（ａ３）（ｎ＋ｐ）次元の初期ベクトルを生成し、（ａ４）初期ベクトルが単位ベクトルになるように正規化を実行し、（ａ５）超平面が原点を通るものとして計算を実行するアルゴリズムを用いて、正規化を実行後の初期ベクトルから法線ベクトルを算出してもよい。正規化を実行すれば、最終的に算出される法線ベクトルの成分の値はより適切になる。
【０１４５】
また、上で述べた初期ベクトルを生成する処理において、（ａ１１）初期ベクトルの各成分の値を、最小値を−１とし、最大値を１とする一様分布から抽出した値に設定してもよい。このようにすれば、初期ベクトルの各成分の値が適切に設定されるようになる。
【０１４６】
また、上で述べた初期ベクトルを生成する処理において、（ａ１２）初期ベクトルの各成分の値を、標準正規分布から抽出した値に設定してもよい。このようにすれば、初期ベクトルの各成分の値が適切に設定されるようになる。
【０１４７】
また、上で述べた初期ベクトルを生成する処理において、（ａ１３−１）データ格納部に格納されている特徴ベクトルに対し主成分分析を実行することにより、主成分の標準偏差σを取得し、（ａ１３−２）初期ベクトルの各成分の値を、最小値を−σとし、最大値をσとする一様分布から所定の方法で抽出した値に設定してもよい。このようにすれば、初期ベクトルの各成分の値が適切に設定されるようになる。
【０１４８】
また、上で述べた初期ベクトルを生成する処理において、（ａ１４−１）データ格納部に格納されている特徴ベクトルに対し主成分分析を実行することにより、主成分の標準偏差σを取得し、（ａ１４−２）初期ベクトルの各成分の値を、平均値を０とし、標準偏差をσとする正規分布から所定の方法で抽出した値に設定してもよい。このようにすれば、初期ベクトルの各成分の値が適切に設定されるようになる。
【０１４９】
また、上で述べた初期ベクトルを生成する処理において、（ａ１５−１）複数の分布の各々について、データ格納部に格納されている特徴ベクトルに対する赤池情報量基準を算出し、（ａ１５−２）算出された赤池情報量基準が最小である分布を特定し、（ａ１５−３）初期ベクトルの各成分の値を、特定された分布から所定の方法で抽出した値に設定してもよい。このようにすれば、初期ベクトルの各成分の値が適切に設定されるようになる。
【０１５０】
また、上で述べた初期ベクトルを生成する処理において、（ａ１６−１）複数の分布の各々について、データ格納部に格納されている特徴ベクトルから求めた度数分布に対するベイズ情報量基準を算出し、（ａ１６−２）算出されたベイズ情報量基準が最小である分布を特定し、（ａ１６−３）初期ベクトルの各成分の値を、特定された分布から所定の方法で抽出した値に設定してもよい。このようにすれば、初期ベクトルの各成分の値が適切に設定されるようになる。
【０１５１】
また、上で述べた初期ベクトルを生成する処理において、（ａ１７−１）複数の分布の各々について、データ格納部に格納されている特徴ベクトルから求めた度数分布に対するカルバックライブラー情報量を算出し、（ａ１７−２）算出されたカルバックライブラー情報量が最少である分布を特定し、（ａ１７−３）初期ベクトルの各成分の値を、特定された分布から所定の方法で抽出した値に設定してもよい。このようにすれば、初期ベクトルの各成分の値が適切に設定されるようになる。
【０１５２】
また、上で述べた初期ベクトルを生成する処理において、（ａ１８−１）複数の分布の各々について、データ格納部に格納されている特徴ベクトルから求めた度数分布に対するジェンセンシャノン情報量を算出し、（ａ１８−２）算出されたジェンセンシャノン情報量が最少である分布を特定し、（ａ１８−３）初期ベクトルの各成分の値を、特定された分布から所定の方法で抽出した値に設定してもよい。このようにすれば、初期ベクトルの各成分の値が適切に設定されるようになる。
【０１５３】
また、上で述べた所定の方法が、特定された分布からランダムに値を抽出する方法であってもよい。このようにすれば、偏り無く値を抽出できるようになる。
【０１５４】
また、上で述べた所定の方法が、特定された分布から（ｎ＋ｐ）個の周辺分布を求め、当該（ｎ＋ｐ）個の周辺分布の各々から所定のパーセンタイルを特定し、特定された（ｎ＋ｐ）個のパーセンタイルの直積により値を抽出する方法であってもよい。このような方法であっても、妥当な値を抽出できるようになる。
【０１５５】
また、上で述べた所定の方法が、特定された分布μから分布（１−μ）を求め、当該分布（１−μ）からランダムに値を抽出する方法であってもよい。このような方法であっても、偏り無く値を抽出できるようになる。
【０１５６】
また、上で述べた所定の方法が、特定された分布から（ｎ＋ｐ）個の周辺分布μｉ（ｉは１≦ｉ≦（ｎ＋ｐ）を満たす自然数）を求め、（ｎ＋ｐ）個の（１−μｉ）から所定のパーセンタイルを特定し、特定された（ｎ＋ｐ）個のパーセンタイルの直積により値を抽出する方法であってもよい。このような方法であっても、妥当な値を抽出できるようになる。
【０１５７】
また、上で述べた第１のｎ次元特徴ベクトル及び検索対象のｎ次元特徴ベクトルは、生体データから抽出された特徴量を成分とする特徴ベクトルであってもよい。但し、生体データに限られるわけではなく、他のデータから抽出された特徴量であってもよい。
【０１５８】
また、上で述べた距離はハミング距離であってもよい。これにより、ビット列間の距離を容易に算出できるようになる。
【０１５９】
また、上で述べたｐの値は１であってもよい。ｐ＝１であれば、計算量が少なくて済む。
【０１６０】
なお、上記方法による処理をコンピュータに行わせるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。尚、中間的な処理結果はメインメモリ等の記憶装置に一時保管される。
【０１６１】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１６２】
（付記１）
ビット列間の距離に基づき認証を行うコンピュータに、
（ｎ＋ｐ）次元空間（ｎ及びｐは自然数）の原点を通る１又は複数の超平面の法線ベクトルを算出し、
第１のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより第１の（ｎ＋ｐ）次元特徴ベクトルを生成し、当該第１の（ｎ＋ｐ）次元特徴ベクトルを、前記１又は複数の超平面の法線ベクトルを用いて第１のビット列に変換し、
データ格納部に格納されている検索対象のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより検索対象の（ｎ＋ｐ）次元特徴ベクトルを生成し、当該検索対象の（ｎ＋ｐ）次元特徴ベクトルを、前記１又は複数の超平面の法線ベクトルを用いて第２のビット列に変換し、
前記第１のビット列と前記第２のビット列との距離を算出する
処理を実行させるための認証プログラム。
【０１６３】
（付記２）
前記第１のビット列に変換する処理及び前記第２のビット列に変換する処理において、
前記第１の（ｎ＋ｐ）次元特徴ベクトル及び前記検索対象の（ｎ＋ｐ）次元特徴ベクトルの第（ｎ＋１）成分から第（ｎ＋ｐ）成分の値は、任意の値である
ことを特徴とする付記１記載の認証プログラム。
【０１６４】
（付記３）
前記第１のビット列と前記第２のビット列との距離が所定の閾値以下である場合に、前記第１のｎ次元特徴ベクトルと前記第２のビット列に対応する特徴ベクトルとが一致するか判断する
処理をさらに実行させるための付記１又は２記載の認証プログラム。
【０１６５】
（付記４）
前記第１のビット列に変換する処理において、
前記１又は複数の超平面の法線ベクトルと生成された前記第１の（ｎ＋ｐ）次元特徴ベクトルとの内積を算出し、当該内積により得られるベクトルの各成分の値が正か否かに基づき当該第１の（ｎ＋ｐ）次元特徴ベクトルをビット列に変換し、
前記第２のビット列に変換する処理において、
前記１又は複数の超平面の法線ベクトルと生成された前記検索対象の（ｎ＋ｐ）次元特徴ベクトルとの内積を算出し、当該内積により得られるベクトルの各成分の値が正か否かに基づき当該検索対象の（ｎ＋ｐ）次元特徴ベクトルをビット列に変換する
ことを特徴とする付記１乃至３のいずれか１つ記載の認証プログラム。
【０１６６】
（付記５）
前記法線ベクトルを算出する処理において、
（ｎ＋ｐ）次元の初期ベクトルを生成し、
前記超平面が原点を通るものとして計算を実行するアルゴリズムを用いて、前記初期ベクトルから前記法線ベクトルを算出する
ことを特徴とする付記１乃至４のいずれか１つ記載の認証プログラム。
【０１６７】
（付記６）
前記法線ベクトルを算出する処理において、
（ｎ＋ｐ）次元の初期ベクトルを生成し、
前記初期ベクトルが単位ベクトルになるように正規化を実行し、
前記超平面が原点を通るものとして計算を実行するアルゴリズムを用いて、前記正規化を実行後の初期ベクトルから前記法線ベクトルを算出する
ことを特徴とする付記１乃至４のいずれか１つ記載の認証プログラム。
【０１６８】
（付記７）
前記初期ベクトルを生成する処理において、
前記初期ベクトルの各成分の値を、最小値を−１とし、最大値を１とする一様分布から抽出した値に設定する
ことを特徴とする付記５又は６記載の認証プログラム。
【０１６９】
（付記８）
前記初期ベクトルを生成する処理において、
前記初期ベクトルの各成分の値を、標準正規分布から抽出した値に設定する
ことを特徴とする付記５又は６記載の認証プログラム。
【０１７０】
（付記９）
前記初期ベクトルを生成する処理において、
前記データ格納部に格納されている特徴ベクトルに対し主成分分析を実行することにより、主成分の標準偏差σを取得し、
前記初期ベクトルの各成分の値を、最小値を−σとし、最大値をσとする一様分布から所定の方法で抽出した値に設定する
ことを特徴とする付記５又は６記載の認証プログラム。
【０１７１】
（付記１０）
前記初期ベクトルを生成する処理において、
前記データ格納部に格納されている特徴ベクトルに対し主成分分析を実行することにより、主成分の標準偏差σを取得し、
前記初期ベクトルの各成分の値を、平均値を０とし、標準偏差をσとする正規分布から所定の方法で抽出した値に設定する
ことを特徴とする付記５又は６記載の認証プログラム。
【０１７２】
（付記１１）
前記初期ベクトルを生成する処理において、
複数の分布の各々について、前記データ格納部に格納されている特徴ベクトルに対する赤池情報量基準を算出し、
算出された前記赤池情報量基準が最小である分布を特定し、
前記初期ベクトルの各成分の値を、特定された前記分布から所定の方法で抽出した値に設定する
ことを特徴とする付記５又は６記載の認証プログラム。
【０１７３】
（付記１２）
前記初期ベクトルを生成する処理において、
複数の分布の各々について、前記データ格納部に格納されている特徴ベクトルに対するベイズ情報量基準を算出し、
算出された前記ベイズ情報量基準が最小である分布を特定し、
前記初期ベクトルの各成分の値を、特定された前記分布から所定の方法で抽出した値に設定する
ことを特徴とする付記５又は６記載の認証プログラム。
【０１７４】
（付記１３）
前記初期ベクトルを生成する処理において、
複数の分布の各々について、前記データ格納部に格納されている特徴ベクトルから求めた度数分布に対するカルバックライブラー情報量を算出し、
算出された前記カルバックライブラー情報量が最少である分布を特定し、
前記初期ベクトルの各成分の値を、特定された前記分布から所定の方法で抽出した値に設定する
ことを特徴とする付記５又は６記載の認証プログラム。
【０１７５】
（付記１４）
前記初期ベクトルを生成する処理において、
複数の分布の各々について、前記データ格納部に格納されている特徴ベクトルから求めた度数分布に対するジェンセンシャノン情報量を算出し、
算出された前記ジェンセンシャノン情報量が最少である分布を特定し、
前記初期ベクトルの各成分の値を、特定された前記分布から所定の方法で抽出した値に設定する
ことを特徴とする付記５又は６記載の認証プログラム。
【０１７６】
（付記１５）
前記所定の方法が、特定された前記分布からランダムに値を抽出する方法である
ことを特徴とする付記７乃至１４のいずれか１つ記載の認証プログラム。
【０１７７】
（付記１６）
前記所定の方法が、特定された前記分布から（ｎ＋ｐ）個の周辺分布を求め、当該（ｎ＋ｐ）個の周辺分布の各々から所定のパーセンタイルを特定し、特定された（ｎ＋ｐ）個のパーセンタイルの直積により値を抽出する方法である
ことを特徴とする付記７乃至１４のいずれか１つ記載の認証プログラム。
【０１７８】
（付記１７）
前記所定の方法が、特定された前記分布μから分布（１−μ）を求め、当該分布（１−μ）からランダムに値を抽出する方法である
ことを特徴とする付記７乃至１４のいずれか１つ記載の認証プログラム。
【０１７９】
（付記１８）
前記所定の方法が、特定された前記分布から（ｎ＋ｐ）個の周辺分布μｉ（ｉは１≦ｉ≦（ｎ＋ｐ）を満たす自然数）を求め、（ｎ＋ｐ）個の（１−μｉ）から所定のパーセンタイルを特定し、特定された（ｎ＋ｐ）個のパーセンタイルの直積により値を抽出する方法である
ことを特徴とする付記７乃至１４のいずれか１つ記載の認証プログラム。
【０１８０】
（付記１９）
前記第１のｎ次元特徴ベクトル及び前記検索対象のｎ次元特徴ベクトルは、生体データから抽出された特徴量を成分とする特徴ベクトルである
ことを特徴とする付記１乃至１８のいずれか１つ記載の認証プログラム。
【０１８１】
（付記２０）
前記距離はハミング距離である
ことを特徴とする付記１乃至１９のいずれか１つ記載の認証プログラム。
【０１８２】
（付記２１）
前記ｐの値は１である
ことを特徴とする付記１乃至２０のいずれか１つ記載の認証プログラム。
【０１８３】
（付記２２）
ビット列間の距離に基づき認証を行うコンピュータが、
（ｎ＋ｐ）次元空間（ｎ及びｐは自然数）の原点を通る１又は複数の超平面の法線ベクトルを算出し、
第１のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより第１の（ｎ＋ｐ）次元特徴ベクトルを生成し、当該第１の（ｎ＋ｐ）次元特徴ベクトルを、前記１又は複数の超平面の法線ベクトルを用いて第１のビット列に変換し、
データ格納部に格納されている検索対象のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより検索対象の（ｎ＋ｐ）次元特徴ベクトルを生成し、当該検索対象の（ｎ＋ｐ）次元特徴ベクトルを、前記１又は複数の超平面の法線ベクトルを用いて第２のビット列に変換し、
前記第１のビット列と前記第２のビット列との距離を算出する
処理を実行する認証方法。
【０１８４】
（付記２３）
ビット列間の距離に基づき認証を行う認証装置であって、
検索対象のｎ次元特徴ベクトルを格納するデータ格納部と、
（ｎ＋ｐ）次元空間（ｎ及びｐは自然数）の原点を通る１又は複数の超平面の法線ベクトルを算出する算出部と、
第１のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより第１の（ｎ＋ｐ）次元特徴ベクトルを生成する第１生成部と、
前記データ格納部に格納されている検索対象のｎ次元特徴ベクトルに第（ｎ＋１）成分から第（ｎ＋ｐ）成分を加えることにより検索対象の（ｎ＋ｐ）次元特徴ベクトルを生成する第２生成部と、
前記第１の（ｎ＋ｐ）次元特徴ベクトルを、前記１又は複数の超平面の法線ベクトルを用いて第１のビット列に変換する第１変換部と、
前記検索対象の（ｎ＋ｐ）次元特徴ベクトルを、前記１又は複数の超平面の法線ベクトルを用いて第２のビット列に変換する第２変換部と、
前記第１のビット列と前記第２のビット列との距離を算出する算出部と
を有する認証装置。
【符号の説明】
【０１８５】
１  認証装置    １０１  クエリデータ格納部
１０３  第１持ち上げ部    １０５  第１データ格納部
１０７  第１変換部    １０９  第１バイナリデータ格納部
１１１  検索対象データ格納部    １１３  第２持ち上げ部
１１５  第２データ格納部    １１７  第２変換部
１１９  第２バイナリデータ格納部    １２１  学習データ格納部
１２３  初期化部    １２５  初期値格納部
１２７  第３持ち上げ部    １２９  第３データ格納部
１３１  変換規則生成部  １３３  規則データ格納部
１３５  検索部    １３７  検索結果格納部
１３９  出力部
【図１】
2014074964.tif 000009
【図２】
2014074964.tif 000010
【図３】
2014074964.tif 000011
【図４】
2014074964.tif 000012
【図５】
2014074964.tif 000013
【図６】
2014074964.tif 000014
【図７】
2014074964.tif 000015
【図８】
2014074964.tif 000016
【図９】
2014074964.tif 000017
【図１０】
2014074964.tif 000018
【図１１】
2014074964.tif 000019
【図１２】
2014074964.tif 000020
【図１３】
2014074964.tif 000021
【図１４】
2014074964.tif 000022
【図１５】
2014074964.tif 000023
【図１６】
2014074964.tif 000024
【図１７】
2014074964.tif 000025
【図１８】
2014074964.tif 000026
【図１９】
2014074964.tif 000027
【図２０】
2014074964.tif 000028
【図２１】
2014074964.tif 000029
【図２２】
2014074964.tif 000030
【図２３】
2014074964.tif 000031
【図２４】
2014074964.tif 000032
【図２５】
2014074964.tif 000033
【図２６】
2014074964.tif 000034
【図２７】
2014074964.tif 000035
【図２８】
2014074964.tif 000036
【図２９】
2014074964.tif 000037