Ensembles

Algorithms can make mistakes, so it's important to increase confidence in their outputs.

Ensembles are a machine learning technique designed to do exactly that. They increase confidence in predictions:

• multiple learners are used simultaneously
• their outputs are aggregated to produce a final decision

Ensembles are useful with decision trees, which tend to overfit. By combining many overfitted trees, an ensemble can produce a model that generalizes better.

Voting

Voting is used to improve decision-making by aggregating the outputs of multiple learners.

Making decisions is hard for computers and humans alike:

• human:
  • societies often aggregate many people's opinions to reduce the impact of individual biases or errors
  • this doesn't guarantee perfect decisions but helps avoid mistakes caused by one person's judgment
• machines:
  • machine learning models also have biases, often inherited from the training data
  • if the data is biased, incomplete, or unbalanced, the model's predictions will reflect those flaws

Voting-based ensembles make decisions by consensus:

• multiple learners are trained on different datasets
• after training, each model makes a prediction
• the final result is determined by a voting method

Voting methods:

• plurality voting
  • each model gets one vote
  • the prediction with the most votes wins
  • ties are resolved randomly or with a re-vote
• weighted plurality voting
  • each vote is assigned a weight
  • some learners influence the result more than others
• confidence-based voting
  • learners indicate how confident they are
  • more confident predictions count more

Ensembles of decision trees

Popular techniques for building decision tree ensembles:

1. bagging
2. random forest
3. extremely randomized trees

Bagging (bootstrap aggregating)

Bagging improves prediction accuracy by combining multiple decision trees.

It works by creating many "bootstrap" datasets from the original training using sampling with replacement:

Each bootstrap is then used to train a separate decision tree.

Together, these trees form an ensemble.

To classify a new sample:

1. give the sample to every decision tree in the ensemble
2. each tree makes a prediction
3. the final result is chosen by a plurality vote producing either a winner or a tie

Analysis shows that more trees generally improve accuracy, but beyond a point, gains diminish (law of diminishing returns).

Rule of thumb: use roughly as many trees as classes in the dataset, or search for the best number of trees using cross-validation.

Random forest (feature bagging)

Random forests improve on basic bagging by adding randomness in feature selection to improve diversity and accuracy.

Like bagging, each tree is trained on bootstrapped subsets of the training data and predictions are made by plurality vote across all trees.

However, random forests add feature randomness or feature bagging:

• when splitting a decision node in a tree, the model does not consider all features
• instead, a random subset of features is selected
• then the best split is chosen only from that subset (using e.g., information gain or gini impurity)
• this is done independently at each node to prevent the same dominant features from being chosen repeatedly

This randomness reduces the correlation between trees, increasing ensemble diversity and improving overall performance.

In "random forest":

• random: refers to the random choice of features at each node
• forest: refers to the resulting collection of decision trees

Extra trees (extremely randomized trees)

Extra trees is another way to add randomness:

• instead of finding the best split at each node based on a criterion (like information gain), the split point is chosen randomly from the feature's values
• the result is an ensemble called Extremely Randomized Trees (Extra Trees)

A classifier built with randomness seems counterintuitive, however:

• multiple trees are trained on the same dataset (typically without bootstrapping)
• their predictions are combined to produce a joint conclusion about an input sample
• each tree has different strengths and weaknesses
• when combined, the strengths tend to enhance the output quality, making the sum greater than the parts

This added randomness helps reduce overfitting, making the ensemble more robust, even if individual trees are less accurate.

Boosting

Boosting combines many weak learners into a strong learner. It's applicable to any kind of learner, not just decision trees.

A weak learner is a classifier that performs just slightly better than random:

Step	Explanation	Image
Dataset	A dataset with samples from two classes.
Random labeling	A random classifier ignores the data and randomly assigns each sample to one of the two classes like flipping a coin.
Weak learner	The random classifier is slightly improved so that it performs just a bit better than chance. This is a weak learner.

How boosting works:

Step	Explanation	Image
Dataset	A dataset with two types of points (circles and squares). No single straight line can separate all squares from all circles.
Add the first weak classifier (line A)	Line A cuts through the space. Everything on the side of A pointed to by the arrow is labeled square, the other side is labeled circle The accuracy of this weak classifier is better than random, but not by much: (TP + TN) / (TP + TN + FP + FN) = (12 + 8) / (12 + 8 + 12 + 2) = 59 %
Add two more weak classifiers (lines B and C)	Accuracy: line B: accuracy ≈ 73% line C: accuracy ≈ 12% (worse than random, so we flip its direction → its accuracy becomes 88%) The 3 lines divide the space into seven regions, each containing only one class.
Label the regions	Label each region with the learners that point toward it. By looking at these regions, we can classify new samples using the combined output of the 3 lines.
Assign scores (0 or 1)	Instead of each classifier returning a class, make them return: 1 if the sample is on the positive side (arrow side) 0 otherwise Adding these values across learners gives a composite score for each region. Example for region C: positive side of C → 1 negative side of A and B → 0 from each total score = 1 Example for region AB: negative side of C → 0 positive side of A and B → 1 from each total score = 2
Replace 1s with classifier weights	This is where boosting kicks in: replace each 1 with a voting weight (found for us by the boosting algorithm) find a threshold that turns the summed value in each region into a class Example set of weights: A = 1 B = 1.5 C = -2 → C was pointing in the wrong direction, so giving it a negative value has the effect of reversing its decisions Now, each region has a total score. Decision rule: if sum > threshold (e.g., 0) → predict square if sum < threshold → predict circle Result: blue regions = positive score → classified as square red regions = negative score → classified as circle The combined model correctly classifies the entire dataset, even though no single line could.

Individual classifiers may perform poorly, but together they can perfectly classify complex data.

The only hyperparameter required is how many classifiers we want:

• rule of thumb: use roughly as many as there are classes
• as always in machine learning, the best number is found through trial and error

Boosting was popularized by the AdaBoost algorithm.

It is mainly designed for binary classification.