Lazy Learners

Lazy Learners

1. Eager vs Lazy Learning

Aspect	Eager learner	Lazy learner
When is work done?	Model built at training time, before any query	Almost no training; work deferred to classification time
Model	Explicit (tree, rules, network weights)	Implicit — just the stored training tuples
Prediction cost	Low, constant	High (search over stored data)
Training cost	High	Near zero (or just indexing)
Adaptability	Must retrain for new data	New tuple added instantly, no retraining
Examples	Decision tree, naive Bayes, SVM, neural net, rule induction	k-nearest neighbour, case-based reasoning, lazy Bayesian rules (LBR), locally weighted regression

Key term: instance-based / memory-based learning — the learner stores instances and generalises only when a new query arrives.

2. k-Nearest Neighbour (k-NN) Classifier

Algorithm

kNN(TestTuple xq, TrainingSet D, k):
  1. for each training tuple (xi, yi) in D:
        compute distance d(xq, xi)
  2. select the k tuples nearest to xq (the k-nearest neighbours)
  3. class of xq = majority class among those k neighbours
     (for numeric prediction -> mean of the k neighbour values)
     ties are broken arbitrarily, or by weighting

Distance measures

Measure	Formula	Use
Euclidean	$d(x_i,x_j)=\sqrt{\sum_{a=1}^{n}(x_{ia}-x_{ja})^{2}}$	Continuous, most common
Manhattan	$\sum_a |x_{ia}-x_{ja}|$	Robust, grid-like
Minkowski	$\left(\sum_a |x_{ia}-x_{ja}|^{p}\right)^{1/p}$	General ($p=1$ Manhattan, $p=2$ Euclidean)
Cosine	$\frac{\mathbf{x}_i\cdot\mathbf{x}_j}{\|\mathbf{x}_i\|\|\mathbf{x}_j\|}$	Text / sparse vectors
Hamming	number of differing positions	Nominal / binary
Mahalanobis	$\sqrt{(\mathbf{x}_i-\mathbf{x}_j)^{T}\Sigma^{-1}(\mathbf{x}_i-\mathbf{x}_j)}$	Correlated attributes

For nominal attributes use a simple overlap metric: difference 0 if equal, 1 otherwise; or the HVDM (heterogeneous value difference metric) for mixed types.

Distance-weighted voting (removes the influence of k):

Numeric prediction with k-NN: $\hat y(x_q)=\dfrac{\sum_i w_i\,y_i}{\sum_i w_i}$ (or the simple mean of the k neighbours).

3. Worked Example (k = 3, Euclidean on normalised data)

Training tuple 1 (x=1, y=2, class A); t2 (2,3,B); t3 (3,1,A); t4 (6,5,B); test x_q = (2,2).

Neighbour	Squared Euclidean distance
t1 (1,2)	$(2-1)^2+(2-2)^2 = 1$ → d = 1.00
t2 (2,3)	$0^2+1^2 = 1$ → d = 1.00
t3 (3,1)	$1^2+1^2 = 2$ → d = 1.41
t4 (6,5)	$16+9=25$ → d = 5.00

3 nearest = {t1(A), t2(B), t3(A)} → majority = A.
Weighted: $1/1 + 1/1.41 = 1 + 0.709 = 1.709$ for A vs $1/1 = 1.000$ for B → A (stronger margin).

4. Choosing k and Normalisation

k	Bias–variance behaviour	Effect
k = 1	Very low bias, very high variance	Fits noise; zero training error but poor generalisation, sensitive to outliers
Small k (3-5)	Flexible boundary	Good for well-separated classes
Large k	High bias, low variance	Smooths the boundary; over-smoothing when classes are unbalanced (majority class dominates)
k = n	Predicts the majority class always	Useless

Guidance: try several values of $k$; a common starting point is $k = \sqrt{n}$ (odd to break ties) and tune with cross-validation.

Normalisation is essential because k-NN uses distance: with income in lakhs and age in years, income would dominate. Use min-max or z-score scaling first.

5. Efficiency and Scalability Issues

• Time complexity: $O(n \cdot d)$ per query with a linear scan; $O(n^2)$ for the whole test set. Prohibitive for huge or streaming datasets (use sampling, editing/condensing, or parallel/approximate search).
• Space: stores all training data (can be reduced by prototype selection — keep representatives instead of all tuples).
• Indexing for speed:
  • k-d trees / ball trees / R-trees — space-partitioning indexes for low-dimensional data.
  • Locality-sensitive hashing (LSH) — approximate neighbour search in high dimensions.
  • Inverted index / inverted lists with pruning (e.g. iDistance, VA-file) for high-dimensional data.
• Only a portion of attributes may matter — use attribute weighting or feature selection to reduce $d$.

6. Variants and Related Techniques

Variant	Idea
Locally weighted regression (LWR)	Fit a regression surface locally around the query point (memory-based)
Case-based reasoning (CBR)	Uses richer case structures and adaptation rules (medical diagnosis, help desks)
Lazy Bayesian Rules (LBR)	Builds a Bayesian rule only for the specific test instance
k-NN for outlier detection	A point whose k-th neighbour is far away is an outlier (distance-based outliers)
Editing/condensing	Reduce the stored set: remove noisy tuples, merge prototypes

7. Advantages and Limitations

Advantages

• Simple, easy to implement and understand; no model assumptions (non-parametric), so it can fit complex, non-linear boundaries.
• Very fast "training", learns from data as it arrives (incremental, no retraining); naturally handles multi-class and mixed data; intuitive.
• Usually quite accurate on moderate-sized, well-scaled datasets; the local approximation adapts per query.

Limitations

• Lazy — prediction cost is high and grows with the training set; poor scalability in time and space.
• Sensitive to irrelevant attributes and to attribute scaling (must normalise/weight attributes), and requires a well-chosen distance function.
• Curse of dimensionality — in high dimensions distances become similar and k-NN degrades (needs dimensionality reduction or metric learning).
• No interpretable model, no explanation of a prediction; sensitive to noise/outliers (especially with k=1); imbalanced classes bias the majority vote; tie-breaking is ad hoc.

8. Comparison with an Eager Learner

	k-NN	Decision tree
Model built?	No (instance based)	Yes
Prediction time	High	Low
Training time	Near zero	High
Explanation of a prediction	Neighbours only	Path/rule
New data	Immediate	Retrain
Missing values	Must impute (needs a distance)	Handled natively

9. Exam Points

• Define lazy vs eager learning and classify k-NN — 5 marks.
• Explain the k-NN algorithm with a numerical example and the choice of k — 10 marks (very frequent).
• Explain distance measures and the effect of the choice of k — 5 marks.
• Efficiency issues and indexing techniques for k-NN — 5 marks.
• Advantages and limitations of lazy learners — 5 marks.