# Getting over High-Dimensionality: How Multidimensional Projection Methods Can Assist Data Science
## 4 Multidimensional Projection Approaches and Domains
### Stochastic Neighbor Embedding  
[PERSON] and [PERSON] [65] developed the Stochastic Neighbor Embedding (SNE), a nonlinear statistical technique based on the minimization of the Kullback-Leibler (KL) divergence [66] that takes probabilities distributions to represent dissimilarities from original and projected spaces. SNE models two Gaussian distributions, one \(P\) over the original \(m\)-dimensional space and another \(Q\) over the projected \(p\)-dimensional space (initialized with random positions). In this scenario, pairs of instances with small Euclidean distances are associated with high probability values, and pairs with large distances have low probabilities.  
Equation (20) defines the conditional probability \(p_{i|j}\) between each par of instances \(x_{i}\) and \(x_{j}\), being \(\delta\) the Euclidean distance and \(\sigma_{i}\) related to the size of the \(x_{i}\) neighborhood, being smaller in dense regions and bigger in the sparse ones [67]. The best value of \(\sigma_{i}\) is encountered by a binary search in the [1, _perplexity_] range in such a way that the Shannon entropy of \(p\) probabilities reaches \(\log_{2}perplexity\), being _perplexity_ frequently defined by the user in the [50; 50] range [65]. Meanwhile, Equation (21) defines probabilities in \(p\)-dimensional space, being \(\sigma_{i}=1/\sqrt{2}\) without generality loss. In both spaces, self-probabilities are null, i.e., \(p_{i|i}=q_{i|i}=0\).  
\[p_{i|j}=\frac{\exp(-\delta(x_{i},x_{j})^{2}/2\sigma_{i}^{2})}{\sum_{k\
eq i} \exp(-\delta(x_{i},x_{k})^{2}/2\sigma_{i}^{2})} \tag{20}\]  
\[q_{i|j}=\frac{\exp(-\left\|y_{i}-y_{j}\right\|^{2})}{\sum_{k\
eq i}\exp(-\left\| y_{i}-y_{k}\right\|^{2})} \tag{21}\]  
KL divergence between probability distributions \(P_{i}\) and \(Q_{i}\) is minimized by the application of the gradient descent algorithm [68] to discover the best values of \(p\)-dimensional coordinates [67] such as in Equation (22).  
\[\arg\min_{y}\sum_{i}\text{KL}(P_{i}||Q_{i})=\sum_{i}\sum_{j}p_{i|j}\log\frac{p _{i|j}}{q_{i|j}} \tag{22}\]  
This optimization process can be interpreted as a system with attraction/repulsion forces between \(y_{i}\) and all \(y_{j}\) points because it approximates similar points and segregates the dissimilar ones.  
Sadly, KL divergence generates space distortions due to its asymmetric characteristics and is sensitive to the crowding problem [28]. These issues were mitigated by [PERSON] and [PERSON] [28] with the introduction of _t-Distributed Stochastic Neighbor Embedding_ (t-SNE), which applies to the original space a symmetrized version of conditional probabilities, such as  
\[p_{ij}=p_{ji}=\frac{p_{j|i}+p_{i|j}}{2n} \tag{23}\]  
being \(p_{ii}=0\). In the projected space, the authors replaced the Gaussian distribution with the t-Student distribution because the latter is simpler and faster to compute while maintaining similarities with the former distribution [28]. In addition, at the projected space is defined \(q_{ij}=q_{ji}\) and \(q_{ii}=0\).  
Both SNE and t-SNE can represent global structures and reveal local data characteristics, preserving some levels of data neighborhood. The t-SNE and other similar techniques are robust against norm concentration, a typical characteristic of the curse of dimensionality [7], because of the shift-invariant similarities [69]. Although attaining good results if compared to other methods, in t-SNE projections, the observed distance between clusters is unreliable and sensitive to parametrization (perplexity parameter) [70], which can generate a misleading effect of cluster distance and shape resulting from the local nature of optimization and how hyperparameters are set up [8]. Nonetheless, t-SNE presents computational complexity equal to \(O(n^{2})\), which impairs practical applications, but [PERSON] [67] developed an accelerated version that reaches \(O(n\log n)\) through approximations.