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?
Odpowiedzi:
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 .
Mam tutaj przykładowy kod (tylko 50 linii) w Pythonie, który używa podobieństwa cosinusowego. https://gist.github.com/94a3d425009be0f94751
źródło
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
źródło
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
źródło
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/
źródło
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.
źródło
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
źródło