2025 Fall UVA CS - Machine Learning



TuTh 3:30pm-4:45PM

RF and Boosting

3Classification Ensemble Discriminative

Att: the following markdown text was generated from the corresponding powerpoint lecture file automatically. Errors and misformatting, therefore, do exist (a lot!)!

Summary:

Study Guide: Ensemble Methods in Machine Learning

This guide provides a comprehensive review of ensemble methods in machine learning, including Bagging, Random Forests, Stacking, and Boosting, based on the provided lecture materials. It includes a quiz to test your knowledge, an answer key, a set of essay questions for deeper consideration, and a glossary of key terms.

Short-Answer Quiz

Instructions: Answer the following questions in 2-3 sentences each, based on the provided source material.

  1. What is the core two-step framework of an ensemble method in machine learning?
  2. Explain the process of “bootstrap sampling” as it is used in Bagging.
  3. Why is model instability considered a beneficial trait for the base classifiers used in Bagging?
  4. What is the primary limitation of Bagging that the Random Forest algorithm is designed to address?
  5. How does the Random Forest algorithm de-correlate the individual decision trees within its ensemble?
  6. Explain the role that pairwise correlation (ρ) between trees plays in determining the overall variance of an ensemble model.
  7. Describe the general architecture of Stacking, identifying its main components.
  8. What are the three core principles that guide boosting strategies?
  9. Contrast the training processes of Boosting and Bagging, highlighting a key difference in their approach to the training data.
  10. List at least three key features of the XGBoost implementation that contribute to its efficiency.

Answer Key

  1. The framework of an ensemble method involves two main steps. First, a set of diverse classifiers is generated. Second, the predictions of these individual classifiers are aggregated, for instance by taking a majority vote, to form a final prediction.

  2. Bootstrap sampling is a technique of randomly drawing datasets with replacement from the original training data. Each new sample is the same size as the original training set, and because the sampling is done with replacement, individual data points can be duplicated within a sample.

  3. Model instability is beneficial in Bagging because the more variable or unstable a basic model is, the more improvement can be gained by averaging multiple versions of it. High-variability models like decision trees see more improvement from Bagging than low-variability methods.

  4. The primary limitation of Bagging is that the bagged trees are often correlated with each other. Random Forest is an extension of Bagging that was specifically designed to reduce this correlation between the trees.

  5. Random Forest de-correlates its trees by introducing an additional layer of randomness during the tree-building process. At each node, when choosing a feature for a split, the algorithm only considers a random subset of m features from the total p available features, rather than all of them.

  6. Pairwise correlation (ρ) between classifiers directly impacts the variance of the ensemble’s average prediction. Even as the number of classifiers (B) approaches infinity, the variance term related to correlation (ρσ²) remains, meaning that higher correlation prevents the total variance from being minimized.

  7. Stacking involves learning and combining multiple classifiers. It uses a set of “base learners” trained on the data, and their predictions are then fed as input into a “meta learner” or “blender,” which is a higher-level classifier that makes the final prediction.

  8. The three core principles of boosting are: (1) using many base classifiers to vote on a decision, (2) sequentially training classifiers where each corrects the mistakes of the previous ones, thereby focusing on hard examples, and (3) giving higher weight to the better-performing base classifiers.

  9. Unlike Bagging, which trains classifiers in parallel on different bootstrap samples of the data, Boosting trains classifiers sequentially on the entire training set. Boosting adaptively re-weights the training examples at each step to focus on instances that previous classifiers misclassified.

  10. Key features of the XGBoost implementation include: the ability to use L1 or L2 regularization, a sparsity-aware split finding algorithm for handling sparse data, and a block structure system design that enables parallel learning across multiple CPU cores. Other features include cache awareness and out-of-core computing for very large datasets.

Essay Questions

Instructions: The following questions are designed for longer, more detailed responses. Formulate your answers by synthesizing information from across the lecture materials.

  1. Compare and contrast the Bagging and Boosting ensemble methods. Discuss their approaches to training data, model creation (parallel vs. sequential), and their primary goals in improving model performance.

  2. Explain the Bias-Variance Tradeoff in the context of ensemble methods. How do techniques like Bagging leverage complex, high-variance base models (like full decision trees) to create a final classifier with significantly lower variance?

  3. Describe the evolution from a simple Bagged Decision Tree to a Random Forest. What specific mechanism was introduced in Random Forest, and why is it mathematically significant for reducing the ensemble’s variance, as explained by the role of pairwise tree correlation?

  4. Detail the sequential nature of boosting algorithms like AdaBoost. How does the process focus on “hard examples” from one iteration to the next, and what roles do example weights and classifier weights play in constructing the final, powerful model?

  5. Discuss the practical implementation and features of modern boosting libraries like XGBoost and LGBM. What technical innovations allow them to be so efficient and popular in machine learning competitions, and what is a key difference in their tree growth strategies?

Glossary of Key Terms

Term Definition
AdaBoost An adaptive boosting algorithm that sequentially trains base classifiers, focusing on hard examples from previous iterations by updating example weights, and combines them into a final weighted sum.
Bagging Stands for “Bootstrap Aggregation.” An ensemble technique for reducing the variance of a prediction function by generating multiple versions of a predictor from bootstrap samples and aggregating them.
Base Learner An individual classifier (e.g., a decision tree) that is part of a larger ensemble model, particularly used in the context of Stacking.
Boosting An ensemble method that sequentially trains base classifiers, where each new classifier is trained to correct the mistakes of the previous ones. It combines a weighted sum of many classifiers, often shallow decision trees.
Bootstrap Sampling A re-sampling technique that involves randomly drawing datasets with replacement from the original training data. Each sample is the same size as the original set.
Discriminative Classifier A type of classification approach that directly estimates a decision rule or boundary. Examples include SVM, decision trees, and neural networks.
Ensemble Method A machine learning framework that involves generating a set of diverse classifiers and aggregating their predictions to produce a final result. Examples include Bagging, Boosting, and Stacking.
Generative Classifier A type of classification approach that builds a generative statistical model. Examples include Bayesian networks and Naïve Bayes classifiers.
Instance-based Classifier A type of classification approach that uses observations directly without building an explicit model. An example is the K-nearest neighbors algorithm.
LGBM Stands for Light Gradient Boosted Machines. An efficient library for training GBMs developed by Microsoft that uses leaf-wise tree growth and novel techniques like Gradient-based one-side sampling.
Meta Learner (Blender) In Stacking, the higher-level classifier that is trained on the predictions generated by the base learners to make the final prediction.
Random Forest An ensemble classifier that extends Bagging by de-correlating the trees. It does this by considering only a random subset of features at each split when building the individual decision trees.
Stacking An ensemble method where multiple base learners are trained, and a meta learner is then trained on the predictions of the base learners to produce the final output.
XGBoost Stands for Extreme Gradient Boosting. A highly efficient and popular implementation of a Gradient Boosting Decision Tree that incorporates features like regularization, parallel learning, and handling of sparse data.