コサイン距離ベースのLSHをRubyで

参考文献:Web+DB press vol.49 レコメンド特集のPart3など。

アルゴリズムの概要

詳細(特に数学的な)はぐぐれ。

モチベーションとしては、高次元における近傍点探索を高速で行いたい。まじめにやるとどう工夫しても計算量がすごいことになるので、近似で。
どうするかというと、「距離が近いと同じような値になるハッシュ関数」を使う。あるベクトルの近傍を求めたい場合、そのベクトルのハッシュと同じ(もしくは近い)値のハッシュを持つベクトルをテーブルから引いてきて返す。計算量がどうなるかはややこしいけど、とりあえず全部探すよりは速い。

で、どういう関数をハッシュとするのか。これは距離の定義によって異なる。ハミング距離、コサイン距離、ユークリッド距離などにはそういった関数の存在が知られている。
コサイン距離の場合、ランダムなベクトルをいくつか用意して、入力されたベクトルがそれらと似ているか(相関度>0か)によって0/1の列を作ってハッシュとする。近いベクトル同士は似たベクトルもだいたいおなじなので、まあそれっぽくはある(数学的詳細は略)。

探索時には、対象となるベクトルのハッシュを求める→そのハッシュに近い値を持つバケツから候補ベクトルをもってくる→距離でソートして足きり。
ハッシュ値0101は0100や1101と似てる。全部列挙するのは残念。ビットの順序をランダムにシャッフルしてソートしてから近いのを取り出す操作を複数回行う。

基準となるベクトルの数をいくつにするのかとか探索時に何回試行するのかとかで精度と計算量をコントロールできる。私はどう決めればいいのかよくわからないですけど。まあ多ければ多いほど正確で遅くなるよね。

出力の精度

出力を実際の順位と比較してみる。
ベクトルの長さは40、サンプル数は10000．
fullはO(n^2)の全探索。lshはLSHによる近似解。

# test.rb sample
preparing vectors(dim=40,N=10000)
constructing LSH index
      user     system      total        real
  5.687000   0.015000   5.702000 (  5.703000)
====================================================
full:
[[0, 0.581864900382649],
 [1, 0.574474091288696],
 [2, 0.523016426961361],
 [3, 0.499381700218387],
 [4, 0.486891924653849],
 [5, 0.473448941861435],
 [6, 0.462915299959355],
 [7, 0.458705998000323],
 [8, 0.450913275426321],
 [9, 0.449166354628291]]
lsh:
[[18, 0.437988633765385],
 [22, 0.425749431997503],
 [53, 0.390452490928918],
 [60, 0.38346026175299],
 [117, 0.347519319663936],
 [118, 0.347510046229593],
 [132, 0.341924602491841],
 [145, 0.337067156923535],
 [178, 0.326775842196073],
 [179, 0.326516411304021]]
 (以下略)

まあそれっぽい要素がとれてるんじゃないですかね(精度低いのはおいといて)

速度

N=1000

# test.rb bench
preparing vectors(dim=40,N=1000)
constructing LSH index
      user     system      total        real
  0.547000   0.000000   0.547000 (  0.562000)
listing 100 NNs with full scan(100 times)
      user     system      total        real
 16.078000   0.000000  16.078000 ( 16.094000)
listing 100 NNs with lsh(100 times)
      user     system      total        real
 10.062000   0.032000  10.094000 ( 10.173000)

N=5000

# test.rb bench
preparing vectors(dim=40,N=5000)
constructing LSH index
      user     system      total        real
  2.907000   0.000000   2.907000 (  2.985000)
listing 100 NNs with full scan(100 times)
      user     system      total        real
 88.984000   0.016000  89.000000 ( 89.806000)
listing 100 NNs with lsh(100 times)
      user     system      total        real
 17.656000   0.015000  17.671000 ( 17.830000)

N=10000

# test.rb bench
preparing vectors(dim=40,N=10000)
constructing LSH index
      user     system      total        real
  5.687000   0.000000   5.687000 (  5.688000)
listing 100 NNs with full scan(100 times)
      user     system      total        real
181.094000   0.032000 181.126000 (181.891000)
listing 100 NNs with lsh(100 times)
      user     system      total        real
 21.641000   0.000000  21.641000 ( 21.657000)

まあなるほど。

ところでLSHは速度と精度のトレードオフをわりとかんたんに制御できるのがいいかなーとおもいました。
まだパラメータをどう決めるのかよくわかってないけど。

ソース

# lsh.rb
require 'pp'
module LSH
  class Cosine
    def initialize(dim,l,&accessor)
      @dim=dim
      @accessor=accessor
      @vectors=gen_vectors(dim,l)
      @items=[]
      @l=l
      reflesh_index
    end

    def gen_vectors(dim,l)
      (0...l).map{
        (0...dim).map{ -1+rand*2 }
      }
    end

    def add(item)
      @items.push item
    end

    def nears(item,n)
      vec=@accessor.call(item)
      h=hash_of(vec)
      p=7349
      items_per_bucket=@items.size.to_f/@buckets.size
      w=(n/items_per_bucket).to_i
      candidates=[]
      5.times {
        a=1+rand(p-1)
        b=rand(p)
        (((h-w) % @buckets.length)..((h+w) % @buckets.length)).each{|i|
          candidates.push @buckets[shuffle(i,a,b,p)]
        }
      }
      return candidates.flatten(1).uniq{|x|x.id}.sort_by{|x|-self.class.sim(vec,@accessor.call(x))}[0...n]
    end

    def shuffle(h,a,b,p)
      return (a*h+b) % p % @buckets.length
    end

    def reflesh_index
      @buckets=(0...2**@l).map{|i| []}
      @items.each{|item|
        h=hash_of(@accessor.call(item))
        @buckets[h].push item
      }
    end

    def hash_of(item_vec)
      @vectors.inject(0){|res,vec| res*2+(self.class.posi_sim?(item_vec,vec) ? 1 : 0)}
    end

    def self.dist(v_a,v_b)
      1.0-dist(v_a,v_b)
    end

    def self.posi_sim?(v_a,v_b)
      a=0.0
      (0...v_a.size).each{|i|
        a+=v_a[i]*v_b[i]
      }
      return a > 0
    end

    def self.sim(v_a,v_b)
      a=0.0
      b=0.0
      c=0.0
      (0...v_a.size).each{|i|
        ia=v_a[i]
        ib=v_b[i]
        a+=ia*ib
        b+=ia*ia
        c+=ib*ib
      }
      return a/(Math.sqrt(b)*Math.sqrt(c))
    end
  end
end

# test.rb
require 'benchmark'
require 'pp'

require File.join(File.dirname(__FILE__),'lsh.rb')

Vec=Struct.new(:id,:vec)

## ベクトルの次元
DIM=40
## ベクトルの個数
N=10000
## LSHのアレ
L=7

## ベンチマーク時の繰り返し数
BENCH_LOOP=100
## ベンチマーク時の近傍取得数
BENCH_NN_COUNT=100

def gen_vecs(dim,n)
  (0...n).map{|i|
    Vec.new(i,(0...dim).map{-1+rand*2})
  }
end

def get_nears(v,vecs,n)
  sort_by_sim(v,vecs)[0...n]
end
def sort_by_sim(v,vecs)
  vecs.sort_by{|vec| -LSH::Cosine.sim(v.vec,vec.vec) }
end

def prepare
  puts "preparing vectors(dim=#{DIM},N=#{N})"
  @vecs=gen_vecs(DIM,N)

  @lsh=LSH::Cosine.new(DIM,L) {|item| item.vec }

  puts 'constructing LSH index'
  puts Benchmark::CAPTION
  puts Benchmark.measure {
    @vecs.each{|v| @lsh.add v}
    @lsh.reflesh_index
  }
end

case ARGV.first
when 'bench'
  prepare
  puts "listing #{BENCH_NN_COUNT} NNs with full scan(#{BENCH_LOOP} times)"
  puts Benchmark::CAPTION
  puts Benchmark.measure {
    BENCH_LOOP.times { nears=get_nears(@vecs.choice,@vecs,BENCH_NN_COUNT) }
  }
  puts "listing #{BENCH_NN_COUNT} NNs with lsh(#{BENCH_LOOP} times)"
  puts Benchmark::CAPTION
  puts Benchmark.measure {
    BENCH_LOOP.times { nears=@lsh.nears(@vecs.choice,BENCH_NN_COUNT) }
  }
when 'sample'
  prepare
  gen_vecs(DIM,3).each{|target|
    puts '===================================================='
    puts 'full:'
    list_with_rank=sort_by_sim(target,@vecs).to_enum.with_index.to_a
    pp list_with_rank[0...10].map{|v,i|[i,LSH::Cosine.sim(target.vec,v.vec)]}
    puts 'lsh:'
    pp @lsh.nears(target,10).map{|v|[list_with_rank.find{|x|v.id==x[0].id}[1],LSH::Cosine.sim(target.vec,v.vec)]}
  }
when 'indexing'
  prepare
else 
  puts <<EOS
usage: #{$0} bench|sample
EOS
end