Guest author: thanks to Aviv Netanyahu for writing this post!

Before working on a dataset we would like to understand it. After working on it, we want to communicate our conclusions with others easily. When dealing with high-dimensional data, it’s hard to get a ’feel’ for the data by just looking at numbers, and we will advance pretty slowly. For example, common visualization methods are histograms and scatter plots, which capture only one or two parameters at a time, meaning we would have to look at many histograms (one for each feature). However, by visualizing our data we may instantly be able to recognize structure. In order to do this we would like to find a representation of our data in $2$ D or $3$ D.

Find an embedding of high-dimensional data to 2D or 3D (for simplicity, will assume $2$ D from now on).
Formally, we want to learn $$\{\mathbf{x}_{1},...,\mathbf{x}_{N}\}\to\{\mathbf{y}_{1},...,\mathbf{y}_{N}\}$$ ($\{\mathbf{x}_{1},...,\mathbf{x}_{N}\}\subseteq\mathbb{R}^{n}$ is our data, $\{\mathbf{y}_{1},...,\mathbf{y}_{N}\}\subseteq\mathbb{R}^{2}$ is the embedding) such that the structure of the original data is preserved after the embedding.

PCA projects high-dimensional data onto a lower dimension determined by the directions where the data varies most in. The result is a linear projection which focuses on preserving distance between dissimilar data points. This is problematic:

This algorithm for high-dimensional data visualization focuses on preserving high-dimensional ’neighbors’ in low-dimension.

This is good, as structure is preserved better by focusing on keeping close points together. This is easy to see in the following example: think of “unrolling” this swiss roll (like unrolling a carpet). Close points will stay within the same distance, far points won’t. This is true for many manifolds (spaces that locally resemble Euclidean space near each point) besides the swiss roll.

The main problem with SNE - mapped points tend to “crowd” together, like in this example: images of 5 MNIST digits mapped with SNE to 2D and then marked by labels

Instead of mapped points correcting themselves to minimize the loss, we can do this by increasing $q_{j|i}$ in advance. Recall, the loss is: $\sum\limits _{i}\sum\limits _{j}p_{j|i}\log\frac{p_{j|i}}{q_{j|i}}$ , thus larger $q_{j|i}$ minimizes it. We do this by defining: $$q_{ij}=\frac{(1+||\mathbf{y}_{i}-\mathbf{y}_{j}||)^{-1}}{\sum\limits _{k\neq l}(1+||\mathbf{y}_{k}-\mathbf{y}_{l}||)^{-1}}$$ using Cauchy distribution instead of Gaussian distribution. This increases $q_{j|i}$ since Cauchy distribution has a heavier tail than Gaussian distribution:

Computing the gradient for each mapped point each iteration is very costly, especially when the dataset is very large. At each iteration, $\forall i$ , we compute: $$\frac{\partial C}{\partial\mathbf{y}_{i}}=4\sum_{j\neq i}\frac{(p_{ij}-q_{ij})}{1+||\mathbf{y}_{i}-\mathbf{y}_{j}||^{2}}\cdot(\mathbf{y}_{i}-\mathbf{y}_{j})$$ We can think of $\mathbf{y}_{i}-\mathbf{y}_{j}$ as a spring between these two points (it might be too tight/loose depending on if the points were mapped to far/close accordingly). The fraction can be thought of as exertion/compression of the spring, in other words the correction we do in this iteration. We calculate this for $N$ mapped points, and derive $C$ by all data-points, so for each iteration we have $\mathcal{O}(N^{2})$ computations. This limits us to datasets with only few thousands of points! However, we can reduce the computation time to $\mathcal{O}(N\log N)$ by reducing the number of computations per iteration. The main idea - forces exerted by a group of points on a point that is relatively far away are all very similar. Therefore we can calculate $\mathbf{y}_{i}-\mathbf{y}_{j^{*}}$ where $\mathbf{y}_{j^{*}}$ is the average of the group of far away points, instead of $\mathbf{y}_{i}-\mathbf{y}_{j}$ for each $\mathbf{y}_{j}$ in the far away group.

When the data is noisy or on a highly varying manifold, the local linearity assumption we make (by converting Euclidean distances to similarities) does not hold. What can we do? - smooth data with PCA (in case of noise) or use Autoencoders (in case of highly varying manifold).