NCVis: Noise Contrastive Approach for Scalable Visualization

Aleksandr	Artemenkov

Skolkovo Institute of Science and Technology
Bolshoy Boulevard 30, bld. 1

Moscow Institute of Physics and Technology
Institutskiy pereulok 9
Moscow Region

Maxim	Panov

Skolkovo Institute of Science and Technology
Bolshoy Boulevard 30, bld. 1

Modern methods for data visualization via dimensionality reduction, such as t-SNE, usually have performance issues that prohibit their application to large amounts of high-dimensional data. In this work, we propose NCVis – a high-performance dimensionality reduction method built on a sound statistical basis of noise contrastive estimation. We show that NCVis outperforms state-of-the-art techniques in terms of speed while preserving the representation quality of other methods. In particular, the proposed approach successfully proceeds a large dataset of more than 1 million news headlines in several minutes and presents the underlying structure in a human-readable way. Moreover, it provides results consistent with classical methods like t-SNE on more straightforward datasets like images of hand-written digits. We believe that the broader usage of such software can significantly simplify the large-scale data analysis and lower the entry barrier to this area.

<concept_desc>Human-centered computing Visualization techniques</concept_desc>
<concept_desc>Mathematics of computing Probabilistic representations</concept_desc>
<concept_desc>Mathematics of computing Dimensionality reduction</concept_desc>
<concept_desc>Computing methodologies Information extraction</concept_desc>

[500]Human-centered computing Visualization techniques
[500]Mathematics of computing Probabilistic representations
[500]Mathematics of computing Dimensionality reduction
[100]Computing methodologies Information extraction

§ INTRODUCTION

NCVis visualization of more than 2 million news headlines <cit.> in less than 15 minutes. The word clouds illustrate the most frequent words used in the headlines from the area.

With the growth of the internet, extensive data sets became ubiquitous. However, it is not always feasible to tag every sample as there are too many of them. Even though we cannot perform a specific labeling procedure, this does not mean that there is no underlying structure in the data. On the contrary, such a structure is almost always present but requires a thorough study to be retrieved. The classical approach is to focus on a considerably smaller subset and try to find patterns there. But, intuitively, we can benefit from using the data, especially when one recalls the advances of statistical methods.

The classical linear approaches to dimensionality reduction, such as Principal Component Analysis (PCA; <cit.>), are computationally efficient and widely used for data preprocessing and feature extraction. However, their linearity usually does not allow them to obtain high-quality low-dimensional representations that would be useful for visualization. Though the development of nonlinear dimensionality reduction methods such as Multidimensional scaling (MDS; <cit.>), Isomap <cit.>, Locally Linear Embedding (LLE; <cit.>), Laplacian Eigenmaps <cit.> and Local Tangent Space Alignment (LTSA; <cit.>) allowed to improve the quality of low-dimensional embeddings, their strong performance on artificial data is often not supported by comparable results on real-world high-dimensional data.

The situation has changed when t-SNE <cit.> – an approach focused on interpretable dimensionality reduction – was introduced and was quickly considered to be a de-facto standard for data visualization via dimensionality reduction. The computational performance of t-SNE is enough to provide a positive user experience with small to medium-sized data, but its poor scalability does not allow for processing large data sets. Several optimizations <cit.> were proposed to solve this problem, but none of them were able to provide a considerable improvement of its performance. The recently introduced LargeVis <cit.> and Umap <cit.> focus on the usage of stochastic optimization for the objective function similar to the one of t-SNE. Both these methods achieve a considerable speedup as compared to their competitors, but still are based on a large set of heuristics, which results in difficulties with understanding the underlying idea and practical usage.

In this paper, we formulate a statistical approach to design high-performance dimensionality reduction algorithms. In this case, the need for heuristics is minimized, so the efficacy can be granted for free. Our approach is based on the theory of Noise Contrastive Estimation (NCE; <cit.>) and proceeds from the assumption that though many representations may have structural similarities with the target object, only a few of them avoid including unnecessary details. This variant of Occam's razor can be interpreted in the following way: while maximizing the correspondence with real data, also minimize the similarity with noise.

When applied to the dimensionality reduction problem, NCE approach allows us to introduce Noise Contrastive Visualization (NCVis)  — a highly-scalable method for visualization via dimensionality reduction. The main issue which prevents the efficient batch training of t-SNE is the necessity to re-normalize the distribution in embedding space at every step. NCVis allows to avoid this issue and its scalability becomes the direct consequence of self-normalizing properties of NCE <cit.>.

Our main contributions can be summarized as follows:

* We propose a principled statistical approach NCVis to obtain scalable dimensionality reduction algorithms basing on Noise Contrastive Estimation methodology. The approach allows for efficiently parallelizable batch training of embeddings.

* We implement NCVis as a multi-platform Python package[https://github.com/stat-ml/ncvis] providing a stable out-of-the-box experience.

* Experiments have proved that NCVis outperforms state-of-the-art methods for visualization via dimensionality reduction in terms of speed without losing a high visualization quality.

* Due to the parallel nature of the algorithm, NCVis gains significant benefits from hardware leveraging which allows us to visualize millions of high-dimensional objects in several minutes using a standard multi-core PC.

§ PROBLEM STATEMENT

In this paper, we address the problem of building a low-dimensional representation of high-dimensional data:
{_i ∈ℝ^M}_i=1^N →{_i ∈ℝ^m}_i=1^N,  where m ≪M.

We also suppose that some distance function $d(\cdot, \cdot)\colon \mathbb{R}^{M} \times \mathbb{R}^{M} \to [0, +\infty)$ can be defined for each pair of vectors from the set $\{\widehat{\vz}_i\}_{i=1}^N$. We assume that the value of this function should increase as the dissimilarity between the points goes up. That is why there is no demand for metric properties except for non-negativity: $d(\cdot, \cdot) \ge 0$.

§ NOISE CONTRASTIVE VISUALIZATION

In this paper, we introduce Noise Contrastive Visualization (NCVis) — a highly-scalable method for visualization via dimensionality reduction based on the Noise Contrastive Estimation (NCE) approach. Its implementation is based on a special optimization procedure, which makes it well suited for parallelization.

An informal overview of the method goes as follows. One can select pairs of neighbors from the original high-dimensional data set. Suppose, that this is done in random manner: the higher the distance between points, the lower the probability for them to be selected. Now suppose that we also given a low-dimensional representation of the original data points, so we can perform a similar procedure there. It seems reasonable, that a good representation should induce the same pairs that were observed in the original data. Note that in order to build such a representation, we need to compute all the pairwise distances in the embedding. This will allow us to compare them and use terms “large” and “small” properly. However, we can reformulate the objective. Consider noisy representation where all the neighbors probabilities are almost equal. We can now use them as reference to mark lower-dimensional probabilities as either large or small. In this case we do not need to gather information about all the pairs of neighbors, it will be enough to know the scale of lower-dimensional probabilities with respect to the noisy probabilities.

§.§ Noise Contrastive Estimation

We start by describing NCE approach and establishing the notations to be used further. Noise Contrastive Estimation (NCE) was introduced in <cit.> and developed in a more recent work <cit.>. Let $P_d$ be a data distribution with density $p_d$ and samples $X = \{\vx_i\}_{i=1}^{T_d}$ coming from this distribution. Consider also noise distribution $P_n$ with density $p_n$ and corresponding samples $Y = \{\vy_i\}_{i=1}^{T_n}$. Unite the two sets: $ X \cup Y = U = \{\vu_i\}_{i=1}^{T_d+T_n}$, and assign a binary label $C_t$ to each element $\vu_t$: $C_t = 1$ if $\vu_t \in X$ and $C_t = 0$ if $\vu_t \in Y$. We also define noise ratio as $\nu = \frac{T_n}{T_d}$. Our initial goal is to obtain an approximation of $p_d$ with some model $p_m(\cdot; \vtheta)$. It is important to notice that normalization is included in the parameters $\vtheta$, so, generally speaking, the model is unnormalized. NCE objective $J_T(\vtheta)$ is then given by the principle of maximum likelihood:
J_T() →max_,

1/T_d{ ∑_i=1^T_d logp_m(_i; )/p_m(_i;) + νp_n(_i)

∑_i=1^T_n logνp_n(_i)/p_m(_i;) + νp_n(_i)}.

In order to apply the law of large numbers, we can also rewrite it as

1/T_d∑_i=1^T_d logp_m(_i; )/p_m(_i;) + νp_n(_i)

+ ν1/T_n∑_i=1^T_n logνp_n(_i)/p_m(_i;) + νp_n(_i).

Assume that both $P_d$ and $P_n$ have a finite mean. When $T_d$ tends to infinity (and $T_n$ also tends to infinity as $T_n = \nu T_d$) the following objective is obtained using the weak law of large numbers:

_∼P_d [ logp_m(; )/p_m(;) + νp_n() ]

ν_∼P_n[logνp_n()/p_m(;) + νp_n()].

Due to a stochastic nature of the objective function, the first order batch optimization methods can be beneficial in the case of the large number of parameters $\vtheta$. The explicitly written gradient with respect to the vector of parameters is given by

∂/∂_i J() = ∫p_d()  - p_m(; )/1 + p_m(; )/νp_n() ∂/∂_i logp_m(; ) d .

A strong resemblance can be noticed between the proposed approach and a standard ML estimate for unnormalized models. Maximum Likelihood objective function $L(\vtheta)$ and its gradient are given by
L() = _∼P_d [ logp_m(; )/∫p_m(;)d  ],

∂/∂_i L() = ∫{ p_d() - p_m(; )/∫p_m(;)d } ∂/∂_i logp_m(;) d .

The similarity between Equation (<ref>) and Equation (<ref>) goes even further, when noise ratio $\nu$ tends to infinity:
∂/∂J() ν→∞⟶ ∫( p_d() -p_m(; ) ) ∂/∂ logp_m(;),

which coincides with Equation (<ref>) if $\int p_m(\vx;\vtheta) d \vx = 1$. As it follows, every stationary point of MLE objective where $p_m(\vx;\vtheta)$ is normalized is also a stationary point of NCE objective and vice versa.

Recall that t-SNE <cit.> minimizes Kullback-Leibler divergence between $p_d$ and $p_m$, and thus maximizes the corresponding likelihood. The optimum is usually searched for by a gradient descent or other first-order optimization methods. To conclude, if noise ratio $\nu$ is high enough and the resulting model is normalized, there is no significant difference between using t-SNE and NCVis (see also the experimental validation in Section <ref>).

§.§ Probabilistic Model

In this section, we specify the particular instance of the approach described above to provide a simple but powerful probabilistic method for obtaining high-quality visualizations.

First of all, we reintroduce the main idea of t-SNE which starts from defining conditional probabilities $\mathbb{P} =\{p_{ij}\}_{i, j = 1}^N$ of high-dimensional points:

p_ij = p_ij/∑_k ≠lp_kl,   p_ij =
exp[-_i - _j_2^2/2σ_i^2].

In Equation (<ref>) the variances $\{\sigma_i^2\}_{i=1}^N$ are selected to keep the entropy of distributions $\{p_{ij}\}_{j=1}^N$ close to the predefined value for each $i$. Similarly, for points in low-dimensional space the probabilities $\mathbb{Q} =\{q_{ij}\}_{i, j = 1}^N$ are introduced:
q_ij = q_ij/∑_k ≠l q_kl,   q_ij =
1/1 + _i - _j_2^2.

Finally, the low-dimensional embeddings $\{\vz_i\}_{i=1}^N$ are obtained by minimizing Kullback-Leibler divergence between the distributions:
ℙℚ →min_.

The main problem here is that every $q_{ij}$ is normalized, which requires the computation of aggregate sum $\sum_{k \neq l}\widehat{q}_{kl}$ and leads to a significant slowdown and parallelization issues. This difficulty can be overcome by switching to unnormalized models which can be done by using NCE since it provides a robust framework to handle such problems.

We note, that probabilities $p_{ij}$ from (<ref>) quickly become negligible when the distance between the points increases. Having taken it into account, we propose to simply use neighborhood indicators instead of Gaussian type probabilities in (<ref>). For a fixed number neighbours $k$ we define
1_i^k(j) =

1,     if point $\widehat{\vz}_j$ is among $k$ nearest neighbors of point $\widehat{\vz}_i$,

0,     otherwise or if $i = j$.

Another function that is useful for us is $\mathbb{1}^k(i, j) = \mathbb{1}_i^k(j) \vee \mathbb{1}_j^k(i)$, which is non-zero if at least one of the points is among $k$ nearest neighbors of the other point. Now for each pair of points $(i, j)$ in the high dimensional space we introduce the probability of observing their co-occurrence
p_ij = 1^k(i, j)/∑_i ≠j 1^k(i, j).

For a lower-dimensional space, unlike t-SNE, we propose to treat normalization constant $Q$ as one of the parameters:
q_ij = q_ij e^-Q,   q_ij = (1 + a_i - _j^2b)^-1,

where $a$ and $b$ are some fixed values. Such an expression for probabilities is inspired by Umap <cit.>.

Finally, using NCE notation, we observe the nearest neighbor graph
X ⊆{(i, j)}_i,j = 1^N   with edge probabilities   p_d(i, j) = p_ij.

As proposed before, we are intended to unite the normalization parameter $Q$ and vector representations $\{\vz_i\}_{i=1}^N$ into a single vector parameter $\vtheta = \{Q, \{\vz_i\}_{i=1}^N\}$. In this notation the modelling distribution is given by
p_m(i, j; ) = q_ij.

To be consistent in simplification, we propose the noise distribution with the following sampling procedure:

* Sample edge $(i, j)$ according to distribution $\{p_d(i, j)\}_{i=1, j=1}^N$.

* Select $k$ from uniform distribution on $\{l\}_{l=1, l \neq i}^N$.

* Return edge $(i, k)$ as the sample.

This induces the following noise distribution:
Y = {(i, j)}_i,j=1^N   with probabilities    p_n(i,j) = 1/N-1 ∑_k=1^N p_ik.

After the construction of the distributions, which one can easily sample from, we will now utilize stochastic gradient ascent to optimize NCE objective.

§.§ Optimization Algorithm

The whole purpose of using Noise Contrastive Estimation is the ability to leverage batch optimization. The expectations in Equation (<ref>) can be approximated by sampling from the distributions $P_d$ and $P_n$, respectively. That is why it was essential to keep them as simple as possible. Otherwise, efficient parallelization may not be enough to compensate for the complexity of sampling. The details can be found in Algorithm <ref>.

A set $\{\widehat{\vz}_i \in \mathbb{R}^{M}\}_{i=1}^N$ of vectors
Visualization $\{\vz_i \in \mathbb{R}^{m}\}_{i=1}^N$ of the input
Construct $P_d$ and $P_n$ from $\{\widehat{\vz}_i\}_{i=1}^N$

Initialize $\vtheta = \{Q, \{\vz_i\}_{i=1}^N\}$

$epoch$ $\gets 1$ $N_{epochs}$
$sample$ $\gets 1$ $N_{samples}$
$\vx \gets (v_1, v_2) \sim P_d$ *sample real edges
$j$ $\gets 1$ $\nu$
$\vy_j \gets (v_1, v_2) \sim P_n$ *sample noise

$J_T(\vtheta) \gets 0$;

$J_T(\vtheta) \gets J_T(\vtheta) + \log \frac{p_m(\vx; \vtheta)}{p_m(\vx; \vtheta) + \nu p_n(\vx)}$;

$J_T(\vtheta) \gets J_T(\vtheta) + \sum_{j=1}^{\nu} \log \frac{\nu p_n(\vy_j)}{p_m(\vy_j; \vtheta) + \nu p_n(\vy_j)}$;

$\vtheta \gets \vtheta + \alpha \cdot \nabla J_T(\vtheta)$ *gradient
ascent step

Embedding construction algorithm.

During the initialization phase, we use the Power Iteration method. The reason can be formulated as follows. If the nearest neighbor graph adjacency matrix has a block structure, the corresponding coordinates of the initialization vector will be located closely to each other. Thus, representations of the nodes from one community will be located near each other providing high values of likelihood.

In our setting, it is crucial to have an efficient solution for the nearest neighbor graph construction. To achieve it, we have selected the approach based on Hierarchical Navigable Small World graphs (HNSW), whose advantages over the alternatives are presented in detail in <cit.>. The main idea of the method is to build a hierarchical structure of proximity graphs that allows localizing nearest neighbors via subsequent scale reduction efficiently.

§.§ Complexity

If we use $k$ nearest neighbors for each point, then NCVis will consist of the following steps:

* The nearest neighbor graph construction by HNSW has complexity $O(N \log N)$ <cit.>.

* Embedding initialization is performed with the Power Iteration method. Due to the sparsity of the graph, it has complexity $O(kN)$.

* Embedding optimization is a direct application of Algorithm <ref> and thus also has complexity $O(kN)$.

Consequently, the overall complexity is $O\bigl(N(k + \log N)\bigr)$ and is determined by the complexity of the graph construction approach for a sufficiently small number $k$ of nearest neighbors.

§ PERFORMANCE EVALUATION

We compared the speed and visualization quality of NCVis to those of other existing methods. Our algorithm aims to provide state-of-the-art performance on large data sets while giving predictable output is standard cases. It is essential for a such software to show a good out-of-the-box performance and to have a convenient interface. The most popular methods in this category are Multicore t-SNE <cit.>, Umap <cit.> and t-SNE implemented in Scikit-learn <cit.>. However, we also want our method to be competitive with those which do not satisfy this criterion but are still efficient in practice such as FIt-SNE <cit.> and LargeVis <cit.>. For all the experiments, we used NCVis with $15$ nearest neighbors, $50$ optimization epochs and the data set size as the number of samples.

§.§ Speed Comparison

We use preprocessed samples from the News Headlines Of India data set <cit.> to perform the comparison. Test cases are generated by taking the first $1000, 2\cdot1000, \dots, 2^{10}\cdot1000$ samples from the data set. The hardware used is $12\,\times\,$$\text{Intel\textsuperscript{\textregistered}}$$\text{Core\textsuperscript{\texttrademark}}$  i7-8700K CPU @ 3.70GHz, $64\, \text{Gb RAM}$. Figure <ref> summarized the results of the experiment which show that the performance of the proposed method is superior to its alternatives. It should be noted here that Scikit-learn t-SNE and Umap do not support parallelization while other methods benefit from it.

Comparison of the visualization methods by speed. Given same amount of time NCVis allows to process more than double number of samples compared to other methods, visualizing $10^6$ points in only $6$ minutes.

§.§ Quality Comparison

Our next step was to evaluate the quality of the method and, what is more important, its predictable behavior on simple data sets. We used the Optical Recognition of Handwritten Digits Data Set from <cit.> which comprised $5620$ preprocessed handwritten digits and thus has a simple structure that is assumed to be revealed by visualization. Figure <ref> proves that NCVis shows the behavior consistent with classical methods like t-SNE while producing visualization up to the order of magnitude faster.

t-SNE, $29.5$s

FIt-SNE, $17.4$s

Multicore t-SNE, $14.3$s

LargeVis, $9.7$s

Umap, $7.5$s

NCVis, $0.9$s

The comparison of visualization methods on handwritten digit data set. NCVis behaves similarly to t-SNE and does not tend to collapse clusters, though reduces the time significantly. Each colored cluster corresponds to a distinct digit.

§.§ Parallelization Efficiency

Another important criterion to measure the method's scalability is an efficient use of the resources. We can compare the methods, which support parallelization, by the efficiency of parallelization. We use a traditional notation: let $\tau_1, \tau_2, \dots, \tau_n$ be the times which correspond to execution with $1, 2, \dots, n$ processes. One can define efficiency as $S_n = \frac{\tau_1}{\tau_n}$: it equals $1$ for $n=1$ and for more processes we expect $S_n$ to be close to $n$. Even though in practice the achievement of such an efficiency is challenging, we can still use it as a reasonable comparison criterion. The results of the experiment are presented in Figure <ref>. We used $10000$ samples from a news data set. It should be pointed out, however, that slow data loading procedures impact FIt-SNE and LargeVis performance.

The comparison of visualization approaches by efficiency. Ideally, the efficiency should be equal to the number of threads. NCVis does not achieve this limit but significantly outperforms other methods.

§ LARGE SCALE APPLICATION

There are numerous artificial tasks which exhibit a clear cluster structure. On the contrary, pure clusters rarely occur in real-life applications. Nevertheless, there is still inner structure which can be revealed by visualization. To show the full potential of NCVis we will visualize a large India News headlines data set of more than $2$ million samples <cit.>. The challenge is to study the incredibly vast set of topics in a reasonable amount of time.

§.§ Data Preprocessing

The samples in the data set $\mathcal{D} = \{s_i\}_{i=1}^N$ are India News headlines. Our task is to build vector representation for each of them. In order to do so, we use $1$ million English word vectors <cit.> trained on Wikipedia 2017, UMBC webbase corpus and statmt.org news data set. These data allow us to perform mapping $\mathcal{R}\colon \mathcal{W} \to \mathbb{R}^M$ for words $w$ in dictionary $\mathcal{W} = \{w_l\}_{l=1}^L$. Each headline $s_i$ is split into the words $\{v_k\}_{k=1}^{K_i}$. For each word we then find the representation according to the rule
v_k →_k =

ℛ(v_k),      if  v_k ∈𝒲,

0,      if  v_k ∉𝒲.

Finally, each sentence is represented by the mean of its words:
s_i →_i = 1/K_i ∑_k=1^K_i _k.

§.§ Data Visualization

Afterwards, NCVis is used with cosine similarity as distance function to construct the visualization:
{_i ∈ℝ^M}_i=1^N →{_i ∈ℝ^2}_i=1^N.

Cosine similarity was selected as representations for similar words have greater dot product than for dissimilar ones. Thus we assume that the same also holds for sentence representations. The result can be found in Figure <ref>.

NCVis visualization of India News headlines embeddings. The focus is on several dense and isolated areas, as we believe to find the most interesting information there.

§.§ Visualization Analysis

There are more than $1$ thousand categories provided in the data set, which makes a standard cluster analysis complicated. However, it can be much more useful to introduce a less excessive list of topics based on the data set structure. One can focus on specific groups of points to develop a better understanding of the presented headlines. We propose to visualize vector representations of news headlines and then to focus on areas of interest: isolated regions and regions with a higher density, see several examples on Figure <ref>.

Within a short time, we have been able to find relevant news topics and study them more carefully by sampling the headlines from one of the selected areas (for example, the one connected with medicine). Several headlines sampled from this “medicine” region are presented in Table <ref>. We clearly see strong semantic links between the selected headlines which shows that the obtained visualization is meaningful.

Examples of news headlines selected from the area connected with medicine.

kidney transplant saves life of year old

south tn s first ever heart transplant performed in grh

seventh heart transplant takes place in mulund hospital

two hsc papers of oct rescheduled to oct

two get new shot at life after kidney transplants

§ RELATED WORK

The problem of data visualization is well studied and can be solved in several ways.

The Scikit-learn implementation of t-SNE <cit.> is probably the most well-known and most widely used visualization method. Among the advantages of the method making it so popular are a convenient, user-friendly, interface and its ability to provide state-of-the-art visualization quality for small and medium-sized data sets. Still, it fails to be efficient enough for large-scale applications because of the normalization problem discussed in Section <ref>.

The issue of scalability can be addressed directly by using the parallel version of the algorithm. Despite the fact that the author of Multicore t-SNE <cit.> adopted this approach and provided the corresponding implementation, the method remains considerably slow and has a low parallelization efficiency, since the normalization term is computed explicitly.

FIt-SNE <cit.> is much more scalable and uses an entirely different idea to compute interactions between the points. It originates from a fast simulation of $N$-body problem, where Fast Fourier Transform can be used to gain a significant speedup. However, only computational part of the algorithm has been changed, and it still behaves similarly to t-SNE in terms of processing large samples.

All the techniques described above leave the theoretical basis unchanged and try to solve the performance difficulties of the original t-SNE algorithm. Another family of methods takes an entirely different path by introducing its own objective functions. As far as we know, LargeVis <cit.> is the first method with a focus on graph visualization that uses the idea of negative sampling. This vital step removes the necessity of explicit calculations of the normalization term.

Umap <cit.> approach is based on the same idea as LargeVis, but it pays much more attention to heuristics, providing a noticeable performance gain. It is also the first method that combines a convenient user interface and efficiency. However, due to the absence of a parallelism support, it faces significant scaling difficulties.

§ CONCLUSION

We developed NCVis – a highly-scalable method for visualization via dimensionality reduction based on the sound theory of Noise Contrastive Estimation. The main idea behind this approach is to focus not only on likelihood maximization between the real data and the model but to keep the model as distinct from the noise as possible. It allows to remove excess information about the object and, at the same time, highlight relevant details. We derive our method from the theory of Noise Contrastive Estimation and outline some of its essential properties. We emphasize that when the amount of noise is large enough, NCVis produces the results, which are close to those obtained with the well-known t-SNE method.

The experimental validation of NCVis was performed on the conventional multi-core hardware against the state-of-the-art methods for visualization via dimensionality reduction such as Multicore t-SNE <cit.>, Umap <cit.>, t-SNE implemented in Scikit-learn <cit.>, FIt-SNE <cit.> and LargeVis <cit.>. We show that the proposed method significantly outperforms the competitors in terms of speed: it needs only $6$ minutes to provide well-interpretable visualizations for more than $1$ million of high-dimensional data points. Moreover, we show that the parallelization efficiency of NCVis is much higher than the one of other methods. This fact creates the possibility for visualization of the data of an arbitrary scale given sufficiently powerful hardware. Finally, on the classical data set of handwritten digits <cit.>, NCVis provides high-quality visualization which is consistent with the famous t-SNE results while computing it 30 times faster.

The whole pipeline can be found online[https://github.com/stat-ml/ncvis-examples]. Taking into account that NCVis is easy to install and cross-platform, our method can be considered as a perfect candidate for real-life applications.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Belkin and NiyogiBelkin and Niyogi2002]
authorpersonMikhail Belkin and
personPartha Niyogi. year2002.
Laplacian eigenmaps and spectral techniques for
embedding and clustering. In booktitleAdvances in neural
information processing systems. pages585–591.

[Dua and GraffDua and Graff2017]
authorpersonDheeru Dua and personCasey
Graff. year2017.
titleUCI Machine Learning Repository.

[Gutmann and HyvärinenGutmann and
authorpersonMichael Gutmann and personAapo
Hyvärinen. year2010.
Noise-contrastive estimation: A new estimation
principle for unnormalized statistical models. In
booktitleProceedings of the Thirteenth International
Conference on Artificial Intelligence and Statistics.

[Gutmann and HyvärinenGutmann and
authorpersonMichael U Gutmann and
personAapo Hyvärinen. year2012.
Noise-contrastive estimation of unnormalized
statistical models, with applications to natural image statistics.
journalJournal of Machine Learning Research
volume13, numberFeb (year2012),

authorpersonHarold Hotelling.
Analysis of a complex of statistical variables into
principal components.
journalJournal of educational psychology
volume24, number6 (year1933),

authorpersonIan Jolliffe.
booktitlePrincipal component analysis.

[Jolliffe and CadimaJolliffe and
authorpersonIan T Jolliffe and personJorge
Cadima. year2016.
Principal component analysis: a review and recent
journalPhilosophical Transactions of the Royal
Society A: Mathematical, Physical and Engineering Sciences
volume374, number2065 (year2016),

authorpersonRohit Kulkarni.
booktitleNews Headlines of India 2001-2018 [CSV data

[Linderman, Rachh, Hoskins, Steinerberger, and
KlugerLinderman et al2019]
authorpersonGeorge C Linderman, personManas
Rachh, personJeremy G Hoskins, personStefan
Steinerberger, and personYuval Kluger.
Fast interpolation-based t-SNE for improved
visualization of single-cell RNA-seq data.
journalNature methods volume16,
number3 (year2019), pages243.

[Maaten and HintonMaaten and Hinton2008]
authorpersonLaurens van der Maaten and
personGeoffrey Hinton. year2008.
Visualizing data using t-SNE.
journalJournal of machine learning research
volume9, numberNov (year2008),

[Malkov and YashuninMalkov and
authorpersonYury A Malkov and
personDmitry A Yashunin. year2018.
Efficient and robust approximate nearest neighbor
search using hierarchical navigable small world graphs.
journalIEEE transactions on pattern analysis and
machine intelligence (year2018).

[McInnes, Healy, and MelvilleMcInnes
et al2018]
authorpersonLeland McInnes, personJohn
Healy, and personJames Melville.
Umap: Uniform manifold approximation and projection
for dimension reduction.
journalarXiv preprint arXiv:1802.03426

[Mikolov, Grave, Bojanowski, Puhrsch, and
JoulinMikolov et al2018]
authorpersonTomas Mikolov, personEdouard
Grave, personPiotr Bojanowski, personChristian
Puhrsch, and personArmand Joulin.
Advances in Pre-Training Distributed Word
Representations. In booktitleProceedings of the
International Conference on Language Resources and Evaluation (LREC 2018).

[Pedregosa, Varoquaux, Gramfort, Michel,
Thirion, Grisel, Blondel, Prettenhofer, Weiss, Dubourg, Vanderplas, Passos,
Cournapeau, Brucher, Perrot, and DuchesnayPedregosa et al2011a]
authorpersonF. Pedregosa, personG.
Varoquaux, personA. Gramfort, personV. Michel,
personB. Thirion, personO. Grisel,
personM. Blondel, personP. Prettenhofer,
personR. Weiss, personV. Dubourg, personJ.
Vanderplas, personA. Passos, personD. Cournapeau,
personM. Brucher, personM. Perrot, and
personE. Duchesnay. year2011a.
Scikit-learn: Machine Learning in Python.
journalJournal of Machine Learning Research
volume12 (year2011), pages2825–2830.

[Pedregosa, Varoquaux, Gramfort, Michel,
Thirion, Grisel, Blondel, Prettenhofer, Weiss, Dubourg, Vanderplas, Passos,
Cournapeau, Brucher, Perrot, and DuchesnayPedregosa et al2011b]
authorpersonF. Pedregosa, personG.
Varoquaux, personA. Gramfort, personV. Michel,
personB. Thirion, personO. Grisel,
personM. Blondel, personP. Prettenhofer,
personR. Weiss, personV. Dubourg, personJ.
Vanderplas, personA. Passos, personD. Cournapeau,
personM. Brucher, personM. Perrot, and
personE. Duchesnay. year2011b.
Scikit-learn: Machine Learning in Python.
journalJournal of Machine Learning Research
volume12 (year2011), pages2825–2830.

[Roweis and SaulRoweis and Saul2000]
authorpersonSam T Roweis and
personLawrence K Saul. year2000.
Nonlinear dimensionality reduction by locally
linear embedding.
journalscience volume290,
number5500 (year2000), pages2323–2326.

[Tang, Liu, Zhang, and MeiTang
et al2016]
authorpersonJian Tang, personJingzhou Liu,
personMing Zhang, and personQiaozhu Mei.
Visualizing large-scale and high-dimensional data.
In booktitleProceedings of the 25th international conference
on world wide web. International World Wide Web Conferences Steering
Committee, pages287–297.

[Tenenbaum, De Silva, and LangfordTenenbaum
et al2000]
authorpersonJoshua B Tenenbaum, personVin
De Silva, and personJohn C Langford.
A global geometric framework for nonlinear
dimensionality reduction.
journalscience volume290,
number5500 (year2000), pages2319–2323.

authorpersonWarren S Torgerson.
Multidimensional scaling: I. Theory and method.
journalPsychometrika volume17,
number4 (year1952), pages401–419.

authorpersonDmitry Ulyanov.

[Van Der MaatenVan Der Maaten2014]
authorpersonLaurens Van Der Maaten.
Accelerating t-SNE using tree-based algorithms.
journalThe Journal of Machine Learning Research
volume15, number1 (year2014),

[Zhang and ZhaZhang and Zha2004]
authorpersonZhenyue Zhang and
personHongyuan Zha. year2004.
Principal manifolds and nonlinear dimensionality
reduction via tangent space alignment.
journalSIAM journal on scientific computing
volume26, number1 (year2004),