# Connection between Stochastic Neighbor Embedding and MDS

In the original SNE paper the authors mention a connection between the SNE objective function and an MDS-like stress function in the regime $$\sigma_i \rightarrow \infty$$, as follows.

When $$\sigma_i^2$$ is very large, it can be shown that SNE is equivalent to minimizing the mismatch between squared distances in the two spaces, provided all the squared distances from an object $$i$$ are first normalized by subtracting off their antigeometric mean $$g_i^2$$: $$\textrm{Mismatch} = \sum_{ij} \big[(d_{ij}^2 - g_i^2) - (\hat{d}_{ij}^2 - \hat{g}_i^2) \big]^2$$ with $$d_{ij}^2 = \lVert x_i - x_j \rVert^2 / \sigma^2,\quad g_i^2 = -\log \sum_{k \ne i} \frac{\exp(-d_{ij}^2)}{n -1}$$ and $$\hat{d}_{ij}^2$$ and $$\hat{g}_i^2$$ defined similarly for the embedding points $$\{y_i\}$$.

My question is, how exactly is this mismatch function derived and what does it represent?

It seems strange because they say "when $$\sigma_i^2$$ is very large" so one might expect that they're talking about a limit, but then there's still a $$\sigma$$ in the expression obtained. Also, for $$\sigma_i = \sigma$$ constant, the expression inside the brackets is exactly $$-\log(p_{ij}) + \log(q_{ij})$$ and I don't see where the square could come from. What is going on here?

• +1. I wondered about it too. I like how they use "it can be shown" here :) – amoeba says Reinstate Monica Oct 11 '19 at 19:46
• It cannot be the actual limit, because in the limit all p_i's are equal and the loss is minimized when all points in the embedding are infinitely far away from each other (to make q's equal to 0). – amoeba says Reinstate Monica Oct 11 '19 at 19:49
• Not infinitely far away, but uniformly distributed. In the limit, only the entropy part of the KL divergence remains, which is maximized when the distribution is uniform. – Călin Oct 12 '19 at 10:39
• Why? If all p's are equal, then the loss function is simpy \sum\log(q) up to a constant factor, and this is minimized when points are infinitely far away from each other. – amoeba says Reinstate Monica Oct 15 '19 at 7:37
• $\mathrm{D}_{\textrm{KL}} [ p_i \parallel q_i ] = -\log(n - 1) - \frac{1}{n - 1} \sum_{j = 1}^n \log q_{ij}$, with $\lim_{\sigma \to \infty} p_{ij} = \frac{1}{n - 1}$, so minimizing the KL divergence corresponds to maximizing the term you mentioned. It's not the entropy, as I said above (I was thinking about the exclusive formulation of the KL divergence), but it's still maximized when $q_i$ is the uniform distribution. This is also intuitive: you match an uniform distribution with another uniform one. – Călin Oct 15 '19 at 11:29