publications
Sony CSL authors: François Pachet, Pierre Roy
Type: incollection
Keywords: plagiarism, markov constraints, constraints
BibTeX entry
@INCOLLECTION { papadopoulos:15c, AUTHOR="Papadopoulos, A. and Pachet, F. and Roy, P.", BOOKTITLE="Creativity and Universality in Language", EDITOR="Degli Esposti, M. and Altmann, E. and Pachet, F.", PUBLISHER="Springer", TITLE="Generating non-plagiaristic Markov sequences with max order Sampling", YEAR="2016", }
Sony CSL authors: François Pachet, Pierre Roy
Abstract
Many natural phenomena exhibit power law spectra. In particular, so-called 1=f noise series with close to 1 (also called pink noise) occur in sound, music and countless human artifacts or natural events, from the fluctuations of the flood levels of the Nile to movements of the stock market. As a consequence, many generative models for 1=f noise have been designed to produce series that look or sound natural or human. In this paper, we formulate the generation of 1=f series as a hard constraint satisfaction problem, so that 1=f noise generation can be used as an add-on to arbitrary sequence generation problems. We take inspiration from a simple yet beautiful stochastic algorithm invented by Voss and introduce the Voss constraint. We show that Voss algorithm can be modeled as a tree of ternary sum constraints, leading to efficient filtering. We illustrate our constraint with a melody generation problem, and show that the addition of the Voss constraint tends indeed to produce sequences whose spectrum have a 1=f distribution, regardless of the other constraints of the problem. We discuss the advantages and limitations of this approach and possible extensions.
Type: inproceedings
Keywords: 1/f, constraints, markov constraints, music generation
Downloads
BibTeX entry
@INPROCEEDINGS { pachet:15a, ADDRESS="Buenos Aires (Argentina)", AUTHOR="Pachet, F. and Roy, P. and Papadopoulos, A. and Sakellariou, J.", BOOKTITLE="24th International Joint Conference on Artificial Intelligence (IJCAI 2015)", MONTH="July", TITLE="Generating 1/f Noise Sequences as Constraint Satisfaction: the Voss Constraint", YEAR="2015", }
Sony CSL authors: François Pachet, Pierre Roy
Abstract
We address the problem of generating all possible palindromes from a corpus of Ngrams. Palindromes are texts that read the same both ways. Short palindromes (“race car”) usually carry precise, significant meanings. Long palindromes are often less meaningful, but even harder to generate. The palindrome generation problem has never been addressed, to our knowledge, from a strictly combinatorial point of view. The main difficulty is that generating palindromes require the simultaneous consideration of two inter-related levels in a sequence: the “character” and the “word” levels. Although the problem seems very combinatorial, we propose an elegant yet non-trivial graph structure that can be used to generate all possible palindromes from a given corpus of Ngrams, with a linear complexity. We illustrate our approach with short and long palindromes obtained from the Google Ngram corpus. We show how we can control the semantics, to some extent, by using arbitrary text corpora to bias the probabilities of certain sets of words. More generally this work addresses the issue of modelling human virtuosity from a combinatorial viewpoint, as a means to understand human creativity.
Type: inproceedings
Keywords: markov constraints, constraints, flow machines, palindromes, creativity
Downloads
BibTeX entry
@INPROCEEDINGS { papadopoulos:15a, ADDRESS="Buenos Aires (Argentina)", AUTHOR="Papadopoulos, A. and Roy, P. and Régin, J.-C. and Pachet, F.", BOOKTITLE="24th International Joint Conference on Artificial Intelligence (IJCAI 2015)", MONTH="July", TITLE="Generating all Possible Palindromes from Ngram Corpora", YEAR="2015", }
Sony CSL authors: François Pachet, Pierre Roy
Abstract
Sampling random sequences from a statistical model, subject to hard constraints, is generally a difficult task. In this paper, we show that for Markov models and a set of Regular global constraints and unary constraints, we can perform perfect sampling. This is achieved by defining a factor graph, composed of binary factors that combine a Markov chain and an automaton. We apply a simplified version of belief propagation to sample random sequences satisfying the global constraints, with their correct probability. Since the factor graph is linear, this procedure is efficient and exact. We illustrate this approach to the generation of sequences of text or music, imitating the style of a corpus, and verifying validity constraints, such as syntax or meter.
Type: inproceedings
Keywords: markov constraints, belief propagation
Downloads
BibTeX entry
@INPROCEEDINGS { papadopoulos:15b, ADDRESS="Cork (Ireland)", AUTHOR="Papadopoulos, A. and Pachet, F. and Roy, P. and Sakellariou, J.", BOOKTITLE="21th Principles and Practice of Constraint Programming Conference (CP 2015)", TITLE="Exact Sampling for Regular and Markov Constraints with Belief Propagation", YEAR="2015", }
Sony CSL authors: Vittorio Loreto, François Pachet
Abstract
We introduce a model for music generation where melodies are seen as a network of interacting notes. Starting from the principle of maximum entropy we assign to this network a probability distribution, which is learned from an existing musical corpus. We use this model to generate novel musical sequences that mimic the style of the corpus. Our main result is that this model can reproduce high-order patterns despite having a polynomial sample complexity. This is in contrast with the more traditionally used Markov models that have an exponential sample complexity.
Type: inproceedings
Keywords: max entropy, markov constraints, flow machines, style
Downloads
BibTeX entry
@INPROCEEDINGS { sakellariou:15a, ADDRESS="Paris (France)", AUTHOR="Sakellariou, J. and Tria, F. and Loreto, V. and Pachet, F.", BOOKTITLE="ICML Workshop on Constructive Machine Learning", MONTH="July", TITLE="Maximum Entropy Model for Melodic Patterns", YEAR="2015", }
Sony CSL authors: François Pachet, Pierre Roy
Abstract
Markov processes are widely used to generate sequences that imitate a given style, using random walk. Random walk generates sequences by iteratively concatenating states to prefixes of length equal or less than the given Markov order. However, at higher orders, Markov chains tend to replicate chunks of the corpus with a size possibly higher than the order, a primary form of plagiarism. The Markov order defines a maximum length for training but not for generation. In the framework of constraint satisfaction (CSP), we introduce M AX O RDER . This global constraint ensures that generated sequences do not include chunks larger than a given maximum order. We exhibit an automaton that recognises the solution set, with a size linear in the size of the corpus. We propose a linear-time procedure to generate this automaton from a corpus and a given max order. We then use this automaton to achieve generalised arc consistency for the M AX O RDER constraint, holding on a sequence of size n, in O(n.T ) time, where T is the size of the automaton. We illustrate our approach by generating text sequences from text corpora with a maximum order guarantee, effectively controlling plagiarism.
Type: inproceedings
Keywords: markov constraints, constraints, plagiarism, style, flow machines
Downloads
BibTeX entry
@INPROCEEDINGS { papadopoulos:14a, ADDRESS="Quebec (Canada)", AUTHOR="Papadopoulos, A. and Roy, P. and Pachet, F.", BOOKTITLE="28th Conference on Artificial Intelligence (AAAI 2014)", MONTH="July", PAGES=" 2731--2737", TITLE="Avoiding Plagiarism in Markov Sequence Generation", YEAR="2014", }
Sony CSL authors: François Pachet, Pierre Roy
Abstract
We address the problem of automatically harmonizing aleadsheet in the style of any arranger. We model the arranging style as a Markov model estimated from a corpus of non-annotated MIDI files. We consider a vertical approach to harmonization, in which chords are all taken from the arranger corpus. We show that standard Markov models, using various vertical viewpoints are not adapted for such a task, because the problem is basically over constrained. We propose the concept of fioriture to better capture the subtleties of an arranging style. Fioritures are ornaments of the given melody during which the arranging style can be expressed more freely than for melody notes. Fioritures are defined as random walks with unary constraints and can be implemented with the technique of Markov constraints. We claim that fioritures lead to musically more interesting harmonizations than previous approaches and discuss why. We focus on the style of Take 6, arguably the most sophisticated arranging style in the jazz genre, and we demonstrate the validity of our approach by harmonizing a large corpus of standard leadsheets.
Type: inproceedings
Keywords: harmonization, markov constraints, constraints, creativity, style, flow machines
Downloads
BibTeX entry
@INPROCEEDINGS { pachet:14a, ADDRESS="Ljubljiana (Slovenia)", AUTHOR="Pachet, F. and Roy, P.", BOOKTITLE="5th International Conference on Computational Creativity (ICCC 2014)", MONTH="June", PAGES="100--107", TITLE="Non-Conformant Harmonization: the Real Book in the Style of Take 6", YEAR="2014", }
Sony CSL authors: François Pachet, Pierre Roy
Abstract
We introduce the problem of generating musical leadsheets, i.e. a melody with chord labels, in the style of an arbitrary composer, that satisfy arbitrary user constraints. The problem is justified by the very nature of musical creativity, as many composers create music precisely by imitating a given style to which they add their own constraints. We propose a solution of this problem by formulating it as a Markov constraint problem. Markov constraints enable users to create stylistically imitative leadsheets that satisfy a large palette of constraints. We show that generated leadsheets are stylistically consistent by reclassifying them using Markov classifiers.
Type: inproceedings
Keywords: leadsheets, constraints, markov constraints, style, creativity
Downloads
BibTeX entry
@INPROCEEDINGS { pachet:14b, ADDRESS="Prague (Czech Republic)", AUTHOR="Pachet, F. and Roy, P.", BOOKTITLE="21st European Conference on Artificial Intelligence (ECAI 2014)", MONTH="August", PAGES="1077--1078", TITLE="Imitative Leadsheet Generation with User Constraints", YEAR="2014", }
Sony CSL authors: François Pachet, Pierre Roy
Abstract
Markov processes are increasingly used to generate finite-length sequences that imitate a given style. However, Markov processes are notoriously difficult to control. Recently, Markov constraints have been introduced to give users some control on generated sequences. Markov constraints reformulate finite-length Markov sequence generation in the framework of constraint satisfaction (CSP). However, in practice, this approach is limited to local constraints and its performance is low for global constraints, such as cardinality or arithmetic constraints. This limitation prevents generated sequences to satisfy structural properties which are independent of the style, but inherent to the domain, such as meter. In this article, we introduce meter, a constraint that ensures a sequence is 1) Markovian with regards to a given corpus and 2) follows metrical rules expressed as cumulative cost functions. Additionally, meter can simultaneously enforce cardinality constraints. We propose a domain consistency algorithm whose complexity is pseudo-polynomial. This result is obtained thanks to a theorem on the growth of sumsets by Khovanskii. We illustrate our constraint on meter-constrained music generation problems that were so far not solvable by any other technique.
Type: inproceedings
Keywords: flow machines, markov constraints, flow machines
Downloads
BibTeX entry
@INPROCEEDINGS { roy:13a, ADDRESS="Bellevue, Washington (USA)", AUTHOR="Roy, P. and Pachet, F.", BOOKTITLE="27th Conference on Artificial Intelligence (AAAI 2013)", MONTH="June", TITLE="Enforcing Meter in Finite-Length Markov Sequences", YEAR="2013", }
Sony CSL authors: Gabriele Barbieri, François Pachet, Pierre Roy
Abstract
We address the issue of generating texts in the style of an existing author, that also satisfy structural constraints imposed by the genre of the text. We focus on song lyrics, for which structural constraints are well-defined: rhyme and meter. Although Markov processes are known to be suitable for representing style, they are difficult to control in order to satisfy non-local properties, such as structural constraints, that require long distance modeling. We show that the framework of Constrained Markov Processes allows us to precisely generate texts that are consistent with a corpus, while being controllable in terms of rhymes and meter, a result that no other technique, to our knowledge, could achieve to date. Controlled Markov processes consist in reformulating Markov processes in the context of constraint satisfaction. We describe how to represent stylistic and structural properties in terms of constraints in this framework and we provide an evaluation of our method by comparing it to both pure Markov and pure constraint-based approaches.We show how this approach can be used for the semi-automatic generation of lyrics in the style of a popular author that has the same structure as an existing song.
Type: inproceedings
Keywords: Virtuoso, Markov constraints
Downloads
BibTeX entry
@INPROCEEDINGS { barbieri:12a, AUTHOR="Barbieri, G., Pachet, F., Roy, P. Degli Esposti, M.", BOOKTITLE="Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012)", EDITOR="Luc De Raedt et al.", PAGES="115--120", TITLE="Markov Constraints for Generating Lyrics with Style", YEAR="2012", }
Sony CSL authors: François Pachet, Pierre Roy
Abstract
Markov chains are a well known tool to model temporal properties of many phenomena, from text structure to fluctuations in economics. Because they are easy to generate, Markovian sequences, i.e. temporal sequences having the Markov property, are also used for content generation applications such as text or music generation that imitate a given style. However, Markov sequences are traditionally generated using greedy, left-to-right algorithms. While this approach is computationally cheap, it is fundamentally unsuited for interactive control. This paper addresses the issue of generating steerable Markovian sequences. We target interactive applications such as games, in which users want to control, through simple input devices, the way the system generates a Markovian sequence, such as a text, a musical sequence or a drawing. To this aim, we propose to revisit Markov sequence generation as a branch and bound constraint satisfaction problem (CSP). We propose a CSP formulation of the basic Markovian hypothesis as elementary Markov Constraints (EMC).We propose algorithms that achieve domain-consistency for the propagators of EMCs, in an event-based implementation of CSP. We show how EMCs can be combined to estimate the global Markovian probability of a whole sequence, and accommodate for different species of Markov generation such as fixed order, variable-order, or smoothing. Such a formulation, although more costly than traditional greedy generation algorithms, yields the immense advantage of being naturally steerable, since control specifications can be represented by arbitrary additional constraints, without any modification of the generation algorithm. We illustrate our approach on simple yet combinatorial chord sequence and melody generation problems and give some performance results.
Type: article
Keywords: Continuator, Virtuoso, Markov constraints
Downloads
BibTeX entry
@ARTICLE { pachet:09c, AUTHOR="Pachet, F. and Roy, P.", JOURNAL="Constraints", MONTH="March", NUMBER="2", PAGES="148-172", TITLE="Markov constraints: steerable generation of Markov sequences", VOLUME="16", YEAR="2011", }
Sony CSL authors: Gabriele Barbieri, François Pachet, Pierre Roy
Abstract
Many systems use Markov models to generate finite-length sequences that imitate a given style. These systems often need to enforce specific control constraints on the sequences to generate. Unfortunately, control constraints are not compatible with Markov models, as they induce long-range dependencies that violate the Markov hypothesis of limited memory. Attempts to solve this issue using heuristic search do not give any guarantee on the nature and probability of the sequences generated. We propose a novel and efficient approach to controlled Markov generation for a specific class of control constraints that 1) guarantees that generated sequences satisfy control constraints and 2) follow the statistical distribution of the initial Markov model. Revisiting Markov generation in the framework of constraint satisfaction, we show how constraints can be compiled into a non-homogeneous Markov model, using arc-consistency techniques and renormalization. We illustrate the approach on a melody generation problem and sketch some realtime applications in which control constraints are given by gesture controllers.
Type: inproceedings
Keywords: Continuator, Markov constraints, Virtuoso
Downloads
BibTeX entry
@INPROCEEDINGS { pachet:11b, ADDRESS="Barcelona, Spain", AUTHOR="Pachet, F. and Roy, P. and Barbieri, G.", BOOKTITLE="Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI", MONTH="July", PAGES="635--642", TITLE="Finite-Length Markov Processes with Constraints", YEAR="2011", }