Autoregressive Synthesis of Sparse and Semi-Structured Mixed-Type Data

Das Paper stellt Origami vor, ein auf autoregressiven Transformern basierendes Modell, das erstmals semistrukturierte, spärliche und gemischt-typische Daten (wie JSON) ohne vorherige Verflachung oder Imputation nativ synthetisiert und dabei bestehende Methoden in Bezug auf Genauigkeit, Nutzbarkeit und Privatsphäre übertrifft.

Das Wesentliche

Stell dir vor, du möchtest eine neue Stadt bauen, aber du hast keine echten Bewohner, nur eine riesige, chaotische Liste von Notizen aus dem echten Leben. Diese Notizen sind nicht wie eine saubere Excel-Tabelle, wo jeder in jeder Zeile die gleichen Spalten hat. Stattdessen sind sie wie persönliche Tagebücher oder JSON-Daten: Manche Einträge haben eine Adresse, andere nicht. Manche haben eine Liste von Hobbys (die mal drei, mal zehn Einträge lang ist), andere haben ein komplexes Familienverzeichnis mit verschachtelten Details.

Das Problem: Die meisten Computerprogramme, die künstliche Daten erstellen, sind wie sture Bauarbeiter, die nur mit starren Bauplänen (festen Tabellen) arbeiten können. Wenn sie diese chaotischen Tagebücher bekommen, versuchen sie, alles in ein riesiges, leeres Raster zu zwängen. Sie füllen die Lücken mit „Nullen" oder Durchschnittswerten auf, bis das Bild verzerrt ist und die echten Muster verloren gehen. Es ist, als würdest du versuchen, einen fließenden Fluss in ein starres Gitter aus Beton zu gießen – das Wasser (die Daten) passt einfach nicht.

Origami ist der neue, cleere Architekt, der dieses Problem löst.

Was ist Origami?

Der Name ist kein Zufall. Wie beim Papierfalten, bei dem man aus einem flachen Blatt komplexe, dreidimensionale Formen macht, nimmt Origami die flachen Daten und „faltet" sie in ihre wahre, komplexe Form zurück.

Hier ist, wie es funktioniert, in einfachen Bildern:

1. Keine mehr, keine weniger (Kein „Flattening")

Statt die Tagebücher gewaltsam in eine riesige Tabelle zu zerlegen, liest Origami sie wie ein Bücherwurm, der den Text Zeile für Zeile, Wort für Wort liest.

• Andere Methoden: Versuchen, jeden Satz in eine eigene Spalte zu stecken. Wenn ein Satz fehlt, entsteht eine riesige Lücke.
• Origami: Versteht, dass ein Satz (ein Schlüssel) zu einem anderen gehört (ein verschachteltes Objekt). Es behält die Hierarchie bei. Es weiß: „Ah, die Adresse gehört zur Person, und die Telefonnummer gehört zur Adresse."

2. Der intelligente Übersetzer (Tokenisierung)

Origami verwandelt die Daten in eine Art Baukasten-Sprache.

• Es zerlegt die Daten in kleine Bausteine: Schlüssel (z. B. "Name"), Werte (z. B. "Max") und Struktur-Bausteine (z. B. "Hier beginnt eine Liste", "Hier endet ein Abschnitt").
• Der Clou: Es ignoriert nicht die Lücken (Sparsity). Wenn ein Eintrag keine Telefonnummer hat, sagt es nicht „Fülle mit Null", sondern „Hier fehlt eine Telefonnummer, und das ist normal". Es lernt, dass das Fehlen von Daten selbst eine Information ist.

3. Der tanzende Schlüssel (Key-Order Shuffling)

In echten Datenbanken ist die Reihenfolge, in der Dinge aufgelistet sind, oft zufällig. Ein Computer, der stur lernt, dass „Name" immer vor „Adresse" kommt, lernt die falsche Regel.

• Origamis Trick: Es mischt die Reihenfolge der Wörter bei jedem Training neu durch, wie ein Kartenspieler, der das Deck immer wieder neu schüttelt.
• Der Effekt: Der Computer kann nicht einfach auswendig lernen, was als Erstes kommt. Er muss wirklich verstehen, was die Dinge bedeuten und wie sie zusammenhängen. Das verhindert, dass er einfach Kopien der Originaldaten auswendig lernt (Memorierung).

4. Der doppelte Hut (Dual-Head Architecture)

Die Welt besteht aus verschiedenen Arten von Dingen: Wörtern (Kategorien) und Zahlen.

• Ein normaler Computer versucht oft, Zahlen in Wörter umzuwandeln (z. B. "100" wird zu "Einhundert"). Das ist ungenau.
• Origami hat zwei Spezialisten: Einen, der mit Wörtern und Strukturen umgeht, und einen, der Zahlen direkt als Zahlen versteht (wie ein Mathematiker, der nicht zählen muss, sondern das Gefühl für Zahlen hat). So bleiben die Zahlen präzise, auch wenn sie sehr groß oder sehr klein sind.

Warum ist das so wichtig?

Stell dir vor, du willst eine neue App testen. Du brauchst Testdaten, aber du darfst die echten Kundendaten nicht verwenden (wegen Datenschutz).

• Die alten Methoden würden dir eine Liste von Kunden geben, bei denen 40% der Adressen falsch sind oder die Namen zufällig gemischt wurden, weil sie die Daten nicht verstanden haben. Deine App würde abstürzen oder falsche Ergebnisse liefern.
• Origami erstellt eine Liste von Kunden, die sich genau wie die echten anfühlen. Sie haben die gleichen Lücken, die gleichen komplexen Familienstrukturen und die gleichen Zufälligkeiten. Ein Hacker oder ein Datenschutzbeauftragter kann kaum unterscheiden, ob die Daten echt oder künstlich sind.

Das Ergebnis

In Tests hat Origami gezeigt, dass es:

1. Besser lernt: Es versteht komplexe, verschachtelte Daten (wie JSON) viel besser als alle bisherigen Methoden.
2. Schneller ist: Es braucht weniger Rechenleistung, weil es keine riesigen, leeren Tabellen erstellen muss.
3. Sicherer ist: Es kopiert keine echten Personen, sondern erfindet neue, realistische Persönlichkeiten.

Zusammenfassend:
Während andere Methoden versuchen, einen fließenden Fluss in ein starres Gitter zu pressen, baut Origami einen neuen Fluss, der genauso fließt, genauso viele Kurven hat und genauso viele Fische enthält wie der Originalfluss – nur dass er aus dem Nichts erschaffen wurde. Es ist der erste Architekt, der versteht, dass moderne Daten nicht in Tabellen passen, sondern in lebendige, verschachtelte Strukturen.

Technische Zusammenfassung

1. Problemstellung

Die Generierung synthetischer Daten ist entscheidend für Datenschutz, Softwaretests und das Benchmarking von Datenbanken. Bisherige Methoden konzentrieren sich fast ausschließlich auf dichte, tabellarische Daten mit festem Schema (z. B. SQL-Tabellen).

Das zentrale Problem liegt in der Diskrepanz zu modernen Datenarchitekturen (Dokumentendatenbanken, REST-APIs, Data Lakes), die Daten in spärlichen, halbstrukturierten Formaten wie JSON speichern. Diese Daten weisen folgende Eigenschaften auf:

• Verschachtelte Strukturen: Objekte und Arrays innerhalb von Objekten.
• Variable Längen: Arrays mit unterschiedlicher Anzahl von Elementen pro Datensatz.
• Sparsity (Dünnbesetztheit): Viele Schlüssel sind in einzelnen Datensätzen nicht vorhanden.
• Typ-Polymorphie: Derselbe Schlüssel kann in verschiedenen Datensätzen unterschiedliche Datentypen haben (z. B. Integer vs. String).

Der aktuelle Ansatz, diese Daten für synthetische Generatoren nutzbar zu machen, besteht darin, sie in flache Tabellen zu „flattening" (abflachen). Dies führt jedoch zu massiven Problemen:

• Skalierungsprobleme: Variable Arrays erzeugen hunderte von Spalten.
• Informationsverlust: Das Entfernen von fehlenden Werten oder das Imputieren (z. B. durch Mittelwerte) zerstört die semantische Bedeutung der Sparsity.
• Fehleranfälligkeit: Herkömmliche Modelle (GANs, VAEs, Diffusionsmodelle) scheitern oft an der hohen Dimensionalität und der Mischung aus kategorialen und kontinuierlichen Daten in diesem Kontext.

2. Methodik: Origami

Die Autoren stellen origami (Object Representa- tIon via Generative Autoregressive ModelIng) vor, eine autoregressive Transformer-Architektur, die JSON-Datensätze nativ verarbeitet, ohne sie vorher abzuflachen oder Werte zu imputieren.

Kernkomponenten der Architektur:

1. Tokenisierung:

   • JSON-Datensätze werden durch eine Tiefensuche in Sequenzen von Tokens zerlegt.
   • Es werden drei Token-Klassen unterschieden: Struktur-Tokens (z. B. obj_start, arr_end), Schlüssel-Tokens (Keys) und Wert-Tokens (Values).
   • Hohe Kardinalität bei numerischen Werten wird nicht diskretisiert, sondern über einen separaten kontinuierlichen Kanal behandelt.

2. Key-Value Position Encoding (KVPE):

   • Herkömmliche Transformer nutzen sequenzielle Positionen. Da JSON-Keys jedoch keine feste Reihenfolge haben, würde dies künstliche Ordnungen einführen.
   • KVPE kodiert die strukturelle Position eines Tokens basierend auf seinem Pfad im JSON-Baum (z. B. user.address.city).
   • Dies macht das Modell invariant gegenüber der Reihenfolge von Geschwister-Keys.

3. Dual-Head-Architektur:

   • Diskreter Head: Vorhersage von Struktur-Tokens, Keys und kategorialen Werten mittels Next-Token-Prediction (Cross-Entropy Loss).
   • Kontinuierlicher Head: Modellierung numerischer Werte als Mixture of Gaussians (MoG). Dies ermöglicht die direkte Modellierung von Unsicherheit und multimodalen Verteilungen, ohne diskrete Binning-Verfahren, die Präzision verlieren.

4. Key-Order Shuffling:

   • Da JSON-Keys keine feste Reihenfolge haben, wird die Reihenfolge der Keys in jedem Trainings-Beispiel zufällig permutiert.
   • In Kombination mit KVPE zwingt dies das Modell, semantische Beziehungen zu lernen, anstatt sich eine willkürliche Reihenfolge zu merken. Dies dient als effektive Regularisierung gegen Overfitting und Memorization.

5. Grammatik- und Schemazwänge:

   • Ein Pushdown-Automat (PDA) und ein kompiliertes Schema-Maskierungssystem garantieren, dass jede generierte Sequenz syntaktisch gültiges JSON ist und dem gelernten Schema (Typen, erlaubte Keys, Array-Längen) entspricht.

6. Nachbearbeitung:

   • Kontinuierliche Werte werden zurück auf den ursprünglichen Skalenbereich transformiert, auf erlaubte Bereiche gekappt und auf ganzzahlige Werte gerundet, falls nötig.

3. Wichtige Beiträge

1. Erste End-to-End-Lösung: Origami ist (nach Kenntnisstand) die erste Architektur, die halbstrukturierte Daten nativ modelliert und generiert, ohne Flattening oder Imputation.
2. KVPE: Einführung einer positionellen Kodierung, die strukturelle Pfade nutzt und die Reihenfolge von Keys ignoriert, was als Regularizer gegen Memorization wirkt.
3. Neue Evaluierungsmetriken: Entwicklung von Methoden zur fairen Bewertung halbstrukturierter Daten, die Sparsity, Typ-Polymorphie und strukturelle Muster explizit berücksichtigen.
4. Umfassende Evaluation: Tests auf Datensätzen von kleinen tabellarischen Benchmarks bis hin zu über einer Million halbstrukturierter Datensätze (DDXPlus).

4. Ergebnisse

Die Evaluation erfolgte auf fünf Datensätzen (Adult, Diabetes, Electric Vehicles, Yelp, DDXPlus) im Vergleich zu sechs Baselines (TVAE, CTGAN, REaLTabFormer, TabularARGN, Tabby, TabDiff).

• Fidelity (Treue): Origami erzielt auf allen Datensätzen die besten oder zweitbesten Ergebnisse. Bei dichten Tabellen liegt es leicht vor dem State-of-the-Art (z. B. TabDiff). Bei spärlichen, halbstrukturierten Daten (bis zu 38% Sparsity) übertrifft es die Baselines deutlich, während diese stark an Leistung verlieren oder aus dem Speicher laufen (OOM).
• Utility (Nützlichkeit): In ML-Aufgaben (Train-Synthetic-Test-Real) erreicht Origami auf 4 von 5 Datensätzen die höchste Genauigkeit.
• Detection (Erkennbarkeit): Origami generiert Daten, die für Klassifikatoren am schwersten von echten Daten zu unterscheiden sind (höchste Detection-Scores, niedrigste ROC-AUC für den Angreifer). Baselines wie TabDiff werden bei hoher Sparsity fast perfekt erkannt (ROC-AUC ~0.999).
• Skalierbarkeit: Während Baselines wie CTGAN oder TVAE bei hohen Kardinalitäten und Sparsity aufgrund von One-Hot-Encoding an Speicher grenzen, skaliert Origami effizient.
• Effizienz: Origami ist mit 1,7 Millionen Parametern deutlich kleiner als vergleichbare Transformer-Modelle (z. B. REaLTabFormer mit 59,4M Parametern) und trainiert schneller.
• Privatsphäre: Origami zeigt keine systematische Memorization (Distance to Closest Record nahe 50%).

Schlüsselerkenntnis zu Baselines: Herkömmliche Methoden scheitern oft, weil sie Sparsity durch Mittelwert-Imputation behandeln. Dies führt dazu, dass das Modell eine künstliche Verteilung lernt, die sich stark von den echten, seltenen Werten unterscheidet und leicht erkannt werden kann.

5. Bedeutung und Fazit

Das Paper demonstriert, dass der Ansatz des „Flattening" für moderne, halbstrukturierte Daten nicht mehr tragfähig ist. Origami beweist, dass autoregressive Transformer-Architekturen, die speziell für die Struktur von JSON-Daten (Tokenisierung, KVPE, Dual-Head) angepasst sind, überlegene Ergebnisse liefern.

Die Arbeit legt den Grundstein für:

• Sichere Datenaustauschmechanismen für komplexe NoSQL-Datenbanken.
• Effizientes Testen von Systemen, die mit JSON-basierten APIs arbeiten.
• Neue Anwendungen wie direkte Likelihood-Schätzung, Imputation und Kardinalitätsschätzung für halbstrukturierte Daten.

Zusammenfassend bietet origami einen robusten, skalierbaren und datenschutzkonformen Weg zur Generierung synthetischer Daten in der Ära von unstrukturierten und halbstrukturierten Datenbeständen.