Laplacian Eigenmaps and Spectral Manifold Learning
This article provides a concise explanation of how Laplacian Eigenmaps utilize the graph Laplacian matrix of data affinities to perform spectral manifold learning in artificial intelligence. It covers the fundamental steps of the algorithm, beginning with the construction of an affinity graph from high-dimensional data, moving through the mathematical formulation of the graph Laplacian, and concluding with how spectral decomposition achieves dimensionality reduction while preserving local geometric structures.
The Core Concept of Manifold Learning
In artificial intelligence, high-dimensional data often lies on or near a much lower-dimensional, non-linear subspace known as a manifold. Spectral manifold learning aims to uncover this hidden structure to reduce dimensionality without losing important information. Laplacian Eigenmaps achieve this by ensuring that data points close to each other in the original high-dimensional space remain close to each other when mapped to the new, low-dimensional space.
Step 1: Constructing the Affinity Graph
Because the true underlying manifold of the data is unknown, Laplacian Eigenmaps approximate it by building an undirected neighborhood graph. Every data point becomes a node in this graph.
Connections (edges) between nodes are established using one of two methods:
- Epsilon-neighborhoods: Nodes are connected if the Euclidean distance between them is less than a specific threshold.
- k-Nearest Neighbors (k-NN): Nodes are connected if one is among the \(k\) closest neighbors of the other.
Step 2: Defining Data Affinities
Once the graph structure is set, weights are assigned to the edges to create an affinity matrix, denoted as \(W\). This matrix quantifies the similarity between connected points. A common approach is to use the Heat Kernel, which assigns higher weights to closer points and exponentially decays the weight as the distance increases. If two nodes are not connected, their affinity weight is set to zero. This step encodes the local geometry of the data into a mathematical matrix.
Step 3: Computing the Graph Laplacian Matrix
The core of the algorithm relies on the graph Laplacian matrix, which acts as a discrete approximation of the continuous Laplace-Beltrami operator on the manifold.
First, a diagonal degree matrix, \(D\), is created by summing the affinity weights connected to each node. The entry \(D_{ii}\) represents the total weight of edges attached to node \(i\), effectively measuring the local density around that point.
The unnormalized graph Laplacian matrix, \(L\), is then calculated by subtracting the affinity matrix from the degree matrix: \[L = D - W\]
Step 4: Minimizing the Objective Function
To map the data to a lower-dimensional space, the algorithm seeks a set of new coordinates, \(y\), that minimizes a specific cost function: \[\sum_{i,j} (y_i - y_j)^2 W_{ij}\]
This function heavily penalizes the mapping if two points have a high affinity (\(W_{ij}\) is large) but are placed far apart in the low-dimensional space (\((y_i - y_j)^2\) is large). Mathematically, this sum can be rewritten using the graph Laplacian as \(y^T L y\). Therefore, preserving local neighborhoods is equivalent to minimizing \(y^T L y\).
Step 5: Spectral Decomposition
To find the optimal low-dimensional representation and prevent the algorithm from collapsing all points into a single location, a constraint utilizing the degree matrix is applied (\(y^T D y = 1\)). The minimization problem then transforms into a generalized eigenvalue problem: \[Ly = \lambda Dy\]
Here, \(y\) represents the eigenvectors and \(\lambda\) represents the eigenvalues. The algorithm solves this equation and orders the eigenvalues from smallest to largest. The smallest eigenvalue is always zero, corresponding to a trivial eigenvector that maps all points to a constant value. The algorithm discards this first eigenvector and selects the next \(m\) smallest eigenvectors. The components of these selected eigenvectors directly provide the new \(m\)-dimensional coordinates for the data points, successfully completing the spectral manifold learning process.