Many systems use Markov models to generate finite-length sequences that imitate a given style. With such systems, users often need to enforce specific control properties on the sequences to generate. Unfortunately, control most often induces 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, so we investigate another solution: Markov constraints.
Reformulating Markov processes as constraint satisfaction problems yields immense advantages over existing approaches to this control problem. To make this approach practicable we investigate, in the FlowMachines project, how specific classes of control properties can be handled efficiently.
Specific topics:
General Markov Constraints: The basic idea to reformulate Markov processes as constraint satisfaction problems. This enables the computation of optimal Markov sequences for arbitrary user control constraints, though with unknown complexity bounds. We show applications to chord sequence and melody generation.
Unary Constraints: Unary constraints can be handled very efficiently, using a greedy algorithm. An applet shows the algorithm at work on a jazz virtuoso improvisation problem, inspired by John McLaughlin. See also the MIROR and Virtuoso projects.
Text Generation: Unary constraints can be used to generate text in specific styles, that satisfy syntactic, rhyme and prosody constraints. We rewrite the lyrics of Yesterday by the Beatles, in the style of Bob Dylan, as well as many other authors.
Meter and Cardinality: This result shows how meter (and cardinality) can be handled with pseudo-polynomial complexity, opening the way to fully-fledged composition applications.
MaxOrder and Plagiarism: This result shows how to enforce a MaxOrder constraint on generated sequences. MaxOrder enables an accurate control on plagiarism, a property that was so far out of reach using traditional approaches.
1/f noise sequences: A nice result showing that we can enforce a 1/f spectrum in symbolic sequences with arbitrary constraints (including Markov). (Related paper)
Sampling regular Markov constraints: This result shows how to do perfect sampling of Markov sequences with regular constraints. This result superseeds in principle the meter and maxOrder constraints by providing sampling (i.e., a distribution of solutions according to their probability in the Markov model). (Related paper)