Manifold alignment

<h2 id="overview">Overview</h2>
Manifold alignment assumes that disparate data sets produced by similar generating processes will share a similar underlying <a href="/facts/Manifold/rXPERJtu">manifold</a> 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 data sets.
Consider the case of aligning two data sets, 
 
 
 
 X
 
 
 {\displaystyle X}
 
 and 
 
 
 
 Y
 
 
 {\displaystyle Y}
 
, with 
 
 
 
 
 X
 
 i
 
 
 ∈
 
 
 R
 
 
 m
 
 
 
 
 {\displaystyle X_{i}\in \mathbb {R} ^{m}}
 
 and 
 
 
 
 
 Y
 
 i
 
 
 ∈
 
 
 R
 
 
 n
 
 
 
 
 {\displaystyle Y_{i}\in \mathbb {R} ^{n}}
 
.
Manifold alignment algorithms attempt to project both 
 
 
 
 X
 
 
 {\displaystyle X}
 
 and 
 
 
 
 Y
 
 
 {\displaystyle 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:

 
 
 
 
 ϕ
 
 X
 
 
 :
 
 
 
 R
 
 
 m
 
 
 →
 
 
 R
 
 
 d
 
 
 
 
 {\displaystyle \phi _{X}:\,\mathbb {R} ^{m}\rightarrow \mathbb {R} ^{d}}

ϕ
 
 Y
 
 
 :
 
 
 
 R
 
 
 n
 
 
 →
 
 
 R
 
 
 d
 
 
 
 
 {\displaystyle \phi _{Y}:\,\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{d}}

Let 
 
 
 
 W
 
 
 {\displaystyle W}
 
 represent the binary correspondence matrix between points in 
 
 
 
 X
 
 
 {\displaystyle X}
 
 and 
 
 
 
 Y
 
 
 {\displaystyle Y}
 
:

 
 
 
 
 W
 
 i
 ,
 j
 
 
 =
 
 
 {
 
 
 
 1
 
 
 i
 f
 
 
 X
 
 i
 
 
 ↔
 
 Y
 
 j
 
 
 
 
 
 
 0
 
 
 o
 t
 h
 e
 r
 w
 i
 s
 e
 
 
 
 
 
 
 
 
 {\displaystyle W_{i,j}={\begin{cases}1&if\,X_{i}\leftrightarrow Y_{j}\\0&otherwise\end{cases}}}

Let 
 
 
 
 
 S
 
 X
 
 
 
 
 {\displaystyle S_{X}}
 
 and 
 
 
 
 
 S
 
 Y
 
 
 
 
 {\displaystyle S_{Y}}
 
 represent pointwise similarities within data sets. This is usually encoded as the <a href="/facts/Heat_kernel/EbLKLbJH">heat kernel</a> of the <a href="/facts/Adjacency_matrix/jYXNhYGs">adjacency matrix</a> of a <a href="/facts/Nearest_neighbor_graph/6pdI9PlH">k-nearest neighbor graph</a>.
Finally, introduce a coefficient 
 
 
 
 0
 ≤
 μ
 ≤
 1
 
 
 {\displaystyle 0\leq \mu \leq 1}
 
, which can be tuned to adjust the weight of the 'preserve manifold structure' goal, versus the 'minimize corresponding point distances' goal.
With these definitions in place, the <a href="/facts/Loss_function/xv5ozuhl">loss function</a> for manifold alignment can be written:

 
 
 
 arg
 ⁡
 
 min
 
 
 ϕ
 
 X
 
 
 ,
 
 ϕ
 
 Y
 
 
 
 
 μ
 
 ∑
 
 i
 ,
 j
 
 
 
 
 ‖
 
 
 ϕ
 
 X
 
 
 
 (
 
 X
 
 i
 
 
 )
 
 −
 
 ϕ
 
 X
 
 
 
 (
 
 X
 
 j
 
 
 )
 
 
 ‖
 
 
 2
 
 
 
 S
 
 X
 ,
 i
 ,
 j
 
 
 +
 μ
 
 ∑
 
 i
 ,
 j
 
 
 
 
 ‖
 
 
 ϕ
 
 Y
 
 
 
 (
 
 Y
 
 i
 
 
 )
 
 −
 
 ϕ
 
 Y
 
 
 
 (
 
 Y
 
 j
 
 
 )
 
 
 ‖
 
 
 2
 
 
 
 S
 
 Y
 ,
 i
 ,
 j
 
 
 +
 
 (
 
 1
 −
 μ
 
 )
 
 
 ∑
 
 i
 ,
 j
 
 
 ‖
 
 ϕ
 
 X
 
 
 
 (
 
 X
 
 i
 
 
 )
 
 −
 
 ϕ
 
 Y
 
 
 
 (
 
 Y
 
 j
 
 
 )
 
 
 ‖
 
 2
 
 
 
 W
 
 i
 ,
 j
 
 
 
 
 {\displaystyle \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}}

Solving this optimization problem is equivalent to solving a <a href="/facts/Generalized_eigenvalue_problem/a2nfF7hJ">generalized eigenvalue problem</a> using the <a href="/facts/Laplacian_matrix/Iwea2mm9">graph laplacian</a><a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> of the joint matrix, G:

 
 
 
 G
 =
 
 [
 
 
 
 
 μ
 
 S
 
 X
 
 
 
 
 
 (
 
 1
 −
 μ
 
 )
 
 W
 
 
 
 
 
 (
 
 1
 −
 μ
 
 )
 
 
 W
 
 T
 
 
 
 
 μ
 
 S
 
 Y
 
 
 
 
 
 
 ]
 
 
 
 {\displaystyle G=\left[{\begin{array}{cc}\mu S_{X}&\left(1-\mu \right)W\\\left(1-\mu \right)W^{T}&\mu S_{Y}\end{array}}\right]}

<h2 id="inter-data-correspondences">Inter-data correspondences</h2>
The algorithm described above requires full pairwise correspondence information between input data sets; a <a href="/facts/Supervised_learning/JlNFNPFt">supervised learning</a> paradigm. However, this information is usually difficult or impossible to obtain in real world applications. Recent work has extended the core manifold alignment algorithm to <a href="/facts/Semi-supervised_learning/4mzcqFjI">semi-supervised</a>
<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
, <a href="/facts/Unsupervised_learning/8a6f61MC">unsupervised</a>
<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
, and <a href="/facts/Multiple-instance_learning/3x78qsYu">multiple-instance</a>
<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
settings.

<h2 id="one-step-vs-two-step-alignment">One-step vs. two-step alignment</h2>
The algorithm described above performs a "one-step" alignment, finding embeddings for both data sets at the same time. A similar effect can also be achieved with "two-step" alignments
<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>
, following a slightly modified procedure:

<ol><li>Project each input data set to a lower-dimensional space independently, using any of a variety of <a href="/facts/Nonlinear_dimensionality_reduction/1lL1Y0vN">dimension reduction</a> algorithms.</li>
<li>Perform linear manifold alignment on the embedded data, holding the first data set fixed, mapping each additional data set onto the first's manifold. This approach has the benefit of decomposing the required computation, which lowers memory overhead and allows parallel implementations.</li></ol>
<h2 id="instance-level-vs-feature-level-projections">Instance-level vs. feature-level projections</h2>
Manifold alignment can be used to find linear (feature-level) projections, or nonlinear (instance-level) embeddings. While the instance-level version generally produces more accurate alignments, it sacrifices a great degree of flexibility as the learned embedding is often difficult to parameterize. Feature-level projections allow any new instances to be easily embedded in the manifold space, and projections may be combined to form direct mappings between the original data representations. These properties are especially important for knowledge-transfer applications.

<h2 id="applications">Applications</h2>
Manifold alignment is suited to problems with several corpora that lie on a shared manifold, even when each corpus is of a different dimensionality. Many real-world problems fit this description, but traditional techniques are not able to take advantage of all corpora at the same time. Manifold alignment also facilitates <a href="/facts/Transfer_learning/pNz4P2KP">transfer learning</a>, in which knowledge of one domain is used to jump-start learning in correlated domains.
Applications of manifold alignment include:

<ul><li><a href="/facts/Cross-language_information_retrieval/UUKQQvWY">Cross-language information retrieval</a> / automatic translation<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
<ul><li>By representing documents as vector of word counts, manifold alignment can recover the mapping between documents of different languages.</li>
<li>Cross-language document correspondence is relatively easy to obtain, especially from multi-lingual organizations like the <a href="/facts/European_Union/6GYcR8qM">European Union</a>.</li></ul></li>
<li>Transfer learning of policy and state representations for reinforcement learning<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a></li>
<li>Alignment of <a href="/facts/Nuclear_magnetic_resonance_spectroscopy_of_proteins/lCIXAFzQ">protein NMR</a> structures<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a></li>
<li>Accelerating model learning in robotics by sharing data generated by other robots <a class="footnote-ref" id="fnref:12" href="#fn:12">12</a></li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Manifold_hypothesis/TYBW1Czr">Manifold hypothesis</a></li></ul>

<h2 id="further-reading">Further reading</h2>
<ul><li>Xiong, L.; F. Wang; C. Zhang (2007). "Semi-definite manifold alignment". Proceedings of the 18th European Conference on Machine Learning. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.7346">10.1.1.91.7346</a>.</li>
<li>Wang, Chang; Sridhar Mahadevan (2009). <a href="https://people.cs.umass.edu/~mahadeva/papers/aaai2009.pdf">"A General Framework for Manifold Alignment"</a> (PDF). AAAI Fall Symposium on Manifold Learning and Its Applications.</li>
<li>Wang, Chang; Sridhar Mahadevan (2010). <a href="http://www.cs.umass.edu/~mahadeva/papers/UM-CS-2010-049.pdf">"Multiscale Manifold Alignment"</a> (PDF). Univ. Of Massachusetts TR UM-CS-2010-049.</li>
<li>Ma, Yunqian (Apr 15, 2012). <a href="https://books.google.com/books?id=LjeGZwEACAAJ&q=Manifold+Learning:+Theory+and+Applications">Manifold Learning Theory and Applications</a>. Taylor & Francis Group. p. 376. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-4398-7109-6.</li>
<li><a href="http://www.cs.umass.edu/~chwang/home/ma-html">Chang Wang's Manifold alignment overview</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Ham, Ji Hun; Daniel D. Lee; Lawrence K. Saul (2003). "Learning high dimensional correspondences from low dimensional manifolds" (PDF). Proceedings of the Twentieth International Conference on Machine Learning (ICML-2003). <a href="ftp://ftp.cis.upenn.edu/pub/datamining/public_html/ReadingGroup/papers/corr_icmlws03.pdf" target="_blank">ftp://ftp.cis.upenn.edu/pub/datamining/public_html/ReadingGroup/papers/corr_icmlws03.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Hotelling, H (1936). "Relations between two sets of variates" (PDF). Biometrika. 28 (3–4): 321–377. doi:10.2307/2333955. JSTOR 2333955. <a href="http://cbio.ensmp.fr/~jvert/svn/bibli/local/Hotelling1936Relation.pdf" target="_blank">http://cbio.ensmp.fr/~jvert/svn/bibli/local/Hotelling1936Relation.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Belkin, M; P Niyogi (2003). "Laplacian eigenmaps for dimensionality reduction and data representation" (PDF). Neural Computation. 15 (6): 1373–1396. CiteSeerX 10.1.1.192.8814. doi:10.1162/089976603321780317. S2CID 14879317. <a href="http://www.cse.ohio-state.edu/~mbelkin/papers/LEM_NC_03.pdf" target="_blank">http://www.cse.ohio-state.edu/~mbelkin/papers/LEM_NC_03.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Ham, Ji Hun; Daniel D. Lee; Lawrence K. Saul (2005). "Semisupervised alignment of manifolds" (PDF). Proceedings of the Annual Conference on Uncertainty in Artificial Intelligence. <a href="http://cseweb.ucsd.edu/~saul/papers/semi_aistats05.pdf" target="_blank">http://cseweb.ucsd.edu/~saul/papers/semi_aistats05.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Wang, Chang; Sridhar Mahadevan (2009). Manifold Alignment without Correspondence (PDF). The 21st International Joint Conference on Artificial Intelligence.[permanent dead link‍] <a href="http://www.cs.umass.edu/~chwang/papers/IJCAI-2009-MA.pdf" target="_blank">http://www.cs.umass.edu/~chwang/papers/IJCAI-2009-MA.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Wang, Chang; Sridhar Mahadevan (2011). Heterogeneous Domain Adaptation using Manifold Alignment (PDF). The 22nd International Joint Conference on Artificial Intelligence. Archived from the original (PDF) on 2012-04-15. Retrieved 2011-12-14. <a href="https://web.archive.org/web/20120415030530/http://www-all.cs.umass.edu/~chwang/IJCAI2011-DA.pdf" target="_blank">https://web.archive.org/web/20120415030530/http://www-all.cs.umass.edu/~chwang/IJCAI2011-DA.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Lafon, Stephane; Yosi Keller; Ronald R. Coifman (2006). "Data fusion and multicue data matching by diffusion maps" (PDF). IEEE Transactions on Pattern Analysis and Machine Intelligence. 28 (11): 1784–1797. CiteSeerX 10.1.1.419.1814. doi:10.1109/tpami.2006.223. PMID 17063683. S2CID 1186335.[permanent dead link‍] <a href="http://www.eng.biu.ac.il/~kellery1/share/dataanalysis/kernel%20methods/Data%20Fusion%20and%20Multicue%20Data%20Matching%20by%20Diffusion%20Maps.pdf" target="_blank">http://www.eng.biu.ac.il/~kellery1/share/dataanalysis/kernel%20methods/Data%20Fusion%20and%20Multicue%20Data%20Matching%20by%20Diffusion%20Maps.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Wang, Chang; Sridhar Mahadevan (2008). Manifold Alignment using Procrustes Analysis (PDF). The 25th International Conference on Machine Learning.[permanent dead link‍] <a href="http://www.cs.umass.edu/~chwang/papers/ICML-2008.pdf" target="_blank">http://www.cs.umass.edu/~chwang/papers/ICML-2008.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Wang, Chang; Sridhar Mahadevan (2008). Manifold Alignment using Procrustes Analysis (PDF). The 25th International Conference on Machine Learning.[permanent dead link‍] <a href="http://www.cs.umass.edu/~chwang/papers/ICML-2008.pdf" target="_blank">http://www.cs.umass.edu/~chwang/papers/ICML-2008.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Wang, Chang; Sridhar Mahadevan (2008). Manifold Alignment using Procrustes Analysis (PDF). The 25th International Conference on Machine Learning.[permanent dead link‍] <a href="http://www.cs.umass.edu/~chwang/papers/ICML-2008.pdf" target="_blank">http://www.cs.umass.edu/~chwang/papers/ICML-2008.pdf</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Wang, Chang; Sridhar Mahadevan (2008). Manifold Alignment using Procrustes Analysis (PDF). The 25th International Conference on Machine Learning.[permanent dead link‍] <a href="http://www.cs.umass.edu/~chwang/papers/ICML-2008.pdf" target="_blank">http://www.cs.umass.edu/~chwang/papers/ICML-2008.pdf</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Makondo, Ndivhuwo; Benjamin Rosman; Osamu Hasegawa (2015). Knowledge Transfer for Learning Robot Models via Local Procrustes Analysis. The 15th IEEE-RAS International Conference on Humanoid Robots (Humanoids). CiteSeerX 10.1.1.728.8830. doi:10.1109/HUMANOIDS.2015.7363502. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
</ol>

Manifold alignment open-in-new

Manifold alignment