CS 188: Artificial Intelligence�

Machine Learning

Instructor: Nicholas Tomlin --- University of California, Berkeley

[These slides were created by Dan Klein and Pieter Abbeel for CS188 Intro to AI at UC Berkeley. All CS188 materials are available at http://ai.berkeley.edu.]

Machine Learning

• Up until now: how use a model to make optimal decisions

​

• Machine learning: how to acquire a model from data / experience
• Learning parameters (e.g. probabilities)
• Learning structure (e.g. BN graphs)
• Learning hidden concepts (e.g. clustering, neural nets)

​

• Today: model-based classification with Naive Bayes

Classification

Example: Spam Filter

• Input: an email
• Output: spam/ham

​

• Setup:
• Get a large collection of example emails, each labeled “spam” or “ham”
• Note: someone has to hand label all this data!
• Want to learn to predict labels of new, future emails

​

• Features: The attributes used to make the ham / spam decision
• Words: FREE!
• Text Patterns: $dd, CAPS
• Non-text: SenderInContacts, WidelyBroadcast
• …

​

Dear Sir.

​

First, I must solicit your confidence in this transaction, this is by virture of its nature as being utterly confidencial and top secret. …

TO BE REMOVED FROM FUTURE MAILINGS, SIMPLY REPLY TO THIS MESSAGE AND PUT "REMOVE" IN THE SUBJECT.

​

99 MILLION EMAIL ADDRESSES

FOR ONLY $99

Ok, Iknow this is blatantly OT but I'm beginning to go insane. Had an old Dell Dimension XPS sitting in the corner and decided to put it to use, I know it was working pre being stuck in the corner, but when I plugged it in, hit the power nothing happened.

Example: Digit Recognition

• Input: images / pixel grids
• Output: a digit 0-9

​

• Setup:
• Get a large collection of example images, each labeled with a digit
• Note: someone has 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

​

​

0

1

2

1

??

Other Classification Tasks

• Classification: given inputs x, predict labels (classes) y

​

• Examples:
• Medical diagnosis (input: symptoms,

classes: diseases)

• Fraud detection (input: account activity,

classes: fraud / no fraud)

• Automatic essay grading (input: document,

classes: grades)

• Customer service email routing
• Review sentiment
• Language ID
• … many more

​

• Classification is an important commercial technology!

​

​

Model-Based Classification

Model-Based Classification

• Model-based approach
• Build a model (e.g. Bayes’ net) 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 its parameters?

​

​

Naïve Bayes for Digits

• Naïve Bayes: Assume all features are independent effects of the label

​

• Simple digit recognition version:
• One feature (variable) F_ij for each grid position <i,j>
• Feature values are on / off, based on whether intensity

is more or less than 0.5 in underlying image

• Each input maps to a feature vector, e.g.

​

​

• Here: lots of features, each is binary valued

​

• Naïve Bayes model:

​

• What do we need to learn?

Y

F₁

F_n

F₂

General Naïve Bayes

• A general Naive Bayes model:

​

​

​

​

​

​

​

​

​

• We only have to specify how each feature depends on the class
• Total number of parameters is linear in n
• Model is very simplistic, but often works anyway

​

Y

F₁

F_n

F₂

|Y| parameters

n x |F| x |Y| parameters

|Y| x |F|ⁿ values

Inference for Naïve Bayes

• Goal: compute posterior distribution over label variable Y
• Step 1: get joint probability of label and evidence for each label

​

​

​

​

​

​

​

​

• Step 2: sum to get probability of evidence

​

• Step 3: normalize by dividing Step 1 by Step 2

​

+

General Naïve Bayes

• What do we need in order to use Naïve Bayes?

​

• Inference method (we just saw this part)
• Start with a bunch of probabilities: P(Y) and the P(F_i|Y) tables
• Use standard inference to compute P(Y|F₁…F_n)
• Nothing new here

​

• Estimates of local conditional probability tables
• P(Y), the prior over labels
• P(F_i|Y) for each feature (evidence variable)
• These probabilities are collectively called the parameters of the model and denoted by θ
• Up until now, we assumed these appeared by magic, but…
• …they typically come from training data counts: we’ll look at this soon

Example: Conditional Probabilities

A Spam Filter

• Naïve Bayes spam filter

​

• Data:
• Collection of emails, labeled spam or ham
• Note: someone has to hand label all this data!
• Split into training, held-out, test sets

​

• Classifiers
• Learn on the training set
• (Tune it on a held-out set)
• Test it on new emails

​

Dear Sir.

​

First, I must solicit your confidence in this transaction, this is by virture of its nature as being utterly confidencial and top secret. …

TO BE REMOVED FROM FUTURE MAILINGS, SIMPLY REPLY TO THIS MESSAGE AND PUT "REMOVE" IN THE SUBJECT.

​

99 MILLION EMAIL ADDRESSES

FOR ONLY $99

Ok, Iknow this is blatantly OT but I'm beginning to go insane. Had an old Dell Dimension XPS sitting in the corner and decided to put it to use, I know it was working pre being stuck in the corner, but when I plugged it in, hit the power nothing happened.

Naïve Bayes for Text

• Bag-of-words Naïve Bayes:
• 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 conditionally independent given label
• New: each W_i is identically distributed

​

• Generative model:

​

• “Tied” distributions and bag-of-words
• Usually, each variable gets its own conditional probability distribution P(F|Y)
• In a bag-of-words model
• Each position is identically distributed
• All positions share the same conditional probs P(W|Y)
• Why make this assumption?
• Called “bag-of-words” because model is insensitive to word order or reordering

Word at position i, not i^th word in the dictionary!

Example: Spam Filtering

• Model:

​

• What are the parameters?

​

​

​

​

​

​

​

​

• Where do these tables come from?

​

the : 0.0156

to : 0.0153

and : 0.0115

of : 0.0095

you : 0.0093

a : 0.0086

with: 0.0080

from: 0.0075

...

the : 0.0210

to : 0.0133

of : 0.0119

2002: 0.0110

with: 0.0108

from: 0.0107

and : 0.0105

a : 0.0100

...

ham : 0.66

spam: 0.33

Spam Example

P(spam | w) = 98.9

Training and Testing

Empirical Risk Minimization

• Empirical risk minimization
• Basic principle of machine learning
• We want the model (classifier, etc) that does best on the true test distribution
• Don’t know the true distribution so pick the best model on our actual training set
• Finding “the best” model on the training set is phrased as an optimization problem

​

• Main worry: overfitting to the training set
• Better with more training data (less sampling variance, training more like test)
• Better if we limit the complexity of our hypotheses (regularization and/or small hypothesis spaces)

​

Important Concepts

• Data: labeled instances (e.g. emails marked spam/ham)
• Training set
• Held out set
• Test set

​

• Features: attribute-value pairs which characterize each x

​

• Experimentation cycle
• Learn parameters (e.g. model probabilities) on training set
• (Tune hyperparameters on held-out set)
• Compute accuracy of test set
• Very important: never “peek” at the test set!

​

• Evaluation (many metrics possible, e.g. accuracy)
• Accuracy: fraction of instances predicted correctly

​

• Overfitting and generalization
• Want a classifier which does well on test data
• Overfitting: fitting the training data very closely, but not generalizing well
• We’ll investigate overfitting and generalization formally in a few lectures

Training

Data

Held-Out

Data

Test

Data

Generalization and Overfitting

Overfitting

0

2

4

6

8

10

12

14

16

18

20

-15

-10

-5

0

5

10

15

20

25

30

Degree 15 polynomial

Example: Overfitting

2 wins!!

Example: Overfitting

• Posteriors determined by relative probabilities (odds ratios):

​

south-west : inf

nation : inf

morally : inf

nicely : inf

extent : inf

seriously : inf

...

What went wrong here?

screens : inf

minute : inf

guaranteed : inf

$205.00 : inf

delivery : inf

signature : inf

...

Generalization and Overfitting

• Relative frequency parameters will overfit the training data!
• Just because we never saw a 3 with pixel (15,15) on during training doesn’t mean we won’t see it at test time
• Unlikely that every occurrence of “minute” is 100% spam
• Unlikely that every occurrence of “seriously” is 100% ham
• What about all the words that don’t occur in the training set at all?
• In general, we can’t go around giving unseen events zero probability

​

• As an extreme case, imagine using the entire email as the only feature (e.g. document ID)
• Would get the training data perfect (if deterministic labeling)
• Wouldn’t generalize at all
• Just making the bag-of-words assumption gives us some generalization, but isn’t enough

​

• To generalize better: we need to smooth or regularize the estimates

Parameter Estimation

Parameter Estimation

• Estimating the distribution of a random variable

​

• Elicitation: ask a human (why is this hard?)

​

• Empirically: use training data (learning!)
• E.g.: for each outcome x, look at the empirical rate of that value:

​

​

​

​

• This is the estimate that maximizes the likelihood of the data

​

​

​

r

r

b

r

b

b

r

b

b

r

b

b

r

b

b

r

b

b

Smoothing

Maximum Likelihood?

• Relative frequencies are the maximum likelihood estimates

​

​

​

​

​

• Another option is to consider the most likely parameter value given the data

????

Unseen Events

Laplace Smoothing

• Laplace’s estimate:
• Pretend you saw every outcome once more than you actually did

​

​

​

​

​

​

​

• Can derive this estimate with Dirichlet priors (see cs281a)

​

​

Laplace Smoothing

• Laplace’s estimate (extended):
• Pretend you saw every outcome k extra times

​

​

​

​

• What’s Laplace with k = 0?
• k is the strength of the prior

​

• Laplace for conditionals:
• Smooth each condition independently:

​

​

​

Estimation: Linear Interpolation*

• In practice, Laplace often performs poorly for P(X|Y):
• When |X| is very large
• When |Y| is very large

​

• Another option: linear interpolation
• Also get the empirical P(X) from the data
• Make sure the estimate of P(X|Y) isn’t too different from the empirical P(X)

​

​

​

• What if α is 0? 1?

​

• For even better ways to estimate parameters, as well as details of the math, see cs281a, cs288

Real NB: Smoothing

• For real classification problems, smoothing is critical
• New odds ratios:

helvetica : 11.4

seems : 10.8

group : 10.2

ago : 8.4

areas : 8.3

...

verdana : 28.8

Credit : 28.4

ORDER : 27.2

<FONT> : 26.9

money : 26.5

...

Do these make more sense?

Tuning

Tuning on Held-Out Data

• Now we’ve got two kinds of unknowns
• Parameters: the probabilities P(X|Y), P(Y)
• Hyperparameters: e.g. the amount / type of smoothing to do, k, α

​

• What should we learn where?
• Learn parameters from training data
• Tune hyperparameters on different data
• Why?
• For each value of the hyperparameters, train and test on the held-out data
• Choose the best value and do a final test on the test data

Features

Errors, and What to Do

• Examples of errors

​

​

​

​

​

​

​

Dear GlobalSCAPE Customer,

GlobalSCAPE has partnered with ScanSoft to offer you the latest version of OmniPage Pro, for just $99.99* - the regular list price is $499! The most common question we've received about this offer is - Is this genuine? We would like to assure you that this offer is authorized by ScanSoft, is genuine and valid. You can get the . . .

. . . To receive your $30 Amazon.com promotional certificate, click through to

http://www.amazon.com/apparel

and see the prominent link for the $30 offer. All details are there. We hope you enjoyed receiving this message. However, if you'd rather not receive future e-mails announcing new store launches, please click . . .

What to Do About Errors?

• Need more features– words aren’t enough!
• Have you emailed the sender before?
• Have 1K other people just gotten the same email?
• Is the sending information consistent?
• Is the email in ALL CAPS?
• Do inline URLs point where they say they point?
• Does the email address you by (your) name?

​

• Can add these information sources as new variables in the NB model

​

• Later this week we’ll talk about classifiers which let you easily add arbitrary features more easily, and, later, how to induce new features

​

Baselines

• First step: get a baseline
• Baselines are very simple “straw man” procedures
• Help determine how hard the task is
• Help know what a “good” accuracy is

​

• Weak baseline: most frequent label classifier
• Gives all test instances whatever label was most common in the training set
• E.g. for spam filtering, might label everything as ham
• Accuracy might be very high if the problem is skewed
• E.g. calling everything “ham” gets 66%, so a classifier that gets 70% isn’t very good…

​

• For real research, usually use previous work as a (strong) baseline

​

Confidences from a Classifier

• The confidence of a probabilistic classifier:
• Posterior probability of the top label

​

​

​

• Represents how sure the classifier is of the classification
• Any probabilistic model will have confidences
• No guarantee confidence is correct

​

• Calibration
• Weak calibration: higher confidences mean higher accuracy
• Strong calibration: confidence predicts accuracy rate
• What’s the value of calibration?

Summary

• Bayes rule lets us do diagnostic queries with causal probabilities

​

• The naïve Bayes assumption takes all features to be independent given the class label

​

• We can build classifiers out of a naïve Bayes model using training data

​

• Smoothing estimates is important in real systems

​

• Classifier confidences are useful, when you can get them

Linear Classifiers

Feature Vectors

Hello,

​

Do you want free printr cartriges? Why pay more when you can get them ABSOLUTELY FREE! Just

# free : 2

YOUR_NAME : 0

MISSPELLED : 2

FROM_FRIEND : 0

...

SPAM

or

+

PIXEL-7,12 : 1

PIXEL-7,13 : 0

...

NUM_LOOPS : 1

...

“2”

Some (Simplified) Biology

• Very loose inspiration: human neurons

Linear Classifiers

• Inputs are feature values
• Each feature has a weight
• Sum is the activation

​

​

​

​

• If the activation is:
• Positive, output +1
• Negative, output -1

Σ

f₁

f₂

f₃

w₁

w₂

w₃

>0?

Weights

• Binary case: compare features to a weight vector
• Learning: figure out the weight vector from examples

# free : 2

YOUR_NAME : 0

MISSPELLED : 2

FROM_FRIEND : 0

...

# free : 4

YOUR_NAME :-1

MISSPELLED : 1

FROM_FRIEND :-3

...

# free : 0

YOUR_NAME : 1

MISSPELLED : 1

FROM_FRIEND : 1

...

Dot product positive means the positive class

Decision Rules

Binary Decision Rule

• In the space of feature vectors
• Examples are points
• Any weight vector is a hyperplane
• One side corresponds to Y=+1
• Other corresponds to Y=-1

BIAS : -3

free : 4

money : 2

...

0

1

0

1

2

free

money

+1 = SPAM

-1 = HAM

Weight Updates

Learning: Binary Perceptron

• Start with weights = 0
• For each training instance:
• Classify with current weights

​

​

​

• If correct (i.e., y=y*), no change!

​

​

​

​

• If wrong: adjust the weight vector

Learning: Binary Perceptron

• Start with weights = 0
• For each training instance:
• Classify with current weights

​

​

​

​

• If correct (i.e., y=y*), no change!
• If wrong: adjust the weight vector by adding or subtracting the feature vector. Subtract if y* is -1.

​

Examples: Perceptron

• Separable Case

Multiclass Decision Rule

• If we have multiple classes:
• A weight vector for each class:

​

​

• Score (activation) of a class y:

​

​

​

• Prediction highest score wins

Binary = multiclass where the negative class has weight zero

Learning: Multiclass Perceptron

• Start with all weights = 0
• Pick up training examples one by one
• Predict with current weights

​

​

• If correct, no change!
• If wrong: lower score of wrong answer, raise score of right answer

​

Example: Multiclass Perceptron

BIAS : 1

win : 0

game : 0

vote : 0

the : 0

...

BIAS : 0

win : 0

game : 0

vote : 0

the : 0

...

BIAS : 0

win : 0

game : 0

vote : 0

the : 0

...

“win the vote”

“win the election”

“win the game”

Properties of Perceptrons

• Separability: true if some parameters get the training set perfectly correct

​

• Convergence: if the training is separable, perceptron will eventually converge (binary case)

​

• Mistake Bound: the maximum number of mistakes (binary case) related to the margin or degree of separability

Separable

Non-Separable

Problems with the Perceptron

• Noise: if the data isn’t separable, weights might thrash
• Averaging weight vectors over time can help (averaged perceptron)

​

​

• Mediocre generalization: finds a “barely” separating solution

​

​

• Overtraining: test / held-out accuracy usually rises, then falls
• Overtraining is a kind of overfitting

​

​

​

​

Improving the Perceptron

Non-Separable Case: Deterministic Decision

Even the best linear boundary makes at least one mistake

Non-Separable Case: Probabilistic Decision

0.5 | 0.5

0.3 | 0.7

0.1 | 0.9

0.7 | 0.3

0.9 | 0.1

How to get probabilistic decisions?

• Perceptron scoring:
• If very positive 🡪 want probability going to 1
• If very negative 🡪 want probability going to 0

​

• Sigmoid function

Best w?

• Maximum likelihood estimation:

​

​

​

​

with:

​

= Logistic Regression

Separable Case: Deterministic Decision – Many Options

Separable Case: Probabilistic Decision – Clear Preference

0.5 | 0.5

0.3 | 0.7

0.7 | 0.3

0.5 | 0.5

0.3 | 0.7

0.7 | 0.3

Multiclass Logistic Regression

• Recall Perceptron:
• A weight vector for each class:

​

• Score (activation) of a class y:

​

• Prediction highest score wins

​

​

• How to make the scores into probabilities?

​

original activations

softmax activations

Best w?

• Maximum likelihood estimation:

​

​

​

​

with:

​

= Multi-Class Logistic Regression

Maximum Likelihood Estimation

Parameter Estimation with Maximum Likelihood

Parameter Estimation with Maximum Likelihood

Parameter Estimation (General Case)

Parameter Estimation (General Case)

Example from Discussion 6B

Regularization

Recall: Overfitting

0

2

4

6

8

10

12

14

16

18

20

-15

-10

-5

0

5

10

15

20

25

30

Degree 15 polynomial

Example: Overfitting

2 wins!!

Recall: Overfitting

L1 and L2 Regularization

L1

(aka lasso regression)

L2

(aka ridge regression)