Un algorithme d’analyse sémantique fondée sur les graphes via le problème de l’arborescence généralisée couvrante (A graph-based semantic parsing algorithm via the generalized spanning arborescence problem) (2022)

Abstract: Nous proposons un nouvel algorithme pour l’analyse sémantique fondée sur les graphes via le problème de l’arborescence généralisée couvrante.

## introduction dans cet article, nous nous intéressons au problème de l'analyse sémantique avec des contraintes de bonne formation, c'est-à-dire respectant les contraintes de valence et de typage des arguments. pour ces problèmes, les analyseurs modernes utilisent des architectures neuronales de type séquence-àséquence avec attention @xcite @xcite , entre autres), de façon similaire à ce qui est fait en traduction automatique @xcite . récemment, @xcite ont proposé d'utiliser une représentation du contenu sémantique formellement similaire aux constituants syntaxiques, permettant d'utiliser les modèles et algorithmes développés pour ces derniers. en d'autres termes, le même contenu sémantique est représenté différemment ce qui ouvre la voie à l'utilisation d'autres méthodes de prédiction, un principe bien connu en analyse syntaxique @xcite . dans la même lignée, nous proposons de prédire l'arbre de syntaxe abstraite (asa) associé à un programme sémantique (voir figure 1b ), ce qui ouvre la voie aux méthodes de prédiction structurée fondées sur les graphes. celles-ci comportent deux étapes @xcite : nous nous focalisons sur des représentations sémantiques dont les asa n'ont pas de réentrance. nous posons les hypothèses suivantes : nous qualifions de sémantiquement « vides » les mots qui ne sont l'ancre d'aucun prédicat ou argument. le problème du calcul du sous-graphe contraint se réduit alors à un problème joint d'étiquetage et d'analyse en dépendances bi-lexicales : une étiquette (correspondant à un prédicat, un argument ou un vide sémantique) doit être choisie pour chaque mot et les dépendances bi-lexicales identifient les arguments des prédicats. en terme de graphe, cela correspond à une arborescence couvrante généralisée @xcite , représentation déjà utilisée en traitement automatique des langues pour l'analyse en constituants discontinus @xcite . nos contributions peuvent être résumées comme suit : 1. nous proposons une nouvelle approche pour l'analyse sémantique fondée sur les graphes ; 2. nous proposons un nouvel algorithme pour calculer l'arborescence couvrante généralisée de poids maximum capable de prendre en compte les contraintes de la grammaire sémantique ; 3. nous proposons une approche d'apprentissage par approximations variationnelles afin de pouvoir utiliser des données où l'ancrage des prédicats et arguments est absent des annotations ; 4. nous évaluons notre approche sur deux jeux de données. b⟩ est une arborescence généralisée couvrante sur what state has the most major cities ? ∅ state loc_1 ∅ most major city_all ∅ join : loc_1 join : city_all join : major(city_all) join : loc_1(major(city_all)) join : state(loc_1(major(city_all))) join : most(state(loc_1(major(city_all)))) join : most(state(loc_1(major(city_all)))) (a) len intersection riverid river loc_2 stateid (b) where is indianapolis ? ∅ loc_1 len cityid riverid (c) figure 1 -(a) exemple de la réduction de l'analyse sémantique à une analyse en constituants. l'analyseur de herzig & berant (2021) ne peut pas produire cette structure car elle est en dehors de l'espace de recherche : le constituant formé par les mots soulignés par un trait plein rouge a un parent également discontinue via l'ajout du mot souligné avec un trait pointillé vert (corro, 2020, section 3.6). (b) exemple d'un arbre de syntaxe abstraite. (c) exemple d'analyse sémantique d'une phrase sous forme d'une arborescence généralisée couvrante. la partition π de g si et seulement si g ′ est une arborescence et que v [b] contient exactement un noeud par groupe de π. en pratique, l'objectif est de calculer l'analyse sémantique la plus probable d'après une fonction de coût paramétrisée par un réseau de neurones. malheureusement, le problème de l'arborescence couvrante généralisée de poids maximum est un problème np-difficile @xcite . nous faisons l'hypothèse que les contraintes du langage sémantique que nous ajoutons n'en changent pas la complexité. ## programme mathématique et méthode de résolution nous proposons une modélisation du problème d'analyse syntaxique décrit dans la section précédente sous forme d'un programme linéaire en nombre entiers. notre formulation est fondée sur des flots multi-commodités mais adaptés à notre problème particulier @xcite . l'intuition est la suivante : la racine 0 du graphe envoie une unité de flot à chaque groupe de noeuds dans π. s'il existe un chemin entre la racine et un noeud du groupe, alors le flot est consommé par celui-ci. de plus, en restreignant le nombre d'arcs sélectionnés à être égal à |π| -1, seules les structures de type arborescence couvrante satisfont les contraintes. nous définissons trois vecteurs de variables binaires : @xmath0, 1} v indiquant la présence ou l'absence d'un noeud dans l'arborescence généralisée couvrante ; @xmath1, 1} a indiquant la présence ou l'absence d'un arc dans l'arborescence généralisée couvrante ; @xmath2, 1} a×π indiquant la quantité de flot à destination d'un groupe passant sur un arc. les vecteurs µ ∈ r v et ϕ ∈ r a contiennent les poids associés aux noeuds et aux arcs, respectivement. le problème de l'analyse sémantique via l'arborescence généralisée couvrante peut être formulé de la façon suivante : la racine envoie une unité de flot par groupe dans π \{v 0 } (contraintes 1) et seuls les arcs sélectionnés peuvent transporter des unités de flot (contraintes 4). chaque groupe consomme l'unité de flot lui étant destiné et propage les autres (contraintes 5). en ajoutant la contrainte (2) qui impose qu'exactement @xmath3, y est contraint à être une arborescence sur les groupes « contractés », c'est-à-dire que cela ne garantit pas que tous les arcs sélectionnés incidents d'un groupe soient incidents au même noeud. un noeud est sélectionné si et seulement s'il admet un arc entrant (contrainte 3). maximiser l'objectif sous les contraintes (1-5) est un problème polynomial : on peut utiliser l'algorithme de chu-liu-edmonds sur un graphe dans lequel les groupes ont été contractés, comme observé par @xcite . finalement, les contraintes (6) garantissent qu'un noeud ne peut avoir des arcs sortants que s'il est selectionné et que le type et la valence de la grammaire sémantique sont respectés dans le sous-graphe prédit. on observe que ces dernières contraintes rendent le problème difficile : il n'existe plus d'algorithme polynomial permettant de résoudre le programme linéaire en nombre entiers lorsque celles-ci sont introduites. nous proposons d'introduire les contraintes (6) comme des pénalités quadratiques dans l'objectif @xcite et d'utiliser la méthode du gradient conditionnel (a.k.a frank-wolfe, frank & wolfe, 1956; levitin & polyak, 1966) pour résoudre le problème résultant, approche introduite par yurtsever et al. (2018). cette méthode consiste à résoudre le problème de manière itérative par descente de gradient sur des approximations du premier ordre de l'objectif. ces approximations sont produites par un oracle linéaire qui, dans notre cas, est simplement l'algorithme de chu-liu-edmonds sur un graphe contracté. un avantage de cette méthode d'optimisation est que si seules des égalités sont relâchées, la taille de pas optimale peut être calculée sous une forme analytique -si des inégalités sont également relâchées (voir section 4), une taille de pas quasi-optimale peut être trouvée par bisection car l'espace de recherche est borné. notons que notre algorithme retourne la relaxation continue du programme linéaire en nombres entiers. si la solution optimale n'est pas binaire, nous utilisons cplex pour résoudre le programme ci-dessus en conservant uniquement les variables ayant une valeur non-nulle dans la solution de la relaxation continue. ce dernier programme a donc un très petit nombre de variables et est rapide à résoudre. ## apprentissage sans les ancrages les jeux de données annotés en représentation sémantique ne contiennent pas nécessairement les ancrages des prédicats et arguments sur les mots de la phrase. c'est le cas des données geoquery @xcite que nous utilisons dans nos expériences. nous proposons donc un objectif probabiliste dans lequel nous marginalisons sur toutes les solutions induisant la représentation sémantique annotée dans les données d'entrainement. soit x et y deux variables aléatoires dont les réalisations x et y sont définies de façon similaire aux variables du programme mathématique. la probabilité d'un couple ⟨x, y⟩ est définie comme : ces deux termes étant intractables, nous dérivons une borne supérieure tractable. borne supérieure où m est le polytope des marginaux, c'est-à-dire l'enveloppe convexe des solutions entières faisables. le terme h[p] =i p i log p i est l'entropie de shannon et h m [m] est définie tel que les deux premières formes variationelles sont équivalentes (cette fonction d'entropie jointe n'a généralement pas de forme analytique). nous dérivons une borne supérieure en maximisant sur un espace de recherche plus grand, c-à-d l ⊇ m, et en décomposant le terme d'entropie jointe @xcite , propriété 4 du summary en page 41). en particulier, on observe que chaque solution faisable a exactement un arc entrant et un noeud sélectionné par groupe. nous imposons uniquement cette contrainte, l'approximation de c étant alors un ensemble de log-partitions de distributions de boltzmann indépendantes, deux par par groupe (une pour les arcs et une pour les noeuds). plutôt que de calculer la distribution q qui maximise cette borne inférieure, nous cherchons la distribution qui assigne une probabilité de 1 au couple ⟨x, y⟩ de poids maximum. ceci est équivalent à trouver un alignement entre les noeuds de l'asa sémantique et les mots de la phrase foot_0 . notons que si nous n'avons aucune contrainte d'alignement, c'est-à-dire qu'un mot peut être l'ancrage de plusieurs noeuds de l'asa, alors on peut calculer l'alignement de poids maximum par programmation dynamique, où l'algorithme remonte les noeuds de l'asa dans l'ordre topologique inverse, d'une façon similaire à l'algorithme d'étiquetage d'arbre de dérivation @xcite . si nous ajoutons la contrainte que chaque mot ne peut être aligné qu'avec au plus un noeud, alors le problème devient intractable. nous remplaçons donc cette contrainte par une pénalité quadratique dans l'objectif et utilisons l'algorithme du gradient conditionnel où notre programme dynamique est l'oracle linéaire. ## conclusion dans cet article, nous proposons une nouvelle approche pour l'analyse sémantique fondée sur les graphes par réduction au problème de l'arborescence généralisée couvrante. cette approche est différente de ce qui a été exploré dans la littérature et permet, entre autre, d'explorer un espace de recherche plus grand que l'approche @xcite . des travaux futurs pourront s'intéresser à l'utilisation de notre analyseur pour d'autres jeux de données et à améliorer les résultats sur les découpages non-aléatoires.