# Supervised Learning: Instance-based Learning and K-Nearest Neighbors

Original: https://swyx.io/supervised-learning-instance-based-learning-and-k-nearest-neighbors-kge
Published: 2019-01-27

> Regression isn't the only way. What if we were far, far... lazier about it?

*This is the 5th in a series of class notes as I go through the [Georgia Tech/Udacity Machine Learning course](https://www.udacity.com/course/machine-learning--ud262). The class textbook is [Machine Learning by Tom Mitchell](https://www.cs.ubbcluj.ro/~gabis/ml/ml-books/McGrawHill%20-%20Machine%20Learning%20-Tom%20Mitchell.pdf).*


## What is "Instance Based"?

Recall that Supervised Learning [approximates a function](https://dev.to/swyx/machine-learning-an-overview-216n). Then projections are made by plugging in values to the function, without any reference to the actual data.

An alternative approach just puts all the raw data ("all instances") in a database, and, when queried, looks up the corresponding output. No time is spent doing any learning, so it is fast and simple.

However, of course, we lose out on **generalization** (for example if we are asked something close to but not exactly what we have data for) and we are prone to **overfitting** (for example if our data is noisy).

So Instance Learning looks at the nearest neighbors to decide what any queried point should be. Specifically, the `k` nearest neighbors.

## `K` Nearest Neighbors

Given:

- Training Data `D = {Xi, Yi}`
- Distance Metric `d(q, x)` (representing your domain knowledge - a way to quantify the similarity of one thing to another) 
- Number of neighbors, `k` (also relying on your domain knowledge as to what matters)
- A query point, `q`

The algorithm is simply - given `D`, find the `k` nearest neighbors (K-NN) based on your distance metric `d(q, x)`.

You can do both **classification** and **regression** this way:

- Classification: based on vote of `Yi`'s - your point is classified by whatever the most neighbors are
- Regression: the average of the `Yi`'s.

Instead of a simple vote or simple average that weighs all neighbors the same, you can also weight them by closeness so that closer neighbors count more.

## Lazy vs Eager

You can loosely break up these algorithms into **learning** and **querying** stages:

- The learning stage computational complexity of K-NN is `O(1)`, while Linear Regression is `O(N)`.
- The querying stage computational complexity of K-NN is `O(log N)`, while Linear Regression is `O(1)`

Thus more work is frontloaded by Linear Regression, making it an "eager" learning algorithm, whereas K-NN does more work while querying, making it "lazy.

## In Python

For some light programming practice, try solving the problems pictured here: 
{% youtube eBt8vTvmsV4 %}

[Here's a sample Repl](https://repl.it/@swyx/PracticalHarmfulOutsourcing) solution calculating nearest neighbors by Euclidian and Manhattan distance.

Note that the real answer ([based on the hidden function](https://www.youtube.com/watch?time_continue=319&v=X8tm6x2k_gQ)) was `18`, which K-NN doesn't get close to by any of these methods.

## KNN's biases

KNN's preference bias (its beliefs about what makes a good hypotheses) are:

- Locality - assumes that Near Points are "similar"
- Smoothness - using averaging
- All features matter equally <-- this belies the Curse...

## Curse of Dimensionality

> As the number of **features** or **dimensions** grows, the amount of data we need to **generalize accurately** grows exponentially!

[More on wikipedia](https://en.wikipedia.org/wiki/Curse_of_dimensionality)

## A blended approach

Instead of a Euclidean/Manhattan weighted/unweighted average approach to estimating the final result, we can also combine a KNN with regression to create [locally-weighted regression](https://en.wikipedia.org/wiki/Local_regression) to have the best of both worlds. This isn't just limited to regression - within the defined nearest neighbors, you can use any of the methods we have covered so far, like neural networks or decision trees.

## Optimal Data Structure

We can also consider more efficient data structures for kNN than a simple lookup table. [Ball Trees](https://en.wikipedia.org/wiki/Ball_tree) are promising in this regard.

## Next in our series

Hopefully that was a good introduction to Instance-based Learning and K-Nearest Neighbors. I am planning more primers and would love your feedback and questions on:


- [Overview](https://dev.to/swyx/machine-learning-an-overview-216n)
- Supervised Learning
    - [Decision Trees](https://dev.to/swyx/machine-learning-classification-learning--decision-trees-1mbh)
    - [Regression](https://dev.to/swyx/supervised-learning-regression-4d17)
    - [Neural Networks](https://dev.to/swyx/supervised-learning-neural-networks-mpo)
    - [Instance Based Learning (K Nearest Neighbors)](https://dev.to/swyx/supervised-learning-instance-based-learning-and-k-nearest-neighbors-kge)
    - [Ensemble Learning (AdaBoost)](https://dev.to/swyx/supervised-learning-ensemble-learning-lim)
    - [Kernel Methods & SVMs](https://dev.to/swyx/supervised-learning-support-vector-machines-3mgk)
    - [Computational Learning Theory](https://dev.to/swyx/supervised-learning-computational-learning-theory-160h)
    - [VC Dimensions](https://dev.to/swyx/supervised-learning-vc-dimensions-10b)
    - [Bayesian Learning](https://dev.to/swyx/supervised-learning-bayesian-learning-403l)
    - [Bayesian Inference](https://dev.to/swyx/supervised-learning-bayesian-inference-4l72)
- Unsupervised Learning
    - [Randomized Optimization](https://dev.to/swyx/unsupervised-learning-randomized-optimization-4c1i)
    - [Information Theory](https://dev.to/swyx/unsupervised-learning-information-theory-recap-4iem)
    - Clustering - week of Feb 25
    - Feature Selection - week of Mar 4
    - Feature Transformation - week of Mar 11
- Reinforcement Learning
    - Markov Decision Processes - week of Mar 25
    - "True" RL - week of Apr 1
    - Game Theory - week of Apr 15