Pachet, F. and Roy, P.
Markov constraints: steerable generation of Markov sequences.
Constraints,
16(2):148-172, March
2011.

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.

Keywords: Continuator, Virtuoso, Markov constraints

### Downloads

Adobe Acrobat PDF file

### 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",
}