B4B33RPZ · Pattern Recognition and Machine Learning

Exercise lab I

Lab 7: solving exam-style exercises, test 1 feedback, and nearest neighbours

Klára JanouškováFEE CTU, Prague

Warm-up: logistic regression

Logistic regression models directly…

$p(k \mid x) = \sigma(k\,\mathbf{w}^\top\mathbf{x})$ : it is a discriminative model. It never says how the $x$ of a class are distributed, so it cannot generate data.

The training data are linearly separable. Without regularisation, the ML weights $\mathbf{w}$ …

Making $\|\mathbf{w}\|$ larger pushes every $\sigma(k\,\mathbf{w}^\top\mathbf{x})$ closer to 1, so the loss keeps falling and never reaches a minimum. A prior (L2 penalty) stops it.

What does the $k$ in $\sigma(k\,\mathbf{w}^\top \mathbf{x})$ do?

Last week's fit gives each student a score $a = \mathbf{w}^\top \mathbf{x} = 1.79\,x - 5.83$ ; $a > 0$ predicts "pass".

Passed students ( $k = +1$ ): $\ p(+1 \mid \mathbf{x}) = \sigma(a)$

↓ the two probabilities sum to 1, and $\sigma$ is symmetric: $1 - \sigma(a) = \sigma(-a)$

Failed students ( $k = -1$ ): $\ p(-1 \mid \mathbf{x}) = 1 - \sigma(a) = \sigma(-a)$

One formula for both: $\ p(k \mid \mathbf{x}) = \sigma(k\,a)$ . Multiplying by $k$ mirrors the failed students: the margin is $m = k\,a$

Now all students lie on one curve $\sigma(m)$ = probability of their true label: $m > 0$ correct, $m < 0$ wrong side (2 students).

So one loss $-\ln \sigma(m)$ works for both classes: next slide.

Recap: how do we score $\mathbf{w}$ on the training data?

Labels $k_i \in \{-1, +1\}$ , $\mathbf{x}$ with a 1 appended. The model: $p(k \mid \mathbf{x}) = \sigma(k\, \mathbf{w}^\top \mathbf{x})$ .

Likelihood of the training labels:

L(\mathbf{w}) = \prod_{i=1}^{N} \sigma(k_i\, \mathbf{w}^\top \mathbf{x}_i)

↓ maximising $L$ = minimising $-\tfrac1N \ln L$ , and $-\ln \sigma(m) = \ln(1 + e^{-m})$

E(\mathbf{w}) = \frac{1}{N} \sum_{i=1}^{N} \ln\big(1 + e^{-m_i}\big), \qquad m_i = k_i\, \mathbf{w}^\top \mathbf{x}_i

The margin $m_i > 0$ : example on the correct side. Correct side: loss $\to 0$ ; wrong side: loss $\approx |m|$ .

With L2: minimise $E(\mathbf{w}) + \lambda \|\mathbf{w}\|^2$ (bias not penalised).

Three students, three margins

Last week's ML fit: $w_0 = -5.83$ , $w_1 = 1.79$ .

↓ the boundary is where $p = 0.5$ , i.e. $w_0 + w_1 x = 0$

$b = -w_0 / w_1 = 3.26$ h, so $w_0 = -w_1 b$ and $m = k\, w_1 (x - b)$

A passed, 5.5 h: $m = 1.79 \cdot 2.24 = 4.0$ , loss $0.02$

B failed, 3 h: $m = -1.79 \cdot (-0.26) = 0.46$ , loss $0.49$

C passed, 2.5 h: $m = 1.79 \cdot (-0.76) = -1.36$ , loss $1.58$

Steeper $\sigma$ : double $w_1$ , keep $b$ . All margins double:

A $0.02 \to 0.00$ , $\$ B $0.49 \to 0.34$ , $\$ C $1.58 \to 2.77$

Correct points gain a little, wrong ones lose ~linearly.

Separable vs. overlapping: where is the minimum?

Keep each boundary $b$ ( $w_0 = -w_1 b$ ) and drag $w_1$ : only the steepness changes. Lines: how far each point is from its label.

Separable (top): every point is correct, every loss shrinks: $E \to 0$ , no minimum, $\|\mathbf{w}\| \to \infty$ .

Overlapping (bars): the 2 wrong-side students' losses grow $\approx |m| \propto w_1$ , the others' shrink.

$E$ = falling part + growing part (thin curves): the sum has a minimum, $w_1 \approx 1.8$ .

Convex, but no closed form: gradient descent or Newton. L2 ( $+\lambda w_1^2$ ) gives a minimum in both cases.

w_1

= 1.00 add L2,

\lambda = 0.01

Halfway through the labs

About half of the labs are done, so you should already be able to solve about half of the exam exercises.

Test 1 feedback: what went well, and what we want to see in definitions
Typical exam exercises, solved on the whiteboards:
- E1: maximum likelihood with missing failure times
- E2: Parzen windows and Neyman–Pearson
- E3: Bayes with Gaussians and a "don't know" option
Nearest neighbours: k-NN, Voronoi cells, k-d trees, condensation and editing, and an exam exercise on 1-NN (E4)

Where to find exam questions

Past exam questions

cmp.felk.cvut.cz/cmp/courses/recognition/Exam-questions

Old exams, grouped by topic. Today's three exercises come from there.

Exercise book (Sbírka úloh)

Course page → Labs → Sbírka úloh

Typical problems with solutions, mostly from past exams. It is updated during the semester, so download it again from time to time.

Found a mistake in the exercise book? Report it in the exercisebook repository (linked on the course page).

Part 1

Test 1: feedback

How did test 1 go?

24 students, 12 points per test.

9.5mean

10.6median

3 – 12range

Computations went well. The weak spots are the formal definitions (a) parts) and the error integrals in Neyman–Pearson / minimax.

Part	Average	Max
Q1 a) definition	0.94	1
Q1 b) missing values	0.99	1
Q1 c) optimal strategy	2.62	3
Q1 d) risk	0.79	1
Q2 a) definition	0.70	1
Q2 b) strategy	2.94	4
Q2 c) errors	0.55	1

Definitions: what is the Bayesian task?

Given: observations $X$ , hidden states $K$ , decisions $D$ , the joint probability $p: X \times K \to [0,1]$ and the loss $W: K \times D \to \mathbb{R}$ .

Strategy: any function $q: X \to D$ ; $Q$ = the set of all strategies.

Risk of a strategy (the expected loss):

R(q) = \sum_{x \in X} \sum_{k \in K} p(x, k)\, W\big(k, q(x)\big)

Task: $\displaystyle q^* = \operatorname*{argmin}_{q \in Q} R(q)$

The partial risk

R(x, d) = \sum_k p(x,k)\,W(k,d)

and

q^*(x) = \operatorname{argmin}_d R(x,d)

is how we solve the task, not its definition. From test 2 on, definitions are graded strictly.

Quick check: risks and errors

Which one is the risk of a strategy $q$ ?

b) is the partial risk of one decision $d$ at one $x$ . c) uses $p(x \mid k)$ , which ignores how often each class occurs (the priors).

NP: only $p(x \mid 1)$ , $p(x \mid 2)$ are known (no priors). Class 1 is dangerous; $q$ says "danger" on $X_1$ , "safe" on $X_2$ . The overlooked danger $\varepsilon_1 = P(\text{safe} \mid 1)$ is…

$\varepsilon_1 = P(x \in X_2 \mid 1)$ : a class-1 $x$ in the other region. a) is $1 - \varepsilon_1$ (6 of 23 in test 1).

Exercise 1 · 8 points

Maximum likelihood: light bulbs

E1: how long do light bulbs live?

The lifetime $t$ of a bulb has the density

p(t) = \frac{1}{\theta}\, e^{-t/\theta}, \qquad t \in [0, \infty),

where $p(t)\,\delta$ is the probability that a bulb fails in a short interval $\delta$ around $t$ .

(a) 3 points. Six bulbs were tested and failed at

$t_0 = 0.0,\ t_1 = 1.0,\ t_2 = 2.3,\ t_3 = 2.7,\ t_4 = 6.0,\ t_5 = 12.0.$

What is the maximum likelihood estimate of the reliability parameter $\theta$ ?

(0) Definition first. Write the formal definition of the maximum likelihood estimate.

E1: the test stops early

Same bulbs, same lifetimes $0.0,\ 1.0,\ 2.3,\ 2.7,\ 6.0,\ 12.0$ , same density $p(t) = \frac{1}{\theta} e^{-t/\theta}$ .

(b) 3 points. The test finishes at $t_{\text{end}} = 4.0$ , so two bulbs are still on: their failure times are unknown. What is the ML estimate of $\theta$ now?

Directly, using the probability that a bulb still works at $t_{\text{end}}$ (2 points).
With the EM algorithm, which replaces each unknown failure time by its expected value given that it is after $t_{\text{end}}$ (1 point). Optional for now: EM is in lecture 12 (11. 12.).

(c) 2 points. The logging device is broken. We only know that at $t_{\text{end}}$ , $G$ bulbs are still good and $F$ bulbs have failed. Find $\theta$ .

Recap: the exponential distribution

How long until something fails, if failures happen at a constant average rate?

Density, with $\theta$ = the mean lifetime:

p(t) = \tfrac{1}{\theta}\, e^{-t/\theta},\quad t \ge 0

Mean lifetime:

\mathbb{E}[T] = \theta

Often written with the rate $\lambda = 1/\theta$ : $p(t) = \lambda e^{-\lambda t}$ , $\ \mathbb{E}[T] = 1/\lambda$ . The continuous version of the geometric distribution $P(X = k) = (1-p)^{k-1} p$ .

Where does $\mathbb{E}[T] = \theta$ come from?

Mean lifetime:

\mathbb{E}[T] = \int_0^\infty t\, \tfrac{1}{\theta} e^{-t/\theta}\, dt

↓ by parts: $u = t$ , $v' = \tfrac1\theta e^{-t/\theta}$ , so $u' = 1$ , $v = -e^{-t/\theta}$

= \Big[-t\,e^{-t/\theta}\Big]_0^\infty + \int_0^\infty e^{-t/\theta}\, dt

↓ the bracket is 0 at both ends; $\int_0^\infty e^{-t/\theta}\,dt = \Big[-\theta\, e^{-t/\theta}\Big]_0^\infty = \theta$

= 0 + \theta = \theta

Before (b): a bulb that is still on

What do we know about the two bulbs still on, and how likely is it?

Only $T > t_{\text{end}}$ : $\ P(T > t) = \int_t^\infty \tfrac{1}{\theta} e^{-s/\theta}\, ds$

↓ antiderivative: guess $F(s) = -e^{-s/\theta}$ , check with the chain rule (inner derivative of $-s/\theta$ is $-\tfrac1\theta$ )

F'(s) = -e^{-s/\theta} \cdot \Big(-\frac{1}{\theta}\Big) = \frac{1}{\theta}\, e^{-s/\theta} \ \checkmark

↓ evaluate $F(\infty) - F(t)$ ; as $s \to \infty$ , $e^{-s/\theta} \to 0$

P(T > t) = \Big[-e^{-s/\theta}\Big]_t^\infty = 0 - \big(-e^{-t/\theta}\big) = e^{-t/\theta}

Each bulb still on contributes this probability to the likelihood, instead of $p(t_i)\,\delta$ .

Exercise 2 · 6 points

Parzen windows and Neyman–Pearson

E2: two classes, few points

Training sets: $X_1 = \{1, -1, 1, 2, 0\}$ and $X_2 = \{-1, 0, 1, 3\}$ .

(a) 3 points. Estimate $p(x \mid 1)$ from $X_1$ and $p(x \mid 2)$ from $X_2$ with Parzen windows, kernel $K(x, y) = k(x - y)$ :

k(z) = \begin{cases} 1/h & \text{for } |z| \le h/2,\\ 0 & \text{for } |z| > h/2,\end{cases}\qquad h = 2.

Plot the estimated densities. Find $p(x \mid 1)$ and $p(x \mid 2)$ for $x = 0.5$ .

(b) 3 points. Class 2 is dangerous. Construct the Neyman–Pearson strategy for overlooked danger $< 40\,\%$ . What are the errors $\varepsilon_1$ and $\varepsilon_2$ for classes 1 and 2?

Definition first: write the formal definition of the Neyman–Pearson task.

Exercise 3 · 6 points

Bayes with Gaussians and a "don't know"

E3: two Gaussian classes

Two classes with equal priors and Gaussian class-conditional densities $N(\boldsymbol\mu_1, \mathbf{C}_1)$ , $N(\boldsymbol\mu_2, \mathbf{C}_2)$ :

\boldsymbol\mu_1 = \begin{bmatrix}3\\6\end{bmatrix},\ \ \mathbf{C}_1 = \begin{bmatrix}2&0\\0&2\end{bmatrix},\qquad \boldsymbol\mu_2 = \begin{bmatrix}3\\-2\end{bmatrix},\ \ \mathbf{C}_2 = \begin{bmatrix}2&0\\0&2\end{bmatrix}.

Definition first: write the formal definition of the Bayesian task with the reject option used in (b).

(2 points) Find the classifier minimising the probability of classification error.
(2 points) Reject option: saying "don't know" costs 0.1, an error costs 1. For which $\mathbf{x} \in \mathbb{R}^2$ does the Bayes-optimal strategy say "don't know"?
(2 points) Find $q: \mathbb{R}^2 \to \{1, 2\}$ minimising the Bayes risk for $W(1,2) = 2$ , $W(2,1) = 1$ : classifying a class-1 object as class 2 costs twice as much as the other error.

Recap: the multivariate normal

How likely is a point $\mathbf{x} \in \mathbb{R}^k$ under a class with mean $\boldsymbol\mu$ and covariance $\boldsymbol\Sigma$ ?

p(\mathbf{x}) = \frac{\exp\!\Big(-\tfrac12 (\mathbf{x} - \boldsymbol\mu)^\top \boldsymbol\Sigma^{-1} (\mathbf{x} - \boldsymbol\mu)\Big)}{\sqrt{(2\pi)^k\, |\boldsymbol\Sigma|}}

↓ for $\boldsymbol\Sigma = \sigma^2 \mathbf{I}$ : $\ \boldsymbol\Sigma^{-1} = \tfrac{1}{\sigma^2}\mathbf{I}$ , the quadratic form is a squared distance

p(\mathbf{x}) \propto \exp\!\Big(-\frac{\|\mathbf{x} - \boldsymbol\mu\|^2}{2\sigma^2}\Big)

Contours are circles around $\boldsymbol\mu$ . Same $\boldsymbol\Sigma$ in both classes: the normalising constant is the same and cancels in every ratio.

Recap: Bayes with a reject option

Decisions $D = K \cup \{\texttt{not known}\}$ , with the loss

W(k, d) = \begin{cases} 0, & d = k,\\ 1, & d \ne k,\ d \ne \texttt{not known},\\ \varepsilon, & d = \texttt{not known}.\end{cases}

The Bayesian strategy minimises the partial risk at each $x$ :

q^*(x) = \operatorname*{argmin}_{d \in D} \sum_{k \in K} p(k \mid x)\, W(k, d)

What does each decision cost at $x$ ?

R(x, k) = 1 - p(k \mid x), \qquad R(x, \texttt{not known}) = \textstyle\sum_k p(k\mid x)\,\varepsilon = \varepsilon

Recap: when is "don't know" the best answer?

Compare the cheapest class with the fixed cost $\varepsilon$ of saying "not known":

q^*(x) = \begin{cases} \operatorname*{argmax}_{k} p(k \mid x), & \text{if } 1 - \max_k p(k \mid x) < \varepsilon,\\ \texttt{not known}, & \text{if } 1 - \max_k p(k \mid x) \ge \varepsilon.\end{cases}

Find the class with the largest posterior, $p_{\max}(x)$ .
If $1 - p_{\max}(x) < \varepsilon$ , answer that class.
Otherwise answer not known: even the best guess is wrong too often.

Lecture recap

Nearest neighbours

Which class is the new point?

No model, just the training set $\mathcal{T}$ and a distance $d$ . Look at what the closest training points say.

1. Find the $K$ points $S$ of $\mathcal{T}$ closest to $x$ in the metric $d$ .

2. Vote: the class with the majority in $S$ ,

k = \operatorname*{argmax}_{l}\ \sum_{i=1}^{K} [\![\, k'_i = l \,]\!],\qquad (x'_i, k'_i) \in S

K = 1

: the nearest point is a triangle → class 2

K = 3

: two circles, one triangle → class 1

k-NN: pros and cons

+

Easy to implement: a good baseline
General: no assumptions about the distributions
No training

−

Needs a metric; different axes may have different scales
Naive version is slow (compare with all $N$ points) and keeps the whole training set in memory

The rest of this part: making it faster (k-d tree) and smaller (condensation), and more accurate (editing).

Quick check: k-NN

Features: height in metres, weight in grams. Euclidean k-NN mostly looks at…

Weights differ by thousands of grams, heights by tenths of a metre, so the weight dominates every distance. Standardise each feature (subtract the mean, divide by the standard deviation) first.

The error of 1-NN on its own training set (no duplicate points) is…

Every training point is its own nearest neighbour. So the training error says nothing about 1-NN: measure on held-out data.

Where does 1-NN say class 1?

Every point of the plane belongs to its nearest training point.

Voronoi diagram: the cells of all points closest to one training point. Cell edges lie on the perpendicular bisectors between neighbours.

1-NN gives each cell the class of its point.

The decision boundary is made of the cell edges between points of different classes: piecewise linear.

Finding the nearest neighbour fast: k-d tree

Six points in the plane (labelled in the figure).

Split at the median in $x$ : $(7,2)$

Each half at its median in $y$

Then in $x$ again, until each cell has one point

Query: go down to the leaf, then back up, visiting a cell only if it can contain something closer than the best so far. About $O(\log N)$ per query in low dimensions.

Animations: YouTube, Wikipedia

How fast can we find a median?

Sorting: $O(n \log n)$ . Can we do it in $O(n)$ ?

Pick an element: the pivot (at random works well in practice).
Split the list: elements $\le$ pivot (lesser), elements $>$ pivot (greater).
We look for the $k$ -th element ( $k = n/2$ for the median). If lesser has at least $k$ elements, recurse into it; otherwise recurse into greater for element $k - |\texttt{lesser}|$ .

Only one side is searched: $n + n/2 + n/4 + \dots \approx 2n$ on average, but $O(n^2)$ with bad pivots.

Median of medians: choose the pivot as the median of the medians of groups of 5. It is always near the middle, so $O(n)$ even in the worst case.

Condensation: keep only the points that matter

Goal: a smaller training set $A$ that classifies all of $\mathcal{T}$ correctly with 1-NN.

Put one random sample of $\mathcal{T}$ into $A$ , the rest into $B$ .
Classify the samples of $B$ by 1-NN with training set $A$ . Move every misclassified $x \in B$ to $A$ .
If anything moved in step 2, repeat step 2.

Output: $A$ , the condensed training set for 1-NN.

Condensation on an example

From 220 to 89 points, the same labels on all training points. In the overlap many points are kept, and the boundary stays ragged.

Editing: remove the points that mislead

Goal: a lower error (not a faster classifier).

Split $\mathcal{T}$ into two sets $A$ and $B$ : $\ \mathcal{T} = A \cup B$ , $A \cap B = \emptyset$ .
Classify the samples of $B$ by K-NN with training set $A$ . Remove from $B$ every misclassified sample.

Output: $B$ , the training set for 1-NN.

Edit first, then condense: the condensation then keeps only a few points along a smooth boundary.

Editing on the same example

Editing keeps 168 of 220 points and smooths the boundary; condensing the edited set leaves only 25 points near it.

E4: optimal classifier and 1-NN (exam, Jan 2025)

Two classes 1 and 2: $p(x \mid 1) = \frac12$ on $[-1, 1]$ , $p(x \mid 2) = \frac14$ on $[0, 4]$ , priors $p(1) = \frac14$ , $p(2) = \frac34$ .

(5 points) Find the optimal classifier $q^*(x)$ , the one minimising the classification error. Write down the result.
(1 point) Compute the classification error $\varepsilon^*$ .
(6 points) The 1-NN classifier, asymptotic case: the training and test sets grow to infinity. Compute its error $\varepsilon^{NN}$ .

Definition first: write the formal definition of the task in (a).

Wrap-up

Solving an exam exercise

Write the definitions (what is given, what is the strategy, what is minimised).
Sketch the densities and the regions.
Formula first, then the numbers.
Check: errors in $[0,1]$ , densities integrate to 1, does the boundary move the right way?

Next week, 13. 11.

Test 2 at the start of the lab (12 points)
New assignment: the perceptron
Practise with the exercise book

Optional

Extra exercise and nearest neighbours today

Extra: ML and MAP, two-step density (Jan 2026)

$p(x) = a$ for $x \in [-1, 0]$ , $\ p(x) = b$ for $x \in (0, 0.5]$ , zero elsewhere. Training data: $K$ points in $[-1, 0]$ , $L$ points in $(0, 0.5]$ .

(1 point) Constraints on $a, b$ so that $p$ is a density.
(2 points) The likelihood of the data.
(4 points) ML formulas for $a, b$ ; compute them for $\mathcal{X}_A = \{-0.1, 0.2\}$ and $\mathcal{X}_B = \{-0.8, -0.5, -0.3, 0.3\}$ .
(6 points) Prior $P(a) = 4a^3$ , $0 \le a \le 1$ . MAP formulas for $a, b$ ; compute them for the same sets.

Definition first: write the definitions of the ML and the MAP estimate.

k-NN is everywhere in modern models

Learned features + k-NN: self-supervised encoders (e.g. DINO, DINOv2) are evaluated by k-NN on their embeddings, with no classifier trained.
Retrieval: image and text search (e.g. with CLIP embeddings) is nearest-neighbour search with the cosine distance.
Approximate search at scale: billions of vectors, so exact k-d trees are replaced by graphs (HNSW) and compressed codes (product quantisation), e.g. in the FAISS library.
Retrieval-augmented language models look up the nearest documents before answering.

The hard part moved from the classifier to the metric: a good embedding makes plain k-NN work.

Exercise lab I

Warm-up: logistic regression

What does the kkk in σ(k w⊤x)\sigma(k\,\mathbf{w}^\top \mathbf{x})σ(kw⊤x) do?

Recap: how do we score w\mathbf{w}w on the training data?

Three students, three margins

Separable vs. overlapping: where is the minimum?

Halfway through the labs

Where to find exam questions

Test 1: feedback

How did test 1 go?

Definitions: what is the Bayesian task?

Quick check: risks and errors

Maximum likelihood: light bulbs

E1: how long do light bulbs live?

E1: the test stops early

Recap: the exponential distribution

Where does E[T]=θ\mathbb{E}[T] = \thetaE[T]=θ come from?

Before (b): a bulb that is still on

Parzen windows and Neyman–Pearson

E2: two classes, few points

Bayes with Gaussians and a "don't know"

E3: two Gaussian classes

Recap: the multivariate normal

Recap: Bayes with a reject option

Recap: when is "don't know" the best answer?

Nearest neighbours

Which class is the new point?

k-NN: pros and cons

Quick check: k-NN

Where does 1-NN say class 1?

Finding the nearest neighbour fast: k-d tree

How fast can we find a median?

Condensation: keep only the points that matter

Condensation on an example

Editing: remove the points that mislead

Editing on the same example

E4: optimal classifier and 1-NN (exam, Jan 2025)

Wrap-up

Extra exercise and nearest neighbours today

Extra: ML and MAP, two-step density (Jan 2026)

k-NN is everywhere in modern models

What does the $k$ in $\sigma(k\,\mathbf{w}^\top \mathbf{x})$ do?

Recap: how do we score $\mathbf{w}$ on the training data?

Where does $\mathbb{E}[T] = \theta$ come from?