Algorithms for inference

Definitions

Chordal graph: a graph is chordal if any cycle of the graph of size >= 4 has a chord.

Formulas

Parameter estimation for HMM with Gaussian distribution for emission probabilities:

$$\underline{\mu}_s^t = \frac{\sum_{i=1}^n\sum_{j=1}^mp(S_j = s|\underline{x}_{i,1}\dots\underline{x}_{i,m};\theta)\underline{x}_{i,j}}{\sum_{i=1}^n\sum_{j=1}^mp(S_j = s|\underline{x}_{i,1}\dots\underline{x}_{i,m};\theta)}$$

General form of EM algorithm

The basic idea is that we want to maximize the likelihood of the "complete" data. Because we don't know the "complete" data, we need to take the expectation of the "complete" data with respect to the probability distribution of the hidden variables.

Let \(\mathbf{Z}\) denote all the hidden variables for all the examples, and let \(\boldsymbol{\theta}\) be all the parameters for the probability model. \begin{aligned}\boldsymbol{\theta}^{(i+1)} &= \underset{\boldsymbol{\theta}}{\arg\max}\sum_{\boldsymbol{z}}P(\boldsymbol{Z} = \boldsymbol{z}|\boldsymbol{x}, \boldsymbol{\theta}^{(i)})L(\boldsymbol{x}, \boldsymbol{Z} = \boldsymbol{z}|\boldsymbol{\theta}) \\ &=\underset{\boldsymbol{\theta}}{\arg\max}E_{P(\boldsymbol{Z} = \boldsymbol{z}|\boldsymbol{x}, \boldsymbol{\theta}^{(i)})}L(\boldsymbol{x}, \boldsymbol{Z}= \boldsymbol{z}|\boldsymbol{\theta}) \end{aligned}
The E-step is the computation of the summation, which is the expectation of the log likelihood of the "completed" data with respect to the distribution \(P(\boldsymbol{Z} = \boldsymbol{z}|\boldsymbol{x}, \boldsymbol{\theta}^{(i)})\).