T-distributed Stochastic Neighbor Embedding (t-SNE/tSNE)

tSNE - Algorithm

Convert Distance “Structure” Between Points in High Dimensional Raw Data into a Probability Distribution (Target)

1. measure distance from one point wrt every other point
2. map distance to the normal probability distribution
3. scale distances to 1 (similar to softmax)
4. steps 2 & 3 can be combined with the following equation:
   • $P_{j|i}=\frac{norm(x_i-x_j)}{{\sum }_{k\ne i}norm(x_i-x_k)}$
   • $P_{j|i}=\frac{exp(-||x_i-x_j|{|}^2/(2{𝜎}_i^2))}{{\sum }_{k\ne i}exp(-||x_i-x_k|{|}^2/(2{𝜎}_i^2))}$
5. convert conditional probabilities into joint probabilities
   1. $P_{ij}=\frac{P_{j|i}+P_{i|j}}{2n}$
6. (𝜎_𝑖)² controls what “closeness” means; these variances are chosen so that the entropy equals a user-specific value called the perplexity
   1. $Perplexity=2^{-{\sum }_j{P}_{j|i}lo{g}_2{P}_{i|j}}$

Convert Distance “Structure” Between Points in Reduced Dimensional Space into a Probability Distribution

• Randomly plot all points onto low dimensional space (initialize)
• calculate probability distribution with t-distribution:
  • $Qij=\frac{(1+||x_i-x_j||{)}^{-1}}{{\sum }_{k\ne i}(1+||x_i-x_k||{)}^{-1}}$

Make Adjustments to Points in Reduced Space s.t. its Probability Distribution equals the Target Probability Distribution

• KL divergence measures the “distance” between two probability distributions
  • $KL(P||Q)={\sum }_{i,j}{P}_{ij}log(\frac{P_{ij}}{Q_{ij}})$
• Use gradient descent to minimize the sum of the KL divergence over all the points
• Take the partial derivative of the cost function wrt every point. This partial derivative tells us how to move the points within the reduced dimensional space.
  • $\frac{𝛿KL(P||Q)}{𝛿x_i}=4{\sum }_j\frac{P_{ij}-Q_{ij}}{(1+||x_i-x_j||{)}^{-1}}(x_i-x_j)$

tSNE - Other

• tSNE vs UMAP

Resources

• https://distill.pub/2016/misread-tsne/
• https://github.com/robkravec/t-SNE-Implementation/blob/main/Implementing%20t-SNE%20in%20Python%20with%20Optimized%20Code%20and%20Examples.ipynb