Logistic Regression Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University September 28th 2009 1 Carlos Guestrin 2005 2009 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 discrete or continuous Carlos Guestrin 2005 2009 2 1 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 4 2 0 2 Carlos Guestrin 2005 2009 4 6 3 Logistic regression for more than 2 classes Logistic regression in more general case where Y y1 yR Carlos Guestrin 2005 2009 4 2 Logistic regression more generally Logistic regression in more general case where Y y1 yR for k R for k R normalization so no weights for this class Features can be discrete or continuous Carlos Guestrin 2005 2009 5 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 Carlos Guestrin 2005 2009 6 3 Expressing Conditional Log Likelihood Carlos Guestrin 2005 2009 7 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 Carlos Guestrin 2005 2009 8 4 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 Carlos Guestrin 2005 2009 9 Maximize Conditional Log Likelihood Gradient ascent Carlos Guestrin 2005 2009 10 5 Gradient Descent for LR Gradient ascent algorithm iterate until change For i 1 n repeat Carlos Guestrin 2005 2009 11 That s all M C LE How about MAP One common approach is to define priors on w Corresponds to Regularization Normal distribution zero mean identity covariance Pushes parameters towards zero Helps avoid very large weights and overfitting More on this later in the semester MAP estimate Carlos Guestrin 2005 2009 12 6 M C AP as Regularization Penalizes high weights also applicable in linear regression Carlos Guestrin 2005 2009 13 Large parameters Overfitting If data is linearly separable weights go to infinity Leads to overfitting Penalizing high weights can prevent overfitting again more on this later in the semester Carlos Guestrin 2005 2009 14 7 Gradient of M C AP Carlos Guestrin 2005 2009 15 MLE vs MAP Maximum conditional likelihood estimate Maximum conditional a posteriori estimate Carlos Guestrin 2005 2009 16 8 Logistic regression v Na ve Bayes Consider learning f X Y where Could use a Gaussian Na ve Bayes classifier X is a vector of real valued features X1 Xn Y is boolean 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 Carlos Guestrin 2005 2009 17 Derive form for P Y X for continuous Xi Carlos Guestrin 2005 2009 18 9 Ratio of class conditional probabilities Carlos Guestrin 2005 2009 19 Derive form for P Y X for continuous Xi Carlos Guestrin 2005 2009 20 10 Gaussian Na ve Bayes v Logistic Regression Set of Gaussian Na ve Bayes parameters feature variance independent of class label Representation equivalence Set of Logistic Regression parameters 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 Carlos Guestrin 2005 2009 21 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 Carlos Guestrin 2005 2009 22 11 G Na ve Bayes vs Logistic Regression 1 Ng Jordan 2002 Generative and Discriminative classifiers Asymptotic comparison training examples infinity when model correct GNB with class independent variances and LR produce identical classifiers when model incorrect LR is less biased does not assume conditional independence therefore LR expected to outperform GNB Carlos Guestrin 2005 2009 23 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 Carlos Guestrin 2005 2009 24 12 Na ve bayes Logistic Regression Some experiments from UCI data sets Carlos Guestrin 2005 2009 25 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 LR optimized by conditional likelihood decision rule is a hyperplane 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 Carlos Guestrin 2005 2009 26 13
View Full Document
Unlocking...