1
$\begingroup$

I am tryign to understand HMM based on this paper: A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition but I find it difficult to actually understand one of its basic elements. The reason for that is, I assume, I probably haven't fully understood advance probability. Having said that, I do know about things like conditional probability, joint distribution, independence etc.

The paper explaines HMM can be chcracteriased by five elements. What I think I have understood is explained below:

  • a set of states $S=\{s_1, s_2, ..., s_N\}$, that we assume the system can be in.
  • a set of distinct symbols we observe, that is $V=\{v_1, v_2, ... , v_M\}$, where $M$ is a number of symbols; I understand the number of possible symbols is the same in each state but independent to number of states and in different states we may observe the same symbols
  • the transition matrix $\textbf{A}=\{a_{ij}\}$ is defined as a probability that system changes from one state to another, from $s_i$ to $s_j$; $a_{ij}=P(Q_{t+1}=s_j|Q_t=s_i)$
  • The initial state distribution $\boldsymbol{\pi}=\pi_i$, where $\pi_i=P(Q_1=s_i)$, where $i=\{1, 2, ..., N\}$
    This took me some time but I assume that we need to know about the probability that system may start from a particular state.
  • "The observation symbol probability distribution in state $j$", $\textbf{B}=\{b_j(k)\}$, where

\begin{aligned} b_j(k)&=P(R_t=v_k|Q_t=s_j) \\ &\qquad j\in\{1, ..., N\} \\ &\qquad k\in\{1, ..., M\} \end{aligned}

where $R_t$ is the observation at time $t$. In the paper $q_t$ denotes a state that system currently is in at time $t$.

I am confused by the last point. I don't know exactly what $\textbf{B}$ is. It says probability distribution. My understanding is that probability distribution could be normal, gaussian, mixter of gaussians, binomial, multinomial, even constant etc. But how this corresponds to what what $\textbf{B}$ is. Is $\textbf{B}$ vector? Does it mean that symbol $3$ would most likely occur than the others? Does it change from state to state or is it constant characteristic of HMM?

I would appreciate any help and example if it's possible.

Thanks.


EDIT:

I would like to extend the example from the paper.

Let's say we have a couple of urns (1,2,3, .... N) from left to right, balls in different colours (1, 2, up to M) distributed over urns. Genie picks the balls but hides the process of how the balls are being picked but we can observe which balls have been picked. Let's say Genie likes to start from certain urns (left side) and tends to move to right side, and then to middle, then to left again etc. Let's say there is uneven proportion of balls distributed over urns, such that from a certain urn it is more likely to pick a certain ball, like red.

In HMM (I apologise if I have used too simplified terminology):

  • initial distribution $\boldsymbol{\pi}$ explains that the Genie would prefer to start from left side; (s)he would rather pick one of the left urns (1,2, or 3 etc.) over the others
  • transition probability distribution explains that, with next choice, Genie prefers to move to the right (N-3, N-2, N-1, or N), then to the middle, and then to the left again
  • observation probability distribution $\textbf{B}$ explains which ball $v_k$ is very likely to be chosen when urn has been picked (state $s_j$) because of different proportion of balls in different urns.

Summarizing, if we have more red balls in left(ish) urns, more green balls in right(ish) urns, and blue distributed over middle part, providing my conditions, we would expect that if we see red, green, blue, and then probably red again, Genie started from left side, moved to right, to the middle and again to the left. I don't know if I am correct. I hope I am :). Cheers.

$\endgroup$
2
$\begingroup$

Celdor,

Given how accurate most of what you said was, it's not clear exactly where you're misunderstanding the last element, so I'm going to try and cover a lot of ground. I think the easiest context to first learn HMM is where your state space, $S$, and observation space, $V$, are discrete and finite as you have stated in your problem. In that case there are three probability distributions of interest (or if you prefer to look at it another way, there are $N + N + 1$ distributions of interest. You can think of all of them as Multinomial Distribution because their event spaces are all finite.

Note: I have made a lot of edits to your question namely changing all of the random variables to capital letters, and the values they can take to lower case letters. An example that I want you to think of is sentences in English. The states are the "parts of speech" ($S = \{$noun, verb, article, $\cdots$, $\}$). The observations are actual words $V = \{$ the, fence, swim, $\dots \}$. We have two sequences of random variables,

\begin{eqnarray} &Q_1& \rightarrow &Q_2& \rightarrow &Q_3& \rightarrow \cdots \\ &\downarrow& &\downarrow& &\downarrow& \\ &R_1& &R_2& &R_3& \end{eqnarray}

  • The simplest of these is the starting distribution. What is the chance that we start the process in state $s_i$? In our example, what is the chance that we start with an adverb? (low) What is the chance that we start with an article? (high). Put into normal notation this is, $$ \pi_i = P(Q_1 = s_i). $$ These values can be stored in a vector $\pi = (\pi_0, \dots, \pi_N)$, whose non-negative coordinates sum to 1.

  • Now let's focus on the distribution(s) that is giving you trouble. Given I am in state $s_i$, what is the probability that I observe $v_k$? For example, if we've determined that $Q_1 =$ "article", the chances the first word is "The" is probably very high. The chances the first word is "slowly" is zero because "slowly" isn't an article. So for each possible value of $Q_t$ we have a different distribution over $R_T$. This is a conditional distribution $$ B_{k,j} = P(R_t = v_k | Q_t = s_i). $$ These values can be stored in a matrix $B$. Each column represents a different possible value for $Q_T$, and the value in the $k^{th}$ row of the column is the probability of observing $v_k$ in that state. So this matrix is $M \times N$, and the columns will each sum to 1, because they each represent a probability distribution.

  • Lastly, there are state transitions. Once again this is a conditional distribution. Given that I am in state $s_i$, what is the probability that my next state will be $s_j$. For example, the chance that you transition from verb to adverb is high, but from article to adverb is very low. So for each $Q_t$ we have a different distribution over $Q_{t+1}$. Formally, $$ A_{j,i} = P(Q_{t+1} = s_j|Q_t = s_i). $$ Again, these values can be stored in a matrix $A$. Each column represents a different possible value for $Q_T$, and the value in the $j^{th}$ row of the column is the probability of transitioning to state $s_j$ from that state. So this matrix is $N \times N$, and the columns will each sum to 1, because they each represent a probability distribution.

If any of these don't make sense let me know. I may not have added much but hopefully I cleaned it up a bit and added something with my concrete examples.

Edit: Example Fleshed Out

So as a generative model for sentence construction, we are assuming sentences are constructed as follows. We have $2N + 1$ dice, $\pi$, $a_i$, $b_i$ for $i$ in $\{1, \dots, N \}$. We do the following.

1) Roll the $\pi$ die to determine what the first part-of-speech will be. It lands on $3$, so $$Q_1 = s_3 = \text{"article".}$$ 2) Roll the $b_3$ die to determine what the first word will be. It lands on $97$, so $$R_1 = v_{97} = \text{"The".}$$ 3) Roll the $a_3$ die to determine what the second part-of-speech will be. It lands on $5$, so $$Q_2 = s_5 = \text{"adjective".}$$ 4) Roll the $b_5$ die to determine what the second word will be. It lands on $1935$ so, $$R_2 = v_{1935} = \text{"quick".}$$

$\endgroup$
  • $\begingroup$ It's definitely clearer and I think I have got the idea now. It's a really good answer and serves me like an appendix to the paper :p. To put everything together I have tried to make my own example based on one in the paper. It's just to re-think through what I have read and see if I'm still OK :) I have edited question to add an example and my explanation of it :) $\endgroup$ – Celdor Oct 1 '15 at 13:38
  • $\begingroup$ "it's not clear exactly where you're misunderstanding the last element". I really missed the probability distributions in transfer and symbol probability distribution. The example with speech was very good to clarify this. $\endgroup$ – Celdor Oct 1 '15 at 14:32
  • $\begingroup$ @Celdor Great! Perhaps you'd like to upvote and/or accept the answer. I am going to add one last statement summing up the example. $\endgroup$ – jlimahaverford Oct 1 '15 at 14:39
  • $\begingroup$ Sorry. I was meant to do it after reading but I think I was too excited I actually managed to understand so much at such hard topic :p $\endgroup$ – Celdor Oct 1 '15 at 15:01

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.