Interview Question

"Explain how Random Forest reduces variance compared to a single decision tree. What is the role of feature sampling in Random Forest? How does out-of-bag error estimation work and why is it useful?"

Difficulty: Medium | Frequently asked at Google, Apple, Amazon

Theoretical Foundation

From Decision Trees to Random Forest

A single decision tree has low bias but high variance. Small changes in training data can lead to completely different tree structures. Random Forest addresses this by building many trees and aggregating their predictions.

Random Forest Algorithm:

1. For $b = 1, \ldots, B$ trees: a. Draw a bootstrap sample $X^*$ from the training data b. Grow a decision tree $T_b$ on $X^*$ c. At each split, select $\sqrt{p}$ (classification) or $p/3$ (regression) random features
2. Output:
   • Classification: $\hat{f}(x) = \text{majority vote}\{T_1(x), \ldots, T_B(x)\}$
   • Regression: $\hat{f}(x) = \frac{1}{B} \sum_{b=1}^{B} T_b(x)$

Two Sources of Randomness

Random Forest introduces two sources of randomness:

1. Bootstrap Aggregating (Bagging)

Each tree is trained on a bootstrap sample (sampling with replacement) of the original data. On average, each bootstrap sample contains about 63.2% of the original samples (since $1 - (1 - 1/n)^n \approx 0.632$).

Why bagging reduces variance:

For $B$ independent trees with variance $\sigma^2$:

where $\rho$ is the correlation between trees. As $B \to \infty$:

Bagging reduces the second term, but doesn't affect the first. To reduce $\rho$, we need feature sampling.

2. Feature Sampling (Random Subspace Method)

At each split, only consider a random subset of features. This decorrelates the trees because:

• Different trees will use different features for splits
• Important features won't dominate all trees
• The model becomes more robust to noisy features

Why feature sampling works:

• If one feature is very strong, all trees would use it, making them correlated
• By randomly excluding this feature, some trees must find alternative patterns
• This diversity improves the ensemble's generalization

Out-of-Bag (OOB) Error Estimation

Each bootstrap sample leaves out about 36.8% of the original data. These out-of-bag (OOB) samples can be used as a validation set:

where $\hat{f}_{-i}(x_i)$ is the prediction for sample $i$ using only trees that did not include $i$ in their bootstrap sample.

Advantages of OOB estimation:

• No need for a separate validation set
• Each sample is predicted by about 36.8% of the trees
• Provides an unbiased estimate of generalization error
• Computed during training (no additional cost)

Feature Importance in Random Forest

Mean Decrease in Impurity (MDI)

Aggregate impurity decrease across all trees:

Mean Decrease in Accuracy (Permutation Importance)

For each feature $j$:

1. Compute OOB accuracy $A_j$ with original feature values
2. Randomly permute feature $j$ across OOB samples
3. Compute OOB accuracy $A_j^{\text{perm}}$ with permuted values
4. Importance: $A_j - A_j^{\text{perm}}$

Permutation importance is more reliable because:

• Not biased toward high-cardinality features
• Captures feature interactions
• Accounts for feature correlation

Hyperparameters

Code Implementation

Explanation of Code

1. RF vs Single Tree: Shows how Random Forest reduces overfitting by comparing training-test accuracy gaps.

2. Number of Trees: Demonstrates diminishing returns as more trees are added.

3. OOB Error: Shows how OOB provides a free validation estimate during training.

4. Feature Importance: Compares impurity-based and permutation-based importance measures.

5. Feature Sampling: Shows how max_features affects performance and tree correlation.

6. Tree Correlation: Demonstrates that fewer features per split leads to less correlated trees.

Real-World Applications

Google: Search Ranking

Google uses Random Forest variants for:

• Query Understanding: Classifying search intent
• Spam Detection: Identifying low-quality web pages
• Feature Selection: Identifying important ranking signals

Apple: Siri Voice Recognition

Apple uses Random Forest for:

• Wake Word Detection: "Hey Siri" activation
• Intent Classification: Understanding user commands
• Device Recommendations: Personalized suggestions

Common Follow-Up Questions

Q1: Why does Random Forest use bootstrap sampling instead of using the full dataset for each tree?

Bootstrap sampling introduces diversity between trees. If all trees used the full dataset, they would be identical (for deterministic splitting criteria). Bootstrap ensures each tree sees slightly different data, creating diverse predictions.

Q2: What happens when max_features = 1?

Each split considers only one random feature. This maximizes decorrelation but may miss the best split. The model becomes a "random subspace" method. In practice, sqrt(p) works well for classification.

Q3: Can Random Forest handle missing values?

Standard scikit-learn Random Forest cannot. However, implementations like XGBoost and LightGBM handle missing values by learning the optimal direction (left or right) for missing values at each split.

Q4: How do you determine the optimal number of trees?

There's no overfitting with more trees (unlike boosting). Monitor OOB error or validation error and increase trees until it stabilizes. Typically, 100-500 trees suffice for most problems.

Company-Specific Tips

Google Interview Tips

• Discuss computational complexity: $O(B \cdot n \cdot p \cdot \log n)$ for training
• Be ready to explain why RF doesn't overfit with more trees
• Mention parallelization benefits (trees are independent)
• Talk about feature importance for model interpretability

Apple Interview Tips

• Focus on real-time inference requirements
• Discuss model compression techniques
• Be prepared to explain ensemble diversity
• Mention privacy considerations in federated learning

Related Topics

• Decision Trees Interview Guide
• Gradient Boosting Deep Dive
• Ensemble Methods Overview
• Feature Selection Techniques