5.2 Non-parametric Models

Introduction

Non-parametric models do not assume a fixed form for the underlying function. Instead, their complexity grows with the amount of training data. These models make fewer assumptions about the data distribution and can adapt to complex patterns.

Key Characteristics

Flexible Structure: Model complexity increases with data size
Few Assumptions: No predetermined functional form
Data-Driven: Rely on the training data directly for predictions
Local Learning: Make predictions based on nearby training examples

Mathematical Foundation

Unlike parametric models with fixed $ \theta \in \mathbb{R}^d $, non-parametric models maintain the entire training dataset $ \mathcal{D} = \{(x_1, y_1), \ldots, (x_n, y_n)\} $ and define: $$f(x) = g(x, \mathcal{D})$$ where $ g $ is a function that uses the training data directly.

K-Nearest Neighbors (k-NN)

The k-NN algorithm predicts based on the $ k $ closest training examples: $$\hat{y} = \frac{1}{k}\sum_{i \in \mathcal{N}_k(x)} y_i$$ where $ \mathcal{N}_k(x) $ are the $ k $ nearest neighbors of $ x $ under some distance metric (typically Euclidean: $ d(x, x') = \|x - x'\|_2 $).

Interactive: k-NN Classification

Adjust $ k $ and see how the decision boundary changes:

Number of Neighbors (k): {{k}}

Training Points: Blue (Class 0), Red (Class 1)

Background: Shows predicted class for each region

Notice: As k increases, decision boundary becomes smoother (less overfitting)

Comparison: Parametric vs Non-parametric

Interactive Comparison

Compare how both model types fit the same data:

Data Complexity: k-NN k value: {{compareK}}

Parametric (Linear)

Non-parametric (k-NN)

Parametric MSE: {{parametricMse | number:3}}

Non-parametric MSE: {{nonparametricMse | number:3}}

Decision Trees: Hierarchical Non-parametric Models

Decision trees partition the input space recursively. At each node, they split based on a feature: $$\text{Split}(S, f, t) = \{x \in S : x_f \leq t\} \cup \{x \in S : x_f > t\}$$ The split is chosen to maximize information gain or minimize impurity (Gini or entropy).

Gini Impurity

$$\text{Gini}(S) = 1 - \sum_{c=1}^{C} p_c^2$$ where $ p_c $ is the proportion of class $ c $ in set $ S $.

Interactive: Decision Tree Splits

See how the tree partitions the space:

Max Depth: {{maxDepth}}

Splits: Each vertical/horizontal line represents a decision boundary

Depth {{maxDepth}}: {{Math.pow(2, maxDepth)}} maximum leaf nodes

Kernel Methods

Kernel methods generalize similarity between points. The kernel function $ K(x, x') $ measures similarity: $$K(x, x') = \phi(x)^T \phi(x')$$ where $ \phi $ maps data to a higher-dimensional space. Common kernels:

Linear: $ K(x, x') = x^T x' $
Polynomial: $ K(x, x') = (x^T x' + c)^d $
RBF (Gaussian): $ K(x, x') = \exp(-\gamma \|x - x'\|^2) $

Interactive: Kernel Density Estimation

Visualize how bandwidth affects density estimation:

Bandwidth (h): {{bandwidth}}

Formula: $ \hat{f}(x) = \frac{1}{nh}\sum_{i=1}^{n} K\left(\frac{x - x_i}{h}\right) $

where $ K $ is the kernel function and $ h $ is the bandwidth

Advantages and Limitations

Aspect	Parametric	Non-parametric
Flexibility	Low (fixed form)	High (adapts to data)
Training Time	Fast	Very fast (just store data)
Prediction Time	Very fast O(1)	Slow O(n) or O(n log n)
Memory	Low (just parameters)	High (store all data)
Interpretability	High	Medium (trees) to Low (k-NN)
Overfitting Risk	Low (strong assumptions)	High (if not regularized)

Why LLMs Use Parametric Models

Large language models overwhelmingly use parametric (neural network) architectures because:

Scalability: Training data contains trillions of tokens; storing all would be infeasible
Generalization: Parameters compress patterns, enabling generation of novel text
Inference Speed: O(1) prediction time crucial for real-time applications
Transfer Learning: Pre-trained parameters can be reused and fine-tuned

Sample Data Summary

Model Type	Parameters Stored	Prediction Formula
Linear Regression	$ \theta \in \mathbb{R}^d $	$ \hat{y} = \theta^T x $
k-NN	$ \{(x_i, y_i)\}_{i=1}^n $	$ \hat{y} = \frac{1}{k}\sum_{i \in \mathcal{N}_k(x)} y_i $
Decision Tree	Tree structure	Follow splits to leaf
Neural Network	$ W, b $ (matrices, vectors)	$ \hat{y} = f_\theta(x) $

Model Type	Parameters Stored	Prediction Formula
Linear Regression	\( \theta \in \mathbb{R}^d \)	\( \hat{y} = \theta^T x \)
k-NN	\( \{(x_i, y_i)\}_{i=1}^n \)	\( \hat{y} = \frac{1}{k}\sum_{i \in \mathcal{N}_k(x)} y_i \)
Decision Tree	Tree structure	Follow splits to leaf
Neural Network	\( W, b \) (matrices, vectors)	\( \hat{y} = f_\theta(x) \)