Formal definition. Diversity among base learners is the property that different models make different errors on the same data. Without diversity, an ensemble degenerates into a single model repeated $L$ times — you gain nothing. Four practical strategies create diversity:

Formal definition. Let there be $L$ base classifiers. For a test instance $x$, each classifier $C_i$ produces a prediction $C_i(x)$. The ensemble prediction $C^{\ast }(x)$ is got by applying a combination function to the $L$ individual predictions: $$C^{\ast }(x)=\text{Combine}(C_1(x),C_2(x),\dots ,C_L(x))$$

Formal definition — two necessary conditions. An ensemble outperforms its individual members only when both conditions hold: 1. Base classifiers must be (about) independent. The output of one classifier must not determine the output of another. In practice, perfect independence is impossible, but decorrelation is the goal — we want errors to be uncorrelated so they cancel out rather than accumulate. 2. Every base classifier must be better than random guessing. Its error rate $E$ must satisfy $E<0.5$. Equivalently, accuracy > 50%.

Visual intuition. Consider a graph where the x-axis is the base classifier error rate $ϵ$ and the y-axis is the ensemble classifier error rate $e_{\text{ensemble}}$: - Diagonal line ($y=x$): The baseline — points where the ensemble performs exactly the same as a single model. If a single model has error 0.4 and the ensemble also has error 0.4, the point sits on the diagonal. This happens when base classifiers are perfectly correlated (identical). - Success zone (below the diagonal): The ensemble curve bends downward, away from the diagonal. When base error is 0.2, ensemble error may be near zero. When base error is 0.4, ensemble error might be about 0.15. The gap between the diagonal and the curve is the ensemble gain. This is where we want to operate — with $E<0.5$ and some diversity among classifiers. - Danger zone (above the diagonal, when $E>0.5$): The ensemble curve crosses above the diagonal. The ensemble error exceeds the base classifier error. Combining bad models makes the system worse, not better. Landmark: The curves cross the diagonal at exactly $E=0.5$. This is the tipping point — below 0.5, ensemble helps; above 0.5, ensemble hurts.

Purpose. Bagging reduces variance (overfitting) by training multiple models on different random subsets of the data and averaging their predictions. It is most effective with unstable base learners (like deep decision trees) whose predictions change significantly with small data perturbations. Inputs: Training data $D$ with $N$ observations; number of bootstrap samples $K$; a base learning algorithm (default: decision tree). Outputs: An ensemble of $K$ trained classifiers $C_1,\dots ,C_K$, plus a combination rule for final prediction.

Steps — the bagging procedure.

Let K = number of bootstrap samples (number of base learners)
For i = 1 to K:
    Create bootstrap sample D_i of size N from D
        (random sampling with replacement — same record can appear multiple times)
    Train base classifier C_i on D_i
End For

For a new instance x:
    Classification: C*(x) = argmax over classes y of Σ δ(C_i(x) = y)
        where δ outputs 1 if C_i predicts class y, 0 otherwise.
    Regression:     ŷ = (1/K) Σ_{i=1}^{K} ŷ_i

Formal explanation — bias-variance decomposition. Bagging reduces variance, not bias. The expected prediction error of any model decomposes as: $$\text{Error}={\text{Bias}}^2+\text{Variance}+\text{Noise}$$ Bagging attacks the variance term: by averaging across bootstrap samples, the random fluctuations of individual models cancel out. The bias (systematic error from model assumptions) remains unchanged. If a base classifier is stable — meaning its predictions do not change much with minor perturbations in the training set — then bagging may not significantly improve performance. The ensemble's error is primarily caused by bias in the base learner, and bagging reduces variance, not bias. Examples of stable classifiers: linear regression, KNN with large $K$. If a base classifier is unstable — meaning small changes in training data cause large changes in predictions (e.g., deep unpruned decision trees) — then the classifier has high variance. Bagging helps by averaging out the variance across different samples. This is why decision trees are the most common base learner for bagging.

Purpose. Random forest extends bagging by adding feature randomization, producing a more diverse set of decision trees. The double randomization (rows + columns) decorrelates the trees more aggressively than bagging alone, typically yielding better generalization. Inputs: Training data $D$ with $N$ observations and $d$ features; number of trees $T$; number of features to sample per split $p$ (default: $\sqrt{d}$ for classification, $d/3$ for regression). Outputs: A forest of $T$ unpruned decision trees, plus feature importance scores.

Steps — the random forest procedure. 1. For each tree $t=1,\dots ,T$: - Create a bootstrap sample $D_t$ of size $N$ from $D$ (sampling with replacement). 2. Grow each tree by recursively repeating at every node: - Randomly sample $p$ attributes from the total $d$ features. - Compute the best split (via information gain, Gini impurity, or entropy) using only those $p$ features. - Split the node on the best feature and threshold among the $p$. - Do NOT prune — let the tree grow until all leaves are pure (or until min_samples_split is reached). 3. For prediction on a new instance $x$: - Classification: majority vote across all $T$ trees. - Regression: average of all $T$ tree predictions.

from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_iris

iris = load_iris()
X, y = iris.data, iris.target

rf = RandomForestClassifier(
    n_estimators=500,      # 500 trees in the forest
    n_jobs=-1              # use all CPU cores for parallel training
)
rf.fit(X, y)

Purpose. AdaBoost (Adaptive Boosting) is the foundational boosting algorithm. It sequentially trains weak classifiers (typically shallow decision trees), reweighting training examples after each round so that misclassified examples get higher weight. The final prediction is a weighted majority vote where more accurate classifiers get larger voting weights. Inputs: Training data with $N$ samples $(x_j,y_j)$ where $y_j\in \{-1,+1\}$; number of boosting rounds $T$; a base learning algorithm (typically decision stump or shallow tree). Outputs: A sequence of $T$ classifiers $C_1,\dots ,C_T$ with associated importance weights ${\alpha }_1,\dots ,{\alpha }_T$, and a combination rule for final prediction.

Steps — the AdaBoost algorithm (professor's formulation). Let there be $N$ training samples and $T$ base classifiers $C_1,C_2,\dots ,C_T$. Step 1 — Initialize weights: All $N$ records start with equal weight: $$w_j=\frac{1}{N},j=1,2,\dots ,N$$ Step 2 — For each classifier $i=1$ to $T$: (a) Train classifier $C_i$ on the weighted training data (some versions use the full dataset; some versions use a bootstrap sample weighted by $w_j$). (b) Compute the error rate $E_i$: $$E_i=\frac{1}{N}\sum _{j=1}^N{w}_j\cdot \delta \left(C_i(x_j)\ne y_j\right)$$ where $\delta (\cdot )$ is the indicator function: outputs 1 if the condition is true (misclassification), 0 otherwise. The professor calls this "the weighted average of the mistakes." (c) Compute the classifier importance ${\alpha }_i$: $${\alpha }_i=\frac{1}{2}\ln \left(\frac{1-E_i}{E_i}\right)$$ ${\alpha }_i$ determines how much "voice" classifier $C_i$ has in the final ensemble: - Low $E_i$ (accurate) → ${\alpha }_i$ large → high importance. - $E_i=0.5$ (random) → ${\alpha }_i=0$ → no contribution. - $E_i>0.5$ (worse than random) → ${\alpha }_i$ negative → the algorithm resets all weights to $1/N$ and restarts. (d) Update the weights for the next round: For each record $j$: - If $C_i$ classified it correctly: $$w_j^{\text{new}}=w_j^{\text{old}}\times e^{-{\alpha }_i}$$ - If $C_i$ classified it incorrectly: $$w_j^{\text{new}}=w_j^{\text{old}}\times e^{{\alpha }_i}$$ Since ${\alpha }_i>0$ for a useful classifier, $e^{-{\alpha }_i}<1$ (weight shrinks) and $e^{{\alpha }_i}>1$ (weight grows). Misclassified records become heavier; correctly classified records become lighter. (e) Normalize the weights: $$w_j^{\text{normalized}}=\frac{w_j^{\text{new}}}{{\sum }_{k=1}^N{w}_k^{\text{new}}}$$ The normalization factor $Z={\sum }_{k=1}^N{w}_k^{\text{new}}$ ensures the weights sum to 1 for the next round. Step 3 — Final prediction: For a new instance $x$: $$H(x)=\text{sign}\left(\sum _{i=1}^T{\alpha }_i\cdot C_i(x)\right)$$ Multiply each classifier's prediction $C_i(x)\in \{-1,+1\}$ by its importance ${\alpha }_i$, sum them, and take the sign.

14.4.3 Full Worked Example — AdaBoost with 10 Data Points

14.4.4 Weight Dynamics — Visual Interpretation

Look at how weights change across rounds for representative records:

Record	Round 1 Weight	Round 2 Weight	Round 3 Weight	Interpretation
Easy (e.g., 0.9)	0.10 → 0.010	→ 0.005	→ 0.002	Correctly classified every round. Weight steadily decreases.
Hard type A (e.g., 0.1)	0.10 → 0.311	→ 0.019	→ 0.010	Misclassified R1, then corrected R2–R3. Weight spiked then fell.
Hard type B (e.g., 0.5)	0.10 → 0.010	→ 0.155	→ 0.350	Correct R1, then misclassified R2–R3. Weight keeps increasing.

A record whose weight keeps increasing is hard to classify — multiple models struggle with it. If the weight keeps increasing even after many rounds, the record may be an outlier or the data may be noisy. This is one failure mode of boosting (see Section 14.4.5).

14.4.5 When Boosting Fails

14.4.6 AdaBoost Properties

14.4.7 Code Example — Ensemble Methods Comparison

14.4.8 Student Q&A on AdaBoost

Real-world & domain connection. AdaBoost was invented by Freund and Schapire in 1996 and won the Gödel Prize in 2003 — one of the rare ML algorithms recognized with a major theoretical computer science award. In practice, AdaBoost has been largely superseded by gradient boosting (XGBoost, LightGBM, CatBoost) which offer better handling of arbitrary loss functions, built-in regularization, and faster training. However, AdaBoost remains the clearest introduction to the boosting concept. It is still used in face detection (the Viola-Jones face detector uses AdaBoost with Haar-like features) and in domains where interpretability of the sequential weighting is valued.

---

Comparison — when to pick which.

Dimension	Bagging	Random Forest	Boosting (AdaBoost)
Core idea	Average over random data subsets	Bagging + random feature subsets	Sequentially focus on hard examples
Row randomization	Yes (bootstrap)	Yes (bootstrap)	Optional (version-dependent)
Feature randomization	No	Yes (at every split)	No
Training	Parallel	Parallel	Sequential
Base learners	Any model	Decision trees only	Usually decision trees (shallow)
Variance reduction	High	Very high	Moderate (can increase variance if overfit)
Bias reduction	None	None	Yes — sequential correction reduces bias
Overfitting risk	Low	Low	Moderate–High (sensitive to noisy data)
Best for	High-variance base models	Tabular data with many features	Clean data where base models are weak
Interpretability	Low	Medium (feature importance)	Low

Practical guidance — selecting hyperparameters. In Python (scikit-learn), the key parameter for the number of base learners is n_estimators. Typical starting values:

Method	Typical n_estimators range	Notes
Bagging	50–200	Fewer needed if base model is strong
Random Forest	100–500	More trees = smoother decision boundary
AdaBoost	50–200	Stop when validation error plateaus
Gradient Boosting	100–1000	Need more than AdaBoost due to learning rate scaling