Naïve Bayes
1 Introduction
In the conditional-models chapter, we built a model of the form \(P(Y)\,P(X \mid Y)\), a class prior together with a class-conditional distribution over the features, and found it worked cleanly for one feature, discrete or continuous, but exploded exponentially the moment we tried to extend it to several features at once. We noted that there is a way to keep this recipe’s advantages without the exponential blow-up. This chapter presents a solution that fixes the exponential blow-up with a single, deliberately naive assumption.
2 Generative Classifiers
The model we built in the previous chapter is a generative classifier, even though we didn’t name it that at the time. It aimed to learn the data-generating distribution during training, and to classify a new example, it needed to use Bayes’ rule during inference. Let’s revisit the concepts we learnt about probabilistic modelling in the context of generative classifiers, before comparing them to other models we learnt about previously, e.g., logistic regression.
A generative classifier is defined by describing how the data was supposedly produced. It learns the joint probability \(P(X, Y) = P(Y) P(X \mid Y)\). The name “generative” comes from the fact that we can generate new data points from that distribution, i.e., we can generate new samples that look like they were produced from the same distribution as our data.
For example, once we learn \(P(Y)\) and \(P(X \mid Y)\) for our example of the opposing team’s rating and the match’s final outcome, we can generate a synthetic data point by sampling a match result (loss/win) from the prior distribution \(P(Y)\). This was a Bernoulli distribution for the two-class case. Based on the result we received, we then sample the opposing team’s score from the class-conditional distribution \(P(X \mid Y)\).
Concretely, the model says: first flip a coin for whether our team lost or won, then draw the opposing team’s score from whichever distribution, \(P(X \mid Y = 1)\) or \(P(X \mid Y = 0)\), matches that outcome. These are two separate distributions, one describing what the opposing team’s ratings look like in games we win and one describing what the opposing team’s ratings look like in games we lose.
2.1 Training
Learning still involves calculating the MLE or MAP estimates of the model’s parameters from the data. This follows the exact same recipe we discussed earlier.
2.2 Inference
Once we have \(P( X \mid Y)\) and \(P(Y)\), prediction for a new example is a direct application of Bayes’ rule:
\[ \begin{aligned} \underbrace{P(Y \mid X)}_{\text{posterior}} = \frac{ \overbrace{P(Y)}^{\text{class prior}} \overbrace{P(X \mid Y)}^{\text{class likelihood}} \; }{\underbrace{P(X)}_{\text{evidence}}} . \end{aligned} \]
where the evidence is obtained by the law of total probability: \[ \begin{aligned} & P(X) \\ & = \sum_{c \in \{0, 1\}} P(X, Y = c) \\ & = \sum_{c \in \{0, 1\}} P(Y = c) P(X \mid Y = c) \\ & = P(Y {=} 0) P(X \mid Y {=} 0) + P(Y {=} 1) P(X \mid Y {=} 1) \end{aligned} \]
Note, however, that if we are only interested in a prediction (which class to assign), we don’t actually need to calculate \(P(X)\).
When making a prediction, we are trying to calculate: \[ \begin{aligned} & \arg\max_{c}\; P(Y = c \mid X) \\ & = \arg\max_{c}\; \frac{P(Y = c) P(X \mid Y = c)}{P(X)} \end{aligned} \]
As is evident from the above equation, \(P(X)\) doesn’t depend on the choice of \(c\), i.e., we use the same normalizing constant for all classes. As a result, to decide which class is more probable, we only need to compare numerators:
\[ \begin{aligned} & \arg\max_{c}\; P(Y = c \mid X) \\ & = \arg\max_{c}\; P(Y = c)\,P(X \mid Y = c) \end{aligned} \]
2.3 Discriminative vs. Generative Classifiers
Up until the probabilistic-modelling chapters, we had only discussed classifiers like logistic regression and softmax regression, which learn the decision boundary directly. In contrast, generative classifiers, introduced in this chapter, work by modelling the probability distribution of the data itself.
These are actually two fundamentally different ways to solve a supervised classification problem. This distinction is usually called discriminative vs. generative, and it’s worth pinning down precisely.
2.3.1 Discriminative Classifiers: “How Do I Separate the Classes?”
A discriminative classifier learns a mapping directly from inputs to labels by modelling \(P(y \mid x)\) only. It never specifies a distribution over \(x\).
During training, the model learns \(P(y \mid x)\) directly (e.g., logistic regression fits a softmax/sigmoid of \(w^\top x + b\)). During inference, for a new data point, the model simply evaluates \(\arg\max_{y' \in \text{classes}} P(y=y' \mid x)\). Examples include logistic regression, softmax regression, and decision trees.
2.3.2 Generative Classifiers: “What Does Each Class Look Like?”
A generative classifier models how the data for each class has been generated by modelling the joint distribution \(P(x, y) = P(y) P(x \mid y)\).
During training, the model learns \(P(x, y) = P(y) P(x \mid y)\). During inference, the model needs to calculate \(P(y \mid x)\) using Bayes’ rule to evaluate \(\arg\max_{y' \in \text{classes}} P(y=y' \mid x)\). Examples include Bayes classifiers, Naïve Bayes, and Gaussian Discriminant Analysis.
3 A New Example: Match Review Classification
Suppose we want to label short match reviews as positive or negative. This will be the running example for the rest of this chapter. Our goal is to classify each match review as positive \((y = 1)\) or negative \((y = 0)\).
| Review | Text | Class |
|---|---|---|
| 1 | “keeper was sharp and composed” | positive |
| 2 | “match was composed” | positive |
| 3 | “brilliant match” | positive |
| 4 | “match was not sharp” | negative |
| 5 | “match was not composed” | negative |
A discriminative view of our task is: given the text of a review (features \(x\)), what is \(P(y \mid x)\), i.e., the probability it is positive? We learn a mapping straight from words to a label. A generative view, on the other hand, asks: given that a review is positive (or negative), what text (features \(x\)) would we expect to see? We learn \(P(x \mid y=1)\) and \(P(x\mid y= 0)\) (“what do positive reviews look like? what do negative reviews look like?”), and only then flip the question around with Bayes’ rule to classify a new review.
4 Bag-of-Words Features
In order to classify our reviews, we first need to turn text into a feature vector \(x\). The simplest approach is bag-of-words, where we treat a piece of text as a collection of its words, disregarding word order and the number of times each word occurs. To do that, we need to build a vocabulary of all unique words across the dataset. We then represent each piece of text as a vector of \(0\)s and \(1\)s, one entry per vocabulary word, indicating whether that word appears.
Let’s use the dataset provided above as an example:
The vocabulary is all unique words across the five reviews: keeper, was, sharp, and, composed, match, brilliant, not. Since our vocabulary contains \(8\) words, each feature vector would consist of \(D=8\) features as well, corresponding to the words in our vocabulary.
Question: Write the bag-of-words features for each review.
Answer:
| Review | keeper | was | sharp | and | composed | match | brilliant | not | Class |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | positive |
| 2 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | positive |
| 3 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | positive |
| 4 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | negative |
| 5 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | negative |
Each row is now a length-\(8\) binary vector \(x=(x_1,\dots,x_8)\).
4.1 Properties of Bag-of-Words Features
While simple, the bag-of-words approach to building feature vectors has many favourable properties.
It is simple, efficient, and scalable: any piece of text becomes a fixed-length vector, of length \(|\text{vocabulary}|\), regardless of how long the original text was. It is also surprisingly effective for many text classification tasks (sentiment analysis, spam detection, topic categorisation) since certain words carry a strong signal on their own.
However, it ignores word order and frequency: “Match was not brilliant” and “brilliant, was match not” would produce the same feature vector. This is a real limitation, but it is also what makes the model tractable, and it is foundational for more advanced models that do account for order.
5 Naïve Bayes
5.1 The Remaining Challenge
Our bag-of-words vectors have \(D=8\) entries. During training, we learn \(P(x_1, \dots , x_D, y) = P(y) P(x_1, \dots , x_D \mid y)\). To classify a new review, we apply Bayes’ rule during inference. But the conditional-models chapter already showed what happens if we model \(P(x_1,\dots,x_D\mid y)\) in full: the number of parameters doubles with every additional feature, giving \(2^{D+1}-1\) parameters in total. For a real vocabulary of hundreds or thousands of words, this is completely hopeless both to store and to estimate from any realistic amount of data.
We need to cut this down without giving up on the generative recipe. The fix is a single, deliberately simplifying assumption.
5.2 The Naïve Assumption
Naïve Bayes assumes the features are conditionally independent given the class: \[ \begin{aligned} & P(x_1, x_2, \dots, x_D \mid y) \\ & = P(x_1 \mid y)\,P(x_2 \mid y)\,\cdots\,P(x_D\mid y) \\ & = \prod_{j=1}^{D}P(x_j\mid y). \end{aligned} \]
This is not the same as saying \(x_j\) and \(x_k\) are (marginally) independent (they generally are not). It says that once you already know the class, learning whether one word appears tells you nothing more about whether another word appears. Concretely: knowing that a review is positive, learning that the word “brilliant” appears tells us nothing extra about whether “composed” also appears. This is a strong, and literally false, assumption about real language, but it turns out to work well in practice, and it is exactly what makes the parameter count manageable.
As a graphical model, this is the simplest possible Bayesian network: the class \(y\) is a single parent node, and every feature \(x_j\) is a child with no edges between the features themselves.
5.3 Naïve Bayes Parameters
\(Y\) is a binary random variable representing whether a review is positive (\(Y = 1\)) or negative (\(Y = 0\)).
Additionally, each feature \(X_j\) is a binary random variable representing the presence (\(X_j = 1\)) or absence (\(X_j = 0\)) of the \(j^{\text{th}}\) word. As a result, we can model all variables using Bernoulli distributions, where:
\[ \begin{aligned} & Y \sim \mathrm{Bernoulli}(\pi), \\ & X_j \mid Y \sim \mathrm{Bernoulli}(\theta_{j,c}) \end{aligned} \]
Or equivalently, writing out each probability explicitly: \[ \begin{aligned} & P(Y = 1 ) = \pi, \\ & P(X_j = 1 \mid Y = 1) = \theta_{j,1}, \\ & P(X_j = 1 \mid Y = 0) = \theta_{j,0} \end{aligned} \]
Question: How many parameters do we need to learn by applying the Naïve Bayes assumption?
Answer:
\(P(y)\) needs \(1\) parameter, \(\pi\). \(P(x_j \mid y)\) needs \(1\) parameter per word, per class, i.e., \(D\) parameters for \(c{=}1\), and \(D\) more for \(c{=}0\).
\[ \begin{aligned} \boxed{\;1+2D\text{ parameters total,}\;} \end{aligned} \]
By employing the Naïve Bayes assumption, we need to learn \(2 D + 1\) parameters, compared to \(2^{D+1}-1\) for the full joint. For our \(D=8\)-word vocabulary, that’s \(17\) parameters instead of \(511\), and the gap only widens as the vocabulary grows.
5.4 Training
As for any generative classifier, training refers to the process of learning the parameters \(\theta = \{\pi\} \cup \{ \theta_{j,c} \}_{j=1,c=0}^{j=D,c=1}\) from the data using one of the methods we learnt earlier: Maximum Likelihood Estimation or Maximum-A-Posteriori Estimation.
In these notes, we will focus on deriving and calculating the MLE of our parameters \(\theta\), i.e., the parameter values that maximize the probability of the data.
To derive the estimates, we will follow the same steps presented in the previous two chapters:
- Derive the likelihood of data given the parameter(s).
- Derive the log-likelihood of data given the parameter(s).
- Take the derivative of the log-likelihood w.r.t. the parameter(s).
- Set the derivative to \(0\) and solve for the parameter(s).
First, we need to derive the likelihood function that assesses how likely it is to observe our reviews given the parameters. \[ \begin{aligned} & \mathcal{L}(\theta) = P(\mathcal{D} | \theta) \\ & = P((\mathbf{x}^{(1)}, y^{(1)}), (\mathbf{x}^{(2)}, y^{(2)}), \dots, (\mathbf{x}^{(N)}, y^{(N)}) \mid \theta) \end{aligned} \]
Given that our observations are independent and identically distributed:
\[ \begin{aligned} & = \prod_{i=1}^{N} P(\mathbf{x}^{(i)}, y^{(i)} \mid \theta) \end{aligned} \]
By the chain rule of probability:
\[ \begin{aligned} & = \prod_{i=1}^{N} P(y^{(i)} \mid \theta) P(\mathbf{x}^{(i)} \mid y^{(i)}, \theta) \end{aligned} \]
But remember that \(\mathbf{x}^{(i)}\) is actually a feature vector:
\[ \begin{aligned} & = \prod_{i=1}^{N} P(y^{(i)} \mid \theta) P(\begin{bmatrix} x_1^{(i)} & x_2^{(i)} & \dots & x_D^{(i)} \end{bmatrix}^\top \mid y^{(i)}, \theta) \end{aligned} \]
By the Naïve Bayes assumption:
\[ \begin{aligned} & = \prod_{i=1}^{N} P(y^{(i)} \mid \theta) \left[ P(x_1^{(i)} \mid y^{(i)}, \theta) * P(x_2^{(i)} \mid y^{(i)}, \theta) * \dots P(x_D^{(i)} \mid y^{(i)}, \theta) \right] \\ & = \prod_{i=1}^{N} P(y^{(i)} \mid \theta) \prod_{j=1}^D P(x_j^{(i)} \mid y^{(i)}, \theta) \end{aligned} \]
The log-likelihood is therefore:
\[ \begin{aligned} & \ell(\theta) = \log \mathcal{L}(\theta) \\ & = \log \big[ \prod_{i=1}^{N} P(y^{(i)} \mid \theta) \prod_{j=1}^D P(x_j^{(i)} \mid y^{(i)}, \theta) \big] \\ & = \underbrace{\big[ \sum_{i=1}^{N} \log P(y^{(i)} \mid \theta) \big]}_{\text{Log-likelihood of the prior probability of each class}} \\ & \quad + \underbrace{\big[ \sum_{i=1}^{N} \sum_{j=1}^{D} \log P(x_j^{(i)} \mid y^{(i)}, \theta) \big]}_{\text{Log-likelihood of the probability of each feature given class}} \end{aligned} \]
Since \(Y \sim \mathrm{Bernoulli}(\pi)\), we can express \(P(y^{(i)} \mid \theta)\) as: \[ \begin{aligned} P(y^{(i)} \mid \theta) = \pi^{y^{(i)}} (1 - \pi)^{1 - y^{(i)}} \end{aligned} \]
Similarly, \(X_j \mid Y = c \sim \mathrm{Bernoulli}(\theta_{j,c})\), and so we can express \(P(x_j^{(i)} \mid y^{(i)}, \theta)\) as: \[ \begin{aligned} & \left( \theta_{j,1}^{x_j^{(i)}} (1 - \theta_{j,1})^{1 - x_j^{(i)}} \right)^{y^{(i)}} \cdot \left( \theta_{j,0}^{x_j^{(i)}} (1 - \theta_{j,0})^{1 - x_j^{(i)}} \right)^{1 - y^{(i)}} \end{aligned} \]
The log-likelihood can therefore be expressed as: \[ \begin{aligned} & \ell(\theta) \\ & = \big[ \sum_{i=1}^{N} \left( y^{(i)} \log \pi + (1 - y^{(i)}) \log(1 - \pi) \right) \big] \\ & \quad + \sum_{i=1}^{N} \sum_{j=1}^{D} \big[ y^{(i)} \left\{ x_j^{(i)} \log \theta_{j,1} + (1 - x_j^{(i)}) \log (1 - \theta_{j,1}) \right\} \big] \\ & \quad + \sum_{i=1}^{N} \sum_{j=1}^{D} \big[ (1 - y^{(i)}) \left\{ x_j^{(i)} \log \theta_{j,0} + (1 - x_j^{(i)}) \log (1 - \theta_{j,0}) \right\} \big] \end{aligned} \]
Exactly as in the conditional-models chapter, the log-likelihood decomposes into \(D + 1\) independent pieces: one for \(\pi\) and one for each word’s \((\theta_{j,1},\theta_{j,0})\) pair, so each can be maximised on its own.
To derive the estimate for \(\pi\), we simply take the derivative w.r.t. \(\pi\):
\[ \begin{aligned} & \frac{\partial \ell(\theta)}{\partial \pi} \\ & = \sum_{i=1}^{N} \left( \frac{y^{(i)}}{\pi} - \frac{(1 - y^{(i)})}{(1 - \pi)} \right) \\ & = \frac{\sum_{i=1}^{N} y^{(i)}}{\pi} - \frac{\sum_{i=1}^{N} (1 - y^{(i)})}{(1 - \pi)} \end{aligned} \]
Setting the derivative to \(0\) and solving for \(\pi\): \[ \begin{aligned} & \frac{\sum_{i=1}^{N} y^{(i)}}{\pi} - \frac{\sum_{i=1}^{N} (1 - y^{(i)})}{(1 - \pi)} = 0 \\ & (1 - \pi) \sum_{i=1}^{N} y^{(i)} - \pi \sum_{i=1}^{N} (1 - y^{(i)}) = 0 \\ & \pi = \frac{\sum_{i=1}^{N} y^{(i)}} {\sum_{i=1}^{N} y^{(i)} + \sum_{i=1}^{N} ( 1 - y^{(i)})} \\ & \pi = \frac{\sum_{i=1}^{N} y^{(i)}} {N} \end{aligned} \]
The MLE for \(\pi\) is therefore
\[ \begin{aligned} \hat{\pi} = \frac{\sum_{i=1}^{N} y^{(i)}}{N} \end{aligned} \]
i.e., the proportion of positive reviews.
We similarly derive the estimate for \(\theta_{j,c}\) by taking the derivative w.r.t. \(\theta_{j,c}\):
\[ \begin{aligned} & \frac{\partial \ell(\theta)}{\partial \theta_{j,1}} = \frac{\sum_{i=1}^{N} y^{(i)} x_j^{(i)}}{\theta_{j,1}} - \frac{\sum_{i=1}^{N} y^{(i)} (1 - x_j^{(i)})}{1 - \theta_{j,1}} \end{aligned} \]
and
\[ \begin{aligned} & \frac{\partial \ell(\theta)}{\partial \theta_{j,0}} = \frac{\sum_{i=1}^{N} (1 - y^{(i)}) x_j^{(i)}}{\theta_{j,0}} - \frac{\sum_{i=1}^{N} (1 - y^{(i)}) (1 - x_j^{(i)})}{1 - \theta_{j,0}} \end{aligned} \]
Setting the derivative to \(0\) and solving for \(\theta_{j,c}\) yields: \[ \begin{aligned} & \frac{\sum_{i=1}^{N} y^{(i)} x_j^{(i)}}{\theta_{j,1}} - \frac{\sum_{i=1}^{N} y^{(i)} (1 - x_j^{(i)})}{1 - \theta_{j,1}} = 0 \\ & \Rightarrow \theta_{j,1} = \frac{\sum_{i=1}^N y^{(i)} x_j^{(i)}}{\sum_{i=1}^N y^{(i)}} \\[0.5em] % & \frac{\sum_{i=1}^{N} (1 - y^{(i)}) x_j^{(i)}}{\theta_{j,0}} - \frac{\sum_{i=1}^{N} (1 - y^{(i)}) (1 - x_j^{(i)})}{1 - \theta_{j,0}} = 0 \\ & \Rightarrow \theta_{j,0} =\frac{\sum_{i=1}^N (1 - y^{(i)}) x_j^{(i)}}{\sum_{i=1}^N (1 - y^{(i)})} \end{aligned} \]
The MLE for \(\theta_{j,c}\) is therefore
\[ \begin{aligned} \hat{\theta}_{j,c} = \frac{\sum_{i=1}^{N} \mathbb{1}[x_j^{(i)} = 1 \land y^{(i)} = c]}{\sum_{i=1}^{N} \mathbb{1}[y^{(i)} = c]} \end{aligned} \]
i.e., the fraction of reviews in class \(c\) where this word appears.
Calculating the estimates using our dataset, we get:
\[ \begin{aligned} \hat\pi=\frac{3}{5}. \end{aligned} \]
| Word | \(\hat\theta_{j,1}\) (positive) | \(\hat\theta_{j,0}\) (negative) |
|---|---|---|
| keeper | 1/3 | 0/2 |
| was | 2/3 | 2/2 |
| sharp | 1/3 | 1/2 |
| and | 1/3 | 0/2 |
| composed | 2/3 | 1/2 |
| match | 2/3 | 2/2 |
| brilliant | 1/3 | 0/2 |
| not | 0/3 | 2/2 |
A couple of things to note: “not” never appears in a positive review (\(P(X_{\text{not}} = 1 \mid Y = 1) = 0\)), and “was” appears in every single negative review (\(P(X_{\text{was}} = 0 \mid Y = 0) = 0\)). We will see how this could be problematic in the next section.
5.5 Inference
In order to classify a new review \(\mathbf{x}\), we will need to apply Bayes’ rule to calculate \(P(y \mid \mathbf{x})\):
\[ \begin{aligned} & \arg\max_{c \in \{0, 1\}} P(y = c \mid \mathbf{x}) \\ & = \arg\max_{c \in \{0, 1\}} \frac{P(y = c) P(\mathbf{x} \mid y = c)}{P(\mathbf{x})} \\ & = \arg\max_{c \in \{0, 1\}} P(y = c) P(\mathbf{x} \mid y = c) \end{aligned} \]
Recall that we don’t need to normalize the probability (i.e., we don’t need the denominator) if we are only interested in the more likely class. Instead, it suffices to compute \(P(y = 0) P(\mathbf{x} \mid y = 0)\) and \(P(y = 1) P(\mathbf{x} \mid y = 1)\).
We can then predict the class with the larger value.
When calculating \(P(\mathbf{x} \mid y = c)\), we will also need to apply the Naïve Bayes assumption:
\[ \begin{aligned} & P(\mathbf{x} \mid y = c) \\ & = P(x_1 \mid y =c) \, P(x_2 \mid y =c) \, \cdots \, P(x_D \mid y =c) \\ & = \prod_{j = 1}^D P(x_j \mid y = c) \end{aligned} \]
5.5.1 Example
How would our model classify the review: “match was sharp”?
Since only the words “match”, “was”, and “sharp” are present and every other word in our vocabulary is absent, our feature vector will look like:
\[ \begin{aligned} \mathbf{x} = \begin{bmatrix} 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \end{bmatrix}^\top \end{aligned} \]
Referring back to the parameters estimated earlier, we can calculate:
\[ \begin{aligned} & P(y = 1 \mid \mathbf{x}) \\ & \propto P(y = 1) \prod_{j = 1}^8 P(x_j \mid y = 1) \\ & = \hat{\pi} \, (1 {-} \hat{\theta}_{\text{keeper},1}) \, \hat{\theta}_{\text{was},1} \, \hat{\theta}_{\text{sharp},1} \, (1 {-} \hat{\theta}_{\text{and},1})\, (1 {-} \hat{\theta}_{\text{composed},1}) \, \hat{\theta}_{\text{match},1} \, (1 {-} \hat{\theta}_{\text{brilliant},1}) \, (1 {-} \hat{\theta}_{\text{not},1}) \\ & = \tfrac{3}{5} \cdot \tfrac{2}{3} \cdot \tfrac{2}{3} \cdot \tfrac{1}{3} \cdot \tfrac{2}{3} \cdot \tfrac{1}{3} \cdot \tfrac{2}{3} \cdot \tfrac{2}{3} \cdot \tfrac{3}{3} \\ & \approx 0.00878 \end{aligned} \]
\[ \begin{aligned} & P(y = 0 \mid \mathbf{x}) \\ & \propto P(y = 0) \prod_{j = 1}^8 P(x_j \mid y = 0) \\ & = (1 - \hat{\pi}) \, (1 {-} \hat{\theta}_{\text{keeper},0}) \, \hat{\theta}_{\text{was},0} \, \hat{\theta}_{\text{sharp},0} \, (1 {-} \hat{\theta}_{\text{and},0})\, (1 {-} \hat{\theta}_{\text{composed},0}) \, \hat{\theta}_{\text{match},0} \, (1 {-} \hat{\theta}_{\text{brilliant},0}) \, (1 {-} \hat{\theta}_{\text{not},0}) \\ & = \tfrac{2}{5} \cdot \tfrac{2}{2} \cdot \tfrac{2}{2} \cdot \tfrac{1}{2} \cdot \tfrac{2}{2} \cdot \tfrac{1}{2} \cdot \tfrac{2}{2} \cdot \tfrac{2}{2} \cdot \tfrac{0}{2} \\ & = 0 \end{aligned} \]
Our model will therefore classify this review as a positive review.
Question: How would our model classify the review below?
not sharp match
Answer:
Since only the words “not”, “sharp”, and “match” are present and every other word in our vocabulary is absent, our feature vector will look like:
\[ \begin{aligned} \mathbf{x} = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \end{bmatrix}^\top \end{aligned} \]
Referring back to the parameters estimated earlier, we can calculate:
\[ \begin{aligned} & P(y = 1 \mid \mathbf{x}) \\ & \propto P(y = 1) \prod_{j = 1}^8 P(x_j \mid y = 1) \\ & = \hat{\pi} \, (1 - \hat{\theta}_{\text{keeper},1}) \, (1 - \hat{\theta}_{\text{was},1}) \, \hat{\theta}_{\text{sharp},1} \, (1 {-} \hat{\theta}_{\text{and},1})\, (1 {-} \hat{\theta}_{\text{composed},1}) \, \hat{\theta}_{\text{match},1} \, (1 {-} \hat{\theta}_{\text{brilliant},1}) \, \hat{\theta}_{\text{not},1} \\ & = \tfrac{3}{5} \cdot \tfrac{2}{3} \cdot \tfrac{1}{3} \cdot \tfrac{1}{3} \cdot \tfrac{2}{3} \cdot \tfrac{1}{3} \cdot \tfrac{2}{3} \cdot \tfrac{2}{3} \cdot \tfrac{0}{3} \\ & = 0 \end{aligned} \]
\[ \begin{aligned} & P(y = 0 \mid \mathbf{x}) \\ & \propto P(y = 0) \prod_{j = 1}^8 P(x_j \mid y = 0) \\ & = (1 - \hat{\pi}) \, (1 - \hat{\theta}_{\text{keeper},0}) \, (1 - \hat{\theta}_{\text{was},0}) \, \hat{\theta}_{\text{sharp},0} \, (1 {-} \hat{\theta}_{\text{and},0})\, (1 {-} \hat{\theta}_{\text{composed},0}) \, \hat{\theta}_{\text{match},0} \, (1 {-} \hat{\theta}_{\text{brilliant},0}) \, \hat{\theta}_{\text{not},0} \\ & = \tfrac{2}{5} \cdot \tfrac{2}{2} \cdot \tfrac{0}{2} \cdot \tfrac{1}{2} \cdot \tfrac{2}{2} \cdot \tfrac{1}{2} \cdot \tfrac{2}{2} \cdot \tfrac{2}{2} \cdot \tfrac{2}{2} \\ & = 0 \end{aligned} \]
We just ran into a problem, and the classifier cannot decide.
In the above example, both \(P(y = 1 \mid \mathbf{x})\) and \(P(y = 0 \mid \mathbf{x})\) evaluated to \(0\). This happened because in our very small dataset, “not” never appeared in any of the positive reviews, thus signalling that the review is not positive. Simultaneously, “was” doesn’t appear in the review but appears in every negative review in our dataset, thus signalling that the review cannot be negative.
This is a data-sparsity problem: with only \(2\)–\(3\) examples per class, it’s easy for a word to have appeared \(0\) times in one class purely by chance, or for it to appear in every single review within a class. MLE takes that completely literally. The fix is the same one used for the Bernoulli examples earlier in this chapter: replace the hard MLE estimate \(\hat{\theta}_{j,c}\) with a MAP estimate using a Beta prior, which smooths every \(\hat{\theta}_{j,c}\) away from exact \(0\)s and \(1\)s using pseudo-counts.
6 Summary
We extended our understanding of conditional probabilistic models to generative classifiers. We distinguished between generative and discriminative classifiers:
| Discriminative | Generative | |
|---|---|---|
| Models a distribution over \(x\)? | No | Yes |
| Learn (training) | \(P(Y \mid X)\) only | \(P(X, Y) = P(Y) P(X \mid Y)\) |
| Calculating \(P(Y \mid X)\) for inference | directly | via Bayes’ rule, at inference time |
| Tries to solve | “How do I separate the classes?” | “What does each class look like?” |
| Examples | logistic/softmax regression, decision trees | Bayes classifiers, Naïve Bayes |
We discussed how, with multiple features, modelling the full joint probability distribution becomes computationally expensive since the number of parameters grows exponentially in the number of features. Naïve Bayes assumes that different features are independent given the class, i.e.,
\[ \begin{aligned} P(X_1, \dots, X_D \mid Y = c) = \prod_{j=1}^{D} P(X_j \mid Y=c) \end{aligned} \]
This cuts down the parameter count from \(2^{D+1} - 1\) to \(2D + 1\).
Training a Naïve Bayes model involves calculating the MLE or MAP estimates of the model parameters. Luckily, we saw how the likelihood function, and therefore the log-likelihood, decomposes into \(D + 1\) components, which simplifies the parameter calculation. Unsurprisingly, calculating the parameter MLEs simply involves counting.
During inference, we use Bayes’ rule and the Naïve Bayes assumption to make a prediction based on the larger of the values \(P(Y = 1 \mid \mathbf{x})\) and \(P(Y = 0 \mid \mathbf{x})\). However, we saw a weakness with using the MLEs for words that never occur or always occur in a class. Just like before, the solution requires MAP estimation of the parameters.
We applied our understanding of the Naïve Bayes model in the context of review sentiment analysis. As part of this example, we learnt about representing a review as a bag-of-words. This involves converting text to a fixed-length binary vector, one entry per vocabulary word, ignoring order and frequency.
Please note that we covered the Bernoulli case since we simply modelled the presence and absence of the words in our vocabulary, but the same idea extends to other distributions, e.g., Categorical Naïve Bayes for word counts, or Gaussian Naïve Bayes for continuous features.