Improving the Effectiveness and Efficiency of Stochastic Neighbour Embedding with Isolation Kernel (Extended Abstract)

1 Introduction andMotivation

t-SNE [Maaten and Hinton, 2008] has been a successful and popular dimensionality reduction method for visualisation. It aims to project high-dimensional datasets into lowerdimensional spaces while preserving the similarities between data points, as measured by the KL divergence.

The original SNE [Hinton and Roweis, 2003] employs a Gaussian kernel to measure similarity in both high and lowdimensional spaces. t-SNE replaces the Gaussian kernel with the distance-based similarity (1 + dij)2 (where dij is the distance between instances i and j) in low-dimensional space, while retaining the Gaussian kernel for high-dimensional space.

When using the Gaussian kernel, t-SNE has to fine-tune a bandwidth of the Gaussian kernel centred at each point in a given dataset because Gaussian kernel is independent of data distribution. In other words, t-SNE must determine n bandwidths for a dataset of n points.

The bandwidth determination process in t-SNE uses a heuristic search with a single global parameter called perplexity such that the Shannon entropy is fixed for all probability distributions at all points while adapting each bandwidth to the local density of the dataset. As the perplexity can be interpreted as a smooth measure of the effective number of neighbours [Maaten and Hinton, 2008], the method can be interpreted as using a user-specified number of nearest neighbours (aka kNN) in order to determine the n bandwidths. Whilst there is a single external parameter perplexity, a bandwidth setting must be optimised for each data point internally.

∗This work is originally published in the Journal of Artificial Intelligence Research, 71:667-695, August 2021.

This becomes the first obstacle in dealing with large datasets due to the massive computational cost of the bandwidth search process. In addition, the point-based bandwidth is also the cause of misrepresentation in high-dimensional space under some conditions.

To date, the common practice is still using Gaussian kernel in t-SNE. Yet, sound and workable solutions to its drawbacks mentioned above are not available.

The contributions of this paper are:

1. Uncovering two deficiencies due to the use of Gaussian kernel. First, the point-based-bandwidth Gaussian kernel often creates misrepresented structure(s) that do not exist in high-dimensional space under some conditions. Second, the use of the data-independent kernel requires t-SNE to determine n bandwidths for a dataset of n points, despite the fact that a user needs to set one parameter only. This becomes one key obstacle in dealing with large datasets.
2. Revealing the advantages of using a partition-based datadependent kernel in t-SNE. First, this kernel enables the true structure(s) in the high-dimensional space to be represented correctly under the same condition mentioned above. Second, the data-dependent similarity is set with a single parameter only; this allows it to be computed more efficiently. These two advantages enable t-SNE to deal with large-scale datasets without trading off accuracy with faster runtime, without resorting to approximation methods.
3. Proposing an improvement to t-SNE by simply replacing the data-independent kernel with a data-dependent kernel, leaving the rest of the procedure unchanged.
4. Verifying the effectiveness and efficiency of the datadependent kernel in t-SNE.

While many improved methods have been proposed since the introduction of SNE (e.g., [Cook et al., 2007; Yang et al., 2009; Venna et al., 2010; Van Der Maaten and Weinberger, 2012; Lee et al., 2013; Van Der Maaten, 2014; Linderman and Steinerberger, 2017; Shaham and Steinerberger, 2017; Arora et al., 2018; Linderman et al., 2019]), none of them has investigated the suitability of Gaussian kernel in t-SNE.

Since t-SNE needs a data-dependent kernel, we propose to use a recent data-dependent kernel called Isolation kernel [Ting et al., 2018; Qin et al., 2019] to replace the dataindependent Gaussian kernel in t-SNE. The Isolation kernel is a perfect match for the task because a data-dependent kernel, by definition, adapts to local distribution without any additional optimisation. The kernel replacement is conducted in the component in the high-dimensional space only, leaving the other components of the t-SNE procedure unchanged.

The experiment result shows that using Isolation kernel improves the performance of t-SNE and resolves the issues brought by Gaussian kernel in t-SNE.

2 Two Deficiencies of Gaussian Kernel When Used in t-SNE

2.1 The First Deficiency

Gaussian kernel determines each local bandwidth based on one local point only. It often creates misrepresented structure(s) that do not exist in high-dimensional space under some conditions.

Point-Based Bandwidth: The Cause of Misrepresentation in High-Dimensional Space

As bandwidth σi of the Gaussian kernel is fixed for each point xi, we have the following observation:

Observation 1. Gaussian kernel with point-based bandwidth can misrepresent the structure of a data distribution that has points significantly denser than the majority of the points in a sample generated from the distribution.

An example simulation result of t-SNE's misrepresentation is shown in the first column in Figure 1: t-SNE is unable to identify the joint component of the three clusters in different subspaces which share the same mean at the origin only in the high-dimensional space but nowhere else. Notice that the mapped origin point is misrepresented to be associated with one cluster only; and it is totally disassociated with the other two clusters. 1

2.2 The Second Deficiency

The use of the data-independent kernel requires t-SNE to determine n bandwidths for a dataset of n points. This becomes one key obstacle in dealing with large datasets.

Low Computational Efficiency With Gaussian Kernel

The use of a Gaussian kernel necessitates the search for a local bandwidth for each local point. t-SNE utilises a binary search for the value of σi that makes the entropy of the distribution over neighbours equal to logK, where K is the effective number of local neighbours or "perplexity" [Maaten and Hinton, 2008]. This search is the key component that determines the success or failure of t-SNE. A gradient descent search has been used successfully to perform the search for n parameters for small datasets [Maaten and Hinton, 2008]. This formulation has two key limitations for large datasets. First, the need for n-parameters search poses a real limitation in terms of finding appropriate settings for a large number of parameters. Second, it cannot deal with large datasets because it has high time complexity O(n2 ).

1 A Matlab code demonstration of using t-SNE with Isolation kernel can be obtained from https://github.com/zhuye88/IKt-sne.

3 Using the Isolation Kernel in t-SNE

Since t-SNE needs a data-dependent kernel, we propose to use a recent data-dependent kernel called Isolation kernel [Ting et al., 2018; Qin et al., 2019] to replace the data-independent Gaussian kernel in t-SNE.

The Isolation kernel is a perfect match for the task because a data-dependent kernel, by definition, adapts to local distribution without any additional optimisation. The kernel replacement is conducted in the component in the high-dimensional space only, leaving the other components of the t-SNE procedure unchanged.

3.1 Isolation Kernel Versus Gaussian Kernel

The key difference is that the Isolation kernel adapts to local density distribution, but the Gaussian kernel is independent of the data distribution.

In addition, the technical differences can be observed in two aspects. First, the Isolation kernel has no closed-form expression. Second, it is derived directly from a dataset, without explicit learning or optimisation. Its adaptation to local density is a direct outcome of its isolation mechanism used to partition space, i.e., the mechanism produces large partitions in sparse regions and small partitions in dense regions [Ting et al., 2018; Qin et al., 2019]. A natural isolation mechanism that has this

(a) ψ = 16

(b) ψ = 64

Figure 2: Two examples of partitioning H using the nearest neighbour (a Voronoi diagram) on a dataset having two regions of uniform densities, where the left half has a lower density than the right half.

characteristic is a Voronoi diagram. Given a sample of the underlining distribution, each Voronoi cell isolates a point from the rest of the points in the sample; and the cells are small in the dense region and large in the sparse region.

Note that the Voronoi diagram is obtained very efficiently, i.e., given a sample, nothing else needs to be done in the training stage because boundaries in the Voronoi diagram can be obtained at the testing stage as the equal distance between the two nearest points in the given sample.

Figure 2 shows two examples of partitioning H using the nearest neighbour or a Voronoi diagram on the same dataset with two different subsample sizes ψ. These examples show that there are more (small) cells in the dense region than (large) cells in the sparse region for each ψ; and the sizes of the cells are usually decreasing with respect to ψ. Two points located in the same cell get a similarity score of 1 in a partitioning. The final Isolation kernel similarity between two points is the probability of both points falling into the same cell over a finite number of partitionings.

The Isolation kernel has the following well-defined datadependent characteristic: two points in a sparse region are more similar than two points of equal inter-point distance in a dense region [Ting et al., 2018]. The details of Isolation kernel are provided in [Ting et al., 2018; Qin et al., 2019].

3.2 The Isolation Kernel Makes Full Use of the Distributional Information in Small Samples

The Isolation kernel only requires small samples (ψ) for the space partitioning without a computationally expensive process. A small sample of a dataset contains data distributional information which is sufficient to build a data-dependent kernel. The Isolation kernel extracts this information in the form of a Voronoi diagram, which depicts the relative densities between regions.

In contrast, using a data-independent measure such as the Gaussian kernel, the distributional information in a dataset is ignored and each point in the input space is treated as an independent point. In order to get the distributional information in the form of variable bandwidths that are adaptive to the local distribution, a separate optimisation process is required, as conducted in step 1 of the t-SNE algorithm.

It is important to note that when they could not handle a large dataset, most methods often use a small sample as a mitigation approach, and this inevitably trades off runtime with accuracy. But it is not the case for the Isolation kernel where small samples are the key to achieving high accuracy 2 ; and sample sizes larger than the optimal ψ degrade the accuracy of Isolation kernel.

In other words, by using the Gaussian kernel, t-SNE must employ a computationally expensive approach to get the distributional information in a dataset. It does not exploit the same information which is freely available in small samples of the dataset. The Isolation kernel is a direct approach that makes full use of the distributional information freely available in small samples of a dataset.

3.3 Overcoming the Two Deficiencies

The Isolation Kernel's Parameter Is Not Point-Based

Isolation kernel with one parameter ψ ensures that the local structure is truly reflected in the similarities among local points in the high-dimensional space: the three clusters are well separated and yet they share a common point, indicated by the mapped origin point as shown in the second column in Figure 1, unlike the misrepresentation exhibited in the first column when the Gaussian kernel is used.

This is possible because Isolation kernel is partition-based, points in the local neighbourhood are most likely to be in the same partition. As a result, t-SNE using the Isolation kernel produces an improved visualisation quality that has no misrepresentations.

High Computational Efficiency With Isolation Kernel

The computational complexities of the Gaussian kernel and Isolation kernel [Ting et al., 2018; Qin et al., 2019] used in t-SNE are shown in Table 1. Although the parameter ψ of

2 Isolation kernel performs optimally with small samples was formally analysed in the context of nearest neighbour anomaly detection [Ting et al., 2017]. The work is motivated by the previous finding that small samples can produce better detection accuracy for some anomaly detectors than large samples (e.g., [Liu et al., 2008; Sugiyama and Borgwardt, 2013].) The theoretical analysis based on computational geometry reveals that the geometry of data distribution has a direct impact on the sample size setting which is essential to produce an optimal nearest neighbour anomaly detector [Ting et al., 2017]. In a simple geometry such as a Gaussian distribution, a sample size of one data point (at the mean of Gaussian distribution) yields the optimal nearest neighbour anomaly detector; and a sample of more data points will produce a worse performing detector. In a more complex geometry of data distribution (e.g., a mixture of multiple Gaussian distributions), while the optimal sample size is more than one data point, a sample size more than the optimal one also produces a worse performing detector. See [Ting et al., 2017] for details.

t-SNE in 2d

t-SNE on 5 selected classes in 3d

Isolation kernel corresponds to the bandwidth parameter of the Gaussian kernel, the Isolation kernel needs no optimisation to determine n bandwidths locally. This is because the partitioning mechanism used by the Isolation kernel produces small partitions in dense regions and large partitions in sparse regions; and the sizes of the partitions are monotonically decreasing with respect to ψ. As the local adaptation has already been done during the process of deriving the kernel, no further adaptation is required after the kernel is derived.

Though the Isolation kernel derived from a dataset takes constant O(tψ) time, it is significantly less than the optimisation required to determine n bandwidths which takes O(n2 ) time in Gaussian kernel. For a large dataset, when using Gaussian kernel, it is infeasible to estimate a large number of bandwidths with an appropriate degree of accuracy, and its computational cost is prohibitively high.

The consequence of using Isolation kernel is that the runtime of step 1 in the t-SNE algorithm is significantly reduced. This enables the Isolation kernel version of t-SNE to deal with large datasets.

4 Example Evaluations

Here we provide two example evaluations. First, on a realworld dataset COIL20, we have identified a structural misrepresentation issue with the Gaussian kernel, similar to the one shown in Figure 1.

Figure 3 shows the five clusters where the Gaussian kernel has misrepresented structures in the high-dimensional space.

The 3-dimensional results denote that the Isolation kernel depicts a more nuanced structural relationship between the five clusters; whereas the Gaussian kernel depicts that they are disparate five clusters, shown in the second column in Figure 3. Also, note that a reference point × is close to all five clusters when the Isolation kernel is used, but it is far from many clusters when a Gaussian kernel is used.

Second, though both Gaussian Kernel and Isolation kernel have quadratic time and space complexities, using Gaussian kernel in t-SNE needs a large number of iterations to search for the optimal local bandwidth for each point. As a result, t-SNE takes a much longer time in step 1 of the algorithm than the Isolation kernel version of t-SNE. For example, in a dataset of 100,000 data points, the Isolation kernel version of t-SNE is two orders of magnitude faster than the Gaussian kernel version (887 seconds versus 72,196 seconds).

Further details of the proposed method and the evaluation results can be found in the full paper [Zhu and Ting, 2021]. This includes existing methods FIt-SNE [Linderman et al., 2019] and opt-SNE [Belkina et al., 2019] that employ an approximation approach to address the efficiency issue of tSNE, but the misrepresentation issue remains because they all use Gaussian kernel.

In a nutshell, the proposed method of using Isolation kernel is a unique approach to address the two deficiencies of t-SNE from their root cause that no existing methods can provide.