Instance-Based vs Model-Based Learning

You're building a real-time loan approval system. Every application needs a credit decision in under 100 milliseconds. You train a logistic regression model — a few hundred coefficients, sub-millisecond inference. Now a colleague suggests K-Nearest Neighbors instead: no training, just store all past applications. Inference now takes hundreds of milliseconds, and you discover a key difference: logistic regression compressed the training data into a compact formula; KNN kept every row.

That choice — throw the data away vs keep it — separates model-based learning from instance-based learning. Getting it wrong means deploying a system that's either too slow to serve or too rigid to capture the real pattern.

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.3\text{k}$

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.3\text{k}$

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}=250\text{k}$

For a second query, sq_ft = 800:

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

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

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

The model-vs-instance distinction feeds directly into the hyperparameter tradeoffs in this series: polynomial degree (post 13) controls model complexity for linear regression just as $k$ controls KNN's local vs global behavior. Both are forms of the bias-variance tradeoff, explored in post 10.

A common mistake is assuming instance-based methods beat the curse of dimensionality. They don't — they just fail differently. A linear model with $p>n$ produces infinite possible weight vectors; KNN with $p>50$ produces nearest neighbors that are still geometrically far. The high-dimension problem is structural, not algorithmic — which is why feature engineering and dimensionality reduction are prerequisites, not optional improvements.

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?