Bayesian Learning Rong Jin Outline MAP learning vs ML learning Minimum description length principle Bayes optimal classifier Bagging Maximum Likelihood Learning ML Find the model that best model by maximizing the loglikelihood of the training data Logistic regression r 1 p y x q v r 1 exp y x w c q w1 w2 wm c Parameters are found by maximizing the likelihood of training data r n w c max l D max i 1 log r r train w c w c 1 r r 1 exp y x w c Maximum A Posterior Learning MAP In ML learning models are solely determined by the training examples Very often we have prior knowledge preference about parameters models ML learning is unable to incorporate the prior knowledge preference on parameters models Maximum a posterior learning MAP Knowledge preference about parameters models are incorporated through a prior q arg max Pr D q Pr q q Prior for parameters Example Logistic Regression ML learning r n w c max l D max i 1 log r r train w c w c 1 r r 1 exp y x w c Prior knowledge Preference No feature should dominate over all other features Prefer small weights Gaussian prior for parameters models r 1 Pr w exp 2 s m 2 w i 1 i Example Logistic Regression ML learning r n w c max l D max i 1 log r r train w c w c 1 r r 1 exp y x w c Prior knowledge Preference No feature should dominate over all other features Prefer small weights Gaussian prior for parameters models r 1 Pr w exp 2 s m 2 w i 1 i Example cont d MAP learning for logistic regression r r r w c argrmax Pr D w c Pr w c w c r r arg max log Pr D w c log Pr w c q 1 1 n argrmax log r r 2 i 1 s 1 exp y x w c w c Compared to regularized logistic regression N lreg Dtrain i 1 log 1 m 2 s w r r i 1 i 1 exp y c x w m 2 w i 1 i Example cont d MAP learning for logistic regression r r r w c argrmax Pr D w c Pr w c w c r r arg max log Pr D w c log Pr w c q 1 1 n argrmax log r r 2 i 1 s 1 exp y x w c w c Compared to regularized logistic regression N lreg Dtrain i 1 log 1 m 2 s w r r i 1 i 1 exp y c x w m 2 w i 1 i Minimum Description Length Principle Occam s razor prefer the simplest hypothesis Simplest hypothesis hypothesis with shortest of bits to encode of bits to encode description length data D given h hypothesis h Minimum description length Complexity of of Mistakes Model hypothesis Prefer shortest hMDL arg min LC1 h LC2 D h h H LC x is the description length for message x under coding scheme c Minimum Description Length Principle hMDL arg min LC1 h LC2 D h h H Sender Send only D Send only h D Send h D h Receiver Example Decision Tree H decision trees D training data labels LC1 h is bits to describe tree h LC2 D h is bits to describe D given tree h Note LC2 D h 0 if examples are classified perfectly by h Only need to describe exceptions hMDL trades off tree size for training errors MAP vs MDL MAP learning hMAP arg max Pr D h Pr h arg max log 2 Pr D h log 2 Pr h h H h H arg min log 2 Pr h log 2 Pr D h h H Fact from information theory Description length of exceptions under coding length code for an optimal coding The optimal shortest expected event with probability p is log2p Description ofMAP h using MDL principle length Interpret under optimal coding hMDL arg min LC1 h LC2 D h h H Problems with Maximum Approaches Consider Three possible hypotheses Pr h1 D 0 4 Pr h2 D 0 3 Pr h3 D 0 3 Maximum approaches will pick h1 Given new instance x h1 x h2 x h3 x Maximum approaches will output However is this most probably result Bayes Optimal Classifier Bayesian Average Bayes optimal classification c x arg max c Pr h D Pr c h x h H Example Pr h1 D 0 4 Pr h1 x 1 Pr h1 x 0 Pr h2 D 0 3 Pr h2 x 0 Pr h2 x 1 Pr h3 D 0 3 Pr h3 x 0 Pr h3 x 1 Pr h D Pr h x 0 4 Pr h D Pr h x 0 6 h h The most probably class is Bayes Optimal Classifier Bayesian Average Bayes optimal classification c x arg max c Pr h D Pr c h x h H Example Pr h1 D 0 4 Pr h1 x 1 Pr h1 x 0 Pr h2 D 0 3 Pr h2 x 0 Pr h2 x 1 Pr h3 D 0 3 Pr h3 x 0 Pr h3 x 1 Pr h D Pr h x 0 4 Pr h D Pr h x 0 6 h h The most probably class is When do We Need Bayesian Average Bayes optimal classification c x arg max c Pr h D Pr c h x h H When do we need Bayesian average Multiple mode case Optimal mode is flat When NOT Bayesian Average Can t estimate Pr h D accurately Computational Issues with Bayes Optimal Classifier Bayes optimal classification c x arg max c h H Computational issues Need to sum over all possible models hypotheses h It is expensive or impossible when the model hypothesis space is large Pr h D Pr c h x Example decision tree Solution sampling Gibbs Classifier Gibbs algorithm 1 2 Choose one hypothesis at random according to P h D Use this to classify new instance Surprising fact E errGibbs 2 E err BayesOptimal Improve by sampling multiple hypotheses from P h D and average their classification results Markov chain Monte Carlo MCMC sampling Importance sampling Bagging Classifiers In general sampling from P h D is difficult because 1 P h D is rather difficult to compute 2 3 Example how to compute P h D for decision tree P h D is impossible to compute for non probabilistic classifier such as SVM P h D is extremely small when hypothesis space is large Bagging Classifiers Realize sampling P h D through a sampling of training examples Boostrap Sampling Bagging Boostrap aggregating Boostrap sampling given set D containing m training examples Create Di by drawing m examples at random with replacement from D Di expects to leave out about 0 37 of examples from D Bagging Algorithm Create k boostrap samples D1 D2 Dk Train distinct classifier hi on each Di Classify new instance by classifier vote …