Locality Sensitive Hashing (LSH) – eine skalierbare Lösung für die Deduplizierung von Jobs aus mehreren Quellen
Zurück zum Thema — warum ist Deduplizierung wichtig?
Wir verwenden einen riesigen Korpus von Stellenangeboten von Kalibrr in Kombination mit geminten Stellenangeboten aus verschiedenen öffentlichen Stellenangeboten, um unser Modell zu trainieren. Wenn mehrere Jobs in unserem Korpus ähnliche Stellenbeschreibungen enthalten, wirkt sich dies nachteilig auf das Modell aus. Beispiel davon ist im Bild unten gezeigt.
Duplicate job descriptions associated to varying positions can affect the model’s performance in distinguishing context between different job titles. Da Deep Learning und im Allgemeinen maschinelles Lernen Modelle darauf trainiert werden, eine Funktion zu erlernen, die eine Reihe von Funktionen Kategorien zuordnet oder ein Ziel optimiert, wirken sich ähnliche Eingaben, die jedoch unterschiedlichen Zielen zugeordnet sind, definitiv auf das Vertrauen und die Leistung des Modells aus.
Neben dem prädiktiven Leistungsproblem verbraucht das Trainieren eines Modells mit einem großen Korpus, bei dem die meisten Daten Duplikate sind, unnötige Rechenressourcen.
Dies veranschaulicht, wie sich das Verständnis der Daten leicht auf die Leistung des Modells auswirken kann.
Tf-Idf — ein einfacher Deduplizierungsalgorithmus
Das Erkennen von Duplikaten kann auf verschiedene Arten erfolgen. Die Darstellung von Dokumenten in einfachen Vektordarstellungen wie tf-idf kann eine vernünftige Methode sein, um nahezu ähnliche Dokumente zu finden. Dies kann durch Vergleich von Ähnlichkeitsmetriken wie Cosinus oder euklidische Ähnlichkeit zwischen Dokumentvektoren erfolgen.
Wir zeigen im folgenden Snippet, wie wir den Algorithmus anwenden können, um nahezu identische Texte zu identifizieren.
Während diese Methode in kleinen Korpora funktioniert, ist dies aufgrund der resultierenden Dimensionalität der Vektoren nach der Transformation der Dokumente ziemlich schwierig zu skalieren. Beachten Sie auch, dass es 319 ms dauerte, bis das Skript die gesamte Pipeline ausführte. Dies ist eine der vielen Manifestationen des „Fluches der Dimensionalität“ — die hohe Dimensionalität der Transformation wirkt sich sowohl auf die räumliche als auch auf die zeitliche Komplexität der Analyse aus.
Locality Sensitive Hashing (LSH) — die skalierbare Technik
Eine Lösung für dieses Problem ist Locality Sensitive Hashing (LSH). Die LSH-Methode kann nahezu Ähnlichkeitsanalysen für massive Datensätze durchführen. Es verwendet Hashing, um Dokumente in Buckets mit einer Dimensionalität abzubilden, die um Größenordnungen niedriger ist als eine äquivalente tf-idf-Transformation. Diese Eigenschaft macht LSH bequem in großen Anwendungen wie Text Mining zu verwenden.
LSH verwendet den Minhash-Algorithmus, um die Kollisionswahrscheinlichkeit zu berechnen. Es wurde gezeigt, dass die Kollisionswahrscheinlichkeit in LSH mit minhash der Jaccard-Ähnlichkeitsmetrik entspricht. Kurz gesagt, die Jaccard-Ähnlichkeit berechnet den Schnittpunkt zweier Mengen geteilt durch die Vereinigung der Elemente in jeder Menge. Die Formel davon ist unten gezeigt.
Die Jaccard—Ähnlichkeit quantifiziert die folgende Idee – zwei Gruppen mit mehr gemeinsamen Elementen sind wahrscheinlich ähnlich.
Hier ist ein Ausschnitt über LSH laut Wikipedia:
Locality-sensitive Hashing (LSH) reduziert die Dimensionalität hochdimensionaler Daten. LSH hasht Eingabeelemente, so dass ähnliche Elemente mit hoher Wahrscheinlichkeit denselben „Buckets“ zugeordnet werden (die Anzahl der Buckets ist viel kleiner als die Anzahl der möglichen Eingabeelemente). LSH unterscheidet sich von herkömmlichen und kryptographischen Hash-Funktionen, da es darauf abzielt, die Wahrscheinlichkeit einer „Kollision“ für ähnliche Elemente zu maximieren. Lokalitätssensitives Hashing hat viel mit Datenclustering und der Suche nach nächsten Nachbarn gemeinsam.
LSH bei der Arbeit
Im Folgenden zeigen wir eine Implementierung von LSH unter Verwendung dieses Moduls, die auf dasselbe oben dargestellte Beispiel angewendet wird.
Die Ergebnisse zeigen, dass die gesamte Pipeline etwa 4x schneller ist als die Tf-Idf-Version. Dieser Unterschied ist drastischer, sobald ein größerer Datensatz verwendet wird. Wir haben die Analyse der Speicherleistung jetzt ausgeschlossen, aber wir werden in einem separaten Beitrag einen umfassenderen Benchmark zwischen den beiden Methoden schreiben.
Wir haben LSH auf unseren Korpus angewendet und festgestellt, dass einige Stellenanzeigen mit nahezu ähnlichem Inhalt mehr als 200 Mal erscheinen!
Abschließende Gedanken
Während Tf-Idf populärer und ein bekannteres Modell für die Arbeit mit Textähnlichkeit ist; Wenn Sie mit skalierten Datensätzen arbeiten, ist LSH ein bequemeres Modell. Selbst für kleinere Datensätze bietet LSH eine erhebliche Verbesserung der Rechenzeit.
In der Lage zu sein, einen Korpus richtig zu deduplizieren, reduziert das Rauschen in den Trainingsdaten, spart Rechenressourcen und hilft, ein genaueres Modell für unseren Anwendungsfall zu lernen.
Wir glauben, dass es eine Vielzahl von Problemen gibt, auf die LSH angewendet werden kann, wie zum Beispiel:
- Doppelte Bildbereinigung: Wenden Sie LSH auf Bildfunktionen an und behalten Sie nur ein eindeutiges Bild aus jedem Bin bei.
- Chatbots: Identifizieren Sie nahezu ähnliche Eingaben und trainieren Sie ein Modell, um die beste Antwort aus der Wissensdatenbank zu ermitteln.
- Empfehlungs-Engine: Gruppieren Sie Elemente mit nahezu ähnlichen Funktionen und empfehlen Sie Benutzern Elemente.
Fühlen Sie sich frei, LSH für Ihre eigenen Probleme zu erforschen und auszuprobieren! 🙂
Referenzen zu LSH
Diese Artikel veranschaulichen sehr gut, wie LSH funktioniert und zeigen auch Beispiele.
Hier ist ein Kurs über das Mining massiver Datensätze, in dem LSH behandelt wird.
Folgen Sie uns!
Wir veröffentlichen kontinuierlich Artikel über Maschinelles Lernen, Deep Learning, NLP, probabilistische Programmierung und Analyseprojekte, die wir bei Kalibrr Research durchführen. Folgen Sie uns, um über unsere nächsten Beiträge informiert zu werden! 🙂