Advanced Machine Learning

10: Naive Bayes

Schedule (you are here )

Outline for the lecture

• Independence
• Parameter estimation: MLE
• MLE and KL-divergence

MAP estimation

I suspect the coin is biased

What about the knowledge we already have?

Rather than estimating a single $\theta$, obtain a distribution over possible values of $\theta$

Prior distribution

• Represents expert knowledge (philosophical approach)
• Simple posterior form (engineering approach)

Uninformative priors:

• Uniform distribution

Bayes rule (revisited)

Bayes, Thomas (1763): An essay towards solving a problem in the doctrine of chances. Philosophical Transactions of the Royal Society of London, 53:370-418

Chain Rule & Bayes rule

Bayesian Learning

MLE vs. MAP

• Maximum Likelihood estimation (MLE)
  Choose value that maximizes the probability of observed data
  $ \hat{\theta}_{MLE} = \underset{\theta}{\argmax} \prob{P}{{\cal D}|\theta} $

• Maximum a posteriori (MAP) estimation Choose value that is most probable given observed data and prior belief \begin{align} \hat{\theta}_{MAP} & = \underset{\theta}{\argmax} \prob{P}{\theta|{\cal D}}\\ & = \underset{\theta}{\argmax} \prob{P}{{\cal D}|\theta}\prob{P}{\theta} \end{align}

MAP for Binomial distribution

MAP for Binomial distribution

Beta distribution

Beta conjugate prior

$n = \alpha_H + \alpha_T$ increases $\rightarrow$

Multinomial distribution

Example: Dice roll problem (6 outcomes instead of 2)

• Likelihood is $\sim \prob{Multinomial}{\theta=\{\theta_1,\theta_2,\dots,\theta_k\}}$

  $ \prob{P}{{\cal D}|\theta} = \theta^{\alpha_1}_1\theta^{\alpha_2}_2,\dots,\theta^{\alpha_k}_k $

• If prior is the Dirichlet distribution:

  $ \prob{P}{\theta} = \frac{\prod_{i=1}^k\theta_i^{\beta_i-1}}{\prob{B}{\beta_1, \beta_2, \dots, \beta_k}} $

• the posterior is the Dirichlet distribution:

  \[ \prob{P}{\theta|{\cal D}} = \prob{Dirichlet}{\beta_1+\alpha_1, \dots, \beta_k+\alpha_k} \]

Bayes rule (practice again)

Fruits in boxes (homework)

AIDS test

Data

• Approximately 0.1% are infected
• Test detects all infections (no false negatives)
• Test reports positive for 1% of healthy

Improve the diagnosis

Use a follow-up test!

• Test 2 reports positive for 90% of infected
• Test 2 reports positive for 5% of healthy people

The Naïve Bayes Classifier

Detector for spam filtering

• date
• time
• recipient path
• IP number
• sender
• encoding
• many more features

The Naïve Bayes Assumptions

The Naïve Bayes Classifier

Given:

• Class prior $\prob{P}{Y}$
• $d$ conditionally independent features $X_1, X_2, \dots, X_d$ given the class label $Y$
• For each $X_i$, we have the conditional likelihood $\prob{P}{X_i|Y}$

The Naïve Bayes for discrete features

$f_{NB}(\vec{x}) = \underset{y}{\argmax} \prod_{i=1}^d \prob{P}{x_i|y}\prob{P}{y}$

Text Classification

• Ex1. Classify e-mails: $y \in \{ \mbox{Spam}, \mbox{NotSpam} \}$
• Ex2. Classify articles into topics
• What are the features of $\mathbf{X}$?
• Full text!

Text Classification: naïvely

• Fix max_len of an article and encode positions $\mathbf{X} = \{X_1, \dots, X_{1000}\}$
• $X_i$ is a word at $i^{th}$ position. $X_i \in \{0, \dots, D\}$, where $D$ is the size of the vocabulary (say 50,000 words).
• $\prob{P}{\mathbf{X}|Y}$ is large
• Need to estimate $K D^{1000} = K 50000^{1000}$ parameters

Naive Bayes to the rescue!

• $\prob{P}{X_i^j|y}$ probability of word $j$ at position $i$ for class $y$
• Need to estimate $DK1000 = 50000K1000$ parameters

Text Classification: bag of words

Word order and positions do not matter! Only presence

• $D=2 \implies$ $X_i$ is binary again
• $\mathbf{X}$ is vocabulary-length (say 50000) binary vector.
• Need to estimate $DK50000 = 50000K$ parameters

Works really well in practice!

Insufficient training data

• What if you never see $x_i = v$ for $y = k$?

• No word "Luxury", when $y = \mbox{NoSpam}$ in the dataset
  $\prob{P}{\mbox{Luxury} = 1, \mbox{NoSpam}} = 0 \implies \prob{P}{\mbox{Luxury} = 1| \mbox{NoSpam}} = 0$

• $\prob{P}{\mbox{Luxury}=1, X_2, \dots, X_n| Y} = $
• $\prob{P}{\mbox{Luxury}=1| Y} \prod_{i=2}^n \prob{P}{X_i|Y} =$
• $0$
• Now what?

The Naïve Bayes Properties

• The counts seemed confusing but it is just a consequence of our choice of the likelihood and prior
• Conveniently estimated everything relative to individual points
• Need to watch out for empty label-feature combinations in the data
• Need to evaluate log probabilities, as products of small numbers lead to problems

What if the features are continuous?

Character recognition: $\vec{x}_{ij}$ is intensity at pixel $(i,j)$

Example: classifying mental states

• resolution around $1^3$ mm
• 1 image per 2 seconds
• about $15,000$ voxels per "frame"
• non-invasive and safe
• measures Blood Oxygenation Level Dependent (BOLD) response

P(Brain Activity | Word Category)