Chart Auto-Encoders for Manifold Structured  Data
Authors: Stephan Schonsheck
Jie Chen
Rongjie Lai
Venue:  (2020)
Keywords: Auto-encoder
differential manifolds
multi-charted latent space

Abstract:  Auto-encoding and generative models have made tremendous successes in image and signal representation learning and generation. These models, however, generally employ the full Euclidean space or a bounded subset (such as $[0,1]^l$) as the latent space, whose trivial geometry is often too simplistic to meaningfully reflect the structure of the data. This paper aims at exploring a nontrivial geometric structure of the latent space for better data representation. Inspired by differential geometry, we propose \textbf{Chart Auto-Encoder (CAE)}, which captures the manifold structure of the data with multiple charts and transition functions among them. CAE translates the mathematical definition of manifold through parameterizing the entire data set as a collection of overlapping charts, creating local latent representations. These representations are an enhancement of the single-charted latent space commonly employed in auto-encoding models, as they reflect the intrinsic structure of the manifold.  Therefore, CAE achieves a more accurate approximation of data and generates realistic new ones. We conduct experiments with synthetic and real-life data to demonstrate the effectiveness of the proposed CAE. 

Under review as a conference paper at ICLR 2020
CHART AUTO-ENCODERS FOR MANIFOLD STRUCTURED DATA
Anonymous authors Paper under double-blind review
ABSTRACT
Auto-encoding and generative models have made tremendous successes in image and signal representation learning and generation. These models, however, gen- erally employ the full Euclidean space or bounded subset (such as [0. 1)/) as the latent space, whose flat geometry is often too simplistic to meaningfully reflect the topological structure of the data. This paper aims at exploring universal ge- ometric structure of the latent space for better data representation. Inspired by differential geometry, propose Chart Auto-Encoder (CAE), which captures the manifold structure of the data with multiple charts and transition functions among them. CAE translates the mathematical definition of manifold through pa- rameterizing the entire data set as a collection of overlapping charts, creating local latent representations. These representations are enhancement of the single- charted latent space commonly employed in auto-encoding models, as they reflect the intrinsic structure of the manifold. Therefore, CAE achieves a more accurate approximation of data and generates realistic synthetic examples. We demonstrate the efficacy of CAES through series experiments with synthetic and real-life data which illustrate that CAEs can out-preform variational auto-encoders on recon- struction tasks while using much smaller latent spaces.
INTRODUCTION
Autoencoding (Bourlard & Kamp 1988 Hinton & Zemel, 1994 Liou et al. 2014) a central tool
in unsupervised representation learning. The latent space therein captures the essential information of a given data set, serving the purposes of dimension reduction, denoising, and generative mod- eling. Even for models such as generative adversarial networks (Goodfellow et al. (014) that do not employ an encoder, the generative component starts with a latent space. A common practice is to model the latent space as low-dimensional Euclidean space IR' or bounded subset of it (e.g., [o, 1])), sometimes equipped with a prior probability distribution. Such spaces carry far simple ge- ometry and may not be adequate for representing complexly structured data. In this work, we concerned with a widely studied structure: manifold.
A commonly held belief, known the Manifold Hypothesis (Belkin & Niyogi 2003 Fefferman
jet al., (016)), states that real-world data often lies on, or at least near, some low -inedinnniional mani- fold embedded in the high-dimensional ambient space. Hence, a natural approach to representation learning is to introduce a low-dimensional latent space to which the data is mapped. It is desirable that such a mapping possesses basic properties such as invertibility and continuity. In differential geometry, such a notion is coined homeomorphism. Challengingly, it is known that even for some simple manifolds, there does not always exist homeomorphie mapping to the Euclidean space of the intrinsic dimension of the data. We elaborate two examples such examples next.
Consider a data set X lying on the 2-dimensional sphere 5 embedded in the ambient space Th where n 2 3. It is well known that there exist no homeomorphic maps between S and an open domain on 2 (Rotman 2013). Therefore, is impossible for a traditional autoencoder with a 2- dimensional latent space to faithfully capture the structure of the data. Consequently, the dimension of the latent space needs be increased beyond the intrinsic dimension (two in this case). For another example, we show in Figure I a double torus. When one uses an autoencoder to map uniform data points on this manifold to ?.., the distribution of the points is distorted and the shape destroyed, whereas if maps to R.3 some of the points depart from the mass and become outliers. Fur-

---

Under review as a conference paper at ICLR 2020
chart 2D latent space
chart latent space
charts latent space
Data Manifold
Figure I: Left: Data on a double torus. Middle two: Data autoencoded to a flat latent space. Right: Data autoencoded 4-chart latent space.
thermore, in the appendix (see Figure demonstrate that increasing the number of parameters of the autoencoder does not help overcome the coverage issue when the latent space is a single 2 2-dimensional space.
To better reflect structures, in this work, we follow the definition of manifolds in differential geome- try and propose Chart Auto-Encoder (CAE) for learning low-dimensional representation of data lying on a manifold. Rather than using a single function mapping, the manifold is parameterized by collection of overlapping chart functions, each of which describes local neighborhood and they collectively cover the entire manifold. To the right of Figure [ aforementioned, now encoded by using four color-coded charts. One sees that the encoding result faithfully preserves the shape of the data set, as well as the topology (two holes).
we show the same double torus
To realize the parameterization, we develop a neural network architecture and propose training regime to implement it. We conduct a comprehensive set of experiments on both synethic data and real-world data to demonstrate that CAE captures much better the structure of the data and enriches the understanding of them.
RELATED WORKS
One common approach enhancing the capability of autoencoders is to impose a prior distribution on the flat Euclidean latent space, as in variational autoencoders (VAE) (Kingma & Welling (013)). The distributional assumption (e.g., Gaussian) introduces low-density regions that sometimes depart from the manifold. Then, paths in these regions will either trace off the manifold or become in- variant. Falorsi et al.] (2018) introduce non-Euclidean latent space to guarantee the existence of homeomorphic representation by using a so-called homeomorphic variational autoencoder (HVAC). There are two disadvantages of this approach. First, it requires class of the data set, which can be extremely difficult for real-world data. Secondly. it requires the computation (or estimation) of the Lie group action on the latent space. the topology of the data is relatively simple (e.g., sphere torus), the computation is possible, but for more complex objects the estimation is much difficult. Similarly, several recent works (Davidson et al.) 2018 Rey 2019] Falorsi 2018) have studied autoencoders with (hyper)-spherical latent spaces. These methods allow for the detection of cyclical features, but offer little insight into the homology of the manifold, since it will always be represented by compact genus-zero surface.
user to know the topological
Exploring the low-dimensional structure of manifolds has led to many dimension reduction tech-
niques in the past two decades (Tenenbaum al. 22000 Roweis & Saul 2000; Cox & Cox 2001
Belkin & Niyogi 2003, He & Niyogii 2003] Zhang & Zhal 2004]] Kokiopoulou & Saad 2007
van der Maaten Hinton] (008). Isomap (Tenenbaum et al., 2000) divides a data set into local
neighborhoods, which are embedded into a low-dimensional space that preserves local properties.
Similarly, Laplacian Eigenmaps (Belkin & Niyogi 2003) use embeddings induced by the Laplace- Beltrami eigen-functions to represent the data. These methods employ flat Euclidean space for embedding and may lose information as aforementioned. Recently, Lei et al. (2019) considers a manifold point of view explain Wasserstein generative adversarial network (WGAN) using opti-
mal transport by minimizing a distance between a manifold parameterize by a neural network and estimated from some training data.
2

---

Under review as a conference paper at ICLR 2020
Under the manifold hypothesis Chen et al. (2019) extend the work of [hahaam al. (2018) and show the theoretical existence of neural networks that approximate functions supported on low- dimensional manifolds, with number of parameters only weakly dependent on the embedding dimension. A key feature in their proposal is a chart determination sub-network that divides the manifold into charts and pairing sub-network that re-combines them. All existing methods only have theoretical consideration of chart structure for data manifolds and assume that the manifold in question known. However, multi-chart latent space representations have not been implemented and conducted computationally. Moreover, part of the constructions relies on information of the underlying manifold, which is unavailable in most real-world applications. Additionally, important questions regarding the loss function and the training method remain open. Our work introduces an implementable neural network architecture which able to address these challenges by directly approximating the data manifold.
2 BACKGROUND ON MANIFOLDS AND CHART BASED PARAMETERIZATION
A manifold is topological space locally homeomorphic to Euclidean domain. More formally, a d-dimensional manifold defined as a collection of pairs {(Ma; (MMa,)))mm (o))a. referred to as charts, where {Ma) are open sets satisfying M = =U. Ma. Each MM is homeomorphic to open set Ua C Rd through coordinate map da MM + Ua. Different charts may be glued together through transition functions dag &a (Ma n (Ma)) - és(Ma MMa)) satisfying cyclic conditions (see Figure (euure@let))
leftt. Smoothness of the transition functions controls the smoothness of the manifold. A well-known result from differential geometry states that any compact manifold can be covered by finite number of charts which obey these transition conditions. The intrinsic dimension of the manifold is the dimension of U,. See See (2033) for a thorough review.
In practice, the coherent structure of data motivates unknown ground manifold. One crucial task in machine learning is to explore the topological and geometric structure of the manifold and perform tasks such classification and data generation. Mathematically, we explain the encoding and decoding process for a manifold as follows. Given some manifold M, usually embedded in a high dimension ambient space R", the encoding network constructs a local parameterization &a from the data manifold to the latent space Un: and the de- coding network maps U,, back the data manifold M through Φ_1 standard autoencoders, only one single chart U., is used as the latent space. In our work, multiple charts are used. Different from classical dimension reduction methods where distance preservation is preferred, we do not require the local parameterization da to preserve metric but only bound its Lipschitz constant control the regularity of the parameterization (see Section for more details).
model given data as samples from
Parametrization Latent Space
Encoder
Finite Continuous Finite VC
Rep.
Rep.
Data Manifold
(-0,, so)
(cox(z), sin(z))
No
Yes
No
Pa
PPs
[0.2mt
(cos(2). sin(2)) jaar))
Yes
Qup :appaee
(-5, πC- U (cos(2), sin(2))e
3
(66,1+6)
(-cos(2), -sin(2) (Sunts)
Yes
Yes
Yes
Figure 2: Left: Illustration of a manifold. Right: Possible parameterizations of a circle. The mani- fold approach (bottom) preserves all desired properties.
To illustrate the utility of such multi-charted parameterizaaion, we consider a simple example: find a latent representation data sampled from a I-dimensional circle 5a embedded in IR.. See Fig- ure right. A simple (non-chart) parameterization is (cos(z), <in())) with (-o,, oo). However, approximating this parameterization with a finite neural network is impossible, since x is unbounded and hence any multi-layes perceptron will have an infinite Vapnik-Chie Senni--hhrvvoenkiss. dimension (Blumer et al. 1989). One obvious alternative is to limit & E [0, 2Tr), but this parameterization introduces a discontinuity and breaks the topology (it is theoretically known that the closed circle is not homeo-
3

---

Under review as a conference paper at ICLR 2020
morhpic to [0, 2T)). Following the definition of manifold, instead parameterize the circle as:
&a : 6, + + 8²
Za + (cos(z), sin(2))
( 6, + + 0as : (-6,6) + (nT 6
2B + (- cos(22 sin
Za aa
0ag : 6, + (-
Za H Za
Although this function is more cumbersome to write, it is more suitable for representation learn- ing, since each encoding function be represented with finite neural networks. Moreover, the topological and geometric information of the data is maintained.
Thus, instead of using only chart in standard autoencoders (Bourlard & Kamp 1988 Hinton & Zemel 1994; Liou et al. (2014), we propose to model the latent space with multiple charts glued by their transition functtion, akin to the concept of manifold. This geometric construction reflects the intrinsic structure of the manifold. Therefore, it is able to achieve more accurate approximation of the data and generate realistic new ones. Moreover, once the charts and the associated transition functions are learned, the geometric information of the data manifold, including metric, geodesics, and curvatures, can be approximated according to their definitions differential geometry. Thus, this multi-chart latent construction leads to a better geometric understanding of the manifold.
NETWORK ARCHITECTURE
To integrate manifold structure the latent space, we investigate a new representation of latent space based on a multi-chart structure. We implement novel network architecture to learn the multi-chart latent space and transition functions. The proposed network architecture, illustrated Figure 3 can be summarized as follows: An input data is passed into an encoding module, which creates an initial latent representation. Next, a collection chart paramterizations- encoders E, as analogy of -ammap the initial latent representation to N different chart spaces Ua. which provides the new multi-chart latent space. Each chart representation then passed into a decoding function, a decoder D; as analogy of Φ_ which produces approximation the input data. Finally, the chart prediction module decides which chart and the associated decoder best represent the data. As detailed in A.3 this architecture, along with the proposed loss function, naturally enforces the chart transitions without explicit computation.
Chart Transition Functions (0)z)
Chart Predicor P
Decoder
Chart
Latent Chart
Encoder Module
Chart Encoder Modulel E;
Chart Decoder
Input
Data
Latent Represenataion
Initial
Chart
Latent
D2
Output
Data
Latent Chart ZN
Chart Decoder N
Du
Figure 3: Architecture diagram CAE and transition functions. The red path illustrates the computation of transition function 112.
The initial encoder serves as a dimension reduction step to find low-dimensional isometric embedding of the data from R." to R!. For example, given an R torus embedded in I 1000 the initial encoder maps from IR 2000 to lower dimensional space, ideally IR3 (Note that however three is not the intrinsic dimension of the torus; rather, two is. Thus, subsequently we introduce chart encoders to map from the d-dimensional space to R².) We approximate this mapping using a neural net, denoted as E, with combination of fully connected and convolution layers (see section A.5 for details). We choose & n; this encoding can viewed as dimension reduction step. which prepares the data to be split into each of the multi-chart latent spaces. Ideally, this step preserves
Initial Encoder

---

Under review as a conference paper at ICLR 2020
the original topology and geometry information of the data set while also reducing its dimension to the minimal isometric embedding dimension of the manifold. It aims at improving computational efficiency for decoders multi-chart latent space. This step can be replaced with Homcomoric Variation Auto-Encoder in the cases where the topology of the data set is known (Falorsi et al.
2018), with an appropriately chosen random matrix projection (Baraniuk & Wakin 2009 Cai
et al. 2018
Chart Encoder This step provides parameterization of the data manifold locally to chart space, whose dimension is approximately close to the intrinsic dimension of the data manifold. This split- ting done with a small collection of networks {Ea} which takes 2 E IR' as input and outputs N local coordinates 2a E Ua- We denote the direct sum of these space as U = ① D= Ua. which is the proposed multi-chart latent space for our model. In practice, we choose Ua [o, 1J' and regularize the Lipschitz constant of the corresponding encoding map, control size and regularity of the region M. C MM paramterized by U (more details in section[4).
We remark that the proposed multi-chart architecture aims at constructing the correct latent space structure and understanding the geometric structure of the data manifold. The decoupled nature of the encoding operations mean that the model tends to be larger in terms of the number of parameters. However, the improvement shown in the experiments is not caused by the use of more parameters; rather, a correct latent space structure. Further experiments in Appendix [A. show that increasing the number of parameters in VAE alone (without increasing the latent dimension) does not allow one to simultaneously produce good reconstruction and generation. A latent space of too small dimension will not be able to cover a manifold, and one of a too large dimension will generate points far from the manifold. Thus, the structure of the latent space is more important than the number of parameters.
Decoders Each of the latent chart Ua is equipped with an associated decoder function Da. which maps from the chart latent space U. back to the ambient space. We represent each of these maps with a deep network, which are trained to reconstruct the input data.
Chart Selection There are several options to the chart selection module P for an input æ sam- pled in the data manifold. In general, this module must produce prediction or confidence measure (x))) Pz)) regarding which chart should be used for a given input. After training, this mod- ule can also be used to reduce the computational cost of evaluating the model, by ensuring that only a small set of decoder functions needs be evaluated for any input signal.
Output The output of the network will depend on the application and the training specifics (dis- cussed further in section 4.1.. In general, the network produces an internal latent representation (x) for an input ær a reconstruction signal & to check the fidelity of the system, as well as some confidence {Pa } in this prediction. Each of ya = D2 E, E(x) may be used as a proxy for y (and then each Pa can be interpreted as this probability)
some combination of the y may be used (in which case the Pa are interpreted as the partition of unity weights).
NETWORK TRAINING DETAILS
In this section, we explain several task specific modeling options, loss functions, regularization, and pre-training schemes that promote training efficiency of the proposed model.
4.1 CHART PREDICTION AND LOSS FUNCTIONS
The chart prediction module assigns any input to one or more charts. If the data manifold has relatively simple geometry, such a a circle, we may use the normalized distance from the data point to the center the patch for prediction. This procedure is extremely efficient, but is not sufficiently powerful in cases where the geometry is more complex. For example, for the same surface area, a high curvature may require many small charts to cover, whereas a flat region may need only one chart. In this case we can compute Pa with deep network, denoted as the chart predictor in Figure 3 using some combination of x, & and/or 2, as inputs. Using x as an input results in a network which is independent of the rest of the network (and can potentially be trained separately), but the
5

---

Under review as a conference paper at ICLR 2020
size and complexity of this network will depend on the ambient dimension of z. Using the internal representation 2 or & as an imput to this network allows the chart selection module to benefit from the dimension reduction of preformed by E.
We propose two loss functions which lead to two slightly different interpretations of the model, based on how to handle regions in which the charts overlap. In the first regime, we define decoder- wise loss for yo = D, о E, o E(x) as ca = || yall and an internal label la = softmax(<,). Then the PrauttPrediction Loss is given by:
N Σ p=1
Lcr(a, 0) min Ca)
&a log(ps);
(2)
where O are network parameters. The first term models the reconstruction error of the predicted chart and the second term is the log-like log-likelihood of the prediction, weighted by decoder-wise error.
The second regime is based on the idea of partition of unity idea (sseeDeng & Han (2008) for details). Here, we view Pa :M- + R as function with compact support in M, i.c. {2 E M Pa (x) of 0} C C.M Pa 2 0 for all a, and Σ. Pa 1. They serve as the partition of unity (See Figure 8 for example). Thus, we represent any point on the manifold as combination of the charts and use the confidence weights predicted by the chart predictor as the coefficients. The loss then given by the following Partition of Unity Loss:
LroU (I,, (): := |0- Σ
Pa
(3)
4.2 REGULARIZATION
Since it is impossible to know a priori the number of charts necessary to cover a given data set, we instead overparameterize the model by using many charts and enforce strong regularization on the decoder functions to eliminate unnecessary charts. Note that during training, a chart function (say E,) which is not utilized in the reconstruction of point (i.e. Pj R 0) does not get any update from the loss function. Then, adding any convex penalty centered at 0 to the weights result in weight decay and, if decoder is never utilized during training, its weights will go to zero. In practice, we can automatically remove these charts by eliminating them from the network when the norm of the decoder weights falls bellow some tolerance. This mechanism provides way of choosing the number of charts used in the network. Namely, we over estimate the number of charts and let the network automatically eliminate unnecessary ones, resulting an appropriate number.
E,will
We also introduce an additional regularization to stabilize the training of our network by balancing the size of Ma parameterized by E, and stopping a small number of charts from dominating the data manifold. For example, if we would like to use our network to model (finitely sampled) sphere 5², then we need at least two 2-dimensional charts. However, if we regularize a network with only 12 weight decay, it may be able to reconstruct the training data well with only one chart without capturing the true structure of the data (see right panel of Figure for such an example). To prevent this type of overreach, we add a Lipschitz regularization to the decoders to penalize how far away nearby inputs can be mapped. Formally, the Lipschitz constant a function is defined as: ((w)) Since the chart spaces are fixed as [0, 1]', controlling the Lipschitz constant of the encoder will control the max (euclidean) volume chart can map onto. To do this, we note that the Lipschitz constant of a composition of functions can be upper bounded by the multiplication of the Lipschitz constants of its constituent functions. The Lipschitz constant of a matrix is its spectral norm and the Lipsehitz constant of the ReLU is 1. Then, we can control the upper bound of the Lipschitz constant of an encoder function by regularizing multiplication of the spectral norm of its weights at each layer. Combining these ideas, and denoting the weights of the bth layer of E., as Wk we propose the following regularization on the decoder functions for a K-layer network:
sup,,y [z -z-
K
1 Σ +
RLip max
II W
II
|
ll2
(4)
N
k=1
0=1
6

---

Under review as a conference paper at ICLR 2020
Here the first term aims at stopping single chart from dominating, and the second term works weight decay which also promotes the smoothness of each chart.
4.3 PRE-TRAINING
Since our model jointly predicts the chart outputs and chart probabilities, it is important that our model is properly initialized, so that the range of each decoder lies somewhere on the manifold and the probability that a randomly sampled point lies in each chart is roughly equal. To do this, we begin by using the furthest point sampling (FPS) scheme to select N data points, {ra], from the training set which are 'far away" from each other. Then we assign each of these data points to decoder and train each one to reconstruct. Additionally, we train the encoder such that za is at the center of the chart space U.. We further define the chart prediction probability as the categorical distribution and use it to pre-train the chart predictor. Then the loss for the 3th initialization example is:
(xn) == || - Dg Eg E(za)lI + [| o E(zg) - [5] + Σ Sap log(Pa).
(5)
We can extend this idea of pre-training to also ensure that the charts are oriented consistently. Details are presented in A.4
We remark that the pre-tra pre-training network does not aim separating the data manifold as different clusters. The pre- pre-training works to ensure that each of the decoders is on the manifold, so that when training begins no decoders stay inactive. Since the chart selection module is learned in conjunction with the rest of the model, we do not assume any prior segmentation of the data. During training the charts will move, change sizes, overlap, or disappear.
NUMERICAL RESULTS
We present numerical results of several experiments to demonstrate the effectiveness of the proposed CAE. First, study three illustrative geometric scamples-spheee double torus, and genus-3 surface-to understand the behavior of the network. Afterward, we use the MINIST data set to further demonstrate the properties of CAE. In the end, we evaluate CAE and compare with other models on several metrics with the use of synethetic data sets as well as MNIST and SVHN.
5.1 ILLUSTRATIVE EXAMPLES
space
Upshitz Reqularizaiinn
Reqularization
-8
190
Figure 4: Left: Latent space. Middle: Model with Lipschitz Regularization. Right: Unregularized Model
In our first experiment illustrated in Figure we visualize the process of applying a four-chart CAE a data set sampled from the unit sphere (see Appendix AA.2 for the network architecture). We apply the proposed loss function with and without the Lipschitz regularization discussed in section 4.2 We use four copies of (0, 1)2 as the chart latent space in this experiment, We color code (0, 1)2 using the distance of each point to the origin. After training, we uniformly sample points on the latent space and use the learned decoders to generate points back to the unit sphere. As we can see from the middle panel of Figure the four charts, when glued together, successfully cover the unit sphere. Moreover, all charts occupy the data manifold in a balanced and regularized way; that is, even thought they are not uniform. single chart dominates the rest. From the right panel of Figure 4. we can see that, when no regularization is employed, the charts are less localized. This behavior shows the necessity of using Lipschitz regularization control the regularity of the decoder.
7

---

Under review as a conference paper at ICLR 2020
Our second experiment is conducted more complex object- the double torus torus-shown in Fig- ure The experiment illustrates some of the difficulties using traditional auto-encoders to capture topologically complex data. Here, the data manifold has local dimension of 2, but it is not home- omorphic to a plane. We uniformly sample the latent space of each model and apply the resulting decoder to generate points back to the ambient space. As we can from the second left plot in Figure [] traditional model with a 2-dimensional single-chart latent space cannot capture the over- all manifold. Since this object can be embedded in R. a model with a 3-dimensional latent space can capture the entire manifold. However, this type of model also likely generates points off the manifold, as we can see from the second right image in Figure [] Finally, we see that our CAE with four 2-dimensional charts can produce points successfully covering the objects without introducing unfaithful points.
Confidence
20.
Chart
10
Chart2
Chart3
Chart
ChartS
-00
Chartö
Chart?
Charl8
Figure 5: Left: Points sampled from high confidence regions. Right: Segmentation of manifold from chart selection
Next, we test our CAE on a genus-3 surface with ten 2-dimensional charts (detailed as CAE 2 in A.2). The left of Figure 5 shows the result of randomly sampling & in the chart latent space U, and decoding the latent representations. The right of this figure shows which chart is active in each region of the manifold. Since this model uses network predict the chart segmentation, the resulting parameterization has charts of varying sizes. This allows the network to place more charts in areas of high curvature, and allow charts grow over more linear regions. Nevertheless, this example demonstrates the effectiveness of our method to handle objects with complex topology.
5.2 THE MNIST MANIFOLD
We apply the 10-chart model on the MNIST data set (now using CAE as detailed in A.2 The left panel of Figure reports the reconstruction result in the training data, for a given image showed in the second last row. Each of the first ten rows the corresponding column shows the decoding result from the i-th chart. Note that while each decoder may produce vastly different outputs, the chart selection module chooses which is most likely to be correct. As we can observe from the image, the chart selection model successfully picks up the most faithful decoding result, repeat in the last row of the image. This picture shows that the proposed multi-chart auto-encoder does provide faithful reconstruction for the training data.
circle and
The middle panel of images generated from the corresponding decoder. Note that each chart produces only few digits, even though every digit is covered by some chart. Additionally, on any chart the digits which that chart produces are "close" to each other (for example the 3s and 8s in chart and the 5s and in chart 1). This means the multi-chart latent space can cover the MINST data manifold in balanced and regular way, similar what we observe from the experiments conducted for geometric objects. The right panel of this figure shows the morphing of '2' to '3' by interpolating linear path through the latent space. Since each of the latent representations decoded along this path produces output similar to examples found in the training set, we can conclude that approximation of the manifold given by our chart parameterization is close to the underlying distribution the training data is sampled from. In traditional approaches this is possible because the latent space (modeled normal distribution) is simply connected. Our model is able to do so without using a distributional assumptions, owing to the transition conditions and Lipshitz regularization.
decoding results by sampling the charts, where each row shows
8

---

Under review as a conference paper at ICLR 2020
Direct Reconstruction
Latent Sampeling
Digit Morphing
2
Taask
D
5
5
8
3
Skant
3
3
Figure 6: Left: Reconstruction of data from MNIST data Middle: Reconstruction from random
sample on the multi-chart latent space. Right: Digit morphing
5.3 MODEL EVALUATION
In this experiment, we apply four traditional models (2 auto-encoders and 2 variational auto- encoders) as well as three CAEs on several data sets. Details of the exact architecture of these networks can be found in A.2 For each model and data set, we are primarily interested in three measures of success, including reconstruction error, unfaithfulness, and coverage (See A. for de- tailed definitions). The reconstruction error measures the fidelity of the model. The unfaithfulness measures how far synthesized data decoded from samples drawn on the latent space are to samples from the original training data. Coverage indicates how much of the training data is covered by the encoder. Models which produce unrealistic data when sampling from the latent space will have high unfaithfulness sores and models which experience mode collapse will have low coverage scores.
We test these measurements on four data sets, the order from the simplest to the most complex. I Sphere: The data consists 2000 equally distributed points sampled uniformly form a sphere embedded in R.3 ② Genus The genus-3 object used in Figure 5 non-trivally embedded in MNIST: The MNIST hand-writted digits database containing 60k training and 10k testing images (LeCun et al.
R50 3
④ SVHN: A real-world image dataset from house numbers in Google Street View images. We focus on the individual digits problem and preprocess the images in gray scale (Netzer et al. (011). Results of the the evaluation metrics are summarized in Figure and
1990).
reported fully in Table in A.10
From these results, clearly the CAE models consistently preform better than other models with simple latent spaces. More specifically, when the dimension of the latent space is fixed, the CAE model preforms better than the associated VAE and AE in every test. Moreover, because of the Lipschitz regularization in our model, we are able to achieve much better coverage results than with the previous methods.
CONCLUSIONS AND FUTURE WORK
We have proposed and investigated the use of chart-based paramterization to model manifold struc- tured data, through introducing multiple-chart latent spaces, along with transition functions, to au- toencoders. The parameterization allows significantly reduce the dimension of latent encoding for efficiently representing data with complex structures. Numerically, we design geometric ex- amples to analyze the behavior of the proposed CAE and illustrate its advantage single-chart

---

Under review as a conference paper at ICLR 2020
Reconeination Erar
1//
Fathfalinss
V0E1
10
02
10
Figure 7: Summary of benchmark test on Sphere, Genus-3, MNIST and SVHN data sets
autoencoders. We also apply method to real-life data sets, including MNIST and SVHN, to demonstrate the effectiveness the proposed model.
We believe that the proposed chart-based parameterizaaton of manifold-structuree data provides many opportunities for further analysis and applications. In future work, we will extend this archi- tecture other generative models (e.g, GAN) and apply the machinery investigate the topology and geometry of real-world data.
REFERENCES
Martin Arjovsky, Soumith Chintala, and Léon Bottou. arXiv:/701.000 707877, 2017.
Wasserstein gan.
arXiv preprint
Richard G Baraniuk and Michael B Wakin. Random projections of smooth manifolds. Foundations of computational mathematics, 91)::11-77, 2009.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373-1333 2003.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapnik-chervonenkis dimension. Journal of the ACM (JACM), 36(4):929-965, 1989.
Hervé Bourlard and Yves Kamp. Auto-association by multilayer perceptrons and singular value decomposition. Biological cybernetics, 59(4-5):21--94, 1988.
Jian-Feng Cai, Dong Li, Jiaze Sun, and Ke Wang. Enhanced expressive power and fast training of neural networks by random projections. arXiv preprint arXiv:1811.09054 2018.
Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Efficient approximation of deep relu networks for functions low dimensional manifolds. arXiv preprint arXiv: 1908.01422 2019.
T.F. Cox and M.A.A. Cox. Multidimensional Scaling. Chapman and Hall, 2001.
Tim Davidson, Luea Falorsi, Nicola De Cao, Thomas Kipf, and Jakub M Tomezak. Hyperspheri- cal variational auto-encoders. arXiv preprint arXiv:1804.00891, 2018
Donggao Deng and Yongsheng Han. Harmonic analysis on spaces of homogeneous rype. Springer
Science & Business Media, 2008
Luca Falorsi, Pim de Haan, Tim Davidson, Nicola De Cao, Maurice Weiler, Patrick Forré, and Taco S Cohen. Explorations in homeomorphic variational auto-encoding. arXiv preprint arXiv: MrXiv:1807.04e 1807.04689, 2018.
Charles Fefferman, Sanjoy Mitter, and Hariharan Narayanan. Testing the manifold hypothesis. Journal of the American Mathematical Society, 1944 2016.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In NIPS, 2014.
Xiaofei He and Partha Niyogi. Locality preserving projections. In NIPS, 2003.
10

---

Under review as a conference paper at ICLR 2020
Geoffrey E Hinton and Richard S Zemel. Autoencoders, minimum description length and helmholtz free energy. In Advances in neural information processing systems, pp. 3-10, 1994.
Diederik Kingma and Max Welling. arXiv:1312.61 14, 2013.
Auto-encoding variational bayes. arXiv preprint
E. Kokiopoulou and Y. Saad. Orthogonal neighborhood preserving projections: A projection-base dimensionality reduction technique. IEEE Transactions Pultern Analysis and Machine Intelli- gence, 29(12)2143-2155 2007.
Yann LeCun, Bernhard Boser, John Denker, Donnie Henderson, Richard E Howard, Wayne Hubbard, and Lawrence D Jackel. Handwritten digit recognition with kack-propagation net- work. In Advances in neural information processing systems, pp. 396-404, 1990.
John M Lee. Smooth manifolds. In Introduction to Smooth Manifolds, pp. 1-31. Springer, 2013.
Na Lei, Kehua Su, Li Cui, Shing-Tung Yau, and Xianfeng David Gu. A geometric view of optimal transportation and generative model. Computer Aided Geometric Design, 18:1-21, 2019.
Cheng- Yuan Liou, Wei-Chen Cheng, Jiun- Wei Liou, and Daw-Ran Liou. Autoencoder for words. Neurocomputing, 139:84 96, 2014.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Luis Armando Pérez Rey. Disentanglement with hyperspherical latent spaces using diffusion varia- tional autoencoders. Proceedings of Machine Learning Research, 1:1-4, 2019.
Joseph Rotman. An introduction to algebraic topology. volume 119. Springer Science & Business Media, 2013.
Sam T. Roweis and Lawrence K. Saul. Nonlinear dimensionality reduction by locally linear embed- ding. Science, 290(55000:2333-22222 2000.
Uri Shaham, Alexander Cloninger, and Ronald R Coifman. Provable approximation properties for deep neural networks. Applied and Computational Harmonic Analysis, 44(3):537-557, 2018.
Joshua B. Tenenbaum, Vin de Silva, John C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290 -9-33,,, 2000.
L.J.P. van der Maaten and G.E. Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, 9:2579-2660 2605, 2008
Zhenyue Zhang and Hongyuan Zha. Principal manifolds and nonlinear dimension reduction via local tangent space alignment. SIAM Journal on Scientific Computing, 26(1):313-338 2004.
A APPENDIX
A.1 NOTATION
Objects:
Functions:
Data: æ E D E Rd
Initial Encoder: E : +
Chart Center: o; Dataset: D
chart Encoder: E, 2 Za
Manifold: M C I
chart Decoder: D; 2a - y/i
Latent Representation:
R
chart Predictor: P (Eai 2; x) - p
Chart Representations;
E R
chart Transition: Tíj : 2a -
Chart Space: U₂ : [0, 1] R
Chart Function: Un M
Discretized chart Space: Ua [0, 1]' R
Function on Manifold: ʃ : -
Chart Prediction: p E P(N)
Loss Functions: Lname
Reconstructed Data: R
Regularization: Rname
Residual e E IR
Error Measurement: Ename
Discretization of chart: {b/) Un
Density function: 7) (Vi 2a; x) + [0.
Parameters:
PCA Projection: U, R
Internal Label 4
11

---

Under review as a conference paper at ICLR 2020
A.2 MODEL DETAILS
In this section we detail the architecture of the networks used in the numerical experiments. We denote fully connected layers FC, where y the number of units in the layers, j... as convolution layers with filters of size(i.j) input dimension & and output dimension I, and dim(U) be the dimension of the latent space. Each model was trained using the chart prediction loss function as we have found it to be more stable during training.
Auto-Encoders:
Encoder: I - FC250 - FC250 - FC250 - FCdim(U) - 2
Decoder: 2 FC250 + FC250 - FC250 + FCN +
Variational Auto-Encoders:
Encoder: x - FC250 + FC250 + FC250 + FC2adim(U)) - 2, 2,0
Decoder : 2 E (2(2, - FC2500 + FC250 + FC250 + FCn -
CAE 1 (4 2-dim charts, distance confidence, chart predictor):
Initial Encoder + FC250 FC250 FC255
Chart Encoder 2 + FC250 + FCdim(U.) + 23
(8)
Decoder: 2; E (N(200) - FC250 -> FC250 + FC250 - FCn -
chart Prediction soflmar(|==])
CAE 2 (10 2-dim charts, learned confidence chart predictor)
Initial Encoder - FC250 + FC250 - FC225 +
Chart Encoder FC250 FCdim(U.)
(9)
Decoder E O22,0) + FC250 - FC250 + FC250 + FCn +
chart Prediction - FC250 - FC10 - soʃ tmax. - p
CAE 3 (10 25-dim charts, convolution layers, learned chart predictor)
Initial Encoder + ConUAA,11 + Conv3,3,4,8 ConU2,22,816 -
Chart Encoder: - FC250 + FCdsm(U)) + 2;
(10)
Decoder: 2, E (2) FC250 - FC250 + FC250 FC,, -
chart Prediction + FC230 + FC10 + softmar + p
A.3 CHART TRANSITION FUNCTIONS
key feature of the chart-based parameterization of manifolds in differential geometry is the con- struction of chart transition functions. As show in figure 2 some points on the manifold may be parameterized by multiple charts. Let &a and Φe be two charts with overlapping domains (M, M, * 0), then the chart transition function da can be computed as: o- 6g.. In our model the o are represented as E, neural networks, but directly computing itself from 6-1 is not simple since ReLU-nets are non-invertable. It would be possible to add additional modules and to train model predict the transition function, but this adds up to (2) new networks to train, many of which may be unnecessary (since we only need chart transition function for overlapping charts). However,
exploit the structure the encoder module and re-encode the signal generated by the first decoder, using the second encoder define a chart transition. Then Each chart transition function can be modeled by the composition:
Φaz Ua nUg + U3 n Ua.
Eg (((Da(aa))
(11)
Note that if E Ma U Mg, then to estimate the chart transition between U. and Up need: I (x( pe(x) 2 (E(x))) 3 (E(x)(E(r)) Each of these conditions
12

---

Under review as a conference paper at ICLR 2020
naturally enforeed by both of loss functions equation equation discussed in the precious section. Therefore the chart transition function this network can computed without explicitly parameterizing them adding terms to the loss function. One could explicitly characterize the the chart transition by re-encoding the decoded signals in a second pass thought the network and computing regularizer:
Reyole (z) I D3 E D o E,, E(x) + 2| D o E,, E D3 Eg
E(a)ll (12)
which measures the exactly error in the transition and reconstruction. However this type of eyclic condition is computationally expensive to implement, and we have found it unnecessary our empiric studies.
A.4 PCA CHART ORIENTATION
We further extend the idea of pre-training also orient the rest of the chart around the center Ca- To do so, we take a small sample of points (C(,,) around the center and use principle component analysis (PCA) to define d-dimensional embedding of the local neighborhood. Let the coordinates of this neighborhood embedding be: (x) == C. W + b, for x E N(ca) where W., is the
optimal orthogonal projection from Ua to I and ba shifts &a (ca) to [.5] and C is chosen local scaling constant. Then we can use this coordinate system to initialize the orientation of the local charts by adding an additional regularization the term the equation
N
Recors
Σ
Σ
(13)
a=1 ZEN(ca)
A.5 CONVOLUTION
has been widely argued that invariant and equivalent properties of convolutions layers promote manifold structured representations. For example, (Shaham et al. 2018) conjectures: 'that in representation obtained as an output of convolutional and pooling layers, the data concentrates near collection of low-dimenn di-edmimniinnl manifolds embedded in a high-dimenssionl space.' In other words, applying dimension reduction operations which has localized invariance (such as convolution and pooling) maps data relatively simple manifolds by contracting the representation space. This suggests that adding convolution and pooling layers to the beginning of the encoder networks will result in representations which easier for our model to estimate since the underlying geometry will be simpler.
A.6 NETWORK QUALITY MEASUREMENTS
We write D as a general notation for the decoder in the model.
Reconstruction Error
Measures fidelity of the output y: Eyecon
Dient ExEDrcu
||x 11.
laithfulness Error Measures how close data decoded from samples drawn the latent space to samples from the original training data. We uniformly selecting M points { in the latent
MM
space and define Esmple M DN min || 1?= Often, people hope that through sampling the latent space and decoding, one can get new data in the original space that novel or original. However, if the training set is sufficiently dense on the data manifold, newly generated data far from anything observed during training will not be realistic, Since we are concerned with fitting a model to the data, properly trained model should always stay close the the underlying manifold. To select the latent variables used in this experiment, we uniformly draw M = 100 samples from the latent space used in the single chart auto-encoder, CAE and VAE.
Coverage Measures how well the latent space and decoders capture the entire data set. We M uniformly draw M samples { from the latent space. Let M be the number of the set {z" | x² arg miggeee Derein || D22))l2 for some i}. We define Egowerage = M surement provides quantitative way describe the well known "mode collapse" problem of GAN
-T This mea-
13

---

Under review as a conference paper at ICLR 2020
Arjovsky al. 2017) wherein some the model captures part of the data well, but ignores large sec- tions (or entire classes) of the data. A coverage score close to one indicates that the samples are well distributed on the manifold, while scores close to zero indicate that the model may be experiencing mode collapse.
A.7 CHART TRANSITIONS
In this experiment, we train a model with four 1-dimensional charts to a circle in order to visualize the transition between charts. In figure the first row shows the output of each chart using the latent variable 2 sampled on (0, 1). The top right shows the chart which has the largest p value. In the second row, we visualize the transition zones. Here, the solid colored lines are decoded samples taken from the U; space. The '+'s 's represent training data, and their color indicates which chart had maximum p value. The ground truth manifold is represented by the dashed lined. The last row show the partition of unity function, unwrapped from the circle to line. From this experiment we can see that charts have very close values in these transition zones and the partition of unity functions are compactly supported.
Chart
Chart
Chart
Chart 4
Predicted Points
100
100
100
100
100
0
-100
-100
-100
-100
-100
0
100
-100
100
-100
0
100
-100
100
-100
100
Transition Zone
Transition Zone
Transition Zone
Transition Zone
92
91
90
89
52
88
440
-84
-82
-80
40
42
44
46
92
94
98
-58
-54
52
-50 -48 -48
Partition of Unity
Chart2
0.5
Charts
Chart4
2/2-"
Figure 8: Top row: Embedding of Charts and Maximum of Patch Prediction. Second row: chart transitions. Training data is marked with "+" and samples taken from the charts are denoted by the solid colored line. The black dash line shows the ground truth. Bottom: Partition of Unity functions
A.8 AUTOMATIC CHART REMOVAL
In this experiment, train model with four 2-dimensional charts for data sampled on sphere in order to visualize the effect of the regularization scheme when using a neural network as the chart prediction module. Figure shows the patch prediction function the training data the end of the pre-training and at the completion of training, respectively. From this figure we see that even though all charts cover the sphere at the beginning. the regularization is able to automatically remove some charts after training.
14

---

Under review as a conference paper at ICLR 2020
Initial Prediction
Trained
Chart!
Chariz Charib
Figure 9: Left: Initial Predictions.
Right: Final regions
A.9 MEASURING GEODESICS
In this experiment, we demonstrate simple example of recovering geometric information from trained model by computing the length of some geodesic curves on a sphere. Let p and q be points on the manifold with latent representations 2p and zq. Then the line (+ 0&2p + (1 a)z in the latent space will correspond to a path on C M. To measure the length of this path, we can sample points along Y/z (t), decode them and then measure the euclidean distance between the decoded points. Figure 10 shows an example of such a test using different numbers of sampling points for five difference curves on the sphere. From this experiment we observe convergence of geometric
these measurements more points intuition. We remark that this is a very preliminary result to show a potential understanding geometric structure of data manifold using multi-chart latent space. We will explore in the direction in our future work.
sampled along the geodesic path, validating
0.45
Convergnce geodesics
0.35
0.7
0.25
0.16
0.1
50
100
Number Points
Figure 10: Left: Geodesic approximation error v.s. number of points sampled in the latent space.
Right: Geodesic curves generated from the decoder network.
A.10 DETAILED BENCHMARK COMPARISONS
Figure I shows an experiment for data sampled on double torus using VAE with different choice of parameters. The latent space dimension is chosed as 2 which is compatible with the intrinsic diemisno the object. This experiment shows that increasing the number of parameters alone (without increasing the latent dimension) does not allow one simultaneously produce good reconstruction and generation. latent space which has too small of a dimension will not able to cover manifold, and one which is too large will generate points far from the data manifold. Thus the structure of latent space is more important than the number of parameters. This is one of the main objectives of this paper.
VAE
15

---

Under review as a conference paper at ICLR 2020
0.003
Pesoammtiion brrer 03000
92231
0.9211
RAcoralAE CU0OSS
Figure 11: Five overparametized VAE with dimensional latent space for data sampled double torus. Blue:training data, Red:samples from latent space.
Model (Latent Space)
of
Intrinsic /Amb.
Recon. Error
Data
Unfaithfulness
Coverage
Param.
128503
Sphere
2
1.32e-01
8. 8.409e-01
.85
AEI ( = [0. 1
152050
Genus
2
50
5.018e-01
3.286e00
.15
519784
MNIST
?
784
3.111c00
3.486e00
.18
640024
SVHN
?
1024
4.235c00
8.123e00
.12
140003
Sphere
2
3
3.521c-02
5.789c-01
.87
AE II u = [0, 2
163550
Genus
2
50
3.819e-02
5.233e-01
.68
531284
MNIST
?
784
2.459e-01
3,975e00
.23
651524
SVHN
?
1024
8.523e-01
2.1756e00
.14
129005
2
3
3.38e-02
7.489e-01
.88
Sphere
VAEI u = = 7)2
152552
2
50
2,459c-01
2.575e-0
.67
Genus
520286
?
784
8.459c-01
2.045c-01
.55
MNIST
57799
?
1024
6.137000
8.100e00
.43
146278
Sphere
2
1,33e-02
9.451e-01
.92
VAE II u = NVO, 2)25
169825
Genus
2
50
4.273e-02
4.002e-01
.66
537559
MNIST
?
784
2.451e-01
6.377e-01
822
657799
SVHN
?
1024
4.012e-00
4.012e-00
.75
333266
Sphere
2
3
8.025e-03
2.921e-02
1
4-chart Model U1 + 1].
392016
Genus
2
50
1.187e-02
8.234c-02
.86
1309516
MNIST
?
784
7.100e-01
8.100e00
.57
1707450
SVHN
?
1024
9.0234e-00
8.904e00
.63
751790
Sphere
2
3
9.878c-03
6.785e-02
1
10-chart Model 4 10 00, 1
881040
Genus
2
50
4.245e-02
1.412e-01
.82
2899540
MNIST
?
784
1.120e-01
8.231e-01
.91
3795750
SVHN
?
1024
8.877e-01
6.311e-01
.75
10-chart Conv. Model U 10
3498564
MNIST
784
8.556e-02
3.209e-02
.87
00 2
4098564
SVHN
? 1024
2.177c-01
8.271c-01
.88
16


Reviews:
[{"review_id": "SyefiJ_uYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary of the Paper\n\nThis paper introduces a new architecture for autoencoders based on the\nconcept of *charts* from (differential) topology. Instead of learning a\nsingle latent representation, the paper proposes learning charts, which\nserve as local latent representations. Experiments demonstrate that the\nlocal representations perform favourably in terms of approximating  the\nunderlying manifold.\n\n## Summary of the Review\n\nThis is an interesting paper with an original idea. I appreciate the use\nof concepts from differential topology in deep learning and agree with\nthe paper that such a perspective is required to increase our\nunderstanding of complicated manifold data sets. However, I find the\nfollowing issues with the paper in its current form, which prevent me\nfrom endorsing it for acceptance:\n\n1. I have doubts about the technical correctness of the proposed\n   architecture; specifically, the relevance of the *initial* latent\n   representation, which employs a Euclidean space, is not analysed.\n\n2. The role of the number of charts, which needs to be specified\n   before-hand, is not analysed in an ablation study.\n\n3. The experiments do not showcase the *conceptual* improvements of the\n   proposed technique.\n\nI shall briefly comment on each of these points before discussing other\nimprovements.\n\nI want to point out that I really like the ideas presented in this\npaper and I think it has the potential to make a strong contribution but\nthe issues in their current form require substantial revisions and\nadditions.\n\n# Concern 1: Technical correctness\n\nThe paper claims at multiple places that the geometry of Euclidean space\nis 'trivial' or 'too simplistic' to meaningfully reflect the structure\nof the data. This claim is double-edged, though: first, there are\nmany methods that use autoencoders based on these spaces that exhibit\nsufficient reconstruction capabilities. Second, the proposed\narchitecture itself uses a Euclidean latent representation as its\ninitial encoder. The paper states that 'Ideally, this step preserves the\ntopology of the data [...]', but this is never analysed.\n\nI fully agree with the idea that charts are a suitable way to describe\ncomplicated manifolds, but the paper needs more precision when terms\nsuch as 'topology' and 'geometry' are being used. Likewise, I disagree\nwith referring to Euclidean space as 'trivial'. Again, other methods\ndemonstrate that the space captures high-level phenomena sufficiently\nwell for reconstruction purposes. At the very least, the paper should\nbe more precise here.\n\nMoreover, I would recommend experiments in which the dimensionality of\nthe initial encoder is discussed.\n\n# Concern 2: Number of charts\n\nSelecting the number of charts appears to me as a critical component of\nthe proposed method. While the appendix contains one experiment for\nMNIST with different numbers of charts, this concept needs to be fleshed\nout more. How do we know that we have a sufficient number of charts?\nSince in differential topology, the choice of chart should not matter,\nhow does it behave in these cases? Is there a way to detect that the\nnumber of charts must be increased?\n\nI could envision something like a simple 'step size' control procedure:\nif a quality measure indicates that there need to be more charts, double\nthe number of charts and re-run the training; if the number of charts\nis too big, halve it and re-run the training.\n\nI get the idea that increasing the number of charts will probably\ndecrease the reconstruction error, but this comes at the obvious expense\nof even more parameters. I thus recommend another set of experiments\nthat shows the influence of the number of charts, maybe even on the\nsynthetic data sets used in the paper.\n\n# Concern 3: Conceptual improvements\n\nWhile I enjoyed the didactic approach of the paper, which first\nintroduces simple test data sets to illustrate the concepts, my\nmain question is about the conceptual improvements that the charts\nprovide in the end.\n\nI see that the reconstruction error for MNIST goes down---but there are\nalso significantly more (!) parameters than in the comparison\narchitectures. The ideas of the sampling or interpolation experiments\ngo in the right direction, but in their present version, they are not\nentirely convincing. In fact, they even raised more questions for me: \n\n- Figure 6 depicts individual charts but their *covering* of the space\n  is highly non-uniform. The letter '0' is covered more often than the\n  letter '1', for example. How can this be compatible with the claim\n  that the novel architecture learns a suitable set of charts? I could\n  understand some overlaps, but there seems to be a clear difference\n  between the charts generated in the synthetic examples---which do\n  appear to be cover everything in a uniform manner---and the charts for\n  MNIST. This needs to be elucidated some more, in particular since the\n  paper writes that the charts 'cover [...] in a balanced and regular\n  way'.\n\n- The digit morphing example is not not entirely convincing to me. Is\n  this not something that I can do equally well with a VAE or generative\n  models in general? I am *not* disputing the claims of the paper here,\n  I am merely stating that *if* the new method is beneficial for this\n  sort of application, a more in-depth experiment is required.\n\nThus, while I would like to give the paper the benefit of the doubt, it\ndoes not show just *why* it is relevant to have a chart-based embedding.\nSome suggestions for a set of experiments:\n\n- Do charts help in separating the input space? I would hypothesise\n  that this is the case---it thus might be worthwhile to study\n  low-dimensional embeddings obtained based on each chart and 'stitch'\n  them together.\n\n- Do charts tell us something about the properties of a manifold? For\n  example, are certain charts 'easier' to embed than others? This could\n  be used to indicate different dimensions in a data set.\n\n## Experimental setup\n\nI have one major point of critique here, namely the way results are\npresented without any measures of tendency. Instead of showing a bar\nplot in Figure 7, I would suggest showing a Table with standard\ndeviations along multiple repetitions of the experiment. It is not clear\nfrom looking at this to what extent this results can be replicated.\n\nMoreover, a discussion of the number of parameters is required. To some\nextent, I find it not surprising that a better reconstruction error is\nachieved if more parameters are present.\n\nThis makes some of the claims in the paper hard to assess.\n\n## Technical clarity\n\nThe papers is generally written well and has a good expository style.\nHere are some cases where I find that clarity can be improved:\n\n- To add to what I wrote above: if charts are Euclidean as well, the\n  paper should elucidate why Euclidean charts do *not* suffer from being\n  too simplistic.\n\n- The discussion of homeomorphisms in the introduction is slightly\n  misleading; none of the functions learned later on is a homeomorphism\n  because of the latent space dimensions.\n\n- Homeomorphic mappings of manifolds into a Euclidean space are not\n  necessarily desirable---this is why the definition of a manifold uses\n  the concept of neighbourhoods. I think this should be rephrased in\n  a positive manner, as in: manifolds are complex, so we cannot expect\n  a *single* map to suffice...\n\n- The leading example of a torus embedding needs more details. Why is\n  the structure destroyed?\n\n- The introduction of 'topological features' on p. 2 is slightly abrupt.\n  It would be sufficient to explain by means of the figure that the\n  mapping obviously does not respect all properties.\n\n- p.2: paths become invariant to _what_ exactly?\n\n- p.2: what is the 'topological class'?\n\n- p.2: would LLE not be a good precursor to the method proposed in this\n  paper?\n\n- p.2: is this paper to be seen as an implementation of Chen et al.  (2019)?\n  This should be made more clear.\n\n- p.3: the concept of intrinsic dimension slightly varies in literature.\n  I would propose mentioning the homeomorphism of every chart to some\n  $d$-dimensional space, and state that if this exists, one calls the\n  manifold $d$-dimensional.\n\n- p.3: the circle example could be explained in more detail for readers\n  unfamiliar with the concepts.\n\n- p.4: the chart prediction module requires a brief explanation at the\n  point when it is first introduced (1 sentence is sufficient). The\n  method plus architecture is presented but the details come very late;\n  I would prefer some intuition here\n\n- p.4: $N$ needs to be defined earlier\n\n- p.4: how is the dimension of latent spaces chosen? Please also refer\n  to my comments on the experiments above.\n\n- p.5: Section 4.1 again mixes 'topological' and 'geometrical' concepts;\n  suddenly, the concept of curvature crops up---this needs to be\n  explained better!\n\n- p.5: Distances can always be measured in connected subsets of\n  real-valued spaces; whether the set is open or closed does not change\n  the fact that a centre exists. Am I misunderstanding this?\n\n- p.5: I like the 'partition of unity' approach, but to me, this reads\n  like a convex combination of predictions. Am I misreading this? If\n  not, I would suggest to rephrase this.\n\n- p.5/6: the goals of the new method need to be stated more clearly; the\n  paper needs to explain better to what extent *reconstruction error* is\n  affected by charts (it does not seem to be, as I outlined above)---and\n  this again raises the question of which quality measure the new method\n  *can* preserve.\n\n- p.6: the definition of the Lipschitz constant could be more precise;\n  please specify the requirements $f$ has to satisfy\n\n- Eq. 4 needs more details for me: it seems as if the weights appear\n  twice as a kind of 'decay term' (in the second part, I see the sum\n  but the product appears in both terms). This should be stated more\n  clearly.\n\n- p.6: the pre-training needs more details; how crucial is this step?\n\n- p.6: what does the 'orientation' imply? It is not defined except in the\n  appendix.\n\n- p.6: the jump from the illustrative examples to the non-synthetic ones\n  is large; the uniform sampling of the latent space does not scale to\n  higher dimensions, for example. The paper should comment on this if\n  possible.\n\n- In general, I would recommend giving the employed models more\n  'speaking' names. I found it hard to keep track of all of them and had\n  to refer to the appendix constantly.\n\n- For Figure 4, please show the full space, together will all charts\n\n- p.7: please give some ideas (see above) for how to use the covering of\n  the points in practice; I like that the object can be reconstructed\n  with a proper set of charts, but the paper could make the necessity\n  of the technique much more obvious by choosing stronger examples.\n\n- p.7: the object arguably *also* has a complex geometry, not only\n  complex topology. This should be mentioned.\n\n- p.8: the discussion of MNIST is slightly incorrect; as outlined above,\n  many digits appear to be generated by multiple charts, while some,\n  such as `1` do not appear on more than one chart.\n\n- The metrics in Section 5.3 should be introduced earlier, maybe at the\n  expense of some exposition in the introduction or the simpler\n  examples; it is not good style to have to refer to the appendix to\n  understand a core experiment of a paper.\n\n- p.8: I do not understand the term 'wholly pyramid'.\n\n- p.11: the decoder should map to $x_i$, if I am not mistaken\n\n- p.11: I would suggest a more consistent terminology to describe the\n  models. The prediction function is replicated multiple times, for\n  example, so why not introduce a shorthand notation for this?\n\n- p.12: '\\cup' and '\\cap' need to be switched: the *intersection* of\n  domains needs to be empty, not their *union*\n\n- p.13: to what extent are the 'faithfulness' and 'coverage' established\n  metrics? It seems that they are developed for this paper, so I would\n  explain them in the main text and also make clear why they are\n  desirable metrics---else, the metrics could be criticised as being\n  fine-tuned for the proposed method.\n\n  For example, if *coverage* can measure the phenomenon of *mode\n  collapse*, this needs to be demonstrated.\n\n## Minor comments\n\nSome typos:\n\n- low dimensional --> low-dimensional\n- eigen-functions --> eigenfunctions\n- considers manifold point --> considers a manifold point\n- paring subnetwork --> pairing subnetwork\n- paramterized --> parametrized\n- preformed --> performed [occurs multiple times]\n- chats --> charts\n- Lipshitz --> Lipschitz (in Figure 4)\n- evalutation --> evaluation\n- seciton --> section", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HJeesHDodr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Notes: \n\n  -Goal is to learn autoencoders which can capture disconnected manifolds by employing multiple discrete charts.  \n\n  -For example in Figure 1, a Torus is shown, which can't be captured by a single chart (smooth mapping from euclidean space).  \n\n  -This motivating intuition makes sense, although I wonder to what extent a neural network can compensate for this by being relatively unsmooth.  \n\n  -The circle example in the introduction is illuminating and I enjoyed it.  \n\n  -It's somewhat subjective, but I feel that autoencoders are becoming less widely used, so the paper might have more impact if it had targeted models like ALI/BiGAN which do reconstruction but purely with adversarial objectives.  \n\n  -Two techniques are presented for handling how points are assigned to charts (4.1).  I'm a bit unclear on how this interacts with the notion that a single point can be covered by multiple charts.  \n\n  -The paper uses lipschitz regularization on the decoder.  Note that Spectral Normalization (Miyato 2018) could also be used here.  \n\n  -The illustration of the effect of lipschitz regularization in figure 4 is good.  \n\n  -For 5.2, I'd prefer the use of a dataset other than MNIST, since we don't strictly know that the digits require different charts (for example I'm pretty sure there's a smooth mapping between \"1\" and \"7\").  I'd prefer an example where literally different types of objects are combined which couldn't possibly be modeled by a single chart.  \n\nReview: Overall I felt like this paper gives a nice mathematical exposition on the relationship between charts, manifolds, and autoencoders.  I slightly lean for acceptance but am very borderline, especially as the results on \"real data\" are very weak.  ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "HJeMrVc3Kr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nThe authors provide a model that is based on multiple Auto-Encoders, and it is claimed that each Auto-Encoder learns a local chart map of the data manifold. \n\nIn general the paper is ok written and tries to present the idea and the theoretical background in a nice way. However, there are few things that in my opinion should be improved (see comments). More importantly, at the first sight the proposed model seems to be solid, but I think that there are some details, which make the model to not behave as it should in theory.\n\nComments:\n\n1. As regards the related work, I think that some references should be included. For instance, several recent papers which discuss the topological structure of the latent space [1,2,3,etc]. Also, recently the geometry of the latent space is analyzed through Riemannian geometry and points out that the uncertainty of the generator is crucial for capturing correctly the data manifold structure [4]. Moreover, there is some work where multiple generators are used in order to model the data [5].\n\n2. I am not entirely convinced that the proposed model learns the charts of the manifold. Instead, I think it just utilizes several auto-encoders, and each of them specializes in some parts of the data manifold:\n\n- First of all, the chart map is very well defined operator. A point in the intersection of two neighborhoods on the manifold U_a, U_b that overlap, has to be reconstructed \"exactly\" by the two corresponding charts. However, from the modeling steps and the experiments I cannot see why this is the case.\n\n- As regards the technical details. The loss function of Eq. 2 essentially implies that only one chart is specialized for the sample x. However, such that to have chart maps, there should be samples on the intersections of neighborhoods on the manifold that are reconstructed by both charts. I do not see how the proposed model can tackle this issue.\n\n- The loss function of Eq. 3 is even more debatable. The reason is that a mixture of auto-encoders is used to reconstruct the point x. However, this is not the definition of a chart. This is simply a way to use several auto-encoders to reconstruct the data, where the function p_i(x) (acts as soft assignment) chooses which of the auto-encoders should be used for the sample.\n\n- The chart is defined as an invertible map. I can understand that in practice the decoder is considered as the inverse of the chart. However, we cannot guarantee that there are not cases where the decoder creates a surface with intersections or that \"degenerates\" some parts of the surface (instead of a 2-dimensional surface, it generates an 1-dimensional curve). In this case, the chart is not invertible on these parts of the surface. So I am not sure if we can directly consider an auto-encoder based on Neural Network as chart map.\n\n3) I think that the first global encoder E couples all the other encoders. Also, it is stated by the authors that this step should respect the manifold topology, which in general is not the case. So even if this helps for computational efficiency, it does not respect the theory.\n\n4) The pretraining together with the regularization make me to believe that the model first separates the dataset into K clusters, and then learns an approximately linear model for each cluster. I think that this is what the Eq. 2 implies, or a soft assignment (weighted) version if the Eq. 3 is used.\n\n5) In the experiments some of the previously mentioned issues appear:\n\n- In Fig. 5 seems that few of the charts are more \"important\" than the others. However, I am more curious for what happens on the intersection of the neighborhoods on the manifold. For instance, from the figure it seems that some of the U_a on the surface are \"disconnected\". Does this mean that simply some of them (e.g. U_a and U_b) intersect and thats why the disconnected sets (e.g. of U_a) appear? If this is the case, then how the two chart maps behave on the intersection?\n\n- As regards the MNIST, I do not think that it is a good example to support the chart learning. Most probably, there are 10 (disconnected) manifolds, and each of them should be modeled by a particular chart (or many charts per digit-manifold). In this case I think that the p(x) should be exactly 0 and 1, such that to chose one chart per digit. Also, in the current setting of the experiment, essentially all the data are considered to lie on the same data manifold. So what is the behaviour of the charts in the parts of the ambient space where there are no data? \n\n- I think that is very important a well constructed experiment that shows the behaviour of the charts on overlapping domains (Sec A.3). Even an example in 2D ambient space with embedded 1-dimensional (disconnected) manifolds.\n \n- Why in Fig. 7 some bars are missing? Also, from the appendix it seems that the CAE ||| is a very powerful model with 10 latent spaces of 25 dimensions each, and moreover, is the only one that uses convolutions. Since, from the text is not clear if the VAE II uses convolutions, and also, it has only one 25 dimensional latent space. In my opinion this is not a reasonable comparisson.\n\n- Probably comparisons with other models that use multiple generators or even latent spaces that respect the topology of the data manifold could be included.\n\nMinor comments:\n1) In my opinion, from the first paragraph of Sec 4.1. is not clear how the function p(x) is defined.\n\n2) The regularization part is a bit unclear. Strong regularization on the decoders probably means that locally the auto-encoders will behave approximatelly as linear models? Especially, since the initialization is based on local PCAs (pre-training), which can potentially act as an inductive bias. Also, in the beggining of paragraph 3 in Sec 4.2. it is stated that the Lipschitz regulariation is used for the decoders, but next it is introduced for the encoders. This needs clarification.\n\n3) How is defined the term at the end of Eq. 5?\n\n\nIn general, I like the problem that the paper aims to solve. However, I have the feeling that the proposed approach is quite debateable. Instead of chart learning, in my opinion, I think that the model just uses several auto-encoders and each of them is specialized at different subsets of the training data. These subsets are chosen at the pre-training phase, and then the function p(.) acts as an (soft) assignment function. Overall, my main question is what happens on the overlap of two neighborhoods on the data manifold? Also, what happens if the data lie on disconnected components?\n\nReferences:\n[1] Diffusion Variational Autoencoders, Luis A. Perez Rey, et al., 2019.\n[2] Hyperspherical Variational Auto-Encoders, Davidson, Tim R., et al., 2018.\n[3] Hierarchical Representations with\nPoincaré Variational Auto-Encoders, Emile Mathieu, et al., 2019.\n[4] Latent Space Oddity: on the Curvature of Deep Generative Models, Georgios Arvanitidis, et al., 2018.\n[5] Competitive Training of Mixtures of Independent Deep Generative Models, Francesco Locatello, 2019.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to use more varied geometric structures of latent spaces to capture the manifold structure of the data, and provide experiments with synthetic and real data that show some promise in terms of approximating manifolds.
While reviewers appreciate the motivation behind the paper and see that angle as potentially resulting in a strong paper in the future, they have concerns that the method is too complicated and that the experimental results are not fully convincing that the proposed method is useful, with also not enough ablation studies. Authors provided some additional results and clarified explanations in their revisions, but reviewers still believe there is more work required to deliver a submission warranting acceptance in terms of justifying the complicated architecture experimentally.
Therefore, we do not recommend acceptance.
Decision: Reject