Combining Reinforcement Learning and Constraint Programming for Sequence-Generation Tasks with Hard Constraints

Malgré les récentes avancées en apprentissage automatique pour les tâches de génération de séquences, les algorithmes d’apprentissage automatique demeurent extrêmement difficiles à contrôler. Au contraire, dans certains domaines d’applications, il est utile pour ne pas dire nécessaire que les séquences soient similaires au corpus tout en respectant un ensemble de constraintes spécifiques au domaine. Par exemple, les lois de la théorie musicale posent des lignes diretrices pour améliorer la musique générée. RL-Tuner est un algorithme préexistant qui utilise l’apprentissage par renforcement pour générer des mélodies semblables à un corpus tout en renforçant le respect des lois de la musique. Ces lois étant vérifiées individuellement, RL-Tuner ne profite pas des interactions entre toutes les contraintes. Dans notre recherche, nous combinons les contraintes dans un modèle de programmation par contraintes, afin de tirer parti de ces interactions. En outre, nous utilisons des récentes avancées en programmation par contraintes pour calculer des distributions marginales sur toutes les valeurs possibles. Ces marginales estiment la probabilité pour chaque note que cette note fasse partie d’une séquence valide. Nous commençons par générer des lignes mélodiques dans le style de la Renaissance. Nous concevons des modèles de programmation par contraintes pour restreindre la hauteur autorisée pour chaque note. Nous montrons que l’ajout de la programmation par contraintes au RL-Tuner nous permet d’augmenter la satisfaction des contraintes, tout en conservant les connaissances stylistiques extraites du corpus. Toutefois, puisque les lignes mélodiques contiennent uniquement la hauteur des notes, nous n’avons pas d’information sur la durée de chaque note et ne pouvons pas générer d’extraits audios ou faire d’évaluation qualitative.

Abstract

Even though Machine Learning algorithms for sequence generation tasks have greatly improved in the past years, they remain incredibly hard to control. However, some application domains require the generated sequences to be similar to a corpus while respecting a set of domain-specific constraints. For example, music theory laws serve as guidelines to improve music generated. RL-Tuner is a preexisting algorithm that uses Reinforcement Learning to generate melodies that are similar to a corpus while enforcing music theory. The music theory rules are checked individually and therefore the RL-Tuner does not benefit from the interactions between all the constraints. In this work, we include all the constraints into a Constraint Programming model as a way to leverage these interactions. Furthermore, we use recent advances in CP to compute marginal distributions over all the possible values reflecting the probability of this value being part of a valid sequence. We first start by generating melodic lines in the style of the Renaissance period. We design CP models to restrict the pitches allowed for each note. We show that by adding CP into the RL-Tuner, we are able to improve satisfaction of the constraints, while retaining the stylistical knowledged extracted from the corpus. However, since melodic lines provide only the pitches of the notes, we have no information about the duration of each note, and cannot generate samples or do a human study. In the second part of our work, we include in