Note: This equation sheet will be provided alongside the midterm exam. Outside copies of this or any other aids are not permitted.
Discrete HMMs
For a discrete HMM with K discrete classes, the transition probability is fully described by the probability of transitioning from state k to k':
\begin{align*} p(z_{t+1,k'} = 1|z_{t,k} = 1) &= A_{k,k'} \\ 0 \leq A_{k,k'} &\leq 1 \\ \sum_{k'=1}^K A_{k,k'} &= 1 \end{align*}
The initial latent node \mathbf{z}_0 has a prior that is fully determined by a vector of probabilities \boldsymbol{\pi}:
p(\mathbf{z}_0) = \prod_{k=1}^K \left(\pi_k \right)^{z_{0,k}}.
The renormalized alpha and beta are:
\begin{align*} \hat{\alpha}(\mathbf{z}_t) &= p(\mathbf{z}_t|\mathbf{x}_{1:t}) = \frac{\alpha(\mathbf{z}_t)}{p(\mathbf{x}_{1:t})} \\ \hat{\beta}(\mathbf{z}_t) &= \frac{p(\mathbf{x}_{t+1:T}|\mathbf{z}_t)}{p(\mathbf{x}_{t+1:T}|\mathbf{x}_{1:t})} \\ c_t &= p(\mathbf{x}_t|\mathbf{x}_{1:t-1}) \end{align*}
The recursion equations are:
\begin{align*} c_t \hat{\alpha}(\mathbf{z}_t) &= p(\mathbf{x}_t | \mathbf{z}_t) \sum_{\mathbf{z}_{t-1}} \hat{\alpha}(\mathbf{z}_{t-1}) p(\mathbf{z}_{t}|\mathbf{z}_{t-1}) \\ c_{t+1} \hat{\beta}(\mathbf{z}_t) &= \sum_{\mathbf{z}_{t+1}} \hat{\beta}(\mathbf{z}_{t+1}) p(\mathbf{x}_{t+1}|\mathbf{z}_{t+1}) p(\mathbf{z}_{t+1}|\mathbf{z}_{t}) \end{align*}
Algorithms
Expectation-Maximization
Input: Initial estimate for the parameters \boldsymbol{\theta}_0.
For n=1 to N_\text{iter}: - q_n = \underset{q}{\text{argmin}} \ \mathrm{KL}(q(\mathbf{Z}) || p(\mathbf{Z}|\mathbf{X},\boldsymbol{\theta}_{n-1})) (E step) - \boldsymbol{\theta}_n = \underset{\boldsymbol{\theta}}{\text{argmax}} \ \mathcal{L}(q_n, \boldsymbol{\theta}) (M step)
Output: Parameter estimate \boldsymbol{\theta}_{N_\text{iter}}.
Particle Filtering
Input: N initial latent samples \mathbf{z}_{0,i} from the prior p(\mathbf{z}_0) and uniform weights w_{0,i}.
For t=1 to T+k: - For i=1 to N_\text{samps}: - \mathbf{z}'_{t-1,i} = \mathbf{z}_{t-1,j} with prob w_{t-1,j} (\mathbf{z}'_{t-1,i} follow p(\mathbf{z}_{t-1} | \mathbf{x}_{1:t-1})) - \mathbf{z}_{t,i} = g(\mathbf{z}'_{t-1,i}) (\mathbf{z}_{t,i} follow p(\mathbf{z}_{t} | \mathbf{x}_{1:t-1})) - For i=1 to N: - If t \leq T: - $ w_{t,i} = $ - Else: - $ w_{t,i} = $
Output: Samples \mathbf{z}_{t,i} and weights w_{t,i}.