Bayes Theorem and Naive Bayes Classifier

This lecture builds a chain of ideas, each one unlocking the next: conditional probability → total probability → Bayes Theorem → the Naive Bayes classifier. Along the way you will learn to compute probabilities backwards (Bayes), compare hypotheses without computing the full denominator (MAP), and handle dozens of features with one bold assumption (Naive Bayes). The lecture ends with a preview of Laplace correction, which patches the zero-probability problem that would otherwise break the classifier.

4.1 Review of Conditional Probability

4.1.1 Definition and Notation

Conditional probability asks: after one event has happened, what is the chance of another event?

There are two directions — and they are NOT the same:

$$P(A\mid B)\text{— probability of }A\text{ after }B\text{ has happened}$$

$$P(B\mid A)\text{— probability of }B\text{ after }A\text{ has happened}$$

These are called conditional events. Swapping them changes the question entirely. $P(\text{rain}\mid \text{thunder})$ and $P(\text{thunder}\mid \text{rain})$ answer completely different questions.

4.1.2 The Multiplication Rule

4.1.3 Conditional Probability When Events Are Independent

Recall that for independent events, $P(A\cap B)=P(A)\cdot P(B)$.

Substitute this into the conditional probability formula:

$$P(A\mid B)=\frac{P(A)\cdot P(B)}{P(B)}=P(A)$$

Similarly, $P(B\mid A)=P(B)$.

Visual intuition: Picture a Venn diagram with two overlapping circles, A and B. The rectangle is the full sample space (area = 1). $P(A\mid B)$ is the fraction of the B-circle that overlaps with A. When you condition on B, you zoom into the B-circle and ask: "what proportion of this circle is also A?" If A and B are independent, the overlap is exactly proportional — A occupies the same fraction of B as it does of the whole rectangle.

Real-World & Domain Connection: Conditional probability underpins medical testing. A test's sensitivity is $P(\text{positive test}\mid \text{disease})$ and its specificity is $P(\text{negative test}\mid \text{no disease})$. But what patients and doctors actually want to know is the reverse: $P(\text{disease}\mid \text{positive test})$. Computing that reverse probability requires Bayes Theorem — which is built on the conditional probability foundation laid here.

4.2 Total Probability

4.2.1 Motivation — The Email Spam Example

Consider three email accounts synced on one device:

- $A_1$: Office email — receives 60% of all mail, $P(A_1)=0.60$ - $A_2$: Bits email — receives 10% of all mail, $P(A_2)=0.10$ - $A_3$: Personal email — receives 30% of all mail, $P(A_3)=0.30$

From past experience, the spam rates are known: - Office mail: 1% spam — $P(B\mid A_1)=0.01$ - Bits mail: 2% spam — $P(B\mid A_2)=0.02$ - Personal mail: 10% spam — $P(B\mid A_3)=0.10$

Here, $B$ is the event "mail is spam."

Question: Across all accounts, what percentage of total mail is spam?

The answer is a weighted sum:

$$\begin{array}{rl}P(B)& =(1\%\text{ of }60\%)+(2\%\text{ of }10\%)+(10\%\text{ of }30\%)\\ & =(0.01\times 0.60)+(0.02\times 0.10)+(0.10\times 0.30)\\ & =0.006+0.002+0.030\\ & =0.038\end{array}$$

So 3.8% of all mail is spam — not 20% as one might guess from casual averaging.

4.2.2 The Total Probability Formula

4.2.3 Conditions Required

4.2.4 Worked Example — Gas Station Customers

                    ┌── Fill (B): 0.30 → 0.40 × 0.30 = 0.12
Regular (A₁): 0.40 ─┤
                    └── Not fill: 0.70

                    ┌── Fill (B): 0.60 → 0.35 × 0.60 = 0.21
Plus (A₂): 0.35 ────┤
                    └── Not fill: 0.40

                    ┌── Fill (B): 0.50 → 0.25 × 0.50 = 0.125
Premium (A₃): 0.25 ─┤
                    └── Not fill: 0.50

4.2.5 Worked Example — Ad Clicking

4.2.6 Worked Example — Poisonous Forest

4.2.7 Student Questions on Total Probability

Visual intuition: Draw a probability tree. The first level splits by $A_i$ (the partition events). The second level from each $A_i$ branches into B and not-B. Total probability is simply adding up the "leaf" probabilities of all branches that end in B. The tree makes it impossible to forget a branch and impossible to confuse $P(B\mid A_i)$ with $P(A_i\mid B)$.

Real-World & Domain Connection: Total probability is used constantly in risk analysis. An insurance company knows accident rates by age group ($P(\text{accident}\mid \text{age group})$) and the demographic breakdown of its customers ($P(\text{age group})$). Total probability gives the overall accident rate, which directly determines premium pricing. The same pattern appears in epidemiology (disease prevalence across subpopulations), quality control (defect rates across production lines), and A/B testing (conversion rates across user segments).

4.3 Bayes Theorem

4.3.1 The Core Question — Finding the Culprit

Total probability answers: "What is the overall chance of spam?" But the more useful question is: "Given that I received spam, which email account is the most likely source?"

This is the Bayes question: given that B has occurred (spam), what is the probability it came from $A_i$?

$$P(A_1\mid B),P(A_2\mid B),P(A_3\mid B)$$

Compare these with the reverse direction we already knew from data:

$$P(B\mid A_1),P(B\mid A_2),P(B\mid A_3)$$

4.3.2 Derivation of Bayes Theorem

4.3.3 Bayes Theorem Using the Tree Diagram

The tree diagram makes Bayes Theorem intuitive — no formula memorization needed.

For the spam example (with the actual computed total $P(B)$):

                    ┌── Spam (B|A₁): 0.01 → Branch product: 0.60 × 0.01 = 0.006
Office (A₁): 0.60 ──┤
                    └── Not spam: 0.99

                    ┌── Spam (B|A₂): 0.02 → Branch product: 0.10 × 0.02 = 0.002
Bits (A₂): 0.10 ────┤
                    └── Not spam: 0.98

                    ┌── Spam (B|A₃): 0.10 → Branch product: 0.30 × 0.10 = 0.030
Personal (A₃): 0.30 ┤
                    └── Not spam: 0.90

Step 1 — Compute the denominator $P(B)$ = sum of all branch products where B occurs: $$P(B)=0.006+0.002+0.030=0.038$$

**Step 2 — For each $A_i$, compute the posterior:**

$$P(A_1\mid B)=\frac{0.006}{0.038}\approx 0.158$$

$$P(A_2\mid B)=\frac{0.002}{0.038}\approx 0.053$$

$$P(A_3\mid B)=\frac{0.030}{0.038}\approx 0.789$$

Step 3 — Identify the culprit: The personal account ($A_3$) has the highest posterior probability at ~78.9%. Even though it only receives 30% of mail, its high spam rate (10%) makes it the dominant source. If you want to reduce spam, clean up the personal account first.

4.3.4 Worked Example — Bonus Scheme

4.3.5 Student Questions on Bayes Theorem

Several students asked about the denominator and its role:

Visual intuition: Draw the same tree as for total probability, but now you are "walking backwards." You know B happened, so you only look at the branches ending in B. The branch products are proportional to the posteriors. Normalize them (divide by their sum) to get the actual probabilities. The tree makes the "inversion" visually obvious.

Real-World & Domain Connection: Bayes Theorem is named after Thomas Bayes (1702–1761), but its modern prominence comes from a fundamental philosophical split in statistics. Frequentists treat probability as long-run frequency and parameters as fixed unknowns. Bayesians treat probability as degree of belief and use Bayes Theorem to update beliefs about parameters when data arrives. The same formula underlies both traditions — but Bayesians place it at the center of everything. In machine learning, Bayes Theorem is the theoretical foundation of probabilistic classifiers, spam filters, and belief networks that power recommendation systems, medical diagnosis tools, and autonomous decision-making.

4.4 Bayes Theorem as a Classifier

4.4.1 The ML Connection

In a classification problem, we have: - Features (inputs): $X$ — the data we observe (e.g., weather conditions, email words) - Target/Class (output): $Y$ — the label we want to predict (e.g., "yes"/"no", "spam"/"not spam")

We want: given a new input $X=\text{some value}$, what is the probability it belongs to each class?

$$P(Y=\text{yes}\mid X)\text{and}P(Y=\text{no}\mid X)$$

4.4.2 Worked Example — Weather and Play

4.4.3 Student Questions on Bayes as Classifier

Visual intuition: Picture a 2D plot with "Outlook" on the x-axis (three bars: sunny, overcast, rainy) and "count" on the y-axis. Color the bars by class: yes in green, no in red. For sunny, the green bar is height 3 and the red bar is height 2 — the green bar is taller, so the classifier predicts "yes." The classifier simply picks the taller bar for the given feature value.

Real-World & Domain Connection: The weather-and-play dataset is the canonical "toy example" in data mining textbooks (notably Witten & Frank's Data Mining), but the same Bayes classification logic powers production systems: credit scoring (will this applicant default?), medical triage (does this patient need immediate care?), and the original spam filters that made email usable. Every time you mark an email as "not spam," you are contributing a training label that updates a Bayes classifier somewhere.

4.5 Maximum A Posteriori Hypothesis (HMAP)

4.5.1 Simplifying the Computation

In the weather example:

$$P(\text{yes}\mid \text{sunny})=\frac{P(\text{sunny}\mid \text{yes})\cdot P(\text{yes})}{P(\text{sunny})}$$

$$P(\text{no}\mid \text{sunny})=\frac{P(\text{sunny}\mid \text{no})\cdot P(\text{no})}{P(\text{sunny})}$$

Notice that the denominator $P(\text{sunny})$ is the same for both calculations. Since both are divided by the same number, the ranking does not change:

$$\text{Compare: }P(\text{sunny}\mid \text{yes})\cdot P(\text{yes})\text{vs}P(\text{sunny}\mid \text{no})\cdot P(\text{no})$$

4.5.2 Student Questions on HMAP

Visual intuition: Think of MAP as comparing the heights of two bars on a bar chart where both bars have been divided by the same scaling factor. The taller bar stays taller whether or not you apply the scaling. MAP simply skips the scaling and compares the raw bar heights.

Real-World & Domain Connection: MAP is the decision-theoretic foundation of most modern classifiers. In Bayesian statistics, the MAP estimate is the mode of the posterior distribution — the single "best guess" for a parameter. While full Bayesians prefer to keep the entire posterior distribution (quantifying uncertainty), MAP provides a point estimate that is often computationally cheaper and enough for decision-making in applications like speech recognition (choosing the most likely word sequence) and image labeling (picking the most likely object class per pixel).

4.6 Maximum Likelihood Estimate (MLE)

4.6.1 When Class Priors Are Unknown

In HMAP, we need the class prior probabilities $P(h)$ — for example, $P(\text{yes})$ and $P(\text{no})$.

What if these priors are not available? The default assumption: all classes are equally likely.

For two classes: $$P(\text{yes})=P(\text{no})=0.5$$

With equal priors, the HMAP comparison becomes:

$$P(D\mid \text{yes})\times 0.5\text{vs}P(D\mid \text{no})\times 0.5$$

Since both are multiplied by the same 0.5, the priors cancel out. The decision now depends only on the likelihood:

4.6.2 The Chain — From Bayes to MLE

4.6.3 Student Questions on MLE

Comparison — MAP vs MLE:

Visual intuition: Imagine two likelihood curves — one for "yes," one for "no" — plotted against the feature value. MLE simply picks the higher curve at the given feature value. MAP tilts the curves by multiplying each by its prior weight before comparing heights. If the priors are equal, the tilting has no effect — the same curve wins.

Real-World & Domain Connection: MLE is the workhorse of classical (Frequentist) statistics. When you fit a linear regression by minimizing squared error, you are implicitly computing the MLE under a Gaussian noise assumption. When you estimate a coin's bias as "number of heads divided by number of flips," that's the MLE. The philosophical divide between MLE (Frequentist, data-only) and MAP/Bayes (incorporates prior belief) is one of the deepest fault lines in statistics — and the fact that both sit on the same Bayes→MAP→MLE chain shows they are more connected than the philosophical debates suggest. In practice, data scientists move fluidly between them depending on what information is available.

4.7 Naive Bayes Classifier

4.7.1 The Problem — Multiple Features

Bayes Theorem works smoothly with one feature (e.g., only "outlook"). But real datasets have many features. In the weather example:

- Outlook: sunny, overcast, rainy - Temperature: hot, mild, cool - Humidity: high, normal - Wind: weak, strong

The class is still binary: play = yes or no.

Now the Bayes calculation becomes:

$$P(\text{yes}\mid X)=\frac{P(X_1\cap X_2\cap X_3\cap X_4\mid \text{yes})\cdot P(\text{yes})}{P(X)}$$

Where $X=(X_1=\text{sunny},X_2=\text{hot},X_3=\text{normal},X_4=\text{false})$.

The difficulty: We need $P(X_1\cap X_2\cap X_3\cap X_4\mid \text{yes})$ — the joint probability of all four features occurring together, given "yes." This joint probability is extremely hard to compute from data. Finding rows that match all four conditions exactly may return zero or very few records. With 4 binary features, there are $2^4=16$ possible combinations — and only 14 total records. The data is too sparse.

4.7.2 The Naive Assumption — Feature Independence

4.7.3 Why "Naive" Is Acceptable

The features are not truly independent in reality: - If it is hot, humidity is likely different - Temperature and humidity are correlated

Yet we assume they are independent. This is the "naive" part.

4.7.4 Naive Bayes — Summary

4.7.5 Student Questions on Naive Bayes

4.7.6 Industry Applications of Naive Bayes

Real-world uses include: - Spam filtering — classifying emails as spam or not spam. This is the canonical Naive Bayes application. - Sentiment analysis — determining if a review is positive or negative based on word frequencies. - Document categorization — assigning topics to articles (sports, politics, technology). - Medical diagnosis — predicting disease presence given symptoms. The prior comes from population statistics; the likelihood comes from clinical data. - Real-time text classification — Naive Bayes is fast enough to classify tweets, chat messages, or streaming text in real time.

The email spam classification story is particularly instructive. About 15 years ago, Gmail used to explicitly ask users "Is this spam?" for each suspicious message. Users' responses trained the Naive Bayes classifier. Today the algorithm is mature — it rarely asks. Emails go straight to the spam folder. Only when you visit the spam folder does it occasionally confirm "Report as spam?" or "Report as fraud?"

Visual intuition: For text classification, picture a "word cloud" for each class. The "spam" cloud has words like "free," "win," "click" in large font. The "not spam" cloud has words like "meeting," " attached," "thanks" in large font. Naive Bayes compares how well a new email's words match each cloud — assuming each word contributes independently to the overall match score. The cloud that has more matching words (weighted by their prominence) wins.

Real-World & Domain Connection: Naive Bayes is one of the oldest ML algorithms still in widespread production use. It powers spam filters in virtually every email provider, sentiment analyzers in social media monitoring tools, and document classifiers in legal e-discovery platforms. Its enduring popularity comes from three properties: (1) it trains in one pass over the data — no iterative optimization, (2) it predicts in microseconds — just multiply and compare, and (3) it is interpretable — you can inspect which words most strongly indicate spam. In an era of deep learning, Naive Bayes remains the go-to baseline for text classification and the algorithm of choice when training data is scarce, latency is critical, or model interpretability matters.

4.8 Preview — Laplace Correction

4.8.1 The Zero-Probability Problem

When computing Naive Bayes with many features, it is common for some feature-class combination to have zero occurrences in the training data. For example, if no "yes" day in the dataset had "cool" temperature, then:

$$P(\text{cool}\mid \text{yes})=\frac{0}{9}=0$$

Since Naive Bayes multiplies all feature probabilities:

$$P(\text{yes}\mid X)\propto P(\text{yes})\cdot P(\text{sunny}\mid \text{yes})\cdot P(\text{cool}\mid \text{yes})\cdot P(\text{normal}\mid \text{yes})\cdot \dots$$

A single zero makes the entire product zero — even if all other features strongly support "yes." The classifier becomes useless for that instance.

4.8.2 The Solution

Real-World & Domain Connection: Laplace correction is named after Pierre-Simon Laplace (1749–1827), who proposed it as a solution to the "sunrise problem": if the sun has risen every day for 5,000 years, what is the probability it will rise tomorrow? The raw MLE would say $1.0$ (it has always risen), but Laplace argued that adding one "pseudo-observation" of a non-sunrise gives a more philosophically defensible probability. The same principle — never assign zero probability to an event that is logically possible — underpins modern smoothing techniques in NLP (Lidstone smoothing, Good-Turing estimation) and is a foundational idea in Bayesian inference.

Exam Guidance Summary

Core exam skills

- Distinguish the two directions: $P(B\mid A)$ vs $P(A\mid B)$ is the most important skill for this topic. Most exam errors come from confusing these. Before answering any Bayes-related question, pause and ask: "Which direction am I computing? What is given, and what am I finding?"

- Total probability conditions: Mutually exclusive AND exhaustive events are required. Always check that the basic event probabilities sum to 1 before applying total probability. If they don't sum to 1, the formula cannot be applied directly — stop and identify what's missing.

- Tree diagrams are valid in exams: Drawing a tree and computing branch products is an accepted method. The professor explicitly endorses it. It helps avoid formula confusion and makes the denominator computation obvious.

- Bayes Theorem via tree: Numerator = specific branch product. Denominator = sum of all branch products where B occurs. No formula memorization needed — just draw the tree and compute.

- Naive Bayes assumption: Features are assumed conditionally independent given the class. Always state this assumption in your answer. Even if it seems wrong, it is what Naive Bayes requires — and research shows it works.

- HMAP vs MLE: HMAP = likelihood × prior. MLE = likelihood only (when priors are unknown or assumed uniform). Know when to use each.

- Multi-feature problems: Expect questions with multiple features where the Naive Bayes assumption must be applied. You will be given a dataset with several features and asked to classify a new instance.

- Laplace correction: Will be covered in the next session. It handles the zero-probability problem in Naive Bayes. For now, know that it exists and why it is needed (a single zero feature probability kills the entire product).

Common exam question types

1. Total probability: Given $P(A_i)$ and $P(B\mid A_i)$, compute $P(B)$. Check exhaustiveness first. 2. Bayes Theorem: Given the same information, compute $P(A_k\mid B)$. Use tree or formula. 3. Bayes classifier (single feature): Given a dataset table, compute $P(\text{class}\mid \text{feature})$ and predict. 4. Naive Bayes (multiple features): Given a dataset with several features, compute the MAP score for each class and predict. State the independence assumption. 5. Conceptual: Explain the difference between $P(B\mid A)$ and $P(A\mid B)$. Explain why the independence assumption is "naive" and why it is acceptable.

Key Industry Applications

The concepts covered in this lecture — conditional probability, total probability, Bayes Theorem, and Naive Bayes — power a remarkable range of real-world systems. Here are the most prominent applications discussed by the professor.

Email spam filtering

Gmail and other email providers use Naive Bayes (historically and as a core component) to classify incoming mail as spam or legitimate. Each word in an email is a feature; the classifier learns $P(\text{word}\mid \text{spam})$ and $P(\text{word}\mid \text{not spam})$ from millions of labeled messages. Early Gmail explicitly asked users "Is this spam?" to collect training labels. Today the model is mature enough to auto-classify with high confidence, rarely asking for confirmation unless you browse the spam folder.

Medical diagnosis

Given a set of symptoms (features), predict the presence of a disease (class). The prior $P(\text{disease})$ comes from population prevalence statistics. The likelihoods $P(\text{symptom}\mid \text{disease})$ come from clinical studies. Bayes Theorem combines them to compute $P(\text{disease}\mid \text{symptoms})$ — exactly what a doctor needs. The professor's example of medical testing (sensitivity, specificity) in the conditional probability section is the foundation of evidence-based medicine.

Sentiment analysis

Classifying product reviews, tweets, or customer comments as positive or negative. Each word is a feature; the classifier learns which words are associated with positive sentiment ("great," "love," "amazing") and which with negative sentiment ("terrible," "broken," "refund"). Naive Bayes is fast enough to process millions of social media posts in real time and interpretable enough to show why a review was classified a certain way.

Document categorization

Assigning topics or tags to text documents — news articles (sports, politics, technology), legal documents (contract, patent, brief), or support tickets (billing, technical, account). The "one-vs-rest" strategy extends binary Naive Bayes to multi-class categorization. This is a standard application in enterprise content management and legal e-discovery platforms.

Ad click prediction and retail analytics

Predicting which device or customer segment is most likely to generate clicks, purchases, or other conversions. Total probability computes the overall conversion rate across segments; Bayes Theorem identifies which segment is the dominant source of conversions — exactly like the "finding the culprit" spam example. Gas station and retail customer behavior analysis follow the same pattern.

Why these applications endure

Naive Bayes persists in production systems — even in the deep learning era — because of three irreplaceable properties: 1. Training speed: One pass over the data. No gradient descent, no hyperparameter tuning. 2. Prediction speed: A few multiplications and comparisons per instance. Suitable for real-time systems. 3. Interpretability: You can inspect which features (words) most strongly indicate each class. In regulated industries (healthcare, finance), this explainability is often a legal requirement.