Naïve Bayes for Text Classification

• Naïve Bayes is used for text classification.
• The lecture covers the task of text classification, the Naïve Bayes Text Classifier, Naïve Bayes learning, Sentiment and Binary Naïve Bayes, and Accuracy, Precision, Recall and F measure.

The Task of Text Classification

• Text classification involves assigning predefined categories to text documents.
• Examples of text classification tasks include sentiment analysis, spam detection, language identification, and assigning categories to news articles

Text Classification Definition

• The input is a document d and a fixed set of classes C = {c1, c2, ..., cJ}.
• The output is a predicted class c that belongs to C.

Classification Methods: Hand-coded Rules

• Classification can be done using hand-coded rules based on the combination of words and other features.
• For example, a spam filter might use the rule: "black-list-address OR ('dollars' AND 'have been selected')".
• Accuracy using hand-coded rules can be high if rules are carefully refined by an expert.
• Building and maintaining these rules can be expensive.

Classification Methods: Supervised Machine Learning

• The input consists of a document d, a fixed set of classes C = {c1, c2, ..., cJ}, and a training set of m hand-labeled documents D = {(d1, c1), ..., (dm, cm)}.
• The output is a learned classifier y: d → c.
• Classifiers can be Naïve Bayes, Logistic regression, Neural networks and k-Nearest Neighbors

Naïve Bayes Intuition

• Naïve Bayes is a classification method based on Bayes' rule.
• The representation of a document is very simple and relies on bag of words.

Bag of Words Representation

• A document's bag of word representation tallies how many times various words occur.

Bayes’ Rule Applied to Documents and Classes

• For a document d and a class c, Bayes' Rule is P(c|d) = [P(d|c)P(c)] / P(d).

Naïve Bayes Classifier

• It returns the class ĉ with the maximum posterior probability (MAP) given the document.
• The formula is ĉ = argmax[c∈C] P(c|d).
• This formula can be rewritten using Bayes' Rule as argmax[c∈C] [P(d|c)P(c)] / P(d).
• Because the probability is the same for all classes, P(d) can be dropped.
• A document d is represented as a set of features (x1,..., xn.)

Multinomial Naïve Bayes Independence Assumptions

• The Bag of Words assumption posits that the location of words in a document doesn't matter.
• Conditional Independence assumes all the feature probabilities P(xi|c) are independent given the class c.
• P(x1, x2, ..., xn|c) = P(x1|c)P(x2|c) ... P(xn|c).

Multinomial Naïve Bayes Classifier

• The formula for the Multinomial Naïve Bayes Classifier is: cMAP = argmax[c∈C] P(x1, x2, ..., xn|c)P(c)
• The Naïve Bayes version of this formula is: cNB = argmax[c∈C] *P(c) ∏[i=1 to n] P(xi|c)

Applying Naïve Bayes Classifiers to Text Classification

• Positions are all word positions in text documents
• The formula is cNB = argmax[c∈C] P(c) ∏[i∈positions] P(wi|c)

Problems with Multiplying Lots of Probs

• Multiplying many probabilities can result in floating-point underflow.
• To avoid issues with floating point underflow, logs can be used because log(ab) = log(a) + log(b)
• Instead of multiplying probabilities, the sum of logs of probabilities is used.

Calculating in Log Space

• Instead of cNB = argmax[c∈C] P(c) ∏[i∈positions] P(wi|c), the calculation becomes argmax[c∈C] log P(c) + ∑[i∈positions] log P(wi|c)
• Taking the log does not change the ranking of classes, the class with the highest probability also has the highest log probability
• Naive Bayes is a linear classifier because it is a max of a sum of weights which makes it a linear function of the inputs

Learning the Multinomial Naive Bayes Model

• Maximum likelihood estimation (MLE) is used.
• P(c) = Nc / N, where Nc is the number of documents in class c, and N the total.
• P(wi|c) = count(wi, c) / ∑w∈V count(w, c), where count(w,c) is the number of times that word w occurs in documents of class c in the training data

Parameter Estimation

• P(wi|c) = count(wi, c) / ∑w∈V count(w, c) which is the fraction of times word wi appears among all words in documents of topic c.
• To create a mega-document, concatenate all docs for topic j.
• Then the word w frequency is used in mega-document

Problem with Maximum Likelihood

• MLE can return a zero when a term-class combination do not occur in the training data.
• For example, if there's no training document with the word "fantastic", then P("fantastic"|positive) = count("fantastic", positive) / ∑w∈V count(w, positive) = 0.

Laplace (add-1) Smoothing for Naïve Bayes

• P(wi|c) = [count(wi, c) + 1] / ∑(count(w, c) + 1)
• Can also be expressed as [count(wi, c) + 1] / (∑w∈V count(w,c)) + |V|

Multinomial Naïve Bayes: Learning

• Extract the vocabulary from the training corpus.
• Calculate P(cj) terms.
• Calculate P(wk | cj) terms
• For each cj in C do: docsj ← all docs with class = cj
• For each word wk in Vocabulary: nk ← # of occurrences of wk in Textj
• Textj ← single doc containing all docsj.
• P(wk | cj) ← [nk + α] / [n+α | Vocabulary |].

Unknown Words

• Words that appear in test data but not in the training data or vocabulary can be ignored.
• Remove unknown words from the test document.
• There is no probability included for them.
• An unknown word model isn't built because knowing which class has more unknown words is not generally helpful.

Stop Words

• Some systems ignore stop words
• Sort the vocabulary by word frequency in training set
• Words like "the" and "a" can be very frequent.
• The top 10 or 50 words or so form the stop word list.
• All stop words are removed from both training and test sets.
• Stop words are removed as if they were never there.
• Most NB algorithms use all words and don't use stop word lists.

Sentiment and Binary Naïve Bayes

• Optimize for sentiment analysis.
• Word occurrence seems more important than word frequency.
• The occurrence of the word 'fantastic' tells a lot
• The fact that it occurs 5 times may not tell much more.
• Clip word counts at 1 by implementing binary multinominal naïve bayes, or binary NB.

Binary Multinominal Naive Bayes on a Test Document d

• Remove all duplicate words from d
• Compute NB using the same equation: cNB = argmax P(cj) ∏ P(wi | cj), where the argmax is taken over all cj ∈ C, and the product is taken over all i ∈ positions

Evaluation

• Consider binary text classification tasks to evaluate performance.
• Positive class: tweets about Delicious Pie Co
• Negative class: all other tweets

The 2-by-2 Confusion Matrix

• The metrics that the confusion matrix feeds into are precision, recall and accuracy

Evaluation: Accuracy

• Accuracy as a metric is not preferred because if 100 of 1 million tweets are about Delicious Pie Co, and 999,900 are about something else, a dumb classifier will label every tweet, "not about pie."
• The "not about pie" classifier will have a 99.99% accuracy, but is useless because it doesn't return the comments the user is looking for.
• Precision and recall are more useful than accuracy.

Evaluation: Precision

• Precision measures how many of the items the system detects are acutally positive.
• Precision = true positives / (true positives + false positives)

Evaluation: Recall

• Recall is the % of items actually present in the input that were correctly identified by the system.
• Recall = true positives / (true positives + false negatives)

Why Precision and Recall

• A dumb pie-classifier just labels nothing as about pie.
• Accuracy is 99.99%
• Recall is 0
• Precision and recall, unlike accuracy, emphasize true positives.

A Combined Measure: F

• The F measure is a single number that combines precision (P) and recall (R).
• Fβ = [(β²+1)PR] / [β²P+R]
• The balanced measure is F1 where F1 = [2PR] / [P+R]

Development Test Sets and Cross-validation

• Datasets are partitioned into training sets, development test sets and test sets.
• Common metrics include precision (P), recall (R), F1 score, and Accuracy.
• Unseen test sets avoid overfitting ("tuning to the test set”) and provide more conservative estimate of performance
• Cross-validation over multiple splits, includes k-fold cross validation or multiple train/test splits

K-fold cross validation

• Data is split into 10 folds.
• Equal positive and negative inside each fold.
• Choose the fold as a temporary test set.
• Train on 9 folds, compute performance on the test fold.
• Report average performance of the 10 runs.