Instance Based Learning
f(x) = lookup(x)
can't generalization overfitting
k nearest neightbors
| Running time | space | |
|---|---|---|
| 1-NN learning | 1 | n |
| query | logn | 1 |
| k-NN learning | 1 | n |
| query | logn + k | 1 |
| linear regression learning | n | 1 |
| query | 1 | 1 |
knn ------- lazy learnnig; linear regression-----eager learning
(weighted)
k = n weighted average(regression) -------locally weighted regression