2a:null 2b:["$","title",null,{"children":"Opening the *t*-SNE black box | Roberto Stelling | Observable"}] 30:T6cd,tsneStart = md ` #### *Problem*: Given a dataset of points in high dimensions, how can we have an idea of how the points are organized in the original space?

Representing data from high dimensions in *3D* or *2D* (or in *1D*!), independent of their original organization in space, is a problem that do not have a unique and generic solution. Data can be organized in many ways in the original dimensions and different data contexts and usages can suggest or imply different projections in two or three dimensions. Depending on the *objective* of the aggregation and its *context* it is very likely that there is ***more than one solution*** to visualize the same high dimension dataset in *2D* or *3D*. In a way, it is a **poorly defined problem** that do not have an optimal solution. In some cases it may be possible to "manually" reduce dimensions, without the usage of an algorithm. For example, the [MNIST¹](#ref) dataset, with 28x28 pixels data, totaling 784 pixels - or dimentions, can be visualized in two dimenstions if we create two "*features*" that represent the same dataset, for example: density and symmetry[²²](#ref) of the original images. With these two dimensions it is possible to create a planar visualization of the digits 1 and 5, as in the the graph below, where 1s are represented with white dots and 5s with black dots.

Over these two new dimenstions we used a simple Perceptron to generate a cut line between digits 1 and 5 from the dataset.

`31:T456,tsne = md`To visualize data from high dimensions we can use #

*t*-SNE [*t*-Distributed Stochastic Neighbour Embedding²](#ref) (*t*-SNE, or ***tees-nee***, as most people call it) is a technique used to visualize data from high dimensions in *1D*, *2D* or *3D*. *t*-SNE, was developed by *Laurens van der Maaten* e *Geoffrey Hinton*, and it is a refinement of a previous method, SNE. The main diference between SNE and *t*-SNE is that the latter uses a Student *t* distribution to map the data on the lower dimensions. Essentially, *t*-SNE uses a gaussian kernel to convert the points on the original space to connection probabilities (**P**) and a Student *t* kernel, with one degree of freedom, to map the connection probabilities in the lower dimensions (**Q**). The cost of the diference between these two distribuitions **P** and **Q** is modeled by the asymmetric Kullbach-Leibler²⁰ divergence. The gradient of this function (see \`[Equation 5]\` bellow) is used to update the connection probabilities in the mapped (lower dimension) space.`32:T44b,tsneAlgorithm1 = md `# *t*-SNE Simplified Algorigthm **Data**: data set ${tex`X = \{x_1, x_2, \dots, x_n\}, x_i \in \mathbb{R}^M`}
Cost function parameters: perplexity ${tex`Perp`}
Optimization parameteres: number of interactions ${tex`T`}, learning rate ${tex`\eta`}, momentum ${tex`\alpha (t)`}.
**Result**: low-dimensional data representation ${tex`\gamma^{(T)} = \{y_1, y_2,\dots,y_n\}, y_i \in \mathbb{R}^{(1, 2, 3)}`}.
\`begin\`
  Compute pairwise affinities ${tex`p_{j|i}`} with perplexity ${tex`Perp`} (using \`Equation 1\`)
  set ${tex`p_{ij} = \frac{p_{j|i}+p_{i|j}}{2}`}
  sample initial solution ${tex`\gamma^{(0)} = \{y_1, y_2,\dots,y_n\}`} from ${tex`\mathcal{N}(0,10^{-4}I)`}
  \`for\` *t=1* \`to\` *T* \`do\`
    Compute low-dimensional affinities ${tex`q_{ij}`} (using \`Equation 4\`)
    Compute gradient ${tex`\frac{\delta C}{\delta \gamma}`} (using \`Equation 5\`)
    \`set\` ${tex`${gamma_eval}`}
  \`end\`
\`end\``33:T674,tsneAlgorithm2 = md `The depiction of the *t*-SNE algorithm above do not include a few important details that are clarified througout the original paper. To accomodate these details and to expose a few hidden corners of *t*-SNE, we will revisit the algorithm below. # *t*-SNE Simplified Algorithm
*Revised version* 1. Given a set of ${tex`N`} points in a high dimensional space 2. Define an entropy factor ${tex`Perp`}, learning rate ${tex`\eta`}, momentum ${tex`\alpha(t)`} and number of interactions ${tex`T`} 3. Compute the distancse between the points in high dimension, convert these distances to probabilities/affinities using a Gaussian kernel. Finding the correct variance for each point, so that it matches the entropy factor ${tex`Perp`} 4. Perform a binary search to determine the correct variance for each point, so that each line of the affinities matrix (${tex`p_{ik}\forall k`}) will have approximately the same entropy 5. Make the resulting matrix symmetric with ${tex`p_{i|j} = \frac{p_{i|j}+p_{j|i}}{2}`} 6. Gess an initial response set in the low-dimensional space ${tex`\gamma^{(1)} = \{y_1, \dots, y_N\}`} 7. Repeat ${tex`T`} times, updating ${tex`t = 1\dots T`}: 8. Compute the affinities on the mapped (low-dimensional) space, ${tex`q_{ij}`}, with a Student *t* distribution with one degree of freedom and ${tex`\sigma^2 = 1`} 9. Compute the grandient of the cost function ${tex`\gamma^{(t)} = \{y_1, \dots, y_N\}`} so that ${tex.block`${eq5}`} 10. Update the points on the low-dimension space so that: ${tex.block`${gamma_eval}`} 11. The set of points ${tex`\gamma^{(T)}`} is the algorithm output`34:Tcaf,vegalite({ width: 600, height: 300, layer: [ { title: "Gaussian with μ=0 and σ=1", data: {values: pointsNormal(-5, 5, 0.01, 1, 0)}, mark: {type: "area", fill:"#d0d0d0", fillOpacity: 0.4}, encoding: { x: {field: "x", type: "quantitative"}, y: {field: "y", type: "quantitative", title: "φ(x)"} } }, { data: { "values": [ {"x": distances[0][1], "y": 0}, {"x": distances[0][1], "y": normal(distances[0][1],1,0)}, ] }, mark: {type: "line"}, encoding: { x: {field: "x", type: "quantitative"}, y: {field: "y", type: "quantitative"} } }, { data: { "values": [ {"x": distances[0][1], "y": normal(distances[0][1],1,0)}, ] }, mark: {type: "text", baseline: "top", dx: 52, dy: -109}, encoding: { text: {field: "y", type: "quantitative"}, } }, { data: { "values": [ {"x": distances[0][2], "y": 0}, {"x": distances[0][2], "y": normal(distances[0][2],1,0)}, ] }, mark: {type: "line"}, encoding: { x: {field: "x", type: "quantitative"}, y: {field: "y", type: "quantitative"} } }, { data: { "values": [ {"x": distances[0][2], "y": normal(distances[0][2],1,0)}, ] }, mark: {type: "text", dx: 61, dy: -73}, encoding: { text: {field: "y", type: "quantitative"}, } }, { data: { "values": [ {"x": distances[0][3], "y": 0}, {"x": distances[0][3], "y": normal(distances[0][3],1,0)}, ] }, mark: {type: "line"}, encoding: { x: {field: "x", type: "quantitative"}, y: {field: "y", type: "quantitative"} } }, { data: { "values": [ {"x": distances[0][3], "y": normal(distances[0][3],1,0)}, ] }, mark: {type: "text", dx: 47, dy: -112}, encoding: { text: {field: "y", type: "quantitative"}, } }, { data: { "values": [ {"x": distances[0][4], "y": 0}, {"x": distances[0][4], "y": normal(distances[0][4],1,0)}, ] }, mark: {type: "line"}, encoding: { x: {field: "x", type: "quantitative"}, y: {field: "y", type: "quantitative"} } }, { data: { "values": [ {"x": distances[0][4], "y": normal(distances[0][4],1,0)}, ] }, mark: {type: "text", dx: 152, dy: 126}, encoding: { text: {field: "y", type: "quantitative"}, } }, { data: { "values": [ {"x": distances[0][5], "y": 0}, {"x": distances[0][5], "y": normal(distances[0][5],1,0)}, ] }, mark: {type: "line"}, encoding: { x: {field: "x", type: "quantitative"}, y: {field: "y", type: "quantitative"} } }, { data: { "values": [ {"x": distances[0][5], "y": normal(distances[0][5],1,0)}, ] }, mark: {type: "text", dx: 171, dy: 136}, encoding: { text: {field: "y", type: "quantitative"}, } }, ] })35:Tcba,vegalite({ width: 600, height: 300, layer: [ { title: "Student-t with μ=0 and σ=1, 1 degree of freedom", data: {values: pointsStudent(-5, 5, 0.01, 1, 0)}, mark: {type: "area", fill:"#d0d0d0", fillOpacity: 0.4}, encoding: { x: {field: "x", type: "quantitative"}, y: {field: "y", type: "quantitative", title: "φ(x)"} } }, { data: { "values": [ {"x": distances[0][1], "y": 0}, {"x": distances[0][1], "y": student(distances[0][1],1)}, ] }, mark: {type: "line"}, encoding: { x: {field: "x", type: "quantitative"}, y: {field: "y", type: "quantitative"} } }, { data: { "values": [ {"x": distances[0][1], "y": student(distances[0][1],1)}, ] }, mark: {type: "text", baseline: "top", dx: 52, dy: -61}, encoding: { text: {field: "y", type: "quantitative"}, } }, { data: { "values": [ {"x": distances[0][2], "y": 0}, {"x": distances[0][2], "y": student(distances[0][2],1)}, ] }, mark: {type: "line"}, encoding: { x: {field: "x", type: "quantitative"}, y: {field: "y", type: "quantitative"} } }, { data: { "values": [ {"x": distances[0][2], "y": student(distances[0][2],1)}, ] }, mark: {type: "text", dx: 61, dy: -23}, encoding: { text: {field: "y", type: "quantitative"}, } }, { data: { "values": [ {"x": distances[0][3], "y": 0}, {"x": distances[0][3], "y": student(distances[0][3],1)}, ] }, mark: {type: "line"}, encoding: { x: {field: "x", type: "quantitative"}, y: {field: "y", type: "quantitative"} } }, { data: { "values": [ {"x": distances[0][3], "y": student(distances[0][3],1)}, ] }, mark: {type: "text", dx: 47, dy: -63}, encoding: { text: {field: "y", type: "quantitative"}, } }, { data: { "values": [ {"x": distances[0][4], "y": 0}, {"x": distances[0][4], "y": student(distances[0][4],1)}, ] }, mark: {type: "line"}, encoding: { x: {field: "x", type: "quantitative"}, y: {field: "y", type: "quantitative"} } }, { data: { "values": [ {"x": distances[0][4], "y": student(distances[0][4],1)}, ] }, mark: {type: "text", dx: 150, dy: 102}, encoding: { text: {field: "y", type: "quantitative"}, } }, { data: { "values": [ {"x": distances[0][5], "y": 0}, {"x": distances[0][5], "y": student(distances[0][5],1)}, ] }, mark: {type: "line"}, encoding: { x: {field: "x", type: "quantitative"}, y: {field: "y", type: "quantitative"} } }, { data: { "values": [ {"x": distances[0][5], "y": student(distances[0][5],1)}, ] }, mark: {type: "text", dx: 171, dy: 112}, encoding: { text: {field: "y", type: "quantitative"}, } }, ] })36:T560,md`# Gradient The gradient of the cost function is given by \`[Equation 5]\`, that relates the probabilities on the high dimension space (${tex`p_{ij}`}) with the probabilities on the mapped space (${tex`q_{ij}`}) and the points on the the mapped space (${tex`y_i`} e ${tex`y_j`}). ${tex.block`${eq5}`} During the optimization stage, ${tex`p`} is kept fixed, the points ${tex`y`} are adjusted according to the gradient and, by definition, the low dimension probabilities ${tex`q`} are recomputed after each iteration. To speed the the optimization stage and to help find better solutions, the paper suggest the following two *"tricks"*: 1. **Initial compression**: This forces the points of the mapped space to be closer on the beginning of the optimization. The smaller the initial distances, the easier it is for the agglomerations to form, resulting on a better exploration of the solution space. 2. **Initial exageration**: Multiply all ${tex`p_{ij}`} by a fixed factor (e.g. 4) during the first steps of the optimization. This means that almost all ${tex`q_{ij}`}, that still add up to 1, are too small to model high values of ${tex`p_{ij}`}. This means that the optimization is "encouraged" to model high ${tex`p_{ij}`} to high ${tex`q_{ij}`}, this tend to separate the agglomerations in different groups in the mapped space and help the clusters to move to and fro.`37:T4c3,md`Learning rate: ${bind(html``, viewof eta)} ${bind(html``, viewof eta)}
Momentum update: ${bind(html``, viewof triggerMomentum)} ${bind(html``, viewof triggerMomentum)}
Exaggeration factor: ${bind(html``, viewof exaggerationFactor)} ${bind(html``, viewof exaggerationFactor)}
Exaggeration stop: ${bind(html``, viewof stopExaggeration)} ${bind(html``, viewof stopExaggeration)}
Perplexity: ${bind(html``, viewof Perp)} ${bind(html``, viewof Perp)}
Number of Interactions: ${bind(html``, viewof T)} ${bind(html``, viewof T)}`38:T774,pointsMap = { if (iteractionCount >= T) yield yDisplay.map((p, i)=>(p.y==undefined?{x:Y[i][0], name:p.name, Cluster:p.Cluster}: {x:Y[i][0], y:Y[i][1], name:p.name, Cluster:p.Cluster})); else { // Adapted from: https://github.com/karpathy/tsnejs var N = Y.length; var dim = Y[0].length; var grad = gradient(Y, pFinal, iteractionCount); var sign = ((p)=>p<0?-1:p>0?1:p); mutable costRun = cost(Y, pFinal); mutable iteractionCount++; // perform gradient step for(var i=0;i(p.y==undefined?{x:Y[i][0], name:p.name, Cluster:p.Cluster}: {x:Y[i][0], y:Y[i][1], name:p.name, Cluster:p.Cluster})); } }39:T424,md `# Limitations - *t*-SNE: - The algorithm do not preserve distances nor densities, it preserves only, up to a certain degree, the neighbourhood. - The performance of *t*-SNE in general tasks of dimensionality reduction is not clearly defined. - There's no guarantee of convergence. - The value of the hyperparameter \`Perp\` can highly influence the resulting map. - This implementation: - The current implementation is a bit fractioned (with pieces and bits of code spread throughout the notebook) and applies ontly from maps from ${tex`\mathbb{R}^M`} to ${tex`\mathbb{R}^{1|2}`}. - It is not difficult to include other datasets, but the process is currently manual. - Text and code can be downloaded from here or from Github²³. - Although one can observe interesting behaviours of *t*-SNE in reductions from ${tex`\mathbb{R}^2`} to ${tex`\mathbb{R}^1`} or mapping to ${tex`\mathbb{R}^2`}, one should generalize the results observed in this notebook with care, given the limited dataset and minimal reduction.`3a:T98e,ref = md`# References and recommended reading ### Paper's BibTeX \`\`\` @article{maaten2008visualizing, title={Visualizing data using t-SNE}, author={Maaten, Laurens van der and Hinton, Geoffrey}, journal={Journal of machine learning research}, volume={9}, number={Nov}, pages={2579--2605}, year={2008} } \`\`\` ### Links 1. [MNIST](http://yann.lecun.com/exdb/mnist/) 2. [Paper: Visualizing data using t-SNE](http://www.jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf) 3. [*t*-SNE site - Laurens van der Maaten](https://lvdmaaten.github.io/tsne/) 4. [Wikipedia: t-SNE](https://en.wikipedia.org/wiki/T-distributed_stochastic_neighbor_embedding) 5. [Paper: Linear t-SNE optimization for the web](https://arxiv.org/pdf/1805.10817.pdf) 6. [How to use t-SNE effectively](https://distill.pub/2016/misread-tsne/) 7. [Introduction to t-SNE with Python](https://towardsdatascience.com/an-introduction-to-t-sne-with-python-example-5a3a293108d1) 8. [t-SNE implemented in R and Python](https://www.analyticsvidhya.com/blog/2017/01/t-sne-implementation-r-python/) 9. [Visualizing datasets with PCA and t-SNE in Python](https://medium.com/@luckylwk/visualising-high-dimensional-datasets-using-pca-and-t-sne-in-python-8ef87e7915b) 10. [t-SNE Guide with Python and R](https://www.analyticsvidhya.com/blog/2017/01/t-sne-implementation-r-python/) 11. [Real time t-SNE Visualizations with TensorFlow.js](https://ai.googleblog.com/2018/06/realtime-tsne-visualizations-with.html) 12. [t-SNE implementation in JavaScript - Karpathy](https://github.com/karpathy/tsnejs) 13. [Why momentum works](https://distill.pub/2017/momentum/) 14. [GoogleBlog: TensorFlow Embedding Projector](https://ai.googleblog.com/2016/12/open-sourcing-embedding-projector-tool.html) 15. [TensorFlow Embedding Projector](http://projector.tensorflow.org/) 16. [Tensorflow: Embeddings](https://www.tensorflow.org/guide/embedding) 17. [Tensorflow.js](https://js.tensorflow.org/) 18. [Student's *t*-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 19. [Gamma Function](https://github.com/substack/gamma.js/blob/master/index.js) 20. [Wikipedia: Kullback-Leibler](https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence) 21. [Mike Bostock - Let's try t-SNE](https://beta.observablehq.com/@mbostock/lets-try-t-sne) 22. [Yasser S. Abu-Mostafa - Caltech](https://work.caltech.edu/) 23. [Github repository](https://github.com/RobStelling/tsne)`3b:[] 2e:{"id":"2379c50fe5f906fb","slug":"t-sne_en","title":"Opening the *t*-SNE black box","thumbnail":"4e6ca27f96b4125210273eb360dd0cd06a873b46c96d4ff25ca508ce2e984f2e","access_level":"public","create_time":"$D2019-01-04T12:14:35.148Z","update_time":"$D2025-05-14T11:53:37.083Z","view_time":null,"first_public_time":"$D2019-01-10T23:13:50.265Z","fork":{"id":"2331ea7cae3cdc98","slug":"t-sne","title":"Abrindo a caixa preta do t-SNE","owner":{"id":"aa1870a7aeb4caa2","login":"robstelling","name":"Roberto Stelling"}},"stars":10,"starred":false,"owner":{"type":"team","id":"aa1870a7aeb4caa2","login":"robstelling","name":"Roberto Stelling","avatar_url":"https://avatars-next.observableusercontent.com/6229413ee5337674416dd44206b49ea53512f6fd7d1275a839bb8250335ed81e","tier":"starter_2024"},"version":7936,"publish_version":7936,"role":null,"authored":false,"authors":[{"type":"individual","id":"8dbfddb7a124d503","login":"robstelling","name":"Roberto Stelling","avatar_url":"https://avatars-next.observableusercontent.com/6229413ee5337674416dd44206b49ea53512f6fd7d1275a839bb8250335ed81e","tier":null}],"members":[{"type":"individual","id":"8dbfddb7a124d503","login":"robstelling","name":"Roberto Stelling","avatar_url":"https://avatars-next.observableusercontent.com/6229413ee5337674416dd44206b49ea53512f6fd7d1275a839bb8250335ed81e","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"title":"Opening the *t*-SNE black box","cells":[{"id":7073,"value":"md`# Opening the *t*-SNE black box\nAn in depth view of *t*-SNE, with algorithm breakdown, implementation and a toy problem playground.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7179,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7196,"value":"md `# Topics\nWhat are you going to see here?
\n\\`Note\\`: you can click on the links below to go directly to the corresponding section\n- A brief discussion of the high dimension data visualization problem\n- Brief *t*-SNE introduction\n- Normal and Student *t* distributions\n- Description of the *t*-SNE algorithm as given by the original paper²\n- A more detailed description of *t*-SNE algorithm, that was used to implement the code in this notebook\n- The *t*-SNE algorithm in baby steps\n- A *t*-SNE playground, where you can:\n - Adjust the algorithm hyperparameters\n - Play with a toy problem\n - See an animation of the algorithm while it is being run`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":43,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":232,"value":"md `# Is there an *optimal solution* to visualize high dimensional data?\nBefore we move on, it is important to understand that there isn't an optimal solution to this problem. To develop this intuition, let's investigate a few alternatives to reduce a couple of artificial datasets from 2 dimensions to 1 dimension.\n\nHow can we reduce data from two (*x* and *y*) dimensions to one (*x*) dimension? Let's try a few alternatives (from naïve to more complex aproaches):\n\n1. Flatten the data to the *x* axis\n2. Flatten the data to the *y* axis\n3. *\"Figure out\"* the ideal projection of the data\n4. Apply a dimensionality reduction or visualization algorithm to the dataset, like SVG, PCA or *t*-SNE\n\nIn the following few examples we will see what happens when we \"experiment with\" 1, 2 and 3. Later we will look into *t*-SNE`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":402,"value":"md `# Simple examples\n### Mapping *2D* data to *1D*\nIn the following examples, we will project the data from *2* dimensions to *1* dimension to each one of the *x* e *y* axes.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":304,"value":"grafico_simples = vegalite({\n width: Math.min(400, width),\n height: 400,\n data: points,\n mark: {type: \"circle\", size: markSize, opacity: opacity},\n encoding: {\n x: {field: \"x\", type: \"quantitative\"},\n y: {field: \"y\", type: \"quantitative\"},\n color: {field: \"Cluster\", type: \"nominal\", scale:{scheme: colorScheme}},\n }\n})\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":394,"value":"md`# Projecting the points to the *X* axis`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":357,"value":"vegalite({\n width: Math.min(400, width),\n data: points,\n mark: {type: \"circle\", size: markSize, opacity: opacity},\n encoding: {\n x: {field: \"x\", type: \"quantitative\"},\n color: {field: \"Cluster\", type: \"nominal\", scale: {scheme: colorScheme}}\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":434,"value":"md `Clusters *c* and *d* are reasonably, but not optimally, separated but *a* e *b* are mixed up.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":396,"value":"md `# Projecting the points to the *Y* axis`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":964,"value":"md `and rotating to the horizontal`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":364,"value":"vegalite({\n width: Math.min(400, width),\n data: points,\n mark: {type: \"circle\", size: markSize, opacity: opacity},\n encoding: {\n x: {field: \"y\", type: \"quantitative\"},\n color: {field: \"Cluster\", type: \"nominal\", scale: {scheme: colorScheme}}\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":436,"value":"md `The projected points to the **y** axis are mixed up in two new clusters formed by, clusters *a* e *d* and clusters *b* and *c*`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":450,"value":"md `# *\"Ideal\"* projection\nIn an *\"ideal world\"* we would like to see the original points reduced from two dimensions to one dimension in a projection similiar to the one below, where each one of the original clusters is properly represented in 1D:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":448,"value":"vegalite({\n width: Math.min(400, width),\n data: idealLinear,\n mark: {type: \"circle\", size: markSize, opacity: opacity},\n encoding: {\n x: {field: \"x\", type: \"quantitative\"},\n color: {field: \"Cluster\", type: \"nominal\", scale: {scheme: colorScheme}}\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":559,"value":"md `# Half moon dataset`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":561,"value":"vegalite(halfMoonChart)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":640,"value":"md `## Projecting over the *x* axis`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":566,"value":"vegalite({\n width: Math.min(500, width),\n data: {values: halfMoon},\n mark: {type: \"circle\", size: markSize, opacity: opacity},\n encoding: {\n x: {field: \"x\", type: \"quantitative\"},\n color: {field: \"label\", type: \"nominal\", scale: {scheme: colorScheme}, title: \"Cluster\"},\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":641,"value":"md `## Projecting over the *y* axis`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7234,"value":"vegalite({\n width: Math.min(500, width),\n data: {values: halfMoon},\n mark: {type: \"circle\", size: markSize, opacity: opacity},\n encoding: {\n x: {field: \"y\", type: \"quantitative\"},\n color: {field: \"label\", type: \"nominal\", scale: {scheme: colorScheme}, title: \"Cluster\"},\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":636,"value":"md `## *\"Ideal\"* projection\nTo map *these particular datapoints* from *2D* to *1D* we can shift all red points a bit to the left, all blue points a bit to the right and then project them on the *x* axis`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":584,"value":"// We massage the data a little bit to \"fake unfold\" the dataset...\nfakeCluster = halfMoon.map(p => {return {x:(p.x+p.label)*(p.label+1.7), label:p.label}})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":619,"value":"vegalite({\n width: Math.min(500, width),\n data: {values: fakeCluster},\n mark: {type: \"circle\", size: markSize, opacity: opacity},\n encoding: {\n x: {field: \"x\", type: \"quantitative\"},\n color: {field: \"label\", type: \"nominal\", scale: {scheme: colorScheme}, title: \"Cluster\"},\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":582,"value":"md `## Circles\n*Divine* algorithm: How to project a circular dataset to 1D?`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":577,"value":"vegalite({\n width: Math.min(500, width),\n height : 500,\n data: {values: circles},\n mark: {type: \"circle\", size: markSize, opacity: opacity},\n encoding: {\n x: {field: \"x\", type: \"quantitative\"},\n y: {field: \"y\", type: \"quantitative\"},\n color: {field: \"label\", type: \"nominal\", scale: {\"scheme\": colorScheme}, title: \"Cluster\"},\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4795,"value":"md`### Radial projection!\nIn each of the previous examples there was a simple and suggestive way to map the points from *2D* to *1D* in a way that they would be separable, but the methods worked because *we knew* how the data was organized on the original *2D* space.\n\nBut how would we choose what transformation to apply to unknown data with 10, 100 or 1000 dimensions?`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3883,"value":"radialMap = {\n // pointsDistances is a vector with the distances of each point to the origin (0,0)\n var pointsDistances = circles.map((p) => ({x:dist(p, {x:0, y:0}), label:p.label}));\n // mean of the distances\n var mean = pointsDistances.reduce((sum, point) => sum + point.x, 0)/circles.length\n // We return a map of each distance minus the mean (so the sample is \"centralized\")\n return pointsDistances.map((p) => ({x: p.x-mean,label:p.label}));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3873,"value":"vegalite({\n width: Math.min(500, width),\n data: {values: radialMap},\n mark: {type: \"circle\", size: markSize, opacity: opacity},\n encoding: {\n x: {field: \"x\", type: \"quantitative\"},\n color: {field: \"label\", type: \"nominal\", scale: {scheme: colorScheme}, title: \"Cluster\"},\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":545,"value":"md `# Also, it is not allways possible to map the points to a lower space and separate data clusters`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1169,"value":"md `### For example, miles per gallon, power and country of origin on the [*cars*](https://vega.github.io/vega-lite/data/cars.json) dataset\nIf the clusters are not separable on the high dimensions, they won't be separable on inferior dimensions (although they may be separable in dimensions higher than the original!). This points to the idea of intrinsic dimensionality, meaning the mininum dimensions necessary to faithfully *\"portrait\"* the data and still separate in the intended clusters. If the data intrinsic dimension is higher than *2D* or *3D*, no mapping will fully express its content.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":499,"value":"vegalite({\n width: Math.min(400, width),\n height : 400,\n data: {values: cars},\n mark: {type: \"circle\", size: markSize, opacity: opacity},\n encoding: {\n x: {field: \"Horsepower\", type: \"quantitative\", title: \"Horse-Power\"},\n y: {field: \"Miles_per_Gallon\", type: \"quantitative\", title: \"Miles/gallon\"},\n color: {field: \"Origin\", type: \"nominal\", scale: {scheme: colorScheme}, title: \"Origin\"}\n }\n})\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7881,"value":"html`

\nt-SNE applied to MNIST (Laurens van der Maaten³)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7935,"value":"md`*t*-SNE is not garanteed to converge but still produces very good results as, for example, the mapping of the MNIST dataset from 784 dimensions to just 2 (or 3, if we include the color and mark channels - that represent the same information: the digit label) dimensions. The graph below was generated with Tensorflow.js¹⁷`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4800,"value":"md`${chart}t-SNE applied to the MNIST dataset (Bostock²¹)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4805,"value":"normalStudent = md `## A brief review of Normal and Student *t*¹⁸ distributions`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1393,"value":"md `### Playing with the parameters of normal density curve`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1155,"value":"vegalite({\n width: Math.min(600, width),\n height: 300,\n layer: [\n {\n title: \"Density curve of a normal distribution\",\n data: {values: pointsNormal(-6, +10, 0.01, 1, 0)},\n mark: \"line\",\n encoding: {\n x: {field: \"x\", type: \"quantitative\"},\n y: {field: \"y\", type: \"quantitative\", title: \"φ(x)\"},\n color: {value:\"steelblue\"}\n }\n },\n {\n data: {values: pointsNormal(-6, 10, 0.01, Math.sqrt(var_2), mean)},\n mark: {type: \"line\"},\n encoding: {\n x: {field: \"x\", type: \"quantitative\"},\n y: {field: \"y\", type: \"quantitative\"},\n color: {value: \"red\"}\n }\n }\n ]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1243,"value":"viewof var_2 = slider({\n min: 0.01, \n max: 16, \n step: 0.01,\n value: 1,\n description: \"Variance [0.1 to 16]\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1255,"value":"viewof mean = slider({\n min: -6, \n max: 10, \n step: 0.01,\n value: 0.0,\n description: \"Mean [-6 to 10]\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4812,"value":"md `Change the variance and mean of the curve above.\n\nSuppose that the red curve represents the hight of the the adult population (a blue curve will be kept as a reference). If you change the mean to 6 (meaning, for example, that the adult population is, in average, 6 ft. tall) and you keep the variance as 1, then the resulting curve suggests that we can find lots of people over 7, 8 and 9 ft. tall! To correct that we need to *reduce* the variance to around 0.15, then the curve will be closer to a real represetation of an adult population averaging 6 ft. tall.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":713,"value":"md `### Comparing normal and Student *t* distrubutions`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":892,"value":"vegalite({\n width: Math.min(600, width),\n height: 300,\n layer: [\n {\n title: \"Normal (red) and Studend-t (blue)\",\n data: {values: pointsStudent(-interval, interval, 0.01, 1, 1)},\n mark: {type: \"line\"},\n encoding: {\n x: {field: \"x\", type: \"quantitative\"},\n y: {field: \"y\", type: \"quantitative\", title:\"φ(x)\"}\n }\n },\n {\n data: {values: pointsNormal(-interval, interval, 0.01, Math.sqrt(var2), 0)},\n mark: {type: \"line\"},\n encoding: {\n x: {field: \"x\", type: \"quantitative\"},\n y: {field: \"y\", type: \"quantitative\"},\n color: {value: \"red\"}\n }\n }\n ]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1324,"value":"viewof var2 = slider({\n min: 0.01,\n max: 9,\n value: 1,\n step: 0.01,\n description: \"Normal distribution variance\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2257,"value":"viewof interval = slider({\n min: 1,\n max: 100,\n value: 6,\n step: 1,\n description: \"Interval\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4810,"value":"md`A Student *t* distribution is \"*shorter*\" and have a \"*longer tail*\" than a normal distribution with the same variance. Change the variance of the normal curve above to see how it compares with the Student *t* distribution.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3967,"value":"md`### Degrees of freedom and on a Student *t* distribution`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":801,"value":"vegalite({\n width: Math.min(600, width),\n height: 300,\n data: {values: pointsNormalStudent(-interval, interval, 0.01, Math.sqrt(variance), 0, degreesFreedom)},\n mark: \"line\",\n title: \"Normal and Student t distributions\",\n encoding: {\n x: {field: \"x\", type: \"quantitative\"},\n y: {field: \"y\", type: \"quantitative\", title: \"φ(x)\"},\n color: {field: \"Curva\", type:\"nominal\", scale: {scheme: colorScheme}, title: \"Distribution\"}\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1540,"value":"viewof degreesFreedom = slider({\n min: 1,\n max: 100,\n value: 1,\n step: 1,\n description: \"Degrees of freedom\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2233,"value":"viewof variance = slider({\n min: 0.1,\n max: 9,\n value: 1,\n step: 0.1,\n description: \"Variance\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4808,"value":"md`A Student *t* distribution is actually a \"*combination*\" of infinite normal curves. With one degree of liberty it is shorter and has a longer tail than a normal curve with the same variance. If you increase the degrees of freedom of a Student *t* distribution it converges to the corresponding normal distribution, as you can observe changing the parameters of the graph above.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4816,"value":"md`## Looking back at *t*-SNE\nFirst, lets review the *t*-SNE algorithm as described in the original paper².`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1741,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1802,"value":"md `## Equations\n[\\`Equation 1\\`] High dimension affinities
\n${tex.block`${eq1}`}\n
[\\`Equation 2\\`] Kullback-Leibler divergence
\n${tex.block`${eq2}`}\nequivalent to:
\n${tex.block`${eq6}`}\n
[\\`Equation 3\\`] Low-dimension affitities
\n${tex.block`${eq3}`}\n
[\\`Equation 4\\`] Low dimension adjustment with Student *t* distribution with 1 degree of freedom(*Cauchy* distribution)
\n${tex.block`${eq4}`}\n
[\\`Equation 5\\`] Gradient of the Kullback-Leibler divergence [\\`Equation 2\\`] between high dimension affinities *P* and low dimension affinities *Q*
\n${tex.block`${eq5}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":976,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1144,"value":"babySteps = md `# *t*-SNE baby steps`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":940,"value":"md `## From distances to affinities\nLets aply *t*-SNE to the simple *2D* dataset we saw at the introduction.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":943,"value":"vegalite(original)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2875,"value":"md`To convert distances to probabilities, we can imagine each point in the original space as a center of a distribution (Normal/Gaussian or any other of your choosing) and use the distance between the chosen point and every other point as the probability of a link between these points. In principle, the smaller the distance, the bigger the probability of a link. In a way we are *defining the neighbourhood between points*. \n\nFor example, in the dataset above, the distance between ${tex`p_0`} and ${tex`p_1`} is given by the distance matrix, on \\`distances[0][1]\\` and equals ${tex`${distances[0][1]}`}. In a normal distribution, with average ${tex`0`} and variance ${tex`1`}, this distance would correspond to ${tex.block`distances[0][1] = ${distances[0][1]}\\rightarrow P_{01} = ${normal(distances[0][1], 1,0)}`}\nBelow we can see the distances and probabilities between a few other points with a normal distribution with ${tex`\\mu = 0`} e ${tex`\\sigma^2 = 1`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2660,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2684,"value":"md `\n\\`distances[0][1] = \\` ${distances[0][1]} - ${tex`P_{01} = P(${distances[0][1]})`} = ${normal(distances[0][1], 1,0)}
\n\\`distances[0][2] = \\` ${distances[0][2]} - ${tex`P_{02} = P(${distances[0][2]})`} = ${normal(distances[0][2], 1,0)}
\n\\`distances[0][3] = \\` ${distances[0][3]} - ${tex`P_{03} = P(${distances[0][3]})`} = ${normal(distances[0][3], 1,0)}
\n\\`distances[0][4] = \\` ${distances[0][4]} - ${tex`P_{04} = P(${distances[0][4]})`} = ${normal(distances[0][4], 1,0)}
\n\\`distances[0][5] = \\` ${distances[0][5]} - ${tex`P_{05} = P(${distances[0][5]})`} = ${normal(distances[0][5], 1,0)}
\n\\`distances[5][0] = \\` ${distances[5][0]} - ${tex`P_{50} = P(${distances[5][0]})`} = ${normal(distances[5][0], 1.2,0)}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2901,"value":"md`The same points from the previous example are shown below with a Student *t* distribution with ${tex`\\mu = 0`} e ${tex`\\sigma^2 = 1`} and one degree of freedom.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2093,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1028,"value":"md `\n\\`distances[0][1] = \\` ${distances[0][1]} - ${tex`P_{01} = P(${distances[0][1]})`} = ${student(distances[0][1], 1)}
\n\\`distances[0][2] = \\` ${distances[0][2]} - ${tex`P_{02} = P(${distances[0][2]})`} = ${student(distances[0][2], 1)}
\n\\`distances[0][3] = \\` ${distances[0][3]} - ${tex`P_{03} = P(${distances[0][3]})`} = ${student(distances[0][3], 1)}
\n\\`distances[0][4] = \\` ${distances[0][4]} - ${tex`P_{04} = P(${distances[0][4]})`} = ${student(distances[0][4], 1)}
\n\\`distances[0][5] = \\` ${distances[0][5]} - ${tex`P_{05} = P(${distances[0][5]})`} = ${student(distances[0][5], 1)}
\n\\`distances[5][0] = \\` ${distances[5][0]} - ${tex`P_{50} = P(${distances[5][0]})`} = ${student(distances[5][0], 1.2)}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2751,"value":"md`## Distances matrix using ${metricNameTex(metric)} metric`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1086,"value":"pt(math.matrix(math.reshape(dFlat.map(y => y<=zero?0.0:+y.toFixed(3)), [16,16])), \"\\\\footnotesize\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4786,"value":"viewof metric = radio({\n title: 'Distance metric',\n description: 'Choose the distance metric',\n options: [\n { label: metricName(0), value: 0 },\n { label: metricName(1), value: 1 },\n { label: metricName(2), value: 2 },\n { label: metricName(3), value: 3 } \n ],\n value: 0\n\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4958,"value":"md`The ${metricNameTex(metric)} distance between the points ${math.matrix(pts[0])} and ${math.matrix(pts[1])} is ${computeDistance(pts[0], pts[1])}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4960,"value":"pts = [[0, 0], [-1, -1]]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1985,"value":"md`The Euclidean, or ${tex`L^2`}, distance between the points is computed for each pair of points on the original high dimensional space and the probability that a point ${tex`x_i`} is \"close\" to a point ${tex`x_j`}, denoted as ${tex`p_{j|i}`} is given by the \\`[Equation 1]\\` below, using a Gaussian distribution with a different variance (${tex`\\sigma^2`}) for each point in space. ${tex.block`${eq1}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1149,"value":"md `The denominator acts as a *\"normalization\"* of the probabilities around each ${tex`x_i`}. This way, bigger distances around locations not too dense are similar to smaller distances on denser locations. The value for each variance ${tex`\\sigma^2_i`} is determined by a binary search using the ${tex`\\log_2`} of the hyperparameter *perplexity* (\\`Perp\\`), given by the user. We will delve into the binary search and \\`Perp\\` later on the road.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2946,"value":"md`## From distances to probabilities, with distributions and variances`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2944,"value":"vegalite(original)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4686,"value":"md`### Affinities matrix, same variance for all points, using ${metricNameTex(metric)} metric.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2714,"value":"pt(math.matrix(math.reshape(pFlat.map(x => +x.toFixed(3)), [16,16])))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2769,"value":"viewof s2 = slider({\n title: 'Variance',\n min: 0.1,\n max: 9,\n step: 0.1,\n value: 1,\n description: \"Adjust the variance for all points and see how the values change\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2468,"value":"md`# Perplexity\nPerplexity (${tex`Perp`}) is a hyperparameter that is used to adjust the variances of the affinities around each point in the original space. We can understand preplexity as a measure of entropy of affinities (${tex`P`}) between the points on the original high dimensional space.\n\nThe mapped space, in low dimensions, will have its affinities (${tex`Q`}) computed over a Student *t* distribution with the same variance for all points, as per \\`[Equation 3]\\`. ${tex.block`${eq3}`}\n\n\\`Note\\`: \\`Perp\\` is used to adjust the affinities in the high dimensional space, not in the low dimensional map.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2475,"value":"md`The perplexity on each point is calculated as\n${tex.block`\\log_2(Perp(p_i)) = entropy(p_i) = \\sum_{j\\ne i} -p_{j|i} \\log_2(p_{j|i})`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2624,"value":"md`#### Entropy\nThe desired entropy is defined by the hyperparameter perplexity [\\`Perp\\` = ${Perp_display}]: ${tex.block`entropy = \\log_2(Perp) = ${+Math.log2(Perp_display).toFixed(4)}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3505,"value":"md``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2580,"value":"function computeEntropy(probabilities){\n // Calcula a entropia de um vetor de probabilidades\n return probabilities.reduce((sum, p) => sum - (p<=zero?0:p*Math.log2(p)), 0)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2790,"value":"md `On the example above, with all variances equal to ${+(s2).toFixed(3)}, we would have ${tex`entropy = ${+(computeEntropy(pFlat)/16).toFixed(4)}`} and ${tex`perplexity = ${Math.exp(computeEntropy(pFlat)/16).toFixed(4)}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2967,"value":"md`To find the right variance on each point we have to perform a binary search, looking for a variance value that will be as close as possible to the desired entropy, according to the hyperparameter \\`Perp\\`.\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2993,"value":"md`## Binary search of high dimension variances`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3167,"value":"function varianceBinarySearch(points, i, entropy, error=1e-6, steps=40) {\n function recursiveBinarySearch(variance, lowerBound, upperBound) {\n const probabilities = computeP_i(points, i, variance),\n currentEntropy = computeEntropy(probabilities);\n \n if (steps-- <= 1 || Math.abs(currentEntropy - entropy) <= error)\n return probabilities;\n if (currentEntropy > entropy)\n return recursiveBinarySearch((lowerBound+variance)/2, lowerBound, variance);\n else\n return recursiveBinarySearch((variance+upperBound)/2, variance, upperBound);\n }\n\n const MINVAR = 0.01,\n MAXVAR = 50;\n return recursiveBinarySearch((MINVAR+MAXVAR)/2, MINVAR, MAXVAR);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3509,"value":"function adjustVariances(points, entropy, error, steps) {\n let size = points.length,\n p = [];\n for (let i = 0; i < size; i++)\n p = p.concat(varianceBinarySearch(points, i, entropy, error, steps))\n var total = p.reduce((sum, current)=>sum+current,0)\n return p.map((x)=>x/total);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3103,"value":"pt(math.matrix(math.reshape(pVariancesDisplay.map(x => +x.toFixed(3)), [16,16])))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6374,"value":"viewof Perp_display = slider({\n title: 'Perplexity',\n min: 1,\n max: 100,\n step: 0.5,\n value: 10,\n description: \"Adjust perplexity hyperparameter\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3109,"value":"md`Resulting entropy (computed from data) = ${computeEntropy(pVariancesDisplay)}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2999,"value":"md`${tex`entropy = \\log_2(Perp) = ${Math.log2(Perp_display)}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3139,"value":"md`# Making the affinities matrix symmetric\nThe resulting affinities matrix is asymmetric, to make it symmetric, so that ${tex.block`P_{i|j} = P_{j|i}`} we need to compute: ${tex.block`p_{ij} = \\frac{P_{j|i}+P_{i|j}}{2}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6370,"value":"pFinalDisplay = {\n var length = pVariancesDisplay.length;\n var m = Math.sqrt(length);\n var result = new Array(pVariancesDisplay.length),\n probMedia;\n for (let i=0; i +x.toFixed(3)), [16,16])))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3158,"value":"md`# Mapping the low dimension points\nWith the high dimensional affinities matrix in hand (${tex`P`}), we need to generate lower dimension points, compute their affinities matrix (${tex`Q`}) and adjust the generated points with a gradient descent. The first batch of low dimensional points are *\"randomically\"* generated, with the desired number of dimensions. In our example we will generate ${Math.sqrt(dFlat.length)} poins in ${tex`\\mathbb{R}^${dimensions}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5253,"value":"md`## Initial projection from ${tex`\\mathbb{R}^2`} to ${tex`\\mathbb{R}^${dimensions}`}\n\nWith the affinities matrix in high dimensions, we must randomically generate the first set of low dimension points mapping ${tex`\\mathbb{R}^2 \\rightarrow \\mathbb{R}^${dimensions}`}, as per our toy example. The paper authors recommend points distributed over a gaussian with ${tex `\\mu = 0`} and ${tex`\\sigma^2 = 10^{-4}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3351,"value":"vegalite(original)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5244,"value":"viewof dimensions = radio({\n title: 'Map dimensions',\n description: 'Choose the number of dimensions to map the points, the graph below should change accordingly',\n options: [\n {label:'One', value:1},\n {label:'Two', value:2}\n ],\n value: 1\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4531,"value":"md`### Initial projection to ${tex`\\mathbb{R}^${dimensions}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3311,"value":"vegalite([fr1(yDisplay),fr2(yDisplay)][dimensions-1])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4138,"value":"viewof guessType = radio({\n title: 'Type of the initial projection',\n description: 'Choose how to generate the initial projection points, see how the distance matrix is affected',\n options: [\n {label:'Random', value:'random'},\n {label:'Compressed random', value:'compressed'},\n {label:'\"Ideal\"', value:'ideal'}\n ],\n value: 'random'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3497,"value":"md`### ${metricNameTex(metric)} distance between generated points`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3377,"value":"pt(math.matrix(math.reshape(distQ.map(y=>y<=zero?0:+y.toFixed(digits)), [16,16])), \"\\\\scriptsize\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5102,"value":"distQ = distancesMatrix(yFlat);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3500,"value":"md`## Computing low dimension affinities\nThe low dimension affinities are computed over a Student *t* distribution, with 1 degree of freedom and variance equal to 1.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5148,"value":"tex.block`${eq3}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4772,"value":" function computeQ(y) {\n // Computes affinities of the points on the mapped space, with a Student t kernel\n // y: Points on the mapped space\n // N: number of points\n // Q: probabilities\n var N = y.length;\n var Q = array(N*N, 1e-100);\n var soma = 0.0;\n for(var i=0; ix>1e-100?x/soma:x);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3407,"value":"pt(math.matrix(math.reshape(computeQ(yFlat).map(x => +x.toFixed(4)), [16,16])), '\\\\footnotesize')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3584,"value":"md`# Cost function\nThe cost function should measure the error, or divergence, between the affinities in high dimensions and the affinities in low dimensions. To compare the relative entropies between the probabilities the algorithm uses the asymmetric **Kullback-Leibler Divergence** (KL). The bigger the divergence, the bigger the difference between the probabilities. If the divergence is 0, the probabilities are identical.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1587,"value":"md `## Kullback-Leibler Divergence\nThe Kullback-Leibler Divergence is given by \\`[Equation 2]\\` ${tex.block`${eq2}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3597,"value":"md`In our example, the cost of the distributions ${tex`P`} and initial guess ${tex`Q`} is: ${tex`${KLD(pFinal, computeQ(yFlat)).toFixed(5)}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3613,"value":"function KLD(prob1, prob2) {\n return prob1.reduce((sum, value, index) => sum + (value==0?0:KL(value, prob2[index])))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2196,"value":"function KL(p, q){\n return p == 0 ? 0 : q == 0 ? Infinity : p * Math.log(p/q)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5161,"value":"function cost(y, P) {\n // Cost between points and a distribution\n // y: points in the mapped space\n // P: distribution in the high dimensional space\n var Q = computeQ(y);\n const N = y.length;\n var costSum = 0;\n for (var i=0; iStart button`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6244,"value":"vegalite(thumbnail)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7761,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6184,"value":"viewof reset = {\n const form = html`

Select the number of interactions and click