Generative Learning Algorithms: Naive Bayes and Laplace Smoothing

# Generative Learning Algorithms: Naive Bayes and Laplace Smoothing **Video Category:** Machine Learning Lecture ## 📋 0. Video Metadata **Video Title:** Not explicitly stated (Inferred: Generative Learning Algorithms, Naive Bayes) **YouTube Channel:** Stanford Engineering **Publication Date:** Not shown in video **Video Duration:** ~1 hour 23 minutes ## 📝 1. Core Summary (TL;DR) This lecture explores generative learning algorithms, contrasting them with discriminative models by highlighting the fundamental trade-off between modeling assumptions and data requirements. It introduces the Naive Bayes algorithm as a powerful generative approach for discrete data, demonstrating its application in text classification tasks like spam filtering using a bag-of-words feature representation. Finally, it addresses the critical "zero-probability" flaw inherent in basic Naive Bayes using Laplace smoothing, a technique that prevents the model from failing when encountering previously unseen features in real-world data. ## 2. Core Concepts & Frameworks * **Generative vs. Discriminative Models:** -> **Meaning:** Generative models (like Gaussian Discriminant Analysis - GDA) learn by modeling the joint distribution $p(x, y)$ or $p(x|y)$ and $p(y)$, attempting to understand how the data was generated. Discriminative models (like Logistic Regression) model $p(y|x)$ directly, focusing solely on the decision boundary between classes. -> **Application:** Generative models are preferred when data is scarce but domain knowledge allows for strong, correct assumptions about the data distribution. Discriminative models are preferred when data is abundant and modeling the input distribution is too complex or unnecessary. * **Naive Bayes Assumption:** -> **Meaning:** A simplifying assumption used in the Naive Bayes algorithm stating that all features $x_1, x_2, ..., x_d$ are conditionally independent given the class label $y$. Mathematically, $p(x_1, ..., x_d | y) = \prod_{j=1}^d p(x_j | y)$. -> **Application:** This assumption makes it computationally feasible to model high-dimensional discrete data, such as text documents, where calculating the true joint probability of thousands of words would be impossible. * **Bag-of-Words Feature Representation:** -> **Meaning:** A method for representing text data where a document is transformed into a binary vector $x \in \{0,1\}^d$. The dimension $d$ is the size of a predefined vocabulary. Each element $x_j = 1$ if the $j$-th word in the vocabulary appears in the document, and $0$ otherwise. -> **Application:** Used to convert emails into mathematical vectors so they can be processed by machine learning algorithms like Naive Bayes for spam classification. * **Laplace Smoothing (Add-One Smoothing):** -> **Meaning:** A technique to handle the problem of zero probabilities in categorical data. Instead of calculating probabilities purely by empirical frequencies, pseudo-counts are added. For a variable taking $k$ possible values, 1 is added to the count of the specific event, and $k$ is added to the total number of events. -> **Application:** In Naive Bayes text classification, it ensures that if a word appears in a test email but never appeared in the training set for a specific class, its probability is small but non-zero, preventing the entire document probability from collapsing to zero. ## 3. Evidence & Examples (Hyper-Specific Details) * **GDA implies Logistic Regression Form:** The lecturer demonstrates mathematically that if you assume $X|y=0 \sim \mathcal{N}(\mu_0, \Sigma)$, $X|y=1 \sim \mathcal{N}(\mu_1, \Sigma)$, and $y \sim \text{Bernoulli}(\phi)$ (the GDA assumptions), it implies that the posterior probability $p(y=1|x)$ takes the exact form used in Logistic Regression: $\frac{1}{1 + e^{-\theta^T x + \theta_0}}$. This shows that GDA makes stronger assumptions that lead to a specific discriminative form. * **Spam Classification Vocabulary:** To represent emails, a vocabulary list is created, e.g., ["a", "aardvark", "aardwolf", ..., "book", ..., "zymurgy"], with a total of $d$ words. * **Feature Vector Construction:** The sentence "I buy a book" is converted into a feature vector $x$. If the word "a" is at index 1 and "book" is at index $j$, then $x_1 = 1$, $x_j = 1$, and words not in the sentence (like "aardvark" at index 2) have $x_2 = 0$. * **Naive Bayes Maximum Likelihood Estimates:** The parameters are derived as empirical fractions: * $\phi_{j|y=1} = \frac{\sum_{i=1}^n \mathbb{I}(x_j^{(i)}=1, y^{(i)}=1)}{\sum_{i=1}^n \mathbb{I}(y^{(i)}=1)}$ (Fraction of spam emails containing word $j$) * $\phi_{j|y=0} = \frac{\sum_{i=1}^n \mathbb{I}(x_j^{(i)}=1, y^{(i)}=0)}{\sum_{i=1}^n \mathbb{I}(y^{(i)}=0)}$ (Fraction of non-spam emails containing word $j$) * $\phi_y = \frac{\sum_{i=1}^n \mathbb{I}(y^{(i)}=1)}{n}$ (Fraction of all emails that are spam) * **The Zero Probability Problem (Aardvark Example):** If the word "aardvark" (index 2) never appears in the training set, then $\sum_{i=1}^n \mathbb{I}(x_2^{(i)}=1, y^{(i)}=1) = 0$. Therefore, the estimate $\phi_{2|y=1} = 0$. If a new test email contains "aardvark", the calculation for $p(x|y=1)$ involves multiplying by $\phi_{2|y=1}$, resulting in $0$. The model fails to classify the email because $p(x|y=1) = 0$ and $p(x|y=0) = 0$, leading to a $0/0$ division when calculating $p(y=1|x)$. * **Laplace Smoothing Coin Toss Example:** Suppose you toss a biased coin 3 times and get 3 tails (0 heads). Vanilla maximum likelihood gives $p(head) = 0/3 = 0$. Applying Laplace smoothing (where $k=2$ for heads/tails), the new estimate is $\phi = \frac{0 + 1}{3 + 2} = \frac{1}{5}$. This provides a more reasonable, non-zero probability. * **Laplace Smoothing in Naive Bayes:** The updated formula for the parameter with smoothing applied is: $\phi_{j|y=1} = \frac{\sum_{i=1}^n \mathbb{I}(x_j^{(i)}=1, y^{(i)}=1) + 1}{\sum_{i=1}^n \mathbb{I}(y^{(i)}=1) + 2}$. The $+2$ in the denominator is because the feature $x_j$ can take $k=2$ values (0 or 1). ## 4. Actionable Takeaways (Implementation Rules) * **Rule 1: Choose Generative Models based on Data Volume and Prior Knowledge** - If you have a small dataset but strong, confident knowledge about the underlying distribution of your data (e.g., you know it's normally distributed), use a generative model like GDA. It will converge faster than a discriminative model. If data is abundant or assumptions are weak, default to discriminative models like Logistic Regression. * **Rule 2: Implement Naive Bayes for High-Dimensional Text Classification** - When building systems like spam filters where features are thousands of discrete word occurrences, use the Naive Bayes algorithm. Calculate parameters by simply counting the frequency of each word in spam vs. non-spam training examples. * **Rule 3: Always Apply Laplace Smoothing to Discrete Generative Models** - When implementing Naive Bayes, never use raw empirical fractions for probabilities. Always add 1 to the numerator (occurrences of the feature) and $k$ (the number of possible values the feature can take, usually 2 for binary word presence) to the denominator. This prevents the model from mathematically crashing when it encounters new vocabulary in production. * **Rule 4: Simplify Text Representation with Bag-of-Words** - When preprocessing text for basic Naive Bayes, ignore word order, grammar, and word frequency within a single document. Represent the document solely as a binary vector indicating whether a word from your vocabulary is present or absent. ## 5. Pitfalls & Limitations (Anti-Patterns) * **Pitfall:** Making incorrect generative assumptions. -> **Why it fails:** Generative models like GDA derive their decision boundaries from assumed distributions ($p(x|y)$). If the real data severely violates these assumptions (e.g., using GDA on heavily skewed, non-Gaussian data), the resulting decision boundary will be suboptimal compared to a model that doesn't make those assumptions. -> **Warning sign:** A simpler discriminative model (like Logistic Regression) significantly outperforms the generative model on validation data. * **Pitfall:** Deploying Naive Bayes without smoothing. -> **Why it fails:** The algorithm assumes conditional independence and calculates the probability of a document by multiplying the probabilities of individual words. If a single word in a test document has an estimated probability of exactly 0 (because it wasn't in the training set), the entire product becomes 0, rendering the model incapable of making a prediction. -> **Warning sign:** The system throws errors (like division by zero) or defaults to erratic classifications when processing real-world inputs containing novel vocabulary. * **Pitfall:** Relying on Bag-of-Words for context-dependent tasks. -> **Why it fails:** The Bag-of-Words model discards word order and context. The sentences "I buy a book" and "A book I buy" have the exact same feature vector. -> **Warning sign:** The model fails to distinguish between sentences with identical vocabulary but completely different meanings or sentiment. ## 6. Key Quote / Core Insight The fundamental trade-off in machine learning algorithm selection is between the strength of your assumptions and the amount of data required: stronger mathematical assumptions require less training data to converge on a solution, but if those assumptions are flawed, the model's performance will permanently suffer regardless of data size. ## 7. Additional Resources & References No external resources explicitly mentioned in this video.