L13) Générer ou reconnaître

La dualité des grammaires formelles

Une grammaire ne sert pas qu’à produire des phrases. Elle peut aussi les analyser. Mais ces deux usages — génération et reconnaissance — ne sont ni symétriques ni équivalents. Cette asymétrie, rarement discutée, est pourtant au cœur de la musique.

Où se situe cet article ?

Dans L1, nous avons découvert la hiérarchie des langages formels. Dans L2, nous avons appris à construire des grammaires qui produisent des phrases par dérivation. Mais nous avons toujours travaillé dans une seule direction : du sens vers les phrases.

Cet article pose une question rarement formulée : que se passe-t-il quand on inverse la direction ? Quand, au lieu de produire une phrase à partir d’une grammaire, on reçoit une phrase et on cherche à comprendre si elle appartient au langage — et quelle structure la grammaire lui assigne ?

C’est la différence entre composer et analyser, entre parler et écouter, entre encoder et décoder. Et cette différence est loin d’être triviale.

Pourquoi c’est important ?

Un piège terminologique célèbre

Le livre le plus cité en théorie musicale formelle s’intitule A Generative Theory of Tonal Music (GTTM, Lerdahl & Jackendoff, 1983 — plus de 5 000 citations). Pourtant, GTTM ne génère aucune musique. C’est une théorie analytique : étant donné une pièce musicale existante, elle fournit des règles de préférence pour lui assigner une structure hiérarchique (groupement, structure métrique, réduction temporelle).

Le terme « generative » est utilisé au sens chomskyen originel — un ensemble de règles formellement explicites — et non au sens de « production ». Lerdahl lui-même a clarifié que GTTM modélise l’auditeur (réception), pas le compositeur (émission) [Lerdahl2009].

Cette confusion illustre un problème plus profond : on utilise le même mot — « grammaire » — pour deux activités fondamentalement différentes.

Deux faces d’une même pièce

Toute grammaire formelle définit un langage — un ensemble de chaînes valides. Mais elle peut être utilisée de deux façons :

Direction	Nom technique	Question posée	Analogie musicale
→ Génération	Production / Dérivation	« Quelles phrases cette grammaire peut-elle produire ? »	Le compositeur écrit une pièce
← Reconnaissance	Parsing / Analyse	« Cette phrase appartient-elle au langage ? Quelle structure lui correspond ? »	Le musicologue analyse une prodction musicale

Mathématiquement, les deux usages définissent le même langage : l’ensemble des chaînes est identique. Mais opérationnellement, les deux directions sont radicalement différentes.

L’idée en une phrase

Une grammaire formelle est un objet bidirectionnel : elle peut générer des phrases ou les analyser, mais les deux directions diffèrent en complexité, en déterminisme et en information disponible.

Expliquons pas à pas

1. L’asymétrie computationnelle

La première différence est de nature algorithmique. Pour une grammaire context-free (CFG, Context-Free Grammar — L2) :

Générer une phrase est rapide : on part de l’axiome (start symbol — le symbole de départ de la grammaire), on applique les règles de réécriture, chaque pas est un choix local. La complexité est linéaire en la longueur de la dérivation.
Reconnaître une phrase est plus coûteux : étant donné une chaîne de n symboles, déterminer si elle appartient au langage et reconstruire sa structure nécessite un algorithme comme CYK (Cocke-Younger-Kasami) ou Earley, en temps O(n³) — c’est-à-dire proportionnel au cube de la longueur de l’entrée.

Pour des formalismes plus expressifs, l’écart se creuse dramatiquement. Les grammaires context-sensitive (Type 1, L1) ont un problème de reconnaissance qui est PSPACE-complet (Polynomial Space complete — une classe de complexité pour laquelle aucun algorithme efficace n’est connu en général) [Berwick1982].

En d’autres termes : produire est généralement plus facile qu’analyser.

Encart : L’analogie du puzzle

Construire un puzzle de 1 000 pièces à partir de l’image complète est relativement simple : on détermine comment on va le découper, on sait donc quelle pièce va où. Mais recevoir un puzzle mélangé et comprendre comment l’assembler — dans quel ordre, par quelle stratégie — est un tout autre problème. La grammaire est l’image de référence ; la génération construit le puzzle ; le parsing le désassemble pour comprendre sa structure.

2. L’asymétrie de déterminisme

La deuxième différence concerne l’ambiguïté :

En génération, on peut choisir une dérivation à chaque étape (éventuellement aléatoirement, comme dans les PCFG probabilistes — cf. B1). Le résultat est une seule phrase.
En reconnaissance, une phrase peut avoir plusieurs analyses valides. C’est l’ambiguïté structurelle : la même séquence de mots peut correspondre à plusieurs arbres de dérivation (L4).

En linguistique, la phrase « J’ai vu l’homme avec le télescope » a deux analyses : j’utilise le télescope pour voir, ou l’homme a le télescope. En musique, une même progression harmonique peut être analysée de plusieurs façons par GTTM (M6).

La génération est un processus one-to-one (une intention → une phrase). La reconnaissance est un processus one-to-many (une phrase → plusieurs structures possibles).

3. L’asymétrie d’information

Le générateur a accès à tout : l’intention communicative, les contraintes stylistiques, le contexte pragmatique. L’analyseur n’a accès qu’au signal observable — la surface sonore, la séquence de symboles.

En musique, le compositeur sait pourquoi il a choisi telle note. L’auditeur doit inférer cette intention à partir du résultat. C’est le problème fondamental de toute analyse musicale : les contraintes créatives sont disponibles pour le générateur mais doivent être reconstruites par l’analyseur.

Umberto Eco, dans L’œuvre ouverte (1962), a formalisé cette asymétrie : une seule production (l’œuvre) admet de multiples interprétations (analyses). La fonction de génération est many-to-one (de multiples intentions convergent vers une œuvre), tandis que la fonction d’analyse est one-to-many (une œuvre diverge vers de multiples interprétations).

4. L’asymétrie temporelle : offline vs temps réel

Les trois asymétries précédentes supposent implicitement qu’on a tout le temps nécessaire — qu’on travaille offline. Mais quand la contrainte du temps réel s’ajoute, l’asymétrie se creuse.

Générer en temps réel est relativement naturel : on produit symbole par symbole, au fil de l’eau. Un compositeur qui improvise, un live coder qui modifie son code pendant le concert — chaque décision est locale et immédiate.
Analyser en temps réel est beaucoup plus difficile : on reçoit le signal au fur et à mesure, sans connaître la suite. L’analyseur doit maintenir des hypothèses multiples sur la structure en cours — c’est le problème du parsing incrémental [Hale2001].

En musique, cette asymétrie est omniprésente. Un auditeur au concert entend les notes une par une. Il ne peut pas « revenir en arrière » pour réanalyser un passage. Son analyse est contrainte par le flux — il doit interpréter en temps réel, avec des informations partielles.

Encart : Le concert vs la partition

Un musicologue qui analyse une sonate de Beethoven a la partition complète sous les yeux — il peut aller et venir, comparer des passages distants, réviser ses interprétations. Un auditeur au concert n’a que le flux sonore : chaque seconde efface la précédente (sauf en mémoire). Les deux font de l’« analyse », mais sous des contraintes temporelles radicalement différentes. Le premier travaille offline (toute l’information disponible d’un coup) ; le second travaille en streaming (information partielle, séquentielle, irréversible).

Le modèle IDyOM formalise exactement cette situation : il prédit la note suivante à partir des notes déjà entendues, sans jamais voir l’avenir. C’est un décodeur incrémental au sens de Shannon — et c’est précisément ce qui le rend plus difficile que la génération.

5. Le pont : l’analyse par synthèse

Le paradigme analysis-by-synthesis (analyse par synthèse), né dans la recherche sur la perception de la parole dans les années 1960, propose un pont entre les deux directions : pour reconnaître un signal, on génère des candidats internes et on les compare au signal reçu [HalleStevens1962].

L’analyse contient la synthèse comme sous-processus. Le récepteur n’est pas un simple filtre passif : il possède un modèle interne génératif qui produit des hypothèses, testées contre l’entrée.

En musique, cela correspond à l’expérience de l’auditeur expert : quand vous entendez un ii-V-I (la progression sous-dominante → dominante → tonique, par exemple Dm7 → G7 → Cmaj7 en do majeur), vous anticipez la résolution parce que votre modèle interne a généré cette attente. Les modèles comme IDyOM (Information Dynamics of Music — un modèle de prédiction musicale basé sur les statistiques d’un corpus) formalisent exactement ce processus prédictif [Pearce2018].

6. Les grammaires réversibles

Certains formalismes sont conçus pour fonctionner dans les deux directions avec la même grammaire :

GF (Grammatical Framework, Ranta, 2019) — un formalisme multilingue où les grammaires sont explicitement réversibles, permettant à la fois le parsing et la génération [Ranta2019]
Grammaires d’unification — utilisées en traduction automatique bidirectionnelle [vanNoord1990]
Steedman (1984 → 2014) — la même grammaire CCG (Combinatory Categorial Grammar — L9) pour les progressions de jazz a été utilisée d’abord pour générer des séquences d’accords [Steedman1984], puis 30 ans plus tard pour les parser (les analyser automatiquement) [GranrothWilding2014]. C’est un exemple remarquable de la même grammaire musicale utilisée dans les deux directions — avec des défis computationnels très différents.

Mais la réversibilité n’est pas automatique. Strzalkowski (1993) a montré qu’une grammaire conçue pour le parsing nécessite des transformations (une « inversion ») pour être utilisée en génération. Le fait même qu’un processus d’inversion soit nécessaire prouve l’asymétrie opérationnelle [Strzalkowski1993].

7. En musique : trois paradigmes

La dualité génération/reconnaissance structure l’ensemble de la musicologie computationnelle :

Le paradigme analytique — la grammaire comme outil d’écoute :

GTTM (Lerdahl & Jackendoff, 1983) : modèle de l’auditeur, pas du compositeur (M6)
Analyse schenkérienne computationnelle : parsing d’une pièce existante pour en extraire la structure profonde [MavromatissBrown2004]
IDyOM : modèle statistique de prédiction musicale — l’auditeur comme machine d’inférence

Le paradigme génératif — la grammaire comme outil de composition :

Holtzman (1981) : utilisation pionnière de grammaires pour la composition automatique
Steedman (1984) : grammaire CCG pour produire des progressions de jazz
Cope / EMI (1989) : système hybride qui analyse un corpus puis génère de nouvelles pièces — les deux directions dans un même système

Le paradigme bidirectionnel — la grammaire comme pont :

Le Bol Processor (Bel & Kippen, 1992) est le cas le plus explicite. BP3 possède trois modes d’utilisation de la grammaire :

– PROD (production, modus ponens) : la grammaire génère des séquences musicales
– ANAL (analysis, modus tollens) : la grammaire teste si une séquence appartient au langage et, le cas échéant, en identifie la structure
– TEMP (template) : la grammaire produit des séquences respectant un gabarit donné

Le cycle complet de Bel et Kippen pour le tabla illustre parfaitement la dualité : un musicien produit des séquences de bols (syllabes mnémoniques du tabla — B2), le système analyse ces séquences pour en inférer une grammaire (via QAVAID, Question Answer Validated Analytical Inference Device — un système d’inférence grammaticale interactif), puis cette grammaire peut re-produire de nouvelles séquences, que le musicien évalue. C’est une boucle analyse → grammaire → génération → évaluation → analyse [KippenBel1989].

8. La troisième direction : l’inférence grammaticale

Au-delà de la dualité génération/reconnaissance, il existe une troisième direction encore plus fondamentale : l’inférence grammaticale (grammar induction) — étant donné des exemples de phrases, retrouver la grammaire elle-même [delaHiguera2010].

C’est le problème inverse de la théorie des langages formels :

Génération : grammaire → phrases
Reconnaissance : grammaire + phrase → oui/non + structure
Inférence : phrases → grammaire

En musique, c’est exactement ce que fait un musicologue quand il écoute un corpus et tente d’en extraire les « règles » — les conventions stylistiques, les contraintes harmoniques, les patterns rythmiques. C’est aussi ce que font les systèmes d’inférence grammaticale comme QAVAID pour le tabla ou les travaux de Cruz-Alcázar & Vidal pour l’identification de style musical [CruzAlcazar2008].

Cette direction sera explorée en détail dans M10.

Le modèle de Shannon : encodeur ≠ décodeur

Le modèle de communication de Claude Shannon (1948) formalise l’asymétrie au niveau le plus fondamental :

Source → Encodeur → Canal → Décodeur → Destination

L’encodeur (génération) et le décodeur (reconnaissance) ne sont pas symétriques :

L’encodeur transforme un message en signal — c’est un choix parmi les possibles
Le décodeur reconstruit le message à partir du signal bruité — c’est une inférence du plus probable

Le canal introduit du bruit — de l’incertitude, de la perte. En musique : l’air est un canal bruité, l’oreille est un décodeur imparfait, la partition est un encodeur lossy (elle ne capture pas le timbre, le toucher, l’intention). Chaque traduction entre représentations musicales est un passage encodeur → canal → décodeur, avec ses propres pertes et ambiguïtés.

Ce qu’il faut retenir

Toute grammaire a deux usages : générer (produire des phrases) et reconnaître (analyser des phrases existantes).
Ces deux directions sont mathématiquement équivalentes (même langage) mais opérationnellement asymétriques : complexité différente, déterminisme différent, information disponible différente.
Générer est généralement plus facile qu’analyser : O(n) vs O(n³) pour les CFG, et l’écart se creuse pour les formalismes plus expressifs.
En temps réel, l’asymétrie se creuse encore : générer en streaming est naturel (on produit au fil de l’eau), analyser en streaming est difficile (on n’a pas encore vu la suite — parsing incrémental).
L’analyse par synthèse montre que la reconnaissance utilise la génération comme sous-processus interne.
En musique, GTTM est analytique (malgré son titre), Steedman est bidirectionnel, et BP3 est explicitement réversible (modes PROD/ANAL/TEMP).
L’inférence grammaticale est la troisième direction : retrouver la grammaire à partir des exemples — le problème fondamental de la musicologie computationnelle.

Pour aller plus loin

Fondements théoriques

Berwick, R. (1984). « Strong Generative Capacity, Weak Generative Capacity, and Modern Linguistic Theories. » Computational Linguistics.
Strzalkowski, T. (1993). Reversible Grammar in Natural Language Processing. Springer — ouvrage fondateur sur les grammaires réversibles.
de la Higuera, C. (2010). Grammatical Inference: Learning Automata and Grammars. Cambridge University Press — référence sur l’inférence grammaticale.

Musique

Lerdahl, F. & Jackendoff, R. (1983). A Generative Theory of Tonal Music. MIT Press — le modèle analytique le plus influent.
Steedman, M. (1984). « A Generative Grammar for Jazz Chord Sequences. » Music Perception — grammaire de jazz utilisée ensuite pour le parsing (Granroth-Wilding & Steedman, 2014).
Bel, B. & Kippen, J. (1992). « Modelling Music with Grammars: Formal Language Representation in the Bol Processor » — le système bidirectionnel par excellence.
Cruz-Alcázar, P.P. & Vidal, E. (2008). « Two Grammatical Inference Applications in Music Processing. » Applied Artificial Intelligence.

Asymétrie temporelle et parsing incrémental

Hale, J. (2001). « A Probabilistic Earley Parser as a Psycholinguistic Model. » NAACL — modèle fondateur du parsing incrémental probabiliste.

Analysis-by-synthesis

Halle, M. & Stevens, K.N. (1962). « Speech Recognition: A Model and a Program for Research. » IRE Transactions on Information Theory.
Poeppel, D. & Monahan, P.J. (2011). « Feedforward and Feedback in Speech Perception: Revisiting Analysis by Synthesis. » Language and Cognitive Processes.

Dans le corpus

L1 — Les niveaux de complexité
L2 — Les grammaires qui produisent
L9 — Les formalismes mildly context-sensitive (TAG, CCG)
M6 — GTTM : le paradigme analytique appliqué
M10 — L’inférence grammaticale en musique (à venir)
B6 — Wildcards BP3 : du pattern matching dans la grammaire

Glossaire

Analysis-by-synthesis (analyse par synthèse) : Paradigme de reconnaissance où le récepteur génère des candidats internes et les compare au signal reçu. L’analyse contient la synthèse comme sous-processus.
ANAL (mode) : Mode analytique du Bol Processor — la grammaire teste si une séquence appartient au langage (modus tollens).
Ambiguïté structurelle : Propriété d’une phrase qui admet plusieurs arbres de dérivation pour la même grammaire. Fréquente en reconnaissance, absente en génération.
Encodeur / Décodeur : Dans le modèle de Shannon, l’encodeur transforme un message en signal (génération), le décodeur reconstruit le message depuis le signal (reconnaissance). Ils ne sont pas symétriques.
Grammaire réversible : Grammaire conçue pour être utilisée dans les deux directions (génération et parsing) sans transformation. Exemples : GF, grammaires d’unification.
IDyOM (Information Dynamics of Music) : Modèle statistique de prédiction musicale basé sur l’entropie d’un corpus. Modélise l’auditeur comme machine d’inférence.
Inférence grammaticale (grammar induction) : La « troisième direction » — retrouver la grammaire à partir d’exemples de phrases. Problème inverse de la théorie des langages formels.
Modus ponens / modus tollens : En logique, le modus ponens va de la règle vers la conséquence (si A alors B, A, donc B — direction générative). Le modus tollens va de l’observation vers la prémisse (si A alors B, B observé, donc A plausible — direction analytique).
NLG / NLU (Natural Language Generation / Understanding) : Les deux sous-domaines du NLP (Natural Language Processing, traitement automatique des langues) qui incarnent la dualité génération/reconnaissance.
Parsing incrémental : Analyse syntaxique qui traite l’entrée symbole par symbole, au fur et à mesure de sa réception, sans attendre la fin de la phrase. Nécessaire pour l’analyse en temps réel. Plus difficile que le parsing offline car l’analyseur n’a pas accès à la suite du signal.
Parsing (analyse syntaxique) : Processus qui, étant donné une phrase et une grammaire, détermine si la phrase appartient au langage et reconstruit sa structure (arbre de dérivation).
PROD (mode) : Mode production du Bol Processor — la grammaire génère des séquences musicales (modus ponens).
QAVAID (Question Answer Validated Analytical Inference Device) : Système d’inférence grammaticale interactif de Bel & Kippen pour le tabla. Le nom signifie aussi « grammaire » en arabe/ourdou.

Prérequis : L1, L2
Temps de lecture : 14 min
Tags : #grammaires #dualité #génération #reconnaissance #parsing #analyse-par-synthèse #BP3