Dwa algorytmy znalezienia najbliższego sąsiada z mieszaniem wrażliwym na lokalizację, który?

Question

Obecnie studiuję, jak znaleźć najbliższego sąsiada za pomocą mieszania wrażliwego na lokalizację. Podczas gdy czytam papiery i przeszukuję internet, znalazłem dwa algorytmy:

1- Używaj L liczby tabel mieszania z L liczbą losowych funkcji LSH, zwiększając w ten sposób szansę, że dwa dokumenty, które są podobne do uzyskać ten sam podpis. Na przykład, jeśli dwa dokumenty są w 80% podobne, wówczas istnieje 80% szans, że otrzymają tę samą sygnaturę z jednej funkcji LSH. Jeśli jednak użyjemy wielu funkcji LSH, wówczas istnieje większa szansa na uzyskanie tego samego podpisu dla dokumentów z jednej z funkcji LSH. Sposób ten wyjaśniono w Wikipedia i nadzieję mi się, były:

http://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search

2- Inny algorytm wykorzystuje sposób z papieru (fragment 5) o nazwie: podobieństwo Techniki estymacji z zaokrągleń algorytmów Moses S. Charikar. Opiera się on na użyciu jednej funkcji LSH do wygenerowania sygnatury, a następnie zastosowania na nią permutacji P, a następnie posortowania listy. Właściwie nie rozumiem tej metody bardzo dobrze i mam nadzieję, że ktoś mógłby to wyjaśnić.

Moje główne pytanie brzmi: dlaczego ktoś miałby używać drugiej metody zamiast pierwszej metody? Jak uważam, jest to łatwiejsze i szybsze.

Naprawdę mam nadzieję, że ktoś może pomóc !!!

EDYTOWANIE: Właściwie nie jestem pewien, czy @ Raff.Edward miesza się między "pierwszym" a "drugim". Ponieważ tylko druga metoda używa promienia, a pierwsza po prostu używa nowej rodziny hash składającej się z rodziny mieszającej F. Sprawdź link wikipedia. Użyli po prostu wielu funkcji g do generowania różnych sygnatur, a następnie dla każdej funkcji g miała odpowiednią tablicę haszującą. Aby znaleźć najbliższego sąsiada punktu, po prostu pozwól mu przejść przez funkcje g i sprawdź odpowiednie tabele mieszania dla kolizji. W ten sposób zrozumiałem, że to więcej funkcji ... więcej szans na kolizje.

Nie znalazłem żadnej wzmianki o promieniu pierwszej metody.

Dla drugiej metody generują tylko jeden podpis dla każdego wektora cech, a następnie stosują na nich permutacje P. Teraz mamy listę permutacji P, z których każda zawiera n podpisów. Teraz następnie sortują każdą listę od P. Po tym, jak dany punkt zapytania q, generują podpis dla niego, a następnie stosują na nim permutacje P, a następnie używają wyszukiwania binarnego na każdej permutowanej i posortowanej liście P, aby znaleźć najbardziej podobny podpis do zapytanie q. Zakończyłem to po przeczytaniu wielu artykułów na ten temat, ale nadal nie rozumiem, dlaczego ktokolwiek użyłby takiej metody, ponieważ nie wydaje się, że szybko znajduje odległość Hamminga !!!!

Dla mnie wystarczy wykonać następujące czynności, aby znaleźć najbliższego sąsiada dla punktu zapytania q. Biorąc pod uwagę listę sygnatur N, wygenerowałbym podpis dla punktu zapytania q, a następnie zeskanowałem listę N i obliczyłem odległość Hamminga pomiędzy każdym elementem w N a podpisem q. W ten sposób skończę z najbliższym sąsiadem dla q. I zajmuje O (N) !!!

Answer 1

Twoje zrozumienie tego pierwszego jest trochę niecelne. Prawdopodobieństwo wystąpienia kolizji nie jest proporcjonalne do podobieństwa, ale to, czy jest ono mniejsze, czy też nie jest ono wcześniej zdefiniowane. Celem jest, aby wszystko w promieniu miało dużą szansę na kolizję, a wszystko poza promieniem * (1 + eps) będzie miało małą szansę na zderzenie (a obszar pomiędzy nimi jest nieco mętny).

Pierwszy algorytm jest dość trudny do wdrożenia, ale może uzyskać dobre wyniki.W szczególności pierwszy algorytm dotyczy metryk L1 i L2 (i technicznie kilku innych).

Drugi algorytm jest bardzo prosty w implementacji, choć naiwna implementacja może zużywać zbyt dużo pamięci, aby była użyteczna w zależności od rozmiaru problemu. W tym przypadku prawdopodobieństwo kolizji jest proporcjonalne do podobieństwa danych wejściowych. Działa to jednak tylko dla podobieństwa Cosinusa (lub metryk odległości bazujących na transformacji podobieństwa).

Który z nich będzie bazował przede wszystkim na metodzie dystansu używanej dla najbliższego sąsiarza (lub jakiejkolwiek innej aplikacji).

Ten drugi jest w rzeczywistości łatwiejszy do zrozumienia i wdrożenia niż pierwszy, a papier jest po prostu bardzo rozwlekły.

Skrócona wersja: Weź losowy wektor V i nadaj każdemu indeksowi niezależną wartość normalną losowej jednostki losowej. Utwórz tyle wektorów, ile chcesz mieć długość podpisu. Podpis jest oznaką każdego indeksu, gdy robisz produkt Matrix Vector. Teraz odległość między dwoma dowolnymi sygnaturami jest związana z podobieństwem cosinusa między odpowiednimi punktami danych.

Ponieważ możesz zakodować podpis w tablicy int i użyć XOR z instrukcją liczby bitów, aby uzyskać bardzo krótki dystans Hamminga, możesz uzyskać bardzo zbliżone wyniki podobieństwa kosinusów.

Algorytmy LSH nie mają dużej standaryzacji, a dwa dokumenty (i inne) używają różnych definicji, więc czasami jest to trochę mylące. Niedawno zaimplementowałem oba te algorytmy w JSAT i nadal pracuję nad ich pełnym zrozumieniem.

EDYCJA: Odpowiadanie na edytowanie. Artykuł wikipedia nie jest świetny dla LSH. Jeśli czytasz original paper, pierwsza metoda, o której mówisz, działa tylko dla ustalonego promienia. Funkcje mieszające są następnie tworzone na podstawie tego promienia i łączone w celu zwiększenia prawdopodobieństwa zbliżania się do punktów w kolizji. Następnie konstruują system do robienia k-NN na wierzchu, określając maksymalną wartość k, a następnie znajdując największą odległość, jaką znajdą w najbliższym sąsiedzie. W ten sposób wyszukiwanie promienia najprawdopodobniej zwróci zestaw k-NN. Aby to przyspieszyć, tworzą one również dodatkowy mały promień, ponieważ gęstość jest często niejednolita, a mniejszy promień, którego używasz, powoduje szybsze wyniki.

Sekcja wikipedii, którą łączysz, pochodzi z opisu papieru dla sekcji "Dystrybucja stabilna", która przedstawia funkcję skrótu dla wyszukiwania o promieniu r = 1.

W przypadku drugiego papieru "sortowanie", które opisujesz, nie jest częścią haszowania, ale częścią jednego schematu do szybszego przeszukiwania przestrzeni hamującej. Jak już wspomniałem, ostatnio to zaimplementowałem i widzisz, że użycie brutalnego wyszukiwania siły jest wciąż znacznie szybsze niż naiwna metoda NN. Ponownie wybrałbyś tę metodę, jeśli potrzebujesz podobieństwa cosinusów do odległości L2 lub L1. Znajdziesz wiele innych artykułów proponujących różne schematy przeszukiwania przestrzeni Hamminga stworzonej przez podpisy.

Jeśli potrzebujesz pomocy w przekonaniu siebie, dopasowanie może być szybsze, nawet jeśli nadal robisz brutalną siłę - po prostu spójrz na to w ten sposób: Powiedzmy, że przeciętny dokument o rzadkich rozmiarach ma 40 wspólnych słów z innym dokumentem (bardzo konserwatywna liczba w moje doświadczenie). Masz n dokumentów do porównania. Brutalne podobieństwo cosinusów wymagałoby wówczas około 40 * n zwielokrotnień zmiennoprzecinkowych (i trochę dodatkowej pracy). Jeśli masz podpis 1024 bitowy, to tylko 32 liczby całkowite. Oznacza to, że możemy wykonać przeszukiwanie LSH brute force w operacjach na liczbach całkowitych 32 * n, które są znacznie szybsze niż operacje zmiennoprzecinkowe.

Są tu również inne czynniki. W przypadku rzadkiego zestawu danych musimy przechowywać zarówno indeksy podwójne, jak i całkowite, aby reprezentować niezerowe indeksy, tak więc produkt z rzadkimi kropkami wykonuje wiele dodatkowych operacji na liczbach całkowitych, aby zobaczyć, które indeksy mają wspólne. LSH pozwala również na oszczędzanie pamięci, ponieważ nie musimy przechowywać wszystkich tych liczb całkowitych i podwójnych dla każdego wektora, zamiast tego możemy po prostu zachować jego skrót - to tylko kilka bajtów. Zmniejszone wykorzystanie pamięci może pomóc nam lepiej wykorzystać pamięć podręczną procesora.

Twoje O (n) to naiwny sposób, którego użyłem w moim poście na blogu. I jest szybkie. Jednakże, jeśli sortujesz bity przed ręką, możesz wykonać wyszukiwanie binarne w O (log (n)). Nawet jeśli masz L z tych list, L < < n, a więc powinno być szybciej. Jedynym problemem jest to, że przybliżasz nam hamowanie NN, które jest już zbliżone do podobieństwa cosinusów, więc wyniki mogą stać się nieco gorsze. To zależy od tego, czego potrzebujesz.