Markov model


Markov model

In probability theory, a Markov model is a stochastic model that assumes the Markov property. Generally, this assumption enables reasoning and computation with the model that would otherwise be intractable.

Contents

Introduction

The most common Markov models and their relationships are summarized in the following table:

Markov models
System state is fully observable System state is partially observable
System is autonomous Markov chain hidden Markov model
System is controlled Markov decision process partially observable Markov decision process

Markov chain

The simplest Markov model is the Markov chain. It models the state of a system with a random variable that changes through time. In this context, the Markov property suggests that the distribution for this variable depends only on the distribution of the previous state. An example use of a Markov chain is Markov Chain Monte Carlo, which uses the Markov property to prove that a particular method for performing a random walk will sample from the joint distribution of a system.

Hidden Markov model

A hidden Markov model is a Markov chain for which the state is only partially observable. In other words, observations are related to the state of the system, but they are typically insufficient to precisely determine the state. Several well-known algorithms for hidden Markov models exist. For example, given a sequence of observations, the Viterbi algorithm will compute the most-likely corresponding sequence of states, the forward algorithm will compute the probability of the sequence of observations, and the Baum–Welch algorithm will estimate the starting probabilities, the transition function, and the observation function of a hidden Markov model. One common use of hidden Markov models is for voice recognition.

Markov decision process

A Markov decision process is a Markov chain in which state transitions depend on the current state and an action vector that is applied to the system. Typically, a Markov decision process is used to compute a policy of actions that will maximize some utility with respect to expected rewards. It is closely related to Reinforcement learning, and can be solved with value iteration and related methods.

Partially observable Markov decision process

A partially observable Markov decision process (POMDP) is a Markov decision process in which the state of the system is only partially observed. POMDPs are known to be NP complete, but recent approximation techniques have made them useful for a variety of applications, such as controlling simple agents or robots.

Markov random field

A Markov random field (also called a Markov network) may be considered to be a generalization of a Markov chain in multiple dimensions. In a Markov chain, state depends only on the previous state in time, whereas in a Markov random field, each state depends on its neighbors in any of multiple directions. A Markov random field may be visualized as a field or graph of random variables, where the distribution of each random variable depends on the neighboring variables with which it is connected. More specifically, the joint distribution for any random variable in the graph can be computed as the product of the "clique potentials" of all the cliques in the graph that contain that random variable. Modeling a problem as a Markov random field is useful because it implies that the joint distributions at each vertex in the graph may be computed in this manner.

See also


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Markov model — [ mα:kɒf] (also Markov chain) noun Statistics a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Origin named after the Russian… …   English new terms dictionary

  • Hidden Markov model — Probabilistic parameters of a hidden Markov model (example) x mdash; states y mdash; possible observations a mdash; state transition probabilities b mdash; output probabilitiesA hidden Markov model (HMM) is a statistical model in which the system …   Wikipedia

  • Variable-order Markov model — Variable order Markov (VOM) models are an important class of models that extend the well known Markov chain models. In contrast to the Markov chain models, where each random variable in a sequence with a Markov property depends on a fixed number… …   Wikipedia

  • Hierarchical hidden Markov model — The Hierarchical hidden Markov model (HHMM) is a statistical model derived from the hidden Markov model (HMM). In an HHMM each state is considered to be a self contained probabilistic model. More precisely each stateof the HHMM is itself an HHMM …   Wikipedia

  • Hidden semi-Markov model — A hidden semi Markov model (HSMM) is a statistical model with the same structure as a hidden Markov model except that the unobservable process is semi Markov rather than Markov. This means that the probability of there being a change in the… …   Wikipedia

  • Hidden Markov model — Das Hidden Markov Model (HMM) ist ein stochastisches Modell, das sich durch zwei Zufallsprozesse beschreiben lässt. Ein Hidden Markov Model ist auch die einfachste Form eines dynamischen Bayesschen Netz. Der erste Zufallsprozess entspricht dabei… …   Deutsch Wikipedia

  • Layered hidden Markov model — The layered hidden Markov model (LHMM) is a statistical model derived from the hidden Markov model (HMM). A layered hidden Markov model (LHMM) consists of N levels of HMMs, where the HMMs on level i + 1 correspond to observation symbols or… …   Wikipedia

  • Hidden Markov Model — Das Hidden Markov Model (HMM) ist ein stochastisches Modell, das sich durch zwei Zufallsprozesse beschreiben lässt. Es ist die einfachste Form eines dynamischen Bayes schen Netzes. Der erste Zufallsprozess entspricht dabei einer Markov Kette, die …   Deutsch Wikipedia

  • Maximum-entropy Markov model — MEMM redirects here. For the German Nordic combined skier, see Silvio Memm. In machine learning, a maximum entropy Markov model (MEMM), or conditional Markov model (CMM), is a graphical model for sequence labeling that combines features of hidden …   Wikipedia

  • Markov perfect equilibrium — A solution concept in game theory Relationships Subset of Subgame perfect equilibrium Significance Proposed by …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.