Exact Regular-Constrained Sampling for Variable-Order Markov Generation

Par François Pachet

François Pachet. “Exact Regular-Constrained Sampling for Variable-Order Markov Generation.” NeurIPS 2026, Paris.

À propos de l’article

Comment générer une mélodie dans un style appris en garantissant sa dernière note ? Un modèle de Markov d’ordre variable adapte la quantité de contexte récent utilisée pour prédire la suite. Cet article combine cette souplesse aux règles sur toute la mélodie, comme une fin imposée ou un motif interdit.

Résumé de l’article

La méthode suit deux états : le contexte du modèle de Markov et l’état de l’automate qui vérifie les règles. Un calcul arrière donne, pour chaque paire d’états accessible, la probabilité de terminer validement la séquence. Le prochain symbole est pondéré par sa probabilité initiale et celle de mener à une fin valide. Lorsque les contraintes ont une probabilité non nulle dans le modèle, on obtient un échantillon exact de sa distribution conditionnée.

La version arXiv s’intitule Exact Regular-Constrained Variable-Order Markov Generation via Sparse Context-State Belief Propagation.

Recherches associées

Exact Sampling for Regular and Markov Constraints with Belief Propagation · PDF (CP 2015) a introduit l’échantillonnage exact de chaînes de Markov sous contraintes régulières par propagation de croyances. L’article de 2026 l’étend aux modèles d’ordre variable.

Voir le projet Contraintes de Markov et l’article antérieur Markov Constraints: Steerable Generation of Markov Sequences.