Composez un programme graphique simplement en regardant un croquis dessiné à la main. Berkeley, en Californie, enseigne de nouvelles compétences aux modèles de diffusion.

Il s'avère que les modèles de diffusion peuvent être utilisés non seulement pour générer des images et des vidéos, mais aussi pour synthétiser de nouveaux programmes.

Supposons que nous donnions au modèle un graphique en forme de "5" dessiné à la main, il peut modifier le programme par des mutations continues, et enfin obtenir un programme capable de générer le graphique cible.

Ce modèle provient d'une équipe de recherche de l'Université de Californie à Berkeley. Cette nouvelle méthode de synthèse de programme proposée par eux utilise un modèle de diffusion neuronale pour faire fonctionner directement les arbres syntaxiques.

Papier 1 En tant que Shreyas Kapur, doctorant à l'école, son superviseur est Stuart Russell, professeur d'informatique à l'école.

• Titre de l'article : Diffusion sur les arbres de syntaxe pour la synthèse de programmes
• Adresse de l'article : https://arxiv.org/pdf/2405.20519
• Adresse du projet : https://diffusion-diffusion. github.io/
• Base de code : https://github.com/revalo/tree-diffusion

Les modèles de diffusion ont déjà connu un grand succès dans le domaine de la génération d'images. L'équipe a découvert qu'en utilisant le mécanisme de diffusion, le modèle peut apprendre à optimiser le programme de manière itérative tout en garantissant la validité syntaxique. La clé de cette nouvelle approche est de permettre un processus de débogage efficace en permettant au modèle d'observer la sortie du programme à chaque étape.

La capacité d'itération a été démontrée dans des systèmes tels qu'AlphaZero, et la nature itérative du mécanisme de diffusion sera naturellement utilisée dans la synthèse de programmes basés sur la recherche.

L'équipe a découvert qu'en entraînant un modèle de valeur en même temps que le modèle de diffusion, elle pouvait guider le processus de débruitage vers un programme qui produit les résultats souhaités. Cela permet une exploration efficace de l'espace du programme et prend des décisions plus éclairées à chaque étape du processus de génération.

Pour mettre en œuvre cette approche, l'équipe a choisi une tâche graphique inverse, qui suppose qu'un langage spécifique au domaine est utilisé pour dessiner des images.

L'équipe a déclaré : "La tâche de rétro-ingénierie convient naturellement à notre approche, car un petit changement dans le code peut conduire à des changements sémantiques significatifs dans l'image résultante

Par exemple, si Une forme égarée apparaît dans l'image et peut être facilement vue et positionnée dans l'espace programme. La figure 1 donne quelques exemples.

Les principales contributions de cette recherche comprennent :

1. Proposer une nouvelle méthode utilisant la diffusion sur les arbres syntaxiques

2 Implémenter la méthode pour la tâche graphique inverse et constater que la nouvelle méthode est supérieure à celle-ci. la méthode précédente.

Méthode

En bref, l'idée centrale de cette méthode est : développer un modèle de diffusion de débruitage pour les arbres syntaxiques, similaire au modèle de diffusion d'images développé pour les tâches de vision.

Tout d'abord, regardons un exemple de tâche tiré de l'article d'Ellis et al. « Écrire, exécuter, évaluer : synthèse de programme avec un repl » : générer un programme à géométrie solide construite (CSG2D) basé sur une image. En utilisant CSG2D, nous pouvons combiner des primitives simples comme des cercles et des quadrilatères en utilisant des opérations booléennes comme l'addition et la soustraction pour créer des formes plus complexes en utilisant la grammaire sans contexte (CFG) suivante :

dans la figure 2, z₀ est le programme cible, x₀ est la version rendue de z₀.

La tâche consiste à inverser x₀ pour récupérer z₀. Premièrement, le processus de débruitage mute aléatoirement y=16 en y=10. Transformez ensuite le sous-arbre avec deux formes à gauche en un nouveau sous-arbre avec une seule forme. Le but ici est de former un réseau de neurones capable d'inverser ce processus de débruitage, en partant de z₃ et x₃, en fonction de l'image x₀, pour obtenir z₀.

Ce qui suit décrira d'abord comment ajouter du « bruit » à l'arbre syntaxique, puis décrira en détail comment entraîner un réseau neuronal qui inverse ce bruit, et enfin décrira comment utiliser ce réseau neuronal pour effectuer une recherche.

Échantillonnage de petites mutations

Soit z_t le programme à l'instant t. Soit p_N (z_{t+1}|z_t) la distribution sur laquelle le programme z_t est muté aléatoirement en z_{t+1}. Ici, nous espérons que la mutation p_N satisfait deux points : (1) elle est petite et (2) elle peut obtenir un z_{t+1} syntaxiquement valide.

Pour ce faire, l'équipe a exploré un large corpus de littérature sur la sécurité informatique sur les tests fuzz basés sur la grammaire. Pour s'assurer que les mutations sont petites, ils définissent d'abord une fonction σ(z) qui donne la « taille » du programme z. Dans l'expérience, un ensemble de points de terminaison (terminaux) dans CFG est défini comme primitives.

Par exemple, si elles étaient écrites dans leur langage CSG2D, les primitives ci-dessus seraient {Quad, Circle}. Lorsqu'elle travaille avec ce langage, l'approche de l'équipe consiste à laisser σ(z) = σ_primitive (z), qui compte le nombre de primitives. σ(z) peut également contenir des options telles que la profondeur, le nombre de nœuds, etc.

Ensuite, échantillonnez aléatoirement la procédure de CFG en fonction de la contrainte exacte σ_min

Afin de muter un programme z donné, générez d'abord un ensemble de nœuds candidats dans une certaine plage σ_small dans son arbre syntaxique :

Ensuite, échantillonnez uniformément un nœud de mutation à partir de cet ensemble :

Comme il peut lire l'intégralité de l'arbre syntaxique et du CFG, il sait quelle règle de génération peut obtenir m, et peut ainsi garantir que des mutations syntaxiquement valides sont obtenues. Par exemple, si m est un nombre, son remplacement doit également être un nombre. Si m est une sous-expression générale, elle peut être remplacée par n'importe quelle sous-expression générale. Par conséquent, m' peut être échantillonné, ce qui est un substitut de m :

Stratégie

Processus Forward

L'équipe traite le problème de synthèse du programme comme un problème d'inférence. Soit p (x|z) un modèle d'observation, où x peut être n'importe quel type d'observation. La tâche consiste à inverser la direction de ce modèle d'observation, c'est-à-dire à obtenir un programme z étant donné une observation x.

Tout d'abord, prenez un programme z₀ à partir d'un ensemble de données D, ou dans ce cas, échantillonnez au hasard un programme du CFG. Autrement dit, échantillonnez un z₀ qui satisfait σ(z₀) ≤ σ_max. Le bruit est ensuite ajouté à z₀, en prenant s étapes, où s ∼ Uniform [1, s_max], et s_max est un hyperparamètre :

Ensuite, un réseau neuronal conditionnel est formé qui modélise la distribution suivante.

où ϕ est le paramètre du réseau neuronal, z_t est le programme actuel, x_t est la sortie actuelle du programme et x₀ est la sortie cible qui doit être résolue.

Chemin de mutation inverse

En raison de la possibilité d'obtenir des mutations de vérité terrain, les trajectoires échantillonnées peuvent être inversées simplement via le processus direct Chaîne de Markov z₀ → z₁ →... pour générer L'objectif de la formation d'un réseau neuronal. À première vue, cela peut sembler un choix raisonnable. Cependant, entraîner directement le modèle pour inverser la dernière mutation risque de créer un signal beaucoup plus bruyant pour le réseau neuronal.

Par exemple, dans un arbre syntaxique beaucoup plus grand, le chemin de mutation d'une couleur est :

La couleur de l'image cible x₀ est rouge et la couleur de l'image mutée x₂ est verte.Si vous apprenez simplement au modèle à inverser la chaîne de Markov ci-dessus, vous pouvez entraîner le réseau à transformer le vert en bleu, même si vous pouvez directement entraîner le réseau à transformer le vert en rouge.

Par conséquent, afin de créer un meilleur signal d'entraînement, le chemin d'édition entre l'arbre cible et l'arbre de mutation peut être calculé. L’équipe a utilisé un algorithme de chemin d’édition des arbres vaguement basé sur la distance d’édition des arbres. Le problème généralisé de distance d'édition d'arbre permet l'insertion, la suppression et le remplacement de nœuds arbitraires. Mais le cadre ici est différent. L’édition d’arbres ne peut être réalisée que dans un espace d’action qui n’autorise que de petites mutations.

Pour deux arbres z_A et z_B, leurs structures syntaxiques peuvent être comparées de manière linéaire. Pour les changements qui satisfont ≤ σ_small, ils sont ajoutés à la liste de mutations. Pour les changements > σ_small, recherchez la première mutation qui réduit la distance entre les deux arbres. Par conséquent, pour deux programmes z_A et z_B quelconques, la première étape du chemin de mutation peut être calculée en un temps O (|z_A| + |z_B|).

Réseau de valeurs et recherche

L'équipe a également formé un réseau de valeurs v_ϕ (x_A, x_B), dont l'entrée est constituée de deux images rendues x_A et x_B, et la prédiction est de générer ces deux La distance d'édition entre les programmes sous-jacents de l’image. Étant donné que la distance d'édition entre les arbres a été calculée lors de l'entraînement, pour toute paire d'images rendues, leur distance d'édition procédurale de vérité terrain est directement obtenue, ce qui peut être utilisée pour entraîner cette valeur de manière supervisée.

En utilisant la nouvelle stratégie ci-dessus et le nouveau réseau de valeurs proposés par l'équipe, il est possible d'effectuer une recherche de faisceau pour n'importe quelle image cible x₀ et un programme z_t initialisé aléatoirement. A chaque itération, un ensemble de nœuds dans l'arbre de recherche avec les valeurs les plus prometteuses est conservé et seuls ces nœuds sont développés.

Architecture

La figure 3 montre un aperçu de l'architecture neuronale nouvellement proposée.

Leur modèle de débruitage q_ϕ (z_{t−1}|z_t, x_t; x₀) utilise le modèle visuel-langage. Quant à l'encodeur d'image, ils ont utilisé une implémentation standard de NF-ResNet-26 ; une architecture convolutive sans normalisateur qui évite les problèmes d'instabilité temporelle lors de l'utilisation de Batch-Norm.

L'équipe a implémenté un tokenizer personnalisé qui utilise le point de terminaison de leur CFG comme token. Le reste du modèle d'édition est un petit transformateur réservé au décodeur.

Ils ont également ajouté deux autres types de jetons : qui sert de jeton de début de phrase pour le modèle, et le jeton qui permet au modèle de faire référence à des emplacements dans son contexte.

Étant donné une image actuelle, une image cible et le programme tokenisé actuel, entraînez le modèle Transformer pour prédire les positions d'édition et le texte de remplacement de manière autorégressive. Lors des prédictions, le processus de décodage est limité par la grammaire. L'équipe a masqué le logit prédit pour inclure uniquement les positions d'édition qui représentent les nœuds de l'arbre syntaxique, et n'a obtenu que des substitutions syntaxiquement valides pour les positions d'édition sélectionnées.

Ici, nous définissons σ_small = 2, ce qui signifie que le réseau n'est autorisé à produire des modifications qu'avec moins de deux primitives. Pour les données d'entraînement, ils échantillonnent un flux infini d'expressions aléatoires du CFG. Pour les pas de bruit s, ils en sélectionnent un au hasard parmi [1, 5]. Une certaine proportion des échantillons ρ est complétée en échantillonnant aléatoirement de nouvelles expressions en tant qu'expressions mutées. Ils se sont entraînés pendant trois jours en utilisant un seul GPU NVIDIA A6000.

Expériences

Ils ont mené des expérimentations sur 4 langages graphiques spécifiques à un domaine : CSG2D, CSG2D-Sketch, TinySVG, Rainbow.

Les méthodes de référence sélectionnées sont « Écrire, exécuter, évaluer : synthèse de programme avec un repl » proposée par Ellis et al. et « CSGNet : analyseur de forme neuronale pour une géométrie solide constructive » proposé par Sharma et al.

La figure 4 compare les performances de la nouvelle méthode avec la méthode de base.

On peut voir que dans les environnements CSG2D et TinySVG, la stratégie de diffusion arborescente nouvellement proposée est nettement meilleure que la stratégie de la méthode précédente.Les performances de cette stratégie peuvent être encore améliorées si elles sont combinées avec la recherche de faisceaux, ce qui permet de résoudre le problème avec moins d'appels au moteur de rendu que les autres méthodes.

La figure ci-dessous donne quelques exemples réussis du nouveau système et le résultat de la méthode de référence. Comme vous pouvez le constater, le nouveau système peut résoudre des problèmes plus mineurs que les autres méthodes ne parviennent pas à résoudre.

La vidéo suivante montre deux exemples de procédures de récupération basées sur des croquis utilisant le langage CSG2D-Sketch, ce qui montre que le modèle d'observation ne nécessite pas nécessairement un rendu déterministe ; il peut également être composé d'images aléatoires dessinées à la main.

Pour comprendre l'impact de ces nouvelles conceptions, l'équipe a également mené des expériences d'ablation en utilisant un modèle Transformer plus petit dans un environnement Rainbow simplifié. Les résultats sont présentés dans la figure 5. Dans l’ensemble, les résultats de ces choix de conception sont prouvés.

Veuillez vous référer au document original pour plus de détails.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!