1CS 188: Artificial IntelligenceFall 2009Lecture 23: Perceptrons11/17/2009Dan Klein – UC BerkeleyAnnouncements Project 4: Due Thursday! Final Contest: Qualifications are on! P5 will be due late enough to give you plenty of contest time2Recap: General Naïve Bayes A general naïve Bayes model: Y: label to be predicted F1, …, Fn: features of each instanceYF1FnF2Example Naïve Bayes Models Bag-of-words for text One feature for every word position in the document All features share the same conditional distributions Maximum likelihood estimates: word frequencies, by labelYW1WnW2 Pixels for images One feature for every pixel, indicating whether it is on (black) Each pixel has a different conditional distribution Maximum likelihood estimates: how often a pixel is on, by labelYF0,0Fn,nF0,13Naïve Bayes Training Data: labeled instances, e.g. emails marked as spam/ham by a person Divide into training, held-out, and test Features are known for every training, held-out and test instance Estimation: count feature values in the training set and normalize to get maximum likelihood estimates of probabilities Smoothing (aka regularization): adjust estimates to account for unseen dataTrainingSetHeld-OutSetTestSetRecap: 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: Can be derived by dividingH H T64Better: Linear Interpolation Linear interpolation for conditional likelihoods Idea: the conditional probability of a feature x given a label y should be close to the marginal probability of x Example: A rare word like “interpolation” should be similarly rare in both ham and spam (a priori) Procedure: Collect relative frequency estimates of both conditional and marginal, then average Effect: Features have odds ratios closer to 17Real NB: Smoothing Odds ratios without smoothing:south-west : infnation : infmorally : infnicely : infextent : inf...screens : infminute : infguaranteed : inf$205.00 : infdelivery : inf...5Real NB: Smoothinghelvetica : 11.4seems : 10.8group : 10.2ago : 8.4areas : 8.3...verdana : 28.8Credit : 28.4ORDER : 27.2<FONT> : 26.9money : 26.5...Do these make more sense? Odds ratios after smoothing:Tuning on Held-Out Data Now we’ve got two kinds of unknowns Parameters: P(Fi|Y) and P(Y) Hyperparameters, like the amount of smoothing to do: k, α Where to learn which unknowns Learn parameters from training set Can’t tune hyperparameters on training data (why?) For each possible value of the hyperparameters, train and test on the held-out data Choose the best value and do a final test on the test dataProportion of PML(x) in P(x|y)6Baselines First task when classifying: 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 spam Accuracy might be very high if the problem is skewed When conducting real research, we usually use previous work as a (strong) baselineConfidences from a Classifier The confidence of a classifier: Posterior of the most likely label Represents how sure the classifier is of the classification Any probabilistic model will have confidences No guarantee confidence is correct Calibration Strong calibration: confidence predicts accuracy rate Weak calibration: higher confidences mean higher accuracy What’s the value of calibration?7Naïve Bayes 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 Confidences are useful when the classifier is calibratedExample ErrorsDear 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 tohttp://www.amazon.com/appareland 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 . . .148What to Do About Errors Problem: there’s still spam in your inbox 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? Naïve Bayes models can incorporate a variety of features, but tend to do best in homogeneous cases (e.g. all features are word occurrences)15Features A feature is a function that signals a property of the input Naïve Bayes: features are random variables & each value has conditional probabilities given the label. Most classifiers: features are real-valued functions Common special cases: Indicator features take values 0 and 1 (or -1 and 1) Count features return non-negative integers Features are anything you can think of for which you can write code to evaluate on an input Many are cheap, but some are expensive to compute Can even be the output of another classifier or model Domain knowledge goes here!169Feature Extractors Features: anything you can compute about the input A feature extractor maps inputs to feature vectors Many classifiers take feature vectors as inputs Feature vectors usually very sparse, use sparse encodings (i.e. only represent non-zero keys)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. …W=dear : 1W=sir :
View Full Document
Unlocking...