Machine Learning Review Notes

Pattern Recognition and Machine Learning (PRML) focuses on traditional machine learning algorithms and their probabilistic interpretations.

Clustering

K-means (Hard Clustering)

$J = \sum_{n=1}^N \sum_{k=1}^K r_{n k} \|\| x_n - \mu_k \|\|^2$, where $r_{n k} \in \{0, 1\}$, $\sum_{k=1}^K r_{n k} = 1$

$\mu_k = \frac{\sum_{n=1}^N r_{n k} x_n}{\sum_{n=1}^N r_{n k}}$

Probabilistic Clustering (Soft Clustering)

The connction between GMM and K-means

We can consider a GMM with $\Sigma_k = \varepsilon I$. The distribution will be

We see $\varepsilon$ as a constant, then for a specific data point, the responsibility will be

If we consider $\ \varepsilon \to 0$, then the responsibility will be

$\gamma(z_{n k}) \to r_{n k}\$ which is the same as K-means.

The generalization of EM algorithm

Consider a probabilistic model where:

• Observed variable: $X$
• Latent variable: $Z$
• Model parameters: $\theta$

The goal is to maximize the likelihood function:

We can decompose the log-likelihood function as:

where:

• $q(Z)$ is the distribution over the latent variables.
• Lower bound:

• KL divergence:

Since KL divergence satisfies: $\ \mathcal{D}_{KL}(q || p) \geq 0\$, it implies that: $\ \mathcal{L}(q, \theta)\$ serves as a lower bound for $\ \ln p(X | \theta)\$.

Based on the above observations, the EM algorithm consists of two steps:

1. E-step:

   • Keep $\ \theta\$ fixed.
   • Maximize $\ \mathcal{L}(q, \theta)\$ by minimizing $\ \mathcal{D}_{KL}(q || p)\$.
   • At maximum $\ \mathcal{D}_{KL}(q || p) = 0\$, which implies: $\ q(Z) = p(Z | X, \theta^{\text{old}})\$.

2. M-step:

   • Maximize the lower bound $\mathcal{L}(q, \theta)$ with respect to $\theta$.
   • Since $\ \mathcal{D}_{KL}(q || p) \geq 0\$, any increase in $\mathcal{L}$ ensures that $\ \ln p(X | \theta)\$ also increases.

Practical Reformulation

From the E-step, we use:

and derive:

Let:

The remaining term is a constant (information entropy), so the M-step effectively maximizes $\ \mathcal{Q}(\theta, \theta^{\text{old}})$.

• The EM algorithm alternates between estimating the latent variable distribution ($q(Z)$) and maximizing the lower bound with respect to parameters ($\theta$).
• The KL divergence guarantees that each iteration increases the likelihood $\ p(X | \theta)$.
• The reformulated objective function simplifies computations by focusing on the expected complete-data log-likelihood ($\mathcal{Q}$).

Hidden Markov Matrix

• Transmission Probabilities: $\ p(z_n = k | z_{n-1} = j) = A_{jk}\$
  • Initial state probabilities: $\ p(z_1 = k) = \pi_k$
• Emission Probabilities: $\ p(x_n | z_n, \phi) = \prod_{k=1}^K p(x_n | \phi_k)^{z_{nk}}\$
  • Example with Gaussian emissions: $\ p(x_n | z_n, \phi) = \prod_{k=1}^K \mathcal{N}(x_n | \mu_k, \Sigma_k)^{z_{nk}}\$
• Joint Probability of Observations and Hidden States: $\ p(\{x_N\}, \{z_N\}) = p(z_1) \left[ \prod_{n=2}^{N} p(z_n | z_{n-1}) \right] \prod_{n=1}^{N} p(x_n | z_n, \phi)\$
  • Thus, the parameters controlling the model can be represented as: $\ \theta = \{\pi, A, \phi\}\$

Three Key Problems for HMMs

1. Learning (Parameter Estimation):

   • Goal: What is the most likely HMM model ($\theta$) for a given observation sequence $\ \\\{x_1, \dots, x_N\\\}\$?
   • Solution: Use the Expectation-Maximization (EM) strategy.

2. Evaluation (Likelihood Computation):

   • Goal: Given an HMM model $\ \theta = \\\{\pi, A, \phi\\\}\$, what is the likelihood of the observation sequence $\ \\\{x_1, \dots, x_N\\\}\$ generated by this model?
   • Solution: Use the Forward-Backward Algorithm to efficiently compute probabilities.

3. Decoding (Hidden State Inference):

   • Goal: Given an HMM model $\ \theta = \\\{\pi, A, \phi\\\}\$, what is the most likely sequence of latent states $\ \\\{z_1, \dots, z_N\\\}\$ for an observation sequence $\ \\\{x_1, \dots, x_N\\\}\$?
   • Solution: Use the Viterbi Algorithm to determine the most probable hidden state path.

Expectation-Maximization (EM) for HMMs

Forward-Backward Algorithm

• Forward Algorithm:
  • Initialization: $\ \alpha_1(z_1) = p(x_1 | z_1, \phi) p(z_1 | \pi)\$
  • Recursion: $\ \alpha_{n+1}(z_{n+1}) = p(x_{n+1} | z_{n+1}, \phi) \sum_{z_n} \alpha_n(z_n) p(z_{n+1} | z_n, A)\$
  • Termination: $\ p(x | \theta) = \sum_{z_N} \alpha_N(z_N)\$
• Backward Algorithm:
  • Initialization: $\ \beta_N(z_N) = 1\$
  • Recursion: $\ \beta_n(z_n) = \sum_{z_{n+1}} p(x_{n+1} | z_{n+1}, \phi) p(z_{n+1} | z_n, A) \beta_{n+1}(z_{n+1})\$
  • Termination: $\ p(x | \theta) = \sum_{z_1} \pi(z_1) p(x_1 | z_1, \phi) \beta_1(z_1)\$