Cost Functions and Distances - 0. Distance Metrics: The Foundation of Similarity

0. Distance Metrics: The Foundation of Similarity and Discrepancy

Distance metrics are the foundation upon which many cost functions are built. They quantify the similarity or dissimilarity between data points, and they are used in clustering, retrieval, dimensionality reduction, and as building blocks for cost functions. This section provides a comprehensive taxonomy of distance metrics, from the most common (Euclidean, Manhattan) to more specialized measures (Mahalanobis, Levenshtein, Cosine). Understanding these metrics is essential for selecting the right cost function and for interpreting the behavior of machine learning models.

The diagram in Fig 2 visualizes the relationship between different distance metrics and their properties. Each metric is suited for different types of data and applications, and the choice of metric can significantly impact the performance of the model.

This figure provides a comprehensive overview of the major distance metrics used in machine learning. Each metric is designed for a specific type of data and application. Euclidean and Manhattan distances are the most common for continuous feature spaces. Mahalanobis distance accounts for correlations between features, making it useful for multivariate data. Cosine distance is widely used in text processing and high-dimensional sparse data. Levenshtein distance is the standard for string comparison, while Jaccard and Hamming distances are used for sets and binary data. The Earth Mover's (Wasserstein) distance is used for distributions, and KL Divergence, while not a true metric, is fundamental in information theory. The choice of distance metric can significantly impact model performance and must be carefully considered.

0.1 Euclidean Distance (L2 Norm)

The Euclidean distance (also called the L2 norm) is the most common distance metric. It measures the straight-line distance between two points in Euclidean space:

Euclidean distance satisfies all four metric properties. It is intuitive and widely used in clustering (K-means), nearest neighbor search (KNN), and as the basis for the Mean Squared Error cost function. However, Euclidean distance is sensitive to the scale of the features and can be dominated by large values. It also performs poorly in high-dimensional spaces due to the curse of dimensionality, where the distance between points becomes less discriminative. In such cases, other metrics like cosine distance or Mahalanobis distance may be preferred.

Applications: K-means clustering, KNN classification, image retrieval, and as the basis for MSE loss. In wireless communications, the Normalized Mean Squared Error (NMSE) is used as a loss function for training neural networks in signal processing applications (Wang et al., 2020). Euclidean distance is also the standard metric for evaluating regression models in housing price prediction.

0.2 Manhattan Distance (L1 Norm)

The Manhattan distance (also called the L1 norm or city block distance) measures the sum of absolute differences between two points:

Manhattan distance is less sensitive to outliers than Euclidean distance because it does not square the differences. It is the natural distance in grid-like spaces and is used in applications like pathfinding and robotics. Manhattan distance is the basis for the Mean Absolute Error (MAE) cost function. Like Euclidean distance, it satisfies all four metric properties but is also sensitive to feature scaling. It is often preferred when the data has many outliers or when the features are independent and the contribution of each feature should be treated equally.

Applications: Pathfinding, robotics, robust regression (MAE), and as the basis for the Mean Absolute Error cost function. In YOLO object detection, L1 loss is used for bounding box regression to penalize localization errors for the width and height coordinates. The Balanced L1 Loss, an enhanced version, improves robustness and accuracy when object sizes vary significantly (Redmon & Farhadi, 2018). Manhattan distance is also used in radiation therapy dose prediction models like DeepDoseNet (Fan et al., 2019).

0.3 Minkowski Distance

The Minkowski distance is a generalization of both Euclidean and Manhattan distances:

When p = 1, it becomes Manhattan distance; when p = 2, it becomes Euclidean distance. The Minkowski distance is a valid metric for all p ≥ 1. The parameter p controls the sensitivity to large differences; larger values of p emphasize larger differences more strongly. For p → ∞, it becomes the Chebyshev distance, which measures the maximum absolute difference between coordinates. The Minkowski distance is used in various applications where the choice of p allows tuning the sensitivity to outliers and feature scales.

Applications: Generalized nearest neighbor search, clustering with tunable sensitivity to outliers, and distance-based anomaly detection where p can be optimized for the specific data distribution.

0.4 Mahalanobis Distance

The Mahalanobis distance accounts for correlations between features and is scale-invariant:

where S is the covariance matrix of the data. The Mahalanobis distance is particularly useful when the features are correlated and have different scales. It effectively transforms the data into a space where the features are uncorrelated and have unit variance, making the distance measure more meaningful. Mahalanobis distance is used in anomaly detection, multivariate outlier detection, and as a basis for some cost functions. It satisfies all four metric properties when S is positive definite.

Applications: Anomaly detection, multivariate outlier detection, multivariate analysis, and metric learning. In industrial quality control, Mahalanobis distance is used to detect defective products by measuring their deviation from the normal distribution of features (Taguchi & Jugulum, 2002). It is also used in financial fraud detection to identify suspicious transactions that deviate from normal patterns.

0.5 Cosine Similarity and Cosine Distance

The cosine similarity measures the cosine of the angle between two vectors:

The cosine distance is then defined as:

Cosine distance is not a true metric because it does not satisfy the triangle inequality in all cases. However, it is widely used in text processing and high-dimensional sparse data because it is insensitive to the magnitude of the vectors and only considers their direction. This makes it ideal for comparing documents represented as TF-IDF vectors or word embeddings. Cosine distance is used in many information retrieval systems and as a similarity measure in recommendation systems. It is also the basis for some contrastive losses in deep learning.

Applications: Text retrieval, document similarity, recommendation systems, and as a similarity measure in metric learning. In movie recommendation systems, cosine similarity is the primary metric used in KNN-based recommenders, comparing user or item vectors to find similar users or movies (Sarwar et al., 2001). Cosine similarity is also used in hybrid loss functions that combine Bayesian Personalized Ranking with cosine similarity for more accurate recommendations.

0.6 Levenshtein Distance (Edit Distance)

The Levenshtein distance (also called edit distance) measures the minimum number of single-character edits (insertions, deletions, or substitutions) required to transform one string into another. It is defined recursively as:

For two strings a and b of lengths m and n, the Levenshtein distance L(a, b) is:

where $\mathrm{cost}=0$ if $a[0]=b[0]$ and 1 otherwise. The Levenshtein distance is a true metric and is widely used in spell checking, DNA sequence alignment, and natural language processing. It is computationally expensive for long strings (O(mn)), but efficient implementations exist using dynamic programming.

Applications: Spell checking, DNA sequence alignment, natural language processing, and approximate string matching. The pyspellchecker library uses Levenshtein Distance (up to edit distance 2) to find candidate corrections for misspelled words (Barr, 2020). Spell-checkers like Ispell suggest words with an edit distance of 1. In legal technology, systems have been proposed to automatically correct misused legal terms using the Levenshtein Edit Distance algorithm. It is also used in duplicate address detection (e.g., "931 Main St" vs "931 Main Street").

0.7 Hamming Distance

The Hamming distance measures the number of positions at which two strings of equal length differ. For binary strings, it counts the number of differing bits:

The Hamming distance is a true metric and is widely used in coding theory, error detection and correction, and in some machine learning applications where data is represented as binary vectors. It is computationally efficient and can be computed quickly using bitwise operations. Hamming distance is also used in some classification algorithms and as a similarity measure for binary features.

Applications: Error detection and correction, binary classification, DNA sequence analysis, and image hashing. In coding theory, Hamming distance is used to design error-correcting codes that can detect and correct bit errors (Hamming, 1950). It is also used in perceptual hashing algorithms for near-duplicate image detection, where the Hamming distance between hash codes indicates visual similarity.

0.8 Jaccard Distance

The Jaccard distance measures the dissimilarity between two sets. It is defined as:

The Jaccard distance is a true metric and is widely used in set-based applications such as document similarity, recommendation systems, and image segmentation. It measures the proportion of elements that are not shared between the two sets. Jaccard distance is particularly useful when the data is represented as sets of features or as binary vectors. It is also used in clustering algorithms and as a similarity measure in information retrieval.

Applications: Document similarity, recommendation systems, image segmentation, and set-based clustering. In information retrieval, Jaccard distance is used to measure the overlap between sets of words or n-grams in documents, enabling near-duplicate detection. In recommendation systems, it compares the sets of items rated by different users to find similar users for collaborative filtering.

0.9 Earth Mover's Distance (Wasserstein Distance)

The Earth Mover's Distance (also called the 1-Wasserstein distance) measures the minimum cost of transforming one probability distribution into another:

The Earth Mover's distance is a true metric and is used in a variety of applications, including image retrieval, generative modeling (WGAN), and domain adaptation. It is computationally expensive to compute exactly, but efficient approximations exist. The Wasserstein distance is particularly useful in generative modeling because it provides meaningful gradients even when the distributions have disjoint support, unlike KL divergence.

Applications: Generative modeling (WGAN), image retrieval, domain adaptation, and histogram comparison. In the Industrial Internet of Things (IIoT), WGAN with Wasserstein distance is used for anomaly detection to generate high-fidelity minority samples (Li et al., 2021). In image retrieval, the Earth Mover's distance is used to compare histograms and probability distributions. The Wasserstein GAN (WGAN) uses the 1-Wasserstein distance as its loss function, leading to more stable training than standard GANs (Arjovsky et al., 2017).

0.10 Kullback-Leibler Divergence

The Kullback-Leibler (KL) divergence measures the information loss when using distribution Q to approximate distribution P:

KL divergence is not a true metric because it is asymmetric and does not satisfy the triangle inequality. However, it is fundamental in information theory and is used extensively in machine learning, particularly in variational autoencoders (VAEs) and in knowledge distillation. KL divergence measures the amount of information lost when Q is used to approximate P. It is non-negative and equals zero only when P = Q.

Applications: Variational autoencoders, knowledge distillation, model evaluation, and information theory. In transfer learning, KL divergence is used as a regularization loss to guide model fine-tuning and quantify domain discrepancy in data-driven applications like shield tunneling (Zhang et al., 2021). It is also used in drift detection where autoencoder-based models incorporate KL divergence as an additional loss term to detect changes in data distribution. In knowledge distillation, the student model is trained to minimize the KL divergence between its output distribution and that of the teacher model (Hinton et al., 2015).

0.11 Jensen-Shannon Divergence

The Jensen-Shannon divergence is a symmetric version of KL divergence:

where $M=(P+Q)/2$. JSD is symmetric, non-negative, and bounded between 0 and log(2). It is used in generative adversarial networks (GANs) and as a distance measure in clustering and model comparison.

Applications: Generative adversarial networks, clustering, and model comparison. In GANs, JSD is used to measure the similarity between the generated distribution and the real data distribution, providing a more stable and interpretable divergence than KL (Goodfellow et al., 2014). It is also used in clustering to measure the distance between clusters and in the evaluation of probabilistic models.

0.12 Comparing Distance Metrics

Table 1 provides a comprehensive comparison of the major distance metrics, their properties, and their typical applications. The choice of distance metric can significantly impact the performance of machine learning models, and it is essential to select the metric that is best suited for the data and the task.

Table 1: Comparison of distance metrics. The table summarizes the formula, metric properties, data type suitability, and common applications. Euclidean and Manhattan are the most widely used for continuous data. Mahalanobis is preferred when features are correlated. Cosine is the go‑to for high‑dimensional sparse data like text. Levenshtein, Hamming, and Jaccard are used for strings, binary, and set data respectively. Earth Mover’s and KL divergence are used for distributions, with KL being asymmetric and thus not a true metric. The choice of distance metric should be guided by the nature of the data and the requirements of the task.

Table 1 provides a comprehensive comparison of the major distance metrics and divergences used in machine learning. The table summarizes the formula, the metric properties (whether it satisfies non-negativity, symmetry, and the triangle inequality), the data type it is best suited for, and the common applications. As shown, Euclidean and Manhattan distances are the most widely used for continuous data. Mahalanobis distance is preferred when features are correlated. Cosine distance is the go-to for high-dimensional sparse data like text. Levenshtein, Hamming, and Jaccard distances are used for strings, binary, and set data respectively. Earth Mover's and KL divergence are used for distributions, with KL divergence being asymmetric and thus not a true metric. The choice of distance metric should be guided by the nature of the data and the requirements of the task.