{"id":735,"date":"2019-01-09T06:09:06","date_gmt":"2019-01-09T06:09:06","guid":{"rendered":"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=735"},"modified":"2019-01-09T08:14:35","modified_gmt":"2019-01-09T08:14:35","slug":"markov-and-hidden-markov-models","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/chapter\/markov-and-hidden-markov-models\/","title":{"rendered":"Markov and Hidden Markov Models"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n\r\n
\r\n\r\n \r\n\r\nLearning Objectives:<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of this module are as follows:\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To understand the concept of Markov Chain\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To explain Markov Chain with an example\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To understand the concept of Hidden Markov Model\r\n\r\n \r\n\r\n34.1 Markov Random Processes<\/strong>\r\n\r\n \r\n

Until now, we have considered data to be i.i.d (independent and Identically distributed). Now we study sequential data such as time-series like stock market, speech, video analysis and ordered like text, genes, etc. If underlying process is unknown we can construct a model to predict the next state in sequence. In general, product rule expresses joint distribution for sequence<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n

First-order Markov chain is described as each observation being independent of all previous observations except the most recent.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\nIn this case the Maximum Likelihood parameter estimates are easy.\r\n\r\n \r\n

Now we define the Markovprocessas 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. A random sequence has the Markov property if its distribution is determined solely by its current state. Any random process having this property is called a Markov random process.For observable state sequences (state is known from data), this leads to a Markov chain model.For non-observable states, this leads to a Hidden Markov Model (HMM).<\/p>\r\n \r\n\r\n34.1.1 Markov Model<\/strong>\r\n\r\n \r\n\r\nA discrete (finite) system can be described as consisting of:\r\n\r\n \r\n\r\n\u2013\u00a0 N distinct states.\r\n\r\n\u2013\u00a0 Begins (at time t=1) in some initial state(s).\r\n

\u2013 At each time step (t=1,2,\u2026) the system moves from current to next state (possibly the same as the current state) according to transition probabilities associated with current state.<\/p>\r\n \r\n

This kind of system is called a fi nite, or discrete Markov model. The model has been named after Andrei Andreyevich Markov (1856 -1922).<\/p>\r\n \r\n\r\n34.1.2 Markov Property<\/strong>\r\n\r\n \r\n\r\nNow let us discuss a very important property that is known as the Markov property<\/span>.<\/strong>\r\n\r\n \r\n

Markov Property: <\/strong>The state of the system at time <\/span>t<\/em>+1 depends only on the state of the system at time <\/span>t.<\/em> This property allows us to assume that the state at time <\/span>t<\/em>+1is independent of the states at all times before t (Figure 34.1). This is a simplifying assumption that allows us to compute the states of many sequential problems.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Figure 34.1 Markov Property<\/strong><\/p>\r\n \r\n

Stationary Assumption: <\/strong>In general, a process is called stationary if transition probabilities are independent of t, namely (Figure 34.2)<\/p>\r\n\"\"\r\n

Figure 34.2 Stationary Property<\/strong><\/p>\r\n \r\n

This means that if system is in state i, the probability thatthe system will next move to state j is pij , no matter whatthe value of t is.<\/p>\r\n \r\n\r\n34.2 Components of the Markov Model<\/strong>\r\n\r\n \r\n

Markov model is a stochastic processes holding the Markov property. The Markov property is also called as memoryless property.This is because the future is independent of past given present. One step transition probability is the basis.We need the following three basic information to define a Markov model which is essentially a state space model:<\/p>\r\n\r\n