Naive Bayes Classifier
Implement a Naive Bayes text classifier.
Training: Given labeled documents, compute:
- Prior: P(c)=total docscount of docs in class c
- Likelihood: P(w∣c)=total words in class c+∣V∣count of w in class c+1 (Laplace smoothing)
Where |V| is the vocabulary size (unique words across all documents).
Prediction: For a test document, compute: argmaxc[logP(c)+∑w∈doclogP(w∣c)]
Input format:
- Line 1: Number of training documents N
- Lines 2 to N+1: label followed by the document text (space-separated words)
- Line N+2: Test document (space-separated words)
Output: The predicted class label.
Example:
4 pos I love this movie pos great film wonderful neg terrible movie awful neg bad film horrible I love this film
pos
Training counts:
- pos: 2 docs, words: [I, love, this, movie, great, film, wonderful] = 7 words
- neg: 2 docs, words: [terrible, movie, awful, bad, film, horrible] = 6 words
- Vocabulary size |V| = 11 unique words
Priors: P(pos) = 2/4 = 0.5, P(neg) = 2/4 = 0.5
Test doc: "I love this film" For class "pos": log(0.5) + log(P("I"|pos)) + log(P("love"|pos)) + log(P("this"|pos)) + log(P("film"|pos)) Each P(w|pos) uses (count+1)/(7+11) = (count+1)/18
For class "neg": similar but lower scores for "I", "love", "this"
Result: pos has higher score.
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
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.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.