Wie ist Locality Sensitive Hashing zu verstehen? [closed]

Mir ist aufgefallen, dass LSH eine gute Möglichkeit zu sein scheint, ähnliche Gegenstände mit hochdimensionalen Eigenschaften zu finden.

Nach dem Lesen der Zeitung http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdfich bin immer noch verwirrt mit diesen Formeln.

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

Das beste Tutorial, das ich für LSH gesehen habe, ist in dem Buch: Mining of Massive Datasets. Lesen Sie Kapitel 3 – Ähnliche Artikel finden
http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf

Ich empfehle auch 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 Kosinusähnlichkeit.

Ich leihe mir zwei Dias aus Benjamin Van Durme & Ashwin Lall, ACL2010 und versuchen Sie, die Intuitionen der LSH-Familien für die Cosinus-Distanz ein wenig zu erklären.

• In der Abbildung gibt es zwei Kreise mit rot und gelb farbig, die zwei zweidimensionale Datenpunkte darstellen. Wir versuchen, ihre zu finden Kosinusähnlichkeit mit LSH.
• Die grauen Linien sind einige gleichmäßig zufällig ausgewählte Ebenen.
• Je nachdem, ob sich der Datenpunkt über oder unter einer grauen Linie befindet, markieren wir dieses Verhältnis als 0/1.
• In der oberen linken Ecke befinden sich zwei Reihen mit weißen/schwarzen Quadraten, die jeweils die Signatur der beiden Datenpunkte darstellen. Jedes Quadrat entspricht einem Bit 0 (weiß) oder 1 (schwarz).
• Sobald Sie also einen Pool von Flugzeugen haben, können Sie die Datenpunkte mit ihrer Position in Bezug auf die Flugzeuge codieren. Stellen Sie sich vor, dass, wenn wir mehr Flugzeuge im Pool haben, die in der Signatur codierte Winkeldifferenz näher an der tatsächlichen Differenz liegt. Denn nur Ebenen, die sich zwischen den beiden Punkten befinden, geben den beiden Daten unterschiedliche Bitwerte.

• Nun schauen wir uns die Signatur der beiden Datenpunkte an. Wie im Beispiel verwenden wir nur 6 Bits (Quadrate), um alle Daten darzustellen. Dies ist der LSH-Hash für die ursprünglichen Daten, die wir haben.
• Die Hamming-Distanz zwischen den beiden Hash-Werten beträgt 1, da sich ihre Signaturen nur um 1 Bit unterscheiden.
• Unter Berücksichtigung der Länge der Unterschrift können wir ihre Winkelähnlichkeit wie in der Grafik gezeigt berechnen.

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

Tweets im Vektorraum können ein großartiges Beispiel für hochdimensionale Daten sein.

Sehen Sie sich meinen Blog-Beitrag zur Anwendung von Locality Sensitive Hashing auf Tweets an, um ähnliche Tweets zu finden.

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

Und weil ein Bild mehr als tausend Worte sagt, sehen Sie sich das Bild unten 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 machte einen großen Unterschied für mich. In Teil zwei geht es mehr um LSH, aber in Teil eins geht es auch darum.

Ein Bild der Übersicht (In den Folien gibt es noch viel mehr):

Nahe-Nachbar-Suche in hochdimensionalen Daten – Teil 1:
http://www.stanford.edu/class/cs345a/slides/04-highdim.pdf

Nahe-Nachbar-Suche 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 nimmt und eine Art Hash-Tabelle ausgibt.
• Die Indizes dieser Tabelle enthalten die Dokumente, sodass Dokumente berücksichtigt werden, die sich auf demselben Index befinden ähnlich und die auf verschiedenen Indizes sind “unähnlich“.
• Wo ähnlich hängt vom metrischen System und auch von einer Schwellenähnlichkeit ab s was wie ein globaler Parameter von LSH wirkt.
• Es liegt an Ihnen, den angemessenen Schwellenwert zu definieren s ist für dein 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 (Kosinus-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 ein visueller Mensch. Hier ist, was für mich als Intuition funktioniert.

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

Meine Intuition für ein LSH ist, dass es ähnlich ist, die Schatten dieser Objekte zu nehmen. Wenn Sie den Schatten eines 3D-Würfels nehmen, erhalten Sie einen quadratischen 2D-Schatten auf einem Blatt Papier, oder eine 3D-Kugel erzeugt 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 sein könnte), aber die Schatten Analogie ist immer noch sehr nützlich für mich.

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 einzigen Dimension.

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

Der ganze Trick besteht darin, die Schatten so zu nehmen, dass sie in der unteren Dimension noch Sinn machen, dh sie ähneln dem ursprünglichen Objekt in einer Weise, die gut genug erkannt werden kann.

Eine 2D-Zeichnung eines Würfels in Perspektive sagt mir, dass dies ein Würfel ist. Aber ich kann ohne Perspektive nicht einfach ein 2D-Quadrat 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. Also stelle ich mir einen “guten” LSH vor, der meine Objekte vor einem Licht so dreht, dass ihr Schatten am besten als Repräsentation meines Objekts erkennbar ist.

Um es noch einmal zusammenzufassen: Ich denke an Dinge, die mit einem LSH indiziert werden sollen, als physische Objekte wie ein Würfel, ein Tisch oder ein Stuhl, und ich projiziere ihre Schatten in 2D und schließlich entlang einer Linie (einer kleinen Zeichenfolge). 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 meine Bit-String zu erhalten.

Wenn ich schließlich suchen möchte, ob ein Objekt, das ich habe, einigen Objekten ähnelt, die ich indiziert habe, nehme ich die Schatten dieses “Abfrage” -Objekts auf die gleiche Weise, um mein Objekt vor dem Licht zu präsentieren (schließlich mit einem bisschen Schnur auch). Und jetzt kann ich vergleichen, wie ähnlich dieser Bit-String mit all meinen anderen indizierten Bit-Strings ist, was ein Proxy für die Suche nach meinen ganzen Objekten ist, wenn ich einen guten und erkennbaren Weg gefunden habe, meine Objekte meinem Licht zu präsentieren.

Als ganz kurze tldr Antworten:

Ein Beispiel für ortsabhängiges Hashing könnte darin bestehen, zuerst Ebenen zufällig (mit einer Drehung und einem Versatz) in Ihrem Eingabebereich zu hashen und dann Ihre Punkte im Raum zu hashen und für jede Ebene zu 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 davor oder danach gemessen werden.

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