Recitation 3 Naive Bayes and Logistic Regression and a surprise Ekaterina Spriggs 10701 15781 Fall 2009 Friday September 25 2009 Recitation 3 Naive Bayes and Logistic Regression and decision trees Ekaterina Spriggs 10701 15781 Fall 2009 Friday September 25 2009 Classifiers tly c e r i d P Y X1 Xn Bay es P Y X1 Xn Discriminative P Y X P X Y P Y P X Generative P X1 Xn Y P Y Friday September 25 2009 Generative vs discriminative models Friday September 25 2009 NB decision rule f X Y Most probable value of f x y Friday September 25 2009 NB decision rule time f X Y Most probable value of f x y X1 Xn Friday September 25 2009 x11 x21 xN 1 x1n x2n y1 y2 xN yN n crossover dribble crossover dribble shoot NB decision rule time f X Y Most probable value of f x y X1 Xn Friday September 25 2009 x11 x21 xN 1 x1n y1 y2 x2n yN xN n f x11 x1n Decision rule f X Y Most probable value of f x y predict YM LE arg max P X x1 X xn Y yj predict YM AP arg max P Y yj X x1 X xn predict YN B Friday September 25 2009 yj Y yj Y arg max yj Y n i P X xi Y yj P Y yj Decision rule f X Y Most probable value of f x y predict YM LE arg max P X x1 X xn Y yj predict YM AP arg max P Y yj X x1 X xn predict YN B Friday September 25 2009 yj Y yj Y arg max yj Y n i P X xi Y yj P Y yj Decision rule f X Y Most probable value of f x y predict YM LE arg max P X x1 X xn Y yj predict YM AP arg max P Y yj X x1 X xn Bayes optimal predict YN B Friday September 25 2009 yj Y yj Y arg max yj Y n i P X xi Y yj P Y yj NB decision rule predict YN B arg max yj Y n i P X xi Y yj P Y yj P X xi Y yj you know this from class P Y yj you know this from class Matlab structures Friday September 25 2009 example for NB how to count number of data points num data points 9 number of possible values for the features x num outcomes 4 feature dimensionality x dim 3 number of possible outcomes y num outcomes 2 Y 0 0 0 1 1 1 0 0 0 X 4 3 4 3 4 3 4 3 4 1 4 3 1 2 1 2 3 1 3 1 2 4 1 4 1 3 2 fprintf Data n X Y class conditional probability table each feature y outcomes x outcomes table zeros x dim y num outcomes x num outcomes P X i k Y j what is this X Y 1 3 some code i 1 dim of X j 1 values of Y k 1 values of X table i j k sum X Y j i k more code something sum Y j something once you have your conditional probability table how do you make a decision Friday September 25 2009 NB decision rule predict YN B arg max yj Y n i P X xi Y yj P Y yj In the homework Y 0 or Y 1 Comparing n i n i Friday September 25 2009 P X xi Y 1 P Y 1 P X xi Y 0 P Y 0 NB decision rule predict YN B arg max yj Y n i P X xi Y yj P Y yj Problem 0 2 0 3 alright 0 2 0 3 0 8 0 1 0 02 0 7 trouble Hint argmax a monotonic function of the decision rule Friday September 25 2009 NB Gaussian inputs vs discrete inputs Gaussian inputs in class Discrete inputs in homework See suggested reading for Gaussian NB Friday September 25 2009 NB performance f X1 X2 Y prediction truth Classification performance I f X1 X2 Y Y not the same as error rate Friday September 25 2009 NB error rate f X1 X2 Y prediction truth f X1 X2 Y P X1 X2 Y X1 X2 Y Friday September 25 2009 I f X1 X2 Y P X1 X2 Y Logistic regression P Y 1 X w g w0 wi xi i g w0 wi xi w0 i g w0 i Friday September 25 2009 1 1 e wi xi g w0 n i 1 wi xi i n wi xi g wi xi i 0 x0 1 LR learning the weights MLE Log likelihood lnP DY DX w Concave lnP DY DX w j lnP y x w j j Gradient ascent wikipedia or class on Monday Friday September 25 2009 LR gradient ascent lnP DY DX w j lnP y x w j j i i w w lnP y x w w j For all features i t 1 wi Until Friday September 25 2009 t wi j j j xi y P Y 1 x w j j estimate doesn t change much t LR classification rule Classification rule see class notes Friday September 25 2009 Information theory Quick intro this will be covered in class Friday September 25 2009 Information theory Entropy H Y k P Y yi log2 P Y yi i 1 On average smallest number of bits needed to transmit values drawn from Y s distribution Information gain IG Y X H Y H Y X How much better can we do if we share knowledge about X Friday September 25 2009 Information theory Conditional entropy H Y X Friday September 25 2009 v j 1 P X xj k i 1 P Y yi X xj log2 P Y yi X xj Decision trees ID3 check wikipedia Friday September 25 2009 Credits Andrew Moore s lectures http www autonlab org tutorials Carlos Guestrin s lectures http select cs cmu edu class 10701 F09 schedule html Tommi Jaakola lectures Videos CMU graphics lab Friday September 25 2009 Homework questions Friday September 25 2009
View Full Document
Unlocking...