Japan CV Dayで発表してきました

今更ですが一応。

Japan Computer Vision Day 2013
http://partake.in/events/5a96edbd-7a32-4a6d-81b8-bf5e7bbcbbf4

togetter
http://togetter.com/li/540498

Ustream
http://www.ustream.tv/channel/%E5%90%8D%E5%8F%A4%E5%B1%8Bcv-prml%E5%8B%89%E5%BC%B7%E4%BC%9A

発表資料

"K-means Hashing: an Affinity-Preserving Quantization Method for Learning Binary Compact Codes," CVPR'13. を概説しています。k-means（ベクトル量子化）の符号化効率の良さと、バイナリコードの高速な距離計算の良いとこ取りができる手法です。ハッシングをk-meansでやっているところが面白くてこの論文を選びましたが、既存手法のiterative quantization (ITQ) のも非常に面白いです。
ITQは、ハッシングを量子化とみなすことで、ハッシングのための射影行列の最適化に直交プロクラステス問題を適用することを可能としました。直交プロクラステス問題は下式で表現される最小化問題です。
R = \arg\min_{\Omega} || A \Omega - B ||_F^2 \; \mathrm{subject \; to} \; \Omega^T \Omega = I
http://en.wikipedia.org/wiki/Orthogonal_Procrustes_problem
直感的には行列AとBをなるべく同じにするような回転行列Rを求める問題です。量子化問題の場合、AとBはそれぞれ、量子化対象のベクトルとそれに対応するコードブックのベクトルを並べた行列です。そしてこれらの行列の差分のフロベニウスノルム（量子化誤差）を最小化する回転行列RがSVDで簡単に求まるのです。
ハッシングではなく、直積量子化の符号化効率の改善に利用している手法も提案されており、ほとんど同じ手法が同時にCVPR'13に採録されています。読んでみるとどちらも同じく直交プロクラステス問題に落とし込んでいることが分かると思います。ITQ論文がなければこれらの手法が生まれるのはもう少し遅かったのではないでしょうか。
"Cartesian k-means," CVPR'13.

"Optimized Product Quantization for Approximate Nearest Neighbor Search," CVPR'13.

やっていることはITQとほぼ同じで、直積量子化時の量子化誤差を最小化する回転を求め、回転されたベクトルを再度直積量子化コードブックに割り当て、その割り当てから直積量子化コードブックを更新するということを繰り返しています。

ついでなのでハッシング系の論文リストもおいておきます。

  1. "Similarity search in high dimensions via hashing," VLDB'99. (LSH)
  2. "Spectral Hashing," NIPS'08. (SH)
  3. "Learning to Hash with Binary Reconstructive Embeddings," NIPS'09. (BRE)
  4. "Locality Sensitive Binary Codes from Shift-Invariant Kernels," NIPS'09. (SIKH)
  5. "Kernelized Locality-Sensitive Hashing for Scalable Image Search," ICCV'09. (KLSH)
  6. "Sequential Projection Learning for Hashing with Compact Codes," ICML'10. (USPLH)
  7. "Self-Taught Hashing for Fast Similarity Search," SIGIR'10.
  8. "CARD: Compact And Real-time Descriptors," ICCV'11.
  9. "Complementary Hashing for Approximate Nearest Neighbor Search," ICCV'11.
  10. "Coherency Sensitive Hashing," ICCV'11.
  11. "Hashing with Graphs," ICML'11. (AGH)
  12. "Minimal Loss Hashing for Compact Binary Codes," ICML'11.
  13. "Random Maximum Margin Hashing," CVPR'11.
  14. "Iterative Quantization: A Procrustean Approach to Learning Binary Codes," CVPR'11. (ITQ)
  15. "LDAHash: Improved Matching with Smaller Descriptors," PAMI'12. (LDAH)
  16. "Isotropic Hashing," NIPS'12.
  17. "Supervised Hashing with Kernels," CVPR'12.
  18. "Spherical Hashing," CVPR'12.
  19. "Multidimensional Spectral Hashing," ECCV'12.
  20. "Double-Bit Quantization for Hashing," AAAI'13.
  21. "Variable Bit Quantisation for LSH," ACL'13.
  22. "Hash Bit Selection: a Unified Solution for Selection Problems in Hashing," CVPR'13.
  23. "Compressed Hashing," CVPR'13.
  24. "Inductive Hashing on Manifolds," CVPR'13.
  25. "Learning Binary Codes for High-Dimensional Data Using Bilinear Projections," CVPR'13.
  26. "K-means Hashing: an Affinity-Preserving Quantization Method for Learning Binary Compact Codes," CVPR'13.