# Machine learning/Classification algorithms

Classification is a subcategory of supervised learning problems.

## k-nearest neighbor

• a simple classification algorithm
• Intuition: Find the majority vote in the training data
• This is a discriminative model, meaning that there is no way to generate the training data points

### Algorithm

• Define some distance metric or similarity metric. The simplest case is Euclidean distance.
• Given some input point $x$ , find the $k$ 'th nearest neighbors from the training set.
• Do a majority vote between these nearest neighbor list and classify the input point as the category with highest number of vote.

### Probabilistic interpretation

Consider the classification output as a random variable $y$ . Define probability of $y$  given input $x$  and training data $D$  is

$P(y|x,D)={\text{fraction of points }}x_{i}{\text{ in }}k{\text{-th nearest neighbor points to }}x{\text{ such that }}y_{i}=y$

The output of the classification is

${\hat {y}}=\arg \max _{y}P(y|x,D)$