忍者ブログ
研究室生活のメモ・・・だった過去の遺産。移転先→http://negimochix2.blogspot.com/
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

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

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


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

M2になって、方向転換(動画像)ですよw

(゜∀。)ワヒャヒャヒャヒャヒャヒャ

こりゃ祭りだワッショイヽ(゚∀゚)メ(゚∀゚)メ(゚∀゚)ノワッショイ


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

内容不透明杉w

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

ゲシュタルト爆弾www

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

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





全然関係ないが、
ケータイ打ちだと2ch絵文字が登録されてない件。
辞書とかないのかな?
やり直し.最初から.

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

まあ,どうせこんなもんですよ.

(´Д`)ハァ…

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

Locality-Sensitive Hashing
LSHは近似最近傍探索(Approximate Nearest Neighbor)アルゴリズムの一つ.

近似最近傍探索とは,簡単に言うとクエリqから半径(1+ε)内にある点vを探索すること.
つまり,半径(1+ε)の点のうち,どれか1つでも探索できればおk.
言葉の意味そのままに最近傍探索(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限あり.
→死亡確定

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

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


さて,研究の話.
論文の内容の概略.

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補題」というらしいけど,
どうやらこれも使ってるみたい.
一応,確認しておくか.
Infomation
くさもち 【中の人】
・くさもち
・ボカロ廃大学院生
・βからのニコ厨
・もちろん非リア充
・ミクZ4 第二期個人スポンサー

【メール】
・negimochi.tabetai(゚Д゚)gmail.com
(゚Д゚)→@

【その他やってるもの】
Twitter

・これは痛いピアプロ
・過去の遺産smart.fm

【作ったもの】
・製作に参加したDTX GDPメインサイト
で,実際に作ったIRページ
カレンダー
02 2024/03 04
S M T W T F S
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
Heartsnative
『Heartsnative/MOSAIC.WAV×鶴田加茂 feat.初音ミク』応援中!
VOCALOID Ranking Watcher
新曲は常にチェックすべし。
真・フルみっくすプレイヤー
おすすめ記事
jubeat ripples
今更やってみる