Chapter 07 - Manifold Learning

Dimensionality reduction and manifold learning

Introduction

These techniques work well if the given data happens to lie near a lower-dimensional vector subspace or submanifold of the original space.

Foundational algorithms are

• PCA “principle component analysis” — vector subspaces
  • starts with $X\subset {\mathbb{R}}^n$ a finite metric space (point-cloud data)
• MDS “multidimensional sampling” — manifold subspaces
  • starts with arbitrary metric space $(X,d)$

Goal:

Given (small) $k\in {\mathbb{Z}}_{\ge 0}$, find an optimal map $\theta :X\to {\mathbb{R}}^k$ which in some sense represents the structure of the data by minimizing the error:

$$\mathcal{E}=\sum _{x_i,x_j\in X}(d_X(x_i,x_j)-d_{{\mathbb{R}}^k}(\theta (x_i),\theta (x_j)){)}^2$$ Link to original

Theory - PCA

PCA

Let $M$ be an $n\times n$ matrix with eigenvalues ${\lambda }_i$ and eigenvectors ${\mathbf{v}}_i$, so $M{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$.

Recall that if $M$ is symmetric, we know that ${\lambda }_i\in \mathbb{R}$ and

$${\lambda }_i\ne {\lambda }_j⟹{\mathbf{v}}_i\perp {\mathbf{v}}_j$$

For PCA, we start with $X=\{{\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_3\}\subset {\mathbb{R}}^n$. Fix $k\in {\mathbb{Z}}_{\ge 0}$ small.

The goal is to find an “optimal” linear map $\theta :{\mathbb{R}}^n\to {\mathbb{R}}^k$ which distorts distances between data points as little as possible. (Minimal mean-square error.)

PCA Algorithm:
(1) Normalization

Consider $\mu =\frac{1}{n}{\sum }_i{\mathbf{x}}_i$ and let ${\tilde{\mathbf{x}}}_i={\mathbf{x}}_i-\mu$.

(2) Covariance matrix

Define the covariance matrix $C$:

$$C=\frac{1}{n}\sum _i{\tilde{\mathbf{x}}}_i{\tilde{\mathbf{x}}}_i^{\mathsf{T}}$$

Note that $C_{jk}={\mathbf{x}}_j\cdot {\mathbf{x}}_k$. Then, since each summand of $C$ is symmetric, $C$ must be symmetric.

(3) Eigenvalues

Compute the top (largest) $k$ eigenvalues of $C$.

If these are pairwise distinct, the corresponding eigenvectors are all linearly independent, so they span a $k$-dimensional linear subspace $V$.

Consider the orthogonal projection $\theta :{\mathbb{R}}^n\to V$.

(Note: one must somehow identify $V$ with ${\mathbb{R}}^k$ first.)

If some eigenvalue ${\lambda }_j$ has multiplicity, then consider the corresponding eigenspace $V_j$.

Theorem:

The outcome of this algorithm is an optimal $\theta$ which minimizes the error $\mathcal{E}$.

(In the context of PCA or MDS, in fact.)

Combining techniques

It is often reasonable to combine techniques discussed thus far.

For example, the outcome of PCA/MDS may be fed into Mapper; a coordinate project in the PCA output may be used as the filter function.

Link to original

Theory - MDS

MDS

Multi-dimensional scaling starts with an arbitrary finite metric space $(X,d)$, and attempts to embed this in ${\mathbb{R}}^k$ in a way that is optimal in the sense of minimizing $\mathcal{E}$. This is done as follows:

(1) Metric matrix:

$$D_{ij}=d_X({\mathbf{x}}_i,{\mathbf{x}}_j)$$

(2) $H$ and $Z$

Let $H$ be the matrix $H=I-\frac{1}{n}1$ where $1$ is the matrix with all entries $1$.

Let $Z$ be the matrix $Z=-\frac{1}{2}HDH$.

(This step centers the result at the origin.)

(3) Define $\theta :X\to {\mathbb{R}}^k$:

Create a matrix $A$ with columns the eigenvectors ${\mathbf{v}}_j$, normalized so that $||{\mathbf{v}}_j|{|}^2={\lambda }_j$. Then:

$$\theta (x_i)=i^{\text{th}}\text{ row of }{A}^{\mathsf{T}}$$ Link to original

Theory - Isomap manifold learning

Isomap manifold learning

The given data is aligned along a non-linear subspace of ${\mathbb{R}}^n$.

This method is used in facial recognition, for example.

We are assuming that the data lies along (very near) a submanifold $M\subset {\mathbb{R}}^n$. This $M$ is assumed to have an “intrinsic” metric $d_M(x,y)$ for $x,y\in M$.

$$d_M(x,y)=\underset{\text{curves }\alpha }{\min }{\int }_0^1||\dot{\alpha }(t)||dt$$

The idea of isomap is that, assuming $M\subset {\mathbb{R}}^n$ is smoothly embedded, there is a scale at which

$$d_M(x,y)\sim d_{{\mathbb{R}}^n}(x,y)$$

Isomap description in detail:

Let us be given $X=\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_m\}\subset {\mathbb{R}}^n$, as well as a scale $\epsilon >0$ and a target dimension $k$.

Isomap procedure

(1) Build weighted graph $G$:

• Vertices: the points ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_m$
• Edges: join ${\mathbf{x}}_i$ to ${\mathbf{x}}_j$ when $d({\mathbf{x}}_i,{\mathbf{x}}_j)<\epsilon$
• Weights: the distances $w_{ij}=d({\mathbf{x}}_i,{\mathbf{x}}_j)$

(2) New metric space $(X^{\prime },d_{X^{\prime }})$:

Same points, new distances:

$$d_{X^{\prime }}({\mathbf{x}}_i,{\mathbf{x}}_j)=\underset{\begin{array}{c}\text{paths }{\mathbf{x}}_i\\ \text{ to }{\mathbf{x}}_j\text{ in }G\end{array}}{\min }\sum \text{path weight}$$

(Use Dijkstra’s Algorithm to compute the minimal path.)

(3) Apply PCA/MDS:

Find an optimal map $\theta :X^{\prime }\to {\mathbb{R}}^k$.

Isomap - single chart

Isomap is most effective when the manifold can be covered by a single chart and the algorithm effectively “flattens” and “unrolls” the space.

It is less effective for manifolds with topology. For example, when applied to ${\mathbb{S}}^2\subset {\mathbb{R}}^3$, the output of isomap is a flat disk.

(Rabadan-Blumberg 2020)

Link to original

Theory - Local Linear Embedding (LLE)

Local Linear Embedding (LLE)

LLE is a variation of isomap manifold learning that is “locally linear.” It does not attempt to preserve the metric globally. The algorithm is a little more efficient than isomap as well.

LLE Procedure

Suppose we are given the data set $\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_m\}\subset {\mathbb{R}}^n$, the target dimension $k\in \mathbb{N}$ and a “neighborhood size” $K$.

(1) Find minimizer weights:

For each ${\mathbf{x}}_i$, find weights $w_{ij}$ that minimize the error:

$$\mathcal{E}=\sum _i{\left({\mathbf{x}}_i-\sum _j{w}_{ij}{\mathbf{x}}_j\right)}^2$$

subject to the constraints:

$$\{\begin{array}{rl}{w}_{ij}& =0\text{ if }{\mathbf{x}}_i,{\mathbf{x}}_j\text{ are NOT }K\text{-neighbors}\\ & \\ \sum _j{w}_{ij}& =1\end{array}$$

The weights determine approximations of a point using the plane that best fits its neighbors. If the manifold is actually linear around a point, the error at that point will be zero.

(2) Use minimizer weights to recover points:

Find points $\{y_1,\dots ,y_m\}\subset {\mathbb{R}}^k$ that minimize the error:

$$\mathcal{E}=\sum _i{\left(y_i-\sum _j{w}_{ij}{y}_j\right)}^2$$

The new embedding is $\theta :x_i⟼y_i$.

Locality

The Isomap and LLE algorithms are local, meaning that the output $\theta (x)$ is determined by the data around $x$. Data points far from $x$ have no effect on $\theta (x)$.

Link to original

Laplacian eigenmaps

Introduction

The Laplace operator $\Delta$ on smooth functions on ${\mathbb{R}}^n$ may be written in a variety of ways:

$$\begin{array}{rl}\Delta f& =\mathrm{div}(\nabla f)\\ & \\ & =\nabla \cdot \nabla f\\ & \\ & =\frac{{\partial }^{2}f}{\partial x_1^2}+\cdots +\frac{{\partial }^{2}f}{\partial x_n^2}\end{array}$$

We would like to extend the concept of $\Delta f$ to

1. smooth manifolds (coordinate independent version)
2. graphs (combinatorial version)

Link to original

Theory - Laplace-Beltrami operator

Laplace-Beltrami operator

The extension of the concept of $\Delta$ to smooth manifolds is called the Laplace-Beltrami operator. It is still defined as the divergence of the gradient, but these too must be upgraded to the context of manifolds.

Write $C^{\infty }(M)$ for the space of smooth functions $M\to \mathbb{R}$. Write ${\Omega }^n(M)$ for the space of differential $n$-forms on $M$. The exterior derivative is a map:

$$d_n:{\Omega }^n(M)\to {\Omega }^{n+1}(M)$$

and the co-differential is a map:

$${\delta }_{n+1}:{\Omega }^{n+1}(M)\to {\Omega }^n(M)$$

(It is defined using the Hodge star operator.) Then $\Delta f=(\delta \circ d)(f)$.

The spectrum of $\Delta$ is the set of eigenfunctions $f:M\to \mathbb{R}$, meaning functions satisfying:

$$\Delta f=\lambda f$$

for some $\lambda$.

If you know the complete spectrum of $M$, then you know a lot about the shape of $M$ (although you may not be able to recover $M$ completely).

Link to original

Theory - Laplacian for graphs

Laplacian for graphs

In spectral graph theory one studies the spectrum of a combinatorial extension of the Laplacian concept to a graph.

We start with a weighted graph:

• Vertices $\{x_1,\dots ,x_n\}$
• Edges with weights $w_{ij}$

The adjacency matrix $A$ is the matrix $(w_{ij})$ for off-diagonal elements, and zeros on the diagonal. (No self-loops.)

The graph Laplacian $\Delta$ is the matrix with $(w_{ij})$ off-diagonal, and the diagonal entries given as follows:

$$D_{ii}=\sum _{\begin{array}{c}j=1\\ j\ne i\end{array}}^n{w}_{ij}$$

Then:

$$\Delta =D-A$$

Explanation:

For a graph $G$, let

• $C_1(G)$ be the vector space with edges of $G$ as basis
• $C_0(G)$ be the vector space with vertices of $G$ as basis

Then define

$$d_1:C_1(G)\to C_0(G)$$

by $d:(x_i,x_j)\mapsto x_j-x_i$.

There is an adjoint (transpose) map $C_0(G)\to C_1(G)$.

Laplacian eigenmaps process

Let us be given a scale $\sigma$ and a target dimension $k$.

Form a weighted graph:

• Vertices $\{x_1,\dots ,x_m\}$
• Edge weights: $w_{ij}$ as follows:

$$w_{ij}=\{\begin{array}{ll}\exp \left(-\frac{d_M(x_i,x_j{)}^2}{\sigma }\right)& d_M(x_i,x_j)<\sigma \\ & \\ 0& d_M(x_i,x_j)>\sigma \end{array}$$

Let $W=(w_{ij})$ and $D$ by $D_{ii}={\sum }_j{w}_{ij}$. The graph Laplacian is $\Delta =D-W$.

Consider the matrix with columns given by eigenvectors corresponding to the $k$-largest eigenvalues of $L$. The rows of this matrix define points $y_i\in {\mathbb{R}}^k$. Define $\theta$ by assigning

$$\theta :x_i⟼y_i$$

This definition of $y_1,\dots ,y_m$ minimizes the error:

$$\mathcal{E}=\sum _{i,j}|y_i-y_j{|}^2{w}_{ij}$$

Given the definition of $w_{ij}$, this error penalizes most strongly nearby points $x_i,x_j$ that are sent to distant points $y_i,y_j$.

The Laplacian eigenmaps process does not work well for spheres and other noncontractible spaces that are not covered by a single coordinate chart.

Link to original

UMAP

Introduction

Uniform Manifold Approximation and Prediction

The goal of UMAP is to rebuild the data in a high $N$ space ${\mathbb{R}}^N$ as:

• Low-dimensional manifold
  • The data is first cast as a weighted graph (1-dimensional)
• Uniform sampling assumption
  • Dense clusters are spread apart and sparse areas contracted

Link to original

Theory - UMAP process

UMAP process

We are given a data cloud $\{x_1,\dots ,x_n\}\in {\mathbb{R}}^N$, and a neighbor-count $k$.

(1) Create weighted partial graphs local to each data point:

For each point $x_i$, define weights as follows:

• Set $w(x_i,y_1)=1$.
• All $y_j$ are infinitely far from each other: $w(w_i,w_j)=0$ for $i\ne j$.
• For $j\ge 2$:
  • Require that $w(x_i,y_j)$ is proportional to $d(x_i,y_j)-d(x_i,y_1)$,
  • Require that ${\sum }_{j=2}^{k}w(x_i,y_j)={\log }_{2}k$.

That is, the nearest neighbor $y_1$ is placed at distance $0$ from $x_i$, and the other $k-1$ neighbors are made closer to $x_i$ by the distance removed. For each fixed $i$, the collection $\{w(x_i,y_j){\}}_{j=1,\dots ,k}$ encodes metric structure of the original data near $x_i$ but with the closest point $y_1$ substituted for $x_i$.

The weight $w(x_i,y_j)$ is supposed to be interpreted as the probability that the point $y_j$ will lie in the same cluster as the point $x_i$.

From these requirements it is possible to deduce a formula for $w(x_i,y_j)$, as follows:

Set $d_1=d(x_i,y_1)$. (Distance to the closest neighbor.) For each $i$, solve for ${\sigma }_i$ such that:

$$\sum _{j=1}^k\exp \left(\frac{-\max (0,d(x_i,y_j)-d_1}{{\sigma }_i}\right)={\log }_{2}k$$

The idea is that for the closest neighbor $y_1$, the weight $w(x_i,y_1)$ should be the highest; the weight should decrease for neighbors that are farther away.

---

(2) Glue partial metrics into a single weighted graph:

Now we define a single weighted graph with vertices the points $x_1,\dots ,x_n$ and weights coming from the set of partial graphs defined in Step (1).

Observe that a given pair of vertices $x_i,x_{i^{\prime }}$ could appear with finite distance in at most two partial graphs. The relation of being “nearest neighbor” is not in general symmetric:

Now, let us be given a pair of vertices $(x_i,x_{i^{\prime }})$.

If this pair appears (with finite weight) in only one partial graph, give the pair a weighted edge in the total graph with the same weight it had in that partial graph.

If this pair appears in two partial graphs, then $x_i$ is the center point in one of them and $x_{i^{\prime }}$ is the center in the other.

We combine the weights as follows:

• Let $p_1=w(x_i,x_{i^{\prime }})$
• Let $p_2=w(x_{i^{\prime }},x_i)$

Then the weight on the pair $(x_i,x_{i^{\prime }})$ shall be defined as:

$$1-(1-p_1)(1-p_2)=p_1+p_2-p_1{p}_2$$

Now we have defined a total weighted graph that combines the information from all the weighted partial (local) graphs.

---

(3) Embed the total weighted graph $G$ in a lower-dimensional space ${\mathbb{R}}^k$ as a weighted graph $H$.

This can be done with standard techniques that we don’t cover here. Briefly:

Start with the spectral graph embedding. Edge weights for edge $e$ are $p_e$ in $G$ and $q_e$ in $H$. Cross-entropy formula:

$$\sum _e{p}_e\log \left(\frac{p_e}{q_e}\right)+(1-p_e)\log \left(\frac{1-p_e}{1-q_e}\right)$$

Use this cross-entropy as a cost function and perform stochastic gradient descent to minimize the cost.

Link to original

Theory - Gradient descent

Gradient descent

Suppose we are given a cost function $f:M\to \mathbb{R}$.

Given any $x\in M$, the gradient of $f$, written $D_{\mathbf{v}}(f)$, is the direction of the largest rate of change of $f$.

$$\mathbf{v}=\nabla f=⟨\frac{\partial f}{\partial x_1},\dots ,\frac{\partial f}{\partial x_n}⟩$$

Smallest rate of change is $-\nabla f$.

Link to original

Illustration

Illustration - uniform sampling assumption

UMAP is based on an assumption that the data samples uniformly from a manifold.

Link to original

Hausdorff manifolds - a non-Hausdorff example from data

Hausdorff manifolds?

Consider $X=\mathbb{R}\backslash \{0\}\bigsqcup \{B\}\bigsqcup \{R\}$ with the standard non-Hausdorff metric:

So the points $B$ and $R$ cannot be separated by a disjoint neighborhood.

But this can actually happen with data! Suppose flowers come in two colors, red and blue, but the value (lightness) ranges from very dark (black) to very light (white):

Link to original

Illustration

Illustration - UMAP figure from Böhm et al 2022

(Böhm et al. 2022)

Link to original