The tree autoencoder model, with application to hierarchical data visualization
Authors: Miguel Á. Carreira-Perpiñán
Kuat Gazizov
Venue: NeurIPS 2024 poster (2024)
Keywords: visualization
dimensionality reduction
decision trees
principal component analysis
autoencoders
Primary area: interpretability_and_explainability

Abstract: We propose a new model for dimensionality reduction, the PCA tree, which works like a regular autoencoder, having explicit projection and reconstruction mappings. The projection is effected by a sparse oblique tree, having hard, hyperplane splits using few features and linear leaves. The reconstruction mapping is a set of local linear mappings. Thus, rather than producing a global map as in t-SNE and other methods, which often leads to distortions, it produces a hierarchical set of local PCAs. The use of a sparse oblique tree and PCA makes the overall model interpretable and very fast to project or reconstruct new points. Joint optimization of all the parameters in the tree is a nonconvex nondifferentiable problem. We propose an algorithm that is guaranteed to decrease the error monotonically and which scales to large datasets without any approximation. In experiments, we show PCA trees are able to identify a wealth of low-dimensional and cluster structure in image and document datasets.

The Tree Autoencoder Model, with Application to Hierarchical Data Visualization
Miguel Á. Carreira-Perpináá Dept. of Computer Science and Engineering University California, Merced waw.aarar-ppppnnnnuuumom edu
Kuat Gazizov Dept. of Computer Science and Engineering University California, Merced
kgazizov@ucmerced. edu
Abstract
We propose new model for dimensionality reduction, the PCA tree, which works like regular autoencoder, having explicit projection and reconstruction mappings. The projection is effected by sparse oblique tree, having hard, hyperplane splits using few features and linear leaves. The reconstruction mapping is set of lo- cal linear mappings. Thus, rather than producing global map as in t-SNE and other methods, which often leads to distortions, it produces hierarchical set of local PCAs. The use of a sparse oblique tree and PCA in its leaves makes the overall model interpretable and very fast to project or reconstruct new points. Joint optimization of all the parameters in the tree a nonconvex nondifferen- tiable problem. We propose algorithm that is guaranteed decrease the error monotonically and which scales to large datasets without any approximation. experiments, show PCA trees are able identify wealth of fow-dimensional and cluster structure in image and document datasets.
Introduction
As a form of exploratory data analysis, dimensionality reduction (DR) for visualization seeks to pro- vide representation of dataset in dimension at most 3 (we will focus 2D) that, combined with the human visual ability to pick patterns, is able to find structure of interest in a high-dimensional dataset. Many DR methods have been proposed over the years. Currently, i-SNE (40) and PCA the most popular choices and have seen widespread application in many areas.
Here we advocate for different approach, that of hierarchical local linear projections, which call the PCA tree. Hierarchical DR is not new, but what is new is our definition the model as certain type of tree autoencoder and our algorithm to learn it by minimizing the reconstruction error in self-supervised way, which brings considerable advantages in interpretability and training and inference time. From the outset, acknowledge that DR is hard, ill-defined problem that no single technique can solve satisfactorily. In reducing a dataset to 2D we necessarily have to lose information and produce artifacts. Indeed, the distortions of t-SNE and their impact applications have been well documented ( [22]- However, the PCA tree provides significant, complementary advantages previous methods.
Firstly, PCA trees are practical and intuitive to use. They optimize the reconstruction error, which has clear meaning. They do not require neighborhood graph (and perplexity parameter, etc.), which is tricky to estimate so captures manifold structure, and computationally very costly. The model, tree autoencoder (see later), directly defines nonlinear out-of- out-of-sample mappings (encoder and decoder). Its hyperparameters are natural: the depth A of the tree, which directly controls the resolution (number of scatterplots and reconstruction error), and the sparsity X. which helps to inter- pret the tree decision nodes. Inference on a tree (encoding or decoding) is extremely fast. Training
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

(to find a local optimum, a hard problem because the tree is nondifferentiable) is linear on the sample size and parallelizable, hence scalable to large datasets without the need for approximations.
Second, PCA trees are highly interpretable and, as demonstrated in our experiments, they extract wealth of information from complex datasets. This comes from the fact that both trees and PCA are techniques with well understood interpretability. Specifically: 1) the use of trees to construct a nested hierarchy of maps where an input instance follows a single root-leaf path; 2) the use of sparse oblique trees, with hyperplanes using few features at the decision nodes; 3) the use of linear projections in the leaves, each PCA scatterplot; and 4) the ability to see the data at multiple scales.
Third, a PCA tree uses multiple local latent projections (an "album") hierarchically organized rather than single global one ("atlas") "). The latter is more likely to introduce distortions in trying to arrange many dimensions into a 2D map, and is hard to use with large datasets, requiring a lot of pan and zoom. This is less of a problem if one focuses on local part of the data, particularly if there are clusters. Also, a linear projection is easy to understand and, while it does introduce distortions, it is well understood how this happens: distances can only shrink. If PCA map shows clusters, these are real-in contrast with (-SNE's tendency to create false clusters (G. 22)), for example. Also, PC directions often correspond to some real degree of freedom, and the mean is obviously a useful summary of the data. Thus, while global PCA generally collapses different parts of manifold, local PCAs can succeed- if properly learned. Multiple local maps are like an album of house, where each picture shows different room, but with an hierarchical structure.
A final advantage is that the loss function is really self- supervuue regression problem. This makes it possible to use cross-validation to determine the hyperparameters (although, in an exploratory data analysis, we probably want to explore such hyperparameters manually).
The PCA tree does have its limitations, as follows. It needs access to the explicit feature vectors, unlike graph-based methods, which need instead pairwise affinities. The optimization converges to local optimum, which depends on the initialization. And, as with any DR method, PCA trees reveal only some structure, so practitioners should try multiple, complementary methods.
2 Related work
The literature on DR is vast. We note connections to the most relevant methods.
Non-hierarchical DR Of the many existing DR methods, mention two large groups that particularly important in this paper. One are autoencoders, which learn an encoder or projection mapping and decoder or reconstruction mapping so as to minimize the reconstruction error of each training point. The classic examples are PCA and neural network autoencoders [34,, [7]). where the encoder and decoder are linear and nonlinear, respectively. Our tree autoencoders are another ex- ample. The other are nonlinear embedding methods, which learn the 2D projection of each training point so that Euclidean distances in latent space best match distances or similarities in the high-dt mensional space. These include multidimensional scaling [5). SNE [16), t-SNE [40], the clastic embedding [6] and UMAP [28), among others. Although often proposed as matching distributions of neighbors in the high- and low-dimensional spaces, these methods can be equivalently seen as optimizing a tradeoff of attraction between true neighbors and repulsion between points (6. 41, 22
Hierarchical DR A multiscale view of DR is an attractive idea that has been explored before, often justified by the fact that a single 2D map may miss much of the structure in a complex dataset. We consider two ways of defining the hierarchical structure: soft and hard. In soft hierarchies, one defines a soft, probabilistic tree (20) so that an input instance traverses every tree path with a positive probability. Thus, the model really is probabilistic mixture of the leaves ("experts"") with mixing proportions given by the tree structure. This has the advantage that the model is differentiable, so optimization is straightforward with gradient- or EM-based approaches. Unfortunately, we lose the interpretability and fast training and inference, since an instance reaches all nodes, and the leaves may not localize in input space and overlap with each other. Examples of this are 14. 30 38 19]. A more detailed comparison of soft and hard oblique decision trees appears in [12]
Making the tree decisions hard makes the hierarchy nested, but the optimization is much more dif- ficult (indeed, this an important contribution in our paper). One can construct a hard hierarchy in greedy sequential way by recursively partitioning the dataset, or by using some other tree con-
2

---

struction (such as kd-trees [1]] or cover trees (2]): and then applying some form of DR at each node. However. this is suboptimal (since the node parameters are fixed as they are added, or independently from the leaf parameters) and produces overly large trees. Conversely, one can grow the tree bottom- up by a form of hierarchical clustering. but this also suboptimal. These approaches include work such as 1 24 26 29 and others such as hierarchical self-organizing maps (32), sequential NMF [9] and hierarchical SNE [3]].
Flat, local DR This seeks to estimate collection of local latent maps but without any hierarchy, Again, this can be done in a soft way via probabilistic mixtures (of factor analyzers [13], PCAs [37]. etc.) or in hard way as a form of k-PCAs [21]]. A few works have also sought to align a collection of local DR models into a single global map [33 36 44 23).
Other related models Some works have tried to combine graph-based methods, such t-SNE, with hierarchical DR. For any DR method that does not define an out-of-sample mapping, such as I- SNE and other nonlinear embedding methods, it is possible to learn a tree-based projection mapping [45]- Also, some fast approximations for graph-based embedding methods are based on tree data
structures, such Barnes-Hut trees [43 39 42 35)-
However, this is intended to accelerate the N-body computations, not to define a hierarchical DR.
In view of this, the main novelty of our work is in defining autoencoder consisting of a hard tree encoder and a local linear decoder, and in giving an algorithm to learn it by optimizing the reconstruction error. We believe this is the first algorithm to guarantee monotonic decrease of the error jointly over the tree parameters and local PCAs. We describe both the tree autoencoder model and the optimization algorithm next.
3 Definition of the PCA tree as an autoencoder
Like any autoencoder, the PCA tree defines encoder F and decoder f, but in peculiar way, as follows. Firstly, consider a fixed rooted directed tree structure with decision nodes and leaves indexed by sets 'D and L. respectively, and / = DD U L. Both the encoder and autoencoder use this tree structure. Each decision node i E D has a decision function h,; w., wao): HD - C,, where C, = right, C N, sending instance to the corresponding child of i. Rather than axis-aligned trees, which are a poor model for high-dimensional data, we use oblique trees, having hyperplane decision functions "go to right if w x + who 2 0", with w; E DRD and who E R. The tree's prediction for an instance x is obtained by routing x from the root to exactly one leaf and applying this leaf's predictor (defined below). We define the reduced set (RS) R2 C (1,..., N) of a node E N as the training instances that reach given the current tree parameters.
Encoder projection mapping F This is given by tree mapping T θ): RD + -LRR where the predictor for leaf j has the form of a linear mapping F, Ux; = (x where Uj IR DxL is an orthogonal matrix and μ E RR_ The encoder parameters are O (w;, WeD U [U;, My Jizc- Thus, the encoder maps an input instance x E RR" to a leaf index j E L and an L-dimensional real vector = U (x (ty). which an optimum (see later) will be the PCA projection in that leaf. This means that the PCA tree does not have common latent space of dimension L where all instances are projected. Instead, it has one separate L-dimensional PCA space per leaf. Thus, the PCA tree latent space C x R.' is mixed discrete-con concrete-oontinuouu]] although it can also be seen as separate continuous L-dimensional PCA space per leaf.
Decoder or reconstruction mapping f This maps leaf index j and L-dimensional vector z (in L x 4) to a vector in D It consists of set of linear mappings of the form f U,,1,,) = U,Z+ + My E..
Tree autoencoder We can now define the autoencoder as the composition of the decoder and encoder, T = f F. Conveniently, we can absorb the leaf index implicitly into each leaf. Thus,
We could define the autoencoder so it uses single, global latent space. However, this complicates the optimization (although it could be done with the method of auxiliary coordinates (MAC) of [8) by considering the problem as a nested function). Also, the per-leaf space arises naturally from the fact that the encoder partitions the space into leaf regions.
3

---

local autvencoderr
single path
encoder
(x)
projection
3, z
3 = 3
decoder
32
fz(2²)
42
j 4
reconsir.
J1
tree partitions RD into leaves
Figure I: Illustration of the tree autoencoder model with a data space R a tree of depth A with leaves - = {1.2, 3, 4), defining latent space (album) of four 2D spaces.
A = 0 (PCA), F 1.10
A tree
1 initial, F. = 0.84
A = 1 final, F = 0.08
W1. Wb
U2
Figure 2: PCA tree 2D toy data set. Left plot: regular PCA (PCA tree with A = 0). Rest of plots: PCA tree with A 1. Mean py: diamond; principal component direction U, and variance: dashed line and arrows; decision boundary W1,W10 at the root: solid line.
T(x; θ) is simply a regression tree identical to the tree encoder Tx: θ) but where the predictor mapping of leaf j has the form (x; U).(,,) of rank T, < D, and it is the composition fj F of leaf j's decoder with the encoder.
(43) = U, U. (1,) My Note this is linear mapping
Fig. illustratee the tree autoencoder idea. Fig. shows a PCA tree on 2D toy example using latent dimension ==
Optimization algorithm
Our objective function is the regular reconstruction error of autoencoder T: R.D RRD with an l regularization term of hyperparameter 2 on a training set (xn L.N C R:D:
E Σ | T(x,; 0)1 + (will S.t. -
Thus. the PCA tree is trained like a regression tree which maps real vectors to real vectors. It consists of fixed tree structure (which will take as complete of depth A); sparse oblique decision nodes, consisting of a hyperplane split using few features (as encouraged by the & sparsity penalty); ); and linear low-rank leaves. The following theorem explains why we call "PCA tree" (in fact, designed the form of the loss function and tree so that this would happen).
Theorem 4.1 (optimality condition over the leaves). The optimal { 13 hee given the remaining purameters are fixed, i.e.:
E(() S.1. UJU (U;-5,
min
corresponds setting each (U) the principal components of R2, the RS of leaf j.
Proof. Because of the separability condition (theorem 4.2) and the fact that {w;, waler are fixed, problem 2 is equivalent to
min
Σ ||xn - (xm: U₁, (3,1))113 s.t. UJU,= L,
(3)
neR;

---

which (since the objective and constraints separate) is also equivalent to solving this for each leaf j E L separately:
min Ug R
+ s.t. U I.
(4)
The solution of the latter problem is well known be given by PCA, i.e. 2j R2 EnER, X is the mean of the training instances in R3 and U3 consists of the L eigenvectors of the covariance (x)) 1exxn-1i -13)" associated with its largest L eigenvalues.
matrix Σj R.y EXER, (Xn -n,)-,xxx,,
We borrow the idea of alternating optimization over the tree nodes from 7 (Tree Alternating Op- timization (TAO)), which is fundamental be able to update the parameters so as reduce the objective function. Firstly, at any decision tree making hard decisions, each input instance follows exactly one root-leaf path. This results in the following separabilityy condition.
Theorem 4.2 (Separability condition), Let T(x; ②) be the autoencoder tree and C. N a nonempty set of nodes that are not descendant from each other. Call 0; the parameters in node i. Then, as a function of the parameters {0;: i E S) (i.e., fixing all other parameters O rest O {0,: E S) the function ) of eq. [ can be equivalently written as
E = Σ Es(O;; Press) + Erese O rea))
(5)
'ES
where {Eg i E 8) and Erest are certain functions.
Proof. Analogous to that in 77. It follows from the fact that the reduced sets of all nodes in S are disjoint, because the tree makes hard decisions.
That is, optimizing over the parameters of any set of nodes which are not descendants of each other separates: we can equivalently optimize each node on its own over its parameters and using only its RS. This simplifies the problem considerably and introduces significant parallelism: for example, all nodes at the same depth can be optimized in parallel. Indeed, our overall algorithm will process nodes from the leaves towards the root, optimizing all nodes at the same depth at each step.
Second, we still have to solve the problem of optimizing ( over the parameters of one given node, This simplifies into a reduced problem (RP). If the node is a leaf j. theorem 4.1 gives us the answer: we set the leaf's s Uj. f4 to the PCA on Ry. This is the exact solution the optimization over the leaves, so the overall objective function value will either decrease or stay constant. If the node is a decision node i, optimizing ①I over W,, W/o is equivalent to RP as given by the following theorem.
Theorem 4.3 (Reduced problem over decision node). Consider the objective function E(O) of eq. ① and a decision node E DD Assume the parameter values of all the nodes except are fixed. Then, the optimization problem miDw.,waa E(O) is equivalent the following problem:
min F., (,,,,, Wan) = Σ Tem (Ten: (x(X;;; Wi, Wso)) + A/|wa|l1 We,
(6)
nER:
where: Ri is the reduced set of node i; we define the weighted 0/1 loss Lin (To:: C. - CR+ U fO} for instance n E R2 as (an( 3) = (nn(y) Ian (T.)) Vy E C;: we define the pseudolabel J.n arg argminyec, ly) the "best" child of for (or any Van arg argminyec, (n((y) in case of ties); and we define the function lini C. + E. as lin = l|x,, Tx O 12 for any C, (child of i), where T=(::0, .)) is the predictive function for the subtree rooted at node z.
Proof. Analogous to that for the decision node RP in 7 A difference is that there the tree was a classification tree with the 0/1 loss, which resulted in an unweighted problem; while here we use the reconstruction error, which results in a weighted problem in ( This follows from the fact that all a decision node can do with an instance is send it down its left or right child, and the ideal choice is the one that results in the lowest reconstruction error downstream from that node.
The reduced problem of eq. (6 is an rrrrgullarzedd weighted 0/1 loss binary classification problem over a linear classifier h, with binary pseudolabels {Tm)), defined as the child of that gives the best reconstruction for Xn under the current tree. This problem is NP-hard, but we can typically
5

---

get good approximate solution by solving an r-rreuular surrogate loss instead. We use the logistic loss with instances weighted as in theorem We can guarantee that the overall objective function value decreases or stays constant by accepting the surrogate solution only if it improves over the previous parameten which empirically is usually the case. This means each node update, hence each overall iteration over all nodes, monotonically decreases ①.. We stop when there is little change in the parameters or objective, or when we reach a set number of iterations.
This concludes the algorithm, whose pseudocode is in fig. 6 Essentially, it repeatedly updates the nodes in turn: leaf solves a PCA, and at decision node it solves an f--regularized, instance- weighted logistic regression problem (we use LIBLINEAR (1dh. The tree is initialized as a random median tree, i.e., at the root we pick a random direction for the weight vector and bias so that half of the instances go to either child; and we repeat this recursively down the tree.
5 Computational complexity for training and inference
Throughout, assume a complete tree of depth A: sparse decision weight vectors having sD nonzero values on average, with E [0, 1] (so 1 means dense vectors); and a latent dimension s L S D at each leaf (L < 3 for visualization). As cost we use the number of scalar multiplications.
5.1 Inference
By inference we mean the time to map an input instance x E RD to its leaf j E C and latent vector z E R This requires traversing single root-leaf path of depth A, at cost O(sDA), and computing the leaf PCA projection, at a cost ((LD), total @([ + s))D) (which, for A = O, i.e., regular PCA, corresponds O (I.D).. This is very fast, since both L and A are very small. Reconstructing a latent vector z E TR at a leaf j E L costs (LD).
5.2 Training
The cost of one iteration, i.e., updating each node in the tree once, is as follows. For the decision nodes, this equals to setting up the RP (i.e., computing the pseudolabel losses) and solving it with one logistic regression in each node's RS. To work this out we note that the RSs of all nodes at the same depth total N instances, and we assume logistic regression to be linear in the dimensionality and sample size. Then, the total cost of all decision nodes has two terms. The first is the pseudolabel cost over all decision nodes, which is N - 1)). This is due to the fact that, at each decision node, we have to send each training instance down the left and right children to compute their losses (actually, we need only send down one child if we precompute the losses), and the decision nodes span depths from 0 to A 1. The second is the RP solution, whose cost is proportional to that of running A logistic regressions on the whole dataset (at depths ... A - 1), (c; DA). where >> 0 is constant factor (which includes the average number of iterations of the logistic regression solver). This cost as in the sparse oblique classification trees of [ Asymptotycally, totals ((NDA)).
For the leaves, we have peculiar situation. Say a leaf has a RS with M instances. The cost of PCAE on that RS is D(MD2 + D2) if D < M and @DMM² + 02 M3) if D 2 M, depending on whether we compute the eigenvectors of the D D covariance matrix of the N x N Gram matrix, respectively, where 02 >> 0 is a constant factor. Assume for simplicity that each RS has M = N2 instances (balanced partition) and define the critical depth A logz ( Then:
cost, all leaves
[ A < A shullow tree regime:
@(ND² + +22D22 O(N= N2 I O((1 o2))
A A+, deep tree regime:
For given dataset of fixed N and D, the cost depends on the tree depth A and has a turning point when A = A For datasets having N < D, we are always in the deep regime, but if N > D then we can be in the shallow or deep regime for small or large A, respectively. Interestingly, this leads
"In fact, in practice we find that always accepting the update (even if it increases the objective) works as well and is simpler. This makes the iterates slightly noisy. but over iterations the objective decreases steadily. 'It is possible to accelerate this via approximate SVD algorithms or matrix sketches to compute just the top eigenvectors, as well as using a good initialization, but here we consider the cost of a full eigendecomposition. 'If N < D we always run PCA first and reduce the data D < N without error.

---

to a non- mon-oooottncc cost as a function of A, as shown in fig. 3. because the shallow regime cost increases with A but the deep regime one decreases with A. This is surprising because the deeper the tree the more leaves it has, yet the faster they train. The reason is that the PCA cost is superlinear on the sample size, but the sample size per leaf decreases proportionally to the number of leaves.
We emphasize that, as noted above, in both regimes the leaves' cost is strictly upper bounded by (1 + N (with equality if A A*), hence this cost is at most linear in N and quadratic in D. just like in regular PCA. For fixed N and D. the leaves cost first dominates the decision nodes cost (shallow tree regime) because the former includes a term N D that dominates the decision nodes' term (N B(NDA DA?), since A < D in practical cases. But as A grows (deep tree regime) the leaves cost decreases and reaches N ((D + C2) for A log, N (when each leaf contains a single instance), so the overall cost is eventually dominated by the decision nodes, ( DAR). As a useful summary, for fixed A the rough cost ((ND²) for shallow trees and (N for deep trees- which is asymptotically faster than PCA! (although very deep trees having few instances per leaf are likely not practical). This makes the algorithm highly scalable large sample sizes without the need for any approximation. This is a significant advantage over neighbor embedding algorithms such as 4-SNE, which have a quadratic cost on N and require some approximation to reduce this 39 42 43
Parallel training From the separability condition, all nodes at the same depth can be updated in parallel, which accelerates the training considerably. Assume for simplicity we have 2 processors (which is perfectly feasible for trees having depth 4, as in our experiments). Then the costs are as follows. For decision nodes, we have the cost of running logistic regression on A datasets of sizes N, N. ; N2 (from the root to the leaf parents), a geometric series which is upper bounded by 2.,, hence a total cost of (2c, N D). i.e., _ times faster than the sequential computation. (The pseudolabel computation separates over instances and is thus 2 times faster.) For the leaves, we have the cost of running PCA in single leaf, i.e., 2 times faster than the sequential computation. Again, this is a significant advantage over t-SNE, which cannot be easily parallelized.
6 Experiments
In summary, we show the following: we confirm our theoretical predictions about monotonic de- crease of the objective function and training time; compare the reconstruction error with PCA; and demonstrate how PCA trees are highly interpretable and extract significant structure from complex datasets. We use several datasets of different types (images, documents), some of which appear in the appendix.
6.1 Training time and scalability to large datasets
Fig. 3 (right plots) shows learning curves for different datasets and tree depths. As can be seen, the objective function decreases monotonically over iterations, and converges to near-optimal solution in usually less than 10 iterations.
Fig. 3 (left 2 plots) shows the training time per iteration in seconds (theoretical and actually mea- sured for the MNIST dataset), as a function of the tree depth A in one processor (sequential computation, without parallelism). For the theoretical estimate we used constant factors = 1, C2- (see section (5) and s (dense decision node weight vectors). To vary the dimensionality D E {64, 784, 1600, 2500}, we subsampled or oversampled the MNIST images to 8 x 8, 28 x 28 (original size), 40 x 40 and 50 x 50 pixels, respectively. The plots confirm what we described in our complexity analysis: the computation at the leaves first increases until A = A then decreases, resulting in a non-monotonic total training time. The critical depth A at which the change happens decreases with D, from around 10 to 5; note the actual depth at which the total time peaks is different, because the latter also considers the decision nodes' cost, which is linear on A.
NN logg ())
Fig. (plot 3) shows scalability to larger sample sizes using the Infinite MNIST dataset (27] (images of 28 x 28, so = 784). We ran the PCA tree for 10 iterations, when it approximately converged.
The linear cost of the PCA tree is clear as a slope 1 in the log-log plot. Training on 1M samples with depth 4 takes less than an hour. contrast, t-SNE [39] and UMAP (28) are slower and have a superlinear cost, even though the implementations we used are not exact (they use approximations, such as Barnes- Hut trees or neighbor subsampling, to accelerate the computations, besides finding approximate rather than nearest neighbors).

---

MNIST (thcoretical)
MNIST
Infinite MNIST
Fashion MNIST
Amazon Reviews
210
x76
Training time (5)
Objective funection
320
1d"
950
1.4
1.90
x
UMAP
150
14
1.25
120
depth A 10
10
10" sample size N
20
20
depth A
iteration
iteration
Figure 3: Plots 1. 2: training time per iteration on (Infinite) MNIST for PCA trees with different N D. A. Plot 3: training time for PCA trees (10 iterations) and for t-SNE and UMAP (default user parameters). Plots 4, 5: learning curves for PCA trees of different depths on several datasets.
Fashion MNIST
20newsgroups
Reconstruction error
g
A m.d
Figure 4: Squared reconstruction error per sample of PCA as a func- tion of the number of principal components L and of PCA tree us- ing L = PCs in each leaf, for different depths on two datasets: Fashion MNIST (N
40
PCA
=
PCA tree
30
0.62
L= 11
20
0.4
A
18
0.2
60000, D 784) and 20newsgroups (N 11314. D 72764).
10
10a
10
10a
10
10a
# principal components
principal components L
6.2 Reconstruction error
Fig. shows the reconstruction error for PCA and PCA tree. Although the PCA tree uses L in each leaf, it is able to achieve a much lower error than PCA, which would need a much larger number of components match it. This is the result of the PCA tree ability to learn a partition of the data and local PCAs that are jointly optimal.
6.3 Interpreting and exploring PCA tree visualizations
Fig. (see also figs. I0 in the appendix) shows results for the Fashion MNIST datase This consists of N 60 000 grayscale images of 28 28 pixels (so D 784), each showing clothing or shoe item, labeled into 10 balanced classes. The features are the pixel intensities in [0.1]. The class labels were not used during training, they were only used for visualization purposes. We show a PCA tree of depth 4 (using À = 100), thus having 15 decision nodes (with weight vectors shown as 28 x 28 images) and 16 leaves (showing a 2D PCA scatterplot and the mean and PCs as images). The appendix contains results for other datasets (images: MNIST, documents: Amazon Reviews). Even at a glance we can see lots of structure in the tree: many classes organize hierarchically in a meaningful way; decision weight vectors are sparse and highly meaningful, often separating groups of classes by focusing on the discriminant regions of the image; the PCs in the leaves usually are highly meaningful, indicating the change of some relevant degree of freedom; and the leaf scatter- plots show clusters or class structure; among other things. We comment on some of these in detail. For reference, fig. (appendix) shows the 2D global plot by PCA, t-SNE and other algorithms.
Global tree structure Although algorithm is unsupervised, it has the ability separate differ- ent types of classes. For example, leaves LI and L2 contain different types of shoes, while Icaf L14 contains only bags. Some classes (e.g. Pullover and Shirt in L8) differ in tiny details and can only be separated if using the labels (remember that minimizing the reconstruction error seeks maximum- variance directions, which are not necessarily aligned with class variation). The coordinate axes in the leaves show the most variance in the data within the leaf's region. Since the RSs are nested along the tree hierarchy, we can also show scatterplot at each decision node (appendix fig. D which shows how classes and other patterns are progressively separated as one descends deeper into the tree. However, note the optimal parameters if the tree was shallower would differ from those.
Local tree structure The decision nodes' weight vectors select features sparsely, often focusing on parts of the image that can differentiate groups of images and send them selectively to the left or
'It is instructive to compare these results with those of training sparse oblique classification tree on the Fashion MNIST dataset [14], there interesting similarities and differences.
8

---

right subtree. The figure is annotated in some places to make this clear. For example, decision node D2 separates clothes "with" and "without" sleeves. In some cases, this results in the tree separating actual classes. For instance, node D14 separates "outerwear" type of clothes from "bags", which explainable by simply looking at the decision node weights and the part of the image where they focus: blue values indicate "if the image has neckline and shoulders" (like outwear clothes) and red values indicate "if it has wide frames" (like bags).
PCA at the leaves Since each leaf applies 2D PCA on its corresponding reduced set, its linear projection scatterplot shows the most variance directions in the leaf region. As expected with PCA, amplified by the fact that it focuses on a region of the whole data, this often shows insights about the intrinsic local structure of the data. In particular, we can usually identify the coordinate axes (PCs) with meaningful quantities or degrees of freedom (labeled in the scatterplot below each leaf' in fig. 55. For example, leaves L1, L2, L4, L7, L14, L15 and L16 contain objects of specific type, such as L1 containing high-heel and high-ankle boots and sandals, or even isolating a class, such as L14 isolating bags. Interestingly, we find all these leaves often detect similar degrees of freedom: usually, PCI is (overall) pixel intensity in the image and PC2 is object size (either height or width). Again, this is the result of minimizing reconstruction error, which projects along maximum-varianne directions. Also, since overall intensity and object size are correlated, this is seen in the PCA plots as triangular shapes whose vertex corresponds to low-intensity images (caused by either overall low intensity or by a very small object). This can be clearly seen in leaf L4 (consisting of T-shirts and tops), as well as in other leaves: L7/L15 intensity-widdte L1/L2/L16 sitensity-heighte L14 intensity- size of bags. The density of the projections in the 2D embedding is also informative. For example, in leaf L4, narrow tops are much more frequent than thin tops.
Some leaves find degrees of freedom not aligned with a PC direction, but visible in the seatter- plot, such as elongated clusters. These often correspond different classes, where the direction of elongation is some meaningful degree of freedom within the cluster. For example, as shown in the bottom of fig. [5] leaf 1.3 contains two types of clothes: "shirts" and "shoes". PC1 represents the class discrimination direction, while PC2 represents intensity. Local inspection of each cluster separately demonstrates that both clusters have maximum variation indicating pixel intensity. The shoe cluster also has variations in "weight" (lightweight shoes below and chunky shoes above). The "shirts" cluster has variation in T-shirt width. Leaves L4, L15, and L16 have almost single class: shirts, dresses, and slim sneakers, respectively, and all of them have similar variations, i.e., intensity as PC1 and width or thickness as PC2. Finally, note that the appearance of clusters or complex structure within a leaf scatterplot suggests it would be worth either further expanding that leaf or using a deeper tree, which could be done in an interactive way.
This dataset provides evidence of what patterns are real and whether they are detected by a given DR method. If clusters appear in a PCA plot, they are real (unlike in a t-SNE or UMAP embedding). This is because, in an orthogonal linear projection, distances either decrease or do not change, but cannot increase. Another example is the fact that the image overall intensity arises throughout the PCA tree leaves as a principal component. This is not surprising: intensity changes in this dataset are large, and thus carry considerable variance, which the local PCAs pick. Even the global PCA is able to pick that too and locate low-intensity images in the lower-left area of the 2D embedding (see appendix fig. [0]. However, both t-SNE and UMAP do not; we have verified that low-intensity images are mapped all over the embedding in haphazard way. A similar effect happens with the Amazon reviews document dataset (appendix section (E): individual document classes appear in PCA plots as "streaks", caused by the document length (which changes the norm of the TF-IDF feature vector), and converging on the area occupied by short documents. Again, such an important pattern is lost in the t-SNE and UMAP embeddings.
7 Conclusion
We have defined a new model for data visualization, the PCA tree, as a tree autoencoder that pro- duces set of hierarchical low-dimensional maps, and have given algorithm learn it by mini- mizing the reconstruction error, based on Tree Alternating Optimization (TAO). PCA trees are fast for training and out-of-sample inference, and highly interpretable. We hope they will provide a use- ful tool for data visualization. Beyond this, tree autoencoders have application in dimensionality reduction in general, as well as in clustering, subspace clustering, data compression, fast search and other problems that we are exploring.

---

Askle books
books
Bag
eneatyye Sancule
rgh
Sheet
Sindal
Shics
Lone sleeved clsthes Tignnrrs
Olo
Stices
Begi
Dipa
Palaonrr
Theener
Tsldlitshoots
Pilgts
Walk neckline
ligh top and
Long slaeveR
Lang coot
Shoes tore piaele in the zudiic repion
with how sundals
wiltie
mi
Hight heef sandals
Long sleeved ckopes Haus
lebcllss Gresses Low hep sneaken
Pullowes
DV
BB
nedkline
shoellons
Mlag modker
Sceaker sminged bottontally
iran uslarvoue
15
HR
BB
B
Dresses are an arraneed vestically
310
shirs
Shoes have pixels
Sucakers are arranged hosizosrally
in the middlle region
14
LIS
L16
Thickness
Intensity
Width
Class discrimination
Intensity
Intensity
Intensity
Mcan
PCI
PC2
Mezn
PC1
PC2
Moun
PC1
PC2
Mean
PC1
PC2
Figure 5: PCA tree trained the Fashion MNIST dataset (A 4, 100, RMSE per pixel and image of 0.158). The decision nodes' weight vectors (and the leaves' PCs U,) are shown as 28 28 images, with negative/zern/posittve values colored blue/white/red, respectively. Each leaf shows a 2D PCA scatterplot of its RS (instances reaching it). and helow it the mean μ4 as a grayscale image and the PCs U, as color images. To the right of the scatterplot, bar chart displays class proportions and class means. The legend (top left) shows, for each class, its mean (grayscale image), color (for the scatterplots) and description. For visualization purposes, the tree split into its left and right root subtrees (fig. shows the whole tree). The bottom panel zooms into two regions of the tree, for decision nodes 8 and 14. You may want zoom into the figure see more details.
10

---

Acknowledgments and Disclosure of Funding
Work supported by NSF award IIS-2007147. We thank Magzhan Gabidolla for help with the TAO implementation.
References
[1] W. K. Allard, G. Chen, and M. Maggioni. Multi-scale geometric methods for data sets II: Geometric multi-resolution analysis. Applied and Computational Harmonic Analysis, 32(3): May 2012.
[2] A. Beygelzimer, S. Kakade, and J. Langford. Cover trees for nearest neighbor. In W. W.
Cohen and A. Moore, editors, Proc. of the 23rd Int. Conf. Machine Learning (ICML,06), pages 97-104, Pittsburgh, PA, June 25-29 2006.
[3] S. Bird, E. Klein, and E. Loper. Natural Language Processing with Python: Analyzing Text with the Natural Language Toolkit. O'Reilly & Associates, 2009.
[4] C. M. Bishop and M. E. Tipping. A hierarchical latent variable model for data visualization. IEEE Trans. Pattern Analysis and Machine Intelligence, 20(3):281-22) Mar. 1998.
[5] I. Borg and P. Groenen. Modern Multidimenssonal Scaling: Theory and Application. Springer Series Statistics. Springer- Verlag, Berlin, second edition, 2005.
[6] M. Á. Carreira-Perpince The elastic embedding algorithm for dimensionality reduction. In Fürnkranz and Joachims, editors, Proc. of the 27th Int. Conf. Machine Learning (ICML 2010), pages 167-174, Haifa, Israel, June 21-25 2010.
[7] M. Á. Carreira-Perpiin Perpiñán and P. Tavallali. Alternating optimization of decision trees, with appli- cation to learning sparse oblique trees. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems (NeurIPS), volume 31, pages 1211-1221 MIT Press, Cambridge, MA, 2018.
[8] M. Á. Canreira-Perpiñaae and W. Wang. Distributed optimization of deeply nested systems. In S. Kaski and J. Corander, editors, Proc. of the 17th Int. Conf. Artificial Intelligence and Statistics (AISTATS 2014), pages 10-19, Reykjavik, Iceland, Apr. 22-25 2014.
[9] A. Cichocki and R. Zdunck. Multilayer nonnegative matrix factorisation. Electron, Lett., 42 (16):947-948, Aug. 2006.
[10] R.-E. Fan, K.-W. Chang, C.-J. Hsich, X.-R. Wang, and C.-J. Lin. LIBLINEAR: A library for large linear classification. Machine Learning Research, 9:1871-1874, Aug. 2008.
[11] H. Friedman, L. Bentley, and A. Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Trans. Mathematical Software, 3(3):209-226, 1977.
[12] K. Gazizov, A. Zharmagambetov, and M. Á. Carreira-Perpiñaán. A critical comparison of soft vs hard oblique classification trees. 2025.
[13] Z. Ghahramani and G. E. Hinton. The EM algorithm for mixtures of factor analyzers. Technical Report CRG- TR- 96-1, University of Toronto, May 1996.
[14] S. Hada and M. Á. Parreira-Perpiñán. Interpretable image classification using sparse oblique decision trees. In Proc. of the IEEE Int. Conf. Acoustics, Speech and Sig. Proc. (ICASSP '22), pages
Singapore, May 22-27 2022.
[15] R. He and J. McAuley. Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. In Proc. of the 25th World Wide Web Conference (WWW20016), pages 507-517, Montreal, Canada, May 11-15 2016.
[16] G. Hinton and S. T. Roweis. Stochastic neighbor embedding. In S. Becker, S. Thrun, and K. Obermayer, editors, Advances Neural Information Processing Systems (NIPS), vol- ume 15, pages 857-864. MIT Press, Cambridge, MA, 2003.

---

[17] G. E. Hinton and R. R. Salakhutdinov. Reducing the dimensionality of data with neural net- works. Science. 313(5786):504-5077
28 2006.
[18] M. Honnibal, I. Montani, S. Van Landeghem, and A. Boyd. spaCy: Industrial-strennth natural language processing in Python. https://spacy... 1o, 2020.
[19] O. Irsoy and Alpaydın. Unsupervised feature extraction with autoencoder trees. Neurocom- puting, 258:63-73, Oct. 4 2017.
[20] M. I. Jordan and R. A. Jacobs. Hierarchical mixtures of experts and the EM algorithm. Neural Computation, 6(2):181 1214, Mar. 1994.
[21] N. Kambhatla and T. K. Leen. Dimension reduction by local principal component analysis. Neural Computationn 9(7):19331111 Oct. 1997.
[22] D. Kobak and P. Berens. The art of using t-SNE for single-cell transcriptomics. Nature Com- munications, 10(5416), 2019.
[23] D. Kohli, A. Cloninger, and G. Mishne. LDLE: Low Distortion Local Eigenmaps. J. Machine Learning Reseurch, 22(282): 2021.
[24] W. Liao and M. Maggioni. Adaptive geometric multiscale approximations for intrinsically low-dimensional data. J. Machine Learning Research, 20:163,, 2019.
[25] M. Lichman. UCI machine learning repository. Iuttp://archive uci eduum 2013.
[26] A. V. Little, M. Maggioni, and L. Rosasco. Multiscale geometric methods for data sets I: Multiscale SVD, noise and curvature. Applied and Computational Harmonic Analysis, 43(3):
Nov. 2017.
[27] G. Loosli, S. Canu, and L. Bottou. Training invariant support vector machines using selective sampling. In L. Bottou, O. Chapelle, D. DeCoste, and J. Weston, editors, Large Scale Kernel Machines, Neural Information Processing Series, pages 301-320. MIT Press, 2007.
[28] L. McInnes, J. Healy, J. Melville. UMAP: Uniform manifold approximation and projection for dimension reduction. NKKV:1802.0344: Dec. 6 2018.
[29] G. Mishne, R. Talmon, I. Cohen, R. R. Coifman, and Y. Kluger. Data-driven tree transforms and metries. IEEE Trans. Signal and Information Processing over Networks, 4(3):451 Sept. 2018.
[30] I. T. Nabney. Y. Sun, P. Tiño, and A. Kabán. Semisupervised learning of hierarchical latent trait models for data visualization. IEEE Trans. Knowledge and Data Engineering, 17(3):384 400, Mar. 2005.
[31] N. Pezzotti, Т. Höllt, B. Lelieveldt, E. Eisemann, and A. Vilanova. Hierarchical stochastic neighbor embedding. Computer Graphics Forum, 35(3):21-30, June 2016.
[32] A. Rauber, D. Merkl, and M. Dittenbach. The growing hicrarchical self- self-organizing map: Ex- ploratory analysis of high-dimensional data. IEEE Trans. Neural Networks, 133))113311341, Nov. 2002.
[33] S. Roweis, L. Saul, and G. Hinton. Global coordination of local linear models. In T. G. Dietterich, S. Becker, and 7. Ghahramani, editors, Advances Neural Information Processing Systems (NIPS), volume 14, pages 889-896. MIT Press, Cambridge, MA, 2002.
[34] D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning internal representations by error propagation. In D. E. Rumelhart and J. L. MacClelland, editors, Parallel Distributed Comput- ing: Explorations in the Microstructure of Cognition. Vol. I: Foundations, chapter 8, pages 318-362. MIT Press, Cambridge, MA, 1986.
[35] J. Tang, J. Liu, M. Zhang, and Q. Mei. Visualizing large-scale and high-dimensional data. In Proc. of the 25th Inf. World Wide Web Conference (WWW'2016), pages 287-297, Montreal, Canada, May 11- 11-15 2016.
12

---

[36] Y. W. Teh and S. Roweis, Automatic alignment of local representations. In S. Becker, S. Thrun, and K. Obermayer, editors, Advances Neural Information Processing Systems (NIPS), vol- ume 15, pages 865-872. MIT Press, Cambridge, MA, 2003.
[37] M. E. Tipping and C. M. Bishop. Mixtures of probabilistic principal component analyzers. Neural Computation, 11(2):43-482, Feb. 1999.
[38] Tiño and I. Nabney. Hierarchical GTM: Constructing localized non-linear projection man- ifolds in principled way. IEEE Trans. Pattern Analysis and Machine Intelligence, 24(5): 639-656, May 2001.
[39] L. J. P. van der Maaten. Accelerating t-SNE using tree-based algorithms. J. Machine Learning Research, 15:3221-3245, Oct. 2014.
[40] I.. J. P. van Maaten and G. Hinton. Visualizing data using I-SNE. Machine Learning Research, 9:2579- 2605, Nov. 2008.
[41] M. Vladymyrov and M. Á. Carreira-Perpiñáán Pastial-Hessian strategies for fast learning of nonlinear embeddings. In J. Langford and Pineau, editors, Proc. of the 29th Int. Conf. Ma- chine Learning (ICML 2012), pages 345-352, Edinburgh, Scotland, June 26 - July 2012.
[42] M. Vladymyrov and M. Á. Carreira- Pereira-Perpiinn... Linear-time training of nonlinear low- dimensional embeddings. In S. Kaski and Corander, editors, Proc. of the 17th Int. Conf. Arti- ficial Intelligence and Statistics (AISTATS 2014), pages 968-977, Reykjavik, Iceland, Apr. 22- 25 2014.
[43] Z. Yang, J. Peltonen, and S. Kaski. Scalable optimization for neighbor embedding for visu- alization. In S. Dasgupta and D. McAllester, editors, Proc. of the 30th Int. Conf. Machine Learning (ICML 2013), pages 127-135, Atlanta, GA, June 16-21 2013.
[44] Z. Zhang and H. Zha. Principal manifolds and nonlinear dimension reduction via local tangent space alignment. SIAM J. Sci. Comput., 26(1):313 (31):3311-338) 2004.
[45] A. Zharmagambetov and M. Á. Peaeerra-Perpinán. Learning interpretable, tree-based projec- tion mappings for nonlinear embeddings. In G. Camps- Valls, F. J. R. Ruiz, and I. Valera, editors, Proc. of the 25th Int. Conf. Artificial Intelligence and Statisties (AISTATS 2022), pages 9550-9570, Online, Mar. 28 30 2022.
13

---

A Appendix supplemental material
A.1 Algorithm pseudocode
input training set -
sparsity hyperparameter À 2 0: initial tree T(; θ) of depth A with parameters O {w6 WeD U (U,, M Hylsec .o....,NNA +- nodes at depth 0, A, respectively
for each i N: generate R, (instances that reach node i) on tree T
repeat
for A down 0 parfor i Naa if E then
(4, PCA with components R₁ else
generate pseudolabels T, and weights Wn for each instance Xn R; [w,, w + fit l-regullarzeed weighted binary classifier on {(x: Wn, Fn Jn)RRER with penalty
end if end for end for
for each E W: update R₂ on tree T
until stop return T
Figure 6: Pseudocode for the PCA tree optimization algorithm.
14

---

B Experimental Details on Datasets and Algorithms
MNIST and Fashion MNIST We use only the training set of size (NV 60000) and scale pixel values to [0, 1] by dividing by 255.
20newsgroups We use only the training set (N 11314) without headers, footers, and quotes. The text is converted to lowercase, and all URLs, email addresses, punctuation, and numbers are removed. Stopwords are removed using NLTK B1 and the dataset is lemmatized using SpaCy [18). We then apply scikit-learn's 's TfIdfVectori zer with default parameters, resulting in dimension of 72764.
Letter Recognition task for classifying 26 capital letters in the English alphabet (25 the training set (N 16000). Standardization applied to all features.
We use only
Amazon Reviews We subsample text reviews from the large collection in 15 (version from 2014).
Reviews are selected from the following categories:
Toys and Games: [Learning & Education: (Mathematics & Counting, Reading & Writing),
Games: (Board Games, Card Games)]
Beaaty: [Skin Care: (Hands & Nails, Face), Hair Care: (Hair Color, Shampoo)]
We use scikit-learn's CountVectorizer to extract unigrams from the raw texts. We set stop_ 'engrds=''ngishh'. min_df=O. fo__df000000 .002 and fax__f=0.= Then, we apply the FridfTransformer. The resulting dataset size is N = 20000 and D = 9430.
The summary of the datasets is the following:
MNIST
FMNIST
Letter
20newsgroups
Amazon reviews
N
60000
60000
16000
11314
20000
D
784
784
16
72764
9430
K
10
10
26
20
Implementation We implement PCA tree using a combination of C++ and Python. Decision node optimization implemented in C++ using LIBLINEAR [10), and leaf optimization is implemented in Python using PCA from the scikit-learn library with svd_ aedd_ssoveee cooover=aree wowpaacpcckaaa. and n components=2. We use the following hyperparameters: À and X 0.01 for 20newsgroups and Amazon Reviews. The algorithm includes early stopping criterion that terminates training there is no decrease the training error for iterations with change of less than 10-3
for MNIST and Fashion MNIST, = 1 for Letter,
For t-SNE, we use the scikit-learn implementation (the default number iterations 1 000). For UMAP, we use the implementation from htttps///uaat learn. readthedoca io/ Lo/en/latest lann/st//t///// (the default number of iterations 500 if the dataset size has fewer than 100000 points and 200 otherwise).
Hardware All experiments are conudcted on Intel(R) Xeon(R) CPU ES-2699 v3 @ 2.30GHz, 256GB RAM.

---

C Additional experimental results
MNIST
FMNIST
Letter
20newsgroups
Amazon reviews
Objective function
xtof
x10#
02
1.5
1.06
1.90
1.4
1.04
1.85
1.8
20
1.80
1.4
1.0
1,00
1.75
iteration
iteration
iteration
iteration
iteration
Figure 7: Objective function across training iterations for different datasets.

---

D Interpretation and comparison of PCA tree visualizations
D.1 Fashion MNIST
Figure 8: The same tree as in Figure S in unsplitted view.
The tree structure allows visualization of PCA scatterplots not only for the leaves but also for the decision nodes, as shown in Fig. Note how PCA projections of each class or group of classes separate distinctly from each other.
Figure 9: The same tree as in fig. but with decision nodes representing PCA projections on their respective reduced sets.
PCA
t-SNE
UMAP
Figure 10: Scatterplots of different dimensionality reduction methods for the same dataset as in fig. (Fashion MNIST) (N 60000, D 784). Class colors match the labels from fig. [

---

D.2 MNIST dataset
We evaluate our algorithm on the MNIST dataset. noticeable that almost half of the PCA tree leaves are nearly pure, containing mostly samples from a single class, while the other half contain classes that can be linearly transformed into each other. For example, leaf L16 contains three classes: 4. 9, and 7. By adding the top bar and removing the middle bar, we can achieve the following linear transformation:
9 - 7, as shown by the first principal component. The second component represents pixel intensity, so digits go from thin to thick from bottom to top. Now, consider the pure leaf L12. The digit changes its inclination from "to the right" to "to the left" on the x-axis and its intensity from bottom top.
PCA overlaps nearly all data points except for those representing the digit "1".
t-SNE distorts the global structure of the data. It forms clusters such that each cluster represents separate class, which can be misleading in terms of distances. For example, the cluster for the digit "2" appears close to the cluster for "1" and far from "3", but in the high-dimensional space, the relationship the opposite. A similar issue occurs with the digits "0" and "5".
UMAP also distorts the positions of data points. may show that the digit "3" is closer "6" than to "4", while in the original high-dimensional space, the relationship is the opposite.
Such distortions can result in wrong interpretations of the data's 's structure and cluster relationships.
Figure 11: Trained PCA tree structure on the MNIST dataset with a reconstruction loss of 0.29
PCA
t-SNE
UMAP
Figure 12: Scatterplots of different dimensionality reduction methods for the same dataset as in fig
(N 60000, 784). The class colors correspond to the labels in fig. 11

---

E
Amazon Reviews Dataset
Consider now the dataset from different domain, specifically text data. We use the Amazon Re- views dataset, represented as TF-IDF features, containing 20,000 samples and 9,430 features. The decision tree structure, illustrated in fig. [3] allows us to visualize the top words corresponding the highest and lowest weight values, indicating important words at each decision node. Furthermore, using highest and lowest entries for both principal components, can be demonstrated variation across reviews, see table[[]
By visually inspecting the leaves, can identify similar reviews from different classes. For exam- plc, the first leaf contains many samples from different classes, but most of these samples are short reviews about "returns" and "refunds". Elongated clusters within the leaf reveal reviews about dif- ferent topics, such as games (left cluster) and cosmetics (right cluster). Additionally, reviews from different classes may pertain to items with similar purposes. In leaf L3, there are four classes, but all are related to games: the top cluster is about "funny learning", the left cluster is about "teaching children to count using cards", and the right cluster is about "card games".
Similar to previous examples, this tree has principal components that represent semantic or class separation. For instance, in leaf L5, the first principal component separates children's games from adult games, while in leaf L11,, the first principal component distinguishes one class from the rest. Note that some leaves are pure, such leaf L7 or L10, and within these leaves, clusters correspond to topics. Leaf L7, for example, is split into three topics: "cuticles" (left), "polishing" (top), and "nail growing" (right), although all samples are from the same class.
t-SNE and UMAP significantly overlap most of the classes. While PCA projections present some cluster elongations, they also show overlapping classes and do not reveal the inner local structure.
Figure 13: Trained PCA tree structure on the Amazon reviews dataset with a reconstruction loss of 0.9004
PCA
t-SNE
UMAP
Figure 14: Scatterplots of different dimensionality reduction methods for the same dataset as in
fig. B (N- -20000, D 9430). The class colors correspond to the labels in fig. [
19

---

Leaf
1st principal component
2nd principal component
L1
cream, hand, skin, cards, deck, card, hands, bb
cards, cream, hand, skin, hands
item, expected,
playing, box
book, dies, mag- netic
L2
hands, hand, dry, lo- tion, greasy
color, brown, coloring
blonde, natural,
blonde, light, ash, highlights, toner
color, hands, lasts, lotion, hand
L3
conditioner, sham- poo, using, clean, soft
gray, scent, color, gray, conditioner,
scent, clean, strong, suave, nice
cover, coverage
color, cover, cover- age learn, easy, fun, numbers, cards, children, help
L4 cards, game, card, play, players
numbers, letters, learn, loves
learning,
card, letters
number,
L5
apples, friends, version
game, adult,
year, old, toy, loves, bought
toy, learning, child,
year, old, game, ap- ples, play
toys, educational
L6
diary, lock, key, fun, game, family, journal, daughter playing, play
set, chess, pieces, board, nice
fun, diary, lock, game, key
L7 nails, grow, stronger, weak
cuticles, cuticle, oil, nail, dry
nail. polish, coat, base, art
cuticles, nails, cuti- cle, oil, dry
coat,
L8
blocks, nice, qual- brown, color, dark, ity, wood, usa
nice, board, pieces, price, smells
blocks, color, medium
brown,
medium, black
dark,
L9
soap, hand, hands, soaps, scent
loves, son, played, game, daughter
loves, soap, son, daughter, abso- lutely
played, game, fun, family, blast
L10
skin, face, sensitive, dry, acne
price, buy, bought, good, amazon
face, wash, clean, cleanser, acne
skin, price, work, sensitive, dry
L11 kids, game, love. playing, fun
shampoo, dandruff, scalp. shampoos, clean
dandruff. scalp, clear, anti, shoul- ders
shampoo, kids, love, suave, volume
L12 good, smell, smells, works, really game, play, family, fun, playing
red, color, dye, brown, dark
dye, purple, bleach, black, did
red, good, smell, smells, brown
L13
math, love, stu- dents, facts, leamn ing
love, students, per- fect, price, abso- lutely
math, game, fun, skills, kids
L14
serum, vitamin,
skin, acid,
game, play, friends, fun, family
friends, playing, game
played,
play, kids, easy, old, family, time
hyaluronic
L15
expansion, game, packs, cards, pack
letters, magnets, fridge, magnet, magnetic
magnets, fridge,
letters, expansion, game, case, lower
hold, strong, fall
L16
34, shampoo, color, does, doesn
loved, games, game, family, board
loved, gift, birthday, games, game, niece, journal
board, fun, family
Table 1:
Two principal components of each leaf in PCA tree[]3] showing the words corresponding to the top 5 positive and negative entries the U, columns (principal components' coefficients).
20

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
End of introduction and throughout paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach ad- dress problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
21

---

Justification:
Algorithm section.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple-
mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yss]
Justification: Main paper and supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model). releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
22

---

Answer:
[No]
Justification:
We plan to make available code in the future.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see
data submission guidelines (https://nips) cctppaalll/piiidee///eeeeeaassop tails.
the NeurIPS code and
for more de-
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines /etpgdddeeeoeeeebmiieeeeeeeeeeee
for more details. The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
luttps://nips.co
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experiment section and supplementary material. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined other appropri- ate information about the statistical significance of the experiments?
Answer: [No]
Justification:
Too much computation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
23

---

It should be clear whether the enror bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Experiment section and supplementary material
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https::ttttssrpppp::: httpar/ppp.cpppl.i////hcccciuuus htw..//eeeiiccccceeeeeeeeee.
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper diseuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification:
Generic algorithm for dimensionality reduction.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, pat.sss.pppssiiispae thcode. com/ datasete has curated licenses for some datasets. Their licensing guide can help determine the cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
25

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsourcing research
with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "XYEkqW2DCV", "reviewer": "Reviewer_7zsa", "summary": "The authors nicely describe an extension of [5] to unsupervised dimensionality reduction.\nThe paradigm is quite different from regular DR (unique scatterplot) as it yields a tree and thus multiple leafs.\nThere are some similarities with hierarchical clustering (to some extent).\nThe authors also emphasize a connection with autoencoders (though readers might understand NN autoencoders while here these are rather linear auto-encoder, equivalent to PCA).\nAttention is dedicated to the computational complexity and parallelization of the tree structure.\nThere is one illustrative experiment in the paper and some other classical benchmarks are reported in the suppl.mat.", "questions": "See above", "limitations": "The limitations appear quite clearly in the text, although the first limitation at the end of section 1 does not really make sense (t-SNE uses graph but is essentially DR and thus assumes/uses coordinates (or feature vectors)).", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper is very nicely structured and written.\nThe method is intuitive and well explained.\nThere are sufficient experiments.", "weaknesses": "The novelty with respect to [5] might seem a bit limited.\nThe proposed visualization paradigm is unconventional and probably shares the same shortcomings as those of a dendrogram in hierarchical clustering.\nThe global structure is probably hard to tell, which is not different than the usual drawback of t-SNE and such (although a user study might answer that question).\nTo some extent (again), the proposed visualization is reminiscent of what was done in the past with SOMs (here the leafs would resemble a 1D SOM). The vast literature about SOMs might contain some variants with hierarchies or PCAs in the grid nodes... (open question)\nAnother possible comparison is with some older spectral DR techniques, working by stitching local 2D projections (back to a unique scatterplot then...).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review and in particular for the connections with other methods.\n\n- *Novelty with respect to [5].*\n\n  Since trees making hard decisions are not differentiable, we cannot use gradient-based methods and instead we use alternating optimization over the nodes. While [5] also used alternating optimization, there the model was a classification tree. Here we propose a different model, tree autoencoders, and adapt the alternating optimization algorithm accordingly. We believe this is the first time that this type of autoencoders have been proposed and successfully trained on high-dimensional data.\n\n- *The proposed visualization paradigm is unconventional.*\n\n  We agree with this, so we put significant effort in illustrating it in the experiments of section 6.3 and figure 4.\n\n- *Shortcomings as those of a dendrogram in hierarchical clustering.*\n\n  Hierarchical clustering algorithms (either bottom-up or top-down) do not optimize a global objective function over the tree and clustering. One critical advantage of our work is that it does define a global objective function of the parameters of the tree and the local DRs at the leaves, which our algorithm monotonically decreases at each iteration.\n\n- *The vast literature about SOMs might contain some variants with hierarchies or PCAs in the grid nodes.*\n\n  Thanks for noting SOMs, which we missed in our literature review. Indeed, we have now found some papers exploring hierarchical SOMs (all based on Rauber et al 2002). They are conceptually similar to what we describe in lines 73ff: one grows a hierarchical SOM recursively in a greedy way. This doesn't optimize a global objective function over all the tree and individual SOM parameters (indeed the regular SOM is well known not to optimize an objective function, its iterative process is stopped manually). The regular SOM also does not define an encoder and decoder explicitly, as it is essentially a vector quantization with a topology bias. We'll note this in the paper.\n\n- *Older spectral DR techniques that stitch local 2D projections to a unique scatterplot.*\n\n  We did mention this in the related work (lines 82-83). We did not compare with them in the experiments because we already included the single-scatterplot techniques that are currently most popular (PCA, t-SNE, UMAP).\n\n- *t-SNE uses graph but [...] thus assumes feature vectors.*\n\n  We can run t-SNE without feature vectors, as in MDS, if we have access to pairwise similarities between instances (or neighbor probabilities), although admittedly most applications do use feature vectors directly.", "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": "mmOw17uLaO", "reviewer": "Reviewer_2dBg", "summary": "The paper proposes a hierarchical data visualisation method that is a combined use of oblique decision tree and PCA over leaf nodes. In experiments, the authors demonstrate the visualisation results of the proposed method for a few datasets and compare the reconstruction errors with standard PCA.", "questions": "How is the oblique tree trained in their experiments?\n\nI invite the authors to comment on why the results from the three theorems are important.", "limitations": "No discussion on limitation.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The demonstrated visualisation results are useful.", "weaknesses": "Very limited originality. The proposed method works by firstly training an oblique decision tree and then applying PCA over examples assigned to each leaf nodes. This is a straightforward use of very classical existing methods. It hardly qualifies as a new method…\n\nSince this paper contributes to hierarchical data visualisation, their experiments should focus on comparison with the use of existing hierarchical DR for data visualisation.\n\nMost theoretical results/analysis on PCA tree come from simple applications of classical PCA results. The three theorems do not seem to present any significant result, for which I invite the authors to comment on.\n\nThe method description is quite hard to follow, which appears like a piece of overly complicated writing for simple method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your questions, but it seems there are several misunderstandings in your review. Hopefully our answers below will clarify them.\n\n- *Very limited originality [...] The method description is quite hard to follow, which appears like a piece of overly complicated writing for simple method [...] How is the oblique tree trained in their experiments?*\n\n  It appears you may have misunderstood our algorithm. If, as you say, our algorithm consisted of 1) training (somehow) an oblique decision tree and 2) given this tree, applying PCA over the examples assigned to each leaf, then we'd agree that this is straighforward (and suboptimal). But what we do is different, as follows. 1) We define a global objective function (eq. (1)), the reconstruction error, over all the tree parameters (at the decision nodes, which route the examples to the leaves; and at the leaves, which effect the DR). 2) We propose a new algorithm that monotonically decreases this objective function until convergence, thus iteratively rerouting examples to find an optimal, hierarchical partition of the feature space, and correspondingly optimal local dimensionality reduction at each leaf region. The algorithm is based on alternating optimization over the tree nodes' parameters. Overall, then, we define a new model (the tree autoencoder) and train it jointly over all its parameters (which is not straighforward due to the nondifferentiable, nonconvex nature of the tree).\n\n- *Comparison with the use of existing hierarchical DR for data visualisation.*\n\n  As noted in our related work, hierarchical DR is either soft (which makes it hard to interpret) or hard (for which, as far as we know, there is no work that optimizes some desirable objective function over the tree). For comparison purposes, we could have constructed a tree using a traditional algorithm such as CART (greedy top-down recursive partitioning) and fitted PCA at the leaves, but this works extremely poorly (it generates huge trees with a large error). Instead, we opted to compare with state-of-the-art methods such as t-SNE.\n\n- *The three theorems do not seem to present any significant result.*\n\n  Our theorems have several purposes. 1) They make it possible to apply alternating optimization over the decision nodes and leaves, which require the solution of certain precisely-defined optimization subproblems. 2) They ensure that our algorithm monotonically decreases the objective function. 3) They indicate under what conditions nodes can be trained in parallel. 4) For the leaves, the Reduced Problem theorem gives an optimality condition akin to a KKT condition for differentiable problems.\n\n- *How is the oblique tree trained in their experiments?*\n\n  We do not just train an oblique tree. We train a tree autoencoder having oblique decision nodes and linear autoencoders at the leaves, jointly over all the parameters. The fundamental technique is alternating optimization over the nodes, whose solution is given by our theorems. Section 4 gives the details and figure 5 the pseudocode.\n\n- *No discussion on limitation.*\n\n  We do have a discussion on limitations, which starts in line 58.", "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": "KKkrDEH2fn", "reviewer": "Reviewer_DywJ", "summary": "This study proposes PCA trees as a hierarchical data visualization tool. PCA trees hierarchically partition the data space using hyperplanes, with the partition pattern represented by a binary tree. PCA is then applied to each leaf node of this binary tree. The parameters of a PCA tree consist of coefficients defining the hyperplanes for splitting at internal nodes and projection matrices for PCA at leaf nodes. The function representing the fitting of the PCA tree to the data satisfies a separability condition with respect to its parameters. Therefore, we can perform effective alternating optimization. The characteristics of PCA trees are also verified through visualization of real-world datasets such as Fashion MNIST.", "questions": "What strategies or techniques are employed to avoid converging to local optima?", "limitations": "The paper acknowledges that the solution may converge to local optima. Further discussion on strategies to mitigate this issue would enhance the work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* Formulation that reduces hierarchical data visualization to the optimization of a certain type of decision tree.\n* Proposal of an algorithm for efficient execution of this optimization.\n* Thorough explanation of the results of applying the proposed method to real-world datasets such as Fashion MNIST.", "weaknesses": "PCA trees divide the data space into multiple disjoint subsets and project the data points in each subset into a different low-dimensional space. Therefore, it is debatable whether this truly achieves dimensionality reduction in the strict sense. The description of ''dimensionality reduction'' in the abstract and introduction may be misleading. It might be more appropriate to view this as a data visualization technique. Furthermore, there are doubts about whether the visualization provided by PCA trees is intuitively easy to understand. Analysts need to conceptualize and integrate complex hierarchical partitions of high-dimensional space along with projections in various directions. In particular, intuitively grasping the positional relationships of data points between different nodes might be challenging. However, given that the assessment of visualization quality is largely subjective, PCA trees may still have value when used complementarily with other visualization techniques.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review.\n\n- *Does our PCA tree truly achieve dimensionality reduction in the strict sense?*\n\n  It does indeed, but we need to define the latent space and its coordinates accordingly. This latent \"space\" consists of 1) the discrete index of a leaf (local latent space) and 2) a continuous latent vector (within that local latent space). For example, in figure 4 (Fashion MNIST dataset), an image is \"projected\" to a triplet $(j,z_1,z_2)$ (index and two real numbers), and reconstructed back from such a triplet. See lines 107ff. The encoding and decoding mappings are correspondingly defined based on that space. This makes our autoencoding framework well defined mathematically, and indeed the right way to handle multiple latent spaces. We do acknowledge that it is unconventional within traditional DR, where autoencoders are traditionally seen as purely continuous and on a single latent space.\n\n- *Is the visualization provided by PCA trees intuitively easy to understand?*\n\n  Using multiple latent spaces is not a perfect solution. We acknowledge our work's limitations in section 1 and caution practitioners to use multiple methods. But, are methods using a single space, such as t-SNE, really \"easy to understand\"? The necessary, misleading distortions arising from using a single latent space have been well documented. Ultimately, all methods must make compromises to arrange high-dimensional data onto some kind of visualization. For a visualization to be useful, it should extract meaningful patterns from the data, and we think that hierarchical local DR has important, complementary benefits in this respect compared to global-space methods (see section 1).\n\n- *Strategies or techniques are employed to avoid converging to local optima.*\n\n  Given the nonconvexity of the problem, this is an unavoidable issue (as is the case with t-SNE, for example). At present, we simply try different random initializations of the decision node hyperplane directions (the hyperplane bias is set to achieve a 50%/50% partition of the samples, so all leaves receive about the same number of samples in the first iteration). We have explored other ideas, for example doing a bottom-up merging as in agglomerative clustering, but we cannot recommend them as consistently better.", "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": "sYQwDECq9R", "reviewer": "Reviewer_Aeto", "summary": "This paper proposes a dimensionality reduction approach that comprises a tree of local PCA projections. The authors make the following contributions:\n1. A mathematical description of their approach.\n2. An optimisation algorithm and pseudocode to fit their method to a training set, together with the computational complexity of inference and training of the model giving evidence of the excellent properties of the approach.\n3. Experiments with benchmark datasets of various types confirming the claims around scalability and computational complexity, the reconstruction error, and examples of using the approach to explore and interpret datasets.", "questions": "How to set the hyperparameters? What is the sensitivity to hyperparameter values? How significant is the effect of local minima to this optimization problem?\n\nGraph-based similarity approaches have several advantages and disadvantages compared to distance-based methods like the approach in this paper. Given that the proposed approach sub-divides data space to explore local structure, is there an opportunity to unify the two approaches in the leaves?", "limitations": "The paper describes limitations of the proposed approach, although to some extent these are limitations for all dimensionality reduction / visualisation methods. The paper does not speak much to the effect of local minima. The paper does not explore the sensitivity to hyperparameters. It might also be interesting to explore dimensionality reduction in synthetic datasets where there is known structure, e.g., the noisy swiss roll datasets, box datasets and others, for example used in Lee and Verleysen, Nonlinear Dimensionality Reduction (2007) as an approach to compare a wide set of methods.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This is an interesting, high quality, well written and argued paper that addresses a significant problem in data exploration and visualisation. Whilst there is a plethora of approaches for dimensionality reduction of complex datasets, no one approach has really emerged. The proposed approach marries the benefits of PCA (including consistent distances) with a hierarchy which allows understanding of sub-regions of the space, giving a representation that is explainable and fast to compute compared to other approaches such as UMAP or t-SNE.\n2. The related work is to the point and identifies the state of the art / popular dimensionality reduction methods. They highlight the novelty of their work against this background and why their approach is desirable. The work is original to my understanding, building on hierarchical DR methods, particularly hierarchies of sparse oblique trees.\n3. The mathematical definition of their approach is clear and concise and the proofs around the optimisation clearly highlight why their approach has good properties around the possibility of parallelism, and benefits in computational complexity. In particular, the discussion around the surprising properties in the computational complexity was very interesting.\n4. There is a nicely articulated discussion of experimental results, which confirm the properties around the optimisation algorithm, its scalability and reconstruction properties for a well known set of benchmark datasets of various types: image and text, as well as a detailed description of examples of the local structure found in the Fashion MNIST dataset. The experiments generally confirm the claims stated in the introduction.\n5. Whilst there is no code available at this stage, the benchmark datasets are readily obtainable and there is sufficient detail around the experiments that the work could be reproduced with some effort.", "weaknesses": "1. There are several hyperparameters for the approach, most notably $\\lambda$ and $\\Delta$. However, the paper does not describe how to set these parameters nor the sensitivity of the approach to different values.\n2. At the moment the approach builds out a full tree to depth $\\Delta$, but it would be better if the tree could be deeper in particular areas depending on the data in the associated region. In fact, several nodes would be improved in the example in fig. 4 if the tree were deeper - e.g. L3, L5, L8 and L11.\n3. I couldn't see the parameter settings for the experiments with t-SNE and UMAP.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your very thorough review.\n\n- *Hyperparameter setting and sensitivity.*\n\n  In principle, since an autoencoder defines a supervised problem, the hyperparameters might be chosen using a hold-out validation set. However, for visualization purposes we set them manually as described next.\n\n  The tree depth $\\Delta$ controls the granularity of the result and the level of detail seen. The deeper the tree, the lower the reconstruction error (eventually reaching zero error), but the more leaves it has and the harder it is to interpret. Larger datasets may require deeper trees. For visualization purposes, we tried depths up to 4 (= 16 leaves).\n\n  The hyperparameter $\\lambda$ controls the decision node hyperplane sparsity. The larger $\\lambda$ is, the fewer nonzero weights we have (and, if all weights in a hyperplane are zero, that node can be pruned, as it becomes redundant). In our visualization experiments we used relatively few nodes, so we set $\\lambda$ to a value (100, in line 273) that results in zeroing unnecessary weights, which improves interpretability, but is not aggressive enough that nodes are actually pruned. Empirically, we observe $\\lambda$ has to vary exponentially (say, from $10^{-3}$ to $10^6$) for it to affect significantly the results.\n\n  We'll note this in the paper.\n\n- *It would be better if the tree could be deeper in particular areas.*\n\n  Yes, in fact we mentioned this briefly in lines 319ff. This could be done in different ways. One is by tuning the hyperparameters $\\lambda$ and $\\Delta$ (by cross-validation or interactively); note that using a deep enough tree with high enough sparsity will prune nodes and result automatically in an irregular tree structure. Another way, not explored here, is to have the training algorithm expand nodes on the fly in some way. Perhaps the simplest way (noted in line 321) is to have the user expand nodes selectively in an interactive way (and running the algorithm to re-optimize the new tree).\n\n- *Parameter settings for the experiments with t-SNE and UMAP.*\n\n  We set the hyperparameters for t-SNE and UMAP to their default values in the implementations we used (perplexity 30 and 15, respectively).\n\n- *Effect of local minima.*\n\n  Given the nonconvexity of the problem, this is an unavoidable issue (as is the case with t-SNE, for example). At present, we simply try different random initializations of the decision node hyperplane directions (the hyperplane bias is set to achieve a 50%/50% partition of the samples, so all leaves receive about the same number of samples in the first iteration). We have explored other ideas, for example doing a bottom-up merging as in agglomerative clustering, but we cannot recommend them as consistently better.\n\n- *Combining graph-based similarity approaches with subdividing the data space.*\n\n  We have some ideas about that which hopefully we'll develop at some point...", "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:

Meta-review: The majority of the reviewers lean towards accept. I also find the proposed method interesting and novel, which may spark further research ideas. Thus I also recommend the paper be accepted.

In the camera-ready version, the authors should revise their paper based on the discussions with the reviewers. Additionally, for future work, I suggest the authors expand their comparisons to other hierarchical methods, such as those suggested by reviewer 2dBg. While the authors provided extra comparisons during the discussion phase, the use of reconstruction error is somewhat unsatisfying as the proposed method is explicitly designed to optimize this error. Other metrics should also be included in future work, although admittedly good metrics are hard to come by in these problems.
Decision: Accept (poster)