Wie verstehe ich Locality Sensitive Hashing?

Mir ist aufgefallen, dass LSH ein guter Weg ist, um ähnliche Objekte mit hochdimensionalen Eigenschaften zu finden.

Nachdem ich die Zeitung http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf gelesen habe , bin ich immer noch mit diesen Formeln verwechselt.

Kennt jemand einen Blog oder Artikel, der das auf einfache Weise erklärt?

Das beste Tutorial, das ich für LSH gesehen habe, ist im Buch: Mining von massiven Datensätzen. Überprüfen Sie Kapitel 3 - Finden ähnlicher Elemente http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf

Außerdem empfehle ich die folgende Folie: http://www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf . Das Beispiel auf der Folie hilft mir sehr beim Verständnis des Hashings für Cosinus-Ähnlichkeit.

Ich leihe mir zwei Folien von Benjamin Van Durme und Ashwin Lall, ACL2010, aus und versuche, die Intuitionen von LSH-Familien für Cosine Distance ein wenig zu erklären.

• In der Figur gibt es zwei Kreise mit roter und gelber Farbe, die zwei zweidimensionale Datenpunkte darstellen. Wir versuchen, ihre Kosinusähnlichkeit mit LSH zu finden.
• Die grauen Linien sind einige gleichmäßig zufällig ausgewählte Flugzeuge.
• Je nachdem, ob sich der Datenpunkt über oder unter einer grauen Linie befindet, markieren wir diese Beziehung als 0/1.
• In der oberen linken Ecke befinden sich zwei Reihen weißer / schwarzer Quadrate, die die Signatur der beiden Datenpunkte darstellen. Jedes Quadrat entspricht einem Bit 0 (weiß) oder 1 (schwarz).
• Sobald Sie einen Pool von Ebenen haben, können Sie die Datenpunkte mit ihrer Position entsprechend den Ebenen codieren. Stellen Sie sich vor, wenn wir mehr Ebenen im Pool haben, ist die in der Signatur codierte Winkeldifferenz näher an der tatsächlichen Differenz. Weil nur Ebenen, die sich zwischen den beiden Punkten befinden, den beiden Daten einen unterschiedlichen Bitwert geben.

• Nun betrachten wir die Signatur der beiden Datenpunkte. Wie im Beispiel verwenden wir nur 6 Bits (Quadrate), um die einzelnen Daten darzustellen. Dies ist der LSH-Hash für die Originaldaten, die wir haben.
• Der Hamming-Abstand zwischen den beiden Hash-Werten beträgt 1, da sich ihre Signaturen nur um 1 Bit unterscheiden.
• In Anbetracht der Länge der Signatur können wir ihre Winkelähnlichkeit wie in der Grafik gezeigt berechnen.

Ich habe hier einen Beispielcode (nur 50 Zeilen) in Python, der Cosinus-Ähnlichkeit verwendet. https://gist.github.com/94a3d425009be0f94751

Tweets im Vektorraum können ein gutes Beispiel für hochdimensionale Daten sein.

Schauen Sie sich meinen Blog-Beitrag über das Anwenden von Locality Sensitive Hashing auf Tweets an, um ähnliche zu finden.

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

Und weil ein Bild mehr als tausend Wörter enthält, sehen Sie sich das folgende Bild an:

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

Ich hoffe es hilft. @mvogiatzis

Hier ist eine Präsentation von Stanford, die es erklärt. Es hat einen großen Unterschied für mich gemacht. Teil zwei befasst sich mehr mit LSH, aber Teil eins behandelt es auch.

Ein Bild der Übersicht (Die Folien enthalten noch viel mehr):

Suche in der Nähe von Nachbarn in hochdimensionalen Daten - Teil 1: http://www.stanford.edu/class/cs345a/slides/04-highdim.pdf

Suche in der Nähe von Nachbarn in hochdimensionalen Daten - Teil 2: http://www.stanford.edu/class/cs345a/slides/05-LSH.pdf

• LSH ist eine Prozedur, die eine Reihe von Dokumenten / Bildern / Objekten als Eingabe verwendet und eine Art Hash-Tabelle ausgibt.
• Die Indizes dieser Tabelle enthalten die Dokumente, sodass Dokumente, die sich im selben Index befinden, als ähnlich und Dokumente in verschiedenen Indizes als " unterschiedlich " angesehen werden.
• Wo ähnlich ist abhängig von dem metrischen System und auch auf einer Schwelle Ähnlichkeit s , die wie ein globaler Parameter von LSH wirkt.
• Es ist an Ihnen zu definieren , was die angemessene Schwelle s für Ihr Problem.

Es ist wichtig zu betonen, dass unterschiedliche Ähnlichkeitsmaße unterschiedliche Implementierungen von LSH haben.

In meinem Blog habe ich versucht, LSH für die Fälle von minHashing (Jaccard-Ähnlichkeitsmaß) und simHashing (Cosinus-Abstandsmaß) gründlich zu erklären. Ich hoffe, Sie finden es nützlich: https://aerodatablog.wordpress.com/2017/11/29/locality-sensitive-hashing-lsh/

Ich bin eine visuelle Person. Hier ist, was für mich als Intuition funktioniert.

Sagen wir, jedes der Dinge, nach denen Sie ungefähr suchen möchten, sind physische Objekte wie ein Apfel, ein Würfel, ein Stuhl.

Meine Intuition für ein LSH ist, dass es ähnlich ist, die Schatten dieser Objekte zu nehmen. Wenn Sie beispielsweise den Schatten eines 3D-Würfels nehmen, erhalten Sie ein 2D-Quadrat auf einem Blatt Papier, oder eine 3D-Kugel erhalten einen kreisförmigen Schatten auf einem Blatt Papier.

Schließlich gibt es in einem Suchproblem viel mehr als drei Dimensionen (wobei jedes Wort in einem Text eine Dimension haben könnte), aber die Schattenanalogie ist für mich immer noch sehr nützlich.

Jetzt können wir Bitfolgen in der Software effizient vergleichen. Eine Bitfolge mit fester Länge ist mehr oder weniger wie eine Linie in einer einzelnen Dimension.

Mit einem LSH projiziere ich die Schatten von Objekten schließlich als Punkte (0 oder 1) auf eine einzelne Linie / Bitfolge mit fester Länge.

Der ganze Trick besteht darin, die Schatten so zu nehmen, dass sie in der unteren Dimension immer noch Sinn machen, z. B. ähneln sie dem ursprünglichen Objekt auf eine gut genug erkennbare Weise.

Eine 2D-Zeichnung eines Würfels in Perspektive sagt mir, dass dies ein Würfel ist. Aber ich kann ein 2D-Quadrat ohne Perspektive nicht einfach von einem 3D-Würfelschatten unterscheiden: Beide sehen für mich wie ein Quadrat aus.

Wie ich mein Objekt dem Licht präsentiere, bestimmt, ob ich einen gut erkennbaren Schatten bekomme oder nicht. Ich stelle mir also ein "gutes" LSH vor, das meine Objekte vor ein Licht stellt, sodass ihr Schatten am besten als Repräsentation meines Objekts erkennbar ist.

Um es noch einmal zusammenzufassen: Ich stelle mir Dinge, die mit einem LSH indiziert werden sollen, als physische Objekte wie einen Würfel, einen Tisch oder einen Stuhl vor und projiziere ihre Schatten in 2D und schließlich entlang einer Linie (einer Bitfolge). Und eine "gute" LSH "-Funktion" ist, wie ich meine Objekte vor einem Licht präsentiere, um eine annähernd unterscheidbare Form im 2D-Flachland und später in meiner Bitfolge zu erhalten.

Wenn ich schließlich suchen möchte, ob ein Objekt, das ich habe, einigen von mir indizierten Objekten ähnlich ist, nehme ich die Schatten dieses "Abfrage" -Objekts auf die gleiche Weise, um mein Objekt vor dem Licht darzustellen (was schließlich zu einem kleinen Ergebnis führt) Zeichenfolge auch). Und jetzt kann ich vergleichen, wie ähnlich diese Bitfolge mit all meinen anderen indizierten Bitfolgen ist. Dies ist ein Proxy für die Suche nach meinen gesamten Objekten, wenn ich eine gute und erkennbare Möglichkeit gefunden habe, meine Objekte meinem Licht zu präsentieren.

Als sehr kurze Antwort: tldr :

Ein Beispiel für ortsabhängiges Hashing könnte sein, zuerst Ebenen zufällig (mit Drehung und Versatz) in Ihrem Eingabebereich auf Hash zu setzen und dann Ihre Punkte auf Hash im Bereich abzulegen und für jede Ebene, die Sie messen, ob der Punkt ist darüber oder darunter (zB: 0 oder 1), und die Antwort ist der Hash. Punkte, die im Raum ähnlich sind, haben also einen ähnlichen Hash, wenn sie mit dem Kosinusabstand vorher oder nachher gemessen werden.

Sie können dieses Beispiel mit scikit-learn lesen: https://github.com/guillaume-chevalier/SGNN-Self-Governing-Neural-Networks-Projection-Layer