Znajdowanie podobnych wektorów w czasie subkwadratowym

Pozwolić $d:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}$ być funkcją, którą nazywamy funkcją podobieństwa . Przykłady funkcji podobieństwa to odległość cosinus, $l_2$ norma, odległość Hamminga, podobieństwo Jaccard itp.

Rozważać $n$ binarne wektory długości $k$ : $\vec{v} \in (\{0,1\}^k)^n$ .

Naszym celem jest grupowanie wektorów, które są podobne. Bardziej formalnie chcemy obliczyć wykres podobieństwa, w którym węzły są wektorami, a krawędzie reprezentują wektory podobne ( $d(v,u) \leq \epsilon$ ).

$n$ i $k$ są bardzo dużymi liczbami i porównują dwie długości $k$ wektory są drogie, nie możemy wykonać całej brutalnej siły $O(n^2)$ operacje. Chcemy obliczyć wykres podobieństwa przy znacznie mniejszej liczbie operacji.

czy to możliwe? Jeśli nie, to możemy obliczyć przybliżenie do wykresu, który zawiera wszystkie krawędzie na wykresie podobieństwa plus co najwyżej $O(1)$ inne krawędzie?

ds.algorithms graph-algorithms clustering

— Baran
źródło

Tak być powinno

\leq ϵ

$\leq \epsilon$ zamiast

\geq ϵ

$\geq \epsilon$ ?

— usul

@usul Dziękujemy za komentarz :) W tym miejscu chcieliśmy grupować przedmioty, które są bardzo podobne. Zredagowałem pytanie, mam nadzieję, że teraz jest jasne.

— Ram

Wydaje mi się, że można by użyć funkcji Hashing podobieństwa ( arxiv.org/pdf/1311.7662v1.pdf ), aby zmniejszyć wymiar problemu.

— RB

To pytanie nie jest w ogóle dobrze zdefiniowane, proszę podać więcej szczegółów. Np. Jeśli

d

$d$ jest podany przez wyrocznię, to oczywiście nie możesz zrobić lepiej niż .

(\binom{n}{2})

${n\choose 2}$

— domotorp

Pracujesz dla Twittera? blog.twitter.com/2014/all-pairs-similarity-via-dimsum Poważnie, nawet wykrycie, czy na tym wykresie jest krawędź (tj. że nie jest to niezależny zestaw wierzchołków), będzie bardzo trudne do wykonania szybciej niż dla dowolnej funkcji podobieństwa.

O (n^{2})

$O(n^2)$

— Ryan Williams

Być może istnieje sposób na róg buta twierdzenie Johnsona-Lindenstraussa w tym problemie. Zasadniczo JL stwierdza, że można wyświetlać dane wielowymiarowe w przestrzeniach o niższych wymiarach w taki sposób, że odległości par są prawie zachowane. Mówiąc prościej, Achlioptas ma artykuł zatytułowany Losowe projekcje przyjazne bazom danych: Johnson-Lindenstrauss z monetami binarnymi, które wykonują tę projekcję w sposób losowy, co działa całkiem dobrze w praktyce.

Teraz z pewnością twoja funkcja podobieństwa nie jest dokładnie taka sama, jak coś, co pasowałoby do twierdzenia JL. Wygląda jednak na funkcję odległości i być może część powyższej teorii może pomóc.

— wyer33
źródło