EM Algorithm and Gaussian Mixture Models

EM Algorithm Introduction

• The Expectation-Maximization (EM) Algorithm is an iterative method for finding maximum likelihood or maximum a posteriori estimates of parameters in statistical models with unobserved latent variables.

EM Algorithm Use-Cases

• Clustering: Discovering clusters in data using models like Gaussian Mixture Models (GMM).
• Missing Data Imputation: Inferring missing data points within datasets.
• Latent Variable Models: Estimating parameters in Hidden Markov Models (HMM).

Gaussian Mixture Model (GMM) Definition

• GMM is a probabilistic model assuming data points are generated from a mixture of Gaussian distributions with unknown parameters.
• Parameters include mixture component probabilities ($\pi_k$), means ($\mu_k$), and covariance matrices ($\Sigma_k$).
• $\sum_{k=1}^{K} \pi_k = 1$, ensuring that the probabilities of the mixture components sum to one.

GMM Probability Density Function

• The probability density function for a GMM is: $p(x) = \sum_{k=1}^{K} \pi_k \mathcal{N}(x \mid \mu_k, \Sigma_k)$
• $\mathcal{N}(x \mid \mu_k, \Sigma_k)$ represents the Gaussian density: $\mathcal{N}(x \mid \mu_k, \Sigma_k) = \frac{1}{(2\pi)^{D/2} |\Sigma_k|^{1/2}} \exp\left(-\frac{1}{2}(x - \mu_k)^T \Sigma_k^{-1} (x - \mu_k)\right)$

Use of EM for GMM

• A latent variable $z_i$ indicates which Gaussian component generated data point $x_i$.
• The likelihood function is expressed as: $p(X \mid \pi, \mu, \Sigma) = \prod_{i=1}^{N} \sum_{k=1}^{K} \pi_k \mathcal{N}(x_i \mid \mu_k, \Sigma_k)$
• EM algorithm is used because directly maximizing the likelihood function is complicated.

EM Algorithm Steps

• Initialization: Initialize parameters $\pi_k, \mu_k, \Sigma_k$ randomly.
• E-step: Evaluate responsibilities given current parameters using $\gamma(z_{ik}) = p(z_i = k \mid x_i, \pi, \mu, \Sigma) = \frac{\pi_k \mathcal{N}(x_i \mid \mu_k, \Sigma_k)}{\sum_{j=1}^{K} \pi_j \mathcal{N}(x_i \mid \mu_j, \Sigma_j)}$
• M-step: Re-estimate parameters via:
  • $N_k = \sum_{i=1}^{N} \gamma(z_{ik})$
  • $\mu_k^{new} = \frac{1}{N_k} \sum_{i=1}^{N} \gamma(z_{ik}) x_i$
  • $\Sigma_k^{new} = \frac{1}{N_k} \sum_{i=1}^{N} \gamma(z_{ik}) (x_i - \mu_k^{new}) (x_i - \mu_k^{new})^T$
  • $\pi_k^{new} = \frac{N_k}{N}$
• Convergence Check: Evaluate log-likelihood and check for convergence. Reiterate E-step if not converged.

Derivation of M-step Description

• Log-likelihood of the complete data: $\log p(X, Z \mid \pi, \mu, \Sigma) = \sum_{i=1}^{N} \sum_{k=1}^{K} z_{ik} \left[ \log \pi_k + \log \mathcal{N}(x_i \mid \mu_k, \Sigma_k) \right]$
• E-step computes posterior probability via $\gamma(z_{ik}) = \mathbb{E}[z_{ik}] = p(z_i = k \mid x_i, \pi, \mu, \Sigma)$
• M-step maximizes expected log-likelihood: $\mathbb{E}[\log p(X, Z \mid \pi, \mu, \Sigma)] = \sum_{i=1}^{N} \sum_{k=1}^{K} \gamma(z_{ik}) \left[ \log \pi_k + \log \mathcal{N}(x_i \mid \mu_k, \Sigma_k) \right]$

EM Algorithm Convergence

• Converges monotonically to a local optimum of the likelihood function.
• Solution depends on initial parameter values.
• It is optimal to run EM multiple times with different initializations.

EM Algorithm Advantages

• Implementation is simple.
• Convergence to a local optimum is guaranteed.

EM Algorithm Disadvantages

• Slow convergence.
• Sensitive to initialization.
• Can get trapped in local optima.

EM Algorithm Extensions

• Variational Inference: Offers a lower bound on marginal likelihood, providing robustness against local optima.
• Online EM: A version of EM that handles data streams.

Overall Conclusion of EM Algorithm

• EM Algorithm supports parameter estimation in models with latent variables.
• Has widespread utility across clustering, missing data imputation, and latent variable models.
• Grasping EM is essential for machine learning and statistics.

Action Plan Based on Quality Management System (QMS)

• The overall goal is to enhance the efficiency and effectiveness of key organizational processes.
• It involves implementing and maintaining a Quality Management System (QMS) based on ISO 9001:2015.
• This aims for customer satisfaction and continuous improvement.

Specific Objectives

• Initial Assessment: An exhaustive assessment of current processes and the existing QMS.
• Detailed Design: A detailed plan identifying objectives, scope, resources, and timelines for QMS implementation.
• QMS Documentation: Recording processes, procedures, and work guidelines needed for the QMS.
• QMS Implementation: Deploying recorded systems and methods across the organization.
• Employee Training: Training staff on the ISO 9001:2015 standards and QMS processes.
• Internal Audits: Undertaking routine internal audits to check QMS compliance and pinpoint enhancement areas.
• Management Review: Performing management reviews to gauge QMS effectiveness and decide on updates.
• QMS Certification: Gaining QMS certification via an accredited certifying entity.

Roles and Responsibilities

• Consultant, leaders, teams, area managers, HR deparment, auditor, and executive manager must contribute.
• Budget allocations must be assigned for training, auditing, certification, software and tools
• Document management, computing facilities, office supplies, to be tracked for success

Monitoring Indicators

• Percentage of processes documented.
• Number of non-conformities identified in internal audits.
• Customer satisfaction rating.
• Number of corrective actions implemented.
• Average time until non-conformities are resolved.
• Adherence to the implementation schedule.

Goal of Hypothesis Testing

• Inference about a population derived from sample data.
• Examples are testing if the average height of a UM student is more than 5'8" and tests for whether movie A is better than movie B etc

Key Ingredients of Hypothesis testing

• Null Hypothesis ($H_0$).
• Alternative Hypothesis ($H_A$).
• Test Statistic.
• Significance Level ($\alpha$).
• P-value.

Null Hypothesis ($H_0$)

• A statement regarding a population parameter that is assumed true unless proven otherwise.
• Examples: "The average height of a UM student is 5'8" and the average rating of movie A is the same as B
• The null hypothesis can be rejected or cannot be rejected

Alternative Hypothesis ($H_A$)

• Statement contraindicating the null hypothesis.
• Examples: "The average height of a UM student is greater than 5'8" and the average rating of movie A is higher from movie B.

Test Statistic

• A value derived from sample data to decide about rejecting the null hypothesis.
• $z = \frac{\bar{x} - \mu}{\frac{\sigma}{\sqrt{n}}}$, where $\bar{x}$ is the sample mean, $\mu$ is the population mean, $\sigma$ is the standard deviation, and $n$ is the sample size.

Significance Level ($\alpha$)

• The probability of rejecting a true null hypothesis (Type I error), often set at $\alpha = 0.05$.
• $H_0$ is rejected when the p-value is less than $\alpha$.

P-value

• The probability of observing a test statistic as extreme or more extreme than that computed from the sample data, assuming the null hypothesis holds.

Type I Error

rejecting the null hypothesis when it should be accepted.

• Type II Error is accepting the null hypothesis when the alternative is true.

Gaussian Mixture Model Details

• Statistical model assuming data points are generated from a finite number of Gaussian distributions with unknown parameters.

• Each Gaussian component is defined by a mean ($\mu_k$) and covariance matrix ($\Sigma_k$).

• The number of Gaussian components is defined by $K$.

• Each has a mixing proportion, or probability of choosing the component, is defined by $\pi_k$

  • $0 \leq \pi_k \leq 1$
  • $\sum_{k=1}^{K} \pi_k = 1$

Learning GMM

• Given a dataset $X = {x_1, \dots, x_N}$, estimates GMM parameters $\theta = {\pi_1, \dots, \pi_K, \mu_1, \dots, \mu_K, \Sigma_1, \dots, \Sigma_K}$.

• Maximum Likelihood Estimation is a method used to estimate the parameters

  • Likelihood function: $p(X|\theta) = \prod_{n=1}^{N} p(x_n|\theta) = \prod_{n=1}^{N} \sum_{k=1}^{K} \pi_k \mathcal{N}(x_n|\mu_k, \Sigma_k)$
  • Log-likelihood function: $\log p(X|\theta) = \sum_{n=1}^{N} \log \sum_{k=1}^{K} \pi_k \mathcal{N}(x_n|\mu_k, \Sigma_k)$
  • No closed-form solution exists, so iterative optimization algorithms are needed.

EM Algorithm Application

The EM algorithm is used to iteratively find the maximum likelihood.

• The algorithm is general and can be used in many different cases.
• For each $x_n$ a latent variable of ,$z_n$ is created the component that generated it
  • Has a length $\textit{K}$
  • Value of 1 in the $k$th dimension if that element generated the $x_n$, and 0 otherwise
  • $p(z_{nk} = 1) = \pi_k$

What is complete data?

• complete data = observed data ($X$) and latent variables $Z = {z_1, \dots, z_N}$
• can be defined as: -$p(z_n|\pi) = \prod_{k=1}^{K} \pi_k^{z_{nk}}$ -$p(x_n|z_n, \mu, \Sigma) = \prod_{k=1}^{K} \mathcal{N}(x_n|\mu_k, \Sigma_k)^{z_{nk}}$

What is the goal?

Instead of directly maximizing the log-likelihood function, maximizing the expected log-likelihood function about the observed data and current param estimates.

EM Algorithm 3 Steps

• E - step: Evaluate the probabilities using the current estimates of the parameters
• M - step: Re-estimate with the output of the E-step!
• Loop to see if can converge, and do it again if not

Explore the Expectation-Maximization (EM) algorithm, an iterative method for parameter estimation in statistical models with latent variables. Learn about its applications, including clustering with Gaussian Mixture Models (GMM). Understand GMM's probabilistic model and probability density function.