Classification and Kernel Methods

Introduction

Classification is the supervised-learning task of assigning an observation to one of a finite set of classes. A classifier estimates a relationship between input variables and a categorical response, then uses that relationship to support a decision. Applications include fraud screening, medical diagnosis, credit-risk assessment, document categorisation, fault detection and image recognition.

Classification has two distinct aspects. First, a model estimates class membership, such as the probability that a transaction is fraudulent. Second, a decision rule converts that estimate into an action, such as blocking or approving the transaction. Separating estimation from decision-making is essential when classes are imbalanced, errors have unequal costs, or predicted probabilities must be calibrated.

This chapter develops logistic regression, naïve Bayes, nearest-neighbour methods, support vector machines (SVMs) and kernel methods. It also examines feature scaling, regularisation, class imbalance, thresholds, calibration and cost-sensitive classification.

Learning Objectives

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

1. Explain the distinction between discriminative and generative classification.
2. Construct and interpret logistic-regression models.
3. Apply Bayes’ rule and the naïve Bayes assumption.
4. Use nearest-neighbour methods and analyse their computational behaviour.
5. Explain maximum-margin classification and the role of support vectors.
6. Select and interpret linear and nonlinear kernels.
7. Evaluate classifiers using metrics appropriate to imbalance and decision costs.
8. Calibrate probabilities and choose operational thresholds responsibly.

1. Classification as Estimation and Decision

Let an observation be represented by a feature vector [[M:x ∈ ℝ^p]], and let its class label be [[M:y ∈ {1,…,K}]]. A classifier may produce either a predicted class [[M:ŷ]], a score, or estimated posterior probabilities [[M:P(y=k|x)]].

For binary classification, write the positive class as 1 and the negative class as 0. A general threshold rule is

Here [[M:s(x)]] is a score or estimated probability and [[M:τ]] is the decision threshold. The threshold need not be 0.5. It should reflect prevalence, error costs, capacity constraints and the consequences of action.

A confusion matrix records decisions against actual outcomes:

Accuracy is [[M:(TP+TN)/(TP+TN+FP+FN)]]. It can be misleading when one class is rare. Precision, recall and specificity are

Precision is also called positive predictive value; recall is also called sensitivity. The F1 score is the harmonic mean of precision and recall:

These metrics assume binary labels and nonnegative denominators. If a denominator is zero, the corresponding metric is undefined and the reporting convention must be stated.

The receiver operating characteristic (ROC) curve plots true-positive rate against false-positive rate, where [[M:FPR=FP/(FP+TN)]], over thresholds. The area under the ROC curve (ROC-AUC) measures ranking ability, but does not itself select an operating threshold. Precision–recall curves are often more informative when the positive class is rare.

2. Logistic Regression

2.1 Model and interpretation

Logistic regression is a discriminative model for conditional class probability. For binary classification, let [[M:x=(x₁,…,x_p)]] and let [[M:β₀]] be an intercept. The linear predictor is

The logistic function maps any real number to the interval (0,1):

Equivalently, logistic regression assumes that the log-odds are linear in the features:

The coefficients are interpreted on the log-odds scale. Holding all other features fixed, increasing [[M:x_j]] by one unit changes the log-odds by [[M:β_j]] and multiplies the odds by [[M:e^{β_j}]]. This interpretation depends on the feature’s unit and on the linearity assumption in the log-odds.

With the default threshold 0.5, a prediction is positive when [[M:z≥0]], because [[M:σ(z)≥0.5]] exactly when [[M:z≥0]]. A different threshold changes decisions without necessarily changing fitted coefficients.

2.2 Estimation and regularisation

For independent observations [[M:(x_i,y_i)]], maximum likelihood estimates parameters by maximising the Bernoulli likelihood:

It is computationally more convenient to minimise the negative log-likelihood, also called log loss or cross-entropy:

A regularised objective can be written as

where [[M:λ≥0]] controls penalty strength and [[M:Ω(β)]] is a penalty. L2 regularisation uses [[M:Ω(β)=½∑_{j=1}^p β_j²]] and shrinks coefficients smoothly. L1 regularisation uses [[M:Ω(β)=∑_{j=1}^p |β_j|]] and can produce exact zero coefficients, supporting sparse feature selection. The intercept is commonly excluded from the penalty, although implementations differ.

Regularisation reduces variance but introduces bias. [[M:λ]] should be selected using validation or cross-validation within the training data; test data must remain untouched until final evaluation. Numerical optimisation is usually performed with gradient-based methods or specialised convex solvers. Logistic loss with L1 or L2 penalties is convex, so a global optimum exists under standard conditions, although unregularised estimates can fail to be finite under complete separation.

2.3 Worked example

Suppose a fitted model has [[M:z=−1.2+0.8x₁−0.4x₂]]. For an observation with [[M:x₁=2]] and [[M:x₂=1]],

[[M:z=−1.2+0.8(2)−0.4(1)=0.0]]. Therefore,

[[M:P(y=1|x)=1/(1+e^0)=0.5]].

At threshold 0.5 the observation is classified as positive. Increasing [[M:x₁]] by one unit, holding [[M:x₂]] fixed, multiplies the odds by [[M:e^{0.8}≈2.23]], not the probability by 2.23.

3. Naïve Bayes

3.1 Bayes’ rule and conditional independence

Bayes’ rule expresses posterior class probability as

The prior [[M:P(y=k)]] represents class prevalence. The likelihood [[M:P(x|y=k)]] describes feature values under class [[M:k]]. The evidence [[M:P(x)]] normalises the probabilities.

Naïve Bayes assumes conditional independence of features given the class:

The assumption is often false, but the resulting classifier can still perform well, particularly with high-dimensional sparse text data. Since [[M:P(x)]] is common to all classes, prediction can use

In practice, log probabilities are used to avoid underflow:

3.2 Variants and smoothing

Gaussian naïve Bayes models each continuous feature conditionally as a normal distribution with class-specific mean and variance. Multinomial naïve Bayes is common for nonnegative count features such as word frequencies. Bernoulli naïve Bayes models binary feature presence.

Zero counts can make a likelihood zero. Laplace smoothing replaces a count [[M:N_{jk}]] by [[M:N_{jk}+α]], where [[M:α>0]] is a smoothing parameter. For a categorical feature with [[M:V]] possible values and class total [[M:N_k]],

Smoothing reduces sensitivity to unseen categories but changes estimated probabilities. Naïve Bayes probabilities are therefore often poorly calibrated even when classification accuracy is strong.

4. Nearest-Neighbour Classification

The k-nearest-neighbour (k-NN) method stores the training data. For a query point, it identifies the [[M:k]] closest training observations and predicts the majority class. A distance-weighted version gives nearer observations greater influence.

For standardised Euclidean distance,

Standardisation is important when features have different units or scales. A common transformation is [[M:x′_j=(x_j−μ_j)/σ_j]], where [[M:μ_j]] and [[M:σ_j]] are calculated using training data only. Other distances, such as Manhattan distance, may be more appropriate for particular data geometries.

Small [[M:k]] gives low bias and high variance; large [[M:k]] gives smoother, more biased predictions. The value of [[M:k]] should be selected by validation. In high dimensions, distances become less discriminative, a phenomenon associated with the curse of dimensionality. Feature selection, dimensionality reduction and domain-specific representations can help.

Prediction can be expensive because a query may require comparison with many stored observations. Approximate-neighbour structures can reduce latency, but their accuracy and maintenance requirements must be evaluated. k-NN is attractive for its simplicity and local interpretability, but it is sensitive to irrelevant features, missing values, scale and data density.

5. Support Vector Machines

5.1 Linear maximum-margin classification

For linearly separable data, a hyperplane is [[M:wᵀx+b=0]]. The signed score is [[M:f(x)=wᵀx+b]]. The geometric margin is maximised by minimising [[M:½||w||²]] subject to

where [[M:y_i∈{−1,+1}]]. The constraint fixes a scale for [[M:w]] and [[M:b]]. The closest points satisfy equality and are called support vectors.

Real data are often not separable. The soft-margin SVM introduces slack variables [[M:ξ_i≥0]]:

Here [[M:C>0]] controls the trade-off between margin size and training violations. An equivalent hinge-loss formulation is

The SVM score is not automatically a probability. It is a margin-based ranking score and requires calibration if probabilities are needed.

5.2 Class imbalance and weighted SVMs

If positive errors are more important or positives are rare, separate penalties can be used. A weighted formulation replaces [[M:C]] with [[M:C_+]] for positive examples and [[M:C_-]] for negative examples. Larger class weight penalises violations more strongly. Class weights should reflect both statistical imbalance and operational costs, not merely be applied mechanically.

6. Kernel Methods

6.1 The kernel idea

A nonlinear classifier can become linear after mapping inputs into a feature space [[M:φ(x)]]. The kernel trick avoids explicitly computing that potentially high-dimensional mapping by using

A valid positive-semidefinite kernel generates a Gram matrix whose quadratic form is nonnegative. This condition supports optimisation and corresponds to an inner product in a feature space.

Common kernels include:

For the RBF kernel, [[M:γ>0]] controls locality. A large [[M:γ]] produces narrow, highly local influence and can overfit; a small value produces smoother boundaries. Parameters such as [[M:C]], [[M:γ]] and polynomial degree should be selected jointly through nested or carefully controlled cross-validation.

Kernel SVMs can be powerful on moderate-sized datasets but may have substantial memory and computational costs because the Gram matrix grows with the number of training observations. Linear SVMs, approximation methods, random Fourier features and specialised solvers are alternatives for large-scale problems.

7. Imbalance, Thresholds, Calibration and Costs

7.1 Class imbalance

Imbalance occurs when class frequencies differ substantially. It does not automatically make a problem invalid, but it changes the meaning of metrics and may cause a learner to favour the majority class. Appropriate responses include stratified splitting, class-weighted loss, careful resampling, anomaly-detection formulations and collecting more minority examples.

Oversampling must be performed inside each training fold. Otherwise, duplicated or synthetic information can leak into validation data. Synthetic methods such as SMOTE should be applied only to training partitions and should be assessed for plausibility and subgroup effects.

7.2 Threshold selection and expected cost

Let [[M:C_{FP}]] be the cost of a false positive and [[M:C_{FN}]] the cost of a false negative. If the model outputs a calibrated probability [[M:p=P(y=1|x)]], predicting positive has expected cost [[M:C_{FP}(1−p)]], while predicting negative has expected cost [[M:C_{FN}p]]. Predict positive when the former is no greater than the latter:

Thus the cost-minimising threshold is

This simplified threshold assumes calibrated probabilities, no action-dependent benefits, and equal consideration of other operational constraints. If class priors or sampling schemes differ between development and deployment, probabilities and costs must be aligned to the deployment population.

7.3 Calibration

A classifier is calibrated if, among cases assigned probability approximately [[M:q]], the observed event frequency is approximately [[M:q]]. Reliability diagrams, calibration curves and the Brier score are useful tools. For binary outcomes, the Brier score is

Lower values are better, although the score reflects both calibration and refinement. Platt scaling fits a logistic transformation to validation scores; isotonic regression fits a flexible monotonic mapping. Calibration must use data separate from model fitting, preferably through cross-validation, and must be rechecked after changes in prevalence or data generation.

8. Model Development and Evaluation Workflow

A defensible workflow is as follows:

1. Define the target, prediction horizon, intervention and costs.
2. Inspect label quality, missingness, prevalence and possible leakage.
3. Split data by time, entity or group when random splitting would allow information to cross the deployment boundary.
4. Build a simple baseline, such as a prevalence predictor or regularised logistic regression.
5. Fit candidate models using pipelines that contain preprocessing, feature selection and resampling.
6. Tune hyperparameters using validation or nested cross-validation.
7. Evaluate discrimination, calibration, confusion-matrix metrics and decision utility.
8. Select a threshold using a validation set and stated operational constraints.
9. Test once on a protected holdout set, then monitor post-deployment drift.

Performance should be reported with uncertainty where feasible. Confidence intervals may be obtained by bootstrap resampling, but resampling must respect dependence structures such as patients, customers or time periods. A high ROC-AUC does not guarantee useful precision, calibration or fairness at the chosen operating point.

9. Illustrative Case: Fraud Screening in Digital Payments

Background

A payment platform wants to identify potentially fraudulent card transactions before settlement. Fraud represents 0.3% of transactions. Blocking a legitimate transaction costs approximately 2 monetary units in customer service and lost trust. Allowing a fraudulent transaction costs an estimated 120 monetary units.

Problem

A model that predicts “legitimate” for every transaction achieves 99.7% accuracy but detects no fraud. The platform needs a ranking model, an operational threshold and a monitoring plan.

Analysis

Candidate models include regularised logistic regression for transparent baseline analysis, naïve Bayes for text-like merchant descriptors, a linear or RBF SVM for nonlinear boundaries and k-NN for local comparisons. Features include amount, merchant history, device signals and time patterns. Preprocessing is placed inside a time-aware validation pipeline. Random splitting is avoided because the same device or account may appear in both training and validation periods.

Because false negatives are much more expensive than false positives, accuracy is unsuitable as the principal metric. Precision–recall curves, recall at a fixed review capacity, expected cost and calibration are reported. Class weights are considered, but they are not treated as a substitute for threshold selection.

Approach and solution

Suppose calibrated probabilities are used and costs are [[M:C_FP=2]] and [[M:C_FN=120]]. The cost-based threshold is

[[M:τ=2/(2+120)=2/122≈0.0164]].

This low threshold is not an assertion that 1.64% probability means fraud is common; it reflects the asymmetric costs. In practice, a manual-review capacity constraint may require a different threshold. The team therefore compares the cost threshold with thresholds selected to review, for example, the highest-risk 0.5% of transactions.

A logistic model provides a transparent baseline. An RBF SVM improves ranking on validation data but initially produces poorly calibrated scores. Isotonic calibration is fitted on temporally later validation data. The final threshold is chosen on a separate decision-validation period, and the untouched test period is used for final estimation.

Outcome

The selected system sends a small high-risk group to review and automatically approves low-risk transactions. Monitoring tracks precision, recall, review volume, calibration, subgroup error rates, changes in fraud prevalence and drift in device and merchant features. Review outcomes are fed back only after label maturity, since fraud labels may arrive weeks after a transaction.

Learning points

The case illustrates that classification is a complete decision system rather than merely a model. Imbalance makes accuracy deceptive; probability quality matters for cost decisions; threshold selection depends on capacity and costs; temporal validation is essential; and monitoring must account for delayed labels and adversarial adaptation.

10. Limitations, Governance and Contemporary Practice

No classifier is universally best. Logistic regression is interpretable and often well calibrated after appropriate processing, but its linear log-odds assumption may be restrictive. Naïve Bayes is fast and effective in suitable feature spaces, but conditional independence and probability calibration can be weak. k-NN is intuitive but suffers from scaling, storage and high-dimensionality problems. SVMs can generalise strongly with appropriate margins and kernels, but tuning, calibration and scalability require care.

Feature leakage, biased labels and selective measurement can produce apparently strong but invalid models. In healthcare, a diagnosis label may reflect access to care rather than underlying disease. In lending, historical decisions may encode discriminatory practices. Governance therefore requires documentation of data provenance, intended use, limitations, performance by relevant groups, human oversight and appeal mechanisms.

Fairness cannot be inferred from one metric. Equalised error rates, predictive parity and calibration can conflict when base rates differ. The appropriate analysis depends on law, institutional policy, causal assumptions and the consequences of errors. Sensitive attributes may be needed for auditing even when they are excluded from prediction, subject to privacy and governance requirements.

Modern practice increasingly combines interpretable baselines with nonlinear models, uncertainty estimates, drift detection and decision-curve analysis. Automated machine-learning tools can accelerate experimentation but do not remove the need for leakage control, validation design, calibration, threshold governance and domain review.

Chapter Summary

Classification estimates class membership and converts estimates into decisions through thresholds. Logistic regression models conditional probability using a linear log-odds relationship and supports L1 or L2 regularisation. Naïve Bayes applies Bayes’ rule with conditional feature independence and is especially useful for fast, high-dimensional problems. k-NN makes local predictions based on a chosen distance and requires careful scaling and selection of [[M:k]]. SVMs maximise a margin, use hinge loss in the soft-margin case and can represent nonlinear boundaries through valid kernels. Kernel choice and hyperparameters control the geometry and complexity of the decision function.

Reliable classification requires more than selecting an algorithm. Imbalance demands suitable metrics and leakage-free resampling. Thresholds should reflect costs and operational capacity. Calibration is necessary when probabilities drive decisions, and evaluation should include discrimination, calibration, utility, subgroup performance and temporal robustness. Ethical deployment requires attention to labels, privacy, fairness, documentation, human oversight and post-deployment monitoring.

Key Terms

Classification: Assignment of observations to categorical classes.

Discriminative model: Model that estimates a decision boundary or conditional distribution directly.

Generative model: Model that represents how features arise within each class and combines this with class priors.

Logistic regression: A model whose log-odds are linear in the features.

Logit: The logarithm of odds, [[M:log(p/(1−p))]].

Regularisation: Addition of a penalty that controls model complexity.

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

Laplace smoothing: Adjustment that prevents zero probability estimates for unseen categories.

Nearest neighbour: Training observation used as a local reference for prediction.

Support vector: Observation defining or influencing an SVM margin.

Margin: Distance-related separation between a classifier boundary and observations.

Hinge loss: SVM loss [[M:max(0,1−yf(x))]].

Kernel: Function representing an inner product in a feature space.

RBF kernel: Gaussian-like kernel producing local nonlinear similarity.

Class imbalance: Unequal prevalence of classes in a dataset.

Calibration: Agreement between predicted probabilities and observed frequencies.

Threshold: Score or probability value separating predicted classes.

Precision: Fraction of predicted positives that are actually positive.

Recall: Fraction of actual positives that are detected.

Cost-sensitive classification: Classification in which errors have explicitly unequal consequences.

Review Questions

Short Answer Questions

1. Why can accuracy be misleading for a highly imbalanced classification problem?
2. Interpret a positive coefficient in logistic regression on the odds scale.
3. State the conditional-independence assumption made by naïve Bayes.
4. Why should features generally be scaled before Euclidean k-NN?
5. What is the role of support vectors in an SVM?

Long Answer Questions

1. Explain logistic regression from its linear predictor through probability estimation, likelihood, regularisation and thresholding.
2. Compare naïve Bayes, k-NN and logistic regression in terms of assumptions, computational behaviour, interpretability and calibration.
3. Derive the soft-margin SVM formulation and explain the roles of slack variables and [[M:C]].
4. Explain the kernel trick, positive-semidefinite kernels and the effects of [[M:γ]] in an RBF kernel.
5. Design a leakage-resistant evaluation protocol for an imbalanced, time-dependent fraud-classification problem.

Analytical / Application Questions

1. A medical screening model has [[M:C_FP=1]] and [[M:C_FN=19]]. Assuming calibrated probabilities and no capacity constraint, derive the cost-minimising probability threshold and explain its operational meaning.
2. A classifier has excellent ROC-AUC but poor precision at the deployment prevalence. Analyse at least three possible reasons and propose an evaluation and remediation plan.
3. For a customer-retention dataset containing age, income and account tenure in different units, design a comparison between logistic regression, k-NN and an RBF SVM. Specify preprocessing, validation, metrics, calibration and threshold selection.

Multiple Choice Questions with Answers

Question 1

Which expression gives the logistic-regression probability for a linear score z?

A. [[M:1/(1+e^(−z))]]

B. [[M:e^z]]

C. [[M:z/(1+z)]]

D. [[M:1−z]]

Correct Answer: A. [[M:1/(1+e^(−z))]]

Question 2

In logistic regression, increasing feature x_j by one unit while holding other features fixed multiplies the odds by:

A. [[M:β_j]]

B. [[M:e^{β_j}]]

C. [[M:1−β_j]]

D. [[M:β_j²]]

Correct Answer: B. [[M:e^{β_j}]]

Question 3

Which assumption is central to naïve Bayes?

A. Features are marginally independent

B. Classes have equal prevalence

C. Features are conditionally independent given the class

D. All features are normally distributed

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

Question 4

Why is feature scaling important for Euclidean k-NN?

A. It guarantees linear separability

B. It prevents large-unit features from dominating distance

C. It removes the need to choose k

D. It converts labels into probabilities

Correct Answer: B. It prevents large-unit features from dominating distance

Question 5

In a soft-margin SVM, increasing C generally:

A. Penalises margin violations more strongly

B. Forces every feature coefficient to zero

C. Always increases the margin

D. Removes all support vectors

Correct Answer: A. Penalises margin violations more strongly

Question 6

For an RBF kernel [[M:K(x,x′)=exp(−γ||x−x′||²)]], a larger γ generally produces:

A. More local similarity and potentially a more complex boundary

B. A strictly linear boundary

C. Identical similarity for every pair

D. No dependence on distance

Correct Answer: A. More local similarity and potentially a more complex boundary

Question 7

If TP=80 and FN=20, recall is:

A. 0.20

B. 0.40

C. 0.80

D. 0.90

Correct Answer: C. 0.80

Question 8

With calibrated probability p, false-positive cost [[M:C_FP]] and false-negative cost [[M:C_FN]], the simplified cost-minimising threshold is:

A. [[M:C_FN/(C_FP+C_FN)]]

B. [[M:C_FP/(C_FP+C_FN)]]

C. [[M:C_FP−C_FN]]

D. [[M:C_FP×C_FN]]

Correct Answer: B. [[M:C_FP/(C_FP+C_FN)]]

Question 9

Which statement about ROC-AUC is correct?

A. It directly specifies the deployment threshold

B. It measures ranking performance across thresholds

C. It guarantees calibrated probabilities

D. It is unaffected by all prevalence changes

Correct Answer: B. It measures ranking performance across thresholds

Question 10

When oversampling is used with cross-validation, best practice is to:

A. Oversample before splitting all data

B. Apply oversampling separately inside each training fold

C. Oversample only the test fold

D. Use oversampling instead of validation

Correct Answer: B. Apply oversampling separately inside each training fold