前の Key-Value Store 勉強会でO 野原くんに勧められた Spectral Hashing の論文(NIPS 2008)も読んでみた。前もスペクトラルクラスタリングについて書いたが、要はグラフ分割の問題に落とし込んで、厳密に分割を求めようとすると NP 困難なので、制約を少し緩和して k 個の固有ベクトルを求める問題に帰着して近似解を求める、というもの。主成分分析のように重要な軸から順番に次元抽出して圧縮するので、非常にシンプルな方法だが、高い性能を得られそうであり、実際その通りだそうだ。
具体的に実験を見てみると、人工データと現実のデータの両方で比較実験しており、いずれも Locality Sensitive Hashing (LSH) と Restricted Boltzmann Machine (RBM) より遙かにいい性能を得られるそうである。かなり impressive な内容だが、個人的に疑問なのは、8,000万の画像検索で使えたそうだが、PCA (裏で SVD 計算する)は O(n^3) かかるので、いったいどうやってこれを計算したんだろう。(行列の低ランク近似でもそういう問題について言及したが)
ともあれ、小規模なデータであればかなり効果がありそうなので、そういう状況設定であれば使ってよさそうである。
上記エントリーに関連して、
- 作者: arton,桑田誠,角田直行,和田卓人,伊藤直也,西田圭介,岡野原大輔,縣俊貴,大塚知洋,nanto_vi,徳永拓之,山本陽平,田中洋一郎,下岡秀幸,ミック,武者晶紀,高林哲,小飼弾,はまちや2,WEB+DB PRESS編集部
- 出版社/メーカー: 技術評論社
- 発売日: 2009/02/23
- メディア: 大型本
- 購入: 10人 クリック: 373回
- この商品を含むブログ (45件) を見る
をようやく入手したので読んでみた。レコメンドエンジン特集は、知識としてはいろいろ書いてあっていいのだが、ちょっと詳しくなろうとすると「興味ある人は『○○』というキーワードで検索してみてください」と投げられてしまうので、あまり親切ではないかな……。しかしながら、こういう最新の研究・開発動向を一般の人に広めていく活動をするのは金銭的・労力的には全く割に合わないと思うが、この分野の裾野を広げるというのはとても大事なことなので、がんばって広めてもらっていてすばらしいと思う。ぜひまた今度は違うネタで書いていただきたく :-)
個人的にはこれよりnaoya さんが書いた「WEB+DB PRESS Vol.49 はてなブックマーク構築ノウハウ大公開」が参考になった。文章もよく練られていて、知りたい人には技術的な詳細が(惜しげもなく)書かれているし、初心者も道に迷わないように丁寧に解説されている。これはすごい……。特にはてなブックマークのインデックスや本文のサイズ、どういう構成の計算機(仮想環境)でやっているのかなど、資料的価値も高い。Googleは1つの検索クエリーに対し、1000台のマシンを使って0.2秒で処理しているなんて話もあるし、大規模なデータを扱うにはアルゴリズム的な工夫(時には多少性能を犠牲にし)もあるし、計算機的なチューニングも必要だし、なかなかこのあたりまで全部見て文書まで書けてしまう人というのは貴重だと思う。
cf. 楽天も情報爆発しています
