Logistic Regression,Generative and Discriminative ClassifiersOverviewGenerative vs. Discriminative ClassifiersLogistic regressionLogistic regressionBinary logistic regressionLogistic regression vs. Linear regressionExampleLog likelihoodLog likelihoodMaximum likelihood estimationGradient descentGradient ascentExampleConvergenceNaïve Bayes vs. Logistic RegressionGenerative-Discriminative PairsGenerative-Discriminative PairsWhat is the difference asymptotically?Rate of covergence: logistic regressionRate of covergence: naïve BayesRate of covergence: naïve Bayes parametersSome experiments from UCI data setsWhat you should know:AcknowledgmentLogistic Regression,Generative and Discriminative ClassifiersRecommended reading: • Ng and Jordan paper “On Discriminative vs. Generative classifiers: A comparison of logistic regression and naïve Bayes,” A. Ng and M. Jordan, NIPS 2002.Machine Learning 10-701Tom M. MitchellCarnegie Mellon UniversityThanks to Ziv Bar-Joseph, Andrew Moore for some slidesOverviewLast lecture:• Naïve Bayes classifier• Number of parameters to estimate• Conditional independenceThis lecture: • Logistic regression• Generative and discriminative classifiers• (if time) Bias and variance in learningGenerative vs. Discriminative ClassifiersTraining classifiers involves estimating f: X Æ Y, or P(Y|X)Generative classifiers:• Assume some functional form for P(X|Y), P(X)• Estimate parameters of P(X|Y), P(X) directly from training data• Use Bayes rule to calculate P(Y|X= xi)Discriminative classifiers:1. Assume some functional form for P(Y|X)2. Estimate parameters of P(Y|X) directly from training data• Consider learning f: X Æ Y, where• X is a vector of real-valued features, < X1…Xn>• Y is boolean• So we use a Gaussian Naïve Bayes classifier• assume all Xiare conditionally independent given Y• model P(Xi| Y = yk) as Gaussian N(µik,σ)• model P(Y) as binomial (p)• What does that imply about the form of P(Y|X)?• Consider learning f: X Æ Y, where• X is a vector of real-valued features, < X1…Xn>• Y is boolean• assume all Xiare conditionally independent given Y• model P(Xi| Y = yk) as Gaussian N(µik,σ)• model P(Y) as binomial (p)• What does that imply about the form of P(Y|X)?Logistic regression• Logistic regression represents the probability of category i using a linear function of the input variables:where for i<kand for k)()|(110 didiixwxwwgxXiYP+++=== K∑−=+=111)(Kjzzijieezg∑−=+=1111)(KjzkjezgLogistic regression• The name comes from the logit transformation:didikixwxwwzgzgxXKYpxXiYp+++======K110)()(log)|()|(logBinary logistic regression• We only need one set of parameters• This results in a “squashing function” which turns linear predictions into probabilitieszxwxwwxwxwwxwxwweeeexXYpdddddd−+++−+++++++=+=+===11111)|1()(110110110KKKLogistic regression vs. Linear regressionzexXYP−+===11)|1(ExampleLog likelihood∑∑∑===+−=++−=−−+=NiwxiiNiwxiiiNiiiiiiiewxyewxpwxpywxpywxpywl111)1log()11log();(1();(log));(1log()1();(log)(Log likelihood∑∑∑===+−=++−=−−+=NiwxiiNiwxiiiNiiiiiiiewxyewxpwxpywxpywxpywl111)1log()11log();(1();(log));(1log()1();(log)(• Note: this likelihood is a concave in wMaximum likelihood estimation∑∑==−==+−∂∂=∂∂NiiiijNiwxiijjwxpyxewxywwlwi11)),(()}1log({)(Kprediction errorCommon (but not only) approaches:Numerical Solutions:•Line Search• Simulated Annealing• Gradient Descent•Newton’s Method• Matlab glmfit functionNo close form solution!Gradient descentGradient ascent)),(((1wxpyxwwiiijitjtj−+←∑+ε• Iteratively updating the weights in this fashion increases likelihood each round. • We eventually reach the maximum • We are near the maximum when changes in the weights are small. • Thus, we can stop when the sum of the absolute values of the weight differences is less than some small number.Example• We get a monotonically increasing log likelihood of the training labels as a function of the iterationsConvergence• The gradient ascent learning method converges when there is no incentive to move the parameters in any particular direction: kwxpyxiiiji∀=−∑0)),(((• This condition means that the prediction error is uncorrelated with the components of the input vectorNaïve Bayes vs. Logistic Regression• Generative and Discriminative classifiers• Asymptotic comparison (# training examples Æ infinity)• when model correct• when model incorrect• Non-asymptotic analysis• convergence rate of parameter estimates• convergence rate of expected error• Experimental results[Ng & Jordan, 2002]Generative-Discriminative PairsExample: assume Y boolean, X = <X1, X2, …, Xn>, where xiare boolean, perhaps dependent on Y, conditionally independent given YGenerative model: naïve Bayes:Classify new example x based on ratioEquivalently, based on sign of log of this ratios indicates size of set.l is smoothing parameterGenerative-Discriminative PairsExample: assume Y boolean, X = <x1, x2, …, xn>, where xiare boolean, perhaps dependent on Y, conditionally independent given YGenerative model: naïve Bayes:Classify new example x based on ratioDiscriminative model: logistic regressionNote both learn linear decision surface over X in this caseWhat is the difference asymptotically?Notation: let denote error of hypothesis learned via algorithm A, from m examples• If assumed model correct (e.g., naïve Bayes model), and finite number of parameters, then• If assumed model incorrectNote assumed discriminative model can be correct even when generative model incorrect, but not vice versaRate of covergence: logistic regressionLet hDis,mbe logistic regression trained on m examples in ndimensions. Then with high probability:Implication: if we wantfor some constant , it suffices to pick Æ Convergences to its classifier, in order of n examples(result follows from Vapnik’s structural risk bound, plus fact that VCDim of n dimensional linear separators is n )Rate of covergence: naïve BayesConsider first how quickly parameter estimates converge toward their asymptotic values. Then we’ll ask how this influences rate of convergence toward asymptotic classification error.Rate of covergence: naïve Bayes parametersSome experiments from UCI data setsWhat you should know:• Logistic regression– What it is– How to solve it– Log linear models• Generative and Discriminative classifiers– Relation between Naïve Bayes
View Full Document
Unlocking...