Learning Interpretable Characteristic Kernels via Decision Forests

1: During the experiments, the hyperparameters of Random Forest are fixed, but how would changes to these affect the results? I would like to know the extent of the impact that model selection has on experimental outcomes.

2: While Random Forest requires a target for training as it is a supervised learning model, I wonder if there are instances when performing independence testing of distributions where a target may not be present. What would be done in such cases?

3: Please let me know if there are any unique features or points regarding the KMERF algorithm that can be highlighted.

About the theory:

1. The proof of theorem 2 uses the local dense condition (condition 2) to deduce the positivity of the second integral in the second equality, but the proof does not show why the kernel must be positive at the limit point of the dense set \omega_z.
2. It is still not clear presented why random forest-induced partition kernel satisfies the conditions of Theorem 2, can you make the relevant claim “Random forests exhibit a property similar to k-nearest-neighbors, and they do satisfy the conditions outlined in Theorem 2” more rigorously?
3. Previous methods such as HSIC and MGC choose kernels or some fixed rule (e.g. the knn rule which is not learned from data) a priori, independent of the data and thus independent of the independent test, while the proposed partition kernel learns rule from the particular sample, and the corresponding independence test then seems conditional on some learned information. Note that the independence tests are correlated to the performance of the random forest: observing that the KMERF has bad performance on the datasets such as the high-dimensional noised circle/diamond sample on which RF also has difficulties in classification or regression tasks. This is a little bit confusing to me. Does this learning procedure impair the validity of the independence test?

To make your content self-contained and more reader-friendly, please:

1. Add more explanations on steps 3-5 in section 4, i.e., tell the reader why you do it;
2. Include a mathematical introduction of the methods in comparison (MGC, HHG, HSIC, etc.);

Some problems with respect to the experiments:

1. The noise scaling \kappa in your simulation is not specified;
2. Figures from F1 and F2 are largely blank.

Q1. I hope the author can analyze the differences in kernel characteristics between RF and other comparison methods under different data types.

I am including here both questions and suggestions for improvement.

Theorem 1 is never referenced. Why is it important?

I have several questions and doubts about Theorem 2:

• The statement regarding $z$ and $\epsilon$ is somewhat ambiguous. Do you mean "For any point $z\in\mathbb{R}^p$, there exists a positive value $\epsilon$" or "For any point $z\in\mathbb{R}^p$ and positive value $\epsilon$"?
  • If the former, I think that the statement following (3) in the proof is not valid because the conditions only hold for one particular value of epsilon, which may not be an epsilon such that $f_{X_1}(x)>f_{X_2}(x)$ on all $x\in b(z,\epsilon)$.
  • If the latter, I cannot see how this condition can possibly be satisfied for all $\epsilon>0$, e.g. if if condition 1 holds for $\epsilon$, then condition 2 does not hold for $2\epsilon$.
• It would be nice to define a "dense subset", and perhaps make it clear why it is used (instead of a simpler condition). I had to look up this term, and I suspect other interested readers would too.
• The proof assumes that the probability densities are continuous. This must be stated in the theorem.
• It is also not clear that the given example (partition [0,1] into $n$ sub-intervals) is correct. For example, even for only the given $z=0.01$ and $\epsilon=0.01$, for a partition with any $n>50$, it is not true that $x$ and $z$ belong to the same leaf for all $x$ in some dense subset of $b(z,\epsilon)=[0,0.02]$.
• Likewise, I do not think it is possible, in general, to construct a partition such that, for any $x_1$ and $x_2$, $x_1$ and $x_2$ are in the same leaf if and only if $x_2$ is in the $k$-nearest-neighborhood of $x_1$.

It would be helpful to state the hypothesis being tested at the start of section 4 instead of section 5.

Distance-kernel transformation: what is the purpose? It is hard to tell what it's doing by the equation alone. How efficiently can we compute the distance-kernel transformation?

The chi-squared test is used as a more efficient alternative to permutation testing. What is the tradeoff? That is, what is the disadvantage of the chi-squared approach, and how severely can we expect it to affect the results?

What is the complexity of step 2, computing K?

I don't know how fair it is to claim that the algorithm is overall "fast and scalable". Mnp could be very large, and the n^2 term can become problematic for very large data. How does this compare to prior work in this are, e.g. the experimental baselines? Also, it would help if the experiments supported the claim of scalability, but the fixed n=100 does not inspire confidence.

In Theorem 3, it is stated that each tree must individually satisfy the conditions of Theorem 2. Then why is Theorem 2 stated as a property of sets of partitions, and not of individual partitions?

Second-to-last paragraph of section 5: I am hoping for some clarification on Theorem 2 as described above, but as to my current understanding, I don't see how the properties listed here imply that the conditions are satisfied. Moreover, it is certainly not true, without some assumptions about $F_{XY}$, that $k/n \to 0$ for random forests, unless you modify the tree growth algorithm to ensure that leaves have a sufficiently small sample count.

Why do the results show statistical power vs. dimension instead of vs. sample count? Shouldn't this be necessary to experimentally demonstrate consistency?

What value of $\kappa$ was used for the data simulations?

If you can, an explanation of why KMERF performs poorly on the few data sets where it does would be useful.

Only one real-world data set is considered, and the experimental setup is somewhat confusing. What exactly are the hypotheses being tested on the two axes of the left part of Figure 4?

With regards to the interpretability experiment: it looks like you use fixed $p=5$ here, and the x axis in Figure 3 is the feature index? If so, the former should be stated explicitly, and the x axis label and caption of Figure 3 (which suggest that the x axis is p) should be corrected. Also, when you say "sorted by feature importance", I think you mean sorted by decreasing coefficient in the underlying simulation? Maybe there is a different way to say that, but it is not to be confused with the estimated feature importance.

Nitpicks:

• Definition 1: should be one sentence
• Definition 1: either define how a set $\phi_m$ is used as a function, or write it using common notation such as $\in$
• Definition 1: state that the members of a partition are called "leaves" before using the term "leaf"
• I don't think the example in the paragraph following Definition 1 is particularly necessary or helpful.
• For the stated $O(Mpn \log n)$ complexity for fitting a random forest, we have to assume the trees are approximately balanced. If they are highly unbalanced, it is $O(Mpn^2)$.