複合ソート法による高速な全ペア類似度検索(特別セッション,機械学習とその応用)

概要

論文の詳細を見る
近年、画像や信号などを、数十ビット程度のスケッチとよばれるビット列で表す手法が、多く提案されている。ここから、半教師つき学習などに必要な類似度ネットワークを作成するには、ハミング距離の意味で近いペアを網羅的に発見する必要がある。しかし、全てのペアに関して距離を計算する方法は遅すぎ、三角不等式を用いて枝刈りをする方法を用いても十分な速度が得られない。本発表では、アイテムセットマイニングに用いられるPatternGrowth法と、基数ソートを組合わせた複合ソート法という手法を紹介し、160万サンプルの画像データに適用して、cover tree, Lanczos bisectionなどの他手法よりも、大幅に高速であることを示す。特に、Locality sensitive hashingを用いてスケッチを作成した際の平均的な偽陰性確率(見逃しの確率)や、重複した発見を避けるための工夫についても述べる。また、同じアイデアを編集距離に基づくペア発見に適用することによって、生物配列への適用も可能になる。この方法で、数千万本の短いDNA配列に対して全ペア類似度検索を行った結果、Suffix Arrayを用いる方法に比べて、20-1000倍の高速化を達成した。
2010-06-07