1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ +1. I wondered about it too. I like how they use "it can be shown" here :) $\endgroup$ – amoeba says Reinstate Monica Oct 11 '19 at 19:46
  • $\begingroup$ 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). $\endgroup$ – amoeba says Reinstate Monica Oct 11 '19 at 19:49
  • $\begingroup$ 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. $\endgroup$ – Călin Oct 12 '19 at 10:39
  • $\begingroup$ 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. $\endgroup$ – amoeba says Reinstate Monica Oct 15 '19 at 7:37
  • $\begingroup$ $\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. $\endgroup$ – Călin Oct 15 '19 at 11:29

Your Answer

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

Browse other questions tagged or ask your own question.