Naïve Bayes Classifier �

• A Naive Bayes classifier is a probabilistic machine learning model used for classification task.

​

• The root of this classifier is based on the Bayes theorem.

Applications

• Real time classification — because the Naive Bayes Classifier works is very fast as compared to other classification models.
• It is used in applications that require very fast classification responses on small to medium sized datasets.
• Spam filtering
• Text classification
• The Naive Bayes Classifier generally works very well with multi-class classification and even it uses that very naive assumption, it still outperforms other methods.

2

• Naïve Bayes algorithm is a supervised learning algorithm, which is based on Bayes theorem and used for solving classification problems.
• It is mainly used in text classification that includes a high-dimensional training dataset.
• Naïve Bayes Classifier is one of the simple and most effective Classification algorithms which helps in building the fast machine learning models that can make quick predictions.
• It is a probabilistic classifier, which means it predicts on the basis of the probability of an object.
• Some popular examples of Naïve Bayes Algorithm are spam filtration, Sentimental analysis, and classifying articles.

3

Outline

• Background
• Probability Basics
• Probabilistic Classification
• Naïve Bayes
• Principle and Algorithms
• Example: Play Tennis
• Zero Conditional Probability
• Summary

​

​

4

Background

• There are three methods to establish a classifier
• Model a classification rule directly

Examples: k-NN, decision trees, perceptron, SVM

b) Model the probability of class memberships given input data

Example: perceptron with the cross-entropy cost

c) Make a probabilistic model of data within each class

Examples: naive Bayes, model based classifiers

• a) and b) are examples of discriminative classification
• c) is an example of generative classification
• b) and c) are both examples of probabilistic classification

5

Probability Basics

6

​

• Prior, conditional and joint probability for random variables
• Prior probability:
• Conditional probability:
• Joint probability:
• Relationship:
• Independence:

​

• Bayesian Rule

Probability Basics

7

​

• Quiz: We have two six-sided dice. When they are tolled, it could end up with the following occurance: (A) dice 1 lands on side “3”, (B) dice 2 lands on side “1”, and (C) Two dice sum to eight. Answer the following questions:

Probabilistic Classification

8

​

• Establishing a probabilistic model for classification
• Discriminative model

​

• To train a discriminative classifier regardless its probabilistic or non-probabilistic nature, all training examples of different classes must be jointly used to build up a single discriminative classifier.
• Output L probabilities for L class labels in a probabilistic classifier while a single label is achieved by a non-probabilistic classifier .

​

Probabilistic Classification…

9

​

• Establishing a probabilistic model for classification (cont.)
• Generative model (must be probabilistic)

• L probabilistic models have to be trained independently
• Each is trained on only the examples of the same label
• Output L probabilities for a given input with L models
• “Generative” means that such a model produces data subject to the distribution via sampling.

Probabilistic Classification…

10

​

• Maximum A Posterior (MAP) classification rule
• For an input x, find the largest one from L probabilities output by a discriminative probabilistic classifier
• Assign x to label c* if is the largest.
• Generative classification with the MAP rule
• Apply Bayesian rule to convert them into posterior probabilities

​

​

​

​

• Then apply the MAP rule to assign a label

Naïve Bayes

11

​

• Bayes classification
• Naïve Bayes classification
• Assume all input features are class conditionally independent!

​

​

​

Example 1

12

Consider the data given in table and classify a sample x={M, 1.95m)

Example 1

13

Consider the data given in table and classify a sample x={M, 1.95m)

Example 1…

14

Example 1…

15

Example 1…

16

Using MAP

Example 2

17

x’=(Outlook=Sunny, Temperature=Cool, Humidity=High, Wind=Strong)

Example 2…

18

​

• Learning Phase

P(Play=Yes) = 9/14

P(Play=No) = 5/14

x’=(Outlook=Sunny, Temperature=Cool, Humidity=High, Wind=Strong)

Example 2…

19

​

• Test Phase
• Given a new instance, predict its label

x’=(Outlook=Sunny, Temperature=Cool, Humidity=High, Wind=Strong)

• Look up tables achieved in the learning phrase

​

​

​

​

​

• Decision making with the MAP rule

P(Outlook=Sunny|Play=No) = 3/5

P(Temperature=Cool|Play==No) = 1/5

P(Huminity=High|Play=No) = 4/5

P(Wind=Strong|Play=No) = 3/5

P(Play=No) = 5/14

P(Outlook=Sunny|Play=Yes) = 2/9

P(Temperature=Cool|Play=Yes) = 3/9

P(Huminity=High|Play=Yes) = 3/9

P(Wind=Strong|Play=Yes) = 3/9

P(Play=Yes) = 9/14

P(Yes|x’) ≈ [P(Sunny|Yes)P(Cool|Yes)P(High|Yes)P(Strong|Yes)]P(Play=Yes) = 0.0053

P(No|x’) ≈ [P(Sunny|No) P(Cool|No)P(High|No)P(Strong|No)]P(Play=No) = 0.0206

​

Given the fact P(Yes|x’) < P(No|x’), we label x’ to be “No”.

​

�Zero Conditional Probability…

20

​

• If no example contains the feature value
• In this circumstance, we face a zero conditional probability problem during test

​

• For a remedy, class conditional probabilities re-estimated with

​

(m-estimate)

�Zero conditional probability…

21

​

• Example: P(outlook=overcast|no)=0 in the play-tennis dataset
• Adding m “virtual” examples (m: up to 1% of #training example)
• In this dataset, # of training examples for the “no” class is 5.
• We can only add m=1 “virtual” example in our m-esitmate remedy.
• The “outlook” feature can takes only 3 values. So p=1/3.
• Re-estimate P(outlook|no) with the m-estimate

Summary

• Naïve Bayes: the conditional independence assumption
• Training and test are very efficient
• Two different data types lead to two different learning algorithms
• Working well sometimes for data violating the assumption!
• A popular generative model
• Performance competitive to most of state-of-the-art classifiers even in presence of violating independence assumption
• Many successful applications, e.g., spam mail filtering
• A good candidate of a base learner in ensemble learning
• Apart from classification, naïve Bayes can do more…

22