What're the differences between PCA and autoencoder?

Question

Both PCA and autoencoder can do demension reduction, so what are the difference between them? In what situation I should use one over another?

Answer 1

PCA is restricted to a linear map, while auto encoders can have nonlinear enoder/decoders.

A single layer auto encoder with linear transfer function is nearly equivalent to PCA, where nearly means that the $W$ found by AE and PCA won't necessarily be the same - but the subspace spanned by the respective $W$'s will.

Answer 2

As bayerj points out PCA is method that assumes linear systems where as Autoencoders (AE) do not. If no non-linear function is used in the AE and the number of neurons in the hidden layer is of smaller dimension then that of the input then PCA and AE can yield the same result. Otherwise the AE may find a different subspace.

One thing to note is that the hidden layer in an AE can be of greater dimensionality than that of the input. In such cases AE's may not be doing dimensionality reduction. In this case we perceive them as doing a transformation from one feature space to another wherein the data in the new feature space disentangles factors of variation.

Regarding to your question about whether multiple layers means very complex non-linear in your response to bayerj. Depending on what you mean by "very complex non-linear" this could be true. However depth is really offering better generalization. Many methods require an equal number of samples equal to the number of regions. However it turns out that "a very large number of regions, e.g., $O(2^N)$, can be defined with $O(N)$ examples" according to Bengio et al. This is a result of the complexity in representation that arises from composing lower features from lower layers in the network.

Answer 3

The currently accepted answer by @bayerj states that the weights of a linear autoencoder span the same subspace as the principal components found by PCA, but they are not the same vectors. In particular, they are not an orthogonal basis. This is true, however we can easily recover the principal components loading vectors from the autoencoder weights. A little bit of notation: let $\{\mathbf{x}_i \in \mathbb{R}^n \}_{i=1}^N $ be a set of $N$ $n-$dimensional vectors, for which we wish to compute the PCA, and let $X$ be the matrix whose columns are $\mathbf{x}_1,\dots,\mathbf{x}_N$. Then, let's define a linear autoencoder as the one-hidden layer neural network defined by the following equations:

$$ \begin{align} \mathbf{h}_1 & = \mathbf{W}_1\mathbf{x} + \mathbf{b}_1 \\ \hat{\mathbf{x}} & = \mathbf{W}_2\mathbf{h}_1 + \mathbf{b}_2 \end{align} $$

where $\hat{\mathbf{x}}$ is the output of the (linear) autoencoder, denoted with a hat in order to stress the fact that the output of an autoencoder is a "reconstruction" of the input. Note that, as it's most common with autoencoders, the hidden layer has less units than the input layer, i.e., $W_1\in \mathbb{R}^{n \times m}$ and $W_2\in \mathbb{R}^{m \times n}$ with $m < n$.

Now, after training your linear autoencoder, compute the first $m$ singular vectors of $W_2$. It's possible to prove that these singular vectors are actually the first $m$ principal components of $X$, and the proof is in Plaut, E.,From Principal Subspaces to Principal Components with Linear Autoencoders, Arxiv.org:1804.10253.

Since SVD is actually the algorithm commonly used to compute PCA, it could seem meaningless to first train a linear autoencoder and then apply SVD to $W_2$ in order to recover then first $m$ loading vectors, rather than directly applying SVD to $X$. The point is that $X$ is a $n \times N$ matrix, while a $W_2$ is $m\times n$. Now, the time complexity of SVD for $W_2$ is $O(m^2n)$, while for $X$ is $O(n^2N)$ with $m < n $, thus some saving could be attained (even if not as big as claimed by the author of the paper I link). Of course, there are other more useful approaches to compute the PCA of Big Data (randomized online PCA comes to mind), but the main point of this equivalence between linear autoencoders and PCA is not to find a practical way to compute PCA for huge data sets: it's more about giving us an intuition on the connections between autoencoders and other statistical approaches to dimension reduction.

Answer 4

The general answer is that auto-associative neural networks can perform non-linear dimensionality reduction. Training the network is generally not as fast as PCA, so the trade-off is computational resources vs. expressive power.

However, there was a confusion in the details, which is a common misconception. It is true that auto-associate networks with linear activation functions agree with PCA, regardless of the number of hidden layers. However, if there is only 1 hidden layer (input-hidden-output), the optimal auto-associative network still agrees with PCA, even with non-linear activation functions. For the original proof see the 1988 paper by Bourlard and Kamp. Chris Bishop's book has a nice summary of the situation, in Ch.12.4.2:

It might be thought that the limitations of a linear dimensionality reduction could be overcome by using nonlinear (sigmoidal) activation functions for the hidden units in the network in Figure 12.18. However, even with nonlinear hidden units, the minimum error solution is again given by the projection onto the principal component subspace (Bourlard and Kamp, 1988). There is therefore no advantage in using two-layer neural networks to perform dimensionality reduction.