Finite-Length Markov Processes with Constraints

1 Introduction

Markov processes are a popular modeling tool used in content generation applications, such as text generation, music composition and interaction. Markov processes are based on the "Markov hypothesis" which states that the future state of a sequence depends only on the last state, i.e.,

The Markovian aspects of musical sequences have long been acknowledged, see e.g. [Brooks et al., 1992]. Many attempts to model musical style have therefore exploited Markov chains in various ways [Nierhaus, 2009], notably sequence generation.

In practice, Markov models are often estimated by counting occurrences and transitions in a corpus of training sequences. Once the model is learn, sequences can be generated simply by random walk: the first item is chosen randomly using the prior probabilities; then, a continuation is drawn using the model, and appended to the first item. This is iterated to produce a sequence of length L. This process has the advantage of being simple to implement and efficient.

For instance, the Continuator [Pachet, 2002] uses a Markov model to react interactively to music input. Its success was largely due to its capacity to faithfully imitate arbitrary musical styles, at least for relatively short time frames. Indeed, the Markov hypothesis basically holds for most melodies played by users (from children to professionals) in many styles of tonal music (classical, jazz, pop, etc.). The other reason of its success is the variety of outputs produced for a given input. All continuations produced are stylistically convincing, thereby giving the sense that the system creates infinite, but plausible, possibilities from the user's style.

With the Continuator, a user typically plays a musical phrase using a MIDI keyboard. The phrase is then converted into a sequence of symbols, representing a given dimension of music, such as pitch, duration, or velocity. The sequence is then analyzed by the system to update the Markov model. When the phrase is finished, typically after a certain temporal threshold has passed, the system generates a new phrase using the model built so far. The user can then play another phrase, or interrupt the phrase being played, depending on the chosen interaction mode. It was shown that such incremental learning creates engaging dialogs with users, both with professional musicians and children [Addessi and Pachet, 2005]. Other systems such as Omax [Cont et al., 2007] followed the same principle with similar results.

In such interactive contexts, the control problemmanifests itself under different forms:

• The so-called zero-frequency problem arises during random walk, when an item with no continuation is chosen (see, e.g. [Chordia et al., 2010]). Many strategies have been devised to circumvent this problem, including restarting the walk from scratch [Dubnov et al., 2003].
• The end point or [Davismoon and Eccles, 2010] concern the fact that the generated sequence can violate musical constraints holding, e.g., on the pitch range of the melody.
• User control constraints. In a musical context, the user may want the sequence to be globally ascending, pitchwise, or to follow an arbitrary pitch contour. These constraints can be a consequence of a particular gesture, de-

tected, e.g., by input sensors. For instance, it may be interesting to improvise a melody that ends on a particular note. This is a striking effect used in Hard-Rock guitar virtuoso improvisations, which often consist of a frantic sequence of notes ending gracefully on a note of the triad (e.g. the tonic of the underlying chord).

Most approaches proposed to deal with these issues consist in grafting heuristic search on top of random walk: simulated annealing [Davismoon and Eccles, 2010], case-based reasoning [Eigenfield and Pasquier, 2010], generate-and-test [Dubnov et al., 2003]. However, these methods do not offer any guarantee that a solution will be found. Moreover, the solutions found are not consistent with the underlying Markov model, i.e., the probability to draw them is not the Markov probability. Lastly, these methods are not efficient enough for interactive, real-time applications.

Mixed Networks [Dechter and Mateescu, 2004], a special case of graphical models, combine constraints and probabilities in a coherent manner. However the problem addressed is different: infer the posterior probabilities of the new model obtained mixing constraints and probabilities. Instead we generate a new model that, when combined with the constraints, is equivalent, probability-wise, to the initial Markov model.

It is important to note that HiddenMarkovModels (HMM) cannot be applied, because in our context the Bellman principle does not hold. Control constraints cannot be modeled as cumulative cost functions: even anchor constraints (imposing a fixed value at a specific position) may have implications on the whole sequence, as we show below.

As outlined by [Pachet and Roy, 2011], control constraints raise a fundamental issue since they establish relationships between items that violate the Markov hypothesis: obviously as soon as the constraint scope (the variables on which the constraint holds) is larger than the Markov scope, the information cannot be represented in a Markov model. However, even constraints that remain within the Markov scope (e.g., unary constraints) create implicit dependencies that violate the Markov hypothesis.

[Pachet and Roy, 2011] show that the reformulation of the problem as a constraint satisfaction problem allows, for arbitrary sets of control constraints, to compute optimal, singular solutions, i.e., sequences that satisfy control constraints while being optimally probable. However, what is often needed in practice is a distribution of good sequences. We cannot use the approach of [Pachet and Roy, 2011], as it does not produce a distribution of sequences, but only optimal solutions. Furthermore, it involves a complete search-optimization algorithm, which limits real-time use.

In this paper, we show that when control constraints do not exceed the Markov scope (unary and binary adjacent for order-1, as defined below) they can be "compiled" into a new Markov model that is statistically equivalent to the initial one. This yields the advantage of retaining the simplicity of random walk, while ensuring that control constraints are satisfied. This result is obtained by establishing yet another bridge between Markov generation and constraint satisfaction.

Section 2 introduces an example to illustrate our problem, Section 3 states the problem in the framework of constraint Table 1: The 16 4-note melodies satisfying the control constraint and their probabilities in M. The sum of probabilities for these sequences, σ = 77/384, is not 1 because M generates sequences that do not satisfy the constraint.

satisfaction, Section 4 describes how to build the new model and Section 5 sketches some applications.

2 AMelody Generation Example

Let us consider a Markov model M estimated from the two sequences (melodies) shown in Figure 1.

The prior vector of M is:

The transition probabilities of M are:

We consider the problem of generating 4-note melodies. There are 60 possible such melodies with non-zero probabilities. For instance, sequence CDED has probability:

We then add the control constraint that the last pitch be a D. There are only 16 such sequences (see Table 1).

Our goal is to build a Markov process ˜M that generates exactly these 16 melodies with the same probability distribution. In general, of course, the solutions and their probabilities are not known. We show here how to build ˜M given M and control constraints, for a particular class of constraints.

3 Problem Statement

We are interested in generating fixed-length sequences from a Markov process M that satisfy control constraints. To use a random walk approach, we need a Markov process ˜M that generates exactly the sequences satisfying the control constraints with the probability distribution defined by M. In general, it is not possible to find such a Markov process because control constraints violate the Markov property, as outlined by [Pachet and Roy, 2011]. However, when control constraints remain within the Markov scope, we show that such a model exists and can be created with a low complexity.

For the sake of simplicity, we consider only order-1 Markov processes, defined by a stochastic transition matrix (i.e., each row sums up to 1). Generalization to higher and variable orders is discussed in Section 4.5.

A Markov process M is defined over a finite state space A = {a1, . . . , an}. A sequence s of length L is denoted by s = s1, . . . , sL with si ∈ A. S is the set of all sequences of length L generated by M with a non-zero probability:

Following [Pachet and Roy, 2011], we represent the sequence to generate as a sequence of finite-domain constrained variables {V1, . . . , VL}, each with domain A, and Markov properties as Markov constraints on these variables, defined below. Control constraints are also represented as finitedomain constraints. The induced CSP is denoted by P and the set of solutions SC. Given these notations, ˜M should verify:

• (I) p ˜M (s) = 0 for s /∈ SC,
• (II) p ˜M (s) = pM(s|s ∈ SC) otherwise.

These properties state that ˜M generates exactly the sequences s ∈ SC. Most importantly, sequences in SC have the same probabilities in M and ˜M up to a constant factor α = pM(s ∈ SC), i.e., ∀s ∈ SC, p ˜M (s) = 1/α · pM(s). In the running example, α = σ.

Our main result is that for a certain class of induced CSPs, hereafter referred to as Binary-Sequential CSPs(BSC), there exists a non-homogeneous Markov process ˜M that satisfies (I) and (II). We define the scope of a constraint as the interval between its leftmost and rightmost variables. A BinarySequential CSP is a CSP that contains only constraints whose scope remains within the scope of the Markov order. With a Markov order of 1, these constraints consist in 1) unary constraints and 2) binary constraints among adjacent variables (see Section 4.1).

A non-homogeneous Markov process (NHM) is a Markov process whose transition matrices change over time [Kolarov and Sinai, 2007]. A NHM of length L is defined as a series of transition matrices ˜M (i) , i = 0, . . . ,L-1.

We now describe how to build ˜M fromM and its induced BSC, and show that ˜M achieves the desired properties.

4 Construction of ˜M

˜M is obtained by applying two successive transformations to the initial model M. The first transformation exploits the induced CSP to filter out state transitions that are explicitly or implicitly forbidden by the constraints. This is achieved by replacing the corresponding transition probabilities by zeros in the initial transition matrices. A side-effect is that the transition matrices are not stochastic anymore (rows do not sum up to 1 any longer). The second transformation consists in renormalizing those matrices to obtain a proper (nonhomogeneous) Markov model, a step which turns out to be non trivial. We prove that this model satisfies (I) and (II).

4.1 Induced CSPs

We consider a BSC with unary control constraints U1, . . . , UL and binary constraints B1, . . . , BL-1. Ui defines the states that can be used at position i in the sequence. Bi defines the allowed state transitions between positions i and i + 1. Markov constraints, denoted by K1, . . . ,KL-1, are posted on all pairs of adjacent variables. Markov constraints represent the following relation:

The CSP induced by our running example is the following:

The first step of our process is to make P arc-consistent. Arc-consistency consists in propagating the constraints in the whole CSP, through a fixed-point algorithm that considers constraints individually [Bessi`ere et al., 1995]. This ensures that each constraint c holding on variables Vi and Vj satisfies:

General algorithms for achieving arc-consistency were proposed [Mackworth, 1977] but specific constraints can be filtered more efficiently [Bessi`ere et al., 1999]. Specific filtering methods for Markov constraints are described in the next section.

It is important to note here that enforcing arc-consistency on a BSC P is sufficient to allow the computation of the transition matrices once for all, prior to the generation, with no additional propagation. This can be shown as follows:

Proposition: If P is arc-consistent, then for all consistent partial sequences s1 . . . si (i.e., sequences that satisfy all the constraints between variables V1, . . . , Vi), the following properties hold:

Proof. P is of width 2 as its constraint network is a tree; [Freuder, 1982] proved that arc-consistency enables a backtrack-free resolution of a CSP of width 2, therefore every partial consistent sequence can be extended to a solution, which is equivalent to P1. The condition in P2 is obviously sufficient; it is also necessary as no constraint links Vi+1 back to any other variable than Vi.

P1 and P2 ensure that the domains of variables after arcconsistency contain exactly the valid prefixes and suffixes of the corresponding transitions. The next step is to extract the matrices from the domains, as described in Section 4.3.

4.2 Enforcing arc-consistency of P

Arc-consistency of the Markov constraints Ki can be achieved efficiently with the following propagators:

On instantiation: If Vi is instantiated with a ∈ A, remove every b ∈ A such that pM(b|a) = 0 from the domain of Vi+1. Conversely, if Vi+1 is instantiated with b ∈ A, remove all the a ∈ A such that pM(b|a) = 0 from the domain of Vi.

On removal: If a ∈ A is removed from the domain of Vi, remove all the b ∈ A such that pM(b|c) = 0, ∀c ̸= a from the domain of Vi+1. The same strategy is applied when a value is removed from the domain of Vi+1. This can be implemented efficiently by associating a support counter with each value in the domain of Vi+1.

Arc-consistency of binary control constraints can be implemented with a general binary arc-consistency algorithm or a specific one, depending on the nature of the constraint.

Arc-consistency of P necessitates enforcing arcconsistency of all constraints until a fixed-point is reached, i.e., no more values are removed.

In our example, arc-consistency removes D from the domain of V3 yielding the following domains:

Note that arc-consistency of Markov constraints as such solves the zero-frequency problem, regardless of control constraints: no choice made during the random walk can lead to a zero-frequency prefix.

In the case where arc-consistency detects the unsatisfiability of P, i.e., the solution space SC is empty, we can apply constraint relaxation techniques.

The next step is to extract the matrices from the domains.

4.3 Extraction of the Matrices

Recall that our goal is to generate a non-homogeneous Markov model, represented by a series of transition matrices. An intermediary series of L matrices Z (0) , . . . , Z (L-1) are obtained by zeroing, in the initial matrix, the elements that correspond to values or transitions that were removed during arc consistency. More precisely, the algorithm is:

• Inizialization: Z (0) ←M0 (the prior probabilities of M), Z (i) ← M, ∀i = 1, . . . , L - 1 (the transitions).
• For each ak ∈ A removed from the domain of Vi: Z (i) j,k ← 0, ∀j = 1, . . . , n (set the k-th column to zero).
• All forbidden transitions in the binary constraints should
• also be removed from the matrices: Z (i) j,k ← 0, ∀i, j, k such that Bi(aj , ak) = false.

The matrices obtained for our example are the following:

Modifying the initial matrix makes it non stochastic anymore. The next section describes how to renormalize the matrices to satisfy property (II).

4.4 Renormalization

We build the final transition matrices ˜M (i) of ˜M from the intermediary matrices Z (i) . Transition matrices could be renormalized individually, i.e., by dividing each row by its sum. This would indeed produce an non-homogeneous Markov model, but this model does not satisfy property (II) above, as it generates sequences with a different probability distribution than M.

For our example, the matrices after individual normalization are:

In this model, p ˜ Z (CCCD) = 1/6 and p ˜ Z (CDCD) = 1/16. The ratio between these 2 probabilities (16/6) is different from the original ratio (64/32=2).

The normalization process should indeed maintain the initial probability distribution. It turns out that a simple rightto-left process can precisely achieve that. The idea is to back propagate the perturbations in the matrices induced by individual normalization, starting from the right-most one.

To do this, we first normalize individually the last matrix Z (L-1) . We then propagate the normalization from right to left, up to the prior vector Z (0) . The elements of the matrices ˜M (i) and the prior vector ˜M (0) are given by the following recurrence relations:

By construction, when α(i) j = 0, the j-th columns of the preceding Z (i) contain only 0 as well. By convention, the division yields 0 since there is no normalization to back propagate. These coefficients can be computed in O(L × n2 ). We now show that this model satisfies the 2 desired properties.

Proposition: The ˜M (i) are stochastic matrices and the nonhomogeneous Markov process ˜M defined by the ˜M (i) matrices and the prior vector ˜M (i) satisfies (I) and (II).

Proof. The ˜M (i) matrices are stochastic by construction, i.e., each row sums up to 1. The probability of a sequence s = s1 . . . sL to be generated by ˜M is:

where ki is the index of si in A. Hence, by construction of Z (i) :

���

���

���

���

���

���

���

α(0) is precisely the probability for sequences in M of satisfying the control constraints, i.e., α(0) = pM(SC).

The final matrices for the running example are the following:

It is interesting to observe that even the addition of a simple unary constraint (here, last item = D) has an impact that propagates back to priors. In our example, p ˜M (C) is slightly increased (from .5 to .506), p ˜M (D) is decreased (from .1666 to .1558) and p ˜M (E) increased (from .333 to .337). Table 2 shows the ˜M probabilities of all sequences in SC. These probabilities are indeed equal to the initial probabilities, to the constant multiplicative factor α(0) .

4.5 Discussion

Our algorithm generates a model that satisfies the desired properties. Its complexity is low, as it involves only performing arc-consistency once on the induced CSP, and a renormalization in O(L×n2 ). This theoretical worst-case complexity is confirmed experimentally, see Figure 2 and Figure 3.

As shown in our example, renormalization may have a small impact on the transition matrices, although a difficult one to quantify precisely. In practice, it may be interesting to sacrifice accuracy and skip the renormalization step (i.e., use individual normalization): in that case, a larger class of constraints can be handled. A necessary and sufficient condition is that the induced CSP should be made backtrack-free, to ensure that any choice performed during the random walk leads to a sequence in SC. Property 2 of BSCs (see Section 4.1) is no longer true, so propagation is needed after each instantiation during the random walk to filter out values made incompatible with the current choice. Additionally, the algorithm is considerably simplified: transition matrices need not be constructed explicitly since their only use is to propagate the normalization. Instead, variable domains can be used directly to perform a random draw at each step of the random walk, with a prior individual normalization of the initial matrix M, i.e., arc-consistency does most of the job, which is to propagate the local effects of control constraints throughout the CSP.

As an illustration, let us consider our example in which the control constraint is changed to: "any three consecutive item should be different". This can be implemented by posting an AllDiff constraint [R´egin, 1994] on all consecutive triplets of variables. Such a constraint exceeds the Markov scope (order 1 here) so the induced CSP is not a BSC. However, we can make the induced CSP backtrack-free by applying pathconsistency (strong-3 consistency, see [Freuder, 1982]), with a complexity of O(n3 ). In our example, it turns out that the CSP is already path-consistent so no value is removed. SC now contains 6 sequences, whose probabilities are shown in Table 3. The probabilities are not equivalent to those in M but this approximation is the price to pay to get a random walk that satisfy those ternary constraints.

We have described our solution for fixed order-1 Markov models. Generalization to order d consists in 1) introducing order-d Markov constraints (this step is straightforward), and 2) applying the rest of the method to nd × n transition matrices (rows are d-grams and columns are the state) instead of the n × n transition matrices described here. In practice, most d-grams have no continuation, so sparse representations (graphs, oracles) are more appropriate than matrices.

In the case where proper normalization can be sacrificed, performing arc-consistency with an order-1 model allows to use variable-order random walk, provided the CSP is a BSC. This is achieved by adding to the basic order-1 procedure a phase consisting in removing higher order prefixes that contain a removed prefix of order 1. This is because all prefixes of length > 1 are also prefixes of length 1. This ensures that all solutions with longer prefixes will be found and only them. Contrarily to the approach of [Pachet and Roy, 2011] our approach scales-up well so composition applications can be envisaged. Once ˜M is built, the generation of a sequence does not require any computation other than a standard random walk algorithm whose complexity is a linear function of both the size of the alphabet n and the length of the sequence to generate L, i.e., O(L × n), as can be seen in Figure 2 and Figure 3 .

5 Applications

This method applies in general to style-imitation sequence generation requiring control constraints on individual items at arbitrary positions. A text generation application is currently developped, to generate text in the style of X, with additional constraints on rhymes, phrase structure and semantics. We describe below two musical applications.

5.1 RepresentingMusical Intentions

Unary constraints can be used to represent various musical intentions, when producing an melody from a Markov model M, and an input melody provided in real-time. For instance, we can define the following types of melodic output:

Continuation: input is continued to produce a sequence of the same size. A constraint is posted on the last note to ensure that it is "terminal", i.e., occurred at the end of an input melody, to produce a coherent ending.

Variation: is generated by adding two unary constraints that the first and last notes should be the same, respectively, as the first and last notes of the input.

Answer: is like a Continuation, but the last note should be the same as the first input note. This creates a phrase that resolves to the beginning, producing a sense of closure.

For all types, unary constraints are posted on each intermediary note that they should not be initial nor final, to avoid false starts/ends within the melody.

Figure 4 shows a melody, taken from [Davismoon and Eccles, 2010] from which we build a Markov model M. Figure 5 shows examples of continuations, variations and answers, built from M and the constraints corresponding to each melody type, from an input (I). It is clear that these melodies belong to the corresponding musical categories. Continuations end naturally, with the same 3 notes as the input (a consequence of the constraint on the last note); variations sound similar to the input; and answers sound as responses to the input. This shows how unary constraints can have a global effect on the structure of the generated melodies.

5.2 Generating VirtuosoMelodies

Our approach trivially extends to non-homogeneous Markov models (M). In practice, this enables a simple representation of non-constant harmonic contexts. In the case of melodies spanning different tonalities, each transition between two notes belongs to the model of the corresponding tonality. As an example, let us consider the melody extracted from an improvisation performed by jazz guitarist John McLaughlin during a famous concert [GuitarTrio, 1977]. This melody consists of 43 notes played on a sequence of three chords (see Figure 6). The 8 first notes belong to the harmonic context of Gmin7♭5, the 20 next to C7♭9, and the remaining 15 to F min.

Negotiating such chord transitions fast is precisely one of the most sought after skills of virtuoso jazz improvisers. Our technique can easily produce such melodies in real-time. To do so, we consider a training set made of typical jazz scales, as used in jazz training. As a simple example we consider the scales described in [Leavitt, 2005]: so-called "staircase" melodies, in all tonalities (for each key and each chord type). Figure 8 shows the staircase melody for C minor.

The sequence to generate can be seen as produced by a non-homogeneous Markov model, whose transition matrices change according the changes in tonality. To further illustrate our approach, we add three constraints stating that the first, middle, and last notes should be the ones played by John McLaughlin. Figure 7 shows one melody generated by the system. It can be observed that the melody is indeed 1) a concatenation of "staircase" chunks, 2) complies with the harmonic context, and 3) satisfies the three anchor constraints. Such melodies are generated in less than a millisecond.

This idea was used to implement an augmented instrument, called Virtuoso. With Virtuoso, the user plays bebop melodies by targeting specific notes ahead of time. These targets are selected using a gesture controller and transformed into unary constraints, e.g., on the last note. The underlying harmony is provided in real time by an mp3 file previously analyzed, from which timelined harmonic metadata is extracted. Videos are available online (www.youtube.com/watch?v=9f3caQNgxmI, /watch?v=GLUPcWT3tjc, /watch?v=LuvfWI7iMH4).

6 Conclusion

We propose a general solution to the issue of generating finite-length Markov chains with control constraints. The solution exploits the fruitful connection between Markov processes and constraint satisfaction, initiated in [Pachet and Roy, 2011] but in a randomwalk setting, i.e., without search. We have shown that for constraints that remain within the Markov scope, arc-consistency enables us to solve the zerofrequency problem, as well as to compile control constraints in the form of a non-homogeneous Markov model. This model can in turn be used straightforwardly with random walk to generate sequences that satisfy the constraints with their original probabilities.

More complex constraints can be handled provided they can be filtered to obtain backtrack-free CSPs, at the cost of inaccurate probabilities. The approach generates all the sequences satisfying the constraints with no search, so is suitable for real-time, interactive applications.

Acknowledgments

Research reported in this paper was partly funded by the EU project MIROR and carried out at the Sony Computer Science Laboratory in Paris. We thank Simon Colton and Michael Spranger for their thoughtful remarks and suggestions.