2
$\begingroup$

From the article on Stochastic Neighbor Embedding (by Geoffrey Hinton and Sam Roweis):

Stochastic Neighbor Embedding (SNE) tries to place the objects in a low-dimensional space so as to optimally preserve neighborhood identity and can be naturally extended to allow multiple different low-d images of each object.

What is actually meant by this? and how can it be seen in practice? Why don't other algorithms like Isomap preserve nighborhood identity?

$\endgroup$
2
$\begingroup$

It is a slightly dense sentence indeed. It tries to combine two central notions, "preserving neighbourhood identity" and "extending to multiple different low-d images", in one go. The original paper by Hinton and Roweis can be found here.

The main part is the "preserving neighbourhood identity". This means that the main notion used is the pairwise distances between points as to ensure "similar points are still close to each other". This is in contrast for example with PCA where the main notion used it the covariance matrix of the points (or better yet the diagonalization of it).

Aside the obvious "points with low dissimilarity are close to each other", the other point that this can be seen in practice is that the distance between the clusters is uninformative. Similarly, individual axes are also devoid of a physical meaning. This has been touched more detail in the thread: "What is the meaning of the axes in t-SNE?".

Specifically for Isomap, which can be viewed as a variant of standard multi-dimensional scaling (MDS), instead of the direct pairwise distances in Euclidean space, we use the geodesic distance between all pairs of points on a graph $G$. That graph $G$ is constructed such that there is an edge between any two neighbouring points; that geodesic distance is approximated by the shortest path between points on $G$. So theoretically, Isomap cares about the neighbourhood identity on the graph $G$ rather than on the original space of the data. This might cause certain points that "seem" close to drift further apart (especially if the neighbourhood size small).

To briefly touch upon the notion of "extending to multiple different low-d images" too: Exactly because SNE has a probabilistic interpretation, we can redefine our problem of estimating the induced probabilities $q_{ij}$ as being drawn from a mixture distribution (Eq. 6 in the paper) instead of a single one (Eq. 3). By changing the mixing proportions $\pi$ of the mixture distribution one can theoretically explore the linear combination of various non-linear manifolds.

In general, all data visualisation algorithms try to preserve some sort of neighbourhood identity; they would be almost indecipherable otherwise! Some algorithms, explicitly try to work with the distance between two points $x_j$ and $x_i$, while some others try to implicitly respect it but focus on some other aspect of similarity.

| cite | improve this answer | |
$\endgroup$

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.