Text Classification

​

The Naïve Bayes algorithm

​

​

​

IP notice: most slides from: Chris Manning, plus some from William Cohen, Chien Chin Chen, Jason Eisner, David Yarowsky, Dan Jurafsky, P. Nakov, Marti Hearst, Barbara Rosario

Outline

• Introduction to Text Classification
• Also called “text categorization”
• Naïve Bayes text classification

​

Is this spam?

Author identification

• Who wrote which Federalist papers?
• 1787-8: anonymous essays try to convince New York to ratify U.S Constitution: Jay, Madison, Hamilton.
• Authorship of 12 of the letters in dispute
• 1963: solved by Mosteller and Wallace using Bayesian methods

​

James Madison

Alexander Hamilton

Generated by ChatGPT?

"AI Text Classifier” by OpenAI (https://openai.com/blog/new-ai-classifier-for-indicating-ai-written-text)

• The software rates the likelihood a chunk of text was generated by an AI model on a five-point scale that goes from "very unlikely" to "unclear" to "likely.”
• Accuracy:
• Precision: 26% correctly identified AI-written text (true positives) as “likely AI-written,”
• 9% incorrectly labelled human-written text as AI-written (false positives)

​

GPTZero by Edward Tian, Princeton University (https://gptzero.me/)

Positive or negative movie review?

• unbelievably disappointing
• Full of zany characters and richly applied satire, and some great plot twists
• this is the greatest screwball comedy ever filmed
• It was pathetic. The worst part about it was the boxing scenes.

​

​

​

​

​

What is the subject of this article?

• Antogonists and Inhibitors
• Blood Supply
• Chemistry
• Drug Therapy
• Embryology
• Epidemiology
• …

​

MeSH Subject Category Hierarchy

?

MEDLINE Article

​

More Applications

• Authorship identification
• Age/gender identification
• Language Identification
• Assigning topics such as Yahoo-categories

e.g., "finance," "sports," "news>world>asia>business"

• Genre-detection

e.g., "editorials" "movie-reviews" "news“

• Opinion/sentiment analysis on a person/product

e.g., “like”, “hate”, “neutral”

• Labels may be domain-specific

e.g., “contains adult language” : “doesn’t”

Text Classification: definition

• The classifier:

f: D → C

• Input: a document d ∈ D
• fixed set of classes C = {c₁,...,c_K}
• Output: a predicted class c ∈ C
• The learner:
• Input: a set of N hand-labeled documents T = { (d₁,c₁),....,(d_N,c_N) }
• Output: a learned classifier f: D → C

​

Slide from William Cohen

Document Classification

Slide from Chris Manning

Multimedia

GUI

Garb.Coll.

Semantics

ML

Planning

planning

temporal

reasoning

plan

language...

programming

semantics

language

proof...

learning

intelligence

algorithm

reinforcement

network...

garbage

collection

memory

optimization

region...

“planning

language

proof

intelligence”

Training

Data:

Test

Data:

Classes:

(AI)

(Programming)

(HCI)

...

...

Classification Methods: Hand-coded rules

• Some spam/email filters, etc.
• E.g., assign category if document contains a given boolean combination of words
• spam: black-list-address OR (“dollars” AND “have been selected”)
• Accuracy is often very high
• if a rule has been carefully refined over time by a subject expert
• Building and maintaining these rules is expensive

Slide from Chris Manning

Classification Methods: Supervised Machine Learning

• Input:
• a document d ∈ D
• a fixed set of classes C = {c₁, c₂,…, c_K}
• A training set of N hand-labeled documents T = { (d₁,c₁),....,(d_N,c_N) }
• Output:
• a learned classifier γ: D → C

Classification Methods: Supervised Machine Learning

• Any kind of classifier
• Naïve Bayes
• Logistic regression
• Support-vector machines
• k-Nearest Neighbors
• Deep Neural Networks

​

• …

Naïve Bayes Intuition

Naïve Bayes Intuition

• Simple (“naïve”) classification method based on Bayes rule
• Relies on very simple representation of document
• Bag of words

​

Bag of words representation

Slide from William Cohen

ARGENTINE 1986/87 GRAIN/OILSEED REGISTRATIONS

BUENOS AIRES, Feb 26

Argentine grain board figures show crop registrations of grains, oilseeds and their products to February 11, in thousands of tonnes, showing those for future shipments month, 1986/87 total and 1985/86 total to February 12, 1986, in brackets:

• Bread wheat prev 1,655.8, Feb 872.0, March 164.6, total 2,692.4 (4,161.0).
• Maize Mar 48.0, total 48.0 (nil).
• Sorghum nil (nil)
• Oilseed export registrations were:
• Sunflowerseed total 15.0 (7.9)
• Soybean May 20.0, total 20.0 (nil)

The board also detailed export registrations for subproducts, as follows....

Categories: grain, wheat

Bag of words representation

xxxxxxxxxxxxxxxxxxx GRAIN/OILSEED xxxxxxxxxxxxx

xxxxxxxxxxxxxxxxxxxxxxx

xxxxxxxxx grain xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx grains, oilseeds xxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxx tonnes, xxxxxxxxxxxxxxxxx shipments xxxxxxxxxxxx total xxxxxxxxx total xxxxxxxx xxxxxxxxxxxxxxxxxxxx:

• Xxxxx wheat xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx, total xxxxxxxxxxxxxxxx
• Maize xxxxxxxxxxxxxxxxx
• Sorghum xxxxxxxxxx
• Oilseed xxxxxxxxxxxxxxxxxxxxx
• Sunflowerseed xxxxxxxxxxxxxx
• Soybean xxxxxxxxxxxxxxxxxxxxxx

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx....

Categories: grain, wheat

Slide from William Cohen

The Bag of Words Representation

Representing text for classification

Slide from William Cohen

ARGENTINE 1986/87 GRAIN/OILSEED REGISTRATIONS

BUENOS AIRES, Feb 26

Argentine grain board figures show crop registrations of grains, oilseeds and their products to February 11, in thousands of tonnes, showing those for future shipments month, 1986/87 total and 1985/86 total to February 12, 1986, in brackets:

• Bread wheat prev 1,655.8, Feb 872.0, March 164.6, total 2,692.4 (4,161.0).
• Maize Mar 48.0, total 48.0 (nil).
• Sorghum nil (nil)
• Oilseed export registrations were:
• Sunflowerseed total 15.0 (7.9)
• Soybean May 20.0, total 20.0 (nil)

The board also detailed export registrations for subproducts, as follows....

f(

)=c

?

What is the best representation for the document d being classified?

simplest useful

Bag of words representation

xxxxxxxxxxxxxxxxxxx GRAIN/OILSEED xxxxxxxxxxxxx

xxxxxxxxxxxxxxxxxxxxxxx

xxxxxxxxx grain xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx grains, oilseeds xxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxx tonnes, xxxxxxxxxxxxxxxxx shipments xxxxxxxxxxxx total xxxxxxxxx total xxxxxxxx xxxxxxxxxxxxxxxxxxxx:

• Xxxxx wheat xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx, total xxxxxxxxxxxxxxxx
• Maize xxxxxxxxxxxxxxxxx
• Sorghum xxxxxxxxxx
• Oilseed xxxxxxxxxxxxxxxxxxxxx
• Sunflowerseed xxxxxxxxxxxxxx
• Soybean xxxxxxxxxxxxxxxxxxxxxx

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx....

Categories: grain, wheat

word

freq

Slide from William Cohen

Formalizing Naïve Bayes

Bayes’ Rule

Allows us to swap the conditioning

Sometimes easier to estimate one kind of dependence than the other

Conditional Probability

• let A and B be events
• P(B|A) = the probability of event B occurring given event A occurs
• definition:

P(B|A) = P(A ∩ B) / P(A)

Deriving Bayes’ Rule

Bayes Rule Applied to Documents and Classes

Slide from Chris Manning

The Text Classification Problem

• Using a supervised learning method, we want to learn a classifier (or classification function): γ

​

​

​

• We denote the supervised learning method by Γ:

Γ(T) = γ

• The learning method Γ takes the training set T as input and returns the learned classifier γ
• Once we have learned γ, we can apply it to the test set (or test data)

Slide from Chien Chin Chen

Multinomial Naïve Bayes Classifiers

We represent an instance D as a vector of features.

​

Task: Classify a new instance D into one of the classes c_j ∈ C

Slide from Chris Manning

The probability of a

document d being in class c.

Bayes’ Rule

We can ignore the denominator

Naïve Bayes Assumption

P(c_j)

• Can be estimated from the frequency of classes in the training examples.

P(x₁,x₂,…,x_n|c_j)

• O(|X|ⁿ•|C|) parameters
• Could only be estimated if a very, very large number of training examples was available.

Naïve Bayes Conditional Independence Assumption:

• Assume that the probability of observing the conjunction of attributes is equal to the product of the individual probabilities P(x_i|c_j).

Slide from Chris Manning

The Naïve Bayes Classifier

• Conditional Independence Assumption:
• features are independent of each other given the class:

P(X₁, …, X₅ | C) = P(X₁ | C) ∙ P(X₁ | C) ∙ … P(X₅ | C)

Slide from Chris Manning

Multinomial Naive Bayes Text Classification

Features are just the words in the document.

• Still too many possibilities
• Assume that classification is independent of the positions of the words
• Use same parameters for each position
• Result is bag of words model (over tokens not types)

Slide from Chris Manning

Learning the Model

Simplest: Maximum Likelihood Estimate

• simply use the frequencies in the data

Slide from Chris Manning

Problem with Max Likelihood

P(X₁, …, X₅ | C) = P(X₁ | C) ∙ P(X₂ | C) ∙ … P(X₅ | C)

• What if we have seen no training cases where patient had no flu and muscle aches?

​

​

• Zero probabilities cannot be conditioned away, no matter the other evidence!

Slide from Chris Manning

Smoothing to Avoid Overfitting

Bayesian Unigram Prior:

Slide from Chris Manning

# of values of X_i

overall fraction in data where X_i=x_i,k

extent of

“smoothing”

Laplace:

Naïve Bayes: Learning

• From training corpus, extract Vocabulary
• Calculate required P(c_j) and P(w_k | c_j) terms
• For each c_j in C do

docs_j ← subset of documents for which the target class is c_j

Text_j ← single document containing all docs_j

for each word w_k in Vocabulary

n_kj ← number of occurrences of w_k in Text_j

n_j ← number of occurrences in Text_j

Slide from Chris Manning

Naïve Bayes: Classifying

• positions = all word positions in current document which contain tokens found in Vocabulary
• Return c_NB, where

Slide from Chris Manning

i.e. discard unknown words

Underflow Prevention: log space

• Multiplying lots of probabilities, which are between 0 and 1 by definition, can result in floating-point underflow.
• Since log(xy) = log(x) + log(y), it is better to perform all computations by summing logs of probabilities rather than multiplying probabilities.
• Class with highest final un-normalized log probability score is still the most probable.

​

​

​

• Note that model is now just max of sum of weights…

Slide from Chris Manning

Naïve Bayes Generative Model for Text

spam

ham

Slide from Ray Mooney

Choose a class c according to P(c)

Then choose a word from that class with probability P(x|c)

Essentially model probability of each class as class-specific unigram language model

$

science

homework

Category

Naïve Bayes and Language Modeling

• Naïve Bayes classifiers can use any sort of features
• URL, email address, dictionary
• But, if:
• We use only word features
• We use all of the words in the text (not subset)
• Then
• Naïve Bayes bears similarity to language modeling

Each class = Unigram language model

• Assign to each word: P(word | c)
• Assign to each sentence: P(c | s) = P(c)∏P(w_i | c)

P(s | c) = 0.0000005

Naïve Bayes Language Model

Two classes: in language, out language

P(s | in) > P(s | out)

Naïve Bayes Classification

Win lotttery $ !

Slide from Ray Mooney

spam

ham

$

Category

NB Text Classification Example

• Training:

Vocabulary V = {Chinese, Beijing, Shanghai, Macao, Tokyo, Japan} and |V| = 6.

​

P(c) = 3/4 and P(~c) = 1/4

​

P(Chinese|c) = (5+1) / (8+6) = 6/14 = 3/7

P(Chinese|~c) = (1+1) / (3+6) = 2/9

P(Tokyo|c) = P(Japan|c) = (0+1)/(8+6) =1/14

P(Chinese|~c) = (1+1)/(3+6) = 2/9

P(Tokyo|~c) = p(Japan|~c) = (1+1)/(3+6) = 2/9

• Testing:

P(c|d) = 3/4 * (3/7)³ * 1/14 * 1/14

≈ 0.0003

​

P(~c|d) = 1/4 * (2/9)³ * 2/9 * 2/9

≈ 0.0001

Slide from Chien Chin Chen

Naïve Bayes Text Classification

Naïve Bayes algorithm – training phase.

Slide from Chien Chin Chen

TrainMultinomialNB(C, D)

V = ExtractVocabulary(D)

N = CountDocs(D)

​

for each c in C

N_c = CountDocsInClass(D, c)

prior[c] = N_c / Count(C)

text_c = TextOfAllDocsInClass(D, c)

for each t in V

F_tc = CountOccurrencesOfTerm(t, text_c)

for each t in V

condprob[t][c] = (F_tc+1) / ∑(F_t’c+1)

​

return V, prior, condprob

Naïve Bayes Text Classification

Naïve Bayes algorithm – prediction phase.

​

Slide from Chien Chin Chen

ApplyMultinomialNB(C, V, prior, condProb, d)

W = ExtractTokensFromDoc(V, d)

for each c in C

score[c] = log prior[c]

for each t in W

score[c] += log condprob[t][c]

​

return argmax_c score[c]

Evaluating Categorization

• Evaluation must be done on test data that are independent of the training data
• usually a disjoint set of instances
• Classification accuracy: c/n where n is the total number of test instances and c is the number of test instances correctly classified by the system.
• Adequate if one class per document
• Results can vary based on sampling error due to different training and test sets.
• Average results over multiple training and test sets (splits of the overall data) for the best results.

Slide from Chris Manning

Measuring Performance

Trade off precision vs. recall by setting threshold

Measure the curve on annotated dev data (or test data)

Choose a threshold where user is comfortable

Slide from Jason Eisner

Measuring Performance

Slide from Jason Eisner

low threshold:

keep all the good stuff,�but a lot of the bad too

high threshold:

all we keep is good,

but we don’t keep much

The 2-by-2 contingency table

Precision and Recall

• Precision: % of selected items that are correct
• Recall: % of correct items that are selected

A Combined measure: F

• The F measure assesses the P/R tradeoff, through the weighted harmonic mean:

Multiclass Classification

• Dealing with > 2 classes
• For each class c ∈ C
• Build a binary classifier Y_c to distinguish c from ~c
• Given a test document d
• Evaluate membership in each class using Y_c
• Assign d to each class c for which Y_c returns true

Micro- vs. Macro-Averaging

• If we have more than one class, how do we combine multiple performance measures into one quantity
• Macroaveraging: compute performance for each class, then average
• Microaveraging: collect decision for all classes, compute contingency table, evaluate

Micro- vs. Macro-Averaging: Example

54

Class 1

Class 2

Micro Ave. Table

• Macroaveraged precision: (0.5 + 0.9)/2 = 0.7
• Microaveraged precision: 100/120 = 0.83
• Microaveraged score is dominated by score on common classes

​

More Complicated Cases of Measuring Performance

• For multiclass classifiers:
• Average accuracy (or precision or recall) of 2-way distinctions: Sports or not, News or not, etc.
• Better, estimate the cost of different kinds of errors
• e.g., how bad is each of the following?
• putting Sports articles in the News section
• putting Fashion articles in the News section
• putting News articles in the Fashion section
• Now tune system to minimize total cost
• For ranking systems:
• Correlate with human rankings?
• Get active feedback from user?
• Measure user’s wasted time by tracking clicks?

Slide from Jason Eisner

Which articles are most Sports-like?

Which articles / webpages most relevant?

Evaluation Benchmark

• Reuters-21578 Data Set
• Most (over)used data set, 21,578 docs (each 90 types, 200 tokens)
• 9603 training, 3299 test articles (ModApte/Lewis split)
• 118 categories
• An article can be in more than one category
• Learn 118 binary category distinctions
• Average document (with at least one category) has 1.24 classes
• Only about 10 out of 118 categories are large

Evaluation: Classic Reuters-21578 Data Set

• Most (over)used data set, 21,578 docs (each 90 types, 200 toknens)
• 9603 training, 3299 test articles (ModApte/Lewis split)
• 118 categories
• An article can be in more than one category
• Learn 118 binary category distinctions
• Average document (with at least one category) has 1.24 classes
• Only about 10 out of 118 categories are large

​

​

​

​

57

Common categories

(#train, #test)

• Earn (2877, 1087)
• Acquisitions (1650, 179)
• Money-fx (538, 179)
• Grain (433, 149)
• Crude (389, 189)

• Trade (369,119)
• Interest (347, 131)
• Ship (197, 89)
• Wheat (212, 71)
• Corn (182, 56)

Reuters Text Categorization data set

58

<REUTERS TOPICS="YES" LEWISSPLIT="TRAIN" CGISPLIT="TRAINING-SET" OLDID="12981" NEWID="798">

<DATE> 2-MAR-1987 16:51:43.42</DATE>

<TOPICS><D>livestock</D><D>hog</D></TOPICS>

<TITLE>AMERICAN PORK CONGRESS KICKS OFF TOMORROW</TITLE>

<DATELINE> CHICAGO, March 2 - </DATELINE><BODY>The American Pork Congress kicks off tomorrow, March 3, in Indianapolis with 160 of the nations pork producers from 44 member states determining industry positions on a number of issues, according to the National Pork Producers Council, NPPC.

Delegates to the three day Congress will be considering 26 resolutions concerning various issues, including the future direction of farm policy and the tax law as it applies to the agriculture sector. The delegates will also debate whether to endorse concepts of a national PRV (pseudorabies virus) control and eradication program, the NPPC said.

A large trade show, in conjunction with the congress, will feature the latest in technology in all areas of the industry, the NPPC added. Reuter

&#3;</BODY></TEXT></REUTERS>

Confusion matrix c

• For each pair of classes <c₁,c₂> how many documents from c₁ were incorrectly assigned to c₂?
• c_3,2: 90 wheat documents incorrectly assigned to poultry

​

Development Test Sets and Cross-validation

• Metric: P/R/F1 or Accuracy
• Unseen test set
• avoid overfitting (‘tuning to the test set’)
• more conservative estimate of performance
• Cross-validation over multiple splits
• Handle sampling errors from different datasets
• Pool results over each split
• Compute pooled dev set performance

Training set

Development Test Set

Test Set

Test Set

Training size

The more the better! (usually)

Results for text classification^*

*From: Improving the Performance of Naive Bayes for Text Classification, Shen and Yang,

Test error vs training size on two classes

Slide from Nakov/Hearst/Rosario

Violation of NB Assumptions

• Conditional independence
• “Positional independence”
• Examples?

Slide from Chris Manning

Naïve Bayes is Not So Naïve

• Naïve Bayes: first and second place in KDD-CUP 97 competition, among 16 (then) state of the art algorithms

Goal: Financial services industry direct mail response prediction model: Predict if the recipient of mail will actually respond to the advertisement – 750,000 records.

• Robust to Irrelevant Features

Irrelevant Features cancel each other without affecting results

Instead Decision Trees can heavily suffer from this.

• Very good in domains with many equally important features

Decision Trees suffer from fragmentation in such cases – especially if little data

• A good dependable baseline for text classification (but not the best)!

Slide from Chris Manning

Naïve Bayes is Not So Naïve

• Optimal if the Independence Assumptions hold:

If assumed independence is correct, then it is the Bayes Optimal Classifier for problem

• Very Fast:

Learning with one pass of counting over the data; testing linear in the number of attributes, and document collection size

• Low Storage requirements
• Online Learning Algorithm

Can be trained incrementally, on new examples

SPAM Filtering: SpamAssassin

• Naïve Bayes widely used in spam filtering
• Paul Graham’s A Plan for Spam
• A mutant with more mutant offspring...
• Naive Bayes-like classifier with weird parameter estimation
• But also many other things: black hole lists, etc.
• Many email topic filters also use NB classifiers

​

• SPAM incidence is over 75% of all mail traffic:
• University of Pisa receives a typical daily number of:
• 400,000 unsolicited mail
• 130,000 proper mail

Slide from Chris Manning

SpamAssassin Tests

• Mentions Generic Viagra
• Online Pharmacy
• No prescription needed
• Mentions millions of (dollar) ((dollar) NN,NNN,NNN.NN)
• Talks about Oprah with an exclamation!
• Phrase: impress ... girl
• From: starts with many numbers
• Subject contains "Your Family”
• Subject is all capitals
• HTML has a low ratio of text to image area
• One hundred percent guaranteed
• Claims you can be removed from the list
• 'Prestigious Non-Accredited Universities'
• http://spamassassin.apache.org/old/tests_3_3_x.html

Conclusions

• Classification is a general task, to which many NLP tasks can be reduced
• Naïve Bayes is a simple statistical method
• Though simple, Naïve Bayes has still useful applications, in particular since it provides online learning