Classification and Kernel Methods

Introduction

Classification is a supervised learning task in which a model learns from labelled examples and assigns one of a set of discrete classes to a new observation. Applications include detecting fraudulent transactions, diagnosing diseases, filtering email, recognising images, approving loans and identifying defective manufactured products.

A classification system usually contains four elements: a feature representation, a learning algorithm, a decision rule and an evaluation procedure. If an observation is represented by a feature vector x = (x₁, x₂, …, x_p), the objective is to learn a function that maps it to a class label y ∈ {1, 2, …, K}. Some classifiers also estimate class probabilities, which are valuable when decisions have unequal costs.

This chapter examines logistic regression, k-nearest neighbours, naïve Bayes and support vector machines. It also develops the ideas of decision boundaries, kernel functions, probability calibration and multiclass classification.

Learning Objectives

By the end of this chapter, a learner should be able to:

• distinguish discriminative and generative classification methods;
• construct and interpret logistic regression models;
• apply k-nearest neighbours and select an appropriate value of k;
• explain naïve Bayes assumptions and calculate posterior probabilities;
• formulate the support vector machine margin and explain the kernel trick;
• compare linear, polynomial and radial basis function decision boundaries;
• evaluate classification models using appropriate metrics;
• calibrate probability estimates and implement multiclass strategies;
• identify practical, ethical and operational risks in classification systems.

1. Classification Foundations

A binary classifier predicts one of two classes, conventionally represented as 0 and 1. A multiclass classifier predicts one of K classes. In multilabel classification, an observation may belong to several classes simultaneously; this is a different problem from ordinary multiclass classification.

A classifier produces either a hard prediction or a score. A hard prediction is a class label. A score ranks observations by their evidence for a class. A probability estimate attempts to satisfy 0 ≤ P(y = k | x) ≤ 1 and ∑_k=1^K P(y = k | x) = 1. Scores should not automatically be interpreted as probabilities.

Decision boundaries

A decision boundary is the set of feature values at which the predicted class changes. For a linear binary classifier, the boundary is described by:

Here, w is a vector of feature weights, x is the feature vector and b is an intercept. Points for which wᵀx + b > 0 are assigned to one side, while points for which it is negative are assigned to the other side. In two dimensions the boundary is a line; in three dimensions it is a plane; in higher dimensions it is a hyperplane.

The vector w is perpendicular to the boundary. Increasing the magnitude of a feature weight increases the model's sensitivity to that feature, although comparisons are meaningful only when feature scales and units have been considered.

Data preparation and leakage

Classification pipelines commonly include missing-value treatment, categorical encoding, scaling and feature selection. These operations must be fitted using training data only. If information from the validation or test set influences preprocessing, the reported performance is optimistically biased; this is called data leakage.

Standardisation is often useful for distance-based and margin-based methods. For feature j, training-set standardisation is:

where μ_j and σ_j are the training mean and standard deviation. The same values must transform validation and production data. Standardisation is not always necessary for naïve Bayes, and tree-based methods generally do not require it.

2. Logistic Regression

Logistic regression is a discriminative model that estimates the probability of a binary outcome. It first forms a linear score:

The logistic, or sigmoid, function converts this score to a probability:

The coefficients are estimated by maximum likelihood. For observations (x_i, y_i), where y_i ∈ {0,1}, the likelihood is:

where p_i = P(y_i = 1 | x_i). In practice, the negative log-likelihood, also called log loss or cross-entropy, is minimised:

The formula assumes independent observations and a correctly specified conditional relationship on the log-odds scale. The logarithm is natural unless otherwise stated.

The log-odds interpretation is:

Holding other variables constant, increasing x_j by one unit multiplies the odds by e^β_j. This interpretation requires care when predictors are transformed, standardised or correlated.

Classification threshold

The common threshold is 0.5: predict class 1 when p ≥ 0.5. Because σ(z) ≥ 0.5 exactly when z ≥ 0, this threshold produces the linear boundary β₀ + βᵀx = 0. A different threshold may be preferable when false negatives and false positives have different costs.

Regularisation

To reduce overfitting, a penalty can be added to the loss. Ridge logistic regression uses:

Lasso logistic regression uses:

Here λ ≥ 0 controls penalty strength. The intercept is commonly excluded from the penalty. Larger λ produces stronger shrinkage. Lasso can set some coefficients exactly to zero, whereas ridge usually retains all features with smaller magnitudes.

Worked example

Suppose a model is z = −2 + 0.8x. For x = 3, z = −2 + 0.8(3) = 0.4. Therefore:

At a threshold of 0.5 the observation is assigned to class 1. At a threshold of 0.7 it is assigned to class 0. The score and the decision are therefore distinct.

3. k-Nearest Neighbours

k-nearest neighbours (k-NN) is a non-parametric, instance-based method. It stores the training observations. For a query point, it identifies the k closest training examples and predicts the majority class. A distance-weighted version gives closer neighbours greater influence.

The Euclidean distance between two p-dimensional vectors is:

This distance is appropriate for numeric features where straight-line distance is meaningful. Manhattan distance, ∑_j |x_j − x′_j|, may be more robust in some high-dimensional or grid-like settings. Categorical variables require suitable encodings or specialised distances.

For binary classification, an unweighted estimate of the local class probability is:

where N_k(x) is the set of k nearest training points and I(·) is 1 when its condition is true and 0 otherwise.

A small k creates flexible boundaries and low bias but can have high variance. A large k smooths the boundary, increasing bias but reducing variance. The value of k should be selected using validation or cross-validation, not the test set.

Scaling is essential when variables have different units. For example, annual income measured in thousands and age measured in years can cause income to dominate Euclidean distance unless features are transformed appropriately. k-NN also suffers from the curse of dimensionality: as the number of dimensions increases, distances become less informative and the required sample size grows rapidly.

Prediction is computationally expensive for large datasets because distances to many stored points may be required. Approximate-neighbour indexes can reduce latency, but their accuracy and maintenance should be evaluated.

4. Naïve Bayes

Naïve Bayes is a generative classifier based on Bayes' theorem:

For classification, the denominator is common to all classes. The naïve conditional-independence assumption gives:

Thus the selected class is:

The assumption is usually false, but the method can still classify effectively, particularly with text data where word counts are sparse and high-dimensional.

Common variants include Gaussian naïve Bayes for continuous features, multinomial naïve Bayes for counts such as word frequencies, and Bernoulli naïve Bayes for binary indicators. Gaussian naïve Bayes assumes feature j within class k follows a normal distribution with class-specific mean μ_jk and variance σ²_jk:

The formula requires σ²_jk > 0. Numerical underflow can occur when many small probabilities are multiplied, so implementations use log probabilities:

For categorical or count data, zero-frequency estimates can assign zero probability to an otherwise plausible document or observation. Laplace smoothing replaces a count with a positive adjusted count. Its strength should be selected carefully because excessive smoothing can distort probabilities.

Naïve Bayes is fast, interpretable at the feature-distribution level and effective with limited training data. Its probability estimates may be poorly calibrated, especially when features are correlated.

5. Support Vector Machines

A support vector machine (SVM) seeks a separating hyperplane with a large margin. For labels encoded as y_i ∈ {−1,+1}, the signed functional margin is y_i(wᵀx_i+b). A correctly classified point has a positive value.

For linearly separable data, the canonical hard-margin problem is:

The geometric margin between the two supporting hyperplanes is 2/||w||. Minimising ||w||² therefore maximises the margin. The support vectors are observations lying on or inside the margin boundaries; they determine the fitted solution.

Real data are often not perfectly separable. Soft-margin SVM introduces slack variables ξ_i ≥ 0:

The parameter C > 0 controls the trade-off between a wide margin and training violations. Large C penalises violations strongly and may produce a narrower, less regularised boundary. Small C permits more violations and encourages a wider margin. The hinge loss associated with an example is:

SVMs are sensitive to feature scale. The linear version is effective when classes are approximately linearly separable in the feature space. Nonlinear relationships require an appropriate kernel or explicit feature transformation.

6. Kernels and Nonlinear Decision Boundaries

A kernel function computes an inner product in an implicit transformed feature space:

Here φ maps the original input into a possibly high-dimensional feature space. The kernel trick allows an algorithm to use these inner products without explicitly constructing φ(x).

Common kernels include:

In the RBF kernel, γ > 0 controls the locality of influence. Large γ makes each point influential only nearby, creating highly flexible boundaries; small γ creates smoother, broader influence. The parameterisation is sometimes written using σ, where γ = 1/(2σ²). These are equivalent only under that stated relationship.

A valid kernel must produce a positive semidefinite Gram matrix under the relevant conditions. The Gram matrix has entries K_ij=K(x_i,x_j). Kernel choice should be guided by domain knowledge, validation performance, computational cost and interpretability rather than by training accuracy alone.

7. Comparing Decision Boundaries

Logistic regression and linear SVM create linear boundaries in the original feature space. k-NN creates local, data-dependent boundaries. Naïve Bayes creates boundaries determined by the assumed class-conditional distributions; Gaussian assumptions can produce quadratic boundaries when class variances differ. Kernel SVMs create nonlinear boundaries in the original space while remaining linear in the implicit feature space.

No method is universally superior. Model selection should consider predictive performance, calibration, latency, memory, explainability, fairness and the consequences of errors.

8. Evaluation and Probability Calibration

A confusion matrix records true positives (TP), true negatives (TN), false positives (FP) and false negatives (FN). Important metrics are:

The F1 score is the harmonic mean of precision and recall:

These ratios require nonzero denominators. Accuracy can be misleading under class imbalance. Precision is important when false alarms are costly; recall is important when missed positive cases are costly. Receiver operating characteristic (ROC) curves plot true-positive rate against false-positive rate over thresholds. Precision–recall curves are often more informative when the positive class is rare.

Log loss evaluates probabilistic predictions. For binary outcomes it is the cross-entropy expression given earlier. A well-calibrated model means that among cases assigned probability about 0.7, approximately 70% belong to the relevant class, subject to sampling variation. Discrimination and calibration are different: a model can rank cases well but provide inaccurate probabilities.

Calibration can be improved using a held-out calibration set or nested cross-validation. Platt scaling fits a logistic mapping to model scores. Isotonic regression fits a non-decreasing, piecewise relationship and can be more flexible, but generally needs more data. Calibration must not be fitted on the same predictions used to estimate the model's final performance.

9. Multiclass Strategies

Binary algorithms can be extended to K classes in several ways.

One-vs-rest (OvR). Train K classifiers. Class k is treated as positive and all other classes as negative. Predict the class with the largest score. OvR is computationally economical but can produce incomparable scores if classifiers are trained independently.

One-vs-one (OvO). Train one classifier for every pair of classes, requiring K(K−1)/2 models. For example, five classes require 5×4/2 = 10 pairwise models. Voting or pairwise probability coupling combines their outputs. OvO can be useful for algorithms that work particularly well on binary problems, although prediction requires evaluating many models.

Multinomial or softmax logistic regression. For class k, assign a score z_k = β_kᵀx. The softmax probability is:

The probabilities are nonnegative and sum to one. Adding the same constant to every z_k does not change the probabilities, so an identifiability constraint or reference class is normally used during estimation.

Class weights, threshold selection and resampling may address imbalance, but they solve different problems. Resampling changes the training distribution; threshold adjustment changes the decision rule; calibration estimates probabilities under a specified target distribution.

10. Applied Case: Illustrative Loan-Default Screening

Background

A lender wants to identify applications requiring additional review. The dataset contains income, debt-to-income ratio, repayment history, employment duration and a default label. The system is illustrative; it does not represent a real lender or a regulatory determination.

Problem

The positive class, default, represents only 6% of applications. Missing a likely default may create financial loss, while incorrectly referring a reliable applicant for manual review creates delay and potential unfairness. A model should therefore be evaluated using recall, precision, calibration and subgroup performance rather than accuracy alone.

Analysis

The data are split chronologically so that later applications form the test set. This reduces the risk of using future information to predict the past. Missing values are imputed within each training fold. Numeric variables are standardised for logistic regression, k-NN and SVM. The default label, post-application events and any variables derived from future repayment information are excluded to prevent leakage.

A regularised logistic model provides a transparent baseline. k-NN is tested after scaling, while Gaussian naïve Bayes provides a fast distributional comparison. Linear and RBF SVMs are tuned using nested cross-validation. The positive-class weight is increased during training, but the final threshold is selected using the lender's documented cost ratio.

Approach and solution

The selected model is not simply the one with the highest accuracy. Suppose the RBF SVM has strong ranking performance but poorly calibrated probabilities, while regularised logistic regression has slightly lower ranking performance and reliable calibration. If decisions depend on estimated risk, logistic regression may be preferable, or the SVM may be calibrated on independent validation predictions. The organisation should document the threshold, version, training data, features and reason codes.

Fairness checks compare false-positive and false-negative rates across legally and ethically relevant groups, subject to privacy and applicable law. A protected attribute should not be removed automatically: it may be needed for auditing, although its use in decisions may be restricted. Human review should not be a superficial appeal process; reviewers require clear procedures and authority to correct data errors.

Outcome and learning points

The appropriate outcome is a monitored decision-support process, not an autonomous rejection engine. Performance must be re-evaluated under changing economic conditions, and drift detection should trigger review. The case demonstrates that model choice depends on probability quality, costs, governance and fairness as well as predictive scores.

11. Implementation Best Practices and Limitations

A professional workflow uses a reproducible pipeline: define the target; establish a leakage-resistant split; inspect class balance; preprocess inside cross-validation; tune hyperparameters; compare against a simple baseline; evaluate on untouched test data; calibrate if probabilities are required; and monitor after deployment.

Important limitations include:

• Sampling bias: training data may not represent future or underserved populations.
• Concept drift: the relationship between features and labels may change.
• Label noise: delayed, subjective or incorrect labels limit the achievable performance.
• Correlation and causation: predictive association does not prove that changing a feature will change the outcome.
• High-dimensionality: distance and density estimates degrade as dimensions increase.
• Operational constraints: latency, memory, retraining cost and explainability may determine feasibility.
• Adversarial behaviour: users may manipulate inputs when decisions are known.

Security, privacy and governance should be designed into the system. Sensitive personal data should be minimised, access-controlled and retained only as justified. Predictions should not be presented as certain facts. Documentation should state intended use, exclusions, data provenance, known limitations, threshold rationale and monitoring responsibilities. Regulatory requirements vary by jurisdiction and application, so professional teams must consult applicable law and institutional policy.

Contemporary Developments

Modern classification systems increasingly combine classical models with representation learning. Kernel methods remain valuable when datasets are moderate in size, feature engineering is meaningful and strong nonlinear performance is required without training a large neural network. Approximate kernel methods, random Fourier features and scalable linear solvers extend their use to larger datasets. Automated machine-learning systems can compare classifiers, but automation does not remove the need for leakage control, calibration, fairness evaluation or human accountability.

Chapter Summary

Classification learns a mapping from feature vectors to discrete labels and may also estimate class probabilities. Logistic regression models a linear relationship on the log-odds scale and provides an interpretable baseline. k-NN uses local distances and requires careful scaling and selection of k. Naïve Bayes applies Bayes' theorem with a conditional-independence assumption and is particularly effective for some sparse, high-dimensional problems. SVMs maximise a separating margin; soft margins use slack variables and the parameter C to control regularisation.

Kernel functions enable nonlinear decision boundaries by computing inner products in an implicit feature space. Evaluation must distinguish discrimination, threshold-dependent classification and calibration. Precision, recall, specificity, F1, ROC analysis, precision–recall analysis and log loss answer different questions. Multiclass prediction can use one-vs-rest, one-vs-one or multinomial formulations. In professional systems, model selection must incorporate leakage prevention, class imbalance, probability quality, fairness, privacy, interpretability, monitoring and the consequences of errors.

Key Terms

Classification: Assigning observations to discrete outcome classes.

Decision boundary: The set of input values where a classifier changes its predicted class.

Discriminative model: A model that directly estimates a decision function or conditional distribution.

Generative model: A model that represents how features arise within each class.

Logistic regression: A model using the sigmoid function to estimate binary-class probability.

Log-odds: The logarithm of the odds, log(p/(1−p)).

Regularisation: A constraint or penalty used to control model complexity.

k-nearest neighbours: An instance-based classifier using the labels of nearby observations.

Curse of dimensionality: The degradation of distance and density methods as dimensionality increases.

Naïve Bayes: A Bayesian classifier using conditional independence of features given the class.

Support vector: An observation that influences the maximum-margin SVM solution.

Margin: The geometric separation between a classifier's supporting boundaries.

Slack variable: A nonnegative variable permitting SVM margin violations.

Kernel: A function representing an inner product in a transformed feature space.

RBF kernel: A Gaussian kernel producing locality-sensitive nonlinear relationships.

Calibration: Agreement between predicted probabilities and observed frequencies.

Precision: The proportion of predicted positives that are true positives.

Recall: The proportion of actual positives detected by the classifier.

One-vs-rest: A multiclass strategy training one binary model per class against all others.

Data leakage: Use of information unavailable at prediction time or improperly drawn from evaluation data.

Review Questions

Short Answer Questions

1. What is a decision boundary, and how does it differ between a linear and nonlinear classifier?
2. Why must features commonly be scaled before using k-nearest neighbours?
3. State the conditional-independence assumption of naïve Bayes.
4. What role do support vectors play in an SVM?
5. Distinguish discrimination from probability calibration.

Long Answer Questions

1. Explain logistic regression from the linear score through the sigmoid probability, including coefficient interpretation and regularisation.
2. Compare k-NN, naïve Bayes, logistic regression and SVM in terms of assumptions, computation, interpretability and likely use cases.
3. Derive the relationship between the SVM weight norm and the geometric margin, and explain the purpose of slack variables.
4. Explain how linear, polynomial and RBF kernels produce different modelling capabilities and discuss the importance of hyperparameter selection.
5. Describe a leakage-resistant workflow for evaluating an imbalanced binary classifier whose probabilities will support operational decisions.

Analytical / Application Questions

1. A medical screening system has a high cost for missed cases and a lower cost for unnecessary referrals. Which evaluation metrics and threshold strategy should be used, and why?
2. A text classifier performs well in accuracy but produces extreme probabilities that are often incorrect. Explain how you would investigate and improve the system.
3. A five-class SVM is to be implemented using one-vs-one classification. How many binary models are required, and what practical trade-offs does this strategy create?

Multiple Choice Questions with Answers

Question 1

In logistic regression, what does the sigmoid function primarily do?

A. Transforms a linear score into a value between 0 and 1

B. Selects the k closest training observations

C. Maximises the geometric margin

D. Computes a Euclidean distance

Correct Answer: A. Transforms a linear score into a value between 0 and 1

Question 2

For an unweighted binary k-NN classifier, the local class probability is estimated as:

A. The product of all feature likelihoods

B. The proportion of the k neighbours belonging to the class

C. The inverse of the feature variance

D. The average of all training labels regardless of distance

Correct Answer: B. The proportion of the k neighbours belonging to the class

Question 3

Which assumption is central to naïve Bayes?

A. All classes have equal prior probability

B. All features are normally distributed in every application

C. Features are conditionally independent given the class

D. The classes must be linearly separable

Correct Answer: C. Features are conditionally independent given the class

Question 4

What is the main objective of a hard-margin SVM?

A. Maximise the number of features

B. Minimise the number of classes

C. Maximise the separating margin

D. Force all probabilities to equal 0.5

Correct Answer: C. Maximise the separating margin

Question 5

In an RBF kernel, increasing γ generally makes the influence of each training point:

A. More local

B. Exactly linear

C. Independent of distance

D. Uniform across the feature space

Correct Answer: A. More local

Question 6

Which metric is especially concerned with the proportion of predicted positives that are actually positive?

A. Recall

B. Specificity

C. Precision

D. Accuracy

Correct Answer: C. Precision

Question 7

A calibrated group of predictions assigned probability 0.8 should, approximately, contain what fraction of positive outcomes?

A. 8%

B. 20%

C. 50%

D. 80%

Correct Answer: D. 80%

Question 8

How many one-vs-one binary classifiers are required for five classes?

A. 5

B. 10

C. 15

D. 25

Correct Answer: B. 10

Question 9

Why is fitting a scaler on the complete dataset before cross-validation problematic?

A. It makes all features categorical

B. It causes the model to have no intercept

C. It can leak validation information into the training process

D. It guarantees underfitting

Correct Answer: C. It can leak validation information into the training process

Question 10

Which multiclass strategy trains one classifier for each class against all remaining classes?

A. One-vs-rest

B. One-vs-one

C. Pairwise coupling only

D. Nearest-centroid elimination

Correct Answer: A. One-vs-rest