The Naive Bayes Classifier

The arithmetic a paper wants. For the class yes: the prior is 9/14, and the four conditional probabilities are read straight off the table by counting. Their product is 0.02351558. The same for no gives 0.01028571. Normalising, P(yes) is 0.6957, so the answer is yes.

Note that the two products do not sum to 1 before normalising. They are P(class) * P(evidence | class), which is the joint, and normalising by their sum divides by P(evidence). That is the normalising constant of Bayes Theorem computed without ever being named.

The zero-frequency problem

Read the middle block. Among the five students who did not attend, none had clear weather, so P(weather = clear | no) is 0/5 = 0.

One zero destroys everything. The product for no becomes exactly 0, whatever the other three features say, so the classifier reports P(yes) = 1.0000: absolute certainty from one missing count. That is not confidence, it is an artefact, and it would occur on any feature value that happens not to appear with a class in a finite sample.

Laplace smoothing is the fix and it is one line:

With alpha = 1, P(weather = clear | no) becomes (0 + 1)/(5 + 3) = 0.1250 instead of 0, and the same student's prediction falls from the absurd 1.0000 to a sensible 0.8319. Same answer, honest confidence.

The denominator must add alpha times the number of possible values, not alpha once, or the smoothed probabilities for a feature no longer sum to 1. And this is Regularization again: smoothing is a prior pulling every estimate towards uniform, and alpha = 1 is exactly a uniform prior on each feature's distribution. It is the same device as The Learning Agent used to stop an early run of failures producing an estimate of zero.

The three standard variants

MU writes Naive Bayes without qualification, and a paper may ask which kind.

Multinomial and Bernoulli differ in a way that matters for text: Bernoulli explicitly scores a word's absence, multinomial ignores it. For short documents Bernoulli usually wins; for long ones multinomial does.

Gaussian naive Bayes is how continuous features are handled without discretising them: estimate the mean and variance of each feature within each class from the training data, and use the normal density. That is two numbers per feature per class, so it remains linear in the number of features.

Why a false assumption gives a good classifier

The assumption is almost always false. In text, New and York are strongly dependent given any class. In the 14 rows, weather and distance may well be related. And the classifier works. A paper asking why expects this answer.

The probabilities are wrong; the ordering is often right. Classification needs only the largest class, not a correct probability. Dependent features count their shared evidence more than once, which pushes the winning class's product further ahead, and the winner usually does not change.

So the correct statement is precise: naive Bayes is a good classifier and a bad probability estimator. Its outputs are notoriously overconfident, clustering near 0 and 1. Anything that uses the probability as a number, such as ranking by risk or setting a threshold on expected cost, should not use naive Bayes without recalibrating it.

Two more practical reasons it survives: it needs very little data, since each estimate is a one-dimensional count rather than a joint; and it is immune to the curse of dimensionality that defeats k-NN in k-NN for Regression, and What Limits the Method, because it never computes a distance.

Two implementation points that cost marks

Underflow. Multiplying a hundred probabilities gives a number too small for a computer to represent, and it becomes 0. The fix is to work with logarithms: maximise log P(c) + sum of log P(xi | c), which turns the product into a sum and cannot underflow. Every real implementation does this.

A feature value never seen at all, in any class, contributes the same factor to every class and so cannot affect the comparison. It is usually simply skipped.

Distinctions

What it does not mean

Naive does not mean simple-minded. It names the independence assumption specifically.

The assumption is not usually true, and the classifier is not claiming it is. It is claiming that the ordering of the classes survives the approximation.

The output probability is not a probability you should act on numerically. It is overconfident. Use it to choose a class, not to price a risk.

Smoothing is not a fudge. It is a uniform prior, and it is the same device as the ridge penalty of Regularization.

A zero probability is not evidence of impossibility. It is evidence that the value did not occur in a finite sample.

Multiplying the probabilities directly is not how it is implemented. Logarithms are used, to avoid underflow.

Quick revision

• P(c | x) proportional to P(c) * product of P(xi | c). Bayes theorem, drop the denominator, and assume the features are conditionally independent given the class.
• Training is counting. No optimisation, no iteration. With 30 binary features it needs 61 numbers where the full joint needs 2,147,483,647.
• Worked: prior 9/14, four conditionals counted off the table, product 0.02351558 against 0.01028571, giving P(yes) = 0.6957.
• Zero frequency: P(weather = clear | no) = 0/5 = 0 makes the whole product 0, so the classifier reports 1.0000. One missing count produces absolute certainty.
• Laplace smoothing: (count + alpha) / (n + alpha * number of values). With alpha = 1 the estimate becomes 0.1250 and the confidence falls from 1.0000 to 0.8319. It is a uniform prior, that is regularization.
• Variants: multinomial (counts), Bernoulli (presence, and absence is evidence), Gaussian (continuous, mean and variance per feature per class).
• A good classifier and a bad probability estimator. The assumption is false, the probabilities are overconfident, and the class ordering usually survives.
• Implementation: use logarithms, or the product underflows to zero.

Test yourself

1. Derive the naive Bayes rule from Bayes theorem. Bayes theorem gives P(c | x) as P(x | c) times P(c) divided by P(x). The denominator is the same for every class and cannot change which is largest, so it is dropped. Assuming the features are conditionally independent given the class, P(x | c) factorises into the product of P(xi | c), giving P(c | x) proportional to P(c) times that product.

2. Compute the prediction for a student in rain, near, with a friend going, no early lecture. For yes: prior 9/14 times the four conditionals, giving 0.02351558. For no: prior 5/14 times its conditionals, giving 0.01028571. Normalising, P(yes) is 0.6957, so the prediction is that the student attends.

3. What is the zero-frequency problem, and what does it do to the output? If a feature value never occurs with a class in the training data, its conditional probability is exactly zero, and multiplying by it makes the entire product zero however strong the other evidence. In this chapter no non-attending student had clear weather, so the classifier reports a probability of 1.0000, absolute certainty produced by one missing count.

4. State Laplace smoothing and apply it to that case. Estimate each conditional as the count plus alpha, divided by the class count plus alpha times the number of possible values of that feature. With alpha of 1, P(weather = clear | no) becomes one over eight, that is 0.1250, instead of zero, and the classifier's confidence falls from 1.0000 to 0.8319.

5. Name the three variants of naive Bayes and say what each suits. Multinomial, for count features such as word frequencies. Bernoulli, for presence-or-absence features, which also scores a feature's absence as evidence and suits short documents. Gaussian, for continuous features, modelling each with a normal distribution whose mean and variance are estimated per class.

6. The independence assumption is usually false. Why does the classifier still work? Because classification needs only the correct class to have the largest score, not a correct probability. Dependent features double-count their shared evidence, which exaggerates the leading class's score but usually does not change which class leads. The correct summary is that it is a good classifier and a poor probability estimator, since its outputs are systematically overconfident.

7. Why are logarithms used in an implementation? Because multiplying many probabilities produces a number too small to represent, which becomes zero and destroys the comparison. Taking logarithms turns the product into a sum of logarithms, which cannot underflow, and the class with the largest sum is the same as the class with the largest product.