九工大篠原研コミュのSketchについて色々教えて！

新しい研究であるSketchについて、キリ丸大先生の後輩の彼（名前は覚えたけど、あだ名は何？）に、私が色々と教えてもらうトピックです。

コメント(4)

最初
全て
最新の40件

Sketchについて私の理解を簡単に説明すると、距離空間上を色々な方法でＮ分割（代表的には２分割？）していった時の各所属グループを文字として文字列を形成し、ハミング距離空間に射影を行う。
このハミング距離空間上で距離が近いものは、元空間中でも距離が近いだろうという仮説の元、絞込みを行う。（ただし絞込みは非常に誤差が大きいため、おおよその目安にしかしない）

気になるのは、ｎ次元距離空間→ｍ次元ハミング距離空間のとき、ｎとｍはどういう関係になるのか、ということ。（ｎがたとえば１０００のとき、ｍは１０ぐらいになるもの？　それとも、ｎが１００のとき、ｍを１０００ぐらいにしても、その後の処理的には問題がないもの？　また、ｎ＞ｍのとき、ｎが３の様に小さくなり過ぎた場合にもSketchは有用なのか？）

また、Sketch自体は射影法だと思うのだけれども、Sketchの射影に合った独自の索引構造が用いられているはずだよね。どういう索引構造を使うから効率が良いのか、気になります。

[2] mixiユーザー 03月12日 03:06

あと、Sketchを文字列編集距離に使った場合は、どういう結果が得られるのかについても、教えて下さい。

＃　それと、文字列編集距離（レーベンシュタイン距離）のオーダーって何だったっけ？
＃　日本語wikipediaにはまだO(NM)とか書かれてるけど、もっと効率の良いアルゴリズムがあったはず。

[3] mixiユーザー 03月13日 00:56

呼ばれた気がしたので、やってきましいた～

質問・・・答えになってるか分りませんが，答えます．

1，スケッチの長さについて
Sketｃｈは距離空間をN分割して，ハミング距離空間に射影(射影って言ったら怒られるかもしれませんが)することで作成できます．実際，Nの値としてはどのような値を用いてもSketchの概念からは外れないため，問題ないと考えていますが，Sketchの距離をハミング距離で計算することから，2分割するのが最も良いのではないかと考えています．また，ｎ次元距離空間→ｍ次元ハミング距離空間のときについてですが，n,mの値には関係なくSketchを作成することは可能です．しかし，ｍを非常に大きくとってしまった場合，Sketchデータベースに対する近傍質問のコストが大きくなりますので，検索効率が良くならない場合が考えられます．逆に，ｎが非常に小さい場合には実距離の計算が高速に計算できることが考えれられ，Sketchを用いても効果が出ない可能性が考えられます．ただ，最も問題になるのは距離関数が何なのかであると考えています．

2，Sketchの射影にあった索引構造について
はっきりと把握できていないため，どのようなものが存在するか等には詳しくお答えすることはできませんが，ハミング距離空間に適したインデックスがあるそうです．これを用いることで，現在の全検索を用いて検索した場合よりも，高速な検索を実現することが可能であると考えています．

3，文字列編集距離について
Sketchにおいて扱える距離空間に制限は無いものと考えられています．とくに，私が利用しているGHPは任意の距離空間に適用可能な空間分割法であり，編集距離にも十分に適応できると考えています．また，アルさんの研究では，Sketchが木構造に対する距離(木の編集距離とは違うアルさんの示した距離空間)でも利用できることが示されています．

4，文字列編集距離のオーダーについては確認しておきます．

以上です．駄文で申し訳ありません．

[4] mixiユーザー 03月15日 12:25

＞3，文字列編集距離について

Sketchが文字列編集距離で使えるのは以前聞いた原理から分かっている
（と思ってたけれども、GHPだから使えるというのは少し見落としてた）のだけれども、
私の質問の意図は、L1、L2、L∞等に適用した場合と比べて、
どの程度、実用的なのか……みたいな所です。
L1で用いたSketchほどにはレーベンシュタイン距離では実用的な効果は得られないのか、
それとも、レーベンシュタイン距離に用いたSketchの方が
より実用に適しているという速度測定の結果が出るのか。

私の研究していた成分分解SMAPの時もそうだったけれども、
レーベンシュタイン距離というのは、見た目の文字数以上に、
計測上の次元数が馬鹿の様に高次元なのだけれども
（そもそもL1とかと並べて次元数を論議しちゃいけない気もするんだけれども）、
ハミング距離というのは、ある意味でL1と等しいので、
Sketchを使ってレーベンシュタイン距離50文字→ハミング距離500文字とかの射影を行った時に、
射影後の距離空間ではどの程度の距離を保持していて、
どの程度の距離情報は失われているのだろうかな、と思いました。

そもそもSMAPでは元距離空間と射影後距離空間の距離単位が等しいのに対して、
Sketchではそれは成り立たないので、目安程度のことしか言えないとは思うのだけれども。
レーベンシュタイン距離の計算時間に比べれば、
ハミング距離の計算時間なんてほとんど無い様なものだから、
レーベンシュタイン距離50文字→ハミング距離500文字の射影は充分にあり得ると思うわけね。

ただ、Sketchでは、候補を多めにピックアップして、その全てに対して元距離での計算を行うから、
そこで結局はコストの大きいレーベンシュタイン距離の計算が入ってしまうわけだけれども。

しかし、もし仮に、射影後の次元数を上げることで、元距離の計算が必要な候補数を減らせるのなら、
結構実用的なのかなぁと思うんだけれども。
でも、Sketchの場合は、（L1とかで、だと思うけれども）射影後の次元数を増やしても、
あまり精度は良くならないという発表を、この間見たような気がするから、
そういう意味で、文字列編集距離への適用は、難航しそうな気配が感じ取れるね。

他の回答へのコメントは、今度付けます。回答ありがとう。

ログインすると、みんなのコメントがもっと見れるよ