Momentan studiere ich, wie man einen nächsten Nachbarn findet, indem man lokalisierungssensitives Hashing verwendet. Aber während ich Zeitungen lese und im Internet suche, habe ich zwei Algorithmen dafür gefunden:
1- Verwenden Sie L Anzahl der Hash-Tabellen mit L Anzahl der zufälligen LSH-Funktionen, wodurch die Wahrscheinlichkeit steigt, dass zwei Dokumente, die ähnlich sind, dieselbe Signatur erhalten. Wenn beispielsweise zwei Dokumente zu 80% ähnlich sind, besteht eine 80% ige Chance, dass sie dieselbe Signatur von einer LSH-Funktion erhalten. Wenn wir jedoch mehrere LSH-Funktionen verwenden, besteht eine höhere Wahrscheinlichkeit, dass die Dokumente aus einer der LSH-Funktionen dieselbe Signatur erhalten. Diese Methode wird in Wikipedia erklärt und ich hoffe mein Verständnis ist richtig:
2- Der andere Algorithmus verwendet eine Methode aus einem Papier (Abschnitt 5), genannt: Ähnlichkeitsschätztechniken aus Rundungsalgorithmen von Moses S. Charikar. Es basiert auf der Verwendung einer LSH-Funktion, um die Signatur zu generieren und dann P-Permutationen darauf anzuwenden und dann die Liste zu sortieren. Eigentlich verstehe ich die Methode nicht sehr gut und ich hoffe, wenn jemand es klären könnte.
Meine Hauptfrage ist: Warum sollte jemand die zweite Methode anstelle der ersten verwenden? Wie ich finde, ist es einfacher und schneller.
Ich hoffe wirklich, dass jemand helfen kann!
BEARBEITEN: Eigentlich bin ich mir nicht sicher ob @ Raff.Edward zwischen dem "ersten" und dem "zweiten" mischte. Da nur die zweite Methode einen Radius verwendet und die erste nur eine neue Hash-Familie g verwendet, die aus der Hash-Familie F besteht. Bitte überprüfen Sie den Wikipedia-Link. Sie haben einfach viele g-Funktionen benutzt, um verschiedene Signaturen zu erzeugen, und dann hat sie für jede g-Funktion eine entsprechende Hash-Tabelle. Um den nächsten Nachbarn eines Punktes zu finden, lassen Sie den Punkt einfach durch die g-Funktionen gehen und überprüfen Sie die entsprechenden Hash-Tabellen auf Kollisionen. So wie ich es verstanden habe als mehr Funktion ... mehr Chance für Kollisionen.
Ich habe für die erste Methode keinen Hinweis auf Radius gefunden.
Für die zweite Methode erzeugen sie nur eine Signatur für jeden Merkmalsvektor und wenden dann P-Permutationen auf sie an. Jetzt haben wir P Listen von Permutationen, in denen jede n Signaturen enthält. Jetzt sortieren sie dann jede Liste von P aus. Danach geben sie einen Abfragepunkt q, generieren die Signatur dafür und wenden dann die P-Permutationen darauf an und verwenden dann die binäre Suche für jede permutierte und sortierte P-Liste, um die ähnlichste Signatur zu finden die Abfrage q. Ich habe das nach dem Lesen vieler Artikel abgeschlossen, aber ich verstehe immer noch nicht, warum jemand solch eine Methode benutzen sollte, weil es nicht schnell scheint, die Hamming-Distanz zu finden !!!!
Für mich würde ich einfach folgendes tun, um den nächsten Nachbarn für einen Abfragepunkt q zu finden. Bei einer Liste von Signaturen N würde ich die Signatur für den Abfragepunkt q erzeugen und dann die Liste N scannen und die Hamming-Distanz zwischen jedem Element in N und der Signatur von q berechnen. So würde ich mit dem nächsten Nachbarn für q enden. Und es braucht O (N) !!!
Ihr Verständnis der ersten ist ein wenig aus. Die Wahrscheinlichkeit einer Kollision ist nicht proportional zur Ähnlichkeit, sondern ob sie kleiner ist als der vordefinierte Radius. Das Ziel ist, dass alles innerhalb des Radius eine hohe Chance hat, zu kollidieren, und alles außerhalb des Radius * (1 + eps) hat eine geringe Chance zu kollidieren (und der Bereich dazwischen ist etwas trüb).
Der erste Algorithmus ist tatsächlich ziemlich schwer gut zu implementieren, kann aber gute Ergebnisse erzielen. Insbesondere ist der erste Algorithmus für die L1- und L2- (und technisch einige mehr) Metriken.
Der zweite Algorithmus ist sehr einfach zu implementieren, obwohl eine naive Implementierung möglicherweise zu viel Speicher verbraucht, um abhängig von Ihrer Problemgröße nützlich zu sein. In diesem Fall ist die Kollisionswahrscheinlichkeit proportional zur Ähnlichkeit der Eingaben. Es funktioniert jedoch nur für die Cosine Similarity (oder Entfernungsmetrik basierend auf einer Transformation der Ähnlichkeit).
Was Sie also verwenden würden, basiert in erster Linie darauf, welche Entfernungsmetrik Sie für Nearest Neighbor (oder eine andere Anwendung) verwenden.
Der zweite ist eigentlich viel einfacher zu verstehen und zu implementieren als der erste, das Papier ist nur sehr wortreich.
Die kurze Version: Nehmen Sie einen Zufallsvektor V und geben Sie jedem Index einen unabhängigen Zufallseinheitnormalwert. Erstellen Sie so viele Vektoren, wie Sie die Signaturlänge haben möchten. Die Signatur sind die Zeichen jedes Index, wenn Sie ein Matrix Vector-Produkt erstellen. Nun hängt die Hamming-Distanz zwischen zwei beliebigen Signaturen mit der Kosinusähnlichkeit zwischen den jeweiligen Datenpunkten zusammen.
Da Sie die Signatur in ein int-Array codieren können und ein XOR mit einer Bitzählanweisung verwenden, um die Hamming-Distanz sehr schnell zu erhalten, können Sie ungefähre Cosinus-Ähnlichkeitswerte sehr schnell erhalten.
LSH-Algorithmen haben nicht viel Standardisierung, und die beiden Arbeiten (und andere) verwenden unterschiedliche Definitionen, so dass es manchmal etwas verwirrend ist. Ich habe diese beiden Algorithmen erst kürzlich in JSAT implementiert und arbeite noch daran, sie vollständig zu verstehen beide.
BEARBEITEN: Beantworten Sie Ihre Bearbeitung. Der Wikipedia-Artikel ist nicht großartig für LSH. Wenn Sie das Originalpapier lesen, funktioniert die erste Methode, über die Sie sprechen, nur für einen festen Radius . Die Hash-Funktionen werden dann basierend auf diesem Radius erstellt und verkettet, um die Wahrscheinlichkeit zu erhöhen, dass sich Punkte bei einer Kollision nähern. Sie konstruieren dann ein System zum Ausführen von k-NN darüber hinaus, indem sie den maximalen Wert von k sie wan bestimmen und dann den größten angemessenen Abstand finden, den sie den k-ten nächsten Nachbarn in finden würden. Auf diese Weise wird eine Radius-Suche sehr wahrscheinlich die Menge von k-NNs zurückgeben. Um dies zu beschleunigen, erzeugen sie auch ein paar extra kleine Radien, da die Dichte oft nicht gleichmäßig ist, und je kleiner der Radius ist, desto schneller sind die Ergebnisse.
Der verlinkte Wikipedia-Abschnitt stammt aus der Papierbeschreibung für den Abschnitt "Stabile Verteilung", der die Hash-Funktion für eine Suche mit dem Radius r = 1 darstellt.
Für das zweite Papier ist das "Sortieren", das Sie beschreiben, nicht Teil des Hashings, sondern Teil des Ein-Schemas, um den Hamming-Raum schneller zu durchsuchen. Wie ich bereits erwähnt habe, habe ich dies kürzlich implementiert und Sie können einen schnellen Benchmark I tat mit einer Brute-Force-Suche ist immer noch viel schneller als die naive Methode von NN. Auch hier würden Sie diese Methode wählen, wenn Sie die Cosinus-Ähnlichkeit über die L2- oder L1-Distanz benötigen. Sie werden viele andere Artikel finden, die verschiedene Schemata vorschlagen, um den durch die Signaturen erzeugten Hamming-Raum zu durchsuchen.
Wenn Sie Hilfe brauchen, um sich selbst zu überzeugen, können Sie schneller sein, selbst wenn Sie noch rohe Gewalt betrieben haben - sehen Sie es sich so an: Sagen wir, dass das durchschnittliche Dokument nur 40 Wörter mit einem anderen Dokument hat (eine sehr konservative Zahl in meinem Erfahrung). Sie haben n Dokumente zum Vergleich. Brute-Force-Kosinusähnlichkeit würde dann etwa 40 * n Gleitkommamultiplikationen (und etwas zusätzliche Arbeit) beinhalten. Wenn Sie eine 1024-Bit-Signatur haben, sind das nur 32 ganze Zahlen. Das bedeutet, dass wir eine Brute-Force-LSH-Suche in 32 * n Integer-Operationen durchführen könnten, die wesentlich schneller sind als Gleitkommaoperationen.
Auch hier spielen andere Faktoren eine Rolle. Für einen Sparse-Datensatz müssen sowohl der Double- als auch der Integer-Index die Nicht-Null-Indizes darstellen, sodass das Spared-Dot-Produkt viele zusätzliche Integer-Operationen ausführt, um zu sehen, welche Indizes sie gemeinsam haben. LSH erlaubt uns auch, Speicher zu sparen, weil wir nicht alle diese Integers und Doubles für jeden Vektor speichern müssen, stattdessen können wir einfach seinen Hash beibehalten - was nur ein paar Bytes ist.Reduzierte Speicherauslastung kann uns helfen, den CPU-Cache besser auszunutzen.
Dein O (n) ist der naive Weg, den ich in meinem Blogpost benutzt habe. Und es ist schnell. Wenn Sie die Bits jedoch vorher sortieren, können Sie die binäre Suche in O (log (n)) durchführen. Selbst wenn Sie L dieser Listen haben, ist L & lt; & lt; n, und so sollte es schneller sein. Das einzige Problem ist, dass Sie NN annähern, die die Kosinus-Ähnlichkeit bereits annähern, so dass die Ergebnisse ein bisschen schlechter werden können. Es hängt davon ab, was Sie brauchen.
Tags und Links algorithm machine-learning locality-sensitive-hash