CMPM147

Generative Design

Markov Models

Lucas N. Ferreira

University of California, Santa Cruz

Summer 19

UC Santa Cruz

Announcements

Last lecture we talked about:

• Genetic Algorithms
• Representation (genotype vs phenotype)
• Fitness Functions
• Reproduction
• Mutation

​

Upcoming deadlines:

• Assignment 4: Due this Saturday

​

UC Santa Cruz

2

Markov Models

Markov Models

In probability theory, a Markov model is a stochastic model used to model randomly changing systems.

​

They can be applied to generate sequences of events that follow a given learned probability distribution.

​

UC Santa Cruz

4

Brief History

Markov models are named after the Russian mathematician Andrey Markov.��Markov studied such processes in the early 20th century, publishing his first paper on the topic in 1906

Markov Models

In probability theory, a Markov model is a statistical model used to model randomly changing systems.

​

There are four common markov models:

• Markov Chains
• Hidden Markov Model
• Markov Decision Process
• Partially Observable Markov Decision Process

​

​

​

UC Santa Cruz

6

Markov Chains

A Markov Chain is a statistical model of a system that moves sequentially from one state to another. It is defined by:

​

• A discrete set S = {s₁, s₂, … s_n} of states.

​

• A conditional probability distribution P(s_t|s_t-1 )

describing the probability of changing from

state s_t-1 to a state s_t.

​

​

​

​

S₁

S₂

P(s₂|s₁ )

P(s₁|s₂ )

P(s₂|s_s )

P(s₁|s₁)

UC Santa Cruz

7

Markov Chains

For example, one can define a Markov chain of a baby's behavior (random variable) as follows:

​

States

S = { Playing (P), eating (E), sleeping (S) and crying (C) }.

​

Probability Distribution

​

​

​

​

​

​

UC Santa Cruz

8

Creating Markov Chains from Data

One can create a Markov Chain from a dataset of sequential data as follows:

​

1. Create a state for each event in the dataset (include a state for <start> and <end>).
2. For each event s_t, calculate the probability of s_t appear after another event s_t+1.

​

This process is called training.

​

​

​

​

​

UC Santa Cruz

9

Sampling from a Markov Chain to Generate Content

After training a markov chain, one can sample events from it's probability distribution to generate content:

​

1. Starting from the <start> event.
2. Generate a random event considering the probability of P (<start>| t).
3. Repeat until you generate <end>

​

This process is called sampling.

​

​

​

UC Santa Cruz

10

Example: Name Generator

One can train a Markov Chain from a dataset of names (sequential data) to generate new random names:

​

Training

• Create a dataset of common (e.g. Hobbit names) names

​

<start>Frodo<end>

<start>Samwise<end>

<start>Bilbo<end>

​

​

​

​

​

​

​

UC Santa Cruz

11

Example: Name Generator

One can train a Markov Chain from a dataset of names (sequential data) to generate new random names:

​

Training

2. Create a state for each character in the dataset (include a state for <start> and <end>).

​

​

​

​

​

​

​

UC Santa Cruz

12

Example: Name Generator

One can train a Markov Chain from a dataset of names (sequential data) to generate new random names:

​

Training

3. For each char s_t, calculate the probability P(s_t|s_t-1) of s_t-1 appear before another char s_t-1.

​

​

​

​

​

​

​

UC Santa Cruz

13

Example: Algorithmic Music Composition

The same idea can applied to generate monophonic music.

​

Training

• Create a dataset of symbolic music (e.g. MIDI).

​

​

​

​

​

​

​

​

[C, quarter], [E, quarter], [F, quarter], [E, 8th], [D, 8th], [C, 8th], [C, quarter], [D, quarter], [C, 8th], [A, 8th], [C, quarter]

UC Santa Cruz

14

Example: Algorithmic Music Composition

The same idea can applied to generate monophonic music.

​

Training

2. Create a state for each pair [note, duration] in the dataset

(include a state for <start> and <end>).

​

​

​

​

​

​

UC Santa Cruz

15

Example: Algorithmic Music Composition

The same idea can applied to generate monophonic music.

​

Training

3. For each state s, calculate the probability of s appear after another state y_.

​

​

​

​

​

​

UC Santa Cruz

16

Example: Algorithmic Music Composition

To model polyphonic music we can divide the pieces in timesteps (e.g. 16th notes) and create a state that represents end-of-timestep.

​

Every note in the same timestep is played simultaneously.

​

​

​

​

​

​

[C, quarter], [D, 8th], [E, 8th], <ts>, <ts>, <ts>, [C, quarter], <ts>, <ts>, <ts>, <ts>, [E, quarter], <ts>, <ts>, <ts>, <ts>, ...

UC Santa Cruz

17

High Order Markov Chain

Markov chains restrict the probability distribution to only depend on the previous state.

​

Higher-order Markov Chains relax this condition by

allowing the probability distribution P(s_t|s_t-1,...,s_t-d )

to include d previous states.

​

​

​

​

​

S_1,1

S_2,2

P(s_2,2|s_1,1, s_1,2,s_2,1 )

S_1,2

S_2,1

UC Santa Cruz

18

Example: Linear Level Generators

One can train a High Order Markov Chain from a dataset of linear levels (sequential data) to generate new random levels:

​

Training

• Create a dataset of common (e.g. Super Mario Bros 1-1) levels.

​

​

​

​

​

UC Santa Cruz

19

Example: Linear Level Generators

One can train a High Order Markov Chain from a dataset of linear levels (sequential data) to generate new random levels:

​

Training

2. Define a level representation:

A level can be represented as a WxH two-dimensional array m, where each cell m[x][y] takes a value from a finite set of tiles T.

​

​

​

​

​

UC Santa Cruz

20

Example: Linear Level Generators

One can train a High Order Markov Chain from a dataset of linear levels (sequential data) to generate new random levels:

​

Training

3. Create a state for each tile in the dataset (include a state for <start> and <end>).

​

​

​

​

UC Santa Cruz

21

Example: Linear Level Generators

​

One can train a High Order Markov Chain from a dataset of linear levels (sequential data) to generate new random levels:

​

Training

4. Calculate the probability P(s_x,y|s_{x-1, y}, s_{x, y-1}) of a tile s_x,y to be after a tile s_{x-1, y} and above the tile s_{x, y-1}

​

​

​

​

UC Santa Cruz

22

Sampling

One can train a High Order Markov Chain from a dataset of linear levels (sequential data) to generate new random levels:

​

Sampling

1. Starting from the bottom left corner of the level.
2. Sample tiles vertically until you reach a tile <E>.

​

​

​

​

​

​

​

​

UC Santa Cruz

23

How Much Training Data is Required?

In general, data-driven approaches (including Markov Chains) require a "large" amount of examples to learn a representative probability distribution.

​

The amount of data you need depends both on the complexity of your problem and on the complexity of your chosen algorithm.

​

​

​

​

​

​

​

​

​

​

UC Santa Cruz

24

References

Markov Chains

• Markov Chains Explained Visually

Applications

• Procedural Name Generator with Markov Chains
• Algorithmic Music Composition with Markov Chains

UC Santa Cruz

25