If you pay peanuts, you get monkey.

Computation on HMM

Viterbi Algorithm

$\delta(t) = \max_{Z_{1:t-1}} P(Z_{1:t-1}, Z_t , x_{1:t})\\ \delta(t) = \max_{Z_{t-1} \in \mathbb Z}\left[\vec\delta(t-1) \times P(Z_t|Z_{t-1})\times P(x_t|Z_t)\right]$

Please compute this term using logrithm, will underflow otherwise.

Forward Backward

$\begin{aligned} \pi & = \pi(Z_1) = P(Z_1)\\ a(1) & = \pi, b(T) = \vec 1\\ a(t) & = P(x_{1:t}, Z_t) = P(x_t|Z_t)\sum_{Z_{t-1}}P(x_{1:t-1}, Z_{t-1})P(Z_t|Z_{t-1})\\ & = P(x_t|Z_t)\sum_{Z_{t-1}}a(t-1)P(Z_t|Z_{t-1})\\ b(t) & = P(x_{t+1: T}|Z_t) = \sum_{Z_{t+1}}[P(x_{t+2:T}|Z_{t+1})P(Z_{t+1}|Z_t)P(x_{t+1}|Z_{t+1})]\\ & = \sum_{Z_{t+1}} [b(t+1) P(Z_{t+1}|Z_t)]P(x_{t+1}|Z_{t+1}) \end{aligned}$

Scaled Forward

Perhaps using $P(Z_t|x_{1:t})$ rather than using $P(Z_t, x_{1:t})$ ?

We define $\bold {\hat a}(t) = P(Z_t|x_{1:t})$ . We just re-normalizes at each step.
$\begin{aligned} \sum_{Z_{t-1}} & P(Z_{t-1}|x_{1:{t-1}}) P(Z_{t}|Z_{t-1}) = P(Z_{t}|x_{1:{t-1}})\\ a'(t) & = P(Z_{t}|x_{1:t-1}) P(x_{t}|Z_{t}) = P(x_{t}, Z_{t}|x_{1:t-1})\\ c(t) & = \sum_{Z_{t}} P(x_{t}, Z_{t}|x_{1:t-1}) = P(x_{t}|x_{1:t-1})\\ \hat a(t) &= \frac{a'(t)}{c(t)} = P(Z_{t}|x_{1:t}) \end{aligned}$

$c(1) = P(x_1)\\ \prod_{t=s}^e c(t)= P(x_{s:e}|x_{1:s-1})$

Scaled Backward

Mostly for working with the scaled forward algorithm. Notice that the backward term was originally a conditional distribution, so not really necessary.

$\begin{aligned} \hat b(t) & = \frac{\sum_{Z_{t+1}}{\hat b(t + 1)}P(Z_t|Z_{t+1})P(x_{t+1}|Z_{t+1}) }{c(t+1)}\\ \end{aligned}$

Equalities in Scaled Forward-Backward

$\left [\prod_{\tau=1}^t c(\tau)\right ]\hat a(t) = P(x_{1:t}) P(Z_t|x_{1:t}) = P(Z_t, x_{1:t}) = a(t)\\ \hat a(t) \hat b(t) P(x) = a(t) b(t) = P(Z_t, x_{1:T})$

When you want to do a replacement for the product $a(t) b(t+1)$
$a(t)b(t+1)=\frac{P(x) \hat a(t) \hat b(t)}{c(t+1)}$

EM Algorithm

Notice that we are discussing only for MLE(Maximum Likelihood Estimation) of Parameters here. It is possible to use EM in Bayesian Estimation of Parameters.

Problem Formulation in General PGM(Probabilitistic Graphical Models)

Suppose we have a Bayesian Network $\mathcal N$ , which contains parameters $\Theta$ .

Suppose we start from some random parameter estimation $\Theta^0$ .

Suppose we have database $D = \left \{D_1, D_2, ..., D_n\right \}$ , where each $D_i = X$ gives a possibly partial assignment to all the variables in the network.

Assume all data are iid.

For some data sample $D_l$ , we denote the missing variable set to be $X_{l}$ . Denote one possible assignment to the missing variable to be $x_l$ .

Algorithm

The algorithm is iterative, suppose we are at step t of the algorithm.

Step One : Fixing up existing Data

Filling up the fractured dataset, the filled up sample is called a fractional sample(碎权样本). The filled up samples are given a possibility rather than a certainty.

We combine the filled up sample and the normal samples together to form the completed dataset $D^c$ . And the completed data points are denoted $D_l^c$

$D$

	$X_1$	$X_2$	$X_3$
$D_1$	1	1	1
$D_2$	1	2	2
$D_3$	1	?	1
$D_4$	2	?	2

$D_c$

	$X_1$	$X_2$	$X_3$	$P$
$D_1$	1	1	1	1
$D_2$	1	2	2	1
$D_{3, 1}$	1	1	1	4/5
$D_{3, 2}$	1	2	1	1/5
$D_{4, 1}$	2	1	2	1/5
$D_{4, 2}$	2	2	2	4/5

$P(X_2 = 1|D_3, \Theta^0) = \frac{4}{5}\\ P(X_2 = 2|D_3, \Theta^0) = \frac{1}{5}\\$

Step Two : Maximize Weighted Likelihood

We define the weighted (log) likelihood to be the following:
$Q(\Theta|\Theta^t) = \sum_{l=1}^m \sum _{x_l \in \mathcal X_l} P(X_l=x_l|D_l, \Theta^t) \log P(D_l,X_l = x_l|\Theta)$
This equation is also called the Expected LogLikelihood Function The weight is estimated using the last model parameter step.

The next step is to maximize this function for $\Theta^{t+1}$ .

Step Three : Evaluating Current Step*

Using VE requires recalculate likelihood again on the new parameters completely. Instead, we could another algorithm for efficient continuous evaluation.

Proving EM Algorithm

Monotonicity of the EM Algorithm is guaranteed:
$P(D |\Theta^t) \le P(D|\Theta^{t+1})$

Observe that:
$\sum_{X_l} P(X_l | D_l, \Theta) =1,\quad P(D_l|\Theta) = \frac{P(D_l, X_l|\Theta)}{P(X_l|D_l, \Theta)}\\$
Then we can do the following transformation:
$\begin{aligned} \log P( D|\Theta) & = &\sum_{l=1}^m \sum_{X_l} P(X_l | D_l, \Theta^t) \log \frac{P(D_l, X_l|\Theta)}{P(X_l|D_l, \Theta)}\\ & = &\sum_{l=1}^m \sum_{X_l} P(X_l | D_l, \Theta^t) \log P(D_l, X_l|\Theta)\\ & &+H(P(X_l|D_l,\Theta^t)||P(X_l|D_l,\Theta))\\ &= & Q(\Theta|\Theta^t) + H(P(X_l|D_l,\Theta^t)||P(X_l|D_l,\Theta)) \\ \end{aligned}$

Now this is a fairly interesting result.
$\log P(D|\Theta^t) = Q(\Theta^t|\Theta^t) + H_{t|t} = Q(\Theta^t|\Theta^t)\\ \log P(D|\Theta^{t+1}) = Q(\Theta^{t+1}|\Theta^t) + H_{t|t+1}$

Clearly $Q(\Theta^{t+1}|\Theta^t)$ is guaranteed to be larger than the original $Q$
Cross Entropy is guaranteed to be larger then corss entropy with self, which is 0.

Therefore, EM Algorithm is both converging and monotonic. Although it does not guarantee to converge to any of the global minimums. It might converge to some saddle point or local minimum.

In practice, we rerun the program multiple times and take the best result.

EM in GMM*

$P(x) = \sum_{k=1}^K \pi_k \mathcal N(x|\mu_k, \Sigma_k)$

We can introduce latent variables to GMM model, making it a latent graphical model:

$Z_k \in \left \{ 0, 1\right \}, \sum_{k}Z_k = 1\\ \begin{aligned} P(X) & = \sum_Z P(Z) P(X|Z)\\ & = \sum_Z (\prod_{k=1}^K \pi_k^{Z_k} \mathcal N(x|\mu_k, \Sigma_k)^{Z_k}) \end{aligned}$

$\begin{aligned} \gamma(i, k) & = P(Z_k = 1|x_i)\\ & = \frac{P(Z_k = 1) P(x_i|Z_k = 1)}{\sum_{j=1}^K P(Z_j = 1)P(x_i|Z_j = 1)}\\ & = \frac{\pi_k \mathcal N(x_i|\mu_k, \Sigma_k)}{\sum_j \pi_j \mathcal N(x_i|\mu_j, \Sigma_j)} \end{aligned}$

Then we maximize for the expected log likelihood:
$N_k = \sum_{n=1}^N \gamma(i, k), \pi_k = \frac{N_k}{N}\\ \mu_k = \frac{1}{N_k} \sum_{i=1}^N \gamma(i, k) x_i\\ \Sigma_k = \frac{1}{N_k} \sum_{i=1}^N \gamma(i, k) (x_i - \mu_k)(x_i - \mu_k)^T\\$

EM in Discrete HMM*

Single Instance Training with non Scaled Forward-Backward

$\psi(t) = P(x_{1:T}, Z_t, Z_{t+1}) = P(x_{1:t}, Z_t) \times P(x_{t+2:T}|Z_{t+1}) \times P(Z_{t+1}|Z_{t}) \times P(x_{t+1}|Z_{t+1})\\ \psi(t) = a(t) \times b(t+1) \times P(Z_{t+1}|Z_{t}) \times P(x_{t+1}|Z_{t+1})$

$\gamma(t) = P(x_{1:T}, Z_t) = \sum_{Z_{t+1}} \psi(t) =a(t) b(t)$

$\vec \pi = \gamma(1)\\ P'(z'_{t+1}|z'_{t}) = \frac{\sum_{t=1..T-1} \psi(t)(z'_{t+1}|z'_t)}{\sum_{t=1..T-1} \gamma(t)(z'_t)}\\ P'(x'_{t}|z'_{t}) = \frac{\sum_{t=1..T-1} 1(x_t= x'_t)\gamma(t)(z'_t)} {\sum_{t=1..T-1}\gamma(t)(z'_t)}$

Batched Training with non Scaled Forward-Backward

Clearly we need to extend the EM algorithm to multiple training samples. Notice that the training results are of variable lengths.

Extend the definition and equations above:

We first extend the notations for a single instance of forward and backward:

$a_n(t)$ Representing the forward result of $x^{(n)}$

$b_n(t)$ Representing the backward result of $x^{(n)}$
We introduce the probability of sequence $x^{(n)}$ under current model

$P(x^{(n)}) = P_n$
Then we extend the equations:
$\psi_n(t) = P(x^{(n)}_{1:T}, Z_t, Z_{t+1})= a_n(t) \times b_n(t+1) \times P(Z_{t+1}|Z_{t}) \times P(x^{(n)}_{t+1}|Z_{t+1})\\ \gamma_n(t) = P(x_{1:T}^{(n)}, Z_t) = \sum_{z_{t+1}} \psi_n(t) = a_n(t) b_n(t)\\$
Then the updating criterions with probability weighting
$\vec \pi = \frac{\sum_n \frac{1}{P_n} \gamma_n(1)}{\sum_n \frac{1}{P_n}}\\ P'(z'_{t+1}|z'_{t}) = \frac{\sum_n \frac{1}{P_n}\sum_{t=1}^{T_n-1} \psi_n(t)(z'_{t+1}|z'_t)}{\sum_n \frac{1}{P_n} \sum_{t=1}^{T_n-1} \gamma_n(t)(z'_t)}\\ P'(x'_{t}|z'_{t}) = \frac{\sum_n \frac{1}{P_n} \sum_{t=1}^{T_n-1} 1(x_t= x'_t)\gamma_n(t)(z'_t)}{\sum_n \frac{1}{P_n} \sum_{t=1}^{T_n-1}\gamma_n(t)(z'_t)}$
We will give the update of the not so probable result more weight
You can easily modify the equations using the scaled version.

Training HMM in ASR*

Training data is typically not aligned, audio and non-time-stamped text.

Feature Extraction and Forced Alignment

[图片上传失败...(image-4a6351-1544038499224)]

キ|ジ|ノ|ナ|ガ|サ|ワ|ジュ|ゴ|ヲ|コ|エ|テ|ワ|ナ|ラ|ナ|イ

Baum-Welch Training

Optimizing criterion of BW Training:
$\Theta = \mathop{\arg\max}_\Theta \sum_ZP(Z, X|\Theta)$

We set certain transitions in the transition matrix to 0, they will stay 0 during training.
- Restricting the structure of the path
- Set the rest possible values to identical ones at the beginning of training.
Initialize the mean and variance of gaussians to the corresponding distribution observed in training data.

image-20181205185829859-4007510.png

image-20181205182826102-4005706.png

Viterbi Training

Instead of summing over all possible paths, just take the single most likely path
Use the Viterbi Algorithm to compute this Viterbi Path
- This fills in the probability of the missing data determinstically.
Much faster than Baum-Welch

$\Theta = \mathop{\arg\max}_\Theta \max_ZP(Z, X|\Theta)$

It is possible to train using Gradient Descent. Perhaps it is less stable and slower. I haven't compared EM and Gradient Descent yet.

More Variance

Standard Training Process:
- Start with the monophone, do EM Training
- Clone Gaussians to form triphones
- Build Decision Tree to cluster Gaussians
- Clone and train mixtures
Increasing Complexity
- Single State
  - Single Gaussian
  - Multivariate Gaussian
  - Mixture of Multivariate Gaussian
- What is a state
  - Context Independent Phone
  - Context Independent SubPhone
  - Context Dependent Phone
  - State tied CDPhone
- Training Scheme
  - BW Training
  - Viterbi Training

image-20181205184306948-4006587.png

2018-12-06