6
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I wouldn't expect that to hold for anything - after all, people use autoencoder latent spaces to have more meaningful similarity - for example, if you train a conv autoencoder on images, similar latent vectors correspond to semantically related images, as opposed to images similar in pixel space. $\endgroup$ – Jakub Bartczuk Jun 15 '18 at 21:21
  • 2
    $\begingroup$ When you say "preserve (pairwise) distances", do you mean between all points of the input space, or just between the points of the training set? In other words, suppose I get a new input point $P$ (test point) which was not used at training time. Do you expect the autoencoder to learn a representation $Z$ such that the distance of $Z$ from any point in the reduced space, is the same distance as the distance of $P$ in the original space? $\endgroup$ – DeltaIV Jun 16 '18 at 8:40
  • 1
    $\begingroup$ Or would you be content with an autoencoder which just learns representations of the training set which preserv the pairwise distances of the points in the training set? I.e., something like Multidimensional Scaling? $\endgroup$ – DeltaIV Jun 16 '18 at 13:45
  • 1
    $\begingroup$ @DeltaIV The property I would like to see is that if a sample in the test set is close to a point in training/test set in the original space, it would be close in the reduced space as well. $\endgroup$ – Mahdi Jun 18 '18 at 6:14
  • $\begingroup$ Thank you very much. Please include this information in the body of the question: all important info should be there. Comments are meant to be temporary. $\endgroup$ – DeltaIV Jun 18 '18 at 9:54
5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ +1 nice find that paper! (will read!) It reminded me of a statement I read years ago: "a basic linear auto-encoder learns essentially the same representation as a Principal Component Analysis (PCA)" Längkvist et al. Pattern Recognition Letters 42 (2014) 11-24. (So many great papers to read. I feel that if I read half of the papers I want to read but I have not read, I would read more paper than the ones I have read.) $\endgroup$ – usεr11852 Jun 24 '18 at 21:07
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ approach 2 is flawed - apart from the fact that the isometry group is made of reflections, rotations and translations (thus not only rotations, but any composition of the three: however, this is just a technicality), anyway the isometry group is made of bijections from a metric space $\mathcal{X}$ onto itself. Thus, they preserve dimension, and as such, are not the kind of transformation learnt by autoencoders, but not because of the nonlinearities (an autoencoder without the bottleneck layer could learn the identity transformation): because of dimensionality reduction. $\endgroup$ – DeltaIV Jun 16 '18 at 7:58
  • $\begingroup$ @DeltaIV Added an 'edit' to address your point, ie, I agree that auto-encoders dont in general preserve distance; and I was going a step further and thinking about, "what can one do if one did want them to preserve distance?". $\endgroup$ – Hugh Perkins Jun 16 '18 at 13:27
  • 1
    $\begingroup$ @DeltaIV Actually, I realized, I didnt fully read your comment before replying :D added 'edit 2', addressing the dimensionality reduction part, which I confess, I hadn't got as far as thinking about earlier :) $\endgroup$ – Hugh Perkins Jun 16 '18 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.