Locality-sensitive hashing

Cel: Znajdź dokumenty z podobieństwem Jaccarda co najmniej t

Główną ideą LSH jest znalezienie algorytmu takiego, że jeśli wprowadzimy podpisy 2 dokumentów, powie nam, że te 2 dokumenty tworzą parę kandydującą lub nie, tj. ich podobieństwo jest większe niż próg t. Pamiętaj, że bierzemy podobieństwo podpisów jako przybliżenie dla podobieństwa Jaccarda pomiędzy oryginalnymi dokumentami.

Specyficznie dla macierzy podpisów min-hash:

• Hashowanie kolumn macierzy podpisów M przy użyciu kilku funkcji skrótu
• Jeśli 2 dokumenty hashują do tego samego kubełka dla przynajmniej jednej z funkcji skrótu, możemy wziąć te 2 dokumenty jako parę kandydującą

Teraz pytanie brzmi jak stworzyć różne funkcje skrótu. W tym celu wykonujemy partycję pasmową.

Partycja pasmowa

Oto algorytm:

• Podziel macierz sygnatur na b przedziałów, każdy przedział ma r wierszy
• Dla każdego przedziału, Zhashuj swoją część każdej kolumny do tablicy haszującej z k kubełkami
• Kandydujące pary kolumn to te, które haszują do tego samego kubełka dla co najmniej 1 pasma
• Dostosuj b i r, aby złapać większość podobnych par, ale niewiele niepodobnych par

Jest tu kilka rozważań. Idealnie dla każdego pasma chcemy wziąć k, aby było równe wszystkim możliwym kombinacjom wartości, które kolumna może przyjąć w ramach pasma. Będzie to równoznaczne z dopasowaniem tożsamości. Ale w ten sposób k będzie ogromną liczbą, która jest obliczeniowo niewykonalna. Na przykład: Jeśli dla zespołu mamy 5 wierszy w nim. Teraz, jeśli elementy w podpisie są 32-bitowymi liczbami całkowitymi, to k w tym przypadku będzie (2³²)⁵ ~ 1.4615016e+48. Możesz zobaczyć, co jest problemem tutaj. Normalnie k przyjmuje się około 1 miliona.

Chodzi o to, że jeśli 2 dokumenty są podobne, to pojawią się jako para kandydatów w co najmniej jednym z pasm.

Wybór b & r

Jeśli przyjmiemy duże b, tzn. większą liczbę funkcji haszujących, to zmniejszymy r, ponieważ b*r jest stałą (liczba wierszy w macierzy sygnatur). Intuicyjnie oznacza to, że zwiększamy prawdopodobieństwo znalezienia pary kandydatów. Ten przypadek jest równoważny z przyjęciem małego t (próg podobieństwa)

Powiedzmy, że twoja macierz podpisów ma 100 wierszy. Rozważmy 2 przypadki:

b1 = 10 → r = 10

b2 = 20 → r = 5

W drugim przypadku istnieje większa szansa, że 2 dokumenty pojawią się w tym samym kubełku przynajmniej raz, ponieważ mają więcej możliwości (20 vs 10) i mniej elementów sygnatury jest porównywanych (5 vs 10).

Wyższe b implikuje niższy próg podobieństwa (wyższy false positives), a niższe b implikuje wyższy próg podobieństwa (wyższy false negatives)

Postarajmy się to zrozumieć na przykładzie.

Ustawienie:

• 100k dokumentów przechowywanych jako sygnatury o długości 100
• Macierz sygnatur: 100*100000
• Porównanie podpisów metodą brute force da w efekcie 100C2 porównań = 5 miliardów (całkiem sporo!)
• Przyjmijmy b = 20 → r = 5

próg podobieństwa (t) : 80%

Chcemy, aby 2 dokumenty (D1 & D2) o 80% podobieństwie były haszowane w tym samym kubełku dla co najmniej jednego z 20 pasm.

P(D1 & D2 identyczne w danym paśmie) = (0,8)⁵ = 0,328

P(D1 & D2 nie są podobne we wszystkich 20 pasmach) = (1-0,328)^20 = 0,00035

To oznacza, że w tym scenariuszu mamy ~.035% szansy na fałszywy negatyw @ 80% podobnych dokumentów.

Chcemy również, aby 2 dokumenty (D3 & D4) z 30% podobieństwem nie były haszowane w tym samym kubełku dla żadnego z 20 pasm (próg = 80%).

P(D3 & D4 identyczne w danym paśmie) = (0.3)⁵ = 0.00243

P(D3 & D4 są podobne w co najmniej jednym z 20 pasm) = 1 – (1-0.00243)^20 = 0.0474

To oznacza, że w tym scenariuszu mamy ~4.74% szansy na fałszywy pozytyw @ 30% podobnych dokumentów.

Więc widzimy, że mamy kilka fałszywych pozytywów i kilka fałszywych negatywów. Te proporcje będą się różnić w zależności od wyboru b i r.

Co chcemy tutaj jest coś jak poniżej. Jeśli mamy 2 dokumenty, które mają podobieństwo większe niż próg, to prawdopodobieństwo, że dzielą one ten sam kubełek w co najmniej jednym z pasm powinno wynosić 1, w przeciwnym razie 0.

Najgorszym przypadkiem będzie sytuacja, w której b = liczba wierszy w macierzy sygnatur, jak pokazano poniżej.

Uogólniony przypadek dla dowolnego b i r jest pokazany poniżej.

Dobierz b i r tak, aby uzyskać najlepszą krzywą S i.e minimalny współczynnik fałszywie negatywny i fałszywie pozytywny

Podsumowanie LSH

• Dostrój M, b, r, aby uzyskać prawie wszystkie pary dokumentów z podobnymi sygnaturami, ale wyeliminować większość par, które nie mają podobnych sygnatur
• Sprawdź w pamięci głównej, czy pary kandydatów naprawdę mają podobne sygnatury

.