Instance-Based vs Model-Based Learning

After training, does the algorithm throw the data away or keep it? That single question separates the two fundamental strategies in ML. Getting the answer wrong means deploying a model that's either too slow to serve predictions or too rigid to capture the real pattern in the data.

What "Learning" Means Here

Mitchell's definition: a program is said to learn from experience E with respect to task T and performance measure P, if its performance at T, as measured by P, improves with experience E. For house price prediction: E = 6 training examples, T = predict price, P = MSE.

The key question isn't whether it learns — it's what it keeps from that experience. Does it compress the data into a compact model, or does it keep the raw examples?

Anchor dataset:

X = [650, 850, 1100, 1400, 1600, 1900]  # sq_ft
y = [180, 220, 280,  340,  370,  430]   # price in $k
# Query: predict price for sq_ft = 1000

Model-Based Learning

Model-based (eager) learning fits a parametric function to the training data and extracts a compact summary: the parameters. Once training ends, the training data can be discarded.

Linear regression on our 6-point anchor yields $w_0=53.33$, $w_1=0.20$. At inference:

$\hat{y}(1000)=53.33+0.20\times 1000=\$253.3k$

The six training rows are gone. Only two numbers remain — $w_0$ and $w_1$. For a second query:

$\hat{y}(800)=53.33+0.20\times 800=\$213.3k$

Inference time is $O(p)$ — a single dot product. Memory is $O(p)$ — just the weight vector. For $p=1000$ features, that's 1000 numbers regardless of whether the training set had 100 or 100 million samples.

Algorithms in this class: Linear Regression, Logistic Regression, SVM, Neural Networks, Naive Bayes, Decision Trees (once built).

Instance-Based Learning (Lazy Learning)

Instance-based (lazy) learning memorizes the entire training set. There is no fitting phase — the "training" step is just storing the data. All computation is deferred to inference.

KNN ($k=2$) on the same anchor for query sq_ft = 1000:

Distances to each training point:

Two nearest: sq_ft = 850 (price 220) and sq_ft = 1100 (price 280).

$\hat{y}(1000)=\frac{220+280}{2}=\$250k$

For a second query, sq_ft = 800:

Nearest neighbors: 650 (price 180) and 850 (price 220).

$\hat{y}(800)=\frac{180+220}{2}=\$200k$

Linear regression gave \213.3k$ for this same query. These are different predictions — not by coincidence, but structurally. KNN interpolates locally from the two closest neighbors. Linear regression fits a single global line. On data that isn't perfectly linear, they will consistently disagree in regions far from training points.

Inference time is $O(n)$ — compute distance to every stored training point. Memory is $O(n)$ — all training data must be kept. At $n=10$ million samples, that's expensive.

When the Difference Matters: Four Scenarios

1. Large dataset, real-time inference (loan approval at a bank, $n=10M$): KNN must compute $10M$ distances per query — hundreds of milliseconds per decision. Use model-based (logistic regression). Inference is one dot product — sub-millisecond.

2. Streaming data that changes over time (user preference prediction): Instance-based wins — append new examples without retraining. Model-based requires periodic full retrains, which may take hours for large models.

3. Non-linear local patterns (housing prices by neighborhood): KNN captures the local cluster around each query point. A single global linear model may underfit neighborhoods that don't follow the citywide trend.

4. Interpretability required (medical diagnosis): Model-based (logistic regression, decision tree) — the physician can inspect the coefficients or rules. KNN offers no such explanation: "your nearest neighbors voted default" isn't useful.

Generalization: The Core Tradeoff

Model-based generalizes via the parametric assumption. If the true relationship is linear and you have very little data, a linear model generalizes from 3 points to any $x$. The downside: if the assumption is wrong, it's wrong everywhere — a systematic global error.

Instance-based generalizes by similarity — a new point inherits the labels of its nearest training points. No assumption about the global shape. The downside: in high dimensions, "nearest" stops being meaningful. When $p\gg 3$, two training points can be the "closest" while still being geometrically far away — a problem called the curse of dimensionality.

Comparison Table

Decision Guide

Related Concepts and Honest Limitations

KD-trees and ball-trees reduce KNN inference from $O(n)$ to $O(\log n)$ in low dimensions — but this speedup evaporates above roughly $p=20$ features, where the tree degenerates. That's why approximate nearest-neighbor methods (HNSW, FAISS) are used in high-dimensional retrieval systems.

Model-based learning isn't automatically safe from high-dimensional failure either: with more features than samples ($p>n$), OLS is undefined (singular matrix), and even regularized models need careful treatment. The curse of dimensionality hits everyone, just differently.

Test Your Understanding

1. For the anchor dataset, compute KNN ($k=2$) predictions for sq_ft = 1250. Then compute the linear regression prediction for the same query. Which is higher, and why does the difference arise?

2. You add a new training sample (sq_ft = 1050, price = 265) to the dataset. How does each approach handle this? Which requires more work?

3. An instance-based model "memorizes" training data exactly. Can it overfit? What would overfitting look like for $k=1$?

4. For a 100-feature dataset with $n=500$ samples, you're choosing between logistic regression (model-based) and KNN (instance-based). What factors push you toward logistic regression?

5. Why does the KNN inference cost not depend on the number of features $p$, while a linear model's inference cost does? Which grows faster with scale, and when does the crossover matter?