📊 statistics

MaxSketch: Robust Distinct Counting in Streams via Random Projections

Dieser Beitrag stellt MaxSketch vor, einen Algorithmus auf Basis zufälliger Projektionen, der die geometrische Struktur in gelernten Repräsentationen nutzt, um eine nahezu optimale logarithmische Speicherkomplexität für die robuste Schätzung von Distinct-Counts in verrauschten, hochdimensionalen Datenströmen zu erreichen und dabei die Einschränkungen klassischer Skizzen sowie vorheriger Worst-Case-Schranken zu überwinden.

Ursprüngliche Autoren: Nikos Tsikouras, Constantine Caramanis, Christos Tzamos

Veröffentlicht 2026-05-18

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Nikos Tsikouras, Constantine Caramanis, Christos Tzamos

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie stehen mit einer Kamera an einer belebten Kreuzung und versuchen zu zählen, wie viele einzigartige Personen vorbeigehen.

In den alten Tagen der Informatik war das Zählen einfach, wenn jeder einen einheitlichen Ausweis trug. Wenn „Alice" vorbeiging, stand auf ihrem Ausweis „Alice". Wenn sie erneut vorbeiging, stand darauf immer noch „Alice". Der Computer musste lediglich prüfen, ob er diesen exakten Ausweis bereits gesehen hatte. So funktionieren klassische Zählwerkzeuge: Sie verlassen sich auf exakte Übereinstimmungen.

Aber in der realen Welt tragen Menschen keine Ausweise. Sie tragen unterschiedliche Kleidung, stehen unter verschiedenen Lichtverhältnissen und nehmen verschiedene Posen ein. Wenn Alice einmal in einem roten Mantel und später in einer blauen Jacke vorbeigeht, könnte ein einfacher Computer denken: „Das ist eine neue Person!" und sie doppelt zählen. Dies ist das Problem rauschbehafteter, hochdimensionaler Daten: Dasselbe Objekt sieht jedes Mal anders aus, wenn man es betrachtet.

Der alte Weg versus das neue Problem

Frühere Versuche, dies zu lösen, versuchten, ähnlich aussehende Dinge zu gruppieren (Clustering). Doch dies ist wie der Versuch, Menschen zu zählen, indem man ein Foto von jeder einzelnen Person aufbewahrt, die man je gesehen hat. Wenn man 10.000 Menschen sieht, muss man sich 10.000 Fotos merken. Dies verbraucht zu viel Speicherplatz, insbesondere wenn man einen massiven Datenstrom in Echtzeit verarbeitet.

Ein anderer Ansatz versuchte zu sagen: „Wenn zwei Fotos nah genug beieinander liegen, sind es dieselbe Person." Doch mathematisch erweist sich dies als unglaublich schwierig. Im schlimmsten Fall bräuchte man eine enorme Menge an Speicherplatz (proportional zur Quadratwurzel der Gesamtzahl der Personen), um eine genaue Zählung zu erhalten. Das wäre so, als müsste man eine Bibliothek von der Größe einer Stadt benötigen, nur um die Menge in einem Stadion zu zählen.

Die Lösung: MaxSketch

Die Autoren dieses Papiers stellen eine neue Methode namens MaxSketch vor. Sie erkannten, dass moderne KI (insbesondere Deep Learning) bereits hervorragende Arbeit bei der Organisation von Daten leistet. Wenn man eine KI trainiert, Gesichter oder Objekte zu erkennen, lernt sie natürlich, „Alice" in einem engen Cluster und „Bob" in einem weit entfernten anderen Cluster zu platzieren. Selbst wenn Alice ihren Mantel wechselt, bleibt ihr „digitaler Fingerabdruck" nahe an ihrem ursprünglichen Ort.

MaxSketch nutzt diese natürliche Clusterbildung, um zu zählen, ohne jedes einzelne Foto merken zu müssen.

Die Analogie: Der „Windkanal"

Stellen Sie sich einen riesigen Windkanal mit vielen Ventilatoren vor, die aus verschiedenen zufälligen Richtungen blasen.

Das Setup: Sie haben einen Strom von Menschen (Datenpunkten), die durch den Tunnel laufen.
Der Test: Für jede Ventilatorrichtung fragen Sie: „Wer ist die Person, die in Richtung dieses Windes am weitesten steht?"
Die Magie: Wenn 100 Fotos von Alice durchlaufen, wird sie für eine bestimmte Ventilatorrichtung nur einmal die „weiteste" Person sein. Die anderen 99 Mal ist sie zwar noch da, aber sie ändert die Antwort nicht, da sie bereits das Maximum ist. Der Windkanal ignoriert effektiv die Wiederholung und kümmert sich nur um das Vorhandensein der einzigartigen Gruppe.
Die Zählung: Durch das Mitteln der Ergebnisse von Tausenden dieser zufälligen Windrichtungen kann der Computer abschätzen, wie viele verschiedene „Cluster" (einzigartige Personen) im Strom enthalten sind.

Warum es funktioniert

Das Papier beweist, dass diese Methode unglaublich effizient ist, wenn die Daten „wohlgeartet" sind (was bedeutet, dass die KI ähnliche Dinge erfolgreich gruppiert und verschiedene Dinge weit voneinander entfernt gehalten hat).

Speicher: Anstatt eine Bibliothek von der Größe einer Stadt zu benötigen, braucht MaxSketch nur ein kleines Notizbuch (logarithmischer Speicher). Es ist wie das Zählen einer Menge, indem man ein paar schnelle Schnappschüsse der Windrichtung macht, anstatt jedes einzelne Foto zu machen.
Genauigkeit: Es kann die Anzahl der einzigartigen Personen mit sehr hoher Präzision schätzen (innerhalb eines winzigen Fehlerspielraums).
Robustheit: Es funktioniert auch dann, wenn die „Alice" im roten Mantel etwas anders aussieht als die „Alice" in der blauen Jacke, solange sie beide noch als zur gleichen allgemeinen „Nachbarschaft" im Gedächtnis der KI gehörend erkannt werden.

Was sie getestet haben

Die Forscher testeten dies an:

MNIST (Handschriftliche Ziffern): Wo die „Cluster" sehr klar sind (eine „3" sieht immer wie eine „3" aus). Hier war MaxSketch perfekt, selbst beim Zählen von Sequenzen, die viel länger waren als die, für die es trainiert wurde.
CIFAR-10 (Kleine Farbbilder): Wo die Dinge chaotischer sind. Es funktionierte immer noch gut, insbesondere wenn die KI bereits trainiert war, die Objekte zu erkennen.
Echte Gesichtsdaten: Unter Verwendung echter Fotos von Menschen aus der Wildnis. Obwohl die Daten nicht perfekt waren, lieferte MaxSketch eine sehr gute Schätzung, wie viele einzigartige Personen in einem Strom von Tausenden Fotos waren, und übertraf dabei frühere Methoden, die für chaotische Daten entwickelt wurden.

Das Fazit

MaxSketch ist ein cleverer Trick, der ein schwieriges Zählproblem in ein einfaches „Maximum finden"-Problem verwandelt. Indem es die Tatsache nutzt, dass moderne KI ähnliche Dinge natürlich gruppiert, kann sie einzigartige Elemente in einem massiven, rauschbehafteten Strom mit sehr wenig Speicher zählen. Es schließt die Lücke zwischen alten Zählalgorithmen und moderner KI und zeigt, dass man, wenn die Daten gut organisiert sind, nicht alles merken muss, um zu wissen, wie viele einzigartige Dinge vorhanden sind.

Technische Zusammenfassung: MaxSketch: Robustes Zählen verschiedener Elemente in Datenströmen mittels zufälliger Projektionen

Problemstellung

Das klassische Problem der Schätzung der Anzahl verschiedener Elemente in einem Datenstrom ist gut verstanden, wenn wiederholte Vorkommen eines Elements durch identische Schlüssel dargestellt werden (z. B. exakte String-Übereinstimmungen). Algorithmen wie HyperLogLog erreichen dies mit logarithmischem Speicherbedarf, indem sie auf konsistente Hash-Werte zurückgreifen. In modernen Datenmodalitäten (z. B. Computer Vision, natürliche Sprache) sind Beobachtungen jedoch hochdimensional und verrauscht. Wiederholte Instanzen desselben zugrunde liegenden Objekts (z. B. verschiedene Bilder derselben Person) sind nur annähernd ähnlich, nicht identisch.

In diesem Regime des „robusten Zählens verschiedener Elemente" versagen klassische Skizzen, da sie nicht zwischen einem neuen Objekt und einer verrauschten Variation eines bestehenden Objekts unterscheiden können. Neuere Arbeiten in allgemeinen metrischen Räumen haben eine untere Schranke für den Speicherbedarf im Worst-Case von $\tilde{\Omega}(\sqrt{n})$ für robustes Zählen etabliert, was exponentiell schlechter ist als das im exakten Setting erreichbare $\tilde{O}(\log n)$ . Die zentrale Frage, die dieser Artikel adressiert, lautet, ob die spezifische geometrische Struktur, die in modernen gelernten Repräsentationen zu finden ist – wobei Beobachtungen desselben Objekts enge Cluster bilden und verschiedene Objekte gut getrennten Richtungen entsprechen – diese $\sqrt{n}$ -Barriere umgehen kann.

Methodik: MaxSketch

Die Autoren stellen MaxSketch vor, eine einfache, max-lineare Streaming-Skizze, die entwickelt wurde, um die geometrische Struktur gelernter Einbettungen auszunutzen.

Kernmechanismus

Anstatt Projektionen zu summieren oder zu mitteln (was mit der Häufigkeit skaliert und Verschiedenheit mit Vielfachheit verwechselt), aggregiert MaxSketch Beobachtungen mittels Maximum-Operationen.

Zufällige Projektionen: Gegeben einen Strom von Einheitsvektoren $X = \langle \tilde{x}_1, \dots, \tilde{x}_n \rangle \subset S^{d-1}$ , fixiert der Algorithmus $m$ unabhängige zufällige Gaußsche Vektoren $w_1, \dots, w_m \sim \mathcal{N}(0, I_d)$ .
Max-Aggregation: Für jede Projektion $w_j$ berechnet er das maximale Skalarprodukt mit einer beliebigen Beobachtung im Strom:
$M_j(X) = \max_{1 \le i \le n} \langle w_j, \tilde{x}_i \rangle$
Statistik: Die finale Skizze ist der Durchschnitt dieser Maxima:
$S(X) = \frac{1}{m} \sum_{j=1}^m M_j(X)$

Theoretische Grundlage

Die Methode beruht auf der Annahme, dass der Strom $(\eta, \rho)$ -clustervereinbar ist. Dies bedeutet:

Ausrichtung innerhalb des Clusters: Beobachtungen desselben Objekts sind in Richtung eines latenten Zentrums nahe beieinander (gesteuert durch $\eta$ ).
Trennung zwischen Clustern: Latente Zentren verschiedener Objekte weisen niedrige Skalarprodukte auf (gesteuert durch $\rho$ ).

Unter dieser Annahme verhält sich die maximale Projektion einer Menge von Vektoren wie das Maximum unabhängiger Gaußscher Variablen. Der Erwartungswert dieses Maximums wächst monoton mit der Anzahl verschiedener latenter Richtungen (Cluster). Durch die Analyse der Extremwertstatistik Gaußscher Prozesse (unter Verwendung der Slepian-Ungleichung und der Konzentration Lipschitz-stetiger Funktionen) beweisen die Autoren, dass die Lücke der erwarteten Maxima zwischen $k$ und $(1+\epsilon)k$ Clustern ausreicht, um diese mit hoher Wahrscheinlichkeit zu unterscheiden.

Hauptbeiträge

MaxSketch-Algorithmus: Eine permutationsinvariante, streaming-kompatible Skizze, die direkt auf kontinuierlichen Einbettungen operiert. Sie verwirft die Vielfachheit durch Konstruktion, da zusätzliche Wiederholungen desselben Objekts den Wert der maximalen Projektion nicht erhöhen, sobald der „Gipfel" des Clusters erreicht ist.
Verbesserte Speicher-Garantien: Der Artikel beweist, dass MaxSketch unter der natürlichen Annahme der Clustervereinbarkeit eine $(1+\epsilon)$ -multiplikative Approximation der Anzahl verschiedener Elemente unter Verwendung von $\tilde{O}(\log n / \epsilon^2)$ Speicher erreicht. Dies stellt eine erhebliche Verbesserung gegenüber der für allgemeine metrische Räume ohne solche Struktur bekannten unteren Schranke von $\tilde{\Omega}(\sqrt{n})$ dar.
Lernreduktion: Die Autoren zeigen, dass, sobald die zufälligen Projektionen fixiert sind, die Abhängigkeit der Skizze vom Input auf eine einzige skalare Statistik $S(X)$ kollabiert, die monoton in der wahren Anzahl ist. Folglich reduziert sich das Lernen zur Vorhersage der Anzahl auf das Anpassen einer eindimensionalen monotonen Funktion (Readout), was prozesseffizient und gut konditioniert ist.
Existenz einer festen Skizze: Während theoretische Garantien zunächst frische zufällige Projektionen für jeden Strom voraussetzen, beweist der Artikel, dass eine einzelne feste Menge von Projektionen für eine Verteilung clustervereinbarer Ströme mit hoher Wahrscheinlichkeit ausreicht.

Experimentelle Ergebnisse

Die Autoren validieren MaxSketch in drei Bereichen:

MNIST: In einem Setting mit geringer Intra-Klassen-Variabilität erreicht MaxSketch (end-to-end trainiert mit reiner Anzahl-Supervision) nahezu perfekte Genauigkeit und extrapoliert auf Sequenzlängen, die signifikant länger sind als die während des Trainings gesehenen. Dies bestätigt die theoretische Vorhersage, dass der Aggregationsmechanismus robust ist, wenn Einbettungen gut geclustert sind.
CIFAR-10: In einem Setting mit höherer Intra-Klassen-Variabilität führt das end-to-end Training allein aus der Anzahl-Supervision zu einer geringeren Genauigkeit im Vergleich zur Verwendung vortrainierter Merkmale. Das Modell erfasst jedoch immer noch die korrekte Reihenfolge der Anzahlen, was darauf hindeutet, dass die Schwierigkeit im Erlernen der clustervereinbaren Geometrie liegt und nicht im Zählmechanismus selbst.
Echte Gesichtsströme: Unter Verwendung fester vortrainierter Einbettungen (DeepFace) auf fusionierten Gesichtsdatensätzen (LFW, CelebA, Multi-PIE) wird MaxSketch mit Zhangs Algorithmus für robustes Zählen verschiedener Elemente in allgemeinen metrischen Räumen verglichen. MaxSketch zeigt eine überlegene Robustheit und behält eine hohe Genauigkeit (z. B. $\ge 60\%$ innerhalb eines $\pm 50$ -Fehlers) über einen weiten Bereich verschiedener Anzahlen (bis zu 5.100) bei, während der Basisalgorithmus aufgrund der Überlappung in Distanzverteilungen, die seine strengen geometrischen Annahmen verletzen, signifikant versagt.

Bedeutung und Behauptungen

Der Artikel beansprucht, die Lücke zwischen klassischen Streaming-Algorithmen und modernem Repräsentationslernen zu schließen. Seine primäre Bedeutung liegt darin zu demonstrieren, dass geometrische Strukturen, die in gelernten Repräsentationen üblich sind, die Komplexität des Zählens verschiedener Elemente fundamental reduzieren.

Die Autoren argumentieren, dass die $\sqrt{n}$ -untere Schranke für robustes Zählen ein Artefakt von Worst-Case-metrischen Räumen ohne Struktur ist. Im Regime des modernen Deep Learnings, wo „Neural Collapse" enge Intra-Klassen-Cluster und gut getrennte Inter-Klassen-Richtungen induziert, wird das Problem mit polylogarithmischem Speicherbedarf lösbar. MaxSketch dient als theoretisch fundierte, analytisch handhabbare Lösung, die diese Struktur nutzt und einen Weg zu effizientem Zählen verschiedener Elemente in verrauschten, hochdimensionalen Datenströmen bietet, ohne explizites Clustering oder Identitäts-Supervision zu erfordern.