Non-Parametric Models

Overview

This block begins the competition-centered portion of MA289. We move from models with fixed functional forms to flexible models that adapt directly to the structure of the data.

The central mathematical examples are decision trees and Support Vector Machines. Decision trees recursively partition feature space, while SVMs construct separating boundaries using margin-based optimization.

Topics Covered

Regression and classification trees
Recursive binary splitting
RSS, Gini impurity, entropy, and information gain
Tree depth, stopping rules, and pruning
Bias-variance tradeoff in tree models
Bagging and out-of-bag error
Random forests
Boosting and gradient-boosted trees
Support Vector Machines
Feature scaling, kernels, C, and gamma
Local validation versus Kaggle leaderboard performance

Kaggle Competitions in this Block

Competition	Dates	Prediction Task	Primary Methods	Link
Competition 1: Tree Method Housing Data	Launch: 01 Sep 2026 Due: 22 Sep 2026 NLT 2359	Ames Housing regression: predict `SalePrice` from residential housing features.	Decision trees, pruning, bagging, random forests, gradient boosting, cross-validation, and OOB error.	Open Ames Housing Competition
Competition 2: Spoken Digit Data	Launch: 29 Sep 2026 Due: 16 Oct 2026 NLT 2359	Binary spoken-digit classification: distinguish spoken sixes from sevens using spectrogram-based image data.	SVM, scaling, linear and RBF kernels, feature extraction, cross-validation, and probability-based submissions.	Open Spoken Digit Competition

Core Mathematical Relationships

Regression Trees

If a node contains observations S, the leaf prediction is the mean response

c(S) = (1 / |S|) Σ y_i.

For feature j and split point s, define

S_L(j,s) = {i ∈ S : x_ij < s}

and

S_R(j,s) = {i ∈ S : x_ij ≥ s}.

The best split minimizes

RSS(S_L) + RSS(S_R).

Classification Trees

For estimated class proportions p_k within a node, common impurity measures include

Gini = Σ p_k(1 - p_k)

and

Entropy = -Σ p_k log(p_k).

The tree selects the split producing the greatest reduction in node impurity.

Bagging

Fit B trees to B bootstrap samples and average:

f_bag(x) = (1/B) Σ f^*b(x).

Averaging reduces the variance of unstable learners such as deep decision trees.

Approximately 37% of the original training observations are left out of an individual bootstrap sample. These out-of-bag observations can be used to estimate generalization error.

Support Vector Machines

For binary labels y_i ∈ {-1,1}, a separating hyperplane has the form

β₀ + β^Tx = 0.

The maximal-margin classifier chooses the separating hyperplane that maximizes the minimum distance between the decision boundary and the training observations.

Soft-margin SVMs allow margin violations and use the parameter C to control the tradeoff between a wider margin and fitting the training observations more tightly.

Key Topics, Lesson Objectives, Readings, and Competition Work

Date	Key Topics	Lesson Objectives	Readings	Competition Work
01 Sep 2026	Decision Trees 1 Recursive Partitioning	Understand decision trees as recursive functions. Derive regression-tree splitting using RSS. Extend the splitting idea to classification using Gini impurity and entropy. Connect tree depth and model flexibility to the bias-variance tradeoff. Lesson notes: Decision Trees via Recursive Formulas .	ISLP Chapter 8: Tree-Based Methods §8.1 The Basics of Decision Trees §8.1.1 Regression Trees §8.1.2 Classification Trees Approximately pp. 331-340 Géron Chapter 6: Decision Trees Training and Visualizing a Decision Tree Making Predictions Estimating Class Probabilities The CART Training Algorithm Gini Impurity or Entropy? Regression Trees	Competition 1 Launch: Ames Housing. Kaggle: Tree Method Housing Data Competition Launch: 01 Sep 2026 Due: 22 Sep 2026 NLT 2359 Prediction goal: estimate `SalePrice` for homes in Ames, Iowa. Inspect the data, create a local validation split, train a decision-tree baseline, generate a valid submission, and record the initial Kaggle score.
08 Sep 2026	Decision Trees 2 Pruning, Bagging & OOB Error	Understand why deep trees generally have high variance. Understand cost-complexity pruning. Derive variance reduction through averaging. Understand bootstrap samples and out-of-bag observations. Lesson notes: Decision Trees, Bagging, Entropy & OOB Error .	ISLP Chapter 8 §8.1.1 Tree Pruning §8.1.3 Trees Versus Linear Models §8.1.4 Advantages and Disadvantages of Trees §8.2.1 Bagging Approximately pp. 335-345 Géron Chapter 6: Decision Trees Regularization Hyperparameters Decision Trees Have a High Variance Chapter 7: Ensemble Learning and Random Forests Bagging and Pasting Out-of-Bag Evaluation	Competition 1: Ames Housing Compare tree depth, minimum leaf size, and pruning. Compare training and validation performance. Add bagging and use OOB error when appropriate. Continue recording local validation and Kaggle results.
15 Sep 2026	Random Forests & Boosting	Understand why decorrelating trees can improve bagging. Compare random forests and boosted trees. Understand sequential versus parallel ensemble construction. Connect ensemble hyperparameters to bias and variance. Related lesson notes: Bagging, Variance Reduction & OOB Error .	ISLP Chapter 8 §8.2.2 Random Forests §8.2.3 Boosting §8.2.5 Summary of Tree Ensemble Methods Optional Python Lab: §8.3.3 Bagging and Random Forests §8.3.4 Boosting Géron Chapter 7: Ensemble Learning and Random Forests Random Forests Extra-Trees Feature Importance AdaBoost Gradient Boosting Histogram-Based Gradient Boosting Stacking	Competition 1: Ames Housing Compare the single-tree baseline with Random Forest and Gradient Boosting models. Tune important hyperparameters with cross-validation. Maintain an experiment log containing model, preprocessing, hyperparameters, validation score, and Kaggle score.
22 Sep 2026	Competition 1 Review Validation & Generalization	Compare modeling strategies. Diagnose differences between local validation and leaderboard performance. Identify overfitting, leakage, and useful feature engineering. Explain why the final model improved over the baseline. Related validation notes: Resampling, Cross-Validation & Bootstrapping .	ISLP Chapter 5: Resampling Methods §5.1 Cross-Validation §5.2 The Bootstrap Géron Chapter 2: End-to-End Machine Learning Project Select and Train a Model Better Evaluation Using Cross-Validation Fine-Tune Your Model Grid Search Randomized Search Analyze the Best Models and Their Errors	Competition 1 Due: 22 Sep 2026 NLT 2359 Submit to the Ames Housing Competition Finalize the Kaggle submission and course repository. Compare the final model against the original decision-tree baseline and summarize the strongest evidence that the improvement generalizes.
29 Sep 2026	Support Vector Machines Spoken Digit Classification	Understand separating hyperplanes. Understand the maximal-margin classifier. Understand soft-margin classification. Understand kernels. Interpret the effect of C and gamma. Understand why scaling and feature representation matter for SVM classification. Lesson notes: Support Vector Machines \| Hyperplanes & Maximal Margin Classifier .	ISLP Chapter 9: Support Vector Machines §9.1 Maximal Margin Classifier §9.2 Support Vector Classifiers §9.3 Support Vector Machines Approximately pp. 367-382 Géron Chapter 5: Support Vector Machines Linear SVM Classification Soft Margin Classification Nonlinear SVM Classification Polynomial Kernel Gaussian RBF Kernel Under the Hood: Decision Functions, Dual Problem, and Kernels	Competition 2 Launch: Spoken Digit Data Competition. Kaggle: Spoken Digit Data Competition Launch: 29 Sep 2026 Due: 16 Oct 2026 NLT 2359 Prediction goal: distinguish spoken sixes from sevens using spectrogram-based image data. Begin with a scaled SVM baseline. Compare linear and RBF approaches and tune `C` and `gamma` using cross-validation. Feature-extraction approaches such as image profiles or Histogram of Oriented Gradients (HOG) may be used to convert spectrogram structure into SVM predictors.

Resources

ISLP Chapter 5: Resampling Methods
ISLP Chapter 8: Tree-Based Methods
ISLP Chapter 9: Support Vector Machines
Géron Chapter 2: End-to-End Machine Learning Project
Géron Chapter 5: Support Vector Machines
Géron Chapter 6: Decision Trees
Géron Chapter 7: Ensemble Learning and Random Forests
Kaggle Competition 1: Ames Housing
Kaggle Competition 2: Spoken Digit Data
Kaggle Competitions & Student Work