Naive Bayes Classifier

mediumPROText ClassificationNLP 2: Applications

Implement a Naive Bayes text classifier.

Training: Given labeled documents, compute:

Prior: $P(c) = \frac{\text{count of docs in class c}}{\text{total docs}}$
Likelihood: $P(w|c) = \frac{\text{count of w in class c} + 1}{\text{total words in class c} + |V|}$ (Laplace smoothing)

Where |V| is the vocabulary size (unique words across all documents).

Prediction: For a test document, compute: $\arg\max_c \left[ \log P(c) + \sum_{w \in doc} \log P(w|c) \right]$

Input:

train_docs: a list of training documents, each a list of words
train_labels: a list of class labels (strings), one per training document
test_doc: the document to classify, as a list of words

Output: The predicted class label (a string).

Example

Input

4
pos I love this movie
pos great film wonderful
neg terrible movie awful
neg bad film horrible
I love this film

Output

pos

Reasoning

Inputs: four training documents (two pos, two neg), each a list of words, and the test document I, love, this, film. Labels are plain strings.
Counts: the pos documents hold 7 words in total, the neg documents hold 6, and there are $|V| = 11$ distinct words across all four documents. Both priors are $P(c) = 2/4 = 0.5$ .
Smoothed likelihoods: for pos the denominator is $7 + 11 = 18$ . Each of I, love, this, film appears once, so each gets $\frac{1+1}{18} = \frac{1}{9}$ . For neg the denominator is $6 + 11 = 17$ : I, love, this never appear, giving $\frac{1}{17}$ each, while film appears once, giving $\frac{2}{17}$ .
Log scores: $\log 0.5 + 4\log\frac{1}{9} \approx -0.6931 - 8.7889 = -9.4820$ for pos, and $\log 0.5 + 3\log\frac{1}{17} + \log\frac{2}{17} \approx -11.3329$ for neg.
Output: pos has the larger (less negative) score, so the answer is pos. Notice that add-1 smoothing keeps the unseen words in neg from making its probability zero; they only pull the score down.

Constraints

Use Laplace smoothing (add-1) for likelihoods
Use log probabilities to avoid underflow
Words are already lowercase
If a test word is not in training vocab, skip it
Labels are strings

Learn this in

Mathematical FoundationsFoundations Probability & StatisticsFoundations NLP FundamentalsML Study Plan ClassificationML Study Plan

More from NLP 2: Applications

BIO Entity Span Extractoreasy Simple Entity Taggereasy Sentiment Word Countereasy Keyword Classifiereasy One-Hot Sequence Encodereasy

Concept primerPREVIEW

Background Knowledge

The Naive Bayes Classifier is a fundamental algorithm in Natural Language Processing (NLP) and Machine Learning (ML). It's based on Bayes' theorem, which describes the probability of an event based on prior knowledge of conditions that might be related to the event. In the context of text classification, we're dealing with multinomial distributions, where each document is a collection of words (features) that contribute to its class label. The Naive Bayes assumption simplifies the problem by treating each word as independent of the others, given the class label.

The prior probability $P(c)$ represents the probability of a document belonging to a particular class $c$ before observing any words. The likelihood $P(w|c)$ represents the probability of observing a word $w$ given that the document belongs to class $c$ . Laplace smoothing is used to avoid zero probabilities when a word is not present in a class. This is achieved by adding 1 to the numerator and the vocabulary size $|V|$ to the denominator when calculating the likelihood.

Understanding the mathematical formulation of the Naive Bayes Classifier is crucial. The logarithmic form is often used for prediction, as it allows us to compute the product of probabilities as a sum of logarithms, which is more numerically stable. The vocabulary size $|V|$ plays a significant role in Laplace smoothing, as it determines the amount of smoothing applied to the likelihood estimates.

Algorithm/Approach

The general approach to solving this problem involves:

Training: Compute the prior probabilities and likelihoods for each class and word.
Prediction: Use the trained model to compute the predicted class label for a test document by finding the class with the highest posterior probability.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.