Page 1
CS361 (Software Engineering Program) Artificial Intelligence II-Applied Machine Learning Lecture 7 A Basic Introduction to Ensemble Learning [ Bagging, Random Forests, Boosting, AdaBoost ] Amr S. Ghoneim (Assistant Professor, Computer Science Dept.) Helwan University Fall 2019 Lecture is based on its counterparts in the following courses (and the following resources): o Ensemble Learning, University of Szeged "Szegedi Tudományegyetem" (Hungary), Institute of Informatics. o Web-Mining Agents: Classification with Ensemble Methods, Universität zu Lübeck (Germany), R. Möller, at the Institute of Information Systems. o Machine Learning CS165B, UCSB University of California Santa Barbara (California USA), Department of Computer Science. o Explaining AdaBoost, Princeton University (New Jersey USA), Rob E. Schapire, Department of Computer Science: https://www.cs.princeton.edu/~schapire/papers/explaining-adaboost.pdf
Page 2
Today’s Key Concepts o Basic Idea o Condorcet’s Jury Theorem o Strong versus Weak Learners o Ensemble Learning .. a Generic Approach o Conditions o How to produce Diverse Classifiers? o Randomization of Decision Trees o Random Forests o Ensemble-Based Methods specifically invented for Ensemble Learning o Bagging o Bootstrap Resampling o Random Forests o Boosting o Boosting by Sampling o Boosting by Weighting o Adaboost (Adaptive Boosting)
Page 3
Machine Learning? {A r t i f i c i a l I n t e l l i g e n c e} M a c h i n e L e a r n i n g M a p 3
Page 4
Recap:Supervised Learning Goal: learn predictor h(x): o High accuracy (low error). o Using training data { (x1, y1), .., (xn, yn) }.
Page 5
Recap:Supervised Learning Person Age Male? Height > 55” Male? Alice 14 0 1 Yes No Bob 10 1 1 Age>9? Age>10? Carol 13 0 1 Yes No Yes No Dave 8 1 0 Erin 11 0 0 1 0 1 0 Frank 9 1 1 Gena 8 0 0 é age ù ìï 1 height > 55" x =ê ú y =í êë 1 úû ïî 0 height £ 55" [gender=male]
Page 6
Basic Idea ..Condorcet’s Jury Theorem Concordet’s jury theorem (1785) is a political science theorem about the relative probability of a given group of individuals arriving at a correct decision. The theorem was first expressed by the Marquis de Condorcet in his 1785 work Essay on the Application of Analysis to the Probability of Majority Decisions. The assumptions of the simplest version of the theorem are that: • A group wishes to reach a decision by majority vote (i.e., the votes are combined by the majority rule). • One of the two outcomes of the vote is correct (i.e., they have to select between two choices from which only one is correct). • Each voter has an independent probability p of voting for the correct decision (i.e., They vote independently, and the probability that they vote correctly is p). The theorem asks how many voters we should include in the group.
Page 7
Basic Idea ..Condorcet’s Jury Theorem The result depends on whether p is greater than or less than 1/2: o If p is greater than 1/2 (each voter is more likely to vote correctly), then adding more voters increases the probability that the majority decision is correct. In the limit, the probability that the majority votes correctly approaches 1 as the number of voters increases. o On the other hand, if p is less than 1/2 (each voter is more likely to vote incorrectly), then adding more voters makes things worse: the optimal jury consists of a single voter. That is, Let M denotes the probability that the majority vote is correct, thus if p > 0.5, then M→1 if the number of votes goes to infinity. • The crowd is more clever than the individuals under relatively weak assumptions. • Each individual must be correct: p > 0.5 (better than random guessing). • They should make independent decisions. Now, how can we apply this idea in machine learning?
Page 8
Basic Idea .. An Example:Weather Forecast Reality 1 X X X 2 X X X 3 X X X 4 X X 5 X X Combine CS 4700, Foundations of Artificial Intelligence, Carla P. Gomes
Page 9
StrongversusWeak Learners Strong learner: we seek to produce one classifier for which the classification error can be made arbitrarily small (So far we’ve been looking for such methods). Weak learner: a classifier which is just better than random guessing (thus, now, this will be mostly our only expectation). Ensemble learning: instead of creating one strong classifier, we create a huge set of weak classifiers, then we combine their outputs into one final decision. o According to Concordet’s theorem, under proper conditions we can expect that the ensemble model can attain an error rate that is arbitrarily close to zero. o While creating a lot of weak classifiers is hopefully a much easier task than to create one strong classifier.
Page 11
Conditions Training the same classifier on the same training data several times would give the same result for most machine learning algorithms (with the exception of methods where the training involves some randomness). o Combining these classifiers would make no sense. Classifier combination gives the best result if: o The classifier outputs for the same input are diverse. o The classifiers operate independently (or at least partially independently). o The classifiers have some unique or “local” knowledge. E.g., they are trained on different (or at least partially different) training data sets. We also must have some formalism to combine (aggregate) the opinions of the various classifiers.
Page 12
How to produceDiverse Classifiers? o We can combine different learning algorithms (“hybridization”). o E.g. we can train a GMM, an SVM, a k-NN,… over the same data, and then combine their output. o We can combine the same learning algorithm trained several times over the same data. o This works only if there is some random factor in the training method. o For example, Neural Networks trained with different random initialization. o We can combine the same learning algorithm trained over different subsets of the training data. o We can also try using different subsets of the features. o Or different subsets of the target classes (multi-class task, lot of classes). o For certain algorithms we can use the same algorithm over the same data, but with a different weighting over the data instances.
Page 13
Randomization of Decision Trees Random Forests The decision tree is a very popular choice for combination-based methods: o (Small) decision trees are not really efficient classifiers. o But their training is very simple and fast, so it is very easy to create an ensemble learner from a huge set of (small) decision trees. The decision tree algorithm is deterministic, how can we modify it to produce different learners at different runs? o Data Randomization – use different subsets of training data for each tree. o “Random Subspace” method – each tree is grown using a random subset of the features. o Algorithm Randomization – instead of choosing the best attribute for node splitting, we select an attribute randomly from the K best attributes.
Page 14
Aggregation Methods(Combining Classifiers) There are several methods to combine (aggregate) the outputs of the various classifiers: When the output is a class label: • Majority Voting. • Weighted Majority Voting (e.g., we can weight each classifier by its reliability (which also has to be estimated somehow). When the output is numeric (for example, a probability estimate for each class ci): • We can combine the dj scores by taking their (weighted) mean, product, minimum, maximum, .. etc. Stacking • Instead of using the above simple aggregation rules, we can train yet another classifier on the output values of the base classifiers.
Page 15
Aggregation Methods(Combining Classifiers) There are several methods to combine (aggregate) the outputs of the various classifiers. • Linear combination L y = w d j j j=1 L w 0 and w = 1 j j j=1 • Classification L y = w d i j ji j=1
Page 16
Aggregation Methods(Combining Classifiers) Voting versus Stacking: "Voting" or "Averaging" of predictionsof multiple pre-trained models. "Stacking": Usepredictions of multiple models as“features” to train a newmodel andusethe new model to makepredictionsontest data.
Page 17
Ensemble-based Methods Classifier combination is a general concept that can be applied for any training task, and by using any set of classifiers that are diverse. In this lecture .. we will concentrate on those algorithms that have been specially invented to exploit the ensemble approach: • They will create a large set of classifiers, called the “base learners”. • These classifiers can be weak, as we expect that the power of these methods will be in the ensemble approach. • We will create a lot from these base classifiers. • We will try to force them to be diverse, or in better methods, to complement each other. • During their combination we will seek maximum classification accuracy. These methods will be: Bagging, Boosting, AdaBoost, and Random Forests.
Page 18
Bagging – basedonBootstrapResampling Random Forests – basedonDecisionTrees Boosting –BoostingbySampling –BoostingbyWeighting Adaboost (AdaptiveBoosting) Ensemble-BasedMethods specificallyinventedfor EnsembleLearning
Page 19
Bagging ..Bootstrap+ aggregating o It uses bootstrap resampling to generate L different training sets from the original training set. o On the L training sets it trains L base learners. o During testing it aggregates the L learners by taking their average (using uniform weights for each classifiers), or by majority voting. o The diversity or complementarity of the base learners is not controlled in any way, it is left to chance and to the instability of the base learning method. o The ensemble model is almost always better than the unique base learners if the base learners are unstable (which means that a small change in the training dataset may cause a large change in the result of the training).
Page 20
Bootstrap Resampling Suppose we have a training set with n samples: • We would like to create L different training sets from it. • Bootstrap resampling takes random samples from the original set with replacement. • Randomness is required to obtain different sets for L rounds of resampling. • Allowing replacement is required to be able to create sets of size n from the original data set of size n. • As the L training sets are different, the result of the training over these set will also be more or less different, independent of what kind of training algorithm we use. • Works better with unstable learners (e.g., neural nets, decision trees). • Not really effective with stable learners (e.g., k-NN, SVM).
Showing the first 20 pages. Download the document to see it all.
Comments (0)
No comments yet. Be the first!