Title: EFFICIENT REPRESENTATION OF LOW-DIMENSIONAL MANIFOLDS USING DEEP NETWORKS

Abstract: We consider the ability of deep neural networks to represent data that lies near a low-dimensional manifold in a high-dimensional space. We show that deep networks can efficiently extract the intrinsic, low-dimensional coordinates of such data. Specifically we show that the first two layers of a deep network can exactly embed points lying on a monotonic chain, a special type of piecewise linear manifold, mapping them to a low-dimensional Euclidean space. Remarkably, the network can do this using an almost optimal number of parameters. We also show that this network projects nearby points onto the manifold and then embeds them with little error. Experiments demonstrate that training with stochastic gradient descent can indeed find efficient representations similar to the one presented in this paper.
Let p = p 0 + δ be as in the last section. We define the embedding error of p by E(p) = B (k) A (k) -X (k)T p, where X (k) denotes the orthogonal projection to S k , as in Sec. 3. Noting that, by the construction of our network, B (k) A (k) p 0 = X (k)T p 0 (since p 0 is on S k ) and that X (k)T δ = 0 (due to the orthonormality of X (k) ), we obtain E(p) = B (k) A (k) δ. The magnitude of the error therefore is scaled at most by the maximal singular value of B (k) A (k) , denoted σ k .
To bound σ k we note that B (k) A (k) = BA + ba T for k ≥ 2 (where, as before, we drop superscripts so that B denotes B (k-1) ). Therefore, σ k ≤ σ k-1 +|a T b|, where σ k-1 denotes the largest singular

1. INTRODUCTION:

Figure 1 : We illustrate the embedding of a manifold by a deep network using the famous Swiss Roll example (left). Dots represent color coded input data, with color indicating one of the intrinsic coordinates of each input point. In the center, the data is divided into three parts using hidden units represented by the yellow and cyan planes. Each part is then approximated by a monotonic chain of linear segments. Additional hidden units, also depicted as planes, control the orientation of the next segments in the chain. A second layer of the network then flattens each chain into a 2D Euclidean plane, and assembles these into a common 2D representation (right).

Deep neural networks have achieved state-of-the-art results in a variety of tasks. One possible reason for this remarkable success is that their hierarchical, layered structure may allow them to capture the geometric regularities of commonplace data. We support this hypothesis by exploring ways that networks can handle input data that lie on or near a low-dimenisonal manifold. In many problems, for example face recognition, data lie on or near manifolds that are of much lower dimension than the input space (Turk & Pentland, 1991; Basri & Jacobs, 2003; Lee et al., 2003) , and that represent the intrinsic degrees of variation in the data.

We study the ability of deep networks to represent manifold data. We show that the initial layers of networks can approximate data that lies on high-dimensional manifolds using piecewise linear functions, and economically output their coordinates embedded in a low-dimensional Euclidean space. In fact, each new linear segment approximating the manifold can be represented by a single additional hidden unit, leading to a representation of manifold data that in some cases is nearly optimal in the number of parameters of the system. Subsequent layers of a deep network could build upon these early layers, operating in lower dimensional spaces that more naturally represent the input data. We further show empirical results that suggest that training with stochastic gradient descent can find efficient representations akin to the one suggested in this paper.

We first show how this embedding can be done efficiently for manifolds consisting of monotonic chains of linear segments. We then show how these primitives can be combined to form linear approximations for more complex manifolds. This process is illustrated in Figure 1 . We further show that when the data lies sufficiently close to their linear approximation, the error in the embedding will be small. Our constructions will use a feed-forward network with rectified linear unit (RELU) activation. We consider fully connected layers, although the treatment of complex manifolds that are divided into pieces (e.g., of monotonic chains) will be modular, resulting in many zero weights.

2. PRIOR WORK:

Realistic learning problems, e.g., in vision and speech processing, involve high dimensional data. Such data is often governed by many fewer variables, producing manifold-like sub-structures in a high dimensional ambient space. A large number of dimensionality reduction techniques, such as principle component analysis and multi-dimensional scaling (Duda et al., 2012) , Isomap (Tenenbaum et al., 2000) , and local linear embedding (LLE) (Roweis & Saul, 2000) , have been introduced. An underlying manifold assumption, which states that different classes lie in separate manifolds, has also guided the design of clustering and semi-supervised learning algorithms (Nadler et al., 2005; Belkin & Niyogi, 2003; Weston et al., 2008; Mobahi et al., 2009) .

A number of recent papers examine properties of neural nets in light of this manifold assumption. Brahma et al. (2015) show empirically that the layers of deep networks trained with data that lies on a manifold progressively unfold that data into Euclidean spaces. They do not consider the mechanisms used to perform this unfolding. Rifai et al. (2011) trained a contractive auto-encoder to represent an atlas of manifold charts. Shaham et al. (2015) demonstrate that a 4-layer network can efficiently represent any function on a manifold through a trapezoidal wavelet decomposition. In both, each chart is represented independently, requiring an independent projection for each chart. Likewise, (Chui & Mhaskar, 2016) consider methods by which a neural network can map points on a manifold to a low-dimensional, Euclidean space, although they do not consider the efficiency of this representation in terms of hidden units or weights. We show that for monotonic chains we can reduce the size of the representation to near optimal by exploiting geometric relations between neighboring projection matrices, so an additional chart requires only a single hidden unit.

Another family of networks attempt to learn a "semantic" distance metric for training pairs, often by using a siamese network (Salakhutdinov & Hinton, 2007; Chopra et al., 2005; R. Hadsell & LeCun, 2006; Yi et al., 2014; Huang et al., 2015) . These assume that the input space can be mapped nonlinearly by a network to produce the desired distances in a lower dimensional feature space. Giryes et al. (2016) shows that even a feed-forward neural network with random Gaussian weights embeds the input data in an output space while preserving distances between input items.

Another outstanding question is to what extent deep networks can be more efficient than shallow networks with a single hidden layer. Shallow networks are universal approximators (Cybenko, 1989) . However, recent work demonstrates that deep networks can be exponentially more efficient in representing certain functions (Bianchini & Scarselli, 2014; Telgarsky, 2015; Eldan & Shamir, 2015; Delalleau & Bengio, 2011; Montufar et al., 2014; Cohen et al., 2015) . On the other hand, (Ba & Caruana, 2014) shows empirically that in many practical cases a shallow network can be trained to mimic the behavior of a deep network. Our construction does not produce exponential gains, but does show that the early layers of a network can efficiently reduce the dimensionality of data that feeds into later layers.

3. MONOTONIC CHAINS OF LINEAR SEGMENTS:

We construct networks that perform dimensionality reduction on data that lies on or near a manifold. We focus on feed-forward networks with RELU activation, i.e., max(x, 0). Clearly the output of such networks are continuous, piecewise linear functions of their input. It is therefore natural to ask whether they can embed piecewise-linear manifolds in a low-dimensional Euclidean space both ac-Figure 2 : Left: A continuous chain of linear segments (above) that can be flattened to lie in a single low-dimensional linear subspace (bottom). Right: A monotonic chain. S k denotes the k'th segment in the chain. H k is a hyperplane bounding the half-space that separates S1, ..., S k from S k+1 , ..., SK . curately and efficiently. In this section we construct such efficient networks for a class of manifolds that we call monotonic chains of linear segments, which are defined shortly. These will serve as building blocks for handling more general data that can be decomposed into monotonic chains.

We will consider data lying in a chain of linear segments, denoted C = S 1 ∪ ... ∪ S K . Each segment S k (1 ≤ k ≤ K) in the chain is a portion of some m-dimensional affine subspace of R d , and the segments are connected to form a chain (Figure 2 ). We suppose that every two consecutive segments S k-1 and S k intersect, and that the intersection lies in an (m -1)-dimensional affine subspace. We further assume that these chains can be flattened by isometry so that they may be represented in R m . Note that any curve on C will be mapped to a curve of the same length in R m on the flattened chain.

Each unit in the first hidden layer of a neural network will have a response of zero to input points that lie on a hyperplane, defined by its weights and bias term. This hyperplane bounds a half-space in which the output of the unit is positive; when the output is negative, RELU turns the output to zero. We say that a unit is active over the half-space in which its output is positive. There is a close connection between these hyperplanes and the embedding of a manifold, which we begin to develop with the following definition.

Definition::

We say that a chain of K linear segments is monotonic (see Figure 2 ) when there exist a set of hyperplanes such that the k'th hyperplane separates the first k segments from the rest. Denoting the positive half-spaces associated with these hyperplanes as H 1 , H 2 , ..., H K-1 , then H k is bounded by a hyperplane that contains the intersection of S k and S k+1 , and S k+1 , S k+2 , ..., S K ⊂ H k while S 1 , S 2 , ..., S k ⊂ H C k , where H C k is the complement of H k . We can consider each halfspace to represent a hidden unit that is active (i.e., non-zero) over a subset of the regions. With a monotonic chain, the set of active units grows monotonically, so that, (H k+1 ∩ C) ⊆ (H k ∩ C). We can also define some additional units that are active over all the regions. Below we show that monotonic chains can be embedded efficiently by networks with two layers of weights. These networks have d units in the input layer, a hidden layer with κ = K + m -1 units that encodes the structure of the manifold, and an output layer with m units. Denote the weights in the first layer by a κ × d matrix A and further use a bias vector a 0 ∈ R κ . The second layer of weights is captured by a m × κ matrix B. The total number of weights in these two layers is (d + m + 1)(K + m -1). This network maps a point x ∈ R d to the embedding space R m through u = B[Ax + a 0 ] + where [.] + denotes the RELU operation. For now we do not use a bias or RELU in the second level, but those will be used later when we discuss more complex manifolds.

A simple example of a manifold that can be represented efficiently with a neural network occurs when the data lies in a single m-dimensional affine subspace of R d . Embedding can be done in this case with just one layer, with the matrix A of size m × d containing in its rows a basis parallel to the affine space. One way to extend this example to handle chains is by encoding each linear segment separately. Such encoding will require mK units in addition to units that use RELU to separate each segment from the rest of the segments. A related representation was used, e.g., in (Shaham et al., 2015) . Below we show that monotonic chains can be encoded much more efficiently.

We next show how to construct the network (i.e., set the weights in A, a 0 , and B) to encode monotonic chains. Below we use the notation A (k) to denote the matrix formed by the first k rows of A, a 0 (k) is the vector containing the first k entries of a 0 , and B (k) the matrix including the first k columns of B. Therefore B (k) [A (k) x + a 0 (k) ] + will express the output of the network when only the first k hidden units are used. These will be set to recover the intrinsic coordinates of points in the first k segments in C; RELU ensures that subsequent hidden units do not affect the output for points in these segments.

For the construction we consider the pull-back of the standard basis of R m onto the chain, producing a geodesic basis to the manifold. Note that to produce a local basis for the intrinsic coordinates of points on the manifold, we only need a basis for each linear segment. This basis is expressed by a collection of d × m column-orthogonal matrices X (1) , X (2) , ..., X (K) . Each matrix provides an orthogonal basis for one of the segments.

We will construct the network inductively. Suppose k = 1. We set A (1) = X (1) T , B (1) = I, and set a 0

(1) so that for all x ∈ C all the components of A (1) x + a 0 (1) are non-negative. Clearly, B (1) A (1) = X (1) T is an orthogonal projection matrix and B (1) A (1) X (1) = I. This shows that the network projects the orthonormal basis for the first segment into I, an orthonormal basis in R m . Next we will show that B (k) A (k) X (k) = I for all k. This implies that B (k) A (k) x = X (k) T x, so there is no distortion in the projection. This will show that the network extends this basis throughout the monotonic chain in a consistent way.

Suppose we used m + k -2 units to construct A (k-1) , a 0 (k-1) , and B (k-1) for the first k -1 ≥ 1 segments. (For notational convenience we will next omit the superscript k -1 for these matrices and vectors, so A = A (k-1) , etc.) We will now use those to construct A (k) , a 0 (k) , and B (k) . We do so by adding a node to the first hidden layer. The weights on the incoming edges to this node will be encoded by appending a row vector a T ∈ R d to A and a scalar a 0 to a 0 , and the weights on the outgoing edges will be encoded by appending a column vector b ∈ R m to B. Our aim is to assign values to these vectors and scalar to extend the embedding to S k .

By induction we assume that any:

x ∈ S 1 ∪ ... ∪ S k-1 is embedded with no distortion to R m by ũ = B[Ax + a 0 ] + ,

and that BAX = I. By monotonicity we further assume that S k-1 ∩ S k is m -1 dimensional and there exists a hyperplane H with normal h ∈ R d that contains this intersection with C -(S 1 ∪ ... ∪ S k-1 ) lying completely on the side of H in the direction of h, while S 1 ∪ ... ∪ S k-1 lies on the opposite side of H. We then set a = h and set a 0 so that a T x + a 0 = 0 for any point

x ∈ S k-1 ∩ S k . (This is well defined since h is orthogonal to S k-1 ∩ S k .)

To determine b, we first rotate the bases X (k-1) (referred to as X below) and

X (k) by a com- mon, m × m matrix R, i.e., Y = XR and Y (k) = X (k) R so that Y = [w, y 2 , ..., y m ] and Y (k) = [v, y 2 , ..., y m ]

with y 2 , ..., y m providing an orthogonal basis parallel to S k-1 ∩ S k . (This is equivalent to rotating the coordinate system in the embedded space and then pulling-back to the manifold.) Note that by the induction assumption BAY R T = I. We next aim to set b so that B (k) A (k) X (k) = I. We note that

B (k) A (k) X (k) = B (k) A (k) Y (k) R T = (BA + ba T )Y (k) R T .

We aim to set b so that (BA + ba T )Y (k) R T = I = BAY R T . Consider this equality first for the common columns y 2 , ..., y m of Y and Y (k) . These columns are parallel to S k-1 ∩ S k , so that a T y j = 0 for 2 ≤ j ≤ m, implying equality for any choice of b. Consider next the left-most column of Y and Y (k) , denoted respectively w and v, we get

(BA + ba T )v = BAw. This is satisfied if we set b = 1 a T v BA(w -v).

We have constructed b so that the segments are embedded with consistent orientations. In Appendix A we show that they are also translated properly by a 0 , to create a continuous embedding. Note that by construction a T y + a 0 ≤ 0 for all y ∈ S 1 ∪ ... ∪ S k-1 so RELU ensures that the embedding of the these segments will not be affected by the additional unit.

Finally, we note that the proposed representation of monotonic chains with a neural network is very efficient and uses only a few parameters beyond the degrees of freedom needed to define such chains. In particular, the definition of a chain requires specifying m basis vectors in R d for one linear segment (exploiting orthonormality these require m(d -(m + 1)/2) parameters), with each additional segment specified by a 1D direction for the new segment (a unit vector in R d specified by d -m -1 parameters) and a direction in the previous segment to be replaced (specified by a unit vector in R m , i.e. m -1 parameters). The total number of degrees of freedom of a chain is therefore

N = m(d -(m + 1)/2) + (K -1)(d -2)

. This is the number of parameters required to specify a monotonic chain. Our construction requires N = (K + m + 1)(d + m + 1) parameters. Specifically, note that for any choice of parameters

K, d, m > 0, N ≥ (K + m -1)(d -m -2).

We therefore obtain that

N N ≤ 1 + 2 K + m -1 1 + 2m + 3 d -m -2 . Assuming d, K + m >> 1 we get N N 1 + 2m d -m .

Since we normally expect that the dimension of the input space will be much greater than the dimension of the manifold, this ratio will be close to 1.

4. ERROR ANALYSIS:

We now consider points that do not lie exactly on the monotonic chain, due to noise, or because we are approximating a non-linear manifold with piece-wise linear segments. Let p 0 be a point on the segment S j that is then perturbed by some small noise vector, δ, that is perpendicular to S j , to produce the point p = p 0 + δ. Ideally, the network would represent p using the coordinates of p 0 .

In effect, the network would project all points onto the monotonic chain. If the network embeds p and p 0 with coordinates p and p0 we define the relative error of the embedding as p-p0 δ . We now analyze this relative error. Our analysis assumes that δ is small enough that p and p 0 lie in the same region so that they are both on the same side of all hyperplanes defined by the hidden units.

We note that given sufficient data that lies on the manifold, it is possible to learn local linear projections of the manifold that will embed it with zero relative error. This can be done with traditional manifold learning methods or by neural networks that contain a sufficiently large number of units. Zhang & Zha (2004) provides an error analysis that shows how the error of their approach depends on the noisiness and number of points in the training data, and the magnitude of the difference between the manifold and its linear approximation. Our contribution here is to analyze the error that can occur when a network learns the embedding very efficiently using a small number of units.

In Appendix B we show that in the worst case, the relative error of the embedding can be unbounded. This occurs when the monotonic chain has very high curvature, so that a separating hyperplane has to be nearly parallel to the segment that follows it. In this section we show that for more typical cases, the relative error will be a small constant.

We will consider a class of monotonic chains in which the total curvature between all segments is less than or equal to some angle T , and in each separating hyperplane is not too close to parallel to the next segment. We denote the angle between S k-1 and S k as θ k-1 . (This angle is well defined since S k-1 and S k intersect in an m -1-dimensional affine space.) As before, we will drop the subscript when it is k -1, and just write θ. Specifically, we define θ so that cos θ = v T w (where v and w are defined as in Sec. 3, as vectors perpendicular to S k-1 ∩ S k , and parallel to S k-1 and S k , respectively), defining θ k similarly for any k. We then express our constraint on the curvature as

K-1 k=1 |θ k | ≤ T .

Now let c be a constant such that we can bound a T v ≥ 1/c for any k -1. c is a bound on the cosine of the angle between the normal to a separating hyperplane and a vector in the direction of the next segment. To understand this, recall that a is a unit vector normal to the hyperplane separating S k-1 and S k . By saying this bound holds for all k -1, we mean that we are able to choose the hyperplanes that divide the chain into segments so that the angle between the normal to each hyperplane and the following segment is not too big. We next bound the error in terms of c and δ .

Figure 3 : This plot shows the error in flattening the Swiss Roll. Relative error is constant in every segment, starting from zero for each monotonic chain and increasing with each segment. The absolute error (for display purposes this error is normalized by the maximal distance from the Swiss Roll to its linear approximation) behaves similarly, but vanishes at the end points of each segment where the Swiss Roll and its linear approximation coincide. value of BA. Recall that a = 1 and b = 1

a T v BA(w -v). Note that w -v ≤ θ k-1 . Therefore, |a T b| ≤ cσ k-1 θ k-1 , from which we conclude that σ k ≤ σ k-1 (1 + cθ k-1 ).

Finally, note that B (1) A (1) = X (1)T , implying that σ 1 = 1. We therefore obtain

σ k ≤ k-1 j=1 (1 + cθ j ). Note that k-1 j=1 θ j ≤ T and so k-1 j=1 (1 + cθ j ) ≤ (1 + cT k-1 ) k-1 . Therefore, σ k ≤ 1 + cT k-1 k-1 ≤ e cT . We conclude that E(p 0 + δ) ≤ e cT δ .

Many segments of many monotonic chains can be divided using hyperplanes in which c is not too big, and may be as low as 1. For such manifolds, when a point is perturbed away from the manifold, its coordinates will not be changed by more than the magnitude of the perturbation times a small constant factor. For example, if T = π/4 and c = 1 then e k ≤ e π 4 ≈ 2.19. Note that rather than beginning at the start of the monotonic chain, we could "begin" in the middle, and work our way out. That is, provide an orthonormal basis for the middle segment and add hidden units to represent the chain from the central segment toward either ends of the chain. This can reduce the total curvature from the starting point to either end by up to half. We further emphasize that this bound is not tight.

We conclude this section by showing the error obtained in using our construction in the "Swiss Roll" example. To represent this data we use hidden units and their corresponding hyperplanes to divide the Roll into three monotonic chains (see Section 5 below for further details). We then divide each chain into segments, obtaining a total of 14 segments. Figure 1 shows the points that are input into the network, and the 2D representation that the network outputs. The points are color coded to allow the reader to identify corresponding points. In Figure 3 we further plot the absolute and relative error in embedding every point of the Swiss Roll due to the linear approximation used by the network. One can see that the Swiss Roll is unrolled almost perfectly. In fact, despite the relatively large angular extent of each monotonic chain (the three chains range between 126 to 166.5 degrees each in total curvature), the relative error does not exceed 2.5. (In fact, our bound for this case is very loose, amounting to 18.3 for 166.5 • .) The mean relative error is 0.98, indicating that the magnitude of the error is approximately the same as the distance of points to the approximating monotonic chains.

5. COMBINATIONS OF MONOTONIC CHAINS:

To handle non-monotonic chains and more general piecewise linear manifolds that can be flattened we show that we can use a network to divide the manifold into monotonic chains, embed each of these separately, and then stitch these embeddings together. Suppose we wish to flatten a nonmonotonic chain that can be divided into L monotonic chains, M 1 , M 2 , ...M L . Let A l , a 0l and B l denote the matrices and bias used to represent the hidden units that flatten M l , which has K l segments. We suppose that a set of J l hyperplanes (that is, a convex polytope) can be found that separate M l from the other chains. Let N l denote a matrix in which the rows represent the normals to these hyperplanes, oriented to point away from M l . We can concatenate these vertically, letting A l = [A l ; N l ]. We next let Υ = -n1 m×J l where 1 m×J l denotes an m × J l matrix containing all ones and n is a very large constant. Note that B l has m rows. So we can define B l = [B l , Υ], where the matrices are concatenated horizontally.

We now note that if u = B l [A l x + a 0l ] + then when x lies on M l , u will contain the coordinates of x embedded in R m , as before. When x lies on a different monotonic chain, u will be a vector with very small negative numbers. Applying RELU will therefore eliminate these numbers.

A l and B l therefore represent a module consisting of a two layer network that embeds one monotonic chain in R m while producing zero for other chains. We can then stitch these values together. First, we must rotate and translate each embedded chain so that each chain picks up where the previous one left off. Let R l denote the rotation of each chain, and let b 0l denote its appropriate translation. Then, for each chain, the appropriate coordinates are produced by

[R l B l [A l x + a 0l ] + + b 0l ] + .

We can now concatenate these for all chains to produce the final network. We let A, a 0 and b 0 be the vertical concatenation of all A l and a 0l and b 0l respectively, and let B be the block-diagonal concatenation of all R l B l . The application of [B[Ax + a 0 ] + + b 0 ] + to x ∈ M l will produce a vector with mL entries in which the m(l -1) + 1, ..., ml entries give the embedded coordinates of x and the rest of the entries are zero. We can now construct a third layer of the network to then stitch these monotonic chains together. Let C denote a matrix of size m × mL obtained by concatenating horizontally L identity matrices of size m × m. Then the output of the network is:

u = C[B[Ax + a 0 ] + + b 0 ] + .

Note, for example, that the first element of u is the sum of the first coordinates produced by each module in the first two layers. Each of these modules produces the appropriate coordinates for points in one monotonic chain, while producing 0 for points in all other monotonic chains.

We note that this summation may result in wrong values if there is overlap between the regions (which will generally be of zero measure). This can be rectified by replacing the summation due to C by max pooling, which allows overlap of any size. Together, all three layers will require

L l=1 J l + m + K l -1 + (L + 1)m units. If the network is fully connected, this requires L l=1 J l + m + K l -1 (d + Lm) + Lm 2 weights.

Note that the size of this network depends on how many regions are required (L) and how many hyperplanes each region needs to separate it from the rest of the manifold (L l ). In the worst case, this can be quite large. Consider, for example, a 1D manifold that is a polyline that passes through every point with integer coordinates in R d . To separate any portion of this polyline from the rest will require regions that are not unbounded, and so L l = O(d) for all l. We expect that many manifolds can be divided appropriately using many fewer hyperplanes. We have shown this for the example of a Swiss rolls (Figure 1 ).

6. EXPERIMENTS:

Up to this point we have theoretically analyzed the representational capacity of a deep network. Our primary result is to show that data lying on a monotonic chain can be efficiently flattened by a network with two hidden layers, using m+k-1 hidden units in the first layer, and m units in the second layer. An important question is whether real networks trained with stochastic gradient descent can uncover such efficient representations. In this section we address that question experimentally.

We do not expect that a trained network will always produce the constructions developed in this paper. First,we note that our constructions provide an upper bound; more efficient representations possible. So we predict that m + k -1 or fewer hidden units are needed. Second, a trained network may settle in a local minimum, and not produce an efficient embedding, even though one might be possible. To determine whether a particular architecture can produce a good embedding, we train networks with multiple random starting points, and select the solutions that produce very low error. To determine the number of hidden units needed to create effective embeddings, we generate data on monotonic chains in which we vary the dimension of the manifold, m, and the number of segments, k. An example in which m = 2 and k = 7 is shown in Figure 5 . Note that there is some skew in the chain, so that none of the dimensions can be trivially embedded by a single linear projection. We sample 40,000 points on the manifold. We then train a regressor, with a varying number of hidden units, using the squared difference between the ground truth distance between pairs of embedded points and the distance computed by the network as a loss function. This simulates non-linear metric learning. For each condition, we repeat training 15 times, and report the minimum error in the objective (see Figure 4 ). We can see that for each curve the error has dropped to an asymptote near zero when h = m + k -1, just as our theory predicts.

In Figure 5 we show a typical example produced for a 2D manifold with seven segments, shown in a 3D space. Portions of hyperplanes correspond to six hidden units. This solution resembles our constructions in several ways. One hyperplane is active over the entire chain, while the other hyperplanes intersect the manifold at the intersection of consecutive segments. The solution differs from our construction in that some hyperplanes are used to handle two segments of the manifold; it is even more efficient than our construction. And two hyperplanes, at the top, intersect the manifold in the same location. These hidden units have weights with opposite signs, producing positive outputs for different segments. For reasons of space and simplicity, we do not discuss these constructions theoretically, but it is straightforward to show that they can also produce efficient embeddings. We perform a final experiment to get a sense of whether such embeddings can occur with more realistic data. We generate images of a face with azimuth ranging from 0 to 50 degrees, and with elevation ranging from 0 to 8 degrees. As a loss function, we use an L2 norm between the m output units and the true azimuth and elevation. Because the images have many pixels, and the amount of training data is limited, a fully connected network would overfit the data if we use each pixel as an input dimension. Consequently, we perform PCA before training to reduce the faces to a 3D space, which also allows us to visualize the input and resulting network (see Figure 6 ). We can see that the data forms an approximately 2D manifold, but that it is much messier than with our previous, synthetic data. The resulting embedding captures the azimuth and elevation reasonably well, but with some noise (eg., it does not form a perfect grid). We can also see that the hyperplanes associated with the first hidden layer of the network also resemble our construction, with individual units periodically intersecting the manifold as it curves. 

7. DISCUSSION:

We show that deep networks can represent data that lies on a low-dimensional manifold with great efficiency. In particular, when using a monotonic chain to approximate some component of the data, the addition of only a single neural unit can produce a new linear segment to approximate a region of the data. This suggests that deep networks may be very effective devices for such dimensionality reduction. It also may suggest new architectures for deep networks that encourage this type of dimensionality reduction.

We also feel that our work makes a larger point about the nature of deep networks. It has been shown by Montufar et al. (2014) that a deep network can divide the input space into a large number of regions in which the network computes piecewise linear functions. Indeed, the number of regions can be exponential in the number of parameters of the network. While this suggests a source of great power, it also suggests that there are very strong constraints on the set of regions that can be constructed, and the set of functions that can be computed. Our work shows one way in which a single hidden unit can control the variation in the linear function that a network computes in two neighboring regions; it can shape this function to follow a manifold that contains the data.

B WORST-CASE ERROR:

In this section we show that the error obtained while embedding noisy points using our construction can in principle be unbounded. As we show below, this happens when we are forced to choose hyperplanes that are almost parallel to the segments they represent. In contrast, Section 4.1 of our paper shows that we can bound the error in many reasonable scenarios.

To show that the error can be unbounded, we consider a simple case in which the piecewise linear manifold consists of three connected 1D line segments, S 1 , S 2 and S 3 , with 2D vertices respectively of (0, 0) and (N, 0), (N, 0) and (N, ), and (N, ) and (0, ). N is very large, and is very small (see Figure 7 ). Since three segments compose a 1D manifold, three hidden units defining three hyperplanes, H 1 , H 2 and H 3 (lines) will be needed to represent the manifold. In addition, a single output unit will sum the results of these units to produce the geodesic distance from the origin to any point on the three segments.

Figure 7 : In black, we show a 1D monotonic chain with three segments. In red, we show three hidden units that flatten this chain into a line. Note that each hidden unit corresponds to a hyperplane (in this case, a line) that separates the segments into two connected components. The third hyperplane must be almost parallel to the third segment. This leads to large errors for noisy points near S 3.

Using our construction in Section 3 of the paper we get the embedding

f (p) = B[Ap + a 0 ] + with B = 1, 1 q 2 , - 1 r 1 2 + q 1 q 2 , A = 1 0 q 1 q 2 r 1 r 2 , a 0 = 0 q 3 r 3

.

Note that the first row of A uses the standard orthogonal projection (x, y) → x; the two other rows of A and a 0 separate the three segments with (1) q 1 , q 2 > 0 and q 1 /q 2 ≤ /N and q 3 = -q 1 N set so that the separator H 2 goes through (N, 0), and (2) r 1 < 0, r 2 > 0 and r 1 /r 2 ≥ -/N , and r 3 = -r 1 N -r 2 set so that the separator H 3 goes through (N, ). It can be easily verified that in this setup points on the first segment (x, 0), 0 ≤ x ≤ N are mapped to x, points (N, y), 0 ≤ y ≤ on the second segment are mapped to N + y, and points (x, ), 0 ≤ x ≤ N on the third segment are mapped to N + + (N -x).

Ideally, we would want p to be embedded to the same point as k) δ. It can be readily verified that, under these conditions, when p 0 ∈ S 1 then E(p) = 0; when p 0 ∈ S 2 then E(p) = (1 + q 1 /q 2 )δ, and when p 0 ∈ S 3 then E(p) = (1 -(r 2 /r 1 )(2 + q 2 /q 1 ))δ. Therefore, there is no error in embedding p for p 0 ∈ S 1 . The error in embedding p with p 0 ∈ S 2 is small and bounded (since q 1 /q 2 ≤ /N , assuming is small and N is large), while the error in embedding p when p 0 ∈ S 3 can be huge since -r 2 /r 1 ≥ N/ . In the next section we show that this can only happen when there is a large angle between a segment and the normal to the previous separating hyperplane.

p 0 . Let E(p) = f (p) -f (p 0 ). Clearly E(p) = B (k) A (

C CLASSIFICATION:

In experiments in the body of this paper we have demonstrated that the theoretical constructions that we analyze can arise when networks are trained to solve regression problems that map points on the manifold to their low-dimensional embeddings. An interesting question is whether similar embeddings may be learned by a network that is trained to classify points that lie on a low-dimensional manifold when it is more efficient to represent the boundaries of these classes in the embedded space than it is in the ambient space. In this Appendix, we describe some very preliminary experiments that address this question.

First we note that the embeddings that arise in solving classification problems may be much less constrained and therefore more complex than those that arise in regression problems. The regression loss function directs the network to learn the known, ground truth coordinates of the embedded manifold. Only an isometric unfolding of the manifold will satisfy this condition. While this isometric embedding will facilitate classification as well, there may be many non-isometric unfoldings that will be equally useful in classification.

As a simple example of this, suppose a monotonic chain contains two classes that are linearly separable, once the chain is isometrically embedded in a low-dimensional space. If instead of an isometric embedding, we allow a related embedding in which each segment of the chain undergoes a different linear transformation that stretches it in the direction of the linear separator, or orthogonal to the separator, the classes will still be linearly separable in the transformed, non-isometric embedding.

As another example, no mapping of the manifold to a low-dimensional space will allow for correct classification if it maps two points from different classes to the same point in the low-dimensional space. However, classification may not be affected if two points from the same class are mapped to the same point. So when points from only one class appear near the boundary between two segments, a network may learn a mapping in which the points from two segments overlap in the low-dimensional space.

It is an open and rather complex problem to determine which mappings of the input to low-dimension may be suitable for classification of a particular set of labeled points. However, we stress that the main point of our paper is to show that when isometric embeddings can be used to solve a problem, a deep network can efficiently represent such embeddings. It is certainly possible that the network can also efficiently find alternate embeddings that are equally useful.

Bearing this in mind, we have designed some simple classification tasks and examined the embeddings that they give rise to in a neural network. We stress that these experiments are quite preliminary, and should be taken as intriguing examples that can help motivate future work.

In our experiments we created monotonic chains with seven segments, similar to those used in our earlier experiments. We generate 20,000 points that lie on each chain. To label these points with classes, we unfolded the chain and intersected it with several lines, varying the number. These lines form an arrangement on the 2D unfolded manifold; we labeled each region of the arrangement, which is a convex polygon, as a separate class. We did this randomly, selecting arrangements in which classes tended to span multiple segments.

We then trained a network to perform classification. After the input layer, the next layer contained between five and eight hidden units. This was followed by a layer containing two hidden units. This was followed by another layer with 10-30 units, and an output layer with a unit for each class.

Relu was used between layers, with softmax for the loss function. The layer containing two units essentially represents a two-dimensional embedding of the input. The previous layer could be used to represent the constructions developed in this paper, while the subsequent layer can be used to classify the data in the low-dimensional space. This architecture allows us to easily extract the embedding that the network has learned.

Figure 8 shows a typical example of the results. On the left we plot the input points, color coded to indicate their class. On the right, we plot each point at its embedded location, color coded to indicate to which segment it belongs. The embedding preserves the order and continuity of the segments. In several cases each segment has been approximately transformed by a different linear transformation.

In the case of the red and green colored segments on the right, there is some overlap. Looking at the left-hand figure we can see that in this case, points near the boundary between the two segments belong to the same class. So this folding over of the segments in the embedding does not interfere with the network's ability to correctly classify the points.

In general, this embedding meets our expectations, showing that the monotonic chain can be very efficiently mapped to a low-dimensional space using very few units, in a way that enables accurate classification. It would be interesting in future work to determine the class of mappings that can be instantiated efficiently by a network, and to understand how these relate to different classification problems. It would also be interesting to design classification problems that can only be solved using isometric embeddings, and to determine whether these embeddings can be found by neural networks.

Figure 8 : We train a network on a classification problem in which the points lie on a low-dimensional manifold.

We show the points on the left, color coded to indicate their class. We then extract the embedding learned by the network. Here we show the input mapped to this embedding, with points colored to indicate which of the seven segments of the monotonic chain they lie on.

D DEEPER NETWORKS:

We also note that the previously developed constructions can be applied recursively, producing a deeper network that progressively approximates data using linear subspaces of decreasing dimension. That is, we may first divide the data into a set of segments that each lie in a low dimensional subspace whose dimension is higher than the intrinsic dimension of the data. Then we may subdivide each segment into a set of subsegments of lower dimension, using a similar construction, and deeper layers of the network. These subsegments may represent the original data, or they be further subdivided by additional layers, until we ultimately produce subsegments that represent the data.

We first illustrate this hierarchical approach with a simple example that requires only one extra layer in the hierarchy. Consider a monotonic chain of K, m 2 -dimensional linear segments that collectively lie in a m 1 -dimensional linear subspace, L, of a d-dimensional space, with m 2 < m 1 . We can construct the first hidden layer with m 1 units that are active over the entire monotonic chain, so that their gradient directions form an orthonormal basis for L. The output of this layer will contain the coordinates in L of points on the monotonic chain. These can form the input to two layers that then flatten the chain, as described in Section 3.

In Section 3 we had already shown how to flatten the manifold with two layers that take their input directly from the input space. Here we accomplish the same end with an extra layer. However, this construction, while using more layers, may also use fewer parameters. The construction in Section 3 required d(m 2 + K -1) parameters. Our new construction will require dm 1 + m 1 (m 2 + K -1) parameters. Note that as K increases, the number of parameters used in the first construction increases in proportion to d, while in the second construction the parameters increase only in proportion to m 1 . Consequently, the second construction can be much more economical when K is large and m 1 is small.

In much the same way, we could represent a manifold using a hierarchy of chains. The first layers can map a m 1 -dimensional chain to a linear m 1 -dimensional output space. The next layers can select an m 2 -dimensional chain that lies in this m 1 -dimensional space, and map it to an m 2 -dimensional space. This process can repeat indefinitely, but whether it is economical will depend on the structure of the manifold.

:



Figures and Tables:

Figure 4: This graph shows error in the embedding produced by a trained network. Each curve represents a manifold of different dimension, with a different number of segments. Each curve shows how error in the embedding on validation points changes as the number of hidden units increases. Stars indicate the validation error at the point of each curve in which h = m + k -1. As our theory predicts, the error has reached an asymptote close to zero at these points.

Figure 5: A network trained with m = 2, k = 7, h = 6. Left: Colored dots represent points on the manifold. Their ground truth coordinates are encoded by the size and hue of the dots. Colored rectangles represent the hyperplanes associated with the six hidden units. Right: We show the labels generated for each point, in 2D. Points are colored to indicate their segment. The embedding is near perfect.

Figure 6: We train a regression network to learn the azimuth and elevation of face images. Left: the face images projected to 3D and the hyperplanes learned in the first network layer. Dot size encodes elevation and hue encodes azimuth. Right: We show the images embedded in a 2D space by the trained network.

Peer review (iclr2017):
Summary: In this paper, the authors look at the ability of neural networks to represent low dimensional manifolds efficiently e.g. embed them into a lower dimensional Euclidian space. They define a class of manifolds, monotonic chains (affine spaces that intersect, with hyperplanes separating monotonic intervals of spaces) and give a construction to embed such a chain with a neural network with one hidden layer. They also give a bound on the number of parameters required to do so, and examine what happens when the manifold is noisy. Experiments involve looking at embedding synthetic data from a monotonic chain using a distance preservation loss. This experiment supports the theoretical bound on number of parameters needed to embed the monotonic chain. Another experiment varies the elevation and azimuth of of faces, which are known to lie on a monotonic chain, on a regression loss. Comments: The direction of investigation in the paper (looking at what happens to manifolds in a neural network), is very compelling, and I strongly encourage the authors to continue exploring this direction. However, the current version of the paper could use some more work: The experiments are all with a regression loss and a shallow network, and as part of the reason for interest in this question is the very large, high dimensional datasets we use now, which require a deeper network, it seems important to address this case. It also seems important to confirm that embedding works well when *classification* loss is used, instead of regression The theory sections could do with being more clearly written -- I’m not as familiar with the literature in this area, and while the proof method used is relatively elementary, it was difficult to understand what exactly was being proved -- e.g. formally stating what could be expected of an embedding that “accurately and efficiently” preserves a monotonic chain, etc.