AA228V Lecture 02/03: System Modeling

We don’t want to find out in the real world!

We do want to find out in simulation!

Today, we will discuss ways to model systems so that
we can simulate them for offline validation.

Plan for Today

General Thoughts on Models

Steps for Building Models

Select a Model Class

Select the Parameters for the Model Class

Validate the Model

General Thoughts on Models

There are many different types of models/simulators.

They don’t even have to be on the computer!

We will focus on computational models in this class.

General Thoughts on Models

Models vary in complexity.

flight

h′ = h + ḣΔt
ḣ′ = ḣ + ḧΔt

low
complexity

high
complexity

We want to pick the model that is just complex enough to capture what matters.

General Thoughts on Models

Models vary in complexity.

flight

h′ = h + ḣΔt
ḣ′ = ḣ + ḧΔt

low
complexity

high
complexity

We want to pick the model that is just complex enough to capture what matters.

“Everything should be as simple as possible, but not simpler.”

— Albert Einstein
(maybe)

General Thoughts on Models

Key Challenges

1Model needs to be expressive enough to capture all possible scenarios the system may encounter.

How can I capture all possible scenarios my <insert crazy complex system here> will end up in?

… I don’t even know what they all are!

Yeah, it’s a problem. 😬

But there is some hope! Stay tuned for the runtime monitoring chapter.

General Thoughts on Models

Key Challenges

1Model needs to be expressive enough to capture all possible scenarios the system may encounter.

2Requires data and/or expert knowledge.

3Need to select an objective and optimization technique to find model parameters.

“All models are wrong, but some are useful.”

— British statistician George Box (for real)

Plan for Today

General Thoughts on Models

Steps for Building Models

Select a Model Class

Select the Parameters for the Model Class

Validate the Model

Select a Model Class

We are going to focus on creating probabilistic models.

Nature essay: Why probability probably doesn’t exist (but it is useful to act like it does)

“All of statistics and much of science depends on probability — an astonishing achievement, considering no one’s really sure what it is.”

— David Spiegelhalter, Nature (2024)

Select a Model Class

We are going to focus on creating probabilistic models.

The probability of a particular outcome is a number between zero and one that quantifies the likelihood of that outcome occurring, relative to all possible outcomes.

Select a Model Class

A common type of model class is a probability distribution, which is a function that assigns probabilities to different outcomes.

Discrete Distributions

Continuous Distributions

Probability Mass Function

P (x)

Probability Density Function

p (x)

\sum_{x} P (x) = 1

\int_{- \infty}^{\infty} p (x) d x = 1

0 \leq P (x) \leq 1

p (x) \geq 0

SELECT A MODEL CLASS

Main consideration when selecting a model class:

It needs to be “expressive enough.”

i.e. there is some setting of the model parameters for which the model will fit the data well

SELECT A MODEL CLASS

Gaussian Distribution

μ{{ muTxt }}

σ{{ sigTxt }}

Show log likelihood

We can fit data set 1 well with a Gaussian, but not data set 2, because data set 2 is multimodal.

SELECT A MODEL CLASS

We can fit data set 1 well with a Gaussian, but not data set 2, because data set 2 is multimodal.

Idea: combine several simple distributions into one more expressive distribution.

A Gaussian mixture model is a weighted sum of Gaussians:

p (x) = \sum_{i} w_{i} N (x ∣ μ_{i}, σ_{i}^{2}), \sum_{i} w_{i} = 1

SELECT A MODEL CLASS

Gaussian Mixture

p (x) = w_{1} N (x ∣ μ_{1}, σ_{1}^{2}) + w_{2} N (x ∣ μ_{2}, σ_{2}^{2})

μ_{1}

σ_{1}

μ_{2}

σ_{2}

w_{2} = 1 - w_{1}

Show log likelihood

SELECT A MODEL CLASS

Single Gaussianpoor fit

If a simple distribution does not fit the data well for any setting of its parameters, we need a more complex model class.

Gaussian Mixturegood fit

One way to create more complex distributions is to use a weighted mixture of simpler distributions.

Another way to create a more complex model class is by applying a functional transformation to a simple distribution.

SELECT A MODEL CLASS

Another way to create a more complex model class is by applying a functional transformation to a simple distribution.

Start with a distribution we know:

Z \sim N (0, 1^{2})

10,000 samples of Z, with its density

SELECT A MODEL CLASS

What is the probability density of this new distribution?

Z \sim p_{z} (\cdot), X \sim p_{x} (\cdot), x = f (z)

If f is invertible and differentiable, then

p_{x} (x) = p_{z} (g (x)) ∣ g^{'} (x)∣

where g is the inverse of f.

g (x) = x^{3}, g^{'} (x) = 3 x^{2}

p_{x} (x) = N (x^{3} ∣ 0, 1^{2}) \cdot 3 x^{2}

SELECT A MODEL CLASS

Does it match the samples?

p_{x} (x) = N (x^{3} ∣ 0, 1^{2}) \cdot 3 x^{2}

Note: This formula requires

f

to be differentiable and invertible!

p_{x} (x) = p_{z} (g (x)) ∣ g^{'} (x)∣

SELECT A MODEL CLASS

We can still apply a functional transformation that is not differentiable and invertible! We just won’t be able to calculate the resulting PDF.

samples from a pseudorandom number generator

transformed samples

We call models represented in this way generative models.

SELECT A MODEL CLASS

We call models represented in this way generative models.

f (x) =

neural network

Credit: ajolicoeur.ca/cats

To throw in some buzz words: generative adversarial networks (GANs), variational autoencoders (VAEs), diffusion models, etc.

SELECT A MODEL CLASS

joint distribution: probability distribution over multiple variables.

(multivariate distribution)

represents the likelihood of multiple outcomes occurring simultaneously

Discrete:

P (x, y)

e.g. table representation

x

y

P (x, y)

0.1

0.2

0.5

0.2

Continuous:

p (x, y)

e.g. multivariate Gaussian

Σ = [1001]

Σ = [1 0.5 0.5 1]

Σ = [1 - 0.8 - 0.8 1]

SELECT A MODEL CLASS

Multivariate Gaussian

Σ_{x}

Σ_{y}

Σ_{xy}

Σ =

Not a valid covariance: need Σ_xy² < Σ_xΣ_y

SELECT A MODEL CLASS

joint distribution: probability distribution over multiple variables.

(multivariate distribution)

represents the likelihood of multiple outcomes occurring simultaneously

Note: If two variables are independent, then

P (x, y) = P (x) P (y)

. Otherwise, this is not the case.

SELECT A MODEL CLASS

Note: If two variables are independent, then

P (x, y) = P (x) P (y)

. Otherwise, this is not the case.

Fun aside: what is the probability that four textbook authors have 0, 0, 4, and 5 wisdom teeth?

SELECT A MODEL CLASS

Fun aside: what is the probability that four textbook authors have 0, 0, 4, and 5 wisdom teeth?

From a few minutes of googling, guessing, and asking ChatGPT. Take these with a grain of salt.

1Find every combination of four counts that adds up to the total.

2Sum the product of their probabilities.

Total = {{ tnTxt }}

SELECT A MODEL CLASS

conditional distribution: distribution over a variable given one or more other variables

P (y ∣ x) = \frac{P ( y , x )}{P ( x )}

Discrete:

P (y ∣ x)

e.g. table representation

x

y

P (y ∣ x)

0.1

0.5

Continuous:

p (y ∣ x)

e.g. conditional Gaussian

p (y ∣ x) = N (y ∣ x, σ^{2})

SELECT A MODEL CLASS

conditional distribution: distribution over a variable given one or more other variables

Note: the distributions we want to model for the system are conditional distributions!

Agent

π (a ∣ o)

Environment

T (s^{'} ∣ s, a)

Sensor

O (o ∣ s)

a

s

o

Plan for Today

General Thoughts on Models

Steps for Building Models

Select a Model Class

Select the Parameters for the Model Class

Validate the Model

SELECT THE PARAMETERS FOR THE MODEL CLASS

We want to automatically do this:

Parameters

θ

μ_{1}

σ_{1}

μ_{2}

σ_{2}

w_{2} = 1 - w_{1}

Show log likelihood

Dataset

D

SELECT THE PARAMETERS FOR THE MODEL CLASS

We want to automatically do this:

Parameters

θ

μ_{1}

σ_{1}

μ_{2}

σ_{2}

w_{2} = 1 - w_{1}

Show log likelihood

Dataset

D

How do we know which parameters are the best?

We look for the ones that make the data most likely.

SELECT THE PARAMETERS FOR THE MODEL CLASS

How do we know which parameters are the best?

We look for the ones that make the data most likely.

\hat{θ} = argmax_{θ} P (D ∣ θ)

probability of the data set given the parameters

SELECT THE PARAMETERS FOR THE MODEL CLASS

\hat{θ} = argmax_{θ} P (D ∣ θ)

D = {o_{1}, o_{2}, \dots, o_{m}} = o_{1 : m}

Assume the data points in

D

are independent and identically distributed.

P (D ∣ θ) = P (o_{1} ∣ θ) P (o_{2} ∣ θ) \dots P (o_{m} ∣ θ)

P (D ∣ θ) = \prod_{i = 1}^{m} P (o_{i} ∣ θ)

↓ take the logarithm for better numerical stability

lo g P (D ∣ θ) = \sum_{i = 1}^{m} lo g P (o_{i} ∣ θ)

↓ maximizing the log gives the same solution for

θ

\hat{θ} = argmax_{θ} \sum_{i = 1}^{m} lo g P (o_{i} ∣ θ)

SELECT THE PARAMETERS FOR THE MODEL CLASS

Maximum Likelihood Parameter Estimation

\hat{θ} = argmax_{θ} P (D ∣ θ)

\hat{θ} = argmax_{θ} \prod_{i = 1}^{m} P (o_{i} ∣ θ)

\hat{θ} = argmax_{θ} \sum_{i = 1}^{m} lo g P (o_{i} ∣ θ)

A silly way to solve this optimization problem: try values by hand!

SELECT THE PARAMETERS FOR THE MODEL CLASS

Model class:

p (o ∣ s) = N (o ∣ θ_{1} s + θ_{2}, θ_{3}^{2})

θ_{1}

θ_{2}

θ_{3}

Log likelihood: {{ pLL }}

Each point is a state s and its noisy sensor measurement o.

SELECT THE PARAMETERS FOR THE MODEL CLASS

\hat{θ} = argmax_{θ} \sum_{i = 1}^{m} lo g P (o_{i} ∣ θ)

A better way: give it to an optimization algorithm!

Optimization
Algorithm

Objective

Parameters

Optimal Parameters

More buzzwords: gradient descent, ADAM, genetic algorithms, momentum, etc.

We will talk more about these in Chapter 4.
Take AA222/CS361 for the full story!

SELECT THE PARAMETERS FOR THE MODEL CLASS

Model class:

p (o ∣ s) = N (o ∣ θ_{1} s + θ_{2}, θ_{3}^{2})

θ_{1}

θ_{2}

θ_{3}

Log likelihood: {{ pLL }}

Gradient ascent on the log likelihood

\hat{θ} \approx

({{ t1Txt }}, {{ t2Txt }}, {{ t3Txt }})

SELECT THE PARAMETERS FOR THE MODEL CLASS

This optimization problem leads to many common loss functions!

\hat{θ} = argmax_{θ} i = 1 \sum m lo g p_{θ} (y_{i} ∣ x_{i}) = argmax_{θ} i = 1 \sum m lo g N (y_{i} ∣ f_{θ} (x_{i}), σ^{2}) = argmax_{θ} i = 1 \sum m lo g \frac{1}{2 π σ ^{2}} exp (- \frac{( y _{i} - f _{θ} ( x _{i} ) ) ^{2}}{2 σ ^{2}}) = argmax_{θ} i = 1 \sum m [lo g (1) - lo g (2 π σ^{2}) - \frac{( y _{i} - f _{θ} ( x _{i} ) ) ^{2}}{2 σ ^{2}}] = argmax_{θ} i = 1 \sum m - (y_{i} - f_{θ} (x_{i}))^{2} = argmin_{θ} i = 1 \sum m (y_{i} - f_{θ} (x_{i}))^{2}

This is the least-squares objective: minimize the sum of squared errors.

Sometimes we can keep going and get an analytical solution!

Example 2.9 in the textbook: try it if you want extra practice!

SELECT THE PARAMETERS FOR THE MODEL CLASS

We can also derive analytical solutions for the parameters of a Gaussian distribution and a Bernoulli distribution (and many others!).

Example 2.8 in the textbook: try it if you want extra practice!

Example 2.7 in the textbook: try it if you want extra practice!

SELECT THE PARAMETERS FOR THE MODEL CLASS

That’s maximum likelihood parameter learning!

\hat{θ} = argmax_{θ} \sum_{i = 1}^{m} lo g P (o_{i} ∣ θ)

There is another option…

SELECT THE PARAMETERS FOR THE MODEL CLASS

Bayesian parameter learning is perfect for indecisive people like me and Chidi!

Why pick just one set of parameters? Let’s maintain a distribution over all possible parameters!

θ

P (θ ∣ D)

SELECT THE PARAMETERS FOR THE MODEL CLASS

P (θ ∣ D)

We do not know how to directly compute this.

But we do know how to compute

P (D ∣ θ)

D = {o_{1}, o_{2}, \dots, o_{m}} = o_{1 : m}

Assume the data points in

D

are independent and identically distributed.

P (D ∣ θ) = P (o_{1} ∣ θ) P (o_{2} ∣ θ) \dots P (o_{m} ∣ θ)

P (D ∣ θ) = \prod_{i = 1}^{m} P (o_{i} ∣ θ)

SELECT THE PARAMETERS FOR THE MODEL CLASS

Bayes’ Rule

Definition of conditional probability:

P (y ∣ x)

=

P (x, y)

P (x)

and

P (x ∣ y)

=

P (x, y)

P (y)

SELECT THE PARAMETERS FOR THE MODEL CLASS

Bayes’ Rule

Multiply both sides by the denominator:

P (y ∣ x)

P (x)

=

P (x, y)

and

P (x ∣ y)

P (y)

=

P (x, y)

SELECT THE PARAMETERS FOR THE MODEL CLASS

Bayes’ Rule

Expand the denominator with the law of total probability:

P (y ∣ x)

=

P (x ∣ y)

P (y)

\sum_{y} P (x ∣ y) P (y)

P (x) = \sum_{y} P (x ∣ y) P (y)

SELECT THE PARAMETERS FOR THE MODEL CLASS

Bayes’ Rule

P (y ∣ x)

=

P (x ∣ y)

P (y)

\sum_{y} P (x ∣ y) P (y)

P (θ ∣ D) = \frac{P ( D ∣ θ ) P ( θ )}{\sum _{θ} P ( D ∣ θ ) P ( θ )}

SELECT THE PARAMETERS FOR THE MODEL CLASS

Bayesian Parameter Estimation

P (θ ∣ D) = \frac{P ( D ∣ θ ) P ( θ )}{\sum _{θ} P ( D ∣ θ ) P ( θ )}

P (θ ∣ D) = \frac{P ( D ∣ θ ) P ( θ )}{\sum _{θ} P ( D ∣ θ ) P ( θ )}

P (θ ∣ D) = \frac{P ( D ∣ θ ) P ( θ )}{\sum _{θ} P ( D ∣ θ ) P ( θ )}

P (θ ∣ D) = \frac{P ( D ∣ θ ) P ( θ )}{\sum _{θ} P ( D ∣ θ ) P ( θ )}

likelihood model

P (D ∣ θ) = \prod_{i = 1}^{m} P (o_{i} ∣ θ)

prior distribution over

θ

posterior distribution over

θ

SELECT THE PARAMETERS FOR THE MODEL CLASS

Bayesian Parameter Estimation

Discrete:

P (θ ∣ D) = \frac{P ( D ∣ θ ) P ( θ )}{\sum _{θ} P ( D ∣ θ ) P ( θ )}

Continuous:

p (θ ∣ D) = \frac{p ( D ∣ θ ) p ( θ )}{\int _{θ} p ( D ∣ θ ) p ( θ ) d θ}

In general, the denominator is difficult to compute analytically. However, we can compute the numerator, which lets us sample from the posterior using probabilistic programming.

SELECT THE PARAMETERS FOR THE MODEL CLASS

Bayesian Parameter Estimation

p (θ ∣ D) = \frac{p ( D ∣ θ ) p ( θ )}{\int _{θ} p ( D ∣ θ ) p ( θ ) d θ}

In general, the denominator is difficult to compute analytically. However, we can compute the numerator, which lets us sample from the posterior using probabilistic programming.

SELECT THE PARAMETERS FOR THE MODEL CLASS

Same sensor data, but now we learn a distribution over

θ

for

N (o ∣ θ_{1} s + θ_{2}, θ_{3}^{2})

Data points used: {{ npTxt }}

p (θ_{1} ∣ D)

E [θ_{1}] =

p (θ_{2} ∣ D)

E [θ_{2}] =

p (θ_{3} ∣ D)

E [θ_{3}] =

maximum likelihood

data used

models sampled from the posterior

SELECT THE PARAMETERS FOR THE MODEL CLASS

Let’s flip frisbees!

θ

: probability of both frisbees landing in the same direction

1 - θ

: probability of both frisbees landing in different directions

Flip 10 times…

D = {s, d, s, s, d, d, d, s, d, s}

n

: number of times same

m

: total number of flips

p (D ∣ θ) = θ^{n} (1 - θ)^{m - n}

Turns out that if we select our prior distribution to be

p (θ) = Beta (θ ∣ α, β)

…

our posterior will be

p (θ ∣ D) = Beta (θ ∣ α + n, β + m - n)

SELECT THE PARAMETERS FOR THE MODEL CLASS

Let’s flip frisbees!

θ

: probability of same

n

: number of times same

m

: total number of flips

p (θ) = Beta (θ ∣ α, β)

p (θ ∣ D) = Beta (θ ∣ α + n, β + m - n)

Some Notes

I skipped over the actual calculation of the posterior using this equation:

p (θ ∣ D) = \frac{p ( D ∣ θ ) p ( θ )}{\int _{θ} p ( D ∣ θ ) p ( θ ) d θ}

You can either trust me or check out Chapter 4 of Algorithms for Decision Making.

The Beta distribution is a conjugate prior for the Bernoulli distribution: the posterior is in the same class as the prior.

See the demo for some intuition!

SELECT THE PARAMETERS FOR THE MODEL CLASS

Let’s flip frisbees!

Number same

Number different

Show P(θ > 0.5 | D)

Probability same is more likely: {{ pSame }}

SELECT THE PARAMETERS FOR THE MODEL CLASS

Many common distributions have conjugate priors

likelihood

conjugate prior

Bernoulli / binomial

Beta

multinomial

Dirichlet

Gaussian

SELECT THE PARAMETERS FOR THE MODEL CLASS

Many common distributions have conjugate priors

likelihood

conjugate prior

Bernoulli / binomial

Beta

multinomial

Dirichlet

Gaussian

likelihood model

conjugate prior

SELECT THE PARAMETERS FOR THE MODEL CLASS

What if we do have to make a choice though? 😬

We can use the expectation of the distribution.

Although that might not be the best plan if the distribution is multimodal…

We can instead use the maximum a posteriori (MAP) estimate:

\hat{θ} = argmax_{θ} P (θ ∣ D)

*sometimes also called the mode

SELECT THE PARAMETERS FOR THE MODEL CLASS

Two ways to learn θ from data

Point estimate

Maximum Likelihood

Pick the single θ that makes the data most likely

\hat{θ} = argmax_{θ} \sum_{i = 1}^{m} lo g P (o_{i} ∣ θ)

Output: one value θ̂

Distribution

Bayesian

Keep a belief over every possible θ

P (θ ∣ D) = \frac{P ( D ∣ θ ) P ( θ )}{\int _{θ} P ( D ∣ θ ) P ( θ ) d θ}

Need one value? Use the expectation or MAP

SELECT THE PARAMETERS FOR THE MODEL CLASS

One last thing on parameter learning: we should be careful about generalization.

We should evaluate our model on a separate validation set to make sure we are not overfitting.

Training Set

Validation Set

SELECT THE PARAMETERS FOR THE MODEL CLASS

One last thing on parameter learning: we should be careful about generalization.

We should evaluate our model on a separate validation set to make sure we are not overfitting.

Training Set

Validation Set

Holdout Method

K-fold Cross Validation

Plan for Today

General Thoughts on Models

Steps for Building Models

Select a Model Class

Select the Parameters for the Model Class

Validate the Model

VALIDATE THE MODEL

There is a story that has been going around about a physicist, a chemist, and an economist who were stranded on a desert island with only a can of food. The physicist and the chemist each devised an ingenious mechanism for getting the can open; the economist merely said, "Assume we have a can opener"!

VALIDATE THE MODEL

Our assumptions don’t mean much if they aren’t grounded in reality.

All of our downstream validation results depend on how good our model is!

VALIDATE THE MODEL

Our assumptions don’t mean much if they aren’t grounded in reality.

All of our downstream validation results depend on how good our model is!

So we need to validate the model.

VALIDATE THE MODEL

We want to compare features of the model to features of the data.

Quantile-Quantile (Q-Q) Plot

PDF Plot

α = 0.1

q_{model} = - 2.28

q_{data} = - 1.29

VALIDATE THE MODEL

We want to compare features of the model to features of the data.

Quantile-Quantile (Q-Q) Plot

PDF Plot

α = 0.1

q_{model} = - 2.28

q_{data} = - 1.29

VALIDATE THE MODEL

We want to compare features of the model to features of the data.

Quantile-Quantile (Q-Q) Plot

PDF Plot

Calibration Plot

CDF Plot

good fit

bad fit

VALIDATE THE MODEL

We want to compare features of the model to features of the data.

Quantile-Quantile (Q-Q) Plot

PDF Plot

Calibration Plot

CDF Plot

good fit

bad fit

These are visual diagnostics. We can summarize them using summary metrics.

VALIDATE THE MODEL

PDF Plot

good fit

bad fit

These are visual diagnostics. We can summarize them using summary metrics.

We can summarize the PDF plot using the Kullback-Leibler divergence (K-L divergence).

D_{KL} (p ∥ q) = \int p (x) lo g (\frac{p ( x )}{q ( x )}) d x

D_{KL} = 8.6 \times 1 0^{- 5}

D_{KL} = 0.49

The K-L divergence is part of a broad class of divergences called the F-divergences.
The K-L divergence is not symmetric and it is not defined if the support of

p

is not a subset of the support of

q

VALIDATE THE MODEL

good fit

bad fit

These are visual diagnostics. We can summarize them using summary metrics.

We can summarize the CDF plot using the Kolmogorov-Smirnov statistic (K-S statistic).

CDF Plot

D_{KS} = max_{x} ∣ P (X \leq x) - Q (X \leq x) ∣

VALIDATE THE MODEL

good fit

bad fit

These are visual diagnostics. We can summarize them using summary metrics.

We can summarize the calibration plot using the Maximum Calibration Error (MCE) and Expected Calibration Error (ECE).

Calibration Plot

Average Gap

VALIDATE THE MODEL

We don’t want to miss the interactions between features.

One option: create a single feature that captures the relationship between multiple features.

VALIDATE THE MODEL

We don’t want to miss the interactions between features.

One option: create a single feature that captures the relationship between multiple features.

Multiple Features

Combined Feature

Multiple Features

VALIDATE THE MODEL

We don’t want to miss the interactions between features.

One option: create a single feature that captures the relationship between multiple features.

Combined Feature

Another option: extend summary metrics to multiple dimensions.

VALIDATE THE MODEL

What about conditional distributions?

Combined Feature

Partition conditioning variable into bins and compute visual diagnostics and metrics for each bin.

Plan for Today

General Thoughts on Models

Steps for Building Models

Select a Model Class

Select the Parameters for the Model Class

Validate the Model