B1) PCFG

Quand les grammaires jouent aux dés

Et si une grammaire pouvait choisir ses règles au hasard, mais pas n’importe comment ?

Où se situe cet article ?

Cet article ouvre la série BP3 (Bol Processor, version 3 — voir I2). Il étend les grammaires context-free (L2) en y ajoutant des probabilités — le mécanisme fondamental qui permet au Bol Processor de générer de la musique variée tout en restant contrôlé.

Encart : Qu’est-ce qu’une PCFG ?

PCFG signifie Probabilistic Context-Free Grammar (Grammaire Hors-Contexte Probabiliste). C’est une extension des grammaires context-free (CFG) classiques où chaque règle de production est associée à une probabilité. Le terme « context-free » (hors-contexte) signifie que le remplacement d’un symbole ne dépend pas de ce qui l’entoure : on peut remplacer A par x y z que A soit au début, au milieu ou à la fin de la chaîne.

Pourquoi c’est important ?

Imaginez que vous écrivez une grammaire pour générer des phrases en français. Vous avez plusieurs façons de former un groupe nominal : « le chat », « un petit chat noir », « ce vieux matou de gouttière ». Techniquement, toutes ces formes sont correctes. Mais dans la vraie vie, « le chat » est bien plus fréquent que « ce vieux matou de gouttière ».

Une grammaire context-free (CFG) classique traite toutes les alternatives de manière égale — elle ne sait pas qu’une tournure est plus probable qu’une autre. Les grammaires probabilistes (PCFG) corrigent cette lacune en associant une probabilité à chaque règle.

Résultat : on peut non seulement reconnaître si une phrase est grammaticale, mais aussi :

Calculer quelle est la probabilité qu’elle soit produite
Choisir l’analyse la plus vraisemblable quand plusieurs sont possibles
Générer des séquences avec des fréquences réalistes

En musique, cette idée prend tout son sens. Un compositeur qui improvise ne choisit pas ses notes au hasard pur : certaines progressions sont plus « naturelles » que d’autres selon le style. Les PCFG permettent de modéliser ces tendances statistiques.

L’idée en une phrase

Une PCFG est une grammaire context-free où chaque règle de production a une probabilité, et où les probabilités de toutes les alternatives d’un même symbole somment à 1.

Expliquons pas à pas

La structure d’une PCFG

Une PCFG reprend exactement la structure d’une CFG, avec quatre composants :

Symboles non-terminaux (N) : variables intermédiaires qui seront remplacées. Exemples : S (phrase), NP (Noun Phrase, groupe nominal), VP (Verb Phrase, groupe verbal). Par convention, ils sont écrits en majuscules.

Symboles terminaux (T) : les éléments finaux qui apparaissent dans le résultat. Exemples : les mots « le », « chat », « mange ». Par convention, ils sont écrits en minuscules ou entre guillemets.

Symbole de départ : le non-terminal initial d’où commence toute génération (généralement S pour Sentence).

Règles de production : instructions de la forme A → x qui disent « A peut être remplacé par x ».

La différence avec une CFG classique ? Dans une PCFG, chaque règle est annotée d’une probabilité entre crochets [p], où p est un nombre entre 0 et 1.

Exemple 1 : une grammaire de phrases simples

S  → NP VP     [0.8]    # Une phrase = groupe nominal + groupe verbal (80%)
S  → VP        [0.2]    # Une phrase = juste un groupe verbal (20%)

NP → Det N     [0.6]    # Groupe nominal = déterminant + nom (60%)
NP → N         [0.4]    # Groupe nominal = juste un nom (40%)

VP → V NP      [0.7]    # Groupe verbal = verbe + complément (70%)
VP → V         [0.3]    # Groupe verbal = juste un verbe (30%)

Det → le       [0.5]    # Le déterminant est "le" (50%)
Det → un       [0.5]    # Le déterminant est "un" (50%)

N  → chat      [0.6]    # Le nom est "chat" (60%)
N  → chien     [0.4]    # Le nom est "chien" (40%)

V  → mange     [0.5]    # Le verbe est "mange" (50%)
V  → dort      [0.5]    # Le verbe est "dort" (50%)

Encart : Lire une règle PCFG

La notation S → NP VP [0.8] se lit :

« S peut être remplacé par NP suivi de VP »

« Cette règle a une probabilité de 0.8 (80%) »

C’est comme un dé pipé : si vous avez deux façons de développer S, avec probabilités 0.8 et 0.2, imaginez un dé à 10 faces où 8 faces donnent la première règle et 2 faces la seconde.

Vérification de normalisation :

Pour chaque non-terminal, la somme des probabilités de ses règles doit égaler 1 :

S : 0.8 + 0.2 = 1.0
NP : 0.6 + 0.4 = 1.0
VP : 0.7 + 0.3 = 1.0
Det : 0.5 + 0.5 = 1.0
N : 0.6 + 0.4 = 1.0
V : 0.5 + 0.5 = 1.0

Calculer la probabilité d’une phrase :

Prenons « le chat dort ». Une dérivation est la séquence d’applications de règles qui transforme le symbole de départ S en la phrase finale. Voici comment calculer sa probabilité étape par étape :

Étape 1: S → NP VP                  Probabilité de cette règle: 0.8
Étape 2: NP → Det N (dans NP VP)    Probabilité de cette règle: 0.6
Étape 3: Det → le                   Probabilité de cette règle: 0.5
Étape 4: N → chat                   Probabilité de cette règle: 0.6
Étape 5: VP → V                     Probabilité de cette règle: 0.3
Étape 6: V → dort                   Probabilité de cette règle: 0.5

La probabilité totale est le produit de toutes les probabilités (comme pour des événements indépendants en probabilités) :

P("le chat dort") = 0.8 × 0.6 × 0.5 × 0.6 × 0.3 × 0.5 = 0.0216

Encart : Pourquoi multiplier ?

Imaginez tirer à pile ou face plusieurs fois. La probabilité d’obtenir pile puis face puis pile est : P(pile) × P(face) × P(pile) = 0.5 × 0.5 × 0.5 = 0.125

C’est le même principe : chaque choix de règle est indépendant, donc on multiplie les probabilités. Plus la dérivation est longue (plus de règles appliquées), plus la probabilité finale est petite.

Soit environ 2.16% de chance de générer exactement cette phrase avec cette grammaire. Cela peut sembler peu, mais c’est cohérent : cette grammaire peut générer des dizaines de phrases différentes.

Exemple 2 : une grammaire de tabla probabiliste

Le Bol Processor a été créé pour modéliser les compositions de tabla — le tambour à deux fûts de la musique classique indienne [KippenBel1989]. Les syllabes de percussion (bols) comme dha, dhin, tin, ta sont les terminaux naturels de ces grammaires. Voici une PCFG simplifiée inspirée des travaux de Bel et Kippen [BelKippen1992a] :

Phrase    → Motif_res Motif_res  [0.6]    # Deux motifs résonants (section ouverte)
Phrase    → Motif_res Motif_sec  [0.3]    # Résonant puis sec (contraste)
Phrase    → Motif_sec            [0.1]    # Motif sec seul (rare, section khali)

Motif_res → dha dhin dhin dha    [0.5]    # Motif résonant courant (theka de tintāl)
Motif_res → dha tirakita dhin    [0.3]    # Motif orné (tirakita = séquence rapide)
Motif_res → ghe dha dhin         [0.2]    # Motif avec attaque bāyāṅ

Motif_sec → tin ta tin            [0.6]    # Motif sec simple
Motif_sec → ta tirakita ta        [0.4]    # Motif sec orné

Cette grammaire exprime des régularités que Kippen et Bel ont observées chez les maîtres du tabla de Lucknow :

60% des phrases enchaînent deux motifs résonants (bols dha, dhin, frappés des deux mains — son riche et ouvert)
Les motifs secs (bols tin, ta, frappés d’une main — son aigu et clair) sont moins fréquents et apparaissent typiquement dans la section khali (section sans résonance) du cycle rythmique
Le motif dha dhin dhin dha est le plus probable (50%) car c’est le motif de base du theka (ostinato) du tintāl

Une génération possible :

Phrase → Motif_res Motif_sec          [0.3]
       → dha dhin dhin dha Motif_sec  [0.5]
       → dha dhin dhin dha tin ta tin  [0.6]

P = 0.3 × 0.5 × 0.6 = 0.09

Cette séquence — un motif résonant suivi d’un motif sec — a 9% de chances d’être générée. Elle reproduit le contraste typique entre les sections thali (résonante) et khali (sèche) d’un cycle de tabla.

Pourquoi normaliser à 1 ?

La contrainte que les probabilités somment à 1 pour chaque non-terminal n’est pas arbitraire. C’est une exigence mathématique fondamentale.

Encart : L’analogie de l’urne

Imaginez une urne contenant des boules de différentes couleurs. Si vous dites « il y a 70% de chance de tirer une boule rouge et 50% de chance de tirer une boule bleue », cela n’a pas de sens : 70% + 50% = 120% ! Les probabilités des événements mutuellement exclusifs (vous tirez UNE boule, pas deux) doivent sommer à 100%.

C’est exactement pareil pour les règles d’un non-terminal : quand vous développez S, vous choisissez UNE règle parmi les alternatives. Ces choix sont mutuellement exclusifs, donc leurs probabilités doivent sommer à 1.

La normalisation garantit que :

La distribution est mathématiquement valide : on peut interpréter les valeurs comme de vraies probabilités.

La somme des probabilités de toutes les phrases possibles égale 1 (pour les grammaires qui terminent toujours). Chaque phrase générée « consomme » une partie de cette probabilité totale.

On peut comparer des analyses : si une phrase a deux arbres de dérivation possibles (grammaire ambiguë), celui avec la plus haute probabilité est « préféré ».

Contre-exemple — que se passe-t-il sans normalisation ?

Si on avait :

S → A    [0.7]
S → B    [0.5]

La somme est 1.2 — ce n’est pas une distribution de probabilité valide. Concrètement, trois choses peuvent se produire selon le système utilisé :

Rejet pur : le parseur refuse la grammaire comme malformée (c’est le choix le plus strict).

Renormalisation implicite : le système divise chaque poids par la somme totale, donnant P(A) = 0.7/1.2 ≈ 0.583 et P(B) = 0.5/1.2 ≈ 0.417. Cela fonctionne en pratique, mais les probabilités « déclarées » par l’auteur de la grammaire ne correspondent plus à ce qui est réellement appliqué — source de confusion.

Utilisation naïve : le système tire un nombre aléatoire entre 0 et 1 et parcourt les règles. Si la somme dépasse 1 (comme ici, 1.2), la dernière règle « déborde » du segment [0, 1] : B devrait couvrir l’intervalle [0.7, 1.2], mais les tirages ne dépassent jamais 1, donc sa probabilité effective tombe à 0.3 au lieu de 0.5. Inversement, si la somme est inférieure à 1 (par exemple 0.3 + 0.4 = 0.7), il existe une zone « morte » de 30% où aucune règle n’est sélectionnée — la dérivation échoue silencieusement. Dans les deux cas, le comportement réel diverge de l’intention du compositeur.

En théorie formelle, seule l’option 1 est correcte : une PCFG exige la normalisation. BP3, comme nous allons le voir, choisit l’option 2 — mais en l’assumant explicitement.

BP3 vs PCFG : deux philosophies du hasard

BP3 (Bol Processor) utilise aussi des poids pour choisir entre les règles, mais avec des différences fondamentales.

Les poids statiques de BP3 (mode RND, random)

Attention : BP3 n’utilise pas des probabilités entre 0 et 1 comme les PCFG. Il utilise des poids — des nombres entiers positifs arbitraires qui expriment une importance relative. C’est BP3 qui se charge de les normaliser automatiquement en probabilités à l’exécution (option 2 du contre-exemple ci-dessus, mais assumée par conception).

gram#1[1] S → <3> A
gram#1[2] S → <2> B
gram#1[3] S → <1> C

Les poids 3, 2, 1 ne somment pas à 1 — et c’est normal. BP3 calcule les probabilités à la volée par renormalisation :

P(A) = 3/(3+2+1) = 3/6 = 0.5
P(B) = 2/(3+2+1) = 2/6 ≈ 0.333
P(C) = 1/(3+2+1) = 1/6 ≈ 0.167

Le résultat après normalisation est bien une distribution valide (somme = 1). L’avantage de cette approche : le compositeur raisonne en proportions relatives (« A est 3× plus fréquent que C ») sans se soucier de la normalisation. C’est plus intuitif que de calculer manuellement des fractions qui somment à 1.

Jusqu’ici, le résultat est mathématiquement équivalent à une PCFG — seule l’interface change (poids relatifs vs probabilités explicites).

Les poids dynamiques de BP3 : la grande différence

gram#1[1] S → <50-12> A S
gram#1[2] S → <1> fin

La notation <50-12> signifie : « poids initial 50, décrémenté de 12 à chaque utilisation ».

Évolution au fil des dérivations :

Utilisation	Poids de A	Poids de fin	P(A)
1	50	1	98%
2	38	1	97%
3	26	1	96%
4	14	1	93%
5	2	1	67%
6	0	1	0%

Au bout de 5 utilisations, la règle A devient impossible et fin est forcée.

Ce que cela permet :

Modéliser l’épuisement d’une idée musicale
Forcer la terminaison des récursions
Créer des structures de longueur contrôlée

Pourquoi ce n’est plus une PCFG :

Une PCFG a des probabilités fixes. Le même non-terminal a toujours la même distribution, quel que soit l’historique de la dérivation. C’est ce qu’on appelle la propriété de Markov (ou « sans mémoire ») : la probabilité d’un choix ne dépend que de l’état actuel, pas de comment on y est arrivé.

Encart : Processus markovien vs non-markovien

Markovien (sans mémoire) : Imaginez un jeu de cartes où, après chaque tirage, vous remettez la carte dans le paquet et vous mélangez. Peu importe que vous ayez tiré l’as de pique au tour précédent — la probabilité de le tirer à nouveau reste exactement la même (1/52). Le paquet « ne se souvient pas » des tirages passés. Une PCFG fonctionne ainsi : S a toujours les mêmes probabilités.

Non-markovien (avec mémoire) : Imaginez maintenant le même jeu, mais sans remettre les cartes. Vous tirez l’as de pique : il reste 51 cartes. Vous tirez le roi de cœur : il reste 50 cartes. À chaque tirage, la composition du paquet change et les probabilités de toutes les cartes restantes se modifient. Le paquet « se souvient » de l’historique complet. Les poids dynamiques de BP3 fonctionnent ainsi : chaque utilisation d’une règle modifie son poids, et donc la distribution de probabilité pour le choix suivant.

Les poids dynamiques de BP3 introduisent une mémoire qui viole cette hypothèse. En termes formels, BP3 avec poids dynamiques est un processus stochastique (comportant une part d’aléatoire) non-markovien : la probabilité d’un choix dépend de l’historique complet des choix passés.

Tableau comparatif

Aspect	PCFG	BP3 (poids dynamiques)
Probabilités	Fixes	Variables dans le temps
Mémoire	Sans (Markov)	Avec (compteurs)
Normalisation	Explicite (somme = 1)	Implicite (calculée à la volée)
Terminaison	Non garantie	Peut être forcée
Analyse statistique	Bien comprise	Plus complexe

Applications des PCFG

1. Traitement automatique des langues

Les PCFG sont au cœur des analyseurs syntaxiques statistiques. Quand Google Translate analyse une phrase, il utilise (entre autres) des probabilités pour choisir la bonne structure grammaticale.

Exemple d’ambiguïté résolue :
« J’ai vu l’homme avec le télescope »

Interprétation 1 : J’utilisais un télescope pour voir l’homme
Interprétation 2 : L’homme tenait un télescope

Une PCFG entraînée sur du texte réel préférera statistiquement l’interprétation la plus fréquente.

2. Génération de texte procédural

Les jeux vidéo utilisent des PCFG pour générer des descriptions, des dialogues, des noms de lieux. Les probabilités assurent une variété tout en gardant un « style » cohérent.

3. Modélisation musicale

L’application historique des grammaires probabilistes à la musique est l’œuvre de Bernard Bel et James Kippen au CNRS/GRTC (Marseille) dans les années 1980-90. Leur projet — le Bol Processor — est né de la modélisation des compositions de tabla du gharānā (école) de Lucknow [KippenBel1989]. En collaborant avec des maîtres percussionnistes indiens, ils ont montré que les séquences de bols du tabla présentent une structure grammaticale : les motifs récurrents, les variations et les proportions d’apparition peuvent être capturés par des grammaires probabilistes [BelKippen1992a]. C’est cette approche pionnière qui a donné naissance au mécanisme de poids de BP3, que nous détaillerons dans les articles suivants.

Plus largement, les PCFG ont été utilisées pour :

Analyser le style de compositeurs (quelles progressions d’accords sont typiques de Bach ?)
Générer des improvisations jazz (Keller & Morrison, 2007)
Créer des harmonisations automatiques

Encart : L’origine indienne des grammaires BP3

Dans les années 1980, l’ethnomusicologue James Kippen (University of Toronto) étudiait le tabla du gharānā de Lucknow — une tradition de percussion transmise oralement depuis des générations. Il a rencontré Bernard Bel (CNRS, Marseille), informaticien spécialiste de la représentation des connaissances. Ensemble, ils ont eu une intuition fondatrice : les séquences de bols (syllabes de percussion) que les maîtres tablistes composent et improvisent ne sont pas aléatoires — elles suivent des règles grammaticales implicites avec des fréquences d’apparition observables [KippenBel1989].

Leur « processeur de bols » — le Bol Processor — a été le premier système à appliquer des grammaires probabilistes à la musique non-occidentale. L’article fondateur [BelKippen1992a] décrit comment les modes de dérivation et les poids probabilistes permettent de modéliser la richesse des compositions de tabla. Trente ans plus tard, cette approche a influencé des outils majeurs comme TidalCycles (Alex McLean cite [Bel2001] dans 8+ publications) et reste une référence dans les surveys sur la composition algorithmique [Fernández & Vico, 2013].

4. Bio-informatique

L’analyse de séquences ARN (Acide RiboNucléique) utilise des SCFG (Stochastic Context-Free Grammar, variante des PCFG adaptée à la bio-informatique) pour modéliser les structures secondaires.

Ce qu’il faut retenir

Une PCFG associe une probabilité à chaque règle de production d’une grammaire context-free.
Les probabilités doivent être normalisées : pour chaque non-terminal, la somme des probabilités de ses alternatives égale 1.
La probabilité d’une dérivation est le produit des probabilités de toutes les règles utilisées.
Les PCFG ont des probabilités statiques (fixes), contrairement aux poids dynamiques de BP3 qui évoluent au fil de la dérivation.
Les PCFG sont utilisées en linguistique computationnelle, génération procédurale, et modélisation musicale.
Direction : cet article décrit les probabilités dans le sens de la production (génération). BP3 possède aussi un mode analytique (ANAL) où les poids sont appris : chaque règle utilisée lors de la reconnaissance d’une séquence voit son poids incrémenté — un mécanisme d’apprentissage intégré directement dans la grammaire (B8).

Pour aller plus loin

Article fondateur : Booth & Thompson (1973), « Applying Probability Measures to Abstract Languages »
Livre de référence : Jurafsky & Martin, Speech and Language Processing, chapitre sur les PCFG
Tutoriel pratique : Stanford NLP – PCFG Parsing
BP3 et poids : Bol Processor – Grammar Control
Grammaires et tabla : Bel, B. & Kippen, J. (1992), « Modelling Music with Grammars: Formal Language Representation in the Bol Processor » — l’article principal sur les PCFG appliquées au tabla (46 citations)
La genèse : Kippen, J. & Bel, B. (1989), « The Identification and Modelling of a Percussion ‘Language' » — comment les bols ont été formalisés comme un langage
Les trois directions de BP3 : B8 — production, analyse et inférence grammaticale, incluant l’apprentissage des poids en mode analytique

Glossaire

Ambiguïté (grammaire) : Propriété d’une grammaire où une même chaîne peut être dérivée de plusieurs façons différentes (plusieurs arbres de syntaxe possibles).
Arbre de dérivation (arbre de syntaxe) : Représentation visuelle d’une dérivation, avec le symbole de départ à la racine et les terminaux aux feuilles.
Bol : Syllabe mnémonique du tabla indien (ex : dha, dhin, tin, ta). Le « Bol » dans « Bol Processor ».
CFG (Context-Free Grammar) : Grammaire Hors-Contexte. Grammaire où chaque règle remplace un seul symbole non-terminal, indépendamment du contexte environnant.
Context-free (hors-contexte) : Propriété d’une règle qui s’applique quel que soit l’environnement du symbole. Le remplacement de A par xyz ne dépend pas de ce qui précède ou suit A.
Dérivation : Séquence d’applications de règles partant du symbole initial (S) jusqu’à une chaîne ne contenant que des terminaux.
Non-terminal : Symbole intermédiaire (variable) qui sera remplacé durant la dérivation. Par convention, écrit en majuscules (S, NP, VP).
Normalisation : Contrainte mathématique que les probabilités d’un ensemble d’alternatives mutuellement exclusives somment à 1 (100%).
PCFG (Probabilistic CFG) : Grammaire context-free où chaque règle de production est associée à une probabilité.
Poids dynamique : Dans BP3, poids numérique associé à une règle qui change (généralement décroît) après chaque utilisation de cette règle.
Processus markovien (sans mémoire) : Processus stochastique où la probabilité d’un événement futur ne dépend que de l’état présent, pas de l’historique.
Processus non-markovien (avec mémoire) : Processus stochastique où la probabilité d’un événement dépend de l’historique des événements passés.
Règle de production : Instruction de la forme A → x qui indique qu’on peut remplacer A par x.
Khali : Section « vide » (sans résonance) d’un cycle de tāla indien, où les bols secs (tin, ta) remplacent les bols résonants (dha, dhin).
Stochastique : Qui comporte un élément aléatoire. Un processus stochastique est un processus dont l’évolution dépend du hasard.
Terminal : Symbole final qui apparaît dans la sortie et ne peut plus être réécrit. Par convention, écrit en minuscules.
Theka : Pattern de base d’un tāla indien, joué en ostinato par le tabla. Séquence fixe de bols qui définit le caractère du cycle rythmique.
Tintāl : Le tāla (cycle rythmique) le plus courant de la musique classique du nord de l’Inde : 16 temps en 4 groupes de 4.

Prérequis : L2 — Grammaires context-free, I2 — Bol Processor
Temps de lecture : 8 min
Tags : #PCFG #probabilités #grammaires #BP3 #génération