Random Forests Ensemble Trees Variance Reduction
# Random Forests: Ensemble Trees & Variance Reduction
## Introduction & Motivation
Random forests aggregate predictions from many trees trained on random subsets of data/features, reducing overfitting via bagging and feature randomness. Each tree independent; predictions averaged (regression) or majority-voted (classification). State-of-the-art for tabular data; scales to large datasets; naturally parallelizable.
Motivation: Single decision tree overfits; ensemble reduces variance. Random subsampling (bootstrap) and feature subsampling decorrelate trees, improving ensemble diversity. Fast inference—each tree independent.
Applications: Feature ranking, missing value imputation, anomaly detection, Kaggle competitions.
---
## Core Concepts & Theory
### Bootstrap Aggregating (Bagging)
Train each tree on bootstrap sample (n samples with replacement). Reduces variance:
$$ ext{Var}[ ext{ensemble}] = \frac{
ho \sigma^2 + (1-
ho)\sigma^2/m}{1}$$
where
ho is correlation, m is number of trees.
### Feature Randomness
At each split, select from random feature subset (sqrt(d) for classification, d/3 for regression). Decorrelates trees.
---
## Mathematical Formulation
Bagging prediction (regression):
$$\hat{y} = \frac{1}{m}\sum_{i=1}^{m} T_i(\mathbf{x})$$
where T_i is tree i.
Majority voting (classification):
$$\hat{y} = \arg\max_c \sum_{i=1}^{m} \mathbb{1}[T_i(\mathbf{x}) = c]$$
---
## Advanced Theory & Extensions
### Out-of-Bag (OOB) Error
Each bootstrap sample excludes ~36.8% of data (OOB set). Estimate validation error without separate test set.
### Feature Importance (MDI)
Mean Decrease Impurity: importance = sum of gain across all splits using feature, weighted by sample count at each split.
---
## Computational Considerations
Training: O(m imes n \log n) for m trees, n samples (parallelizable).
Inference: O(m imes ext{tree depth}) ≈ O(m \log n).
Memory: O(m imes ext{tree size}).
---
## Practical Implementation Strategies
### Hyperparameter Tuning
n_estimators: More trees → better (diminishing returns ~100-500).
max_depth: Limit depth; typically ~10-20.
max_features: Feature subset size; default sqrt(d) or d/3.
min_samples_leaf: Minimum samples in leaf; increase for robustness.
---
## Benchmark Datasets & Evaluation
Classification: Breast Cancer, Iris. Metric: Accuracy, AUC.
Regression: Boston Housing, California. Metric: RMSE, R².
---
## Key Challenges & Limitations
### Feature Importance Bias
MDI biased toward high-cardinality features. Use permutation importance for stability.
### Model Size
Many trees require substantial memory; pruning or quantization for deployment.
---
## Hyperparameter Tuning
Grid search: n_estimators \in {50, 100, 200\}, max_depth \in {5, 10, 15\}, max_features \in {sqrt, log2\}.
---
## Real-World Applications & Case Studies
Finance: Credit risk scoring; feature importance guides underwriting.
Healthcare: Patient stratification; OOB error for validation.
---
## Integration with Other Methods
RF + Recursive Feature Elimination → Reduced feature set, faster inference.
---
## Future Research Directions
Extremely randomized trees (extra randomness); infinite forests (online learning).
---
## Summary & Key Takeaways
Random forests reduce tree overfitting via bootstrap sampling and feature randomness, achieving strong performance on tabular data.
Principles:
1. Bagging reduces variance via independent trees.
2. Feature randomness decorrelates trees.
3. OOB error estimates validation without separate set.
4. Feature importance ranks predictive contribution.
5. Ensemble reduces bias-variance tradeoff.
---
---
## Appendix: Practical Labs
### Lab 1: Random Forest Basics
from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
rf = RandomForestClassifier(n_estimators=100, max_depth=10, random_state=42)
rf.fit(X_train, y_train)
y_pred = rf.predict(X_test)
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy:.4f}")
assert accuracy > 0.8, "Should be high"
assert len(rf.estimators_) == 100, "Should have 100 trees"
print("✓ Random Forest working")
if __name__ == "__main__":
print("Lab 1: Random Forest - PASSED")### Lab 2: OOB Error Estimation
from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
rf = RandomForestClassifier(n_estimators=100, oob_score=True, random_state=42)
rf.fit(X_train, y_train)
oob_score = rf.oob_score_
test_score = accuracy_score(y_test, rf.predict(X_test))
print(f"OOB score: {oob_score:.4f}, Test score: {test_score:.4f}")
assert 0.7 < oob_score < 1.0, "OOB should be reasonable"
print("✓ OOB error working")
if __name__ == "__main__":
print("Lab 2: OOB Error - PASSED")### Lab 3: Feature Importance
import numpy as np
from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_iris
iris = load_iris()
X, y = iris.data, iris.target
rf = RandomForestClassifier(n_estimators=100, random_state=42)
rf.fit(X, y)
importances = rf.feature_importances_
indices = np.argsort(importances)[::-1]
print("Feature importance ranking:")
for i in range(min(4, len(importances))):
print(f"{iris.feature_names[indices[i]]}: {importances[indices[i]]:.4f}")
assert len(importances) == 4, "Should have 4 features"
assert abs(np.sum(importances) - 1.0) < 1e-6, "Should sum to 1"
print("✓ Feature importance working")
if __name__ == "__main__":
print("Lab 3: Feature Importance - PASSED")### Lab 4: Ensemble Size Effect
import numpy as np
from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
n_trees = [10, 50, 100, 200, 500]
accuracies = []
for n in n_trees:
rf = RandomForestClassifier(n_estimators=n, random_state=42)
rf.fit(X_train, y_train)
acc = accuracy_score(y_test, rf.predict(X_test))
accuracies.append(acc)
print(f"n_trees={n}: {acc:.4f}")
# More trees should not decrease performance
assert accuracies[-1] >= accuracies[0], "More trees should maintain/improve"
print("✓ Ensemble size effect working")
if __name__ == "__main__":
print("Lab 4: Ensemble Size - PASSED")