Section 3 of 5 · Classical Machine Learning

Trees, Ensembles, Neighbors & Kernels

These families encode different geometries and costs. The goal is to choose among them from evidence and constraints instead of defaulting to whichever library wins one score.

8 units 17 topics 0/8

Units

8 in this section

3.1 CART: split objectives, impurity, stopping and pruning
derive · implement
5 h
3.2 Bagging, random forests and out-of-bag estimates
explain · measure
3 h
3.3 AdaBoost and gradient boosting
derive · implement
5 h
3.4 XGBoost, LightGBM and CatBoost configuration
explain
2 h
3.5 k-nearest neighbors, search cost and the curse of dimensionality
implement · measure
3 h
3.6 Support vector machines: margins, hinge loss and slack
derive
4 h
3.7 Kernels, bandwidth and kernel matrix cost
derive · measure
3 h
3.8 Feature importance caveats and class weighting effects
explain · measure
3 h

Before moving on

Checkpoint

Implement a tested tree core plus one neighbor or kernel mechanism, then defend a family choice using geometry, uncertainty, interpretability, fit cost and prediction cost.

Deliberately out of scope

Leave for later

Distributed and histogram-based boosting internals
Large-scale approximate nearest-neighbor systems
SHAP, LIME and advanced kernel proofs

Resources for this section

Shared by every unit above

Hands-On Machine Learning with Scikit-Learn and PyTorch - nonlinear classical models
Aurelien Geron (O'Reilly, 2025)implementation

primary

Read Chapters 3, 5 and 6 and the online Appendix C notebook as the first pass through performance measures, trees, ensembles and SVMs, running notebooks 03, 05 and 06 alongside. Vary depth, estimators, learning rate, k, C and RBF width under fixed splits.
scikit-learn - neighbors, SVMs, trees and ensembles
scikit-learnreference

reference

Check official estimator constraints, complexity, preprocessing needs, missing-value behavior and probability caveats. Do not use library calls as the mechanism implementation.
ISLP - tree-based methods and support vector machines
James, Witten, Hastie, Tibshirani and Taylortheory

required

Use Chapters 8 and 9 with their Python labs for the statistical account of trees, bagging, random forests, boosting and SVMs that the notebooks leave implicit, and for model-choice and feature-importance arguments.
Deep-ML - tree, ensemble and kernel problems
Deep-MLpractice

support

Use 138 Best Gini-Based Split, 20 Decision Tree Learning, 307 Bagging Classifier, 21 Pegasos Kernel SVM and 280 RBF Kernel as unit checks after the local implementation passes. Their tests were read in review; each card states what they pin, including tie and update-order conventions.
Probabilistic Machine Learning, Chapter 16: exemplar-based methods
Kevin Murphytheory

support

Read Sections 16.1 to 16.1.3 for the KNN decision rule, the curse of dimensionality with the growing-hypercube example, and the speed section on k-d trees, hashing and approximate search.
XGBoost parameters and sklearn estimator interface
XGBoost developersreference

reference

Read the tree-booster parameter list for eta, depth, sampling and regularization names and defaults, and the sklearn page for early stopping with eval_set.
LightGBM parameters
LightGBM developersreference

reference

Read learning_rate, num_leaves, max_depth, min_data_in_leaf, feature_fraction, bagging_fraction with bagging_freq, lambda_l2 and early stopping defaults.
CatBoost common parameters and categorical features
CatBoost developersreference

reference

Read iterations, learning_rate, l2_leaf_reg, depth, grow_policy, subsample, rsm, boosting_type, use_best_model and one_hot_max_size defaults, plus native categorical handling.

Apply the section

Mini-project · Tree core, one neighbor or kernel mechanism, and a family-choice defense (12 to 16 h)

Implement a deterministic CART core with one ensemble and one neighbor or kernel mechanism in NumPy in your own repository, test them against hand cases and scikit-learn, configure the boosting libraries on one fixed split, and defend a family choice from geometry, uncertainty, interpretability, fit cost and prediction cost.

Steps

Build the CART core: Gini and entropy impurity, an exhaustive split scan with a stated threshold and tie rule, growth limits (max_depth, min_samples_leaf) and prediction. Match hand cases, then DecisionTreeClassifier predictions on tie-free data with matching limits.
Prune by cost complexity: take the \(\alpha\) path and choose \(\alpha\) by cross-validation on the training split only.
Add bagging or a random forest over your core. Show validation error and its spread over seeds against the number of trees, next to a single tree.
Add one neighbor or kernel mechanism: kNN with a stated tie rule and a scaled-versus-unscaled test, a Pegasos kernel SVM, or an RBF kernel matrix with a positive semidefinite check. Compare predictions with KNeighborsClassifier or SVC on a fixed split.
On one fixed tabular split, configure HistGradientBoosting and XGBoost, LightGBM and CatBoost from their parameter pages with early stopping on a validation split. State each library's categorical handling and record the best iteration, validation score, fit time and predict time.
Add a random high-cardinality column and compare impurity (MDI) importance with permutation importance on held-out data.
Defend a family choice: compare a tree, an ensemble, a boosting model, kNN and an SVM on the same split with paired uncertainty on the validation metric, plus calibration, interpretability, fit cost and prediction cost. Name the condition that would reverse the choice.

Deliverables

The tree package: impurity, split search, growth limits, pruning and the ensemble, with tests.
The neighbor or kernel mechanism with its differential tests.
The family-choice dossier: one comparison table with paired uncertainty and costs, the boosting-library runs, the importance comparison, the decision and its tripwire.

Checks

external-tests · Deep-ML 138, 20, 307, 21 and 280
rubric · Self-grade with the rubric below

Rubric

Criterion	Pass	Strong
Tree core correctness	Impurity and split search match hand cases, and predictions match scikit-learn on tie-free data.	Property tests cover ties under a documented rule, and depth and leaf limits reproduce scikit-learn's node counts.
Ensemble	The ensemble lowers validation error or its spread over seeds compared with one tree.	An out-of-bag estimate tracks a held-out estimate, and the report explains any gap.
Neighbor or kernel mechanism	Predictions match scikit-learn on a fixed split.	Tests cover feature scaling and a tie or degenerate-kernel case.
Boosting configuration	HistGradientBoosting and at least one of XGBoost, LightGBM or CatBoost run with early stopping and stated categorical handling.	All three external libraries run, and the report explains the learning-rate and iteration tradeoff from the recorded best iterations.
Family-choice defense	One table reports the metric with paired uncertainty, fit time and predict time for each family.	The choice survives a small change in the best score, and the report names the condition that would reverse it.

Feeds into: Milestone artifact 2, the mechanisms suite: the deterministic tree core, the ensemble and the kNN or kernel model come from here. The family-choice comparison feeds the decision dossier.