(57)【要約】  計算量の増大を抑えながら精度の向上を図る、全く新規なハッシュ関数の学習に基づくバイナリデータ変換方法と装置、システムを提供する。ハッシュ関数のパラメータを最適化するパラメータ最適化部を備え、Ｄ次元（Ｄは所定の正整数）空間上のポイントで表される複数のデータの集合を入力し、データポイントの射影ベクトルへの射影に基づき、２値表現に変換するK個（Ｋは所定の正整数）の各ハッシュ関数として最適化されたパラメータのハッシュ関数を用いて、Ｋビット長の複数個の２値化データに変換し、前記パラメータ最適化部は、変数がデータポイントの射影ベクトルへの射影を含む連続値関数のハッシュ関数を用いて、ハッシュ値を求め、連続値バイナリ変換学習データとして記憶し、データポイント間の距離として予め定められた所定の距離パラメータ以内では距離を保存するが、前記距離パラメータを超えると、値が小さくなる距離関数で計算された距離と、前記連続値のバイナリ変換学習データの距離とに基づき規定されるコスト関数を最小化する前記ハッシュ関数のパラメータを、最適化されたパラメータとして導出する。
2014050952.tif 000002
【特許請求の範囲】
【請求項１】
ハッシュ関数のパラメータを最適化するハッシュ関数パラメータ最適化部を備え、
記憶部から予め定められた所定の次元数の空間上のポイントで表される複数のデータの集合を入力し、データポイントの射影ベクトルへの射影に基づき２値表現に変換するＫ個（Ｋは所定の正整数）の各ハッシュ関数として、前記最適化されたパラメータのハッシュ関数を用いて、Ｋビット長の複数個の２値化データに変換し、
前記ハッシュ関数パラメータ最適化部は、
前記ハッシュ関数として、変数が、前記データポイントの射影ベクトルへの射影を含む連続値関数のハッシュ関数を用いて、ハッシュ値を求め、連続値のバイナリ変換学習データとして、記憶部に出力するハッシュ関数演算部を備え、
データポイント間の距離として、予め定められた所定の距離パラメータ以内では距離を保存するが、前記距離パラメータを超えると、値が小さくなる距離関数を用いて計算される距離と、前記連続値のバイナリ変換学習データの距離とに少なくとも基づき規定されるコスト関数を最小化する前記ハッシュ関数のパラメータを、前記ハッシュ関数の前記最適化されたパラメータとして導出する、ことを特徴とするバイナリデータ変換装置。
【請求項２】
前記ハッシュ関数演算部では、ｋ番目（ｋ＝１、・・・K）の前記連続値関数のハッシュ関数として、シグモイド（sigmoid）関数
2014050952.tif 000048
（ただし、β(t)は正値の制御パラメータ（ｔは前記ハッシュ関数パラメータ最適化部でのパラメータ導出の反復回数であり、β(t)は、反復回数が多くなると大となる）、
→ｗｋは射影ベクトル（ｋ＝１、・・・K）、
Ｔは転置、
→ｘはデータポイント（D次元、ただしDは所定の正整数）、
→ｗｋT→ｘは前記データポイントの射影ベクトルへの射影、
αｋはオフセット）
を用い、前記ハッシュ関数のパラメータ→ｗｋとαｋの最適化を行う、ことを特徴とする請求項１記載のバイナリデータ変換装置。
【請求項３】
前記ハッシュ関数パラメータ最適化部が、
前記データポイント間の距離として、予め定められた所定の距離パラメータ以内では距離を保存するが、前記距離パラメータを超えると、値が指数関数的に小さくなる距離関数を用いて距離行列を計算する距離行列計算部と、
前記コスト関数を用いてコスト値を計算するコスト計算部と、
前記コスト計算部で今回求めたコスト値と、前記コスト計算部で前回求めたコスト値とを比較し、予め定められた収束条件を満たしているか否か判定するコスト比較部と、
前記収束条件を満たしている場合には、前記ハッシュ関数のパラメータを最適値として出力するパラメータ出力部と、
前記収束条件を満たしていない場合には、前記ハッシュ関数のパラメータを更新して記憶装置に記憶する更新部と、
備え、
前記収束条件を満たしていない場合、前記ハッシュ関数演算部は、前記更新部で更新された前記ハッシュ関数のパラメータを用いて、前記バイナリ変換学習データを出力し、
前記コスト計算部によるコスト値の計算、
前記コスト比較部による収束判定が行われる、ことを特徴とする請求項１又は２記載のバイナリデータ変換装置。
【請求項４】
前記距離行列計算部は、第ｉ、第ｊのデータポイント間の距離ｄi,j（ただし、ｉ，ｊは１以上、ｎ以下の整数）を、距離関数
2014050952.tif 000049
（ただし、εは前記距離パラメータ）
を用いて求める、ことを特徴とする請求項３記載のバイナリデータ変換装置。
【請求項５】
前記コスト関数は、前記第ｉ、第ｊのデータポイント間の距離ｄi,jと、前記バイナリ変換学習データ→ｙi、→ｙj間の距離｜→ｙi−→ｙj｜を乗算した項のｉ、ｊのデータ数ｎ分の総和
2014050952.tif 000050
を含む、ことを特徴とする請求項４記載のバイナリデータ変換装置。
【請求項６】
前記コスト関数は、さらに項
2014050952.tif 000051
（ただし、λは所定の正数）
を含み、
2014050952.tif 000052
としてなる、ことを特徴とする請求項５記載のバイナリデータ変換装置。
【請求項７】
前記コスト関数の最小値を最急勾配法で求め、前記コスト関数のコスト値が収束条件を満たしていない場合、前記更新部は、前記ハッシュ関数の現在の前記射影ベクトルと、前記オフセットと、前記コスト関数の前記射影ベクトルと前記オフセットによる偏微分パラメータを用いて、前記ハッシュ関数の射影ベクトルとオフセットを更新し、さらに、
前記制御パラメータを更新する、ことを特徴とする請求項３乃至６のいずれか１項に記載のバイナリデータ変換装置。
【請求項８】
登録フェーズにおいて、生体情報から特徴量抽出したデータ集合に対して、請求項１乃至７のいずれか１項に記載のバイナリデータ変換装置から出力されるバイナリデータ（２値化データ）Zに対して、乱数Sを生成し、
前記乱数Sをエンコーダで誤り訂正符号化した符号語Cと前記バイナリデータZの排他的論理和（Z (+) C）、及び、前記乱数Sを入力とするハッシュ関数の出力H（S）を、データベースへ登録する、生体認証システム。
【請求項９】
認証フェーズにおいて、前記バイナリデータ変換装置から出力される認証対象のバイナリデータZ’と、前記データベースから読み出した前記（Z (+) C）との排他的論理和をとった値C’をデコーダに入力して誤り訂正復号し、
前記デコーダの出力S'をハッシュ関数に入力し、
前記ハッシュ関数の出力H(S')と、前記データベースに登録されているH(S)とが等しいか否か判定する、請求項８記載の生体認証システム。
【請求項１０】
登録フェーズにおいて、前記エンコーダは誤り訂正符号として線形符号を用い、
前記ハッシュ関数は準同型性を有する、請求項８記載の生体認証システム。
【請求項１１】
認証フェーズでは、認証を行う毎に第２の乱数S'を生成し、
前記第２の乱数S’を、第２のエンコーダで誤り訂正符号化した符号語C’と、前記バイナリデータ変換装置から出力される認証対象のバイナリデータZ’との排他的論理和（C' (+) Z'）と、前記データベースから読み出した（Z (+) C）との排他的論理和(Z'ｉ (+) Z'ｉ) (+) (Cｉ (+) C'ｉ)）を第２のデコーダに入力して誤り訂正復号し、
前記第２のデコーダからの出力S”をハッシュ関数に入力して求めたハッシュ値H(S”)と、前記第２の乱数S'をハッシュ関数に入力して求めたハッシュ値H(S')との排他的論理和（値H(S') (+) H(S”)）が、前記データベースに登録されたH(S)と等しいか否か判定し、
前記第２のエンコーダ、第２のデコーダは、誤り訂正符号として線形符号を用い、前記ハッシュ関数は準同型性を有する、請求項１０記載の生体認証システム。
【請求項１２】
ハッシュ関数のパラメータを最適化するパラメータ最適化工程と、
記憶部から予め定められた所定の次元数の空間上のポイントで表される複数のデータの集合を入力し、データポイントの射影ベクトルへの射影に基づき、２値表現に変換するＫ個（Ｋは所定の正整数）の各ハッシュ関数として、前記パラメータ最適化工程で最適化されたパラメータのハッシュ関数を用いて、Ｋビット長の複数個の２値化データに変換する工程と、
を含み、
前記パラメータ最適化工程では、
前記ハッシュ関数として、変数が、前記データポイントの射影ベクトルへの射影を含む連続値関数のハッシュ関数を用いて、ハッシュ値を求め、連続値のバイナリ変換学習データとして記憶部に出力し、
データポイント間の距離として、予め定められた所定の距離パラメータ以内では、前記データポイント間の距離を保存した値をとり、前記距離パラメータを超えると、値が小さくなる特性の距離関数を用いて計算される距離と、前記連続値のバイナリ変換学習データの距離と、に少なくとも基づき規定されるコスト関数を最小化する前記ハッシュ関数のパラメータを、前記ハッシュ関数の最適化されたパラメータとして導出する、ことを特徴とするバイナリデータ変換方法。
【請求項１３】
前記連続値関数のハッシュ関数（ｋ番目のハッシュ関数、ｋ＝１、・・・Ｋ）として、シグモイド（sigmoid）関数
2014050952.tif 000053
（ただし、β(t)は正値の制御パラメータ（ｔは前記パラメータ最適化工程でのパラメータ導出の反復回数であり、β(t)は、反復回数が多くなると大となる）、
→ｗｋは射影ベクトル（ｋ＝１、・・・Ｋ）、
Ｔは転置、
→ｘはデータポイント（D次元）、
→ｗｋT→ｘは前記データポイントの射影ベクトルへの射影、
αｋはオフセット）
を用い、前記ハッシュ関数のパラメータ→ｗｋとαｋの最適化を行う、ことを特徴とする請求項１２記載のバイナリデータ変換方法。
【請求項１４】
前記コスト関数の最小化の過程において、
コスト比較部が、今回求めた前記コスト関数のコスト値と、前回求めた前記コスト関数のコスト値とを比較し、予め定められた収束条件を満たしているか否か判定し、
前記収束条件を満たしている場合、パラメータ出力部が、前記ハッシュ関数のパラメータを最適値として出力し、
前記収束条件を満たしていない場合、更新部が、前記ハッシュ関数のパラメータを更新して記憶装置に記憶し、
前記収束条件を満たしていない場合、前記ハッシュ関数演算部は、前記更新部で更新されたハッシュ関数のパラメータにより前記ハッシュ値を求めバイナリデータを出力し、前記コスト計算部によるコスト値の計算、前記コスト比較部による収束判定が行われる、ことを特徴とする請求項１２又は１３記載のバイナリデータ変換方法。
【請求項１５】
前記距離行列計算部は、第ｉ、第ｊのデータポイント間の距離ｄi,j（ただし、ｉ，ｊは１以上、ｎ以下の整数）を、距離関数
2014050952.tif 000054
（ただし、εは前記距離パラメータ）を用いて求める、ことを特徴とする請求項１２乃至１４のいずれか１項に記載のバイナリデータ変換方法。
【請求項１６】
前記コスト関数は、前記第ｉ、第ｊのデータポイント間の距離ｄi,jと、前記バイナリ変換学習データ→ｙi、→ｙj間の距離｜→ｙi−→ｙj｜を乗算した項のｉ、ｊのデータ数ｎ分の総和
2014050952.tif 000055
を含む、ことを特徴とする請求項１５記載のバイナリデータ変換方法。
【請求項１７】
前記コスト関数は、さらに項
2014050952.tif 000056
（ただし、λは所定の正数）
を含み、
2014050952.tif 000057
としてなる、ことを特徴とする請求項１６記載のバイナリデータ変換方法。
【請求項１８】
前記コスト関数の最小値を最急勾配法で求め、前記コスト関数のコスト値が収束条件を満たしていない場合、前記ハッシュ関数の現在の前記射影ベクトルと前記オフセットと、前記コスト関数の前記射影ベクトルと前記オフセットによる偏微分パラメータを用いて、前記ハッシュ関数の射影ベクトルとオフセットを更新し、さらに、
前記制御パラメータを更新する、ことを特徴とする請求項１２乃至１７のいずれか１項に記載のバイナリデータ変換方法。
【請求項１９】
ハッシュ関数のパラメータを最適化するパラメータ最適化処理と、
記憶部から予め定められた所定の次元数の空間上のポイントで表される複数のデータの集合を入力し、データポイントの射影ベクトルへの射影に基づき、２値表現に変換するK個（Ｋは所定の正整数）の各ハッシュ関数として、前記パラメータ最適化処理で最適化されたパラメータのハッシュ関数を用いて、Ｋビット長の複数個の２値化データに変換する処理を、コンピュータに実行させるプログラムであって、
前記パラメータ最適化処理は、
前記ハッシュ関数として、変数が、前記データポイントの射影ベクトルへの射影を含む連続値関数のハッシュ関数を用いてハッシュ値を求め、連続値のバイナリ変換学習データとして、記憶部に出力する処理と、
データポイント間の距離として、予め定められた所定の距離パラメータ以内では距離を保存するが、前記距離パラメータを超えると、値が小さくなる距離関数を用いて計算される距離と、前記連続値のバイナリ変換学習データの距離とに少なくとも基づき規定されるコスト関数を最小化する前記ハッシュ関数のパラメータを、前記ハッシュ関数の前記最適化されたパラメータとして導出する処理を含む、ことを特徴とするプログラム。
【請求項２０】
前記連続値関数のハッシュ関数（ｋ番目のハッシュ関数、ｋ＝１、・・・K）として、シグモイド（sigmoid）関数
2014050952.tif 000058
（ただし、β(t)は制御パラメータ（ｔは前記パラメータ最適化工程でのパラメータ導出の反復回数であり、β(t)は、反復回数が多くなると大となる）、
→ｗｋは射影ベクトル（ｋ＝１、・・・Ｋ）、
Ｔは転置、
→ｘはデータポイント（D次元）、
→ｗｋT→ｘは前記データポイントの射影ベクトルへの射影、
αｋはオフセット）
を用いる、ことを特徴とする請求項１９記載のプログラム。
【請求項２１】
前記パラメータ最適化処理が、
今回求めた前記コスト関数のコスト値と、前回求めたコスト関数のコスト値とを比較し、予め定められた収束条件を満たしているか否か判定する処理と、
前記収束条件を満たしている場合、前記ハッシュ関数のパラメータを最適値として出力する処理と、
前記収束条件を満たしていない場合、前記ハッシュ関数のパラメータを更新して記憶装置に記憶する処理と、
を含み、
前記収束条件を満たしていない場合、前記ハッシュ関数演算処理が、前記更新されたハッシュ関数のパラメータにより前記ハッシュ値を求めバイナリデータを出力し、前記コスト値の計算と前記収束判定が行われる、ことを特徴とする請求項１９又は２０記載のプログラム。
【請求項２２】
前記距離関数を用いて距離を求めるにあたり、第ｉ、第ｊのデータポイント間の距離ｄi,j（ただし、ｉ，ｊは１以上、ｎ以下の整数）を、距離関数
2014050952.tif 000059
（ただし、εは距離パラメータ）を用いて求める、ことを特徴とする請求項１９乃至２１のいずれか１項に記載のプログラム。
【請求項２３】
前記コスト関数は、前記第ｉ、第ｊのデータポイント間の距離ｄi,jと、前記バイナリ変換学習データ→ｙi、→ｙj間の距離｜→ｙi−→ｙj｜を乗算した項のｉ、ｊのデータ数ｎ分の総和
2014050952.tif 000060
を含む、ことを特徴とする請求項２２記載のプログラム。
【請求項２４】
前記コスト関数は、さらに項
2014050952.tif 000061
（ただし、λは所定の正数）
を含み、
2014050952.tif 000062
としてなる、ことを特徴とする請求項２３記載のプログラム。
【請求項２５】
前記コスト関数の最小値を最急勾配法で求め、前記コスト関数のコスト値が収束条件を満たしていない場合、
前記更新処理は、前記ハッシュ関数の現在の前記射影ベクトルと前記オフセットと、前記コスト関数の前記射影ベクトルと前記オフセットによる偏微分パラメータを用いて、前記ハッシュ関数の射影ベクトルとオフセットを更新し、
さらに前記制御パラメータを更新する、ことを特徴とする請求項１９乃至２４のいずれか１項に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願についての記載］
本発明は、日本国特許出願：特願２０１２−２１３４１９号（２０１２年  ９月２７日出願）に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、バイナリデータ変換方法と装置及びプログラムに関する。
【背景技術】
【０００２】
Webサイトに公開されているような数百万〜数億といった巨大なデータを高速に検索するための技術として、データの特徴を短い２値テンプレートへ変換・検索する、“バイナリハッシング”で総称される技術の開発が盛んに行われている。検索対象データは、固定長２値データ（２値テンプレート）に変換されるとともに、固定長２値データ（２値テンプレート）間の距離にはXOR（排他的論理和）等のビット論理演算が用いられる。XOR等のビット論理演算は高速である。このため、固定長２値データ（２値テンプレート）のデータ長を十分短くすることができれば、大規模データベースでの検索等においても、計算機の物理メモリ上に載せて、高速の検索を実現することができる。しかし、二つの２値テンプレート間の距離の算出として、XORの演算結果におけるビットのフリップ（ビット反転）数を数える方法は、元のデータ間における距離とは大きく異なってしまう可能性がある。【０００３】
なお、バイナリハッシングとは、D次元（Dは所定の正整数）空間上のポイントで表現される複数（n個）のデータ集合（data set）
2014050952.tif 000003
において、元の空間での近傍点（near or nearest neighbors）が同様に近傍となるようなバイナリコード（２値符号）になるハミング（Hamming）空間に写像するものである。すなわち、元のデータ集合の空間RD×nでのユークリッド（Euclid)距離による近傍関係を保ったまま、Kビット長（Kは所定の正整数）のn個のバイナリコード（２値化データ）
2014050952.tif 000004
に変換する。記号→はベクトルを表している。→ｘi(i=1,・・・n)はD次元ベクトル、→ｙi (i=1,・・・n)はK次元ベクトルである。なお、式(1)において、Rは実数全体の集合を表し、式(2)において、Bはバイナリコード（２値符号）を表している。【０００４】
Kビットのバイナリコードの生成に、K個のハッシュ（Hash）関数が用いられる。ハッシュ関数は、D次元ベクトルを入力とし、例えばバイナリ値-1または1を出力とする。【０００５】
ハッシュ関数には様々な方式があるが、ここでは線形射影（linear-projection）に基づくハッシングを想定し、k番目（k=1,・・・,K）のハッシュ関数hｋ(→ｘ)は、次式(3)で定義する。【０００６】
2014050952.tif 000005
【０００７】
ここで、sgn()は引数の符号を返す符号関数（式(3)では引数f()が負のとき-1、非負（０又は正）のとき、＋１）、f()は変換関数、→ｗｋは射影ベクトル、Ｔは転置、→ｘはデータポイント、bｋは閾値（オフセット）である。【０００８】
2014050952.tif 000006
であることから、バイナリ・ハッシュビット（ｋビット目）は、次式(4)で与えられる。
2014050952.tif 000007
・・・(4)【０００９】
すなわち、バイナリコードのkビット目（ｋ=1、・・・、K）は、ｋ番目のハッシュ関数hｋ(→x)が+1、−１のとき、それぞれ、1、0となる。【００１０】
バイナリハッシングの手法として、Locality Sensitive Hashing(「LSH」と略記される）と呼ばれる一連の手法がある（非特許文献１等参照）。【００１１】
LHSは、上式(1)の変換関数f()に恒等関数を用い、→ｗをp-stable分布（p安定分布）からランダムに選び、→bを一様分布からランダムに選ぶ。LHSでは、パラメータの選択、学習データに依らない。このため、パラメータ決定に要する時間は非常に短い。【００１２】
LHSでは、射影するビット長Kを128、512等と大きくしていくことで、近傍関係の近似度を上げることができる（すなわち、Hamming距離がEuclid距離を良く近似することができる）ことが証明されている。一方で、LHSは、ビット長Kが大きくない場合に近似が良くなく、十分な精度が達成できないことが指摘されている。【００１３】
LHSと同様に、ハッシュ関数のパラメータの選択が学習データに依らない手法が、非特許文献２等に開示されている。この手法は、→ｗをLHSと同様に選択するが、変換関数f()として、三角関数を用いており、ビット長Kが大きくないときの精度が改善されている、と言われている。【００１４】
近年、学習データに依存する手法が開発されている。非特許文献３に開示されているSpectral Hashingは、ハッシュ関数の変換関数f()として三角関数を用い、学習データをその重心が原点になるよう移動した後、オフセットｂを0とし、射影ベクトル→ｗｋとして、学習データ｛→ｘｉ｝を主成分分析（Principle Component Analysis：PCAと略記される）して得られた主軸を選択する手法である。すなわち、Spectral Hashingアルゴリズムは次のように規定される。【００１５】
・平均値が0になるようデータを平行移動した後、PCAを用いてデータの主成分を求める。【００１６】
・各PCA方向に、矩形近似で、Lp（例えば１次元ラプラシアン）の固有関数（LpΦ＝λΦ）（k個の最小の単一次元解析的固有関数（analytical eigenfunction））を計算し、各方向に対して、k個の最小の固有値を計算し、d×k個の固有値のリストを作成し、k個の最小の固有値を求める。【００１７】
・各データを入力したときの解析的固有関数の出力を、０を閾値としてバイナリコードを得る。【００１８】
非特許文献３では、１次元ラプラシアン（Laplacian）Lpの固有関数Φｋと固有値λｋとして次が例示されている。
2014050952.tif 000008
2014050952.tif 000009
【００１９】
LHSでは、射影ベクトル→ｗをランダムに生成しているが、Spectral Hashingでは、データの主成分分析（PCA）に基づき、求めている。このため、Spectral Hashingの方がLHSよりも精度がよいと言われている。しかしながら、Spectral Hashingでは、主成分分析を行う必要がある。このため、例えば数値計算として安定な特異値分解(singular value decomposition)を用いた場合、Spectral Hashingの計算量は、行列の次数（特徴量次元数）Nに対して、O（N２）〜O（N３）のオーダーを要する。なお、O（N２）〜O（N３）は、計算量が入力データセットのサイズ（N）の２乗、３乗のオーダに比例するアルゴリズムであることを表している。【００２０】
一般に認識対象となるパターンは、特徴量空間で、比較的コンパクトかつ複雑な多様体を形成することが知られている。このような場合、少数の主成分ベクトルで張られる部分空間にパターン分布が集中してしまう傾向にあり、精度が十分でない、ことが指摘されている。【００２１】
この問題を解決するとした非特許文献４に開示されたアルゴリズム（Unsupervised sequential projection learning for hashing（USPLHと略記される）)では、f()は恒等関数、学習データ重心が原点になるよう移動した後、固有ベクトルを求め、データを射影して０で閾値化する。０に近いｒ＋の点とｒ−の点（図１参照）は、距離が近いのに異なるハッシュ値が割当てられる。符号が同一で０に近いｒ＋の点、０から遠いＲ＋の点は同一のハッシュ値が割当てられ、また０に近いｒ−、０から遠いＲ−の点は同一のハッシュ値が割当てられるように学習する（図１参照）。USPLHでは、次のアルゴリズムでパラメータ→ｗｋの学習が行なわれる（非特許文献４のAlgorithm 2参照）。【００２２】
１．学習データＸとバイナリコード長（ハッシングコード長）Kを入力する。【００２３】
２．初期化：Ｘ０ＭＣ＝φ，Ｓ０ＭＣ＝０【００２４】
３．k＝１からKまで以下の４〜７を繰り返す：【００２５】
４．補正された共分散行列を計算する：
Ｍｋ＝Σｋ−１ｉ＝０λｋ−ｉＸｉＭＣＳｉＭＣＸｉＭＣＴ＋ηＸＸＴ【００２６】
５．Ｍｋの第１主成分ベクトル（固有ベクトル）→ｅを抽出して→ｗｋにセットする：
→ｗｋ＝→ｅ【００２７】
６．射影→ｗｋから擬似ラベルを生成する：
ＸｋＭＣをサンプルし、ＳｋＭＣを構築する。【００２８】
７．残差を計算する：
Ｘ＝Ｘ−→ｗｋ→ｗｋＴＸ【００２９】
データポイントを１次元軸上に射影した場合について説明する。→ｗｋＴ→ｘ＝０（一次元軸分割の境界）に関して、境界左側の点をhk(→x)=-1、境界右側の点をhｋ(→x)=+1とすると、境界を間に挟んで境界に近接した左右の領域ｒ−、ｒ＋の２点(→xi，→xj)(→xi∈ｒ−，→xj∈ｒ＋）は、一次元軸上での射影が極めて近接しているにもかかわらず、異なったハッシュビットが割当てられる。→ｘi、→ｘｊの射影ベクトル→ｗｋによる射影の距離｜→ｗｋ（→ｘi−→ｘｊ）｜がε（εは予め定められた正数）以下であるのに対して、ハッシュ値ｈ（→ｘｉ）＝−１、ｈ（→ｘｊ）＝１とされる。なお、図１は、非特許文献４のFigure２に基づく図である。【００３０】
また、境界を間に挟んで境界から遠く離れた左右の領域Ｒ−、Ｒ＋に関して、→ｘｉ∈ｒ−且つ→ｘｊ∈Ｒ−、あるいは、→ｘｉ∈ｒ＋、且つ、→ｘｊ∈Ｒ＋の２点(→xi，→xj)は、射影は互いに遠く離れているにもかかわらず（｜→ｗｋ（→ｘi−→ｘｊ）｜≧ζ：ζは予め定められた正数）、同一のハッシュビットが割当てられる。すなわち、ハッシュ値ｈ（→ｘｉ）、ｈ（→ｘｊ）の積が１となる。【００３１】
このような境界誤差を修正するため、USPLHでは、隣接ペア集合Ｍと、非隣接ペア集合Ｃが導入される。集合Ｍに含まれるデータポイント対(→xi，→xj)は、例えばｒ-内のデータポイントとｒ+内のデータポイントであり、同一のハッシュビットが割当てられるべきである。集合Ｃに含まれるデータポイント対(→xi，→xj)は、R-内のデータポイントとｒ-内のデータポイント、又は、R＋内のデータポイントとr+内のデータポイントであり、互いに異なるハッシュビットが割当てられるべきである。以下の近傍対集合（neighbor-pair set Ｍと非近傍対集合（non-neighbor-pair set）Ｃを導入する。【００３２】
Ｍ＝｛(→xi,→xj)｝：h(→xi)・h(→xj)＝-1，|→ｗkT(→xi - →xj)|≦ε
Ｃ＝｛(→xi,→xj)｝：h(→xi)・h(→xj)＝１，|→ｗkT(→xi -xj)|≧ζ
ただし、ε＜ζである。【００３３】
近傍対集合Ｍと非近傍対集合Ｃから所望数ペアをサンプルする。ＸＭＣは少なくとも１つの標本ペア分離れた全ての点を含む。ラベル化されたペアとＸＭＣを用いて（ｍ個サンプリング）、ペア単位のラベル行列ＳＭＣを求める。【００３４】
Ｓ∈Rｍ×ｍ
Si,ｊ＝1      ((→xi,→xj)∈Ｍ）
Si,ｊ＝-1     ((→xi,→xj)∈Ｃ）
Si,ｊ＝0      (上記以外の場合)【００３５】
すなわち、
(→xi,→xj)∈Ｍのペアに対して、ＳｋＭＣ＝１、
(→xi,→xj)∈Ｃのペアに対して、ＳｋＭＣ＝−１
が割当てられる。【００３６】
次の繰り返しで、擬似ラベルは、集合Ｍのデータポイント対を同一ハッシュ値に割り当てられるようにし、集合Ｃのデータポイント対を異なるハッシュ値に割り当てられるようにし、前回のハッシュ関数での誤差を修正する。【００３７】
各ハッシュ関数hk()は、擬似ラベルＸｋＭＣと対応するラベル行列ＳｋＭＣを生成する。新たなラベル情報がシーケンシャル学習の各反復において、データ共分散行列の調整に用いられる。新たな射影ベクトル→ｗを学習する場合、開始からの全てのペアワイズのラベル行列が用いられるが、その寄与は、各反復において、パラメータλによって指数関数的に減少する。【００３８】
残差誤差（residual error）により修正した主成分方向を求めるが、開始時点で擬似ラベルは存在しないため、第１のベクトル→ｗ1がデータの主方向となる。各ハッシュ関数は、データ共分散行列を調整することで、反復的に擬似ラベルを満足するように学習が行われる。上記したUSPLHアルゴリズムは、残差誤差により修正した主成分方向を求める手法となっていることがわかる。【００３９】
なお、特許文献１には、ハッシュ関数を用いた近似最近傍探索法において、高速化、誤差比で最近接パターンを探索する手法として、学習パターン集合を正規分布（ガウス分布）であると過程し、学習パターンの任意の軸上における累積確率分布をシグモイド関数（Psd=1/{1-exp(-(x-μ)/a)}、μは平均、aは標準偏差）で最小二乗近似等により近似し、累積確率分布を基に確率値を一定間隔で分割するハッシュ関数を複数個定義し、未知のパターンを入力する各ハッシュ関数の出力値によりハッシュ関数により分割された空間領域（パケット）中の部分集合の和集合を求め、その集合中から最近傍パターンを探索する手法が開示されている。【００４０】
非特許文献５には、バイオメトリクス認証において、データベース上に置く認証用テンプレートをランダムなBCH（Bose-Chaudhuri-Hocquenghem）符号語(code word）Cでマスクする（ビットワイズなXOR（排他的論理和）をとる）ことによって、生体情報を保護する方式が開示されている（後述する実施例で参照される）。この方式では、認証用テンプレートは固定長二値データであることが必要であるため、前記のバイナリハッシング技術を応用することが可能である。
【先行技術文献】
【特許文献】
【００４１】
【特許文献１】特開２００９−２０７６９号公報
【非特許文献】
【００４２】
【非特許文献１】Mayur Datar, Nicole Immorlica, Piotr Indyk and Vahab S. Mirrokni, "Locality-Sensitive Hashing Scheme Based on p-Stable Distributions", Proc. Symposium on Computational Geometry, pp.253-262, 2004.
【非特許文献２】Maxim Raginsky and Svetlana Lazebnik, "Locality-Sensitive Binary Codes from Shift-Invariant Kernels", NIPS Vol.22, 2010.
【非特許文献３】Yair Weiss, Antonio Torralba and Rob Fergus, "Spectral Hashing", NIPS 2008.
【非特許文献４】Jun Wang, Sanjiv Kumar and Shih-Fu Chang, "Sequential Projection Learning for Hashing with Compact Codes", Proc. of the 27th ICML 2010.
【非特許文献５】Pim Tuyls, Anton H. M. Akkermans, Tom A. M. Kevenaar, Geert-Jan Schrijen, Asker M. Bazen and Raymond N. J. Veldhuis, "Practical Biometric Authentication with Template Protection", Proceedings of AVBPA 2005, Lecture Notes in Computer Science, Vol. 3546, Springer Verlag, pp. 436-446, (2005)
【発明の概要】
【発明が解決しようとする課題】
【００４３】
以下関連技術の分析を与える。以下では、特に、特徴量空間中でのバイナリ表現について検討する。【００４４】
上記したLSH等、学習データによらない手法は、ビット長を十分長くしておかないと、十分な近似精度が得られない。このため、必要とされる記憶容量、演算器（ビット長）等の点で、非効率である。【００４５】
学習型について検討する。ここで、数値のビット表現を考察する。図２には、char（文字型）の数値179を８ビット表現した例が示されている。他の数値（ビット列）とXOR（排他的論理和）演算後の“１”となったビット数を距離としたとき、たとえ１ビットしか異なっていなくても、MSB（Most Significant Bit）側とLSB(Least Significant Bit）側とでは、重みが異なっている。８ビット（1バイト）中、１ビットの相違がMSBの場合、その重みは128、１ビットの相違がLSBの場合、重みは１であり、１ビットの相違であるにもかかわらず、ビット位置の重みの相違で値が大幅に異なる。従って、各ビットの重みはできるだけ、同じになるようにすることが望まれる。【００４６】
上記したSpectral Hashingは、主成分方向に対して複数の三角関数を適用する手法である。図３は、Spectral Hashingを模式的に説明する図であり、０番目から３番目の固有ベクトル（Eigenvector）が示されている。Spectral Hashingでは、
・PCAの主成分方向で正負の領域を設定すること、
・領域の大きさが段階的に変わること、
が特徴である。これは、図２に示した数値ビット表現と本質的に同じであることがわる。【００４７】
Spectral Hashingでは、パターンが低次元空間に集中しているときに、所望の近似精度がでない。これは、Spectral Hashingが、図２の通常の数値のビット表現と同じ問題を解決していないことによるものである、ことは明らかである。【００４８】
また、上記したUSPLHのアルゴリズムでは、残差により修正するとはいえ、USPLHは、直交座標系の抽出方法であることから、その近似精度には限界があるものと思料される。図４に、USPLHアルゴリズムでの固有ベクトルを示す。図４に示すように、ステップ関数により、数値を表現（符号化）することで、各ビットの重みを同等とすることができ、排他的論理和（XOR）による距離と、特徴量空間上での距離とが比例することがわかる。【００４９】
すなわち、USPLHでは、特徴量の投影軸（射影ベクトル）方向だけを最適化しても、近似精度の向上には限界があり、オフセット分も同時に修正する必要があることがわかる。【００５０】
このように、学習型は、有効ではあるが、線形部分空間での原点閾値による２値化であるため、精度等には、限界がある。【００５１】
したがって本発明は、上記問題点に鑑みて創案されたものであって、その目的は、計算量の増大を抑えながら精度の向上を図る、バイナリデータ変換方法と装置、システム、プログラムを提供することにある。
【課題を解決するための手段】
【００５２】
本発明の１つの側面によれば、ハッシュ関数のパラメータを最適化するハッシュ関数パラメータ最適化部を備え、
記憶部からＤ次元（Ｄは予め定められた所定の正整数）空間上のポイントで表される複数のデータの集合を入力し、データポイントを射影ベクトルに射影させた値に基づき、２値表現に変換するK個（Ｋは所定の正整数）の各ハッシュ関数として、前記最適化されたパラメータのハッシュ関数を用いて、Ｋビット長の複数個の２値化データに変換し、
前記ハッシュ関数パラメータ最適化部は、前記ハッシュ関数として、変数が、前記データポイントの射影ベクトルへの射影を含む連続値関数のハッシュ関数を用いてハッシュ値を求め、連続値のバイナリ変換学習データとして、記憶部に出力するハッシュ関数演算部を備え、データポイント間の距離として、予め定められた所定の距離パラメータ以内では距離を保存するが、前記距離パラメータを超えると、値が小さくなる距離関数を用いて計算される距離と、前記連続値のバイナリ変換学習データの距離とに少なくとも基づき規定されるコスト関数を最小化する前記ハッシュ関数のパラメータを、前記ハッシュ関数の前記最適化されたパラメータとして導出する装置（バイナリデータ変換装置）が提供される。【００５３】
本発明の別の側面によれば、ハッシュ関数のパラメータを最適化するパラメータ最適化工程と、
記憶部からＤ次元（Ｄは所定の正整数）空間上のポイントで表される複数のデータの集合を入力し、データポイントを射影ベクトルに射影させた値に基づき、２値表現に変換するK個（Ｋは所定の正整数）の各ハッシュ関数として、前記パラメータ最適化手段で最適化されたパラメータのハッシュ関数を用いて、Ｋビット長の複数個の２値化データに変換する工程と、
を含み、
前記パラメータ最適化工程では、
変数が、前記データポイントの射影ベクトルへの射影を含む連続値関数のハッシュ関数を用いて、ハッシュ値を求め、連続値のバイナリ変換学習データとして記憶部に出力し、
データポイント間の距離として、予め定められた所定の距離パラメータ以内では、前記データポイント間の距離を保存した値をとり、前記距離パラメータを超えると、値が小さくなる特性の距離関数を用いて計算される距離と、前記連続値のバイナリ変換学習データの距離とに少なくとも基づき規定されるコスト関数を最小化する前記ハッシュ関数のパラメータを、前記ハッシュ関数の前記最適化されたパラメータとして導出する方法（バイナリデータ変換方法）が提供される。【００５４】
本発明のさらに別の側面によれば、ハッシュ関数のパラメータを最適化するパラメータ最適化処理と、
記憶部からＤ次元（Ｄは予め定められた所定の正整数）空間上のポイントで表される複数のデータの集合を入力し、データポイントを射影ベクトルに射影させた値に基づき、２値表現に変換するK個（Ｋは所定の正整数）の各ハッシュ関数として、前記パラメータ最適化手段で最適化されたパラメータのハッシュ関数を用いて、Ｋビット長の複数個の２値化データに変換する処理を、コンピュータに実行させるプログラムであって、
前記パラメータ最適化処理は、変数が、前記データポイントの射影ベクトルへの射影を含む連続値関数のハッシュ関数を用いて、ハッシュ値を求め、連続値のバイナリ変換学習データとして記憶部に出力するハッシュ関数演算処理と、
データポイント間の距離として予め定められた所定の距離パラメータ以内では距離を保存するが、前記距離パラメータを超えると、値が小さくなる距離関数を用いて計算される距離と、前記連続値のバイナリ変換学習データの距離とに少なくとも基づき規定されるコスト関数を最小化する前記ハッシュ関数のパラメータを、前記ハッシュ関数の前記最適化されたパラメータとして導出する処理を含むプログラムが提供される。【００５５】
本発明のさらに別の側面によれば、登録フェーズにおいて、生体情報から特徴量抽出したデータ集合に対して、前記バイナリデータ変換装置で変換されたバイナリデータZに対して、乱数Sを生成し、
前記乱数Sをエンコーダで誤り訂正符号化した符号語Cと前記バイナリデータZの排他的論理和（Z (+) C）、及び、前記乱数Sを入力とするハッシュ関数の出力H（S）を、データベースへ登録する生体認証システムが提供される。【００５６】
本発明のさらに別の側面によれば、認証フェーズにおいて、前記バイナリデータ変換装置で変換された認証対象のバイナリデータZ’と、前記データベースから読み出した前記（Z (+) C）との排他的論理和をとった値C’をデコーダに入力して誤り訂正復号し、
前記デコーダの出力S'をハッシュ関数に入力し、
前記ハッシュ関数の出力H(S')と、前記データベースに登録されているH(S)とが等しいか否か判定する生体認証システムが提供される。【００５７】
本発明のさらに別の側面によれば、前記登録フェーズにおいて、前記エンコーダは誤り訂正符号として線形符号を用い、前記ハッシュ関数は準同型性を有する。また、認証フェーズでは、認証を行う毎に第２の乱数S'を生成し、前記第２の乱数S'を、第２のエンコーダで誤り訂正符号化した符号語C’と、前記バイナリデータ変換装置から出力される認証対象のバイナリデータZ’との排他的論理和（C' (+) Z'）と、前記データベースから読み出した（Z (+) C）との排他的論理和((Z'ｉ (+) Z'ｉ) (+) (Cｉ (+) C'ｉ))を第２のデコーダに入力して誤り訂正復号し、前記第２のデコーダからの出力S"をハッシュ関数に入力して求めたハッシュ値H(S”)と、前記第２の乱数S'をハッシュ関数に入力して求めたハッシュ値H(S')との排他的論理和（値H(S') (+) H(S”)）が、前記データベースに登録されたH(S)と等しいか否か判定し、前記第２のエンコーダ、第２のデコーダは、誤り訂正符号として線形符号を用い、前記ハッシュ関数は準同型性を有する生体認証システムが提供される。
【発明の効果】
【００５８】
本発明によれば、計算量の増大を抑えながら精度の向上を図る、全く新規なハッシュ関数の学習に基づくバイナリデータ変換方法と装置、システム、プログラムが提供される。
【図面の簡単な説明】
【００５９】
【図１】非特許文献４のFigure 2に基づく図である。
【図２】数値のバイナリ表示例を示す図である。
【図３】Spectral Hashingの固有ベクトルを例示する図である。
【図４】USPLHアルゴリズムの固有ベクトルを例示する図である。
【図５】シグモイド関数のグラフを示す図である。
【図６】距離関数のグラフを示す図である。
【図７】近傍と距離関数の関係を説明する図である。
【図８】実施形態の構成を示す図である。
【図９】実施形態の処理手順の一例を示す流れ図である。
【図１０】実施例１を説明する図である。
【図１１】実施例２を説明する図である。
【発明を実施するための形態】
【００６０】
本発明の実施形態を以下に説明する。以下では、まず、ハッシュ関数のパラメータの学習を説明する。D次元空間中にｎ個のデータから構成されるデータ集合（data set）
2014050952.tif 000010
をハッシュ関数h()によって、Kビット長のバイナリコードYへと変換する。
2014050952.tif 000011
【００６１】
本実施形態では、ハッシュ関数hk(→ｘ)として、連続関数であるシグモイド関数(sigmoid function)を用いて次式(5)のように拡張定義する（k=1,・・・K）。
【００６２】
2014050952.tif 000012
・・・(5)
【００６３】
式(5)において、β(t)は制御パラメータ、→ｗｋは射影ベクトル（絶対値|→ｗｋ|=1、k=1,・・・K）、Tは転置（→ｗｋTは→ｗｋの転置べクトル）、→ｘはD次元データポイント、αｋは閾値（オフセット）、→ｗｋT→ｘは、データポイント→ｘと射影ベクトル→ｗｋとの内積であり、データポイント→ｘの→ｗｋへの射影（projection）である。なお、シグモイド関数は、変数ｘについてσ（ｘ）＝１／（１＋exp(-ａｘ)）（ａをゲインという）の形式で表される。
【００６４】
式(5)において、β(t)は正値であり、定数、又は、学習が進むにしたがい（後述される最適化時の反復回数が大となるに従い）、β(t)は大きくなるように制御する。
【００６５】
図５に、式(5）のシグモイド関数を用いたハッシュ関数hash(x)を示す。図５において、横軸のｘは、式(5)の→ｗｋＴ→ｘ−αｋ，縦軸はシグモイド関数の値である。
【００６６】
また、図５のハッシュ関数hash(x)（シグモイド関数）は、β→∞の極限で−１又は＋１となり、式(6)と一致する。ハッシュ関数のパラメータの学習が完了し、最適なパラメータ→ｗｋ、αｋが得られると、この式(6)のハッシ関数（２値化関数）を用いて、バイナリハッシュ値を得る。
【００６７】
2014050952.tif 000013
・・・(6)
【００６８】
上式(3)と式(6)を較べると、
2014050952.tif 000014
より、式(6)は、式(3)の変換関数f()を恒等写像（f(x)=x）とし、式(3)のbｋを-αｋとした場合に等しいことがわかる。
【００６９】
また、D次元特徴量空間でのデータポイント間の距離を表すn×nの距離行列Dのｉ行ｊ列の要素di,jを次式(7)で定義する。
【００７０】
2014050952.tif 000015
・・・(7)
【００７１】
式(7)において、εは正の定数であり、特徴量空間中での近傍を予め定義する値（距離パラメータ）である。図６に、上式(7)の距離行列の要素di,jのグラフを示す。図６において、横軸ｘは、式(7)におけるデータポイント対の距離｜→ｘi−→ｘj｜であり、縦軸は、di,jである。図６に示すように、｜→ｘi−→ｘj｜＝０のとき、di,j=1、｜→ｘi−→ｘj｜＝εのとき、横軸のxは１となり、di,j＝1/e=1/2.71828・・・となる。さらに、｜→ｘi−→ｘj｜＞εで、di,jは急激に（指数関数的に）小さくなる。
【００７２】
図７（A）、図７（B）は、特徴量空間（ＲD×n）における近傍の概念を説明する図である。ある点を中心とし、半径ε以内の近傍内では、距離を保存し、半径ε外、すなわち近傍以外では、距離を保存しない。すなわち、バイナリハッシング等の２値化において、どのような大きさの距離であっても近似できるようなビット表現は、必ずしも望まれるわけではない。言い換えると、近傍での距離は、例えば本人−他人の弁別等に重要であるが、ある程度離れた位置との間の距離は、閾値に対して十分大きければ、近似誤差が大きくても構わない、ということができる。｜→ｘi−→ｘj｜＞εで、di,jは急激に（指数関数的に）小さくなる、ということは、離れているデータ点間距離は、学習時に考慮しない、ことと等価である。また、di,jが十分小さいときには、その値を０とすることで、計算を省略することができ学習時間を短縮することが可能である。
【００７３】
バイナリデータＹは、元のデータ集合（２値化される前のデータ集合）Ｘ間の距離を表す行列Ｄを近似すべきであることから、式(5)のシグモイド関数で定義されるハッシュ関数
2014050952.tif 000016
中のパラメータ→ｗｋ、αｋを、次式(8)で与えられるコスト関数（目的関数）Ｓ（Ｗ，→α）の値を最小化するハッシュ関数の係数（パラメータ）として学習する（最適化問題）。
【００７４】
2014050952.tif 000017
・・・(8)
【００７５】
上式(8)のＷ、→αはそれぞれ次式(9),(10)で与えられる。
2014050952.tif 000018
・・・(9)
【００７６】
2014050952.tif 000019
・・・(10)
【００７７】
式(8)において、
2014050952.tif 000020
は、距離の近似に関わる項である。di,jは距離行例Dの要素(ｉ,j)（ｉ番目のデータポイントとｊ番目にあたるデータポイント間の距離）である。｜→yｉ- →yｊ｜は、ハッシュ値から得られるバイナリ変換学習データの距離である。元のデータセットからハッシュ関数により変換されたバイナリコードｙｉ、ｙｊ間は、XOR（排他的論理和）により比較することになるが、本実施形態では、数式上、取り扱いが容易でバイナリ符号の場合にはXORと同値となる二次式で表している。
【００７８】
ハッシュ関数の係数（パラメータ）の学習は、コスト関数Ｓの最小値を求めるにあたり、特に制限されないが、最急降下法（Most  Steepest  Descent）を用いる。コスト関数Ｓを、最急勾配法により最小化することで、ハッシュ関数（シグモイド関数）のパラメータ→ｗｋとαｋの最適値
2014050952.tif 000021
2014050952.tif 000022
を求める。＾は最適値を表している。
【００７９】
すなわち、ハッシュ関数のパラメータ学習時（パラメータの最適化時）に、バイナリ表現（２値化関数）を、連続値をとるシグモイド関数（式(5)）で置き換え、例えば最急降下法等の最適化法の適用を可能とし、パラメータ学習を行う。なお、特に制限されないが、本実施形態では、β（ｔ）の値を、学習回数ｔに依存して大きくすることで、シグモイド関数は、２値化関数に近づくようにしている。
【００８０】
ここで、ｔ回目の更新時（t=0は初期値）の各パラメータ→ｗｋ、αｋを
2014050952.tif 000023
2014050952.tif 000024
と表すものする。
【００８１】
(t+1)回目の更新における各パラメータ
2014050952.tif 000025
2014050952.tif 000026
（k=1、2、・・・n）は、t回目の反復でのパラメータ値
2014050952.tif 000027
2014050952.tif 000028
と、コスト関数Ｓの勾配（Ｓの→ｗ(t)ｋ、α(t)ｋによる偏微分係数）
2014050952.tif 000029
2014050952.tif 000030
により、それぞれ次式(11)、(12)により、更新する。
【００８２】
2014050952.tif 000031
・・・(11)
【００８３】
2014050952.tif 000032
・・・(12)
【００８４】
ここで、γ(t)は所定の正定数とするか、あるいは、繰り返し（iteration）毎にその値を小さくする(γ(t+1)<γ(t))ように制御する。
【００８５】
式(11)の偏微分項は以下の式(13)で表される。
2014050952.tif 000033
・・・(13)
【００８６】
ただし、
2014050952.tif 000034
・・・(14)
である。
【００８７】
式(12)の偏微分項は以下の式で表される。
【００８８】
2014050952.tif 000035
・・・(15)
【００８９】
2014050952.tif 000036
・・・(16)
【００９０】
(t+1)回目の反復（iteration）で求めた式(8)のコスト関数S(t+1)(W,→α)と、t回目の反復で求めた式（８）のコスト関数S(t)(W,→α)の差S(t+1)(W,→α)-S(t)(W,→α)の絶対値が収束判定パラメータδ以下の場合、
｜S(t+1)(W,→α)-S(t)(W,→α)｜＜δ
コスト関数S(W,→α)は収束したものと判定され（最小値）、このときのパラメータＷ（t+1)、→α(t+1)が、係数出力部１１２から、ハッシュ関数（式(5)のシグモイド関数）のパラメータ（最適パラメータ）
2014050952.tif 000037
2014050952.tif 000038
として出力される。
【００９１】
n個のD次元データポイントを含む学習データ（データ集合）に対して、ハッシュ関数の最適パラメータ＾Ｗ（t+1)、＾→α(t+1)と、＾β(t+1)を、式(5)のシグモイド関数のパラメータに用いて、図５の横軸ｘ＝０で２値化して得られた、Kビット長のn個のバイナリハッシュコードＹ∈BK×nが求めるバイナリコードである。なお、式(5)においてβ(t+1)→∞とした式（６）のハッシュ関数ｈk（→x;→W,αｋ）の→ｗｋ、αｋに、導出された最適化パラメータ＾Ｗ（t+1)、＾→α(t+1を代入することで、２値化（バイナリハッシング）してもよい。このバイナリコードは、例えば近接近傍探索処理等に用いられる。
【００９２】
上記の通り、ハッシュ関数として、連続値表現のシグモイド関数を用い、元のデータ集合（Euclid空間）の距離ｄとして、近傍では距離を保存するが、近傍以外では距離を保存しない（予め定められた所定値以上離れた距離はほぼ同一の一定値に設定される）特性の距離関数を用いて求めた距離行列ｄi,jと、連続関数であるシグモイド関数をハッシュ関数として用いて求めたバイナリ学習データｙｉ，ｙｊの距離と、に基づき規定されるコスト関数の最小化により、ハッシュ関数の最適パラメータを求める、という新規な学習方法を実装したことで、計算量等の増大を抑止しながら、精度の向上（例えば、元の空間での近傍点（near or nearest neighbors）が類似したバイナリコードを持つこと）を可能としている。
【００９３】
なお、式(8)において、→yiと→yjが同一の場合に、||内が０となる。このため、学習の途中で、→yiと→yjが同じ値となる方が、コスト関数Ｓ（Ｗ,→α）は小さくなる。つまり、→yi、及び→yjが同一になるように誤った学習をしてしまう事態が発生し得る。この事態を防ぐために、式(8)において、ペナルティ項を付与する、ようにしてもよい。例えばλを正定数として、→yiがばらつく方が好ましいペナルティ項をとりいれたコスト関数として、次式(17)を用いるようにしてもよい。
【００９４】
2014050952.tif 000039
・・・(17)
【００９５】
式(17)をコスト関数として用いた場合でも、コスト関数を最小化するハッシュ関数の係数の学習は、式(8)をコスト関数として用いた場合と同様にして行われる。
【００９６】
図８は、本発明の実施形態の構成を説明する図である。図８には、本実施形態の装置（バイナリコード変換装置）１００において、ハッシュ関数のパラメータ最適化を行う部分（ハッシュ関数パラメータ最適化部（手段））が模式的に示されている。複数（ｎ個）のＤ次元（Ｄは所定の整数値）データポイントを含むデータ集合を入力し、前記データポイントを射影ベクトルに射影させた値に基づき２値化するＫ個（Ｋは所定の整数値）のハッシュ関数によってＫビット長の複数（ｎ個）のバイナリデータに変換する装置であって、距離行列計算部１０２、ハッシュ関数演算部１０４、コスト計算部１０６、コスト比較部１０８、更新操作部１０９、ハッシュ関数係数更新部１１０、係数出力部１１２、距離パラメータεを記憶する記憶部１１４、学習データの記憶部１１６、距離行列を記憶する記憶部１１８、バイナリ変換学習データの記憶部１２０、コスト値を記憶する記憶部１２２、収束判定パラメータδの記憶部１２４、ハッシュ関数係数Ｗ、αを記憶する記憶部１２６、パラメータβを記憶する記憶部１２８を備えている。ストレージ装置として図示される１１４、１１６、１１８、１２０、１２２、１２４、１２６、１２８は、磁気／光／半導体ストレージのいずれであってもよい。また、各ストレージ装置は同一のストレージ装置の別の記憶領域であってもよい。また、パラメータε、δ、βを格納するストレージ装置１１４、１２４、１２８は、ラッチ回路、レジスタであってもよい。記憶部１１６に記憶される学習データは、バイナリコード（２値化データ）に変換対象のデータ集合（data set）からなり、例えば生体情報等から特徴抽出（Feature Extraction）により取得された特徴量からなる。
【００９７】
距離行列計算部１０２、ハッシュ関数演算部１０４、コスト計算部１０６、コスト比較部１０８、更新操作部１０９、ハッシュ関数係数更新部１１０、係数出力部１１２は、コンピュータで実行されるプログラムでその処理・機能を実現するようにしてもよい。また実施形態によれば、該プログラムを記録したコンピュータで読み出し可能な媒体(半導体メモリ、磁気／光ディスク媒体・装置)が提供される。
【００９８】
図９は、本発明の実施形態の処理手順を説明する図である。図８及び図９を参照して、本実施形態におけるハッシュ関数のパラメータ最適化の処理手順を説明する。
【００９９】
ステップ１（図９のS101）：
距離行列計算部１０２は、記憶部１１６からD次元空間のn個の学習データ
2014050952.tif 000040
を入力し、記憶部１１４から距離パラメータεを入力し、式(7)に従って２つのデータポイント間の距離di,jを計算し、n×nの距離行列Dを記憶部１１８に出力する。
【０１００】
ステップ２（図９のS102）：
ハッシュ関数演算部１０４は、記憶部１１６からD次元空間のn個のデータポイント
2014050952.tif 000041
を入力し、
記憶部１２６から式(5)のシグモイド関数の係数（パラメータ）
2014050952.tif 000042
2014050952.tif 000043
を入力し、
記憶部１２８からシグモイド関数の制御パラメータβ(t)を入力し、
上式（5）に従い、シグモイド関数を用いたハッシュ関数
2014050952.tif 000044
(ただし、k=1,・・・K)
の値を計算する。ハッシュ関数演算部１０４は、K個のハッシュ関数ｈｋのハッシュ値からバイナリ変換学習データを求め、
2014050952.tif 000045
を記憶部１２０に出力する。
【０１０１】
ステップ３(図９のS103)：
コスト計算部１０６は、記憶部１１８から、距離行列Dを読み出し、記憶部１２０からバイナリ変換学習データＹ∈BK×nを読出し、式(8)又は式(17)のコスト関数（目的関数）
2014050952.tif 000046
を計算し、記憶部１２２と、コスト比較部１０８に出力する。
【０１０２】
ステップ４(図９のS104)：
コスト比較部１０８は、前回のコスト値S(t-1)を記憶部１２２から読み出し、収束判定パラメータδを記憶部１２４から読み出し、コスト計算部１０６からのコスト値S(t)と比較する。すなわち、コスト比較部１０８は、コスト値S(t)と前回のコスト値S(t-1)に関して収束条件：
2014050952.tif 000047
が成立するか否か判定する。判定の結果、(18)の収束条件が成立であれば、収束であり、収束条件が不成立であれば、非収束である。
【０１０３】
ステップ５（図９のS105）：
収束した場合(S104の判定Yes)、係数出力部１１２はＷ(t)、α（ｔ）を出力する（コスト関数の最小化終了）。コスト関数の最小化によるハッシュ関数のパラメータの最適値を発見した段階で、ハッシュ関数演算部１０４は、最適化完了後のパラメータを用いて２値表現のハッシュ値（式（５）の−１と＋１の間の連続値の代わりに、式（６）の｛−１、＋１｝の２値表現のハッシュ値）を求め、これが、求めるバイナリデータとなる。
【０１０４】
ステップ６（図９のS106）：
一方、収束条件を満たさない場合(S104の判定No)、更新操作部１０９は、パラメータβ(t)をβ(t+1)に更新し、ハッシュ関数係数更新部１１０に、係数（パラメータＷ、→α）の更新を指示する。ハッシュ関数係数更新部１１０は、上記した最急降下法等にしたがって、ハッシュ関数のパラメータＷ(t+1)、α(t+1)を、それぞれ上式(11)、(12)にしたがって計算する。
【０１０５】
ステップ２(図９のS102)に戻り、ハッシュ関数演算部１０４は、ハッシュ関数係数更新部１１０で計算したＷ(t+1)、α(t+1)、更新操作部１０９により更新されたβ(t+1)を入力し、ハッシュ値を求め、バイナリ変換学習データを、記憶部１２０に格納する。
【０１０６】
上記の通り、本実施形態は、ハッシュ関数のパラメータの学習（最適化）を数式アルゴリズムを用いた明確な手続き（exactな解）として規定している。
【０１０７】
本実施形態によれば、ハッシュ関数に非線形のシグモイド関数を用い、さらに元のデータの距離（距離行列）として近傍領域のみ距離を保存する関数型を採択し、距離行列の要素と対応するバイナリ変換データの距離との演算で求められる目的関数（コスト関数）の最適化（最小化）を行うことで、ハッシュ関数のパラメータ（射影ベクトル、閾値（オフセット））の最適化を行い、バイナリ変換データを取得している。
このため、本実施形態によれば、線形部分空間での原点閾値による２値化を行う関連技術の問題点を解消して、精度を向上し、計算量の増大を抑制している。本実施形態によれば、学習型の近似最近傍探索等の任意応用に適用可能である。例えばWebサイトのデータ比較や類似データの抽出、Bigデータに対する大規模データマイニング等にも適用可能であるが、以下では、一実施例として生体認証への適用例を説明する。
【０１０８】
＜実施例１＞
図１０は、非特許文献５のFigure.2に基づく図である。なお、図１０において、生体情報を取得するセンサ（例えば指紋情報を取得するセンサ）、非特許文献５のFigure.2の特徴量の抽出（Feature Extraction）、統計処理（Statistical Analysis）、量子化（Quantization）、選択（select）等は省略されている。テンプレートの登録（enrollment）は、以下のようにして行われる。非特許文献５では、生体情報Ｚと秘匿情報Ｓを用いて、生体認証用テンプレートを生成している。図９において、生体情報Ｚは、特徴量の抽出の結果得られたｎ個のD次元データポイントを含むデータ集合（X∈RD×ｎ）を、本実施形態により２値化したバイナリコード集合Y∈BK×ｎ）からなる。
【０１０９】
（１）ユーザ毎にランダムに生成された秘匿情報Ｓｉをエンコーダ（ENC）２０２に入力して誤り訂正符号化し（Error Correcting Coding：ECC）、符号語Ｃｉを生成する。ECCはパラメータ（K, s, d）の２元BCH符号が用いられる。Kは符号語（code word）の長さ、sは情報シンボル(information symbol）数、dは訂正可能な誤り数である。
【０１１０】
（２）符号語Cｉと生体情報Zｉを排他的論理和２０６に入力し、
W2ｉ = Cｉ (+) Zｉ
を計算する（ただし、(+)はビット毎の排他的論理和演算（bitwise XOR）を表す）。
【０１１１】
（３）秘匿情報Ｓｉを、SHA（Secure Hash Algorithm）−１等の暗号学的ハッシュ関数（cryptographic (one-way) hash function）２０４に入力して、ハッシュ値H(Sｉ)を得る。
【０１１２】
（４）W2ｉ及びH(Sｉ)をテンプレート情報としてデータベース（DB）２０８に格納する。
【０１１３】
生体情報Ｚｉは、乱数性（ランダムネス）の高い符号語Cｉ でマスクされているため、W2ｉから生体情報は漏洩しない。
【０１１４】
上記（１）から（４）によって生成されたテンプレートと、別の生体情報Ｚ'ｉが同じ人物から採取したものであるか否かの認証（Verification）フェーズは、次のようにして行われる。
【０１１５】
（１）Z'ｉとW2ｉとを排他的論理和２１０に入力し、
C'ｉ = W2ｉ (+) Z'ｉ = Cｉ (+) (Zｉ (+) Z'ｉ)
を計算する。登録フェーズと認証フェーズの生体情報（例えば指紋等）が同一人物のものであれば、(Zｉ (+) Z'ｉ)のHamming重みは小さいので、誤り訂正可能である。
【０１１６】
（２）C'ｉをデコーダ（DEC）２１２に入力してBCH符号の誤り訂正復号を行い、S'ｉを計算する。
【０１１７】
（３）Ｓ'ｉを、SHA-1等の暗号学的ハッシュ関数２１４に入力してハッシュ値H(Sｉ')を計算する。
【０１１８】
（４）データベース（DB）２０８からH(Sｉ)を読み出し、判定器２１６でH(Sｉ) = H(S'ｉ)が成立するかチェックする。H(Sｉ) = H(S'ｉ)が成立する場合には、テンプレートと生体情報Ｚ'ｉが同じ人物から採取されたものと判断する。H(Sｉ) = H(S'ｉ)が成立しない場合は、異なる人物から採取されたものと判断する。
【０１１９】
図１０では、生体情報Zの秘匿に用いた乱数（秘匿情報Ｓi）のハッシュ値H(Si）をデータベースに格納することで秘匿している。生体情報Zを、乱数性の高いデータCi（Siを誤り訂正符号化）と排他的論理和をとることで秘匿している。図１０の手法は、秘匿（暗号化）されたデータを復号することなく、暗号文が、提示されたデータと一定のハミング距離以内のデータを暗号化したものであるか否かの照合を行う方式と解釈することが可能である。
【０１２０】
しかしながら、認証フェーズにおいて、生体情報Z'iそのものが認証を行うサーバに送信される。認証成功時（すなわち、H(Sｉ) = H(S'ｉ)が成立する場合）に、生体情報S'ｉも（デコーダ２１２の出力）も漏洩するため、データべースに登録された生体情報Zｉが認証サーバに知られてしまう可能性がある。このような問題点を解決する手法を実施例２として説明する。
【０１２１】
＜実施例２＞
図１１は、実施例２の構成を説明する図である。登録フェーズでは、秘匿情報Sｉを誤り訂正符号化するエンコーダ３０２は、誤り訂正符号として線形符号を用い、ハッシュ関数３０４は、準同型性を有するハッシュ関数を用いる点が、図１０の構成と相違している。これ以外は、図１０と同一である。なお、準同型性とは、写像ｆ：G→G’が、∀ａ，ｂ∈Gに対してf(a・b)=f(a)・f(b)を満たすことをいう。
【０１２２】
線形符号は、Sｉを誤り訂正符号化した符号語Cｉ、S'iを誤り訂正符号化した符号語C'ｉに関して Cｉ (+) C'ｉが、Sｉ (+) S'ｉを誤り訂正符号化した符号語となるという性質を持った誤り訂正符号を用いる。
【０１２３】
また準同型のハッシュ関数は、
Sｉのハッシュ値H（Sｉ）
S'ｉのハッシュ値H（S'ｉ）
について、
H（Sｉ）(+) H（S'ｉ）＝H（Sｉ (+) S'ｉ）
が成り立つ、すなわち、H（Sｉ）(+) H（S'ｉ）が、Sｉ(+)S'ｉのハッシュ値となるハッシュ関数である。
【０１２４】
図１１を参照すると、認証フェーズでは、認証を行う毎に乱数（秘匿情報Ｓ'ｉ）を生成し、エンコーダ３２０で誤り訂正符号化した符号語C'iを、認証対象の生体情報Z'iを排他的論理和３１８に入力し、
Z'ｉ (+) C'ｉ
を計算する。排他的論理和３１８の出力(Z'ｉ (+) C'ｉ)とデータベース（DB）３０８から読み出したW2ｉを排他的論理和３１０に入力し、
W2ｉ (+) (Z'ｉ (+) C'ｉ)
=(Z'ｉ (+) Z'ｉ) (+) (Cｉ (+) C'ｉ)
を計算する。
【０１２５】
排他的論理和３１０の出力(Z'ｉ (+) Z'ｉ) (+) (Cｉ (+) C'ｉ)をデコーダ（DEC）３１２に入力し、誤り訂正復号を行い、S"ｉを出力する。
【０１２６】
秘匿情報Ｓ'ｉを入力する準同型性のハッシュ関数３２２の出力H（S'ｉ)、デコーダ（DEC）３１２の出力を入力する準同型性のハッシュ関数３１４の出力H（S"ｉ)、データベース（DB）３０８から読み出したH(Si)を判定器３１６に入力し、
H（Sｉ）＝H（S'i） (+) H（S"ｉ）
が成り立つか否か判定する。成り立つ場合、受理、成り立たない場合、拒否する。
【０１２７】
すなわち、認証が受理される場合、
Sｉ＝ S'i (+) S"ｉ
となるため、ハッシュ関数の準同型性より、
H（Sｉ）＝ H（S'i (+) S"ｉ）＝H（S'i） (+) H（S"ｉ）
が成り立つ。
【０１２８】
図１１の構成の場合、認証フェーズにおいてデータベース３０８から送出される情報から生体情報を計算することはできず、生体情報Z'ｉを乱数でマスクした情報が認証サーバに与えられるため、安全性を担保することができる。
【０１２９】
なお、上記の特許文献、非特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施例の各要素、各図面の各要素等を含む）の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【０１３０】
１００  ２値化装置
１０２  距離行列計算部
１０４  ハッシュ関数演算部
１０６  コスト計算部
１０８  コスト比較部
１０９  更新操作部
１１０  ハッシュ関数係数更新部
１１２  係数出力部
１１４  記憶部（距離パラメータεの記憶部）
１１６  記憶部（学習データの記憶部）
１１８  記憶部（距離行列の記憶部）
１２０  記憶部（バイナリ変換学習データの記憶部）
１２２  記憶部（コスト値の記憶部）
１２４  記憶部（収束判定パラメータδの記憶部）
１２６  記憶部（ハッシュ関数係数Ｗ、αの記憶部）
１２８  記憶部（パラメータβの記憶部）
２０２、３０２、３２０  エンコーダ（ENC）
２０４、２１４、３０４、３１４、３２２  ハッシュ関数
２０６、２１０、３０６、３１０、３１８  排他的論理和（XOR）
２０８、３０８  データベース（DB）
２１２、３１２  デコーダ（DEC）
２１６、３１６  判定器
【図１】
2014050952.tif 000063
【図２】
2014050952.tif 000064
【図３】
2014050952.tif 000065
【図４】
2014050952.tif 000066
【図５】
2014050952.tif 000067
【図６】
2014050952.tif 000068
【図７】
2014050952.tif 000069
【図８】
2014050952.tif 000070
【図９】
2014050952.tif 000071
【図１０】
2014050952.tif 000072
【図１１】
2014050952.tif 000073
【手続補正書】
【提出日】平成28年3月7日(2016.3.7)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項３
【補正方法】変更
【補正の内容】
【請求項３】
前記ハッシュ関数パラメータ最適化部が、
前記データポイント間の距離として、予め定められた所定の距離パラメータ以内では距離を保存するが、前記距離パラメータを超えると、値が指数関数的に小さくなる距離関数を用いて距離行列を計算する距離行列計算部と、
前記コスト関数を用いてコスト値を計算するコスト計算部と、
前記コスト計算部で今回求めたコスト値と、前記コスト計算部で前回求めたコスト値とを比較し、予め定められた収束条件を満たしているか否か判定するコスト比較部と、
前記収束条件を満たしている場合には、前記ハッシュ関数のパラメータを最適値として出力するパラメータ出力部と、
前記収束条件を満たしていない場合には、前記ハッシュ関数のパラメータを更新して記憶装置に記憶する更新部と、
を備え、
前記収束条件を満たしていない場合、前記ハッシュ関数演算部は、前記更新部で更新された前記ハッシュ関数のパラメータを用いて、前記バイナリ変換学習データを出力し、
前記コスト計算部によるコスト値を計算し、
前記コスト比較部による収束判定が行われる、ことを特徴とする請求項２記載のバイナリデータ変換装置。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１２
【補正方法】変更
【補正の内容】
【請求項１２】
ハッシュ関数のパラメータを最適化するパラメータ最適化部と、２値データ変換部と、記憶部と、を備えたコンピュータによるバイナリデータ変換方法であって、
前記２値データ変換部では、前記記憶部から予め定められた所定の次元数の空間上のポイントで表される複数のデータの集合を入力し、データポイントの射影ベクトルへの射影に基づき、２値表現に変換するＫ個（Ｋは所定の正整数）の各ハッシュ関数として、前記パラメータ最適化部で最適化されたパラメータのハッシュ関数を用いて、Ｋビット長の複数個の２値化データに変換し、
前記パラメータ最適化部では、
前記ハッシュ関数として、変数が、前記データポイントの射影ベクトルへの射影を含む連続値関数のハッシュ関数を用いて、ハッシュ値を求め、連続値のバイナリ変換学習データとして前記記憶部に出力し、
データポイント間の距離として、予め定められた所定の距離パラメータ以内では、前記データポイント間の距離を保存した値をとり、前記距離パラメータを超えると、値が小さくなる特性の距離関数を用いて計算される距離と、前記連続値のバイナリ変換学習データの距離と、に少なくとも基づき規定されるコスト関数を最小化する前記ハッシュ関数のパラメータを、前記ハッシュ関数の最適化されたパラメータとして導出する、ことを特徴とするバイナリデータ変換方法。
【手続補正３】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１３
【補正方法】変更
【補正の内容】
【請求項１３】
前記パラメータ最適化部は、
前記連続値関数のハッシュ関数（ｋ番目のハッシュ関数、ｋ＝１、・・・Ｋ）として、シグモイド（sigmoid）関数
2014050952.tif 000074
（ただし、β(t)は正値の制御パラメータ（ｔは前記パラメータ最適化部でのパラメータ導出の反復回数であり、β(t)は、反復回数が多くなると大となる）、
→ｗｋは射影ベクトル（ｋ＝１、・・・Ｋ）、
Ｔは転置、
→ｘはデータポイント（D次元）、
→ｗｋT→ｘは前記データポイントの射影ベクトルへの射影、
αｋはオフセット）
を用い、前記ハッシュ関数のパラメータ→ｗｋとαｋの最適化を行う、ことを特徴とする請求項１２記載のバイナリデータ変換方法。
【手続補正４】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１４
【補正方法】変更
【補正の内容】
【請求項１４】
前記パラメータ最適化部は、
前記コスト関数の最小化の過程において、
今回求めた前記コスト関数のコスト値と、前回求めた前記コスト関数のコスト値とを比較し、予め定められた収束条件を満たしているか否か判定し、
前記収束条件を満たしている場合、前記ハッシュ関数のパラメータを最適値として出力し、
前記収束条件を満たしていない場合、前記ハッシュ関数のパラメータを更新して前記記憶部に記憶し、前記収束条件を満たしていない場合、前記ハッシュ関数の演算にあたり、前記更新されたハッシュ関数のパラメータにより前記ハッシュ値を求めバイナリデータを出力し、
前記コスト関数のコスト値を計算し、
前記コスト値と、前回求めた前記コスト関数のコスト値とを比較し、これらが予め定められた収束条件を満たしているか否かの収束判定を行う、ことを特徴とする請求項１３記載のバイナリデータ変換方法。
【手続補正５】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１５
【補正方法】変更
【補正の内容】
【請求項１５】
前記パラメータ最適化部は、前記距離関数を用いて距離を計算するにあたり、
第ｉ、第ｊのデータポイント間の距離ｄi,j（ただし、ｉ，ｊは１以上、ｎ以下の整数）を、距離関数
2014050952.tif 000075
（ただし、εは前記距離パラメータ）を用いて求める、ことを特徴とする請求項１４に記載のバイナリデータ変換方法。
【手続補正６】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１８
【補正方法】変更
【補正の内容】
【請求項１８】
前記パラメータ最適化部は、
前記コスト関数の最小値を最急勾配法で求め、前記コスト関数のコスト値が収束条件を満たしていない場合、前記ハッシュ関数の現在の前記射影ベクトルと前記オフセットと、前記コスト関数の前記射影ベクトルと前記オフセットによる偏微分パラメータを用いて、前記ハッシュ関数の射影ベクトルとオフセットを更新し、さらに、
前記制御パラメータを更新する、ことを特徴とする請求項１３乃至１７のいずれか１項に記載のバイナリデータ変換方法。
【手続補正７】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２０
【補正方法】変更
【補正の内容】
【請求項２０】
前記連続値関数のハッシュ関数（ｋ番目のハッシュ関数、ｋ＝１、・・・K）として、シグモイド（sigmoid）関数
2014050952.tif 000076
（ただし、β(t)は制御パラメータ（ｔは前記パラメータ最適化処理でのパラメータ導出の反復回数であり、β(t)は、反復回数が多くなると大となる）、
→ｗｋは射影ベクトル（ｋ＝１、・・・Ｋ）、
Ｔは転置、
→ｘはデータポイント（D次元）、
→ｗｋT→ｘは前記データポイントの射影ベクトルへの射影、
αｋはオフセット）
を用いる、ことを特徴とする請求項１９記載のプログラム。
【手続補正８】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２１
【補正方法】変更
【補正の内容】
【請求項２１】
前記パラメータ最適化処理が、
今回求めた前記コスト関数のコスト値と、前回求めたコスト関数のコスト値とを比較し、予め定められた収束条件を満たしているか否か判定する処理と、
前記収束条件を満たしている場合、前記ハッシュ関数のパラメータを最適値として出力する処理と、
前記収束条件を満たしていない場合、前記ハッシュ関数のパラメータを更新して記憶装置に記憶する処理と、
を含み、
前記収束条件を満たしていない場合、前記ハッシュ関数の演算にあたり、前記更新されたハッシュ関数のパラメータにより前記ハッシュ値を求めてバイナリデータを出力し、前記コスト値の計算と前記収束判定が行われる、ことを特徴とする請求項２０記載のプログラム。
【手続補正９】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２２
【補正方法】変更
【補正の内容】
【請求項２２】
前記距離関数を用いて距離を求めるにあたり、第ｉ、第ｊのデータポイント間の距離ｄi,j（ただし、ｉ，ｊは１以上、ｎ以下の整数）を、距離関数
2014050952.tif 000077
（ただし、εは距離パラメータ）を用いて求める、ことを特徴とする請求項２１記載のプログラム。
【手続補正１０】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２５
【補正方法】変更
【補正の内容】
【請求項２５】
前記コスト関数の最小値を最急勾配法で求め、前記コスト関数のコスト値が収束条件を満たしていない場合、
前記ハッシュ関数のパラメータの更新にあたり、前記ハッシュ関数の現在の前記射影ベクトルと前記オフセットと、前記コスト関数の前記射影ベクトルと前記オフセットによる偏微分パラメータを用いて、前記ハッシュ関数の射影ベクトルとオフセットを更新し、
さらに前記制御パラメータを更新する、ことを特徴とする請求項２１乃至２４のいずれか１項に記載のプログラム。
【国際調査報告】
2014050952.tif 000078
2014050952.tif 000079
2014050952.tif 000080
2014050952.tif 000081