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

Origami is een door autoregressieve transformers aangedreven architectuur die synthetische data genereert voor spaarzame, semi-gestructureerde en gemengde datatypes zonder flattening, en hiermee de bestaande methoden overtreft op het gebied van kwaliteit, schaalbaarheid en privacy.

De kern

Stel je voor dat je een enorme, chaotische bibliotheek hebt. In deze bibliotheek staan boeken (data) die er allemaal heel anders uitzien. Sommige boeken hebben vaste pagina's met strakke tabellen, maar de meeste moderne boeken zijn als Lego-bouwwerken: ze hebben vakken, vakjes in vakjes, lijsten met wisselende lengtes, en sommige pagina's zijn gewoon leeg gelaten omdat ze niet nodig waren.

De meeste bestaande computersystemen voor het maken van nep-data (synthetische data) zijn als stempelmachines. Ze kunnen alleen werken met strakke, rechthoekige tabellen. Om die Lego-boeken in zo'n stempelmachine te stoppen, moet je ze eerst platdrukken. Je moet alle vakjes uit elkaar halen, lege plekken opvullen met "raar" getallen, en de structuur vernietigen. Het resultaat is een rommelige, onherkenbare lap tekst die de computer probeert na te bootsen, maar die vaak faalt of heel raar wordt.

Origami is de oplossing die de auteurs van dit paper hebben bedacht. In plaats van de data plat te drukken, leert Origami de computer om te denken als een origami-meester.

Hier is hoe het werkt, vertaald naar alledaagse taal:

1. De Origami-Techniek (Geen Platdrukken)

Stel je voor dat je een ingewikkeld papieren vogeltje vouwt. Je hoeft het papier niet plat te maken om te begrijpen hoe het eruitziet; je volgt de vouwen.

• Het probleem: Bestaande methoden proberen de vouwen uit te strijken tot een plat vel. Als je een lijst met 5 vrienden hebt in het ene boek en 1 vriend in het andere, wordt dat bij platdrukken een enorme, lege tabel.
• De Origami-oplossing: Origami kijkt naar de structuur zelf. Het ziet dat er een "naam" is, een "adres" (dat weer een "straat" en "huisnummer" bevat), en een "hobby-lijst". Het maakt geen platte tabel, maar een rij van instructies (tokens) die zegt: "Hier begint een lijst, hier komt een naam, hier eindigt de lijst." Hierdoor blijft de oorspronkelijke vorm en de lege plekken (sparsiteit) behouden.

2. De Twee Hoofden (Voor Alles wat er is)

De computer van Origami heeft twee speciale "hoofden" (denk aan twee verschillende gereedschappen in één set):

• Hoofd 1 (De Woordenschat): Dit hoofd is goed in woorden, namen, en categorieën (zoals "Action" of "Sci-Fi"). Het leert de structuur van de Lego-blokjes.
• Hoofd 2 (De Wiskundige): Dit hoofd is goed in echte getallen (zoals temperatuur of gewicht). In plaats van getallen te forceren in hokjes (wat onnauwkeurig is), leert dit hoofd de vorm van de getallen. Het kan zeggen: "De kans is groot dat dit getal rond de 10 ligt, maar soms springt het naar 15." Dit heet een "Mixture of Gaussians" (een wiskundige manier om onzekerheid te modelleren).

3. De Magische Rol (KVPE)

In een normaal boek staat tekst in een vaste volgorde: regel 1, regel 2, regel 3. Maar in een JSON-bestand (de moderne data-indeling) maakt de volgorde van de vakjes niets uit. Of je nu eerst de "naam" schrijft of eerst de "leeftijd", het is hetzelfde boek.

• Het probleem: Normale AI's denken dat volgorde belangrijk is. Als je de volgorde verandert, raken ze in de war.
• De oplossing: Origami gebruikt een KVPE (Key-Value Position Encoding). Denk hierbij aan een GPS-coördinaat in plaats van een huisnummer. Het AI-model weet niet "dit is regel 5", maar "dit is het vakje 'straat' binnen het vakje 'adres'".
• Het trucje: De auteurs laten de computer tijdens het leren elke keer de volgorde van de vakjes willekeurig herschikken. Dit is als een dansles waarbij je elke keer een andere danspartner krijgt. Zo leert de AI echt wat de gegevens betekenen, in plaats van te onthouden waar ze staan. Dit voorkomt dat de AI gewoon de originele boeken kopieert (wat een privacy-risico is).

4. De Veiligheidscontrole (Grammatica)

Wanneer Origami een nieuw boek schrijft, zorgt een speciale grammatica-check (een pushdown automaton) ervoor dat het boek nooit "kapot" is.

• Als de AI begint met een lijst, moet het ook eindigen met een lijst.
• Als een vakje een getal moet zijn, mag er geen woord in staan.
  Dit zorgt ervoor dat elke gegenereerde record perfect geldig is, zonder dat de computer hoeft te raden of te improviseren.

Waarom is dit belangrijk?

Vroeger, als je data wilde delen zonder privacy te schenden, moest je die data eerst "platdrukken". Dat was als het proberen om een 3D-puzzel in een 2D-tekening te zetten: je verloor alle diepte en details.

• Met de oude methoden: Op grote, complexe datasets (zoals Yelp-reviews of medische dossiers) faalden de oude systemen. Ze werden te groot, werden traag, of maakten nep-data die heel makkelijk te onderscheiden was van de echte data.
• Met Origami: Het systeem werkt direct op de complexe, ingewikkelde data. Het maakt nep-data die zo goed is dat zelfs de slimste detectoren niet kunnen zeggen of het echt of nep is. Het is snel, veilig, en houdt de structuur van de data intact.

Kortom: Origami is de eerste AI die leert om 3D-Lego na te bouwen, in plaats van te proberen die Lego plat te drukken en te tekenen op papier. Het is een enorme stap voorwaarts voor het veilig delen van complexe data in de moderne wereld.

Technische samenvatting

Probleemstelling

Huidige methoden voor het genereren van synthetische data zijn grotendeels ontworpen voor dichte tabellen met een vast schema (rijen en kolommen). Ze gaan ervan uit dat data homogeen is en behandelen sparsiteit (ontbrekende waarden) als een probleem dat tijdens de preprocessing moet worden opgelost via imputatie (bijv. invullen met gemiddelden) of het verwijderen van rijen.

Dit benadering botst echter met de realiteit van moderne datasystemen (documentdatabases, REST API's, data lakes), die data opslaan in spare, semi-gestructureerde formaten zoals JSON. Deze data kenmerkt zich door:

• Geneste objecten en variabele lengte arrays: Data is hiërarchisch, niet plat.
• Sparsiteit: Veel sleutels zijn optioneel en ontbreken in specifieke records.
• Type-poly morfisme: Dezelfde sleutel kan in verschillende records verschillende datatypes hebben (bijv. een integer in de ene record en een string in de andere).
• Schaalbaarheid: Het "platdrukken" (flattenen) van dergelijke JSON-data naar tabellen leidt tot extreme sparsiteit (vaak >30%) en een explosie aan kolommen, waardoor bestaande synthesizers (zoals GANs, VAEs en zelfs diffusion-modellen) falen, niet schalen of de structurele eigenschappen van de data vernietigen.

Methodologie: Origami

De auteurs presenteren origami (Object Representa-tIon via Generative Autoregressive ModelIng), een autoregressieve transformer-architectuur die data direct verwerkt in zijn tokeniseerde JSON-vorm, zonder flattening of imputatie.

Kerncomponenten:

1. Tokenisatie en Representatie:

   • JSON-records worden omgezet in sequenties van tokens via een diepte-eerst-traversie.
   • Het vocabulaire bestaat uit drie klassen: Structurele tokens (start/end van objecten en arrays), Sleutel-tokens (key names) en Waarde-tokens (categorische waarden).
   • Numerieke waarden met hoge kardinaliteit worden gestandaardiseerd en via een apart continu kanaal verwerkt, terwijl ze in de discrete sequentie worden gemarkeerd met een num-token.

2. Key-Value Position Encoding (KVPE):

   • In plaats van sequentiële posities (zoals bij standaard transformers), encodeert KVPE de structurele positie van een token binnen de JSON-boom (het pad).
   • Dit maakt het model invariant voor de volgorde van zuster-sleutels, aangezien JSON-objecten per definitie geen vaste volgorde hebben.

3. Dual-Head Architectuur:

   • Discrete Head: Voorspelt structurele tokens, sleutels en categorische waarden via next-token prediction.
   • Continu Head (Mixture of Gaussians): Voor numerieke waarden wordt geen discretisatie toegepast. In plaats daarvan wordt een Mixture of Gaussians (MoG) gebruikt om de continue verdeling direct te modelleren. Dit behoudt precisie en ordinaal structuur.

4. Key-Order Shuffling:

   • Tijdens training wordt de volgorde van sleutels binnen objecten willekeurig gepermuteerd.
   • In combinatie met KVPE fungeert dit als een krachtige regularisatiestrategie. Het dwingt het model om te leren op basis van semantische relaties in plaats van het memoriseren van een canonieke volgorde, wat overfitting en memorisatie van trainingsdata voorkomt.

5. Grammatica- en Schema-beperkingen:

   • Een Pushdown Automaton (PDA) en een gecompileerde schema-masker worden gebruikt tijdens zowel training als inferentie.
   • Dit garandeert dat elke gegenereerde record syntactisch geldig JSON is en voldoet aan de geleerde schema-beperkingen (bijv. toegestane types, vereiste velden, array-lengtes).

6. Post-processing:

   • Gegevenen worden teruggezet naar het originele schaalbereik en afgerond of geknipt volgens de oorspronkelijke schema-constraints (bijv. naar integer afronden als dat vereist is).

Belangrijkste Bijdragen

1. Eerste End-to-End Semi-gestructureerde Synthese: Origami is, voor zover bekend, de eerste architectuur die semi-gestructureerde data (JSON) direct kan modelleren en genereren zonder flattening of imputatie.
2. KVPE: Een principieel mechanisme voor het modelleren van data met willekeurige sleutelvolgorde, wat dient als effectieve regularisator.
3. Nieuwe Evaluatiemethodiek: De auteurs ontwikkelen een methode om semi-gestructureerde data eerlijk te evalueren tegenover tabulaire baselines door een "flattening"-pipeline te gebruiken voor vergelijking, maar met aangepaste metrics die sparsiteit en type-poly morfisme expliciet meenemen.
4. Uitgebreide Evaluatie: Evaluatie op diverse datasets, variërend van academische tabellen tot grote semi-gestructureerde collecties met meer dan 1 miljoen records.

Resultaten

Origami werd getest op vijf datasets (Adult, Diabetes, Electric Vehicles, Yelp, DDXPlus) en vergeleken met zes baselines (TVAE, CTGAN, REaLTabFormer, TabularARGN, Tabby, TabDiff).

• Fidelity (Betrouwbaarheid): Origami presteert consistent bovenop alle baselines op bijna alle datasets. Op dichte tabellen (Adult, Diabetes) is de verbetering gematigd, maar op semi-gestructureerde data (Yelp, DDXPlus) is de kloof groot. Baselines zoals TabDiff zien hun fidelity-score dalen van ~0.98 naar ~0.80 op de meest complexe datasets.
• Detectie: Origami is het moeilijkst te onderscheiden van echte data. De ROC AUC van een detector (XGBoost) ligt dicht bij 0.5 (willekeurig) voor Origami, terwijl andere modellen vaak een hoge AUC (>0.9) halen, wat betekent dat ze makkelijk als synthetisch te herkennen zijn.
• Utility (ML-efficacy): Origami behoudt de voorspellende kracht van de originele data uitstekend (Train-Synthetic-Test-Real protocol), vaak presterend als de beste of tweede beste methode.
• Privacy: Origami behaalt hoge privacy-scores (>0.97) en toont weinig tekenen van memorisatie (Distance to Closest Record).
• Schaalbaarheid: Op datasets met hoge sparsiteit (tot 38%) en grote omvang (Yelp, DDXPlus) faalden veel baselines volledig door geheugenproblemen (OOM) of konden ze niet trainen. Origami bleef stabiel en efficiënt.
• Efficiëntie: Origami is een zeer klein model (1.7M parameters), aanzienlijk kleiner dan concurrenten zoals REaLTabFormer (59.4M), en trainde binnen de tijdslimiet van 24 uur op alle datasets.

Betekenis en Conclusie

Het paper markeert een verschuiving in het veld van synthetische data-generatie. Het toont aan dat de traditionele aanpak van "flattenen en imputeren" fundamenteel ongeschikt is voor de moderne, semi-gestructureerde data-ecosystemen.

Origami bewijst dat autoregressieve transformers, wanneer ze correct worden aangepast met structurele encoding (KVPE), hybride output-heads en grammaticale beperkingen, de ideale oplossing zijn voor deze complexiteit. Het biedt niet alleen superieure kwaliteit en privacy, maar opent ook de deur voor nieuwe toepassingen zoals conditionele sampling, data-imputatie en query-optimalisatie op semi-gestructureerde data, zonder de noodzaak van complexe pre-processing pipelines.