Yanal-Lab News

概要：大規模なデータを高速に探索するためにバイナリコード化させるハッシング手法についてのチュートリアル
高速に処理が行えるためモバイル画像検索や3D復元などに用いられる
基本的ながらも精度のよいPCAハッシングやIQTの説明やグラフ/構造体に基づく方法などの説明を受けた
クロスモーダルハッシングやDeep Learningによるハッシングなどが今後の課題とされる

以下スライド概要
そもそもハッシングとは？
・たくさんのデータの中からざっくりと近いものを早く探すためのcontent-basedなデータインデクシング法
・画像では検索、マッチング、３D復元などいろいろ使われる
・大規模画像処理の基本的なツールの一つ

何のためにあるのか？
基本は近傍探索のため
真面目にやると非常に時間がかかる

近似近傍探索
多少いい加減でもよいことにすると処理速度が上がる
ハッシングはこの近似近傍探索を実現するための代表ツール

ハッシングとは
ハッシュ関数を使ってインデクシングする
低次元なバイナリコードへの変換＝ハッシュコードに変換する
もともと遠いものは遠く、近いものは近く

ハッシュランキング
そうすることでハミング距離を求めることで近いものをランキングすることができる。
長所：必ず近似近傍を見つけることができる
短所：距離計算をしなければならない（それでもL2距離などよりは少ない）

ハッシュルックアップ
ハッシュコードで作ったルックアップテーブルを使って一定距離内のデータをすぐに見つけることができる
長所；データが増えても検索時間は変わらない
短所：近似近傍が見つからない場合がある

ハッシュを用いることでモバイル画像検索にも用いられている。
3次元復元では処理時間は通常では21時間、ハッシュでは5分！　243倍！

ハッシュ関数の構成法
局所鋭敏性ハッシング　LSH
原始的なハッシュ関数構成の一つ
元の空間の距離に応じて様々なアルゴリズムが提案されている
画像分野では角度距離を保存するランダムプロジェクションが用いられる

LSHはハッシュ関数をたくさん用いなければならないデータから学習するハッシング


ハッシング法の紹介
ランダム型と学習型が存在する
基本的には次元削減＋バイナリ量子化
主に教師なし型を今回は議論する

PCAハッシング
主成分ベクトルを引き、そのベクトルに垂直に線をひき01を分ける
10が均等な確率で現れる　ビット間の相関がない方がよい
量子化誤差が問題
ITQ
量子化誤差が少なくなるようにデータを回転させてしまう。
その回転行列Rを求める
近傍探索精度を大幅に改善できる　5倍近い改善がみられる
分散が均一化される
様々な発展形が存在している（要旨参照）
ハッシングを行うならまずこれを試してみる

K-means　ハッシング　KMH
K-meansを用いたハッシング法
代表点にバイナリの値を割り当てその値を用いて距離の計算を行う
ITQでは立方体の回転のみでの対応だったがKMHでは立方体のゆがみによる修正を行う事ができるので量子化誤差を少なくする面で優秀

Double-Bit Quantization (DBQ)
1次元あたり2ビット量子化する
分割した際に次元ごとの量子化誤差が最も小さくなるように線引きする
ITQとの併用で精度がよくなる
グラフ/多様体に基づくハッシング
Laplacian Eigenmaps（LE）
本質的なデータの構造をとらえて低次元化する
多様体構造　簡単にいえば局所的な近接性
元の空間でのデータの局所的な近接性が、より低次元な空間上で出来る限り再現されるように配置する問題を解く
固有値問題

局所的な近接性の観点に近いもの同士が近いハッシュコードになる
しかし単純にLEを適用してしまうと学習データにしか適応できない
なので様々な方法が提案されている

Spatialハッシング
特徴空間を三角関数で分割してハッシング
新規点と既存点との類似度を求める　この時にはサイン関数を用いる

Local　Linear　Embedding　LLE
相対距離が保持される
近接する異なる多様体同士を分離して探索できる


現在そしてこれからの課題
クロスモーダルハッシング
異なるデータ同士の相互検索（画像―文書）
多くの場合ユニモーダル（画像―画像）精度を改善できることも知られている
モーダル内類似度とモーダル間類似度の2つの類似度を保持するようなハッシュコードを求める
詳しくは要旨参照

超次元ハッシング
検索はデータ数に対して比例しない時間で実行できる
ハッシュコード生成は1ビットあたり特徴次元に比例する時間かかる
特徴ベクトルを行列に折りたたむことでメモリの削減などを行う

Deep-Learning　Hashing
CNNを用いたハッシュ法特徴抽出とハッシングが同時に行える