01.Naïve Bayes Classifier

Background

There are three methods to establish a classifier

A. Model a classification rule directly
B. Model the probability of class memberships given input data
C. Make a probabilistic model of data within each class

Examples

Method	discriminative classification	generative classification	probabilistic classification	Examples
A	Yes	No	No	k-NN, decision trees, perceptron, SVM
B	Yes	No	Yes	perceptron with the cross-entropy cost
C	No	Yes	Yes	naive Bayes, model based classifiers

Probability Basics

Prior, conditional and joint probability for random variables

• Prior probability: $P(X)$
• Conditional probability: $P(X_1| X_2), P(X_2| X_1)$
• Joint probability: $\chi=(X_1,X_2), P(\chi)=P(X_1,X_2)$
• Relationship: $P(X_1, X_2)=P(X_2|X_1)P(X_1)=P(X_1|X_2)P(X_2)$
• Independence: $P(X_2|X_1)=P(X_2)P(X_1|X_2)=P(X_1)P(X_1,X_2)=P(X_1)P(X_2)$

Bayes Rule (Bayesian Inference)

1. $P(C|\chi)=\frac{P(\chi|C) P(C)}{P(\chi)}$

2. $Posterior=\frac{Likelihood \times Prior}{Evidence}$

   ---

   $Likelihood = P(\chi|C)$
   $Prior = P(C)$
   $Evidence = P(\chi)$
   $\chi$ is what the data we have now.

   Basic Idea: We got a data $\chi$, then we want to know the probability of $C$ happened before based what we got ($\chi$).

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"
C. Two dice sum to eight

We set the probabilities:
a. dice 1: $\frac{1}{6}$
b. dice 2: $\frac{1}{6}$
c. dice 3: $\frac{1}{6}$

Answer the following Questions:

1. $P(A) = \textcolor{orange}{P(a | c) = \frac{P(a,c)}{c} = \frac{1}{6}}$.
2. $P(B) = \textcolor{orange}{P(b | a) = \frac{P(a,b)}{a} = \frac{1}{6}}$.
3. $P(C) = \textcolor{orange}{\frac{1}{6}*\frac{1}{6}*5 = \frac{5}{36}}$
4. $P(A|B) = \textcolor{orange}{\frac{P(A,B)}{P(B)} = \frac{1}{6}}$
5. $P(C|A) = \textcolor{orange}{\frac{P(A,C)}{P(A)} = \frac{5}{36}}$
6. $P(A,B) = \textcolor{orange}{P(A)P(B) = \frac{1}{36}}$
7. $P(A,C) = \textcolor{orange}{P(A)P(C) = \frac{1}{6}*\frac{5}{36}}$
8. Is $P(A,C)$ equal to $P(A)*P(C)$ ?
   Answer: Yes

Probabilistic Classification

Establishing a probabilistic model for classification

• Discriminative model
  

• Generative model
  

MAP classification rule

• MAP: Maximum A Posterior
• Assign $x$ to $c^*$ if $P(C=c^*|\Chi=\chi) > P(C=c|\Chi=\chi) c \neq c^*, c=c_1, ..., c_{_L}$

Generative classification with the MAP rule

• Apply Bayes rule to convert them into posterior probabilities
  $P(C=c_i|\Chi=\chi)=\frac{P(\Chi=\chi|C=c_i)P(C=c_i)}{P(\Chi=\chi)} \propto P(\Chi=\chi| C=c_i)P(C=c_i)$ for i=1,2,..., L

Naïve Bayes

• Bayes classification
  $P(C|\Chi) \propto P(\Chi|C)P(C)=P(X_1,\cdot\cdot\cdot, X_n | C) P(C)$
  Difficulty: learning the joint probability $P(X_1,\cdot\cdot\cdot ,X_n|C)$
• Naïve Bayes classification
  Assumption that all input features are conditionally independent!

$$\begin{equation} \begin{split} P(X_1,X_2,\cdot\cdot\cdot,X_n|C) &=P(X_1|X_2,\cdot\cdot\cdot,X_n,C)P(X_2,\cdot\cdot\cdot,X_n|C)\\ &=P(X_1|C)P(X_2,\cdot\cdot\cdot,X_n|C)\\ &=P(X_1|C)P(X_2|C)\cdot\cdot\cdot P(X_n|C) \end{split} \end{equation}$$

MAP classification rule: for $x=(x_1,x_2,\cdot\cdot\cdot,x_n)$
$[P(x_1|C^*)\cdot\cdot\cdot P(x_n|c^*)]P(c^*)>[P(x_1|c)\cdot\cdot\cdot P(x_n|c)]P(c),c\neq c^*,c=c_1,\cdot\cdot\cdot,c_L$

---

• Algorithm: Discrete-Valued Features
  1. Learning Phase: Given a training set S,
     For each target value of $c_i(c_i=c_1,\cdot\cdot\cdot,c_{_L})$
     $\hat{P}(C=c_i)\gets$ estimate $P(C=c_i)$ with examples in S;
     for every feature value $\chi_{jk}$ of each feature $X_j(j=1,\cdot\cdot\cdot,n;k=1,\cdot\cdot\cdot,N_j)$
     $\hat{P}(X_j=x_{jk}|C=c_j)\gets$ estimate $P(X_j=x_{jk}|C=c_i)$ with example in $S$;
     Output: conditional probability tables; for $X_j,N_j\times L$ elements
  2. Test Phase: Given an unknown instance $\Chi^{'}=(a_{1}^{'},\cdot\cdot\cdot,a_{n}^{'})$
     Look up tables to assign the label $c^*$ to $\Chi^{'}$ if
     $[\hat{P}(a_{1}^{'}|c^*)\cdot\cdot\cdot \hat{P}(a_{n}^{'}|c^*)]\hat{P}(c^*) > [\hat{P}(a_{1}^{'}|c)\cdot\cdot\cdot\hat{P}(a_{n}^{'}|c)]\hat{P}(c), c\neq c^*, c=c_1,\cdot\cdot\cdot, c_{_L}$

Examples: Discrete-Valued Features

Original Data

Day	Outlook	Temperature	Humidity	Wind	PlayTennis
D1	Sunny	Hot	High	Weak	No
D2	Sunny	Hot	High	Strong	No
D3	Overcast	Hot	High	Weak	Yes
D4	Rain	Mild	High	Weak	Yes
D5	Rain	Cool	Normal	Weak	Yes
D6	Rain	Cool	Normal	Strong	No
D7	Overcast	Cool	Normal	Strong	Yes
D8	Sunny	Mild	High	Weak	No
D9	Sunny	Cool	Normal	Weak	Yes
D10	Rain	Mild	Normal	Weak	Yes
D11	Sunny	Mild	Normal	Strong	Yes
D12	Overcast	Mild	High	Strong	Yes
D13	Overcast	Hot	Normal	Weak	Yes
D14	Rain	Mild	High	Strong	No

Learning Phase

$P(Play = Yes) = \frac{9}{14}$ $P(Play = No) = \frac{5}{14}$

Outlook	Play = Yes	Play = No
Sunny	$\frac{2}{9}$	$\frac{3}{5}$
Overcast	$\frac{4}{9}$	$\frac{0}{5}$
Rain	$\frac{3}{9}$	$\frac{2}{5}$

Temperature	Play = Yes	Play = No
Hot	$\frac{2}{9}$	$\frac{2}{5}$
Mild	$\frac{4}{9}$	$\frac{2}{5}$
Cool	$\frac{3}{9}$	$\frac{1}{5}$

Outlook	Play = Yes	Play = No
High	$\frac{3}{9}$	$\frac{4}{5}$
Normal	$\frac{6}{9}$	$\frac{1}{5}$

Outlook	Play = Yes	Play = No
Strong	$\frac{3}{9}$	$\frac{3}{5}$
Weak	$\frac{6}{9}$	$\frac{2}{5}$

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
  $P(Outlook = Sunny | Play=Yes) = \frac{2}{9}$
  $P(Outlook=Sunny|Play=No) = \frac{3}{5}$
  $P(Temperature=Cool|Play=Yes) = \frac{3}{9}$
  $P(Temperature=Cool|Play==No) = \frac{1}{5}$
  $P(Huminity=High|Play=Yes) = \frac{3}{9}$
  $P(Huminity=High|Play=No) = \frac{4}{5}$
  $P(Wind=Strong|Play=Yes) = \frac{3}{9}$
  $P(Wind=Strong|Play=No) = \frac{3}{5}$
  $P(Play=Yes) = \frac{9}{14}$
  $P(Play=No) = \frac{5}{14}$

• Decision making with the MAP rule
  $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$

Final Result

The fact $P(Yes|x') < P(No|x')$, we label $x'$ to be “$No$”.

• Algorithm: Continuous-valued Features

  • Numberless values for a feature
  • Conditional probability often modeled with the normal
    $\hat{P}(X_j|C=c_i)=\frac{1}{\sqrt{2\pi}\sigma_{ji}}exp(-\frac{(X_j-\mu_{ji})^2}{2\sigma_{ji}^{2}})$
    $\mu_{ji}$: mean (average) of feature values $X_j$ of examples for which $C=c_j$
    $\sigma_{ji}$: standard deviation of feature values $\Chi_{j}$ of examples for which $C=c_i$
  1. Learning Phase:
     for $\Chi=(X_1,\cdot\cdot\cdot,X_n),C=c_1,\cdot\cdot\cdot,c_{_L}$
     Output: $n \times L$ normal distributions and $P(C=c_i) i=1,\cdot\cdot\cdot,L$
  2. Test Phase: Given an unknown instance $\Chi^{'}=(a_{1}^{'},\cdot\cdot\cdot,a_{n}^{'})$
     • Instead of looking-up tables, calculate conditional probabilities with all the normal distributions achieved in the learning phrase
     • Apply the MAP rule to make a decision

Example: Continuous-valued Features

Data

• Temperature is naturally of continuous value.
  Yes: 25.2, 19.3, 18.5, 21.7, 20.1, 24.3, 22.8, 23.1, 19.8
  No: 27.3, 30.1, 17.4, 29.5, 15.1

• Estimate mean and variance for each class
  $\mu = \frac{1}{N}\displaystyle\sum_{n=1}^{N}x_n$
  $\sigma^2 = \frac{1}{N}\displaystyle\sum_{n=1}^{N}(x_n-\sigma)^2$

According to the formula above, the result could be get
$\mu_{yes} = 21.64, \sigma_{yes} = 2.35$
$\mu_{No} = 23.88, \sigma_{No} = 7.09$

Learning Phase

output two Gaussian models for P(temp|C)
$\hat{P}(x | Yes) = \large{\frac{1}{2.35\sqrt{2\pi}}exp\left(-\frac{(x-21.64)^2}{2*2.35^2}\right)} = \large{\frac{1}{2.35\sqrt{2\pi}}exp\left(-\frac{(x-21.64)^2}{11.09}\right)}$

$\hat{P}(x | No) = \large{\frac{1}{7.09\sqrt{2\pi}}exp\left(-\frac{(x-23.88)^2}{2*7.09^2}\right)} = \large{\frac{1}{7.09\sqrt{2\pi}}exp\left(-\frac{(x-23.88)^2}{50.25}\right)}$

Relevant Issues

• Violation of Independence Assumption
  • For many real world tasks, $P(X_1,\cdot\cdot\cdot,X_n|C) \neq P(X_1|C)\cdot\cdot\cdot P(X_n|C)$
  • Nevertheless, naïve Bayes works surprisingly well anyway!
• Zero conditional probability Problem
  • If no example contains the attribute value
  • In this circumstance, $$ during test
  • For a remedy, conditional probabilities estimated with

    $\large{\hat{P}(X_j = a_{jk} | C=c_i) = \frac{n_c + mp}{n + m}}$
    $n_c:$ number of training examples for which $X_j = a_{jk}$ and $C=c_i$
    $n:$ number of training examples for which $C=c_i$
    $p:$ prior estimate (usually, $p = \frac{1}{t}$ for $t$ possible values os $X_j$)
    $m:$ weight to prior(number of "virtual" examples, $m\ge 1$)

Summary

• Naïve Bayes: the conditional independence assumption
  • Training is very easy and fast; just requiring considering each attribute in each class separately
  • Test is straightforward; just looking up tables or calculating conditional probabilities with estimated distributions
• 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…

Thuc

References

1. Naive Bayes Classifier
   Resource from Youtube
2. Week 2 Slides from Thuc (SP52023)