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

Ce papier présente Origami, une architecture de transformateur autoregressif pionnière capable de générer nativement des données semi-structurées et éparses de type mixte sans nécessiter d'aplatissement, surpassant ainsi les méthodes existantes en termes de fidélité, d'utilité et d'échelle.

L'essentiel

Imaginez que vous essayez de recréer une bibliothèque de livres très particuliers. Ces livres ne sont pas tous identiques : certains ont des chapitres, d'autres des annexes, certains ont des listes de personnages, d'autres des cartes géographiques. De plus, beaucoup de pages sont blanches (vides) parce que certains livres n'ont pas besoin de certaines sections.

C'est le défi que rencontrent les ordinateurs aujourd'hui avec les données modernes (comme les profils utilisateurs sur les réseaux sociaux ou les dossiers médicaux). Les méthodes actuelles pour créer de fausses données (synthétiques) sont comme des bibliothécaires rigides : ils essaient de forcer tous ces livres différents dans un seul et même format de tableau Excel.

Voici comment l'article explique la solution proposée, Origami, avec des images simples :

1. Le Problème : L'usine à "Écraser" les données

Les anciennes méthodes fonctionnent comme un compresseur de matelas géant. Pour mettre des données complexes (avec des listes, des objets imbriqués) dans un tableau, il faut les "aplatir".

• L'analogie : Imaginez que vous avez une valise remplie de vêtements pliés, de chaussures et de brosses à dents. Pour les mettre dans un tiroir plat, vous devez tout étaler, tout couper et tout étirer.
• Le résultat : Vous obtenez un tableau immense, rempli de trous (des cases vides) et de déformations. Les données perdent leur forme naturelle. C'est comme essayer de ranger un arbre entier dans une boîte aux lettres : ça ne rentre pas bien, et ça prend trop de place.

2. La Solution : Origami, l'architecte des plis

L'équipe a créé Origami (un nom qui évoque l'art du pliage). Au lieu d'aplatir les données, Origami apprend à les plier et à les déplier naturellement, comme un origami.

• Le Tokenisation (Le vocabulaire des plis) : Au lieu de voir une ligne de texte, Origami voit une suite de "briques" (des jetons). Il y a des briques pour dire "ici commence une liste", "ici commence un objet", "voici un nom", "voici un nombre".
• L'Analogie : C'est comme si vous appreniez à un enfant à construire une maison avec des LEGOs. Au lieu de lui donner un plan dessiné sur du papier plat (le tableau), vous lui donnez les instructions étape par étape : "Pose une brique rouge, puis une brique bleue, puis ajoute une fenêtre". Origami apprend à reconstruire la maison pièce par pièce, exactement comme elle était.

3. Les Trois Astuces Magiques d'Origami

Pour réussir là où les autres échouent, Origami utilise trois techniques intelligentes :

A. L'Ordre n'a pas d'importance (Le chaos organisé)

Dans un fichier informatique moderne, l'ordre des éléments n'a pas d'importance (un dossier "Adresse" peut venir avant ou après "Nom"). Les anciens modèles se trompaient en pensant que l'ordre était une règle.

• L'astuce : Origami mélange l'ordre des éléments à chaque fois qu'il étudie un exemple, un peu comme si vous appreniez une recette de cuisine en mélangeant l'ordre des ingrédients à chaque fois que vous la lisez.
• Le résultat : L'ordinateur apprend vraiment ce qui va ensemble (le lien entre les ingrédients) et non pas l'ordre dans lequel ils sont écrits. Cela l'empêche de "par cœur" les données (mémorisation) et le force à comprendre la logique.

B. Le Double Chapeau (Le cerveau bilingue)

Les données contiennent à la fois des mots (catégories) et des nombres précis (prix, poids).

• L'astuce : Origami porte deux "chapeaux" (deux têtes de prédiction).
  • Le premier chapeau gère les mots et la structure (les "briques" de l'origami).
  • Le second chapeau gère les nombres avec une grande précision, sans avoir besoin de les arrondir grossièrement.
• Le résultat : Il ne perd pas la précision des nombres tout en comprenant parfaitement la structure des listes et des objets.

C. Le Gardien de la Grille (Les règles du jeu)

Pour éviter que l'ordinateur ne crée des données illisibles (comme un livre sans fin de chapitre), Origami utilise un "gardien" (un automate).

• L'astuce : Ce gardien vérifie à chaque étape : "Est-ce qu'on a le droit de mettre un nombre ici ?" ou "Est-ce qu'on a fini la liste ?".
• Le résultat : Chaque donnée générée est parfaitement valide, comme un livre bien écrit qui respecte la grammaire et la structure.

4. Pourquoi c'est un changement de paradigme ?

Les méthodes actuelles sont comme un photocopieur : elles essaient de copier des documents complexes en les écrasant sur une feuille A4. Ça marche pour des documents simples, mais pour des dossiers complexes, ça devient illisible.

Origami est comme un sculpteur : il prend la matière brute et la façonne directement dans sa forme naturelle.

• Sur les données simples : Il est aussi bon que les meilleurs.
• Sur les données complexes (remplies de trous et de listes) : Il est bien meilleur. Les autres méthodes s'effondrent ou produisent des résultats bizarres, tandis qu'Origami continue de créer des données réalistes et utiles.

En résumé

Origami est un nouvel outil qui permet de créer de fausses données (pour tester des logiciels ou protéger la vie privée) en respectant la nature "en désordre" et complexe des données modernes. Au lieu de forcer les données dans un moule rigide, il apprend à les plier et les déplier comme un vrai artisan, garantissant que les données générées sont réalistes, précises et respectueuses de la vie privée.

Résumé technique

1. Problématique et Contexte

La génération de données synthétiques est cruciale pour le partage de données, la conformité à la vie privée (RGPD, HIPAA), le test de systèmes et l'entraînement de modèles d'apprentissage automatique. Cependant, les méthodes existantes reposent sur une hypothèse fondamentale obsolète : l'existence de tables denses avec un schéma fixe et des colonnes homogènes.

Cette hypothèse entre en conflit avec les systèmes de données modernes (bases de données documentaires, APIs REST, lacs de données) qui stockent et échangent des données au format JSON. Ces données présentent des caractéristiques complexes que les méthodes tabulaires classiques ne gèrent pas bien :

• Structure hiérarchique : Objets imbriqués et tableaux de longueur variable.
• Clairsemée (Sparsity) : Présence de clés optionnelles qui varient d'un enregistrement à l'autre.
• Types mixtes et polymorphisme : Une même clé peut contenir un entier dans un enregistrement et une chaîne de caractères dans un autre.
• Problème de l'aplatissement (Flattening) : Pour appliquer les méthodes existantes, il faut "aplatir" le JSON en tables larges. Cela crée des tables avec des centaines de colonnes, une clairsemée extrême (jusqu'à 38 %), et une explosion dimensionnelle lors du traitement des catégories (one-hot encoding), ce qui dégrade les performances et la fidélité des modèles.

2. Méthodologie : Origami

Les auteurs proposent Origami (Object RepresentaItion via Generative Autoregressive ModelIng), une architecture basée sur un transformateur autorégressif conçue pour générer des données semi-structurées de bout en bout, sans aplatissement ni imputation.

A. Tokenisation et Représentation

Au lieu de traiter des lignes de tables, Origami tokenise directement les enregistrements JSON :

• Sérialisation : Parcours en profondeur (DFS) des enregistrements JSON pour créer une séquence de tokens.
• Classes de tokens :
  • Structuraux : Délimiteurs pour les objets (obj_start, obj_end), les tableaux (arr_start, arr_end), et les valeurs numériques (num).
  • Clés (Keys) : Un token par clé distincte observée.
  • Valeurs : Tokens pour les valeurs catégorielles et les valeurs numériques à faible cardinalité.
• Gestion des nombres : Les valeurs numériques à haute cardinalité sont standardisées et passées via un canal continu parallèle, tandis qu'un token spécial num est émis dans la séquence discrète.

B. Encodage de Position Clé-Valeur (KVPE)

Contrairement aux transformateurs classiques qui utilisent des indices séquentiels (qui imposeraient un ordre arbitraire aux clés JSON), Origami utilise le KVPE.

• Il encode la position structurelle d'un token en fonction de son chemin dans l'arbre du document (ex: user.address.city).
• Cela rend le modèle invariant à l'ordre des clés sœurs, ce qui est essentiel car l'ordre des clés dans un objet JSON n'a pas de sémantique.

C. Architecture à Double Tête (Dual-Head)

Le modèle possède deux têtes de sortie pour gérer les types de données nativement :

1. Tête Discrète : Prédit les tokens structurels, les clés et les valeurs catégorielles via une prédiction du token suivant (Next-Token Prediction).
2. Tête Continue : Modélise les valeurs numériques à haute cardinalité comme un Mélange de Gaussiennes (MoG). Cela évite la discrétisation (binning) qui perd la précision et la structure ordinale.

D. Contraintes de Grammaire et de Schéma

Pour garantir que les données générées soient des JSON valides et conformes au schéma appris :

• Automate à Pile (PDA) : Un automate suit l'état grammatical (profondeur d'imbrication, attente d'une valeur, etc.) pour masquer les tokens invalides lors de la génération.
• Contraintes de Schéma : Un masque dérivé du schéma JSON appris (types, plages de valeurs, clés requises) est appliqué en conjonction avec le masque grammatical.

E. Augmentation de Données : Mélange des Ordres de Clés

Puisque l'ordre des clés est arbitraire, les auteurs mélangent aléatoirement l'ordre des clés à chaque niveau d'imbrication à chaque époque d'entraînement. Combiné au KVPE, cela agit comme un régularisateur puissant, empêchant le modèle de mémoriser des corrélations spurious basées sur l'ordre et forçant l'apprentissage des dépendances statistiques réelles.

3. Contributions Clés

1. Première architecture end-to-end : Origami est la première architecture capable de synthétiser des données semi-structurées de bout en bout, gérant nativement l'imbrication, les tableaux de longueur variable, la clairsemée et le polymorphisme de type.
2. Encodage KVPE : Proposition d'un mécanisme d'encodage de position invariant à l'ordre, démontré comme un régularisateur efficace contre la mémorisation.
3. Méthodologie d'évaluation : Développement d'une méthode d'aplatissement et d'adaptation des métriques d'évaluation pour permettre une comparaison équitable entre les méthodes tabulaires (aplaties) et Origami (native).
4. Validation à grande échelle : Évaluation sur des jeux de données allant de benchmarks académiques à des collections semi-structurées de plus d'un million d'enregistrements.

4. Résultats Expérimentaux

Les auteurs ont comparé Origami à six méthodes de base (GAN, VAE, Diffusion, Autorégressif) sur cinq jeux de données (Adult, Diabetes, Electric Vehicles, Yelp, DDXPlus).

• Fidélité et Détection : Origami surpasse systématiquement les autres modèles, en particulier sur les données clairsemées.
  • Sur les jeux de données denses (Adult, Diabetes), Origami égale ou dépasse les meilleurs modèles (TabDiff, REaLTabFormer).
  • Sur les données semi-structurées clairsemées (Yelp : 38% de clairsemée, DDXPlus : 35%), les méthodes de base échouent souvent (OOM - Out Of Memory) ou produisent des données facilement détectables comme synthétiques (scores de détection très élevés). Origami maintient une haute fidélité et reste difficile à distinguer des données réelles.
• Utilité (Utility) : Les modèles synthétiques générés par Origami permettent d'entraîner des classificateurs (XGBoost) avec des performances quasi identiques à celles entraînées sur des données réelles (TSTR protocol).
• Vie Privée (Privacy) : Origami obtient des scores de confidentialité élevés (> 0,97), indiquant une absence de mémorisation des enregistrements d'entraînement (mesuré par la Distance to Closest Record - DCR).
• Efficacité : Origami est le modèle le plus léger (1,7M de paramètres), soit 5x plus petit que le deuxième plus petit (TabularARGN) et 35x plus petit que REaLTabFormer. Il converge plus rapidement et consomme moins de mémoire.

Analyse des échecs des baselines :

• Les méthodes basées sur l'encodage one-hot (CTGAN, TVAE) échouent sur les données clairsemées en raison de l'explosion du nombre de colonnes.
• L'imputation par la moyenne (utilisée par TabDiff) dégrade la distribution des données clairsemées, créant des modes artificiels facilement détectables.
• La discrétisation des nombres (TabularARGN) introduit des artefacts statistiques.

5. Signification et Conclusion

Ce travail marque un tournant dans la génération de données synthétiques en passant d'une approche "table-plate" à une approche native pour les données semi-structurées.

• Impact Pratique : Origami permet de générer des données réalistes pour les environnements modernes (NoSQL, APIs) sans perte d'information due à l'aplatissement ou à l'imputation.
• Avantages Techniques : L'architecture hybride (discrète/continue) et l'utilisation de contraintes de schéma garantissent la validité syntaxique et sémantique des données générées.
• Perspectives Futures : L'approche autorégressive offre un estimateur de densité tractable, ouvrant la voie à d'autres applications comme l'imputation de données, l'estimation de cardinalité pour l'optimisation de requêtes, et la détection d'anomalies sur des données semi-structurées.

En résumé, Origami résout le problème de la synthèse de données complexes en traitant la structure hiérarchique et la clairsemée comme des propriétés de première classe, établissant un nouvel état de l'art (SOTA) en matière de fidélité, d'utilité et de confidentialité.