Manifold alignment

Diffusion maps is a machine learning algorithm introduced by R. R. Coifman and S. Lafon. It computes a family of embeddings of a data set into Euclidean space (often low-dimensional) whose coordinates can be computed from the eigenvectors and eigenvalues of a diffusion operator on the data. The Euclidean distance between points in the embedded space is equal to the "diffusion distance" between probability distributions centered at those points. Different from other dimensionality reduction methods such as principal component analysis (PCA) and multi-dimensional scaling (MDS), diffusion maps is a non-linear method that focuses on discovering the underlying manifold that the data has been sampled from. By integrating local similarities at different scales, diffusion maps gives a global description of the data-set. Compared with other methods, the diffusion maps algorithm is robust to noise perturbation and is computationally inexpensive.

Definition of diffusion maps

Following, diffusion maps can be defined in four steps.

Connectivity

Diffusion maps leverages the relationship between heat diffusion and random walk Markov chain. The basic observation is that if we take a random walk on the data, walking to a nearby data-point is more likely than walking to another that is far away. Based on this, the connectivity between two data points, $x$ and $y$, can be defined as the probability of walking from $x$ to $y$ in one step of the random walk. Usually, this probability will be defined as the kernel function on the two points, for example, the popular Gaussian kernel:

$p(x,y)=k(x,y)=e^{-{\frac {||x-y||^{2}}{\alpha }}}$

More generally, the kernel function has the following properties

$k(x,y)=k(y,x)$

($k$ is symmetric)

$k(x,y)\geq 0\,\,\forall x,y$

($k$ is positivity preserving).

The kernel constitutes the prior definition of the local geometry of data-set. Since a given kernel will capture a specific feature of the data set, its choice should be guided by the application that one has in mind.

Diffusion process

With the definition of connectivity between two points, we can define the diffusion matrix $L$ (it is also a version of graph Laplacian matrix)

$L_{i,j}=k(x_{i},x_{j})\,$

Many works use the normalized matrix as

$M=D^{-1}L.\,$

We can define the probabilities for taken from $i$ to $j$ in $t$ steps as:

$p(x_{j},t|x_{i})=M_{ij}^{t}\,$

As we calculate the probabilities$M^{t}$ for increasing values of $t$, we observe the data-set at different scales. This is the diffusion process. Diffusion process reveals the global geometric structure of a data set as paths along the true geometric structure of the data set have high probability.

Diffusion distance

The diffusion distance at time $t$ between two points can be measured as the similarity of two points in the observation space with the connectivity between them. It is given by

$D_{t}(x_{i},x_{j})^{2}=\sum _{y}(p(y,t|x_{i})-p(y,t|x_{j}))^{2}w(y)$

here $w(y)$ is a weighted function which can often treated as $w(y)=1$

Diffusion process

Now, we can give the definition of diffusion map as:

$\Psi _{t}(x)=(\lambda _{1}^{t}\psi _{1}(x),\lambda _{2}^{t}\psi _{2}(x),\ldots ,\lambda _{n}^{t}\psi _{n}(x))$

in, it is proved that

$D_{t}(x_{i},x_{j})^{2}=||\Psi _{t}(x_{i})-\Psi _{t}(x_{j})||^{2}\,$

if we take the first k eigenvectors and eigenvalues, we get the diffusion map from the original data to a k-dimensional space which is embedded in the original space.

Algorithm

The basic algorithm framework of diffusion map is as:

Step 1. Given the similarity matrix L

Step 2. Form the normalized matrix $M=D^{-1}L$

Step 3. Compute the k largest eigenvalues of $M^{t}$ and the corresponding eigenvectors

Step 4. Use diffusion map to get the embedding matrix Y

Application

In the paper, they showed how to design a kernel that reproduces the diffusion induced by a Fokker-Planck equation. Also, they explained that when the data approximate a manifold, then one can recover the geometry of this manifold by computing an approximation of the Laplace-Beltrami operator. This computation is completely insensitive to the distribution of the points and therefore provides a separation of the statistics and the geometry of the data. Since Diffusion map gives a global description of the data-set, it can measure the distances between pair of sample points in the manifold the data is embedded. Based on diffusion map, there are many applications, such as spectral clustering, low dimensional representation of images, image segmentation, 3D model segmentation, speaker identification, sampling on manifolds and so on.

See also

• Nonlinear dimensionality reduction

References

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.