ECE 726 - Winter 2026

Topic 4. Statistical Decision Theory

Sorina Dumitrescu

Electrical and Computer Engineering

McMaster University
c Sorina Dumitrescu

January 16, 2026

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 1 / 24
 Data Generating Distribution

In the probabilistic model of learning we assume that there is a

probability distribution P over the input/output pairs.
The distribution P models the data that we expect to see.
Let x denote the feature vector (input) and t the label or target
(output).
P(x, t) denotes the probability of the pair (x, t) when the data is
discrete; when the data is continuous, p(x, t) denotes the density
function.

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 2 / 24
 Data Generating Distribution

When solving a machine learning problem

we do not know P (we do not know the exact value P(x, t)),
we do not make any assumption on how P might look like,
but, we assume that the training examples are drawn from P and
that they are drawn independently.

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 3 / 24
 Expected Loss

Recall that f denotes the predictor obtained after training a model;

for each input x, f (x) denotes the predicted label.
Recall that `(y , t) denotes the loss function or error function (i.e.,
the error between the predicted label y and the true label t).
Expected loss (or expected error) of the predictor f on examples
drawn from P:
(P
`(f (x), t)P(x, t) discrete case
E(f ) = R (x,t) , (1)
`(f (x), t)p(x, t)dxdt continuos case

The generalization error of a predictor is the expected loss.

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 4 / 24
 Test Error

The generalization error describes the performance of a predictor.

We cannot compute the generalization error because we do not know
the probability distribution P.
Instead we estimate the generalization error by using the test
error (the average error on the test set).
We assume that the test examples are drawn from P and that
they are drawn independently.
Under the above assumption, the test error approaches the
generalization error almost surely as the size of the test set goes
to infinity,
according to the strong law of large numbers.

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 5 / 24
 Optimal Predictor when P Is Known

The optimal predictor fopt is defined as (the predictor function

that minimizes the expected loss)?
If we knew P, could we compute the fopt ?
YES!

Theorem 1
For each x, the optimal predictor fopt satisfies
( P
arg miny t `(y , t)P(t|x) (discrete prob. distrib.)
fopt (x) = R∞ (2)
arg miny −∞ `(y , t)p(t|x)dt (contin. prob. distrib.)

where in the continuous case, p(t|x) denote the density function of the
conditional distribution of t given x.

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 6 / 24
 Optimal Predictor when P Is Known. Proof

In our derivation, we will use the chain rule (or product rule) for
probability:

P(x, t) = P(x)P(t|x).

Apply the chain rule in the formula for the expected loss
X
E(f ) = `(f (x), t)P(x, t)
(x,t)
XX
= `(f (x), t)P(x)P(t|x)
x t
X X
= P(x) `(f (x), t)P(t|x)
x
|t {z }
pick f (x) that minimizes this

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 7 / 24
 Optimal Predictor for Regression with Squared Loss

Theorem 2
Consider regression with squared difference as loss function.
The optimal predictor fopt,sqr (x) is given by
(P
tP(t|x) discrete case
fopt,sqr (x) = R ∞t (3)
−∞ tp(t|x)dt continuouse case

In words: the best predictor for input x is the conditional mean (or
conditional expectation) of the target t given x.
i.e., the average of all possible values of t weighted by their
conditional probability given x.

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 8 / 24
 Optimal Predictor for Regression with Squared Loss. Proof
Consider the discrete case, i.e., the set of possible targets is finite.
According to Theorem 1
X
fopt,sqr (x) = arg min (y − t)2 P(t|x).
y
t

X X
(y − t)2 P(t|x) = (y 2 − 2ty + t 2 )P(t|x)
t t
X X X
= y 2 P(t|x) − 2ty P(t|x) + t 2 P(t|x)
t t t
X X X
2
=y P(t|x) −2y tP(t|x) + t 2 P(t|x) .
| t {z } |t {z } |t {z }
=1 b c

Find arg miny (y 2 − 2by + c).

The cost function is convex, so set the derivative to 0.
(y 2 − 2by + c)0 = 2y − 2b = 0 ⇒ y = b. QED
Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 9 / 24
 Homework

Assume that the data (x, t) is generated such that

t = g (x) + ,

where g (x) is a known function of x, and  is some random noise

independent of x, with mean µ and variance σ 2 .
Find fopt,sqr (x) considering the squared error as the loss function.
Find the smallest squared error that a predictor function could
achieve.

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 10 / 24
 Optimal Predictor for Regression with Absolute Error
(Optional)

Theorem 3
Consider regression with absolute difference as loss function:
`(y , t) = |y − t|.
The optimal predictor fopt,abs (x) equals the median of the conditional
distribution of t given x, i.e.

fopt,abs (x) = m,

where m is such that Prob(t ≤ m|x) = 1/2 in the continuous case,

and Prob(t < m|x) < 1/2 ≤ Prob(t ≤ m|x) in the discrete case.

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 11 / 24
 Optimal Predictor for Regression with Absolute Error.
Proof (Optional)
R∞
Consider the continuous case. Let F (y ) = −∞ |y − t|p(t|x)dt.
We have to find arg miny F (y ).
For this, solve F 0 (y ) = 0.
Z y Z ∞
F (y ) = (y − t)p(t|x)dt + (t − y )p(t|x)dt
−∞ y
Z y Z y
=y p(t|x)dt − tp(t|x)dt
−∞ −∞
Z ∞ Z ∞
+ tp(t|x)dt − y p(t|x)dt
y y
Z y Z y 0 Z y 0
F 0 (y ) = y 0 p(t|x)dt + y p(t|x)dt − tp(t|x)dt
−∞ −∞ −∞
Z ∞ 0 Z ∞ Z∞ 0
0
+ tp(t|x)dt −y p(t|x)dt − y p(t|x)dt
y y y

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 12 / 24
 Optimal Predictor for Regression with Absolute Error.
Proof (Optional)

By using the first fundamental theorem of calculus, we obtain

Z y
0
F (y ) = p(t|x)dt + yp(y |x) − yp(y |x)
−∞
Z ∞
− yp(y |x) − p(t|x)dt + yp(y |x)
y
Z y Z ∞
= p(t|x)dt − p(t|x)dt.
−∞ y

F 0 (y ) = 0 implies y = m.
QED

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 13 / 24
 Overview of Classification

In classification the targets are in a finite set.

Most of the time they are categorical.
In binary classification, there are only two categories.
Medical diagnosis (cancer/no cancer; diabetes/no diabetes).
Spam detection (spam/non-spam).

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 14 / 24
 Decision Regions

A classifier f (x) can be regarded as a decision rule that assigns each

feature vector x to one of the classes.
Say, we have K classes: C1 , C2 , · · · , CK .
The decision rule divides the input space (the space of all possible
x’s) into regions, called decision regions.
For each k, decision region Rk is the set of all vectors x assigned to
class Ck .
The boundaries between decision regions are called decision
boundaries or decision surfaces.

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 15 / 24
 Loss Function for Classification
A common loss function in classification is the zero/one loss:
(
1 if y 6= t
`(y , t) =
0 if y = t.

Example: x ∈ {5, 8}; possible classes are: fog , rain, nei (neither)
P(5, rain) = 1/6, P(5, fog ) = 1/12, P(5, nei) = 1/12
P(8, rain) = 1/6, P(8, fog ) = 1/6, P(8, nei) = 1/3
Prediction function f : f (5) = fog , f (8) = rain, and 0/1 loss.
The expected 0/1 loss when using the prediction function f :

`(f (5), rain)P(5, rain) + `(f (5), fog )P(5, fog ) + `(f (5), nei)P(5, nei)
+`(f (8), rain)P(8, rain) + `(f (8), fog )P(8, fog ) + `(f (8), nei)P(8, nei)
= 1 × P(5, rain) + 0 × P(5, fog ) + 1 × P(5, nei)
+0 × P(8, rain) + 1 × P(8, fog ) + 1 × P(8, nei)

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 16 / 24
 Probability of Prediction Error

Observation
The expected zero/one loss equals the probability of making a
prediction error.

Proof when the data is discrete:

Let the prediction function be f (x). The probability of prediction
error is the probability of the set of all pairs (x, t) for which f (x) 6= t,
in other words:
X X X
P(x, t) = 1 · P(x, t) + 0 · P(x, t)
(x,t),f (x)6=t (x,t),f (x)6=t (x,t),f (x)=t
X
= `0/1 (f (x), t)P(x, t)
(x,t)

QED

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 17 / 24
 Zero/One Loss Function

A common loss function in classification is the zero/one loss:

(
1 if y 6= t
`(y , t) =
0 if y = t.

The expected 0/1 loss equals each of the following:

the sum of the probabilities of the cases when the prediction is wrong
the probability that the prediction is wrong
the probability of misclassification when using f as the classifier
1 - the sum of the probabilities of the cases when the prediction is
correct

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 18 / 24
 Optimal Predictor for Classification with Zero/One Loss
Theorem 4
Assume that there are K classes C1 , C2 , · · · , CK .
Thus, the possible values for t and for y are C1 , C2 , · · · , CK .
Consider the zero/one loss function:
(
1 if y 6= t
`(y , t) =
0 if y = t.

The optimal predictor is given by

fopt (x) = arg max P(Ci |x)

Ci ,1≤i≤K

= Ci0 ,

where P(Ci0 |x) ≥ P(Ci |x) for any other i.

This is called the Bayes classifier.
Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 19 / 24
 Optimal Predictor for Classification with Zero/One Loss.
Proof
For each x
CK
X
fopt (x) = arg min `(Ci , t)P(t|x)
Ci ,1≤i≤K
t=C1
= arg min (1 − P(Ci |x))
Ci ,1≤i≤K

= Ci0

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 20 / 24
 Optimal Predictor for Classification with Zero/One Loss.
Proof
For each x
CK
X
fopt (x) = arg min `(Ci , t)P(t|x)
Ci ,1≤i≤K
t=C1
= arg min (1 − P(Ci |x))
Ci ,1≤i≤K

= Ci0

where we used
CK
X
`(Ci , t)P(t|x) =
t=C1
= P(C1 |x) + · · · + P(Ci−1 |x) + P(Ci+1 |x) + · · · + P(CK |x)
= 1 − P(Ci |x).

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 20 / 24
 Approaches for Classification Problems
Consider classification problems with zero/one loss.
If we knew the posterior class probabilities P(Ci |x), we could use
the Bayes classifier:

fopt (x) = arg max P(y |x) = arg max P(Ci |x).
y Ci ,1≤i≤K

Approaches used to solve classification problems with zero/one loss

(from Bishop, sect. 5.2.4):
Generative Models: Solve the inference problem of determining the
class-conditional densities p(x|Ci ) for each class Ci (i.e., learn a model
for p(x|Ci ), based on the training data). Separately infer the prior
class probabilities P(Ci ). Then compute P(Ci |x) and the Bayes
classifier.
Discriminative Models: Infer the posterior class probabilities P(Ci |x).
Use Bayes classifier to assign x to one of the classes.
Find a function f (x) from the training data, which maps x directly to a
class label (no probabilities are used here). Function f is called a
discriminant function.
Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 21 / 24
 How to Compute P(Ci |x) Based on p(x|Ci ) and P(Ci )?

How can we compute the posterior class probabilities P(Ci |x) if we

know the class-conditional densities p(x|Ci ) and the prior class
probabilities P(Ci )?

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 22 / 24
 Approaches for Regression Problems

Consider regression problems with squared loss.

Recall that the optimal predictor is the conditional mean of t given x
- but we don’t know p(t|x).
Approaches used to solve regression problems with squared error loss
(from Bishop):
Solve the inference problem of determining the joint density p(x, t)
(learn a model for p(x, t), based on the training data). Then compute
p(t|x) and the conditional mean (3).
First solve the inference problem of determining the conditional density
p(t|x) (based on the training data). Then compute the conditional
mean (3).
Find a regression function f (x) directly from the training data.

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 23 / 24
 How to Compute p(t|x) Based on p(x, t)?

How can we compute the conditional density p(t|x) if we only know

the joint density p(x, t)?

Sorina Dumitrescu (McMaster University) ECE 726 Machine Learning: An Introduction January 16, 2026 24 / 24