Module-3

Naive Bayes, Text

Classification and Sentiment
 Syllabus
• Naive Bayes Classifiers,
• Training the Naïve Bayes Classifier,
• Worked Example,
• Optimizing for Sentiment Analysis,
• Naive Bayes for Other Text Classification Tasks,
• Naive Bayes as a Language Model.
 Introduction
• Classification lies at the heart of both human and machine intelligence.
• Deciding what letter, word, or image has been presented to our senses,
recognizing faces or voices, sorting mail, assigning grades to
homeworks; these are all examples of assigning a category to an input.
• The naïve Bayes algorithm, is used for text categorization, the task of
assigning a label or category to an entire text or document.
• Text categorization task, sentiment analysis, the extraction of
sentiment, the positive or negative orientation that a writer expresses
toward some object.
• The simplest version of sentiment analysis is a binary classification task,
and the words of the review provide excellent cues.
• A review of a movie, book, or product on the web expresses the
author’s sentiment toward the product, while an editorial or political
text expresses sentiment toward a candidate or political action.
Extracting consumer or public sentiment is thus relevant for fields from
marketing to politics.
• The following phrases extracted from positive and negative reviews of
movies and restaurants. Words like great, richly, awesome, and pathetic,
and awful and ridiculously are very informative cues:
+ ...zany characters and richly applied satire, and some great plot twists
- It was pathetic. The worst part about it was the boxing scenes...
+ ...awesome caramel sauce and sweet toasty almonds. I love this place!
- ...awful pizza and ridiculously overpriced...
• Spam detection is another important commercial application, the binary
classification task of assigning an email to one of the two classes spam
or not-spam. For example, a suspicious of an email containing phrases
like “online pharmaceutical” or “WITHOUT ANY COST” or “Dear
Winner”.
• Texts on social media, for example, can be in any number of languages.
The task of language id is thus the first step in most language processing
pipelines.
• The oldest tasks in text classification is assigning a library subject
category or topic label to a text. For a search on epidemiology or
embryology, important to have a library such as, MeSH (Medical
Subject Headings) thesaurus.
• Subject category classification is the task for which the naive Bayes
algorithm was invented by Maron, during 1961.
• Classification is essential for tasks like period disambiguation, and word
tokenization.
• Even language modeling can be viewed as classification, where
predicting the next word is classifying the context-so-far into a class for
each next word. A part-of-speech tagger classifies each occurrence of a
word in a sentence as, e.g., a noun or a verb.
• The goal of classification is to take a single observation, extract some
useful features, and thereby classify the observation into one of a set
of discrete classes.
• Handwritten rule-based classifiers can be components of state-of-the-
art systems in language processing (this may be fragile, data change
over time).
• The most common way of doing text classification in language processing is
supervised machine learning.
• In supervised learning, a data set of input observations, each associated with
some correct output. The goal of the algorithm is to learn how to map from a
new observation to a correct output.
• To take an input x and a fixed set of output classes Y = [y1, y2,……. yM] and
return a predicted class y ε Y.
• For text classification, c (class) is used instead of y as our output variable, and
d (document)used instead of x as our input variable. In the supervised there is
a training set of N documents that have each been hand-labeled with a class
[(d1, c1),……., (dN, cN)].
• Our goal is to learn a classifier that is capable of mapping from a new
document d to its correct class c ε C, where C is some set of useful document
classes.
• A probabilistic classifier, tells the probability of the observation being in the
class.
• Many kinds of machine learning algorithms are used to build classifiers.
Generative classifiers like naïve Bayes build a model of how a class could
generate some input data. Discriminative classifiers like logistic regression
instead learn what features from the input are most useful to discriminate
between the different possible classes.
 Naive Bayes Classifiers
• The naive Bayes classifier, so called because it is a Bayesian classifier
that makes a simplifying (naive) assumption about how the features
interact.
• A text document as if it were a bag of words, that is, an unordered set
of words with their position ignored, keeping only their frequency in
the document.
• Intuition of the naive Bayes classifier applied to a movie review, shown
beow;
• Naive Bayes is a probabilistic classifier, meaning that for a
document d, out of all classes c ε C the classifier returns the class
𝑐Ƹ which has the maximum posterior probability given the
document.
• The hat notation ˆ to mean “our estimate of the correct class”,
and use argmax to mean an operation that selects the argument
(class c) that maximizes a function (probability P(c|d)).

• The Bayesian inference was first applied to text classification by

Mosteller and Wallace (1964). The intuition of Bayesian
classification is to use Bayes’ rule to transform above Eq.
• Bayes’ rule gives us a way to break down any conditional
probability P(x|y) into three other probabilities.
• So, we can write 𝑐Ƹ as:

• We can drop the denominator P(d), because it doesn’t change for

each class; we are always asking about the most likely class for
the same document d, which must have the same probability
P(d).

• The Naive Bayes is called as a generative model. In this initially a

class is sampled from P(c), and then the words are generated by
sampling from P(d|c).
• The most probable class 𝑐Ƹ given some document d by choosing
the class which has the highest product of two probabilities: the
prior probability of prior the class P(c) and the likelihood of the
document P(d|c):
• Without loss of generality, a document d can represent as a set of
features f1, f2,……, fn

• From the above eq. it is too hard to compute the probability of

every possible combination of features.
• Naive Bayes classifiers therefore, make two simplifying
assumptions.
• The first is the bag-of-words assumption, where position doesn’t
matter. The features f1, f2,……, fn only encode word identity and
not position.
• The second is commonly called the naive Bayes assumption: this
is the conditional independence assumption that the
probabilities P( fi|c) are independent given the class c and hence
can be ‘naively’ multiplied as follows:

• The final equation for the class chosen by a naive Bayes classifier
is;
• To apply the naive Bayes classifier to text, each word in the
documents used as a feature. Each of the words in the document
considered as by walking an index through every word position in
the document:
• Positions <- all word positions in test document

• Naive Bayes calculations, like calculations for language modeling,

are done in log space, to avoid underflow and increase speed.

• By considering features in log space, computes the predicted

class as a linear function of input features.
• Classifiers that use a linear combination of the inputs to make a
classification decision - like naive Bayes and also logistic
regression are called linear classifiers.
 Training the Naive Bayes Classifier
• The maximum likelihood estimate.
• Firstly, for the class P(c) find the percentage of the documents in our
training set are in each class c.
• Let Nc be the number of documents in our training data with class c
and Ndoc be the total number of documents.

• To learn the probability P( fi|c), assume a feature is just the existence of

a word
• in the document’s bag of words, i.e, P(wi|c), this compute as the
fraction of times the word wi appears among all words in all documents
of topic c.
• Concatenate all documents with category c into one big “category c”
text. Then use the frequency of wi in this concatenated document to
give a maximum likelihood estimate of the probability:
• The vocabulary V consists of the union of all the word types in all
classes, not just the words in one class c.
• There is a problem, in the maximum likelihood training while estimate
the likelihood of the word “fantastic” given class positive, but suppose
there are no training documents that both contain the word “fantastic”
and are classified as positive. In such a case the probability for this
feature will be zero:

• The simplest solution is the add-one (Laplace) smoothing. While

Laplace smoothing is usually replaced by more sophisticated smoothing
algorithms in language modeling, it is commonly used in naive Bayes
text categorization:

• The unknown words in the test sequence, need to be ignored not

include any probability for them at all.
• Some systems choose to completely ignore another class of words:
stop words, very frequent words like the and a.
The naive Bayes algorithm, using add-1 smoothing.
Example: Training and testing naive Bayes with add-one smoothing. We’ll use a
sentiment analysis domain with the two classes positive (+) and negative (-), and
take the following miniature training and test documents simplified from actual
movie reviews.

The prior P(c) for the two classes is computed; P(-) = 3/5 and P(+) = 2/5.
• The word with doesn’t occur in the training set, must drop it completely. Then
computing the probabilities for the remainder of the words in the training set;
Example: Training and testing naive Bayes with add-one smoothing. We’ll use a
sentiment analysis domain with the two classes positive (+) and negative (-), and
take the following miniature training and test documents simplified from actual
movie reviews.

• For the test sentence S = “predictable with no fun”, after removing the word
‘with’, the chosen class, using naïve bayes is therefore computed as follows:

• The model thus predicts the class negative for the test sentence.
Assume the following likelihoods for each word being part of a positive or negative
movie review, and equal prior probabilities for each class.
What class will Naive bayes assign to the sentence
“I always like foreign films.”?

This is having prior probability, P(+) = P(-) = 0.5

Word Likelihood is given in the table;

Positive Class (pos)

P{pos|d) α [Link].[Link].0.08 α 0.0000058416
Negative Class (neg)
P(neg|d) α [Link].[Link].0.11 α 0.00009504
Since P(neg|d) > P(pos|d), the Naive Bayes classifier assigns the
class: Negative to the sentence “I always like foreign films”.
Given the following short movie reviews, each labeled with a genre, either comedy
or action:
1. fun, couple, love, love comedy
2. fast, furious, shoot action
3. couple, fly, fast, fun, fun comedy
4. furious, shoot, shoot, fun action
5. fly, fast, shoot, love action
and a new document D: fast, couple, shoot, fly.
Compute the most likely class for D. Assume a naive Bayes classifier and use add-1
smoothing for the likelihoods.

List of all unique words in all documents: {fun, couple, love, fast, furious,
shoot, fly}, Hence vocabulary size 𝑉=7
Class: Comedy, in a Docs: 1 and 3
Doc 1: fun(1), couple(1), love(2)
Doc 3: couple(1), fly(1), fast(1), fun(2)
Total words in comedy = 1+1+2 + 1+1+1+2 = 9
Word counts in comedy: fun=3, couple=2, love=2, fly=1, fast=1, furious=0,
shoot=0.
Given the following short movie reviews, each labeled with a genre, either comedy
or action:
1. fun, couple, love, love comedy
2. fast, furious, shoot action
3. couple, fly, fast, fun, fun comedy
4. furious, shoot, shoot, fun action
5. fly, fast, shoot, love action
and a new document D: fast, couple, shoot, fly.
Compute the most likely class for D. Assume a naive Bayes classifier and use add-1
smoothing for the likelihoods.
Class: Action, in a Docs: 2, 4, 5
Doc 2: fast(1), furious(1), shoot(1)
Doc 4: furious(1), shoot(2), fun(1)
Doc 5: fly(1), fast(1), shoot(1), love(1)
Total words in action = 3 + 4 + 4 = 11
Word counts in action: fast=2, furious=2, shoot=4, fun=1, fly=1, love=1,
couple=0.
Compute Priors:
Total docs = 5
Comedy docs = 2 → 𝑃(comedy)=2/5=0.4
Action docs = 3 → 𝑃(action)=3/5=0.6
Using Likelihood formula with smoothing:
For Comedy class;
Total words in comedy = 9
Vocabulary size 𝑉=7
Denominator: 9+7=16
| Word | Count | Smoothed Likelihood 𝑃 (𝑤∣comedy)
P( fast | 1) = (1+ 1)/16=0.125
P( couple | 2) = (2+1)/16=3/16=0.1875
P(shoot | 0 ) = (0+1)/16=1/16=0.0625
P( fly | 1)= (1+1)/16=2/16=0.125
𝑃(𝐷∣comedy)=0.125⋅0.1875⋅0.0625⋅0.125= 0.00018310547
P(comedy∣D) ∝ P(comedy)⋅ P(D∣comedy)
=0.4⋅0.00018310547
=0.0000732422
For Action class;
Total words in action = 11
Denominator: 11+7=18
| Word | Count | Smoothed Likelihood P(w∣action)
P(fast | 2) = (2+1)/18=3/18=0.1667
P(couple | 0) = (0+1)/18=1/18≈0.0556
P(shoot | 4) = (4+1)/18=5/18≈0.2778
P(fly | 1) = (1+1)/18=2/18≈0.1111
P(D∣action)=0.1667⋅0.0556⋅0.2778⋅0.1111≈0.000285
P(action∣D) ∝ 0.6⋅0.000285≈0.000171
• The Naive Bayes classifier (with add-1 smoothing) assigns the class:
Action to document D: “fast, couple, shoot, fly”
• This is because the likelihood of the words “fast”, “shoot”, and “fly” is
significantly higher in the action class.
 Optimizing for Sentiment Analysis
• Naive Bayes text classification can work well for sentiment
analysis, some small changes are generally employed that
improve performance.
• Whether a word occurs or not seems to matter more than its
frequency.
• It often improves performance to clip the word counts in each
document at 1. This variant is called binary multinomial naive
Bayes or binary naive Bayes.
• The same algorithm of naïve bayes used, except that for each
document we remove all duplicate words before concatenating
them into the single big document during training and we also
remove duplicate words from test documents.
A set of four documents (shortened and text-normalized for this example) are
remapped to binary, with the modified counts shown in the table on the right.
The example is worked without add-1 smoothing to make the differences clearer.
Note that the results counts need not be 1; the word great has a count of 2 even
for binary naïve Bayes, because it appears in multiple documents.
• For sentiment analysis it is to deal with negation.
• Consider the difference between I really like this movie (positive) and I
didn’t like this movie (negative). The negation expressed by didn’t
completely alters the inferences we draw from the predicate like.
• Negation can modify a negative word to produce a positive review
(don’t dismiss this film, doesn’t let us get bored).
• The negation can be used in sentiment analysis : during text
normalization, prepend the prefix NOT_ to every word after a token of
logical negation (n’t, not, no, never) until the next punctuation mark.
didn't like this movie , but I
becomes
didn't NOT_like NOT_this NOT_movie , but I
• Newly formed ‘words’ like NOT_like, NOT_recommend will occur more
often in negative document and act as cues for negative sentiment,
while words like NOT_bored, NOT_dismiss will acquire positive
associations.
• Syntactic parsing can be used deal more accurately with these negation
words and the predicates.
• Sometimes there is insufficient labeled training data to train accurate naive
Bayes classifiers using all words in the training set to estimate positive and
negative sentiment.
• In such cases, instead of derive the positive and negative word features from
sentiment lexicons, lists of words that are pre-annotated with positive or
negative sentiment.
• Four popular lexicons are the General General Inquirer (Stone et al., 1966),
LIWC (Pennebaker et al., 2007), the opinion lexicon Inquirer LIWC of Hu and
Liu (2004a) and the MPQA Subjectivity Lexicon (Wilson et al., 2005).
• For example, the MPQA subjectivity lexicon has 6885 words each marked for
whether it is strongly or weakly biased positive or negative. Some examples:
+ : admirable, beautiful, confident, dazzling, ecstatic, favor, glee, great
- : awful, bad, bias, catastrophe, cheat, deny, envious, foul, harsh, hate
• To use lexicons in a naive Bayes classifier is to add a feature that is counted
whenever a word from that lexicon occurs.
• If there is lots of training data, and if the test data matches the training data,
using just two features won’t work as well as using all the words.
• When training data is sparse or not representative of the test set, using dense
lexicon features instead of sparse individual-word features may generalize
better.
Naive Bayes for other text classification tasks
• Consider the task of spam detection, deciding if a particular piece of
email is an example of spam (unsolicited bulk email)—one of the first
applications of naïve Bayes to text classification (Sahami et al., 1998).
• A common solution here, rather than using all the words as individual
features, is to predefine likely sets of words or phrases as features,
combined with features that are not purely linguistic.
• For example, the open-source SpamAssassin tool predefines features
like the phrase “one hundred percent guaranteed”, or the feature
mentions “millions of dollars”, which is a regular expression that
matches suspiciously large sums of money.
• More sample SpamAssassin features:
• Email subject line is all capital letters
• Contains phrases of urgency like “urgent reply”
• Email subject line contains “online pharmaceutical”
• HTML has unbalanced “head” tags
• Claims you can be removed from the list.
• Language id—determining what language a given piece of text is
written in—the most effective naive Bayes features are not words
at all, but character n-grams, 2-grams (‘zw’) 3-grams (‘nya’, ‘ Vo’),
or 4-grams (‘ie z’, ‘thei’), or, even simpler byte n-grams, where
instead of using the multibyte Unicode character representations
called codepoints.
• Here spaces count as a byte, byte n-grams can model statistics
about the beginning or ending of words.
• A widely used naive Bayes system, [Link] (Lui and Baldwin,
2012) begins with all possible n-grams of lengths 1-4, using
feature selection to winnow down to the most informative 7000
final features.
• Language ID systems are trained on multilingual text, such as
Wikipedia (Wikipedia text in 68 different languages was used in
(Lui and Baldwin, 2011)), or newswire.
 Naive Bayes as a Language Model
• Naive Bayes classifiers can use any sort of feature: dictionaries, URLs,
email addresses, network features, phrases, and so on.
• Individual word features, and all of the words in the text (not a subset),
then the use of naive Bayes has an important similarity to language
modeling.
• A naive Bayes model can be viewed as a set of class-specific unigram
language models, in which the model for each class instantiates a
unigram language model.
• Since the likelihood features from the naive Bayes model assign a
probability to each word P(word | c), the model also assigns a
probability to each sentence:

• Thus consider a naive Bayes model with the classes positive (+) and
negative (-) and the following model parameters:
• Each of the two columns above instantiates a language model
that can assign a probability to the sentence “I love this fun film”:
P(“I love this fun film”|+) = 0.1 X0.1X0.01X0.05X0:1 = 5X10-7
P(“I love this fun film” |-) = 0.2X0.001X0.01X0.005X0.1 = 1.0X10-9
• As it happens, the positive model assigns a higher probability to
the sentence: P(s|pos) > P(s|neg).
• This is just the likelihood part of the naive Bayes model; once we
multiply in the prior a full naive Bayes model might well make a
different classification decision.