Bayes Classifiers and Detection

A faint echo hides in radar noise. One rule, pick the class with the largest prior times likelihood, makes fewer mistakes than any other classifier can. Turn the knobs and watch its error fall.

Pull the echo strength up and the number of samples up, then press Draw a trace. Watch the error rate, and the decision the rule makes. Then we build the rule piece by piece: the posterior, the theorem, a constant, a change in variance, a known waveform, and signals whose samples are correlated.

You need Bayes rule (how to update a probability after you see evidence) and the bell curve. We build the rest from zero.

Based on Lecture 6 of Stanford EE269: Signal Processing for Machine Learning, taught by Mert Pilanci, here our Lecture 14. Lecture slides and the course slide index. Every idea is re-taught here in our own words and devices. It follows Lecture 13, Cepstrum and MFCC.

Listen for the echo

0.40
8
50%

Illustrative setup, the lecture’s Gaussian detector (slide 9): every sample is noise with spread 1, plus a constant echo of the strength you set when an echo is present. The curves and the error rate are exact for the best rule; the traces are real random draws in your browser, and the tally counts your own draws.

Chapter 0

Why Ask for the Best Classifier

Meet a radar that must decide, and see why some mistakes can never be removed

A radar station sends out a pulse and listens. Every second it records a short list of numbers, the samples of what came back. Most seconds the list is pure static. Some seconds a faint echo from an aircraft is buried in that static.

The station must decide, for each list, whether an aircraft is there. If it says yes to static, it wastes a response. If it says no to an echo, it misses a plane. Either way the decision is a guess, because the same list could come from both worlds.

This lecture asks one clean question about that guess. Of all the rules anyone could write, which one is wrong least often? The answer is a formula with a proof, and it is short. The rest of the lecture applies the formula to signals: a constant, a change in loudness, a known shape, and signals whose samples lean on each other.

Words for the setup

A feature vector is the list of numbers the classifier sees. The lecture writes it x[n], a list of N samples, so x lives in RN. A class label y says which world produced x. Here y takes one of k values, 1 up to k. For the radar, k is 2: y = 1 means noise only, y = 2 means echo plus noise.

A classifier is any function f that takes x and returns a label. It reads N numbers and answers with one of k classes. The rule can be a threshold, a neural network or a coin flip. The lecture wants to compare all of them at once.

Nature draws the pair (x, y) together from a joint distribution, written Pxy. Think of it as a machine that first picks a world and then generates a list of samples from that world. The classifier sees only the list. It never sees which world the machine picked.

Scoring a classifier by its mistakes

To compare rules we need one score. The lecture says the best classifier depends on the performance measure, and then picks the simplest measure: how often the rule is wrong. This is the risk, or probability of error.

R(f)
The risk of classifier f: the fraction of the time f gets the label wrong, if you ran the whole machine many times.
Pxy
The joint distribution. The probability counts both the random world and the random samples, because both change from run to run.
f(x) ≠ y
The event that the answer differs from the truth. Each such event is one mistake.

A worked number makes it concrete. Say the radar sees an echo in 3 seconds out of every 10, so a rule that always answers “static” is wrong 3 times in 10. Its risk is 0.3. A rule that listens at all can do better, and the device below shows how much better, and where it stops.

Draw your own boundary

Take the simplest case: one sample, x, not a list. In the noise world x is drawn from a bell curve centred at 0. In the echo world the bell curve is centred at 2. Both have spread 1. A rule that compares x with a cut point t says “echo” when x is above t. Move the cut point and watch the red area. Red marks the samples that get the wrong answer.

Place the cut point

Blue is the noise world, warm is the echo world. The curves are scaled by how often each world happens. Drag the cut point, or choose how rare echoes are, and watch the red area.

0.00

Illustrative: both curves have spread 1, centres 0 and 2. The risk is computed exactly from the bell curve’s tail area. The best cut point is found by scanning, and the next chapters derive it by hand.

With echoes in half the seconds, the best cut point sits at 1.00, halfway between the two centres, and the rule is wrong 15.9% of the time. Move off 1.00 in either direction and the risk rises. With echoes rare, the best cut point slides right to 2.10, because a high sample is now weaker evidence of an echo: echoes are rare to begin with.

Notice what never happens. No cut point reaches zero. The two curves overlap, so some samples are possible in both worlds, and any answer to them is sometimes wrong. The lecture names the floor under every classifier the Bayes risk, and Chapter 1 gives it a definition.

Where the lecture goes

Lecture 6 of EE269 was given on 9 January 2019 by Mert Pilanci, and it opens the course’s run of detection problems. It runs 28 slides: the definition of the best classifier and its theorem, then four detection problems that each end in a short rule. The lecture ends by showing why, for one family of signals, that rule is a Fourier transform in disguise. Here we walk the slides in order. The lesson before this one is Cepstrum and MFCC, and distance classification is a gentler neighbour. No earlier lesson is required.

  1. Posteriors and Bayes risk: prior, class density, posterior, and the floor on error.
  2. The Bayes classifier: the theorem, proved one point at a time.
  3. A constant in noise: the sum of the samples is the whole story.
  4. A change in variance: the sum of squares is the whole story.
  5. A known waveform: the matched filter, a dot product with the shape.
  6. Correlated signals: the multivariate Gaussian and the question it raises.
  7. The inversion lemma: a clean rule from an ugly one.
  8. Filtering in the eigenbasis: a gain for each direction.
  9. Circulant covariances: the eigenbasis is the Fourier basis.
  10. Field guide: every rule on one page.
Two bell curves overlap. Why can no classifier reach a risk of zero?

Chapter 1

Posteriors and the Floor Called Bayes Risk

Turn a sample into the probability of each world, and name the error no rule can beat

You are the radar operator again. A sample arrives with the value 1.5. You know two things before you look at it: how often echoes happen, and what an echo sample usually looks like. Now you must combine them into one belief. How likely is it that this 1.5 came from an echo?

That belief has a name and a recipe. The recipe is Bayes rule, and the lecture builds three named pieces to feed it. Each piece answers a different question, so keep them apart.

Three pieces, three questions

The prior answers: how common is each world, before I look at the sample? The lecture writes it πk = Py(y = k), one number for each class k. The priors are non-negative and add up to 1. An analogy: the prior is the weather forecast before you glance out of the window.

The class conditional distribution answers: if the world is k, how likely is this sample? The lecture writes it gk(x) = Px|y=k. For the radar, g1 is the bell curve of pure static and g2 is the bell curve of static plus echo. For a continuous sample, gk(x) is a density: a bigger value means samples near x are more common in world k.

The posterior answers the question we actually care about: given this sample, how likely is each world? The lecture writes it ηk(x) = Py=k|x(y = k | x). It is the forecast after you looked out of the window. Because the sample must have come from some world, the posteriors add up to 1 for every x, a fact the slide notes in a line of its own.

ηk(x)
The posterior: the probability of class k after seeing x. Always between 0 and 1.
πk gk(x)
How much of the world’s probability sits in the pair “class k and this sample”: the prior times the likelihood.
Σj πj gj(x)
The same quantity added over every class: the total probability of seeing x at all. It makes the posteriors add up to 1.

Slide 5 of the deck writes the two-class case with the labels −1 and +1, and the numerator with the words “Bayes rule” beside it. Its example is the one we are about to play with: two Gaussians, one for each label.

One worked number, step by step

Let x given y = −1 be a bell curve centred at 0 with spread 1, and x given y = +1 centred at 2 with spread 1. Take the sample x = 1.5. The densities are g−1(1.5) = 0.1295 and g+1(1.5) = 0.3521. The sample sits half a spread from the +1 centre and one and a half from the −1 centre, so +1 explains it better.

First suppose the priors are equal, 0.5 each. The numerators are 0.5 × 0.1295 = 0.0648 and 0.5 × 0.3521 = 0.1760. Their sum is 0.2408. So η+1(1.5) = 0.1760 / 0.2408 = 0.731, and η−1(1.5) = 0.269.

Now suppose +1 is rare, with prior 0.2, and −1 has 0.8. The numerators become 0.2 × 0.3521 = 0.0704 and 0.8 × 0.1295 = 0.1036. Their sum is 0.1740, so η+1(1.5) = 0.405. The same sample now leans toward −1. The sample did not change. The prior did, and it moved the belief across the 50% line.

The floor on error

Now return to the risk from Chapter 0. Among every classifier f you could write, some has the smallest risk. The slide gives it a name and its symbol: the Bayes risk R*, the smallest risk of any classifier. A classifier that reaches it, R(f) = R*, is called a Bayes classifier.

Two facts about R* are worth holding on to. First, it is a property of the problem: the priors and the class densities fix it, before you choose any rule. Second, it is zero only if the worlds never overlap. In the radar story R* measures how confusable echo and static really are.

Read the posterior

Top: prior times density for each class. Middle: the posterior of class +1. Bottom: the split at your probe. Slide the probe along x, then change how wide the +1 curve is and how common +1 is.

1.50
1.00
50%

Illustrative: class −1 is a bell curve at 0 with spread 1, class +1 is a bell curve at 2 with the spread you choose, as in slide 5. The densities and posteriors are computed exactly from the formula above.

Try the spread slider. Widen the +1 curve to 2 and something odd appears: the posterior of +1 starts high on the far left, dips below 50% near the middle, and climbs again on the right, so it crosses the 50% line twice. The classifier now says “+1” far to the left as well, because a wide curve is the more likely source of a far-out sample. A single cut point can never do that. The Bayes classifier can, because it follows the posterior wherever it goes.

Bring the prior of +1 down to 5% and the +1 region shrinks to a sliver. A rare class needs very strong evidence to win. That is the correct behaviour, and it is also why a classifier trained on lopsided data can seem blind to the rare class: its prior is doing exactly what Bayes rule says.

A sample is typical of rare class B (its density is high) but class A is nine times more common. What decides which class the posterior favours?

Chapter 2

The Bayes Classifier Picks the Largest Weighted Density

Prove, one sample at a time, that no other rule can make fewer mistakes

Imagine a courtroom with a rule: at each sample, the judge must name the single most probable world. A rival judge may use any other method at all, a clever neural network, a trained intuition, a lookup table. Slide 6 states a theorem: the first judge is never beaten. Not on average, not on any sample.

The proof is short, and it is worth reading line by line, because it is the engine of the whole lecture. Every detector in the later chapters is this one line applied to a different pair of densities.

The theorem

Here is the statement. The classifier f*(x) that returns the class with the largest posterior is a Bayes classifier. Because the posterior has the shape πk gk(x) divided by a total that is the same for every class, the largest posterior and the largest πk gk(x) pick the same class.

f*(x)
The Bayes classifier: a rule that maps a sample x to one class label.
arg maxk
“The k that makes the expression after it largest.” It returns the winning label, not the winning value.
ηk(x)
The posterior of class k. The first form: pick the most probable class.
πk gk(x)
Prior times density. The second form drops the common total, so you never have to compute it.

The proof, in three moves

Move one. Fix a single sample x and ask: if some classifier answers f(x) here, how likely is that answer to be wrong? It is right with probability ηf(x)(x), the posterior of the class it named. So it is wrong with probability 1 − ηf(x)(x).

Move two. The total risk is the average of that wrong-probability over every x the world can produce. The classifier chooses its answer at each x on its own, with no link between different x. So we can minimise the average by minimising the wrong-probability at each x separately.

Move three. At each x, the wrong-probability is smallest when the named class has the largest posterior. That is the arg max. Any classifier that names a different class at some x pays a higher wrong-probability there, and so cannot beat f*. The best achievable risk is the average of 1 − maxk ηk(x). That average is R*.

A worked case with three classes

Let three worlds A, B and C produce bell curves of spread 1 centred at −2, 0 and 2, with priors 0.5, 0.3 and 0.2. A sample arrives at x = 0.8. The densities are 0.0079 for A, 0.2897 for B and 0.1942 for C.

Multiply by the priors. A gives 0.5 × 0.0079 = 0.0040. B gives 0.3 × 0.2897 = 0.0869. C gives 0.2 × 0.1942 = 0.0388. The largest is B, so f*(0.8) = B. We never needed the total.

If you do want the posteriors, the total is 0.0040 + 0.0869 + 0.0388 = 0.1297. Then ηB = 0.670, ηC = 0.299 and ηA = 0.031. Answering B is wrong 33.0% of the time at this sample. Answering C would be wrong 70.1% of the time. The theorem says B is the least bad choice at this x, and it is.

Try to beat the Bayes rule

Each curve is prior times density for one class. The coloured strip under them shows which curve is highest: the Bayes regions. Drag the rival slider to slide every boundary away from where Bayes puts it. Then change the priors.

0.00

Illustrative: classes A, B, C are bell curves with spread 1 centred at −2, 0 and 2. Risks come from numerically adding the part of each curve that the classifier labels with another class (steps of 0.02 on the x axis). The rival uses the Bayes rule applied at x minus the shift, so all its boundaries move together.

Park the rival shift at 0 and the rival is the Bayes rule, so both risks match. Push the slider either way, and the rival’s risk rises above the Bayes risk. It never dips below it, whatever the priors. That is the theorem, felt: you are trying a family of rivals and none of them wins.

Notice also how the priors move the Bayes regions. Make C common and the strip gives C a wider stretch. A rare class gets a narrow stretch, because its curve is scaled down. The regions are not halfway points between the centres. They sit where the weighted curves cross.

Why the total can be ignored

The total Σj πj gj(x) is the probability density of the sample itself. At one x it is a single positive number, the same for every class. Dividing every candidate by the same positive number cannot change which candidate is largest. This is why the later chapters keep only the numerators, and why they can take logarithms freely: a logarithm preserves order.

Why can the Bayes classifier ignore the total probability of the sample, p(x), when it compares classes?

Chapter 3

Detecting a Constant Hidden in Noise

Derive the simplest detector from the theorem, and see that adding up the samples is the whole answer

The radar sends a steady pulse. If an aircraft is there, every sample of the return is lifted by the same small amount, call it μ. If not, the samples have no lift. Either way each sample is also shaken by random static. Eight samples might read 0.7, −0.2, 1.1, 0.4, −0.5, 0.9, 0.3, 0.2. Is there a lift?

Chapter 2 gave us the method: write the two class densities, multiply by the priors, compare. This chapter does the algebra once, slowly, on the lecture’s first example. Slide 7 sets it up. The slides after that supply the formulas and the answer.

The two worlds

In class 1 (noise only) each of the N samples is a draw from a bell curve centred at 0 with variance σ². In class 2 (signal plus noise) each is a draw from a bell curve centred at μ, with the same variance. The slide says i.i.d., meaning independent and identically distributed: each sample is drawn on its own, from the same curve, so what one sample reads tells you nothing about the next. The priors are π1 and π2. The lift μ is known, an assumption we will later relax.

Because the samples are independent, the density of the whole list is the product of the density of each sample. This is slide 8: g1(x) is the product over i of a bell curve at 0, and g2(x) is the same with μ subtracted inside the exponent.

The algebra, line by line

The theorem says to answer class 2 when π1 g1(x) < π2 g2(x). Products are awkward, so take the natural logarithm of both sides. A logarithm keeps the order, and it turns the product of N bell curves into a sum. The constant in front of each bell curve is the same in both worlds, so it cancels and drops out.

What is left is a comparison of two sums of squares: ln π1 minus Σxi² / 2σ², against ln π2 minus Σ(xi − μ)² / 2σ². Move the two squares to one side. Expand (xi − μ)² = xi² − 2μxi + μ². The xi² terms cancel exactly, and we are left with a result that depends on the samples only through their sum.

μ
The known lift of the echo, the same for every sample.
Σ xi
The sum of all N samples. This is the statistic: the one number the rule needs from the list.
σ² log(π1/π2)
The prior’s push. It is zero for equal priors, positive when noise is more common, negative when echoes are.
Nμ²/2
Half the total echo energy. With equal priors it puts the cut halfway between the two world means.

This is slide 9. Read it as a plain recipe: add up all the samples, multiply by the known lift, and compare with a number you can compute before the data arrive. The rule is a threshold on a sum. All the intelligence is in where the threshold sits.

Evidence adds up one sample at a time

There is a nicer way to see the same result. Divide through by σ². Each sample contributes μ(xi − μ/2)/σ² to a running total called the log-likelihood ratio, the logarithm of how many times more likely the list is under class 2 than under class 1. A sample above μ/2, the halfway point between the two means, adds positive evidence for an echo. A sample below it subtracts. The rule says: answer echo when the running total passes ln(π1/π2).

Add up the evidence

Top: the samples as they arrive. Bottom: the running evidence for an echo, against the purple bar the rule must pass. Choose the truth, press Draw a trace, and watch the total climb or wander.

24
0.50

Illustrative: noise spread σ = 1. Each sample adds μ(x − μ/2) to the total, which is the slide-9 rule divided by σ². The expected error with equal priors is the exact Q-function value shown in the read-out; one trace is one random draw.

How good can it be? A number

Put in numbers. Let σ = 1 and μ = 0.5, with equal priors. The rule says answer echo when the sum passes Nμ/2. For N = 16 that is 4. The sum has spread σ√N = 4. In the noise world its centre is 0, which is one spread below the bar. In the echo world its centre is Nμ = 8, one spread above. Each mistake is a one-spread tail, and the tail beyond one spread is 15.9%. So the error is 15.9%.

Now quadruple the samples to N = 64. The bar moves to 16, and the spread grows only to 8, since it grows with √N while the gap between centres grows with N. Each centre is now two spreads from the bar. The tail beyond two spreads is 2.3%. Four times the data cut the error from 15.9% to 2.3%. In general the error is Q(√N · μ / 2σ), where Q is the tail area of the bell curve. The knob √N μ / σ is the whole story.

Last, make echoes rare: π2 = 0.1. The prior’s push is σ² ln 9 = 2.20, so for N = 16 the bar moves from 4 to 4 + 2.20/0.5 = 8.39 on the sum. The rule demands much more evidence before it cries “echo”.

The echo strength stays the same and you collect four times as many samples. What happens to the Bayes error of the constant-in-noise detector?

Chapter 4

Detecting a Change in Loudness

When the average gives no clue, learn why the sum of squares is the statistic that decides

A microphone sits in a quiet room. Sometimes a machine switches on. The machine has no steady offset: its sound swings up and down around zero, just like the room does. It is only louder. The average of a few samples says nothing, because the swings cancel. How can you tell loud from quiet?

Chapter 3 would fail here. Its sum of the samples has the same centre, zero, in both worlds. Slide 10 sets the new problem up, and slides 11 and 12 apply the theorem and read off a different statistic.

The two worlds

In class 1 every sample is a draw from a bell curve centred at 0 with variance σ1². In class 2 it is a draw from a bell curve centred at 0 with a different variance σ2². Both variances are known. The samples are i.i.d. in each world. The slide labels class 1 “noise” and class 2 “signal plus noise”, and for this lesson we take σ2 larger than σ1: the machine adds loudness.

Variance is the average squared distance from the centre. A bigger variance means the samples swing wider. It is the quantity this problem is about, so a rule should look at how wide the samples swing, not at where they centre.

Derive it, line by line

Start from the theorem: answer class 2 when π1 g1(x) < π2 g2(x). Slide 11 writes the two densities. Each is a product of N bell curves, and this time the bell curves carry different spreads, so a spread-dependent factor 1/σ is left in each product. It does not cancel.

Take logarithms. For class 1 you get ln π1 − N ln σ1 − Σxi² / 2σ1², plus a constant that is the same in both worlds. For class 2 the same with σ2. Gather the terms with x on the left and the terms without on the right, and the rule appears.

(1/2σ1² − 1/2σ2²)
A positive number when σ2 > σ1. It says how much sharper the quiet world’s curve is. If class 2 were the quieter one, it would be negative and the inequality would flip.
Σ xi²
The energy of the list: every sample squared, then added. Big swings in either direction count the same.
log(π1/π2)
The prior’s push, as before: zero for equal priors.
(N/2) log(σ1²/σ2²)
A term from the 1/σ factors. It is negative when σ2 is larger, so it lifts the right side by N ln(σ2/σ1).

This is slide 12. The statistic is the energy Σxi². Squaring throws away the sign, so a swing up and a swing down both count as loudness. The rule is again a threshold on one added-up number. The number is just a different one.

A worked case

Let σ1 = 1 and σ2 = 2, with N = 8 and equal priors. The factor on the left is 1/2 − 1/8 = 0.375. The right side is 0 + 8 ln 2 = 5.545. So answer class 2 when Σxi² > 5.545 / 0.375 = 14.79.

Divide by N to get the average power per sample: 14.79 / 8 = 1.85. A quiet sample has power about 1, a loud one about 4, and the cut sits at 1.85, between them but closer to the quiet one. The cut is not at the midpoint 2.5, because the quiet curve is narrower, so it has less room for loud-looking values. With equal priors the average-power cut does not even depend on N: it is ln(σ2²/σ1²) / (1/σ1² − 1/σ2²) = 1.386 / 0.75 = 1.85 every time. More samples sharpen both curves around their own average power, and the cut stays put.

Count the energy

Each bar counts simulated lists. Blue lists come from the quiet world, warm from the loud one. The purple line is the Bayes cut. Switch to the plain average and watch the two piles land on top of each other.

12
2.0

Illustrative: quiet spread σ1 = 1, equal priors. Each press simulates 400 lists per world in your browser. The cut for average power is the slide-12 formula. For the plain average, no formula exists, so the device shows the best single cut it can find by scanning, which is the kindest possible test for that statistic.

With the power statistic, the two piles separate, and the error falls as you add samples. With the plain average they pile up at the same place: both worlds have a centre of zero, and the quiet world is only a little narrower. The best single cut errs about as often as a coin flip.

This is a general lesson of the lecture. The Bayes rule tells you which statistic carries the information. Chapter 3 needed the sum because the worlds differed in centre. This chapter needs the energy because they differ in spread. You do not guess the statistic. You derive it.

Two worlds have the same centre, 0, and different spreads. Which statistic of the N samples does the Bayes rule use?

Chapter 5

Detecting a Known Waveform: the Matched Filter

Learn why the best detector for a known shape is a dot product with that shape

A sonar sends out a short ping that rises and falls like a small burst of a single tone. The shape of the ping is known exactly: it is the sound the sonar itself made. The return, if there is a target, is that same shape, faint, with static on top. Where in the trace is it? Is it there at all?

In Chapter 3 the echo was a flat lift, the same μ at every sample. Now the echo has a shape that varies from sample to sample. Slide 13 states this: a known waveform s[n] in RN, and nothing else changes.

The two worlds

In class 1 every sample is static: a bell curve centred at 0, variance σ². In class 2 sample i is a bell curve centred at si, the i-th value of the known waveform, with the same variance. So class 2 is the waveform plus the same static. Slide 14 writes both densities, and the only change from Chapter 3 is that μ became si.

The same algebra, with s in place of μ

Take logarithms and compare, exactly as in Chapter 3. The xi² terms cancel. The cross terms no longer collect into a plain sum: each sample is multiplied by its own si. The leftover constants add up the squared waveform values.

⟨x, s⟩
The inner product (dot product): multiply sample i by si for every i, then add. It is large when x rises and falls where s does.
σ² log(π1/π2)
The prior’s push, zero for equal priors.
½ ‖s‖2²
Half the energy of the waveform: half of s1² + s2² + …. With equal priors it puts the cut halfway between the two typical values of the statistic.

This is slide 15, and slide 16 writes it as an inner product. The rule: compute the dot product of the trace with the known shape, and compare it with half the shape’s energy plus the prior’s push. The slide gives this rule its name: a matched filter, with the examples “face detector” and “DFT basis”.

Why a dot product is the right test

Think of x and s as two arrows in N-dimensional space. The dot product measures how far x points along s. If x is only static, it points in a random direction and the dot product is near zero, give or take noise. If x contains s, it points partly along s, and the dot product is near the energy of s. The cut sits between the two.

The word filter comes from running the dot product at every position in a longer trace: the same template slides along, and each position gives one number. That output is the trace passed through a filter whose weights are the template, flipped in time. Where the template lines up with a hidden copy of itself, the output peaks. A face detector does this in two dimensions: it slides a face template over an image. A DFT bin does it with a sine and cosine: it is a matched filter for one pure tone.

One worked example by hand

Let the waveform be s = (1, 2, −1), so ‖s‖² = 1 + 4 + 1 = 6, with σ = 1 and equal priors. The cut is half of 6, which is 3. Suppose the trace is x = (0.8, 2.5, −0.3). The dot product is 0.8 × 1 + 2.5 × 2 + (−0.3) × (−1) = 0.8 + 5.0 + 0.3 = 6.1. That is above 3, so we answer echo.

Another trace, x = (−0.4, 0.6, 0.5). The dot product is −0.4 + 1.2 − 0.5 = 0.3. That is below 3, so we answer noise. Under noise the statistic has centre 0 and spread σ‖s‖ = √6 = 2.45. Under echo it has centre 6 and the same spread. The cut at 3 is 1.22 spreads from each centre, so the error is the tail beyond 1.22 spreads, about 11.0%.

In general the distance between the two centres, in units of spread, is ‖s‖/σ. It is the signal to noise ratio in amplitude. The Bayes error with equal priors is Q(‖s‖ / 2σ). A longer or louder waveform has more energy, so it is easier to find. Its shape matters only through that energy.

Slide the template into place

Top: the true ping. Middle: the trace. Bottom: the detector’s statistic for noise only (blue) and for an echo (warm), with the best cut in purple. Choose a detector, raise the noise, and press Draw a trace.

1.2

Illustrative: a 64-sample ping, a tone with 8 samples per cycle under a bell-shaped window centred on sample 32. The detector gets its best possible cut for whatever template it uses (halfway between the two centres, equal priors); the error is the exact tail area. The matched template uses the slide-16 cut. The traces are real random draws.

Pick the matched template and push the noise up to 2. The ping is invisible in the trace, yet the two bell curves of the statistic are still apart, and the error is a few percent. Now pick the template late by 1 sample. The dot product shrinks by a factor of about 0.7, and the error rises. Late by 2 samples is a quarter of a cycle: the template is now at right angles to the ping, the dot product has centre 0 in both worlds, and the detector is a coin flip. The flat template does no better, since a ping that swings above and below zero adds up to nearly nothing.

That is the cost of a mismatch, and the reason the filter is called matched. The rule is optimal for the shape you give it, and only for that shape.

The waveform s doubles in amplitude, with the same noise. What happens to the matched filter’s error with equal priors?

Chapter 6

When the Samples Lean on Each Other

Meet the multivariate Gaussian and the covariance matrix, then set up detection for a signal that is correlated

So far each sample was drawn on its own. Real signals are not like that. A slow hum, a drifting temperature, a spoken vowel: if one sample is high, the next is probably high too. The samples lean on each other. A detector that treats them as independent throws that leaning away, and the leaning is often the very thing that separates the signal from static.

Slide 17 gives the tool for this: the multivariate Gaussian. Slides 18 to 20 use it to pose the detection problem. This chapter builds both, and ends with a question that Chapters 7 to 9 answer.

A bell curve for a whole list

One sample has a centre μ and a spread σ. A list of N samples needs more. It needs a centre for each sample, a vector μ, and a table that says how each pair of samples moves together. That table is the covariance matrix Σ, an N by N grid. Entry (i, j) is the average of how far sample i is from its centre times how far sample j is from its centre. A positive entry means they rise and fall together. A zero means they do not lean on each other.

P(x; μ, Σ)
The density of the list x under a Gaussian with centre μ and covariance Σ. This is slide 17.
1 / ((2π)N/2 |Σ|1/2)
The scale that makes the total probability 1. |Σ| is the determinant: a number for how big the cloud is. A wider cloud has a larger |Σ| and a lower, flatter peak.
(x − μ)T Σ−1 (x − μ)
How far x is from the centre, measured in units of the cloud’s own shape. It is small along the cloud’s long direction and large across it.

Look at the exponent. With Σ equal to σ² times the identity matrix, it collapses to the sum of squares over 2σ², the independent case of Chapters 3 to 5. With a general Σ the exponent is a quadratic form: a sum of squares and products of the samples, weighted by the inverse covariance. The inverse covariance is what makes a step along the cloud’s long direction cheap, and a step across it expensive.

The picture is a cloud of points shaped like a tilted oval. Its contours are ellipses of equal density. The long axis of the oval points along the direction where the samples rise together.

The detection problem

Slide 18 states the problem. In class 1 (noise) the list is N(0, σ²IN): independent static. In class 2 (signal plus noise) the signal is a random Gaussian list N(0, Σ), with correlation described by Σ, and independent static is added on top. Adding independent Gaussians adds their covariances, so class 2 is N(0, Σ + σ²IN). Both σ and Σ are known.

Notice what changed from Chapter 4. There, both worlds were round clouds of different size. Here, class 1 is a round cloud and class 2 is a tilted oval. The signal has no fixed values; it is a random wiggle with a known leaning pattern.

The setup, and a worked case

Slide 19 writes the two densities. Slide 20 applies the theorem. The log of each density is a constant plus −½ times a quadratic form, so the rule compares two quadratic forms, and a constant that holds the determinants.

Try two samples. Let Σ = [[1, 0.8], [0.8, 1]] and σ² = 0.5. Then Σ + σ²I = [[1.5, 0.8], [0.8, 1.5]], with determinant 1.5² − 0.8² = 1.61. Its inverse is (1/1.61) [[1.5, −0.8], [−0.8, 1.5]].

Take x = (1, 1), where the two samples agree. The class 2 quadratic form is xT(Σ + σ²I)−1x = 1.4 / 1.61 = 0.870. The class 1 form is xTx / σ² = 2 / 0.5 = 4. The log densities are −3.145 for class 1 and −2.510 for class 2, so class 2 is more likely: the log ratio is +0.63. Now take x = (1, −1), which has the same length but the samples disagree. The class 2 form is 2.857, the log density −3.504, and the log ratio is −0.36. Now class 1 wins. Same length, opposite verdict. A detector that looks only at length could not tell them apart.

See the tilted cloud

Each dot is a list of two samples. Blue dots are noise only, warm dots are signal plus noise. The tint shows where the Bayes rule says “signal”. Raise the correlation and watch the signal cloud tilt and stretch.

0.80
0.50

Illustrative, two samples so the cloud fits on a page: Σ = [[1, ρ], [ρ, 1]], equal priors. 250 dots per world are drawn in your browser; the tint is the slide-20 comparison evaluated at every pixel; the error rate counts the dots on the wrong side.

With a correlation of 0, the signal cloud is a round cloud like the noise cloud, only a little bigger, and the error is large. Raise the correlation and the oval stretches along the diagonal and shrinks across it. The tint grows out along the diagonal first: a dot far out on the diagonal is called signal, while a dot the same distance out across the diagonal is still called noise. The covariance is information, and the Bayes rule spends it.

The tint also shows that the “signal” region is not a half-plane cut by a line. It is the outside of an ellipse: a small hole around the centre is called noise, and everything beyond it, favouring the diagonal, is called signal. The next chapter asks whether the rule has a cleaner form than slide 20’s two inverses.

The signal is N(0, Σ) and independent static N(0, σ²I) is added. What is the covariance of the class 2 samples?

Chapter 7

The Inversion Lemma Cleans the Rule

Trade two matrix inverses for one, and see the rule as a signal estimate dotted with the data

Chapter 6 ended with an unwieldy rule: compare two quadratic forms, each with its own matrix inverse. You can compute it, but you cannot see it. What does it do to the data? Is it a filter, a projection, an average? A rule you cannot see is a rule you cannot trust or improve.

Slides 21 to 23 clean it up with one algebraic identity. The result has a form you can read.

Where we left off

Slide 20 reached this comparison. Answer class 2 when the first line is smaller than the second:

log π1 − ½ xT(σ²I)−1x < −½ xT(Σ + σ²I)−1x + log π2 + constant

The constant holds the two determinants. The x enters through two quadratic forms with two different inverses. Move both forms to one side and you get one form with the difference of the two inverses: (σ²I)−1 − (Σ + σ²I)−1. Slide 21 asks: can that difference be written more simply?

The matrix inversion lemma

Slide 21 states an identity for the inverse of a sum of two matrices, when A is invertible:

(A + B)−1 = A−1 − A−1(I + BA−1)−1BA−1

You can check it in the scalar case, where everything commutes. With A = a and B = b, the right side is 1/a − (1/a)(1 + b/a)−1(b/a) = 1/a − b/(a(a + b)) = (a + b − b) / (a(a + b)) = 1/(a + b), which is the left side. The matrix identity has the same shape. The lemma lets you express the inverse of a sum through the inverse of one part, which is exactly what we want, since (σ²I)−1 is just I/σ².

Apply it, step by step

Put A = σ²I and B = Σ. Then A−1 = I/σ². Compute the middle piece: I + Σ/σ² = (σ²I + Σ)/σ², whose inverse is σ²(σ²I + Σ)−1. Plug into the lemma:

(Σ + σ²I)−1 = I/σ² − (I/σ²) · σ²(σ²I + Σ)−1 · Σ/σ² = I/σ² − (σ²I + Σ)−1Σ/σ²

Move the I/σ² to the left side. This gives slide 22’s line, the difference of the two inverses:

(σ²I)−1 − (Σ + σ²I)−1
The difference of the two inverses that appear in the rule: the noise world’s inverse minus the signal world’s.
1/σ²
A positive scale. It only changes the size of the threshold, not the shape of the rule.
(σ²I + Σ)−1 Σ
The matrix that matters: the signal covariance, shrunk by the total covariance. It is the gain that Chapter 8 will take apart.

Now put it back into the comparison. Collect the x terms: the rule says answer class 2 when ½(1/σ²) xT(σ²I + Σ)−1Σx is greater than log(π1/π2) plus the determinant constant. Multiply by 2σ² and you reach slide 23’s form: xT(σ²I + Σ)−1Σx > a threshold. The threshold is 2σ² log(π1/π2) + σ² log|I + Σ/σ²|.

One honest note. The slide prints the threshold as σ² log(π2/π1) plus a constant. Our line differs in the factor of 2, and in the order of the prior ratio. We checked it by hand in the one-sample case below and by computer in the device. The structure is the same: a quadratic form with the matrix (σ²I + Σ)−1Σ, compared with a number computed ahead of time.

One sample, to see it work

Take N = 1 so every matrix is a number. Let Σ = 3 and σ² = 1. Then Σ + σ² = 4, the gain is 3/4, and the log ratio is x²/2 × (3/4) minus half of ln 4, which is 0.375x² − 0.693. Compare with computing it directly: class 1 is a bell curve of variance 1, class 2 of variance 4, and ln g2 − ln g1 = −½ ln 4 − x²/8 + x²/2 = 0.375x² − 0.693. The two agree. With equal priors the rule says class 2 when x² > 1.85, the same cut Chapter 4 found for a change from variance 1 to variance 4. The change-in-variance detector was a special case all along.

Check the lemma by numbers

Left: the difference of the two inverses. Right: (1/σ²)(σ²I + Σ)−1Σ. Warm cells are positive, blue are negative. Press the button for a new random Σ and a new sample x, and change σ².

0.50

Illustrative: Σ = AAT/4 for a random 4 by 4 matrix A, so it is a valid covariance; the inverses and the determinant come from Gauss-Jordan elimination in your browser. The log ratio is computed once from the two Gaussian densities and once from the quadratic form of this chapter plus its constants.

The two heat maps are the same to about fifteen digits. The log ratio is the same both ways. Change σ²: the matrices change, the agreement does not. An identity holds for every input, and this is the check you can do on a computer when you do not trust your algebra.

Reading the clean rule

Now look at the quadratic form as two pieces. Let ŝ = Σ(σ²I + Σ)−1x. This is a classical formula, the best linear guess of the signal part of x, given that x is the signal plus the static. Because Σ and (σ²I + Σ)−1 commute, the quadratic form equals xTŝ, and the rule is that number compared with a threshold. The detector estimates the signal, then measures how well the estimate lines up with the data. This is the matched filter of Chapter 5, except that the template is not given: the data builds its own template, with the covariance telling it how.

What does the matrix inversion lemma let us do in the correlated-signal detector?

Chapter 8

Filtering in the Eigenbasis

Rotate the data into the covariance’s own directions, and the rule becomes a gain on each direction

Think of a graphic equaliser on a stereo. Sliders for bass, mid and treble let you turn up the parts of the sound you want and turn down the parts you do not. A good equaliser for a hiss-covered recording would turn each slider by how much music and how much hiss lives in that band.

Chapter 7 left us with a rule built on one matrix, (σ²I + Σ)−1Σ. It still looks like a tangle of numbers. Slides 24 to 26 show that this matrix is an equaliser in disguise. Rotate into the right directions, and the tangle becomes one gain per slider.

The covariance has favourite directions

The covariance matrix Σ is symmetric. Linear algebra says a symmetric matrix can be written Σ = UΛUT, an eigenvalue decomposition. The columns u1, …, uN of U are the eigenvectors: N directions at right angles to each other, the oval’s own axes. Λ is a diagonal matrix of eigenvalues λ1, …, λN. Eigenvalue λn is the variance of the signal along direction un. Slide 24 writes this as the sum Σ = Σn λn ununT.

In Chapter 6 the oval had two axes: the diagonal, with eigenvalue 1 + ρ, and the cross direction, with 1 − ρ. Along its long axis the signal is strong. Along its short axis it is weak. The eigenvectors name those directions, and the eigenvalues say how strong the signal is in each.

The substitution

Put Σ = UΛUT into the matrix. Since UTU = I, we can write σ²I + UΛUT = U(σ²I + Λ)UT. Its inverse is U(σ²I + Λ)−1UT, because the inverse of a product reverses the factors and UT is the inverse of U. Multiply by UΛUT: the inner UTU cancels, and slide 25 reads

xT(σ²I + UΛUT)−1UΛUTx = xTU (σ²I + Λ)−1Λ UTx

The middle matrix is now diagonal, so it is easy to read. It multiplies the n-th coordinate by λn/(λn + σ²).

A change of basis

Slide 26 gives the last step: let y = UTx. This is the same data written in the eigenvectors’ coordinates. Coordinate y[n] says how much of x points along un. It is a rotation: it keeps lengths, and only changes the axes you read them on. The statistic becomes a sum over directions:

yT(σ²I + Λ)−1Λy
The detection statistic from Chapter 7, now in the eigenbasis, where its matrix is diagonal.
Σn
Add over the N directions.
λn / (λn + σ²)
The gain of direction n: a number between 0 and 1. Near 1 when the signal is much stronger than the static in that direction, near 0 when it is much weaker.
|y[n]|²
The energy of the data along direction n.

The slide also writes this as a filter. Define yfiltered[n] = √(λn/(λn + σ²)) y[n]. Then the statistic is the plain energy of the filtered coordinates. The detector is: rotate to the eigenbasis, scale each coordinate, measure the energy.

A worked case

Take three directions with eigenvalues 4, 1 and 0.25, and noise variance σ² = 1. The gains are 4/5 = 0.8, 1/2 = 0.5 and 0.25/1.25 = 0.2. Suppose the data in the eigenbasis is y = (2, 1, 1). The plain energy is 4 + 1 + 1 = 6. The weighted statistic is 0.8 × 4 + 0.5 × 1 + 0.2 × 1 = 3.9.

Now suppose y = (0.5, 1, 2), the same set of numbers rearranged. The plain energy is 0.25 + 1 + 4 = 5.25, nearly the same as before. The weighted statistic is 0.8 × 0.25 + 0.5 × 1 + 0.2 × 4 = 1.5, far smaller. The plain energy cannot tell these two traces apart. The Bayes statistic can. The first has its energy where the signal lives. The second has it where only static does.

Set the equaliser

Top: the signal’s variance in each of 12 directions (purple bars), the static level (blue line) and the gain each direction receives. Bottom: one trace’s energy before the gain (warm) and after it (purple). Move the static level and draw traces.

0.50

Illustrative: 12 directions with signal variances 8 e−0.55 n for n = 0 to 11, so the signal is strong in a few directions and faint in the rest. The error rates come from 600 simulated traces per world, each rule given its best single cut, equal priors. Traces are real random draws in your browser.

Raise the static variance and the gains of the weak directions fall to near zero first: the rule stops listening to directions where the signal is faint, because they only carry static there. Lower it, and every direction is passed at nearly full gain, which reduces the rule to plain energy, the simple detector. The weighted error is lowest, as the theorem promised. The plain energy rule does worse whenever the static is high enough to bury some directions. That gap is the value of knowing Σ.

The idea echoes through signal processing. Shrinking each coordinate by signal over signal plus static is the Wiener filter, the best linear way to pull a signal out of static, and Chapter 7’s ŝ is its output. Detection and denoising turn out to use the same gains.

In the eigenbasis, which directions does the Bayes statistic give the largest weight?

Chapter 9

Circulant Covariances: the Eigenbasis Is the Fourier Basis

See why, for signals whose statistics do not change with time, the best detector is a DFT with a gain on each bin

Chapter 8 left one price tag. To build the equaliser, you must find the eigenvectors of Σ. For N = 1,000 samples, that means decomposing a 1,000 by 1,000 matrix, which takes about a billion operations, for each new Σ. And you must store the matrix of eigenvectors, a million numbers.

Slides 27 and 28 show that for a very common kind of signal, you never have to. The eigenvectors are known in advance, they are the same for every such signal, and you already own the tool that applies them: the discrete Fourier transform.

A signal whose statistics do not drift

Think of a steady hum, a stretch of wind noise, or an engine at constant speed. Its statistics do not change over time. How strongly sample 5 leans on sample 8 is the same as how strongly sample 105 leans on sample 108. All that matters is how far apart the two samples are, three steps here. Such a signal is called stationary, and our next lesson treats it in full.

For the covariance matrix this has a clear consequence: entry (i, j) depends only on the distance |i − j|. Let s[n] be the covariance between two samples n steps apart. Then each row of Σ is the row above it, shifted one place along. To avoid a special case at the ends, the lecture wraps the list into a circle, so the sample after the last one is the first one. The matrix on slide 27 shows the pattern: the first row is s[0], s[1], s[2], …, s[2], s[1], and each later row is a wrapped shift. A matrix like this is a circulant matrix. The slide adds two conditions: Σij = Σji (symmetric), and s[N − n] = s[n], so samples n steps apart in either direction lean on each other equally.

The Fourier basis, tried on the matrix

Slide 28 introduces the Fourier basis: wk[n] = (1/√N) ej2πnk/N, for k = 0 to N − 1. Each wk is a pure tone that makes k full turns around the circle of N samples. It is a column of the DFT matrix, scaled to have length 1. (If the complex exponential is new, our DFT lesson builds it from zero: it is a cosine for the real part and a sine for the imaginary part.)

Now multiply the circulant matrix by a tone. Row i of Σ applied to wk gives a sum over j of s[(j − i) mod N] times the tone at j. Because the tone at j is the tone at i, turned by a fixed angle that depends only on j − i, you can pull the tone at i out of the sum. What is left is a sum over distances, s[n] times a tone at n, the same for every row. So Σwk equals a single number times wk. A vector that a matrix only rescales is, by definition, an eigenvector. The slide writes this as wkHΣ = S[k] wkH, where H means the transpose with complex conjugates.

wkH Σ
The tone, conjugated, applied to the covariance matrix.
S[k]
The eigenvalue for tone k. It is the DFT of the first row s[n]: S[k] = Σn s[n] cos(2πkn/N) for a symmetric s. This is the power spectrum of the signal: how much variance lives at frequency k.
wkH
The same tone again. The matrix did not turn it, only scaled it.

This closes the loop with Chapter 8. There U was a matrix we did not know; here it is the DFT matrix, and the eigenvalue λn is the signal’s power at frequency k. So y = UHx is just the DFT of the trace, divided by √N.

The optimal detector, in one sentence

Put it all together. For a stationary Gaussian signal in independent static, the Bayes detector takes the DFT of the trace, multiplies the power in bin k by S[k]/(S[k] + σ²), adds the results, and compares the sum with a threshold. It is a bank of frequency channels, each turned up where the signal has power and turned down where only static does. The cost is N log N operations with the fast Fourier transform, not N³.

Count the cost for N = 1,000. A dense eigendecomposition is about 109 operations. The FFT is about 1,000 × 10 = 104. That is a factor of 100,000 (illustrative operation counts, in order of magnitude only).

A worked case with four samples

Let N = 4 and the first row of Σ be (2, 1, 0, 1), so s[0] = 2, s[1] = 1, s[2] = 0. The matrix has rows (2,1,0,1), (1,2,1,0), (0,1,2,1), (1,0,1,2). The eigenvalues are S[k] = 2 + 2cos(πk/2) + 0, which is 4, 2, 0, 2 for k = 0, 1, 2, 3. Check k = 0, the all-ones tone: each row sums to 2 + 1 + 0 + 1 = 4, so Σ times the ones is 4 times the ones. Correct.

With σ² = 1 the gains are 4/5 = 0.8, 2/3 = 0.67, 0 and 0.67. Take the trace x = (1, 2, 1, 0). Its DFT is X = (4, −2j, 0, +2j), with powers 16, 4, 0, 4. The statistic is (0.8 × 16 + 0.67 × 4 + 0 + 0.67 × 4) / 4 = 4.53. The bin with S[2] = 0 gets gain 0: the signal has no power at that frequency, so it is ignored. We divided by N = 4 because the unitary DFT carries a factor 1/√N in each coordinate.

Check that tones are eigenvectors

Left: the 16 by 16 circulant matrix for a signal whose correlation falls off with distance. Right: its spectrum S[k]. Bottom: the tone k (blue) and the matrix applied to it (warm). Choose a tone and see that the two curves have the same shape.

0.70
2

Illustrative: N = 16 and s[n] = ρd, where d is the circular distance min(n, N − n). The wave drawn is the real part of the tone (a cosine). The matrix is applied to it by direct multiplication, not by the formula, so the two curves agreeing is a real check.

Slide the correlation decay to 0 and the matrix becomes the identity: every tone has the same S[k] = 1, so the signal is white, with equal power everywhere, and no frequency is special. Raise ρ and the spectrum piles up at low k, because slowly changing samples are strongly correlated. The detector then listens mostly to the low bins. Whatever the matrix, the warm curve is the blue curve scaled by S[k].

That is the end of the lecture’s argument. A detector for correlated signals looked like an N by N problem. For a stationary signal it is N separate one-number problems, one for each frequency, tied together by the DFT.

The covariance of a stationary signal is circulant. What does this make the eigenvectors, and what are the eigenvalues?

Chapter 10

Field Guide: Every Detector on One Page

Look up the rule for each problem, check your understanding, and see where to go next

The whole lecture is one theorem and five applications. The theorem says: at each sample, answer the class with the largest prior times density. The applications ask what that rule looks like when the densities are Gaussian. The answer is always a statistic, a number computed from the samples, compared with a threshold.

What changes from case to case is the statistic. A constant lift needs the sum. A change in loudness needs the energy. A known shape needs the dot product with that shape. A correlated random signal needs a quadratic form, and for stationary signals that form is a gain on each DFT bin. The prior only moves the threshold. The densities choose the statistic.

The rules and the numbers

Problem (slides)StatisticAnswer “signal” whenNumber to remember
Bayes classifier (6)πk gk(x) for each classk is the arg maxRisk R* is the floor, E[1 − max ηk]
Constant in noise (7 to 9)Σ xiμ Σxi > σ² ln(π1/π2) + Nμ²/2Error Q(√N μ / 2σ): N = 16, μ = 0.5, σ = 1 gives 15.9%
Change in variance (10 to 12)Σ xi²(1/2σ1² − 1/2σ2²) Σxi² > ln(π1/π2) − (N/2) ln(σ1²/σ2²)σ1 = 1, σ2 = 2: cut at power 1.85
Known waveform (13 to 16)⟨x, s⟩⟨x, s⟩ > σ² ln(π1/π2) + ½‖s‖²Error Q(‖s‖ / 2σ): s = (1, 2, −1), σ = 1 gives 11.0%
Correlated signal (17 to 23)xT(σ²I + Σ)−1ΣxAbove a threshold set by the prior and |I + Σ/σ²|One quadratic form after the inversion lemma
Eigenbasis (24 to 26)Σn λn/(λn + σ²) |y[n]|²Above the same thresholdEigenvalues 4, 1, 0.25 and σ² = 1 give gains 0.8, 0.5, 0.2
Circulant (27 to 28)Σk S[k]/(S[k] + σ²) |X[k]|²/NAbove the same thresholdEigenvectors are the DFT tones, eigenvalues S[k] the power spectrum

Pick the detector

Here is the lesson in one question. Choose a situation and read off the statistic, the cut, and the chapter that derives it.

Match the signal to its rule

Choose what you know about the signal. The panel writes the statistic the Bayes rule uses and a sample value from this lesson’s worked cases.

The values are this lesson’s worked examples: Chapter 3 (N = 16, μ = 0.5), Chapter 4 (σ1 = 1, σ2 = 2), Chapter 5 (s = (1, 2, −1)) and Chapter 9 (the four-sample circulant).

The core as code

Every detector is a few lines. The log-likelihood ratio is computed from the two densities, and the circulant case uses the FFT. The functions below take a trace x, the known parameters, and the priors, and return True for “signal”.

pythonimport numpy as np

def constant_in_noise(x, mu, sigma2, pi1, pi2):      # x: shape (N,)
    N = len(x)
    return mu * x.sum() > sigma2 * np.log(pi1 / pi2) + N * mu**2 / 2

def change_in_variance(x, s1, s2, pi1, pi2):         # s1 < s2 are variances
    N = len(x)
    lhs = (1 / (2 * s1) - 1 / (2 * s2)) * (x**2).sum()
    return lhs > np.log(pi1 / pi2) - (N / 2) * np.log(s1 / s2)

def matched_filter(x, s, sigma2, pi1, pi2):          # x, s: shape (N,)
    return x @ s > sigma2 * np.log(pi1 / pi2) + 0.5 * s @ s

def correlated_signal(x, Sigma, sigma2, pi1, pi2):   # Sigma: shape (N, N)
    N = len(x)
    C = sigma2 * np.eye(N) + Sigma
    q = x @ np.linalg.solve(C, Sigma @ x)             # x^T (s2 I + Sigma)^-1 Sigma x
    _, logdet = np.linalg.slogdet(np.eye(N) + Sigma / sigma2)
    return q > 2 * sigma2 * np.log(pi1 / pi2) + sigma2 * logdet

def circulant_signal(x, s_row, sigma2, pi1, pi2):    # s_row: first row of Sigma, shape (N,)
    N = len(x)
    S = np.fft.fft(s_row).real                         # eigenvalues = power spectrum
    X = np.fft.fft(x)                                  # shape (N,), complex
    q = (S / (S + sigma2) * np.abs(X)**2).sum() / N
    logdet = np.log1p(S / sigma2).sum()                # log |I + Sigma/sigma2|
    return q > 2 * sigma2 * np.log(pi1 / pi2) + sigma2 * logdet

The last two functions answer the same question. Build Σ from s_row as a circulant matrix and the two agree to rounding. The FFT version needs no matrix at all. All five return the decision with the shapes noted in the comments, and no learning step: the densities were given.

Checklist

Where it sits in the field

The Bayes classifier is the bar that learned classifiers are measured against. When the densities are Gaussian with a shared covariance, its boundary is a line, and learning that line from data is the Fisher discriminant. The support vector machine also learns a line, without assuming Gaussians. When the densities are not known, you estimate them, or you skip them and learn the boundary directly. The detectors of this lesson are the rare cases where the densities are known, and the answer is exact.

Keep going

The takeaway. The best classifier is not a design. It is a calculation: multiply each class’s prior by its density and take the largest. The densities decide what the rule does with the samples. A shifted centre becomes a sum, a wider spread becomes an energy, a known shape becomes a dot product, and a correlated signal becomes a gain on each Fourier bin.

The course is Stanford EE269, Signal Processing for Machine Learning, taught by Mert Pilanci. Its slides are on the course slide index; this lesson follows Lecture 6 (9 January 2019), and every explanation and device here is our own.

You must detect a known 200-sample chirp in Gaussian static, with equal priors. Which rule is Bayes optimal, and what sets its cut?

Now press Present or Teach and explain the lecture out loud, from memory: why no classifier beats the Bayes rule, how one line of algebra turns two densities into a sum, an energy or a dot product, and why the Fourier transform appears at the end. Then go back to the echo at the top and push it to the edge of what it can hear.

EE269 Lecture 14: Bayes Classifiers and Detection
The course site · Slide index · Lecture slides · Back to Gleams