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

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

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5971722号 (P5971722)
登録日 平成28年7月22日(2016.7.22)
発行日 平成28年8月17日(2016.8.17)
発明の名称または考案の名称 ハッシュ関数の変換行列を定める方法、該ハッシュ関数を利用するハッシュ型近似最近傍探索方法、その装置及びそのコンピュータプログラム
国際特許分類 G06F  17/30        (2006.01)
FI G06F 17/30 350C
G06F 17/30 412
請求項の数または発明の数 11
全頁数 16
出願番号 特願2012-547940 (P2012-547940)
出願日 平成23年12月12日(2011.12.12)
国際出願番号 PCT/JP2011/078702
国際公開番号 WO2012/077818
国際公開日 平成24年6月14日(2012.6.14)
優先権出願番号 2010276013
優先日 平成22年12月10日(2010.12.10)
優先権主張国 日本国(JP)
審査請求日 平成26年12月2日(2014.12.2)
特許権者または実用新案権者 【識別番号】304027349
【氏名又は名称】国立大学法人豊橋技術科学大学
発明者または考案者 【氏名】青野 雅樹
【氏名】立間 淳司
個別代理人の代理人 【識別番号】100095577、【弁理士】、【氏名又は名称】小西 富雅
審査官 【審査官】小太刀 慶明
参考文献・文献 特開2003-141160(JP,A)
特開2010-256951(JP,A)
特開2010-277522(JP,A)
古川 修平 他,隣接情報を用いた類似文書検索とリランキング,第1回データ工学と情報マネジメントに関するフォーラム-DEIMフォーラム-論文集,日本,電子情報通信学会データ工学研究専門委員会,2009年 5月 9日,No.A9-2,pp.1-5.,URL,http://db-event.jpn.org/deim2009/proceedings/files/A9-2.pdf
仲野 将 他,線形化拡散写像手法の提案とその文書データへの適用,情報処理学会第72回(平成22年)全国大会講演論文集,日本,社団法人情報処理学会,2010年 3月 8日,Vol.2,No.3W-6,pp.2-465~2-466.
調査した分野 G06F 17/30
特許請求の範囲 【請求項1】
データベースに含まれる第1のベクトルデータx(n次元)をコンピュータによってバイナリ符号であるy=[y1,y2,・・・yd]、ただし、n>>dに変換処理することにより、バイナリ符号化されたデータによる比較を可能にするハッシュ型近似最近傍探索方法において、下記式(A)~式(C)より前記バイナリ符号yを得る該コンピュータの処理のために、下記ハッシュ関数h(x)に適用する変換行列rを定めるように該コンピュータに処理させる方法であって、
【数6】
JP0005971722B2_000036t.gif
ここに、前記バイナリ符号yは次のように表される、
【数7】
JP0005971722B2_000037t.gif
【数8】
JP0005971722B2_000038t.gif
前記第1のベクトルデータxを前記バイナリ符号yのビット数である前記dの次元に射影したときの第2のベクトルデータhを下記式(D)で規定したとき、
【数9】
JP0005971722B2_000039t.gif
ただし、
【数10】
JP0005971722B2_000040t.gif
下記式(E)が最小になる変換行列Fを求め、この変換行列Fを式(A)の変換行列rとする、
【数11】
JP0005971722B2_000041t.gif
ただし、Wijは前記データベースの第1のベクトルデータxにつき、
【数12】
JP0005971722B2_000042t.gif
式(F)を最小とする重みである、ハッシュ関数の変換行列を定めるための処理の方法。
【請求項2】
前記変換行列Fを求める際に前記重みWijを正規化する、請求項1に記載処理の方法。
【請求項3】
前記正規化は、前記データベースにおける第1のベクトルデータxでの近傍の分布を下記式(G)のスコアで定義し、
【数35】
JP0005971722B2_000043t.gif
この分布スコアの対角行列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のいずれかの方法により定められた変換行列を備えるハッシュ関数を特定するハッシュ関数特定部と、 特定されたハッシュ関数をテストデータベースに適用し、該テストデータベースのベクトルデータをテストデータバイナリ符号に変換する変換部と、 検索対象のベクトルデータへ前記ハッシュ関数を適用して検索対象バイナリ符号を作成するバイナリ符号作成部と、 該検索対象バイナリ符号を前記テストデータバイナリ符号と比較する比較部と、 を備えるハッシュ型近似最近傍探索装置として機能させるコンピュータプログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明はハッシュ関数の変換行列を定める方法、該ハッシュ関数を利用するハッシュ型近似最近傍探索方法、その装置及びそのコンピュータプログラムに関する。
【背景技術】
【0002】
現在、インターネット上には、文書、画像、音楽、動画など様々なデータが大量に存在している。これら大量のデータを有効利用するため、大規模データベースを対象とし、高速に検索質問と類似するものを見つけ出す技術が、コンピュータビジョンやテキストマイニングの分野で注目されている。例えば、画像であれば、カメラ付き携帯電話で商品を撮影し、それと見た目が類似した商品を、大量の商品データから瞬時に検索することができる。また、特定の風景画像を検索したい場合に、大規模画像データベースから類似する画像を高速に検索できれば、どこで撮影された画像かを即座に判定することができる。
【0003】
一般的に、文書ベクトルや画像の特徴ベクトルは、数百から数千の高次元なものとなる。高次元特徴ベクトルで、大規模データベースを検索対象とした場合、線形探索では実用的な検索速度を得ることは難しい。この問題に対して、近似最近傍探索という、大規模データベースで高速な検索を実現する技術が注目されている。
近似最近傍探索は、木構造型とハッシュ型(非特許文献1)の二つに大きく分類される。木構造型近似最近傍探索は、特徴空間上に張られる軸の分割を繰り返して木構造を生成し、探索の際に探索範囲を狭めることで高速に探索を行う。探索範囲は、検索クエリとの暫定的な距離と許容誤差で定義される半径による超球で定義されるが、高次元ベクトルデータを対象とした場合に、次元の呪いの影響をうける。ハッシュ型近似最近傍探索は、高次元ベクトルデータを、短いバイナリ符号に変換し、これをハッシュテーブルのキーとすることで、高速に検索を行う。特徴空間上での距離関係をとらえ、類似するベクトルデータ同士では、バイナリ符号間のハミング距離が小さくなるように変換することで、次元の呪いの影響を小さくできる。また、短いバイナリ符号に変換することで、検索インデックスに必要な容量を抑えることもできる。
【0004】
ハッシュ型近似最近傍探索で焦点となるのは、高次元ベクトルデータをバイナリ符号に変換するアルゴリズムである。その目的は、 n次元の m個のベクトルデータ集合 X =[x1, x2,..., x] ∈ Rn × mが与えられた場合に、ハッシュ関数 hを用いて、ベクトルデータ間の類似関係を保持したまま、dビットのバイナリ符号集合 Y =[y1, y2,..., ym] ∈ Bd × m
へと変換することである。
【0005】
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】
JP0005971722B2_000002t.gif

【0006】
また、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よりも高い検索精度を得た。
【0007】
Weissらが提案した Spectral Hashing (SH)は、グラフの分割問題を応用してバイナリ符号を求める(非特許文献2)。Weissらは、ハッシュ型近似最近傍探索における有効なバイナリ符号を求めるため、(1)新規データのバイナリ符号計算が容易であること (2)わずかなビット数で全データセットを表現すること (3)類似するデータは類似するバイナリ符号となること、の三つの条件を設定した。これら条件を満たすバイナリ符号を求めるため、 Weissらは、以下の最小化問題を考えた。
目的関数:
【数2】
JP0005971722B2_000003t.gif
制約条件
【数3】
JP0005971722B2_000004t.gif
【数4】
JP0005971722B2_000005t.gif
【数5】
JP0005971722B2_000006t.gif
ここで、 Wi,j = exp(-||xi - xj||22)であり、式 (1)は、特徴空間の局所的な類似関係をバイナリ符号に反映することを示す。制約条件において、式 (2)は、バイナリ符号が -1と 1からなることを、式 (3)は、各ビットは偏りなく -1もしくは 1を取り得ることを、式 (4)は、異なるビット間は互いに独立であることを表す。 Weissらは、式 (2)の制約条件を緩和することで、グラフラプラシアンの固有ベクトルを求める問題とした。 SHは、 LSH、KLSH、Semantic Hashingなどよりも検索精度が高いことが知られている。
【0008】
この他に、逐次学習を応用して頑健なバイナリ符号を得る手法、ラベルが付与されたデータを用いてデータの類似・相違を教師する手法、平行移動不変カーネルで表されるデータ間の関係を保持したバイナリ符号を得る手法、ベクトルデータの分布とバイナリ符号の分布によるカルバック・ライブラー情報量が最小となるようにバイナリ符号を求める手法などがある。
【先行技術文献】
【0009】

【特許文献1】特開2010-39778号公報
【特許文献2】特開2009-75603号公報
【特許文献3】特開2006-309718号公報
【0010】

【非特許文献1】Charikar,M., Similarity estimation techniques from rounding algorithms, In Proceedings of the thirty-fourth annual ACM symposium on Theory of computing, pp.280-288, 2002.
【非特許文献2】Weiss,Y.,Torralba,A.,Fergus,R., Spectral hashing, In The Naural Information Processing Systems, Vol.21, pp.1753-1760,2008.
【非特許文献3】Wang,B.,Li,Z.,Li,M.,Ma,W-Y., Large-Scale Duplicate Detection for Web Image Search, In Proceedings of IEEE International Conference on Multimedia and Expo, pp.353-356, 2006.
【発明の概要】
【発明が解決しようとする課題】
【0011】
インターネット上に存在するデータの量は拡大の一途をたどっているので、検索サイトに用いられる検索アルゴリズムには更なる精度の向上が期待されている。
そこで本発明者らは、検索サイト用の検索アルゴリズムとして現在利用されている上記LSHに着目し、その改良、即ち検索精度の向上を検討した。
その結果、LSHでは、そこで用いられる下記ハッシュ関数
hi(x) = sign(riT x)
において変換ベクトルrがランダムに決められているため、ベクトルデータをバイナリ符号に変換したとき、もととなるベクトルデータ間の類似関係が充分に維持されないおそれがあると考えた。
非特許文献3には、ベクトルデータが含まれるデータベースの特性を当該変換ベクトルに反映させ、もってバイナリ符号に変換する際にベクトルデータ間の類似関係維持を図ろうとする試みが示されている。
しかしながら非特許文献3に記載の方法は、主成分分析法を利用しているため、非線形構造をなす多次元空間のデータベースの特性を充分に変換ベクトルに反映させることには無理がある。
【課題を解決するための手段】
【0012】
そこで本発明者らは、変換ベクトルにデータベースがなす非線形構造を反映させるべく鋭意検討を重ねた結果、この発明に想到した。
即ち、この発明の第1の局面は次のように規定される。
データベースに含まれる第1のベクトルデータx(n次元)をバイナリ符号であるy=[y1,y2,…yd]、ただし、n>>dに変換するハッシュ型近似最近傍探索方法において、
下記式(A)~式(C)より前記バイナリ符号を得る下記ハッシュ関数h(x)に適用する変換行列rを定める方法であって、
【数6】
JP0005971722B2_000007t.gif
ここに、前記バイナリ符号yは次のように表わされる、
【数7】
JP0005971722B2_000008t.gif
【数8】
JP0005971722B2_000009t.gif
前記第1のベクトルデータxを前記バイナリ符号yのビット数である前記dの次元に射影したときの第2のベクトルデータhを下記式(D)で規定したとき、
【数9】
JP0005971722B2_000010t.gif
ただし、
【数10】
JP0005971722B2_000011t.gif
下記式(E)が最小になる変換行列Fを求め、この変換行列Fを式(A)の変換行列rとする、
【数11】
JP0005971722B2_000012t.gif
ただし、wijは前記データベースの第1のベクトルデータxにつき、
【数12】
JP0005971722B2_000013t.gif
式(F)を最小とする重みである、ハッシュ関数の変換行列を定める方法。
【0013】
第1の局面に規定の発明の基本原理を以下に説明する。
高次元ベクトルデータをバイナリ符号に変換するアルゴリズムの多くが、次元削減のアルゴリズムに基づいている。次元削減の目的は、高次元空間上でベクトルデータがなす、低次元の部分空間を推定することである。近年、全体では非線形構造を成していても、局所的には通常のユークリッド空間と同じ構造をなす、多様体の性質を利用した非線形次元削減手法が幾つか提案されている。その内、Locally Linear Embedding (LLE)は、局所的な範囲で低次元の線形モデルをあてはめ、それらが滑らかに繋がるように全体の多様体を推定する。このLLEによる多様体構造の推定方法を用いて、ベクトルデータがなす非線形な関係をとらえたバイナリ符号を得る。以下、Weissらと同様に、問題の簡単化のため、式(2)の制約条件を緩和する。
【0014】
局所的な範囲で低次元の線形モデルをあてはめるため、それぞれのベクトルデータxiを、近傍のベクトルデータ xj ∈Niを用いて再構成することを考える。これは、以下の再構成誤差を最小化することで表される。
【数13】
JP0005971722B2_000014t.gif
ここで、wijは、再構成する際の重みである。再構成には近傍のベクトルデータを用いるため、
【数14】
JP0005971722B2_000015t.gif
重みの大きさの任意性を解決するためΣj wij = 1 とする。各ベクトルデータでの再構成誤差は、
【数15】
JP0005971722B2_000016t.gif
と表わせる。ここで、 Cjk =(xi - xj)T (xi - xk)とした。この再構成誤差は、ラグランジュ乗数ηiを用いて
【数16】
JP0005971722B2_000017t.gif
となる。極致を求めるため、wijについて偏微分し0とおくことで、以下の線形方程式を解く問題となる。
【数17】
JP0005971722B2_000018t.gif
以上の重みを求める計算については、 de Ridderらや Panらの研究で詳述されている。
【0015】
近傍による再構成の重みwijで表される、それぞれのベクトルデータにおける局所的な関係を、バイナリ符号に反映させるため、Weissらの最小化問題において、式(1)の目的関数を以下のものに置き換える(式(E))。
【数18】
JP0005971722B2_000019t.gif
さらに、新規データのバイナリ符容易に求められるよう、変換行列 F ∈ Rn×dによる線形変換を考える(式D)。
【数19】
JP0005971722B2_000020t.gif
ここで、式 (3)の制約条件を満たすため、平均ベクトル x ̄で引いた。
【数20】
JP0005971722B2_000021t.gif

【0016】
バイナリ符号の集合を H =[h1, ..., hm]と表すと、式 (E)の目的関数は、以下のように表される。
【数21】
JP0005971722B2_000022t.gif
ここで、M =(I - W )(I - W )Tとした。さらに、式 (4)の制約条件は、
【数22】
JP0005971722B2_000023t.gif
となり、式(6)の目的関数の最小化は、
【数23】
JP0005971722B2_000024t.gif
と表わせる。これは、ラグランジュの未定乗数法から、
【数24】
JP0005971722B2_000025t.gif
となるので、Fで偏微分して0としておくことにより、
【数25】
JP0005971722B2_000026t.gif
以下の一般固有値問題へと帰着する。
【数26】
JP0005971722B2_000027t.gif
【数27】
JP0005971722B2_000028t.gif

【0017】
上記において、ベクトルデータhは、ベクトルデータxをバイナリ符号yのビット数であるdの次元に射影したものである。変換行列Fを式(A)の変換行列rへ当てはめる。
上記において、局所的な近傍構造を表す重み Wijを、それぞれのベクトルデータの近傍から求める。しかし、注目しているベクトルデータに対して、近傍が密集して位置するものもあれば、遠く離れて位置するものもある。そこで、この分布の偏りによる影響を軽減するため、各ベクトルデータでの近傍の分布を表すスコアを定義する。
【数28】
JP0005971722B2_000029t.gif
近傍の分布を考慮した変換行列 Fは、分布スコアからなる対角行列 D = diag[d1, ..., dm]により、以下の最小化問題を解くことで得られる。
【数29】
JP0005971722B2_000030t.gif

【0018】
これは、ラグランジュの未定乗数法から、
【数30】
JP0005971722B2_000031t.gif
と表わすことができる。さらに、Xがフルランク行列であれば、 XT Xは正則となることから、
【数31】
JP0005971722B2_000032t.gif
【数32】
JP0005971722B2_000033t.gif
Xがフルランク行列ではない場合は、特異値分解を用いて、行列 Xのランク数 lと等しい次元の部分空間に射影する。
【数33】
JP0005971722B2_000034t.gif
【数34】
JP0005971722B2_000035t.gif

【0019】
上記の処理はいわゆるグラフラプラシアンの理論を用いて、重みWijを正規化したことを意味し、n次空間のベクトルデータxをd次空間への射影するとき、n次空間におけるベクトルデータxの分布の偏りの影響を軽減できる。よって、ベクトルデータ得られた変換行列Fはデータベースの特性をより正確に反映したものとなる。
【図面の簡単な説明】
【0020】
【図1】図1は、この発明のハッシュ型近似最近傍検索システムの構成を示すブロック図である。
【図2】図2は、20-newsgroupsでビット数を8から64まで変化させた場合の、検索結果上位400件における適合率(Precision)を表したグラフである。
【図3】図3は、20-newsgroupsで検索結果の上位件数を変化させた場合の、ビット数64における再現率 (Recall)を表したグラフである。
【図4】図4は、20-newsgroupsにおける再現率と適合率を表したグラフである。
【図5】図5は、CIFAR-10でビット数を8から64まで変化させた場合の、検索結果上位1,000件における適合率(Precision)を表したグラフである。
【図6】図6は、 CIFAR-10で検索結果の上位件数変化させた場合の、ビット数 64における再現率 (Recall)を表したグラフである。
【図7】図7は、 CIFAR-10における再現率と適合率を表したグラフである。
【図8】図8は、CIFAR-10で、SHとNSHによる 32ビットのバイナリ符号を用いた、自動車の画像での検索結果上位20件を並べたものである。
【図9】図9は、実施例のハッシュ型近時最近傍探索装置を示すブロック図である。
【発明を実施するための形態】
【0021】
このようにして定められた変換行列を有するハッシュ関数を用いてハッシュ型近似最近傍検索を行なうシステム1を図1に示す。
図1において、訓練データベース3、テストデータベース13、テストデータバイナリ符号データベース19はサーバのメモリ装置の所定の領域が対応される。
訓練データベース3のデータはベクトル化処理部5において所定の方法でベクトル化される。
ハッシュ関数特定部7は、ベクトル化された訓練データベース3のデータ(第1のベクトルデータx)の一部又は全部を用いて、既述の処理を行ない、変換ベクトルFを特定し、もって、第1のベクトルデータxをバイナリ符号化するハッシュ関数を特定する。

【0022】
テストデータベース13のデータは、ベクトル化処理部15において、ベクトル化処理部5と同一の方法でベクトル化される。
バイナリ符号化部17は、ハッシュ関数特定部7で特定されたハッシュ関数を用いてベクトル化されたテストデータベースのデータの一部又は全部をバイナリ符号に変換し、テストデータバイナリ符号データベース19に保存する。

【0023】
クライアントPCが検索対象特定部20に対応し、この検索対象特定部20においてユーザが検索対象を特定する。特定された検索対象はベクトル化処理部21においてベクトル化処理される。このベクトル化処理の方法は、既述のベクトル化処理部5において、訓練データベース3のデータを第1のベクトルデータに変換したベクトル化処理法と同一である。
このようにしてベクトル化された検索対象はバイナリ符号化部23において、ハッシュ関数特定部7で特定されたハッシュ関数を用いてバイナリ符号化される。比較部25は、検索対象のバイナリ符号をテストデータバイナリ符号データベース19に保存されているテストデータバイナリ符号と比較し、例えば、検索対象のバイナリ符号に対する距離が所定の閾値以内のものを、近い順に出力する。

【0024】
この発明の探索方法を評価するために、ベンチマークに20-newsgroupsと CIFAR-10を用いて、従来手法との比較実験を行った。従来手法には、Locality-Sensitive Hashing (LSH)、Kernelized Locality-Sensitive Hashing (KLSH)、Spectral Hashing (SH)を選択した。この内、アルゴリズム中に乱数生成を含むLSHとKLSHについては、5回実行して平均をとった。
20-newsgroupsは、Usenet newsgroupから取得した18,845件のニュースグループの文書からなる。各文書は、異なる20個のニュースグループのいずれかに分類され、11,314件が訓練データセットとして、7,531件がテストデータとして与えられる。各アルゴリズムの訓練には、訓練データセットからランダムに選択した5,000件を用いた。実験では、前処理として単語のステミングとストップワードの除去を行ったのち、文書頻度の大きいほうから 2,000語を選択し、tf-idfにより重み付けを行った文書ベクトルを作成した。本発明のパラメータは、事前実験により求めた最適値、近傍数 k = 205、分布スコアのガウスカーネル幅 λ =4.0を用いた。

【0025】
図1は、20-newsgroupsでビット数を8から64まで変化させた場合の、検索結果上位400件における適合率(Precision)を表したグラフである。全てのビット数で、本件発明(NSH)が最も大きな適合率となっている。図3は、20-newsgroupsで検索結果の上位件数を変化させた場合の、ビット数64における再現率 (Recall)を表したグラフである。全ての上位件数で、本件発明(NSH)が最も大きな再現率となっているのがわかる。図4は、20-newsgroupsにおける再現率と適合率を表したグラフである。曲線が右上に伸びるほど検索精度が高いと言える。本件発明(NSH)が、従来手法と比較して、正確性・網羅性ともに高いことがわかる。

【0026】
20-newsgroupsは、20個のカテゴリに分類されているが、それらは、コンピュータの話題やスポーツの話題など、大きく分類することもできる。これらは高次元の文書ベクトル空間で、類似した話題のものが集まりながらも、粗密をなして複雑な構造を成していると予想する。ベクトルデータの非線形構造を推定し、分布の偏りを重みにより考慮する本件発明(NSH)は、従来手法と比較して、この複雑な文書ベクトル空間を正しくとらえられたと考える。

【0027】
CIFAR-10は、飛行機や自動車、イヌなどの 10種類のラベルが付与されクラス分けされた、60,000個の 32 × 32のカラー画像が含まれており、50,000個が訓練データセットとして、10,000個がテストデータセットとして与えられる。各アルゴリズムの訓練には、訓練データセットからランダムに選択した 5,000個を用いた。実験では、RGBごとに 4×4領域 6方向 4スケールで 3×4×4×6×4=1, 152次元の GIST特徴ベクトルを抽出し、それをバイナリ符号に変換した。本件発明(NSH)のパラメータは、事前実験により求めた最適値、近傍数 k = 90、分布スコアのガウスカーネル幅 λ =0.5を用いた。

【0028】
図5は、CIFAR-10でビット数を8から64まで変化させた場合の、検索結果上位1,000件における適合率(Precision)を表したグラフである。全てのビット数で、本件発明(NSH)が最も大きな適合率となっている。図6は、 CIFAR-10で検索結果の上位件数変化させた場合の、ビット数 64における再現率 (Recall)を表したグラフである。全ての上位件数で、本件発明(NSH)が最も大きな再現率となっているのがわかる。図7は、 CIFAR-10における再現率と適合率を表したグラフである。本件発明(NSH)が、従来手法と比較して、正確性・網羅性ともに高いことがわかる。

【0029】
CIFAR-10には、飛行機や自動車などからなる乗り物画像と、イヌやシカなどからなる生物画像に、大きく分けられる。しかし、画像全体では特定の色が多く使用されている、背景が類似しているなどの要因で、特徴空間上では、乗り物画像と生物画像がはっきりと区別されることなく、粗密をなして分布していると予想する。分布の偏りを重みにより抑えつつ、ベクトルデータがなす非線形な構造を推定する NSHは、この特徴空間上の複雑なデータ関係を、従来手法と比較して正しくとらえられたと考える。

【0030】
図8は、CIFAR-10で、SHとNSHによる 32ビットのバイナリ符号を用いた、自動車の画像での検索結果上位20件を並べたものである。左上端の画像が検索質問画像であり、正解の画像は緑色の枠で、不正解の画像は赤色の枠で囲んだ。SHと比較して、本件発明(NSH)では適合画像が多く、検索精度が高いことがわかる。

【0031】
本件発明(NSH)は、特徴空間上の局所的な近傍構造に基づいて、ベクトルデータがなす非線形構造をとらえた短いバイナリ符号を得る。文書データベンチマーク20-newsgroupsと画像データベンチマーク CIFAR-10を用いた比較実験から、 Spectral Hashingなどの従来手法よりも高い検索精度を得られることが確認できた。

【0032】
実施例のハッシュ型近似近最傍探索装置100を図9に示す。
この装置100は、検索サーバ101とクライアント端末200がネットワークN1を介して接続されている。任意の数のクライアント端末200をネットワークN1へ接続可能で、ネットワークN1はインターネット300へ開いていてもよい。

【0033】
検索サーバ101はデータ保存部110とデータ処理部120とを備える。データ保存部110は原データ取得・保存部111を備える。この原データ取得・保存部111は被検索対象となるデータを、インターネット300を介して外部のデータベースから取得し、保存する。外部のデータベースは特定のデータが整理保存された商用、または検索用のデータベースはもとより、法人若しくは個人が運営するホームページ、ブログ、ツイッター等も含まれるものとする。
訓練データ抽出・更新部113は、原データ取得・保存部111に保存されたデータから無作為にデータを抽出し、訓練データとする。抽出するデータ数は特に限定されるものではないが、既述の試験例に準じて5000個程度とすることが好ましい。なお、この訓練データは周期的に、若しくは任意のタイミングで更新することが好ましい。

【0034】
ベクトル化処理部121及びハッシュ関数特定部123の動作は、図1のベクトル化処理部5及びハッシュ関数特定部7と同じである。即ち、訓練データ抽出・更新部121で抽出されたデータを特徴量次元削減法等の汎用的な手法(第1のベクトル化方法)でベクトル化処理し、ハッシュ関数特定部123において、本発明の手法に従いハッシュ関数(第1のハッシュ関数)を特定する。
ベクトル化処理部121は原データ取得・保存部111のデータの全部をまたは所定のルールで選択されたその一部を訓練データと同様にベクトル化処理する。ベクトル化処理され原データは、バイナリ符号化部125においてバイナリ符号化データに次元削減される(前処理130)。このとき、ハッシュ関数特定部123において特定されたハッシュ関数が利用される。バイナリ符号化されたデータはバイナリ符号化データ保存部115に保存される。

【0035】
クライアント端末200において、検索対象となるデータが入力部210で指定される。指定されたデータはベクトル化処理部221において、検索サーバ101のベクトル化処理部121と同一の方法によりベクトル化される。バイナリ符号化部223には、検索サーバ101のハッシュ関数特定部123で特定されたハッシュ関数が提供され、ベクトル化された検索対象データをバイナリ符号化する。このようにしてバイナリ符号化された検索対象データは検索サーバ101の比較部127へ送られる。比較部127はバイナリ符号化された検索対象データとバイナリ符号化データ保存部115に保存されているバイナリ符号化された原データとを比較し、所定のルールに従い近似するデータを抽出する。

【0036】
比較部127で抽出されたデータはクライアント端末200の出力部230へ送られ、ここで出力される。なお、出力部230はバイナリ符号化されたデータをデコード(逆ハッシュ関数処理、逆ベクトル処理)し、原データの状態で表示できる。
この比較部を端末側に配置することができる。また、比較部を、検索サーバ及び端末と独立して設置することもできる。
【符号の説明】
【0037】
1 ハッシュ型近似最近傍検索システム
3、13、19データベース
5、15、21 ベクトル化処理部
7 ハッシュ関数特定部
17、23 バイナリ符号化部
25 比較部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8