Logistic Regression (Continued)Generative v. DiscriminativeDecision TreesAnnouncementsLogistic RegressionLogistic Regression – a Linear classifierLogistic regression v. Naïve BayesGaussian Naïve Bayes v. Logistic RegressionLogistic regression more generallyLogistic regression with more than 2 classes – an exampleLoss functions: Likelihood v. Conditional LikelihoodExpressing Conditional Log LikelihoodMaximizing Conditional Log LikelihoodOptimizing concave function – Gradient ascentMaximize Conditional Log Likelihood: Gradient ascentThat’s all M(C)LE. How about MAP?M(C)AP as RegularizationGradient of M(C)APMLE vs MAPNaïve Bayes vs Logistic RegressionG. Naïve Bayes vs. Logistic Regression 1G. Naïve Bayes vs. Logistic Regression 2Some experiments from UCI data setsWhat you should know about Logistic Regression (LR)Linear separabilityNot linearly separable dataAddressing non-linearly separable data – Option 1, non-linear featuresAddressing non-linearly separable data – Option 2, non-linear classifierA small dataset: Miles Per GallonA Decision StumpRecursion StepRecursion StepSecond level of treeClassification of a new exampleAre all decision trees equal?Learning decision trees is hard!!!Choosing a good attributeMeasuring uncertaintyEntropyAndrew Moore’s Entropy in a nutshellAndrew Moore’s Entropy in a nutshellInformation gainLearning decision treesInformation Gain ExampleLook at all the information gains…A Decision StumpBase CasesBase Cases: An ideaThe problem with Base Case 3If we omit Base Case 3:Basic Decision Tree Building SummarizedReal-Valued inputs“One branch for each numeric value” idea:Threshold splitsChoosing threshold splitA better idea: thresholded splitsExample with MPGExample tree using realsWhat you need to know about decision treesAcknowledgements©2006 Carlos Guestrin1Naïve Bayes & Logistic Regression,See class website:Mitchell’s Chapter (required)Ng & Jordan ’02 (optional)Gradient ascent and extensions:Koller & Friedman Chapter 1.4Decision Trees: many possible refs., e.g.,Mitchell, Chapter 3 Logistic Regression (Continued)Generative v. DiscriminativeDecision TreesMachine Learning – 10701/15781Carlos GuestrinCarnegie Mellon UniversityFebruary 1st, 2006©2006 Carlos Guestrin2Announcements 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 8thbeginning of class Mitchell’s chapter is most useful reading©2006 Carlos Guestrin3Logistic RegressionLogisticfunction(or Sigmoid): Learn P(Y|X) directly! Assume a particular functional form Sigmoid applied to a linear function of the data:Z©2006 Carlos Guestrin4Logistic Regression –a Linear classifier-6 -4 -2 0 2 4 600.10.20.30.40.50.60.70.80.91©2006 Carlos Guestrin5Logistic 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 Xiare 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 Guestrin6Gaussian Naïve Bayes v. Logistic RegressionSet of Gaussian Naïve Bayes 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 solutionsSet of Logistic Regression parameters©2006 Carlos Guestrin7Logistic regression more generally Logistic regression in more general case, where Y ∈{Y1... YR} : learn R-1 sets of weightsfor k<Rfor k=R (normalization, so no weights for this class)Features can be discrete or continuous!©2006 Carlos Guestrin8Logistic regression with more than 2 classes – an example Y ∈{Y1... YR} : learn R-1 sets of weightsfor k<Rfor k=R (normalization, so no weights for this class)Features can be discrete or continuous!©2006 Carlos Guestrin9Loss 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 Guestrin10Expressing Conditional Log Likelihood©2006 Carlos Guestrin11Maximizing Conditional Log LikelihoodGood news: l(w) is concave function of w → no locally optimal solutionsBad news: no closed-form solution to maximize l(w)Good news: concave functions easy to optimize©2006 Carlos Guestrin12Optimizing concave function –Gradient ascent Conditional likelihood for Logistic Regression is concave → Find optimum with gradient ascent Gradient ascent is simplest of optimization approaches e.g., Conjugate gradient ascent much better (see reading)Gradient:Update rule:Learning rate, η>0©2006 Carlos Guestrin13Maximize Conditional Log Likelihood: Gradient ascentGradient ascent algorithm: iterate until change < εFor all i, repeat©2006 Carlos Guestrin14That’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 Guestrin15M(C)AP as RegularizationPenalizes high weights, also applicable in linear regression (see homework)©2006 Carlos Guestrin16Gradient of M(C)AP©2006 Carlos Guestrin17MLE vs MAP Maximum conditional likelihood estimate Maximum conditional a posteriori estimate©2006 Carlos Guestrin18Naïve Bayes vs Logistic RegressionConsider Y boolean, Xicontinuous, X=<X1... Xn>Number of parameters: NB: 4n +1 LR: n+1Estimation method: NB parameter estimates are uncoupled LR parameter estimates are coupled©2006 Carlos Guestrin19G. 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
View Full Document