動画像、何それ？おいしいの？

いや、全く知らないわけでもないけれど。

むしろ、実はb4の頃は動画像でディゾルブ検出とかテロップ抽出、文字認識してましたが。


うん、今メインの研究が画像分類だというのに、

M2になって、方向転換（動画像）ですよｗ

(゜∀。)ﾜﾋｬﾋｬﾋｬﾋｬﾋｬﾋｬ

こりゃ祭りだﾜｯｼｮｲヽ(ﾟ∀ﾟ)メ(ﾟ∀ﾟ)メ(ﾟ∀ﾟ)ノﾜｯｼｮｲ


うん。なんか、動画像の提示に関する内容らしい。でも・・・

内容不透明杉ｗ

語るだけ語っておきながら、投下されたんですけど

ゲシュタルト爆弾ｗｗｗ

まさに、頭がゲシュタルト崩壊した瞬間でしたよ。と。
 

支部会おわた

支部会自体はまだありますが。
自分の発表は終了。
するどい質問がなくてよかった…。
むしろ、従来手法の高速化だっつうのに「（アプリケーション的に）その速度で満足か？」みたいな質問がでたんですが…。
立て続けに「あなたとしては、その速さでどう感じたか？」と問われたので、
「個人的な感想としては満足できる速度だと思った」
て言った。
いいのか？こんなんでw





全然関係ないが、
ケータイ打ちだと2ch絵文字が登録されてない件。
辞書とかないのかな？

実験

やり直し．最初から．

ええ．やりますよ．
データベース作るところから．

まあ，どうせこんなもんですよ．

(´Д｀)ﾊｧ…

LSHまとめ(1)

ここ10日間研究室にとまったおかげで，
LSHとその周辺についていろいろとわかった．
ネットサーフィンならぬ文献サーフィンをしていたので，
一度ここで整理しておく．

Locality-Sensitive Hashing

LSHは近似最近傍探索(Approximate Nearest Neighbor)アルゴリズムの一つ．

近似最近傍探索とは，簡単に言うとクエリqから半径(1+ε)内にある点vを探索すること．
つまり，半径(1+ε)の点のうち，どれか1つでも探索できればおｋ．
言葉の意味そのままに最近傍探索(Nearest Neighbor)の条件を少し緩くした探索といえる．
（実は，特徴ベクトルの次元がd=2の場合なら，ボロノイ図を使えば近似最近傍探索ができる）

LSHはハッシュ関数を用いた確率的探索で近似最近傍探索を解く．
そう，実はハッシュ関数を用いるということ以上に確率的探索ということに大きな意味がある．（これが自分にとってはかなりやっかいな問題）
LSHでは，クエリqと近傍(半径(1+ε)以内)にある点ではハッシュ値が一致する確率が高く，
クエリqと遠い位置にある点ではハッシュ値が一致する確率が低くなるようなハッシュ関数を定める．
各点の特徴ベクトルを入力として，ハッシュ関数から得られたハッシュ値に対し，
ハッシュ値が等しいものを同じバケットに格納する．
これにより，近傍にある（可能性の高い）データ同士の集合が生成される．
クエリqが含まれるバケットを探索することで，近似最近傍探索が実現される．

以上よりLSHメリット・デメリットは以下のようになる．
メリット：
・2点間の距離を算出をしない　→　高速な探索が可能
・クエリの数，つーかクエリの有無に関係なく近傍探索のコストは同じ．

デメリット：
・確率的探索　→　精度に問題
・精度に限界がある

2つ目のメリットはでかい．
バケット=クラスタと考えれば，ある意味LSH自体がクラスタリングをしているといっても過言ではない．
でも，実際にはバケット=クラスタとすることができない．
それは，バケットがあくまでも確率的に可能性が高いとしか言えないから．
うーん，なんとも歯がゆい感じ．

そもそも，なぜ確率に頼るのか．
それは，ハッシュを使っているから．
この考え方だと，ハッシュ値が一致したものしか同じバケットに格納されない．
だから，確率的に変動させておかないと，まったく同じ特徴ベクトルのものしか格納されないことになる．

最初に提案されたのは，
"Approximate Nearest Neighbors : Towards Removing the Curse of Dimensionality"(P.Indyk et al, 1998)
でも，LSHは全体の手法の一部としか紹介されおらず，
具体的なハッシュ関数の定義が書いていない．
というか，実験すらしてないΣ(ﾟдﾟ)
なので，理論だけ．
ときどき，(A.Gionis et al, 1999)をrefしてる文献があったけど，
それは正確ではない．
そっちは，具体的にハッシュ関数を定めたやつ．(最初，どっちがどっちだかわからずこまった)

LSHのハッシュ関数

LSHでは特徴ベクトルをどんな距離空間で比較するかによってハッシュ関数を定める．
自分が確認したの以下のようなもの．
・L1距離(Hamming Space)
定義・証明：
"Similarity Search in High Dimensions via Hashing"(A.Gionis et al, 1999)

・Lp距離
安定分布を用いることでLp空間に対応．
定義・証明：
"Locality-Sensitive Hashing Scheme Based on p-Stable Distributions"(M.Datar et al, 2005)

・Jaccard係数
Min-wise Independent Family(最小値独立変換族)に属する順列(Permutation)を用いることでJaccard係数に対応．
のちにMinHashと呼ばれたりする．
理論の元：
"Syntactic clustering of the Web"(A.Z.Border et al, 1997)
Min-wise Independent Familyの定義等：
"Min-wise Independent Permutations"(A.Z.Border et al, 1998)
Min-wise Independent Familyからハッシュ関数への証明：
"A small approximately min-wise independent family of hash functions"(P.Indyk, 1999)

・Cosine尺度(Earth Mover Distance:EMD)
定義・証明：
"Similarity Estimation Techniques from Rounding Algorithms"(M.S.Charikar, 2002)

土〜月まで

ずっと研究室．
しかも，月曜は2,3限あり．
→死亡確定

LSHの論文

鬱です．
ゼミ前ってホントいやですね．

Imagineも大規模アップデートでいろいろと追加・変更があったので，
そろそろやりたい．
なんだかんだであまりにもブランクあけすぎた（あれｗもしかして，一ヶ月オーバー？）ので，
さっさと復帰したい．
でも，ゼミ終わるまでは無理．
というかゼミが無理ｗ
打ち合わせがもっと無理ｗ


さて，研究の話．
論文の内容の概略．

Approximate Nearest Neighbors: Towards Removing the Cures of Dimensionality

この論文で初めてLSHが提案された．たぶん．
でも，LSH主体な訳ではなく，
あくまでε-NNS(ε-approximate Nearest Neighbor Search)
を解く提案手法の一部として紹介されている．

この論文では，ε-NNSを解くために，
ring-cover treesという新しいデータ構造を用いることで高速化を可能としている．
詳細は・・・しょーじきよくわかりません（ぉぃ
まあ，でも実際これは概略さえ知ってればいいか思う．

しかしながら，ring-cover treesを構成する上でpoint location問題
を解く必要がある．
ここで，point location問題とは，queryの点が含まれている領域を探索すること．
http://www.cs.sunysb.edu/~algorith/files/point-location.shtml
で，論文では，point location問題の解法として，2つの手法を挙げており，
そのうちの片方がLSHというわけ．

あと，どうやらこの手法には次元の削減にramdom projection(ランダム射影)
を用いているらしい．
最初，ただランダムに次元を選ぶようなので，
まあ，そういうもんか
と思っていたら，きちんとした理論展開があるらしい・・・．
「Johnson-Lindenstrauss補題」というらしいけど，
どうやらこれも使ってるみたい．
一応，確認しておくか．