KO | EN

GitLite

Minimalist Open Source Repository Search Engine

gitlite — search

#dsh #dsh-plugin #typescript #ai-agent #developer-tools #claude-code #codex #deepseek-harness #ai-agents #react #mcp #rust

t-SNE

★ 3 Open GitHub ↗

Implementation of t-SNE and Barnes-Hut-SNE algorithm. Comparison of algorithm implementation with sklearn library implementation on sample databases.

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# t-Distributed Stochastic Neighbor Embedding (t-SNE algorithm)

## Table of contents
1. [t-SNE algorithm](#p1)
2. [Barnes-Hut-SNE algorithm](#p2)
3. [t-SNE and Barnes-Hut-SNE project structure](#p3)
4. [Databases and results](#p4)
5. [References](#p5)

## t-SNE algorithm <a name="p1" /></a>

t-SNE algorithm represents non linear dimensionality reduction method which maps high-dimensional data X = {x1, x2, ..., xn} in low dimensional data Y = {y1, y2, ..., yn} such that we preserve as much information as possible. This is done by making pairwise similarities pij between high dimensional points X as similar as possible to pairwise similarities qij between low dimensional points Y. 
Pairwise similarities pij are defined with Gaussian distributions:

Where each of Gaussian variances centered in data point xi we can obtain by binary search of sigma_i for predefined perplexity (neighborhood points): 
 
 
<img src="https://user-images.githubusercontent.com/24530942/218085105-00690dd0-953e-4aa8-8e47-2e78f06b843b.png" height="50" width="400">

Pairwise similarities qij are defined with Student t-distribution:

Student t-distribution is used to overcome "Crowding Problem". Similarities between same points are set to zero so pij and qij are set to 0. 
For mapping to be successful we want that these high dimensional distributions pij are as same as possible to low dimensional distributions qij. Hance, Kullback-Leibler divergence is used as criterium function which is minimized: 
 
<img src="https://user-images.githubusercontent.com/24530942/218095840-53886d17-30ee-427e-8d08-b86dcca5be7d.png" height="60" width="250">

KL divergence is minimized using gradient decent algorithm, with adaptive learning rate and momentum. 
 <ins>Pseudo code od the algorithm can be found below:</ins>

<img src="https://user-images.githubusercontent.com/24530942/218096573-1811ded6-f999-4833-8a8f-7fee2afa24e6.png" height="300" width="550">
 
## Barnes-Hut-SNE algorithm <a name="p2" /></a>

Time and memory complexity of t-SNE algorithm is O(N^2), where N is number of data points, which is not appropriate for datasets with more than few thousand points. Barnes-Hut-SNE is approximation of t-SNE algorithms which requires O(NlogN) time and memory complexity and can be used for large datasets. Barnes-Hut-SNE uses 2 approximations: 
	&emsp;1. Approximation of input data similarity pij 
	&emsp;2. Approximation of t-SNE gradient calculation 
	
First approximation is done using k-dimensional (k-d) tree for finding the first p=3*perplexity neighbors of each input data point. Complexity of this approach is O(NlogN). Example k-d tree constructed on synthetic data is presented in picture below:

t-SNE KL gradient is defined with formula:

KL Gradient can be represented as follows:

F_attr can be calculated in O(pN) time complexity. F_rep requires O(N^2) time complexity which we can reduce to O(NlogN) using Barnes-Hut approximation. Barnes-Hut-SNE constructs quad tree on output (low-dimensional) data Y and in each iteration of calculation of F_rep it decides if current node can be used as summary of contribution to F_rep for all the data inside that node. Example quad tree constructed on synthetic data is presented in picture below:

## t-SNE and Barnes-Hut-SNE project structure <a name="p3" /></a>

Project structure can be found in picture below. Module tsne_algorithm is the core module and has t-SNE and Barnes-Hut-SNE implemented using only numpy. Implementation of tree structures (k-d tree and quad tree) can be found in module tsne_algorithm/trees. Module tsne_test_script has scripts for testing t-SNE implementation and it is used for results visualisation. Folder dataset contains data used for testing t-SNE implementation. Test data can be obtaind just by unzipping 7z files.

## Databases and results <a name="p4" /></a>

Two databases are use as test of tsne and Barnes-Hut-SNE implementation: 
&emsp;1. MNIST - 6000 images of digits 0-9 with resolution 28x28. Sample images can be found below

&emsp;2. Olivetti faces - 400 images of 40 different people with resolution 64x64. Sample images can be found below.

<ins> Results on MNIST dataset on 4000 samples of t-SNE "exact" method </ins>

<ins> Results on MNIST dataset on 1000 samples of Barnes-Hut-SNE method </ins>

<ins> Results on Olivetti faces dataset of t-SNE "exact" method </ins>

<ins> Results on Olivetti faces dataset of Barnes-Hut-SNE method </ins>

## References <a name="p5" /></a>
**Implementation of t-SNE algorithm references** 
<ins>t-SNE algorithm:</ins> 
https://distill.pub/2016/misread-tsne/ 
https://towardsdatascience.com/t-sne-clearly-explained-d84c537f53a 
https://jeremy9959.net/Blog/tsne_annotated-fixed/ 
http://jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf 
<ins>Adaptive learning rate update:</ins> 
https://web.cs.umass.edu/publication/docs/1987/UM-CS-1987-117.pdf 
<ins>K-d tree:</ins> 
https://upcommons.upc.edu/bitstream/handle/2117/76382/hpgm_15_1.pdf 
https://arxiv.org/pdf/cs/9901013.pdf 
https://en.wikipedia.org/wiki/K-d_tree 
<ins>Neighbors Heap:</ins> 
https://www.hackerearth.com/practice/notes/heaps-and-priority-queues/ 
<ins>Quad tree</ins> 
https://en.wikipedia.org/wiki/Quadtree 
<ins>Barnes-Hut approximation in t-SNE:</ins> 
https://arxiv.org/pdf/1301.3342.pdf 
https://jheer.github.io/barnes-hut/

t-SNE

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README