End-to-End Training of Unsupervised Trees: KAURI and DOUGLAS

The authors methods connect KMeans directly with tree-based models. This simplifies the clustering process if one would like to use a tree for this purpose. The connection with mutual information is natural.

We thank you for your thorough review and appreciate your understanding of our work.

The objective of KAURI is introduced as being equivalent to optimizing the K-means objective. In that case, what should we consider as the motivation behind this study? I would like to understand the rationale for using this research approach instead of traditional Kernel KMeans. While one example is provided in Appendix E, I also wondered if there might be cases where KAURI doesn't perform well conversely. I believe the clear difference lies in the fact that it is an end-to-end approach. What might be the motivation behind this choice?

The global motivation for the study was to introduce a complete framework on tree architecture and GEMINI training. The link with kernel KMeans is here to serve as a theoretical justification for the expected performances of one specific case of this framework: KAURI.

We believe that there exists indeed a clear difference between the end-to-end training approach of such a tree compared to twofold methods, especially with Table 4 (now 5) displaying a shallower structure on average, Figure 2 highlighting how we deal better with non-axis aligned decision boundary beyond Appendix E (now F).

Still, none of our experiments showed KAURI as significantly underperforming compared to kernel KMeans. In addition, the normalised KMeans scores suggested by reviewer #2 (dexj) that we added to the paper remain better or close on average.

How do the experimental results vary when the temperature parameter in Equation 9 is modified? Although the temperature is set to 0.1 throughout this paper, it is known that this parameter is crucial in the context of differentiable trees. (See Reference [1])

Our preliminary study on the parameters did not reveal significant changes in ARI or KMeans score for temperatures ranging from 0.01 to 10. Therefore, we chose to let the default parameter to 0.1 as advised by Yang et al., authors of DNDTs, in our experiments.

Please provide information on the machine resources used, computation time, memory usage, and the amount of parameter tuning (See Weakness part).

To begin with, the memory complexity of DOUGLAS is that of DNDTs. It grows in $\mathcal{O}((T+1)^d)$ with $d$ the number of features and $T$ the number of cuts, e.g. in section 5.1: 20 features cut in 2 is approx. 2^20 parameters. Then, the autodiff framework and the number of samples make this number grow linearly. Consequently, with the double encoding which is required for the Wasserstein GEMINI, the model associated to the car evaluation dataset would already take multiple GBs which saturated our GeForce RTX 2080 (8GB). The time performances of the model's complete training could range from a couple of seconds for the Haberman survival (fewest features and 2 clusters) to half an hour for the Avila dataset (20,000 samples and 12 clusters). The number of clusters intervenes on the complexity of the GEMINI computation by a $K^2$ factor.

For KAURI, beyond the complexity per split which could be at worst of $\mathcal{O}(n^2[(L+d)(n+K)+dL]+L^2(d+K))$ as reported in App. C.1.4 worst for $n$ samples, $L$ leaves, $d$ features and $K$ clusters, practical numbers would be roughly less than a second for the iris dataset, and close to a few minutes for the Avila dataset.

In the Appendix, it's stated that the handling of categorical variables varies depending on the dataset. However, information is only provided for the US congressional votes dataset, affecting the experiment's reproducibility.

The other method used for the categorical variables in other datasets is one hot-encoding. While this was briefly mentioned in Table 2 for the car dataset, we clarified it in Appendix D (now E).

We thank you for appreciating the writing and our use of novel objective functions for discriminative clustering.

[...] While the original paper (Ohl et al., 2022) shows good results on unsupervised neural network training, it is still not clear what makes this objective well-suited for clustering problems, particularly with trees.

To elaborate on the choice of this objective (GEMINI), there exist very few clustering objectives that can train discriminative models, i.e. without parametric assumptions on the data distribution $p(x)$. Most of these objectives are related to mutual information. Yet, Ohl et al. highlighted the superiority of GEMINI to MI in discriminative clustering. Moreover, the connection of this objective function to KMeans makes it a sensible objective for clustering. These reasons motivate the choice of GEMINI for training unsupervised trees.

The paper has quite limited novelty. It adapts a recent clustering objective into the traditional CART-type greedy recursive partitioning algorithm to learn the axis-aligned tree (KAURI algorithm). And similarly with DOUGLAS algorithm, which just uses the existing differentiable deep neural decision trees.

We would like to emphasize that we showed here novel types of splits that are not part of the initial CART algorithm, e.g. completely reallocating samples to other or new clusters. We extended GEMINI to train non-differentiable models, contrary to its initial design by Ohl et al. To the best of our knowledge, we are the first to optimise the KMeans objective within a decision tree without prior warm starts, explaining better or similar performances on average.

The paper attempts to motivate for the end-to-end learning of clustering trees rather than using existing clustering algorithm such as k-means as reference. However, both theoretically and experimentally the advantage of end-to-end learning has not been clearly demonstrated.

As KAURI is guided by a kernel KMeans objective, it seems reasonable to us that the performances cannot exceed that of kernel KMeans. Still, we showed shallower tree structures in Table 3, especially when the ideal decision boundary is not axis-aligned as illustrated by Fig. 2.

The datasets used in experiments seem to be quite small [...] Having a dataset of at least MNIST-level size can help to show its scalability.

Adjusted rand index measure used to compare the clustering performance is questionable. As far as I understand, adjusted rand index uses ground-truth class labels but clustering is an unsupervised problem. Reporting both the k-means objective and GEMINI objective might help as they are the objective function being optimized.

We already had an additional dataset (Poker hand dataset) containing approx 1 million entries. We originally discarded the dataset because all entries were 0 of score for ARI, but this experiment clearly shows that KAURI can scale to large datasets. We could not add DOUGLAS for this specific dataset due to the limitations of the Wasserstein GEMINI. We restored this dataset in the results, but discarded its ARI score because all models obtained 0. Still, we would like to draw attention to App. C.1.4 where we report a complexity of $\mathcal{O}(n^2[(L+d)(n+K)+dL]+L^2(d+K))$ at worst for $n$ samples, $L$ leaves, $d$ features and $K$ clusters when choosing the optimal split.

You may see the performance in the global response. As a follow-up on the performance metrics, we added the table with normalised KMeans score on the same benchmark as Table 3. The performances are written in the new Table 4.

Specifically, we followed the suggestion of Reviewer #3 (4Lqz) regarding the placement of section 2.3 and relegated it to the appendix for the table above. This helped the incorporation of proposed related works by Reviewer #1 (xtwY) in the coherence of the section 2.

Why is this particular neural decision tree used for the DOUGLAS algorithm? How interpretable are these trees? Why not just regular soft decision tree?

Assuming you refer to Soft Decision Trees O. Irsoy, O. T. Yildiz, E. Alpaydin ICPR 21, the differentiable neural tree allows us to have a ready-made full structure when training with the Wasserstein GEMINI. Specifically, we found that this objective is expensive to compute and the optimisation of one branch parameter after another like for soft decision trees combined with the combinatorial question of which cluster to affect each new branch would cost even more than the proposal of DNDTs architectures.

The interpretability of DNDTs lies in their soft-binning functions which translate to affectation rules: certain combinations of bins lead to a specific class/cluster. That is why Yang et al., the authors, introduced the notion of active cut points that we used in section 5.3: these are the features for which the bins from the soft-thresholding actually leverage a partition of the data, rather than putting everything in a single bin.

The authors methods connect KMeans directly with tree-based models. This simplifies the clustering process if one would like to use a tree for this purpose. The connection with mutual information is natural.

We thank you for appreciating our proposed simplifications of clustering processes among trees and its "natural connection with mutual information".

The authors results show some improvement over KMeans combined with a supervised tree. But the improvement is small and I'm not sure the improved interpretability is sufficient to strengthen the contribution enough. Interpretability is always a very thorny issue. It is ultimately and under-specified property and its value is in the eye of the beholder. I agree that explain another clustering output using a decision tree leaves something to be desired in terms of elegance. But clusters are often used as a form of explanation, which raises the question why does one need to explain a clustering output to begin with?

We understand that the interpretability can be considered a "thorny issue". In this sense and in order to clarify further the advantages of the proposed end-to-end approach, we added performances regarding the KMeans score of each algorithm, as requested by as well by reviewer #2 (dexj). You may find the table of new results in the global response showing (new Table 4) that not only are our trees shallower, but also well-performing on KMeans objective. Thus, the gain is not only on the subjective topic of interpretability but as well on KMeans performances.

Overall, we remind that interpretability is to begin with a desired property in clustering. As mentionned in the paper Interpretable clustering: an optimization approach (Bertsimas et al., 2020) highlighted by reviewer #1 (xtwY) above: "[...] Clustering algorithms provide little insight into the rationale for cluster membership, limiting their interpretability."

Section 2 strays into topics that are somewhat out-of-place in the document. Discussing the advantages and nuances of the method overly much before the method has been introduced on a technical level is premature. Can portions of section 2 be moved into the discussion?

We thank you for the suggestion of structure and propose to move the section 2.3 into the appendix, and use the remaining space to both present the performances with k-means loss as suggested by reviewer #2 (dexj), then incorporate further references from reviewer #1.

Learning clustering trees is an interesting problem, and the proposed approach has an interesting connection to kernel k-means.

We thank you for providing these interesting references and finding interesting the connection to kernel KMeans.

The performance of the proposed algorithms is comparable to the performance of the simple two-stage approach based on k-means and standard decision trees.

We would like to draw attention to the fact that we maintain comparable clustering performances with shallower trees which we attribute to the end-to-end nature of training. Moreover, and with the questions of reviewer #2 (dexj), we added the table of KMeans score which highlights good or better scores on average for both KAURI and DOUGLAS.

There is important work on clustering trees and density estimation trees that is not considered in the submission, see the references below:

As reviewer #3 (4Lqz) suggests a replacement of some parts of section 2 for clarity and relevance, we chose to move section 2.3 to appendices in order to get more room for the papers mentioned above.