Na ve Bayes Logistic Regression See class website Mitchell s Chapter required Ng Jordan 02 optional Gradient ascent and extensions Koller Friedman Chapter 1 4 Decision Trees many possible refs e g Mitchell Chapter 3 Logistic Regression Continued Generative v Discriminative Decision Trees Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University February 1st 2006 2006 Carlos Guestrin 1 Announcements Recitations stay on Thursdays 5 6 30pm in Wean 5409 This week Na ve Bayes Logistic Regression Extension for the first homework Due Wed Feb 8th beginning of class Mitchell s chapter is most useful reading 2006 Carlos Guestrin 2 Logistic Regression Logistic function or Sigmoid Learn P Y X directly Assume a particular functional form Sigmoid applied to a linear function of the data Z 2006 Carlos Guestrin 3 Logistic Regression a Linear classifier 1 0 9 0 8 0 7 0 6 0 5 0 4 0 3 0 2 0 1 0 6 2006 Carlos Guestrin 4 2 0 2 4 6 4 Logistic regression v Na ve Bayes Consider learning f X Y where X is a vector of real valued features X1 Xn Y is boolean Could use a Gaussian Na ve Bayes classifier assume all Xi are conditionally independent given Y model P Xi Y yk as Gaussian N ik i model P Y as Bernoulli 1 What does that imply about the form of P Y X Cool 2006 Carlos Guestrin 5 Gaussian Na ve Bayes v Logistic Regression Set of Gaussian Na ve Bayes parameters Set of Logistic Regression parameters Representation equivalence But only in a special case GNB with class independent variances But what s the difference LR makes no assumptions about P X Y in learning Loss function Optimize different functions Obtain different solutions 2006 Carlos Guestrin 6 Logistic regression more generally Logistic regression in more general case where Y Y1 YR learn R 1 sets of weights for k R for k R normalization so no weights for this class Features can be discrete or continuous 2006 Carlos Guestrin 7 Logistic regression with more than 2 classes an example Y Y1 YR learn R 1 sets of weights for k R for k R normalization so no weights for this class Features can be discrete or continuous 2006 Carlos Guestrin 8 Loss functions Likelihood v Conditional Likelihood Generative Na ve Bayes Loss function Data likelihood Discriminative models cannot compute P xj w But discriminative logistic regression loss function Conditional Data Likelihood Doesn t waste effort learning P X focuses on P Y X all that matters for classification 2006 Carlos Guestrin 9 Expressing Conditional Log Likelihood 2006 Carlos Guestrin 10 Maximizing Conditional Log Likelihood Good news l w is concave function of w no locally optimal solutions Bad news no closed form solution to maximize l w Good news concave functions easy to optimize 2006 Carlos Guestrin 11 Optimizing concave function Gradient ascent Conditional likelihood for Logistic Regression is concave Find optimum with gradient ascent Gradient Learning rate 0 Update rule Gradient ascent is simplest of optimization approaches e g Conjugate gradient ascent much better see reading 2006 Carlos Guestrin 12 Maximize Conditional Log Likelihood Gradient ascent Gradient ascent algorithm iterate until change For all i repeat 2006 Carlos Guestrin 13 That s all M C LE How about MAP One common approach is to define priors on w Normal distribution zero mean identity covariance Pushes parameters towards zero Corresponds to Regularization Helps avoid very large weights and overfitting Explore this in your homework More on this later in the semester MAP estimate 2006 Carlos Guestrin 14 M C AP as Regularization Penalizes high weights also applicable in linear regression see homework 2006 Carlos Guestrin 15 Gradient of M C AP 2006 Carlos Guestrin 16 MLE vs MAP Maximum conditional likelihood estimate Maximum conditional a posteriori estimate 2006 Carlos Guestrin 17 Na ve Bayes vs Logistic Regression Consider Y boolean Xi continuous X X1 Xn Number of parameters NB 4n 1 LR n 1 Estimation method NB parameter estimates are uncoupled LR parameter estimates are coupled 2006 Carlos Guestrin 18 G Na ve Bayes vs Logistic Regression 1 Ng Jordan 2002 Generative and Discriminative classifiers Asymptotic comparison training examples infinity when model correct GNB LR produce identical classifiers when model incorrect LR is less biased does not assume conditional independence therefore LR expected to outperform GNB 2006 Carlos Guestrin 19 G Na ve Bayes vs Logistic Regression 2 Ng Jordan 2002 Generative and Discriminative classifiers Non asymptotic analysis convergence rate of parameter estimates n of attributes in X Size of training data to get close to infinite data solution GNB needs O log n samples LR needs O n samples GNB converges more quickly to its perhaps less helpful asymptotic estimates 2006 Carlos Guestrin 20 Na ve bayes Logistic Regression Some experiments from UCI data sets 2006 Carlos Guestrin 21 What you should know about Logistic Regression LR Gaussian Na ve Bayes with class independent variances representationally equivalent to LR Solution differs because of objective loss function In general NB and LR make different assumptions NB Features independent given class assumption on P X Y LR Functional form of P Y X no assumption on P X Y LR is a linear classifier decision rule is a hyperplane LR optimized by conditional likelihood no closed form solution concave global optimum with gradient ascent Maximum conditional a posteriori corresponds to regularization Convergence rates GNB usually needs more data LR usually gets to better solutions in the limit 2006 Carlos Guestrin 22 Linear separability A dataset is linearly separable iff a separating hyperplane w such that w0 i wi xi 0 if x x1 xn is a positive example w0 i wi xi 0 if x x1 xn is a negative example 2006 Carlos Guestrin 23 Not linearly separable data Some datasets are not linearly separable 2006 Carlos Guestrin 24 Addressing non linearly separable data Option 1 non linear features Choose non linear features e g Typical linear features w0 i wi xi Example of non linear features Degree 2 polynomials w0 i wi xi ij wij xi xj Classifier hw x still linear in parameters w Usually easy to learn closed form or convex concave optimization Data is linearly separable in higher dimensional spaces More discussion later this semester 2006 Carlos Guestrin 25 Addressing non linearly separable data Option 2 non linear classifier Choose a classifier hw x that is non linear in parameters w e g Decision trees neural networks nearest neighbor More general than linear
View Full Document
Unlocking...