MAP IT to Visualize Representations
Authors: Robert Jenssen
Venue: ICLR 2024 poster (2024)
Keywords: Visualization; Representation learning; Dimensionality reduction; Divergence
Primary area: visualization or interpretation of learned representations
TL;DR: MAP IT is a new method for visualization by dimensionality reduction using a projective divergence measure as cost function

Abstract: MAP IT visualizes representations by taking a fundamentally different approach to dimensionality reduction. MAP IT aligns distributions over discrete marginal probabilities in the input space versus the target space, thus capturing information in local regions, as opposed to current methods which align based on individual probabilities between pairs of data points (states) only. The MAP IT theory reveals that alignment based on a projective divergence avoids normalization of weights (to obtain true probabilities) entirely, and further reveals a dual viewpoint via continuous densities and kernel smoothing. MAP IT is shown to produce visualizations which capture class structure better than the current state of the art while being inherently scalable.

Published as a conference paper at ICLR 2024
MAP IT TO VISUALIZE REPRESENTATIONS
Robert Jenssen UIT The Arctic University of Norway & U Copenhagen & Norwegian Computing Center
ABSTRACT
MAP IT visualizes representations by taking a fundamentally different approach to dimensionality reduction. MAP IT aligns distributions over discrete marginal probabilities in the input space versus the target space, thus capturing information in wider local regions, as opposed to current methods which align based on pair- wise probabilities between states only. The MAP IT theory reveals that alignment based on a projective divergence avoids normalization of weights (to obtain true probabilities) entirely, and further reveals dual viewpoint via continuous den- sities and kernel smoothing. MAP IT is shown to produce visualizations which capture class structure better than the current state of the art.
INTRODUCTION
Representation learning is key to any machine learning system. For instance for learning to visu- alize input representations, or for visualizing learned representations obtained e.g. via deep neural networks trained in supervised or umsppervieed/sslllssupevvssss manner in order to gain insight"
Methods such as t-SNE (Böhm et al. [023 Tucker et al. 2023 Huang et al.] [2022] van der Maaten &
Hinton 2008 van der Maaten (2014), the closely related Large Vis (Tang al.] (2016), well as the
recently proposed UMAP (Meinnes et al. 2020). TriMAP (Amid & Warmuth, (219)) and PacMap
(Wang et al. [02TT, + tremendously important contributions, spurring numerous theoretical works,
e.g. (Draganov et al. 2023 Damrich & Hamprecht 2021
Kobak & Linderman 2021).
However, these dominant dimensionality reduction (DR) methods (further discussed in Appendix A) take vastly different theoretical approaches, but despite this diversity, none of the theories provide framework which explain when normalization of weights is needed and when not. Understanding the role of normalization in DR has been an important quest (Draganov et al.) 2023). Moreover, all existing methods are based on pairwise comparisons of weights the input space and the target space without considering wider information from local regions.
MAP IT represents a major shift. The MAP IT framework is based on information theory (IT) and statistical divergences, showing that normalization is not needed when the divergence used projective. Based on a Cauchy-Schwarz projective divergence, MAP IT aligns distributions of marginal probabilities which capture information about wider local regions in the data, in essence aggregating information from pairwise weights in a new manner. A dual viewpoint to MAP IT is derived via continuous densities enabled by kernel smoothing. revealing the role of neighborhoods for the gradient- based MAP IT. See Appendix B for all proofs with additional comments.
MAP IT creates overall markedly different embeddings. As example, Figure I shows MAP IT embeddings of a subset of MNIST (d) compared to t-SNE (a), UMAP (b) and PacMAP (c). MAP IT separates four of the classes of digits much clearer than any of the other methods. For the challenging digits 4, 9 and 7 (rectangles, zoomed), MAP IT creates less overlap between 4s and 9s, and much better separation of 7s (f) compared e.g. PacMap (e).
The main contributions of this paper are i) Providing a new theory for visualization by dimension- ality reduction; ii) Showing that normalization of weights obtain true probabilities is not needed in MAP IT by the use of projective divergence; iii) Revealing a dual viewpoint by aligning over distributions over discrete marginal probabilities equivalently via continuous densities enabled by kernel smoothing; iv) Shedding light on the role of local neighborhoods for the MAP IT update rule; v) Generating markedly different visualizations compared to the current state of the art.
To prepare the representations for downstream task also he of interest but not considered here.

---

Published as a conference paper at ICLR 2024
(a) (-SNE.
(b) UMAP.
(c) PacMap.
(d) MAP IT.
(e) Zoomed PacMap.
(l) Zoomed MAP IT.
Figure I: Visualizing a subset of MNIST. MAP IT separates digits much more distinctly compared to the alternatives and creates less overlap difficult classes shown when zooming in (rectangles).
T-SNE FRAMEWORK
t-SNE minimizes the Kullback-Leibler (KL) divergence between joint probability distribution P over states given by Zi...., Fn E R, in the high-dimensional input space and joint probability distribution Q over states (mapped data points) 2i...., 2n E R in the low-dimensional target space
arg min KL(PI[Q) arg min $1 EBRa
Σ Pis log i.j
Pij
arg min
-- Pij log 4ij 1
(1)
#1 21....,.. EBA
4z BL ERa
where Oiy [1 ||2 2-|1 Zzg are joint probabilities in the target space defined by the t-distribution (Cauchy distribution) and where Zy = En.m + || =m - is an explicit normalization factor. Note that for this particular choice, one may write qs 2z where du [ z - 1,| is an unnormalized quantity. To better prepare for the theory outlined in Section 3 the model Pij = exp [-ma]la;; 2,)1²) /Zp will be assumed, with the normalization factor 4p En... exp(-kil [ 2m (further discussed in Appendix C).
Proposition 1. [Minimizing (L(P))Q) and the role of normalization). Let qiş = ãig Z for some choice of âig where Zy E qnm- Then
arg min KL(P[IQ) ERy
arg min
Σ b
Piy log qií + log Σ Irom
En ERa
7L,77
Comment to Proposition 1 The t-SNE cost function may by this result be expressed both over probabilities Pt, and over quantities Üs low dimensional space which are not probabilities as they are not normalized This also carries over to the expression for the gradient of KL(P)IQ):
Some interesting properties of the t-SNE cost function related to Laplacian eigenmaps may he highlighted when inserting the explicit form for ăg. This is explored in Appendix A.
2

---

Published as a conference paper at ICLR 2024
Proposition 2. [Gradient of (L((1)) (L(PIQ) - = 4 (pis (1)) zi).
i 0z:
The role of normalization. In t-SNE, gradient descent can only be performed after computing dij over the entire data set for each iteration or epoch, and can be interpreted as an n-body system of attractive forces and repulsive forces. Speeding up these computations is the reason for the devel- opment of the Barnes-Hur tree algorithm (van der Maaten 2014) or the more recent interpolation- based t-SNE (Linderman et al.) 2019). The requirement for normalization also hampers the utility of parametric t-SNE (van der Maaten 2009) as discussed in (Sainburg et al. (021). Recently, new
algorithms and insight normalization have been revealed (Artemenkov & Panov 2020 Damrich
et al. 2023) from the viewpoint of noise contrastive learning (Gutmann & Hyvärinen] 2012). also in
the context of the interplay between attractive and repulsive forces (Böhm al. 2022).
Brief perspectives on t-SNE, UMAP, PacMap and variants. A number of new dimensionality reduction methods have been proposed, most being more computationally efficient than t-SNE, usu- ally ending up as system of attractive and repulsive forces. UMAP (McInnes et al. 2020) exploits cross-entropy between simplical sets and invokes a sampling strategy on repulsive forces which has resemblance the approach proposed in Large Vis (Tang et al. 2016) (a method inspired by t-SNE). TriMAP (Amid& & Warmuth| 2019) and PacMap (Wang et al. (221)) are heuristic methods where the former is based triplet loss and the latter empirically sets up cost function based on pairwise distances between near pairs, mid-near pairs, and non-neighbor pairs. These methods are considered to be leading approaches, elaborated in more detail in the Appendix A
MAP IT FRAMEWORK
3.1 MAP IT BY THE CAUCHY SCHWARZ DIVERGENCE
SNE elegantly formulated in terms the KI. divergence. However, the KI. divergence requires normalization factor since the KI. divergence is not projective.
Definition (Projective Divergence). Let Pij Pig/ and qi - where Zp Σn Pum
and Zg En From are normalizing constants. This means that P P/Zp and Q = Q/Zg. A projective divergence is such that
D(PIIQ)=D(PP))
(4)
where D is the divergence measure.
For optimization purposes, the use of projective divergence function may be appealing since the direct dependence on normalization constants is removed. A divergence measure which has received widespread attention in recent years is the Cauchy-Schwar divergence (Yu et al. 2023
2022 Principe 2010 Jenssen et al. 2006).
Without loss of generality, the CS divergence is here defined in terms of marginal probabilities P(x;)) = in the input space and P(z,) = zj in the target space, respectively.
Definition 2 (CauchySchwaal (CS) Divergence). Denote Pm = {pr) and Qm {ail
Then
Σ 3
CS(P Qm. = - -log
(5)
7
Σ E
Σ
of
'A plethora of dimensionality reduction variants exist, see e.g. the overview
Wang al. 2021 or visit the E-SNE and the other methods
excellent repository hhttps://]] mm 1 ee. ee.gitttil wwt.. iic.bb.oo.. /0/ smal 1 1 vv mentioned here all use gradient descent but build on many aspects from spectral theory, e.g. (Roweis & Saul 2000). (Tenenbaum et al. 2000). (Belkin & Niyogi 2003). (Donoho & Grimes
2003). (Jenssen 2010))
*Coud equivalently be defined with marginal probabilities = 4. 2n bility functions q(z) (7.)/7n. 7g
Gt. or continuous proba-
((z)dz (likewise for p.x)
3

---

Published as a conference paper at ICLR 2024
Proposition 3. /CS divergence is projective). Let Pj -p//pp. Zp Eg Py,, and 9j 4z/Zuy 7 Ez 4z. Then
(6)
The CS divergence will provide the backbone for the MAP IT framework. MAP IT will be derived both from the viewpoint of marginal probabilities and from the viewpoint of continuous risk func- tion. The latter provides a coupling to kernel methods which provides a dual framework. MAP IT's cost function lends itself nicely to optimization with gradient descent, explained in the next sections.
3.2 MAP IT VIA MARGINAL PROBABILITIES
By the law of total probability Pj Σ Pik and q = Ex Ujk- Since Pit and ljk are assumed normalized (Eq. 11). ). E, Pj and 2, = Note that by this argument one may express = iz/Zg. where Oj Σ. ljk. Zg = E m.m Ium. and likewise for pj.
Definition 3 (MAP IT cost function), Let P. = Σx P5k and 0J = Ex Ojk. The proposed MAP IT cost function and optimization problem
arg min CS(Pm 1Qm) (mmm) Sn ERa
arg min CS(Pmm1Q@m 2n EBa
(7)
Comment to Definition A major deviation from the SNE framework that MAP IT aims to align distributions over marginal probabilities for states corresponding to data points in the two spaces, i.e. Pj and qj- These probabilities can be interpreted as degrees associated with the nodes of the underlying similarity graphs in the two spaces, reflecting properties of regions of the data, as opposed to considering only pairwise local connections. This is associated with the underlying mapping which may be expressed as 2, = m(xx) + where m(-) the mapping function and Ey is some noise random variable. Minimizing (mm114mm) yields:
Proposition 4. [Minimizing CP Qm)) with respect 21...., Zn E Raa]
arg min Rn CB3
CS(Pm I(@m) arg min ERR
log Σ p + log Σ
(8)
As main result of this paper, the gradient of MAP needed in order perform minimization of CSS(Pn) Pm 1m) over 21,..., 2n E a, is derived and stated in the following proposition: Proposition 5. [Gradient of C5((mll(mm)
i CS(Pp (l -4 Σ
D3
/
d 22)) 21).
(9)
dz.
Σ
Q3
Σ
9
Comment to Proposition
4
The MAP IT update rule z;
2; 11 0
11.z.
CS(Pm (l yields
2: = 2i +1) Σ
P
P2 - 2i)
(10)
Σ Py
where the factor has been fused into 77. MAP IT thus has easily interpretable gradients, forming a n-bodd problem where each z; experiences an attractive force 인J and a repulsive force i from each other data point zj. The forces are adaptively weighted by entropy in the sense that log Σ,- o is a Renyi entropy of Qm and - log En; Ty is cross entropy. All quantities are unnormalized.
3.3 MAP IT VIA CONTINUOUS DENSITY FUNCTIONS
This section provides an alternative derivation for MAP IT via kernel smoothing. This reveals the role of local neighborhoods via derivation, affecting the computation of gradients. The following definition is provided, referred here to as the map CS divergence:
4

---

Published as a conference paper at ICLR 2024
Definition 4 (Map CS divergence). Let p(x) be the probability density function over domain X and define g(z) to be the probability density function for the stochastic map x = m(x) + E over Z.
Let f(x, z) be the joint distribution over X x Z. The map CS divergence is defined
J p(z 2d)dz
C((p(x))lg(2)) -log
(11)
()) (JJ (2)= dxxdz))
Comment Definition Consider two functions g(z) and h(z) where some mapping of
2. Within risk minimization, R = Exxz h(z) = [ [g(x)) h(z) f(x 2 ddxdz for some loss I(-). Empirical risk minimization aims to minimize R E, L (g(x), h(z)) with respect to some variables or parameters. From this, the map CS divergence may be understood as normalized risk function over (ax) p()) and h(z) = ((z) with product loss.
Proposition [The map CS divergence is projective). Let z m(x) + E and assume p(x) DZp and q(2) = 2( where p(x) and ğ(z) are unnormalized with Zp p(x) and Zg = f ((() dz as the respective normalization constants. Then
CS(p(z))lg(z)) = CCSp(=))l(()))
(12)
Assume in the following unnormalized functions ç(xx) and ((z).
Proposition 7. [Empirical map CS divergence]. Let a sample æı...., En E Rn be given and assume the mapping = m(x) + e. Then, an empirical map CS divergence given by
Σt(e))((z))
(S(p(=))l((2)) -llog
(13)
(
Σ 3
Proposition 8. [Minimizing CS(p(x))lg(x)) with respect to 21...., nn E Rd]
arg min CS(p(z))l((z)) arg min - log > ((2))](21) + 2 EnE
log Σ q2 (zz).
(14)
En
Proposition |Gradient of (S(p()))lu(=)))
f(x,)
((z,)
θ 0z, ((zz).
dz. (S((t)))((z))=
= Σ 3
(15)
Σ Ena ((
Σ 7
Comment to Proposition 9 Eq. (15) is a more general result compared to Eq. (9). For a particular
choice or estimator of p(xr)) and ((2z). ), the basic MAP IT update rule z; 2, 13s. CS Qm)
will equal z; 2, 1) nzz Cp(((x) [q(2)) as is shown next. But this is not true in general, and the latter result may actually be more flexible.
Consider in the following the choice f(=,) Ee Kz, zg) and similarly for ((xr)). In this viewpoint, xc()) is assumed to be a shift-invariant kernel function and Σg (2 - 2x) is the well- known kernel smoothing procedure, which is the backbone of reproducing kernel Hilbert space methods (e.g. (Schrab et af. (023)) and of utmost importance in machine learning. Note that both the t-distribution (Cauchy distribution) and the Gaussian are valid kernel functions.
Proposition 10. [Gradient of Cp(((x)) [[{())) with kernel smoothing). Let q(z,) =E Kz(2z 2x) and j(xr,) = Ee (2 - wx) for shift- invariant kernel functions kz(.)) and (.).). Then
0 CS(p(=))l((2)) -4
D;
1 2
2:) zz).
(16)
0z,
Σ
5

---

Published as a conference paper at ICLR 2024
K- (A)+MAA))
(a)
(b)
(c)
Figure 2: Illustrating the role of local neighborhoods in MAP IT.
With the notation Tja def K2 z;) associated with ((z,) Ee Kz(zj - zx), this result shows that in this particular situation the MAP IT rule z; 2;
Comment to Proposition 10
1oz, CS(PmllQm)) equals 2; 2; T82.
8 (S(p(())ll((z))
MAP IT via marginal probabilities and MAP IT via continuous densities thus dual viewpoints enabled by the map CS divergence and the kernel smoothing approach.
Having derived MAP IT, it is important make clear that t-SNE based the Cauchy-Schwan divergence, instead of the Kullback-Leibles appears as special case of the theory.
(CS) t-SNE a special case of MAP IT). Let Pys be the prob- ability for the joint event T. O øk- Let Ojk' be the probability for the joint event 2j Zk- (x, O (g) ) n (zj O zx)) E 0, then
Proposition 11.
(S(Pmll@m)=CS((P)) =
(17)
3.4 MAP IT VIA LOCAL NEIGHBORHOODS
One subtle but very important aspect which affects the MAP IT theory from the previous sections concerns the role of local neighborhoods. This is best revealed from the starting point of MAP IT via continuous densities as follows. The aim of MAP IT is to discover ......, 2n E IR, from F1..... In RD. This entails derivatives 0z, p(-)(()) and 02.9 g-) which are quantities defined over neighborhoods. Consider
R p(z, p(z,+ Áz,)(zz + Az,) - p(z.)((z;)
0z, ,2 7()7(-
(18)
Az;
where Az; defines a neighborhood in the target space around 2,, A sketch illustrating this situation
shown in Fig. (2 (a). However, an assumption that an unknown transformation exists, m(x)+ +e. If the transformation was known, there would be no need for MAP IT and neighborhoods
Az, around z; would correspond to neighborhoods Az; around x; m 10- (zz)). However, even the transformation is not known, points in the two spaces come in pairs the course of the optimization neighborhood topologies in the two spaces should start to correspond. During the optimization, since the effect of the underlying mapping function only gradually will be learned, neighborhood topologics in the two spaces will not initially correspond. For differentiation with respect to z, must therefore rely Az, m( (Ax). This is illustrated in Fig. (2) (b).
m((x;) + E, and over
The practical consequence of the above analysis is that all marginal probabilities, part of the MAP IT learning rule, will be computed with respect to neighborhood m(Ax,) and will be denoted Pine, and lix., respectively, where Nr. refers to the neighborhood around æ;, yielding
Pina: Σ 9r Σ 3'
aine:
2, = 2i
7i
Σ 3
22 x.).
(19)
One may envision several possibilities for defining N Here, it is argued that if xy is of the nearest neighbors of x; then the nearest neighbors Φy are also i the neighborhood of æ, The Pine; and lix., are thus computed over the nearest neighbors of æ... Of course, this line of thought

---

Published as a conference paper at ICLR 2024
(a) Run 1.
(b) Run 2.
(c) Run 3.
(d) Run 4.
Figure 3: MAP IT for subset of MNIST for different initial values (runs) for k 10.
could have been continued some degree (neighbors of neighbors), but is not explored further in this paper. Fig. (2) (c) shows as a filled black square a point æ; (z,) and how the nearest neighbors of æ; as well as their neighbors constitute Na.- This resembles some degree the use of near pairs and mid-near pairs in PacMap. For points that are not neightbors of one could compute Pin,, and Liv,, in a similar manner. However, since all Pij for zj not neighbor of æ; will be relatively small and constant with respect points in the vicinity of 2;, only Pij (9tz) is used in that case, as illustrated in Fig. 2 (c) (solid black circles). This resembles to some degree the use of non-near pairs in PacMac. Please see Appendix C for additional perspectives. Finding neighbors can be done in an exact manner, or by vintage trees YYanilos 1993), or by approximate search (Dong et al. 2011 as in Large Vis and UMAP.
Importantly, the MAP IT theory deviates fundamentally from the theory for I-SNE, UMAP, and all the alternative DR approaches the literature by not aligning based a pairwise comparison of points, iee individual Pij and qij. MAP IT exploits combined information represented by marginal prob- abilities Pj and gj. which are aligned, and which naturally encompass information about multiple pairs of points simultaneously, using unnormalized quantities. This represents major shift.
MAP IT's VISUALIZATIONS
General comments to the experimental part. The MAP IT theory has been developed from the viewpoint of divergence and for that reason the v/Gaussian distributions (and perplexity computation) as in i-SNE are chosen (see Appendix C for further considerations approach to metrics and weights could have been used, only amounting to design choices. In all MAP IT experiments, random initialization is used, perplexity value of 15 is used, and no gain or "trick" are used such as to multiply Pyk by some constant in the first (say. 100) iterations (widely done in the t-SNE literature). The common delta-bar-delta rule is used, setting momentum to 0.5 for the first 100 iterations and then 0.8. The learning rate is set to 50 always, over 1000 iterations. Results are found to be relatively stable with these choices (see Appendix C for more comments on implementation). For I-SNE the highly optimized Barnes-Hut algorithm is used with its default parameters. For UMAP, the state-of-the-art implementation from the Herzenberg Lab, Stanford, is used with default parameters, thus always initialized by Laplacian eigenmaps. The PacMap author's Python implementation u with default parameters, thus always initialized by PCA. All meth- ods return a cost function value used to select the best result out of several runs. MAP IT code is available at bttps: /
these choices.). The UMAP
com SF'///SII-- -wtt-iiiaaaalelellleeeee
The focus of this paper is to introduce MAP IT fundamentally new way to approach dimension- ality reduction and not to extensively scale up MAP IT. For that reason, the focus is on a range of relatively modest sized data sets, to convey the basic properties of MAP IT as new approach. In Appendix C, some further considerations on potential upsealing of the method based on sampling of forces and computation of (entropy) weights (Eq. (99) provided. Visualizations below are best viewed in color. Plots are enlarged and repeated in Appendix C, for the benefit of the reader, where also more details about data sets are given.
't-SNE Barnes- Hut, UMAP: C. Meehan, J. Ebrahimian, W. Moore, and S. Meehan (2022). Uniform Mani- fold Approximation and Projection (UMAP) PacMap: wwtp://aw.oooomaaaaaaaaaaaeeeeee Wwt.aaaaaaaaaaaa/////////cooaec

---

Published as a conference paper at ICLR 2024
(a) L-SNE.
(b) UMAP.
(c) PacMap.
(d) MAP IT.
Figure 4: Visualizing the Coil-20 dataset.
(a) I-SNE
(b) UMAP
(c) PacMap.
(d) MAP IT.
Figure Visualizing visual concepts.
MNIST. A random subset of MNIST consisting of 2000 points is used. Figure has already illustrated that MAP IT, despite not being heavily optimized and by random initialization, produced markedly different representation compared to the alternatives, with clear class structure and with better separation between classes. Figure IO in Appendix C shows visualizations using different values of nearest neighbors. The value of this hyperparameter will influence results. Based MNIST and other data sets appears as a value between and 15 produce reasonable results over range of data sets. Figure illustrates MAP IT with 10 for MNIST over different runs. The main structure of the mapped data is always the same showing robustness wrt. initialization. Appendix C provides further quantitative analysis.
Coil 20. can be seen in Figure that MAP IT separates very well the 20 classes, when compared to the alternatives. may be that MAP IT experiences symmetry breaking to a somewhat larger degree than e.g. PacMap (flattening out ring structures).
Visual Concepts. Images corresponding to three different visual concepts visualized in Fig. by their SIFT (Lowe) 1999) descriptors (0000dimensioona), The visual concepts used are straw- berry (blue), lemon (cyan) and australian terrier (yellow). It evident from all the methods that the concepts are overlapping. t-SNE splits the australian terrier. PacMap splits the hugely overlapping groups strawberry and lemon. UMAP doesn't 't split groups but indicates little group structure. MAP IT indicates more of a group structure, without splitting any group.
Newsgroups. bag of 100 words is created. Randomly, 10% of the documents are selected, obtaining total of 1625 documents distributed over the categories comp, rec, sci and talk, and a document-word matrix formed and used to visualize the word distribution, Fig. 6 (see Appendix C for word-clouds). t-SNE and UMAP uniformly spread the words in the plane. PacMap seems to put words in groups roughly corresponding to topics, which may be natural but which is strict (the word "computer", for instance, would be expected sci). MAP IT also puts words in groups to some degree, but not exclusively, like PacMap.
be exclusive to e.g. group
Frey faces. The 1965 (28 x 20) "Frey faces" are visualized and shown in Fig. 7 Fach image is frame in video of the same face varying smoothly over time. t-SNE, UMAP, and PacMap all seem to predominantly pick up on a "smile" versus "no smile" structure in the video. MAP IT creates smaller local structures but these structures seem more spread out in the space in the sense of for instance not placing smiling faces very far from other faces.
Sampling over neigneigsbors. As mentioned, scaling up MAP is not a main focus in this paper. is however of interest for future work. As initial experiment, computation of attractive/repulsive
8

---

Published as a conference paper at ICLR 2024
(a) L-SNE.
(b) UMAP.
(c) PacMap.
(d) MAP
Figure 6: Visualizing word-representations from Newsgroups.
(a) t-SNE.
(b) UMAP.
PacMAP.
(d) MAP IT.
Figure Visualizing the Frey faces.
forces are split on two groups over & neighbors and - k non-ncighbors for each point. The latter group is sampled, using only some multiple of k. here 3k. For 10 and n = 2000, this yields over 98.5 percent reduction in computations. Fig. @hsow for MNIST that the visualization is basically unchanged (elaborated more in Appendix C).
CONCLUSIONS
MAP IT takes fundamentally different ap- proach visualize representations by aligning distributions over discrete marginal probabili- ties (node degrees) the input space versus the target space, thus capturing information in wider local regions. This is contrary to current methods which align based on individual prob- abilities between pairs of data points (states) only. The MAP IT theory reveals that align- ment based on a projective divergence avoids normalization of weights (to obtain prob- abilities) entirely, and further reveals dual viewpoint continuous densities and kernel smoothing. MAP IT is shown to produce visualizations which capture class structure better than the current state the art.
Figure 8: MAP IT with sampling of non-neighbor attractive/repulsive forces.
ACKNOWLEDGMENTS
This work partially funded by the Research Council of Norway (RCN) grant 309439 Centre of Research-basce Innovation Visual Intelligence, http: /vi sua sual-inne -intellll gence. no, as well as RCN grant no. 303514. The author thanks the anonymous reviewers for helpful comments.
Reproducibility statement. To ensure reproducibility, proofs are included in Appendix B and ad- ditional results and analysis are included Appendix C. Code is available bhttpss://giiiii com SST-TVVIIS. Intell gence/]

---

Published as a conference paper at ICLR 2024
REFERENCES
Ehsan Amid and Manfred K Warmuth. TriMap: Large-scale dimensionality reduction using triplets.
arXiv preprint arXiv:1910.00220 0000000 2019.
Aleksandr Artemenkov and Maxim Panov. Nevis: Noise contrastive approach for scalable
visualization. Proceedings of The Web Conference 2020, 2020. URL attpss:/aapi
semanticscholase htt.:/aa.....//oor.r.1::202.1010
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15:1373-1396, 2003.
Anne C. Belkina, Christopher O. Ciccollela, Rina Anno, Richard Halpert, Josef Spidlen, and Jen- nifer E. Snyder- Automated optimized parameters for t-distributed stochastic neighbor embedding improve visualization and analysis of large datasets. Nature Communications, 10 (5415), 2019.
Jan Niklas Böhm, Philipp Berens, and Dmitry Kobak. Attraction-repulsion spectrum in neighbor embeddings. Journal of Machine Learning Research, 13:1-32, 2022.
Niklas Böhm, Philipp Berens, and Dmitry Kobak. Unsupervised visualization of image datasets us- ing contrastive learning. In The Eleventh International Conference on Learning Representations, 2023. URL
net
Kerstin Bunte, Sven Haase, and Thomas Villmann. Stochastic neighbor embedding SNE for dimen- sion reduction and visualization using arbitrary divergences. Neurocomputing, 90:23-45, 2012.
T. Tony Cai and Rong Ma. Theoretical foundations of t-SNE for visualizing high-dimensional clustered data. Journal of Machine Learning Research, 23(1):1 2022.
Miguel Carreira-Perpiaan The clastic embedding algorithm for dimensionality reduction. In Inter- national Conference Machine Learning, volume 10, pp. 167-174. 2010.
Sebastian Damrich and Fred Hamprecht. On UMAP's true loss function. In Advances in Neural Information Processing Systems, volume 34, Curran Associates, 2021.
Sebastian Damrich, Niklas Böhm, Fred A. Hamprecht, and Dmitry Kobak. From t-SNE to UMAP with contrastive learning. In International Conference on Learning Representations, volume 11, 2023. URL /ttpattt/////eeeeeeeeeee
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei Li. Imagenet: A large-scale hierarchical image database. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2009.
Wei Dong, Charikar Moses, and Kai Li. Efficient k-nearest neighbor graph construction for generic similarity measures. In International Conference on World Wide Web, volume 20. ACM, 2011.
David Donoho and Carrie Grimes. Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data. In Proceedings of the National Academy of Arts and Sciences, volume 100 (10), pp. 5591-5596. 2003.
Andrew Draganov, Jacob Rødsand Jørgensen, Katrine Scheel Nelleman, Davide Mottin, Ira Assent, Tyrus Berry, and Aslay Cigdem. ActUp: Analyzing and consolidating t-SNE and UMAP. arXiv preprint arXiv:2305. 230.00730, 07320, 2023.
Michael Gutmann and Hyvärinen. Noise-contrastive estimation unnormalized statisti- cal models, with applications natural image statistics. Journal of Machine Learning Research, 12(2), 2012.
Raia Hadsell, Sumit Chopra, and Yann LeCun. Dimensionality reduction by learning an invariant mapping. In Proceedings of the IEEE International Conference on Computer Vision, volume 2, pp. 1735-1742, 2006.
Geoffrey E. Hinton and Sam Roweis. Stochastic neighbor embedding. Advances in Neural Information Processing Systems, volume 15, MIT Press, 2002.
10

---

Published as a conference paper at ICLR 2024
Yanyong Huang, Kejun Guo, Xiuwen Yi, Jing Yu, Zongxin Shen, and Tianrui Li. T-copula and wasserstein distance-bart saaancee-baedd stochastic neighbor embedding. Knowledge-batt based Systems, 243: 108431, 2022.
J. Hull. Database for Handwritten Text Recognition Research. IEEE Transactions on Patlern Analysis and Machine Intelligence, 16(5):550-555 1994.
Robert Jenssen. Kernel entropy component analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(5):847-860, 2010.
Robert Jenssen, Jose C. Principe, Deniz Erdogmus, and Torbjørn Eltoft. The Cauchy- Schwwrz divergence and Parzen windowing: Connections to graph theory and Mercer kernels. Journal of the Franklin Institute, 343(6):624-629, 2006.
Dmitry Kobak and Phillip Berens. The art of using t-SNE for single-cell transcriptomics. Nature Communications, 10:5416, 2019.
Dmitry Kobak and George C. Linderman. Initialization is critical for preserving global data structure in both t-SNE and UMAP. Nature Biotechnology, 39(2) 2021.
Dmitry Kobak, George Linderman, Stefan Steinerberger, Yuval Kluger, and Phillip Berens. Heavy- tailed kernels reveal finer cluster structure in t-SNE visualisations. In Machine Learning and Knowledge Discovery in Databases, pp. 124-139. Springer International Publishing, 2020.
George C. Linderman and Stefan Steinerberger. Clustering with t-SNE, provably. Siam Math.
Data Sci., 1:313-332, 2019. 2019.
George C. Linderman, Manas Rachh, Jeremy G. Hoskins, Stefan Steinberger, and Yuval Kluger. Fast interpolation- t-SNE for improved visualization of single-cell RNA-seq data. Nature Methods, 16:243-244 245, 2019.
David Lowe. Object recognition from local scale-invariant features. In Proceedings of the Inter- national Conference Computer Vision. IEEE, 1999.
Leland McInnes, John Healy, and James Melville. UMAP: Uniform manifold approximation and projection for dimension reduction. arXiv preprint 1rXiv:1802.03422 2020.
Karthik Naryan, Ali Punjani, and Pieter Abbeel. Alpha-beta divergences discover micro and macro structures in data. In International Conference on Machine Learning, volume 37. 2015.
Sameer Nene, Shree K. Nayar, and Hiroshi Murase, Columbia object image library (coil-20), In Technical Report. 1996.
Jose Principe. Information Theoretic Learning Renyi's Entropy and Kernel Perspectives. Springer New York, NY, 2010.
Sam Roweis and Lawrence K. Saul. Nonlinear dimension reduction by locally linear embedding. Science, 290(5500):2323-255 2326, 2000.
Tim Sainburg, Leland Mclnnes, and Timothy Q. Gentner. Parametric UMAP embeddings for repre- sentation and semisupervised learning. Neural Computation, 33:2881-2907, 2021.
Antonin Schrab, Ilmun Kim, Melisande Albert, Beatrice Laurent, Benjamin Guedj, and Arthur Gret- ton. MMD aggregated two-sample test. Journal of Machine Learning Research, 24, 2023.
Jian Tang, Jingzhou Liu. Ming Zhang, and Qiaozhu Mei. Visualizing large-scale and high- dimensional data. In International Conference on World Wide Web, volume 25. ACM, 2016.
Joshua Tenenbaum, Vin de Silva, and John C. Langford. A global geometric framework for nonlin- car dimensionality reduction. Science, 290(5500)2231-23200 2000.
Chris Thorton. Separability is learner's best friend. In Neural Computation and Psychology Workshop, volume 4, pp. 40-46. 1998.
11

---

Published as a conference paper at ICLR 2024
Daniel J. Trosten, Rwiddhi Chakraborty, Sigurd Løkse, Robert Jenssen, and Michael Kampffmeyer. Hubs and hyperspheres: Reducing hubness and improving transductive few-shot learning with hyperspherical embeddings. In Proceedings of the IEEE/CVF Conference Computer Viston and Puttern Recognition (CVPR), pp- 7527-7536. IEEE, 2023.
J. Derek Tucker, Matthew Martinez, and Jose Laborde. Dimensionality reduction using elastic measures. Stat, 12, 2023.
Laurens van der Maaten. Learning a parametric embedding by preserving local structure. In Pro- ceedings of the International Conference on Artificial Intelligence and Statistics, volume 12, pp. 384-391. 2009.
Laurens van der Maaten. Accelerating t-SNE using tree-based algorithms. Journal of Machine Learning Research, 15(1):322133255, 2014.
Laurens van der Maaten and Geoffrey E. Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, 9(11), 2008.
Laurens van der Maaten and Killian Weinberger. Stochastic triplet embedding. In Proceedings of the IEEE International Workshop on Machine Learning for Signal Processing, 2012.
Yingfan Wang. Haiyang Huang, Cynthia Rudin, and Yaron Shaposhnik. Understanding how dimen- sion reduction tools work: an empirical approach to deciphering t-SNE, UMAP, TriMAP, and PacMAP for data visualization. Journal of Machine Learning Research, 22(1):9129 (10)))91199900000 29-9201, 2021.
Michael Wilber, Lljung Kwak, David Kriegman, and Serge Belongie. Learning concept embeddings with combined on Computer Vision, volume 2, 2015.
expertise. In Proceedings of the IEEE International Conference
Peter Yianilo.. Data structures and algorithms for nearest neighbor search in general metric spaces. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, volume 93, pp. 311-321. Association for Computing Machinery (ACM), 1993.
Shujian Yu, Francesco Alesiani, Wenzhe Yin, Robert Jenssen, and Jose Principe. Principle of rele- vant information for graph sparsification. In 38th Conference on Uncertainty in Artificial Intelli- gence, volume 180, pp. 2331-2341. PMLR, 2022.
Shujian Yu, Hongmin Li, Sigurd Lokse, Robert Jenssen, and Jose Principe. The conditional cauchy- schwarz divergence with applications to time-series data and sequential decision making. arXiv preprint arXiv:2301.089/ 2023.
APPENDIX A: FURTHER PERSPECTIVES ON T-SNE, UMAP, PACMAP, AND VARIANTS
As mentioned in Section of this paper, large plethora of dimensionality reduction methods exists and an excellent repository for more information is e.g. phttps///
1o/ smalivis/ / In this paper, following recent literature, the main algorithms are considered to be I-SNE (van der Maaten| 2014), and UMAP (McInnes et al. 2020), and we include the empirically motivated PacMap Wang al. 202T) For context, TriMap AAmdd & Warmuth. 2019) and Large
Tang et al. 2016) are discussed below. The t-SNE theory has been outlined in Section 2.
In the paper introducing UMAP, McInnes al. (2200) argues that t-SNE should be considered the current state-of-the-art at that time, and mentions computational scalability as a main benefit of UMAP versus t-SNE. The main aspect with respect to computational scalability for UMAP versus t-SNE is that the simplical set theory shows that for UMAP normalization over pairwise similarities (probabilities in (-SNE) is not needed, as opposed to t-SNE, This illustrates the importance of the sound theoretical foundation of UMAP As further described in (McInnes et al.] 2020). UMAP's simplical set cross-entropy cost function resembles in several ways the Large (Tang et al.) 2016) cost function. Large Vis also avoids normalization in the embedding space, albeit from more heuristic point of view, but not in the input space where a procedure similar to the one used in Barnes-Hut Hut t-SNE (van der Maaten 2014) is used. Avoiding normalization in the embedding space
12

---

Published as a conference paper at ICLR 2024
is key to the negative sampling strategy employed in Large and which is key to its computational scalability, also an integral component in the UMAP optimization. LargeVis Vis is not included in the experimental part of this paper avoid clutter, but is influential algorithm in the t-SNE family. Melnnes et al. 2020) and Wang et al. (2021). for instance, have both extensive comparative experiments sections also involving Large Vis.
A motivation for Wang et al. (2021) is to discuss preservation of local structure versus global struc- ture. They propose heuristic method, PacMap, which is intended to strike balance between TriMap (Amid & Warmuth 2019) (better at preserving global structure) and t-SNE/UMAP (local structure). TriMap is is a trilett loss-based method. Wang al. (2021) argues that TriMap the first successful triplet constraint method (as opposed to (Hadsell et al. (0066] van der Maaten & Weinherger, 2012: Wilber et al. 2013)) but claims that without PCA initialization "TriMap's global structure is ruined". PacMap is based on a study of the principles behind attractive and repulsive forces and finds that forces should be exerted on further points and sets up heuristically designed procedure for treating near pairs, mid-near pairs, and non-neighbors.
Understanding t-SNE versus UMAP, in particular, from a theoretical perspective, has gained interest in the recent years. Damrich & Hamprecht (2021) studies the interplay between attractive and repulsive forces in UMAP in detail and comes to the conclusion that UMAP is actually not exactly optimizing the cost function put forth in (MeInnes et al. 2020). Böhm al. (2022) studies the whole attraction-repulsion spectrum and find cases where UMAP may diverge. Damrich et al.] (2023) provides an entirely new viewpoint relating fixed normalization constant in UMAP to smaller learned normalization constant in t-SNE when considering negative sampling and noise contrastive learning. Draganov al. (2023) argues that the normalization aspect is basically the key difference between I-NE and UMAP, P, and suggests a way to toggle between the two approaches.
Kobak & Linderman (021) show that UMAP's initialization (Laplacian eigenmaps (Belkin & Niyogil 2003)) is very important for UMAP's results and claims that t-SNE can be improved by similar initialization, Wang et al.] (202T) also studies initialization, and claim that both UMAP but also TriMap are very dependent on initialization. Several papers have revealed close connections between t-SNE and Laplacian eigenmaps (Carreira-Perpinal 2010: Linderman & Steinerberger, 2019 Böhm et al. (022). Some further comments on the relationship between t-SNE and Laplacian eigenmaps are provided in Appendix B. Draganov et al. (2023) argues that the normalization aspect is basically the key difference between t-SNE and UMAP, and suggests way to toggle between the two approaches. Other highly influential papers provide important insight (Kobak & Berens 2019
Kobak et al. 2020).
In this paper, sampling is also demonstrated (Figure g and Appendix C), sharing some similarity to the sampling strategies invoked in e.g. Large Vis and UMAP.
should also be mentioned that dimensionality reduction methods inspired by the t-SNE approach by alternative divergences to the Leibber over joint pairwise probabilities have been stud- ied to some degree (Bunte et al. 2012; Naryan et al. 20155 Huang et al.) 2022). However, these works have not discussed projective properties of divergence measures and have contributed to understanding the aspect of normalization.
APPENDIX B: PROPOSITIONS WITH PROOFS AND COMMENTS
For the benefit of the reader, the well-known Kullback-Leeibler-aaae t-SNE relation from the main paper, which van der Maaten & Hinton (2008) builds on, is proved:
arg min KL(PIIQ) Ei ERR
arg min
Σ
Pij log
Pij
arg min
Σ
Pig log qiz-
(20)
E,...,, ERR
T
E ERd i
13

---

Published as a conference paper at ICLR 2024
Proof.
arg min Bn ERa (T(PIIQ)
arg min
Σ
Pij log
Pij
(21)
Bn E.R
= arg min
Σ
Pig log
Σ
Piò log q:j-
(22)
S1 ERd
consiant
arg min
Pig log Oij-
(23)
En C.a
Proposition [Minimizing (PIIQ) and the role of normalization). Let qij qt3 ZZ for some
choice of 9sz where Zg -E Jam Then
m2,m
arg min KI(PIQQ)
arg min
Σ Pij log húj
log Σ Inm-
(24)
Bn EBa
ERR
Proof.
arg min KL(PIQ) = arg min
Σ
Pij log gij
(25)
#1v ERd
En ERd
arg min 21y
Pij log
(26)
Σ Irm
arg min
Σ Pij log Tis
Σ Più log
Σ Fnm
(27)
En ERR
arg min E, ERd
Σ
Pij log Øij
log Σ Anm
(28)
Comment to Proposition 1 Deriving the t-SNE cost function without first expressing yi in a particular form (I-distribution (Cauchy distribution) or Gaussian) shows a general property of the cost function. The t-SNE cost function is by the above result expressed by two terms where the first term relates the normalized Pış to unnormalized æty. The second term only involves the unnormalized 7-j-
From this expression, an interesting aspect of the t-SNE cost function is an intrinsic connection Laplacian eigenmaps (Belkin & Niyogil 2003). Discovery of connections between t-SNE and Laplacian eigenmaps can be traced back to Carreira-Perpinan (2010). More recently, [Böhm et al. (2022) performed a closer examination of this relationship in terms of eigenvectors normalized and unnormalized Laplacian matrices. Linderman & Steinerberger (2019) studied convergence of clustering with t-SNE from the viewpoint of early exaggeration (an often used optimization "trick") and identified regime where t-SNE behaves like iaplaciin-baseed spectral clustering.
In Laplacian eigenmaps, the aim is to find a low-dimensional embedding 21,..., Zn E R2 from 21, In D. It is assumed that some similarity measure be defined in the input space,
'In the original SNE paper (iinton Roweis,
2002 the Gaussian distribution
used To
exp(-x||z; - 2, 2,1l / En,m m. exp(-x||z, - Zm "T))
The argument in (van der Maaten Hinton 2008
was that the t-distribution helps mitigate the so-called crowding problem. It possible formulate the joint prohabilities as functions of other distance functions than the Fuclidean in terms of similarity measures.
14

---

Published as a conference paper at ICLR 2024
pairwise æ; and Zj, which be denoted Way- The Laplacian cost function is essentially Σi, miyll zjll² to be minimized over 21,...,. 2n E IR,, however given orthogonality constraints on ......; In E R avoid trivial minima. Since for I-SNE, (.j function of || 2,ll² for both the t-distribution (Cauchy distribution) and the Gaussian, there is close link between t-SNE and Laplacian eigenmaps. For instance, for qij [1 + 2| zj | [P]-1 the first term becomes
Σig Wij log |z 2 and for the Gaussian the corresponding term becomes Eig Wiy || = I| up proportionality constant (this also pointed out in (Trosten et 2023)). By letting Way Pij the link becomes obvious. In t-SNE, there are no orthogonality constraints on 2,,...,, 2n E R Instead, trivial solutions are avoided by the constraint posed by En,m Qam-
Recently, Cai & Ma (2022) provided elaborate spectral analysis concluding that t-SNE is con- nected to Laplacian eigenmaps. By the above analysis, and from e.g. (Böhm et al. 2022 this is evident from the form of the t-SNE cost function itself.
Proposition 2. [Gradient of (L(I))))
KL -44 - (pi - 4:5) (:5 zi).
(29)
0z:
Proof.
a (L(P)IQ)
Σ i
Pcj log ds + log Σ Inm
(30)
0z,
n,m
The following derivation resembles (van der Maaten & Hinton
2008
Note that if z; changes, the z,||. Hence, the gradient of
only pairwise distances that change are di and dy where dij the cost function C' with respect to 2; is given by
2,
Oc
ac 8c)
Oc
c Σ
(z, (2.-29) 21) = 2
(z+ 2z).
(31)
0z:
0dgg
Odj:
Odly
Furthermore
ac
0 log Σ Adij
Σ k.
Pki Odiy
log qhl
Inm
(32)
Od.j
12,m
0
Σ
Pkl
Okl +
Fam-
(33)
ki
Tal
Od:
Σ
Tum n.m
Odg
n,m
The gradient only non-zero for t: = i, and for n
j. yielding
ac
1
θ
Pij qig Od.3
Tij +
Tij
(34)
0dgj
Σ
Tro
Odgy
n,m
Note that for qg - exp(-<ilzz - 12)1)) the Gaussian distribution, we have
which is the t-distribution, or alternatively for qo
Odg 9.s = 24h..
(35)
Hence,
8C =2 2 0d.j
-Pigfii +
(--pi + + ØGg
(36)
Σ Inm
11.m
15

---

Published as a conference paper at ICLR 2024
since qtz
Rs Σ fmm
Finally, this yields
① C= = KL(PI]Q) = -4 Σ (pis 4b) 9zll2 =z).
(37)
Proposition [CS divergence is projective]. Let Pj = P5/Zp. Zp Ex Py, and 9j = q3 Zg.
Zg EE qz. Then
CS(Pm Qm) -SSP
(38)
Proof.
Σ EPO9
(m((m.||Qm)) = - llog
(39)
9
22 42 Σ
2p 2
- log
(40)
$
Σ
Σ 4/2
Σ Pッ
=olog
(41)
Σ
C...
(42)
Proposition 4. [Minimizing CSS(m (l with respect to 21,..., Zn E Rall
arg min
(l arg min - log Σ p,
+ 2 j
log Σ
93.
(43)
2n. EBd
21 21.... ERg
Proof.
arg min #1 ER.
CS(Pm
(44)
arg min
log
(45)
2i 2, ERJ
Σ
Σ o
indopendent
= arg min 2i En ERd
log Σ 83 + 2
log Σ P.
(46)
(47)
16

---

Published as a conference paper at ICLR 2024
Proposition 5. [Gradient of CS(Pml]Qm))
0 c5(pmllQmm =
Pj
Σ
Lz
2.).
(48)
Oz,
Σ o3
Proof.
arg min (S(
=
arg min
- log Σ pz9
+ 2
log
Σ
o
(49)
2n ERd
(50)
There several ways to proceed. Here, it is chosen to start by expressing CS (Qm) explicitly into cross- prosspproduct terms Psr .. For convenience, the derivation is split into two parts.
0
a
log Σ
Les = Edy dz
ΣΣ j W
(51)
0z:
Ed dzi
3'
Look first at the case j # Then
8 E
Pab will have non-zero terms for k = i, hence k.kk
Dzh
0
0
Σ
Ps Σ
Pyk
Po
gjs.
(52)
0z
dzi
Oz.
For j = i,
0 Σ
Pik =
Σ
Σ
Pike
Tsk
Σ
pk Oz:
Tsk.
(53)
dzi k',k
Ozi
k
R!'
k
Hence,
ΣΣ W
Σ
(54)
0z:
Ozi
Note that for 0g = -+||=--,ح| 1 exp(-x|1zz (1,12,,>,113)))) the Gaussian distribution, have
which is the t-distribution, or alternatively for Tej
0
Oz: 95 (2g 21)
(55)
Thus
log
>
pンqj -4
Σ
[E -2)). zi).
(56)
0z,
Σ
Eg 8.3
Alternatively,
log
Σ p;
1
Σ p.q.
Σ
Pb Oz, qj
(57)
Oz,
Σ Pr
Oz,
and then work with qj
Σ
Tik. For the second part, consider k
0
1
log
1
Σ d
ΣΣ
(58)
0z, 2
2
Σ
33
0z:
2
Σ
dz.
k
8
17

---

Published as a conference paper at ICLR 2024
and work in similar fashion as above from there, express
0 1 log
93
1
Σ
4
Σ
24h
0
41
(59)
0z, 2
2 Σ
Ozi
0zi
97
93
and insert i1 = Σ
Ag.. This gives
k'
0
1
log Σ
1j
-=,(
(60)
0z, 2
Σ 4j'
Hence, when taken together:
a 0z;
CS( =
Σ
Pj
4
Ph -1).
(61)
Σ
Σ 03
10
Proposition 6. [The map CS divergence is projective]. Let m(()) + & and assume p(æ) = /Zp and q(2) (Z where p(x) and @(z) are unnormalized with Zp f(xx)) and Zg @(z dz as the respective normalization constants. Then
=S(pl=))l((e))
(62)
Proof.
CS(p(z))la(z))
(63)
JJ ((x)) ū(x)
2 2y f(x, z z)dzdz
=olog
(64)
(ss
((x) Z
2 f(x z)dxddz)
(15()z))
((x))
[æx 2 2)dxdd
2,2, f p(x)) (z) fx ddxd
=olog
(65)
I (x) ( )ddxd) ( Eे (T) z)dxdd) 1
(1. 2)drdd (2)
- log CS()(=))((()).
(66)
2)xxd))
(67)
(Empirical map CS divergence]. Let a sample Fi...., By RD be given and assume the mapping m(x) + e. Then, an empirical map CS divergence is given by
Proposition
(S(p())ll<(3)) = -log
(68)
) (EPles)
Σ E /
Proof. We have CS(p(=))lg(z)) C(((()))((()) Thus
I [ 2)ddd
CS((())\[((2)) = log
(69)
( (x, à ( (xx))ddd))))
18

---

Published as a conference paper at ICLR 2024
It suffices to look at the numerator. Since (z Exxe [+(=)ā(()) and have
Exx2 [p(x)((2)] {(zz))((Z))
(70)
we have
Σ((o,)((21)
(S(p(=))l((2)) = =loo
(71)
)),),))) ) (z
Proposition 8. [Minimizing CS(p(x))ll(x))) with respect to ,,...., nn E Ral
arg min CS(((=)]l((z)) arg log Σ [(zz))((z)) log Σ q² (z₁).
(72)
$1 ERa
En ERa
Proof.
arg CS(p(x))lg(z)) En
(73)
E((a))((s)
arg min
- log
(74)
F. ERd
1
Σ E((())) 1
independent
log Σ p(z))((z)) + 1
arg min min a CRJ
log Σ (zz))
(75)
j
(76)
Proposition 9. [Gradient of (S(p(=))la(21))
p(x,)
g(z,)
θ
(S(p(a)]((())== = Σ Oz.
0z, ((z)).
(77)
3 )
[(,rr
Proof.
arg min CS(p(a))l((=))
arg min log EMar,)((s)) log Σ {z,)) ER,
(78)
The derivation is split into two parts. First,
Σ p(x,) 3
log Σ ((æz))((z)
0z, ((2,).
(79)
Oz:
Σpley)((zy)
Second,
i log Σ (x,) = Σ (z(zz)
Σ
(2,)
1
Σ 27(2,)
0
((z,). (80)
0z, 2
Oz
=
2 Σ (Z(zz)
0z,
5'
19

---

Published as a conference paper at ICLR 2024
Taken together, thus
p(az))
((z,)
CS ()(p(=)l((())== Σ
[(zz))
(81)
Σ {((z))ā(Z))
{(()))
Ōz,
Proposition 10. [Gradient of (S(((2)) (lg()) with kernel smoothing). Let ((2z) En Ri(2z 2k) and i(xx,) >x Kp( - 2x. for shift-invariat kernel functions kiz()) and kp(.)). Then
0 CS(p(a))la())) = -4 = dz,
Σ Dj
Oj
-z)(2z - zi).
(82)
Σ o3
8
Proof. A shift-invariant kernel function satisfies n(2) 2,) x(dis) where dij
|||1 -2:112.
Hence, similar to the derivation for Proposition] we will have
2
Mar
((2,)
(S(p(=))o(())==- θz
=
{(zg)
(83)
Σ p 7a(zz))
Σ (z())
Ozi
Σ
p(x;))
((2,)
(0n(z))
+ odgs ) (z) =2i)
07(2z)
(84)
play )((z))
Σ (z)))
Odis
pla;))
((z,)
aq(z;)
Σ
2
(zj - zz).
(85)
Σ p )((z)))
Σ (z)r)
adi
8'
Note that 2g(=;) 8d,
Dx. (x)-20)))) = 2x²(2; - 21)) for kzz K= - zi)) = 1+12,~ which is the
8d, t-distribution, or alternatively for k= - 2;)) = exp(- -xil=; =2,(()), the Gaussian distribution.
Taken together,
8 oz,
(S(p()))l((3))= =
D
R 22 -2)(2z z1).
(86)
Σ Ep
Σ
Proposition 11. [Cauchy-Schwee Schwarz (CS) t-SNE is a special case of MAP IT). Let Pat be the prob-
ability for the joint event æy O mw- Let Oike be the probability for the joint event zj Zg. If (x,, O agy) O (z, O xx)) E 0, then
C =
(87)
Proof. We have
3 Epsss
CS(Pm.l(Qm)) = - llgg
(88)
ΣΦ
ΣΦ 9
Σ Σ
Psk
= =-log log
(89)
Σ Σ POp:P9R)
1 K
w
20

---

Published as a conference paper at ICLR 2024
MAP IT
CS t-SNE
Figure 9: Illustration of CS t-SNE as special case of MAP IT.
suffices to look at the numerator since the terms the denominator are related normalization quantities.
If (æy n aerr n (z, n #k) E then Prob((æ, O ax) n (zy O 2x)) = Pjb = 0 (assuming
independence) for K k. Hence
Pju = ΣΣ K
(90)
3
for K' = k =1.
Comment to Proposition 11 The illustration in Fig. 9 brings further perspective to this result.
The black filled circle denotes node j. Nodes within the stapled circle assumed be relatively near and nodes n outside this circle are assumed to be distant in the sense that Pjo is neglible for each such node n.. For MAP IT, Piı² also multiplied by probabilities Qjk and qjz in addition gjsr for nodes l and close to k'. This is not the case for CS t-SNE. This shows that MAP IT is able to capture information in wider local neighborhoods compared to CS t-SNE which only captures local information via pairwise affinities, a property it shares with its KL counterpart t-SNE and methods such as Laplacian eigenmaps (Belkin Niyogi 2003).
In practise, this means that MAP IT models that the event (æ could induce the event (zjnzz) K'' and ls are close.
21

---

Published as a conference paper at ICLR 2024
APPENDIX C: ADDITIONAL RESULTS AND ANALYSIS
Defining probabilities in the input space. The projective property of the CS divergence has been shown to avoid the need for direct normalization of probabilities if the probabilities come in form 9, // Zz. where Zg is as explained in Section 3.2 and where one has access to qj. and similarly for Py- However, for optimization purposes, normalization Zp = Σj Py not as critical since this is procedure done only once. In any case, has recently been shown that dimensionality reduction methods are quite robust to the choice of input space pairwise similarity function, and even binary affinities seem give good results for many algorithms (Böhm et al. 2022). Note that it is easy to show that even if the input space pairwise similarities do not come in the form assumed in Eq. ( that is, Pij = Zpp Z, = Σn,m Prmms but the target space similarities do, then Dcs (Ps(Pr) ll@m) Dcs( Pm (m) (Proposition 3). In order for MAP IT to the exact same input similarities as t-SNE commonly does, so-called symmetrized similarities are here used in the
input space. These are given by Pij Puy with Pjji Enge exp(-x, 1.. and likewise for
exp( (sp(=xxlla=-a) =zyl²")
2n
Pilj- Note that the parameter ri is chosen to yield a pre-speiffid value of the so-called perplexity
of the probability distribution (see e.g. (Böhm al. 2022) function of its entropy.
MNIST. MNIST is data set of 28 28 pixel grayscale images of handwritten digits. There are 10 digit classes (0 through 9) and total of 70000 images. Here, 2000 images are randomly sampled. Each image is represented by 784-dimensional vector. Figure T and Figure 3 in the main paper show that MAP IT produces a MNIST visualization with much better separation between classes compared alternatives and that the embedding is robust with respect to initial conditions.
MAP IT's free parameter is the number of nearest neighbors to go into the computation of Pina, and ian Figure 10 shows representative embedding results for the subset of MNIST for different values of k. As in all dimensionality reduction methods, the visualization results depend on k. For MNIST. for k- = 7 and for k = 10, the class structure appears and is relatively stable also for k = 12. For most data sets, value for k between 5 and 15 seem yield reasonable results. However, the impact of this hyperparameter should be further studied in future work.
Quantitative analysis. For dimensionality reduction methods, various methods for quantifying neighborhood structure may provide insight. For instance, relatively low knn recall may illustrate better capturing of cluster structure at the potential expense of capturing manifold structures, as studied by (Böhm al., 2022). For the embeddings shown in Figure [ the fraction of k nearest neighbors in the input space that remain among the nearest neightbors in the target space ("knn recall") is computed and shown in Table several values of k. For low values of k, PacMap and MAP IT have lower recall values, indicating that these methods better capture cluster structure and may sacrifice some ability to capture manifold structure. For l ca equal to 60 and above the knn recall settles to similar values (slowly diminishing for larger h; not shown here).
MNIST
knn
t-SNE
UMAP
PacMap
MAP IT
15
0.48
0.42
0.37
0.35
30
0.49
0.47
0.43
0.41
45
0.50
0.49
0.47
0.45
60
0.51
0.50
0.49
0.48
Frey
0.09
0.08
0.08
0.09
30
0.11
0.11
0.1
0.1
45
0.13
0.13
0.12
0.13
60
0.15
0.16
0.15
0.15
Table 1: Illustration of knn recall.
MNIST, Newsgroups, "Frey faces" are obtained from httpr///aaiiiiiaa.////////////// html.
22

---

Published as a conference paper at ICLR 2024
ha)= = 5.
(b) k
(c) l: 10.
(d) k 12.
Figure 10: MAP for a subset of MNIST for different values of k.
0.85
UMAP
PacMep MAP
0.8
0.75
0.7
0.6
50
100
160
200
Figure 11: Class-wise knn recall.
Figure 11 shows an alternative way to quantify this effect. Here, the class-wise knn recall in the target space is shown. For each data point, the fraction of nearest neighbors in the low-dimensional space sharing class label with the point in question [Thornton) 1998) is plotted as a curve for various values of k. Here, the known labels for the MNIST are used. It can be observed that as & increases, t-SNE and UMAP have lower class-wise knn recall compared to PacMap and MAP IT. This makes intuitive sense when compared to the visualizations provided in Figure
Further comments on MAP IT's potential for upscaling. Figure in the main paper shows the result of an initial experiment to potentially scale up MAP IT by certain sampling procedure. The proposed sampling procedure not the same as the one employed Large Vis and UMAP. In those methods, attractive forces and repulsive forces are separated. The number of points to go into the computation of repulsive forces are then sampled, so-called negative sampling. When creating Figure in in the main paper, forces have been separated into attractive/repullive forces result- ing from nearest neighbors versus attractive/repuliive forces coming from neigheigs Hence, the proposed MAP IT sampling is different. Experimentally, it was observed that if the number of non-neighbor forces were downsampled for instance to 50 percent, then a multiplication of the attractive/repulsivee forces for non-neighbors by factor two basically reproduced the original em- bedding. A downsampling of non-neighbor forces to 25 percent followed by multiplication factor of four reproduced the original embedding. Similarly, downsampling of non-neighbor forces 12.5 percent followed by a multiplication factor of eight reproduced the original embedding. This is illustrated in Figure 12 for MNIST with k 10. In (a)-(c), the sampling down to 50, 25, and 12.5 percent, respectively, and each of the four subfigures show the embedding after invoking a multiplication factor of 2, and over the nei-neigh forces, respectively. The boxes indicate that the original embedding is in essence recreated (compare e.g. to Figure [1] (c)). For Figure g in the main paper, where only 3k non-neighbor forces are sampled, which means that ca 1.52 percent of non-neighbors are used in the sampling, the factor used is 66 (ca 1/0.0152). The effect that downsampling of attractive/repuliive forces for non-neighbors seems to have, requiring an in- versely proportional multiplication factor as shown above, may be related the observations made in (Böhm et al.) (022) on the effects of non-negative sampling in UMAP. Here, was shown that negative sampling increased attraction in UMAP, and it was argued that without the negative sam-
23

---

Published as a conference paper at ICLR 2024
(a) 50 pereent downsampling.
(b) 25 percent downsampling. (c) 12.5 percent downsampling.
Figure 12: Each subfigure (a)-(c) show the visualizatton/embeedding for different subsampling sce- narios and for a factor 1, 2, 4, and 8, respectively, on non-neighbor attractive/repulsive forces in the MAP IT calculation.
6.4
6.2
5.8
5.6
5.2
11
4.8
4.6
1000
lteratione
Figure 13: Illustration of MAP IT learning rates and number of iterations for subset of USPS.
pling, UMAP may provide embeddings with less cluster structure. Obviously, for MAP IT, there are many aspects that warrant future analysis along these lines. The example provided here meant to show that in this controlled setting, sampling of MAP IT's non-neighbor attractive/repuliiee forces (Figure 8 could reproduce the original embedding (Figure (d)). Please see the end of this Ap- pendix for some further comments implementation.
Learning rates (USPS). In all experiments the MAP IT learning rate has been set to 50 over 1000 iterations. Of course, changing these choices will some degree change the embedding. These choices have however been observed to result in quite stable MAP IT results over range of diverse data sets. Figure 13 shows the MAP cost as a function of iterations for different values of learning rates performed over subset of the USPS data set (Hull 1994). A random subset of the digits 3, 6, and 9 constitute the classes. For each learning rate of 25, 50 and 100 three runs of MAP IT are performed and in each case the curve of cost versus iterations is shown. For this particular data set, low cost function values are obtained quicker for = 100 (leftmost group of curves), compared to ? 50 (middle group of curves) and 1/ 25 (rightmost group of curves). When approaching 1000 iterations all curves have settled at low cost function values. Further studies of the interplay between learning rate, iterations, and various design choices for the MAP IT optimization are left for future work.
Coil 20. This data set (Nnne et al., 1996) consists of 1440 greyscale images consisting of 20 objects under 72 different rotations spanning 360 degrees. Each image is 128x128 image which treat as a single 16384 dimensional vector for the purposes of computing distance hetween images. Visualizations of Coil-20 were shown in the main paper in Figure 4. Enlarged visualizations of Coil 20 are shown in Figures 15
16
and 18
Visual Concepts. Images corresponding to three different visual concepts are visualized. SIFT Lowe 1999) descriptors represented by 1000-dimensional codebook for each visual concept
24

---

Published as a conference paper at ICLR 2024
Figure 14:
Preliminary experiment using the neighborhood structure in the input space when com- puting entropy weights for attractive and repulsive forces for MAP IT.
downloaded from the ImageNet data base (image-net teeeeenet... org) (Deng al. 2009). The visual con- cepts used are strawberry, lemon and australian terrier. The concepts are represented by 1478, 1292 and 1079 images, respectively. The images within each category differ very much, as can be seen A crude approach
e.g. for australian terrier at image-net. org/ hrg/synsets..teeeee.oo.oe synset taken here. Each image is represented by the overall frequency of codewords present for the SIFT descriptors contained in the image. Hence, each image is represented as a 1000-dimensional vector. The local modeling strength of the SIFT descriptors are lost this way, and one cannot expect the resulting data set to contain very discriminative features between the concepts. Visualizations of the visual concepts were shown in the main paper in Figure 5. Enlarged visualizations Coil 20 are shown in Figures 19 20 21 and 22
Newsgroups. Visualizations of words from Newsgroups were shown in the main paper in Figure 6.
Enlarged visualizations of Newsgroups as word clouds are shown in Figures 23
24
25 and 26
Frey faces. Visualizations of the Frey faces were shown the main paper in Figure 7. Enlarged
visualizations of the Frey faces are shown in Figures 27 28 29 and 30
Further comments on implementation and potential scaling. Previously, sampling of attrac- tive/repulsive forces associated with non-neighbors was illustrated on the recurring MNIST exam- ple and it was shown that inclusion of only few non-neighbors in the computations the original embedding, given the use an appropriate multiplication factor. In the current imple- mentation, gradients are computed directly by a matrix operation (D M) where M encodes attractive and repulsive forces according to Eq. (19) where D is the diagonal degree matrix of M and X stores all data points rows. Neighborhood structure is encoded into M. For the sam- pling procedure to potentially truly scale up MAP ITT, more efficient knn graph implementations are needed to avoid memory issues associated with the current very basic approach. This can be done by building on efficient implementations for I-SNE and UMAP, e.g. (Böhm et al.) 2022).
reproduce
In the t-SNE and related literature, problematic issue the normalization factor Z, En.m. Inm which needs to be recomputed over the optimization. For the CS divergence underlying MAP IT, the need for direct normalization is avoided. However, seemingly similar terms (E3 Py. and E, 13.) appear in the weighting the attractive and repulsive forces, Eq. 19). The impact of these terms needs to be further studied. As preliminary experiment, the terms computed using only points in N₂, neighborhoods both in the input space and the target space for MNIST, and the embedding is shown in Figure [4] It can be seen that the main structure the embedding is preserved.
Further comments on parameter choices. Note that (Belkina et al. 2019) provided advice for tailoring the early exaggeration and overall number of gradient descent iterations for t-SNE in dataset-specific manner and argued that this may be especially important for large-scale data sets such cytometry and transcriptomics data sets. Data sets used in this study more traditional (MNIST etc), and available software used in this paper for SNE, UMAP, PacMap are already well- tested for such data sets. However, further parameter tuning discussed in (Belkina et al. 2019)
25

---

Published as a conference paper at ICLR 2024
could potentially improve results for t-SNE. Note that MAP IT uses early exaggeration and there is much room for investigating the effect of for instance step size and the number of iterations, which may affect results also for MAP IT.
Perspectives on MAP IT via local neighborhoods. Section 3 discussed the very important role that local neighborhoods play for MAP IP, revealed via differentiation of the MAP IT cost function. The following main points were observed:
Differentiation must be done with respect to the input space neighborhoods for all quan- tities. For instance, neighborhood structure in the target space Az; will be given by Az; = m((x.)) where m is the (unknown) mapping function.
The practical consequence of this is stated in Eq. 19, which is expressed as a sum over all points j. Here, the attractive force for the gradient vector 2, - 2, depends on Pin.; and the repulsive force depends on Ui,,,' where N₂; denotes a neighborhood around æ,, was further argued that for points 2y that are neighbors of point 2; they would already be in the neighborhood of æ; such that for those nearest neighbors of æ; the MAP IT update rule Eq. (19) uses Pine; for the attractive force and Ūixe; for the repulsive force. For points æ not neighbors of 2;; it was argued that Pixe; simplifies to Pij for the attractive force and likewise Tive, simplifies to qi for the repulsive force.
Knn It is important to note that PiNu; = Eken k= Pyk- It has here been emphasized that han denotes the k'th nearest neighbor of 2j (see Section 3.2 If the Pjæ's 's are interpreted as weights on edges from node j to the nodes h = 1,..., Knn. then it becomes clear that Pixæ; captures local properties in a region around æz.. All of these considerations stem from the MAP IT cost function turned into an update rule for 2, via differentiation.
However, this analysis reveals a new perspective to MAP IT. If we instead of aligning the distribu- tions over the marginal probabilities Pj and qj for all j by the CS divergence focus on the contri- bution to the marginal probabilities from the local region around point æj and zj, respectively, i.e. Pinns and OjNn, by
arg min ER 5
1 log Σ Pasin IiNe, +
2 log Σ Eivv,
(91)
then Eq. (19) would be obtained by the same arguments in Section 3..4 above. This shows that MAP IT effectively aligning the degree of a node in the input space, locally in a neighborhood, with the degree of the corresponding node locally in the target space, but where neighborhoods are defined with respect to the input space in both cases.
To some degree, this perspective resembles the local neighhborhood perspective in Locally Linear Embedding (LLE) (Roweis & Saul (0000. Also here, local neighborhoods are reconstructed in the target space versus the input space via an eigenvector operation. LLE and many other spectral methods (as mentioned in the Introduction of this paper) have inspired much of the research in visu- alization and neighbor embedding methods but as stated in (Wang et al. 202T) their section Local structure preservation methods before I-SNE (page 6) "the field mainly moved away" from these types of methods. In the future, would be interesting to investigate closer links and diffcrences between the fundamental LLE idea and MAP IT.
This an important aspect to point out for the following reason. When basing the input space similarities on symmetrized Pij. which is done in this paper in the experimental part in order to use similarities which are comparable to what t-SNE usually process, an apparent paradox appear In that case, the form of the similarities are such that the p, 's become uniform. In that case would appear as if MAP IT is data independent, always trying to make the 9, 's uniform no matter what the input is. However, the above analysis highlights that via differentiation, MAP IT effectively focus on the contribution to the marginal probabilities from local regions, which will in general differ for the different nodes.
Map KL Divergence?. An interesting question for future research could be to investigate whether the introduction of a map KL divergence similar to the map CS divergence (Definition 4), would
As kindly pointed out by one of the reviewers of this paper.
26

---

Published as a conference paper at ICLR 2024
provide KL-based MAP IT framework via kernel smoothing. Since the KL divergence is not pro- jective, direct normalization of probabilities would not be avoided, but a similar-in moilla-in-sping in-spirit alignment of marginal probabilities seems to be possible.
Concluding remarks. Together with the experiments and analysis in the main paper, these addi- tional MAP IT results and analysis illustrate the potential of this new method to provide visualiza- tions which in many cases markedly different from the current state-of-the-an alternative with better class discrimination and reasonable embeddings overall, from a theoretical approach which fundamentally different and which highlights both viewpoint from the perspective of alignment of marginal probabilities as well as dual viewpoint via continuous densities enabled by kernel smoothing. The role of normalization for divergences be used dimensionality reduction meth- ods follows directly from the MAP IT theory.
27

---

Published as a conference paper at ICLR 2024
8
o
0=0
Figure 15: t-SNE embedding of Coil 20.
Figure 16: UMAP embedding of Coil 20.
28

---

Published as a conference paper at ICLR 2024
Figure 17: PacMap embedding of Coil 20.
Figure 18: MAP IT embedding of Coil 20.
29

---

Published as a conference paper at ICLR 2024
Figure 19: t-SNE embedding of visual concepts.
Figure 20: UMAP embedding of visual concepts..
30

---

Published as a conference paper at ICLR 2024
Figure 21: PacMap embedding of visual concepts..
Figure 22: MAP IT embedding of visual concepts..
31

---

Published as a conference paper at ICLR 2024
CANTUM
banbal
TODAA
Figure 23: t-SNE embedding of words from Newsgroups
problem
chrldaan
Qu
DEANYTUNE
POON
Univenally
ciypiyy
progrum
valagy
GINIT
DOWET
FIMM
Figure 24: UMAP embedding of words from Newsgroups.
32

---

Published as a conference paper at ICLR 2024
Figure 25: PacMap embedding of words from Newsgroups
Whutt
AENSONES
Figure 26: MAP IT embedding of words from Newsgroups..
33

---

Published as a conference paper at ICLR 2024
Figure 27: t-SNE embedding of Frey faces.
Figure 28: UMAP embedding of Frey faces.
34

---

Published as a conference paper at ICLR 2024
Figure 29: PacMap embedding of Frey faces.
Figure 30: MAP IT embedding of Frey faces.
35


Reviews:
[{"review_id": "51cZjqGhhy", "reviewer": "Reviewer_BmiL", "summary": "The authors propose MAP IT, a new algorithm for manifold learning / dimensionality reduction for visualization. They compare qualitatively against previous approaches, including UMAP and T-SNE.\nTheir approach follows t-SNE but replaces the KL divergence with the Cauchy Schwarz Divergence, which removes the need for normalization, resulting in an approach that is theoretically more scalable.\n\nFWIW, I did not have the time to check the proofs, and I don't think I am familiar enough with the literature on relating t-SNE and UMAP to properly appreciate the details in the paper.", "questions": "Can you explain why the kernel smoothing view doesn't apply to t-SNE?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides a new algorithm for a common task, visualizing high dimensional datasets by projecting to two dimensions. They provide an in-depth discussion of how their approach relates to previous approaches, in terms of core ideas, computation, and results. The appendix contains helpful discussion and additional experiments, and all experiments are outlined in great detail.", "weaknesses": "I have two main critiques of the paper:\n- It does not provide quantitative results. It's common in this area to report 1NN results over various datasets in the projected space. While this is a somewhat arbitrary metric, it seems to be the best there is so far, and I think it would be prudent to include it.\n- The paper claims two conceptual novelties, the consideration of neighborhoods and the lack of normalization. Neither of these seem to me as new as the paper claims. Normalization is also not required in UMAP (as the paper mentions). Considering local neighborhoods is done explicitly in the less recent LLE, and implicitly in spectral embedding and laplacian eigenmaps. I was under the impression that t-SNE also has a similar \"dual\" interpretation in terms of kernel density, but I might be mistaken.\n\nMinor:\nAt the bottom of page 1, \"normalization\" is misspelled \"normaliztion\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Qg7CkpR98x", "reviewer": "Reviewer_LbLf", "summary": "This paper introduces an approach to dimensionality reduction by Cauchy-Schwarz projective divergence called MAP IT. This methodology aligns discrete marginal probability distributions rather than individual data points.", "questions": "There are some typos in the manuscript:\n1. Sixth paragraph: normaliztion \n1. After equation 18: neigborhood \n1. After equation 19 second line: also i the\n1. After figure 3: neightbors\n$D(P||Q) = D(P˜||Q˜), \\forall Z_p,Z_q\\neq0$, could be better to understand over the mention of \"$Z_p$ and $Z_q$ being normalizing constants\" which implies $Z_p$ and $Z_q$ need to be some specific values.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* This paper presents a new perspective on dimension reduction using projective divergence. \n* The manuscript is well written, with most equations explained clearly and easy to follow. \n* The authors demonstrate their method across various data sets, showing its ability to discover high-dimensional structures and visualize them in a lower dimension. \n* The commitment to release the code publicly after the review process is admirable.", "weaknesses": "The paper presents projective divergence as a method to simplify high-dimensional data, with its main advantage being the removal of weight normalization. However, from the authors experiments, it's unclear how this could be an improvement compared to existing methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RYiTTmpZUe", "reviewer": "Reviewer_vQ36", "summary": "The authors introduce a new visualization method, called MAP IT.  The\nmethod supposedly improves over other visualization methods that are\ncommonly used, such as t-SNE, UMAP, etc.", "questions": "Could you comment on the computational complexity?\n\nWhy did you not chosse to use commonly used optimization parameters\nfor t-SNE?  In Belkina et al. 2019 they highlight what approaches work\nwell and they considerably improve the visualization quality.  This\nwould also improve the comparison that you draw from Figure 1.\n\nWhy did you choose the delta-bar-delta method for optimization?\n\nWhy do you think current approaches are not sufficient for the\ndatasets that you show in the paper?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The visualizations show some features that are better highlighted\ncompared to other methods.\n\nThe method seems straightforward to optimize and does not rely on too\nmany hyperparameters.", "weaknesses": "The method does not seem scalable, contrary to the authors claim.  The\nCS divergence includes a summation over all p_j and q_j, hence you\nhave quadratic complexity when optimizing.\n\nContinuing the point, there are no large-scale visualizations.  While\nthe authors claim that their approach could be scaled, I am sceptical\nof it previsely because of the definition of the CS divergence.\n\nMisc:\n\nsome citations could be added, e.g. on p. 3 (The role of\nnormalization) you could cite NCVis (Artemenkov & Panov, 2021,\nhttps://arxiv.org/abs/2001.11411); an approach that estimates the\nnorm. const. via NCE (Gutmann & Hyvarinen, 2012).  The role of the\nnormalization constant is also discussed in Böhm et al. (2022, JMLR)\nas well as Damrich et al. (2023, ICLR).\n\nTalking about the scalability of the method is fine, but there is no\nlarge-scale visualization that demonstrates that the method scales\nbeyond what other methods can esily visualize today.\n\nIn the same vein, there are no timings reported for any of the\nmethods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0r61usZx0U", "reviewer": "Reviewer_L3aD", "summary": "In the paper \"MAP IT to visualize representations\", the authors put forward a novel 2D visualisation method (MAP IT), based on t-SNE. There are two main differences between MAP IT and t-SNE: (1) MAP IT uses unnormalized affinities and replaces KL divergence with Cauchy-Schwarz (CS) divergence which is scale-invariant; (2) MAP IT applies the divergence to the \"marginal\" affinities obtained by summing up the rows of the pairwise affinity matrix. The authors claim that this results in a visualization method which is conceptually different from all t-SNE-like predecessors. The authors use several small datasets (n <= 2000) including a subset of MNIST to argue that MAP IT outperforms t-SNE and UMAP.", "questions": "MAJOR ISSUES\n\n* section 3.1: Z_p and Z_q are never formally defined. While I understand that Z_q is the sum over all N^2 Cauchy kernels, I am not sure what Z_p is in t-SNE. Is it simply 2n?\n\n* MOST IMPORTANT QUESTION: The authors define marginal \\tilde p_j as sum over rows of the unnormalized t-SNE affinity matrix. They don't actually define \\tilde p_ij, but I assume that it's just p_ij * 2n. Note that in t-SNE p_{i|j} values sum to exactly 1 in each row, by construction. p_{ij} are obtained by symmetrizing p_{i|j}, but approximately they still have constant row and column sums. So when the authors define marginal p_j probabilities, to me it seems they are constant (??!) or at least near-constant. So I don't undestand how this can be useful for any dimensionality reduction algorithm. What am I missing?\n\n* Conceptual question 1. The authors put a lot of emphasis on using unnormalized affinities (and replacing KL with CS) and also on using marginal probabilities instead of pairwise probabilties. Are these two things somehow related? Could one use unnormalized affinities and CS loss with the pairwise affinities? Could one use marginal probabilities in the KL loss? Are these two independent suggestions and MAP IT just happens to implement both, or are these two suggestions somehow related and follow from each other?\n\n* Conceptual question 2. The authors put a lot of emphasis on using unnormalized affinities, but their CS loss function performs normalization within the loss function (Equation 5). This normalization leads to the N^2 repulsion term similar to t-SNE (Equation 8). To me this seems like the authors simply \"moved\" the normalization from one place (affinities) to another place (loss function), but nothing much changed compared to t-SNE. What am I missing?\n\n* The beginning of section 4 says that MAP IT uses perplexity 15. But in caption of Figure 3 and later in the text (esp. Appendix C), the authors mention k=10 value as if MAP IT uses kNN graph with k=10. How does perplexity 15 relate to k=10? This is very confusing.\n\n* Major limitation: the authors only have implementation that allows them to embed n=2000 data sets. That was fine 25 years ago, but in 2023 this is a major limitation. What is confusing to me, is that in Figure 8 the authors show that they can reduce the runtime 100x fold, and still obtain nearly the same result, but they only show it on the same n=2000 subset of MNIST. Why not run this 100x-sped-up approximation on the entire MNIST? That would be interesting to see!\n\n* Major limitation: no quantitative evaluation. E.g. for MNIST one could do kNN classification in the 2D space, and compare MAP IT with t-SNE/UMAP. One could also compute various NN preservation metrics. Would of course be much more interesting to do this on the entire MNIST and not on the n=2000 subset...\n\n\nMINOR ISSUES\n\n* page 2, formula (1): the minus sign is missing after the last equality sign\n\n* page 2, formula for p_ij in t-SNE: there should be 2n in the denominator, not just 2.\n\n* page 3, \"the role of normalization\": see Damrich et al 2023 https://openreview.net/forum?id=B8a1FcY0vi for parametric t-SNE. This paper would be important to cite in various places, including in the Appendix A\n\n* page 3: \"marginal probabilities\" appear in Definition 2 but have not been properly defined yet.\n\n* section 3.2, second line: one of the p_j = should be q_j =.\n\n* section 3.3: this section needs some introduction. By the end of section 3.2 it seems that the method is already defined. So why do you need another treatment in section 3.3? This needs more motivation.\n\n* page 14: relationship between t-SNE and Lapl. Eigenmaps was discussed in https://jmlr.org/papers/v23/21-0055.html and https://epubs.siam.org/doi/10.1137/18M1216134, it seems one should cite them here. And \"not to have been discussed much in the literature\" is not exactly right.", "limitations": "", "rating": 3, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "I initially found the paper interesting, as it shows a good understanding of existing 2D visualization methods (t-SNE/UMAP) and develops what seems to be a novel alternative approach. I also agree with the authors that their MAP IT visualization of n=2000 subset of MNIST looks interesting and very different from t-SNE/UMAP.", "weaknesses": "Unfortunately, in the end I was confused by the presentation and not convinced by the paper. One big issue is that the paper is hard to understand: formulas have typos, many terms are not properly defined, overall section structure is sometimes confusing, etc. Another big issue is that the authors only show results on tiny datasets and do not seem to have a working scalable implementation that would allow embedding even a modest-sized full MNIST, let alone datasets with millions of points. The third issue is complete lack of quantitative evaluations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)