Instance-Based Learning (Lazy Learning): Stores training instances, delays generalization until query. Prediction via similarity to stored instances, not explicit model.

General steps: Store $D=\{(x_i,y_i)\}$; for query $x_q$, find $k$ nearest neighbors by distance (Euclidean/Manhattan/cosine), combine (majority vote / weighted average / local regression).

Examples:

1. k-Nearest Neighbors (k-NN):

   • Classification: $\hat y = \arg\max_c \sum_{x_i\in N_k(x_q)} \mathbb{I}(y_i=c)$ (optionally distance-weighted: $w_i=1/d(x_q,x_i)^2$)
   • Regression: $\hat y = \frac1k\sum y_i$
   • Choose $k$ via CV; small $k$ flexible but noisy, large $k$ smooth but underfits. Need feature scaling, handles multi-modal, no training time, slow query $O(n d)$, needs KD-tree/ball-tree for speed. Pros: simple, effective with many data. Cons: curse of dimensionality, sensitive to irrelevant features.

2. Locally Weighted Regression (LWR):

   • Fits local model (e.g., linear) weighted by kernel $w_i=\exp(-d(x_q,x_i)^2/2\tau^2)$. Prediction $\hat f(x_q)=x_q^T\beta_q$ where $\beta_q=(X^T W X)^{-1}X^T W y$.
   • Example: LOESS for smoothing.

3. Case-Based Reasoning (CBR): Solves new problems by adapting solutions from similar past cases (e.g., medical diagnosis: retrieve similar patient cases, adapt treatment). Retrieve-Reuse-Revise-Retain cycle.

4. Radial Basis Function (RBF) Network (kernel memory based): Some interpretations include it.

Characteristics: No explicit training, incremental easily, ability to model complex boundaries locally, but memory intensive, needs careful distance metric selection and feature weighting.