Answers.Body: <p>In general, to formally state that the Markov property holds, you need to have <span class="math-container">$P(
  x_t \mid x_{t-1:1}) = P(x_t \mid x_{t-1})$</span>.</p>
  
  <p>So, you cannot conclude <em>only</em> from <span class="math-container">$P(q_{t-1} = i, q_t=j, o_1^{t-1}, o^t|\lambda)$</span> that the Markov property holds, because  <span class="math-container">$P(q_{t-1} = i, q_t=j, o_1^{t-1}, o^t|\lambda)$</span> is the <strong>joint</strong> probability of <span class="math-container">$q_{t-1} = i, q_t=j, o_1^{t-1}$</span> and <span class="math-container">$o^t$</span> <em>given</em> <span class="math-container">$\lambda$</span>.</p>
  
  <p>Nonetheless, the theory of <a href="http://jedlik.phy.bme.hu/~gerjanos/HMM/node5.html" rel="nofollow noreferrer">hidden Markov model often assumes that a few properties (including the Markov property) hold</a></p>
  
  <ol>
  <li><p>the Markov property: <span class="math-container">$$P(q_{t+1} \mid q_{t}) = P(q_{t+1} \mid q_{t:1}),$$</span> where <span class="math-container">$q_t$</span> is the hidden state at time step <span class="math-container">$t$</span> and <span class="math-container">$q_{t:1} = q_t, q_{t-1}, \dots, q_1$</span>.</p></li>
  <li><p>the stationarity property: <span class="math-container">$$P(q_{t_1 + 1} \mid q_{t_1}) = P(q_{t_2 + 1} \mid q_{t_2}),$$</span> for any time step <span class="math-container">$t_1$</span> and <span class="math-container">$t_2$</span>. In other words, the <em>state transition probabilities are independent of the actual time at which the transitions takes place</em>.</p></li>
  <li><p>the output independence property: <span class="math-container">$$P(o^{T:1} \mid q_{T:1}) = \prod_{t=1}^T P(o^t \mid q_t , \lambda)$$</span>
  where <span class="math-container">$o^{T:1} = o^T, o^{T-1}, \dots, o^1$</span>. In other words, this is the assumption that the output at time step <span class="math-container">$t$</span>, <span class="math-container">$o^t$</span>, is independent of the outputs at previous time steps.</p></li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-16T13:39:49.683Z
Answers.LastActivityDate: 2019-06-16T13:39:49.683Z
Answers.UserDisplayName: nbro
Body: <p>I'm majoring in pure linguistics (not computational), and I don't have any basic knowledge regarding computational science or mathematics. But I happen to take the &quot;Automatic Speech Recognition&quot; course in my graduate school and struggling with it.</p>
  <p>I have a question regarding getting the formula for a component of the <a href="https://en.wikipedia.org/wiki/Forward_algorithm" rel="nofollow noreferrer">forward algorithm</a>.</p>
  <p><span class="math-container">$$
  \alpha_t(j) = \sum_{i=1}^{N} P(q_{t-1} = i, q_t=j, o_1^{t-1}, o^t|\lambda)
  $$</span></p>
  <p>When <span class="math-container">$q$</span> is a hidden state, <span class="math-container">$o$</span> is a given observation, and <span class="math-container">$\lambda$</span> contains transition probability, emission probability and the start/end state.</p>
  <p>Is the Markov assumption (the current state is only dependent upon the one right before it) assumed here? I thought so, because it contains <span class="math-container">$q_{t-1}=i$</span> and not <span class="math-container">$q_{t-2}=k$</span> or <span class="math-container">$q_{t-3}=l$</span>.</p>
  
Tags: <machine-learning><markov-property><hidden-markov-model>
Title: Is the Markov property assumed in the forward algorithm?
UserDisplayName: Jeeyoung Jeon
ThreadText: # Is the Markov property assumed in the forward algorithm?
  
  (Asked by: username_0 on 2019-06-16)
  
  I'm majoring in pure linguistics (not computational), and I don't have any basic knowledge regarding computational science or mathematics. But I happen to take the "Automatic Speech Recognition" course in my graduate school and struggling with it.
  
  I have a question regarding getting the formula for a component of the [forward algorithm](https://en.wikipedia.org/wiki/Forward_algorithm).
  
  $$
  \alpha\_t(j) = \sum\_{i=1}^{N} P(q\_{t-1} = i, q\_t=j, o\_1^{t-1}, o^t|\lambda)
  $$
  
  When $q$ is a hidden state, $o$ is a given observation, and $\lambda$ contains transition probability, emission probability and the start/end state.
  
  Is the Markov assumption (the current state is only dependent upon the one right before it) assumed here? I thought so, because it contains $q\_{t-1}=i$ and not $q\_{t-2}=k$ or $q\_{t-3}=l$.
  
  **Tags:** machine-learning, markov-property, hidden-markov-model
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-06-16. Score: 0 | Accepted answer
  
  In general, to formally state that the Markov property holds, you need to have $P(
  x\_t \mid x\_{t-1:1}) = P(x\_t \mid x\_{t-1})$.
  
  So, you cannot conclude *only* from $P(q\_{t-1} = i, q\_t=j, o\_1^{t-1}, o^t|\lambda)$ that the Markov property holds, because $P(q\_{t-1} = i, q\_t=j, o\_1^{t-1}, o^t|\lambda)$ is the **joint** probability of $q\_{t-1} = i, q\_t=j, o\_1^{t-1}$ and $o^t$ *given* $\lambda$.
  
  Nonetheless, the theory of [hidden Markov model often assumes that a few properties (including the Markov property) hold](http://jedlik.phy.bme.hu/~gerjanos/HMM/node5.html)
  
  1. the Markov property: $$P(q\_{t+1} \mid q\_{t}) = P(q\_{t+1} \mid q\_{t:1}),$$ where $q\_t$ is the hidden state at time step $t$ and $q\_{t:1} = q\_t, q\_{t-1}, \dots, q\_1$.
  2. the stationarity property: $$P(q\_{t\_1 + 1} \mid q\_{t\_1}) = P(q\_{t\_2 + 1} \mid q\_{t\_2}),$$ for any time step $t\_1$ and $t\_2$. In other words, the *state transition probabilities are independent of the actual time at which the transitions takes place*.
  3. the output independence property: $$P(o^{T:1} \mid q\_{T:1}) = \prod\_{t=1}^T P(o^t \mid q\_t , \lambda)$$
     where $o^{T:1} = o^T, o^{T-1}, \dots, o^1$. In other words, this is the assumption that the output at time step $t$, $o^t$, is independent of the outputs at previous time steps.
  
  
  ---
  
  