学習
AIと機械学習

ローカル感度ハッシング (L.S.H.)：包括的ガイド

Mar 30, 20241 分で読めます

ローカルセンシティビティハッシング（LSH）は、大規模で高次元のデータセットの複雑さに対処し、類似検索とデータ検索のプロセスを合理化するための極めて重要な技術である。

シリーズ全体を読む

ビッグデータと機械学習の時代において、大規模で高次元のデータセットから最近傍や類似のアイテムを効率的に見つけることは、多くのアプリケーションにおける基本的な課題である。例えば、Spotifyのような音楽ストリーミングサービス。パーソナライズされた楽曲推薦を提供するためには、数百万曲の膨大なライブラリから、ユーザーの好みに最も近い楽曲を素早く特定する必要がある。これは高次元の近似最近傍探索問題である。

リニアスキャン、空間分割ツリー法、ハッシュテーブルのような伝統的な手法は、次元数やデータ点数が増えるにつれて、計算量が膨大になる。そこで、Locality Sensitive Hashing (LSH)と呼ばれるアプローチや、時にはハッシュベースのインデックスが登場する。LSHは近似的な手法であり、類似したデータポイントを高い確率で同じバケットや場所にインテリジェントにマッピングすることで、高次元での類似性探索の効率を劇的に向上させることができる。これにより、データセット全体と網羅的に比較する代わりに、候補の小さなサブセットのみを探索することができます。

高次元データにおける類似検索の本質と課題

類似度またはベクトル類似度検索は、情報検索やデータ駆動型アプリケーションにおける手法の一つである。その目的は、与えられたクエリベクトルに似たアイテムやデータ点を、高次元空間における空間的距離を比較することによって特定することである。

この技術は、数多くのユースケースで活躍している。例えば、電子商取引では、類似検索は商品推薦エンジンに力を与え、顧客の嗜好に沿った選択肢を提供し、それによってショッピング体験を豊かにする。マルチメディア・サービスでは、特定のパターンやテーマと共鳴する画像、ビデオ、音楽を検索し、コンテンツの発見可能性とユーザー・エンゲージメントを高めることができる。しかし、類似性検索は、特に大規模で高次元のデータセットを扱う上で、大きな計算上の課題がある。従来のブルートフォース手法は、各データポイントと他のすべてのポイントを比較するが、特にビッグデータにおいては、2次関数的な時間複雑性のため、実用的でないほど時間がかかる。その結果、網羅的なペアワイズ比較を必要とせず、類似アイテムを迅速に特定し、大規模データセットにおける検索プロセスを効率化する効率的なアプローチが必要となる。Locality Sensitive Hashing (LSH)は、類似入力に対するハッシュ値の衝突の可能性を高め、それらをハッシュビンにグループ化し、類似検索の効率を向上させることでこれに対処する。

Locality-Sensitive Hashing (LSH) とは?

Locality-Sensitive Hashing (LSH)は1998年にIndyk-Motwaniによって発表された、近似最近傍(ANN)検索で使用される技術で、類似検索の効率を支え、高速化する。各データ点の対応付けに主眼を置く従来のハッシュとは異なり、LSHは類似データ点をグループ化する。これは "局所性感度 "によって実現され、元のデータ空間で近い点が同じ場所（"バケット "とも呼ばれる）にあることを保証する。

LSH vs 通常のハッシング](https://assets.zilliz.com/LSH_vs_Regular_Hashing_b8bd08a337.png)

LSHは複数のハッシュ関数を用いてデータセット間で類似したデータタイプをグループ化するため、類似検索は迅速に絞り込まれる。これは、高次元空間でより近くにある関連しそうなデータポイントに焦点を当てることで、検索を高速化する。ランダムなハッシュ関数は、様々なデータセットで一貫した性能を保証する上で重要な役割を果たす。ランダムに選ばれたハッシュ関数は、確率的な保証をすべてのデータセットに等しく適用することで性能を向上させる。このアプローチは、レコメンダーシステムの最近傍探索、重複検出などのアプリケーションに有用である。

LSH の仕組み

ローカルセンシティビティハッシングは、3つの主要なステップで動作します：**このプロセスでは、同じハッシュコードを持つデータポイントはハッシュバケットにまとめられ、共有されたハッシュコードに基づいて類似のアイテムを素早く見つけ、調べることができるため、効率的なクエリが容易になる。

LSHアルゴリズムの主要ステップ](https://assets.zilliz.com/The_key_steps_of_an_LSH_algorithm_35385d105e.png)

シングリング

このステップでは、文書を長さkの文字の集合（k-シングルスまたはk-グラムとも呼ばれる）に変換することに重点を置く。この変換により、Jaccard類似度のような集合類似度メトリクスに基づいて比較する文書を表現することができる。

ミニハッシュ

この技法は、Minhashシグネチャを割り当てて比較することで、2つのデータセットの類似性を調査する。署名は、文書の内容の本質を短い形式で捉えるため、これらのセットを比較するために使用される。これは、Jaccardインデックスが使用されるステップである。2つの集合のJaccardインデックスは、共通要素の数をすべての要素の長さで割ったものである。

LSH テクニック

このステップでは、類似した項目をクラスタリングします。ランダム投影は、点の集合の次元を小さくするために使用される技法です。LSH 手法では、複数のランダム投影関数を使用して、文書の署名を低次元空間にマッピングする。ランダム投影は、類似した文書と署名が同じバケツにマッピングされるように設計されているため、これでプロセスは終了する。類似文書は同じハッシュ値にマップされる可能性が高く、効率的なクエリが容易になる。

LSH の実装

LSHを実装するには、以下のコード・スニペットにあるいくつかのステップを使うことができる。

高次元空間で単一のハッシュ関数を使用すると、柔軟性に欠け、近似近傍を特定する性能が低下する可能性があります。その代わりに、複数のハッシュ関数を利用することで、類似アイテムの検索精度を向上させることができます。

以下のライブラリをインクルードすることから始めてください。

python npとしてnumpyをインポートする。


これが終わったら、ハッシュ関数を定義する。

python
def hash_function(datapoint, random_vector)：
  """
  データポイントをランダムな射影ベクトルを使ってハッシュします。


  引数
      datapoint：データポイントを表す NumPy の配列。
      random_vector：ランダムな射影ベクトルを表す NumPy の配列。


  戻り値
      1ビットのハッシュ値（0または1）。
  """
  射影 = np.dot(datapoint, random_vector)
  projection >= 0 なら 1 を返す。

この関数は、データポイントとランダムな射影ベクトルを入力とします。両者の内積を計算し、射影が負でなければ 1 を返します。この処理により、データポイントとランダムベクタの関係に応じた1ビットのハッシュ値が生成される。

ランダムな射影行列を生成する。

def generate_random_matrix(num_projections, data_dim)：
/*
  指定した次元のランダムな射影行列を生成します．


  引数
      num_projections：生成するランダムな射影ベクトルの数.
      data_dim：データポイントの次元数.


  戻り値
      ランダムな射影行列を表す NumPy の配列。
*/
  return np.random.randn(num_projections, data_dim)

具体的に、この関数の役割について説明しよう。 num_projectionsはランダムな射影ベクトルをいくつ作成したいかを示す整数で、data_dim` はデータポイントの次元数を示す別の整数です。

全体として、この関数は各行がランダムな射影ベクトルである行列を生成し、高次元のデータポイントを低次元の空間に射影するために使用することができます。

ローカルセンシティブハッシングの操作を開始します。

def lsh_hash(datapoint, random_matrix)：
  """
  複数のランダムな射影を用いてデータポイントをハッシュします。


  引数
      datapoint：データポイントを表す NumPy の配列。
      random_matrix：ランダムな射影行列を表す NumPy の配列.


  戻り値
      ハッシュ値のリスト（各ランダム射影ベクトルに対して1つずつ）。
  """
  ハッシュ値 = [].
  for random_vector in random_matrix：
    hash_values.append(hash_function(datapoint, random_vector))
  return hash_values

ish_hash関数は、LSHプロセスのコアステップである、複数のランダムプロジェクションを使用してデータポイントをハッシュします。最初の行には NumPy の配列datapointとrandom_matrix` が含まれており、それぞれハッシュされるデータポイントとハッシュのためのランダムな射影行列を表しています。

処理のステップに進むと、初期化ステップが hash_values によって実行され、生成されたハッシュ値を格納するための空のリストが作成される。

続いて、ランダムな射影ベクトルによる反復処理が行われる。random_matrix は各行をループし、random_vector は datapoint と random_vector を引数として hash_function を呼び出す。

戻り値は hash_values リストに格納され、各ランダムベクタのハッシュ値が格納される。

``python

データポイントのサンプル

datapoint = np.array([1, 2, 3])

ランダムな投影の数

num_projections = 2

データポイントの次元数

data_dim = len(datapoint)

ランダムな射影行列を生成

random_matrix = generate_random_matrix(num_projections, data_dim) # ランダムな射影行列を生成する．

データポイントをハッシュする

ハッシュ値 = lsh_hash(datapoint, random_matrix)

ハッシュ値を表示する

print("LSH ハッシュ:", hash_values)

このコードスニペットはサンプルデータ点を生成します。ランダムな射影の数とデータの次元数を定義し、ランダムな射影行列を生成し、データ点をハッシュし、ハッシュ値を1と0で表示します。

## LSH のアプリケーションと使用例

LSHは効果的かつ効率的に類似検索を行うように設計されており、様々な分野で応用されている。
最も応用されている使用例のひとつは、計算生物学、特に遺伝子やタンパク質の配列解析である。これは、LSHがゲノム[データベース](https://zilliz.com/glossary/ai-database)の類似遺伝子発現の同定に役立つからである。特に遺伝子発現データは高次元であることが多いからである。

LSH関数は、データ間の類似性を維持しながら、高次元の画像データを低次の表現にマップする。これにより、クエリ画像に類似した画像を高速に検索することができる。これは、ユーザーが特定のビジュアルを要求するストックフォトサービスや、類似症例を見つけることで診断に役立つ可能性がある医療画像分析などに適用される。また、画像検索アプリケーションにおけるハッシュ技術や圧縮性能も向上している。LSHは盗作検出ソフトウェアにも使われている。文書間の類似性を特定するのに役立ち、多くの場合パーセンテージで表示され、似ている部分が強調表示される。LSHは他にも、ビデオ検索、ソーシャルネットワーク分析、推薦システム、データマイニングなどにも応用されており、これらはすべて、データセット間の類似性を発見する能力のおかげである。

## 局所性ハッシュの概要

局所感度ハッシング（LSH）は、大規模で高次元のデータセットの複雑性に対処し、類似検索とデータ検索のプロセスを合理化するための極めて重要な技術である。類似したデータポイントを効率的に縮小された次元の検索空間内の同じ「バケット」にマッピングするその能力は、様々な分野で非常に貴重なツールとなっている。電子商取引におけるレコメンデーション・システムから、計算生物学における高度な研究の促進まで、検索効率と精度の向上におけるLSHの役割は否定できない。

article.updateAt