Markov Chains Flashcards
What is a Markov chain?
Probabilistic model of sequences. A 1st order Markov process
What can a Markov chain be thought of? What does this mean?
Generative model- A model of how sequences of objects can be produced in a random or probabilistic fashion.
What is an nth order Markov process?
A probability distribution over sequences. The objects in the sequence belong to a state space. The probability of st being generated at time t is only determined by the n values before it in the sequence.
p(st | st-1, st-2,….s1) = p(st | st-1, st-2, …, st-n)
What is a zeroth order Markov process?
A random sequence of objects
What is a homoogeneous Markov process?
Transition probabilities remain fixed over time
Given a directed graph, how do we calculate p(s)
p(s) = p(s1)p(s2 | s1)p(s3|s2)…p(STOP)
What is a normalisation condition in a Markov chain model?
Arrows leaving each state sum to one.
sum for all st of p(st | st-1) = 1
What is a transition matrix?
Transition probabilities written in a table. All numbers in each row sum to one.
What do we gain from unfolding in time?
Display of all the possible sequences of a fixed length T and their associated probabilities. Transition probabilities leaving each state do not sum to one because it doesn’t represent all possible sequences.
How can we write the sum over all possible sequences between s1 = n and sT+1 = STOP?
sum of all s_ns between 2 and T in S p(s1 = n and s2 and s3 … and sT)
= sum of all ….. in S p(s1 = n)p(s2 | s1 = n)p(s3 | s2)…p(STOP | sT)
How many operations when calculating unfolding in time?
(T-2)|S|^2
Write a recursion relation to demonstrate unfolding in time
base case:
p(s2 and s1 = n) = p(s2 | s1 = n)p(s1 = n)
step case:
p(sT+1 and s1 = n) = sum of all sT in S p(sT+1 | sT)p(sT and s1 = n) for 2 <= t <= T
How do we estimate transition probabilities for a Markov chain model?
Fit a Markov chain model to training data.
The simplest approach is to use frequency counts from the sequences in the training data. Set the transition probabilities to be proportional to these counts
How can a higher order Markov process be mapped onto a 1st order process
Using an extended alphabet. E.g. a second order model with state space S = {a,b} is equivalent to a 1st order model with state space S = {aa, ab, ba, bb}
What is a triphone Markov model?
A 3rd order phoneme Markov process mapped onto a 1st order process with an extended state space.
