MODULE 4
INSTANCE BASED
LEARNING
INTRODUCTION
Instance Based Learning
❑ No explicit description of the target function when training
examples are provided.
❑ Instance-based learning methods simply store the training
examples.
❑ Generalizing these examples is postponed until a new
instance must be classified.
❑ Each time a new query instance is encountered, its
relationship to the previously stored examples is examined in
order to assign a target function value for the new instance.
Instance-based learning methods
❑Instance-based learning methods:
•K-Nearest Neighbour and
•Locally weighted regression
LAZY LEARNING: straightforward approaches
❑Local approximation to the target function(discrete or real
valued) that applies in the neighbourhood of the new query
instance.
❑Most suitable when target concept
4 is complex.
K-NEAREST NEIGHBOR
LEARNING
K-Nearest Neighbour
▪ Instance based learning includes nearest neighbor and locally weighted regression
methods that assume instances can be represented as points in a Euclidean space.
▪ The positive and negative training examples are shown by "+" and "-"respectively. A
query point xq. Note the 1-NEAREST NEIGHBOR algorithm classifies x, as a positive
[Link] 5-NEAREST NEIGHBOR algorithm classifies it as a negative example.
6
K-NEAREST NEIGHBOR LEARNING:Key idea
✓ Basic Supervised algorithm.
✓ Nearest Neighbor is defined by Euclidean distance.
✓ Assumption: All instances correspond to points in the n-
dimensional space ℜn.
✓ The distance between two instances xi and xj is defined to be
d(xi, xj )
Where,
x is an instance defined by
ar(x) denotes the value of rth attribute of instance x
K-NN Example-1
New instance:
height=161, Weight=61
K-NN Example-1
K=3,k<=sqrt([Link]
training examples),
generally k is odd
10
Where KNN?
11
Why KNN?
12
Why KNN?
13
K-NEAREST NEIGHBOR LEARNING
14
Instance-based learning methods are conceptually
straightforward approaches to approximating real-valued
or discrete-valued target functions.
•Classification problem : Discrete Valued
•Regression problem: Real valued
15
K-NN in two Dimensional Space
✓ The target function may be either discrete-valued or real-valued.
✓ Consider learning discrete-valued target functions of the form f :
ℜn → V, where V is the finite set {V1, . . . Vs,}
Delta counts how many of the k neighbors belong to class 𝑣
K-NN for Continuous /Real Valued Target Function
✓ The algorithm calculate the mean value of the k nearest training
examples rather than calculate their most common value.
✓ To approximate a real-valued target function f : ℜn → ℜ, replace the
final line of the above algorithm by the line
k-NN Regression Problem
▪ Predict output for x = 3 using k = 2
Step 1: Distance from x = 3
•|3−1| = 2
•|3−2| = 1
•|3−4| = 1
x y •|3−5| = 2
1 2 Step 2: Select k = 2 nearest
•(2,4)
2 4 •(4,4)
4 4 Step 3: Average Output
4+4
5 5 𝑦= =4
2
Predicted value = 4
18
When To Consider Nearest Neighbor
▫A key advantage of this kind of delayed, or lazy, learning is that
instead of estimating the target function once for the entire instance
space, these methods can estimate it locally for each new instance
to be classified.
▪Advantages:
▫Training is very fast
▫Learn complex target functions
▪Disadvantages:
▫Slow at query time
▫Easily fooled by irrelevant attributes
19
Distance-Weighted Nearest Neighbor Algorithm
✓ Refinement to the k-NN algorithm is to weight the contribution of each of
the k neighbors according to their distance to the query point Xq giving
greater weight to closer neighbors.
✓ Assigning greater weights to closer neighbors can be done by:
Where,
Distance-Weighted Nearest Neighbor Algorithm
✓ Distance-weight for real-valued target functions can be applied by
replacing the final line of the algorithm as:
Constant
Where,
Issues of K-NN Algorithm
✓ Distance between instances is calculated based on all attributes of the
instance: The distance between neighbors will be dominated by the large
number of irrelevant attributes.
✓ Curse of Dimensionality
Solution:
1. Weight each attribute differently when calculating the distance between
two instances.
2. Completely eliminate the least relevant attributes from the instance
space.(Dimensionality reduction)
3. Efficient memory indexing
23
K-NN Example2
Consider a dataset that contains two variables: height (cm) & weight (kg). Each
point is classified as normal or underweight.
Based on the above data, you need to classify (weight=57 and height =170) set as
normal or underweight using the KNN algorithm(Take maximum value possible for
k)
LOCALLY WEIGHTED
REGRESSION
Locally Weighted Regression(LWR)
✓ LWR is instance based learning algorithm.
✓ Local because the function is approximated based only
on data near the query point
✓ Weighted because the contribution of each training
example is weighted by its distance from the query
point.
✓ Regression :Approximating a real-valued target
function
26
Example
Step 1: Add Bias Term
1 1 1 2
Point x₁ x₂ y 𝑋 = 1 2 1 ,𝑦 = 3
1 3 2 5
𝑥𝑞 = [1,2,2]
A 1 1 2 Step 2: Compute Distance
𝑞 𝑞
𝑑= ൬𝑥1 − 𝑥1 )2 + ቀ𝑥2 − 𝑥2 )2
B 2 1 3
•A:
C 3 2 5 ൬1 − 2)2 + ቀ1 − 2)2 = 2 ≈ 1.414
•B:
൬2 − 2)2 + ቀ1 − 2)2 = 1
Q = (2, 2) •C:
Bandwidth: τ = 1
27 ൬3 − 2)2 + ቀ2 − 2)2 = 1
Τ (tau)
▪ The bandwidth parameter τ controls the locality of LWR.
▪ A small τ gives high weight to nearby points leading to
overfitting, while a large τ gives nearly equal weights resulting
in underfitting.
▪ τ>0 and τ <= 1.
28
Step 3: Compute Weights Step 4: Form Weight Matrix
2
▪ 𝑤𝑖 = 𝑒 / 2𝜏
−𝑑𝑖
2
𝜏=1 0.367 0 0
𝑊= 0 0.606 0
A:
0 0 0.606
▪ 𝑤1 = 𝑒 −2/2 = 𝑒 −1 = 0.367
Step 5:
B:
Compute θ
▪ 𝑤2 = 𝑒 −1/2 = 0.606 𝜃 = ൫𝑋 𝑇 𝑊𝑋)−1 𝑋 𝑇 𝑊𝑦
C: 0.33
▪ 𝑤3 = 𝑒 −1/2 = 0.606 𝜃 ≈ 1.17
29
0.83
Step 5: Compute θ
5.1 Compute 𝑋 𝑇
1 1 1 5.3 Compute 𝑋 𝑇 𝑊𝑋
𝑋𝑇 = 1 2 3 1.579 3.397 2.185
1 1 2 ▪ 𝑋 𝑇 𝑊𝑋 = 3.397 8.245 4.821
5.2 Compute 𝑊𝑋 2.185 4.821 3.397
Multiply each row of X by 5.4 Compute 𝑊𝑦
weights: 0.367 × 2 0.734
𝑊𝑋 ▪ 𝑊𝑦 = 0.606 × 3 = 1.818
0.367 0.367 0.367 0.606 × 5 3.03
= 0.606 1.212 0.606
0.606 1.818 1.212 30
Compute θ
5.5 Compute 𝑋 𝑇 𝑊𝑦
𝜃 = ൫𝑋 𝑇 𝑊𝑋)−1 𝑋 𝑇 𝑊𝑦
5.582 0.33
▪ 𝑋 𝑇 𝑊𝑦 = 13.46 𝜃 ≈ 1.17
8.612 0.83
5.6 Compute Inverse Step 6: Final Prediction
𝑦 = 𝑥𝑞 ⋅ 𝜃
▪ ൭𝑋 𝑇 𝑊𝑋)−1 𝑦 = 1 0.33 + 2 1.17 + 2 0.83
𝑦 = 0.33 + 2.34 + 1.66 = 4.33
3.2 −1.4 −0.8
≈ −1.4 0.9 −0.2 Predicted value = 4.33
31
−0.8 −0.2 1.1
Snippet of LWR
32
When to use LWR?
Method Use When…
You want simple prediction based on
k-NN
similar past data
You want local learning where nearby
LWR
points matter more
You expect a straight-line
Linear Regression
relationship
33
and need fast results
Application
• House price (simple trend)
→ Linear Regression
•Stock trend (local changes)
→ LWR
• Recommendation system →
k-NN
34
Thank You…!!!
35