User:Perimosocordiae/Manifold alignment

Manifold alignment is a class of machine learning algorithms that produce projections between sets of data, given that the original data sets lie on a common manifold. The concept was first introduced as such by Ham, Lee, and Saul in 2003, though the idea of correlating sets of vectors has existed since at least 1936.

Overview

Manifold alignment takes advantage of the assumption that disparate data sets produced by similar generating processes will share a similar underlying manifold representation. By learning projections from each original space to the shared manifold, correspondences are recovered and knowledge from one domain can be transferred to another. Most manifold alignment techniques consider only two data sets, but the concept extends to arbitrarily many initial domains.

Consider the case of aligning two data sets, $X$ and $Y$, with $X_{i}\in \mathbb {R} ^{m}$ and $Y_{i}\in \mathbb {R} ^{n}$.

Manifold alignment algorithms attempt to project both $X$ and $Y$ into a new d-dimensional space such that the projections both minimize distance between corresponding points and preserve the local manifold structure of the original data. The projection functions are denoted $\phi _{X}:\,\mathbb {R} ^{m}\rightarrow \mathbb {R} ^{d}$ and $\phi _{Y}:\,\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{d}$. Let $W_{i,j}$ represent the binary correspondence matrix between points $X_{i}$ and $Y_{j}$, and $S_{X}$ and $S_{Y}$ represent pointwise similarities within data sets. The loss function for manifold alignment can then be written:

$\arg \min _{\phi _{X},\phi _{Y}}\mu \sum _{i,j}\left\Vert \phi _{X}\left(X_{i}\right)-\phi _{X}\left(X_{j}\right)\right\Vert ^{2}S_{X,i,j}+\mu \sum _{i,j}\left\Vert \phi _{Y}\left(Y_{i}\right)-\phi _{Y}\left(Y_{j}\right)\right\Vert ^{2}S_{Y,i,j}+\left(1-\mu \right)\sum _{i,j}\Vert \phi _{X}\left(X_{i}\right)-\phi _{Y}\left(Y_{j}\right)\Vert ^{2}W_{i,j}$

Note that the coefficient $\mu$ can be tuned to adjust how much importance preserving manifold structure should be given, versus minimizing corresponding points. Solving this optimization problem is equivalent to solving a generalized eigenvalue problem using the graph laplacian of the joint matrix, G:

$G=\left[{\begin{array}{ccc}\mu S_{X}\\&\mu S_{Y}\\&&\left(1-\mu \right)W\end{array}}\right]$

Variants

Several variants of the basic manifold alignment technique have been proposed.

• Various dimension reduction algorithms may be used: Laplacian Eigenmaps, Locally Linear Embeddings, Isomap, and semi-definite embedding.
• Two-step alignments, as opposed to the standard one-step approach.
• Instance vs feature level projections.
• Alignment with different amounts of correspondence information: Supervised, semi-supervised, and unsupervised learning, as well as learning from labelled data.
• Alignment at multiple scales, using diffusion wavelet trees.

Applications

Manifold alignment is suited to problems with several corpora that lie on a shared manifold, especially when each corpus is of a different dimensionality. Examples include:

• Cross-language information retrieval / automatic translation
• Transfer learning of policy and state representations

Further Reading

• Ma, Yunqian (Apr 15, 2012). Manifold Learning Theory and Applications. Taylor & Francis Group. p. 376. ISBN 1439871094.
• Wang, Chang (2009). "A General Framework for Manifold Alignment" (PDF). AAAI Fall Symposium on Manifold Learning and its Applications. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
• Wang, Chang (2011). "Heterogeneous Domain Adaptation using Manifold Alignment" (PDF). The 22nd International Joint Conference on Artificial Intelligence. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

External links

• Chang Wang's Manifold alignment overview