5 Classification Algorithms
This chapter covers
- Introduction to Classification
- Perceptron Algorithm
- SVM Algorithm
- SGD Logistic Regression
- Bernoulli Naïve Bayes Algorithm
- Decision Tree (CART) Algorithm
In the previous chapter, we looked at computer science fundamentals required to implement ML algorithms from scratch. In this chapter, we focus on supervised learning algorithms. Classification is a fundamental class of algorithms and is widely used in machine learning. We will derive from scratch and implement a number of selected classification algorithms to build our experience with fundamentals and motivate the design of new ML algorithms.
5.1 Introduction to Classification
In supervised learning, we are given a dataset D={(x1,y1),…,(xn,yn)} consisting of tuples of data x and labels y. The goal of a classification algorithm is to learn a mapping from inputs x to outputs y, where y is a discrete quantity, i.e. y∈{1,...,K}. If K=2, we have a binary classification problem, while for K>2 we have multi-class classification.
A classifier h can be viewed as a mapping between a d-dimensional feature vector ϕ(x) and a k-dimensional label y, i.e. h:Rd→Rk. We often have several models to choose from, let's call this set of classifier models H. Thus, for a given h ∈ H, we can obtain a prediction y=h(ϕ(x)). Note that we are typically interested in predicting on new or unseen data. In other words, our classifier h must be able to generalize to new data samples.