Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
Based on my understanding, autoencoders are used to find a compact representation of input features that carries the essential underlying information.
Is there any relationship between the L2 distances in the original input space and reduced (compact) space? If not, can I train the network such that the compact representation preserves distance after the transformation?
No, they don't. We basically design them so that they cannot preserve distances. An autoencoder is a neural network which learns a "meaningful" representation of the input, preserving its "semantic" features. The quoted words (like so many terms in Deep Learning papers) have no rigorous definition, but let's say that, trained on a set of inputs, the autoencoder should learn some common features of these inputs, which allow to reconstruct an unseen input with small error 1.
The simplest way for the autoencoder to minimize the differences between input and output (reconstructed input) would be to just output the input, i.e., to learn the identity function, which is an isometry, thus it preserves distances. However, we don't want the autoencoder to simply learn the identity map, because otherwise we don't learn "meaningful" representation, or, to say it better, we don't learn to "compress" the input by learning its basic semantic features and "throwing away" the minute details (the noise, in the case of denoising autoencoder).
To prevent the autoencoder from learning the identity transformation, and forcing it to compress the input, we reduce the number of units in the hidden layers of the autoencoder (bottleneck layer or layers). In other words, we force it to learn a form of nonlinear dimensionality reduction: not for nothing, there is a deep connection between linear autoencoders and PCA, a well-known statistical procedure for linear dimensionality reduction.
However, this comes to a cost: by forcing the autoencoder to perform some kind of nonlinear dimensionality reduction, we prevent it from preserving distances. As a matter of fact, you can prove that there exists no isometry, i.e., no distance preserving transformation, between two Euclidean spaces $\mathbb{E}^n$ and $\mathbb{E}^m$ if $m < n$ (this is implicitly proven in this proof of another statement). In other words, a dimension-reducing transformation cannot be an isometry. This is quite intuitive, actually: if the autoencoder must learn to map elements of a high-dimensional vector space $V$, to elements of a lower-dimensional manifold $M$ embedded in $V$, it will have to "sacrifice" some directions in $V$, which means that two vectors differing only along these directions will be mapped to the same element of $M$. Thus, their distance, initially nonzero, is not preserved (it becomes 0).
NOTE: it can be possible to learn a mapping of a finite set of elements of $V$ $S=\{v_1,\dots,v_n\}$, to a finite set of elements $O=\{w_1,\dots,w_n\}\in M$, such that the pairwise distances are conserved. This is what multidimensional scaling attempts to do. However, it's impossible to map all the elements of $V$ to elements of a lower-dimensional space $W$ while preserving distances.
1things gets more complicated when we refer to my favourite flavour of autoencoder, the Variational Autoencoder, but I won't focus on them here.
You can train a network with any loss function you like. Thus, approach 1, you can create a loss function that pushes the network to ensure that the distance between pairs in a mini-batch in the output equals that between pairs in the input. If you do it on a mini-batch basis, and batch-size is say 16 or 32, that seems not unworkable. Or you could sample a few pairs, and calculate the loss on those (same number of pairs each mini-batch, eg sampled randomly).
As far as creating a non-linear network that is guaranteed to preserve distance, an approach 2, I think one approach could be to build the network out of blocks which themselves preserve distances, eg rotations. I'm not sure that this network could be anything other than a linear transformation, and just a rotation at that. Any non-linearity, such as a sigmoid squashing, would deform the distances.
I think approach 1 sounds workable to me, although no guarantee that distances are always preserved, and they won't be very exactly preserved. The second approach sounds intuitively to me that you'd be limited to a single rotation transformation?
Edit: to clarify. I'm answering the question "how can one make an auto-encoder preserve distance?". The implicit answer I'm giving to "Does an auto-encoder preserve distance?" is "Not by default; though you could put in a bunch of leg-work to encourage this to be the case, ie approach 1 above".
Edit 2: @DeltaIV has a good point about dimension reduction. Note that the existence of t-SNE and so on, ie low-dimensional projections of high-dimensional space, shows both the limitations of trying to preserve distance (conflict between global distances and local distances; challenge of preserving distances in reduced dimensions), but also that it is somewhat possible, given certain caveats/compromises.
