Logistic Regression Continued Generative v Discriminative Decision Trees Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University January 31st 2007 2005 2007 Carlos Guestrin 1 Generative v Discriminative classifiers Intuition Want to Learn h X Y X features Y target classes Bayes optimal classifier P Y X Generative classifier e g Na ve Bayes Assume some functional form for P X Y P Y Estimate parameters of P X Y P Y directly from training data Use Bayes rule to calculate P Y X x This is a generative model Indirect computation of P Y X through Bayes rule But can generate a sample of the data P X y P y P X y Discriminative classifiers e g Logistic Regression Assume some functional form for P Y X Estimate parameters of P Y X directly from training data This is the discriminative model Directly learn P Y X But cannot obtain a sample of the data because P X is not available 2005 2007 Carlos Guestrin 2 1 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 Features can be 2005 2007 discrete or continuous Carlos Guestrin Logistic Regression a Linear classifier 3 1 0 9 0 8 0 7 0 6 0 5 0 4 0 3 0 2 0 1 0 6 2005 2007 Carlos Guestrin 4 2 0 2 4 6 4 2 Very convenient implies implies linear classification rule implies 2005 2007 Carlos Guestrin 5 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 2005 2007 Carlos Guestrin 6 3 Derive form for P Y X for continuous Xi 2005 2007 Carlos Guestrin 7 Ratio of class conditional probabilities 2005 2007 Carlos Guestrin 8 4 Derive form for P Y X for continuous Xi 9 2005 2007 Carlos Guestrin Gaussian Na ve Bayes v Logistic Regression Set of Gaussian Na ve Bayes parameters feature variance independent of class label 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 2005 2007 Carlos Guestrin 10 5 Logistic regression for more than 2 classes Logistic regression in more general case where Y Y1 YR learn R 1 sets of weights 2005 2007 Carlos Guestrin 11 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 2005 2007 Carlos Guestrin 12 6 Announcements Don t forget recitation tomorrow And start the homework early 2005 2007 Carlos Guestrin 13 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 2005 2007 Carlos Guestrin 14 7 Expressing Conditional Log Likelihood 2005 2007 Carlos Guestrin 15 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 2005 2007 Carlos Guestrin 16 8 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 2005 2007 Carlos Guestrin 17 Maximize Conditional Log Likelihood Gradient ascent 2005 2007 Carlos Guestrin 18 9 Gradient Descent for LR Gradient ascent algorithm iterate until change For i 1 n repeat 2005 2007 Carlos Guestrin 19 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 More on this later in the semester MAP estimate 2005 2007 Carlos Guestrin 20 10 M C AP as Regularization Penalizes high weights also applicable in linear regression 2005 2007 Carlos Guestrin 21 Gradient of M C AP 2005 2007 Carlos Guestrin 22 11 MLE vs MAP Maximum conditional likelihood estimate Maximum conditional a posteriori estimate 2005 2007 Carlos Guestrin 23 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 2005 2007 Carlos Guestrin 24 12 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 25 2005 2007 Carlos Guestrin 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 2005 2007 Carlos Guestrin 26 13 Na ve bayes Logistic Regression Some experiments from UCI data sets 2005 2007 Carlos Guestrin 27 What you should know about Logistic Regression LR Gaussian Na ve Bayes with class independent variances representationally equivalent to LR In general NB and LR make different assumptions Solution differs because of objective loss function 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 less data LR usually gets to better solutions in the limit 2005 2007 Carlos Guestrin 28 14 Linear separability A dataset is linearly separable iff a separating hyperplane w such that w0 i
View Full Document
Unlocking...