TOP > 国内特許検索 > ハッシュ関数の変換行列を定める方法、該ハッシュ関数を利用するハッシュ型近似最近傍探索方法、その装置及びそのコンピュータプログラム

ハッシュ関数の変換行列を定める方法、該ハッシュ関数を利用するハッシュ型近似最近傍探索方法、その装置及びそのコンピュータプログラム

国内特許コード P150011195
掲載日 2015年1月28日
出願番号 特願2012-547940
登録番号 特許第5971722号
出願日 平成23年12月12日(2011.12.12)
登録日 平成28年7月22日(2016.7.22)
国際出願番号 JP2011078702
国際公開番号 WO2012077818
国際出願日 平成23年12月12日(2011.12.12)
国際公開日 平成24年6月14日(2012.6.14)
優先権データ
  • 特願2010-276013 (2010.12.10) JP
発明者
  • 青野 雅樹
  • 立間 淳司
出願人
  • 国立大学法人豊橋技術科学大学
発明の名称 ハッシュ関数の変換行列を定める方法、該ハッシュ関数を利用するハッシュ型近似最近傍探索方法、その装置及びそのコンピュータプログラム
発明の概要 インターネット上に存在するデータの量は拡大の一途をたどっているので、検索サイトに用いられる検索アルゴリズムには更なる精度の向上が期待されている。
データによる多様体上の局所的な近傍構造で表される非線形な関係を保持し、短いバイナリ符号に変換する新しいハッシュ型近似最近傍探索手法を提案する。
従来技術、競合技術の概要



現在、インターネット上には、文書、画像、音楽、動画など様々なデータが大量に存在している。これら大量のデータを有効利用するため、大規模データベースを対象とし、高速に検索質問と類似するものを見つけ出す技術が、コンピュータビジョンやテキストマイニングの分野で注目されている。例えば、画像であれば、カメラ付き携帯電話で商品を撮影し、それと見た目が類似した商品を、大量の商品データから瞬時に検索することができる。また、特定の風景画像を検索したい場合に、大規模画像データベースから類似する画像を高速に検索できれば、どこで撮影された画像かを即座に判定することができる。





一般的に、文書ベクトルや画像の特徴ベクトルは、数百から数千の高次元なものとなる。高次元特徴ベクトルで、大規模データベースを検索対象とした場合、線形探索では実用的な検索速度を得ることは難しい。この問題に対して、近似最近傍探索という、大規模データベースで高速な検索を実現する技術が注目されている。

近似最近傍探索は、木構造型とハッシュ型(非特許文献1)の二つに大きく分類される。木構造型近似最近傍探索は、特徴空間上に張られる軸の分割を繰り返して木構造を生成し、探索の際に探索範囲を狭めることで高速に探索を行う。探索範囲は、検索クエリとの暫定的な距離と許容誤差で定義される半径による超球で定義されるが、高次元ベクトルデータを対象とした場合に、次元の呪いの影響をうける。ハッシュ型近似最近傍探索は、高次元ベクトルデータを、短いバイナリ符号に変換し、これをハッシュテーブルのキーとすることで、高速に検索を行う。特徴空間上での距離関係をとらえ、類似するベクトルデータ同士では、バイナリ符号間のハミング距離が小さくなるように変換することで、次元の呪いの影響を小さくできる。また、短いバイナリ符号に変換することで、検索インデックスに必要な容量を抑えることもできる。





ハッシュ型近似最近傍探索で焦点となるのは、高次元ベクトルデータをバイナリ符号に変換するアルゴリズムである。その目的は、 n次元の m個のベクトルデータ集合 X =[x1, x2,..., x] ∈ Rn × mが与えられた場合に、ハッシュ関数 hを用いて、ベクトルデータ間の類似関係を保持したまま、dビットのバイナリ符号集合 Y =[y1, y2,..., ym] ∈ Bd × m

へと変換することである。





Locality Sensitive Hashing (LSH)は、最も知られているハッシュ型近似近傍探索アルゴリズムである。 LSHのハッシュ関数は以下の特性を満たすことを条件としている。

Pr[h(xi)= h(xj)] = sim(xi, xj)

ここで、sim(xi, xj) ∈ [0, 1]は、類似度を表す関数である。これは、類似するベクトルデータ同士は、同じハッシュ値になることを示している。 Charikarは、内積による類似度 sim(xi, xj)= xiT xjを考え、データxと同じ次元の標準正規分布 N(0,I)によるランダムな超平面(変換ベクトル)rとの積によるハッシュ関数を提案した。

hi(x) = sign(riT x)ここで、signは、与えられた数値の符号を返す関数である。バイナリ符号yは、以下のようにして得る。

y =[y1,y2, ..., yd]T

yi = (1+ hi(x))/2

このハッシュ関数が、 LSHの特性を満たすことは、最大カット問題の近似解法で示される。

【数1】








また、Kulisらは、非線形な写像 Φ(x)の内積による類似度 sim(xi, xj)= k(xi, xj)= Φ(xi )TΦ(xj)を用いた Kernelized Locality Sensitive Hashing (KLSH)を提案した。

Salakhutdinovらは、ユニット数を徐々に減少させた複数の Restricted Boltzmann Machines(RBM)によるネットワーク構造を用いてバイナリ符号を得る Semantic Hashingを提案した。Semantic Hashingのアルゴリズムでは、教師なしの事前訓練フェーズと、教師ありの微調整フェーズの二段階の学習からなる。事前訓練フェーズでは、ある層での出力は次の層の入力となるように、段階を追って各層ごとに訓練が実施される。微調整フェーズでは、ラベル付きデータを用いて、誤差逆伝搬法により、事前訓練フェーズで得られた重みを調整する。Torralbaらは、この Semantic Hashingを類似画像検索に応用し、 LSHよりも高い検索精度を得た。





Weissらが提案した Spectral Hashing (SH)は、グラフの分割問題を応用してバイナリ符号を求める(非特許文献2)。Weissらは、ハッシュ型近似最近傍探索における有効なバイナリ符号を求めるため、(1)新規データのバイナリ符号計算が容易であること (2)わずかなビット数で全データセットを表現すること (3)類似するデータは類似するバイナリ符号となること、の三つの条件を設定した。これら条件を満たすバイナリ符号を求めるため、 Weissらは、以下の最小化問題を考えた。

目的関数:

【数2】




制約条件

【数3】




【数4】




【数5】




ここで、 Wi,j = exp(-||xi - xj||22)であり、式 (1)は、特徴空間の局所的な類似関係をバイナリ符号に反映することを示す。制約条件において、式 (2)は、バイナリ符号が -1と 1からなることを、式 (3)は、各ビットは偏りなく -1もしくは 1を取り得ることを、式 (4)は、異なるビット間は互いに独立であることを表す。 Weissらは、式 (2)の制約条件を緩和することで、グラフラプラシアンの固有ベクトルを求める問題とした。 SHは、 LSH、KLSH、Semantic Hashingなどよりも検索精度が高いことが知られている。





この他に、逐次学習を応用して頑健なバイナリ符号を得る手法、ラベルが付与されたデータを用いてデータの類似・相違を教師する手法、平行移動不変カーネルで表されるデータ間の関係を保持したバイナリ符号を得る手法、ベクトルデータの分布とバイナリ符号の分布によるカルバック・ライブラー情報量が最小となるようにバイナリ符号を求める手法などがある。

産業上の利用分野



本発明はハッシュ関数の変換行列を定める方法、該ハッシュ関数を利用するハッシュ型近似最近傍探索方法、その装置及びそのコンピュータプログラムに関する。

特許請求の範囲 【請求項1】
データベースに含まれる第1のベクトルデータx(n次元)をコンピュータによってバイナリ符号であるy=[y1,y2,・・・yd]、ただし、n>>dに変換処理することにより、バイナリ符号化されたデータによる比較を可能にするハッシュ型近似最近傍探索方法において、下記式(A)~式(C)より前記バイナリ符号yを得る該コンピュータの処理のために、下記ハッシュ関数h(x)に適用する変換行列rを定めるように該コンピュータに処理させる方法であって、
【数6】


ここに、前記バイナリ符号yは次のように表される、
【数7】


【数8】


前記第1のベクトルデータxを前記バイナリ符号yのビット数である前記dの次元に射影したときの第2のベクトルデータhを下記式(D)で規定したとき、
【数9】


ただし、
【数10】


下記式(E)が最小になる変換行列Fを求め、この変換行列Fを式(A)の変換行列rとする、
【数11】


ただし、Wijは前記データベースの第1のベクトルデータxにつき、
【数12】


式(F)を最小とする重みである、ハッシュ関数の変換行列を定めるための処理の方法。

【請求項2】
前記変換行列Fを求める際に前記重みWijを正規化する、請求項1に記載処理の方法。

【請求項3】
前記正規化は、前記データベースにおける第1のベクトルデータxでの近傍の分布を下記式(G)のスコアで定義し、
【数35】


この分布スコアの対角行列D=diag[d1,……,dm] をもとめて、グラフラプラシアン理論に基づき行なう、請求項2に記載の処理の方法。

【請求項4】
原データベースの原データから訓練データを抽出する訓練データ生成部と、 前記訓練データに基づき第1のハッシュ関数を特定するハッシュ関数特定部と、 前記第1のハッシュ関数を用いて前記原データベースの原データをバイナリ符号化するバイナリ符号化部と、 バイナリ符号化された前記原データを保存するバイナリ符号化データ保存部と、を備える検索サーバと、 入力された検索対象データを前記第1のハッシュ関数を用いてバイナリ符号化する第2のバイナリ符号化部を備えるクライアント端末と、 前記クライアント端末の第2のバイナリ符号化部でバイナリ符号化された検索対象データと前記バイナリ符号化された原データとを比較する比較部と、 を備える、ハッシュ型近似最近傍探索装置において、 前記第1のハッシュ関数は請求項1~請求項3にいずれかの方法で定められる、ハッシュ型近似最近傍探索装置。

【請求項5】
ハッシュ型近似最近傍探索装置に用いられる検索サーバであって、 原データベースの原データから訓練データを抽出する訓練データ生成部と、 前記訓練データに基づき第1のハッシュ関数を特定するハッシュ関数特定部と、 前記第1のハッシュ関数を用いて前記原データベースの原データをバイナリ符号化するバイナリ符号化部と、 バイナリ符号化された前記原データを保存するバイナリ符号化データ保存部と、を備え、 前記第1のハッシュ関数は請求項1~請求項3にいずれかの方法で定められる、検索サーバ。

【請求項6】
原データベースの原データから訓練データを抽出する訓練データ生成部と、 前記訓練データを第1のベクトル化方法に基づきベクトル化処理する第1のベクトル化処理部と、 ベクトル化処理された前記訓練データに基づき第1のハッシュ関数を特定するハッシュ関数特定部と、 前記原データを前記第1のベクトル化方法に基づきベクトル化処理する第2のベクトル化処理部と、 前記第1のハッシュ関数を用いて前記ベクトル化処理された原データをバイナリ符号化するバイナリ符号化部と、 バイナリ符号化された前記原データを保存するバイナリ符号化データ保存部と、を備える検索サーバと、 入力された検索対象データを前記第1のベクトル化方法に基づきベクトル化処理する第3のベクトル化処理部と、 前記ベクトル化処理された検索対象データを前記第1のハッシュ関数を用いてバイナリ符号化する第2のバイナリ符号化部を備えるクライアント端末と、 前記クライアント端末の第2のバイナリ符号化部でバイナリ符号化された検索対象データと前記バイナリ符号化された原データとを比較する比較部と、 を備える、ハッシュ型近似最近傍探索装置において、 前記第1のハッシュ関数は請求項1~請求項3にいずれかの方法で定められるハッシュ型近似最近傍探索装置。

【請求項7】
ハッシュ型近似最近傍探索装置に用いられる検索サーバであって、 原データベースの原データから訓練データを抽出する訓練データ生成部と、 前記訓練データを第1のベクトル化方法に基づきベクトル化処理する第1のベクトル化処理部と、 ベクトル化処理された前記訓練データに基づき第1のハッシュ関数を特定するハッシュ関数特定部と、 前記原データを前記第1のベクトル化方法に基づきベクトル化処理する第2のベクトル化処理部と、 前記第1のハッシュ関数を用いて前記ベクトル化処理された原データをバイナリ符号化するバイナリ符号化部と、 バイナリ符号化された前記原データを保存するバイナリ符号化データ保存部と、を備え、 前記第1のハッシュ関数は請求項1~請求項3にいずれかの方法で定められる、検索サーバ。

【請求項8】
請求項1~請求項3のいずれかの方法により定められ変換行列を利用するハッシュ型近似最近傍探索方法であって、前記コンピュータによる処理が、前記変換行列によってハッシュ関数を特定し、ベクトルデータをバイナリ符号に変換し、バイナリ符号化された複数のデータを比較するものであるハッシュ型近似最近傍探索方法。

【請求項9】
請求項1~請求項3のいずれかの方法により定められる変換行列を利用するハッシュ型近似最近傍探索方法であって、前記コンピュータによる処理が、 データベースとして所定の訓練データベースを用いて、前記変換行列によってハッシュ関数を特定するステップと、 特定されたハッシュ関数をテストデータベースに適用し、該テストデータベースのベクトルデータをテストデータバイナリ符号に変換するステップと、 検索対象のベクトルデータへ前記ハッシュ関数を適用して検索対象バイナリ符号を作成するステップと、 該検索対象バイナリ符号を前記テストデータバイナリ符号と比較するステップと、 を備えるハッシュ型近似最近傍探索方法。

【請求項10】
前記データベースとして所定の訓練データベースを用いて、請求項1~請求項3のいずれかの方法により定められた変換行列を備えるハッシュ関数を特定するハッシュ関数特定部と、 特定されたハッシュ関数をテストデータベースに適用し、該テストデータベースのベクトルデータをテストデータバイナリ符号に変換する変換部と、 検索対象のベクトルデータへ前記ハッシュ関数を適用して検索対象バイナリ符号を作成するバイナリ符号作成部と、 該検索対象バイナリ符号を前記テストデータバイナリ符号と比較する比較部と、 を備えるハッシュ型近似最近傍探索装置。

【請求項11】
コンピュータを、 前記データベースとして所定の訓練データベースを用いて、請求項1~請求項3のいずれかの方法により定められた変換行列を備えるハッシュ関数を特定するハッシュ関数特定部と、 特定されたハッシュ関数をテストデータベースに適用し、該テストデータベースのベクトルデータをテストデータバイナリ符号に変換する変換部と、 検索対象のベクトルデータへ前記ハッシュ関数を適用して検索対象バイナリ符号を作成するバイナリ符号作成部と、 該検索対象バイナリ符号を前記テストデータバイナリ符号と比較する比較部と、 を備えるハッシュ型近似最近傍探索装置として機能させるコンピュータプログラム。
国際特許分類(IPC)
画像

※ 画像をクリックすると拡大します。

JP2012547940thum.jpg
出願権利状態 登録
ご興味のある特許について詳しく内容をお知りになりたい方は、下記までお問い合せください。


PAGE TOP

close
close
close
close
close
close
close