Exploring t-SNE for Dimensionality Reduction in Machine Learning

Introduction

Embark on a journey into non-linear dimensionality reduction, with a specific focus on t-Distributed Stochastic Neighbor Embedding (t-SNE). Our goal is to understand the theory behind t-SNE and apply it using Scikit-learn's TSNE . This journey will take us through an understanding of the difference between linear and non-linear dimensionality reduction, a grasp of the core concepts of t-SNE, an implementation of t-SNE using Scikit-learn's TSNE, and a discussion of potential pitfalls of t-SNE.

Linear vs. Non-Linear Dimensionality Reduction

Dimensionality reduction is a pragmatic exercise which seeks to condense the number of random variables under consideration, thus obtaining a set of principal variables. By familiarizing ourselves with the dimension, we can select the technique that best suits our needs. Imagine having a dataset that contains a person's height in inches and centimeters. These two measurements convey the same information, so one can be removed. This is an example of linear dimensionality reduction. Unlike PCA, a popular linear technique, non-linear techniques like t-SNE adopt a different approach, capturing complex relationships by preserving distances and separations, irrespective of the dimension space.

Understanding t-SNE: High-dimensional Space Calculations

p_{j|i} = \frac{e^{-(\|x_{i}-x_{j}\|^{2} /2\sigma _{i}^{2})}}{\sum_{k \neq i} e^{-(\|x_{i}-x_{k}\|^{2}/2\sigma _{i}^{2})}}

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Understanding t-SNE: Low-dimensional Space Calculations

In the lower-dimensional map, t-SNE employs t-distributions. These distributions, which are heavier-tailed, favor more effective modeling of dissimilarities. The joint probabilities in the low-dimensional space are defined as:

$q_{ij} = \frac{(1+||y_{i}-y_{j}||^{2})^{-1}}{\sum_{k \neq l}(1+||y_{k}-y_{l}||^{2})^{-1}}$

Here, $q_{ij}$ is the probability of $y_i$ being a neighbor of $y_j$ . t-SNE minimizes the divergence between the two distributions with respect to the locations of points (y) in the map. Here are the steps involved in the t-SNE algorithm:

Compute the pairwise similarities in the high-dimensional space using Gaussian joint probabilities using the formula for $p_{j|i}$ .
Compute the pairwise similarities in the low-dimensional space using t-distributions using the formula for $q_{ij}$ . Note that the t-distribution has a heavier tail than the Gaussian distribution and is more robust to outliers — It helps to avoid clumping of points.
Minimize the divergence between the two distributions by adjusting the locations of the points in the low-dimensional space using gradient descent.
Repeat the process until the distributions are similar.

t-SNE uses Kullback-Leibler divergence to measure the difference between the two distributions. Kullback-Leibler divergence is a measure of how one probability distribution diverges from a second, expected probability distribution. The cost function is defined as follows:

$C = KL(P||Q) = \sum_{i} \sum_{j} p_{ij} \log \frac{p_{ij}}{q_{ij}}$

Here, $P$ is the joint probability distribution in the high-dimensional space, $Q$ is the joint probability distribution in the low-dimensional space, and $C$ is the cost function. The goal is to minimize the cost function by adjusting the locations of the points in the low-dimensional space.

Introduction

Linear vs. Non-Linear Dimensionality Reduction

Understanding t-SNE: High-dimensional Space Calculations

Join the 1M+ learners on CodeSignal

Understanding t-SNE: Low-dimensional Space Calculations

Implementing t-SNE: Python Implementation

Python Sample code for t-SNE and Analysis

Pitfalls when Using t-SNE

Lesson Summary and Practice