The task: given an instance described by features x₁ … xₙ, choose the most probable class. START FROM BAYES' RULE, from ACtE0903: P(x₁…xₙ | c) · P(c) P(c | x₁…xₙ) = ───────────────────── P(x₁…xₙ) THE MAXIMUM A POSTERIORI (MAP) CLASSIFIER picks the class maximising this. The denominator is the same for every class, so it can be dropped: c_MAP = argmax over c of P(x₁…xₙ | c) · P(c) THE PROBLEM: P(x₁…xₙ | c) is a joint distribution over all the features. With n binary features it needs 2^n − 1 numbers PER CLASS, and no data set determines them. n = 10 → 1,023 per class n = 20 → 1,048,575 per class n = 30 → over a billion per class THIS IS THE SAME COMBINATORIAL WALL as the full joint distribution in the Bayesian networks topic. THE NAIVE BAYES ASSUMPTION: THE FEATURES ARE CONDITIONALLY INDEPENDENT GIVEN THE CLASS. P(x₁…xₙ | c) = P(x₁|c) · P(x₂|c) · … · P(xₙ|c) Substituting gives the classifier: c_NB = argmax over c of P(c) · Π P(xᵢ | c) i=1..n THE PARAMETER SAVING IS THE WHOLE POINT: full joint per class: 2^n − 1 naive Bayes per class: n at n = 20 that is 1,048,575 against 20 — a factor of over fifty thousand, and the difference between "cannot be estimated" and "estimated from a few hundred examples". WHY IT IS CALLED "NAIVE": THE ASSUMPTION IS ALMOST ALWAYS FALSE. In a medical setting, fever and elevated pulse are correlated even within one disease; in text, "New" and "York" are anything but independent. The model asserts they are, and computes as though they were. WHY IT WORKS ANYWAY, and this is the genuinely interesting part: CLASSIFICATION NEEDS ONLY THE ARGMAX TO BE RIGHT, NOT THE PROBABILITIES. Correlated features cause the same evidence to be counted several times, which pushes the computed probabilities toward 0 or 1 — but usually pushes the CORRECT class furthest, so the ranking survives. The probability estimates are badly calibrated and the decision is often right. THE PRACTICAL CONSEQUENCE: TRUST NAIVE BAYES' DECISIONS AND DISTRUST ITS CONFIDENCE. If you need a calibrated probability — for a cost-based decision, say — this is the wrong model.

USING THE SAME WEATHER DATASET as the decision tree topic, so the two methods can be compared directly. 14 days, 9 yes and 5 no. STEP 1 — THE PRIORS: P(yes) = 9/14 = 0.6429 P(no) = 5/14 = 0.3571 STEP 2 — THE LIKELIHOOD TABLES, counted from the data: OUTLOOK yes no sunny 2/9 3/5 overcast 4/9 0/5 rain 3/9 2/5 TEMPERATURE yes no hot 2/9 2/5 mild 4/9 2/5 cool 3/9 1/5 HUMIDITY yes no high 3/9 4/5 normal 6/9 1/5 WIND yes no weak 6/9 2/5 strong 3/9 3/5 STEP 3 — CLASSIFY a new day: x = ⟨Outlook = sunny, Temp = cool, Humidity = high, Wind = strong⟩ For class YES: P(yes) × P(sunny|yes) × P(cool|yes) × P(high|yes) × P(strong|yes) = (9/14) × (2/9) × (3/9) × (3/9) × (3/9) = 0.6429 × 0.2222 × 0.3333 × 0.3333 × 0.3333 = 0.005291 For class NO: P(no) × P(sunny|no) × P(cool|no) × P(high|no) × P(strong|no) = (5/14) × (3/5) × (1/5) × (4/5) × (3/5) = 0.3571 × 0.6000 × 0.2000 × 0.8000 × 0.6000 = 0.020571 NO IS LARGER, SO THE PREDICTION IS "DO NOT PLAY". STEP 4 — NORMALISE, to get probabilities: total = 0.005291 + 0.020571 = 0.025862 P(yes | x) = 0.005291 / 0.025862 = 0.2046 (20.5%) P(no | x) = 0.020571 / 0.025862 = 0.7954 (79.5%) A CONFIDENT PREDICTION OF "NO" AT ABOUT 80%. COMPARE WITH THE DECISION TREE from the previous topic: its Sunny → Humidity = High path also predicts NO. THE TWO METHODS AGREE, having used the data completely differently — the tree by selecting three attributes and ignoring Temperature, Naive Bayes by using all four and weighting each equally. THE ZERO-FREQUENCY PROBLEM, and it is the standard exam follow-up: Notice P(overcast | no) = 0/5 = 0. If a new instance has Outlook = overcast, the ENTIRE PRODUCT for class "no" becomes zero, whatever the other features say. One unseen combination vetoes the class absolutely. THE FIX IS LAPLACE (ADD-ONE) SMOOTHING: add 1 to every count and k to the denominator, where k is the number of values the attribute can take. P(overcast | no) = (0 + 1) / (5 + 3) = 1/8 = 0.125 P(sunny | no) = (3 + 1) / (5 + 3) = 4/8 = 0.500 P(rain | no) = (2 + 1) / (5 + 3) = 3/8 = 0.375 The three still sum to 1, no probability is zero, and the estimates are pulled gently toward uniform — which is exactly the right behaviour when data is scarce. MORE GENERALLY, add-α smoothing with α < 1 (Lidstone smoothing) applies a weaker correction. AND THE NUMERICAL PRACTICALITY: multiplying many small probabilities UNDERFLOWS in floating point. With 1,000 word features each around 0.001, the product is 10⁻³⁰⁰⁰, which is zero to a computer. THE STANDARD FIX IS TO WORK IN LOGARITHMS: argmax [ log P(c) + Σ log P(xᵢ | c) ] Sums instead of products, and the argmax is unchanged because log is monotonic. EVERY REAL IMPLEMENTATION DOES THIS.

THE VARIANTS, by what the features look like: MULTINOMIAL NAIVE BAYES — for counts, and the standard choice for text features are word frequencies; P(word | class) is estimated as the proportion of that word among all words in that class's documents THE TEXT CLASSIFICATION APPLICATION, in outline: · treat a document as a BAG OF WORDS — order discarded · P(spam) from the proportion of spam in training · P(word | spam) from word counts in spam messages · classify by the log-sum above WHY IT SUITS TEXT PARTICULARLY WELL: the feature space is enormous (tens of thousands of words) and each document contains few of them, so the per-feature estimates are what is available. A joint model over 50,000 words is inconceivable; 50,000 independent estimates are trivial. BERNOULLI NAIVE BAYES — for binary features word present or absent, ignoring counts. Also models the ABSENCE of a word as evidence, which multinomial does not. GAUSSIAN NAIVE BAYES — for continuous features assume each feature is normally distributed within each class, and estimate its mean and variance per class: P(x | c) = (1/√(2πσ²)) · exp(−(x − μ)²/(2σ²)) Two numbers per feature per class — still linear. THE ADVANTAGES, which explain its persistence: · FAST to train — one pass counting frequencies — and fast to apply · works with SMALL TRAINING SETS, because it estimates only n parameters per class rather than 2^n · handles HIGH-DIMENSIONAL data naturally, which is why text is its home · INCREMENTAL: new examples update the counts without retraining · INTERPRETABLE to a degree: you can list the words most indicative of each class · a strong BASELINE — and the professional habit worth acquiring is to run it first, because a complicated model that cannot beat Naive Bayes is not earning its complexity THE DISADVANTAGES: · the INDEPENDENCE ASSUMPTION is false, so probability estimates are poorly calibrated · cannot represent interactions between features. If the class depends on x₁ XOR x₂, Naive Bayes cannot learn it, because each feature alone is uninformative — the same limitation as a single-layer perceptron, met in the neural network section. · the ZERO-FREQUENCY problem, requiring smoothing · continuous features need a distributional assumption that may be wrong NAIVE BAYES AS A BAYESIAN NETWORK, which ties this topic to ACtE0903: it is exactly a network with the class as the single parent of every feature and no other edges — Class ┌────┬─┴──┬────┐ ▼ ▼ ▼ ▼ x₁ x₂ x₃ x₄ THE MISSING EDGES BETWEEN THE FEATURES ARE THE INDEPENDENCE ASSUMPTION, drawn. And that makes the improvement obvious: ADD THE EDGES THAT MATTER. A TREE-AUGMENTED NAIVE BAYES (TAN) permits each feature one additional parent, capturing the strongest dependencies while remaining tractable. It sits exactly between Naive Bayes and a full Bayesian network, which is a good illustration of the expressiveness–tractability trade-off appearing yet again. THE COMPARISON WITH DECISION TREES, since the two were applied to the same data: NAIVE BAYES uses ALL features, weights them independently, needs little data, gives a probability, and cannot model interactions. DECISION TREES SELECT features, model interactions naturally along a path, need more data to split reliably, and give an explanation rather than a probability. THEY FAIL ON DIFFERENT PROBLEMS, which is why comparing both on a new dataset is standard practice rather than laziness.