A MORE GLOBALLY ACCURATE DIMENSIONALITY REDUCTION METHOD USING TRIPLETS
Year: 2018

Abstract:
We first show that the commonly used dimensionality reduction (DR) methods such as t-SNE and LargeVis poorly capture the global structure of the data in the low dimensional embedding. We show this via a number of tests for the DR methods that can be easily applied by any practitioner to the dataset at hand. Surprisingly enough, t-SNE performs the best w.r.t. the commonly used measures that reward the local neighborhood accuracy such as precision-recall while having the worst performance in our tests for global structure. We then contrast the performance of these two DR method against our new method called TriMap. The main idea behind TriMap is to capture higher orders of structure with triplet information (instead of pairwise information used by t-SNE and LargeVis), and to minimize a robust loss function for satisfying the chosen triplets. We provide compelling experimental evidence on large natural datasets for the clear advantage of the TriMap DR results. As LargeVis, TriMap is fast and provides comparable runtime on large datasets.

heading: 1 INTRODUCTION
text: Information visualization using dimensionality reduction (DR) is a fundamental step for gaining insight about a dataset. Motivated by the fact that the humans essentially think in two or three dimensions, DR has been studied extensively (Tenenbaum et al., 2000; Kohonen, 1998; Roweis & Saul, 2000; Hinton & Roweis, 2003; Maaten & Hinton, 2008). However, how to choose the best DR method for visualizing a given dataset is yet unresolved. Despite the plethora of quantitative measures such as trustworthiness-continuity (Kaski et al., 2003), mean (smoothed) precision-recall (Venna et al., 2010), and nearest-neighbor accuracy (Van Der Maaten et al., 2009), there is no standard procedure to assess the quality of a low-dimensional embedding in general. Also these measures only focus on the local neighborhood of each point in the original space and low-dimensional embedding and fail to reflect global aspects of the data. We will argue that selecting a DR method based on these local measures is misleading.
In this paper, we mainly focus on the global properties of the data. These properties include the relative placements of the clusters in the dataset as well as revelation of outlier points that are located far away from the rest of the points in the high-dimensional space. It appears that quantifying the global properties is significantly more complicated and certainly local quality measures of DR (such as precision-recall1) do not capture these properties. Thus we resort to an evaluation based on visual clues that allows the practitioner to build confidence about the obtained DR results. To this end, we propose a number of transformations that happen naturally to real-world datasets. We argue that any DR method that claims to preserve the global structure of the data, should be able to handle these transformations. Ackerman et al. (2010) took a similar more theoretical approach for the task of clustering where certain natural properties are used to taxonomize different clustering algorithms.
Next, we introduce a new DR method, called TriMap. The main idea behind TriMap is to capture higher orders of structure in the data by considering the relative similarities of a chosen set of triplets of points. The method minimizes a loss over triplets that measures how well a triplet is satisfied. This loss is made robust by capping it with a damping function. We provide compelling experimental
1We verified on small datasets that other common measures such as trustworthiness-continuity (Kaski et al., 2003) are also inadequate for evaluating the global structure. Also these measures are too expensive to calculate for moderately large datasets.
results on large natural datasets. We show that t-SNE and LargeVis, which are both based on preserving the pairwise (dis)similarities of the points, tend to form spurious clusters with clean boundaries and fail to properly reflect the global aspects of the data. On the other hand, TriMap’s DR results preserve more of the global structure of the data as well as reveals outliers.

heading: 2 TESTING THE GLOBAL ACCURACY OF DR METHODS
text: Our proposed tests mimic the natural scenarios that happen in the real-world datasets. In each case we run the test on four DR methods: t-SNE, which is currently the most widely used DR method; LargeVis, a more recent method that is also based on pairwise (dis)similarities; TriMap, our new method based on triplet information; and PCA a global method which projects the data onto the two directions of largest variance. We defer the description of t-SNE & LargeVis as well as our new TriMap method to later sections. As a running example, we perform the tests on the MNIST dataset2 which contains 70,000 images of handwritten digits (represented by 784 dimensions)3. We normalized the data to have pixel values between [0, 1] and verified that the results are consistent over multiple runs of all methods. For each embedding, we calculated the area under the mean precision-
2 http://yann.lecun.com/exdb/mnist/
3For ease of comparison, we use the same initial solution for t-SNE and TriMap, whenever possible. The current implementation of LargeVis does not support initial solutions.
recall curve (AUC) (Venna et al., 2010).4 We also calculate the nearest-neighbor classification accuracy for each embedding. The (AUC, NN-Accuracy) values are shown on the bottom of each figure. The main reason for including these local measure in the results is to emphasize the fact that these measures fail to reflect the globally properties of the embedding, discussed in the following. Figure 5(?) shows the results on the full dataset by the four methods.
Partial observation test A DR tool should be invariant to removing a subset of points from the dataset. The placement of the remaining points (or clusters) after running the DR method on the reduced data set should remain relatively unchanged compared to the embedding created from the full dataset. In a first test, the subset of removed points are selected at random. This test mimics the fact that in reality we only see a sample from the data distribution and the DR method should be stable w.r.t. the sample size. Figure 5(2.1.a) shows the results after removing %90 of the dataset at random. t-SNE and TriMap both produce good results in that the clusters of the reduced datasets are located roughly in the same arrangement as in the full dataset. However, LargeVis moves the clusters around (e.g. cluster ‘1’).
For labeled datasets, we might be interested in visualizing a particular subset of the classes, leading to our second test. Figure 5(2.1.b) gives the results on running the methods on just the subset of even digits of MNIST. As can be seen, only the TriMap method is able to preserve the relative distances between all the clusters after removing the odd digits, while t-SNE and LargeVis place the remaining clusters at arbitrary positions.
4More precisely, for each point we fix a neighborhood size of 20 in the high-dimension as the “relevant points” and vary the neighborhood size in the low-dimension between 1 and 100. This gives us a precision and recall curve for each point. The AUC measure is the area under the mean curve for all points.
Outlier test Natural datasets frequently contain outliers due to measurement or experimental errors. Detecting and removing the outliers is key step in statistical analysis that should be facilitated with the DR methods. We can check the ability of the DR methods to reveal outliers by adding artificial outlier points to the original dataset. Figure 5(2.2) shows the DR results after shifting point X (originally placed inside cluster ‘8’ by all methods) far away in a random direction. The point X is clearly an outlier in the new dataset (as verified by the PCA result). Surprisingly, t-SNE and LargeVis both place the outlier inside the cluster ‘3’, which happens to be the nearest cluster to this point in higher dimension. More disturbingly, adding a single outlier this way consistently rearranges the relative location of the clusters for t-SNE and LargeVis. TriMap shows the outlier and preserve the structure.
Multiple scales test A DR tool should be able to reflect the global structure of the data at different scales. For instance, a dataset might consist of multiple clusters where each cluster itself may contain multiple sub-clusters and so on. The practitioner can do a rudimentary test by duplicating and shifting the natural dataset at hand. That is, for each point xn of the original dataset, we add a point xn + c, where c is a fixed random shift which is chosen large enough such that the two copies are guaranteed to be far apart in the high-dimensional space5. When applied on the duplicated dataset, the DR method should be able to show each copy separately. Figure 5(2.3) illustrates the results on a duplicated MNIST dataset. We expect to see two identical copies of the same dataset in the low-dimensional embedding, which can be verified by the PCA result. Curiously enough, both t-SNE and LargeVis fail to provide any meaningful global structure6. In fact, both methods tend to split some of the clusters into smaller sub-clusters. On the other hand, TriMap successfully recovers the two identical copies, which look similar to the original dataset in Figure 5(?).

heading: 3 SKETCH OF THE T-SNE AND LARGEVIS
text: The t-SNE method (Maaten & Hinton, 2008) is perhaps the most commonly used DR method in practice. The main idea of t-SNE is to reflect the pairwise similarities of the points by minimizing a KL divergence between the normalized pairwise similarities in the high-dimensional space and the low-dimensional embedding. The t-SNE method has O(N2) time complexity for N points. However, the complexity can be reduced to O(N logN) by approximating the gradient using treebased algorithms (Van Der Maaten, 2014). t-SNE is easy to apply to general datasets and usually produces nicely separated clusters. Also it has been proven theoretically (Arora et al., 2018) that if the clusters are separated far enough in higher dimension, then t-SNE separates them in the embedding 7. However, as we showed in the previous section, the DR results produced by t-SNE are sometimes extremely misleading: the whole dataset is simply collapsed into an “orb” and the outliers are shown as “inliers”. The latter can be explained by fact that for an outlier point, the pairwise similarities to the points that are closest to the outlier point dominate the rest, causing the method to pull back the outlier point to the closest cluster.
LargeVis is a more recent method (Tang et al., 2016) that also aims to preserve the pairwise (dis)similarities of the points in the high-dimensional space in the low-dimensional embedding. To avoid the O(N2) complexity of t-SNE, LargeVis uses a negative sampling approach (Mikolov et al., 2013) to randomly select a subset of the dissimilar pairs. However, the weights of all the dissimilar pairs are set to a positive constant. This causes the LargeVis to lose global information in the data, as we showed in the previous section. Overall, LargeVis forms well-separated clusters. However, the outlier points that are far away or in-between the clusters are pushed back into the closest clusters. This is a consequence of using a noisy distribution for negative sampling which tends to pick points from the denser regions with higher probability. For example, moving single points that lie between multiple large clusters inside the nearest cluster increases the likelihood of the model (because a single point has a very small probability of being selected as a dissimilar example by any of points that lie inside the large clusters).
5Similar results obtained by shifting the datasets in 4 directions. 6Verified with a large range of the perplexity parameter for t-SNE (from the default of 30 to 150). 7The proof requires that ”early exaggeration” is used in all iterations of training.

heading: 4 THE NEW TRIMAP METHOD
text: The main idea in developing the TriMap method is to preserve a higher-order of structure in the data. In other words, we aim to reflect the relative (dis)similarities of triplets of points, rather than pairs of points. Formally, a triplet is a constraint between three points i, j, and k, denoted as an ordered tuple (i, j, k), which indicates: “point i is more similar to point j than point k”.
Problem formulation Let {xn}Nn=1 denote the high-dimensional representation of N points. Our goal is to find a lower-dimensional representation {yn}Nn=1 for these points (in 2D or 3D). Let p̃ij 0 be a pairwise similarity function between xi and xj in high dimension and q̃ij 0 a similarity function between yi and yj in low dimension. We denote by T be the set of all triplets (i, j, k) where p̃ij > p̃ik, i.e., T = {(i, j, k) : p̃ij > p̃ik}. A low-dimensional embedding can be calculated by minimizing the following objective
min {yn}
X
(i,j,k)2T
!ijk q̃ik
q̃ij (1)
where !ijk is the weight that reflects the importance of the triplet (i, j, k) and the ratio q̃ikq̃ij 0 can be seen as the loss associated with the triplet (i, j, k). Note that as q̃ik becomes smaller and q̃ij becomes larger, the loss approaches zero.
Typically not all the triplets can be satisfied when mapping from high-dimension to lower-dimension, i.e., we cannot have q̃ij > q̃ik, for all (i, j, k) 2 T . The issue arises because of the lower degree of freedom in the low-dimensional space. As a simple example, consider mapping uniformly distributed points on a two-dimensional circle to a one-dimensional line; regardless of the choice of embedding, the end points of line will always violate some triplet constraints. For a highly violated triplet (i, j, k) with q̃ik q̃ij , the triplet loss q̃ikq̃ij will become too large and dominate the loss minimization over all triplets. Thus damping the effect of individual triplets is crucial whenever the triplets are sampled from a high-dimensional space. We use properties of the generalized log and exp functions to define robust versions of the weighted triplet loss:
0 2 4 0
1
2
3 Loss transformation
0 2 4 0
1 Similarity function
We propose the following objective
min {yn}
X
(i,j,k)2T
!ijk logt 1 +
q̃ (t0) ik q̃ (t0) ij
! , (2)
where the logt is defined as (Naudts, 2002):
Note that logt is concave and non-decreasing and generalizes the log function which is recovered at t = 1. Thus Equation (2) includes the logtransformation as a special case (see Figure 2(left, red)). However, for x > 1, the logt function with t > 1 grows slower than the log function and reaches the value 1/(t 1) in the limit x ! 1. Therefore, for t > 1, each triplet can contribute at most 1/(t 1) to the total loss and the objective function of TriMap in Equation (2) is robust to violated triplets.
Also inspired by the good properties of the heavy-tailed distributions for low-dimensional embedding (Maaten & Hinton, 2008; Yang et al., 2009), we define a parameterized similarity function
q̃ (t0) ij = expt0( kyi yjk 2), where expt0(x) = ( exp(x) if t0 = 1 [1 + (1 t0)x]1/(1 t 0) + otherwise. (3)
Here [ · ]+ := max(0, ·). Notice that the tail-heaviness of q̃ (t0) ij increases with the value of t
0. That is, the Gaussian function is recovered at t0 = 1 and t0 = 2 amounts to the Student t-distribution with one degree of freedom. For t0 > 2, we recover distributions with even heavier tails. Figure 2(right) illustrates the q̃(t 0) ij function for several values of t
0. In all our experiments, the default parameters for TriMap were set to t = t0 = 2, but we will briefly explore the other choices in Section 4.
Another crucial component of TriMap is the weight !ijk assigned to the triplet (i, j, k), quantifying the importance for satisfying (i, j, k) (See Appendix C for an experimental justification):
!ijk := p̃ij
p̃ik , where p̃ij = exp(
kxi xjk 2
i j ). (4)
The scale factor i is set to the average distance of xi to its 10-th, 11-th, . . . 20-th nearest-neighbors. This choice of i adjusts the scale of p̃ij to the density of the data (Zelnik-Manor & Perona, 2005).
Triplet sampling For N data points, the number of triplets is O(N3). Thus the minimization of (2) with all the possible is too expensive. However, in practice, there exists a large amount of redundancy among the triplets. For instance, the two triplets (i, j, k) and (i, j, k0), in which k and k0 are located close together, convey the same information. We now develop a heuristic for sampling an O(N) size subset of triplets, such that the mapping produced from the subset essentially reproduces the mapping derived from all triplets (evidence not shown for lack of space). We sample two types of triplets to form the embedding.
Nearest-neighbors triplets: For each point i, the closer point j is selected from m-nearest neighbors of the point and the distant points are sampled uniformly from the subset of points that are farther away from i than j. Note that this choice of triplets reflect the local as well as the global information of the data. For each point in the set of m-nearest neighbors, we sample m0 distant points which results in N ⇥m⇥m0 triplets in total. In all our experiments, we use m = 50 and m0 = 10.
Random triplets: These triplets are sampled uniformly at random from the set of full triplet set T . Random triplets help preserve the global structure of the data. We add s randomly selected triplets for each points, which results in N ⇥ s triplets in total. In all our experiments, we set s = 5.
The overall complexity of the algorithm is bounded by the nearest neighbor search step, which for e.g. Nearest-Neighbor-Descent (Dong et al., 2011) has been shown empirically to have O(N1.14) complexity. However, after the nearest-neighbor calculation step, we achieve linear complexity. In practice, dividing each ratio p̃ijp̃ik at the end by the maximum ratio among the triplets in the set of sampled triplets and adding a constant positive bias > 0 to all ratios improves the results. In all our experiments, we set = 0.001.
Effect of changing t and t 0 We show the effect of changing the parameters t and t0 in Figure 3. The experiments are performed on the USPS Digits dataset 8. In the first set of experiments, we fix t = 1 (i.e. use log-transformation) and increase the value of t0 = 2 (i.e. the tail-heaviness of the similarity function). It is clear from the results that having heavier-tail provides more separability but cannot fix the clutter introduced by the unsatisfied triplets. Next, we fix the similarity function to Student t-distribution (t0 = 2) and increase the value of t for the logt-transformation. Value of t = 0 corresponds to no transformation (Equation (1)) and t = 1 recovers the log-transformation. Note that larger values of t provides denser clusters and more separate clusters and reduces the clutter introduced by unsatisfied triplets. We use t = t0 = 2 in our experiments.

heading: 5 EXPERIMENTS
text: We evaluate the performance of TriMap for DR on a number of real-world datasets and compare the results to t-SNE and LargeVis9. We also compared our results to triplet embedding methods such as STE (van der Maaten & Weinberger, 2012). However, the results were clearly inferior and are omitted due to space constraints. The code for TriMap as well as the datasets for the experiments are available online10. In all our experiments, we use the default values t = t0 = 2. All experiments are performed on a single machine with 2.6 GHz Intel Core i5 processor and 16 GB RAM. We provide DR results on six datasets:
i) Epileptic Seizure Recognition11: contains 11,500 EEG recordings of patients under 5 different conditions. Each data point is one second of measurements with 178 samples / dimensions. ii) Tabula Muris12: contains 53,760 samples from 18 different mouse tissues in 23,433 dimensions. iii) Fashion MNIST13: consists of 70,000 examples. Each example is a 28⇥ 28 gray scale image (784 dimensions) from 10 classes of clothing items. iv) TV News14: contains audio-visual features extracted from 150 hours of TV broadcast from 5 different TV channels. The dataset contains 129,685 instances, labeled as commercial/non-commercial, and 4120 features. v) 380k+ lyrics15: the dataset contains lyrics of 380k+ different songs, gathered from http: //www.metrolyrics.com. We first form a weighted co-occurrence graph for the words based on the frequency of the pairs of words which occur together in a sliding window of length 5 words. Next, we compute the representation of each word using the LINE method Tang et al. (2015). We use number of negative samples equal to 5 and a learning rate of 0.025 with number of training samples equal to 1000M. We map each word to a 256 dimensional vector and then, calculate the representation of each song by a weighted average of the words that occur in the song. After removing the stop words and the songs with no available lyrics, we get 266,557 instances. vi) DBLP collaboration network16: the collaboration network of 317,080 authors. Two authors are connected in the network if they publish at least one paper together. We use LINE to find a 256 dimensional representation of the network before applying the methods. We set number of negative samples to 5, the learning rate to 0.025, and the number of training samples to 3000M.
In our experiments, we use the sklearn implementation of fast t-SNE with the default parameters and learning rates. For LargeVis, we use the official implementation17 with the default setting of the learning equal to 1.0 and number of negative samples equal to 5. For TriMap, we reduce the
8 https://cs.nyu.edu/˜roweis/data.html
9Recently, a new DR method called UMAP was proposed by McInnes & Healy (2018). Although the running time of UMAP is comparable with TriMap, we did not include the UMAP results for two reasons: 1) the method is only described in an arXiv paper, 2) despite the different motivation, the results are strikingly similar to the LargeVis reported here.
10 https://github.com/ANONYMOUS/trimap 11 https://archive.ics.uci.edu/ml/datasets/Epileptic+Seizure+Recognition 12 https://github.com/czi-hca-comp-tools/easy-data/blob/master/datasets/
tabula_muris.md
13 https://github.com/zalandoresearch/fashion-mnist 14 http://archive.ics.uci.edu/ml/datasets/tv+news+channel+commercial+
detection+dataset
15 https://www.kaggle.com/gyani95/380000-lyrics-from-metrolyrics/data 16 https://snap.stanford.edu/data/com-DBLP.html 17 https://github.com/lferry007/LargeVis
dimensionality of data to 100 if necessary, using PCA and apply ANNOY18 (a random projection based approximate nearest neighbor search method) to calculate the nearest neighbors. However, in some cases the random projection based nearest neighbor search fails to correctly estimate the nearest neighbors of outlier points. This can be resolved by finding a small number (typically 5) of nearest neighbors using the Balltree algorithm and combining the results with ANNOY. Further details and hints are provided in our implementation available online. We use m = 50, m0 = 5, and s = 5 for all datasets. The optimization is done with batch gradient descent and adaptive learning rate.
Figure 4-i) illustrates the results on the Epileptic Seizure Recognition dataset. TriMap shows a smooth transition between measurements under different conditions while both t-SNE and LargeVis fail to preserve the global structure. Figure 4-ii) shows the results on the Tabula Muris dataset. As can be seen, TriMap reveals multiple outlier points which are not recovered using t-SNE and LargeVis. These outlier points can be verified by considering the ratio of the average distance of the top 5% farthest points from the center of the dataset to the average distance to the center of the remaining points. The actual ratio in high-dimensions equals to 5.32 where in low-dimension, equals to 1.50, 1.02, and 1.95 for t-SNE, LargeVis, and TriMap, respectively. The results on the Fashion MNIST dataset are shown in Figure 4-iii). t-SNE and LargeVis tend to create many spurious clusters. For instance, the cluster of “Bags” is divided into multiple smaller sub-clusters. On the other hand, TriMap represents a smooth embedding where each class in concentrated around the same region and there appears to be a smooth transitions among different classes. Figure 4-iv) shows the results on the TV News dataset. Bothe t-SNE and LargeVis tend to produce several patches of points that do not have a clear structure. TriMap on the other hand shows a smooth transition between the two classes with a few outliers that are present around the main cluster. Figure 4-v) shows the results on the 380k+ lyrics dataset. We use the 50 clusters in the high-dimensional space found by the k-means++ algorithm as labels. Unlike the other two methods, TriMap reveals multiple layers of structure with several outliers in the dataset. The main cluster that is shown both by t-SNE and LargeVis is also shown in the center of the map with TriMap. Finally, Figure 4-vi) shows the results on the DBLP dataset. As labels, we use the 50 clusters in the high-dimensional space found by the k-means++ algorithm. The results of LargeVis and TriMap are comparable. However, LargeVis tends to create more small clusters by grouping the outlier points that are close together.
Finally, the runtime of the methods is shown in Table 5. TriMap is consistently faster than t-SNE and in some cases, outperforms LargeVis in terms of runtime. The main advantage of TriMap is evident on dataset with very large number of dimensions.

heading: 6 CONCLUSION
text: Dimensionality reduction will remain a core part of Machine Learning because humans need to visualize their data in 2 or 3 dimensions. We formulated a number of transformations and outlier tests that any practitioner can use to test the visualization method at hand. The main existing methods dramatically fail our tests. We also present a new DR method that performs significantly better. This new method called TriMap is based on triplet embedding but otherwise incorporates a number of redeeming features employed by the predecessors such as the use of the heavy tailed distributions and sub sampling for obtaining linear time complexity (after the nearest-neighbor calculation step). Our results on wide range of datasets are quite compelling and suggest that further advances can be made in this area. Our next goal is to apply TriMap to data domains where we can test the quality of the obtained visualization and outlier detection by further physical experiments.
18 https://github.com/spotify/annoy

heading: A RELATION TO T-STOCHASTIC TRIPLET EMBEDDING
text: One of the commonly used methods to find low-dimensional representation of a set of items using only triplet information is the t-Stochastic Triplet Embedding method (t-STE) (van der Maaten & Weinberger, 2012). We show here that t-STE is a special case of our method when the temperatures defining our loss is chosen non-optimally and no weighting of the triplets is used.
Given a set of triplets T = {(i, j, k)} over N items, the goal of t-STE is to find an embedding {yn} N n=1 in the low-dimensional space such that the following relation holds with high probability:
kyi yjk  kyi ykk , for each (i, j, k) 2 T .
Let q̃STEij 0 denote the similarity function between yi and yj . In t-STE, the similarity function is chosen to be a Student t-distributions with ↵ degrees of freedom, that is
q̃ STE ij = 1 +
kyi yjk 2
↵
1+↵2 .
Note that this similarity function is a special case19 of our similarity function q̃(t 0)
ij (defined in Equation (??) with temperature t0 = 3+↵1+↵ , where all the instances are scaled by a constant
20 factor 1+↵2↵ . The satisfaction probability of the triplet (i, j, k) is defined as
Prijk = q̃
STE ij
q̃STEij + q̃ STE ik
= 1
1 + q̃STEik q̃STEij
.
Notice that Prijk ! 1 whenever q̃STEij qSTEik . In t-STE, the low-dimensional embedding is computed by minimizing the sum of negative log-probabilities over all triplets
min {yn}
X
(i,j,k)2T
log Prijk = X
(i,j,k)2T
log 1
1 + q̃STEik q̃STEij
= + X
(i,j,k)2T
log1 1 +
q̃ STE ik q̃STEij .
The above rewrite of t-STE’s objective shows that it is a special case of our loss (2) with temperature t = 1 and when all triplet weights !ijk are set to one. As we discussed in Section 4, the ratio
q̃STEik q̃STEij
may be seen as the loss of the triplet (i, j, k). The transformation log(1 + q̃ STE ik
q̃STEij ) used in the t-STE
objective reduces the effect of each triplet21. However for t = 1, the effect of each individual triplet is still unbounded and the method becomes too outlier dependent. This can be verified by the results in Figure 3 where t-STE (with additional triplet weights) corresponds to (t = 1, t0 = 2) whereas our default temperature choice is (t = 2, t0 = 2). Note that by choosing t > 1, the loss of each individual triplet becomes bounded by 1/(t 1), and therefore the total loss becomes more robust to unsatisfied triplets.

heading: B DR TESTS FOR PHATE, UMAP, AND T-STE
text: In this section we provide the results of the DR tests introduced in Section 2 for the following additional methods: PHATE (Moon et al., 2017), UMAP (McInnes & Healy, 2018), and t-STE (van der Maaten & Weinberger, 2012). Note that t-STE was originally used for finding a low-dimensional embedding for a set of item based on a set of triplet comparisons when the high-dimensional representation was unknown. The results on the DR tests are given in Figure 5. Note that based on the discussion in Appendix A, t-STE corresponds to the special case of TriMap where (t = 1, t0 = 2) and all weights are set to 1.0.
The results on the original dataset are shown in Figure 5.?. Note that t-STE shows many factitious outliers in between, or even away from the clusters. This phenomenon becomes worse as the size of
19Vanilla STE with Gaussian similarities is also a special case where t0 = 1. 20For ↵ = 1, this corresponds to t0 = 2 (our default) and the scaling disappears. 21The log(1 + ·) transformation has been used in the context of ranking to reduce the effect of individual
losses on the overall ordering Yun et al. (2014).
the dataset is decreased (Figure 5.2.1.a). UMAP performs well on the 10% subset, however, PHATE splits the cluster of 6’s. On the subset of even digits, all the methods perform well. However, t-STE again introduces many factitious outliers. Figure 5.2.2 shows the effect of adding an outlier point (marked with X). Except for TriMap, all the other methods fail to reveal the outlier. In fact, all other methods pull the outlier into (the closest) cluster. Finally, the result of copying and shifting the dataset is shown in Figure 5.2.3. PHATE, TriMap, and t-SNE successfully display the two copies. However, the quality of each copy deteriorates in the embedding created by the PHATE method. Also, t-STE again introduces many factitious outliers. Finally, the result for UMAP is similar to the LargeVis method; the clusters of each copy is preserved, however, the relative distances between the clusters are totally lost.
In summary, we are not aware of any DR method that is competite with TriMap on our tests for global accuracy. Also the (AUC,NN-Accuracy) numbers reported in Figure 5 are not helpful.

heading: C THE EFFECT OF WEIGHTS, TRIPLET TYPE AND NUMBER OF TRIPLETS
text: Recall that TriMap picks m⇥m0 triplets per point in the dataset, where m is the number of nearest neighbors and m0 are distant points. We also add s random triplets per data point. In this section we show the effect of changing these parameters as well as the effect of weighting the triplets (as defined
in (4)). Recall that TriMap uses these weights and default values m = 50, m0 = 10 and s = 5. We conduct the experiments on the USPS dataset.
Figure 6 shows the effect of changing the number of nearest-neighbors m while fixing the number of distant points m0 = 10 and number of random triplets per point s = 0. We show the results with and without triplet weighting, i.e. for experiments with unweighted triplets, we set !(i,j,k) = 1 for all (i, j, k) 2 T . As can be seen, for weighted triplets, increasing the number of nearest neighbors consistently improves the results. However, using unweighted triplets introduces multiple factitious outliers. Additionally, when using unweighted triplets, increasing m does not improve the results as much.
Figure 7 shows the results where number of nearest neighbors m = 10 and random triplets per point s = 0 are fixed and the number of distant points m0 is varied. Again, we repeat the experiments with and without assigning weights to triplets. In the weighted case, increasing m0 also improves the results. However, the improvement gained by increasing m0 is not as much as increasing m. This is due to the fact that many triplets are required to capture the local structure around every point. However, the global structure of the data can be explained by a smaller number of triplets.
Finally, Figure 8 illustrate the result of adding randomly generated triplets. We fix m = 5, m0 = 10 and vary the number of random triplets per point s. We repeat the experiments with and without assigning weights. As can be seen, in the weighted triplet setting, adding randomly generated triplets introduces more global structure into the embedding. However, this does not hold for unweighted triplets.
In conclusion, assigning weights to the triplets is a crucial piece in obtaining good low-dimensional embeddings of the data. Without adding weights, we may need much larger number of triplets to achieve similar performance as the weighted case. Additionally, exploring larger number of nearest neighbors provide more information about the local structure of the data whereas the global structure is explained by a fewer number of distant points. Additionally, a small number of randomly generated triplets improves the global structure of the embedding.

heading: D ADDITIONAL EXPERIMENTS SHOWING ON MANIFOLD DATASETS
text: In this section, we show experimental results on datasets with known underlying low-dimensional manifolds. Our datasets include: 1) 3-D Sphere dataset22, which contains 1000 points uniformly sampled from a unit sphere, 2) Swissroll dataset23, which is a 2-D rectangle (1500 points) curved rolled into a 3-D shape, and 3) ISOMAP Faces dataset24, which consists of 698 synthetically generated 128⇥ 128 face images in different pose and lighting. We show the runtime of the t-SNE, LargeVis, and TriMap on these datasets in Table 2. One major point we noticed during our experiments is that LargeVis performs very slow on: 1) small datasets (see Table 2), and 2) datasets with large number of dimensions (Table 1, TV News). The former could be an implementation issue while the latter is due the random projection step for nearest neighbor search. Note that we perform PCA as a step in our algorithm to accelerate the nearest neighbor search (also used in the original t-SNE implementation). The error induced by the PCA step is negligible compared to the error of mapping from high-dimension to 2-D or 3-D. We can also accelerate LargeVis on large dimensional datasets by performing the PCA step (although it is not part of the original algorithm). However, the performance on small datasets still remains slow.
Figure 9 shows the results of t-SNE, LargeVis, and our method, TriMap, on the Sphere and the Swissroll datasets. As can be seen, TriMap successfully preserve the continuity of the underlying manifold in both datasets. On Sphere dataset, the TriMap visualization corresponds to pulling the 3-D sphere along the diagonal and collapsing it on 2-D. On Swissroll dataset, note that TriMap preserves the curvature of the original dataset; the end parts of the rectangle (colored in dark blue and yellow) are actually closer in the original 3-D space (compare this to the result of LargeVis). In Figure 10, we illustrate the results of t-SNE, LargeVis, PCA, PHATE, UMAP, and our method, TriMap, on the ISOMAP faces daatset. PHATE, PCA, and TriMap uncover the curvature on two end-points of the underlying manifold where the sets of darker images having different poses are located. These darker images (having different poses) are intuitively closer to each other in the high-dimensional space than their brighter counterparts.
22 https://research.cs.aalto.fi/pml/software/dredviz/ 23 https://www.mathworks.com/products/demos/machine-learning/swiss_roll/
swiss_roll.html
24 http://web.mit.edu/cocosci/isomap/datasets.html

Review summaries:
In this paper, the authors present a novel dimensionality reduction method named TriMap. TriMap attempts to improve upon the widely-adopted t-SNE algorithm by incorporating global distances through the use of triplets, rather than pairwise comparisons. The authors compare to t-SNE, as well as a newer method called LargeVis which also claims to impose a global distances metric. The authors show that their method is more robust to the addition or removal of clusters and outliers and provides a more meaningful global distance relative to the methods against which they compare.