Instance-based Learning

Introduction to AI and ML (Spring 2026)

Anirvan Krishna

April 26, 2026

1 Introduction to Instance-based Learning

Up to this point, we have studied eager learners (e.g., linear regression or neural networks),
which process training data to construct a global hypothesis θ before a query is ever seen. In
contrast, instance-based learning uses lazy learners that skip the training phase by simply stor-
ing the whole training dataset D = {( xi , yi )}in=1 in memory. These models are non-parametric.
They do not learn any set of parameters to represent the training data (like weights and biases
in neural networks). These models defer all computation until a query xq is received, at which
point they perform learning locally.
The intuition is that the output for xq can be estimated from the outputs yi of the most
similar (or closest) instances xi ∈ D according to a distance metric d( xq , xi ).

2 The k-Nearest Neighbors (k-NN) Algorithm

The k-NN algorithm is governed by the principle that birds of a feather flock together. In a feature
space, instances with similar characteristics (features) should yield similar outputs. To predict
the label of a new query point, we simply identify its k closest neighbors in the training set and
let them vote on the outcome. It assumes that the target function is locally constant or smooth.
Let D = {( xi , yi )}in=1 be a training dataset where xi ∈ Rd represents the feature vector and
yi is the corresponding target. Given a query instance xq , the algorithm proceeds as follows:
1. Distance Computation: Calculate the distance d( xq , xi ) between the query point and
every instance in D . Typically, we use the Euclidean distance (L2 norm):
v
u d
d( xq , xi ) = ∥ xq − xi ∥2 = t ∑ ( xq,j − xi,j )2
u
j =1

2. Neighbor Identification: Sort the distances in non-decreasing order and identify the set
of indices Nk ( xq ) corresponding to the k instances in D that are closest to xq :
Nk ( xq ) = {i | d( xq , xi ) is among the k smallest distances}

3. Prediction:
• For Classification: We perform a majority vote. The predicted class ŷq is the mode
of the neighbor labels:
ŷq = argmaxv∈Y ∑ 1( yi = v )
i ∈Nk ( xq )

where 1(·) is the indicator function that returns 1 if the condition is true and 0 oth-
erwise.

1
 • For Regression: We compute the mean of the neighbor values:

1
k i∈N∑(x )
ŷq = yi
k q

Numerical Example
To solidify our understanding, let’s apply the k-NN algorithm to a low-dimensional dataset.
By calculating these manually, we observe how the distance metric directly dictates the local
decision boundary.

Example 1: k-NN Classification in R3

We are given a reference set D containing four labeled points (prototypes):

• Class ω0 : P1 = (0, 0, 1) and P2 = (1, 1, 1)

• Class ω1 : P3 = (3, 3, 1) and P4 = (3, 2, 3)

Task: Classify the following unknown points Q using k = 2 and Euclidean distance:

Q = {(0, 0, 0), (1, 0, 0), (2, 1, 0), (3, 1, 0), (0, 2, 1), (2, 3, 1), (1, 2, 1)}

Source: EE60020: End-Autumn Semester 2024

Detailed Step-by-Step Logic

For each point xq ∈ Q, we follow three rigorous steps:
q
1. Calculate Distances: Find the Euclidean distance d( xq , Pi ) = ∑( xq,j − Pi,j )2 for i =
1 . . . 4.

2. Find k Neighbors: Identify the two indices {i, j} with the smallest distance values.

3. Vote: Determine if the majority of neighbors belong to ω0 or ω1 .

Example Calculation for xq = (1, 0, 0):

p √ √
• d( xq , P1 ) = (1 − 0)2 + (0 − 0)2 + (0 − 1)2 = 1+0+1 = 2 ≈ 1.41
p √ √
• d( xq , P2 ) = (1 − 1)2 + (0 − 1)2 + (0 − 1)2 = 0+1+1 = 2 ≈ 1.41
p √ √
• d( xq , P3 ) = (1 − 3)2 + (0 − 3)2 + (0 − 1)2 = 4+9+1 = 14 ≈ 3.74
p √ √
• d( xq , P4 ) = (1 − 3)2 + (0 − 2)2 + (0 − 3)2 = 4+4+9 = 17 ≈ 4.12

The 2-nearest neighbors are P1 and P2 . Since both are from ω0 , the point (1, 0, 0) is classified as
ω0 .

2
 Summary Table for Unknown Points

Query xq d( xq , P1 ) d( xq , P2 ) d( xq , P3 ) d( xq , P4 ) Neighbors Predicted Class

(0, 0, 0) 1.00 1.73 4.36 4.69 P1 , P2 ω0
(1, 0, 0) 1.41 1.41 3.74 4.12 P1 , P2 ω0
(2, 1, 0) 2.45 1.41 2.45 3.32 P2 , P1 /P3∗ Tie / ω0
(3, 1, 0) 3.32 2.24 2.24 3.16 P2 , P3 Tie
(0, 2, 1) 2.00 1.41 3.16 3.61 P1 , P2 ω0
(2, 3, 1) 3.61 2.24 1.00 2.45 P3 , P2 Tie
(1, 2, 1) 2.24 1.00 2.24 2.83 P2 , P1 /P3∗ Tie / ω0

*Note on Ties: When k is even, we often encounter ties. In this exercise:

• A Distance Tie occurs for (2, 1, 0) and (1, 2, 1) where multiple points are at the same
distance. Usually, we include all such points or pick one based on index order.
• A Voting Tie occurs for (3, 1, 0) and (2, 3, 1) where one neighbor is from ω0 and the other
is from ω1 . In practice, ties are broken by (a) choosing k to be odd, (b) looking at the
single nearest neighbor (1-NN), or (c) random selection.

Python Implementation for k −NN

Below is the implementation for k −NN algorithm using NumPy.
1 import numpy as np
2
3 def knn_predict ( X_train , y_train , x_query , k =3) :
4 # 1. Compute Euclidean distances using vectorization
5 # Broadcasing calculates distance from x_query to all rows in X_train
6 distances = np . sqrt ( np . sum (( X_train - x_query ) **2 , axis =1) )
7
8 # 2. Get indices of the k smallest distances
9 # argsort returns indices that would sort the array
10 k_indices = np . argsort ( distances ) [: k ]
11
12 # 3. Extract labels and perform majority voting
13 k_nearest_labels = y_train [ k_indices ]
14
15 # Use np . unique to count frequencies of each label
16 labels , counts = np . unique ( k_nearest_labels , return_counts = True )
17
18 # Return the label with the highest count
19 return labels [ np . argmax ( counts ) ]

In practice, however, for most of the machine learning applications (except neural networks),
we use Scikit-Learn. This will save us the time and effort of writing the logic from scratch
every time.

1 from sklearn . neighbors import KNeighborsClassifier

2
3 # Initialize model ( p =2 specifies Euclidean distance )
4 knn = K N e ighborsClassifier ( n_neighbors =3 , p =2)
5
6 # Store the data ( Lazy learning step )
7 knn . fit ( X_train , y_train )
8
9 # Predict for new samples
10 predictions = knn . predict ( X_test )

3
2.1 Weighted k −NNs
A potential limitation of the standard k-NN algorithm is that it treats all k neighbors equally,
regardless of their actual distance from the query point xq . This can be problematic if some
neighbors are significantly closer than others; intuitively, a neighbor that is "almost identical"
to the query should have more influence on the prediction than one that is just barely within
the top k.
To address this, we introduce Weighted k-NN, where each neighbor xi ∈ Nk ( xq ) is assigned
a weight wi based on its distance d( xq , xi ). The most common weight function is the inverse
distance weight:
1
wi =
d ( xq , xi ) + ϵ
where ϵ is a small constant (e.g., 10−7 ) added to the denominator to prevent division by zero if
the query point exactly matches a training instance.

Mathematical Modification
The classification rule is updated so that the "votes" are no longer simple counts, but sums of
weights. The predicted class ŷq is given by:

ŷq = argmaxv∈Y ∑ wi · 1( y i = v )
i ∈Nk ( xq )

For regression tasks, the prediction becomes a distance-weighted average:

∑i∈Nk (xq ) wi yi
ŷq =
∑i∈Nk (xq ) wi

By incorporating these weights, the model becomes more robust to the choice of k. Even if
k is large, distant points will have a negligible impact on the final decision, allowing the local
structure of the data to dominate the prediction.

Problem: Try solving the previous example using a weighted kNN approach and compare your results
with the previous one.

2.2 Limitations of k-NN

k-NN faces significant practical challenges, most notably a high inference delay. As a lazy
learner, it defers all computation until a query is made, requiring a O(nd) distance calcula-
tion against every training instance (Where n is the number of data points and d is the number
of features for each data point), which becomes computationally prohibitive for large datasets.
Furthermore, the algorithm is highly sensitive to irrelevant features; because standard distance
metrics treat all dimensions equally, non-informative features can dominate the distance cal-
culation and obscure the true similarity between points. This sensitivity to noise and the curse
of dimensionality typically necessitates careful feature selection or dimensionality reduction to
ensure the model remains effective in high-dimensional spaces.

4
3 Locally Weighted Regression (LWR)
While standard linear regression seeks a single global hypothesis to fit all training data, locally
weighted regression (LWR) acknowledges that a global linear fit may underfit non-linear data.
Instead of building one model for the entire space, LWR performs a local fit for each specific
query point xq . It treats the target function as locally linear (Fig. 1). By assigning higher im-
portance (weights) to training instances near the query point and ignoring those far away, the
algorithm can track complex, non-linear trends without needing a complex global functional
form.

Figure 1: Simple Linear Regression vs. Locally Weighted Regression

Mathematical Formulation
In global Linear Regression, we minimize the sum of squared errors: J (θ ) = ∑i (y(i) − θ T x (i) )2 .
In LWR, we modify this cost function by introducing a weighting term w(i) for each training
instance ( x (i) , y(i) ):
n
J (θ ) = ∑ w (i ) ( y (i ) − θ T x (i ) )2
i =1

The weights w(i) are non-negative and depend on the distance between the query point xq
and the training point x (i) . A standard choice is the Gaussian kernel:
!
∥ x (i ) − x ∥2
q
w(i) = exp −
2τ 2
Where:

• ∥ x (i) − xq ∥ is the Euclidean distance between the training instance and the query.

• τ is the bandwidth parameter, which controls how quickly the weight of a training point
falls off as its distance from xq increases. A small τ results in a very local fit (high vari-
ance), while a large τ behaves more like global linear regression (high bias).

5
 To find the prediction ŷq = θ T xq , we solve the normal equations modified for weights. In
matrix form, let W be a diagonal matrix where Wii = w(i) . The optimal parameters θ for the
query xq are given by:

θ = ( X T WX )−1 X T Wy
Note that unlike eager learners, LWR must recompute θ for every new query xq , making it
a non-parametric and computationally intensive method.

4 Learning with Radial Basis Functions (RBF)

Intuition
In machine learning, RBF networks act as a bridge between instance-based learning and global
models. Instead of storing every single training instance, we identify a set of centers (proto-
types) in the feature space. Each center represents a local region of influence; as an input x
moves further away from a center c, its influence on the final prediction decays—typically
following a Gaussian "bell" curve. The final model is a linear combination of these localized
responses.

Mathematical Formulation
The most common choice for a radial basis function is the Gaussian kernel. For a given center c j
and a width parameter σj , the activation ϕj ( x ) is defined as:
!
∥ x − c j ∥2
ϕj ( x ) = exp −
2σj2
Where:

• ∥ x − c j ∥ is the Euclidean distance between the input and the center.

• σj (the bandwidth) controls the "receptive field" of the function. A large σ creates a smooth,
broad influence, while a small σ makes the function highly localized and "spiky."

An RBF network typically consists of a three-layer architecture:

1. Input Layer: Passes the feature vector x ∈ Rd to the hidden layer.

2. Hidden Layer: Computes the activations ϕj ( x ) for M different centers {c1 , c2 , . . . , c M }.

3. Output Layer: Computes a linear combination of the hidden layer outputs to produce the
final prediction ŷ:

M
ŷ = w0 + ∑ w j ϕj ( x )
j =1

Unlike k-NN or LWR, which are purely lazy, RBF networks have a hybrid training process.
The centers c j and widths σj are often determined using unsupervised methods (like k-means
clustering) to capture the distribution of the input data, while the output weights w j are learned
via supervised linear regression (least squares). This makes the model semi-parametric and
significantly faster at inference time than pure instance-based methods.

6
5 Case-Based Reasoning (CBR)
Intuition and Structure
While k-NN and RBF typically operate on numerical feature vectors, Case-Based Reason-
ing (CBR) is a more general framework for solving problems by mapping a new query to a
database of rich, structured cases. CBR follows the principle that "similar problems have simi-
lar solutions." Instead of relying purely on mathematical distances in a coordinate space, CBR
often involves complex symbolic representations (like graphs or trees) to describe a situation.
The lifecycle of a CBR system is traditionally described by the 4R Cycle:

1. Retrieve: Given a new problem, the system searches the case base for the most similar
past cases. This requires a "similarity function" analogous to the distance metrics used in
k-NN.

2. Reuse: The solution from the retrieved case is mapped to the new problem.

3. Revise: Because the new problem is rarely identical to the old one, the system adapts or
modifies the retrieved solution to fit the specific constraints of the current query.

4. Retain: Once the new solution is successfully applied, the new problem and its validated
solution are stored back in the case base as a new "experience."

The CADET System: CBR in Engineering Design

The CADET (Case-based Design Aid Tool) system is a specialized application of CBR used for
conceptual design in mechanical and hydraulic engineering. Unlike standard instance-based
models that use numerical vectors, CADET stores cases as behavioral graphs. These graphs rep-
resent physical components by describing qualitative influences—for example, how an increase
in input torque leads to a specific change in output rotation.
When an engineer provides a functional specification for a new device, CADET does not
look for a single identical match. Instead, it performs sub-graph matching to retrieve fragments
of past designs that satisfy parts of the new specification. These fragments are then recomposed
and adapted using domain-specific knowledge to ensure the physical connections between
them are functional and consistent.

Example: Designing a Cooling System

To understand how the 4R Cycle manifests in a system like CADET, consider the design of a
temperature-controlled water cooling system:

• Retrieve: The designer specifies a need for a system that "cools a heat source by varying
water flow based on sensed temperature." CADET searches its library and retrieves two
distinct fragments: (1) a heat exchanger design from a previous refrigeration project and
(2) a thermostatic valve mechanism from an automotive engine case.

• Reuse: The system proposes combining the heat exchanger to handle the thermal transfer
and the thermostatic valve to regulate the flow. It "pastes" these behavioral sub-graphs
together to form a preliminary design.

• Revise: An engineering simulation reveals that the retrieved valve is designed for high-
pressure oil, not low-pressure water. The designer revises the case by adjusting the valve’s
spring constant and material specifications to suit the new fluid properties.

7
 • Retain: Once the design is finalized and verified, the resulting "Temperature-Controlled
Water Cooler" schematic is stored as a new behavioral graph in the case base. Future de-
signers can now retrieve this specific combination as a single unit.

This example highlights that CBR is not limited to simple classification; by utilizing rela-
tional and symbolic data, systems like CADET can perform creative synthesis by piecing together
past experiences to solve novel, complex problems.