0% found this document useful (0 votes)

88 views56 pages

Text Classification Techniques Overview

The document discusses text classification techniques. It introduces text classification problems and describes common classification methods including hand-coded rules and supervised machine learning algorithms like Naive Bayes. Naive Bayes classification makes assumptions of bag-of-words representations and conditional independence between features. The document provides an example of classifying text using Naive Bayes and discusses how Naive Bayes is similar to language modeling.

Uploaded by

Aakash Verma

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

88 views56 pages

Text Classification Techniques Overview

Uploaded by

Aakash Verma

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

Text Classification

SNLP 2016

CSE, IIT Kharagpur

November 7th, 2016

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 1 / 29

Example: Positive or negative movie review?

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 2 / 29

Example: Male or Female Author?

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 3 / 29

Example: What is the subject of this article?

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 4 / 29

Taxt Classification

Assigning subject categories, topics, or genres

Spam detection
Authorship identification
Age/gender identification
Language identification
Sentiment analysis
...

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 5 / 29

Text classification: problem definition

Input
A document d
A fixed set of classes C = {c1 , c2 , . . . , cn }

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 6 / 29

Text classification: problem definition

Input
A document d
A fixed set of classes C = {c1 , c2 , . . . , cn }

Output
A predicted class c ∈ C

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 6 / 29

Classification Methods: Hand-coded rules

Rules based on combinations of words or other features

Spam

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 7 / 29

Classification Methods: Hand-coded rules

Rules based on combinations of words or other features

Spam
black-list-address OR (“dollars” AND “have been selected”)

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 7 / 29

Classification Methods: Hand-coded rules

Rules based on combinations of words or other features

Spam
black-list-address OR (“dollars” AND “have been selected”)

Pros and Cons

Accuracy can be high if rules carefully refined by expert, but building and
maintaining these rules is expensive.

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 7 / 29

Classification Methods: Supervised Machine Learning

Naïve Bayes
Logistic regression
Support-vector machines
...

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 8 / 29

Naïve Bayes Intuition

Simple classification method based on Bayes’ rule

Relies on very simple representation of document - Bag of words

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 9 / 29

Bag of words for document classification

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 10 / 29

Bayes’ rule for documents and classes

For a document d and a class c

P(d|c)P(c)
P(c|d) =
P(d)

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 11 / 29

Bayes’ rule for documents and classes

For a document d and a class c

P(d|c)P(c)
P(c|d) =
P(d)

Naïve Bayes Classifier

cMAP = arg max P(c|d)

c∈C

= arg max P(d|c)P(c)

c∈C

= arg max P(x1 , x2 , . . . , xn |c)P(c)

c∈C

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 11 / 29

Naïve Bayes classification assumptions

P(x1 , x2 , . . . , xn |c)

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 12 / 29

Naïve Bayes classification assumptions

P(x1 , x2 , . . . , xn |c)

Bag of words assumption

Assume that the position of a word in the document doesn’t matter

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 12 / 29

Naïve Bayes classification assumptions

P(x1 , x2 , . . . , xn |c)

Bag of words assumption

Assume that the position of a word in the document doesn’t matter

Conditional Independence
Assume the feature probabilities P(xi |cj ) are independent given the class cj .

P(x1 , x2 , . . . , xn |c) = P(x1 |c) · P(x2 |c) . . . P(xn |c)

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 12 / 29

Naïve Bayes classification assumptions

P(x1 , x2 , . . . , xn |c)

Bag of words assumption

Assume that the position of a word in the document doesn’t matter

Conditional Independence
Assume the feature probabilities P(xi |cj ) are independent given the class cj .

P(x1 , x2 , . . . , xn |c) = P(x1 |c) · P(x2 |c) . . . P(xn |c)

cNB = arg max P(c) ∏ P(x|c)

c∈C x∈X

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 12 / 29

Learning the model parameters

Maximum Likelihood Estimate

doc − count(C = cj )
P̂(cj ) =
Ndoc
count(wi , cj )
P̂(wi |cj ) =
∑ count(w, cj )
w∈V

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 13 / 29

Learning the model parameters

Maximum Likelihood Estimate

doc − count(C = cj )
P̂(cj ) =
Ndoc
count(wi , cj )
P̂(wi |cj ) =
∑ count(w, cj )
w∈V

Problem with MLE

Suppose in the training data, we haven’t seen the word “fantastic”, classified in
the topic ‘positive’.
P̂(fantastic|positive) = 0

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 13 / 29

Learning the model parameters

Maximum Likelihood Estimate

doc − count(C = cj )
P̂(cj ) =
Ndoc
count(wi , cj )
P̂(wi |cj ) =
∑ count(w, cj )
w∈V

Problem with MLE

Suppose in the training data, we haven’t seen the word “fantastic”, classified in
the topic ‘positive’.
P̂(fantastic|positive) = 0

cNB = arg max P̂(c) ∏ P̂(xi |c)

c x∈X

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 13 / 29

Laplace (add-1) smoothing

count(wi , c) + 1
P̂(wi |c) =
∑ (count(w, c) + 1)
w∈V

count(wi , c) + 1
=
( ∑ (count(w, c)) + |V|
w∈V

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 14 / 29

A worked example

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 15 / 29

A worked example

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 16 / 29

A worked example

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 17 / 29

A worked example

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 18 / 29

A worked example

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 19 / 29

A worked example

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 20 / 29

Naïve Bayes and Language Modeling

In general, NB classifier can use any feature

URL, email addresses, dictionaries, network features

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 21 / 29

Naïve Bayes and Language Modeling

In general, NB classifier can use any feature

URL, email addresses, dictionaries, network features

But if we use only the word features and all the words in the text
Naïve Bayes has an important similarity to language modeling.

SNLP 2016 (IIT Kharagpur) Text Classification November 7th, 2016 21 / 29

Naïve Bayes and Language Modeling

In general, NB classifier can use any feature

URL, email addresses, dictionaries, network features

But if we use only the word features and all the words in the text
Naïve Bayes has an important similarity to language modeling.
Each class can be thought of as a separate unigram language model.