Jak rozumieć haszowanie zależne od lokalizacji?

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?

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 .

• 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ą.

• 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

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:

http://micvog.files.wordpress.com/2013/08/lsh1.png

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

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):

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

• 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.

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/

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.

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