Transcript Markov Processes - Lyle School of Engineering

Markov Models and Simulations
Yu Meng
Department of Computer Science and Engineering
Southern Methodist University
Outline
• Markov model/process/chain/property/HMM
• Matlab simulations
Markov Process/chain/model/etc.
•
•
•
•
•
Markov Process
Markov Model
Markov Chain
Markov Property
Hidden Markov Model
Markov Process
• Markov process is a simple stochastic
process in which the distribution of future
states depends only on the present state and
not on how it arrived in the present state.
Simple example-Graphic
representation
Markov Property
• Many systems have the property that given
present state, the past states have no
influence on the future. This property is
called Markov property.
• We can say Markov process is a process or
simulation that satisfies Markov property.
State Space and Time Space
Time Space
State Space
-----------------------Discrete Continuous
----------------------------------------Discrete
(Markov
X
Chain)
Continuous
X
X
Markov Chain
Let {Xt : t is in T} be a stochastic process with
discrete-state space S and discrete-time space
T satisfying
P(Xn+1 = j|Xn = i, Xn-1 = in-1, · · ·,X0 = i0)
= P(Xn+1 = j|Xn = i)
for any set of state i0, i1, · · · , in-1, i, j in S and
n ≥ 0 is called a Markov Chain.
Markov Model
• Sometimes Markov Model restricts
attention to Markov chains with stationary
transition probabilities. But some people
tend to avoid this usage for sake of
confusion.
• Markov Model is also used to refer to all
Markov processes that satisfying Markov
Property.
Hidden Markov Model(HMM)
• In an Hidden Markov Model(HMM), we
don’t know the state sequence that the
model passes through, but only some
probabilistic function of it.
Elements of Hidden Markov Model
• A set of states {1, 2, ..., M}
• An M-by-M transition matrix T whose i, j entry
is the probability of a transition from state i to
state j.
• A set of possible outputs, or emissions, {s1,
s2, ... , sN}.
• An M-by-N emission matrix E whose i,k entry
gives the probability of emitting symbol sk
given that the model is in state i.
HMM Example
• A weighted red coin.The probability of heads
is .9 and the probability of tails is .1.
• A weighted green coin. The probability of
heads is .95 and the probability of tails is .05.
• A red die, having 6 sides, labeled 1 to 6.
• A green die, having 12 sides, 5 of which are
labeled 2 through 6, and the remaining 7
sides are labeled 1.
HMM Example
• Begin to toss the red die, write down the
number. At each step, you flip the coin
that has the same color as the die you
rolled in the previous step. If the coin
comes up heads, roll the same die as in
the previous step. If the coin comes up
tails, switch to the other die.
HMM Example
Matlab simulations
Matlab Statistics Toolbox 4.1
(Released in May 2003)
• hmmdecode
• hmmgenerate
• hmmestimate
• hmmtrain
• hmmviterbi
Matlab simulations
Conclusions
• http://www-2.cs.cmu.edu/~awm/tutorials/