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 "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.

$$ \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$.


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

  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.

  • $\begingroup$ Oh, I think i should've put one more line for someone who's not familiar with the Forward Algorithm. Alphat(j)=P(o1,o2,...,oT-1,oT,qt=j|Lambda). Sorry that I don't know how to type mathematical symbols. $\endgroup$ Jun 17 '19 at 0:18
  • $\begingroup$ @JeeyoungJeon The forward algorithm (FA) is used in context of HMMs, so all the assumptions that are made in the context of HMMs also hold in the context of FA. $\endgroup$
    – nbro
    Jun 17 '19 at 0:21
  • $\begingroup$ I edited my former comment, but I think I've found the answer from you already. Thanks! $\endgroup$ Jun 17 '19 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.