Classification Algorithms

Classification algorithms assign inputs to one of a finite set of categories by learning decision boundaries or class-probability estimates from labeled examples.

Definition

A classification algorithm learns, from input-label pairs, a rule that maps each new input to a discrete class; generative approaches model the distribution of inputs within each class and apply Bayes' rule, while discriminative approaches model the class boundary or posterior probability directly.

Scope

This topic covers the supervised task of predicting categorical labels: probabilistic generative classifiers such as naive Bayes and Gaussian discriminant analysis, discriminative classifiers such as logistic regression, instance-based methods such as k-nearest neighbors, and the notions of decision boundary, posterior class probability, and the Bayes-optimal classifier that minimizes error.

Core questions

• How is a decision boundary between classes estimated from labeled data?
• When should a classifier model class-conditional distributions versus the posterior directly?
• What is the Bayes-optimal error and how close can a learned classifier come to it?
• How are multiclass problems reduced to or solved alongside binary classification?

Key theories

Bayes-optimal classification

Assigning each input to the class with highest posterior probability minimizes expected misclassification error, defining the theoretical optimum that practical classifiers approximate.

Generative versus discriminative models

Naive Bayes and discriminant analysis model how data are generated per class, whereas logistic regression models the class posterior directly, a distinction that affects data efficiency and robustness to model misspecification.

Nearest-neighbor classification

Classifying by the labels of nearby training points is a simple nonparametric rule whose error is asymptotically bounded by at most twice the Bayes error, illustrating how local information alone can be powerful.

Clinical relevance

Classification is the workhorse of applied machine learning, behind email spam detection, sentiment analysis, image labeling, fraud detection, and computer-aided diagnosis; understanding the Bayes optimum and the generative-discriminative distinction guides the choice of method and the interpretation of class-probability outputs.

History

Early classifiers included Fisher's linear discriminant and the nearest-neighbor rule analyzed by Cover and Hart in 1967. Logistic regression migrated from statistics into machine learning, and naive Bayes and discriminant analysis became standard probabilistic baselines, all later unified within the framework of estimating posterior class probabilities.

Key figures

• Thomas Cover
• Peter Hart
• Christopher Bishop

Seminal works

• cover1967
• bishop2006
• hastie2009

Frequently asked questions

Is logistic regression a regression or a classification method?

Despite its name, logistic regression is used for classification. It models the probability that an input belongs to a class, and a decision rule then converts that probability into a predicted label.

Why does k-nearest neighbors need no training phase?

k-nearest neighbors stores the training data and classifies a new point by looking up its closest stored examples at prediction time. There is no explicit fitted model, which makes training trivial but prediction potentially slow and memory-intensive.