The world is surrounded by random system example movement of dust particles on the water, one may try hard to arrive at a pattern but at the first go it looks probably impossible. Another example is stock market prices. Systems which generally have a high degree of randomness are defined as stochastic by nature.
Markov Model is stochastic model used to model randomly changing systems. It is assumed that future state depends on current state not on past events. This assumption enables reasoning and computation with the model that would otherwise be in intractable
Below are the different types of Markov Models
Markov chain simplest of all the models. This model the state of a system with a random variable that changes through time. In this context Markov's suggest the distribution of this variable depends only on the distribution of the previous state.
Ex use of Markov chain is Markov Chain Monte Carlo which uses Markov property to prove that a particular method for performing a random walk will sample from the joint distribution.
Hidden Markov
Hidden Markov is a Markov chain in which state is only partially observable. In other words, observations are related to state of a system but they are typically insufficient to determine the state of the system. Many algorithms for Hidden Markov exists
Markov Decision Process- state transition depends on the current state and an action vector that is applied to the system. The Markov decision process is used to compute a policy of action and will maximum some utility with respects to expected rewards. Closely related to Reinforcement learning.
Partially observable Markov Decision Process-
POMDP in which state of the system is only partially observable, also called NP Complete
Markov Random field
Markov Random field or Markov Network may be considered as a generalization of Markov chain in multiple dimensions, in a Markov chain state depends on the previous state where as in Markov random field each state depends on its neighbours in any of the multiple directions.
Hierarchical Markov Model
Can be applied to categorize human behaviour at various level of abstraction. For example, a series of observations such as a person location in a room can be interpreted to determine more complex information such as what task or activity a person is performing.2 kinds of Hierarchical Markov Model exist Hierarchical hidden Markov and Abstract Hidden Markov. Both of them are used for behaviour recognition.
Tolerant Markov Model
TLM is a probabilistic algorithmic Markov chain model. It assigns probabilities according to a conditioning context that considers the last symbol from the sequence to occur as the most probable instead of true occurring symbol. TMM can be of 3 different natures substitution, addition and deletions. Successful applications have been efficiently implemented in DNA sequences compression.
Markov Chain
As mentioned earlier Marko chain the state of a system with a random variable that changes through time. In this context Markov's suggest the distribution of this variable depends only on the distribution of the previous state.
DTMC (Discrete time Markov Chain)
DTMC is a sequence of random variables X1,X2, X3… Xn characterized by the Markov property(also known as memoryless property). The Markov property states that the distribution of the forthcoming states state Xn+1 depends on the current state Xn and doesn’t depend on previous ones Xn-1, Xn-2…, X1.
Pr(Xn+1 | X1= x1, X2=x2…. Xn = xn) = Pr (Xn+1 = xn+1 | Xn = xn)
The set of possible states S = { s1,s2,…sn } of Xn can be finite and countable and its named as state space of the chain.
The chain moves from one state on to another (this change is named either transition or step) and the probability pij to move from one state si to another sj in one step is named transition probability and is given as
Pij = Pr( X1=sj | X0= si)
The probability of moving from state i to j in n steps is denoted as
A DTMC is called time homogeneous if the property shown in below Equation holds, Time homogeneity implies no change in the underlying transition probabilities as time goes on.
Pr ( Xn+1 = sj | Xn = si) = Pr ( Xn = sj | Xn- 1 = si)
If the Markov chain is time homogeneous then pij = Pr(Xk+1 = sj | Xk = sj) and
Markov Model is stochastic model used to model randomly changing systems. It is assumed that future state depends on current state not on past events. This assumption enables reasoning and computation with the model that would otherwise be in intractable
Below are the different types of Markov Models
Markov chain simplest of all the models. This model the state of a system with a random variable that changes through time. In this context Markov's suggest the distribution of this variable depends only on the distribution of the previous state.
Ex use of Markov chain is Markov Chain Monte Carlo which uses Markov property to prove that a particular method for performing a random walk will sample from the joint distribution.
Hidden Markov
Hidden Markov is a Markov chain in which state is only partially observable. In other words, observations are related to state of a system but they are typically insufficient to determine the state of the system. Many algorithms for Hidden Markov exists
- Viterbi Algo this will compute the most likely corresponding sequence of states.
- Forward Algo will compute probability of the sequences of the observations.
- Baum-Welch Algo will estimate the starting probabilities, transition function and observable function.
Markov Decision Process- state transition depends on the current state and an action vector that is applied to the system. The Markov decision process is used to compute a policy of action and will maximum some utility with respects to expected rewards. Closely related to Reinforcement learning.
Partially observable Markov Decision Process-
POMDP in which state of the system is only partially observable, also called NP Complete
Markov Random field
Markov Random field or Markov Network may be considered as a generalization of Markov chain in multiple dimensions, in a Markov chain state depends on the previous state where as in Markov random field each state depends on its neighbours in any of the multiple directions.
Hierarchical Markov Model
Can be applied to categorize human behaviour at various level of abstraction. For example, a series of observations such as a person location in a room can be interpreted to determine more complex information such as what task or activity a person is performing.2 kinds of Hierarchical Markov Model exist Hierarchical hidden Markov and Abstract Hidden Markov. Both of them are used for behaviour recognition.
Tolerant Markov Model
TLM is a probabilistic algorithmic Markov chain model. It assigns probabilities according to a conditioning context that considers the last symbol from the sequence to occur as the most probable instead of true occurring symbol. TMM can be of 3 different natures substitution, addition and deletions. Successful applications have been efficiently implemented in DNA sequences compression.
Markov Chain
As mentioned earlier Marko chain the state of a system with a random variable that changes through time. In this context Markov's suggest the distribution of this variable depends only on the distribution of the previous state.
DTMC (Discrete time Markov Chain)
DTMC is a sequence of random variables X1,X2, X3… Xn characterized by the Markov property(also known as memoryless property). The Markov property states that the distribution of the forthcoming states state Xn+1 depends on the current state Xn and doesn’t depend on previous ones Xn-1, Xn-2…, X1.
Pr(Xn+1 | X1= x1, X2=x2…. Xn = xn) = Pr (Xn+1 = xn+1 | Xn = xn)
The set of possible states S = { s1,s2,…sn } of Xn can be finite and countable and its named as state space of the chain.
The chain moves from one state on to another (this change is named either transition or step) and the probability pij to move from one state si to another sj in one step is named transition probability and is given as
Pij = Pr( X1=sj | X0= si)
The probability of moving from state i to j in n steps is denoted as
A DTMC is called time homogeneous if the property shown in below Equation holds, Time homogeneity implies no change in the underlying transition probabilities as time goes on.
Pr ( Xn+1 = sj | Xn = si) = Pr ( Xn = sj | Xn- 1 = si)
If the Markov chain is time homogeneous then pij = Pr(Xk+1 = sj | Xk = sj) and
