Manifold Alignment
Unification of multiple datasets
Manifold alignment is a problem of finding a common latent space where we jointly perform dimensionality reduction on multiple datasets that preserves any correspondence between those datasets. Before we dive into the details of manifold alignment, let's understand first what is Manifold.
What's Manifold?
An n-dimensional manifold is a most general mathematical space with limits, continuity, and correctness as well as allows the existence of the continuous inverse function with n-dimensional Euclidean spaces¹. Manifolds locally resemble Euclidean space but they may not be Euclidean space. Essentially, a manifold is a generalization of Euclidean space.
In topology, two objects are considered to be of the same shape if one can be deformed into the other without cutting or gluing. Objects with the same shape are called homeomorphic. Manifolds are homeomorphic to Euclidean spaces.
The Problem of Manifold Alignment
In the era of the information revolution, we are seeing a deluge of data being generated in the field of the Internet of Things, Cyber-physical Systems, Bioinformatics, and Robotics. These data are increasingly becoming multi-modal, i.e. more than one dataset from multiple sources to describe the same physical or biological processes. Naturally, these datasets share similar or the same latent semantic structure. The problem of manifold alignment is about aligning multiple datasets to obtain a more meaningful representation. Datasets obtained from various modalities may have disjoint features that make alignment a challenging problem.
Problem Statement
We can summarize the problem of manifold alignment as joint dimensionality-reduction with constraints inspired by correspondences among various datasets in the question.
If we have to datasets X of size n × p and Y of m × r whose instances lie on the same manifold Z, then the problem of alignment is to find f and g such that _f(xᵢ)_ is close to _g(yᵢ)_ Euclidean space. In that case, we are interested in mapping f: ℝᵖ → ℝᵏ and g: ℝʳ _→_ℝᵏ for some latent dimensionality k. We use ℝ to denote the set of real numbers.
Each sample point _x_ᵢ and yᵢ may have exact correspondence only if _f(_xᵢ) = _g(_yᵢ) otherwise we can use prior correspondence like any information about the similarity of _x_ᵢ and yᵢ. _[ f(x); g(_y)] would be the unified representation of X and Y in the new latent space whereas f(X) a_nd g(_Y) would be new coordinates of X and Y.
A few ideas to solve the problem:
Along with preserving relationships across datasets, preserve the individual structure within each dataset by mapping similar points of each dataset to similar locations in Euclidean space.
Manifold alignment algorithm can be unsupervised, semi-supervised, or supervised depending on how much prior information is available. Complete correspondence allows supervised algorithm, while incomplete correspondence allows for semi-supervised or unsupervised.
Graph Laplacians of each dataset would be a discrete approximation of the same manifold. Thus, diagonal concatenation of these Laplacians along with off-diagonal elements filled with correspondence is an approximation of that manifold.
We can use graph embedding algorithms to preserve local similarities and correspondence can be encoded by the joint Laplacian. Thus manifold alignment can be reduced to a manifold learning problem.
Loss Function
There are two considerations we need to think about while developing a loss function for the manifold alignment problems. The first is that the loss function should preserve local structure and correspondence information. The second is that after forming the joint Laplacian, manifold alignment should be equivalent to Laplacian eigenmaps.
If we have c datasets X⁽¹⁾, X⁽²⁾, ..., X⁽ᶜ⁾, then we can write a loss term for within dataset to reflect preservation of local similarity as
where F⁽ᵃ⁾ is embedded of the a-th dataset, i.e. new coordinates of X⁽ᵃ⁾. It says if ith and jth rows are similar, which is when W-term is larger then F⁽ᵃ⁾(i, ·) and F⁽ᵃ⁾(j, ·) should be put close to each other.
For between datasets, the loss term is
which defines the cost of preserving correspondence between F⁽ᵃ⁾and F⁽ᵇ⁾. Thus we can have complete loss function as
The loss function for Laplacian eigenmaps can be written using the joint adjacent matrix as
where F is a vector representation of all datasets and W is the joint adjacency matrix. This says that if i-th and j-th rows of X⁽ᵃ⁾ and X⁽ᵇ⁾ are similar whether in same or different datasets which happens when W(i, j) is larger, then their location in latent space F(i, · ) and F(j, ·) should be close together. We can rewrite it as
where L is the joint Laplacian of all the datasets
Thus optimization problem for manifold alignment becomes
where I is an s × s identity matrix, s is the dimension of new space.
Optimality of the solution
The optimal solution to the above optimization problem can be solved using the Lagrange multiplier as
where F = [f₁, f₂, ... fₛ] where the solution is s smallest non-zero eigenvectors and λ are Lagrange multipliers.
Final Algorithm
Given c datasets X⁽¹⁾, X⁽²⁾, ..., X⁽ᶜ⁾ all on same manifolds, a similarity function S that provides similarity of two sample points from the same dataset with respect to geodesic distance along the manifold, and some correspondence information - may be in the form of similarities of sample points from different datasets (e.g. Pearson correlation, mutual information, etc - just an idea, we need to explore more), we can devise algorithm as
Find the adjacency matrix W⁽¹⁾, W⁽²⁾, ..., W⁽ᶜ⁾ of each dataset using the similarity function S - maybe include a weight between two instances if one is the k-nearest neighbor of the other.
Construct the joint Laplacian L.
Compute s smallest non-zero eigenvectors of Lf = λDf
The rows of the following equations of F are new coordinates of X⁽ᵍ⁾:
Later on, I will provide a coding example using a toy dataset. In the meantime, if readers have any questions, please feel free to ask in the comments.
Thank you for reading. If you liked my writing and want to support my content, I request you to subscribe to Medium through https://rahulbhadani.medium.com/membership.
References
https://web.archive.org/web/20210506132703/http://www.math.lsa.umich.edu/~jchw/WOMPtalk-Manifolds.pdf
https://www.math.arizona.edu/~glickenstein/research/laymanfin/node3.html
https://web.archive.org/web/20160909193617/http://ocw.mit.edu/courses/mathematics/18-965-geometry-of-manifolds-fall-2004/lecture-notes/lecture1.pdf
https://my.vanderbilt.edu/stacyfonstad/files/2011/10/ShapeOfSpace.pdf
https://people.csail.mit.edu/pkrafft/papers/wang-et-al-2010-manifold.pdf
