Locality Sensitive Hashによる類似ベクトル検索を試す

はじめに

類似性が高いベクトルのハッシュ値が近い値になるようなハッシュ関数を使って、
類似するものを高速に検索することができるので、それを試してみた。

Locality Sensitive Hash

類似するデータが高確率で近い値になる(Locality-Sensitive)ハッシュ関数のこと
- 高次元データの次元圧縮を行える
(P1,P2,r,cr)-sensitiveなHash族とは、
- 2つの特徴ベクトルp,qについて(P1>P2)
- ||p-q||P1
- ||p-q||>crならPr[h(p)=h(q)]
- を満たすハッシュ関数h:R^d->U

コサイン類似度に対するLSH

2つのk次元ベクトルu,vについて
- コサイン類似度: u*v / sqrt(|u|*|v|)
d個のk次元のランダムベクトルr_iを考え、ハッシュ関数h_i(u)を
- h_i(u) = 1 (r*u >=0)
- h_i(u) = 0 (r*u < 0)
- と定義する
定理: Pr[h_r(u)=h_r(v)]=1-θ(u,v)/π
- θ(u,v) : uとvの成す角

LSHを使った(近似)類似ベクトル検索

http://www.isi.edu/natural-language/people/hovy/papers/05ACL-clustering.pdf
目的は、n個のベクトルのリストから、コサイン類似度が設定した閾値以上のものを見つけること。

前処理

d個のk次元ランダムベクトルを生成
- 各要素はN(0,1)からサンプリング
全てのベクトルuに対して、d個のビット列からなるハッシュ関数を計算
- コサイン類似度に対するLSHで定義したものを使って、各ビットが0か1になるビット列[h_1(u),h_2(u),...,h_d(u)](=ハッシュ値)を作る
各ビットを並び替えたものをq個準備する
- ビットの並び替え方を保存しておき、クエリ処理時にも使う
- 各ベクトルを並び替えた後の[h_1(u),h_2(u),...,h_d(u)]をハッシュ値としてソートしておく
q個の、並び替え方とソート済みのリストができる

※並び替え方は、π(x) = (a*x+b) mod pで近似できる(a,bは乱数、a,b

クエリ処理

クエリとして、k次元ベクトルxが与えられるとする
d個のビット列からなるハッシュ値を計算
q個の「並び替え方とソート済みリスト」を使って以下を処理する
- 計算したハッシュ値の各ビットを並び替える
- ソートしておいたリストでの位置を見つけて、前後のB個を確認
- 実際に類似度を計算し、条件を満たすものを返す

コード

あえて、密な低次元ベクトルで検索をしてみる。
雑。。

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;

static const double PI = 3.14159265358979323846264338;
//乱数
// 注意: longではなくint(32bit)にすべき
unsigned long xor128(){
  static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
  unsigned long t;
  t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
//[0,1)の一様乱数
// 注意: int_maxぐらいで割るべき
double frand(){
  return xor128()%10000000/static_cast<double>(10000000);
}
//正規乱数
double normal_rand(double mu, double sigma2){
  double sigma = sqrt(sigma2);
  double u1 = frand(), u2 = frand();
  double z1 = sqrt(-2*log(u1)) * cos(2*PI*u2);
  //double z2 = sqrt(-2*log(u1)) * sin(2*PI*u2);
  return mu + sigma*z1;
}

//ソート用
bool operator<(const pair<int,int>& u, const pair<int,int>& v){
  if(u.first == v.first) return u.second < v.second;
  return u.first < v.first;
}

//LSHによる近似検索
class LSHSearch {
  const static int mod = 99991; //任意の素数

  int k, d, p, B;
  vector< pair<int,int> > abset; //シャッフル用
  vector< vector<double> > rndvec; //ランダムベクトル

  vector< vector< pair<int,int> > > dataset; //p個のシャッフルされたソート済みハッシュ値リスト

  //内積
  double dot(const vector<double>& u, const vector<double>& v){
    double ret = 0;
    for(int i=0; i<k; i++){
      ret += u[i] * v[i];
    }
    return ret;
  }

public:
  //コサイン類似度計算
  double cossim(const vector<double>& u, const vector<double>& v){
    double ret = 0;
    double uu = 0, vv = 0;
    for(int i=0; i<k; i++){
      ret += u[i] * v[i];
      uu += u[i] * u[i];
      vv += v[i] * v[i];
    }
    return ret / ( sqrt(uu) * sqrt(vv) );
  }
  

public:
  //k次元ベクトル,dビット,pセット作る,前後Bずつ確認
  LSHSearch(int k_, int d_, int p_, int B_):k(k_),d(d_),p(p_),B(B_){
    //乱数a,bを生成
    for(int i=0; i<p; i++){
      abset.push_back(make_pair<int,int>(xor128()%mod, xor128()%mod));
    }

    //乱数ベクトルを生成
    for(int i=0; i<d; i++){
      vector<double> tmp;
      for(int j=0; j<k; j++){
        tmp.push_back(normal_rand(0.0, 1.0));
      }
      rndvec.push_back(tmp);
    }

    //データセットを初期化
    vector< pair<int,int> > emp;
    for(int i=0; i<p; i++){
      dataset.push_back(emp);
    }
  }

  //データセット作成
  // list : 検索対象のk次元ベクトルのリスト
  void createDataSet(const vector< vector<double> >& list){
    for(int i=0; i<list.size(); i++){
      //ハッシュ値
      int h = 0;
      for(int j=0; j<d; j++){
        h <<= 1;
        if(dot(list[i], rndvec[j])>=0.0){
          h += 1;
        }else{
          h += 0;
        }
      }

      //ランダムに並び替え(の近似計算)
      for(int j=0; j<p; j++){
        int pi = (abset[j].first * h + abset[j].second)%mod;
        dataset[j].push_back(make_pair<int,int>(pi, i));
      }

    }

    //データセットのソート
    for(int i=0; i<p; i++){
      sort(dataset[i].begin(), dataset[i].end());

      /* //ハッシュ値
      cout << i << "=====" << endl;
      for(int j=0; j<dataset[i].size(); j++){
        cout << dataset[i][j].first << endl;
      }
      //*/
    }
  }

  //検索
  // v : 検索したいk次元ベクトル
  // th : コサイン類似度がth以上のものを探す
  // list : 検索対象のk次元ベクトルのリスト
  vector<int> search(const vector<double> v, double th, const vector< vector<double> >& list){
    set<int> ret;

    //ハッシュ値
    int h = 0;
    for(int j=0; j<d; j++){
      h <<= 1;
      if(dot(v, rndvec[j])>=0.0){
        h += 1;
      }else{
        h += 0;
      }
    }
    
    //ランダムに並び替え(の近似計算)
    for(int j=0; j<p; j++){
      int pi = (abset[j].first * h + abset[j].second)%mod;

      //データセットから探す
      //  dataset[j]からpiの位置を探して、前後B個ずつ確認する
      int lb = 0, ub = dataset[j].size();
      while(ub-lb>1){
        int m = (lb+ub)/2;
        if(dataset[j][m].first <= pi) lb = m;
        else ub = m;
      }
      
      //前後B個を確認
      for(int b = -B; b<=B; b++){
        if(0<=lb+b && lb+b < dataset[j].size()){
          int idx = dataset[j][lb+b].second;
          if(cossim(v, list[idx]) >= th){
            ret.insert(idx);
          }
        }
      }
      
      //[別version]前後B個ではなく、同じハッシュ値を持つものをすべて確認
      /*
      while(lb>=0 && dataset[j][lb].first == pi){
        int idx = dataset[j][lb].second;
        if(cossim(v, list[idx]) >= th){
          ret.insert(idx);
        }
        lb--;
      }
      */
    }

    return vector<int>(ret.begin(), ret.end());
  }

};


int main(int argc, char** argv){
  int k = 5; //k次元ベクトル
  int d = 4; //d次元に圧縮
  int p = 1; //p個のシャッフルされたハッシュ値のソート済みリスト
  int B = 50; //リストの前後B個ずつ確認

  LSHSearch lshs(k, d, p, B);

  //ランダムにk次元ベクトルを1000個作る
  vector< vector<double> > list;
  for(int i=0; i<1000; i++){
    vector<double> tmp;
    for(int j=0; j<k; j++){
      tmp.push_back( frand()*2.0-1.0 );
    }
    list.push_back(tmp);
  }

  //検索用のp個のシャッフルされたハッシュ値のソート済みリストを作る
  lshs.createDataSet(list);


  //検索するk次元ベクトルを作る
  vector<double> v;
  for(int i=0; i<k; i++){
    v.push_back( frand()*2.0-1.0 );
  }

  //コサイン類似度が0.9以上のものを検索
  vector<int> res = lshs.search(v, 0.9, list);

  //-------------------------------------------------------------------
  //検索結果とコサイン類似度
  for(int i=0; i<res.size(); i++){
    cout << res[i] << " : " << lshs.cossim(list[res[i]], v) << endl;
  }

  //リストで0.9以上の類似度を持つものを全列挙
  cout << "----" << endl;
  for(int i=0; i<list.size(); i++){
    if(lshs.cossim(list[i], v) >= 0.9){
      cout << i << " : " << lshs.cossim(list[i], v) << endl;
    }
  }

  return 0;
}

結果

1000個の5次元ベクトルをランダムに生成。
検索用のベクトルも同様に生成し、そのベクトルとコサイン類似度が0.9以上のものを探す。

$ ./a.out
494 : 0.922909
495 : 0.947079
841 : 0.92888
----
120 : 0.902769
254 : 0.912192
304 : 0.962826
494 : 0.922909
495 : 0.947079
841 : 0.92888
948 : 0.930417

上が検索されたもの、下がリスト内で0.9以上のもの。3/7個見つけられている。

同じハッシュ値になるデータの個数がかなり多くなってしまい、前後B個程度じゃ見つけられない、ということがおきた。
別バージョンとして、同じハッシュ値を持つものを全て探しにいくと結構拾えた。

やっぱりパラメータd,p,B(とmod)の調整が難しい。疎な高次元ベクトルの場合だと結構ばらけてくれるぽい。

Negative/Positive Thinking