AI Engineer Exhaustive
MediumClassic ML

Random Forest Majority Vote

Classic ML

Medium

Problem

A Random Forest makes predictions by aggregating the outputs of multiple decision trees. For classification, each tree votes for a class and the final prediction is the class with the most votes (majority vote).

Given the predictions from T decision trees for N samples, compute the majority vote for each sample. Break ties by choosing the smallest class label.

Algorithm

  1. For each sample, count votes from all trees

  2. Select the class with the highest vote count

  3. If multiple classes are tied, pick the smallest class label

Return one integer class label for each sample.

Theory

A Random Forest is an ensemble of decision trees. Instead of relying on a single tree, it trains many trees on different subsets of the data and combines their predictions.

The key insight: individual trees may overfit or make errors, but averaging across many diverse trees reduces variance and improves generalization.

How Random Forest Makes Predictions

For classification:

Each tree votes for a class. The final prediction is the majority vote across all trees.

\hat{y} = \text{mode}(\hat{y}_1, \hat{y}_2, ..., \hat{y}_T)

where \hat{y}_t is the prediction of tree t and T is the total number of trees.

For regression:

Each tree outputs a value. The final prediction is the average across all trees.

\hat{y} = \frac{1}{T} \sum_{t=1}^{T} \hat{y}_t

The Voting Process for Classification

Step 1: Pass the input sample to each tree in the forest

Step 2: Each tree traverses its structure and outputs a class prediction

Step 3: Count votes for each class

Step 4: Return the class with the most votes

If there is a tie, common strategies include:

Worked Example: Classification

Setup: 5 trees, 3 classes (A, B, C)

Tree predictions for sample X:

Vote count:

Final prediction: Class A (majority with 3 out of 5 votes)

Worked Example: Regression

Setup: 5 trees predicting house prices

Tree predictions for sample X:

Final prediction:

\hat{y} = \frac{250000 + 270000 + 245000 + 260000 + 255000}{5} = \frac{1280000}{5} = 256000

The predicted price is $256,000.

Why Voting Works: Wisdom of Crowds

Consider a simple model: each tree has 60% accuracy (better than random guessing at 50%).

Single tree: 60% chance of correct prediction

Majority of 5 trees: Need at least 3 correct

P(\text{majority correct}) = \sum_{k=3}^{5} \binom{5}{k} (0.6)^k (0.4)^{5-k}

= \binom{5}{3}(0.6)^3(0.4)^2 + \binom{5}{4}(0.6)^4(0.4)^1 + \binom{5}{5}(0.6)^5

= 10(0.216)(0.16) + 5(0.1296)(0.4) + 1(0.07776)

= 0.3456 + 0.2592 + 0.07776 = 0.683

Result: Ensemble accuracy 68.3% vs individual 60%

With more trees (assuming independence), accuracy approaches 100%.

Soft Voting vs Hard Voting

Hard voting: Each tree casts one vote for its predicted class. Final prediction is the mode.

Soft voting: Each tree outputs class probabilities. Average the probabilities, then pick the class with highest average probability.

Example of soft voting:

Tree 1 probabilities: [0.7, 0.2, 0.1] for classes [A, B, C]

Tree 2 probabilities: [0.4, 0.5, 0.1]

Tree 3 probabilities: [0.6, 0.3, 0.1]

Average probabilities:

Final prediction: Class A (highest average probability)

Soft voting often performs better because it considers prediction confidence.

Why Random Forests Work

Bagging (Bootstrap Aggregating):

Each tree is trained on a bootstrap sample (random sample with replacement) of the training data. This creates diversity among trees.

Feature randomization:

At each split, only a random subset of features is considered. This further decorrelates the trees.

Variance reduction:

Averaging over many decorrelated trees reduces variance without increasing bias. The expected error of the average is lower than the expected error of individuals.

\text{Var}(\bar{X}) = \frac{\text{Var}(X)}{n} \text{ (for independent variables)}

Number of Trees

More trees:

Typical values: 100 to 500 trees

Rule of thumb: Keep adding trees until out-of-bag error stabilizes.

Handling Ties in Voting

When two or more classes have equal votes:

Option 1: Random selection

Option 2: Class with lower index

Option 3: Use probabilities

Option 4: Weighted voting

Out-of-Bag Predictions

Since each tree is trained on a bootstrap sample, about 37% of samples are "out-of-bag" (not used) for each tree.

OOB prediction: For each sample, aggregate votes only from trees that did not train on it.

This provides a built-in validation estimate without needing a separate validation set.

Feature Importance from Voting

Random forests can estimate feature importance:

Mean Decrease in Impurity: Average reduction in impurity (Gini or entropy) across all splits on that feature, across all trees.

Permutation Importance: Shuffle the feature values and measure how much accuracy drops. Important features cause large drops.

Comparing Voting Strategies

Majority voting (mode):

Weighted voting:

Probability averaging (soft voting):

Computational Considerations

Prediction time: O(T \cdot d) where T is number of trees and d is average tree depth

Parallelizable: Trees are independent, so predictions can be computed in parallel

Memory: Must store all trees in memory

For a forest with 100 trees of depth 10 with 1000 leaves each, memory can be significant but usually manageable.

Examples

Example 1

Input
predictions = [[0, 1, 0], [0, 1, 1], [0, 0, 0]]
Output
[0, 1, 0]
Explanation
Votes are counted column by column across the three trees.

Example 2

Input
predictions = [[0, 1], [1, 0]]
Output
[0, 0]

Hints

  1. Build a vote-count dictionary for one sample column at a time.
  2. Find the largest count, then select the smallest label having that count.

Requirements

Constraints

Starter Code

def random_forest_vote(predictions: list) -> list:
    """
    Returns the majority-vote label for every sample.
    """
    # Write code here
    pass

Test Cases

CaseMatches
Clear majority votes—public
Tie-breaking (smallest label wins)—public