Jak rozumieć haszowanie zależne od lokalizacji?

156

Zauważyłem, że LSH wydaje się dobrym sposobem na znalezienie podobnych przedmiotów o właściwościach o dużych wymiarach.

Po przeczytaniu artykułu http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf nadal jestem zdezorientowany z tymi formułami.

Czy ktoś zna bloga lub artykuł, który wyjaśnia to w prosty sposób?

WoooHaaaa
źródło
3
Przeczytaj rozdział 3 Ullmana - „ ZNAJDYWANIE
achini

Odpowiedzi:

250

Najlepszy samouczek dotyczący LSH, jaki widziałem, znajduje się w książce: Mining of Massive Datasets. Sprawdź rozdział 3 - Znajdowanie podobnych przedmiotów http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf

Polecam również poniższy slajd: http://www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf . Przykład na slajdzie bardzo pomaga mi w zrozumieniu hashowania podobieństwa cosinusowego.

Pożyczam dwa slajdy od Benjamina Van Durme i Ashwina Lall, ACL2010 i próbuję nieco wyjaśnić intuicje rodzin LSH dla odległości cosinusów . wprowadź opis obrazu tutaj

  • Na rysunku znajdują się dwa okręgi w kolorze czerwonym i żółtym , reprezentujące dwa dwuwymiarowe punkty danych. Próbujemy znaleźć ich podobieństwo cosinusowe za pomocą LSH.
  • Szare linie to niektóre jednolicie losowo wybrane samoloty.
  • W zależności od tego, czy punkt danych znajduje się powyżej czy poniżej szarej linii, oznaczamy tę relację jako 0/1.
  • W lewym górnym rogu znajdują się dwa rzędy białych / czarnych kwadratów, reprezentujących odpowiednio sygnaturę dwóch punktów danych. Każdy kwadrat odpowiada bitowi 0 (biały) lub 1 (czarny).
  • Kiedy masz już pulę samolotów, możesz zakodować punkty danych z ich lokalizacją odpowiadającą płaszczyznom. Wyobraź sobie, że gdy mamy więcej płaszczyzn w puli, różnica kątowa zakodowana w sygnaturze jest bliższa rzeczywistej różnicy. Ponieważ tylko płaszczyzny znajdujące się między dwoma punktami dadzą dwóm danym inną wartość bitową.

wprowadź opis obrazu tutaj

  • Teraz przyjrzymy się podpisowi dwóch punktów danych. Podobnie jak w przykładzie, używamy tylko 6 bitów (kwadratów) do reprezentowania wszystkich danych. To jest skrót LSH dla oryginalnych danych, które mamy.
  • Odległość Hamminga między dwiema zaszyfrowanymi wartościami wynosi 1, ponieważ ich sygnatury różnią się tylko o 1 bit.
  • Biorąc pod uwagę długość sygnatury, możemy obliczyć ich podobieństwo kątowe, jak pokazano na wykresie.

Mam tutaj przykładowy kod (tylko 50 linii) w Pythonie, który używa podobieństwa cosinusowego. https://gist.github.com/94a3d425009be0f94751

zieloność
źródło
dlaczego nazywa się to zależne od lokalizacji? ponieważ przypisanie każdego bitu zależy od lokalizacji punktu danych w każdym planie?
nawara
21
wrażliwe na lokalizację - punkty danych, które znajdują się blisko siebie, są mapowane na podobne skróty (w tym samym segmencie z dużym prawdopodobieństwem).
Greeness
2
Przepraszam za spóźnienie w tym temacie ale miałem pytanie odnośnie cosinusa. Prezentacja mówi, że wartość bitu jest równa jeden, jeśli iloczyn skalarny między rzeczywistym wektorem a wektorem płaskim> = 0, albo jest równy 0. Jaki jest kierunek wektora płaskiego, ponieważ kąty między 90 stopni a 180 stopni również dają cosinus, który jest ujemny. Przypuszczam, że każda płaszczyzna składa się z dwóch wektorów i bierzemy mniejszy kąt, który jest utworzony z rzeczywistym wektorem.
vkaul11
Dziękuję Ci. Czy zatem słuszne jest stwierdzenie, że h koduje różnicę kątową, a b „precyzję”? W ten sposób rozumiem, że h * PI to theta w promieniu, a b dokładność kąta.
user305883
1
Przesłany przez Ciebie slajd jest bardzo fajny: cs.jhu.edu/~vandurme/papers/VanDurmeLallACL10-slides.pdf - czy mógłbyś również wyjaśnić matematyczną logikę „sztuczki z pulą ” - lub koncepcje algebry liniowej, na które powinienem zwrócić uwagę żeby to zrozumieć?
user305883
35

Tweety w przestrzeni wektorowej mogą być doskonałym przykładem danych wielowymiarowych.

Sprawdź mój wpis na blogu dotyczący stosowania haszowania z uwzględnieniem lokalizacji w tweetach, aby znaleźć podobne.

http://micvog.com/2013/09/08/storm-first-story-detection/

A ponieważ jedno zdjęcie to więcej niż tysiąc słów, spójrz na poniższe zdjęcie:

wprowadź opis obrazu tutaj http://micvog.files.wordpress.com/2013/08/lsh1.png

Mam nadzieję, że to pomoże. @mvogiatzis

mvogiatzis
źródło
21

Oto prezentacja ze Stanford, która to wyjaśnia. Zrobiło to dla mnie dużą różnicę. Część druga jest bardziej o LSH, ale część pierwsza też to omawia.

Zdjęcie przeglądu (na slajdach jest znacznie więcej):

wprowadź opis obrazu tutaj

Wyszukiwanie bliskich sąsiadów w danych wysokowymiarowych - część 1: http://www.stanford.edu/class/cs345a/slides/04-highdim.pdf

Wyszukiwanie bliskich sąsiadów w danych wysokowymiarowych - część 2: http://www.stanford.edu/class/cs345a/slides/05-LSH.pdf

nilsi
źródło
Dlaczego nie użyć bezpośrednio minhasha jako funkcji LSH?
Thomas Ahle,
1
Uważam, ponieważ liczba nie duplikatów na segment pozostaje wystarczająco wysoka, podczas gdy jeśli użyjemy m takich niezależnych funkcji skrótu, prawdopodobieństwo odwzorowania innych niż bliskie duplikatów do tego samego zasobnika drastycznie spada.
Shatu
7
  • LSH to procedura, która pobiera jako dane wejściowe zestaw dokumentów / obrazów / obiektów i wyświetla rodzaj tablicy skrótów.
  • Indeksy tej tabeli zawierają takie dokumenty, że dokumenty znajdujące się w tym samym indeksie są uważane za podobne, a te w różnych indeksach są „ niepodobne ”.
  • Gdzie podobnie zależy od systemu metrycznego, a także na progu podobieństwa s , który działa jak globalny parametr LSH.
  • To do ciebie, aby określić, co odpowiednia próg s jest dla swojego problemu.

wprowadź opis obrazu tutaj

Należy podkreślić, że różne miary podobieństwa mają różne implementacje LSH.

Na swoim blogu starałem się dokładnie wyjaśnić LSH dla przypadków minHashing (miara podobieństwa jaccarda) i simHashing (miara odległości cosinus). Mam nadzieję, że uznasz to za przydatne: https://aerodatablog.wordpress.com/2017/11/29/locality-sensitive-hashing-lsh/

Carlos Teixeira
źródło
2

Jestem osobą wizualną. Oto, co działa dla mnie jako intuicja.

Powiedz, że każda z rzeczy, których chcesz w przybliżeniu szukać, to obiekty fizyczne, takie jak jabłko, kostka, krzesło.

Moja intuicja co do LSH jest taka, że ​​podobnie jest z cieniem tych obiektów. Na przykład, jeśli weźmiesz cień kostki 3D, otrzymasz kwadratowy kwadrat 2D na kartce papieru, lub sfera 3D da ci cień podobny do koła na kartce papieru.

Ostatecznie istnieje znacznie więcej niż trzy wymiary problemu wyszukiwania (gdzie każde słowo w tekście może być jednym wymiarem), ale analogia z cieniem jest dla mnie bardzo przydatna.

Teraz możemy efektywnie porównywać ciągi bitów w oprogramowaniu. Ciąg bitów o stałej długości jest mniej więcej podobny do linii w jednym wymiarze.

Tak więc za pomocą LSH wyświetlam cienie obiektów ostatecznie jako punkty (0 lub 1) na pojedynczej linii / ciągu bitów o stałej długości.

Cała sztuka polega na tym, aby cienie miały taki sens, aby w dolnym wymiarze nadal miały sens, np. Przypominały oryginalny obiekt na tyle dobrze, że można je rozpoznać.

Rysunek 2D sześcianu w perspektywie mówi mi, że to sześcian. Ale nie mogę łatwo odróżnić kwadratu 2D od cienia sześcianu 3D bez perspektywy: oba wyglądają dla mnie jak kwadrat.

Sposób, w jaki przedstawię swój obiekt świetle, zadecyduje o tym, czy otrzymam dobrze rozpoznawalny cień, czy nie. Myślę więc o „dobrym” LSH jako takim, który obróci moje obiekty przed światło w taki sposób, aby ich cień był najlepiej rozpoznawalny jako reprezentujący mój obiekt.

Podsumowując: myślę o rzeczach do indeksowania za pomocą LSH jako o obiektach fizycznych, takich jak sześcian, stół lub krzesło, i wyświetlam ich cienie w 2D i ostatecznie wzdłuż linii (trochę sznurka). A „dobrą funkcją” LSH ”jest sposób, w jaki przedstawiam swoje obiekty przed światłem, aby uzyskać w przybliżeniu rozpoznawalny kształt na płaskiej powierzchni 2D, a później na moim sznurku bitowym.

Wreszcie, gdy chcę sprawdzić, czy obiekt, który mam, jest podobny do niektórych obiektów, które zindeksowałem, biorę cienie tego obiektu „zapytania” w ten sam sposób, aby przedstawić mój obiekt przed światłem (ostatecznie kończąc na string też). A teraz mogę porównać, jak podobny jest ten ciąg bitów do wszystkich moich innych indeksowanych ciągów bitów, które są proxy do wyszukiwania całych moich obiektów, jeśli znalazłem dobry i rozpoznawalny sposób prezentowania moich obiektów mojemu świetle.

Philippe Ombredanne
źródło
0

Krótko mówiąc, odpowiedź tldr :

Przykładem haszowania uwzględniającego lokalizację może być najpierw losowe ustawienie płaszczyzn (z obrotem i przesunięciem) w przestrzeni danych wejściowych do skrótu, a następnie upuszczenie punktów do skrótu w przestrzeni, a dla każdej mierzonej płaszczyzny, jeśli punkt jest powyżej lub poniżej (np .: 0 lub 1), a odpowiedzią jest hash. Tak więc punkty podobne w przestrzeni będą miały podobny hash, jeśli zostaną zmierzone za pomocą odległości cosinusa przed lub po.

Możesz przeczytać ten przykład za pomocą scikit-learn: https://github.com/guillaume-chevalier/SGNN-Self-Govern-Neural-Networks-Projection-Layer

Guillaume Chevalier
źródło