Semi-Supervised Learning of Tree-Based Models Using Uncertain Interpretation of Data

In response to weaknesses:

We are now including as baselines fully supervised KDDTs and semi-supervised PCTs, which are the contributing components that can be used on their own. Thanks for this suggestion.

We believe that improved performance, sometimes by a large margin, is a strong case for the value of the work. Beyond that, we do have reduced computational complexity in the number of samples compared to purely graph-based methods, and we implement similar assumptions while producing a predictive model which is tree-based and has additional utility as a result. We are not sure how to compare fundamentally different methods from a theoretical perspective, as you say, but we are open to suggestions. We do at least thoroughly motivate our approach from a theoretical standpoint.

A consistent measurement of training time is difficult because we are running experiments in parallel on shared resources with variable hardware. Our method is the most time consuming, due largely to the increased cost of fitting with a variance objective and partially also due to using fuzzy trees and selecting a kernel bandwidth hyperparameter. Tree-based methods in general have low memory needs, and ours should not be different, so we don't see a need for a deep analysis of this. Could you clarify the statement: "Although the order has been evaluated, a comparison with other methods is necessary." We tune two hyperparameters, and the search is not fine-grained; it is actually quite coarse. Tuning over the cost-complexity parameter alpha is not at all expensive because it is done by pruning, which avoids repeating the most expensive component of our algorithm, which is fitting trees. As for kernel bandwidth, we use only four candidate values. The other methods do not require hyperparameter choices; this is simultaneously a relative weakness of our method, in that there is some cost of hyperparameter tuning, but also a strength in that these hyperparameters, particularly the kernel bandwidth, adjust the semi-supervised behavior in meaningful ways that are not possible in some of the baseline models, which is perhaps a reason we achieve improved performance. We will note this in the revision.

In response to questions:

Yes, we will give ablation results in the revision by including baselines for each component of the approach. We do not see a need to do ablation, however, for the kernel shape and training kernel approximation. In general, we always use a Gaussian kernel, and the way it is made into a histogram for training is less influential and is ultimately just a tradeoff of cost and approximation error, so we don't think there is a reason to run additional experiments for this. The choice of kernel bandwidth and ccp-alpha are important, however. Would a breakdown of performance across these hyperparameter values address your concern?

There is no hyperparameter search for the current baselines, though there will be for some of the baselines we are adding in the revision. As for our methods, the main cost of tuning is that it necessitates cross-validation, which we make less expensive by doing it only on the leaf assignment phase, which is much less time consuming than tree fitting. If abundant computation resources are available, one of course could and should do cross-validation by refitting the model entirely. As for each parameter, the cost of tuning alpha is negligible since it can be done by pruning the tree; the cost of tuning the bandwidth roughly corresponds to the number of bandwidths we try. In our case, we try 4 bandwidth values, to the cost is roughly 4x. We will note these nuances in the revision.

In response to weaknesses:

In what way can we improve the presentation of existing work? We have referenced, summarized, and described the relationship of our work to other works with related methods. Besides some notational corrections and clarifications, we believe our presentation of the proposed approach is sufficiently formalized - are there specific concerns we can address? We also have a clear sectional structure describing the components of the method. Please let us know if there was confusion, and how we can make it clearer.

Within each section, we motivate the proposed method; in particular, the leaf assignment methods are based on clear assumptions of smoothness and separability, respectively, which are commonly used in SSL methods for other model types. Please let us know if there are specific elements that should be further clarified.

We gave transductive evaluation based on the precedent of the closest related method, Levatic et al. (2017), and because it makes it possible to compare to label propagation. However, based on multiple reviewers' requests, we will instead report inductive performance in the revision and, accordingly, leave out label propagation as a baseline.

In response to questions:

We will clarify the specific items you pointed out. Thanks for this feedback. Please let us know if there are other ways we can improve clarity.

We will give more thorough descriptions of related work, but due to the page limit, it may need to be moved to the appendix. We will also strive to improve section 3.3. We are unsure what you mean by a lack of formality in the related works and in section 3.3. What could help make this more formal?

We see nothing wrong with the notation mentioned - it is common to represent probability density as a function f, and it is the notation used in the original KDDT paper. To clarify, KDDTs do not interpret the inputs as the realization of a random variable; they interpret each input as a random variable itself. We write the distribution of the random variable associated with an input $x$ as $f(\cdot,x)$; in our experiments, it is the Gaussian probability density with center x and standard deviation chosen by cross-validation.

Would making the lemma statements self-contained address this concern? compared to label propagation, the added value is that, unlike label propagation, our method is (1) inductive, (2) tree-based, (3) based on a kernel that is data-adaptive and not tractable to compute fully for use with label propagation, (4) does not require computation of pairwise distance between data points, and (5) is more performant on many data sets in practice, as shown in the experiments. We will clarify these points in the revision.

We gave transductive evaluation based on the precedent of the closest related method, Levatic et al. (2017), and because it makes it possible to compare to label propagation. However, based on multiple reviewers' requests, we will instead report inductive performance in the revision and, accordingly, leave out label propagation as a baseline.

In response to weaknesses:

• We were not aware of this paper - thanks for pointing it out. We will include it in the discussion of related work. We would point out that our method does not construct a similarity graph over the data, but over the leaves; we never compute distance between any two data instances. Also, the tree-based simplification of the implied similarity score, as described in Lemma 1, is one of the reasons we think our method can perform better than a conventional graph-based approach. We will point out these differences in the revision.
• As far as I can tell, there is no code given with the referenced paper, and the method does not look straightforward to implement. Moreover, it appears to depend on parametric learning (of decision trees), which seems like a whole different model class from what we are doing here. Please correct me if I am wrong.
• We have acknowledged computational limitations in the paper, mainly with respect to the tree growth phase, which is the dominant computational cost. We could use sparse graph methods, but the speedup would be insubstantial since this step is not the dominant computational cost. In what ways could we better clarify the scaling properties of our approach?

In response to questions:

• It was not demonstrated experimentally. Measuring adversarial robustness exactly is NP-Hard for tree ensembles [1] and fuzzy decision trees [2], so measuring it experimentally may be difficult, and beyond that, no verification method is known for KDDTs. However, at least for single-tree KDDT-based models, we can provide a lower bound on robust radius using randomized smoothing theory. We will consider what kind of empirical comparison we can make given these limitations and add it to the revision.

[1] Kantchelian, Alex, J. Doug Tygar, and Anthony Joseph. "Evasion and hardening of tree ensemble classifiers." In International conference on machine learning, pp. 2387-2396. PMLR, 2016.

[2] Good, Jack H., Nicholas Gisolfi, Kyle Miller, and Artur Dubrawski. "Verification of Fuzzy Decision Trees." IEEE Transactions on Software Engineering (2023).

In response to weaknesses:

We do not expect consistent advantage for any semi-supervised method. As we stated in the text, the performance of a semi-supervised learning algorithm largely depends on how well its underlying assumptions apply to the data. This is why different methods do well on different data, and why it is common for even well-accepted methods to do worse than purely supervised learning on some data sets. The fact that ours is the best by a notable margin on many data sets is the best we can reasonably expect and is certainly, we believe, enough to demonstrate the value of the method. Our hyperparameter tuning is coarse, but necessary, and we acknowledge this as a limitation. It is also a strength, in some sense, since it allows tuning of the semi-supervised assumptions, which is not possible in methods that lack such hyperparameters.

We will add baselines which are a fully supervised versions of our method, that is, just KDDT trees and forests.

We did not compare to SSL-PCTs because there is no implementation given by the authors, but we will do our best to reproduce it and include it as a baseline.

Showing confidence in the plots in the main paper would make them unreadable. We will include tabular results with standard deviations in the appendix. Between the number of data sets, baselines, and labeled sample counts, there would be a very large number of confidence tests. Do you have a way of presenting this in mind?

We gave transductive evaluation based on the precedent of the closest related method, Levatic et al. (2017), and because it makes it possible to compare to label propagation. However, based on multiple reviewers' requests, we will instead report inductive performance in the revision and, accordingly, leave out label propagation as a baseline.

We are aware and acknowledge that the cross-validation method we use in experiments is not ideal. We only use it for our proposed method, so it is not unfair to the baselines. It is true that parallelization is straightforward, but we are already parallelizing across hundreds of experiment configurations to the limits of the resources we have available, so we cannot afford full cross-validation for the scope of experiments we have shown. In a real application, where there is only one rather than hundreds of cases, so full cross-validation is reasonable.

We will look into these improvements of self-training to include as baselines in the revision.

We will fix the typos etc. Thanks for pointing these out.

In response to questions:

All random forests in this work contain 100 trees. The baseline random forests are fully grown, as is standard for random forests, so there is no hyperparameter selection.

We were not aware of the Geurts2005 paper. Thank you for pointing this out. The formalism for prediction used in that paper is the same as for KDDTs used with a Gaussian kernel. However, KDDTs also use the same kind of deterministic perturbation on the training data during training, which is done using an algorithm proposed by the original KDDT paper. The method of Geurts2005, on the other hand, does normal decision tree fitting. The perturbation aspect of fitting is important to this SSL method because it grows a tree according to the probabilistic interpretation that is then used to assign leaf values. The theory that motivates our leaf assignment strategies would not work without it, so the method of Geurts and Wehenkel is not suitable.