Super-Bit LSH今日は、すこし前に読んだSuper-Bit LSH (SB-LSH)という手法を簡単に紹介します。 これは角類似度1に対するランダム射影LSH2の改良版です。 Jianqiu Ji, Jianmin Li, Shuicheng Yany, Bo Zhang, Qi Tianz. Super-Bit Locality-Sensitive Hashing. NIPS 2012. ランダム射影LSHの解説は海野さんのスライド(29-30ページ目)がわかりやすいです。 ランダム射影LSHを使うと、角類似度の不偏推定量が得られます。 Super-Bit LSHではこれをNビットごとにグループ分けして、各グループ内の射影ベクトルを直交させるというものです。 直交化はたとえばGram-Schmidtの直交化法を使います。 こうすると、推定量の分散がただのランダム射影よりも小さくなるということです。 論文
