🤖 machine learning

Characterizing Learning in Deep Neural Networks using Tractable Algorithmic Complexity Analysis

Dieser Artikel stellt die Quantized Block Decomposition (QuBD)-Methode vor, einen skalierbaren Algorithmus zur Schätzung der Kolmogorov-Chaitin-Solomonoff-Komplexität von Gewichten tiefer neuronaler Netze, der zeigt, dass die algorithmische Komplexität während des Lernens abnimmt, mit der Generalisierung korreliert und signifikante Bit-Ebenen für eine effektive Modellquantisierung identifiziert.

Ursprüngliche Autoren: Pedram Bakhtiarifard, Sophia N. Wilson, Mahmoud Afifi, Jonathan Wenshøj, Raghavendra Selvan

Veröffentlicht 2026-05-18

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Pedram Bakhtiarifard, Sophia N. Wilson, Mahmoud Afifi, Jonathan Wenshøj, Raghavendra Selvan

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

Die große Idee: Lernen ist wie das Packen eines Koffers

Stellen Sie sich einen riesigen, chaotischen Koffer vor, der voller willkürlich hineingeworfener Kleidung, Socken und Schuhe steckt. Dies repräsentiert ein neu trainiertes Deep Neural Network (DNN) direkt nachdem es mit dem Lernen beginnt. Es verfügt zwar über alle „Parameter" (die Gewichte), doch diese sind lediglich zufälliges Rauschen. Es ist unordentlich, nimmt viel Platz ein und ist schwer zu verstehen.

Wenn das Netzwerk „lernt" (durch Training mit Daten), beginnt es, diesen Koffer zu organisieren. Es faltet die Hemden, rollt die Socken und stapelt die Schuhe ordentlich. Es findet Muster. In der Welt der Informatik nennt man diese Organisation Struktur.

Die Hauptthese des Papiers lautet „Lernen als Kompression". Die Idee ist, dass ein Modell, während es lernt, nicht nur intelligenter wird, sondern tatsächlich einfacher und besser organisiert wird. Wenn Sie Ihren Koffer gut organisieren, passt er in eine kleinere Tasche. Deshalb können wir KI-Modelle später komprimieren, damit sie schneller laufen und weniger Energie verbrauchen.

Das Problem: „Unordnung" zu messen ist schwierig

Wissenschaftler wollten schon lange genau messen, wie organisiert ein neuronales Netzwerk ist. Sie verwenden ein Konzept namens Kolmogorov-Komplexität (oder KCS-Komplexität).

Die Analogie: Denken Sie an die KCS-Komplexität als die Länge des kürzesten Anleitungsbuchs, das benötigt wird, um ein bestimmtes Objekt nachzubauen.
- Ein zufälliger Haufen Kleidung erfordert eine lange Anleitung: „Legen Sie hier eine rote Socke hin, dort einen blauen Schuh..." (Hohe Komplexität).
- Ein ordentlich gefalteter Stapel identischer weißer Hemden erfordert eine kurze Anleitung: „Falten Sie 50 weiße Hemden und stapeln Sie sie" (Niedrige Komplexität).

Der Haken: Die Berechnung dieses „kürzesten Anleitungsbuchs" ist für große, komplexe Objekte wie moderne KI-Modelle mathematisch unmöglich. Bestehende Werkzeuge (genannt CTM und BDM) sind wie der Versuch, die Komplexität einer ganzen Stadt zu messen, indem man nur einen einzelnen Ziegelstein betrachtet. Sie funktionieren für winzige, einfache Dinge (wie Binärcode), versagen jedoch, wenn man versucht, sie auf die massiven Gleitkommazahlen innerhalb moderner KI anzuwenden.

Die Lösung: QuBD (Der „Bit-Ebenen"-Übersetzer)

Die Autoren stellen eine neue Methode namens QuBD (Quantized Block Decomposition) vor.

Wie es funktioniert (Die Metapher):
Stellen Sie sich ein hochauflösendes digitales Foto vor (die KI-Gewichte).

Quantisierung: Zuerst vereinfacht QuBD das Foto, indem es die Farben auf eine bestimmte Palette rundet (wie beim Umwandeln eines Fotos in Pixel-Art). Dies macht die Daten handhabbar.
Bit-Ebenen-Zerlegung: Anstatt das gesamte Foto auf einmal zu betrachten, zerlegt QuBD das Bild Schicht für Schicht, wie eine Zwiebel.
- Schicht 1 (Das höchstwertige Bit): Dies ist das „Skelett" des Bildes. Es enthält die großen Formen und Hauptstrukturen.
- Schicht 2, 3, usw.: Dies sind die feinen Details, die Schattierungen und das winzige Rauschen.
Die Magie: QuBD misst die „Unordnung" (Komplexität) jeder Schicht separat und addiert sie.

Warum ist das besser?
Alte Methoden versuchten, das gesamte Foto sofort in Schwarz-Weiß (Binär) zu verwandeln, wodurch viele Details verloren gingen. QuBD betrachtet die Schichten nacheinander. Das Papier beweist mathematisch, dass dies eine viel genauere Messung liefert, wie „organisiert" die Daten wirklich sind.

Was sie entdeckten: Die Reise des Lernens

Mit diesem neuen „Schicht-Abstreif"-Werkzeug beobachteten die Autoren, wie sich KI-Modelle verändern, während sie lernen. Hier ist, was sie fanden:

1. Lernen reduziert Komplexität
Während ein Modell trainiert, wird sein „Koffer" organisiert. Der Komplexitätswert sinkt ab.

Analogie: Das Modell beginnt mit einem chaotischen Haufen zufälliger Zahlen. Während es lernt, erkennt es: „Oh, ich muss nicht jede einzelne zufällige Zahl merken; ich muss nur das Muster merken." Das Anleitungsbuch wird kürzer.

2. Overfitting macht es wieder unordentlich
Wenn ein Modell zu lange trainiert, beginnt es, die Trainingsdaten auswendig zu lernen, anstatt das Muster zu verstehen. Dies nennt man Overfitting.

Analogie: Das Modell hört auf, die Kleidung zu falten, und stopft jeden einzelnen Socken in eine bestimmte Ecke, nur um sich zu erinnern, wo er war. Der Koffer wird wieder unordentlich, und der Komplexitätswert steigt an.

3. Das „Grokking"-Phänomen
Manchmal scheint ein Modell festzustecken und zu versagen, das Lernen zu meistern, und versteht es dann plötzlich („Grokking").

Analogie: Das Modell kämpft, und die Komplexität bleibt hoch. Plötzlich hat es einen „Aha!"-Moment, die Komplexität sinkt stark ab, und es beginnt, das Problem perfekt zu lösen. Das QuBD-Werkzeug verfolgte diesen Komplexitätsabfall genau in dem Moment, als das Modell begann, zu generalisieren.

4. Die „wichtigen" Schichten
Die Autoren fanden heraus, dass die „Skelett"-Schichten (die höchstwertigen Bits) fast alle nützlichen Informationen enthalten. Die „feinen Details"-Schichten (die niedrigstwertigen Bits) sind oft nur zufälliges Rauschen.

Analogie: Wenn Sie für eine Reise packen, sind die Kleidungsstücke (die Hauptstruktur) wichtig. Der Fussel in Ihren Taschen (die niedrigen Bits) ist egal.
Praktische Anwendung: Dies sagt Ingenieuren, dass sie die „niedrigen Bit"-Schichten sicher entfernen können, um das Modell zu komprimieren, ohne die Leistung zu verlieren. Es dient als Diagnosewerkzeug, um zu entscheiden, wie stark ein Modell komprimiert werden soll.

Zusammenfassung

Dieses Papier erfand ein neues Lineal (QuBD), um zu messen, wie „organisiert" eine KI ist. Sie bewiesen, dass:

Lernen = Organisieren: Wenn KI lernt, wird sie einfacher und besser komprimierbar.
Overfitting = Chaos: Wenn sie zu viel lernt, wird sie wieder unordentlich.
Die „großen Bits" sind wichtig: Die wichtigsten Informationen befinden sich in den oberen Schichten der Daten, was es uns ermöglicht, den Rest sicher zu entfernen, um Platz zu sparen.

Dies gibt uns eine neue Möglichkeit zu verstehen, wie Deep Learning funktioniert, nicht nur durch das Betrachten von Genauigkeitswerten, sondern durch das Betrachten der fundamentalen Struktur der Daten selbst.

Technische Zusammenfassung: Charakterisierung des Lernens in tiefen neuronalen Netzwerken mittels handhabbarer algorithmischer Komplexitätsanalyse

Problemstellung

Das Training großskaliger tiefer neuronaler Netzwerke (DNNs) wird zunehmend ressourcenintensiv, was Techniken zur Modellokomprimierung wie Pruning, Wissensdistillation und Quantisierung erfordert. Die Hypothese „Lernen als Kompression" besagt, dass das Training strukturelle Organisation in den Netzgewichten induziert und damit Kompression ermöglicht. Während die Kolmogorov-Chaitin-Solomonoff (KCS)-Komplexität das theoretische Maß zur Messung einer solchen Struktur ist, ist sie nicht berechenbar. Bestehende Schätzer, die auf der Kodierungstheorem-Methode (CTM) und der Blockzerlegungsmethode (BDM) basieren, sind auf kleine binäre Objekte beschränkt und skalieren nicht auf moderne DNNs, die große, nicht-binäre (Gleitkomma-)Gewichtstensoren beinhalten. Darüber hinaus verlassen sich bestehende Methoden oft auf Binarisierung, was verlustbehaftet sein kann und aussagekräftige strukturelle Informationen verschleiert.

Methodik: Quantisierte Blockzerlegung (QuBD)

Um Skalierbarkeits- und Präzisionsbeschränkungen zu adressieren, stellen die Autoren die Methode der Quantisierten Blockzerlegung (QuBD) vor. Dieser Ansatz erweitert die Schätzung der algorithmischen Komplexität auf beliebige $k$ -wertige Objekte durch folgende Pipeline:

Quantisierung: Netzgewichte $W \in \mathbb{R}^d$ werden mittels eines affinen, uniformen Quantisierers auf ein endliches Alphabet $\Sigma_q$ abgebildet, was zu ganzzahligen Codes $W^{(q)}$ führt.
Bit-Ebenen-Zerlegung: Jedes quantisierte Gewicht wird in seine binäre Expansion über $q$ Bit-Ebenen zerlegt. Die $l$ -te Bit-Ebene $\beta_l$ sammelt das $l$ -te Bit aller $d$ Symbole.
Aggregation: Die KCS-Komplexität wird durch Aggregation von CTM-Schätzungen pro Bit-Ebene geschätzt. Die Gesamtkomplexität wird berechnet als $C_{QuBD}(W) = \sum_{l=0}^{q-1} C(\beta_l)$ , wobei $C(\beta_l)$ aus vorab berechneten CTM-Tabellen für kleine binäre Blöcke abgeleitet ist.

Theoretische Vorteile:
Die Arbeit liefert theoretische Beweise, die zeigen, dass QuBD im Vergleich zu binarisierungsbasierten Methoden eine strikt engere Schätzungslücke zur wahren KCS-Komplexität liefert.

Residuale Zerlegung (Satz 3.1): Die Arbeit formalisiert, dass die Schätzung eines Objekts aus seinem quantisierten Präfix $y_q$ residuale Information $R_q$ verpasst, die in den verworfenen niedrigeren Bits enthalten ist.
Bit-Ebenen-Residualverlust (Satz 3.2): Es wird bewiesen, dass das Hinzufügen von Bit-Ebenen den Residualverlust reduziert. Insbesondere liefert die Beibehaltung mehrerer Bit-Ebenen einen strikt kleineren Residualwert als eine-Bit-Binarisierung, sofern die Bit-Ebenen nicht identisch sind.
Sättigungsanalyse: Die Autoren analysieren die „Sättigung" endlicher CTM-Tabellen. Sie zeigen, dass zwar die Serialisierung (Abflachen aller Bits) CTM-Tabellen aufgrund des enormen Volumens an Blöcken schnell sättigt, die Bit-Ebenen-Zerlegung die Unterstützung jedoch effektiv skaliert, indem sie lokale Strukturen unabhängig über die Ebenen hinweg bewertet und informative Schätzungen bei größeren Skalen aufrechterhält.

Wichtige Ergebnisse

Mittels QuBD liefern die Autoren die erste skalierbare empirische Charakterisierung der Lern dynamiken in DNNs über einfache Feedforward-Netzwerke hinaus:

Komplexitätsreduktion während des Trainings: Während Modelle lernen, nimmt die algorithmische Komplexität ihrer Gewichte ab. Dies wird sowohl bei Multi-Layer Perceptrons (MLPs) als auch bei Vision Transformern (ViTs) beobachtet, wobei die Komplexitätsreduktion mit verbesserter Testgenauigkeit korreliert.
Overfitting und Komplexität: Während des Overfitting nimmt die algorithmische Komplexität zu. Dies deutet darauf hin, dass Memorierung Struktur einführt, die algorithmisch komplex (weniger komprimierbar) ist, im Gegensatz zur Vereinfachung, die während der Generalisierung beobachtet wird.
Grokking-Phänomen: In „Grokking"-Experimenten (bei denen Modelle nach einer langen Phase des Overfitting gut generalisieren) bleibt die QuBD-Komplexität während der Phase mit hoher Validierungsverlust hoch und nimmt erst signifikant ab, sobald der Validierungsverlust auf Null sinkt, wodurch die verzögerte Generalisierung verfolgt wird.
Verteilung der Bit-Ebenen-Information: Algorithmische Information ist nicht gleichmäßig verteilt. Die signifikantesten Bit-Ebenen (MSB) zeigen die größte Komplexitätsreduktion (was auf hohe Struktur hinweist), während niedrigere Bit-Ebenen oft Komplexitätsverhältnisse nahe 100 % (zufällig) aufweisen.
Diagnostik für Kompression: Die Konzentration algorithmischer Information in den MSBs korreliert mit der Leistung der Post-Training-Quantisierung (PTQ). Modelle können mit minimalen Genauigkeitsverlusten auf 4–6 Bit quantisiert werden, da die niedrigeren Bit-Ebenen vernachlässigbare algorithmische Information enthalten. Die QuBD-Komplexität dient als praktische Diagnostik, um optimale Quantisierungsstufen zu bestimmen und Schichten zu identifizieren, die für Pruning geeignet sind.

Bedeutung und Behauptungen

Die Arbeit behauptet, die ersten skalierbaren, handhabbaren Schätzungen der KCS-Komplexität für große, nicht-binäre Objekte wie DNN-Gewichte zu liefern. Ihre Bedeutung liegt in:

Operationalisierung von „Lernen als Kompression": Sie liefert empirische Belege dafür, dass Training Struktur in Gewichten induziert, die über algorithmische Komplexität messbar ist, und stützt damit die Hypothese, dass Lernen ein Prozess der Kompression ist.
Theoretische Überlegenheit: Sie stellt theoretisch fest, dass die Bit-Ebenen-Zerlegung eine engere Schranke für die KCS-Komplexität bietet als die Binarisierung und damit eine fundamentale Einschränkung früherer Anwendungen der algorithmischen Informationstheorie auf DNNs adressiert.
Praktischer Nutzen: Sie demonstriert, dass die algorithmische Komplexitätsanalyse als Diagnosewerkzeug für Modellokomprimierung dienen kann, redundante Kapazität (z. B. niedrigere Bit-Ebenen oder bestimmte Schichten) identifiziert, ohne Leistungsverluste zu erfordern.

Die Autoren schließen, dass die algorithmische Informationstheorie ein leistungsfähiges Paradigma zur Erklärung von Deep-Learning-Mechanismen bietet und eine konkrete Methode zur Charakterisierung von Lern dynamiken liefert, die mit Generalisierungsleistung und Phänomenen wie Grokking übereinstimmt.