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の直交化法を使います。 こうすると、推定量の分散がただのランダム射影よりも小さくなるということです。 論文
大規模データのマイニング - 共立出版
ウェブやインターネットコマースの隆盛によって、とてつもなく巨大なデータセットが出現し、そして、データマイニングによってそれらから情報が抽出されている。 巨大なデータに対するマイニングにおいては、従来から知られているアルゴリズムがそのままでは機能しないことが多い。巨大なデータを扱う上でこれまでとは違った処理戦略や技法が必要となる。 本書はデータマイニングにおいて重要な問題の解決に使われてきており、さらに巨大なデータセットに対しても使用できる実用的なアルゴリズムを、データベースやウェブ技術の分野で著名な原著者が解説する。 まず、データマイニングの本質や、データマイニングがどのように扱われているかを概観する。次に、今後非常に大量のデータの解析を行う際に、クラウドコンピューティングとともに重要視されると考えられ、この後の章の議論に必須のものとなるマップレデュースを解説する。その後、類似するアイテム
GoogleNewsのレコメンドの中身 - UMEko Branding
先日、全体ゼミで発表したときの内容ですが、ここにまとめときます。。GoogleNewsのレコメンドの中身を追った論文の要約です。少し前の全体ゼミで用いた資料です。ソース：Abhinandan Das,Mayur Datar,Ashutosh Garg,Shyam Rajaram,"Google News Personalization: Scalable OnlineCollaborative Filtering",WWW2007不勉強な個所が多々ありますので、誤っている箇所等ありましたら、是非ご指摘ください。 個人的には、最近のモデルベースの手法の勉強・おさらいという意味で用いているので、GoogleNews独自の拡張なり実装の部分の内容が省かれている場合があります。また、データ構造やMapReduceを用いた計算の仕組みの部分は、ここでは省略しています。。一応、 全体像 ・LSH(Lo
Locality Sensitive Hashによる類似ベクトル検索を試す - Negative/Positive Thinking
はじめに 類似性が高いベクトルのハッシュ値が近い値になるようなハッシュ関数を使って、 類似するものを高速に検索することができるので、それを試してみた。 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)
Stanford CS345A: Data Mining
Handouts: 1/5: Introduction Introduction [slides] [reading] 1/7: MapReduce MapReduce [slides] [reading] 1/12: Recommendation System Recommendation System [slides] [reading] 1/14: Near Neighbor Search in High Dimensional Data Near Neighbor Search in High Dimensional Data [slides] [reading] 1/19: Locality Sensitive Hashing (LSH) Locality Sensitive Hashing (LSH) [slides] [reading] 1/21: Structure of
乱択アルゴリズムと自然言語処理: Locality Sensitive Hashing を用いた 高速な名詞クラスタリング
Company Logo 乱択アルゴリズムと自然言語処理: Locality Sensitive Hashing を用いた 高速な名詞クラスタリング Randomized Algorithms and NLP: Using Locality Sensitive Hash Functions for High Speed Noun Clustering D. Ravichandran, P. Pantel, and E. Hovy (ACL 2005) 読み⼿: 岡崎直観 Company Logo この論文について ⼿法とその背景理論がすごく興味深い – 他にもいろいろ使えそう 乱択アルゴリズムの雰囲気が味わえる – ランダムが織りなす不思議な世界 すぐれた実装⽅法を⽰している – 誰でも簡単に実装できる 2005年の研究だが，いまだに⾊褪せてはいない – 画像類似検索でLo
Hadoop Streaming で Locality-Sensitive Hashing を実装してみる | Atsushi TATSUMA Web Page
はじめに 研究室では、大規模データベースを対象とした検索インデックスについて研究しています。 分散処理によるインデックス作成を考えていて、今回 Hadoop Streaming でどこまでできるかを試すべく、 Locality-Sensitive Hashing (LSH) を実装してみました。 実装したアルゴリズムについて LSH にはいくつかのアルゴリズムのバリエーションがあります。 LSH の詳細は、ブログなり論文なり本なりありますので、ここでは省略しますが、 類似したデータに同じハッシュ値を与えることで、検索を高速化しようというアイディアです。 このハッシュ値には、0101 とかの短いバイナリ符号が好まれます。 今回は、いくつかある LSH のアルゴリズムのうち、 Charikar,M., Similarity estimation techniques from ro
3日で作る高速特定物体認識システム (7) 最近傍探索の高速化 - 人工知能に関する断創録
3日で作る高速特定物体認識システム (6) 線形探索を用いた特定物体認識（2009/11/22）のつづきです。今回がこのシリーズの最終回です。 前回の線形探索は遅すぎるので最近傍探索を高速化します。これで表題の高速特定物体認識システムができあがります。高速化にはいくつかの方法がありますが、物体モデルデータベースをなんらかのデータ構造にあらかじめ格納しておくというのがポイントです。今回は、資料でも述べられているkd-treeとLocality Sensitive Hashing (LSH)という手法を試してみます。kd-treeは木構造、LSHはハッシュでデータを構造化（インデキシング）します。kd-treeは、厳密な最近傍を求めますが、LSHは近似最近傍検索と呼ばれ、厳密な最近傍は求められない代わりに計算を大幅に高速化できます。 資料では、ANN (Approximate Nearest
Learning to Hash! 最新 Locality sensitive hashing 事情 - 武蔵野日記
高速に類似度計算をしたい場合、典型的に使われるのは Locality sensitive hashing (LSH)という技術であり、元々距離が近いインスタンス同士はハッシュ値が近くなるようにハッシュ関数を作ることで高速に類似度を計算したりできるというお話なのだが、最近 Semantic hashing や Spectral hashing、また Kernelized LSH という手法が登場して盛り上がりつつあるところ、同じグループの人がもっといいのを出しました、ということらしい。ちなみに情報推薦とか画像検索とか大規模クラスタリングとか、いろいろな分野で高速な類似度計算の応用例がある。 そういうわけで、今日は manab-ki くんが Brian Kulis and Trevor Darrell. "Learning to Hash with Binary Reconstructive
Locality Sensitive Hashing
【論文】M. Datar, N. Immorlica, P. Indyk, and V.S. Mirrokni, Locality-Sensitive Hashing Scheme Based on p-Stable Distributions, Proceedings of the twentieth annual symposium on Computational geometry, 2004. Overview Locality Sensitive Hashing(以下LSH，局所性鋭敏型ハッシュ)は高次元データを次元圧縮するための手法で，圧縮したデータによるハッシュテーブルを作成して，効率的に近似的最近傍探索を行うための手法です．基本的なアイディアとしては高次元空間内での距離が近い2つのベクトルが，ハッシュテーブルにおいて高確率で同じバケットに入るように確率的な処理を行うと
レコメンド, LSH, Spectral Hashing - DO++
WEB+DB press vol.49にレコメンド特集の記事をtkngさんと書きました。 内容は最初は、協調フィルタリングやコンテンツマッチの簡単な話から、特徴量をどのように表すか、大規模データをどのように処理するかにいき、特異値分解などの低ランク行列分解によるレコメンドやRestricted Boltzmann Machineといった最近のnetflix prizeの上位の手法など、かなり突っ込んだ議論もしてます。 個人的には三章でLocality Sensitive Hash(LSH)について扱っているあたりがお勧めです。 レコメンドの内部の問題を極言すると、データというのは疎な高次元の数値ベクトル（数百万次元とか）で表され、クエリでベクトルが与えられた時、これと似たようなベクトルを探してこいという問題になります。”似たような”を数学的にいえば、クエリのベクトルとの内積（各ベクトルは長
PFI Seminar 2012/03/15 カーネルとハッシュの機械学習
2. 自己紹介 得居 誠也 | Tokui, Seiya 東京大学 理学部 数学科 @beam2d 同 情報理工 数理情報学 M2 近傍探索のためのハッシュの学習 PFIアルバイト（一年半くらい） 来月から正社員 3. 今日のおはなし ハッシュ • 近傍探索：クエリに類似したデータを 効率良く取り出す • 機械学習：分類や回帰を効率良く学習する あると良い知識 • 線形学習器を一つでも知っていると わかりやすいと思います 4. 内容 • カーネルの簡単な説明（復習） • ハッシュ関数の導入 • 近傍探索に使えるハッシュ – データのハッシュ – いろいろな手法を紹介 (LSH系, カーネル, ハッシュの学習) • 機械学習に使えるハッシュ – 素性のハッシュ – ハッシュされたデータの学習
最近のバイナリハッシングをいくつかJavaで実装してみた - rubyu's blog
去年の終わりから、バイナリハッシングを使った近似近傍検索をいろいろ調べていたのですが、ぼちぼち一段落したので、ひと通りまとめておきます。 バイナリハッシングとは。 個の 次元の点からなるデータセット で、元空間での近傍点を、類似したバイナリコードに関連づける技術。 要するに、実数ベクトルの検索をマトモにやるには、最近のデータは膨大すぎるのでお手上げ。なので、元空間での距離をなるべく保ったまま、バイナリコードに落としましょう。 そうすると、バイナリ一致か、1ビット違うか、2ビット違うか...と、捜索していくにしても、元空間のデータでやるより高速で、しかもストレージ容量を削減できるというわけです。 その ビットのバイナリコード を作るために、 個のハッシュ関数が使われる。 ハッシュ関数は と定義される。ここで、 はデータセット。 は射影ベクトル。 は閾値。 線形写像ベースのハッシングはシンプル
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Multi-Index Locality Sensitive Hashing for Fun and Profit - Engineering Blog
Google Code Archive - Long-term storage for Google Code Project Hosting.
FAST LARGE-SCALE APPROXIMATE GRAPH CONSTRUCTION FOR NLP
複合ソート法による高速な全ペア 類似度検索
GitHub - bbc/ruby-lsh: Locality Sensitive Hashing in Ruby
b-Bit Minwise Hashing
Similarity Join Algorithms: An Introduction