← Reference · Nestor G Pestelos Jr · Print this page

Machine Learning

Unsupervised Learning

A citable reference on Unsupervised Learning: density estimation, clustering taxonomy, linear and non-linear dimensionality reduction, manifold learning, latent variable models, and self-supervised representations.

1. Formal Problem Formulation

Unsupervised Learning is a machine learning paradigm in which an algorithm extracts underlying patterns, latent representations, or probability distributions from unlabeled datasets without external supervision or ground-truth targets.[1, 2] The learner discovers intrinsic geometric, topological, or statistical structure within the input space.

1.1 Unlabeled Experience and Latent Structure

The training dataset $\mathcal{D}$ consists of $N$ observation vectors sampled independently from an unknown probability distribution $P(X)$ defined over feature space $\mathcal{X} \subseteq \mathbb{R}^d$:

$$\mathcal{D} = \{x_1, x_2, \dots, x_N\} \sim P(X)^N$$

Unlike supervised learning, no target vector $y_i$ accompanies each sample. Unsupervised objectives generally solve one of four fundamental mathematical tasks:

Density Estimation: Reconstruct the probability density function $\hat{p}(x)$ that generated $\mathcal{D}$.
Clustering: Partition the sample indices $\{1, \dots, N\}$ into $K$ disjoint or overlapping subsets based on pairwise similarity metrics.
Dimensionality Reduction: Learn a mapping $g: \mathbb{R}^d \to \mathbb{R}^k$ (where $k \ll d$) that preserves critical geometric distances or topological relationships.
Generative Representation: Learn a parameterized mapping from a low-dimensional prior distribution $p(z)$ over latent space $\mathcal{Z}$ to the data manifold $\mathcal{X}$.

1.2 Probability Density Estimation

In Parametric Density Estimation, the data distribution is modeled as a parameterized family $p(x \mid \theta)$. In a Gaussian Mixture Model (GMM) with $K$ components, the marginal density is a convex combination of multivariate normals:[1]

$$p(x \mid \theta) = \sum_{k=1}^K \pi_k \, \mathcal{N}(x \mid \mu_k, \Sigma_k), \quad \sum_{k=1}^K \pi_k = 1, \quad \pi_k \ge 0$$

Parameters $\theta = \{\pi_k, \mu_k, \Sigma_k\}_{k=1}^K$ are estimated using the Expectation-Maximization (EM) algorithm (Dempster et al., 1977), which iteratively alternates between computing latent component responsibilities in the E-step and updating cluster parameters in the M-step:[3]

$$\gamma_{ik} = \frac{\pi_k \mathcal{N}(x_i \mid \mu_k, \Sigma_k)}{\sum_{j=1}^K \pi_j \mathcal{N}(x_i \mid \mu_j, \Sigma_j)}, \quad \mu_k^{\text{new}} = \frac{\sum_{i=1}^N \gamma_{ik} x_i}{\sum_{i=1}^N \gamma_{ik}}$$

In Non-Parametric Density Estimation, Kernel Density Estimation (KDE) computes the empirical density without distributional assumptions via kernel function $K$:

$$\hat{p}(x) = \frac{1}{N h^d} \sum_{i=1}^N K\left( \frac{x - x_i}{h} \right)$$

2. Taxonomy of Clustering Algorithms

Clustering Paradigm	Representative Algorithms	Optimization Objective / Criterion	Cluster Shape Assumption
Partitioning	$k$-Means, $k$-Medoids (PAM), $k$-Means++	Minimize Within-Cluster Sum of Squares (WCSS)	Spherical, convex, equal variance
Hierarchical	Agglomerative (Single, Complete, Average, Ward)	Iterative pairwise merge based on linkage distance metric	Arbitrary tree hierarchies; dendrogram-based
Density-Based	DBSCAN, OPTICS, HDBSCAN	Discover connected dense regions separated by low-density noise	Arbitrary non-convex shapes; robust to outliers
Model-Based	Gaussian Mixture Models (GMM), Latent Dirichlet Allocation (LDA)	Maximize log-likelihood of mixture distributions via EM	Ellipsoidal distributions with variable covariance
Graph / Spectral	Spectral Clustering, Normalized Cuts	Min-cut partition of graph Laplacian eigenvectors	Complex manifolds, non-linear connectivity

2.1 Partitioning: k-Means and k-Medoids

The standard $k$-Means algorithm (MacQueen, 1967; Lloyd, 1982) partitions $N$ observations into $K$ disjoint sets $S = \{S_1, \dots, S_K\}$ to minimize the Within-Cluster Sum of Squares (WCSS):[4, 5]

$$\arg\min_S \sum_{k=1}^K \sum_{x \in S_k} \|x - \mu_k\|_2^2, \quad \text{where } \mu_k = \frac{1}{|S_k|} \sum_{x \in S_k} x$$

Because finding the global minimum is NP-hard in general metric spaces, Lloyd's heuristic alternates between assigning each sample to its nearest centroid $\mu_k$ and recomputing centroids as sample means. $k$-Means++ (Arthur & Vassilvitskii, 2007) seeds initial centers with probability proportional to squared distance $D(x)^2$ from existing centers, guaranteeing an $O(\log K)$ competitive approximation ratio.[6]

2.2 Hierarchical Clustering and Linkage Criteria

Agglomerative hierarchical clustering begins with each point in its own singleton cluster and sequentially merges the closest pair of clusters until all points reside in a single root. Linkage functions define inter-cluster distance $D(A, B)$:

Single Linkage: $D(A, B) = \min_{a \in A, b \in B} \|a - b\|$ (susceptible to chaining artifacts).
Complete Linkage: $D(A, B) = \max_{a \in A, b \in B} \|a - b\|$ (favors compact, equal-diameter clusters).
Average Linkage (UPGMA): $D(A, B) = \frac{1}{|A||B|} \sum_{a \in A} \sum_{b \in B} \|a - b\|$.
Ward's Linkage: Minimizes total within-cluster variance increase upon merging:
$$\Delta \text{ESS}_{AB} = \frac{|A||B|}{|A| + |B|} \|\mu_A - \mu_B\|_2^2$$

2.3 Density-Based: DBSCAN and HDBSCAN

DBSCAN (Ester et al., 1996) defines clusters as continuous density-reachable components.[7] For a radius $\epsilon$ and minimum points threshold $\text{MinPts}$:

A point $p$ is a Core Point if $|N_\epsilon(p)| \ge \text{MinPts}$, where $N_\epsilon(p) = \{q \in \mathcal{D} \mid \|p - q\| \le \epsilon\}$.
A point $q$ is Directly Density-Reachable from $p$ if $q \in N_\epsilon(p)$ and $p$ is a core point.
Points that are not density-reachable from any core point are classified as noise (outliers).

2.4 Spectral Clustering and Graph Laplacians

Spectral clustering maps non-linearly separable data into a subspace defined by the lowest eigenvectors of a graph Laplacian.[8] Given an affinity adjacency matrix $W$ and degree matrix $D_{ii} = \sum_j W_{ij}$:

Unnormalized Graph Laplacian: $L = D - W$.
Symmetric Normalized Laplacian: $L_{\text{sym}} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2}$.
Random Walk Laplacian: $L_{\text{rw}} = D^{-1} L = I - D^{-1} W$.

By the Rayleigh-Ritz theorem, the first $K$ eigenvectors of $L_{\text{sym}}$ solve the continuous relaxation of the Normalized Cut (NCut) graph partitioning problem.

3. Dimensionality Reduction and Manifold Learning

High-dimensional representations frequently lie near lower-dimensional smooth manifolds embedded in $\mathbb{R}^d$. Dimensionality reduction algorithms extract these intrinsic degrees of freedom.

3.1 Principal Component Analysis (PCA)

Principal Component Analysis (Pearson, 1901; Hotelling, 1933) finds an orthogonal linear transformation that projects centered data $X \in \mathbb{R}^{N \times d}$ onto a $k$-dimensional subspace while maximizing preserved variance (or equivalently, minimizing reconstruction error).[9]

$$\Sigma = \frac{1}{N} X^T X = V \Lambda V^T, \quad Z = X V_k$$

where $V_k \in \mathbb{R}^{d \times k}$ contains the eigenvectors corresponding to the $k$ largest eigenvalues $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_k$ of sample covariance matrix $\Sigma$. Via Singular Value Decomposition (SVD) $X = U S V^T$, the principal coordinates are computed directly as $Z = U_k S_k$.

3.2 Matrix Factorization and Independent Component Analysis

Non-Negative Matrix Factorization (NMF): Decomposes non-negative matrix $V \approx W H$ subject to $W \ge 0, H \ge 0$, learning additive, parts-based representations.
Independent Component Analysis (ICA): Assumes observed signals $x = A s$ are linear mixtures of statistically independent, non-Gaussian source signals $s$. Algorithms maximize non-Gaussianity (measured via kurtosis or negentropy) to estimate unmixing matrix $W = A^{-1}$.

3.3 Non-Linear Manifold Learning: t-SNE and UMAP

t-SNE (van der Maaten & Hinton, 2008) converts pairwise Euclidean distances in high-dimensional space into conditional Gaussian probabilities $p_{j \mid i}$ and models low-dimensional points $y_i, y_j \in \mathbb{R}^2$ using a heavy-tailed Student-t distribution $q_{ij}$:[10]

$$p_{j \mid i} = \frac{\exp(-\|x_i - x_j\|^2 / 2\sigma_i^2)}{\sum_{k \ne i} \exp(-\|x_i - x_k\|^2 / 2\sigma_i^2)}, \quad q_{ij} = \frac{(1 + \|y_i - y_j\|^2)^{-1}}{\sum_{k} \sum_{l \ne k} (1 + \|y_k - y_l\|^2)^{-1}}$$

The low-dimensional embedding is optimized by minimizing the Kullback-Leibler divergence $\text{KL}(P \,\|\, Q) = \sum_{i \ne j} p_{ij} \log \frac{p_{ij}}{q_{ij}}$ via gradient descent. The heavy tail of the Student-t distribution eliminates the crowding problem by allowing moderate high-dimensional distances to expand in low dimensions.

UMAP (McInnes et al., 2018) builds on Riemannian geometry and algebraic topology, modeling the manifold with fuzzy simplicial sets and optimizing cross-entropy between high- and low-dimensional fuzzy sets.[11] UMAP preserves both local and global manifold structure while exhibiting faster computational scaling than t-SNE.

4. Generative Modeling and Latent Variable Models

Deep unsupervised architectures learn generative representations that map simple latent priors to complex target data manifolds.

4.1 Autoencoder Architectures

An autoencoder consists of an encoder $z = f_\phi(x)$ and a decoder $\hat{x} = g_\theta(z)$ trained to minimize reconstruction error $\mathcal{L}(x, g_\theta(f_\phi(x)))$. Undercomplete bottlenecks ($\dim(z) \ll \dim(x)$), sparsity penalties ($L_1$ norm on $z$), or contractive Jacobian regularizers ($\|J_f(x)\|_F^2$) force the network to discard noise and retain latent manifold coordinates.

4.2 Variational Autoencoders (VAEs)

Variational Autoencoders (Kingma & Welling, 2013; Rezende et al., 2014) introduce probabilistic latent variables $z \sim p(z) = \mathcal{N}(0, I)$.[12] Because the true posterior $p_\theta(z \mid x)$ is intractable, a variational encoder $q_\phi(z \mid x) = \mathcal{N}(\mu_\phi(x), \Sigma_\phi(x))$ approximates it by maximizing the Evidence Lower Bound (ELBO):

$$\log p_\theta(x) \ge \mathcal{L}_{\text{ELBO}}(\theta, \phi; x) = \mathbb{E}_{q_\phi(z \mid x)} \left[ \log p_\theta(x \mid z) \right] - D_{\text{KL}}\big(q_\phi(z \mid x) \,\|\, p(z)\big)$$

Differentiability during backpropagation is achieved through the Reparameterization Trick, expressing stochastic latent vectors as a deterministic transformation of standard normal noise:

$$z = \mu_\phi(x) + \sigma_\phi(x) \odot \epsilon, \quad \text{where } \epsilon \sim \mathcal{N}(0, I)$$

4.3 Generative Adversarial Networks (GANs)

Generative Adversarial Networks (Goodfellow et al., 2014) formulate generative modeling as a two-player zero-sum minimax game between a Generator $G_\theta$ and a Discriminator $D_\phi$:[13]

$$\min_G \max_D V(D, G) = \mathbb{E}_{x \sim P_{\text{data}}(x)} \left[ \log D(x) \right] + \mathbb{E}_{z \sim p_z(z)} \left[ \log\big(1 - D(G(z))\big) \right]$$

For an optimal discriminator $D^*(x) = \frac{p_{\text{data}}(x)}{p_{\text{data}}(x) + p_g(x)}$, the minimax objective reduces to minimizing the Jensen-Shannon divergence $2 D_{\text{JS}}(p_{\text{data}} \,\|\, p_g) - 2 \log 2$ between the data distribution and the model distribution.

4.4 Self-Supervised Learning and Masked Modeling

In modern machine learning, self-supervised learning uses structural aspects of the unlabeled data itself as supervisory targets.

Masked Autoencoding (MAE / BERT): Masks a fraction of input tokens or image patches and trains a transformer to reconstruct missing components from unmasked context.
Contrastive Learning (SimCLR / InfoNCE): Maximizes agreement between differently augmented views of the same sample while minimizing similarity to negative distractors using the InfoNCE objective:[14]
$$\mathcal{L}_{\text{InfoNCE}} = -\log \frac{\exp(\text{sim}(z_i, z_j)/\tau)}{\sum_{k=1}^{2K} \mathbb{I}_{[k \ne i]} \exp(\text{sim}(z_i, z_k)/\tau)}$$

5. Cluster Validation Metrics

Because unsupervised tasks lack external ground truth, clustering quality is evaluated via internal geometry or external partition comparisons:

Silhouette Coefficient: For sample $i$, let $a(i)$ be mean intra-cluster distance and $b(i)$ be minimum mean distance to points in any other cluster:
$$s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))}, \quad s(i) \in [-1, 1]$$
Davies-Bouldin Index: Measures the similarity between each cluster $R_{ij} = \frac{s_i + s_j}{d(\mu_i, \mu_j)}$ and computes $\frac{1}{K}\sum_{i} \max_{j \ne i} R_{ij}$; lower values indicate superior partition separation.
Adjusted Rand Index (ARI): Evaluates agreement between cluster assignments and ground-truth classes, normalized for chance:
$$\text{ARI} = \frac{\text{Index} - \text{Expected Index}}{\text{Max Index} - \text{Expected Index}} \in [-1, 1]$$

6. References

^ Christopher M. Bishop, Pattern Recognition and Machine Learning (Springer, 2006).
^ Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd ed. (Springer, 2009). DOI: 10.1007/978-0-387-84858-7.
^ Arthur P. Dempster, Nan M. Laird, and Donald B. Rubin, "Maximum likelihood from incomplete data via the EM algorithm," Journal of the Royal Statistical Society: Series B 39(1), 1–38 (1977). DOI: 10.1111/j.2517-6161.1977.tb01600.x.
^ J. B. MacQueen, "Some Methods for classification and Analysis of Multivariate Observations," Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability 1, 281–297 (1967).
^ Stuart P. Lloyd, "Least squares quantization in PCM," IEEE Transactions on Information Theory 28(2), 129–137 (1982). DOI: 10.1109/TIT.1982.1056489.
^ David Arthur and Sergei Vassilvitskii, "k-means++: The advantages of careful seeding," Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1027–1035 (2007). URL: ACM Digital Library.
^ Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu, "A density-based algorithm for discovering clusters in large spatial databases with noise," Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), 226–231 (1996).
^ Ulrike von Luxburg, "A tutorial on spectral clustering," Statistics and Computing 17(4), 395–416 (2007). DOI: 10.1007/s11222-007-9033-z.
^ Karl Pearson, "On lines and planes of closest fit to systems of points in space," Philosophical Magazine 2(11), 559–572 (1901). DOI: 10.1080/14786440109462720.
^ Laurens van der Maaten and Geoffrey Hinton, "Visualizing data using t-SNE," Journal of Machine Learning Research 9, 2579–2605 (2008). URL: JMLR.
^ Leland McInnes, John Healy, and James Melville, "UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction," arXiv:1802.03426 (2018). DOI: 10.48550/arXiv.1802.03426.
^ Diederik P. Kingma and Max Welling, "Auto-Encoding Variational Bayes," International Conference on Learning Representations (ICLR 2014), arXiv:1312.6114 (2013). DOI: 10.48550/arXiv.1312.6114.
^ Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio, "Generative Adversarial Nets," Advances in Neural Information Processing Systems 27 (NeurIPS 2014). URL: NeurIPS Proceedings.
^ Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton, "A Simple Framework for Contrastive Learning of Visual Representations," International Conference on Machine Learning (ICML 2020), arXiv:2002.05709 (2020). DOI: 10.48550/arXiv.2002.05709.

Clustering Paradigm	Representative Algorithms	Optimization Objective / Criterion	Cluster Shape Assumption
Partitioning	\(k\)-Means, \(k\)-Medoids (PAM), \(k\)-Means++	Minimize Within-Cluster Sum of Squares (WCSS)	Spherical, convex, equal variance
Hierarchical	Agglomerative (Single, Complete, Average, Ward)	Iterative pairwise merge based on linkage distance metric	Arbitrary tree hierarchies; dendrogram-based
Density-Based	DBSCAN, OPTICS, HDBSCAN	Discover connected dense regions separated by low-density noise	Arbitrary non-convex shapes; robust to outliers
Model-Based	Gaussian Mixture Models (GMM), Latent Dirichlet Allocation (LDA)	Maximize log-likelihood of mixture distributions via EM	Ellipsoidal distributions with variable covariance
Graph / Spectral	Spectral Clustering, Normalized Cuts	Min-cut partition of graph Laplacian eigenvectors	Complex manifolds, non-linear connectivity