Generative models and Naive Bayes

The two classifiers so far, k-NN and decision trees (Part 13), came from intuition. This lecture steps back and asks how modelling is done in general.

A model is built from training data and then judged on test data, which need not contain the same points. Two extremes show that some assumption is needed. If the test points were exactly the training points, memorizing would be enough, and that is of no use in practice. If the test data had nothing to do with the training data (study for physics, get examined on chemistry), no algorithm could learn anything useful. Something has to tie the two sets together.

The standard assumption is a probability distribution \(\mathcal{D}\) over \(\mathcal{X}\times\mathcal{Y}\). Here \(\mathcal{X}\) is the feature space, for example \(\mathbb{R}^d\) with \(d\) features, and \(\mathcal{Y}\) is the label set: \(\{+1, -1\}\) (or \(\{0, 1\}\)) for classification, \(\mathbb{R}\) for regression. Every training pair is drawn from \(\mathcal{D}\), and so is the test pair.

This is the box from the estimation lectures (Part 8), except that each press now produces a feature vector together with its label. The mechanism inside can be as complicated as it likes. The hope is that a model which captures \(\mathcal{D}\) well from the training data will predict well on the test data.

To get an actual algorithm, we add structural assumptions about \(\mathcal{D}\) 7:31. Different assumptions lead to different algorithms, and there are two main schools of thought about which kind to make. The discussion uses classification, but the same ideas apply to other supervised problems.

A distribution over features and labels attaches a number \(P(\mathbf{x}, y)\) to every feature vector and label: a probability when the features are discrete, a density when they are continuous (for continuous features every single point has probability 0, so a density is the useful object). The two schools differ in what they model.

The Bengali example L45 · 12:13

The task is to listen to a spoken sentence and decide whether it is Bengali. The lecturer chose Bengali because he cannot speak or write it.

• A generative modeller says: model how Bengali sentences are produced (the features \(\mathbf{x}\)) together with the labels.
• A discriminative modeller says: the goal is only to tell Bengali from non-Bengali, and that does not require knowing how to produce a Bengali sentence. Model \(P(y \mid \mathbf{x})\) and nothing else.

The lecturer, with no Bengali, can still do reasonably well at telling the two apart. A native speaker has a mental model of how Bengali sentences are generated and will ace the same task 16:07. Knowing the generative process makes discrimination easy. If the lecturer forced a made-up generative model of Bengali on himself, though, it would mislead him.

If you have good reason to believe you know how the features are generated, use a generative model. If you don't, a wrong generative model hurts even the discrimination task, so stick to a discriminative one.

There is no single answer. Both kinds are useful, and many of the algorithms in this course are discriminative 17:08.

Both algorithms from Part 13 have a model: for a decision tree it is the tree, for k-NN it is the entire data set. Neither says anything about how the features \(\mathbf{x}\) were generated. Each only says how to get a label once \(\mathbf{x}\) is given, so both are discriminative.

Where is the probability? A deterministic rule is a trivial \(P(y \mid \mathbf{x})\) that only takes the values 0 and 1:

Any deterministic map from the input (feature) space to the output (label) space is of this form, so it falls under modelling \(P(y \mid \mathbf{x})\). Probability is a generalization of deterministic decision making. The next lectures build the first algorithm on a generative assumption 22:55.

The setting is binary classification, except that the features are now binary too.

The motivating application is spam classification. Some emails in the data set are tagged spam (label 1), the rest not spam (label 0). Emails are unstructured: different lengths, different words. The algorithms need a fixed-length vector, so each email must be encoded with the same \(d\) for some fixed \(d\), possibly large.

One encoding is to let \(d\) be the number of words in a dictionary (say 10,000) and give each word one component. An email gets a 1 in the component of every word it contains and 0 everywhere else.

This is one way to build features, not the only one; good features depend on the problem at hand. It is simple enough to explain the algorithm, and it does reasonably well in practice.

A generative model must give a probability to every (email, label) pair. The pair ("hello how are you", spam) might get 0.01, and ("hello how are you", not spam) gets its own number. Instead of guessing the joint directly, use one of its two factorizations:

What we finally need is \(P(y \mid \mathbf{x}_{\text{test}})\). If it is 0.9 for spam we predict spam; if it is 0.05 we predict not spam.

• Route 1, \(P(\mathbf{x})\,P(y \mid \mathbf{x})\). This already contains an assumption about how the label depends on the email, which is all prediction needs. Modelling \(P(\mathbf{x})\) on top gains little, so this route might as well be a discriminative model.
• Route 2, \(P(y)\,P(\mathbf{x} \mid y)\). \(P(y)\) says how often spam occurs; \(P(\mathbf{x} \mid y)\) says what spam emails look like and what non-spam emails look like. This is the more meaningful assumption, because we may well have some idea of how the emails in each class are distributed. The lectures take this route 11:30.

A generative model comes with a generative story: a random procedure that produces each data point. You can tell your own story; this is the first one the lecture tries.

1. Story 1: generate the i-th data point
2. Decide the label. Toss a coin with \(P(y_i = 1) = p\). Heads means this point will be a spam email (we do not know the email yet, only its type).
3. Decide the features using the label. Draw \(\mathbf{x}_i\) from \(P(\mathbf{x} \mid y_i)\).
4. Repeat \(n\) times to get the training set.

To make step 2 concrete, take a dictionary of \(d = 3\) words. Each word is either in the email or not, so there are only \(2 \times 2 \times 2 = 8\) possible emails, from 000 (none of the words, an empty email) to 111 (all three).

In the spam room sits an imaginary eight-faced die, one face per possible email. Unlike a fair die, its faces have different probabilities, unknown to us but fixed, and they sum to 1. Rolling it gives the email. The non-spam room has a different die with the same eight faces and different probabilities; some faces may even have probability 0 there 19:41.

Why two dice? An email containing "lottery", "money", "dollar" and "reply immediately" has the same encoding in both rooms, but that face comes up more often on the spam die. It can still come up on the non-spam die (someone in the lottery business may get such mail), only less often 21:20. The coin fixes \(P(y)\) and the dice fix \(P(\mathbf{x} \mid y)\); multiplying them gives \(P(\mathbf{x}, y)\) for every pair.

To learn this model from data we must estimate every number that determines it. With all of them known we control the generating process completely, so we could generate new \((\mathbf{x}, y)\) pairs and compute \(P(y \mid \mathbf{x}_{\text{test}})\) for any test email.

• The coin: one parameter, its bias \(p\).
• The spam die: \(2^d\) faces (8 for \(d = 3\), 16 for \(d = 4\)). The faces are mutually exclusive and exactly one shows up, so their probabilities sum to 1. Fixing \(2^d - 1\) of them determines the last one, leaving \(2^d - 1\) free parameters.
• The non-spam die: another \(2^d - 1\), since its numbers can be completely different.

Even a moderate dictionary has 10,000 words, which means on the order of \(2^{10{,}000}\) parameters. That is astronomical, far beyond what even modern GPUs could learn.

Ask two things of any generative model. Is it a reasonable explanation of the data? Is it reasonable enough that we can actually learn under it?

Story 1 may well pass the first test, but it fails the second unless \(d\) is tiny, and in spam classification \(d\) is large. So the story has to change, to one with far fewer parameters 29:40.

One parameter for the label coin is manageable, so step 1 stays. The trouble was the \(2^d\)-faced die in step 2. The new story replaces each die by \(d\) coins, one per word.

• Spam room: coins with probabilities \(p^{1}_{1}, p^{1}_{2}, \dots, p^{1}_{d}\).
• Non-spam room: coins with probabilities \(p^{0}_{1}, p^{0}_{2}, \dots, p^{0}_{d}\).

Notation: in \(p^{y}_{j}\) the superscript is the label (which room) and the subscript is the word. \(p^{1}_{j}\) is the chance that word \(j\) appears in a spam email.

1. Story 2: generate the i-th data point
2. Toss the label coin (bias \(p\)). Heads: go to the spam room. Tails: go to the non-spam room.
3. In room \(y\), toss each of the \(d\) coins. If coin \(j\) falls heads, word \(j\) is in the email (\(f_j = 1\)); if tails, it is not (\(f_j = 0\)).
4. Come out and repeat for the next point.

For example, the spam email 011 arises when the word-1 coin falls tails and the word-2 and word-3 coins fall heads 3:39. Two sets of coins are needed for the same reason as two dice: if word 1 is "lottery", its spam coin might have \(p^{1}_{1} = 0.8\) while its non-spam coin has only \(p^{0}_{1} = 0.1\).

The count is now one coin for the label plus \(d\) coins in each room:

\(2d + 1\) is exponentially smaller than \(2^{d+1} - 1\). Twenty thousand parameters is manageable; \(2^{10{,}000}\) is not 7:10.

What do we lose? Suppose the label coin says spam and the "lottery" coin falls heads, so the email contains "lottery". Does that change the chance that "money" also appears? Intuitively yes: a spam email that mentions a lottery probably mentions money too. Under story 2 it does not, because "money" has its own coin with its own fixed probability. Given the class, every word is decided by a separate, independent toss 8:44.

This is the class-conditional independence assumption: conditioned on the class, the features are independent of each other. Once you know an email is spam, learning that "lottery" or "dollar" is present tells you nothing more about "money"; the same holds inside the non-spam class. It may not hold in practice, but it is exactly what reduces the parameter count from \(2^{d+1} - 1\) to \(2d + 1\).

Written as formulas, with a feature vector \(\mathbf{x} = (f_1, \dots, f_d)\), \(f_j \in \{0, 1\}\):

Each factor is \(p^{y}_{j}\) when word \(j\) is present (\(f_j = 1\)) and \(1 - p^{y}_{j}\) when it is absent; this is the compact form of the Bernoulli likelihood from Part 8. Multiplying the factors is justified only because the features are assumed independent given the label. A worked case with \(d = 3\):

Word 1 is absent (its spam coin fell tails), word 2 present, word 3 absent. Together, \(P(y)\) and \(P(\mathbf{x} \mid y)\) give \(P(\mathbf{x}, y)\) for every (email, label) pair using only \(2d + 1\) parameters: \(d\) coins in the spam room, \(d\) in the non-spam room and one to choose the room. The next step is to estimate them, using the simplest method we know, maximum likelihood 17:03.

The parameters to estimate are \(p\), \(p^{1}_{1}, \dots, p^{1}_{d}\) and \(p^{0}_{1}, \dots, p^{0}_{d}\). Every one of them is the bias of a coin, a Bernoulli parameter, and maximum likelihood for Bernoulli parameters was done in detail in Part 8. The estimates are the intuitive ones. Write \(f^{\,i}_{j}\) for feature \(j\) of training email \(i\).

The label coin. In the story, the label is decided first and the features afterwards, so the features carry no information about \(p\). Only the labels do: with \(n\) emails, the coin was tossed \(n\) times.

The word coins. The coin \(p^{y}_{j}\) was only ever tossed for emails with label \(y\), and it only decided feature \(j\). Say 1,000 emails contain 600 spam and 400 non-spam. Then the spam coin for word 5 was tossed 600 times, and we count how often word 5 appeared in those 600 emails 8:19.

The lecture gives these estimates and leaves the derivation to you. A sketch: the log-likelihood of the training set splits into separate groups of terms,

Each parameter appears in only one group, and each group is a Bernoulli log-likelihood, maximized by the sample fraction of ones.

A new email arrives, encoded as a 0/1 vector \(\mathbf{x}_{\text{test}}\) in the same way as the training set; it may or may not appear in the training data. The natural rule, and in a sense the best one can do, is to pick the class that is more probable given the features:

But the model specifies \(P(y)\) and \(P(\mathbf{x} \mid y)\), not \(P(y \mid \mathbf{x})\). Bayes' rule converts one into the other:

Both have the same positive denominator, which does not affect the comparison, so only the numerators need comparing 18:07. Write \(\mathbf{x}_{\text{test}} = (f_1, \dots, f_d)\), use class-conditional independence to expand \(P(\mathbf{x}_{\text{test}} \mid y)\) as a product, and plug in the maximum likelihood estimates as our best guesses for the parameters:

The left side is the likelihood function from before, now evaluated at the estimates instead of treated as a function of the parameters. It uses \(d + 1\) estimates (the spam-room coins and \(\hat p\)); the right side uses the non-spam coins and \(1 - \hat p\). The test features enter only through the exponents: for \(\mathbf{x}_{\text{test}} = (0, 0, 1, 0)\), word 3 contributes \(\hat p^{\,y}_{3}\) and words 1, 2 and 4 contribute \(1 - \hat p^{\,y}_{j}\) 23:16.

1. Naive Bayes for binary features
2. Encode every training email as \(\mathbf{x}_i \in \{0, 1\}^d\) with label \(y_i \in \{0, 1\}\).
3. Estimate \(\hat p\) = fraction of emails labelled 1.
4. For each class \(y\) and word \(j\), estimate \(\hat p^{\,y}_{j}\) = fraction of class-\(y\) emails containing word \(j\).
5. For a test email \((f_1, \dots, f_d)\), compute the spam score \(\hat p \prod_j (\hat p^{\,1}_{j})^{f_j}(1 - \hat p^{\,1}_{j})^{1 - f_j}\) and the non-spam score \((1 - \hat p) \prod_j (\hat p^{\,0}_{j})^{f_j}(1 - \hat p^{\,0}_{j})^{1 - f_j}\).
6. Predict 1 if the spam score is larger, else 0. (L50 sends ties to class 1.)

The name comes from the two things the algorithm rests on.

• Naive: the class-conditional independence assumption, the key step that cut \(2^d\) parameters per class down to \(d\). It is a simplifying assumption that may not hold. Told that an email is spam and contains "lottery", you would expect "money" or "dollar" to be more likely too, so those words are correlated, yet the model treats them as independent given the class.
• Bayes: it is a generative model of \(P(y)\) and \(P(\mathbf{x} \mid y)\), so Bayes' rule is needed to flip the estimates to \(P(y \mid \mathbf{x})\), the quantity prediction actually needs.

Despite the naive assumption, the Naive Bayes algorithm works pretty well in practice, especially when the number of dimensions is large. With dictionary-sized \(d\), the ignored correlations do not seem to matter much for prediction accuracy on real-world data sets. It is a very popular, simple and effective algorithm.

Suppose the \(2d + 1\) parameters have been estimated, and a test email contains a word \(j\), say "zebra", that is in the dictionary but never appeared in any training email, spam or not. Its counting estimates are both zero:

In the test email \(f_j = 1\), so word \(j\)'s factor in the spam score is \((\hat p^{\,1}_{j})^{1}(1 - \hat p^{\,1}_{j})^{0} = 0 \times 1 = 0\), and one zero factor makes the whole product 0. The non-spam score has the same factor with \(\hat p^{\,0}_{j} = 0\), so it is 0 too 6:16. Comparing 0 with 0 decides nothing.

The email may be full of "lottery", "money" and "dollar", all strongly indicating spam. Because the probabilities are multiplied, a single word missing from the training set destroys the information all the other words provide.

The lecture mentions two fixes.

1. Ignore the word. If a test email contains a word that never occurred in training, leave that feature out. This works, but you have to keep track of which words were seen in training and which were not.
2. Add two pseudo-emails (the usual simple fix). Add to the training set the all-ones email \((1, 1, \dots, 1)\) with label 1 and the same all-ones email with label 0. Now every word appears in at least one spam email and at least one non-spam email, so no maximum likelihood estimate can be 0. It may be small, but it is enough to stop the products from collapsing.

This is called Laplace smoothing. Working out what the two pseudo-emails do to the counts: if \(n_y\) training emails have label \(y\) and \(c^{\,y}_{j}\) of them contain word \(j\), each class gains one email that contains every word, and the label coin sees one extra toss of each kind.

There is also a Bayesian reading, as in Part 8. The pseudo-emails act like a prior: before seeing the data, someone has shown you one all-words email of each label, so no word is ever dismissed with probability 0. You can think of it as Bayesian estimation with that prior, or simply as maximum likelihood on the enlarged data set; the two views are equivalent.

Beyond the lecture: with this version, a word that occurs in every class-\(y\) training email gets \(\hat p^{\,y}_{j} = 1\), and a test email without that word still meets a zero factor \(1 - \hat p^{\,y}_{j}\). The common textbook form for binary features adds, per class, one pseudo-email with every word and one with none, giving \((c^{\,y}_{j} + 1)/(n_y + 2)\), which is always strictly between 0 and 1. The toy data below has no such word.

Each score multiplies \(d\) probability estimates, with \(d\) in the thousands, so the products become tiny (standard name: numerical underflow). The numerically more stable way to compare them is to take logarithms and compare sums:

The logarithm is increasing, so the larger log score belongs to the larger score. Taking logs does not remove the zero-frequency problem: \(\log 0\) is undefined, so the estimates must be made nonzero first.

For k-NN and decision trees (Part 13) we asked what the decision boundary looks like: for k-NN it had many holes at small \(k\) and smoothed out as \(k\) grew; a tree cut the feature space with lines parallel to the axes, one per question. The same question for Naive Bayes: in terms of the features, what does its decision function look like?

Predict 1 when the posterior ratio is at least 1, or equivalently when its logarithm is at least 0. Logs turn products into sums, which are easier to read.

Step 1, Bayes' rule. Both posteriors have the denominator \(P(\mathbf{x}_{\text{test}})\), which does not depend on the label, so it cancels:

Step 2, plug in the product. With \(\mathbf{x}_{\text{test}} = (f_1, \dots, f_d)\), both products have the same exponents \(f_j\) and \(1 - f_j\), so they combine into one product 5:38:

Step 3, the log of a product is a sum:

Step 4, collect the terms that multiply \(f_j\). The \(-f_j\) part of \((1 - f_j)\) joins the first log, and the remaining "1" part does not involve the features at all 7:46:

So the features are multiplied by constants that depend only on the estimates, summed, and shifted by another constant that does not depend on the features; the sign decides. \(\mathbf{w}\) depends on the estimated parameters in a complicated way, but it is still just a vector in \(\mathbb{R}^d\) 12:26. Every \(\mathbf{x}_{\text{test}}\) on one side of the hyperplane \(\mathbf{w}^\top\mathbf{x} + b = 0\) is predicted spam, everything on the other side not spam. The constant \(b\) is called the bias (nothing to do with the bias of a coin): it sets how far the hyperplane sits from the origin. The inputs here happen to be binary, but the decision function is still a linear function of them.

Summary of the binary story so far: a class-conditional independence model, its maximum likelihood estimates, the pitfalls and Laplace smoothing, and a linear decision function. Throughout, the features were binary, justified by applications like spam. Can the same generative approach handle real-valued features? Yes; that is the next lecture 15:32.

Now drop the binary assumption. The data is \(\{(\mathbf{x}_1, y_1), \dots, (\mathbf{x}_n, y_n)\}\) with \(y_i \in \{0, 1\}\) as before but \(\mathbf{x}_i \in \mathbb{R}^d\) instead of \(\{0, 1\}^d\). The plan is the same as for Naive Bayes: model \(P(y)\), then \(P(\mathbf{x} \mid y)\).

1. Generative story with Gaussian classes
2. Decide the label with a coin, \(P(y = 1) = p\). Nothing changes here.
3. Generate the feature vector from the Gaussian of that class: \(\mathbf{x} \mid y = 1 \sim \mathcal{N}(\boldsymbol\mu_1, \Sigma)\) and \(\mathbf{x} \mid y = 0 \sim \mathcal{N}(\boldsymbol\mu_0, \Sigma)\).

Earlier, \(d\) coins generated \(d\) binary values. Here a single probability distribution generates the whole point in \(\mathbb{R}^d\) more succinctly, and the most standard choice is a Gaussian. Its density contours are ellipses around the mean; their shape and direction are set by the covariance matrix \(\Sigma\), which describes how the features are correlated (the density involves \(\Sigma^{-1}\)).

Something must differ between the two classes, and here it is the means \(\boldsymbol\mu_1 \ne \boldsymbol\mu_0\). For simplicity the covariance matrix is assumed to be the same for both classes. This is a modelling choice, and the lecture returns to it below. The story looks like the Gaussian mixture model of Part 9, except that here the label of every training point is observed.

Parameters: \(p\), \(\boldsymbol\mu_0\), \(\boldsymbol\mu_1\) and the shared \(\Sigma\) 6:04.

Maximum likelihood estimates L51 · 7:10

The lecture states these without derivation; they are what intuition suggests.

• \(\hat p\) depends only on the labels and is the same as in Naive Bayes: the fraction of points labelled 1.
• \(\hat{\boldsymbol\mu}_1\) is the sample mean of the points labelled 1, and \(\hat{\boldsymbol\mu}_0\) the sample mean of the points labelled 0.
• \(\hat\Sigma\) is not the plain empirical covariance of all the data, because the two classes have different means. Each point is centred at the estimated mean of its own class, \(\hat{\boldsymbol\mu}_{y_i}\), and the \(n\) outer products are averaged. If all points came from one Gaussian, this would reduce to the usual \(\frac1n\sum_i(\mathbf{x}_i - \hat{\boldsymbol\mu})(\mathbf{x}_i - \hat{\boldsymbol\mu})^\top\).

In a generative model, prediction always goes through Bayes' rule: \(P(y_{\text{test}} \mid \mathbf{x}_{\text{test}}) \propto P(\mathbf{x}_{\text{test}} \mid y_{\text{test}})\,P(y_{\text{test}})\). The features are continuous now, so \(P(\mathbf{x}_{\text{test}} \mid y)\) is a density, determined by \(\hat{\boldsymbol\mu}_{y}\) and \(\hat\Sigma\). Predict 1 if

The constant in front depends only on the covariance matrix (through its determinant), and the covariance is shared, so it is the same on both sides and can be ignored. The lecture leaves the remaining simplification as an exercise; here it is. Take logs:

\(\hat\Sigma^{-1}\) is symmetric, so each quadratic form expands as \((\mathbf{x} - \boldsymbol\mu)^\top \Sigma^{-1} (\mathbf{x} - \boldsymbol\mu) = \mathbf{x}^\top\Sigma^{-1}\mathbf{x} - 2\boldsymbol\mu^\top\Sigma^{-1}\mathbf{x} + \boldsymbol\mu^\top\Sigma^{-1}\boldsymbol\mu\). The two \(\mathbf{x}^\top\hat\Sigma^{-1}\mathbf{x}\) terms have opposite signs and cancel, leaving

Only the first term depends on the test point; the rest are numbers computed from the estimates. \(\mathbf{w}\) and especially \(b\) depend on the parameters in complicated ways, but in the end they are a vector and a number, and the decision function is again linear: points on one side of \(\mathbf{w}^\top\mathbf{x} + b = 0\) are predicted 1, points on the other side 0 17:34.

The expression written in the lecture drops the factor \(\tfrac12\) on the mean terms and writes the prior term as \(\log\frac{1 - \hat p}{\hat p}\). Neither changes the conclusion that the boundary is linear. The version above is what the algebra gives, and it matches the lecture's later remark that a larger \(\hat p\) gives more of the space to class 1.

The shared \(\Sigma\) is what makes the boundary linear. Geometrically, both classes have density contours of the same shape and orientation, centred at \(\hat{\boldsymbol\mu}_1\) and \(\hat{\boldsymbol\mu}_0\). At a test point we compare the class-1 density times \(\hat p\) with the class-0 density times \(1 - \hat p\). When the contour shapes match, there is a line on one side of which the first product is always larger.

• \(\Sigma = I\). The contours are circles and \(\mathbf{w} = \hat{\boldsymbol\mu}_1 - \hat{\boldsymbol\mu}_0\), so the boundary is perpendicular to the segment joining the two means. With \(\hat p = \tfrac12\) the prior term vanishes and the boundary is the perpendicular bisector of that segment. The bias \(\log\frac{\hat p}{1 - \hat p}\) slides it along the segment: as \(\hat p\) grows toward 1, more of the space is predicted 1, so the line moves toward \(\hat{\boldsymbol\mu}_0\); as \(\hat p\) falls toward 0 it moves toward \(\hat{\boldsymbol\mu}_1\) 23:42.
• Shared general \(\Sigma\), circular or elliptical. Still a line, a version of the same picture scaled by the covariance; \(\hat\Sigma^{-1}\) tilts it, so it is no longer exactly perpendicular to the segment between the means.
• Separate covariances. Estimate \(\hat\Sigma_1\) and \(\hat\Sigma_0\), one per class. The ellipses can now have different shapes and directions (one class might be round, the other long and tilted), and the region where one class wins need not be separable by a line. The boundary is still the set of points where \(P(y = 1 \mid \mathbf{x}) = P(y = 0 \mid \mathbf{x})\), the place where ties are broken, but in general it is quadratic: a term of the form \(\mathbf{x}^\top A\,\mathbf{x}\) survives 27:03.

The lecture does not derive the quadratic case. Standard result, by the same steps as before with \(\hat\Sigma_1 \ne \hat\Sigma_0\), so that neither the \(\mathbf{x}^\top\Sigma^{-1}\mathbf{x}\) terms nor the determinants cancel:

Same covariance: linear decision boundary. Different covariances: a richer, generally quadratic boundary. Which to use is a modelling decision.

This algorithm goes by several names. The one the lecturer prefers is Gaussian naive Bayes: the naive part is the simple assumption that, given the label, the data is generated by a single Gaussian, and Bayes' rule inverts \(P(\mathbf{x} \mid y)\) and \(P(y)\) into \(P(y \mid \mathbf{x})\), as in any generative model.

Standard names: with a shared covariance this model is usually called linear discriminant analysis (LDA), and with one covariance per class quadratic discriminant analysis (QDA). Many textbooks keep "Gaussian naive Bayes" for the case of a diagonal covariance per class, where the features are independent given the label.

To summarize the generative thread: Naive Bayes for binary features, then a Gaussian model for real features; with a shared covariance the boundary is linear, with different covariances generally quadratic. The linear case is the interesting one, because nice generative assumptions keep producing linear decision boundaries.

That suggests a shortcut. If the decision function ends up linear in most of these nice cases, why not model \(P(y \mid \mathbf{x})\) directly, in a linear fashion, as a discriminative model? This time the model of \(P(y \mid \mathbf{x})\) is explicit, unlike the heuristic rules of k-NN and decision trees. The next lectures take this route: the perceptron and logistic regression, in Part 15.

Data distribution \(\mathcal{D}\)

Unknown but fixed distribution over features and labels that produces both the training and the test pairs.

Generative model

Makes assumptions about the joint \(P(\mathbf{x}, y)\), here as \(P(y)\,P(\mathbf{x} \mid y)\); it describes how the features themselves arise.

Discriminative model

Models only \(P(y \mid \mathbf{x})\). k-NN and decision trees are trivial cases with probabilities 0 or 1.

Generative story

A step-by-step random procedure for producing each data point: a coin for the label, then features given the label.

Class-conditional independence

Given the label, the features are independent. Cuts \(2^{d+1} - 1\) parameters to \(2d + 1\).

Naive Bayes

Classifier built on class-conditional independence ("naive") and Bayes' rule to get \(P(y \mid \mathbf{x})\).

\(\hat p^{\,y}_{j}\)

Estimated chance that word \(j\) appears in a class-\(y\) email: the fraction of class-\(y\) training emails containing it.

Zero-frequency problem

A word absent from training gets estimates 0 in both classes, so both scores of a test email containing it become 0.

Laplace smoothing

Adding pseudo-emails (here one all-words email per label) so no estimate is 0; equivalent to using a prior.

Log scores

Comparing sums of logs instead of products of many small probabilities, for numerical stability.

Decision function

The rule that maps \(\mathbf{x}\) to a label. For Naive Bayes and shared-covariance Gaussians it is \(\mathbf{w}^\top\mathbf{x} + b \ge 0\).

Bias \(b\)

The constant term of a linear decision function, setting how far the hyperplane is from the origin; unrelated to a coin's bias.

Gaussian naive Bayes (lecture's name)

\(\mathbf{x} \mid y \sim \mathcal{N}(\boldsymbol\mu_y, \Sigma)\) with a shared \(\Sigma\), giving \(\mathbf{w} = \hat\Sigma^{-1}(\hat{\boldsymbol\mu}_1 - \hat{\boldsymbol\mu}_0)\).

Quadratic decision boundary

What separate class covariances give in general, because the \(\mathbf{x}^\top A\,\mathbf{x}\) term no longer cancels.