Conditional Density Estimation with Histogram Trees

Authors: lincen  yang
matthijs  van leeuwen
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 19:00:14

Abstract: Conditional density estimation (CDE) goes beyond regression by modeling the full conditional distribution, providing a richer understanding of the data than just the conditional mean in regression. This makes CDE particularly useful in critical application domains. However, interpretable CDE methods are understudied. Current methods typically employ kernel-based approaches, using kernel functions directly for kernel density estimation or as basis functions in linear models. In contrast, despite their conceptual simplicity and visualization suitability, tree-based methods---which are arguably more comprehensible---have been largely overlooked for CDE tasks. Thus, we propose the Conditional Density Tree (CDTree), a fully non-parametric model consisting of a decision tree in which each leaf is formed by a histogram model. Specifically, we formalize the problem of learning a CDTree using the minimum description length (MDL) principle, which eliminates the need for tuning the hyperparameter for regularization. Next, we propose an iterative algorithm that, although greedily, searches the optimal histogram for every possible node split. Our experiments demonstrate that, in comparison to existing interpretable CDE methods, CDTrees are both more accurate (as measured by the log-loss) and more robust against irrelevant features. Further, our approach leads to smaller tree sizes than existing tree-based models, which benefits interpretability.

Main paper: 
 introduction: 
 Conditional density estimation (CDE) is a crucial yet challenging task in modeling the associations between features and a continuous target variable, which has received a lot of research interest since the 1970s [44] . By modeling the full conditional distribution, CDE is useful when the datasets are multi-modal, heavily skewed, or heteroscedastic. As a result, it is widely applied in various fields, including genomics [8] , astronomy [3] , wind power forecasting [19] , and computer networks [47] .CDE provides richer information for data understanding than regression, which only models the conditional mean. This makes CDE desirable for well-informed decision-making in critical areas, such as healthcare [32, 53, 14] , which calls for interpretability.Despite its importance, recent CDE research has predominantly focused on black-box models, such as neural networks [10, 55, 39, 46, 50] and tree ensembles [13] . In contrast, intrinsically interpretable models for CDE are understudied. Specifically, decision tree-based methods are largely neglected, with CADET [6] being the only existing method to the best of our knowledge. However, CADET's assumption of a Gaussian distribution for the target variable in each leaf node limits its ability to model complex conditional densities.As a result, kernel-based models became the standard among 'shallow' models for CDE, including methods based on kernel density estimation (KDE) [44] , and linear models with the basis functions chosen as Gaussian kernels [54, 11] . Nevertheless, kernel-based models are arguably less interpretable than decision trees: as conditions in decision trees are directly readable, they are comprehensible to humans without statistical expertise (e.g., individuals affected by data-driven decisions rather than professional data analysts).To address these limitations, we propose the Conditional Density Tree (CDTree), a flexible tree-based CDE model in which each leaf node consists of a histogram model. For illustration, Figure 1 shows the CDTree learned from a dataset about personal medical costs with demographic features [24] . The figure visualizes the histogram models for the conditional densities on three selected leaf nodes, along with the unconditional density. The readable rules, extracted from the tree paths, and the histogram visualizations, make the results easily comprehensible to humans without statistical expertise. For instance, the difference in medical costs between smokers and non-smokers is evident when comparing the plots. The full results with histograms on all leaf nodes, as well as further descriptions of the dataset, are provided in Appendix E.Learning a CDTree from data is a challenging task, as it requires simultaneously optimizing the decision tree structure and the number of bins for histograms on all leaf nodes. While often used for either task, cross-validation is too time-consuming if we need to search for the optimal number of bins for every possible node split. Thus, we formalize the learning problem using the minimum description length (MDL) principle [16, 41] , which we briefly review in Section 4.1. Adopting MDL eliminates the need for tuning the hyperparameter, by cross-validation, for both regularizing the decision trees [5] and for choosing the number of bins for histograms.Our main contributions are as follows. First, we introduce the CDTree for the CDE task and formalize the learning problem with the MDL principle. Second, we propose an iterative algorithm that can search the optimal histogram for all possible node splits. Third, we benchmark against a wide range of competitors and demonstrate that CDTree is highly competitive. Specifically, CDTree is more accurate than existing interpretable CDE methods (as measured by the log-loss). Meanwhile, CDTree has smaller tree sizes than other tree-based methods, which benefits interpretability. In addition, CDTree is extremely robust to irrelevant features, which is noteworthy as irrelevant features are known to harm the convergence rate for CDE [17] . Further, we argue that the (intrinsic) explanations of CDTree are trustworthy only if the CDTree is robust against irrelevant features. Figure 1 : Three selected leaves from the CDTree modeling the conditional density of the medical costs given demographic features, together with the unconditional density for medical costs.2 Related Work KDE-based CDE. Several CDE methods have been developed based on kernel density estimation (KDE). The most straightforward approach, known as conditional-KDE (CKDE) [44] , involves separately estimating the joint and marginal densities using unconditional KDE and then taking their ratio to obtain the conditional density. Another approach, ϵ-neighborhood KDE (NKDE), estimates the conditional density by applying KDE to the subset of data points within the ϵ-neighborhood of the target point, with the range of the neighborhood controlled by the parameter ϵ.However, KDE-based methods have several limitations. First, KDE is arguably less interpretable than tree-based models, as understanding KDE requires statistical knowledge, making it less accessible to domain experts and the general public. Additionally, while decision trees can naturally handle both discrete and continuous feature values, discrete features pose significant challenges for kernel-based methods. Specifically, CKDE requires estimating the joint density of the features and target variable, which necessitates the use of discrete kernels for discrete variables. These discrete kernels are often difficult to interpret [31] . As for NKDE, when both discrete and continuous feature values exist, the choice of the scale for the continuous variables unavoidably introduces a certain degree of arbitrariness in defining the distances used to characterize the neighborhood.Regression-based CDE. Motivated by several issues of CKDE, including high variance as a plug-in estimator, the exponentially growing search space for bandwidth tuning, and the curse of dimensionality for estimating the joint density function, the method named least-squares CDE (LSCDE) [54] was proposed. LSCDE aims to directly estimate the ratio between the joint and marginal densities by assuming this ratio is a linear combination of several basis functions, chosen to be Gaussian kernels. Similarly, Fan et al. [11] proposed double-kernel local linear regression, which transforms the conditional density function into the conditional expectation of the (unconditional) density function of the target variable, leading to a least-squares approach as well. However, both methods face the challenge of bandwidth selection, as the value of the Gaussian kernel function must be calculated with the entire feature vector as input. This issue becomes particularly problematic as the search space for the bandwidth grows exponentially with the number of features.Tree-based CDE. The only existing CDE method based on single trees that we are aware of is CADET [6] , which improves CART regression trees [5] by designing a node-splitting heuristic specifically for CDE. However, CADET assumes a Gaussian distribution for the target variable on each leaf, which is far less flexible than our non-parametric histogram models.Black-box CDE. Neural networks have been shown to perform well in a wide range of tasks. For CDE, the most well-known methods include NF [39] and MDN [4] . As for tree ensemble models, RFCDE [35] first fits a standard random forest, and then estimates the CDE by the weighted average of the unconditional density estimates obtained via KDE, with weights determined by the random forest. Furthermore, the recently proposed LinCDE [13] method learns a boosted tree model based on Lindsey's method [25] . While black-box models are highly accurate, we argue that interpretable CDE methods are valuable for applications in critical domains and for understanding the data. 
conditional density tree with histograms: 
 Tree-based models divide the feature space into disjoint (hyper-)boxes by recursively splitting on individual feature variables (for which we consider binary splits only). Consequently, the induced partition with K subsets (leaves) can be represented as M = {S k } k∈ [K] , where each leaf S k represents a subset of the feature space and [K] := {1, ..., K}. Further, each leaf is equipped with a single (unconditional) density estimator, denoted as f k (.). Thus, for a dataset D = (x n , y n ) with sample size n, the tree-based model M first identifies the leaf to which each (x, y) ∈ D belongs, and then estimates the conditional density f (y|x) as f k (y) (assuming x ∈ S k ).We choose histograms as our model class for each f k (.). Unlike previous parametric models [13, 6] , which carry the risk of misspecification, histograms are non-parametric yet efficient. Additionally, in comparison to KDE, histograms do not require selecting a kernel or tuning the bandwidth.We next describe our notations and formally present the histogram as a probabilistic model. Formally, a (fixed) histogram model partitions the domain of the target variable Y into equal-width bins, and then approximates the density of Y by piece-wise constants estimated from data. Thus, we can denote a histogram model as a tuple H = (B l , B u , h), with B l and B u respectively representing the lower and upper boundary of the histogram, and h the number of bins. A histogram model H can parameterize a family of distributions by α = (α 1 , ..., α h ), with the probability density function in theform of f H (Y = y) = αj (Bu-B l )/h , ∀y ∈ [B l +(j -1) Bu-B l h , B l +j Bu-B l h ), in which (B u -B l )/h is the bin width and [B l + (j -1) Bu-B l h , B l + j Bu-B l h) denotes the interval for the jth bin. In practice, the histogram boundaries B l and B u are often set based on the dataset at hand, by prior knowledge, or by the range of the values plus/minus a small constant. Meanwhile, the parameters α can be estimated by the maximum likelihood estimator (i.e., by the empirical frequencies in each bin):αj = 1 n n i=1 1 [B l +(j-1) Bu -B l h ,B l +j Bu-B l h) (x i ), in which 1(.) is the indicator function.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: our proof has no additional assumptions.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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• 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 complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
the mdl-optimal cdtree: 
 We briefly review the minimum description length (MDL) principle, and then formalize the problem of learning a CDTree that consists of histograms as an MDL-based model selection problem.Rooted in information theory, the minimum description length (MDL) principle states that the optimal model is the one that compresses the data most [41, 15] . Precisely, given the dataset D = (x n , y n ), the MDL-optimal model is defined asEQUATIONin which M is a CDTree and M the model class of all possible CDTrees for our learning task, meanwhile L(M ) is the code length (in bits) needed to transmit the model in a lossless manner. According to the Kraft's inequality [7] , L(M ) can also be regarded as a prior probability distribution defined on the model class. Further, P M (.) is the so-called universal distribution [15] : as M parameterizes a family of probability distributions, denoted as P M,θ , P M (.) can be regarded as a "representative" distribution such that the maximum regret, defined as max y n {max θ log 2 P M,θ (y n |x n ) -log 2 P M (y n |x n )}, can be bounded by nϵ > 0, ∀ϵ > 0 as n → ∞ [15] , in which the maximum is defined over all possible values for y n in the domain of the target variable. Intuitively, the regret is the difference between the log-likelihood of P M (y n |x n ) (which does not depend on θ) and the maximum log-likelihood max θ log 2 P M,θ (y n |x n ). For our learning task, θ is the parameter vector that contains the histogram parameters (i.e., the α's) for all leaf nodes.The MDL principle has been successfully applied to various data mining and machine learning tasks [12] , and specifically to partition-based models, including histograms and classification trees/rules [37, 57, 36, 22] . The MDL framework provides a principled way of regularizing model complexity without any regularization hyperparameter to be tuned. Moreover, as the Bayesian marginal distribution is one specific type of the universal distributions, the MDL-based model selection can also be regarded as a generalization of Bayesian model selection [16] .The optimal universal distribution under the MDL framework is the so-called normalized maximum likelihood (NML) distribution, defined as [15, 49, 16 ]EQUATIONunder the condition that the denominator is finite. It can be shown that the NML distribution is the only distribution that leads to the minimax regret min P M max y n {max θ log 2 P M,θ (y n |x n )log 2 P M (y n |x n )}, in which the denominator in Eq. 2 is exactly equal to the regret [15] .The denominator in Eq. 2 is in general prohibitively expensive to compute [15, 51, 43] , with a few exceptions including the cases when the probabistic model represents categorical distributions [21] , decision rules for classification [57] , and one-and multi-dimensional histogram models [22, 28, 58] . We extend these previous results and prove that, for CDTrees with histogram models, the denominator (regret) is finite and is equal to the products of the regret terms of the NML distributions for onedimensional histogram models, as shown in Proposition 1. This result is useful for efficiently calculating the denominator (regret) in Eq. 2 for CDTree models, as the regret terms for histogram models are known to be equal to those of categorical distributions [20, 21] , for which an efficient algorithm exists with sub-linear time complexity [30] . Proposition 1. Let θ = (α 1 , ..., α K ) be the histogram parameters for histograms on all leaves, and let θ = arg max θ P M,θ (y n |x n ). Then y n max θ P M,θ (yn |x n ) = k∈[K] R(N k , h k ), in which R(N k , h k )is the regret (denominator) of the NML distribution of the histogram model on the kth leaf node that contains N k data points and h k bins.We defer the proof to Appendix A due to space limitations.To encode a CDTree model in a lossless manner, we need to sequentially encode 1) the number of nodes in the decision tree, 2) the structure of the tree, 3) the splitting condition for each internal node in a predetermined order (e.g., depth first), 4) the number of bins for the histogram on each leaf node, and 5) the boundaries B l and B u of the histograms. That is, let L(.) denote the function that calculates code length in bits, the code length needed to encode a model M can be decomposed toL(M ) =L(# leaves) + L(tree structure) + j∈[K-1]L(splitting condition of the jth internal node)+ k∈[K]L(# bins of histogram on the kth leaf node) + L({B l , B u });(3) we next describe them in order.Encoding the tree size and structure. As we consider full binary trees only, it is sufficient to encode the number of leaves K, which also determines the number of total nodes. As K is a positive integer, we adopt the standard Rissanen's integer universal code [42] , denoted as L N (K), for which the code length is equal to L N (K) = c + log 2 (K) + log 2 log 2 (K) + ...; the summation continues until a small enough precision is reached, and c ≈ 2.865 is a constant.Further, for full binary trees, the number of all possible tree structures for trees with K leaves is equal to the Catalan number, denoted as C K-1 [52] . Hence, specifying one certain structure costs log 2 C K-1 bits. Thus, L N (K) + log 2 C K-1 bits are required for encoding the tree size and structure.Note that while there exist multiple ways of encoding tree size and structure (e.g., one alternative is to leverage the joint probability of the tree size and the tree structure, which can be defined by treating the tree as a realization of a Galton-Watson process [33, 2] ), our encoding scheme adheres to the principle of achieving conditional minimax [16] by explicitly putting a prior on the number of nodes.Encoding the splitting conditions. An individual splitting condition on a single tree node consists of a variable name and a splitting value, which we encode sequentially.To begin with, if the dataset contains m feature variables, encoding the name of a certain variable X costs log 2 m bits. Further, the code length needed for encoding the splitting value depends on the variable type. First, for a discrete variable X with |X | unique values, specifying a single value cost log 2 (|X |) bits. Second, encoding the splitting value for a continuous variable can be achieved by sequentially encoding 1) the granularity level for the search space, denoted as the positive integer d, and 2) the exact value within the granularity level d. Specifically, with a fixed d, we consider as the search space the C • 2 d-1 quantiles that can partition the values of X into equal-frequency bins. Note that the values of X are based on the subset of data points locally contained in this internal node.Hence, encoding d costs L N (d) bits with Rissanen's code [42] , and encoding one specific splitting value (quantile) costs log 2 (C • 2 d-1 ) = log 2 (C) + d -1 bits. That is, we treat the granularity level d as a parameter to be optimized when learning a CDTree from the data, which avoids (arbitrarily) specifying the granularity in advance, a shortcoming in previous MDL-based methods (for other tasks instead of CDE) [22, 36, 58, 57, 28] . In contrast, the parameter C can be used to express the prior belief about the hierarchical structure of the search space, as further discussed in Appendix C.3.Encoding the histograms. One subtle choice we made is to set the boundaries for histograms on all leaves to be the same, and we set them as the global boundary of the target variable. This avoids unseen (test) data points falling outside the boundaries of the histograms on the leaf nodes. This is because while it may be common to assume that the boundaries for the histogram are known in unconditional density estimation, assuming the same for CDE is hardly realistic.Therefore, the code length needed to encode the boundary L({B l , B u }) in Eq. 3 is a constant that does not affect the model selection result. Consequently, it suffices to encode the number of bins for each histogram: for the histogram on the kth leaf with h k bins, it costs L N (h k ) bits by Rissanen's integer code [42] .Combining Eq. 1,2, and 3, together with the results from Proposition 1, we present the following MDL-score as our final model selection criterion:EQUATIONwhich has the form of the regularized maximum likelihood, yet without the need to tune the regularization hyperparameter. Note that the exact form of L(M ) depends on the types of the feature variables; e.g., by assuming all variables are continuous, we obtainL(M ) = L N (K)+log 2 C K-1 + j∈[K-1] (log 2 (m) + L N (d j ) + log 2 (C) + d j -1)+ k∈[K] L N (h k ),where, as defined previously, R(.) denotes the regret term of each histogram, L N (.) the Rissanen's integer universal code [42] , m the number of feature variables, d j the granularity level for the search space for the splitting values corresponding to the jth internal node, C the constant that controls the hierarchical structure of the search space of the splitting values, and h k the number of bins for the histogram on the kth leaf node.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 conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: Full descriptions are provided both in the main context and in the appendix. Also, the source code is provided.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to 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 a 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is 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 submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , 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 are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 6. Experimental Setting/Details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: Full descriptions are provided both in the main context and in the appendix.• The answer NA means that the paper does not include experiments. • The experimental setting should be presented in the core of the paper to a 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, or as supplemental material. 
algorithm: 
 While finding the optimal tree-based model with the branch-and-bound approach is possible for regression [59] and classification [18] , this does not apply to our task for two reasons. First, our MDL-based regularization term differs from traditional penalty terms based on tree size. Second, our task resembles optimizing model trees [27, 38] rather than classification and regression trees, as we aim to find the optimal histogram for each candidate split. Update M by replacing S * with its two child nodes that minimize the MDL-score.A greedy approach for tree construction. We thus take a heuristic approach to optimize our MDLscore in Eq. 4. As summarized in Algorithm 1, we start with a tree with one leaf node M = {S 0 }; next, we iteratively update M by replacing one of the leaf nodes with its 'best' two child nodes. Specifically, to achieve the lowest MDL-score at each iteration, we simultaneously search for 1) which node to split, 2) the splitting condition for that node, and 3) the optimal number of bins for the histograms. That is, we iterate over all leaf nodes in M ; for each leaf node, we search for the splitting condition, along with the number of bins for the histograms on the (potential) child nodes, which as a whole minimizes the MDL-score. Notably, while an exhaustive search for the 'best' models on all potential child nodes is considered infeasible in traditional model tree methods [27, 38] , we empirically demonstrate in Section 6.5 that our algorithm is comparable to KDE-based methods.Finding the child nodes. We next elaborate on the search for the tree-splitting condition at each iteration, for which the pseudo-code is provided in Algorithm 2. For simplicity, we assume that all feature variables are either continuous or binary (i.e., categorical features are one-hot encoded in our implementation).Further, we iterate over all columns of the feature matrix. For each column, we start with the granularity level d = 1 and generate candidate split points as the C • 2 d-1 quantiles that lead to equal frequency binning of the values. Note that the quantiles are generated based on the subset of data points covered by the node to be split, rather than the entire dataset. We search for the best split point at the fixed d that yields the minimum MDL score among all generated candidates. We then proceed to the next granularity level d + 1 and repeat the process, which stops if no split point in the next granularity level results in a better (smaller) MDL score.Last, we also need to search for the optimal number of bins for the histogram that leads to the minimum MDL score, which we defer to Appendix B.  
experiments: 
 We present our experiments to demonstrate the empirical performance of CDTree from various perspectives. Specifically, we aim to answer the following research questions: 1) Does CDTree provide more accurate conditional density estimation compared to existing interpretable (tree-based and kernel-based) methods? 2) As a proxy for interpretability, does CDTree have smaller tree sizes in comparison to other tree-based models? 3) Is CDTree robust against irrelevant "noisy" features? 4) Are the runtimes of our algorithm comparable to those of kernel-based methods?We use 14 datasets with numerical target variables from the UCI repository [1] . These datasets, summarized in Table 1 , cover a wide range of sample sizes and dimensionalities. We benchmark our method against a variety of competitors, with all results obtained on the test sets using five-fold cross-validation. Our competitors include 1) NKDE and CKDE [44, 46] , which are based on kernel density estimation, with bandwidth and ϵ (for NKDE only) tuned by cross-validation; 2) LSCDE [54] , which directly estimates the ratio of joint and marginal density using linear models with Gaussian kernel basis functions; 3) tree-based method CADET [6] , which fits a Gaussian distribution on each leaf node; 4) two more tree-based baselines introduced by us, CART-k and CART-h, which respectively fit a KDE model and a histogram after a CART regression tree [5] is learned from data. Furthermore, we compare against three black-box models as "upper" baselines, including 1) neural network methods NF [39] and MDN [4] , which apply both dropout and noise regularization [45] , and 2) the recently proposed tree boosting method LinCDE [13] . Nonetheless, our goal with CDTree is not to be more accurate than black-box models, but to introduce a CDE method that is both interpretable and accurate.For reproducibility, we provide further details about implementation and parameter choices in Appendix C. We made our source code public: https://github.com/ylincen/CDTree. In Table 2 , we report the average negative log-likelihoods (NLL) on the test sets, which can be regarded as an approximation to the expected log-loss E(-log(y|x)), the standard loss function for measuring CDE accuracy.Comparison to interpretable models. The NLL of the CDTree models are the best (lowest) in 6 out of 14 datasets among all interpretable models, which are shown in bold in the table. Further, among all interpretable models, our average rank is the best, as reported in the (last row) of Table 2 . As the datasets are increasingly ranked based on their dimensionalities, we observe that CKDE-although also achieving the best NLL in 6 datasets-only performs well on datasets with low dimensions. Additionally, the other two kernel-based methods LSCDE and NKDE have in general worse accuracy.Further, CDTree has better accuracy (lower NLL) than all tree-based competitors on almost all datasets (13 out of 14 datasets for CADET, and 12 out of 14 datasets for CART-h and CART-k). The superiority of CDTree highlights the advantages of 1) using non-parametric histogram models, and 2) conducting an exhaustive search for optimal histograms for all node splits when learning the tree structure, rather than fitting the model after the tree structure is fixed, as in CART-h and CART-k.Comparison to black-box models. Neural network models generally exhibit better accuracy than interpretable models, as indicated by their average ranks. However, their non-transparency limits their applicability in critical areas. We argue that studying interpretable models and introducing CDTree paves the way for developing local surrogate models [40, 26] , an essential approach for generating post-hoc explainability for black-box models, as no such method currently exists for CDE.Further, the performance of CDTree is surprisingly on par with that of LinCDE. Since CDTree is based on a single tree while LinCDE is a tree ensemble model, we conjecture that the on-par performance is caused by the fact that CDTree adopts non-parametric histograms whereas LinCDE takes a parametric approach (with a much more flexible model class than Gaussian though).We also report the standard deviations of NLL for all methods in Appendix D.1. The standard deviations for our method remain low, indicating stable performance across different datasets.Figure 2 : Left: the number of leaves for tree-based methods. Right: Runtimes of CDTree and kernel-based methods. Note that the y-axes are scaled by log 10 (.)For tree-based models, the size of the trees is an important proxy for the degree of interpretability [29] .We hence compare the number of leaves of CDTree against the other tree-based models CADET and CART (note that CART-h and CART-k have the same tree structures). We demonstrate in Figure 2 (left) that CDTree has smaller tree sizes than the competitors on most datasets.Figure 3 : Number of internal nodes with split conditions that contain irrelevant features. The y-axis is scaled by the squared-root for better visualization.We next investigate whether CDTree is robust against irrelevant features, which is particularly important for the interpretability of tree-based models, since the (intrinsic) explanation contained in the CDTree would not be trustworthy if such robustness did not hold.Specifically, we generate 'noisy' features in two different ways. The first way is to add w irrelevant features randomly drawn from the standard Gaussian distribution to each dataset. The second way is to first randomly select w features from each dataset; then, for each selected feature X j , we generate a 'noisy' feature by adding a Gaussian noise to it, i.e., X ′ j = X j + N (0, s(X j )/2), where s(X j ) denotes the estimated standard deviation. We refer to the irrelevant features generated by the first (second) approach as independent (dependent) noisy features, where w ∈ {3, 5, 10, 20} in both cases. Note that adding X ′ j to the dataset does not change the true conditional density as the target variable is conditionally independent of X ′ j given the original feature X j . Next, we train the tree-based models on expanded datasets that include irrelevant features. We count the number of nodes with splitting conditions that involve these added irrelevant features. As demonstrated in Figure 3 , the number of splits on irrelevant features for our CDTree is almost always zero for both ways of generating noisy features. In contrast, the tree-based models learned by CART and CADET contain many more nodes with irrelevant features. We also examine whether the negative log-likelihoods (NLL) remain stable when irrelevant features are added. For 'dependent noisy' features, the results are shown in Figure 4 , where the NLL of CDTree remains nearly identical regardless of the number of added features-the only exception being the dataset "slump" (with only 103 rows). In contrast, the NLLs obtained by competitor methods are much less stable: the NLL of NKDE varies for most datasets, and CART-k shows visible changes in 6 out of 14 datasets. Similar results are observed when 'independent noisy' features are added, as shown in Appendix D.2.The idea of fitting separate models on the leaves of a decision tree has existed for a long time [38] . Nevertheless, it is (still) often believed that fitting separate models for all possible node splits when growing a tree is infeasible. However, we show in Figure 2 (right) the runtime of CDTree and demonstrate that its runtimes are in general lower than the runtimes of CKDE (which requires intensive parameter tuning). While NKDE and LSCDE are in general faster than CDTree, the accuracy of their conditional density estimates are sub-optimal, as discussed previously. We exclude the comparison with other tree-based methods whose implementations are based on CART, as CART is highly optimized and known to be extremely fast. Further, as these tree-based methods either model the conditional means only (CART-h and CART-k) or assume a Gaussian model (CADET), they have far smaller search space, and hence are fast but less accurate. 
discussion: 
 In this paper, we studied the interpretable conditional density estimation (CDE) models. Motivated by the fact that tree-based methods are arguably more interpretable than kernel-based methods yet have been largely disregarded for interpretable CDE, we introduced the Conditional Density Tree (CDTree). We formalized the learning problem under the MDL framework, proposed an iterative algorithm, and demonstrated its competitive empirical performance on a wide range of datasets.Limitations. As histograms are used in the CDTree, we implicitly assume that the support of the target variable is bounded. Hence, the boundaries for the histograms need to be chosen in an ad-hoc way, possibly based on prior knowledge. Further, in practice, it may happen that the unseen data points fall outside the histogram boundary, for which the predicted (conditional) density will be 0, unless the full model is re-trained. We realize that this may cause some issues when using CDTree in practice, but meanwhile, we argue that 1) this is a limitation of the histogram model itself, 2) similar issues could happen in modelling quantiles by the empirical cumulative probability function, as in well-known methods like quantile regression trees and forest, and 3) all probability models have their own (implicit) assumptions on the probability tails, including those specifically designed for modeling the extreme value distributions [9, 23] .A Proof Proposition 1. Let θ = (α 1 , ..., α K ) be the histogram parameters for histograms on all leaves, and let θ = arg max θ P M,θ (y n |x n ). Then y n max θ P M,θ (yn |x n ) = k∈[K] R(N k , h k ), in which R(N k , h k )is the regret (denominator) of the NML distribution of the histogram model on the kth leaf node that contains N k data points and h k bins.Proof. Consider the dataset D = {x n , y n } and a CDTree with K leaf nodes M = {S 1 , ..., S K }, each leaf S k equipped with a histogram model H k = (B l , B u , h k ), in which h k denotes the number of bins. Denote the histogram density estimator associated with each H k as f H k (.), and in short f k (.), which contains a family of distributions parameterized by α k . Further, denote the subset of data points that end up in the kth leaf as D k = (x {k} , y {k} ) := {(x, y) ∈ D|x ∈ S k }. Thus,y n max θ P M,θ (y n |x n ) = y n max θ k∈[K] f k (y {k} |x {k} ) = y n k∈[K] max α k f k (y {k} |x {k} ) (Fubini's Theorem) = y {1} y {2}...EQUATIONbecause the NML distribution for D k given the histogram H k is equal to [22] EQUATIONFurther, it has been shown that the denominator (regret) of the NML distributions for histogram models is a function that only depends on N k and h k [22] .We further discuss the detail process of finding the number of histogram bins that minimizes the MDL score, for which the pseudo-code is provided in Algorithm 3.While the search space for the number of bins, denoted as h, for the histogram can range from 1 to the number of data points, this is computationally expensive in practice. To mitigate this, we first narrow down the range of h by fixing a step size g and searching among h ∈ {1, g + 1, 2g + 1, . . .}. The MDL-score will initially decrease as we increase the number of bins, since the the goodness-of-fit of the histogram increases. However, when the number of bins become too large, the MDL-based regularization terms will start to dominate, and hence the MDL-score starts to increase.Assuming the MDL-score starts to increase at h = eg + 1 (where e is a positive integer), we can then narrow the range to (e -2)g + 1 ≤ h ≤ eg + 1, since the maximum so far is reached at (e -1)g + 1.Finally, we iterate over all h within this narrowed range, and we select the number of bins with the smallest MDL score.The runtimes reported in Section 6.5 for all algorithms are recorded on the CPU machines with the AMD EPYC 7702 cores.Input: Target values y {S} covered by a leaf node S, step size g Output: Histogram H S that minimizes the MDL-scoreh ′ ← 1; best_score ← +∞ while True do mdl ← calculate the MDL-score given h ′ if mdl < best_score then best_score ← mdl h ′ ← h ′ + g else break end end bound_low ← max(1, h ′ -2g) ;// Since h -2g may be smaller than 1 bound_high ← h ′ h * ← the optimal h within the range bound_low ≤ h ≤ bound_high that minimizes the MDL-score return h *We noticed that duplicated values in datasets may cause some of our competitor methods to fail. For instance, for those methods that adopt the Gaussian kernel, duplicated values can lead to the standard deviation estimated as 0 for some subsets of data points). Thus, we add a very small noise generated by N (0, 10 -3 ) to all data columns, which are used for all methods.The parameter C. We first discuss the parameter C that controls the hierarchical structure for the search space of the splitting values, for which we set C = 5 in our experiments.The parameter C can be used to express a prior belief on the candidate splitting values. For instance, when C = 5, the code length needed for encoding the 5 quantiles when d = 1 are the same. Equivalently, the prior probabilities of these 5 quantiles are the same.As these 5 quantiles divide the values into 6 subsets, essentially, we are saying that the first quantile among these 5 quantiles, i.e., the 1/6-quantile, and the third quantile, i.e., the 1/2-quantile (3/6quantile), have the same prior probability. However, if we set C = 1, there will be only 1 quantile when d = 1, i.e., the 1/2-quantile. In this case, the prior probability for the 1/2-quantile will be different (larger) than the 1/6-quantile.Thus, the parameter C can be used to express the prior belief in the splitting values. That is, one can ask herself that, is it equally likely, a priori, to observe a node containing the splitting value equal to the 1/100-quantile, and to observe a node containing the splitting value equal to the 1/2-quantile (i.e., the median)? If the answer is yes, C might be set as 99. Otherwise, a smaller C should be considered.The step size g. We set g = 30 in searching the number of histogram bins in Algorithm 3. Note that if we set g very large, we only need very few iterations to "narrow" down the range for the number of bins for histograms; nevertheless, the resulting range will not be very narrow in this case. On the other hand, if we set g very small, it may cost a lot of time to obtain the narrower range. In that sense, g = 30 seems a rather balanced choice.The histogram boundary. Further, as discussed in Section 7, we assume that the range of the target variable for each dataset is known. Thus, we set the global range of the histograms based on the range of the full dataset (before train/test split in the cross-validation) plus/minus a small constant, chosen as 10 -3 . Table 3 : Negative log-likelihoods (smaller is better) on test sets, together with the standard deviation, obtained using five-fold cross-validation. We show in Figure 6 the full results of applying CDTree to the medical expenses dataset used in Section 1. As a sanity check for the goodness-of-fit, we report the average cross-validation negative log-likelihood (on test sets) for CDTree is 9.03 (with the standard deviation 0.13), which is slightly better than that of the black-box boosted tree model LinCDE, with the average negative log-likelihood 9.55 (standard deviation 0.09). Each Histogram corresponds to a single leaf that describes a meaningful subgroup of patients, in which we observe 'age', 'BMI', and 'smoker' are the most distinguishing features to characterize each subgroup. Last, although the dataset contains 9 features and only 1338 samples, the illustrations show that CDTree does not require a very large dataset to reveal meaningful and comprehensible information.Figure 6 : All leaves from the CDTree that describes the conditional density of medical costs, conditioned on demographic features. Root-to-leaf conditions are presented after removing logically redundant conditions.• The authors are encouraged to create a 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 authors should reflect on 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 a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: we report the standard deviation of the negative log-likelihoods, obtained by five-fold cross-validation, in Appendix D.1.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, confidence intervals, or statistical significance tests, at 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 (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to 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 in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: We report the compute resources in Appendix C.1.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 in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes]Justification: [NA] Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes]Justification: The paper discusses the positive societal impacts about 1) interpretable CDE methods have advantages in critical domains, 2) CDTree is more interpretable than kernelbased methods because it is also interpretable to the general public without Statistics knowledge. As far as we are concerned, our method does not have the risk of being misused in a malicious way.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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 specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is 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 mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: [NA] 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.https://github.com/freelunchtheorem/Conditional_Density_Estimation 
 
 Appendix:  


Decision: The paper presents an interesting tree-based, interpretable, conditional density estimator. All the reviews seem to agree that the method is of practical utility and is an interesting application of MDL principle. Interpretability in CDE is indeed under-studied. In case the paper is accepted, I request the authors to incorporate all the changes suggested by the reviewers.

Reviews: review: paper_summary: paper_summary: This paper proposes a new conditional density estimation algorithm based on histogram trees. 
The base model corresponds to a full binary tree, where each internal node is associated with a split of the feature space in one coordinate, and each leaf node is associated with a histogram density estimator for the response variable for the feature variable falling into the leaf node.
To find the best among all possible models that best fit the data, the proposed algorithm invokes the MDL principle, which avoids any hyperparameter tuning, to derive the model selection criterion.
Since the optimization is infeasible to be solved exactly over all possible models, the paper proposes a greedy algorithm.
Experiments support that the resulting estimator CDTree is competitive against the state-of-the-art models.
strength_weakness: strength_weakness: While I like the paper overall, the manuscript is not spotless, especially in terms of presentation, grammatical errors, and typographical mistakes.
I believe that after a careful revision of the paper, this would be a nice addition to the community. (Though the fit might be much better with an applied statistics journal.)
questions: questions: **Suggestions**
- The definition of a conditional density tree with histogram in Section 3 seems to be incomplete. I was able to understand the complete model after I read Section 4.3. I believe that this should be properly defined as a model in Section 3, since without a proper definition Section 4.1 and 4.2 read awkward.
For example, what is the dimension of $x$ and do you assume $y\in\mathbb{R}$? Somehow this is not explicitly defined.
- And I think the sentence in lines 108-110 is quite confusing, in the sense that while the model $M$ may depend on the dataset $D$, a covariate $x$ needs not be from the dataset to evaluate the conditional density.
- In Section 4.1, the definition of MDL optimal model is rather abrupt as the "universal model" is defined only in Section 4.2. I believe that the NML code should be defined before (1) or at least there should be a pointer to (2) in that paragraph. The notation $P_M(.)$ is also misleading. Please consider $P_M(\cdot | \cdot)$.

**Questions**
- Why did the authors define $\hat{\theta}$ in Proposition 1 while it is not used?
- Why are CKDE and NKDE put under "interpretable models"? I was confused as the authors emphasized at multiple points that kernel-based methods are not interpretable.
- A silly baseline is to consider a Gaussian density estimator as CADET assumes in the proposed MDL criterion of CDTree. This would result in a faster algorithm as the search space is simple. I am curious how this simple baseline would work in practice, as this can help understand the benefits of using the flexible histograms in place of Gaussians and using MDL principle separately. I would appreciate additional experiments, if time permits.
- (Minor) Regarding the discussion on runtime: Can you provide a bit more quantitative remark, is possible? For example, the authors mention that CART is highly optimized while the proposed algorithm is not. In which part of CDTree could be more optimized?
- Please revise the bibliographic info. For example, "mdl" in the title of [41] should be capitalized.
limitations: limitations: The authors note its limitation regarding the boundedness assumption of target variable.
On top of that, the algorithm is greedy and there is no guarantee on closeness between the actual estimator and the optimal estimator defined by the learning criterion.
paper_summary: paper_summary: This paper proposed to use decision tree with leaves formed by histogram models for conditional density estimation to gain interpretability. Characteristics of the proposed method, along with the density estimation accuracy and run time, are evaluated with numerical experiments.
strength_weakness: strength_weakness: The proposed method can be viewed as a conditional density estimator with partitions on both X and Y space. There is limited novelty as far as I read from this paper.
questions: questions: - If p(y|x) changes smoothly with respect to x, is the proposed method capable of capturing such smoothness, given it is based on partition of X? 
- How to prevent overfitting?
limitations: limitations: The authors discussed some limitations of their method. There is no potential negative societal impact of their work.
I suggest providing some discussion on the questions raised above.
paper_summary: paper_summary: This paper addresses the problem of conditional density estimation, i.e. given a conditioning variable x estimate the whole distribution of y, with special emphasis on interpretability.
For this interpretability requirement, the authors resort to classical decision trees allowing to partition the conditioning space in an interpretable manner. The conditioned distributions of y are modelled with equally-spaced histograms with a variable number of bins.
This construction is optimised in an heuristic manner using an objective function that is built using a Minimum Description Length (MDL) approach, using different codes for the different parts (size and structure of the tree, splitting conditions and histograms) of the construction to be determined.
Experiments show log loss performance that is globally better than interpretable competitors on the selected datasets. Empirically, the trees obtained with this method are shallower than other interpretable tree-based methods and they are more robust to irrelevant features, in the sense that these are less often used for splitting.
strength_weakness: strength_weakness: This work combines in a straightforward manner classical building blocks from the machine learning and information theory literature: decision trees, histograms, MDL, universal codes for integers, ... so there is little novelty in the construction

Although it is advertised that no hyperparameter tuning is needed thanks to MDL, there are still arbitrary choices for the priors and also the hyperparameter C (C=5 in the experiments).
For example, the tree size and structure could be encoded using Willems' approach in Context Tree Weighting  (preorder traversal of the tree, for each node use one bit to say if it is internal or leaf, which is equivalent to putting a 1/2 prior probability of splitting a node).
(F. M. J. Willems, Y. M. Shtarkov, and T. J. Tjalkens. The context-tree weighting method: Basic properties. Information Theory, IEEE Transactions on, 41(3):653–664, 1995.)
This should be discussed.

The MDL approach used in this work is called "crude" in [14]  since there is some arbitrariness in the choice of priors instead of some optimality criterion.
The only part in this work that is "refined" [14] is the NML  used for the histograms themselves but this is something that is well know (Proposition 1 is a simple extension of existing results). 
This should be discussed.

The optimisation method is heuristic and thus its interest for the NeurIPS audience is limited (in fact, most of the algorithm is in the appendix, which indicates that it is not an important contribution).

For these reasons, I think that the novelty and the significance for NeurIPS is quite limited. 

In my opinion, this work would fit better in a more applied venue.

Minor issues:
citations to books (e.g. [6,14]) should be more precise

line 186: "variable name" can be misleading, I suggest to say "variable index"

typo: line 231 "we iterative"
questions: questions: paragraph explaining the role of C and d  (lines 191 to 194) is a bit confusing, can you provide an example showing what are the splitting options that are encoded when d>1 ?
limitations: limitations: Limitations were properly discussed.
paper_summary: paper_summary: This paper proposes a tree-based conditional density estimation model. Previously, conditional density estimation involved: 1) kernel density estimation-based method (requires expensive bandwidth tuning); 2) neural network (black-box approach); 3) a tree-based model which focuses on a Gaussian distribution for the target; 4) regression-based approach. In contrast to these approaches, the proposed method is 1) non-parametric; 2) uses a MDL principle which eliminates the need for hyperparameter tuning for regularization; 3) an iterative algorithm which searches for the optimal histogram in each leaf (thus modeling the full distribution). The authors claim that the proposed method is both more accurate (as measured by the log-loss) and more robust against irrelevant features. Further, the method is smaller in size and improves interpretability (which comes from a tree-based model). The experimental results are provided against a varying range of datasets from the UCI repository. The comparison is provided against other tree-based models and blackbox-approach methods.
strength_weakness: strength_weakness: 1. The dataset used in the experiments is fairly small. To highlight empirical performance in training, the authors are advised to use larger datasets.
2. The method assumes that the support of the target variable is bounded.
3. Some presentational issues in the figure are present. See below in the Questions section.
questions: questions: 1. The method denoted as "Ours" should be formally labeled as "CDTree."
2. Are all of the attributes in the datasets continuous? How would the method handle discrete/categorical attributes?
3. What model selection criteria is used for CART models? Is it the same as Equation 4 which is used for CDTree?
4. Is it possible to move the pseudocodes into the main writeup?
5. Figure 3 may contain some presentational issues. What do "+", "circle" ,"square", etc mean?
limitations: limitations: Overall the paper is reasonable well-written. However, the experimental results are limited to fairly small datasets which unfortunately do not highlight potential scalability of the proposed method. While the focus of the method is on interpretability and accuracy, the authors would have to provide some empirical results on the training phase. In addition, please move the pseudocode description of the algorithm to the main writeup section.

Comments: title: Further clarifications for Figure 3
probability measure on the space of trees
Thanks for the further advices about the writing
Dear authors
Further clarification
alternative prior and "factual error"
More rebuttal
About "Factual Error in Paragraph 2" + "choosing priors" +  "choosing hyperparameter C"
comment: Dear reviewer, 

Thanks for the further comments and thanks a lot for raising the score. 

Regarding your point that "there does not seem to be sufficient evidence that the proposed method works under case (2)", I have brief further clarifications as follows. 

- As shown in our experiment 6.4, our method is very robust against irrelevant features. This indicates that, in the extreme case you mentioned, i.e., when all features are independent of the target variable $Y$, our method would rarely split on any feature; hence, our model would indeed estimate all $p(y|x)$ by a single $p(y)$. 

- After a CDTree is learned from data, and if two feature (vector) $x_1$ and $x_2$ fall into the same leaf node, our model by definition considers the probability distribution $p(Y|X = x_1)$ "close" to $p(Y|X = x_2)$, since we estimate both of them by the same histogram model (that is equipped to this single leaf node). Notably, determining whether $p(Y|X = x_1)$ is "close enough" to $p(Y|X = x_2)$ is then equivalent to determining whether $x_1$ and $x_2$ "should" belong to the same leaf node, which is also equivalent to determining, during the learning process, whether this leaf node should be further split to let $x_1$ and $x_2$ fall into two different leaf nodes instead. Thus, determining all these points is essentially related to the trade-off between model complexity and the estimation accuracy (for both $p(Y|X = x_1)$ and $p(Y|X = x_2)$), which is handled by our proposed MDL model selection approach. Specifically, our highly competitive experiment results on the accuracy of conditional density estimation (measured by the negative log-likelihoods) demonstrate that our proposed method handles well the trade-off.
Thanks for the response. I raise my score since my concern on the partition of X is partially addressed, although there does not seem to be sufficient evidence that the proposed method works under case (2).
Dear reviewer, 

Thanks again for the detailed comments that help improve my paper further! Somehow the second half of your previous comments is missing in the notification email I received from "neurips2024-notifications", which did not contain your further comments about Figure 3. I only noticed this just now and hereby give further clarifications below. 

Although the common way of presenting the results in Figure 3 is to use a separate figure for each individual dataset (often with the x-axis representing "the number of added features" and the y-axis representing "the number of splits on irrelevant features"), this would lead to too many figures for our case (as we tested 14 datasets). We would need to put all these figures in the Appendix then. Thus, we chose to put the results of all datasets together, which can show that our method learns CDTrees with the number of irrelevant features very close to 0 across all datasets.  As a result, we just use the different shapes to keep the information about the number of features added for each "point" on the figure. 

I do agree that this figure may need more brainwork to process than other plots in the paper; however, the advantages are 1) avoiding too many figures for this single experiment subsection, and 2) using one plot for all datasets can better show the "general picture" of different methods. (Nevertheless, I would be happy to consider other possibilities in your mind as well. Thanks in advance!)

Regarding the point you raised "Why are some of these shapes not aligned on the horizontal axis tick", we do this deliberately by "jittering" the points a bit, to avoid some points being fully covered by others. 

Last, thanks for advices about the fonts used in the replies as well!
Given the discussions and the points addressed in the rebuttal, I raise my score to 5.
Many thanks. Page 3 of Athreya is clear already. 

I hence take back my rebuttal point that your proposed prior is not proper, and I agree that it could be an alternative to the current encoding. I have editted the paper to discuss this. 

Besides this point, I argue that the following points in the review have been addressed in my rebuttal (including my further clarifications in the discussion period): 

- The MDL encoding in this paper should not be called "crude", and the choice of priors is not arbitrary yet follows guidelines, e.g., according to the book [14]. 

- We did not advertise "no hyperparameter tuning is needed" throughout the paper. Further, introducing $C$ has several advantages than the traditional "regularization hyperparameter" including: 1) an ad-hoc global choice $C=5$ has been shown to work reasonable well, and 2) $C$ carries an intuitive meaning. 

- While the judgement of novelty is subjective, I respectfully disagree on the characterization of our method as a "straightforward combination of classical building blocks", for reasons that have been discussed in my (initial) Rebuttal. 

Thanks again for the detailed reviews and inspiring discussions for the priors (especially the always swift responses during the discussion period).
You can find the answer in the references given in [A]: Athreya and Ney, 2004; Harris, 1963.
In particular, see Harris Chap VI, Sec 4 "The probability measure P". 
As noted in (Athreya and Ney, 2004) page 3, Harris treats a more general case.

You can find another statement in the first paragraph of the proposition in Sec. 3 of:
Neveu, J. (1986). Arbres et processus de Galton-Watson. In Annales de l'IHP Probabilités et statistiques (Vol. 22, No. 2, pp. 199-207).
Dear reviewer, 

Thanks for the clarification for the questions. For case (2), i.e., for the case "$x1\approx x2$ then $p(y|x=x1)$ is close to $p(y|x=x2)$", $x_1$ and $x_2$ will be in the same leaf node, and both $p(y|x=x1)$ and $p(y|x=x2)$ will be estimated by a single density estimator (a histogram in our proposed method). 

In the extreme case that $p(y|x) = p(y)$ for all $x$, the decision tree will be learned to have only one node (the root node). This is in fact shown by our experiment in Section 6.4 "Robustness to irrelevant features", in which we show that features that are (conditionally) independent to $y$ won't be used for tree splitting.
Thanks for the rebuttal. 
Regarding smoothness, I was asking about the way that the conditional density changes wrt x. There can be roughly two cases: (1) very heteroscedastic case, where p(y|x) can change drastically across x values, and (2) for x1\approx x2, p(y|x=x1) is close to p(y|x=x2), and the limiting scenario would be p(y|x) = p(y) regardless of x values. 
CDE methods that partitions X is generally suitable for case 1, and I would like to hear how the proposed method deals with case 2.
Thanks for the further clarification! Could you clarify why and how a standard Galton-Watson process defines a probability distribution that adds to 1?
Although in [A] the focus is on trees with max depth = D, the constraint can be easily removed. Consider the remark in [A] Sec 3.1 regarding the equivalence to a Galton-Watson process.
In the case of max depth = $D$, the branching process is stopped at generation $D$. In the unconstrained case $D=\infty$, it corresponds to a standard Galton-Watson process and therefore **still defines a probability distribution, i.e., adds up to 1.**
Notice also that in the second part of the original CTW work ( Willems, F. M. (1998). The context-tree weighting method: **Extensions**. IEEE Transactions on Information Theory, 44(2), 792-798. ), the case of  $D=\infty$ is considered.

In conclusion, this way of encoding a tree is a valid alternative for your problem.
Thanks for the further advices about the writing
(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.**
Again, thanks for the detailed and quick response! (Nice to have these technical discussions anyway.)


First, I never claimed that our prior is the only choice. 

Second, I looked at papers you cited and looked at the exact formula of the prior you proposed. Specifically, 

[A] *Papageorgiou, I., & Kontoyiannis, I. (2024). Posterior representations for Bayesian Context Trees: Sampling, estimation and convergence. Bayesian analysis, 19(2), 501-529. *, 

and [A] cited the below

[B] *Kontoyiannis, Ioannis, et al. "Bayesian context trees: Modelling and exact inference for discrete time series." Journal of the Royal Statistical Society Series B: Statistical Methodology 84.4 (2022): 1287-1323.*

And in [B], Lemma 1 shows that the prior $\pi(T) = \alpha ^ {|T| - 1} \beta ^ {|T| - L_D(T)}$ sums to 1, **for all trees $T$ with the depth smaller than the given number $D$, which does not apply to our case as we do not have the constraint on the tree depth**. (You could say, the max depth $D$ can be specified as the sample size $n$, yet this is a bit arbitrary as it has influence on the priors for trees that reach (or do not reach) the depth $D$ (see the formula). It is at least much less natural for the decision tree for CDE than for the variable-memory Markov chains in [A]. 

Last, I found where another misunderstanding is from. In your original review, you stated that 

*"For example, the tree size and structure could be encoded using Willems' approach in Context Tree Weighting (preorder traversal of the tree, for each node use one bit to say if it is **internal or leaf**, which is equivalent to putting a 1/2 prior probability of splitting a node)"*. However, this is **different** from what is described in Section 3.1 of [A], as no prior probability will be put on those nodes that reach the max depth **(i.e., leaves)**. In fact, it seems to me that your statement above actually says that, given a list of nodes (with a pre-defined order), we specify a prior probability 1/2 on whether to split **independently** to each node; however, in a branching process there is no such indepdency. This is where the misunderstanding mainly comes from. 

It is indeed an elegant way to encode a tree with the max depth given. Very nice to know.
In *Papageorgiou, I., & Kontoyiannis, I. (2024). Posterior representations for Bayesian Context Trees: Sampling, estimation and convergence. Bayesian analysis, 19(2), 501-529.*,  **proper  $m$-ary trees** are considered,  which are defined as follows:

*A tree $T$ is called proper if any node in $T$ that is not a leaf has exactly $m$ children.* 

For $m=2$, it corresponds to full binary trees.
So, **I don't see where the "factual error" is.**

Regarding your futher explanation, I think I see where your misunderstanding comes from : in the Bayesian Context Trees prior,  the structure is encoded **without conditioning on the total number of leaves.** 
The total number of leaves is not explicitly encoded as in your approach.
So, your example gives the correct prior of that particular tree but **it is not the only one**: you need to sum over the whole set of full binary trees.
I appreciate the authors' response. 
Please consider revising the manuscript with the points raised in my review, as well as other reviews. Especially I found that the reviewer n5cC raised many interesting questions, which could help further improve the depth of the paper if properly answered. 
I will keep my score as is, since I believe there is a sufficiently good contribution in this paper.
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.
Thank you for your detailed response.

Your choice of prior for the model consists in encoding the size (number of leaves $K$) with Rissanen's code for integers and then a uniform prior over all trees with K leaves ($1/C_K$). 
I mentioned another possibility which is the prior used in CTW, which puts 1/2 probability on splitting each node.
In a series of papers on Bayesian Context Trees, a more general version is considered with a parameter $\beta$ defining the probability of not splitting, that is, the larger beta, the larger the penalization of more complex models.
See Section 3.1 of 

*Papageorgiou, I., & Kontoyiannis, I. (2024). Posterior representations for Bayesian Context Trees: Sampling, estimation and convergence. Bayesian analysis, 19(2), 501-529.*

I don't understand your remark:
*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)*

If every node is a leaf node => the tree has only one node (the root) => it's a valid decision tree and its prior probability is 1/2 with Willems' scheme.

As mentioned in the reference above on Bayesian Context Trees, one can see the splitting process as a Galton-Watson process, proving that the prior is proper.

As you say: "C establishes a hierarchical structure"  and "This hierarchy helps express prior beliefs about model complexity". Although I understand that empirically C=5 worked well for all the datasets considered, there is no theoretical proof showing that this is a universal constant that shouldn't be tuned.
So I still think that "no hyperparameter tuning is needed" should be at least toned down, since there could be datasets for which some tuning would be beneficial.

Can you clarify how your prior satisfies (1.) of page 426 of the MDL book?