Instance-Based Learning (Lazy vs Eager)

Source: Unit 2 §1

The core idea

Instance-based learning memorizes instead of generalizing.

Most learners, decision trees among them, generalize: they build a model before ever seeing test data. Instance-based learners do the opposite. They simply store the training examples and delay all processing - "lazy evaluation" - until a new instance actually has to be classified.

The two learners do the same total work, but the eager one front-loads it into training while the lazy one defers all of it to query time.

Lazy vs eager learning

	Lazy learning	Eager learning
What it does	Simply stores the training data (or does minor processing) and waits until it is given a test tuple.	Constructs a classification model before receiving any test data.
Example	Instance-based learning (KNN)	Decision tree learning
Training time	Less - it only has to store.	More - it has to build the model.
Prediction time	More - the work is done now.	Less - the model is already there.
Hypothesis	Uses a richer hypothesis space: many local linear functions that together form an implicit global approximation.	Must commit to a single hypothesis covering the entire instance space.

The trade-off is a see-saw, not a win: whichever learner is cheap to train is expensive to query.

◎Exam cueThe key trade-off, in one line

Lazy = little training, lots of prediction time. Eager = lots of training, fast prediction.

⇄CompareWhere the hypothesis lives

LazyNo single global hypothesis is ever committed to. Each query gets its own **local** approximation, built from the neighbours of that query. The implicit global function is the union of all those local pieces, which is why the hypothesis space is described as richer.

EagerOne hypothesis has to cover the whole instance space, chosen at training time before any query is known. Every query is answered from that one commitment.

Three typical instance-based approaches

Approach	Idea
k-Nearest Neighbour	Instances are points in Euclidean space; classify a query from the nearest points.
Locally Weighted Regression	Constructs a local approximation around the query.
Case-Based Reasoning	Uses symbolic representations and knowledge-based inference rather than points in a metric space.

⚠GotchaLazy does not mean cheap

"Lazy" describes when the work happens, not how much there is. A lazy learner with a large stored data set can be the most expensive model you own at query time, which is exactly the cost KNN pays.