Erkennung ähnlicher Duplikate mit Jaccard-Ähnlichkeit und MinHash

 (blog.nelhage.com)
1 Punkte von GN⁺ 2024-07-06 | 1 Kommentare | Auf WhatsApp teilen
  • In großen Dokumentkollektionen kann es beim Web-Crawling vorkommen, dass dieselbe Seite mehrfach erfasst wird oder leicht veränderte Versionen enthalten sind; Jaccard-Ähnlichkeit und MinHash sind daher ein praktischer Ansatz, um „fast gleiche“ Dokumente zu finden
  • Die Jaccard-Ähnlichkeit wandelt Dokumente in Merkmalsmengen um und berechnet dann Größe der Schnittmenge / Größe der Vereinigungsmenge; Paare oberhalb eines Schwellenwerts gelten als ähnliche Duplikate, aber diese Beziehung ist im Allgemeinen nicht transitiv
  • Der Vergleich aller Dokumentpaare verursacht in Bezug auf die Korpusgröße Kosten von O(n²), daher fasst MinHash jedes Dokument in einer Signatur fester Größe zusammen und approximiert die Ähnlichkeit probabilistisch
  • Verwendet man k Hashfunktionen, lässt sich die Ähnlichkeit aus dem Anteil der übereinstimmenden Positionen in den Signaturen zweier Dokumente schätzen; bei der Wahl der Hashfunktionen sind Bedingungen wie min-wise independence wichtig
  • Nutzt man die gesamte Signatur oder Teile davon als Gruppenschlüssel, lässt sich die Wahrscheinlichkeit steuern, dass ähnliche Dokumente in denselben Bucket fallen; n-Gramme und die Tokenisierung bestimmen dabei Empfindlichkeit und Kosten der Erkennung

Die Schwierigkeit bei der Erkennung ähnlicher Duplikate

  • Ziel ist es, in einer großen Dokumentmenge Dokumente zu finden, die nicht exakt gleich, aber fast identisch sind
    • Wenn man das Web über einen bestimmten Zeitraum crawlt, kann dieselbe Seite mehrfach erfasst werden, wobei sich die Metadaten leicht unterscheiden
    • Es kann auch mehrere geringfügig bearbeitete Versionen einer Seite geben
  • Der grundlegende Ansatz besteht darin, eine Ähnlichkeitsfunktion S(A, B) zwischen zwei Dokumenten zu definieren und Paare mit einem Wert von mindestens Scrit als ähnliche Duplikate zu behandeln
  • „Fast identisch“ ist im Allgemeinen keine transitive Relation
    • A und B sowie B und C können oberhalb des Schwellenwerts ähnlich sein
    • Gleichzeitig kann A und C unterhalb des Schwellenwerts liegen
    • Deshalb ist die Erkennung ähnlicher Duplikate in großem Maßstab schwieriger zu handhaben als die Erkennung exakter Duplikate

Definition der Jaccard-Ähnlichkeit

  • Der Jaccard-Index beschreibt die Ähnlichkeit zweier endlicher Mengen als Größe der Schnittmenge / Größe der Vereinigungsmenge

    [ J(A, B) = \frac{|A \cap B|}{|A \cup B|} ]

  • Wenn zwei Mengen ähnlich sind, enthalten sie größtenteils dieselben Elemente; dadurch wächst die Vereinigungsmenge nur wenig und die Schnittmenge wird nur wenig kleiner

  • Sind zwei Mengen vollständig getrennt, ist die Größe der Schnittmenge 0 und die Jaccard-Ähnlichkeit damit 0

  • Sind zwei Mengen identisch, sind Schnittmenge und Vereinigungsmenge dieselbe Menge und die Jaccard-Ähnlichkeit wird 1

  • Reale Dokumente liegen als Unicode-Strings oder in ähnlichen Formen vor; daher muss man ein Dokument zuerst in eine Merkmalsmenge umwandeln

Das Skalierungsproblem beim Vergleich aller Paare

  • Nachdem Dokumente in Merkmalsmengen umgewandelt wurden, ist die Definition, Paare mit hoher Jaccard-Ähnlichkeit zu finden, an sich einfach
  • Vergleicht man jedoch alle Dokumentpaare, steigen die Kosten in Bezug auf die Korpusgröße auf O(n²)
  • Bei der Erkennung exakter Duplikate vermeidet man diese Kosten, indem man Dokumente hasht und solche mit demselben Hash-Bucket gruppiert
  • Auch bei der Erkennung ähnlicher Duplikate braucht man einen ähnlichen Umweg; in diesem Bereich spricht man von Locality-Sensitive Hashing
  • Für die Jaccard-Ähnlichkeit gibt es dafür ein geeignetes Verfahren, dessen Kern MinHash ist

Approximation der Jaccard-Ähnlichkeit mit MinHash

  • MinHash approximiert die Jaccard-Ähnlichkeit, ohne jedes Mal ganze Mengen zu vergleichen, sondern nur anhand einer kleinen, vorab berechneten Signatur pro Dokument

  • Die Grundidee ist ein Sampling, bei dem aus der Vereinigungsmenge gleichverteilt ein zufälliges Element gezogen wird und geprüft wird, ob es auch in der Schnittmenge enthalten ist

  • In der Praxis verwendet man statt einer Zufallspermutation eine gute Hashfunktion H(x) und speichert für jede Menge das Merkmal mit dem kleinsten Hashwert

    [ a_{min} \leftarrow \min_{x \in A} H(x) ]

    [ b_{min} \leftarrow \min_{x \in B} H(x) ]

  • Die min-Operation ist assoziativ, daher kann man den minimalen Hashwert jedes Dokuments unabhängig vorverarbeiten

  • Die Wahrscheinlichkeit, dass die minimalen Hashwerte zweier Mengen gleich sind, ist gleich ihrer Jaccard-Ähnlichkeit

Mehrere Hashfunktionen und Signaturvektoren

  • Mit nur einer Hashfunktion ist für zwei Dokumente lediglich eine boolesche Schätzung „gleich/ungleich“ möglich

  • Mit k verschiedenen Hashfunktionen kann man jedes Dokument zu einem Vektor aus k MinHash-Werten verdichten

    [ A_{sig} = (\min_{x \in A} H_1(x), \min_{x \in A} H_2(x), \dots, \min_{x \in A} H_k(x)) ]

  • Die Jaccard-Ähnlichkeit wird durch den Anteil der Positionen approximiert, an denen zwei Signaturen denselben Wert haben

    [ J(A, B) \approx \frac{1}{k} \sum_{i=1}^{k} (A_{sig}[i] = B_{sig}[i]) ]

  • Die Wahl der Familie von Hashfunktionen ist heikel

    • Das Ziel ist, eine zufällige Permutation des gesamten Merkmalsraums zu approximieren
    • Reale Familien von Hashfunktionen repräsentieren nur einen winzigen Teil aller möglichen Permutationen
    • Ungeeignete Korrelationen müssen vermieden werden; die relevante Eigenschaft heißt min-wise independence
    • Dieses Problem ist vergleichsweise gut untersucht, und in der Literatur gibt es effiziente Lösungen

Kandidatenpaare im gesamten Korpus finden

  • Wenn jedes Dokument auf einen Fingerabdruck aus k Hashwerten reduziert wird, lässt sich die Jaccard-Ähnlichkeit effizient approximieren
  • Das verbleibende Problem ist, im gesamten Korpus Dokumente mit hoher Ähnlichkeit zu finden, ohne alle Dokumentpaare anzusehen
  • Die Strategie besteht darin, Dokumente nach einem Schlüssel zu gruppieren und nur innerhalb derselben Gruppe zu vergleichen
  • Der Gruppenschlüssel sollte so gewählt werden, dass ähnliche Dokumente mit hoher Wahrscheinlichkeit zusammen gruppiert werden, unähnliche jedoch möglichst nicht

  • Die vollständige MinHash-Signatur als Schlüssel verwenden

    • Die einfachste Methode besteht darin, alle k MinHash-Werte als einen einzigen Gruppenschlüssel zu verwenden
    • Zwei Dokumente gelten nur dann als ähnliche Duplikate, wenn alle MinHash-Werte übereinstimmen
    • Das GPT-3-Paper nutzte die Entfernung ähnlicher Duplikate in der Pipeline zur Datensatzvorbereitung; anhand der zitierten Formulierung lässt sich das als Verwendung von Sparks MinHashLSH-Implementierung mit 10 Hashes interpretieren
    • Der Vorteil dieses Ansatzes liegt in Einfachheit und Effizienz
    • Das Gruppieren nach einem einzelnen Byte-String mit hoher Kardinalität lässt sich leicht horizontal skalieren
    • Es entspricht einem grundlegenden Primitive von Datenverarbeitungswerkzeugen, etwa dem „shuffle“ zwischen map und reduce in MapReduce
    • Wenn die Jaccard-Ähnlichkeit zweier Dokumente J(A, B) beträgt und alle k Werte übereinstimmen müssen, dann ist die Kollisionswahrscheinlichkeit für ein einzelnes Paar J(A, B)^k
    • Bei k = 10 kollidieren Dokumente mit einer Ähnlichkeit von ungefähr 0,6 oder weniger fast nie
    • Die Übereinstimmungswahrscheinlichkeit steigt in der Nähe einer Ähnlichkeit von etwa 0,95 deutlich an
    • Wenn das Ziel darin besteht, sehr nahe Dokumentgeschwister zu finden, kann das ausreichend sein
    • Diese J^k-Berechnung gilt für ein einzelnes Dokumentpaar
    • Wenn es viele sehr ähnliche Dokumente gibt, sind die Wahrscheinlichkeiten pro Paar nicht unabhängig
    • In der Praxis landen sehr ähnliche Dokumente meist in nur zwei oder drei Buckets, sodass sich fast alle Duplikate finden lassen

Lockerere Duplikaterkennung

  • Wenn man nicht nur Dokumente mit Ähnlichkeit nahe 1 finden möchte, sondern auch solche ab 0,8 oder 0,7, kann die vollständige Signatur als Schlüssel zu streng sein

  • Verwendet man nur einen Teil der k MinHashes als Gruppenschlüssel, steigt die Kollisionswahrscheinlichkeit auch bei geringerer Ähnlichkeit

    • Beispielsweise kann man nach den ersten 4 MinHash-Werten gruppieren und innerhalb desselben Buckets dann mit der vollständigen MinHash-Signatur die tatsächliche Ähnlichkeit schätzen

  • Die Reduktion der Zahl der Hashes hat allerdings Grenzen

    • J^r ist immer kleiner als J
    • Wenn r zu klein wird, kann es zu zu vielen falschen Kollisionen kommen

  • Stattdessen kann man für jedes Dokument mehrere Schlüssel erzeugen und es in mehrere Buckets einordnen

    • Man kann zum Beispiel k = 20 Hashes berechnen, in b = 4 Buckets einordnen und jeden Schlüssel aus r = 5 Hashes zusammensetzen

  • Die Wahrscheinlichkeit, dass zwei Dokumente in mindestens einem Bucket kollidieren, ist dann

    [ p = 1 - (1 - J^r)^b ]

  • Im Beispiel mit 4 Gruppen und 5 Hashes pro Gruppe verschiebt sich der Punkt, an dem die Kollisionswahrscheinlichkeit 50% beträgt, in die Nähe von J = 0.7

  • Wenn r und b beide größer als 1 sind, hat die resultierende Kurve typischerweise eine S-Form und bietet Spielraum für den Ausgleich zwischen Empfindlichkeit, Recall und Performance-Kosten

Zusammenhang mit HyperLogLog

  • Der zentrale Trick von MinHash ähnelt Sketch-Algorithmen wie HyperLogLog
  • HyperLogLog hasht jedes Element eines Streams und speichert das laufende Maximum der Anzahl führender Nullen im Hashwert
  • Beide Verfahren bilden Eingabeelemente mittels einer Hashfunktion auf eine Gleichverteilung ab und schätzen dann Verteilungseigenschaften mithilfe von Zusammenfassungen konstanter Größe, indem sie laufende Extremwerte berechnen
  • HyperLogLog kann, wenn man die Bitreihenfolge umkehrt, als Verfahren betrachtet werden, das das laufende Minimum von log2(H(x)) berechnet, während MinHash das Minimum von H(x) selbst verwendet
  • Die beiden Strukturen sind in gewissem Sinne dual
    • Durch die Kombination zweier HyperLogLog-Strukturen lässt sich die Größe der Vereinigungsmenge zweier Mengen schätzen
    • Durch den Vergleich zweier MinHash-Strukturen lässt sich die relative Größe der Schnittmenge zweier Mengen schätzen
  • Kombiniert man beide Strukturen, kann man Sketches bauen, die Fragen zu Schnitt- und Vereinigungsmenge beliebiger Mengen behandeln

Wie man Dokumente als Mengen darstellt

  • Um Jaccard und MinHash zu verwenden, muss ein Textdokument zunächst in eine Merkmalsmenge umgewandelt werden
  • Unabhängig von der gewählten Methode kann man Dokumente per Vorverarbeitung normalisieren
    • Umwandlung in eine standardisierte Unicode-Normalisierungsform
    • Kleinschreibung
    • Zusammenfassen aufeinanderfolgender Leerzeichen
    • und ähnliche Transformationen

  • n-Gramme oder Shingles

    • Ein Dokument kann als Menge aller darin vorkommenden n-Gramme dargestellt werden
    • In der Literatur zur großskaligen Textverarbeitung wird auch der Begriff „shingle“ verwendet; hier erfüllt er dieselbe Rolle wie n-Gramme
    • Die Wahl von n ist ein Kompromiss
    • Kleine Werte vergleichen Dokumente gröber
    • So kann zum Beispiel der Großteil englischer Texte aus Sicht von Bigrammen recht ähnlich wirken
    • Große Werte erzeugen unterscheidungskräftigere Merkmale und größere Mengen
    • Werden sie zu groß, kann die Empfindlichkeit sinken; meist treten aber schon vorher Performance-Probleme auf
    • Laut Mining of Massive Datasets §3.2.2 sind in vielen Anwendungen Werte zwischen n = 5 und 9 eine übliche Wahl

  • Trennung in Wörter oder Tokens

    • Man kann die Eingabe auch in „Wörter“ oder „Tokens“ zerlegen und diese als Merkmale verwenden
    • Der Auszug aus dem GPT-3-Paper erwähnt den Standard-Tokenizer von Spark; gemeint ist offenbar pyspark.ml.feature.Tokenizer, der Eingaben in Kleinbuchstaben umwandelt und anhand von Leerzeichen trennt
    • Alternativ kann man einen ausgefeilteren NLTK-Tokenizer verwenden
    • Möglich ist auch ein hybrider Ansatz, bei dem nach der Tokenisierung n-Gramme aus Tokens gebildet werden
    • Einzelne Tokens haben eine höhere Entropie als Bytes oder Zeichen; deshalb verwendet man in diesem Fall kleinere n-Werte

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-07-06
Meinungen auf Hacker News

  • Es wird oft übersehen, dass mengenbasierte Metriken wie die Jaccard-Ähnlichkeit (Tanimoto-Koeffizient) oder der F1-Score (Dice-Koeffizient) genauso auch auf Fuzzy-Mengen angewendet werden können
    Allerdings muss man ein passendes T-Norm-/T-Conorm-Paar wählen, um die Konzepte von Schnittmenge und Vereinigung bei Fuzzy-Mengen auszudrücken; davon gibt es unendlich viele
    Eher ist es ein Vorteil, dass man ein Paar auswählen kann, das zur gewünschten Semantik passt
    Bei der Validierung medizinischer Bildsegmentierung habe ich mich damit beschäftigt, wenn Segmentierungsergebnis und Ground Truth keine binären Masken, sondern probabilistische/Fuzzy-Formen sind: https://link.springer.com/chapter/10.1007/978-3-319-46723-8_..., https://ora.ox.ac.uk/objects/uuid:dc352697-c804-4257-8aec-08...
    Üblicherweise setzt man einen Schwellwert von 0,5, erzeugt daraus eine binäre Menge und verwendet dann die binären Varianten von Jaccard/Dice; dadurch scheint die Genauigkeit des Validierungsoperators um etwa zwei Größenordnungen zu sinken
    Man verkündet dann, der Algorithmus sei um 0,001 besser als der Stand der Technik, ignoriert aber, dass die Fehlerspanne des Validierungsoperators bei 0,1 liegt

  • Um Bürgerdatensätze in einer großen Datenbank der französischen Regierung zu deduplizieren, hatte ein Kunde einmal eine eigene Python-Implementierung dieser Technik gebaut, und sie funktionierte gut
    Heute würde ich vermutlich empfehlen, datasketch zu verwenden: https://pypi.org/project/datasketch/
    Beim Nachsehen stellte sich heraus, dass zu diesem Thema weiterhin neue Tools entstehen. Zum Beispiel ist https://pypi.org/project/rensa/ eine stärker spezialisierte und schnellere Version als MinHash in datasketch, in Rust geschrieben und mit etwas Python darüber

    • Für die Deduplizierung von Personen ist auch das Fellegi-Sunter-Modell ein starker Ansatz. Splink ist eine freie Python-Bibliothek, die dies für große Datensätze implementiert, und möglicherweise lassen sich Teile beider Ansätze kombinieren
      Hinweis: Ich bin der Hauptautor
      Ich habe auch ein interaktives Tutorial geschrieben, das die Funktionsweise erklärt: https://github.com/moj-analytical-services/splink, https://www.robinlinacre.com/intro_to_probabilistic_linkage/
    • Es gibt auch gaoya. Das stammt von mir, ist in Rust geschrieben und bietet auch Python-Bindings
      datasketch ist großartig, war für meinen Anwendungsfall aber nicht performant genug; gaoya wird in einem großen operativen Clustering-System eingesetzt: https://github.com/serega/gaoya

  • Ein erstaunlicher Zufall. Ich habe gerade ein MinHash-System implementiert, das für manche interessant sein könnte
    Das Problem besteht darin, die Pseudoinverse mehrerer geeigneter Teilmatrizen aus einer großen quadratischen Matrix zu finden
    Mit Matrixidentitäten wie Woodbury und Banachiewicz kann man die Inverse einer „nahen“ Teilmatrix aktualisieren und so eine neue Inverse günstig berechnen
    Man speichert bereits berechnete Inversen mit Zeilen-/Spaltenindizes als Schlüssel und sucht für jede neue Teilmatrix eine nahe vorhandene Inverse als Ausgangspunkt für die Aktualisierung
    Ich habe dieses Problem mit MinHash gelöst und die Indizes per Minimum-Hashing verarbeitet, sodass nahe Matrizen mit hoher Wahrscheinlichkeit denselben Hash haben
    In meiner Implementierung habe ich Multi-Resolution-Hashes verwendet, damit sich die Selektivität der Suche anpassen lässt, wenn die Zahl der bereits berechneten Inversen wächst

  • Um etwas Hintergrund zu ergänzen, der in diesem Artikel fehlt: Ich hatte verstanden, dass diese Technik in den frühen Tagen von Google zur Deduplizierung der Crawling-Menge entwickelt wurde
    Interessant ist auch, wie überraschend ähnlich das Erstellen von LLMs und das Erstellen eines gewöhnlichen Index für Webtexte sind
    In Jeffrey Ullmans kostenlosem Buch „Mining Massive Datasets“ kann man dazu ausführlich lesen; es beschreibt viele elegante und beeindruckende Techniken, die damals zum Aufbau eines Index des gesamten Internets verwendet wurden
    Das entsprechende Material findet man kostenlos, wenn man nach „chapter 3 pdf mmds ullman“ sucht
    Korrektur: Wie sich herausstellt, lag ich falsch; laut Wikipedia wurde es bei DEC für AltaVista erfunden: https://en.wikipedia.org/wiki/MinHash
    In jedem Fall enthält Ullmans Buch eine gute Erklärung und behandelt auch, wie es bei Google eingesetzt wurde

  • Beim Versuch, MinHash und seine Varianten zu verstehen, wollte es mir nicht recht in den Kopf, deshalb baue ich ein Online-Visualisierungstool: https://websla.sh/tools/minhash
    Es ist noch nicht fertig, und ich möchte auch Dinge wie die Berechnung der Jaccard-Ähnlichkeit zeigen, aber schon jetzt kann man mehrere Strings eingeben und direkt sehen, was „minhash“ tatsächlich ist

  • Hashing oder kleine neuronale Netze zusammen mit einer Vektorsuchmaschine und Tanimoto/Jaccard zu verwenden, ist eine sehr verbreitete Strategie zur Deduplizierung großer Datensätze
    Das kann klüger sein als ein MapReduce-Job mit linearer Komplexität
    Ein gutes Projekt von Google nutzt das RETSim-Modell mit 500.000 Parametern und die USearch-Engine: https://github.com/google/unisim

  • Ich habe gerade ein ähnliches Problem in PostgreSQL. Es gibt 600.000 feed_items, und das Schema ist (feed_item_id uuid, author varchar, content text, guid varchar, link varchar, title varchar, summary text, feed_id integer)
    Insbesondere sind bei einigen News-Einträgen die Spalten content und summary sehr ähnlich, aber nicht identisch.
    Wenn zwei solche News-Einträge gegeben sind und ich sie auf einen reduzieren möchte: Gibt es dafür eine gute Methode?

    • Ich habe in BigQuery ein MinHash-ähnliches System implementiert und konnte die Kosinus-Ähnlichkeit zwischen allen Stack-Overflow-Einträgen in vertretbarer Zeit berechnen.
      Der grobe Ablauf ist folgender:
      1. Alle Textfelder aneinanderhängen und in ein Array von n-Grammen zerlegen, zum Beispiel in Einheiten von 2 bis n Zeichen.
      2. Globale Arrays A und B der Länge n deklarieren und mit zufälligen 32- bis 64-Bit-Integern füllen.
      3. Jedes n-Gramm zu einem 32- bis 64-Bit-Integer hashen, diesen Hash dann mit jedem Zufallswert aus Array A multiplizieren, den Rest bei Division durch den jeweiligen Zufallswert aus Array B bilden und den Minimalwert nehmen.
        Ziel ist es, für jede Zeile ein „minhashed“ Integer-Array derselben Länge wie die Arrays aus Schritt 2 zu erhalten. Wenn man die Länge des globalen Arrays als 64 festlegt, hat auch das MinHash-Array jeder Zeile die Länge 64.
      4. Mit einer Window-Funktion fortlaufende N MinHash-Werte aufsummieren und damit das Hash-Array in Buckets einteilen. Zum Beispiel jeweils 4 aufeinanderfolgende Zeilen aufsummieren.
        Wenn alles gut funktioniert hat, kann man dieses Array auffalten, als „Quellzeile“ verwenden und den Datensatz anhand jedes gebucketeten MinHash-Werts mit sich selbst joinen; dadurch kommt eine Spalte „Zielzeile“ hinzu.
        Gruppiert man nach Quell-/Zielspalte und zählt die Vorkommen, lässt sich abschätzen, wie ähnlich zwei Zeilen sind.
        Im Kern gilt: Je häufiger zwei Einträge in ähnliche Buckets gehasht werden, desto ähnlicher sind sie. Ab welchem Punkt man die tatsächliche paarweise Jaccard- oder Kosinus-Ähnlichkeit berechnet, muss man selbst festlegen.
    • Hier könnte ein Ansatz mit Text-Embeddings und Kosinus-Ähnlichkeit nützlich sein: https://simonwillison.net/2023/Oct/23/embeddings/
    • Mit MinHash kann man die vollständige O(N^2)-Distanzmatrix vermeiden, aber bei nur 600.000 Einträgen könnte es der Einfachheit halber auch reichen, die vollständige Matrix brachial zu berechnen.
      Entscheidend ist, welches Zeitbudget man hat.
    • Wenn man annimmt, dass zwei Einträge sehr ähnliche Keywords behandeln, dürfte die Jaccard-Distanz gut passen.
      Wenn man annimmt, dass zwei Einträge sehr ähnliche Texte teilen, wäre die Levenshtein-Distanz einen Versuch wert.
    • Man kann ein LLM einen invertierten Index für die Einträge erstellen lassen, dabei aber erzwingen, dass die Kardinalität niedrig bleibt.
      Dann kann man die Jaccard-Ähnlichkeit verwenden.

  • Mir gefällt der Beitrag. Unser Team bei NVIDIA hat kürzlich eine GPU-beschleunigte Version des beschriebenen Fuzzy-Deduplication-Algorithmus veröffentlicht, und ich denke, diese Community könnte daran interessiert sein.
    Das Repository ist hier: https://github.com/NVIDIA/NeMo-Curator/
    Die Dokumentation zum Fuzzy-Deduplication-Skript findet sich hier: https://docs.nvidia.com/nemo-framework/user-guide/latest/dat...
    Es gibt auch ein Python-Beispiel: https://github.com/NVIDIA/NeMo-Curator/blob/main/examples/fu...
    Ich würde mich über Feedback freuen.

  • Solche Techniken versteht man beim Lesen oft nicht, aber wenn man ein paar Mal eigene Daten in ein funktionierendes Codebeispiel steckt und sich die internen Abläufe ansieht, erschließen sie sich sofort.
    Ich habe diese Technik zuerst von Douglas Eck gelernt: https://research.google/people/douglas-eck/
    Bei Google wurde sie für Song-Clustering verwendet, und ich erinnere mich, dass er über Hashing und Zufallsvektoren sprach.
    Damals war ich verwirrt, weil ich dachte, eine Optimierung mit weniger Zufälligkeit müsste besser funktionieren.

    • Die zentrale Intuition ist, zumindest für mich: Wenn man ein Objekt in einen Haufen winziger Stücke zerlegt und n verschiedene Arten erzeugt, diese Haufen zu sortieren, dann landen bei ähnlichen Objekten in mehreren Sortierungen dieselben Stücke ganz oben.
      Kombiniert man das mit Banding und einfacher Wahrscheinlichkeit, kann man die Jaccard-Ähnlichkeit in riesigen Datensätzen billig und sehr leicht parallelisierbar approximieren.

  • Wenn man das als Technik für Dokument-Clustering oder Dataset-Deduplizierung betrachtet: Wie schneiden Ansätze, die „maschinelles Lernen auf das Problem werfen“, in Qualität und Performance gegenüber einfacheren diskreten Algorithmen wie diesem ab?
    Zum Beispiel: mit einem vortrainierten LLM-Encoder Dokument-Vektor-Embeddings erzeugen, diese Vektoren in eine Vektor-DB legen und anschließend mit k-Means clustern.

    • Ein LLM ist nur eine von mehreren Möglichkeiten, Embeddings zu erzeugen.
      Für k-Means muss man trotzdem eine Distanzfunktion wie Jaccard auswählen, und k-Means ist für Near-Duplicates vermutlich nicht ideal.
      Man könnte MinHash als Vorverarbeitung für k-Means verwenden, um es zu beschleunigen.
      Ich sehe nicht, dass eine Vektor-DB dabei besonders viel hilft.
      Wenn man Hunderte Millionen Dokumente hat, könnte man sie nutzen, um MinHash-Sketch-Lookups zu beschleunigen, aber meist dürfte das überdimensioniert sein.
    • Ich habe schon gesehen, dass so ein Ansatz besser funktioniert als LSH.
      Bei jedem Einbetten eines Dokuments sucht man vor dem Hinzufügen nach ungefähren nächsten Nachbarn, daher ist es wie MinHash O(N).
      Vektorindizes wie HNSW und PQ bieten bei Performance/Qualität einen besseren Trade-off als SimHash-LSH, das MinHash für Kosinus-Distanz entspricht.
      Die Qualität hängt davon ab, wie man Near-Duplicates definiert und welches Embedding-Modell man verwendet.
      Moderne Modelle funktionieren gut, und mit gelabelten Daten kann man sie durch Fine-Tuning noch verbessern.
      Der wichtigste Nachteil sind die Zusatzkosten für das Einbetten aller Dokumente, was besonders bei langen Dokumenten ins Gewicht fällt.
      Dank kleinerer Modelle, besserer Optimierungen und schnellerer Hardware sind diese Kosten jedoch sehr schnell gesunken.