13.6 Inference on the Hidden States \(Z\)

There are several ways to find the optimal hidden state sequence \(Z\) given an observation sequence \(\mathbf{x}\), depending on the definition of optimality.

One criterion is to choose the hidden states \(Z_t\)s that are individually most likely at the time point \(t\), that is \[\hat{Z}_t^* = \arg \max_i P(Z_t=i | \mathbf{x}, \hat{\theta}) = \arg \max_i \gamma_t(i)\]

Here we can plug in \(\hat{\theta}\) from the aforementioned EM algorithm and simply get the argmax. Such a solution is optimal in the sense that it maximizes the expected number of correct states (by choosing the most likely state for each \(t\)). However, the resulting sequence may not be the most likely one and it may not even be a valid sequence.

For example, if \(Z\) has three states (instead of 2), and the transition probability \(A(1, 3) = 0\) (impossible to transit from 1 to 3), but it is still possible to have \[\hat{Z}_t^* = 1\,\, \text{ and } \,\, \hat{Z}_{t+1}^* = 3\]

An alternative approach is to find the most likely single sequence, i.e., \[\hat{\mathbf{Z}}^* = \arg \max_{z_{1:n}} P(\mathbf{Z}=\mathbf{z}|\mathbf{x}, \hat{\theta})\]

Note that maximizing this is the same as maximizing \[P(\mathbf{Z} = \mathbf{z}, \mathbf{x} | \hat{\theta}) \text{ w.r.t. } z_{1:n}\]

Solving this with brute force will cost \(m_z^n\) tries, which is almost impossible. Hence, we need some sophisticated algorithm. A dynamic programming method called the Viterbi algorithm was proposed for this.

Define a maximizing sequence \(z_{1:t}\) up to time \(t\), which ends with \(z_t = i\). The associated probability is \[\mu_t(i) = \max_{z_{1:(t-1)}} P \Bigl(\mathbf{Z}_{1:(t-1)} = \mathbf{z}_{1:(t-1)}, Z_t = i, \mathbf{x}_{1:t} | \hat{\theta} \Bigr)\]

which is the highest probability along a single path from 1 to \(t\) that ends up at state \(Z_t = i\), given the observed sequence and the parameter estimation. Realizing that (with \(\hat{\theta}\) omitted) \[\begin{align*} &\mu_{t+1}(i) \\ &= \max_{z_{1:t}} P( z_{1:t}, Z_{t+1} = i, x_{1:(t+1)} | \hat{\theta})\\ &= \max_{z_{1:t}}\Bigl\{ P( z_{1:(t-1)}, Z_{t} = z_t, \mathbf{x}_{1:t} | \hat{\theta}) P(Z_{t+1}|Z_t, \hat{\theta}) P(x_{t+1}|z_{t+1}, \hat{\theta}) \Bigr\}\\ &= \Bigl\{ \max_j \mu_t(j) A(j,i) \Bigr\} B(i, x_{t+1}). \end{align*}\]

To recover the sequence we also store the maximizing predecessor \[\psi_{t+1}(i) = \arg\max_j \bigl\{\mu_t(j) A(j,i)\bigr\}.\] At time \(n\) set \(\hat{Z}_n = \arg\max_i \mu_n(i)\), then trace backward \(\hat{Z}_t = \psi_{t+1}(\hat{Z}_{t+1})\). This is the Viterbi path.