K-Means Clustering, Probability & MLE

Discussion Mini Lecture 3

K-Means Clustering, Probability Theory & Maximum Likelihood Estimation

CS 189/289A, Fall 2025 @ UC Berkeley

Sara Pohland

1. K-Means Clustering
2. Probability Theory
1. Probability Fundamentals
2. Common Distributions
3. Multiple Random Variables
3. Maximum Likelihood Estimation (MLE)
4. Convex Optimization

Concepts Covered

K-Means Clustering

1. K-Means Clustering
2. Probability Theory
1. Probability Fundamentals
2. Common Distributions
3. Multiple Random Variables
3. Maximum Likelihood Estimation (MLE)
4. Convex Optimization

Goal of K-Means Clustering

K-Means Clustering Problem

where

sum of points

total points

Lloyd’s Algorithm (“naïve k-means”)

1. Update Assignments: Assign each data point to the cluster with the nearest mean:

2. Update Means: Recalculate means based on data points assigned to each cluster:

You’ll show this algorithm converges in Problem 3 of Disc. 3.

Random Variables & Statistical Measures

1. K-Means Clustering
2. Probability Theory
1. Probability Fundamentals
2. Common Distributions
3. Multiple Random Variables
3. Maximum Likelihood Estimation (MLE)
4. Convex Optimization

Probability Mass Function (PMF)

Probability Density Function (PDF)

Expectation of a Random Variable

Linearity of Expectation:

Expected Value:

Discrete:

Continuous:

Law of the Unconscious Statistician:

Variance & Standard Deviation

Variance – measures the dispersion around the expected value

Standard Deviation – another measure of dispersion/spread

Common Probability Distributions

1. K-Means Clustering
2. Probability Theory
1. Probability Fundamentals
2. Common Distributions
3. Multiple Random Variables
3. Maximum Likelihood Estimation (MLE)
4. Convex Optimization

Bernoulli Random Variable

Bernoulli random variables are used to represent the outcome a single binary experiment.

PMF:

Expected Value:

Variance:

Binomial Random Variable

Binomial random variables are used to represent the outcome of multiple binary (Bernoulli) experiments.

PMF:

Expected Value:

Variance:

You’ll work with Binomial RVs in Problem 2 of Disc. 3.

Exponential Random Variable

Exponential random variables are used to model the amount of time that passes before an event occurs.

PDF:

Expected Value:

Variance:

Gaussian Random Variable

Gaussian random variables are used to represent many continuous real-world processes.

PDF:

Expected Value:

Variance:

You’ll work with Gaussian RVs in Problem 1 of Disc. 3.

Standard Normal Random Variable

The standard normal random variable is the Gaussian random variable with zero mean and unit variance.

PDF:

Expected Value:

Variance:

Functions of Multiple Random Variables

1. K-Means Clustering
2. Probability Theory
1. Probability Fundamentals
2. Common Distributions
3. Multiple Random Variables
3. Maximum Likelihood Estimation (MLE)
4. Convex Optimization

Joint Probability Mass Function (PMF)

We can find the marginal PMFs from the joint PMFs as such:

Joint Probability Density Function (PDF)

We can find the marginal PDFs from the joint PDFs as such:

Expected Value for Multiple RVs

Discrete:

Continuous:

Variance & Covariance for Multiple RVs

Independent Random Variables

Two random variables are independent if knowing information about one does not tell us information about the other.

You’ll work with independent RVs in Problems 1-2 of Disc. 3.

Independent and Identically Distributed

Conditional Probability Mass Function (PMF)

The conditional PMF tells us the probability of one discrete random variable given our observation of another and is defined as:

Conditional Probability Density Function (PDF)

The conditional PDF tells us the probability of one continuous random variable given our observation of another and is defined as:

You’ll get practice with conditional PDFs in Problem 1 of Disc. 3.

Maximum Likelihood Estimation (MLE)

1. K-Means Clustering
2. Probability Theory
1. Probability Fundamentals
2. Common Distributions
3. Multiple Random Variables
3. Maximum Likelihood Estimation (MLE)
4. Convex Optimization

Maximum Likelihood Estimation (MLE)

*

What is the Assumed Distribution?

Usually, one of the common distributions listed in the probability theory section of slides:

How do we Estimate these Parameters?

Approach: Maximize the likelihood of our data under the assumed

probability distribution.

Likelihood:

Optimization problem:

*

* This assumes that our data is independent and identically distributed (IID)— a very common through rarely true assumption.

Problems 1 & 2 on Disc. 3 cover examples of MLE.

Introduction to Convex Optimization

1. K-Means Clustering
2. Probability Theory
1. Probability Fundamentals
2. Common Distributions
3. Multiple Random Variables
3. Maximum Likelihood Estimation (MLE)
4. Convex Optimization

Two Types of Problems

Convex and Concave Functions

Convex Functions

Concave Functions

Common Convex/Concave Functions

(Unconstrained) Convex Optimization Problems

Solving Convex Optimization Problems

1. Take the derivative of the objective w.r.t. optimization variable:

2. Set the derivative equal to zero and solve for the optimal solution:

3. (Optionally) Compute the optimal value by plugging the optimal solution into the objective function:

You’ll practice this in Problems 1 & 2 of Disc. 3.

Equivalent Optimization Problems

These problems have the same optimal solution! (And the optimal value of one is the negation of the other.)

Equivalent Optimization Problems

These problems have the same optimal solution!

Monotonically increasing function:

Equivalent problems via monotone objective:

Remember this for Problem 1 of Disc. 3!

Equivalent MLE Problems

Because the natural log is a monotonically increasing function,

We very often will solve this second optimization problem!

Remember this for Problem 2 of Disc. 3!

K-Means Clustering, Probability & MLE

Discussion Mini Lecture 3

Contributors: Sara Pohland

Additional Resources

1. K-Means Clustering
1. Deep Learning Foundations and Concepts – Chapter 15.1
2. Sara’s notes on Machine Learning – Section 15.2
2. Probability Theory
• Deep Learning Foundations and Concepts – Chapter 2.1, 2.2, 3.1
• Sara’s notes on Probability & Random Processes – Sections 3-7
4. Maximum Likelihood Estimation
• Deep Learning Foundations and Concepts – Chapter 2.3
• Sara’s notes on Machine Learning – Section 7
5. Convex Optimization
• Sara’s notes on Convex Optimization – Sections 2-3