A partial likelihood approach to tree-based density modeling and its application in Bayesian inference

Li Ma, Benedetta Bruni · 2024

Read A partial likelihood approach to tree-based density modeling and its application in Bayesian inference by Li Ma, Benedetta Bruni (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-11692.txt.

Introduction

Li Ma and Benedetta Bruni wrote a 2024 paper on a smarter way to build tree-based models of probability distributions. Tree priors split the data space into nested regions. To capture detail everywhere, the candidate splits must reach deep in every region. That depth makes fitting slow and invites overfitting where data are scarce.

Standard practice keeps trees shallow, which blunts their local detail and wastes data. Letting splits adapt to where data cluster would help, but it breaks Bayesian coherence by using the data twice. The authors restore coherence with Cox's partial likelihood trick. Their approach slots into existing likelihood-based methods. It promises deeper trees where data are dense and shallow ones where they are thin, without double dipping.

Catalog record

CREATORLi Ma, Benedetta Bruni
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-11692

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A partial likelihood approach to tree-based density modeling and its application in Bayesian inference Li Ma, Benedetta Bruni Abstract Tree-based priors for probability distributions are usually specified using a predetermined, data-independent collection of candidate recursive partitions of the sample space. To characterize an unknown target density in detail over the entire sample space, candidate partitions must have the capacity to expand deeply into all areas of the sample space with potential non-zero sampling probability. Such an expansive system of partitions often incurs prohibitive computational costs and makes inference prone to overfitting, especially in regions with little probability mass. Thus, existing models typically make a compromise and rely on relatively shallow trees. This hampers one of the most desirable features of trees, their ability to characterize local features, and results in reduced statistical efficiency. Traditional wisdom suggests that this compromise is inevitable to ensure coherent likelihood-based reasoning in Bayesian inference, as a data-dependent partition system that allows deeper expansion only in regions with more observations would induce double dipping of the data. We propose a simple strategy to restore coherency while allowing the candidate partitions to be data-dependent, using Cox’s partial likelihood. Our partial likelihood approach is broadly applicable to existing likelihood-based methods and, in particular, to Bayesian inference on tree-based models. We give examples in density estimation in which the partial likelihood is endowed with existing priors on tree-based models and compare with the standard, full-likelihood approach. The results show substantial gains in estimation accuracy and computational efficiency from adopting the partial likelihood. Keywords: Bayesian nonparametrics, generative models, trees, recursive partitioning, density estimation, flow cytometry 1 Introduction Bayesian modeling for probability distributions based on trees typically involves specifying a prior on the space of recursive partitions. While allowing a rich collection of potential partition locations to be supported under such a prior is desirable for effectively characterizing the underlying distribution, incorporating flexible partition locations substantially expands the space of candidate trees, leading to challenges in effectively sampling over such spaces. This is a core challenge in efficient and scalable Bayesian tree-based inference, especially in multivariate and high-dimensional settings. Consequently, some well-known tree-based generative models in the Bayesian literature have focused on trees with constrained partition locations, most commonly requiring the splits in the recursive axis-aligned partitions to occur at predetermined, data-agnostic locations along one of the dimensions (e.g., the midpoint). Some famous examples include the Pólya tree ( Ferguson, 1973 ; Lavine, 1992 ) and tail-free processes ( Freedman, 1963 ) in nonparametric Bayesian modeling. These restricted partition schemes specified without regard to the actual data at hand often result in excessive partitioning in low-density regions with few observations, causing overfitting (or high variance) and unnecessary computation, while not dividing the sample space deep enough in regions with a high concentration of data, resulting in underfitting (or large bias) there. Some previous works attempt to address overfitting by incorporating regularization into the modeling. For example, the optional Pólya tree (OPT) ( Wong and Ma, 2010 ; Ma, 2017 ) adopts the ideas from Bayesian CART ( Chipman et al., 1998 ) in incorporating randomized stopping, a form of hard thresholding to avoid excessive partitioning. This type of regularization is achieved through the prior specification only after the sampling model (or the likelihood) has been specified, and therefore it can only address the overfitting arising from an overparameterization in the likelihood in parts of the sample space where the predetermined partition tree is deep enough, but is incapable of addressing the underparameterization arising from insufficiently deep trees that cause underfitting on those parts of the sample space with high probability mass and rich distributional structure. Such issues are not unique to Bayesian approaches to tree learning. In fact, non-Bayesian tree-based algorithms usually consider partitions that divide on or midway in between the observed data values, which greatly reduces the complexity of the space of candidate partition trees. Moreover, by considering splits along marginal empirical quantiles (such as the median), they alleviate the local over- and underfitting issues by forcing all tree nodes at the same depth to contain roughly the same number of data points. See, for example, a recent algorithm introduced for density estimation ( Walther and Zhao, 2023 ) that employs such a design. These approaches generally deviate from likelihood-based inference and sacrifice many benefits that come with using the likelihood ( Berger and Wolpert, 1988 ) . A natural question is then whether one could incorporate data-dependent partition locations into likelihood-based inference so that the sampling model and hence the likelihood is parameterized in a way that makes downstream inference more efficient and robust. In the absence of oracular knowledge about the actual population marginal quantiles, a straightforward if not naïve approach is to adopt marginal empirical quantiles as the split points in the partition tree. This, of course, runs the risk of “double dipping” the data. A simple remedy is data-splitting—by dividing the training data into two parts, using one part to define partition locations and the other to estimate the underlying density based on the chosen partition grid. While valid, this approach can “waste” a significant portion of the data and cause a decay in the frequentist risk of the resulting estimator. We exploit a new “data splitting” strategy that operates on the basis of a dyadic recoding of real-valued observations into a sequence of 0’s and 1’s and then performs data splitting on such sequences. Consequently, the basic unit of empirical evidence is no longer a single observation x from the corresponding unknown distribution, but the individual 0s and 1s in the corresponding sequence for x . This allows a smaller fraction of the data to be used to pin down the partition locations. Intuitively, if x is only used to guide the choice of partition grids within a subset A of the sample space, then the event that the data point arises in A , that is, x\in A , should still contribute to the learning of the underlying density. The naïve data-splitting strategy would discard x in its entirety, but the dyadic recoding will preserve such information. While the dependency on the same data in specifying the partition tree as those used to estimate the underlying distribution appears to be at odds with pure likelihood-based inference, we show that through the dyadic recoding such a strategy is in essence carrying out inference based on Cox’s partial likelihood ( Cox, 1975 ) . A practical consequence is that recipes for Bayesian inference under popular priors on tree-based density models can proceed based on the partial likelihood with only minor modifications. We use the OPT prior ( Wong and Ma, 2010 ) to demonstrate how such inference can proceed, and show empirically the improvement in estimation accuracy that arises from the more effective data-dependent parametrization of the underlying density. 2 Method 2.1 Likelihood decomposition along a dyadic partition tree We start by presenting a dyadic recoding of data that leads to equivalent likelihood functions under i.i.d. sampling. Suppose we observe training data x_{1},x_{2},\ldots,x_{n}\in\Omega\subset\mathbb{R}^{d} that are i.i.d. samples from an unknown distribution F with density f=dF/d\mu . Without loss of generality, assume that \Omega is a compact rectangle, e.g., [0,1]^{d} . To begin, we assume d=1

Read the complete text