Dear reviewer,

Thanks for the constructive advices! I will now reply to each point in the Weaknesses and Questions sections.

Regarding Weaknesses in the review:

1. Rebuttal to Weakness 1: In comparison to previous research for CDE, the datasets we used are NOT smaller.

• We included 14 datasets in total, with various sample sizes (from 104 to 21263) and dimensionalities (from 5 to 82). We aim to test on both small and large datasets since 1) the sample size is often not too large in critical areas like healthcare; 2) (as mentioned in the Introduction) CDE is often used to understand the data collected from scienfitic experiments, in which data size is often small too, as data collection is expensive.

  Discussion about the data sizes in previous research: for instance, in the most recent related work [12] (Gao, Zijun, and Trevor Hastie. "LinCDE: conditional density estimation via Lindsey's method." Journal of machine learning research 23.52 (2022): 1-55.), which is a tree ensemble method, all datasets considered are below $2 000$, indicating that smaller datasets are indeed interesting to the CDE task. Further, the deep learning model proposed in [9] (Dutordoir, Vincent, et al. "Gaussian process conditional density estimation." Advances in neural information processing systems 31 (2018)) {see page 8, figure 4} considers benchmark datasets with similar sizes (number of rows) to ours (and the dimensionalities of datasets we consider are even in general higher).

• Despite what has been discussed, we tried on a larger dataset about NYC taxi duraion (sample size $N=203686$), which we take from Kaggle. This is a dataset that can be used to predict the taxi trip durations based on the pick-up and drop-off locations (longitutde and latitude). We only use a subset of this data that corresponds to 1 month. However, most interpretable competitor methods fail on this dataset, and specifically CKDE/NKDE/LinCDE fail to return any results because their (widely used) implementations caused that the memory limit is reached.

  Meanwhile, our method and CADET are the only interpretable methods that can be applied to this dataset. However, as shown in the table below, the negative log-likelihoods of our method are pretty close to those of the two neural network methods (NF and MDN), significantly outperforming the negative log-likelihoods of CADET. Although the main goal of this paper is NOT to (just) introduce a CDE method that scales better than existing "shallow" models, this result indeed shows the potential of the scalability of CDTree to larger datasets.

2. Reply to Weakness 2:

• We are aware of this limitation as we already discussed it in the Limitation of the paper.

3. Rebuttal to Weakness 3: Figure 3 does NOT contain the presentational issue mentioned in the review as the legend shows the meanings of different shapes.

• As shown by the legend on the upper part of the figure, each method is shown by a different color TOGETHER with a different shape. We find that, in comparison to using different colors only (with the same shape), our visualization makes it easier to show the general picture for each method accross all datasets.

Reply to Questions:

1. The term "Ours" / "CDTree" for proposed method / model respectively

We deliberately use “Ours” to refer to our method (the model we proposed, the learning criterion, and the algorithm, as a whole). By contrast, we use the term “CDTree'' to refer to the probabilistic model (learned from the data), which can be seen already from our abstract.

2. Our method can handle both discrete/continuous features.

As discussed in Appendix B.2, we do not require the feature variables $X$ to be continuous. That is, while the target variable $Y$ needs to be continuous (otherwise there is no need for conditional density estimation), the feature variables can be both categorical and continuous. Just like the decision tree for classification/regression, the splitting conditions on the internal nodes can be defined for both discrete and continuous variables. We do assume that categorical variables are preprocessed and one-hot encoded though.

3. About CART model selection.

The CART we use is the original version from the inventors. That is, the tree is first grown by iteratively maximizing the gini index, and then pruned by the so-called “cost complexity pruning”, i.e., by optimizing the impurity (MSE for regression) plus a regularization term defined as the number of nodes times a regularization hyperparameter, in which the hyperparameter is tuned by cross-validation in our experiment. These are (already) discussed in Appendix C.4.

4. Put (more) content about Algorithm in the main content.

Yes, if the paper is accepted and then one more page is granted.

5. Resolved (see above).

(Mistake on the previous title - it was directed to the authors who provided the rebuttals): Thanks for your extensive reply on the points.

Perhaps it is better to move clarifying points which are in the appendix to the main writeup (as I see that some answers to my questions are in the appendix which not many reviewers will have to look at, unless there is an explicit hint in the manuscript). I do not believe it will have much impact on the length of the manuscript. In addition, as you go through the draft once more, you will have opportunities to cut down redundant sentences/paragraphs and make your points more succinct.

I still argue that Figure 3 is a very confusing figure - a visualization should not ask readers to combine a combination of color and shape. Why are some of these shapes not aligned on the horizontal axis tick? I also think there are too many horizontal ticks (yes, each tick = dataset) but there is not much space to put all of these information.

One more thing: I would also keep the fonts consistent in your reply - it actually does not help reviewers look at your reply in entirety and it looks less professional.

Thank you for your detailed comments and advice.

We now address each paragraph in the "Weakness" section of your review.

Factual Error in Paragraph 2:

• The statement in the review that "no hyperparameter tuning is needed" is incorrect. Our paper highlights that the advantage of using MDL is the elimination of the need for a REGULARIZATION hyperparameter. We specifically use the term "regularization hyperparameter"/"hyperparameter for regularization" throughout the paper, in which we mentioned the word "hyperparameter" 4 times in total. We specifically emphasized this point because the “standard” way of regularization in decision tree learning is to penalize on the number of nodes times a "regularization hyperparameter", which needs extensive parameter tuning.

Rebuttal about the statement that we are using "crude" MDL (Paragraph 3):

• The claim that our MDL approach is "crude" is incorrect according to Chapter 14.3 of the cited book [14]. See page 426. Here I quote: "In the end, we encode data D using a hybrid two-part/one-part universal model, explicitly encoding the models we want to select between and implicitly encoding any distributions contained in those models", which defines our approach as “the refined MDL”. Additionally, while the NML regret for histograms is well-known, our contribution extends these results to a supervised setting with histograms and demonstrates that the NML regret for the CDTree is the product of the regret terms for all histograms on all leaves.

Rebuttal about choosing priors (Paragraph 2):

• Although there is indeed some flexibility in choosing the model encoding scheme within the MDL framework, similar to selecting priors in Bayesian model selection, encoding the model is not arbitrary but follows requirements and guidelines. This includes ensuring the prior probability defined on the model class sums to 1, preventing an excessively large penalty term that would require larger sample sizes to converge to the true model. The encoding scheme you mentioned is suboptimal because the corresponding prior probability is not proper (consider, e.g., the code word that corresponds to the case that every node is a leaf node, which cannot form a decision tree). Notably, many “old” methods that leverage MDL used various intuitive yet “crude” encoding schemes like this one, and it is hardly possible to review all of them (e.g., the one used in the C4.5 decision tree is different from the one you mentioned above).

About choosing hyperparameter C (Paragraph 2):

• The hyperparameter C establishes a hierarchical structure on the search space of continuous feature variables, setting levels for granularity. This hierarchy helps express prior beliefs about model complexity. For instance, intuitively, if a decision tree gives a split condition with a highly precise value like $X > 1.0001$, domain experts may ask, is this level of granularity (up to the 4 decimal places) necessary? Why not just $X > 1$? Thus, from the perspective of model selection, the former condition is "more complex" (more bits required to encode) than the latter one. However, as different feature variables may have very different ranges, instead of considering the granularity in terms of the decimal precision, in this paper we consider the granularity in terms of the quantiles (e.g., splitting on the 1/2-quantile may be considered "simpler" than splitting on the 1/10000-quantile). As explained in Appendix C.2, just like we have different numeral systems (e.g., decimal/binary), which set up different hierarchical structures for the levels of granularities, the hyperparameter C plays a similar role here in setting up the hierarchical structures for the quantiles.
• We have shown that a global ad-hoc choice for $C = 5$ works well for all datasets in our experiments section. By contrast, it is impossible to have a single value for the regularization hyperparameter used in traditional decision tree learning that works well for different datasets, which also does not carry this natural meaning of the $C$ in our paper.

About our algorithimic innovations (Paragraph 4):

• While our algorithm is greedy, it addresses the challenging task of optimizing the tree structure and separate models (on leaves) simultaneously. Recent algorithmic advancements for classification/regression trees have been reviewed, highlighting the challenges for CDE tasks, which motivates the choice for the heuristic algorithm.
• Our main algorithmic innovations are described in Section 5 (not the appendix), including 1) no pruning for the tree, which favors the model complexity, and 2) searching the histograms directly (without using any "guessing" heuristics that are common in traditional "model tree" methods). We also include in Section 5 a high-level yet complete description of the algorithm process. The pseudo-code and other details are put to the appendix for reproducibility due to the page limit.
• Due to the fact that improving on the heuristic algorithms for classification/regression trees often require a whole research paper to describe (as reviewed in our paper), we consider further improving on our proposed algorithm for CDE as future research.

Rebuttal about the characterization of our method as a "straightforward combination of classical building blocks".

We respectfully disagree on this statement as it overlooks our contributions:

• We propose the first single tree-based model specifically designed for the CDE task (as CADET essentially used the same model as CART due to the equivalence between the MSE loss and the Gaussian assumption);
• We are the first to formalize the decision tree learning under the (modern) MDL framework as a model selection problem, introducing new encoding schemes for data (with NML) and the decision tree itself.
• Our extensive experiments demonstrate that with CDTree, kernel-based methods are no longer the only choice for "shallow" models for CDE.

Dear reviewer,

Thanks for the quick and detailed response. We have further rebuttals as follows.

Further clarification about the prior you proposed

• One factual error: the paper you cited, (Papageorgiou, I., & Kontoyiannis, I. (2024). Posterior representations for Bayesian Context Trees: Sampling, estimation and convergence. Bayesian analysis, 19(2), 501-529.), considers $m$-ary trees, while in our paper we consider (full) binary trees only, as describe in Lines 104-105 and then emphasized in Line 177.
• Further explanations about why the prior probabilities you proposed do not sum to 1. For simplicity, consider the case when a decision tree has 3 nodes in total, for which apparently only one possible tree structure exists (i.e., one root node and two leaf nodes). However, if you put a 1/2 prior probability on whether to split each node, this "only" structure has a prior probability of $(1/2)^3 < 1$. Hence, in this case, the sum of all prior probability masses is $(1/2)^3 < 1$ as well.

Further clarification about the hyperparameter tuning

• Again, as already mentioned in our previous rebuttal, we NEVER claimed that “no hyperparameter tuning is needed”; hence, I am not sure how we "tone it down".
• We indeed introduced $C$, yet we have shown that a global ad-hoc choice for $C$ can work reasonably well for all datasets in our experiments (and whether tuning $C$ can further increase the predictive performance of CDTree is not related to the main research question in this paper). By contrast, this is hardly possible for the regularization hyperparameter; i.e., it is hardly possible to pick a single value with an intuitive meaning for the $\alpha$ in the traditional decision tree learning optimization function, often in the form of "$impurity + \alpha |T|$", in which $|T|$ denotes the size of the tree, and $impurity$ can be MSE for regression.

Regarding Condition (1) of page 426 of the MDL book.

• Notably, the text box on Page 426 does NOT give a rigorous definition of the "Refined MDL model selection", for the following reasons. First, see page 427, the 2nd paragraph, and here I quote "The general idea is summarized in the box on page 426, which provides something like a definition of MDL model selection, but only in a quite restricted context. If we go beyond that context, these prescriptions cannot be used literally, but extensions in the same spirit suggest themselves.". Second, the Condition (1.) of page 426 is also NOT a rigorous definition for the requirements of the priors, as the concept "quasi-uniform" is NOT defined throughout the book (see page 425, here I quote "While we have not formalized what types of codes still count as quasi-uniform and what not ..."). Hence, Condition (1) of page 426 is more like a general guideline summarized from the examples used in the book.

• The last two paragraphs of page 425 (starting from "we can choose the code ..."; and note that the last paragraph of page 425 ends on the top of page 427) are a more general guideline for choosing the priors for model selection than the condition (1) of page 426. Specifically, our proposed prior is close to the general description given by the last sentence of the first paragraph on page 427; here I quote, "In some cases we can apply conditional codes which do achieve a “conditional” minimax regret, ...". That is, in general, we encode the model by

   number of nodes => tree structure => node splitting conditions => number of histogram bins; 
  

  each step is a conditional uniform/quasi-uniform code (as the integer code is listed as an example of quasi-uniform in the book), conditioned on the value encoded in the previous step.

• Notably, we quoted the content of page 427 (in our previous response) as it suffices to give the rebuttal to your previous statement that a mix of NML (one-part) and a model prior makes our MDL encoding "crude"; as shown on page 427, a mix of these two is by definition the form of the "refined" MDL model selection.

Dear Reviewer,

Although I understand that the judgment about novelty can be a subjective matter, I would appreciate it if more information is provided regarding the motivation for this judgment, which would be helpful for me to improve the paper.

Regarding your two questions:

1. I am not sure what exactly you mean by "capturing such smoothness". Could you give a formal definition or an example of "capturing smoothness"? In general, partition-based models (including histograms, decision trees, regression trees, etc) approximate smooth functions (e.g., decision boundaries) in a piecewise manner.
2. As elaborated in the paper, the overfitting is prevented by formalizing the learning problem as a MDL model selection problem.

Thank you so much for the detailed, constructive, and very helpful comments on my writing!

Presentational issues fixed

I have fixed the presentational issues and typos you mentioned. Among others, one extremely helpful comment is that "lines 108-110 are confusing": in these lines I wrote "... $f (y|x)$ as $f _ k (x)$ ... ", but it should actually be "... $f (y|x)$ as $f _ k (y)$ ... ".

Rebuttal about "model definition not complete"

We respectfully disagree that "The definition of a conditional density tree with histograms in Section 3 seems to be incomplete", and you seem to indicate part of the model definition is in Section 4. However, Section 3 contains all information about how to calculate the probability/likelihood of data given a fixed conditional density tree (regardless on whether it is actually a good model), which is sufficient for defining a probabilistic model. In contrast, Section 4 is all about the definition of the model selection criterion.

Rebuttal about "applied statistics journal may be a better fit"

The machine learning community has been recently highly interested in both conditional density estimation (CDE) (e.g., the references [9, 37, 48, 12] in the paper are from NeurIPS/ICML/JMLR) and interpretability, yet interpretable CDE methods are neglected. Second, the lack of CDTree, as the counterpart to the regression tree and classification tree, hinders the development of XAI methods (e.g., local surrogate models) for CDE.

Reply to your questions:

• Regarding the first and last point: you are correct. Thanks so much again!
• Whether CKDE/NKDE is interpretable model: CKDE/NKDE (and other kernel-based models) are currently the standard (if not the only) choices if someone is looking for a "shallow" model for CDE. We argued in the paper that these models are "arguably less interpretable to (single) trees", yet we are also aware that these models may be considered more interpretable than tree ensembles/neural networks. (After all, there is still no precise definition of "interpretable models". )
• About comparison to the baseline with Gaussian assumption: The MDL criterion we proposed CANNOT be used for Gaussian assumptions, as it is known that the regret term for the NML will be infinity (see page 298 of the book [14], {Grünwald 2007, The minimum description length principle MIT press, Example 11.1, Chapter 11}). I agree it would be interesting to do some sort of this kind of comparison though, as kind of an ablation study for the histograms and a supplementary to CART-h in the paper. However, the closest related work I can think of is (Proença, Hugo M., et al. "Discovering outstanding subgroup lists for numeric targets using MDL." ECML PKDD 2020), but they 1) consider rule lists (not trees), 2) they consider subgroup discovery for numeric targets (so not regression or CDE) and 3) they use the Bayesian encoding, not NML (which is not possible as discussed).
• Runtime of CART: it depends on the search space of the regularization hyper-parameter. In our experiments, we set the range by “ccp_alphas = np.logspace(-5, 2, 30)”, and for all datasets, a single run should not exceed 100 seconds from what I remember.