Skip to content

20 ML 1 Naive Bayes

Recap from particle filtering

In robot localization - we know the map, but not the robot's position - observation may be vectors of range and finer readings - state space and readings are typically continuous (works basically like a fine grid) - we cannot store \(B(X)\)

Example

  • particle filter localization with sonar

Naive bayes

agent testing today!

Now we are switching gears to recap the last lecture, we dont have these CPTs and we actually want to learn those tables from data then we can use those tables to compute optimal decisions

ML is really about how do we acquire a model from data instead of being handed one like before

thats kinda where we are going to be for the rest of class

right now we are going to talk about the Naive bayes net model

it works pretty well for a lot of things

one thing to know is that this class is giving a lot of foundations, even though they might not be used as much today, these are where a lot of modern day systems pull from today.

okay so, we are shifting to models

we want to models to make some sort of decisions

we want some sort of inference models

if an email is spam or not, etc.

first we need to learn a model, there are a couple things that go into the model, individual numbers, ect.

in a linear model there are parameters \(A\) and \(B\) in \(Y = AX + B\), those are what govern what the model is and how it performs

  • learning parameters (eg probabilities)
  • learning structure (eg BN graphs)
  • learning hidden concepts (eg clustering, neural nets)

Today: model-based classification with naive Bayes.

CLASSIFICATION

  • trying to determine what "group" it is in

  • spam or email?

  • What number in the picture?

EXAMPLE: Spam filter

  • input: an email

  • output: spam/ham

  • setup:

  • get a large collection of example emails, each labeled spam or ham
  • note: we need to get labels for all this data!

  • want to learn to predict labels of new, future emails

  • features:

  • words: "FREE!!!"
  • Text patterns: $dd, CAPS
  • non-text: sender-in-contacts, widely-broadcast
  • ...
  • With modern language models, hand-specifying features may not be necessary

EXAMPLE: Digit Recognition

Input: images/pixel grids output: digit 0-9

  • setup
  • get a large collection of example images, each labeled with a digit
  • note: want someone to hand-label all this data

  • want to learn to predict labels of new future digit images

  • features

  • The attributes used to make the digit decision
  • Pixels: (6, 8) = ON
  • Shape Patterns: NumComponents, aspectRatio, numLoops
  • ...
  • Features are increasingly induced rather than crafted

EXAMPLE: Cancer Risk Estimation

Input: Mammogram Output: Patient's risk of breast cancer

  • setup:
  • get a large collection of mammograms from multiple sites,
  • get labels for each image (did the patient develop cancer within 5 years)

  • application: women who are predicted high risk referred to additional screening

  • features: the attributes used to predict cancer risk

  • pixels: 1664 x 2048 image
  • Features are learned by a deep learning model

Other classification Tasks:

  • examples
  • medical diagnosis
    • input: symptoms, images, other medical data; classes: diseases
  • fraud detection
    • input: account activity
    • classes: fraud/no fraud
  • automatic essay grading
  • customer service email routing
  • review sentiment
  • language ID
  • ... many more

Let's move into the actual model we are learning:

So first, specifically, the naive Bayes model has both the output label and the features, and we want to connect them by some structure.

we are trying to create something

Model-based object classification

  • model based approach
  • build a model (like a BN?) where both the output label and input features are random variables
  • instantiate any observed features
  • query for the distribution of the label conditioned on the features
  • Challenges
  • what structure should the BN have
  • How should we learn the parameters?

NAIVE BAYES FOR DIGITS

  • Naive Bayes: assume all features are independent effects of the label
  • very strong assumption!
  • simple digit recognition version
  • one feature (variable) \(F_{ij}\) for each position
  • feature values are on/off, based on whether intensity is more or less than 0.5 in the underlying image
  • each input maps to a feature vector, e.g.
    • \(1 = \langle F_{0,0} = 0, F_{0,1} = 1, F_{0,2} = 1, \dots, F_{15,15} = 0 \rangle\)
  • here: lots of features, each is binary valued

  • naive bayes model:

  • \(P(Y, F_{0,0} \dots F_{15,15}) \propto P(Y) \cdot \prod_{i,j} P(F_{i,j} | Y)\)

  • What do we need to learn?

  • we only have to specify how each feature depends on its class

  • \(P(Y | F_1 \dots F_n) \propto P(Y) \cdot \prod_i P(F_i | Y)\)

\(|Y| \times |F|^n\) values vs \(n \times |F| \times |Y|\) values

        ( Y )
       /  |  \
      /   |   \
     v    v    v
   (F_1)(F_2)...(F_n)

now its linear?

# digit example: 16x16 binary pixels, 10 classes
n = 16 * 16
F = 2
Y = 10

# full joint table: exponential in the number of features
joint = Y * F^n =>
# naive bayes: one tiny table per feature, then add up
naive = n * F * Y =>

^ the joint is astronomically huge; naive bayes is \(O(n)\) in the number of features. that's the whole point.

INFERENCE FOR NAIVE BAYES

  • goal: compute posterior distribution over label variable \(Y\)
  • step 1: get joint probability of label and evidence for each label
  • \(P(Y, f_1, \dots f_n) = \begin{bmatrix} P(y_1, f_1, \dots f_n) \\ P(y_2, f_1, \dots f_n) \\ \vdots \end{bmatrix} = \begin{bmatrix} P(y_1) \prod_i P(f_i | y_1) \\ P(y_2) \prod_i P(f_i | y_2) \\ \vdots \end{bmatrix}\)
  • step 2: sum to get \(P(f_1 \dots f_n)\), then normalize
  • predict: \(\hat{y} = \arg\max_y P(y) \prod_i P(f_i | y)\)

General Naive Bayes

  • what do we need in order to use Naive Bayes
  • inference method (we just saw this part)
    • start with a bunch of probabilities: \(P(Y)\) and \(P(F_i|Y)\) tables
    • use standard inference to compute \(P(Y|F_1 \dots F_n)\)

Digit recognition

each digit is on a grid, if you go through the feature vector for the pixels in the grid, so it for 3 it would look like:

\(\langle 0, 0, 1, 1, 1, 0, 0, 0, \dots \rangle\)

# # # # #
. . . . #
# # # # #
. . . . #
# # # # #

(read row-by-row, # = 1, . = 0 → that's the feature vector)

if we had 1000 examples for every digit: then \(P(Y)\) can look like this

\(P(Y)\)

0 = 0.1 1 = 0.1 2 = 0.1 3 = 0.1 ... 9 = 0.1

With fewer samples, it's less likely to be uniform like this, but we know it could be these.

\(P(F_{3,1} = \text{ON} | Y)\)

1 = 0.01 2 = 0.05 3 = 0.05 4 = 0.3 ... 9 = 0.5

How many of those images at this grid point are 3, 1 on, and then calculate the probabilities over all the images.

# each parameter is just a count / total
# e.g. digit 4: 300 of the 1000 examples have pixel (3,1) on
300 / 1000 =>

Naive Bayes for Text:

  • bag of words model
  • features \(W_i\) is the word at position \(i\)
  • as before: predict label conditioned on feature variables (spam vs ham)
  • as before: assume features are conditioned independent given label
  • new: each \(W_i\) is identically distributed

Generative Models

  • \(P(Y, W_1, \dots W_n) = P(Y) \prod_i P(W_i | Y)\) <- words at position i, not ith word in the dictionary!

Tied distributions and bag-of-words

  • Usually, each variable gets its own conditional probability distribution \(P(F|Y)\).

Model: Spam filtering

Model: \(P(Y, W_1, \dots W_n) = P(Y) \prod_i P(W_i | Y)\)

  • what are the parameters?
  • \(P(Y)\):
    • spam = 0.33
    • ham = 0.66
  • \(P(W|\text{Spam})\)
    • the = 0.015
    • to = 0.015
    • and = 0.011
    • of = 0.009
    • you = 0.00

worked example — classify a 2-word email, score each class then normalize:

# priors from the notes
p_spam = 0.33
p_ham = 0.66

# P(word | spam) — example spammy-word values
p_free_spam = 0.02
p_money_spam = 0.01

# P(word | ham) — example values (the notes only list the spam side)
p_free_ham = 0.001
p_money_ham = 0.002

# unnormalized score per class: P(Y) * prod_i P(w_i | Y)
score_spam = p_spam * p_free_spam * p_money_spam
score_ham = p_ham * p_free_ham * p_money_ham

# normalize into a posterior
score_spam / (score_spam + score_ham) =>
score_ham / (score_spam + score_ham) =>