40 Millionen HN-Posts und Kommentare über eine Embedding-Karte erkunden

 (blog.wilsonl.in)
2 Punkte von GN⁺ 2024-05-10 | 2 Kommentare | Auf WhatsApp teilen
  • Ein Such-, Karten- und Analyseprojekt, das über 40 Millionen Elemente aus der öffentlichen Hacker-News-API gesammelt und mehr als 30 Millionen Kommentare sowie 4 Millionen Posts mit Embeddings, Metadaten und Volltext versehen hat
  • Der frühe Ansatz, nur Titel einzubetten, stieß wegen mehrdeutiger Titel und eines Bias durch Ask HN/Show HN an Grenzen; deshalb wurde auf ein Verfahren umgestellt, das zusätzlich den Text verlinkter Webseiten, Top-Kommentare und den Kontext übergeordneter Kommentare nutzt
  • Mit wachsendem Verarbeitungsumfang wurden rund 150 GPUs von RunPod, ein Rust-Queue-Service, ein HTTP/2-DB-Proxy, UMAP, Canvas-Rendering und Edge-Server kombiniert; nach dem Modellwechsel sank die Embedding-Zeit pro Eingabe von etwa 600 ms auf 6 ms
  • Das Suchranking basiert nicht auf einfacher String-Übereinstimmung, sondern kombiniert Kosinus-Ähnlichkeit, HN-Score und Zeitgewichtung, um semantische Relevanz, soziale Signale und Aktualität abzubilden
  • Die öffentliche Demo enthält nur Daten bis ungefähr zum 10. April 2024; die vollständigen Daten und der Code sind auf GitHub veröffentlicht und können für Suche, Empfehlungen, Nutzeranalyse und Experimente mit Echtzeit-Aktualisierung verwendet werden

Projektumfang und veröffentlichte Daten

  • Es wurde eine Karte erstellt, die alle Posts von Hacker News im semantischen Raum anordnet, ergänzt um Werkzeuge für Suche, Analyse und Visualisierung
  • Ausgangspunkt waren Experimente mit Text-Embeddings; HN wurde als geeigneter Datensatz gewählt, weil es viel kuratierten Content enthält und alle Inhalte programmatisch verfügbar sind
  • Embeddings stellen Text als Punkte in einem hochdimensionalen Raum dar; nützlicher als die absolute Position ist dabei die relative Distanz zwischen den Punkten
  • Erwartet wurden drei Einsatzmöglichkeiten
    • semantische Suche in den angesammelten Inhalten von HN
    • personalisierte Empfehlungen passend zu Interessengebieten
    • Analyse von Stimmung, Popularität und Gegenpositionen zu Themen innerhalb der Community
  • Mehr als 30 Millionen Kommentare und 4 Millionen Posts wurden als Dataset-Release veröffentlicht
    • einschließlich Metadaten wie ID, Score und Autor
    • einschließlich Embeddings
    • einschließlich Kommentartexten und gecrawlten Webseitentexten
  • Der Code wurde im hackerverse GitHub-Repository veröffentlicht

Erfassung der Hacker-News-Daten

  • HN bietet eine einfache öffentliche API; alle Objekte werden als item abgerufen
  • maxitem.json liefert die höchste ID, und zum Zeitpunkt des Schreibens lag diese bei über 40 Millionen
  • Selbst bei einer durchschnittlichen Antwortzeit von 10 ms würde das sequentielle Crawlen von 40 Millionen Einträgen mehr als vier Tage dauern, daher war Parallelisierung nötig
  • Zunächst wurde ein schneller Erfassungsdienst in Node.js gebaut, doch der Ansatz mit Semaphore und Promise-Queue war langsam, weil der Großteil der CPU-Zeit in JS-Code im User Space verbraucht wurde
  • Danach wurden mit der API worker_threads Fetch-Aufgaben auf alle CPUs verteilt, was die Leistung durch Auslastung aller Kerne verbesserte
  • Da paralleles Sammeln die Reihenfolge durcheinanderbringt, wurden Completion-Marker in ID-Reihenfolge protokolliert, damit bei Unterbrechungen keine Lücken entstehen
  • Es gab auch beobachtete Eigenschaften der HN-API
    • Scores scheinen nicht unter -1 zu fallen
    • Downvotes für Posts und die Stimmenzahl für Kommentare lassen sich nicht abrufen
    • Bei einigen Posts und Kommentaren sind Titel, Text und URL leer, obwohl sie weder gelöscht noch geflaggt sind
    • Kommentar-IDs können kleiner sein als die ihrer Vorfahren, möglicherweise wegen Verschiebungen im Kommentarbaum
  • Der HN-Crawler wurde außerdem als separates TypeScript-Projekt crawler-toolkit-hn ausgegliedert

Erste Embeddings und Infrastruktur

  • Anfangs wurde davon ausgegangen, dass bereits Posttitel allein für eine ausreichende semantische Repräsentation genügen würden, und darauf basierend wurden Embeddings erzeugt
  • Für den Modellvergleich wurde das Massive Text Embedding Benchmark herangezogen; das zuerst gewählte Modell war BGE-M3
  • BGE-M3 kann zusätzlich zu gewöhnlichen dichten Embeddings auch lexical weights erzeugen und eignet sich damit für hybride Suche in Kombination mit Verfahren wie BM25
  • Die Infrastruktur für die Embedding-Erzeugung war nicht trivial
    • gute Modelle können Hunderte Millionen bis Milliarden Parameter haben
    • auf GPUs sind sie deutlich effizienter, aber GPU-Cluster sind teuer
    • wenn Inferenz pro Eingabe Hunderte Millisekunden dauert, entspräche die Verarbeitung von 40 Millionen Eingaben auf einer einzelnen GPU fast einem Jahr
    • da Daten, Server und GPUs getrennt waren, musste die Pipeline so gestaltet werden, dass die GPUs nicht untätig bleiben
  • Mit RunPod wurden GPU-Maschinen in Rechenzentren als Container ausgerollt, wobei relativ günstige GPUs wie die RTX 4090 genutzt wurden
  • Weil die GPUs weltweit verteilt waren und dadurch DB-Latenz sowie Verbindungs-Overhead zum Problem wurden, entstand db-rpc
    • SQL-Abfragen werden per HTTP/2 an eine lokale DB weitergeleitet
    • es nutzt einen großen gemeinsamen Connection Pool
    • per HTTP/2-Multiplexing können mehrere Queries über eine einzelne Verbindung laufen
  • Da AWS SQS bei Millionen kleiner Job-Nachrichten wegen niedriger Durchsatzlimits und Kosten pro Nachricht unpraktisch war, wurde der RocksDB-basierte Rust-Queue-Service queued entwickelt
    • auf einem einzelnen Node verarbeitet er 100K+ op/s
    • dadurch werden Batching-, Nachrichtengrößen-, Durchsatz- und Kostenprobleme reduziert
  • Durch die Skalierung auf etwa 150 GPUs konnten 40 Millionen Posts und Kommentare in wenigen Stunden eingebettet werden
  • Damals lagen die Embedding-Kosten pro Eingabe bei etwa 600 ms, und die GPU-Auslastung blieb über die gesamte Laufzeit hoch

Mehr Kontext durch Crawlen von Webseiten

  • Das Einbetten nur der Titel war nicht ausreichend
    • viele Posts haben ungewöhnliche, kreative oder mehrdeutige Titel
    • Formulierungen wie Ask HN und Show HN nehmen im Titel oft viel Raum ein, wodurch sie unabhängig vom eigentlichen Thema dazu tendieren, gemeinsam geclustert zu werden
  • Bei Text-Posts und Kommentaren konnte der eigene Text verwendet werden, bei den meisten Link-Posts musste jedoch die verlinkte Webseite gecrawlt werden
  • Ein Rust-Service rief URLs ab und extrahierte aus HTML Metadaten wie Titel, Bild, Autor und Fließtext
  • Eine frühe Node.js-Version war bei CPU-intensiven Aufgaben zehnmal langsamer als die Rust-Version; eine Neuschreibung in Rust verbesserte die Leistung
  • Die Textextraktion erfolgte, indem HTML mit scraper geparst, semantisch nicht zum Hauptinhalt gehörende HTML5-Elemente entfernt und anschließend der verbleibende Baum durchlaufen wurde
  • Link Rot war ebenfalls erheblich
    • rund 200.000 URLs schlugen mit 404, fehlgeschlagener DNS-Auflösung oder Verbindungs-Timeout fehl
    • das sind weniger als 5 % von 4 Millionen Seiten
  • Um Lücken zu verringern, wurden über die Wayback API des Internet Archive einige ältere Artikel bezogen
    • das Rate Limit des Internet Archive war mit ungefähr 5 Anfragen pro Minute sehr niedrig

Zweite Embedding-Strategie

  • Webseiten sind lang, aber BGE-M3 unterstützt ein Kontextfenster von 8192 Token
  • Allerdings war BGE-M3 langsam, daher wurde auf jina-embeddings-v2-small-en gewechselt
    • es hat deutlich weniger Parameter
    • auch die Leistung gemäß MTEB ist solide
    • die Inferenzzeit sank auf etwa 6 ms und wurde damit 100-mal schneller
  • Wegen der langen Eingaben führte eine größere Batch-Größe zu OOM, sodass die GPUs nicht vollständig ausgelastet werden konnten
  • Um Seiten mit wenig Text oder nicht abrufbare Seiten zu ergänzen, wurden die Top-HN-Kommentare eines Posts hinter den Haupttext angehängt
    • es wurde angenommen, dass Kommentare der obersten Ebene in item.kids bereits gerankt sind
    • gelöschte, dead- oder negativ bewertete Kommentare wurden ausgeschlossen
    • die Eingabe wurde auf maximal 64 KiB begrenzt
  • Da Kommentare allein semantisch oft zu wenig hergeben, wurde zusätzlicher Kontext aufgebaut, indem bis zu den Vorfahren-Kommentaren und zum Posttitel zurückgegangen wurde
  • Große Werte wie Embeddings und Text wurden in einer separaten kv-Tabelle gespeichert
    • eine gemeinsame Speicherung in der Zeile hätte die Zeilen aufgebläht
    • auch Updates kleiner Spalten wären teurer geworden
    • ebenso Schemaänderungen

Eine semantische 2D-Karte mit UMAP erstellen

  • UMAP ist ein Verfahren zur Dimensionsreduktion, das hochdimensionale Embeddings auf niedrigere Dimensionen abbildet und dabei semantische Beziehungen möglichst erhält
  • 1024-dimensionale Embedding-Vektoren wurden auf 2D-Punkte reduziert und für Scatterplots sowie Kartenvisualisierungen verwendet
  • UMAP bekam den PyNNDescent-Graphen und die ursprünglichen Embeddings als Eingabe; verwendet wurden metric="cosine" und n_components=2
  • Das Training mit Millionen hochdimensionaler Eingaben dauerte lange, daher wurde eine EC2-VM vom Typ c7i.metal-48xl eingesetzt
    • Die 96-Kern-CPU wurde maximal ausgelastet
    • Nach etwa 1 Stunde und 30 Minuten war die 2D-Matrix erzeugt
  • Die erzeugten 2D-Embeddings und das trainierte UMAP-Modell wurden gespeichert, damit sich später auch neue Embeddings ohne erneutes Training transformieren lassen
  • Der erste Scatterplot hatte zu viele Punkte; deshalb wurde die Dichte reduziert, indem pro Rasterzelle nur der bestbewertete Post ausgewählt und dessen Titel angezeigt wurde
  • Beim zweiten Embedding mit mehr Kontext wurden Posts, die anhand des Titels allein schwer einzuordnen waren, genauer in der Nähe verwandter Inhalte platziert

Kosinusähnlichkeit und Suchranking

  • Der Kern der Embedding-Nutzung ist das Finden von Ähnlichkeit zwischen zwei Embeddings
  • Bei Text-Embeddings werden Kosinusdistanz bzw. Kosinusähnlichkeit häufiger verwendet als die übliche euklidische Distanz
  • Die Kosinusdistanz ist nützlich, wenn die Richtung wichtiger ist als die Größe
    • Eine lange X-bezogene Diskussion sollte X ähnlicher sein als eine lange Y-bezogene Diskussion
    • Wenn die Größe einbezogen wird, kann das solche Beziehungen verzerren
  • Die zentrale Berechnung ist das Dot Product der Embedding-Matrix mit dem Query-Embedding
  • Wenn die Vektoren Einheitsvektoren sind, ist keine zusätzliche Division durch die Größe nötig
  • Suchergebnisse werden nicht nur nach reiner Ähnlichkeit sortiert
    • Die Kosinusähnlichkeit ist ein großer, aber nicht der einzige Faktor
    • Der HN-Score dient als Social Proof
    • Eine Zeitgewichtung fließt als negativer Faktor proportional zu log(age) ein, damit ältere Inhalte bei Queries, bei denen Aktualität wichtig ist, schneller nach unten rutschen

Browser-Karten-App

  • Das Ziel war, den HN-Embedding-Raum als interaktive Karte erkundbar zu machen, ähnlich wie Google Maps
  • Das gewünschte Verhalten war klar
    • Beim Zoomen per Pinch-Geste oder Mausrad werden mehr Punkte angezeigt
    • Auch die Abstände zwischen den Punkten vergrößern sich
    • Einige Punkte erhalten Labels, aber nicht alle
    • Beim Klick auf einen Punkt werden die Post-Details angezeigt
    • Touch und Maus werden sowohl auf Mobilgeräten als auch auf dem Desktop unterstützt
  • Es war ungeeignet, alle Punkte auf einmal an den Client zu senden, da es sich um Millionen handelte
  • Stattdessen wurde der Kartenraum in Rasterkacheln aufgeteilt, und der Client lädt nur die benötigten Kacheln
    • Kacheln lassen sich über (x, y)-Koordinaten identifizieren
    • Sie können in einem KV-Speicher wie S3 abgelegt werden
    • Das lässt sich leicht ohne serverseitige Logik deployen
  • Zoomstufen wurden per LOD-Verfahren behandelt
    • Jede Stufe teilt in jeder Achse in doppelt so viele Rasterzellen
    • Punkte, die auf der vorherigen Stufe ausgewählt wurden, werden in die nächste Stufe kopiert, damit sie beim Hineinzoomen nicht verschwinden
  • Die Kachelgröße zielte komprimiert auf unter 20 KiB
    • Begrenzt auf etwa 1.500 Punkte
    • Pro Punkt wurden 8 Byte für (x, y), 4 Byte für die ID und 2 Byte für den Score verwendet
  • Bei der Darstellung in der Web-App verschlechterte ein Ansatz mit Tausenden DOM-Elementen die Performance massiv
  • Die finale Implementierung verwendet Canvas und zeichnet bei jeder Aktualisierung des Viewports neu
    • Selbst wenn pro Frame Tausende Punkte neu gezeichnet werden, bleibt das Verhalten flüssig und einfach
  • Für die Beschriftung wurden wiederholt die bestbewerteten Posts ausgewählt; überlappte ein Label mit bestehenden Labels, wurde es verworfen
    • Für die Kollisionserkennung kam die R-Tree-Implementierung RBush zum Einsatz
    • Die Labellänge wurde nicht per Browser-measureText(), sondern über das Byte-Array der Titellänge und eine angepasste Formel angenähert
  • Die initialen Label-Boxen und Kollisionsberechnungen waren CPU-intensiv und wurden daher in Web Workers ausgelagert
  • Mit OffscreenCanvas wurde ebenfalls experimentiert, brachte aber keinen großen Effekt, da die Rendering-Logik bereits effizient war

Gelände, Grenzen und Stadt-Labels

  • Einer Karte, die nur aus Punkten besteht, fehlen Orientierung und visuelles Interesse, daher wurden die Konzepte Gelände und Städte ergänzt
  • Da es keine echte Geografie oder politische Grenzen gibt, wurde Gelände als Metapher für Punktdichte verwendet
  • Die Punktdichte dient als Signal, um Bereiche mit viel Aktivität, Interesse, Content, Beteiligung, Popularität und Diskussion schnell sichtbar zu machen
  • Zunächst wurde Kernel Density Estimation in Betracht gezogen, aber Versuche mit Standardbibliotheken dauerten zu lange
  • Stattdessen wurde jeder Punkt auf große Rasterzellen abgebildet, pro Zelle gezählt und anschließend ein Gaussian Blur angewendet
  • Lineare Dichtewerte ergaben keine gute Karte, weil die meisten Werte nahe 0 lagen
  • Mit log(density + 1) entstand eine deutlich natürlichere Staffelung, und dort, wo unterschiedliche Dichtestufen aufeinandertreffen, wirken implizite Grenzen sichtbar
  • Statt eines riesigen Bildes wurden SVG-Pfade erzeugt, die der Client als Polygone zeichnet
    • Das ist effizient, weil es nur vier Farben gibt
    • Die Grenzen bleiben auch beim Zoomen scharf
    • Mit der Contour-Funktion von OpenCV wurden geschlossene Kurven pro Stufe berechnet
  • Stadt-Labels repräsentieren gemeinsame Themen innerhalb eines bestimmten Radius
  • Die Stadtnamen wurden eingebettet und dann mit dem gespeicherten UMAP-Modell in (x, y)-Positionen überführt
  • Es wurde auch automatische Erzeugung ausprobiert
    • Mit einem LLM sollten Stadtnamen erzeugt werden, aber per Prompt ließ sich die gewünschte Ausgabe nicht zuverlässig erreichen
    • K-means fand nicht viele sinnvolle Cluster, wie Menschen sie gruppieren würden
  • Letztlich wurden beim direkten Erkunden der Karte einige Städte manuell eingetragen; das dauerte etwa eine Stunde

Edge-Deployment und Reaktionsfähigkeit

  • Die Kartenerkundung musste schnell und reaktionsfreudig sein, daher war die Reduktion der Daten-Fetch-Latenz wichtig
  • Anfangs lagen alle Kartendaten in der ENAM-Region von Cloudflare R2, doch die Latenz lag zwischen 600 ms und mehreren Sekunden
  • Selbst wenn die physische Latenz bei etwa 200 ms lag, war das nicht gut genug, weil 100 ms ungefähr die Schwelle sind, ab der sich etwas sofortig anfühlt
  • Um die Latenz zu senken, wurden die Daten näher an die Nutzer gebracht
  • Kleine Server in Virginia, San Jose, London und Sydney liefern die Daten über einen Rust-Server aus
  • Der Client ruft mehrfach /healthz auf mehreren Edges auf und wählt dann den Server, der zuerst antwortet
  • Ansätze wie Anycast oder CDN wären ebenfalls möglich gewesen, wurden aber wegen Kosten und übermäßiger Komplexität nicht genutzt
  • Der Speicherverbrauch der Edge-Server-Prozesse lag um das 2- bis 4-Fache über den Rohdaten, was Fragen offenließ
    • möglicherweise falsch gewählte Typen
    • struct padding
    • Überallokation bei Vec und HashMap
    • mögliche Fragmentierung oder Ineffizienz des Memory Allocators

Ergebnisse der semantischen Suche und Grenzen

  • Bei einfachen Queries wie „entering the tech industry“ erschienen sowohl stark upgevotete Ergebnisse als auch weniger beachtete Treffer; Relevanz und Nutzen wirkten gut
  • Im Vergleich zur bestehenden HN-Suche findet die semantische Embedding-Suche Ergebnisse auch dann, wenn keine wörtliche Übereinstimmung vorliegt
  • Auch frageförmige Queries wie „what happened to wework“ liefern Ergebnisse über mehrere Jahre hinweg, etwa zu Entlassungen, Kursverlusten und der Insolvenz von WeWork
  • Die Treffer passen auch dann, wenn sie die Worte „what happened“ nicht tatsächlich enthalten oder gar nicht als Frage formuliert sind
  • Ein Problem war, dass zu wenig ähnliche Ergebnisse nicht herausgefiltert wurden, sodass völlig irrelevante niedrigere Treffer auftauchten
    • Das wird als leicht behebbares Problem behandelt
  • Bei der Suche nach „career growth“ erschienen kreative und vielfältige Essays, die die Wörter nicht wörtlich enthalten
  • Die kuratierte Qualität von HN und die Scores helfen der Suchqualität
  • In der App sind Query-Vorschläge wie „linus rants“, „self bootstrapping“ und „cool things with css“ hartkodiert

Virtuelle Communitys und Kommentaranalyse

  • Mithilfe von Embeddings lässt sich eine Funktion für virtuelle Sub-Communitys erstellen.
  • Gibt ein Nutzer einen Community-Namen oder eine Beschreibung ein, werden Posts, die einen bestimmten Ähnlichkeitsschwellenwert überschreiten, sofort gruppiert.
  • Da HN keine Funktion zur weiteren Unterteilung von Posts hat, lassen sich so sofort themenspezifische Kuratierungen erstellen.
  • Snippets und Bilder auf den Ergebniskarten stammen aus den Seitenmetadaten, die der Webcrawler gespeichert hat.
  • Die Website-Icons wurden vereinfacht, indem der Client statt komplexem Metadaten-Parsing direkt /favicon.ico der Domain abruft.
  • Kommentar-Threads lassen sich auf dieselbe Weise anzeigen.
  • Da Kommentar-Scores von der HN API nicht bereitgestellt werden, ist nur eine Sortierung nach Zeit möglich.
  • Als Ranking-Methode ohne Kommentar-Scores kommen laut Einschätzung Ansätze infrage, die Kommentarhistorie des Nutzers, Beteiligung rund um den jeweiligen Kommentar, Post, Thema und Inhalt nutzen.
  • Es ist auch möglich, einflussreiche oder besonders aktive Nutzer zu einem bestimmten Thema zu finden.
    • Bei der Suchanfrage „cloudflare“ erscheinen jgrahamc und eastdakota weit oben.
    • Die beiden Nutzer sind jeweils CTO und CEO von Cloudflare.
  • Diese Verarbeitung erfolgt per Matrixoperationen, ohne Kommentare separat zu klassifizieren oder Keyword-Suche zu verwenden.
  • Nachträgliches Filtern ist meist schneller und ausreichend als Vorab-Filterung.
    • Bei Vorab-Filterung müssen passende Zeilen aus der Embedding-Matrix entfernt werden, was riesige Speicherkopien oder langsame Berechnungen auf Teilvektoren erfordern kann.
    • Es ist besser, erst ähnliche Zeilen zu finden und dann die Ergebnisse zu filtern.
  • Ein Mindestschwellenwert ist wichtig.
    • Auch nicht relevante Einträge können eine Ähnlichkeit von etwa 0,6 haben.
    • Ohne Schwellenwert könnten Nutzer mit sehr vielen Kommentaren allein wegen ihres Umfangs das Ranking dominieren.

Stimmungs- und Beliebtheitsanalyse des gesamten Kommentardatensatzes

  • Die groß angelegte Analyse, die man mit 30 Millionen Kommentaren ausprobieren wollte, betraf Beliebtheit und Stimmung.
  • Das Ziel war zu sehen, wie HN über die Zeit bestimmte Themen wahrnimmt, wie große Ereignisse die Stimmung beeinflussen und wie Interessenthemen wachsen oder an Bedeutung verlieren.
  • Da keine Stimmungsdaten vorlagen, wurde ein Open-Source-Modell zur Stimmungsklassifikation von Hugging Face verwendet.
  • Gewählt wurde TweetEval, ein auf Social-Media-Inhalten trainiertes Modell.
  • Da TweetEval für kurze Tweets gedacht ist, wurde wie bei den Embeddings kein Vorfahren-Kontext angehängt, sondern nur der Kommentar selbst als Eingabe verwendet.
  • Die Kommentare wurden in eine Queue gestellt, auf einem GPU-Cluster verarbeitet und die Ergebnisse anschließend gespeichert.
  • Weil das Modell klein ist, wurde die Batch-Größe erhöht, um die GPU-Effizienz zu steigern.
  • Eine größere Batch-Größe verbraucht zwar mehr VRAM, kann aber Host-GPU-Speicherübertragungen reduzieren und die Parallelität erhöhen.
  • Bei Transformer-Modellen müssen Batch-Eingaben rechteckig sein und werden daher auf die Länge der längsten Eingabe gepolstert.
    • Wenn einige kurze Eingaben mit einer langen Eingabe gemischt werden, können Gesamtgröße der Eingaben und interne Zustände stark anwachsen.
    • Das kann zu Speicher-Spitzen und OOM führen.
  • Im Beispiel zur Rust-Stimmungsanalyse zeigte sich insgesamt viel positive Stimmung gegenüber Rust.
    • Rund um die Ankündigung von Rust 1.0 gab es einen Positiv-Spike.
    • Negativere Posts korrelieren nach Maßgabe des Modells mit vielen negativen Kommentaren.
  • Die Beliebtheit nach Sprache wurde ebenfalls mit Gewichtung nach Score und Ähnlichkeit geschätzt.
    • Da HN keine Kommentar-Scores bereitstellt, konnten Kommentar-Scores nicht verwendet werden.
    • Rust schlägt sich gut, scheint aber nicht so beliebt zu sein wie andere Sprachen.
    • Der Ähnlichkeitsschwellenwert muss möglicherweise angepasst werden, daher könnten die Ergebnisse falsch sein.

Große numerische Berechnungen mit GPUs beschleunigen

  • Analyseabfragen dauerten selbst auf einer Maschine mit 32 Kernen 10 bis 30 Sekunden und waren damit für interaktive Experimente zu langsam.
  • Nach Überlegungen zu Indexen oder Vorverarbeitung wurde auf den Einsatz von GPUs für vektorisierte numerische Berechnungen umgestellt.
  • CuPy und cuDF bieten APIs ähnlich zu NumPy bzw. pandas, laufen aber auf der GPU.
  • Das Portieren war vergleichsweise einfach, und die Abfragezeit sank auf einige hundert ms.
  • Die Geschwindigkeit war hoch genug, sodass auch kein ANN-Graph verwendet wurde.
  • Der schwierige Teil war, die große Embedding-Matrix auf die GPU zu bekommen.
    • Die Kommentar-Embedding-Matrix hat die Größe 30M x 512.
    • Es war schwierig, mehr als eine Kopie der Matrix im Hauptspeicher oder Videospeicher unterzubringen.
  • Ein einfacher Ladeansatz kann mehrere Kopien erzeugen.
    • Bytes werden von der Festplatte gelesen.
    • Sie werden in ein NumPy-Array geladen.
    • Dieses wird in ein CuPy-Array umgewandelt.
    • Dann wird es auf die GPU kopiert.
    • Dieser Prozess kann insgesamt 4 Kopien erzeugen, von denen sich 3 im Speicher befinden.
  • Die endgültige Methode bestand darin, die Matrix auf der Festplatte speicherabzubilden, auf der GPU vorab eine uninitialisierte Matrix derselben Größe zu allokieren und dann blockweise zu kopieren.
  • So wird vermieden, die Daten zuerst in den Python-Speicher zu lesen, und sowohl System-RAM als auch VRAM werden jeweils genau nur einfach belegt.

Demo und nächste Schritte

  • Die Demo-App ist unter hn.wilsonl.in verfügbar.
  • Auf der Hauptseite gibt es Karte und Suche; über die Schaltfläche oben rechts gelangt man zu den Community- und Analysetools.
  • URLs für Communitys oder Analyseergebnisse speichern die Suchanfrage in der URL und lassen sich daher mit anderen teilen.
  • Der Demo-Datensatz endet ungefähr am 10. April 2024 und enthält keine aktuellen Live-Posts oder Kommentare.
  • Für die Zukunft gibt es verschiedene Ideen, die weiter erkundet werden sollen.
    • Live-Daten, die kontinuierlich aktuell gehalten werden
    • Ein Deep-Learning-basiertes Empfehlungssystem für das von HN kuratierte Web
    • Verbesserte Suchergebnisse durch das Training eines Rerankers
    • Interessante Pfade und Reisen auf der Karte
    • Analyse von Ähnlichkeits- und Gegenbeziehungen zwischen Nutzern
    • Analyse der fachkundigsten Nutzer in einer bestimmten Nische
  • Die vollständigen Daten und der Code sind auf GitHub verfügbar.

Verwandte Beiträge

2 Kommentare

 
GN⁺ 2024-05-10
Meinungen auf Hacker News

  • Für ein Ein-Personen-Projekt ist das eine besonders beeindruckende Arbeit.
    Der Sentiment-Analyse-Graph im Zeitverlauf fiel mir auf, und ich fand es interessant, Rust einmal auf diese Weise betrachtet zu sehen. Ich frage mich, welche Themen im Lauf der Zeit am positivsten waren und ob es Themen gab, die plötzlich stark abgestürzt sind.
    Auch der Satz „Auf HN insgesamt scheint es viel negatives Sentiment zu geben“ klingt aus dem Bauch heraus für Social Media plausibel. Ein Vergleich des Sentiments nach Social-Media-Plattform und Zeitraum wäre ebenfalls spannend.

    • Beim Sentiment würde ich gern tiefer graben. Wie gesagt, es wäre interessant, nicht nur spezifische Abfragen zu betrachten, sondern auch einen Gesamtüberblick zu bekommen.
      Dass das negative Sentiment auffiel, lag daran, dass ich ursprünglich einen klareren Sentiment-Graphen erwartet hatte. Ich hätte erwartet, dass er überwiegend neutral bis positiv ist und in der Nähe positiver Beiträge ins Positive und in der Nähe negativer Beiträge ins Negative ausschlägt. Stattdessen war das Sentiment bei fast allen Abfragen nahezu immer negativ. Selbst positive Beiträge schienen nach Maßstab des Modells und des Ansatzes viel Negativität anzuziehen; beides könnte falsch sein, daher möchte ich das in einem späteren Blogpost weiter untersuchen.
    • Neben Sentiment nach Social-Media-Plattform und Zeitraum wäre es gut, auch Uhrzeit sowie Wochentage/Wochenenden einzubeziehen.
    • Vor ein paar Monaten habe ich einen Blogpost geschrieben, in dem ich das Sentiment von HN-Kommentaren zu AI, Blockchain, Remote Work und Rust analysiert habe. Der abschließende Graph ganz am Ende des Beitrags ist für dieses Thema relevant.
      https://openpipe.ai/blog/hn-ai-crypto
    • Es ist wirklich schade, dass die HN API keine Vote-Zahlen für Kommentare bereitstellt. Ich frage mich, wie sich die Sentiment-Analyse ändern würde, wenn man sie mit Upvotes/Downvotes gewichten könnte.
      Ich habe keine Belege dafür, aber ich vermute, dass Engineers im Allgemeinen kritisch sind und positives Feedback eher mit +1 ausdrücken, statt es wiederholt auszuschreiben. Kritik schreibt man eher direkt hin. :)
    • Crypto würde wohl auch in diese Kategorie fallen.

  • Für Leute, die mit Data Engineering/MLOps nicht vertraut sind, ist das ein gutes Beispiel.
    Ich würde vorschlagen, die Punkte mit HDBSCAN hierarchisch zu clustern und dann mit einem Modell Namen für die inneren Cluster zu erzeugen. So ließen sich Themen leichter bis zu den Blättern erkunden, indem Unterpunkte anhand ihrer Verbindung zum aktuellen Node eingeblendet werden.
    Die Gruppenfarben sollten deutlicher sein, und Cluster wären vermutlich hilfreich. Die Textgröße einzelner Beiträge sollte sich nach ihrer Wichtigkeit bzw. Relevanz insgesamt oder im aktuellen Suchkontext richten. Mit mehr Zusammenfassungen innerer Cluster könnte man mehrere Beiträge bis zum Hineinzoomen durch Gruppenzusammenfassungen ersetzen und so auch die Textüberladung reduzieren.

  • Der Projektumfang ist erstaunlich groß.
    Allerdings scheinen die Embeddings und der Tokenizer, ob nun jina oder bge-3/flag, nicht besonders gut zu technischen Themen zu passen. Bei natürlichsprachlichen Wörtern funktioniert es gut, aber wenn man nach technischen Begriffen wie „xaml“ oder „simd“ sucht, läuft es darauf hinaus, dass die Eingabe tokenisiert wird und dann versucht wird, ähnlich klingende Wörter zu finden.
    Als konstruktives Feedback: Es wäre gut, eine Möglichkeit zu haben, nicht immer wieder dieselben Ergebnisse aus der „HN-Bestenliste“ anzuzeigen, wenn ein Thema so nischig ist, dass es keine Treffer gibt. Wenn man nach Wörtern sucht, mit denen die Embeddings nicht vertraut sind, erscheint häufig „Stephen Hawking has died“.
    Auch bin ich mir nicht sicher, wie gut die Sentiment-Analyse funktioniert. Es wirkte so, als gebe es unrealistisch viel negatives Sentiment; selbst bei einer Suche nach etwas wie „Mr Rogers“, das HN überwältigend positiv sehen dürfte, gibt es starke negative Peaks. Wenn man nach „Carter“ sucht, gibt es im Zusammenhang mit dem Tod von Rosalynn Carter einen riesigen negativen Peak, obwohl es in dem tatsächlichen Beitrag um die großartigen Dinge ging, die das Ehepaar Carter geleistet hat.
    „Popularität im Zeitverlauf“ sollte wohl um die mittlere Vote-Zahl der Beiträge in dem jeweiligen Monat/Jahr bereinigt werden. Wenn man einfach die Anzahl der Beiträge plottet, steigt die Trendlinie immer weiter. An der Popularität von „diesel“ sieht man, was ich meine: Der Begriff hatte vor zehn Jahren seinen Höhepunkt. Oder vielleicht sollte man statt des Beitrags-Scores eher die Keyword-Häufigkeit oder die Anzahl der Einträge verwenden, deren Kosinusähnlichkeit zur Abfrage unter einem Wert x liegt.
    Die dynamische Funktion, Beiträge per Klick zu entfernen und den Ähnlichkeitsschwellenwert neu zu berechnen, ist hervorragend.

    • Wie könnte man programmatisch feststellen, dass ein bestimmtes Embedding-Modell bestimmte Begriffe oder Wörter nicht erkennt?

  • Es gibt ein hervorragendes Tool, das fast dasselbe für beliebige Datensätze macht: https://github.com/enjalot/latent-scope
    Natürlich kommen durch den Umfang des Projekts aus dem Originalbeitrag viele interessante Komplexitäten hinzu, und dieses Tool kann eine solche Größenordnung nicht bewältigen, aber für mittelgroße Datensätze ist es gut.

  • Ich würde gern analysieren, ob Selbstpromotion auf HN zugenommen hat
    Selbstpromotion definiere ich hier nicht als Beiträge im Format „Show HN: Something ...“, sondern als solche im Format „Show HN: I ...“
    Unter den aktuellen Top 100 sind zum Beispiel „Show HN: Exploring HN by mapping and analyzing 40M posts and comments for fun“ und „Show HN: Browser-based knitting (pattern) software“ keine Selbstpromotion-Titel. Das Subjekt ist jeweils das Erkunden bzw. die Software
    Dagegen sind „Show HN: I built a non-linear UI for ChatGPT“ und „Show HN: I created 3,800+ Open Source React Icons“ Selbstpromotion-Titel. Das jeweilige Subjekt ist „I“
    Wenn man in den Algolia-Suchergebnissen schlicht für jedes Jahr ab dem 1. April die Titel prüft, die mit „Show HN: I“ beginnen, und sie durch die Gesamtzahl der Ergebnisse dieses Jahres teilt, ergibt sich als Grafik Folgendes
    2023 ****************************************
    2022 ***********************************
    2021 ***************************
    2020 **************************************
    2019 *************************
    2018 *************
    2017 *******
    2016 **********
    2015 ********
    2014 ************
    2013 *********************
    2012 *****************
    2011 *********
    2010 ***
    Als ich aufgewachsen bin, galt Selbstpromotion im Allgemeinen wohl als schlechte Charaktereigenschaft. Mir wurde beigebracht, dass die eigenen Taten für einen werben sollten, nicht dass man selbst Aufmerksamkeit darauf lenkt; aber diese Kultur scheint sich zu verändern
    Falls Selbstpromotion tatsächlich zugenommen hat, frage ich mich, ob das am Einfluss von Social Media o. Ä. liegt. Auf YouTube spüre ich einen ähnlichen Anstieg, habe aber keine Daten, nur den Eindruck, dass mir viele empfohlene Videos angezeigt werden, die mit „I.....“ beginnen

    • Deine Definition von Selbstpromotion ist etwas anders als das, was ich normalerweise darunter verstehe. Üblicherweise würde man es als Selbstpromotion sehen, wenn jemand etwas bewirbt, das er selbst gemacht hat. Daher wären die beiden Beispiele, die du als nicht selbstpromotional nennst, nach meiner Definition ebenfalls Selbstpromotion
      Was du also in Selbstpromotion und Nicht-Selbstpromotion unterteilst, sind nach meinem Maßstab Fälle, in denen der Titel sehr ausdrücklich Selbstpromotion signalisiert, und Fälle, in denen er es weniger ausdrücklich tut. Allerdings scheint die Formulierung „Show HN“ selbst nur für Selbstpromotion verwendet zu werden, sodass jemand, der die Konvention kennt, auch ohne „I“ erkennt, dass es Selbstpromotion ist
    • Alle Show HN-Beiträge müssen etwas sein, das der Autor erstellt hat; daher ist mir nicht klar, warum es stärker selbstpromotional sein soll, das Implizite explizit zu machen
      Sie bedeuten alle: „Schau mal, ich habe etwas Cooles gebaut, was hältst du davon?“
    • In Walter Isaacsons Biografie über Einstein wird das ebenfalls ausführlich behandelt; Menschen beobachten diese Entwicklung also schon seit langer Zeit
      Zum Beispiel wurde Einstein von Deutschen Selbstpromotion vorgeworfen, während es in Amerika umgekehrt eine Celebrity-Kultur gab. Es könnte ein zyklisches Phänomen sein

  • Das ist mit Abstand der coolste Beitrag, den ich dieses Jahr auf HN gesehen habe

  • Beim ersten Anschauen war es nicht offensichtlich, aber die eigentliche App ist hier: https://hn.wilsonl.in/

    • Ich frage mich, ob der Link zur Landingpage absichtlich fast ganz ans Ende gesetzt wurde. So kommen tatsächlich nur Leute auf die Website, die den Beitrag gelesen haben
      Das ist nicht sarkastisch gemeint; ich halte es für eine gute Idee
    • Suchlinks scheinen nicht teilbar zu sein, oder der Suchbegriff scheint darin nicht enthalten zu sein
      Ich frage mich auch, ob die Suchphrase wortweise eingebettet wird und ob dafür dasselbe Modell verwendet wird wie für die Dokumente. Ich habe nach „lead generation“ gesucht und bekam Ergebnisse zu Bleivergiftung, obwohl ein ordentliches nicht-unigramm-basiertes Embedding diesen Ausdruck verstehen sollte
    • Ich habe mich und meine Beiträge dort gefunden! Schön

  • Als moderne Empfehlung für UMAP gibt es Parametric UMAP: https://umap-learn.readthedocs.io/en/latest/parametric_umap....
    Dabei wird ein kleines Keras-MLP trainiert, das den UMAP-Loss minimiert und eine Dimensionsreduktion auf 2D durchführt. Der Vorteil ist, dass dieses Modell klein ist und gespeichert sowie wiederverwendet werden kann, um auch für unbekannte neue Daten Vorhersagen zu machen. Klassisch trainierte UMAP-Modelle sind groß. Außerdem nutzt es die GPU, daher ist das Training theoretisch deutlich schneller
    Der Nachteil ist, dass die Implementierung im Python-UMAP-Paket nicht besonders gut ist und den erweiterten vollständigen Knoten-/Kanten-Datensatz auf der GPU erzeugt und dorthin schiebt. Deshalb kann man nur bis zu etwa 100.000 Embeddings trainieren, bevor der Speicher ausgeht
    Die vollständig unüberwachte Pipeline UMAP → HDBSCAN → KI-Cluster-Labeling ist so nützlich, dass ich Lust bekommen habe, eine skalierbarere Implementierung von Parametric UMAP zu bauen

    • Eine schnelle GPU-Implementierung gibt es in cuML. Ich weiß nicht genau, warum cuML so wenig bekannt ist
    • Auf den ersten Blick scheint es daran zu liegen, dass die Implementierung den gesamten Graphen, also alle Kanten, auf die GPU schiebt. Das ließe sich durch Kanten-Sampling während des Trainings abmildern

  • Für etwas, das wie ein exploratives Hobbyprojekt wirkt, ist das ein erstaunlich großer Aufwand. Ich will die Leistung nicht schmälern, es ist wirklich cool, aber der Einsatz hat mich überrascht.
    Allein für die Berechnung der Embeddings wurden 150 GPUs verwendet, und für die Kommunikation zwischen den Servern wurden zwei eigene Systeme entwickelt, db-rpc und queued. Dazu kamen noch viel Nebenarbeit und Rechenaufwand.
    Mich würde der Kontext des Projekts interessieren. Auch, wie die Finanzierung und die Zeit für solche Forschung zustande kamen.
    Aus der Perspektive von jemandem, der beruflich viel Ähnliches gemacht hat und wissenschaftliche Paper sowie Patentlandschaften gemappt hat, bin ich mir nicht sicher, ob 150 GPUs wirklich nötig waren. Wenn es am Ende um 2D-Projektion und Clustering geht, wären klassische Bag-of-Words- oder Topic-Modeling-Ansätze deutlich einfacher und günstiger, und der Qualitätsunterschied wäre wahrscheinlich kaum spürbar. Mit dem Graphen aus Autoren und Kommentar-Threads ließen sich ähnliche Ergebnisse erzielen.

    • Die Kosten habe ich im Artikel nicht erwähnt, aber sie lagen im Bereich von ein paar Hundert Dollar, also war es auch als Hobbyprojekt recht zugänglich.
      GPUs waren überraschend günstig, und größtenteils habe ich nur skaliert, weil ich ungeduldig war :) Der gesamte Cluster lief auch nur ein paar Stunden.
      Wenn du Links zu Arbeiten hast, die du gemacht hast, würde ich sie mir gern ansehen. Das klingt interessant, und ich würde gern mehr darüber lesen.
    • Der Autor ist eindeutig sehr fähig. Interessant ist auch, dass er zwar Beiträge auf HN postet, aber seit 2018 nicht mehr kommentiert hat; danach hat er dieses Projekt gestartet.
      Was Finanzierung und Zeit angeht, könnte er zwischen Projekten oder Jobs gewesen sein und durch eine frühere Karriere oder ein früheres Unternehmen finanziell erfolgreich genug gewesen sein, um es aus eigener Tasche zu machen. Auch die GPU-Auslastung war sehr effizient, daher dürften die Kosten nicht allzu hoch gewesen sein.
    • Auch mit günstigeren Embeddings lassen sich ziemlich gute Ergebnisse erzielen.
      Wenn man auf solche Embeddings klassisches Machine Learning wie wahrscheinlichkeitskalibrierte SVMs anwendet, bekommt man gute Ergebnisse bei Klassifikation und Clustering, und das ist mehr als 100-mal schneller als LLM-Finetuning.

  • Normalerweise macht man es nicht wie in dieser Demo, sondern normalisiert die Vektoren.
    Bei normalisierten Vektoren misst die euklidische Distanz den Abstand zwischen den Endpunkten zweier Vektoren. Die Kosinusdistanz hingegen misst die Länge der Projektion eines Vektors auf den anderen.

    • Das Problem der Normalisierung ist, dass man einen Freiheitsgrad verliert. Für eine Visualisierung ist das im Grunde so, als würde man eine Dimension verlieren.
      Ein normalisierter 2D-Vektor ist tatsächlich nur ein 1D-Vektor. Wenn man 2D-Beziehungen zeigen will, muss man 3D-Vektoren verwenden, um wieder zwei Freiheitsgrade zu erhalten.
 
ggg213 2024-05-10

Der Titel fehlt offenbar.