Topological Constraints on Homeomorphic Auto-Encoding
Pim de Haan Luca Falorsi


Quantum Adiabatic Algorithm Design using Reinforcement Learning
    Xiaopeng Li
    December 30, 2023
===============================================================




When doing representation learning on data that lives on a known non-trivial manifold embedded in a high dimensional space, it is natural to desire the encoder to be homeomorphic when restricted to the manifold, so that it is bijective and continuous with a continuous inverse.
Using topological arguments, we show that when the manifold is non-trivial, the encoder must be globally discontinuous and propose a universal, albeit impractical, construction. In addition we derive necessary constraints which need to be satisfied when designing manifold-specific practical encoders.
These are used to analyse candidates for a homeomorphic encoder for the manifold of 3D rotations SO(3).




§ INTRODUCTION


Unsupervised learning attempts to learn to encode data living in a high dimensional space in a more useful low dimensional representation.
This is often reasonable assuming the manifold hypothesis, which states that real world high dimensional data lives on a low dimensional manifold.

Popular methods methods for representation learning, such as Auto-Encoders, learn an encoder which represents the data in Euclidean spaces as well as a decoder that reconstructs the original representation from the latent space. However, when the true manifold of the data has a non-trivial topology, encoding the data in a Euclidean space leads to poor representations.

In such scenarios, one of two things can happen. When the latent space is sufficiently bigger than the intrinsic dimensionality of the true manifold, the true manifold is again embedded in the latent space, which leads to low density areas in the latent space. In the other case, when the dimensionality of the Euclidean latent space is comparable to the dimensionality of the true manifold, but the true manifold can not be embedded in the latent space, the encoder must be discontinuous. This problem was described in <cit.> and <cit.>

In many situations, the true manifold is a known non-trivial manifold, for example, when inferring the pose of an object from images in an unsupervised fashion or when inferring joint angles of images of a robot arm. Three natural requirements of an ideal auto encoder can then be formulated. Firstly, we desire the encoder to be bijective, so that every element of the latent space corresponds to exactly one point on the data manifold. Secondly, we desire continuous trajectories on the data manifold, such as motion of robot joint angles, to correspond to continuous trajectories in the latent space. Last, we desire conversely that continuous paths in the latent space correspond to continuous paths on the data manifold, which is to say that latent space interpolations are correct. An encoder that satisfies these requirements is referred to in topology as a homeomorphism. When combined with a suitable decoder, we call it a Homeomorphic Auto-Encoder. However, the concept translates to popular representation learning methods like the Variational Auto-Encoder, BiGAN and InfoGAN as well.

One immediate consequence of having a homeomorphic encoder is that the latent space is homeomorphic to the true data manifold. This rules out Euclidean spaces for non-trivial true data manifolds. Since neural networks only map to Euclidean spaces, they must be combined with specifically designed functions. Topological arguments allows us to derive necessary and sufficient conditions for such a construction to be a homeomorphic Auto-Encoder.




§ THE ENCODER IS GLOBALLY DISCONTINUOUS

We assume the data lives on a path connected manifold
 topologically embedded in the data space := ^n for some n with embedding i : ↪. The image of the embedding is submanifold ' := i()⊆. We desire encoder ψ : → to be such that its restriction ψ' := ψ|_' is a homeomorphism.
By the following theorem, this immediately leads to a somewhat surprising observation: when  is non-trivial, the encoder must be globally discontinuous, even though it is continuous when restricted to '.






Let ψ be defined as above. Assume additionally that ψ is continuous, in which case ψ is a retract. Then for all k, the k-th homotopy group of , π_k(), is isomorphic to a subgroup of π_k().


i and ψ induce k-th homotopy group homomorphisms: ψ_*:π_k() →π_k() and i_*:π_k() →π_k().
By construction, the function ψ∘ i: → is a homeomorphism, so (ψ∘ i)_*=ψ_*∘i_*:π_k() →π_k() is a group automorphism. Thus i_* must be injective, which implies the thesis.


Let ψ, be defined as above. Assume  having a non-trivial k-th homotopy group for some k. Then no such ψ exist that is additionally continuous.








§ EXISTENCE OF THE ENCODER

We now turn to the question of whether a homeomorphic auto-encoder can always be constructed. Since Neural Networks only map Euclidean spaces to Euclidean spaces, we decompose our encoder ψ = ϕ∘ξ, for ξ : → to be learned by a Neural Network, with  a Euclidean space, and a designed function ϕ : →. In the following subsections, we discuss the existence of ϕ and ξ.



 §.§ Existence and continuity of the map →



Assuming the dimensionality of  is sufficiently large, an embedding can be constructed for any manifold , by the Whitney Embedding Theorem (Theorem 2.6 in <cit.>), which states that any manifold of d dimensions can be embedded in ^2d+1 as a closed subset. 
We take this Euclidean space to be  and call the closed embedding j : →. 

Then the metric projection can be defined in the following way.

For any x ∈, we can define the distance to j():

    d_j()(x) := inf_y ∈ j()x-y = min_y ∈ j()x-y

where the last equality holds since j() is closed. Then the metric projection is:

    π_j()(x) = _y ∈ j()x-y



The projection map may have multiple value may be discontinuous, but the following lemma shows that it is uniquely defined almost everywhere in  and that the projection map is continuous almost everywhere.

Thus it is a potential candidate for the desired mapping.


For a closed set C ⊆^n, for almost all points x ∈^n, there is a unique point y ∈ C, such that d_C(x)=x-y. Additionally, the metric projection is continuous almost everywhere.

First, we show that d_C is 1-Lipschitz. Let x,y ∈^n. Without loss of generality, choose d_C(x) ≥ d_C(y) and let w ∈ C s.t. d_C(y)=y-w. Then:

    | d_C(x) - d_C(y) | = inf_z ∈ Cx- z - y- w≤x- w - y- w≤x- y

where in the last step we used the triangle inequality.

Therefore, by Rademacher's theorem <cit.>, d_C is differentiable almost everywhere.

The envelope theorem in <cit.> states that if d_C is differentiable in x ∈^n and y∈ C s.t. d_C(x)=d(x,y), then ∇ d_C(x) = ∇_x d(x, y), so that:

    ∇ d_C(x) = ∇_x x - y  = x-y/x-y


From this expression of the gradient, we can derive uniqueness of the minimising point. Let d_C be differentiable at x and let y and y' have that d_C(x) =x-y=x-y', we have:

    ∇ d_C(x) = x-y/x-y=x-y'/x-y' y=y'

Furthermore, we have, for all x such that d_C is differentiable:

    π_C(x)=x-d_C(x)∇ d_C(x)

so that π_C is continuous almost everywhere.



The case of the hypersphere S^n nicely illustrates these properties. The manifold can be embedded in ^n+1 and the projection map is the normalisation: ϕ : ^m+1→ S^n : ↦ /. This map is well-defined and continuous everywhere, except on the set containing just the origin, which is of measure 0. In this particular case the projection map is easily computable and smooth almost everywhere, but this is not the case for any manifold. 




 §.§ Existence and continuity of the map →

By the above argument we can construct an embedding j : → and a map ϕ : → such that ϕ∘ j = id_ and we assumed an embedding i: → exists.
Then the function ξ' := j ∘ i^-1 : i() → j(), is a homeormorphism.

Since both  and  are Euclidean, by the Tietze extention theorem <cit.>, this map can be extended from the closed set ' to the entire space , making a continuous map ξ : →.
Since neural networks can approximate continuous functions arbitrarily well <cit.>, we can then try to learn a neural network to approximate ξ.





§ CONSTRAINTS ON A PRACTICAL ENCODER

We can therefore always construct a homeormorphic auto-encoder ψ: → that is continuous almost everywhere, but the projection map may not be differentiable, nor easily computable, in which cases it is impractical for the learning the neural network. For many manifolds  a practical alternative can instead be hand-crafted. For such a construction we can derive several necessary conditions.




 §.§ Decomposing the encoder

Knowing that the encoder must be discontinuous for non-trivial manifolds, it can always be decomposed in the composition of a continuous function ξ, a discontinuous function g and a continuous function h, where ξ and h are possibly identity maps. We can then define spaces as in Figure <ref>.




We additionally define subsets: ' := i(), ' := ξ('), ' := g(') and restricted maps ξ' := ξ|_', g' := g|_',h' := h|_' so that ψ' = h' ∘ g' ∘ξ'.




 §.§ Necessary conditions

When designing such an encoder, care has to be taken to ensure that the intermediate spaces and functions are such that it is possible to express a homeomorphic encoder. This leads to the following necessary conditions.

    

Let ξ, ξ', , , i and ℳ be defined as above. If  is additionally compact and  Hausdorff, then ξ' is a homeomorphism and  is embeddable in .

As defined above, ξ is continuous and ξ' bijective, so ξ' is continuous bijective.
Since  compact then ' is also compact.
Let C be any closed subset of ', then C compact. Now, since continuous maps map compact sets to compact sets then ξ'(C) is compact and, since ' subspace of an Hausdorff space is Hausdorff, ξ'(C) is closed. ξ' is thus closed.
Then ξ' is a homeomorphism and ξ'∘ i is an embedding of  in Y




Let h, h', ,  and ' be defined as above.
If additionally ' is compact then h' is a homeomorphism and  is embeddable in .

As defined above, h is continuous and h' bijective, so h' is continuous bijective.
Since ' compact, h' is closed, following an argument similar to the proof of Lemma <ref>, thus h' is a a homeomorphism. h'^-1 is an embedding of ℳ in .



Let h, h', ,  and ' be defined as above.
Alternatively if we additionally assume  is compact, then the continuity of h implies that ' is compact, since ' = h^-1() is closed and thus compact in .


Since we want to use neural networks to learn a homeomorphic mapping of ' to , we need to be able to be able to apply gradient descent methods. In order for this to be possible we need the discontinuity points of g to be negligible (for example sets of measure 0), or to add constraints on ξ to encourage ' to lie outside of the discontinuity regions. If we make this latter modelling choice, we then see that  needs to be embeddable in all intermediate spaces:

Let ψ, ψ', ξ, ξ', g, g', h, h', , ', , , ' and  be as defined above.
If additionally g' is assumed to be continuous, then ξ', g', h' are all homeomorphisms and  must be embeddable in ,  and .

Notice that by construction ξ', g', h' are bijective functions.
We prove that h' is open: Take A open in ', since ξ', g' are continuous then Ã:= (ξ'∘ g')^-1(A) is open in '. Now since ψ' is a homeomorphism h'(A) = ψ'(Ã)⊆' is open.
Now using that h'^-1∘ψ is a homeomorphism we can prove that g'; is open.

Finally using that g'^-1∘ h'^-1∘ψ is a homeomorphism we can prove that g'; is open.

From this the thesis follows.



Let h, h',  and  be defined as above.
If h' additionally is a homeomorphism, by Theorem <ref> using the fact that h is continuous, h is a retract, so for all k, the k-th homotopy group of , π_k(), is isomorphic to a subgroup of π_k().




§ APPLICATION TO SO(3)

To show the utility of the proposed theory we it analyse four sensible candidate architectures for a homeomorphic encoder to the compact manifold of 3D rotations SO(3). The candidates are taken from <cit.>.
Throughout the next lines we will indicate with ξ:→ℝ^n a neural network and we will use the fact that π_1(SO(3))= ℤ/2ℤ.



  
Exponential map:
ξ:→ℝ^3, g:=𝕀, h:=exp:ℝ^3→ SO(3) where exp is the exponential map from the Lie algebra to the Lie group, which is always continuous and surjective for SO(3). The encoder h∘ g∘ξ is globally continuous, this contradicts the necessary condition following from Theorem <ref>.



  
Quaternions:
ξ:→ℝ^4, g:ℝ^4→ S^3, ↦, h:S^3 → SO(3)
where h is the surjective continuous map from quaternions to SO(3).
Since S^3 is compact, then Lemma <ref> applies. Since S^3 is simply connected, this contradicts the necessary condition following from Corollary <ref>.



  
Axis-Angle[Here, v_1,v_2 indicate the components of S^1⊆ℝ^2, and [·]_×:ℝ^3→𝔰𝔬(3) the vector space isomorphism that maps ℝ^3 to the lie algebra of SO(3), i.e. the space of skew-symmetric 3× 3 real matrices]:
ξ : →ℝ^3 ×ℝ^2,   
g:ℝ^3×ℝ^2→ S^2× S^1, (,)↦ (,) 
   h:S^2× S^1→ SO(3), (,)↦ I + v_1·_× + v_2·_×^2
where S^2× S^1 correspond to the axis and the angle of the rotation. Since S^2× S^1 is compact, then by Lemma <ref>, h' must be a homeomorphism, and thus SO(3) embeddable S^2× S^1, which is false. Thus the necessary conditions are not met.



  
Basis:
ξ:→ℝ^3×ℝ^3,   
g:ℝ^3×ℝ^3→ S^2× S^2, (,)↦ (,), 
    h:S^2× S^2→ SO(3), (𝐮, ) ↦concat(𝐰_1, 𝐰_2, 𝐰_3), 
   𝐰_1 = 𝐮, 𝐰_2' =  - ⟨𝐮,⟩𝐮, 𝐰_2 = 𝐰_2'/𝐰_2', 𝐰_3 = 𝐰_1×𝐰_2
This follows from the fact that SO(3) can be seen as the (oriented) bases of a three dimensional space. This construction satisfies the sufficient condition following from Lemma <ref>.
We see this by defining ϕ:= h∘ g: ^3 ×^3 → SO(3) and ':= {(,)∈^3 ×^3: ==1, ⟨,⟩ = 0}, then ϕ satisfies the hypothesis of Lemma <ref>. In fact ϕ' is a homeomorphism since for the SO(3) matrices, the last column is automatically determined by the first two.

Note that these theoretical results are consistent with the experimental results in <cit.>, where it was found that only the `Basis' method learns a homeomorphic encoder.



§ CONCLUSIONS AND FUTURE WORK

We developed a theoretical framework for the analysis of architectures of Auto-Encoders for non-trivial manifolds. Several necessary conditions were stated for the Auto-Encoder to be homeomorphic, as well as a sufficient condition, which can guide the development of homeomorphic Auto-Encoders for various manifolds. For the SO(3) manifold it was found that the theoretical results were consistent with experimental results in prior work.

In future work we will try to generalise the developed  theory using other topological invariants besides homotopy and to situations where the manifold is not embedded, but imbedded or embedded with symmetries.
In addition we would like to analyse what happens when the embedding is noisy in a probabilistic framework.
Closer attention will be given to investigating to what extent these results are relevant for supervised problems, such as pose estimations.
Finally we will try to apply the principles of the homeomorphic Auto-Encoders to practical problems and existing architectures, such as a version of <cit.> without supervised pose labels.



  §.§.§ Acknowledgments

We would like to thank Patrick Forré for his suggestions on improving an earlier draft and Tim Davidson and Taco Cohen for their helpful discussions.

apalike




