Machine Learning (B.
Tech CSE 6th Semester)
Unit – 6.0
✳ Expectation Maximization (EM) Algorithm
🔹 Introduction
The Expectation Maximization (EM) algorithm is an iterative method to find maximum
likelihood estimates (MLE) of parameters when the data is incomplete or has missing
values.
It’s widely used for:
Clustering (e.g., GMM)
Hidden Markov Models
Missing data estimation
🔹 Working Principle
EM works in two alternating steps:
1. E-step (Expectation):
Estimate missing or hidden variables using current parameter values.
Q(θ∣θ(t)) = EZ∣X,θ(t) [log P (X, Z∣θ)]
2. M-step (Maximization):
Maximize the expected log-likelihood to get new parameter estimates.
θ(t+1) = arg maxθ Q(θ∣θ(t))
Repeat until convergence.
🔹 Example
Suppose we have a dataset with two Gaussian clusters but no labels.
We estimate parameters:
Θ = {π1, π2, μ1, μ2, σ1, σ2}
E-Step: Compute probability that a data point belongs to each cluster:
πkN (xi∣μk, σk)
γ =
i,k 2
∑j=1 π j N (x i ∣μ j , σj)
M-Step: Update parameters using these responsibilities.
✅ Solved Problem
Given: Two clusters (initial μ₁=2, μ₂=8), σ=1, π₁=π₂=0.5, and data X={2,3,8,9}
Goal: One EM iteration.
Step 1 (E-Step):
Compute probability that each point belongs to each cluster.
For x=2:
P (C1∣x) ≈ 1, P (C2∣x) ≈ 0
For x=8:
P (C1∣x) ≈ 0, P (C2∣x) ≈ 1
Step 2 (M-Step):
Update means:
∑ γi1xi ∑ γi2xi
μ1 = ≈ 2.5, μ2 = ≈ 8.5
∑ γi1 ∑ γi2
➡ Parameters move toward actual cluster centers.
🔹 Summary
EM is used for parameter estimation in latent variable models.
Alternates between Expectation (hidden variable inference) and Maximization
(parameter update).
Converges to local maxima of likelihood.
🎯 Gaussian Mixture Models (GMM)
🔹 Introduction
A Gaussian Mixture Model assumes data is generated from multiple Gaussian
distributions with unknown parameters.
P (x) = ∑ πkN (x∣μk, Σk)
k=1
where
πk: mixing coefficient (sum to 1)
μk, Σk: mean and covariance of Gaussian k
🔹 Steps to Learn a GMM
We use EM algorithm to estimate parameters.
1. Initialize parameters randomly.
2. E-Step: Compute responsibilities (posterior probabilities).
3. M-Step: Update parameters based on responsibilities.
4. Repeat until convergence.
✅ Example
Suppose we have heights of people (in cm): {160,165,170,180,185} and we assume 2
Gaussian groups.
Initial Guess:
Group 1 (short): μ₁=162, σ₁=5
Group 2 (tall): μ₂=182, σ₂=5
E-Step: Calculate probability each height belongs to each group.
M-Step: Update means and variances.
➡ After convergence:
μ₁≈165, μ₂≈182, π₁≈0.6, π₂≈0.4
🔹 Application
Image segmentation
Voice recognition
Clustering continuous data
📚 Learning Theory
🔹 Definition
Learning theory provides a mathematical foundation for understanding how algorithms
generalize from training data to unseen data.
🔹 Key Concepts
1. Hypothesis Space (H):
Set of all models algorithm can choose from.
2. Training Error (Empirical Risk):
n
1
Remp(h) = ∑ L(h(xi), yi)
n
i=1
3. True Error (Expected Risk):
R(h) = E[L(h(x), y)]
4. Overfitting and Underfitting:
Overfitting: Model too complex (low train error, high test error).
Underfitting: Model too simple (high both errors).
🔹 PAC Learning (Probably Approximately Correct)
A hypothesis h is PAC-learnable if for any ε>0 and δ>0,
the learner can find a hypothesis with error ≤ε with probability ≥1−δ.
✅ Example
Suppose you train a classifier with 90% accuracy on training and 88% on test data.
→ It generalizes well → PAC learnable with ε=0.02, δ≈0.1.
🔹 Summary
Learning theory connects training performance to generalization.
Helps estimate sample complexity and model capacity.
🧩 Introduction to Reinforcement Learning (RL)
🔹 Concept
Reinforcement Learning is a type of machine learning where an agent learns by
interacting with an environment to maximize cumulative reward.
🔹 Components
Term Description
Agent Learner or decision maker
Environment System with which agent interacts
State (s) Current situation
Action (a) Choice made by agent
Reward (r) Feedback from environment
Policy (π) Mapping from states to actions
🔹 Goal
Find optimal policy π∗ that maximizes expected return:
∞
Gt = ∑ γkrt+k+1
k=0
where γ = discount factor (0 ≤ γ ≤ 1)
✅ Example
Agent: Robot vacuum
State: Room position
Action: Move, Clean
Reward: +10 for cleaning, −1 for bumping wall
Through repeated trials → learns best cleaning route.
🔹 Algorithms
Value-Based: Q-learning, SARSA
Policy-Based: REINFORCE
Actor-Critic: Combines both
🔹 Q-Learning Formula
Q(s, a) ← Q(s, a) + α[r + γ max Q(s′, a′) − Q(s, a)]
a′
✅ Simple Problem
Given:
Q(s,a)=0 initially, α=0.5, γ=0.9, reward=10, next Q=5
Qnew = 0 + 0.5[10 + 0.9 × 5 − 0] = 0.5[14.5] = 7.25
🔹 Summary
RL learns by trial and error.
Q-learning is a common model-free method.
Used in games, robotics, recommendation systems.
🔗 Bayesian Networks
🔹 Definition
A Bayesian Network (BN) is a probabilistic graphical model that represents a set of
variables and their conditional dependencies using a directed acyclic graph (DAG).
🔹 Structure
Each node = random variable
Each edge = probabilistic dependency
Joint probability:
n
P (X1, X2, ..., Xn) = ∏ P (Xi∣Parents(Xi))
i=1
🔹 Example
Weather → Rain → Wet Grass
P (W , R, G) = P (W )P (R∣W )P (G∣R)
✅ Solved Problem
Suppose:
P(Cloudy)=0.5, P(Rain|Cloudy)=0.8, P(Wet|Rain)=0.9
Find P(Wet):
P (Wet) = P (Wet∣Rain)P (Rain∣Cloudy)P (Cloudy) = 0.9 × 0.8 × 0.5 = 0.36
🔹 Applications
Medical diagnosis
Spam filtering
Decision support systems
🔹 Summary
Bayesian Networks = DAG of probabilistic dependencies
Encodes causal relationships
Allows inference and prediction