12. Similarity, Kernels and Dimensionality Reduction

Introduction and Context

Machine-learning systems rarely operate directly on isolated variables. They compare observations, identify neighbourhoods, detect directions of variation, and construct representations in which prediction becomes easier. These operations depend on a central mathematical question: when should two observations be considered similar?

For a set of observations represented by vectors, similarity may be based on distance, angle, correlation, or a learned relationship. The choice is not merely computational. It expresses assumptions about the data and can determine whether a model recognizes meaningful structure or amplifies irrelevant variation. For example, Euclidean distance may be appropriate for standardized physical measurements, whereas cosine similarity may be more useful for document vectors whose magnitude reflects document length rather than meaning.

Kernel methods extend similarity-based reasoning to nonlinear relationships without explicitly constructing a high-dimensional feature representation. Dimensionality-reduction methods, in turn, seek compact representations that preserve information, neighbourhoods, or task-relevant structure. Principal component analysis (PCA) provides a linear algebraic foundation, while manifold learning and embedding methods address data whose geometry is intrinsically nonlinear.

This chapter develops these ideas as connected tools. It begins with distances and similarity measures, proceeds to positive semidefinite kernels and reproducing-kernel Hilbert spaces, and then examines PCA, nonlinear embeddings, practical workflows, limitations, and professional applications.

Learning Objectives

After completing this chapter, the learner should be able to:

1. Distinguish distance, similarity, dissimilarity, and metric properties.

2. Select and interpret Euclidean, Manhattan, Mahalanobis, cosine, and correlation-based measures.

3. Explain kernel functions, Gram matrices, positive semidefiniteness, and the kernel trick.

4. Describe the role of reproducing-kernel Hilbert spaces in kernel learning.

5. Derive the principal steps of PCA using covariance matrices and singular value decomposition.

6. Compare PCA with nonlinear manifold and embedding methods.

7. Diagnose scaling, dimensionality, sparsity, and hyperparameter problems.

8. Apply similarity and dimensionality-reduction methods responsibly in machine-learning workflows.

Similarity as a Mathematical Assumption

Let observations be vectors $x_i,x_j\in\mathbb{R}^d$. A distance function $d(x_i,x_j)$ measures dissimilarity, while a similarity function $s(x_i,x_j)$ measures closeness. A metric satisfies non-negativity, identity of indiscernibles, symmetry, and the triangle inequality. Not every useful dissimilarity is a metric; squared Euclidean distance, for instance, does not satisfy the triangle inequality, although it is extremely useful in optimization.

The most familiar distance is

\[

d_2(x,z)=\sqrt{\sum_{r=1}^{d}(x_r-z_r)^2}.

\]

It treats every coordinate as geometrically comparable. Consequently, units and scale matter. A feature measured in thousands can dominate one measured in fractions. Standardization, $x_r'=(x_r-\mu_r)/\sigma_r$, is therefore often performed before distance-based learning.

The Manhattan or $L_1$ distance is

\[

d_1(x,z)=\sum_r|x_r-z_r|.

\]

It can be more robust to isolated large coordinate differences and is related to sparse modelling. More generally, the Minkowski family is

\[

d_p(x,z)=\left(\sum_r|x_r-z_r|^p\right)^{1/p}.

\]

The Mahalanobis distance incorporates covariance:

\[

d_M(x,z)=\sqrt{(x-z)^T\Sigma^{-1}(x-z)},

\]

where $\Sigma$ is a covariance matrix. Directions with high natural variability are down-weighted, while correlated variables are not counted as independent evidence. In practice, covariance estimation may be unstable when the number of variables is large; regularization or robust covariance estimation may be necessary.

Cosine similarity compares orientation rather than magnitude:

\[

s_{\cos}(x,z)=\frac{x^Tz}{\|x\|\|z\|}.

\]

It is common for text, recommendation, and embedding systems. Two documents containing similar word proportions may have high cosine similarity even if one is much longer. Correlation similarity further removes the effect of feature means and is useful when relative patterns matter more than absolute levels.

Binary and categorical data require special care. Jaccard similarity focuses on shared positive attributes and ignores shared zeros, making it suitable for sparse transaction data. Hamming distance counts coordinate disagreements. Applying Euclidean distance mechanically to nominal categories imposes an artificial numerical order.

In high-dimensional spaces, distances often become less discriminative: the nearest and farthest observations may have increasingly similar distances. This phenomenon, associated with the curse of dimensionality, makes feature selection, normalization, metric learning, or representation learning important. Similarity is therefore a modelling decision, not a neutral preprocessing detail.

Kernels: Similarity with Nonlinear Reach

A kernel is a function $k(x,z)$ that evaluates an inner product in some feature space:

\[

k(x,z)=\langle\phi(x),\phi(z)\rangle_{\mathcal H},

\]

where $\phi$ maps the input into a possibly high- or infinite-dimensional space $\mathcal H$. The key advantage is that algorithms needing only inner products can use $k(x,z)$ directly, without explicitly computing $\phi(x)$.

The Gram matrix for observations $x_1,\ldots,x_n$ is $K\in\mathbb{R}^{n\times n}$ with entries $K_{ij}=k(x_i,x_j)$. A valid positive semidefinite (PSD) kernel satisfies

\[

a^TKa\geq 0

\]

for every vector $a$ and every finite sample. Equivalently, it behaves as an inner-product matrix in a Hilbert space. This condition prevents the similarity representation from assigning inconsistent geometry.

Important kernels include:

• Linear: $k(x,z)=x^Tz$.
• Polynomial: $k(x,z)=(x^Tz+c)^p$, with suitable $c$ and integer degree $p$.
• Gaussian radial basis function (RBF): $k(x,z)=\exp(-\|x-z\|^2/(2\sigma^2))$.
• Laplacian: $k(x,z)=\exp(-\|x-z\|_1/\sigma)$.
• Sigmoid: $k(x,z)=\tanh(\alpha x^Tz+c)$, valid only for appropriate parameter ranges.

The RBF kernel assigns high similarity to nearby observations and low similarity to distant observations. The bandwidth $\sigma$ controls locality. A very small bandwidth produces highly localized similarities and may overfit; a very large bandwidth makes most observations appear similar and may underfit.

Kernel methods are used in support vector machines, kernel ridge regression, kernel principal component analysis, Gaussian processes, spectral clustering, and several forms of metric learning. In a kernelized algorithm, the data often appear only through pairwise inner products. Replacing $x_i^Tx_j$ with $k(x_i,x_j)$ is called the kernel trick.

Reproducing-Kernel Hilbert Spaces

A reproducing-kernel Hilbert space (RKHS) is a Hilbert space of functions in which evaluation is continuous. Each input $x$ is associated with a function $k(x,\cdot)$, and the reproducing property is

\[

f(x)=\langle f,k(x,\cdot)\rangle_{\mathcal H}.

\]

This relationship turns pointwise prediction into an inner-product operation. Under the representer theorem, many regularized learning problems have solutions of the form

\[

f(\cdot)=\sum_{i=1}^{n}\alpha_i k(x_i,\cdot).

\]

Thus, even when the function space is infinite-dimensional, estimation reduces to finding a finite set of coefficients.

For example, kernel ridge regression minimizes

\[

\sum_{i=1}^{n}(y_i-f(x_i))^2+\lambda\|f\|_{\mathcal H}^2.

\]

The first term fits the observations; the RKHS norm penalizes function complexity. The regularization parameter $\lambda$ controls the bias–variance trade-off. Kernel methods consequently combine flexible nonlinear representations with explicit control of complexity.

Kernel choice should reflect domain structure. A kernel is not automatically superior because it is nonlinear. It can fail when its notion of proximity conflicts with the application, when hyperparameters are poorly selected, or when the Gram matrix is too expensive to store. Standard kernel algorithms commonly require $O(n^2)$ memory and between $O(n^2)$ and $O(n^3)$ computation, motivating low-rank approximations, random Fourier features, Nyström approximations, or scalable neural representations.

Principal Component Analysis: A Linear Geometry of Variation

PCA seeks orthogonal directions that capture maximum variance. Let the centred data matrix be $X\in\mathbb{R}^{n\times d}$. Its sample covariance matrix is

\[

S=\frac{1}{n-1}X^TX.

\]

The first principal direction solves

\[

\max_{\|w\|=1} w^TSw.

\]

Using a Lagrange multiplier shows that $w$ is the eigenvector associated with the largest eigenvalue of $S$. Subsequent directions are orthogonal eigenvectors with descending eigenvalues.

If $S=V\Lambda V^T$, the transformed coordinates are $Z=XV$. Retaining the first $q$ columns gives a $q$-dimensional representation. The fraction of variance explained is

\[

\frac{\sum_{j=1}^{q}\lambda_j}{\sum_{j=1}^{d}\lambda_j}.

\]

PCA also gives the best rank-$q$ approximation to the centred data under squared Frobenius reconstruction error. This property explains its use in compression, denoising, visualization, and preprocessing.

PCA can be computed through singular value decomposition, $X=U\Sigma V^T$. The columns of $V$ are principal directions, and the singular values determine explained variance. SVD is often numerically preferable, especially when $d$ or $n$ is large.

PCA is sensitive to scale and outliers. PCA on covariance is appropriate when units and variances are meaningful; PCA on standardized variables effectively uses the correlation matrix and gives each feature equal initial scale. Robust PCA variants separate a low-rank component from sparse corruption. Sparse PCA seeks directions with many zero loadings and can improve interpretability.

PCA is unsupervised. A direction explaining substantial variance may have little relevance to the target variable. Conversely, a low-variance direction may be highly predictive. PCA should therefore be fitted inside the training data during cross-validation rather than on the complete dataset, since fitting it on test observations leaks information.

Beyond Linear Structure: Manifolds and Embeddings

A manifold is a space that may be globally curved but resembles a low-dimensional Euclidean space locally. Images, speech signals, and physical sensor measurements can occupy a small, curved region of a very high-dimensional observation space. The manifold hypothesis states that many real datasets have lower intrinsic dimension than their ambient representation suggests.

PCA preserves global linear variation but cannot unfold a curved surface. Nonlinear dimensionality-reduction methods use different preservation objectives:

Kernel PCA. The data are implicitly mapped through a kernel, and ordinary PCA is performed in the feature space. Kernel centring is essential. If $K$ is the Gram matrix and $H=I-(1/n)\mathbf{1}\mathbf{1}^T$, the centred matrix is $K_c=HKH$. Kernel PCA can reveal nonlinear coordinates, but results depend strongly on the kernel and bandwidth.

Multidimensional scaling (MDS). Classical MDS seeks coordinates whose pairwise Euclidean distances approximate supplied dissimilarities. Metric MDS minimizes a stress function comparing original and embedded distances. It is useful when the starting point is a distance matrix rather than raw features.

Isomap. Isomap estimates geodesic distances along a neighbourhood graph, then applies MDS. It can recover global structure on a smoothly curved manifold, but disconnected or incorrectly connected graphs produce misleading results.

Locally Linear Embedding (LLE). LLE represents each point as a weighted combination of its neighbours and finds low-dimensional coordinates preserving those weights. It emphasizes local geometry and may distort global relationships.

Laplacian eigenmaps and spectral methods. These methods construct a graph with edge weights representing local similarity and seek coordinates that keep strongly connected points close. Their foundation is the graph Laplacian, which links dimensionality reduction to spectral clustering and semi-supervised learning.

t-SNE. t-distributed stochastic neighbour embedding emphasizes local neighbourhood probabilities and uses a heavy-tailed distribution in the low-dimensional space to reduce crowding. It is primarily a visualization method, not a general-purpose feature transformation. Cluster sizes, global distances, and apparent gaps may not have literal quantitative meaning.

UMAP. Uniform Manifold Approximation and Projection constructs a graph-based representation using local connectivity and fuzzy set ideas. It is often faster than t-SNE and can preserve more global organization, although its output remains sensitive to parameters and preprocessing.

Autoencoder embeddings. An autoencoder learns an encoder $z=f_\theta(x)$ and decoder $\hat{x}=g_\psi(z)$ by minimizing reconstruction loss. Bottleneck layers produce compact nonlinear representations. Variational autoencoders impose a probabilistic latent structure, while supervised or contrastive objectives can make embeddings more useful for downstream tasks.

No embedding method preserves every property simultaneously. A representation may preserve local neighbourhoods while distorting global distances, or reconstruct inputs accurately while discarding predictive information. The objective must therefore be stated before selecting a method.

A Practical Workflow for Similarity and Reduction

A reliable workflow begins with the intended use. Visualization, nearest-neighbour retrieval, compression, clustering, and prediction require different preservation criteria. The analyst should then inspect variable types, missingness, sparsity, scale, outliers, and sample size.

Preprocessing must be fitted only on training data. Numerical variables may be standardized or robustly scaled; sparse text vectors may be normalized by length; categorical variables may require specialized encodings. The similarity measure should be tested against domain knowledge. A useful diagnostic is to inspect nearest neighbours and ask whether they are semantically plausible.

For PCA, examine the eigenvalue spectrum, cumulative explained variance, reconstruction error, and loading interpretability. For kernel or graph methods, inspect bandwidth, number of neighbours, graph connectivity, and stability across random seeds. Embeddings should be evaluated with quantitative measures such as trustworthiness, continuity, neighbourhood preservation, reconstruction error, downstream validation performance, and stability—not only by visual appeal.

Dimensionality reduction should be embedded in the modelling pipeline. For supervised learning, select the number of components or kernel parameters using validation data. For deployment, preserve the fitted transformation and apply exactly the same centring, scaling, feature ordering, and parameters to incoming data.

Applications Across AI and Industry

In computer vision, similarity between image embeddings supports image retrieval, duplicate detection, and few-shot classification. Kernel methods can be effective when datasets are moderate in size and engineered features have strong structure. In natural-language processing, TF–IDF vectors commonly use cosine similarity, while modern language embeddings are compared using normalized dot products.

In finance, Mahalanobis distance can flag multivariate anomalies, although covariance estimation and changing market regimes require caution. In manufacturing, PCA-based monitoring identifies deviations from normal process variation; reconstruction residuals can serve as fault indicators. In bioinformatics, kernel methods compare structured biological objects, while manifold embeddings assist exploratory analysis of gene-expression profiles.

Recommendation systems use latent factors and similarity spaces to identify users or items with related preferences. In cybersecurity, graph-based embeddings and distance-based anomaly detection can expose unusual communication patterns. In healthcare, dimensionality reduction may summarize high-dimensional signals, but interpretability, uncertainty, and fairness are essential because a visually persuasive embedding is not clinical evidence.

Illustrative Case Study: Detecting Manufacturing Anomalies

Background. A plant records temperature, vibration, pressure, acoustic, and electrical measurements from each production cycle. The sensors have different units, correlated readings, and occasional missing values. Only a small number of failures have been labelled.

Problem. Engineers need an early-warning system that identifies abnormal cycles without generating excessive false alarms.

Analysis. The team first imputes missing values using a training-only procedure and robustly scales the variables. Correlation inspection shows that several sensors measure related physical effects. PCA is fitted to verified normal training cycles. The first components capture ordinary operating modes, while reconstruction residuals indicate observations poorly represented by the normal low-dimensional subspace.

Because some failures are nonlinear, the team also evaluates an RBF-kernel similarity model and a graph-based local-neighbourhood score. Hyperparameters are selected using time-ordered validation rather than random mixing, since operating conditions drift over time. Engineers review nearest neighbours and high-residual cycles to distinguish genuine faults from sensor maintenance events.

Approach. The deployed system combines a PCA reconstruction score, a robust distance in the retained component space, and a rule requiring persistent abnormality across consecutive cycles. A dashboard reports the contributing sensor groups rather than presenting a black-box alarm alone.

Outcome. The approach provides earlier warnings while reducing alarms caused by single noisy sensors. Its effectiveness is monitored using delayed maintenance outcomes, alarm burden, and stability across production regimes.

Learning points. Scaling and temporal validation are as important as the choice of algorithm. Unsupervised scores require operational thresholds and human review. A compact representation is valuable not simply because it compresses data, but because it supports a defensible decision process.

Limitations, Risks, and Professional Judgement

The curse of dimensionality can weaken neighbourhood meaning and make kernel bandwidth selection difficult. Distances may reflect measurement artefacts rather than semantic similarity. PCA loadings can be unstable when variables are highly correlated or samples are few. Nonlinear embeddings can create apparent clusters through parameter choices, random initialization, or uneven sampling density.

Data leakage is a major practical error: scaling, PCA, imputation, graph construction, or feature selection performed before train–test separation can inflate performance. Another error is treating a two-dimensional visualization as proof of separability. Embeddings are representations, not causal explanations.

Similarity systems can encode social or historical bias. In recruitment, lending, healthcare, and surveillance, a distance or kernel may reproduce patterns that are discriminatory or legally unacceptable. Organizations should document data provenance, feature transformations, kernel choices, validation populations, uncertainty, and human-review procedures. Privacy is also relevant: high-dimensional embeddings may reveal sensitive attributes or enable re-identification even when original variables are removed.

Current Developments and Best Practices

Recent work increasingly combines scalable kernels, approximate nearest-neighbour search, graph learning, contrastive representation learning, and foundation-model embeddings. Random-feature methods approximate shift-invariant kernels with explicit finite vectors. Deep kernel learning learns a representation jointly with a kernel objective. Self-supervised learning constructs similarity through augmentations or positive–negative pairs, making the definition of similarity task dependent.

Best practice is to:

• define what similarity should mean before selecting a formula;
• scale and encode variables consistently with their measurement level;
• fit preprocessing and reduction only on training data;
• compare simple baselines with nonlinear methods;
• tune parameters using validation and assess stability;
• evaluate both geometric quality and downstream utility;
• inspect neighbours, loadings, residuals, and failure cases;
• document computational cost, assumptions, and governance risks.

Chapter Summary

Similarity measures provide the geometry in which machine-learning observations are compared. Euclidean, Manhattan, Mahalanobis, cosine, correlation, Jaccard, and Hamming measures are appropriate for different data structures and assumptions. Kernels generalize inner products through implicit feature maps. Positive semidefinite Gram matrices and RKHS theory explain why kernel algorithms can represent nonlinear functions while retaining regularization and finite computational forms.

PCA finds orthogonal directions of maximum variance and provides optimal linear low-rank reconstruction under squared error. Kernel PCA, MDS, Isomap, LLE, spectral methods, t-SNE, UMAP, and autoencoders address nonlinear or manifold structure, but each preserves different properties. Effective application requires careful preprocessing, validation, stability analysis, interpretation, and attention to leakage, fairness, privacy, and computational cost.

Key Terms

Distance: A function measuring dissimilarity between observations.

Metric: A distance satisfying non-negativity, identity, symmetry, and triangle inequality.

Cosine similarity: Similarity based on the angle between two vectors.

Mahalanobis distance: Covariance-adjusted distance measured relative to the data distribution.

Curse of dimensionality: Degradation of geometric and statistical intuition as dimensionality increases.

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

Gram matrix: Matrix of pairwise kernel evaluations.

Positive semidefinite: A matrix property satisfying $a^TKa\geq0$ for every vector $a$.

Kernel trick: Replacement of explicit inner products by kernel evaluations.

RKHS: A Hilbert space of functions with a reproducing evaluation property.

Representer theorem: Result stating that many regularized solutions are finite kernel expansions.

Regularization: A constraint or penalty controlling model complexity.

PCA: A linear method finding orthogonal maximum-variance directions.

Eigenvalue: A value indicating variance captured by a principal direction.

SVD: Matrix factorization used to compute stable principal components.

Manifold: A locally Euclidean space that may be globally curved.

Intrinsic dimension: The number of degrees of freedom underlying observed data.

Embedding: A mapping of data into a representation space.

Graph Laplacian: A matrix encoding connectivity and smoothness on a graph.

Trustworthiness: A measure of how well local neighbourhoods in an embedding reflect the original data.

Review Questions

Short Answer Questions

1. Why should numerical variables often be standardized before Euclidean distance is computed?

2. State the defining property of a positive semidefinite kernel matrix.

3. What does the bandwidth parameter control in an RBF kernel?

4. Why is PCA sensitive to outliers?

5. Distinguish ambient dimension from intrinsic dimension.

Long Answer Questions

1. Compare Euclidean, Manhattan, Mahalanobis, and cosine measures, giving an appropriate application for each.

2. Explain the kernel trick and the role of the Gram matrix in kernel learning.

3. Derive the PCA optimization problem and explain its eigenvalue solution.

4. Compare PCA, kernel PCA, Isomap, LLE, t-SNE, and UMAP in terms of the structure they aim to preserve.

5. Explain how RKHS regularization and the representer theorem support nonlinear prediction.

Analytical / Application Questions

1. A document collection contains highly sparse TF–IDF vectors of very different lengths. Which similarity measure and normalization would you choose, and why?

2. An embedding shows three visually separated clusters, but a classifier trained on the original data performs poorly. Give at least three explanations and propose validation checks.

3. Design a leakage-resistant anomaly-detection pipeline for multivariate sensor data using PCA and one nonlinear similarity method. Specify preprocessing, validation, evaluation, and governance considerations.

22. Multiple Choice Questions with Answers

Question 1

Which distance is most directly adjusted for correlation and unequal variance among features?

A. Euclidean distance

B. Mahalanobis distance

C. Hamming distance

D. Cosine distance

Correct Answer: B. Mahalanobis distance

Question 2

What condition must a Gram matrix satisfy for a function to be a valid positive semidefinite kernel?

A. Every entry must be positive

B. Its diagonal must contain zeros

C. a^TKa must be nonnegative for every vector a

D. All eigenvalues must be equal

Correct Answer: C. a^TKa must be nonnegative for every vector a

Question 3

What is the principal effect of increasing the bandwidth of an RBF kernel substantially?

A. Most observations become more similarly related

B. The kernel becomes exactly linear

C. All diagonal entries become zero

D. The feature dimension becomes smaller

Correct Answer: A. Most observations become more similarly related

Question 4

PCA selects its first component by maximizing which quantity subject to a unit-norm constraint?

A. Classification accuracy

B. Reconstruction sparsity

C. Projected variance

D. Pairwise categorical agreement

Correct Answer: C. Projected variance

Question 5

Why can PCA fail to reveal a useful predictive direction?

A. PCA always uses labels incorrectly

B. Maximum variance is not necessarily maximum predictive relevance

C. PCA cannot centre data

D. PCA only works with binary variables

Correct Answer: B. Maximum variance is not necessarily maximum predictive relevance

Question 6

Which method primarily emphasizes preserving local neighbourhood probabilities for visualization?

A. t-SNE

B. Ordinary least squares

C. Hamming coding

D. Classical covariance estimation

Correct Answer: A. t-SNE

Question 7

In an RKHS, what does the reproducing property express?

A. A function value can be obtained through an inner product with a kernel function

B. Every kernel must reproduce the original input exactly

C. All functions must be linear in the observed variables

D. The Gram matrix must have rank one

Correct Answer: A. A function value can be obtained through an inner product with a kernel function

Question 8

Which practice prevents preprocessing leakage during model evaluation?

A. Fit scaling and PCA using the complete dataset before splitting

B. Fit all transformations only on the training fold

C. Use test labels to choose the kernel bandwidth

D. Recompute feature order separately for every test observation

Correct Answer: B. Fit all transformations only on the training fold

Question 9

A two-dimensional t-SNE plot shows two large separated groups. Which conclusion is least justified?

A. Some local relationships may be represented distinctly

B. The plot can support exploratory analysis

C. The exact global distance between groups is necessarily meaningful

D. Results should be checked for parameter stability

Correct Answer: C. The exact global distance between groups is necessarily meaningful

Question 10

Why might a manufacturing anomaly system combine PCA residuals with a nonlinear neighbourhood score?

A. To guarantee that no false alarms occur

B. To capture both departures from linear normal structure and nonlinear local irregularities

C. To eliminate the need for validation

D. To make covariance estimation unnecessary in every case

Correct Answer: B. To capture both departures from linear normal structure and nonlinear local irregularities