ConceptDBISAI-written · not yet proofread

Naive Bayes Classifier

Also Naive Bayes · Multinomial Naive Bayes

A probabilistic text classifier that predicts the class c maximizing p_c times the product of the word probabilities p_wc over the words of the document, assuming that the words are independent given the class.

Know these firstBayes' Theorem Conditional Probability Statistical Independence

Definition

Let $C$ be a set of classes and $V$ a vocabulary. A document $d$ is a sequence of words from $V$ ; $n_w(d)$ is the number of occurrences of word $w$ in $d$ . A Naive Bayes classifier has one parameter $p_c = \Pr(c)$ per class (the class prior) and one parameter $p_{wc} = \Pr(w \mid c)$ per word and class (the probability that a word of a class- $c$ document is $w$ ), with $\sum_{w \in V} p_{wc} = 1$ for every $c$ . It predicts

\hat c(d) = \arg\max_{c \in C}\; p_c \cdot \prod_{w \in d} p_{wc} = \arg\max_{c \in C}\; p_c \cdot \prod_{w \in V} p_{wc}^{\,n_w(d)},

where the first product runs over the word occurrences of $d$ (with repetitions).

Formula#

Derivation. By Bayes’ Theorem, $\Pr(c \mid d) = \Pr(d \mid c)\,\Pr(c) / \Pr(d)$ . The denominator $\Pr(d)$ is the same for all classes and drops out of the $\arg\max$ . The naive assumption is that the words of $d$ are independent given the class, so $\Pr(d \mid c) = \prod_{w \in d} \Pr(w \mid c)$ (conditional independence). Together:

\Pr(c \mid d) \;\propto\; p_c \cdot \prod_{w \in d} p_{wc}.

Training (learning step) on labelled documents, by relative frequencies:

p_c = \frac{\#\text{training documents of class } c}{\#\text{training documents}}, \qquad p_{wc} = \frac{n_{wc}}{n_c},

where $n_{wc}$ is the number of occurrences of $w$ in all training documents of class $c$ and $n_c = \sum_{w \in V} n_{wc}$ is the total number of word occurrences in class $c$ .

Prediction in log space. $\log$ is strictly increasing, so

\hat c(d) = \arg\max_{c}\; \Big(\log p_c + \sum_{w \in V} n_w(d) \cdot \log p_{wc}\Big).

With the matrix $M \in \mathbb{R}^{|C| \times (|V|+1)}$ whose row $c$ is $(\log p_{w_1 c}, \dots, \log p_{w_{|V|} c}, \log p_c)$ and the document vector $x = (n_{w_1}(d), \dots, n_{w_{|V|}}(d), 1)$ , all class scores are one matrix-vector product $M \cdot x$ , and $\hat c(d) = \arg\max(M \cdot x)$ (exam WS 19/20, Task 4.3).

Properties#

Zero probabilities. If a word $w$ of $d$ never occurs in the training documents of class $c$ , then $p_{wc} = 0$ and the score of $c$ is $0$ , whatever the other words say. If every class has such a word, all scores are $0$ . Smoothing fixes this, and it is also needed for the log-space version ( $\log 0$ is undefined).
Naive Bayes is a Linear Classifier. For two classes $X, Y$ it predicts $X$ iff $\sum_{w \in V} n_w(d)\,\big(\log p_{wX} - \log p_{wY}\big) \;>\; \log p_Y - \log p_X,$ i.e. iff $w \cdot x > b$ with $x = (n_w(d))_{w \in V}$ , weights $w_i = \log(p_{w_i X} / p_{w_i Y})$ and threshold $b = \log(p_Y / p_X)$ . The decision boundary is a hyperplane in the space of word-count vectors.
Document length and the prior. Repeating a document $k$ times raises the word part of the score to the $k$ -th power but leaves $p_c$ unchanged: $s_c(d^k) = p_c \cdot \big(\prod_{w \in d} p_{wc}\big)^k$ . With equal priors the prediction is invariant under repetition; with unequal priors the word evidence outweighs the prior for long enough documents, so the prediction can change (exam WS 17/18, Task 4.2–4.3).
Rounding. A product of many probabilities $< 1$ underflows to $0$ in floating point. The log-space sum avoids this.
Ties must be broken by a fixed rule (e.g. by the larger class id, exam WS 17/18, Task 4).

Example#

ExampleTraining and prediction

Classes $S$ (sport) and $P$ (politics). Training documents: $S$ : “ball goal”, “ball ball”; $P$ : “vote law”, “vote ball”.

Priors: $p_S = p_P = 2/4 = 1/2$ .
Class $S$ : $n_S = 4$ , $n_{\text{ball},S} = 3$ , $n_{\text{goal},S} = 1$ , so $p_{\text{ball},S} = 3/4$ , $p_{\text{goal},S} = 1/4$ , $p_{\text{vote},S} = p_{\text{law},S} = 0$ .
Class $P$ : $n_P = 4$ , so $p_{\text{vote},P} = 2/4$ , $p_{\text{law},P} = 1/4$ , $p_{\text{ball},P} = 1/4$ , $p_{\text{goal},P} = 0$ .

Document “ball vote”: score $S$ $= \frac12 \cdot \frac34 \cdot 0 = 0$ , score $P$ $= \frac12 \cdot \frac14 \cdot \frac24 = \frac1{16}$ , so $\hat c = P$ . Document “ball goal vote”: both scores are $0$ (goal is unseen in $P$ , vote is unseen in $S$ ). See Laplace Smoothing > Example for the smoothed version.

ExampleNaive Bayes on points in $\mathbb{R}^2$ (exam WS 16/17, Task 4.3)

Take the coordinates of a point as word counts of a two-word vocabulary. Training: $P_1 = (3,1)$ in class $X$ , $P_2 = (1,2)$ and $P_3 = (1,4)$ in class $Y$ . Then $p_X = 1/3$ , $p_Y = 2/3$ , $p_{1X} = 3/4$ , $p_{2X} = 1/4$ , $p_{1Y} = 2/8 = 1/4$ , $p_{2Y} = 6/8 = 3/4$ . A point $(x, y)$ is classified $X$ iff

\log\tfrac13 + x \log\tfrac34 + y \log\tfrac14 > \log\tfrac23 + x \log\tfrac14 + y \log\tfrac34 \iff (\ln 3)\,x - (\ln 3)\,y > \ln 2,

a linear classifier with $w = (\ln 3, -\ln 3)$ and $b = \ln 2$ .

Sources#

Not covered by a WS 25/26 lecture. Source: the former Information Retrieval exams.
Exam WS 17/18, Task 4 (not published) (prediction with for-loops, document repetition)
Exam WS 16/17, Task 4.3–4.4 (not published) (Naive Bayes as a linear classifier)
Exam WS 19/20, Task 4.2–4.3 (not published) (smoothing, prediction as a matrix-vector product)
Exam WS 21/22, Task 4.3 (not published) (training on the numbers 0..15)
Exam WS 22/23, Task 4.1 (not published) (predict returning class and probability)