Understanding t-SNE


I am fascinated by visualizations of high-dimensional vectors such as PCA, t-SNE, and UMAP. I wanted to understand UMAP because it is the latest and said to be faster than t-SNE. However, UMAP looks challenging to me yet, so I will start with t-SNE first. What I am not sure is how the dimensionality reduction is related to other machine learning method like deep neural network. I will think about it after understanding t-SNE and UMAP.

###Stochastic? Embedding?  

The original paper is here, which was published in 2008. The SNE means Stochastic Neighbor Embedding. Do know what stochastic means? Read the following statement from http://mathworld.wolfram.com/Stochastic.html.

>Stochastic is synonymous with "random." The word is of Greek origin and means "pertaining to chance" (Parzen 1962, p. 7). It is used to indicate that a particular subject is seen from point of view of randomness. Stochastic is often used as counterpart of the word "deterministic," which means that random phenomena are not involved. Therefore, stochastic models are based on random trials, while deterministic models always produce the same output for a given starting condition. 

In short, stochastic means that we consider the data was generated with randomness probably with a normal distribution or t-distribution. Then what's the meaning of embedding? It is a lingo from math. See http://mathworld.wolfram.com/Embedding.html

>An embedding is a representation of a topological object, manifold, graph, field, etc. in a certain space in such a way that its connectivity or algebraic properties are preserved. For example, a field embedding preserves the algebraic structure of plus and times, an embedding of a topological space preserves open sets, and a graph embedding preserves connectivity. 


Lots of math terms. Embedding is a representation of something with the same properties. If it is a topological space, open sets are preserved.

### Similarity in the High-dimensional Space

First, probabilities are calculated by the equation below for each data points. The probabilities are for the high-dimensional space. As we will see later, we will define the probabilities for low-dimensional space, too in a similar way.

```math
Eq. 1 \ \ \ \ \ \begin{equation}p_{j|i}= \cfrac{\exp\left({-||x_i - x_j||^2/2{\sigma_i}^2}\right)}{\sum_{k\ne i}^{} \exp\left({-||x_i - x_k||^2/2{\sigma_i}^2}\right)}\end{equation} 
```
Eq. 1 is a conditional probability/similarity of $x_{i} \ to \ x_{j}$. In other words, it is a similarity of the data point $x_j$ to $x_i$. To calculate the probability

>The first step is to convert high-dimensional Euclidean distances into conditional probabilities that represents similarities. 

First, let's see the Gaussian function.

```math
 \begin{equation} g(x) = \cfrac{1}{\sigma\sqrt{2\pi}}\exp\left(-\cfrac{1}{2}{\left( {\left( x-\mu\right)}/{\sigma}\right)^2}\right)\end{equation} 
```
So the x axis is the square of the distance between two vectors, and the sigma i of the Eq. 1 is the standard deviation of the distribution.
<img width="416" alt="Screen Shot 2019-06-21 at 3.44.47 AM.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/435846/f1f93db5-6bf8-d742-2344-f3600d24eac2.png">

The Eq. 1 is a probability in which i evaluates the similarity of j based on the values shown above. What affects the probability is the distance of the two vectors, the sigma i of the curve, and the distribution of the data points.
<img width="719" alt="Screen Shot 2019-06-21 at 3.45.11 AM.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/435846/eec509ef-4dd2-340a-dd12-b217927ff8e7.png">


The $p_{j|i}$ will be small in the left case above, and large in the right case. Therefore the probability reflects the distance relative to other distances. If the i-j distance is relatively small than other distances, the probability will be large. Oppositely, the i-j distance is large relative to other distances, the probability will be small.

So, **the probability reflects a relative similarity of the data point j to i compared to other data points.**

### Similarity in the Low-dimensional Space

Similarly, the probabilities in the low-dimensional space is defined as following:


```math
Eq. 2\ \ \ \ \ \ \ \begin{equation}q_{j|i}= \cfrac{\exp\left({-||y_i - y_j||^2}\right)}{\sum_{k\ne i}^{} \exp\left({-||y_i - y_k||^2}\right)}\end{equation} \ \ 
```

Please be careful that the $y_i$ and else are not yet known in the Eq. 2 above. In the Eq. 1, the x are known because they are the original data in the high-dimensional space. Technically, initial ys are set and optimization goes on using a loss function. The point in the t-SNE is

- Similarities of any two data points are calculated in the high-dimensional space
- An initial vector in the low-dimensional space are set
- Similarities of any two data points are calculated in the low-dimensional space
- A loss function is calculated to optimize the vector in the low-dimensional space

The only difference between the Eq. 1 and the Eq. 2 is the sigma. Why the Eq. 2 doesn't include the variance? The original paper says that the standard deviation in the Eq. 2 is set to $\frac{1}{\sqrt{2}}$ so that the Eq. 2 looks simple. I don't know why.

Now we have two probabilities for each data point, so we can use KL divergence as following as a cost function:

```math
C=\sum_{i}KL ( P_{i}||Q_{i} ) =\sum_{i}\sum_{j}p_{j|i}log{\frac{p_{j|i}}{q_{j|i}}}
```
If you are not familiar with KL divergence, see <a href='https://qiita.com/takahh/items/befa7a009eeb8fe0ffe4'>**my previous post.**</a>

Because t-SNE uses Gaussian function and the Eq. 2, it evaluates the local structure more than the global structure.

We need to optimize the $\sigma_i$. The paper says as following:

> SNE performs a binary search for the value of $\sigma_i$ that produces a $P_i$ with a fixed perplexity that is specified by the user

The perplexity is defined by

```math
Perp(P_i)=2^{H(P_i)}
```
where, $H(P_i)$ is the Shannon entropy of $P_i$ 

```math
H(P_i)=- \sum_{j}p_{j|i}\ log_{2} \ p_{j|i}
```

Thus the perplexity determines how the p would scatter for $x_i$. The $\sigma_i$ determines p, so setting the perplexity determines the $\sigma_i$.

It is said that 5-50 would be good as the perplexity.

OK. Then we would like to optimize $y$ by the following gradient:

```math
\frac{\delta C}{\delta y_i}=2\sum_j (p_{j|i}-q_{j|i}+p_{i|j}-q_{i|j})(y_i-y_j)
```