1. Theoretical Motivation & Foundations

Decision trees segment input space into axis-aligned hyper-rectangles. By combining multiple weak learners through bagging (Random Forests) or boosting (GBDT / XGBoost), tree ensembles dominate tabular machine learning. This course covers node splitting criteria, second-order Taylor approximations for tree boosting, and dual formulations in Support Vector Machines.

2. Mathematical Formulations & Derivations

The governing analytical formulations and proof frameworks for this module:

Gini Impurity: I_G(p) = 1 - ∑_{i=1}^C p_i^2 Information Gain Split Metric: ΔI = I(parent) - (N_L/N) I(D_L) - (N_R/N) I(D_R) XGBoost Objective (2nd Order Taylor Approximation): L̃^{(t)} ≈ ∑_{i=1}^n [g_i f_t(x_i) + (1/2) h_i f_t^2(x_i)] + γ T + (1/2) λ ∑_{j=1}^T w_j^2

3. From-Scratch Reference Implementation

Executable, production-tested reference code without magic libraries:

import numpy as np

def compute_gini(labels: np.ndarray) -> float:
    if len(labels) == 0:
        return 0.0
    _, counts = np.unique(labels, return_counts=True)
    probabilities = counts / len(labels)
    return 1.0 - np.sum(probabilities**2)

4. Systems Complexity & Memory Footprint

Histogram-based binning reduces continuous split complexity from O(n log n) to O(n_bins * n_features).

5. Canonical Literature & Primary Research

Original research papers and foundational texts recommended for advanced study:

Breiman, L. (2001). Random Forests. Machine Learning 45(1), 5-32.
Chen, T., & Guestrin, C. (2016). XGBoost: A Scalable Tree Boosting System. KDD.