Transcript Markov Processes - Lyle School of Engineering

Matlab Simulations of
Markov Models
Yu Meng
Department of Computer Science and Engineering
Southern Methodist University
Outlines
Markov models
/process/chain/property/HMM
Matlab simulations
Applications
Advantages and Limitations
Conclusions.
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.
Markov Models
– A finite state representation
Markov Property
Many systems in real world have the
property that given present state, the
past states have no influence on the
future. This property is called Markov
property.
State Space and Time Space
State Space
Time Space
Discrete
Continuous
Discrete
(Markov
chain)
X
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 Markov property
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.
Hidden Markov Models (HMM)
In an hidden Markov Model(HMM), we don’t
know the state sequence. However we know
some probabilistic function of it.
In plain English, Markov model can be viewed
as a probabilistic finite state engine. The
state is changing over time. But we have no
way to determine the exact changes of the
state. We are able to observe some fuzzy
reflections of the change. Our objective is to
estimate the states of the machine via the
(possibly fuzzy) observations.
Markov Model example
The weather in Dallas of past 26 days
STATES = { pretty, pretty, pretty, pretty, pretty, pretty, pretty,
pretty, pretty, pretty, rainy, rainy, rainy, rainy, rainy, pretty,
pretty, pretty, pretty, pretty, pretty, pretty, pretty, pretty,
pretty, pretty }
Markov Model example
The weather in Dallas of past 26 days
STATES = { pretty, pretty, pretty, pretty, pretty, pretty, pretty,
pretty, pretty, pretty, rainy, rainy, rainy, rainy, rainy, pretty,
pretty, pretty, pretty, pretty, pretty, pretty, pretty, pretty,
pretty, pretty }
Tomorrow’s weather
Today’s
Weather
Pretty
Rainy
Pretty
0.95
0.05
Rainy
0.2
0.8
Markov Model example (2)
0.95
Pretty
0.2
0.05
Rainy
0.8
Markov Model example (2)
0.95
Pretty
0.2
0.05
Rainy
0.8
Markov Model example(3)
Hidden model.
Many time we don’t have a direct observation of the
change of the states. Therefore we say the model is
hidden. However we are still able to observe an emission
of the state changes, and the emission could be fuzzy.
For example, you are isolated in a closed room during the
experiment. In the room, you have no direct observation
of how weather changes. Everyday, an assistant delivers
meals for you once a day. The only way you have clue of
the weather is to observe the how the guy’s dress
changes.
Markov Model example(4)
In the room, you might observe that your
assistant dresses with regular coat (CT), rain
coat(RN), or brings an umbrella (UM). Your
observation sequence may be
SEQ = {CT, CT , CT , UM, CT , CT , CT , CT , CT , CT
, CT , RN , CT , RN , UM , CT , CT, CT, RN, CT, CT, CT
, CT, CT, CT , CT}
Markov Model example(5)
Regular Coat
Rain Coat
Umbrella
Pretty
5/6
1/12
1/12
Rainy
1/3
1/3
1/3
Markov Model example(5)
Regular Coat
Rain Coat
Umbrella
Pretty
5/6
1/12
1/12
Rainy
1/3
1/3
1/3
Mathematical Elements
A set of states over time, denoted by STATES
A set of emissions, or observations over time,
denoted by SEQ
An M-by-M transition matrix TRANS whose
entry(i,j) is the probability of a transition from
state i to state j.
An M-by-N emission matrix EMIS whose i,k
entry gives the probability of emitting symbol
sk given that the model is in state i. EMIS
Outlines
Markov models
/process/chain/property/HMM
Matlab simulations
Applications
Advantages and Limitations
Conclusions.
Why Matlab?
Matlab is a tool for doing numerical
computations with matrices and
vectors. It can also display information
graphically.
Combined with numerous mathematical
libraries, Matlab has become one of the
few tools that can catch up with my
ideas.
Why Matlab?
MATLAB Compiler translates MATLAB code to
ANSI standard C code. With the MATLAB
Compiler, we will be able to automatically
generate optimized C and C++ code. By
translating MATLAB code to C and C++, the
compiler can significantly speed up MATLAB
applications and development.
>>
mcc -t -L C myfun1 % yields myfun1.c
mcc -t -L C myfun2 % yields myfun2.c
mcc -W main -L C myfun1 myfun2 libmmfile.mlib
% yields myfun1_main.c
Matlab simulations
Matlab Statistics Toolbox 4.1
(Released in May 2003)
hmmdecode
hmmgenerate
hmmestimate
hmmtrain
hmmviterbi
Matlab simulations
Matlab scripts demo.m in Matlab
6.5 environment
Outlines
Markov models
/process/chain/property/HMM
Matlab simulations
Applications
Advantages and Limitations
Conclusions.
Applications of Markov Models
Speech recognition,
Modeling of coding/noncoding regions in
DNA,
Protein binding sites in DNA,
Protein folding,
Protein superfamilies,
Multiple sequence alignment,
Flood predictions,
Ion channel recordings,
Optical character recognition.
Outlines
Markov models
/process/chain/property/HMM
Matlab simulations
Applications
Advantages and Limitations
Conclusions.
Advantages of Markov Models
MMs and HMMs have proved effective in a number of
domains.
The basic theory of HMMs is very elegant and easy to
understand. This makes it easier to analyse and
implement, with the help of Matlab.
Because MM uses only positive data, their scalability
is very good. Dr. Dunham’s research group is
investigating an incremental extension algorithm of
Markov chain, which fits for dynamic data processing.
It is complementary of other non-linear models such
as neural networks and time-series analysis.
Limitations of Markov Models
It is a data hog.
Markov property.
Conclusions
http://www2.cs.cmu.edu/~awm/tutorials/
Any Questions?