Machine Learning 10 701 Tom M Mitchell Machine Learning Department Carnegie Mellon University January 27 2011 Today Readings Required Mitchell Na ve Bayes and Logistic Regression see class website Na ve Bayes Big Picture Logistic regression Gradient ascent Generative discriminative classifiers Optional Ng and Jordan paper class website Gaussian Na ve Bayes Big Picture Consider boolean Y continuous Xi Assume P Y 1 0 5 1 What is the minimum possible error Best case conditional independence assumption is satistied we know P Y P X Y perfectly e g infinite training data Logistic Regression Idea Na ve Bayes allows computing P Y X by learning P Y and P X Y Why not learn P Y X directly 2 Consider learning f X Y where 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 What does that imply about the form of P Y X Derive form for P Y X for continuous Xi 3 Very convenient implies implies implies Very convenient implies implies implies linear classification rule 4 Logistic function 5 Logistic regression more generally Logistic regression when Y not boolean but still discrete valued Now y y1 yR learn R 1 sets of weights for k R for k R Training Logistic Regression MCLE we have L training examples maximum likelihood estimate for parameters W maximum conditional likelihood estimate 6 Training Logistic Regression MCLE Choose parameters W w0 wn to maximize conditional likelihood of training data where Training data D Data likelihood Data conditional likelihood Expressing Conditional Log Likelihood 7 Maximizing Conditional Log Likelihood Good news l W is concave function of W Bad news no closed form solution to maximize l W 8 Maximize Conditional Log Likelihood Gradient Ascent Maximize Conditional Log Likelihood Gradient Ascent Gradient ascent algorithm iterate until change For all i repeat 9 That s all for M C LE How about MAP One common approach is to define priors on W Normal distribution zero mean identity covariance Helps avoid very large weights and overfitting MAP estimate let s assume Gaussian prior W N 0 MLE vs MAP Maximum conditional likelihood estimate Maximum a posteriori estimate with prior W N 0 I 10 MAP estimates and Regularization Maximum a posteriori estimate with prior W N 0 I called a regularization term helps reduce overfitting especially when training data is sparse keep weights nearer to zero if P W is zero mean Gaussian prior or whatever the prior suggests used very frequently in Logistic Regression The Bottom Line Consider learning f X Y where 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 Then P Y X is of this form and we can directly estimate W Furthermore same holds if the Xi are boolean trying proving that to yourself 11 Generative vs Discriminative Classifiers Training classifiers involves estimating f X Y or P Y X Generative classifiers e g Na ve Bayes 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 e g Logistic regression Assume some functional form for P Y X Estimate parameters of P Y X directly from training data Use Na ve Bayes or Logisitic Regression Consider Restrictiveness of modeling assumptions Rate of convergence in amount of training data toward asymptotic hypothesis i e the learning curve 12 Na ve Bayes vs Logistic Regression Consider Y boolean Xi continuous X X1 Xn Number of parameters to estimate NB LR 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 13 G Na ve Bayes vs Logistic Regression Generative and Discriminative classifiers Ng Jordan 2002 Asymptotic comparison training examples infinity when conditional independence assumptions correct GNB LR produce identical classifiers when conditional independence assumptions incorrect LR is less biased does not assume cond indep therefore expected to outperform GNB when both given infinite training data Na ve Bayes vs Logistic Regression Generative and Discriminative classifiers Non asymptotic analysis see Ng Jordan 2002 convergence rate of parameter estimates how many training examples needed to assure good estimates GNB order log n where n of attributes in X LR order n GNB converges more quickly to its perhaps less accurate asymptotic estimates Informally because LR s parameter estimates are coupled but GNB s are not 14 Some experiments from UCI data sets Ng Jordan 2002 Summary Na ve Bayes and Logistic Regression Modeling assumptions Na ve Bayes more biased cond indep Both learn linear decision surfaces Convergence rate n number training examples Na ve Bayes O log n Logistic regression O n Bottom line Na ve Bayes converges faster to its potentially too restricted final hypothesis 15 What you should know Logistic regression Functional form follows from Na ve Bayes assumptions For Gaussian Na ve Bayes assuming variance i k i For discrete valued Na ve Bayes too But training procedure picks parameters without the conditional independence assumption MLE training pick W to maximize P Y X W MAP training pick W to maximize P W X Y regularization e g P W N 0 helps reduce overfitting Gradient ascent descent General approach when closed form solutions for MLE MAP are unavailable Generative vs Discriminative classifiers Bias vs variance tradeoff 16
View Full Document
Unlocking...