MLE, MAP, AND NAIVE BAYES10-601 RECITATIONMARY MCGLOHONMLEThe usual representation we come across is a probability density function: But what if we know that , but we don’t know ?We can set up a likelihood equation: , and find the value of that maximizes it.P (X = x|θ)x1, x2, ..., xn∼ N(µ, σ2)µµP (x|µ, σ)MLE OF MUSince x’s are independent and from the same distribution,Taking the log likelihood (we get to do this since log is monotonic) and removing some constants:p(x|µ, σ2) =n!i=1p(xi|µ, σ2)L(x) =n!i=1p(xi|µ, σ2) =1√2πσ2n!i=1exp((xi− µ)22σ2)log(L(x)) = l(x) ∝n!i=1−(xi− µ)-2CALCULUS!We can take the derivative of this value and set it equal to zero, to maximize.dl(x)dx=ddx(−n!i=1x2i− xiµ + µ2) = −n!i=1xi− µ−n!i=1xi− µ = 0 → nµ =n!i=1xi→ µ ="ni=1xinABOUT THE MLEWe can’t always do this analytically, but there are all sorts of tricks. (See homework).This is the traditional statistical approach to finding parameters.(The Unbiased M.L.E.)ABOUT THE MLEWe can’t always do this analytically, but there are all sorts of tricks. (See homework).This is the traditional statistical approach to finding parameters.(The Unbiased M.L.E.)MAPWhat if you have some ideas about your parameter?In the Bayesian school of thought (or “cult”, depending on who you ask)...We can use Bayes’ Rule:P (θ|x) =P (x|θ)P (θ)P (x)=P (x|θ)P (θ)!ΘP (θ, x)=P (x|θ)P (θ)!ΘP (x|θ)P (θ)MAP This is just maximizing the numerator, since the denominator is a normalizing constant.This assumes a prior distribution, .Old-school statisticians hate that. But ifyou get a good estimate of the prior, you’ll probably be ok.(This is why we don’t have old-school statisticians writing spam filters.)argmaxθP (θ|x) = argmaxθP (x|θ)P (θ)!ΘP (x|θ)P (θ)(Emcee M.C.)P (θ)MAP This is just maximizing the numerator, since the denominator is a normalizing constant.This assumes a prior distribution, .Old-school statisticians hate that. But ifyou get a good estimate of the prior, you’ll probably be ok.(This is why we don’t have old-school statisticians writing spam filters.)argmaxθP (θ|x) = argmaxθP (x|θ)P (θ)!ΘP (x|θ)P (θ)(Emcee M.C.)P (θ)WHAT WE CAN DO NOWMAP is the foundation for Naive Bayes classifiers.Here, we’re assuming our data are drawn from two “classes”. We have a bunch of data where we know the class, and want to be able to predict P(class|data-point).So, we use empirical probabilities In NB, we also make the assumption that the features are conditionally independent.prediction = argmaxCP (C = c|X = x) ∝ argmaxCˆP (X = x|C = c)ˆP (C = c)SPAM FILTERINGSuppose we wanted to build a spam filter. To use the “bag of words” approach, assuming that n words in an email are conditionally independent, we’d get:Whichever one’s bigger wins!P (spam|w) ∝n!i=1P (wi|spam)P (spam)P (¬spam|w) ∝n!i=1P (wi|¬spam)P (¬spam)^ ^^ ^THE IMPORTANCE OF THE SAMPLEWhat happens if you train on a set of data that’s mostly spam, and test on a set that’s mostly good emails?Also, just choosing one test set “wastes data”.What can we do?P (spam|w) ∝n!i=1P (wi|spam)P (spam)^ ^CROSS-VALIDATIONCross-validation involves training several times.LOOCV (Leave-one-out cross validation):For each data point, train classifier on -- that is, all data points besides , and classify .Error is the average accuracy.What’s wrong with this?x−ixixiK-FOLDS CVA cheaper way of doing cross-validation is to divide (“fold”) the dataset into k pieces.For each piece i,Train on all data not in set i, classify set i.Report mean error.This is a “happy medium” between straight-up training/testing and LOOCV.LESS-NAIVE BAYESHow would we modify NB to use two dependent attributes? Hint: -- you’re estimating the joint conditional distribution of the attributes. P (xi|c) = P (xi,1, xi,2, ..., xi,A|c)CONTINUOUSLY NAIVE BAYESHow could we modify NB for continuous attributes?For instance, classify whether you like basketball given your age (real), height (real), whether you like football (binary), and type of shoes you wear (categorical).TOPOLOGY OF NAIVE BAYESWhat’s the decision surface for Naive Bayes?Hint: P (c|word) = P (word|c)I(word) + P
View Full Document
Unlocking...