Generative Forests
Authors: Richard Nock
Mathieu Guillame-Bert
Venue: NeurIPS 2024 poster (2024)
Keywords: tabular data
generative models
boosting
trees
Primary area: learning_theory
TL;DR: A new class of tree-based generative models and a training algorithm with fast, boosting compliant induction and models that can be used for data generation, missing data imputation and density estimation.

Abstract: We focus on generative AI for a type of data that still represent one of the most prevalent form of data: tabular data. We introduce a new powerful class of forest-based models fit for such tasks and a simple training algorithm with strong convergence guarantees in a boosting model that parallels that of the original weak / strong supervised learning setting. This algorithm can be implemented by a few tweaks to the most popular induction scheme for decision tree induction (*i.e. supervised learning*) with two classes. Experiments on the quality of generated data display substantial improvements compared to the state of the art. The losses our algorithm minimize and the structure of our models make them practical for related tasks that require fast estimation of a density given a generative model and an observation (even partially specified): such tasks include missing data imputation and density estimation. Additional experiments on these tasks reveal that our models can be notably good contenders to diverse state of the art methods, relying on models as diverse as (or mixing elements of) trees, neural nets, kernels or graphical models.

Generative Forests
Richard Nock
Mathieu Guillame- Google gbmâgoogle.com com
Google Research ri richardnockkooogle.cco
Abstract
We focus on generative AI for type of data that still represent one of the most prevalent form of data: tabular data, Our paper introduces two key contributions: a powerful class of forest-based models fit for such tasks and simple training algorithm with strong convergence guarantees a boosting model that parallels that of the original weak / strong supervised learning setting. This algorithm can be implemented by a few tweaks to the most popular induction scheme for decision tree induction (i.e. supervised learning) with two classes. Experiments quality of generated data display substantial improvements compared to the state of the art. The losses algorithm minimize and the structure of our models make them practical for related tasks that require fast estimation of a density given a generative model and observation (even partially specified): such tasks include missing data imputation and density estimation. Additional experiments on these tasks reveal that our models can be notably good contenders to diverse state of the art methods, relying on models as diverse as (or mixing elements of) trees, neural nets, kernels or graphical models.
the
Introduction
There is substantial resurgence of interest in the ML community around tabular data, not just because still one of the most prominent kind of data available [6]: is recurrently a place of sometimes heated debates on what the best model architectures solve related problems. For example, even for well-poses problems with decades of theoretical formalization like supervised than decade of deep learning disruption
(22). there is still much ink spilled in the debate decision forests vs neural nets (28). Generative A makes no exception. Where the consensus has long been established on the best categories of architectures for data like image and text (neural nets), tabular data still flourishes with a variety of model architectures building up or mixing elements from knowledge representation, logics, kernel methods, graph theory, and of course neural nets [4, 9 12,
learning [39] after
43 44 (see Section 2). Because of the remarkable nature of tabular data where single variable can bring considerable information about target to model, each of these classes can be relevant choice at least in some cases (such is is the conclusion of (28 in the context of supervised learning). key differentiator between model classes is then training and the formal guarantees it can provide [31] 44].
31 34
In this paper, we introduce new generative models based on sets of trees that we denote as generative forests (GF), along with training algorithm which has two remarkable features: it is extremely simple and brings strong convergence guarantees
weak strong learning model that parallels that of the original boosting model of Valiant's 's PAC learning
[18]. These guarantees improve upon the best state the art guarantees 44 B1. Our training algorithm, GF. BOOST, supports training from data with missing values and is simple enough to be implementable by a few tweaks the popular induction scheme for decision tree induction with two classes, which is supported by a huge number
"We use this now common parlance expression on purpose, to avoid confusion with the other "generative" problem that consists in modelling densities 7 37
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

domain
tree, 50 splits
GF, 50 stumps
Table I: Left: domain circgauss. Center: density learned by generative forest (GF) consisting of a single tree, boosted for a small number (50) of iterations. Right: density learned by GF consisting of 50 boosted tree stumps (Center and Right learned using GF. BooST). In domain X with dimension d, single tree with n splits can only partition the domain in n + 1 parts. On the other hand, a set of n stumps in a GF can boost this number to n (4))) (the tilda omits log dependencies), which explains why the right density appears much better than the central one, even when each tree is just stump.
of repositories ML software implementing algorithms like CART or C4.5 II 35 3
36 451. From
the model standpoint, generative forests bring sizeable combinatorial advantage over its closest competitors, generative trees [31] (see Table [ for an example) and adversarial random forests [44]. Experiments variety of simulated or readily available domains display that our models can substantially improve upon state of the art, with models of ours as simple as set of stumps potentially competing with other approaches building much more complex models.
The models we build have an additional benefit: it is computationally easy to compute the full density given observation, even partially specified; hence, tasks like missing data imputation or density estimation. Additional experiments clearly display that our approach can be a good contender the state of the art. To save space and preserve readability, all proofs and additional experiments and results are given in an Appendix.
generative models also be used for side
2 Related work
would not do justice to the large amount of work in the field of "Generative AI" for tabular data to just sample few of them, so devote part of the Appendix an extensive review of the state of the art. Let us just mention that, unlike for unstructured data like images, there is a huge
variety of model types, based on trees 7
[4] 20 47), probabilistic circuits [ 43 38], kernel methods 4 34 graphical models [41 (among others: note that some
31 4
neural networks [12
are in fact hybrid models). The closest approaches to ours are 44 and (31) because the models include trees with a stochastic activation of edges to pick leaves, and a leaf-dependent data generation process. While (3 learn single tree, 44 use way to generate data from set of trees -aee-calll called an adversarial random forest which is simple: sample tree, and then sample an observation from the tree. The model thus simple but not economical: each observation generated by a single tree only, each of them thus having to represent a good sampler in its own. In our case, generating one observation makes use of all trees (Figure [ see also Section 4). We also note that the theory part of 44 is limited because it resorts to statistical consistency (infinite sample) and Lipschitz continuity of the target density, with second derivative continuous, square integrable and monotonic. Similarly, 31 resort to a wide set of proper losses, but with a symmetry constraint impeding in generative context. As we shall see, our theoretical framework does not suffer from such impediments.
3 Basic definitions
Perhaps surprisingly at first glance, this Section introduces generative and supervised loss functions. Indeed, our algorithm, which trains data generator and whose overall convergence shall be shown on a generative loss, turns out to locally optimize supervised loss. For the interested reader, the key link, which is of independent interest since it links in our context losses for supervised and generative learning, is established in Lemma A (Appendix).
Vk E N let [A] = {1, 2, ..., k). Our notations follow 37.. Let B = (π, A, B) denote a binary task, where A, B (and any other measure defined hereafter) are probability measures with the same support, also called domain, X, and E [0, 1] is prior. M - π A + (1 T B is the corresponding mixture measure. For the sake of simplicity, we assume X bounded hereafter, and note that tricks can be used to remove this assumption [1 Remark 3.3]. In tabular data, each of the dim(X) features

---

ARE 4
GB (this puper)
Figure 1: Sketch of comparison of two approaches to generate one observation, using Adversarial Random Forests [4] (left) and using generative forests, GF (right, this paper). In the case of Adversarial Random Forests, tree is sampled uniformly random, then leaf is sampled in the tree and finally an observation is sampled according to the distribution "attached" to the leaf. Hence, only one tree is used generate observation. In our case, we leverage the combinatorial power of the trees in the forest: all trees are used to generate one observation, as each is contributing to one leaf. Figure 3 provides more details on generation using GF.
can be of various types, including categorical, numerical, etc., and associated to natural measure (counting, Lebesgue, etc.) so we naturally associate X to the product measure, which can thus be of mixed type. We also write X = x X,, where X; is the set of values that take variable i. Several essential measures will be used in this paper, including U, the uniform measure, G, the measure associated generator that we learn R, the empirical measure corresponding a training sample of observations. Like in [31]. we do not investigate generalisation properties. Loss functions There is a natural problem associated probability that an arbitrary observation these negative -. To learn supervised model X [0, 1] for such a class probability estimation (CPE) problem, one usually has access to a set of examples where each is a couple (observation, class), the class being in set = {-1, 1] (=(negative, positive)). Examples are drawn i.i.d. according to B. Learning model is done by minimizing a loss function: when it comes to CPE, any such CPE loss 2 some & y x [0. 1]
binary task 2, that of estimating the X was sampled from A - call such positive or B call
whose expression can be split according to partial losses l1, f, E(y. u) = [y 11 8, (u) + [V -1] (m). Its (pointwise) Bayes risk function is the best achievable loss when labels are drawn with particular positive base-rate,
L(p) inf Ey-B(p) (Y,u),
where Bernoulli random variable for class 1. A fundamental property for a CPE loss is properness, encouraging to guess ground truth: l is proper iff L(p) B(p (( p), Vp E [0, 1]. and strictly proper if L(p) < B(p) E(Y, u), Vu * p. Strict properness implies strict concavity of Bayes risk. For example, the square loss has é (u) = (1 2) e (u) = u² and, being strictly proper, Bayes risk (u) = u11 u). Popular strictly proper ML include the log and Matusita's 's losses. All these losses are symmetric since 2 = C (1 u), Vu E (0, 1) and differentiable because both partial losses are differentiable.
In addition to CPE losses, we introduce a set of losses relevant to generative approaches, that are popular in density ratio estimation (29 40 For any differentiable and convex F IR R, the Bregman divergence with generator F is (F(e = F(z) F(=') (=- (0===))e (='). Given function : IR- - R, the generalized perspective transform of F given is F(z) = g(z) F (z/g(=)), being implicit notation F
26
27
32
The Likelihood ratio risk of B with respect to for loss is
dA
dB
De (A,
क. T-
P(
P
(2)
du
du
with g(2) = 2 (1- x)/T in the generalized perspective transform. The prior multiplication is for technical convenience. Dy is non-negative; strict propereess is necessary for a key property of Dy:: Dr = 0 iff A = B almost everywhere 31].
4 Generative forests: models and data generation
Architecture We first introduce the basic building block of our models, trees. Definition 4.1. A tree T is a binary directed tree whose internal nodes are labeled with an observa- tion variable and arcs are consistently labeled with subsets of their tail node's 's vuriable domain.
Consistency is an important generative notion; informally, postulates that the ares' labels define partition of the measure's 's support. To make this notion formal, we proceed need key definition.
3

---

Personal status &
Number exieting credits
(ART) ARL ARE
(A51,
Number existing crects
Job
0,,12,3,,4
6,
(1772,177)
A177
Personal studuse
JA93, A02)
(AG4)
Rt Carmas Crudit
Figure 2: A GF (T 2) associated to UCI German Credit. Constraint (C) (see text) implies that the domain of "Number existing credits" is {0, 10.,1,,.,,,, 8), that of "Job" is (A171, A172, A173, A174), etc.
Algorithm 1 INTI(()))F_1
Algorithm STARUPDATE(T, R)
Trees (Yrll- of a GF; Step 1 for / E [T] Tr,/² root;;
Input:
Input:
Tree T. subset @ c X. measure R: Step 1 if B B(p [Tr. ele) = then e Nx.u n C, T.v" T.,;;;
Y,.done [T A(T.)l:
else
Ny. n e; T.u" T.4f; Step 2: if e T.A then done - true;
For any node us E N(T) (the whole of nodes of Y, including leaves), we denote Xg X the support of the node. The root has X, = X. To get X, for any other node, we initialize it to X and then descend the tree from the root, progressively updating X₂ by intersecting an arc's observation variable's 's domain in X, with the sub-domain labelling the arc until we reach v. Then, a labeling of ares tree consistent iff it complies with one constraint (C):
(C) for each internal node v and its left and right children 1/,, Vt. (respectively). X, = XY,, U Xn and the measure of Xr, Xe, with respect G is zero
For example, the first split at the root of a tree is such that the union of the domains at the two ares equals the domain of the feature labeling the split (see Figure 2 We define our generative models.
Definition 4.2. A generative forest (GF), G, is a set of trees, (Me)T=1. associated to measure R (implicit in notation).
Figure 2 shows example of GF. Following the consistency requirement, any single tree defines recursive partition of X according to the splits induced by the inner nodes. Such is also the case for a set of trees, where intersections of the supports of tuples of leaves (1 for each tree) define the subsets:
P(G) = {oT=IX S.t. A A(T.), Vi3
(A(T) c N(T) is the set of leaves of T). Notably, we can construct the elements of (P(G) using the same algorithm that would compute it for tree. First, considering a first tree Tr, we compute the support of leaf, say Ix,, using the algorithm described for the consistency property above. Then, we start again with a second tree Y₂ but replacing the initial X by XX, yielding Xx, n Xx,- Then until the last tree is processed.
we repeat with third tree Y3 replacing X by Xx, Xxg, and This yields one element of (PG).
Generating one observation Generating one observation relies on stochastic version of the proce- dure just described. It ends up in an element of P(G) of positive measure, from which we sample uniformly one observation, and then repeat the process for another observation. To describe the process at length, we make use of two key routines, INIT and STARUPDATE, see Algorithms/ [ and 2 INIT initializes "special" nodes in each tree, that are called star nodes, to the root of each tree (nota- tion for a variable e relative to tree Y is T.v). Stochastic activation, performed in STARUPDATE, progressively makes star nodes descend in trees. When all star nodes have reached leaf in their respective tree, an observation is sampled from the intersection of the leaves' domains (which is an element of P(G)). A Boolean flag. done takes value true when the star node is in the leaf set of the tree, indicating no more STARUPDATE calls for the tree (I.] is Iverson's 's bracket, (21)).
STARUPDATE called with a tree of the GF for which done is false, a subset of the whole domain
and measure R. The first call of this procedure is done with e = X. When all trees are marked done, e has been "reduced" to some e, P(G), where the index reminds that this the last C we obtain, from which sample observation, uniformly at random in C, Step in STARUPDATE is

---

Aller Lott
STARUTDNTE
STARU
STAHUPPATE 10
STABURINT on
STARUHOATE to
Figure 3: From left to right and top to bottom: updates of the argument of STARUPDATE through a sequence of run of STARUPDATE in generative forest consisting of three trees (the partition of the domain induced by each tree is also depicted, alongside the nature of splits, vertical or horizontal, at each internal node) whose star nodes are indicated with chess pieces (H,, H. 4)). In each picture, é is represented at the bottom of the picture (hence, e = X after INIT). In the bottom-right picture, all star nodes are leaves and thus C, e displays the portion of the domain in which an observation is sampled. Remark that the last star node update produced no change in C.
fundamental: it relies on tossing an unfair coin (a Bernoulli event noted B(p)), where the head probability p is just the mass of R in Xr. n relative to C. Hence, if of O C = C. = 1. There is a simple but important invariant (proof omitted).
Lemma 4.3. STARUPDATE, always holds that the input e satisfies C g NY.
We have made no comment about the sequence of tree choices over which STARUPDATE is called. Let call admissible such sequence that ends up with some C, X. T being the number of trees (see INIT), for any sequence E [7] D(C.), where D(C.) is the sum of the depths of all the star leaves whose support intersection is C,, we say that e is admissible for C, if there exits a sequence of branchings in Step of STARUPDATE, whose corresponding sequence of trees follows the indexes in v, such that at the end of the sequence all trees are marked done and the last C = C., Crucially, the probability to end up in C, using STARUPDATE, given any of its admissible sequences, is the same and equals its mass with respect to R.
Lemma 4.4. For any e, E (PG) and admissible sequence v E [T] for C,, PG [C, = PR. [c.].
The Lemma is simple to prove but fundamental in our context as the way one computes the sequence and thus the way one picks the trees does not bias generation: the sequence of tree choices could thus be iterative, randomized, concurrent (e.g. if trees were distributed), etc., this would not change generation's 's properties from the standpoint of Lemma 4.4 We defer to Appendix (Section H. three examples of sequence choice. Figure |illustaate a sequence and the resulting C,,
Missing data imputation and density estimation with GFS A generative forest is not just gener- ator: it models a density and the exact value of this density at any observation is easily available. Figure 4 (top row) shows how to compute it. Note that if carried out in parallel, the complexity to get this density is cheap, of order O (max, depth( (T)). If one wants to prevent predicting zero density, one can stop the descent if the next step creates a support with zero empirical measure. A GF thus also models an easily tractable density, but this fact alone is not enough to make it good density estimator. To get there, one has to factor the loss minimized during training. In our case, as we shall see in the following Section, we train a GF by minimizing an information-theomm directly formulated on this density ( So, using a GF also for density estimation can be reasonable additional benefit of training GFs.
loss
The process described above that finds leaves reached by an observation can be extended to missing values in the observation using standard procedures for classification using decision trees. We obtain a simple procedure to carry out missing data imputation instead of density estimation: once a tuple of leaves is reached, one uniformly samples the missing features in the corresponding support. This is fast, but at the expense of a bit more computations, we can have much better procedure, as explained in Figure 4 (bottom row). In first step, we compute the density of each support subset corresponding to all (not just 1 as for density estimation) tuples of leaves reached in each tree. This provides us with the full density over the missing values given (i) partial assignment of the tabular domain's 's variables and (ii) the GF. We then keep the elements corresponding to the maximal density value and finally simultaneously sample all missing features uniformly in the corresponding domain. Overall, the whole procedure is (d (E, dc))).
5

---

dessity ciimaation
R10
06
Vol
36
impiration
mAX d,
M
U[[a, 6D
pprrtal observation (y" unkenow))
partol observation (' urrrrwwy
Figure 4: (Top row) Density estimation using GF, an observation indicated by (Left). In each tree, the leaf reached by the observation found and the intersection of all leaves' supports is computed. The estimated density at is computed as the empirical measure in this intersection over its volume (Right)). (Bottom row) Missing data imputation using the same GF, and an observation with one missing value (if X c IR2 then y is missing). We first proceed like in density estimation, finding each tree all leaves potentially reached by the observation y were known (Left); then, we compute the density in each non-empty intersection of all leaves' supports; among the corresponding elements with maximal density, we get the missing value(s) by uniform sampling (Right).
Algorithm 3 GF. BF..BOS, J)
Input: measure R. #iters J. #trees 7;
Output: trees (T,).-1 of GF G;
Step 1: T {T, (root)??=i
Step 2: for = to
Step 2.1 : T, <- tree (T);
Step 2.2 : As - leaf (Y.);
Step 2.3 p aaplitPred (Aa, T.R.R
Step 2.4: split(T..AA.p))
return T;
Learning generative forests using supervised boosting
From the GAN framework to a fully supervised training of generative models It can appear quite unusual to train generative models using a supervised learning framework, so before intro- ducing our algorithm, we provide details on its filiation in the generative world, starting from the popular GAN training framework [12. In this framework, one trains a generative model against a discriminator model which has purpose other than to parameterize the generative loss optimized. As shown in [33], there is generally incvitable slack between the generator and the discriminator losses with neural networks, which translates into uncertainty for training. 31] show that the slack disappears for calibrated models, a property satisfied by their generative trees (and also by our generative forests). Moreover, (31 also show that the GAN training can be simplified and made much more efficient for generative trees by having the discriminator (a decision tree) copy the tree structure of the generator, setting defined copycat. Hence, one gets reduced uncertainty and more efficient training. Training still involves two models but becomes arguably very close to the celebrated boosting framework for top-down induction of decision trees [19]. up to the crucial detail that the generator turns out to implements boosting's leveraged "hard" distribution. This training gives guarantees on the likelihood ratio risk define in 2 Our paper closes the gap with boosting: copycat training can be equivalently simplified to training a single generative model in a supervised (2 classes) framework. The two classes involved are the observed data and the uniform distribution. Using the uniform distribution is allowed by the assumption that the domain is closed, which is reasonable for tabular data but can also be alleviated by reparameterization [1 Remark 3.3]. The (supervised) loss involved for training reduces to the popular concave "entropic" -tyle losses used in CART, C4.5 and in popular packages like scikit teaann. And of course, minimizing such losses still provides guarantee on the generative loss 2 While it is out of scope to show how copycat training does ultimately simplify, we provide components of the "end product": algorithm, loss optimized and the link between the minimization of the supervised and generative losses via boosting.

---

The algorithm To learn GF, we just have to learn its set of trees. Our training algorithm, GF. BOOST (Algorithm B}. performs a greedy top-down induction. In Step 1, we initialize the set of T trees to 7 roots. Steps 2.1 and 2.2 choose a tree (Tx)) and leaf to split (A4) in the tree. In our implementation, we pick the leaf among all trees which is the heaviest with respect to R. Hence, we merge Steps 2.1 and 2.2. Picking the heaviest leaf is standard to grant boosting in decision tree induction [19]; in our case, there is a second benefit: we tend to learn size-balanced models. For example, during the first J = ' iterations, each of the T roots gets one split because each root has a larger mass (1) than any leaf in a tree with depth > 0. Step 2.4 splits Y + by replacing X by a stump whose corresponding splitting predicate, p. is returned in Step 2.3 using a weak splitter oracle called splitPred. "weak" refers to boosting's 's weak/strong learning setting [18] and means that we shall only require lightweight assumptions about this oracle; in decision tree induction, this oracle is the key to boosting from such weak assumptions [19]. This will also be the case for our generative models. We now investigate Step 2.3 and splitPred.
The weak splitter oracle spli splitprer tPre In decision tree induction, a splitting predicate is chosen to reduce an expected Bayes risk ( (e.g. that of the log loss (36), square loss M1, etc.). In our case, splitPred does about the same with catch in the binary task it adresses, which i Ber (T,, R, U) (our mixture measure is thus M = π R + (1 -)- U). The corresponding expected Bayes risk that splitPred seeks to minimize is just:
TPplee] PM]e]
L(T)
=
Σ PM[e]- L (EP(T)
(4)
The concavity of L implies (L) & [(T). Notation P(-) overloads that in (3) by depending explicitly on the set of trees of G instead of G itself. Regarding the minimization of (4 there are three main differences with classical decision tree induction. The first is computational: in the latter case, (4) is optimized over single tree: there is thus single element in P(T) which is affected by the split, Xx,. In our case, multiple elements in P(T) can be affected by one split, so the optimisation is more computationally demanding but a simple trick allows to keep it largely tractable: we do not need to care about keeping in PPT) support elements with zero empirical measure since they will generate no data. Keeping only elements with strictly positive empirical measure guarantees a size [P(T) never bigger than the number of observations defining R. The second difference plays to our ad advantage: compared to classical decision tree induction, a single split generally buys a substantially bigger slack in [(J in our case. To see this, remark that for the candidate leaf Xa.
TPR [e]
[e] P PM [Xx]]
(TPpp [c] p M [c]
Σ
PMLC]- L
Σ eE P(T) e Xx*
L
P PM[e]
e P(T)
e Xxx
<PRR [xxm]
< P PM L
PM [xx,]
(because L is concave and EeEP(T),Ex,, PR pa[e] = PR (xxx..).. The top-left term is the contribution of > to LLJ), the bottom-right one its contribution to L((Tx)) (the decision tree case), so the slack gives a proxy to our potential advantage after splitting. The third difference with decision tree induction is the possibility to converge much faster to a good solution in our case. Scrutinizing the two terms, indeed get that in the decision tree case, the split only gets two new terms. In our case however, there can be up to 2 Card([e E P(T)- C = xx,²) 1) new elements in P(T).
Boosting Two questions remain: can quantify the slack in decrease and of course what quality guarantee does it bring for the generative model G whose set of trees is learned by GF. BooST ? We answer both questions in single Theorem, which relies on a weak learning assumption that parallels the classical weak learning assumption of boosting:
Definition 5.1. WYLA(Y, K)) There exists Y > 0, <.>>>. such that at each iteration of GFBBOOST, the couple (^*,, p) chosen in Steps 2.2, 2.3 of GF. Go.BoSST satisfies the following properties: (a) Xa is not skinny: p M [Xx,]] > //Card(A(T.)) ()). (b) truth values of p moderately correlates with BaRN at x
PR p 2 - pule [xg]
>> Y. and finally (c) there is a minimal proportion of real data at X
TPR
The convergence proof of 19 reveals that both (a) and (b) are jointly made at any split, where our (b) is equivalent their weak hypothesis assumption where their 7 parameter is twice ours. (c)
'hhe prior is chosen by the user: without reasons to do otherwise, balanced approach suggests 0.5.
7

---

Grees Inch
Table 2: 2D density plots generated on OpenML kc1 (a and y = 7) with GF, for varying number of trees T and number of splits J (columns). the domain ground truth for comparison. Each generated dataset contains m = 2000 observations. The two variables (among d 22) were chosen because of their deterministic dependence.
all trees are stumps. The rightmost column recalls
GF >> KDEneitherKDDi >> GF
9
Table DENSITY: comparison between us and KDE (summary), counting the number of domains for which we are statistically better (left), or worse (right). The central column counts the remaining domains, for which no statistical significance ever holds.
postulates that the leaf split has empirical measure at least a fraction its uniform measure thus, of its relative volume. (c) is important to avoid splitting leaves that would essentially be useless for our tasks: leaf for which (c) is invalid would indeed locally model comparatively tiny density values. Theorem 5.2. Suppose the loss is strictly proper and differentiable. Let Go (= U) denote the initial GF with T roots in its trees (Step 1, GF. GF.BoOST) and G the final GF, assuming wlog that the number of boosting iterations J is a multiple of Under WLA K), we get the following on likelihood ratio risks: Dy (R, G,) < D2 (R, Go) xy²x² x2 -Tlog (1 + 4), for some conslant >> 0.
It comes from 25 Remark 1] that we can choose = inf 1, which is > 0 if & is strictly proper and differentiable. Striet properness is also essential for the loss to guarantee that minimization gets to good generator (Section
Experiments
Our code is provided and commented in Appendix, Section V.2 The main setting of our experiments realistic data generation (' ('LIFELIKE'), but we have also tested our method for missing data imputation ('IMPUTE') and density estimation ('DENSITY'); for this reason, we have selected broad panel of state of the art approaches to test against, relying on models as diverse as (or mixing elements of) trees, neural nets, kernels or graphical models, with MICE [42, adversarial random forests (ARFs 44). CT-GANs [47. Forest Flows [17. Vine copulas auto-encoders (VCAE, (11
using neural networks were a low-end CPU laptop - this was purposely done for our technique. Neural network- based algorithms run a bigger machine (technical specs in Appendix, Section V.2h. We carried out experiments on a total of 21 datasets, from UCI I0]. Kaggle, OpenML, the Stanford Open Policing Project, or simulated. All presented in Appendix, Section V.I. We summarize results that are presented in extenso in Appendix. Before starting, we complete the 2D heatmap of Table by another one showing our models can also learn deterministic dependences in weal-wolld domains (Table 2). The Appendix also provides an example experiment on interpreting our models for a sensitive domain (in Section V.
and Kernel density estimation (KDE, 4 34 ). All algorithms
Generation capabilities of our models: LIFELIKE The objective of the experiment is to evaluate whether a generative model able create "realistic" data. The evaluation pipeline is simple: we create for each domain 5-fold stratified experiment. Evaluation is done via four metrics: regularized optimal transport ("Sinkhorn", (8), coverage and density [30] and the Fl score [17]. All metrics are obtained after generating sample of the same size as the test fold. Sinkhorn evaluates an optimal transport distance between generated and real and F1 estimates the error of classifier (a 5-nearest neighbor) to distinguish generated vs real (smaller is better for both). Coverage and density are refinements of precision and recall for generative models (the higher, the better). Due to size constraint, we provide results on one set of parameters for "medium-sized" generative forests with 500 trees, 2 000 total splits (Table thus learning very small trees with an average 4 splits per tree. In the Appendix, we provide additional results on smaller models (T' 200, J 500)
8

---

UCI whaTonn
Opentii AnA WwATCHtAata,.c
(oe. vanishoc)
toun. veiiahlo))
0-42
3110
co9
(AAR (12C V96
brees
15
Table 4: IMPUTE: results on two domains (left and right pane). Since both domain contain categorical and numerical variables, we compute for each perr (categorical variables) and the rmse (numerical variables). In each plot, we display both the corresponding results of GF. BOOST, the results of MICE.RF (indicating the total number of trees used to impute the dataset) and the result of a fast imputation baseline using the marginals computed from the training sample. The z axis displays the number of trees I' in GF BooST and each curve is displayed with its average I standard deviation in shaded color. The result for T = 1 equivalently indicates the performance of single generative tree (GT) with J splits [3], shown with an arrow (see text).
and additional results on one metric (Sinkhorn) against contenders with various parameterizations on more domains. In Table [) contenders are parameterized as follows: ARFs learn sets of 200 trees. Since each tree has to be separately a good generative model, we end up with big models in general. CT-GANs are trained for 000 epochs. Forest Flows and VCAEs are run with otherwise default parameters. 3 contains just a subset of all our domains, furthermore not the same for each contender. This benchmark was crafted to compare against Forest Flows, best LIFELIKE contender but a method requiring to re-encode categorical variables. Since our method and ARFs process data natively, we selected only domains with numerical or binary variables (8 domains). On some of these domains, CT-GANs or VCAE crashed on some folds so we do not provide the results for the related domains. Globally, Generative Forests are very competitive against each contender, significantly beating all VCAEs on all metrics and CT-GANs on coverage and density. Tree- contender methods appear to perform substantially better than neural networks, with FFs performing better than ARFs. Ultmately,, our models compare favorably or very favorably against both FFs and ARFs, while on average being much smaller for example, each FF model can contain up to 6 750 total splits. As our experiments demonstrate (Appendix, Table|o. learning much smaller generative forests with 500 total splits can still buy an advantage in most cases, notable counterexample being density for FFs. From the memory standpoint, our code (Java) is not optimized yet managed to crunch domains of up to m x d 1.5 M while always using less than 1.5Gb memory to train our biggest models. Finally, it clearly emerges from our experiments that there is domain-dependent "ideal" size (T, J) for the best generative forests. "Guessing" the right size a prospect for future work. Missing data imputation with our models: IMPUTE We compared our method against powerful contender, MICE (42), which relies on round-robin prediction of missing values using supervised models. We optimized MICE by choosing supervised models trees (CART) and random forests (RFs, we increased the number of trees to 100 for better results). We create a 5-fold experiment; in each fold, we remove fixed % of observed values (data missing completely at random, MCAR). We then use the data with missing values as input to MICE or us to learn models which are then used to predict the missing values. We compute a per-feature discrepancy, the average error probability (perr, for categorical variables), and the root mean square error (rmse, numerical variables). We also compute one of the simplest baselines, which consists in imputing each variable from its empirical marginal. Results summary Table $ puts the spotlight on two domains. The Appendix provides many more plots. From all results, we conclude that generative forests can compete or beat MICE.RF while using hundred times less trees (eventually using just stumps, when J = T' = 20). From all our results, we also conclude that there a risk of overfitting if J and / or T are too large. This could motivate further work on pruming generative models. For GF, an unexpected pattern is that the pattern "small number of small trees works well" can work on real-woria domains as well (see also Appendix), thereby demonstrating that the nice result displayed in Table gennralisss to bigger domains.
Density estimation: DENSITY We compared GF vs kernel density estimation (KDE) experimental setting is the same as for LIFELIKE: in each of the 5-fold stratified cross validation fold, we use the training sample to learn a model (with KDE or GF. BO.BTTTT which is then used to predict the observation's 's density in the the test sample. The higher the density, the better the model. The
24 34). The
9

---

Axmoim
Sinkhorn
Covenge
Denerry
missemm
us (GF)
ARF
phol
US
(GF)
ARE
pval
Us
ARF
pval
(GF)
ARP
pual
1028500008
0.286 10007
0.2
10,010
056010008
103T
10099
0976100000
0.1
00000000000
00RN 100R7
0.5
0.355
US4S
0307=0052
0020000002
0.94 0000
000
10975
000009
0.08
10.10
"0.95 -0077
0,3000,050
00.07+00055
0043-00012
Twni
0.88
20002
0.36
122
0000400001
0120=00100
szod
1099
U.14
syh1
0100420.00
1180-0002
00.00
0 0.46610012
0.10
0099920017
20.013
"0490200007
0,500:0027
0.44
0.6
0.75
10 UAR
OTT
(156
00922
031220057
uS (GF)
CF
pval
US IGFT
CT
Pval
CT
pval
(GF)
CT
plal
ring
0:35
2004
000
(400
cize
0.7
0.74400011
*0
0.30000.002
0.00
0.1
00.075
082810053
0099520077
'0007200015
0034-00011
0.1
0322700024
100140001
"1980T0202
0.02
10030
VMh1
106410005
039410006
000
0.001000
IN (GP)
FF
pusl
FF
pval
FF
(GF)
FF
sing
002
0.28
<1Y0
10,05
0.5
0.94500.200
096610015
1000000045
0.990000077
50.51410.509
0.500:00228
2
0.21
0.0 TE00OS
Ya64
10:00
10:003
0.287
1000T
0.5
GAST 00002
052710001
0.00
0S79 T0023
1,0000.000
0.05
0,02N 10.08
015
Wreed
0090010002
20
095410001
0.51
0.61
10025
10.054
0.04
04991000
10455
097
WVLL
LUBH -0007
GURR
HOULY
097000.02
0.13
0.493
COUNT
0.7
105020007
0.81
10007
00.56
0.021
0.32
"G430
1000
140010.003
"0,96
10421
0.326 0.018
0.3050052
DN (GP)
YC-4
pual
VCAI
pval
(OFFF)
VCXI
DE (GP)
VCG
pual
ving
20 10.08
0.392 0.005
10,65 0.,10
036410000
"L03T 10099
0.1220.0013
00000
00000
0.291
10035
10000
2002
0620100000
0099520085
0.051000115
0.51410
0.805
20012
00000
0005
2and
10226
0.14
0.003
0.96
0.012
00003
0.99
0002
0,156 0.018
0004100013
10009
GOLD
20025
UNET
049
11064+0000
1.181
-00119
A
90999
0.527=00028
VC-D
VCD
V
(GP)
VCD
71ng
0011
02210.00
00000000000
0131900037
cize
+0251+0005
-0.15
0.645-00055
"0993-00R5
0M13-0011
M214
00.8010002
0.39
00002
70975 F000
H.062
"6985 HO077
00017-00055
0.064- 00.00
Tand
0005
D. 0I
00014000011
022320017
Azed
O 0036
G99 20026
0.3
w9h1
"I 1104420.03
0000000000
087620007
"O
98920011
0.80120.010
'049220037
0608=00037
us (GP)
VCR
poal
US (CIF)
VC-R
pval
VCR
puzl
US (GD)
VCR
pvll
zing
"01265H0000
0.004
000000000110
10.065
0.124H1022
0.222=0025
cizc
F0.SLL00005
0.402
-0003
"0,45 00.15
0.64
10099--00085
0.24400.006
0.006-0.022
". 00
11286-0008
0.17
022990022
kuh1
110450000
074720001
COR9ZOD1
0222000
Table 5: LIFELIKE: comparison of Generative Forests (us, GF), with T -500 trees, J =2 000 total
Adversarial Random Forests (ARF, 200 trees [44)), CT-GAN (CT, 000 epochs (47 ), Forest Flows (FF, 50 trees (17) and Vine copulas autoencoders (VCAE, VC-* where *=G for Gaussian, D for Direct and R for Regular (I).. Metrics used are regularized OT (Sinkhorn), Coverage, Density and Fl measure. Values shown = average over the 5-folds + std dev. The best average for
splits to contenders:
contender is shown with star "*". Convention for p-values: computed using Student pared t-test; if p < 0.01, value is replaced by (wwe beat the contender) or (the contender
beats us). See text for details.
GF models we consider are the same as in LIFELIKE (T = 500, J 2 000).
Results summary Table [3] right) summarizes the results (plots: Appendix, Section V.V.3.7 The leftmost column ("GF >> KDE") counts domains for which there exists an iteration j for GF after which tend to be statistically better (and never statistically worse) than KDE. The rightmost column ("KDE >> GF") counts domains for which KDE is always statistically better than GF. The last type of plots appears to be those for which there is no such statistical difference (central column). The results support the conclusion that GF can also be good models to carry out density estimation.
7 Conclusion
In this paper, we have introduced new generative models based on ensemble of trees and a top-down boosting-comp
training algorithm which casts training in a supervised 2-classes framework. Those generative forests allow not just efficient data generation: they also allow efficient missing data imputation and density estimation. Experiments have been carried out on all three problems against a variety of contenders, demonstrating the ability of small generative forests to perform well against potentially much more complex contenders. A responsible use of such models necessarily includes restriction to tabular data (Section D]. Experiments clearly show that there is a domain-dependent "best fit" size for our models; estimating it can be done via cross- cross-validation but an important question, left for future work, is how to directly "guess" the right model size. A pruning algorithm with good generalization seems like very promising direction.
10

---

Acknowledgments
The authors thank the reviewers for engaging discussions and many suggestions that helped to improve the paper's content.
References
[1] L. Breiman, J. H. Freidman, R. A. Olshen, and C. J. Stone. Classification and regression trees. Wadsworth, 1984.
[2] A. Buja, W. Stuetzle, and Y. Shen. Loss functions for binary class probability estimation ans classification: structure and applications, 2005. Technical Report, University of Pennsylvania.
[3] T. Chen and C. Guestrin. XGBoost: A scalable tree boosting system. In 22nd KDD, pages 785-794, 2016.
[4] Y.-C. Chen. A tutorial on kernel density estimation and recent advances. Biostatistics & Epidemiology, 1:161-187, 2017.
[5] Y. Choi, A. Vergari, and G. Van den Broeck. Probabilistic circuits: a unifying framework for tractable probabilistie models, 2020. pdf
[6] M. Chui, J. Manyika, M. Miremadi, N. Henke, R. Chung P. Nel, and S. Malhotra. Notes from the Al fromtier. McKinsey Global Institute, 2018.
[7] A.H..-C. Correia, R. Peharz, and C.-P. de Campos. Joints in random forests. In NeurlPS 2020.
[8] M. Cuturi. Sinkhorn distances: lightspeed computation of optimal transport. In NIPS#26, pages
2292-2300, 2013.
[9] A. Darwiche. A logical approach to factoring belief networks. In Dieter Fensel, Fausto Giunchiglia, Deborah L. McGuinness, and Mary-Anne Williams, editors, KR'02, pages 409- 420. Morgan Kaufmann, 2002.
[10] D. Dua and C. Graff. UCI machine learning repository, 2021.
[11] Dumoulin, I. Belghazi, Poole, A. Lamb, Arjovsky, Mastropietro, and A.-C. Courville. Adversarially learned inference. In ICLR' 17. OpenReview.net, 2017.
[12] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Bengio. Generative adversarial nets. In NIPS*27, pages 2672-2680, 2014.
[13] L. Grinsztajn, E. Oyallon, and G. Varoquaux. Why do tree-based models still outperform deep learning on tabular data? In NeurlPS'22 22 Datasets and Benchmarks, 2022.
[14] A. Grover and S. Ermon. Boosted generative models. In AAA''18, pages 3077-3084. AAAI Press, 2018.
[15] G.-E. Hinton. The forward-forwant algorithm: Some preliminary investigations. CoRR, abs/2212. 13345, 2022.
[16]
R.C. Holte. Very simple classification rules perform well on most commonly used datasets. MLJ, 11:63-91, 1993.
[17) A. Jolicoeur-Martineau, K. Fatras, and T. Kachman. Generating and imputing tabular data via diffusion and flow-hased gradient-boosted trees. AISTATS volume 238, pages 1288-1296.
PMLR, 2024.
[18] M.J. Kearns. Thoughts hypothesis boosting, 1988. MI. class project.
[19] M.J. Kearns and Y. Mansour, On the boosting ability of top-down decision tree learning algorithms. In Proc. of the 28 ACM STOC, pages 459-468. 1996.
[20] D.-P. Kingma and M. Welling. Auto-encoding variational bayes. In ICLR"/4 /4, 2014.
[21] D.-E. Knuth. Two notes notation. The American Mathematical Monthly, 99(5):403-425 1992.
[22] A. Krizhevsky, I. Sutskever, and G.-E. Hinton. ImageNet classification with deep convolutional neural networks. In NIPS*25, pages 1106-1114, 2012.

---

[23] S. Lang, M. Mundt, F. Ventola, R. Peharz, and K. Kersting, Elevating perceptual sample quality in pes through differentiable sampling. In NeurIPS 2021 Workshop on Pre-Reet Pre-Registration in Machine Learning, 13 December 2021, Virtual, volume 181 of Proceedings of Machine Learning Research, pages 1-25. PMLR, 2021.
[24] Q. Li and J.-S. Racine. Nonparametric estimation of distributions with categorical and continu- ous data. Journal of Multivariate Analysis, 86:266 292, 2003.
[25] Y. Mansour, R. Nock, and R.-C. Williamson. Random classification noise does not defeat all convex potential boosters irrespective of model choice. In ICML 23, 2023.
[26] Maréchal. On a functional operation generating convex functions, part 1: duality. of Optimization Theory and Applications, 36::175-18, 2005.
[27] P. Maréchal, On functional operation generating convex functions, part 2: algebraic properties.
J. of Optimization Theory and Applications, 126:375-366, 2005.
[28] D. McElfresh, S. Khandagale, J. Valverde, V. Prasad C, G. Ramakrishnan, M. Goldblum, and C. White. When do neural nets outperform boosted trees on tabular data? In NeurIPS'25 Datasets and Benchmarks, 2023.
[29] A. Menon and C.-S. Ong. Linking losses for density ratio and class-probability estimation. In 33rd ICML, pages 304-313, 2016.
[30] M.-F. Naeem, S.-J. Oh, Y. Uh, Y. Choi, and J. Yoo. Reliable fidelity and diversity metrics for generative models. In /CML'20, volume 119 of Proceedings of Machine Learning Research, pages 7176-7185. PMLR, 2020.
[31] R. Nock and M. Guillame-Bert Generative trees: Adversarial and copycat. In 39th ICML, pages 16906-16951, 2022.
[32] R. Nock, A.-K Menon, and C.-S. Ong. A scaled Bregman theorem with applications. In NIP5*29, pages 19-27, 2016.
[33] S. Nowozin, B. Cseke, and R. Tomioka. f-GAN: training generative neural samplers using variational divergence minimization. In NIPS*29, pages 271-279, 2016.
[34] R. Parzen. On estimation of a probability density function and mode. The Annals of Mathemati- cal Statistics, 13:5065-1776, 1962.
[35] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
[36] J. R. Quinlan. C4.5 programs for machine learning. Morgan Kaufmann, 1993.
[37] M.-D. Reid and R.-C Williamson. Information, divergence and risk for binary experiments. JMLR, 12:731-817, 2011.
[38] R. Sånchez-Cauce, I. París, and F.-. Diez. Sum-product networks: A survey, IEEE Trans. PAMI, 44(7):3821-3839) 2022.
[39] L.-J. Savage. Elicitation of personal probabilities and expectations. J. of the Am. Stat. Assoc., pages 783-801, 1971.
[40] M. Sugiyama and M. Kawanabe. Machine Learning in Non-Stationary Environments - Intro- duction to Covariate Shift Adaptation. Adaptive computation and machine learning. MIT Press, 2012.
[41] N. Tagasovska, D. Ackerer, and T. Vatter. Copulas as high-dimensional generative models: Vine copula autocncoders. In NeurlPS#32, pages 6525 6537, 2019.
[42] S. van Buuren and K. Stoothuis-Oudshoone Equations in R. Journal of Statistical Software, 45(3):1667, 2011.
mice: Multivariate Imputation by Chained
[43] A. Vergari, Y. Choi, and R. Peharz. Probabilistic circuits: Representations, inference, learning and applications, 2022. NeurlPS'22 22 tutorials.
[44] D.-S. Watson, K. Blesch, J. Kapar, and M.-N. Wright. Adversarial random forests for density and generative modeling. In A/STATS'23, 23, Proceedings of Machine Learning Research. PMLR, 2023.
12

---

[45] I. Witten and E. Frank. Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations. Morgan Kaufmann, 1999.
[46] C. Xiao, P. Zhong, and C. Zheng. BourGAN: Generative networks with metric embeddings. In NeurlPS' 18, pages 2275-2286, 2018.
[47] L. Xu, M. Skoularidou, A. Cuesta- and K. Veeramachaneni. Modeling tabular data using conditional GAN. In NeurlPS*32, pages 7333-7343, 2019.
13

---

Appendix
To differentiate with the numberings in the main file, the numbering of Theorems, etc. is letter-based (A, B...
Table of contents
Related work
Additional content
Pg 16
Supplementary material on proof'
Pg
Proof of Lemma 4.4
Pg
Proof of Theorem
Pg
Simpler models: ensembles of generative frees
Supplementary material experiments
Pg
Domains
Pg
Algorithms configuration and choice of parameters
Pg 25
Interpreting our models: 'SCRUTINIZE"
Pg 27
More examples of Table T (MF)
Pg
28
The generative forest of Table I (MF) developed further
Pg
30
Full comparisons with MICE on missing data imputation
Pg
35
+
Experiment LIFELIKE in extenso
Pg
Comparison with "the optimal generator": GEN-DISCRIM
14

---

I
Related work
The typical Machine Learning (ML) problem usually contains at least three parts: (i) training algorithm minimizes (ii) loss function to output an object whose key part is (iii) a model. The main problem we are interested in is data generation as generally captured by "Generative Al". The type of data we are interested in still represents one of the most prevalent form of data: tabular data [6]. When it comes to tabular data, singular phenomenon of the data world can be observed: there is a fierce competition on part (iii) above, the models. When data has other forms, like images, the ML community has generally converged to broad idea of what the best models look like at a high-level for many generic tasks: neural networks Tabular data offers no such consensus yet, even on well-defined tasks like supervised learning [13] In fact, even on such "simple tasks" the consensus is rather that there is no such consensus (28). It is an understatement to state that in the broader context of all tasks of interest to us, a sense of truly intense competition emerges, whose "gradient" clearly points towards simultaneously the most complex / expressive / tractable models, as shown in [43] Slides 27, 53). One can thus end up finding models based on trees
44 neural graphical models
networks 12 14 20 47. probabilistic circuits [5 43 38) kernel methods 4. 34
(among others: note that some are in fact hybrid models).
So the tabular data world is blessed with a variety of possible models to solve problems like the ones we are interested in, but and this is another singular phenomenon of the tabular data world -, getting the best solutions is not necessarily a matter of competing on size or compute. In fact, it can be the opposite: striving for model simplicity or (non exclusive) lightweight tuning can substantially pay off [28). In relative terms, this phenomenon is not new in the tabular data world: it has been known for more than two decades [16). That it has endured all major revolutions in ML points the fact that lasting solutions can be conveniently addressing all three parts (i-iii) above at once on models, algorithms and losses.
From this standpoint, the closest approaches to ours are and 31,, first and foremost because the models include trees with stochastic activation of edges to pick leaves, and leaf-dependent data generation process. While 31 learn a single tree, 44 use a way to generate data from set of trees- called adversarial random forest which is simple: sample tree, and then sample observation from the tree. Hence, the distribution is a convex combination of the trees' density. This is simple but it suffers several drawbacks: (i) each tree has be accurate enough and thus big enough to model "tricky" data for tree-based models (tricky can be low-dimensional, see the 2D data of Table main file); (ii) if leaves' samplers are simple, which is the case for [31 and our approach, it makes tricky to learn sets of simple models, such as when trees are stumps (we do not have this issue, see Table [] In our case, while our models include sets of trees, generating one observation makes use of leaves in all trees instead of just one as in 44] (Figure T main file). We note that the primary goal of that latter work is in fact not to generate data 44 Section 4].
Theoretical results that are relevant to data generation are in general scarce compared to the flurry of existing methods if we omit the independent convergence rates of the toolbox often used, such for (stochastic) gradient descent. Specific convergence results are given in [44]. but they are relevant to statistical consistency (infinite sample) and they also rely on assumptions that are not realistic for real world domains, such as Lipschitz continuity of the target density, with second derivative continuous, square integrable and monotonic. The assumption made on models, that splitting probabilities on trees is lowerbounded by a constant, is also impeding to model real world data.
In the generative trees of (3I, leaf generation is the simplest possible: it is uniform. This requires big trees to model weal-world or tricky data. On the algorithms side, [31 introduce two training algorithms in the generative adversarial networks (GAN) framework [12. thus involving the generator to train but also a discriminator, which is a decision tree in [31]. The GAN framework is very convenient to tackle (ii) above in the context of our tasks because it allows to tie using first principles the problem of learning a density or a sampler and that of training a model (a "discriminator") to distinguish fakes from real, model that parameterizes the loss optimized. An issue with neural networks is that this parameterization has an uncontrollable slack unless the discriminator is extremely complex [33]. The advantage of using trees as in (31 that for such classifiers, the slack disappears because the models are calibrated, so there is tight link between training the generator and the discriminator. 3I go
Whethee such perception is caused by the models themselves or the dazzling amount of optimisation that has progressively wrapped the models, as advocated for the loss in (23), is not the focus of our paper.
15

---

Algorithm 4 LIEERTIVESUPPORRUUUTTTTYEE
Input: Trees (T,) of GF; GF;
Output: sampling support e, for one observation;
Step 1 C, < X;:
Step 2 (NIT((Te)1_1))
Step 3 for / E [7]
Step 2.1 while done
Step 2.1.1 STARUPDATE(T C., R);
return C,;
Algorithm 5 CONCURREXISSPPORRTUDDTE
Step 1 while !done
Step 1.1 Placcessible) // locks C,
Step 1.2 STARUPDATE(thiss.C R);
Step 1.3: V[accessiblej // unlocks C,
further, showing that one can replace the adversarial training by a copyear training, involving copying parts of the discriminator in the generator to speed-up training (also discussed in [15] for neural nets), with strong rates on training in the original boosting model. There is however limitation in the convergence analysis of [31] as losses have to be symmetric, property which is not desirable for data generation since it ties the misclassification costs of real and fakes with no argument to do so in general.
Our paper lifts the whole setting of [11 models that can fit more complex densities using simpler models (Table using sets of trees that can be much smaller than those of [44] (Figure [ training such models achieved by merging the two steps of copycat training into single one where only the generator is trained, furthermore keeping strong rates on training via the original boosting model, all this while getting rid of the undesirable symmetry assumption [31 for the loss at hand.
II Additional content
In this additional content, we provide the three ways to pick the trees in a Generative Forest to generate one observation (sequential, concurrent, randomized), and then give proof that the optimal splitting threshold on a continuous variable when training generative forest using GF. BoOST is always an observed value if there is tree, but can be another value if there more (thus highlighting some technical difficulties of one wants to stick to the optimal choice of splitting).
II.1
Sequentially choosing trees in a GF for the generation of observations
I1.2 Concurrent generation of observations
We provide concurrent generation using Algorithm which differs from Algorithm (main file). In concurrent generation, each tree runs concurrently algorithm UPDATESUPPORT (hence the use of the Java-style this handler), with additional global variables (in addition to C,, initialized to X): a Boolean semaphore accessible implementing a lock, whose value means C is available for an update (and otherwise it is locked by tree in Steps 1.2/1.3 in the set of trees of the GF). We assume that INIT has been run beforehand (eventually locally).
II.3 Randomized generation of observations
We provide general randomized choice of the sequence of trees for generation, in Algorithm 6
16

---

Algorithm 6 RANDOMMZZDSUUPORTUPPNNE
Step : (NIT(( (1,,
(1,2, 7): Step 2 while (0)=
Step 2.1
(A)DDM
Step 2.2 STARUPDATE(TT,C, R);
Step 2.3 if (Tnne)))) then R(::
Supplementary material on proofs
III.1 Proof of Lemma 4.4
Given sequence e of dimension dim(v), v), denote [dd the sequence of subsets of the domain appearing in the parameters of UPDATESUPPORT through sequence v, which we add last element, C, (and its first element is X). If we let X, denote the support of the corresponding star node whose Bernoulli event triggered at index j in sequence (for example, X1 X), then easily get
Xg, Vj [dim(v)],
(5)
indicating the Bernoulli probability in Step 1.1 of STARUPDATE is always defined. We then compute
PG [C,/v] = pa(n,e,)
(6)
N
= II
PG [C,+//e]]
(7)
5-1
PR. [C++
(8)
PR (e
PR [C
(9)
PR Col
Pn. [C.]
PR [X]
= PR [e.].
(10)
holds because updating the support generation is Markovian in GF, (8) holds because of Step
3.2 and is a simplification through cancelling terms in products.
111.2 Proof of Theorem 5.2
we iteratively learn generators Go, G1, ..., G. where Go is just root. We let PP(G)) denote the partition induced by the set of trees of G,, recalling that each element is the (non-empty) intersection of the support of set of leaves, one for each tree (for example, P(Go) (X)). The criterion minimized to build Gj+1 from G, is
Notations:
L(G₁)
Σ CcP(G,)
PM el
L
TPR
(11)
p P px
The proof entails fundamental notions loss functions, models and boosting. We start with loss functions. A key function we use is
nt nt
g" (')()) (TT 1)
Vt E IR+,
which is concave 37 Appendix A.3].
Lemma A.
D₁ (R, DD
L(G)-))-((Gj)
(12)
Proof. We make use of the following important fact about GFs:
17

---

(FI) For any X' E Py, fx dG, = Sxx dR.
We have from the proof of [31 Lemma 5.6].
dGG,
1)
dR du
De GR,
Σ
g"
Bujx
Bujx
g"
(13)
dU
YeP,
We note that (F1) implies
13
is just sum of slacks of Jensen's inequality. We observe
De (R, GJ-1)
D2 (R, Gy)
dG
1)
dR
Σ
9"
Eupx
Eupx
g"
du
du
x
[dGJ du ) Eupx
(dR
- Σ
9"'
Eupoo
au
Σ
g" (Buxx
ddGJ-1
1)
Σ
g"
[upx
dGJ dt
dU
(Ne (X Jecr
ve(t,f)
where Pyth contains all couples (Ge) such that X,, X, Py and X, u X4 E P--1- These unions were subsets of the partition of X induced by the set trees G and that were cut by predicate P put at the leaf X that created G, from GJ-1- To save space, denote Xx X, u Xx
(G)-1) du
dGJ
))
9"
E
Σ g" vE(t,f)
Eujx,
dU
π SJ,r dGj-1
dG,-1 -(1-T)
du
π
π TI dG + (1 - T)) Ject du
Net
Nist
dG, + +(1 (1- [ dU
"7 Sxn dG,
She dG, + (1 - π Ixx dU
(T] 3x
dG, (1 - T)
[ dU)
π Sag dG,
(14)
Soc dG, + (1 - π) Jxz dl
We now work on (14). Using (F1), we note Saie dG = Sy. dR since Xyx Py-1. Similarly, Sx, dG,, = Sxx dR, Vv E (t, f), so we make appear R in 14 and get:
dGJ-1
)
dGJ
g" Eujerrr
Σ 9"
Bujjr
du
dU
vE(t,f)
Soar dR
p(t)
T Szc dR.
p(f) p(tf)
Sze dR p(f)
} (15)
-(tff)
L
L
L
p(tf)
p(tf)
p(t)
where we let for short
dR + (1 T)) {
p(v)
du, tf)
(16)
xx
We finally get
De (R, GJ-1) - BD (R,
Σ PMlel [P]
PMlCpp_iil
TPR
TpRlC SpRlCpp-iiv]
Σ
PM
Σ
[M
PM[e]
PMMc (p--j.
C-PJ-1
CEP
vE(t.5)
= - -
as claimed. The last identity comes from the fact that the contribution to L(.) the same outside P,-1 for both G and Gj.
D
18

---

Algorithm 7 &
Input: measure R, SPD loss L, weak learner WL, iteration number J > 1, number of trees T; Output: PLM (partition-lineat model) H, with T trees;
Step 1: To = {T,)/_1
(root, root, ro, P(To) {X]:
Step : for j = 1,2.....
Step 2.1 pick e [T]:
Step 2.2 : pick A A())::
Step 2.3 h2 WL(()x;
I/ call to the weak learner for some hy of the type h2 = lp() K
I/ K2 constant, p(.) a splitting predicate (e.g. æ; 2 a)
Step 2.4 : for é (T j-1).
@ - en fo: p(x) is true),
(17)
TPR | CP P PM CP]
a((P)
= (-L')
(18)
e - e n far p(x) false),
(19)
TPR P PM [-pp]
P(C ((-L')
(20)
Step 2.5 update P(TT)::
P(T,) - (PTT)=))PA(T)-I) ( (VeeP.(T-)))eee u (VVP:))))CCC( (V
Step 2.6 split leaf À at Y, using predicate p; return H)((x) a (C(x)) with C(x)) e p(T)) such that a E e;
We now come to models and boosting. Suppose we have trees (T,, T..... T,} in Gj- We want to split leaf À T, into two new leaves, Xe, dt. Let PP(GP (G,) denote the subset of P(GG) containing only the subsets defined by intersection with the support of X, Xx, The criterion we minimize can be reformulated as
L(G,)
PMA
Σ
PM
TPn C
. (T,, T2.... Iz).
PM [CJ]
PM
ΛEA(T)
CEPA(G,)
Here, Y is any tree in the set of trees, since P covers the complete partition of X If we had a single tree, the inner sum would disappear since we would
induced by {Y,, T....., T,). Y,, have PA (G,) = {Xx} and one iteration would split one of these subsets. In case however, with a set of trees, we still split X2 but the impact on the reduction of can be substantially better we may simultaneously split many subsets as there in Px (G,).. The reduction in IL can be obtained by summing all reductions to which contribute each of the subsets.
To analyze it, we make use of reduction to the MODABoOST algorithm of 255 We present the algorithm in Algorithm 7 The original MODABOOST algorithm trains partition-linet models, i.e. models whose output is defined by sum of reals over of partitions to which the observation be classified belongs to. Training means then both learning the organisation which are just the output of a weak classifier given by weak learner, times a leveraging constant com- puted by MODA BOOST. As the classical boosting literature, the original MODABOOST includes the computation and updates of weights.
partitions and the reals
In our case, the structure of partition learned is that of set of trees, each weak classifier h is of form
h(w) K p(x),
where K is real and p is Boolean predicate, usually doing axis aiis-prrallel split of X on an observed feature, such as p(x) (x) = 1g.20-
From now on, it will be interesting to dissociate our generator G,- which includes model structure and an algorithm to generate data from this structure- from set trees -Le. its model structure which we denote I = (Tr) MODABOOST learns both 1 but also predictions for each possible
19

---

Xx
X
r = 1 12}
Card(Px(T)) =3
Figure III.1: Learning a set two trees I' with MODA BOOST. If we want a split at leaf indicated, then it would takes two steps (but single application of the weak learning assumption, [25 Lemma 5) of the original MODABoOST to learn Y2 alone [25] Section 4]. Each step, figured with a plain arrow, ends with adding new leaf. In our case however, have take into account the partition induced by the leaves of Tg. which results in considering not one but three subsets in PA, thus adding not one but three weak hypotheses simultancously (one for each of the dashed arrows on T2). Thanks to Jensen's 's inequality, guaranteed decrease the loss at hand can be obtained by a single application of the weak learning assumption X, just like in the original MODABOOST.
outcome, predictions that we shall not since the loss only on the model structure J. Given the simplicity of the weak classifiers h and the particular nature of the partitions learned, the original MODA BoOST of (25) be simplified to presentation in Algorithm!] 7 Among others, the simplification discards the weights from the presentation of the algorithm. What show entangles two objectives models and loss functions as show that
minimizing can be made to depend
MODABoOST learns the same structure I as GF.BoOST, and yields guaranteed decrease of L(G),
and it achieved via the following Theorem. Theorem B. MODABOOST greedily minimizes the following loss function:
L(T,)
Σ PM AeA(T)
Σ
PM
L
<PR C
Y e .T,.
PM
CEPA(T.)
Furthermore, suppose there exists y > 0, K. such that at each iteration j, the predicate p splits Xx of leaf X E A(T) into X3, and x,, (same nomenclature as in (19) such that:
[M]]
(22)
Card(A(T))
San dR
Siz dU
Sxx, dR
Jox, dU
Y,
(23)
TPR [
[PR[[XA]
min
P PM [Xx]]
P [a]
K.
(24)
Then have the following guaranteed slack between two successive models:
xy2k2
L(T L(T,) & 8Card(A(T))'
(25)
where & is such that 0 < x & inf(f[ )1) (.
Proof sketch The loss function comes directly from 22 Lemma 7]. At each iteration, MODABOOST makes number of updates that guarantee. once Step 2.4 is completed (because
20

---

the elements in PT) are disjoint)
L(T (+1) L(T,)
Σ (EPA(T,)
PMle]
MIe [[ wy)
(26)
2
K [ MJX [ wy)
(27)
2
where the weights are given in 22 Each expression in the summand of (26) is exactly the guarantee of [25] ineq. before (69)]; all such expressions are not important; what more important is (2)): all
single step of MODABooST carried out over the whole Xy. Overall, the number of "aggregated" steps match the counter in MODABOOST. We then just have reuse the proof of [25] Theorem BJ, which implies, in lieu of their 22 eq. (74)
steps occurring in Step 2.4 equivalent
S2z dR
Jaz dU
TPR X
L(T <
-2x PMM-PN())
(28)
Jxx dR
lx, du
p M [Cx]
with L (u) = u(1 - u). Noting 2L (v) e min(u, u, u). we then use the statement of the Theorem.
22
24
which yields
As consequence. if assume that the total number of boosting iterations J is multiple of the number of trees T, it comes from 25 eq. (29)] that after J iterations, we have
2² Tlog 1+ (1+T)
J - T))
L(T))
L(To)
(29)
8
Using Lemma A and the fact that the induction of the sets of trees in MODABOOST is done in the same way as the induction of the set of trees of our generator G in GF. GF.BoOST, we get:
De (R, GJ)
De (R, Go) + (L(G,) L(Go)) " (R, Go) + (L(T,) L(To))
T T. Dr. Go) xy²k2 -Tlog 1 T
as claimed.
Remark One may wonder what is the relationship between the loss that we minimize and "conventional" losses used to train generative models. The advantage of our Theorem 5.2) is that by choosing different proper losses, one can get convergence guarantees for different "conventional" losses. Let illustrate this with the KL divergence between measures A and B, noted (L(A)B).
Lemma D. Suppose the prior satisfies π. > 0 and R absolutely continuous with respect to G. Then for the choice = gmms log-loss, we get
Dyto (R, G) = π. KL (R|G) KL (TdR + (1 x)dU/ + x)d)).
(30)
Proof. We first recall that for any convex F, have with choice of g (assuming 0),
F(2) πZ 1
(31)
π
N2 + 1 - 7
- π
F((z) F
(32)
TE + 1 π
π
TE +
The log-loss has (1) = log u, (w) = -loo - u). It strictly proper and so it comes
1-
1-
( (z) log
log
nे + n
T2 +
We thus get, in our case
dR
dR
7dR
1
+)dU
L
du
=
du
log
ddR + - R)JU
+
π
log
#dR + (1 - π d
(33)
21

---

(0.1, (A93, A94, A9S))
[AB1,
Number existing ng credits
(0.4, (0, 3, 4))
(0.6. 15, 7,
Personal stanus
(0.7. A95))
(A94)
Figure IV.1: A generative tree (GT) associated to UCI German Credit.
and using (32 and the fact that for the log-loss (-L)(u) log(u//(1 u)).
(-L)
dG
Td
log
Td
au
TG + x)JU
TdG (1 7)dU
(1 T)dU
(1 (1-11) --
log
ddG (1 x)
TdG + (1 - (1-r)dt
(1 (1- r)dU
rdG
tdG
loo
(1-r)dU) log
TdG (1 x)dU (34)
rdG (1 =)
Finally, we get, assuming R absolutely continuous with respect to G, Dytoo (R, G)
dR du
dG
dR dG (
(GG
π
du.
x
du
dU
du
rdR log
T)UU log
(1-#)dU
ndR
-TdG-
mdG
TdUU log
(1-r)dU
(35)
(100-(1xxdl
TdG++1-njo
Jx
-dRR log
7dG
+ TdG log
mdG
#dG+ +jd
md
rdR log (48)
(TdR + (1 (1-x)du dU) log (TdR + (1 x)d
(36)
+ (rdR + (1-x)dU)) log (TdG + (1 - rddU)
π KL GR| - KI. (rdR + (1 x dU rd + (1 - d))
(37)
as claimed (end of the proof of Lemma D
Because of the joint convexity of KL divergence, we always have
KL (Ldd + (1 T)GU + (1 - --)dU) & TKL (R|G) + (1 K) (dUlldU)
TKI. (R|G)
which yields (another proof) that our loss, Dawe (R, G). is lowerbounded by 0. In general, if let 7 O such that KI. (TdR (1- ---UUdUUd Td + ddU) & (1 (1-7)- mKL (RJlG) (The strict positivity of v is also a weak assumption as long as R. G sufficiently differ from the uniform distribution), then
Dyao (R, G)
KL.GG)
(38)
so any upperbound on DAoo (R, G) (such as obtained from Theorem 5.2) translates to an upperbound on the KL divergence. Note that the condition for absolute continuity Lemma is always met with the models we learn (both generative forests and ensembles of generative trees).
IV Simpler models: ensembles of generative trees
Storing GF requires keeping information about the empirical measure R to compute the branching probability in Step of STARUPDATE. This does not require to store the full training sample, but requires at least an index table recording the (leaves) (observations) association, for a storage cost in between ((m) and O(mT) where is the size of the training sample. There is a simple way to get rid of this constraint and approximate the GF by set of generative trees (GTs) of [31].
22

---

Models Simply put, a GT is simplified equivalent representation of a generative forest with 1 tree only. In this case, the branching probabilities in Step 1 of STARUPDATE depend only on the tree's star node position. Thus, instead of recomputing them from scratch each time an observation needs to be generated, we compute them beforehand and use them to label the arcs addition to the features' domains, as shown in Figure [V. This representation is equivalent to that of generative trees [31]. If we have several trees, we do this process independently for each tree and end up with an ensemble of generative frees (EOGT). The additional memory footprint for storing probabilities (O(2, IA(T,))) is offset by the fact that we do not have anymore to store associations between leaves and observations for generative forests, for potentially significant reduction is storing size. However, we cannot use anymore STARUPDATE as is for data generation since we cannot compute exactly the probabilities in Step 1. Two questions need to be addressed: is it possible to use ensemble of generative trees to generate data with good approximation guarantees (and if so, how) and of course how do we train such models.
Data generation We propose a simple solution based on how well an EOGT can approximate a generative forest. It relies on a simple assumption about R and X. Taking as references the parameters in STARUPDATE, we now make two simplifications on notations, first replacing Y. by " (tree implicit), and then using notation C, = Xgr e e for any v {t, f), the reference to the tree star node being implicit. The assumption is as follows.
Assumption A. There exists e (0, o0) such that any Step I of STARUPDATE, for any ue {t, f).
we have
Pn. ee [G,]]
E (xxp(==))exp((x]]
(39)
Pu [.,]
A simple condition to ensure the existence of x is a requirement weaker than (c) in Definition 5.1 all Steps 1 of STARUPDATE, PR [e, (0, 1), which also guarantees pa [e (0.1) and thus postulates that the branching in Step 1 of STARUPDATE never reduces to one choice only. The next Lemma shows that is indeed possible to combine the generation of an ensemble of generative trees with good approximation properties, and provides simple algorithm to do so, which reduces to running STAR UPDATE with a specific approximation to branching probabilities in Step For any GF G and e E P(G), deptha (C) is the sum of depths of the leaves in each tree whose support intersection is e. We need the definition of the expected depth of G.
Definition B. The expected depth of GF G is (Gpth(G) = Eeer(G) Pa [e] (C).
depth( (G) represents the expected complexity to sample an observation (see also Lemma
Lemma C. In Step I of STARUPDATF, suppose pn [C. ele] is replaced by
PU [x;] Pu"
Pu-
(40)
Pu [ee|Xu Pu- + pc
Cy|2,;; (1 Pv-)
with p = PR [3n [X,z] the probability labeling are (v*, ve) in its generative tree. Under Assump-
tion A we denote G the initial GF and G the EOGT.P using (40). the following bound holds on the KL divergence between G and G:
(I((G] & 2x ddeph((G), where depth(G) is given in Definition B
(41)
Proof. Because C = Nr... - at any call of STARUPDATE, have
pR [Kx. n ele]
PR [Ce [e]
pR [e.]
= PR [R[ [c.]]] + PR [e,]
(42)
exp exp(x)p1 (x)pu
[er [Kr..g]]]] PR [Kr..]]
(43)
(sp(-xx)pe -
[e,|Xr : PR [xr + exp( - x)pu (r PR [r.
Pu Ce [x [ PR [T.. [Xr...]
exp(2xx
(44)
Pu e. (r PR [G [xr..' + Pu Cr PR
23

---

Pr...PPR. and then using 39 is obtained by dividing numerator and denominator by pR [rr.u +
43 is due to the fact that, since e 'r PR [C,] = PR [ n Xr.,; PR [e,|2Gr.e) Pa [
PR [rr.wel PR [TT.
and satisfy P(G) = P(G) so
f
dG dG
KLGGI(G = dG log
(45)
PG Pg pa
pale] log
(46)
CcP(G)
Finally, pa[C] and Pale] are just the product of the branching probabilities in any admissible sequence. If we use the same admissible sequence in both generators, we can write pa - - Pj
and P3[e] = ((()) p.. and (44) directly yields Py & exp(2xx py Vj E [n(e)], n being a shorthand for depth = depth (see main file). So, for any e P(G),
Pale] Pale]
exp(2x - deptha
(47)
and finally, replacing back ne) by notation depth(C),
2x Σ
palc] depth(e)
CEP(G)
2x (e)
(48)
as claimed.
Note the additional leverage for training and generation that stems from Assumption not just in terms of space: computing Pu [e,[ is (d) and does not necessitate data so the computation of key conditional probabilities (40) drops from (2() to (d)) for training and generation an BOGT.
Lemma C provides the change in STARUPDATE to generate data.
Training To train an EOGT, we cannot rely on the idea that we can just train a GF and then replace each of its trees by generative trees. To take concrete example of how this can be a bad idea in the context of missing data imputation, we have observed empirically that a generative forest (GF) can have many trees whose node's observation variables the same within the tree. Taken independently of the forest, such trees would only model marginals, but in a GF, sampling dependent on the other trees and Lemma 4.4 guarantees the global accuracy of the forest. However, if we then replace the GF by an EOGT with the same trees and use them for missing data imputation, this results in imputation the mode of the marginal(s) (exclusively). which clearly suboptimal. To avoid this, we have to use a specific training for an EOGT, and to do this, it is enough to change key part of training splitPred, the computation of probabilities PR.-J used in (4). Suppose x very small in Assumption A To evaluate a split at some leaf, we observe (suppose we have single tree)
[Xx]] PR [2 PR [Xx [XA] PR [x Pu [
(and the same holds for X₂). Extending this to multiple trees and any e P(T), we get the computation
of any pr. [e.] and pR[Ce, [C+] needed to measure the new (4) for potential split. Crucially, it does
necessitate to split the empirical measure at C but just relies on computing PC [C, [C], (f, t): with
the product measure and since make axis-parallel splits, it can be done in O(1), thus substantially
reducing training time.
More with ensembles of generative trees we can follow the exact same algorithmic steps as for generative trees to perform missing data imputation and density estimation, but use branching probabilities in the trees to decide branching, instead relying on the empirical measure tuples of nodes, which we do not have access to anymore. For this, we rely on the approximation (40) in Lemma C. key difference with GF is that no tuple can have zero density because branching probabilities are in (0, 1) in each generative tree.
24

---

Domain
Tag Source
Missing data ?
m
# Cat.
# Num.
iris
UCI
No
150
4
riingGaus
ring
No
1 1600
circGauus
circ
No
2 200
2
"gridGauss
grid for
No
2 500
forestfires
OpenML
No
517
13
2
11
"randGauss
rand
No
3 800
tictactoe
tic
UCI
No
958
ionosphere
iono
UCI
No
351
34
2
32
student
wttpeettt_proommaceeeeeoo mat
UCI
No
396
33
16
winered
wred
UCI
No
1 1,99
12
12
sruddent_performance
stp
UCI
No
650
33
16
analcatdata_supp supreme
ana
OpenML
No
4 053
I
7
abalone kcl
aba
UCI
No
4 177
OpenML
No
2110
22
21
winewhite wwhi UCI
No
4 4
12
12
sigma-cabs
Kaggle
Yes
5 000
13
5
8
compas
comp OpenML
No
278
14
9
artificial,charactten
arti OpenMI.
No
10218
8
jungle_
jung OpenMI.
No
44
1
open-pol
SOP
Yes
18419
20
16
4
electricity
elec
OpenML
No
452
2
Table Al: Public domains considered our experiments (m = total number of examples, num- ber of features), ordered in increasing x d. "Cat." is shorthand for categorical (nominal / ordinal binary); "Num." stands for numerical (integers reals). (*) = simulated, URL for OpenML: attps://wwz openml org/ Stanford Open Policing project, https: /ttpppss///pmnoicciing stanford edu/ (see text). "Tag"
SOP
refers to tag names used in Tables A7 and A8
V Appendix on experiments
V.1 Domains
ringGauss is the seminal 2D ring Gaussians appearing in numerous GAN papers [46]; those are eight (8) spherical Gaussians with equal covariance, sampling size and centers located on regularly spaced (2-2 angular distance) and at equal distance from the origin. gridGauss was generated as decently hard task from [[ consists 25 2D mixture spherical Gaussians with equal variance and sampled sizes, put on regular grid. circGauss is Gaussian mode surrounded by a circle, substantially harder version of ringGauss with mixture components, in which covariance, sampling sizes and distances sightlines from the origin are all random, which creates very substantial discrepancies between modes.
from [46]. randGauss
V.2 Algorithms configuration and choice of parameters
CF.BoOST We have implemented GF. BooST in Java, following Algorithm 3 blueprint. Our implementation of tree and leaf Steps 2.1, 2.2 is simple: we pick the heaviest leaf among all (with respect to R). The search for the best split exhaustive unless the variable categorical with more than a fixed number of distinct modalities (22 in our experiments), above that threshold, we pick the best split among random subset. We follow (3I's experimental setting: in particular, the input of our algorithm to train generator is a .cSv file containing the training data without any further information. Each feature's 's domain is learned from the training data only; while this could surely and trivially be replaced by a user-informed domain for improved results (e.g. indicating a proportion's s domain as [0%, 100%]. informing the complete list of pecio-professional categories, etc.) and in fact standard in some MI. packages like weka's 's ARFF files, we did not pick this option to alleviate all side information available the GT learner. Our software automatically recognizes three types of variables: nominal, integer and floating point represented.
25

---

Comments on implementation For the interested reader, we give here some specific implementation details regarding choices mades for two classical bottlenecks on tree-based methods (this also applies to the supervised case of learning decision trees): handling features with large number of modalities and handling continuous features.
We first comment the case where the number of modalities of a feature large. The details can be found in the code in File Algorithm.jaryy (class Algorithm) as follows:
method public GemerativeModed hatrraiiieeeeellaaee@nheeeeembb Treee learn_geot () imple- ments both GF.Boost (for generative forests) and its extension training ensembles of generative trees (Appendix) as a single algorithm.
method Node choose _oooselleafiee (String how_to_choose__e_e choose_leate is the method to choose Ieaf (Step 2.2). Since it picks the heaviest leaf among all trees, it also implements Step 2.1 (we initialize all trees to their roots; having tree root for generation does not affect generation).
method
forest (Node leaf, HashSet tol) finds the split for a Generative Forest, given a node chosen for the split. Here is how it works:
public boolean split-generativ _orreetive_forest
<Measur wwwpeeeeopppoppplloootoo...
1. It first computes the complete description of possible splits (not their quality yet), using method public static featurrfett ALL_FEATURE_TESSS (Feature f, Dataset ds) in Feature. java. The method is documented: for continuous features, the list of splits is just a list of evenly spaced splits.
2. then it calls public SplitDetails split_top_dde
(Node
leaf, boolean [ splittable__eaturree HashSet
FeatureTest 00
all feature_testee
tol), which returns the best split as follows: (i) shuffles the potential list of splits and then (ii) picks the best Algorithm thm. MAXIMAL_NUMBERR NUMBNNMBBRROO SOECERRFF_SPLLL_ TESTS_ SETT_EETTS__RR_S TRIES_RREEEEE BBt__EER_______SS BOOSTING, ITERATION elements (if the list is smaller, the search for the best is exhaustive); this class variable is currently = 1000.
in the sublist containing the first
Last, we comment how we handle continuous variables: the boosting theory tells us that finding a moderately good split (condition (b) Definition main file) is enough to get boosting-compliant convergence (Theorem [5.2] main file), so we have settled for a trivial and efficient mechanism: cut-points are evenly spaced and the number fixed beforehand. See method public static Vector<FeatureeTes ALL_ FEATURE_TESTE (Feature f, Dataset ds) in Feature java for the details. turns that this works very well and shows our theory indeed concretely used in the design/impleeennttiin of the training algorithm.
MICE We have used the R MICE package V 3.13.0 with two choices of methods for the round robin (column-wise wise) prediction of missing values: CART [ and random forests (RF) [42]. In that last case, have replaced the default number of trees (10) by larger number (100) to get better results. We use the default number round-robin itcrations (5). We observed that random forests got the best results so, in order not multiply the experiments reported and perhaps blur the comparisons with our method, we report only MICE'S 's results for random forests.
TENSORFL.Ow
To learn the additional Random Forests involved in experiments we used Tensorflow Decision Forests library We use 300 trees with max depth 16. Attribute sampling: sqrt(number attributes) for classification problems, number attributes 3 for regression problems (Breiman rule thumb); the min #examples per leaf 5.
CT-GAN We used the Python implementation[ with default values 47
https::/github.ccm
learners.
26

---

(sane 40.0 depth 8 Suodes 17)
juv count
[NC:root] internal (5278) (jwe_fel commtel_coomt <- 9-41
[-[a1] isternal (5087) lage.cns_rraatrtthee is (age
(10-10)
(0)
internal
[-(35) internal (3780) Aacce_Atricankseere
49)
[-[47] 1eaf (1521)
Arccannciaanmmeriiaa
[48) incernal. (9439) (age <- 19
#10)
[- [es] leat (15)
false
true
1- [+10] intermal (2026) (age < 29 al1 v12)
[e11] internal (2347) (age <e 34.7 #10)
I- [A18] internal (2004) (sso_year_rwcid (006)
415
rea_yeer_recid
(1138)
[d10]] leat (322)
false
true
1- [+122] leaf (79)
[a6] leat (294)
44%
~ 56%
[ad] leat (1083)
[+2] leat (191)
Table A2: SCRUTINIZE: Tree in example of Generative Forest on sensitive domain compas, with 17 nodes and part its graph sketched following F convention, modeling a bias learned from data. Ensemble of such small trees can be very accurate: on missing data imputation, they compete with or beat MICE comparatively using 7 000 trees for imputation (see text for details).
Ad Adversarial Random Forests We used the R code of the generator FORGE made available from the paper [44] learning forests containing variable number of trees in {10, 50, 100, 200). We noted that the code does not run when the dataset has missing values and we also got an error when trying to run the code on kc1.
Vine Copulas AutoEncoders We used the Python code available from the paper 41 which processes only fully numerical datasets. We got few errors when trying run the code on compas.
Forest Flows We used the R code available from the paper 17 Hyperparameters used were
default parameters
Kernel Density Estimation We used the code available in the package npudens with default values following the approach of [24]. We tried several kernels but ended up with sticking to the default choices, that seemed to provide overall some of the best results. Compared to us with GF, KDE's code is extremely compute-intensive as domains below tictactoe in Table Al] it took orders of magnitude more than ours to get the density values on all folds, so we did not run it on the biggest domains. Notice that in our case, computation time includes not just training the generative model, but also, at each applicable iteration J in GF. BOOST, the computation of the same number of density values for KDE.
Computers used Quad-Cor Core Intel Core i5 processor, and part on a desktop Intel(R) Xeon(R) 70GZHZ with 12 cores and 64 Gb RAM. CT-GANs and VCAEs were run the desktop, the other algorithms on the laptop.
We ran part of the experiments on Mac Book Pro 16 Gb RAM w/ 2 GHz
V.3 Supplementary results
Due to the sheer number of tables to follow, we shall group them according to topics
V.V.3.1 Interpreting our models: 'SCRUTINIZE'
Table A2
provides experimental results on sensitive real world domain compas. It shows that it is easy flag potential bias fairness issues in data by directly estimating conditional probabilities: considering the GF of this example and ignoring variable age for simplicity, conditionally to having felony count and race being African-American the probability of generating an observation with cxo_yeerrreecid = true is .622 (=1138/2024).
httts///ggeaabbcccmm//dddd/////p paper
27

---

T-J-20 T-J-10x* J-100
Table A3: 2D density plots (I Life Style Index and Customer Rating) for data generated on sigma_cabs, from models learned with 5% missing features (MCAR), using using ensembles of generative trees (top) and generative forests (bottom), for varying total number of trees I and total number of splits (columns). "*" all trees are stumps. The rightmost column recalls the domain ground truth for comparison. Each generated dataset contains m 2000 observations.
V.V.3.2 More examples of Table 1 (MF)
Tables A3 completes Tables 2 and A2 maain file), displaying that even stochastic dependence can
be accurately modeled.
We provide in Table Table the density learned on all our four 2D (for easy plotting) simulated domains and just circgauss in Table [ (MF). We see that the observations made in Table (MF) can be generalized to all domains. Even when the results are less different between 50 stumps in generative forest and generative tree with 50 splits for ringgauss and randgauss, the difference on gridgauss is stark, I generative tree merging many of the Gaussians.
28

---

Ground truth
GF: 50 stumps
GF: 1 tree w/ 50 splits
circgauss
r ringgauss
gt ddduus
randgauss
Table A4: Comparison of the density learned by Generative Forest (GF) consisting of single tree learned by GF. BooST with n total splits (right) and a set of n GF stumps (1 split per tree) learned by BooS (center). The left picture is the domain, represented using the same heatmap. On each domain, 5% of the data is missing (MCAR = missing completely at random).
29

---

3
5
7
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
25
26
27
28
29
30
5
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
55
56
57
59
60
61 62
63
64
65
66
67
68
69
70
Table A5: Densities learned on cirogauss by GF BooST with generative forests consisting of stumps, for values of T' = J in 2,, 703. The models quickly capture the ring and the middle dense Gaussian. The boxy-shape of the densities, due to the axis-parallel splits, get less noticeable as T = J exceeds few dozen.
V.V.3.3 The generative forest of Table [ developed further
One might wonder how set of stumps gets accurately fit the domain the number of stumps increases. Table A5 provides an answer. From this experiment, we can see that 16 stumps are enough get the center mode. The ring shape takes obviously iterations represent but still, is takes mere few dozen stumps to clearly get an accurate shape, the last iterations just finessing the fitting.
30

---

V.V.4.4 Experiment LIFELIKE in extenso
Cowenge
missum,
(GF)
ptal
(GF)
peal
(GF)
ARD
poal
Fing
6200-6007
0.44
cizc
0.256-00002
0.24
0954
10,92200021
0.27
00968-00227
0.854-0011
0.04
0.520-00011
*0507=0052
0.67
grid
0090220002
0394-6002
0.34
000522002
6660-00000
0000400000
014520012
0.76
0. 0:201-00077
00288-0002
0.6
1994400:110
0.54
0.900-0:027
0.74
0029-0001
0114
1007100007
1.09--0031
0..54000003
0.920000000
0.04
0087420022
0.80
10
00000000000
0.01
03300:0027
COlp
10335
00033
10026
10.0
0.10
"OAZATOOE
0:300
0:011
10500 10025
0220
00020
XTT1
003010007
0,899_000
0.010
0.80100001
0199710004
0,707 0.013
0007
002
IK (GR)
CY
pual
CT
(OB)
CT
CV
Fing
0757-00025
010000075
0.5
10.5600000
0435-000
"006 1002
0,40100:33
0000000000
20055
P716
100000000
0400-6000
00042000000
0004200011
0.8
2064
N0290 0000
0,227 0.03
0.0
USS6 10029
0,582 0.035
0.000
10000
0079 10055
0038
Wired
100210007
1384 0.07
10.054000133
0.800
1077410012
0,599
0.129
0.30
1000
0065510003
10050
T. 1110:-0013
1155-
001
0003
0.50
0.310:00007
us (GF)
1
psal
US IGFF
PVa
US (OF)
1V
pea
plal
Ying
02851000
-0.26
0.00
0.09
095010.00
0.51
0.999
10055
"L.05
0.005500.020
0.020
0.07
11001000
1001
0.75
cize
0255610000
-0.554-0000
0:005
0.30
U.S5GEU.015
1.74
0.969-00027
0306
0550
0.5
grid
00.92110002
0,395
0.00
0.53
"0.964
0.000
0.95400.013
0.07
0
00062
'1.013
0.050
0.01
"0.004
0000000.000
0005
-0007
0.02
0150100001
00,388
0.001
0.35
0.954 0.010
0.921000011
0.04
0.936
(0029
11.000
0.008
0.01
00000000000
0000
70008
0.11
11007-0001
1.050-0029
0.84
U1955E0001
0.95
*1009-00054
40258-0052
11200-0013
"L907 0.007
0.05
10,952
0.955-0.000
0.18
0.40-0011
"0,970 0,023
0.05
0.510-00027
10,98-00061
comp
0891
0.74
047420014
6:440001
0.0
0310=002
1132950006
0854-6016
0.51
0039550004
0.744-0016
0.50000022
(GF)
VCG
(GF)
VGG
VCG
psul
VCG
ring
013320011
0291
cize
10356+0002
0415-6012
0.20-000155
0001=00012
gr1d
000
0.00000003
0096
065
90
0.42-00012
0000410010
0.06
Tand
0414
015621011
wred
100700007
LTOS 0002 0U0
0.954100013
0.93310.013
0.02
"08741000 01012
0.21
0.091
0.041
0.04
"0.503 10/003
0.537
10007
0000
110010013
1181-0019
0.06
0002
0.01
0.51023012
0337500226
003
UN (GP)
VCC
poal
(GF)
peal
(GF)
VCC
pual
(GT)
VC-C
pull
Fing
0394-6016
MURGHIMES
01
1015600002
0.00000000
0.04400014
041810.01
109681002
0275200018
0.S00001
010020001
00990-00004
003
D. IRPERTT
02042000
0020010007
0.115 00005
1095 0.01O
09936
10009
01152
0.014
10.000 10005
0.235 TOOTS
WULL
1120F00033
1.47- 0004
0:920
00015
0L510
us (GF)
VC.D
pval
US
VCD
pval
US (OF)
VCDD
pvll
us (GF)
VCDD
pvul
0.90000011
0 0122-0002
0319200077
0:11-0000
UESPEUSS
01968-0021
0,399
1.520
Rx1d
"0392 0002
0.59%
1.96 0.006
10.0%
"0953 10022
0,043 0.009
"0.04 10000
0000)
Tand
0000000077
0.00
0090400000
189610000
6. 0.015
0000010000
0.25
2001
szed
-1007700007
1.883-0.037
01954-0001
0.808-0.062
0.12
"0874400022
0.738-0.030
"0.005-00023
0.59
19h1
1112010013
1.444 0.056
"0952 00.00
10.02
O050 10019
00019
0.891
0,010
"0.500 10027
0.008
0.037
OK (GF)
VC-R
psal
UN (GF)
VC-R
(GF)
psal
Fing
0.88-
00004
FU
0.124
ciyC
0035610000
0.902 0.003
1.94
0.014
0.00100.017
1002 "OS6R
0,274
0.905
"0,500 8.00
0.066
0.02
grid
0.300-000015
002
Xand
"0,290-00007
0.417-0.01M
11.94-00300
50526-00029
0.145-04121
0.229-00222
0107750007
1365-0098
0087420042
6716-0002
0.01
"O 00999220
039620007 0102
L120550013
0335-003
0129
Table A6: LIFELIKE: comparison of Generative Forests (us, GF), using smaller generative forest models (T" = 200 trees, J =500 total splits) to the same contenders as in Table5 file, we also add the option Center for VCAE; we did not push it in the main file for space constraints but its results are on par with the other VCAE results). Conventions are the same as in Table See text for details.
The objective of the experiment is to evaluate whether a generative model is able to create "realistic" data. Tabular data is hard to evaluate visually, unlike e.g. images text, so we have considered a simple evaluation pipeline: we create for each domain a 5-fold stratified experiment. After a generative model has been trained, we generate the same number of observations in the test fold and compute the optimal transport (OT) distance between the generated sample and the fold's test sample. To fasten the computation of OT costs, we use Sinkhorn's algorithm
{ with an e-entropic
regularizer, for some & = 0.5 which we observed was the smallest in our experiments to run with all domains without leading to numerical instabilities. To balance the importance of categorical features (for which the cost is binary, depending on whether the guess is right or not) and numerical features, we normalize numerical features with the domain's is mean and standard deviation prior to computing OT costs. We then compare our method to three possible contenders: Adversarial Random Forests (ARF) 44), CT-GANS 47 Forest Flows [17] and Vine copula autoencoders (VCAE) 41] All these approaches rely on models that are very different from each other. Adversarial Random Forests (ARF) and Forest Flows (FFs) are tree-based generators. ARFs work as follows to generate one observation: one first sample uniformly at random a tree, then samples a leaf in the tree. The leaf is attached to a distribution which then used to sample the observation. As we already pointed out in Section 2 there are two main differences with our models. From the standpoint of the model's s
31

---

distribution, if one takes the (non-empit support from a tuple of leaves, its probability is obtained from weighted average of the tree's distributions in 44 while obtained from a product of theirs in our case. Hence, at similar tree sizes, the modelling capability of the set of trees tips in our favor, but it is counterbalanced by the fact that their approach equip leaves with potentially complex distributions (e.g. truncated Gaussians) whereas we stick to uniform distributions at the leaves. A consequence of the modeling of ARFs is that each tree has to separately code for a good generator: hence, it has to be big enough or the distributions used at the leaves have to be complex enough. In our case, as we already pointed out, a small number of trees (sometimes even stumps) can be enough to get fairly good generator, even real-world domains. Forest Flows use tree-based models to estimate parameters of diffusion models. Their tree- based models are not necessarily big but they need a lot of them to carry out training and generation, which is a big difference with us. Our next contender, CT-GAN (47, fully relies on neural networks so it is de facto substantially different from ours. The last, VCAE 41 relies subtle combination of deep nets and graphical models learned in the latent space.
Table 5 (main file) with smaller generative forests Table A6 provides the equivalent of Table 5 (with one additional contender, which did not fit in the space allotted for the main file), but which our generative forests are much smaller: T 200 trees, 5500 total splits (so each tree is on average barely bigger than a decision stump). One can check that our models are still competitive with respect to all contenders. The best contender, Forest Flows, beat our models density, but it must be remembered that Forest Flows uses many tree-based models to carry out both training and generation.
Focus on Sinkhorn for different parameterizations of contenders We now investigate how chang- ing the parameterization of various contenders affect their performance against our approach. Here, ARFs are trained with a number of trees T E {10, 50, 100, 200) (ARFs include an algorithm to select the tree size so we do not have to select it). CT-GANs are trained with a number of epochs E {10, 100, 300, 10003.
We compare those models with generative forests with T 500 trees and trained for a total of J = 2000 iterations, for all domains considered. Compared to the trees learned by ARFs, the total number of splits we use can still be small compared to theirs, in particular when they learn T > 100 trees. Each table against ARFs and CT-GANs has a different size and contains only subset of the whole 21 domains: ARFs do not process domains with missing values and we also got issues running contenders on several domains: those are discussed in Appendix, Section V.2
domain
Us (GB)
Adversarial Random Forcsts (ARPs)
7w500, J=2 000
T 10
p-val
T 50
p-val
T - 100
p-val
T 200
p-val
iris
0.423 0.033
0.53010.064
0.0039
0.51710.081
0.0866
0.46610.000
0.1452
0.30210.043
10.043
0.0044
ring
00005
1.289100006
0.1918
1.280
0.852
0.28110.010
0.7205
0.286-10.00
0.6213
cire
00.00S
0.35410.002
0,2942
0.35610.008
0,2063
0.35010.002
0,9050
0.355:00.005
0.3304
grid
0.002
0.39410.003
0.1376
10.002
0.3210
0.392.10.001
0.2118
0.394_10.002
0.0252
1,108 1785
1,27240 281
0,2807
0.1215
0.0972
1,28=002200 209
0.0616
rand
0. 0.286=0.003
0. 0.286+0.003
0,9468
0.290+0.005
0,2359
0 0.28++0.005
0.3990
0.288=0.002
0.3685
0.575=0.002
0.577100001
0,2133
0.57810.001
0.1104
0.77:00000
0.2739
0.577
0.2773
1ono
1.167 0.074
T,31 10.045
0.0005
469
10.09
0.0001
1431 10.058
0.0015
1:400
1 10.056
0.0035
0,975=0.026
1.10000013
0.0304
1.015
0.0231
1.001 +0.010
0.0956
1001400021
0.0261
uxed
0,980 0.032
10.030
0.0003
1.07210.05
0.0133
1086100.03
0.0005
1,999 10.05
0.0001
stp
01966200188
0.99
0.082
012100010
0.0250
106-0000111
0.0280
0003
0.0277
0,168=00014
0.370+0.012
0.7951
0.38+000013
0.1822
0 0.308+0.006
09161
0,309=00077
0.3166
aba
0.490=0.028
0.505+0.046
0.5251
0.484+0.024
0.7011
0 0.503+0.035
0.6757
0.481=0.031
0.4632
vohi
1,064 0.003
1.19910.111
1119910.006
1.10010.014
1.15010.021
000005
comp
0.552=0.008
0,531+00012
0.8278
0.534+0.009
0.8438
0.551+0.023
0.1371
0.335=0.053
0.8642
arti
0.82110.004
00004
0.84910.004
0.0007
1.807
0.0005
0.040
00000
0.000
0.00055
jung
0.929
0.002
0.92910.002
0.6444
0.93010.002
0.6336
092910002
0.5937
0.93
0,4447
01ec
1,83=00.033
0777400088
0.1052
54340.017
0.008
55240.039
0.022
1.58 =0,05
0.00955
wins / lose for us
1571
1771
1671
1771
Table A7: LIFELIKE: comparison of ARFs [44 with different number T of trees, and meduim-sized
Generative Forests (us, GF) where the number of trees and number of iterations are fixed (T 500 trees, total of J = 2000 splits in trees). Values shown = average over the 5-folds + std dev. The p-values for the comparison of our results ("us") and ARFs are shown. Values appearing in green in p-vals mean (i) the average regularized OT cost for us (GF) is smaller than that of ARFs and (ii) p < 0. i.e. our method outperforms ARFs (there is no instance of us being statistically significantly beaten by ARFs). s means p-val < 10
Domain details in Table Al
32

---

Results vs Adversarial Random Forests Table A7 digs into results obtained against adversarial random forests on the Sinkhorn metric. A first observation, not visible the table, is that ARFs indeed tend to learn big models, typically with dozens of nodes in each tree. For the largest ARFs with 100 or 200 trees, this means in general a total of thousands of nodes models. A consequence, also observed experimentally. is that there is sometimes little difference in performance in general between models with a different number of trees in ARFs as each tree is in fact an already good generator. In our case, this is obviously not the case. Noticeably, the performance of ARFs is not monotonic in the number of trees, so there could be a way to find the appropriate number of trees in ARFs to buy the slight (but sometimes significant) increase in performance in Nomain-depennden way. In our case, there is obviously a dependency in the number of trees chosen as well. From the standpoint of the optimal transport metric, even when ARFs make use of distributions at their tree leaves that are much more powerful than ours and in fact fit to some of our simulated domains (Gaussians used in circgauss, randgauss and gridgauss), still manage to compete or beat ARFs on those simulated domains.
Globally, we manage to beat ARFs almost all runs, and very significantly on many of them. Since training generative forests does not include a mechanism to select the size of models, we have completed this experiment by another one on which we learn much smaller generative forests. The corresponding Table is in Appendix, Section V.V.44 Because we clearly beat ARFs on student __ttt__erfffee ormance mat and student_ cetnnttperrfrree pperformance_ppe
in Table A7 but are beaten by ARFs for much smaller generative forests, we conclude that there could exist mechanisms to compute the "right size" of our models, or to prune big models get models with the right size. Globally however, even with such smaller models, we still manage to beat ARFs on a large majority of cases, which is good figure given the difference in model sizes. The ratio "results quality over model size" tips in our favor and demonstrates the potential in using all trees in a forest to generate an observation (us) using single of its trees (ARFs), see Figure |
Table A8 summarizes our results against CT-GAN using various numbers of training epochs (E). In our case, our setting is the same as versus ARFs: we stick to T = 500 trees trained for a total number of J = 2000 iterations in the generative forest, for all domains. We see that generative forests consistently and significantly outperform CT-GAN Furthermore, while CT-GANs performances tend to improve with the number of epochs, we observe that on majority of datasets, performances forests and already induce training times that are far bigger than for generative forests: for example, more than 6 hours per fold for stm while it takes just a few seconds to train a generative forest. Just like we did for ARFs, we repeated the experiment vs CT-GAN using much smaller generative forests (T = 200, J 500). The results presented in Appendix, Section V.V.3.4. There is change in the conclusion: even with such small models, we still beat CT-GANs, regardless of the number of training epochs, on all cases (and very significantly on almost all of them).
Results vs CT-GANs
nearly all cases.
000 epochs are still far from those of generative
More results with small generative forests Tables A9 and A10 present the results of generative forests adversarial random forests and CT-GANs, when the size of our models is substantially smaller than in the main file (T = 200, J = 500). We still manage to compete or beat ARFs on simulated domains for which modelling the Icaf distributions in ARFs should represent advantage (Gaussians used in circgauss, randgauss and gr gridgauss), even more using comparatively very small models compared to ARFs. We believe this could be due to two factors: (i) the fact that in models all trees are used to generate each observation (which surely facilitates learning small and accurate models) and (ii) the fact that we do not generate data during training but base our splitting criterion on an exact computation of the reduction of Bayes risk in growing trees. If we compute aggregated statisties comparing, for each number of trees in ARFs, the number of times we win / lose versus ARFs, either considering only significant p-values or disregarding them, our generative forests always beat ARFs on a majority of domains. Globally, this means we win on 34 out of 52 cases. The results vs CT-GANs are of the same look and feel as in the main file with larger generative forests: generative forests beat them in all cases, and very significantly in most of them.
V.V.3.5 Comparison with "the optimal generator": GEN-DISCRIM
Rather than compare our method with another one, the question we ask here is "can we generate data that looks like domain's data" We replicate the experimental pipeline of [3I]. In short, we shuffle a 3-partition (say R₁, R2, R3) of the training data in a 3! 6-fold CV, then train generator G1
33

---

domain
(GF)
CI-GANs
Eag
7=500, J=2 000
E - 10
p-val
E - 100
p-val
B 300
p-val
E 1000
p-val
ring
0.285 0.0008
0.45740.058
0,0032
0.546
0.0018
0.405=0.044
0.0049
0.0042
0,0183
cire
0,351 0.0005
0.84810.300
0,0213
0.450:10.040
0.0019
0.44
0.35500025
0.0711
grid
0.390=0.002
0.74940.417
0.1268
0.459=0.031
0.0085
0.426=0.022
0.027
0,408
0,1000
1.
9.79615.454
0.0049
089910.289
0.0045
0.
0.0244
152010.311
0,0410
rand
0.003
0.746
0,0119
1.491:00.03.
0.0021
0.368
0.0055
0.0002
0.027
0,0288
tic
0.005
0.601 +0.003
0X0002
0.581=00001
0.0082
0.586
0.0294
0.584
0.0198
1ono
1.167 0.007
2.263-H0.035
0.084
5
1.844
+0.17
0.0002
stm
0.032
1.011
1.049
0.0002
0.068
0.0056
1167
0.0013
ured
0.980=0.032
2.836:00.03
0.0044
0.004
1.825
0.0001
1.304
stp
0.976=0.018
1,66000,161 161
0,0006
0.141=0.0T8
0.0001
0.206=0.0066
0.0007
H186
0.0019
ana 0.368=00014
0.542+0.135
0.0050
0.059
0.0202
0.002
0.0397
0.436
0.0051
aba
0.490=0.028
0.89++0.053
0.463
6
0.054
0.0009
0.607
0,0006
1.04=000003
1770000160
0.0005
8.99:00064
1,284=0.022
+1.000
art1'
0.821 #0.004
0.0020
200=00018.
0.0005
1.06:0.0133
0.0001
0.059
0.0038
wins / lose for
14/0
1470
14/0
1470
Table A8: Comparison of results with respect to CT-GANs [47] trained with different number of epochs E. On some domains, indicated with a "8" CT-GANs crashed on some folds. For such domains, we indicate in index to CT-GANs results the number of folds (out of 5) for which this did not happen. In such cases, we restricted the statistical comparisons with which CT-GANs did not crash: the statistical tests take this into account; instead of providing all corresponding average performances for us, we keep giving the average performance for us on all five folds (leftmost column), which is thus indicative. Other conventions follow Table A7
the folds for
from R1 (we use generative forests with GF. .FF.BOSS), then train a random forest (RF) to distinguish between 11 and R2, and finally estimate its test accuracy on G1 vs R3. The lower this accuracy, the less distinguishable are fakes from real and thus the better the generator. We consider 3 competing baselines to our models: (i) the "optimal" one, COPY, which consists in replacing G. by set of real data, (ii) the "worst" one, UNIF(orm), which uniformly samples data, and (iii) GF. BOOST for 1, which learns a generative tree (GT). We note that this pipeline radically different from the one used in [44]. In this pipeline, domains used are supervised (the data includes a variable to predict). A generator is trained from some training data, then generates an amount of data equal to the size of the training data. Then, two classifiers are trained, one from the original training data, one from the generated data, to predict for the variable to predict and their performances are compared on this basis (the higher the accuracy, the better). There is a risk in this pipeline that we have tried to mitigate with our sophisticated pipeline: if the generator consists just in copying its training data, it is guaranteed perform well according to 44''s metric. Obviously, this would not be a good generator however. Our pipeline would typically prevent this, R2 being different from R3.
Results Tables A1T and A12 provide the results we got, including statistical p-values for the test of comparing our method to COPY. They display that it is possible to get GFs generating realistically looking data: for iris, the Student é-tests show that we can keep Ho "GFs perform identically to COPY" for J = T = 40 (p > .2). For mat, the result is quite remarkable not because of the highest p-val, which is not negligible (> 0.001), but because to get it, it suffices to build GF in which the total number of feature occurrences (J = 80) is barely three times as big as the domain's 's dimension (d 33). The full tables display a clear incentive to grow further the GFS as domains increase in size. However, our results show, pretty much like the experiment against Adversarial Random Forests, that there could be substantial value of learning the right model size: iris and student_per peerffeeefffo ormance_ppai e_por clearly show nontrivial peaks of p-values, for which we would get the best models compared to COPY.
34

---

domain
(GF)
Adversarial Random Forests (ARFS)
lag
T=200, J=500
T= 10
p-val
T 50
p-val
T= 100
p-val
T 200
p-val
iris
0.029
0.030
0.9890
0.51740.081
0.865
0.466
0.1099
0.501
0.6548
ring
0.283+0.005
0.28940.006
0.0651
0.286+0.007
0,4903
0.0000
0,4292
0.286
0.7442
circ
0..06+10.002
0.35410.002
0.4561
0.006
0.7882
0.350:10.002
0.059]
0.3554.0.00$
0.7446
grid
0.39240.002
0.394:0.003
0.4108
0..00200002
0.3403
0.392::11.00
0.8370
0.394400.002
0.3425
for
1.86640.124
1.272:0.281
0.1420
1.431
0.1142
1.311:H0.255
0.1215
1.268+0.209
0.0370
rand
0. 0.000
0.286.0.000
10.003
0.4488
0.290.0..005
0.9553
0.289:10.000
0,9004
0,288 10.002
0.6542
tic
0.001
0.577=0.001
0.0394
0.578+0.001
0.0325
0.577#0.001
0.0657
0.577+0.001
0.0914
lono 1.203++0008
1.401
0.7307
1.46940.079
0.3402
4.401
0.7046
1. 0.420+0.056
0.8737
stm
1..4100003
L01000.011
0.0080
1.01510.018
0.0094
1.001 10.000
0.0037
1014
0.0329
wred
L0277
L08640.036
0.0327
..72200055
0.1432
0.06600.030
0.0095
H0.03
0.0044
stp
1.029400027
0.99910.011
0.0826
1.11240.000
0.3421
1.006:1.001
0.0542
4.003
0.0764
ana 00.011
0.37010.012
0.8229
0.002
0.2318
0..00
0.9264
1..09
0.8722
aba 0.476
0,005:0.046
0.2264
0.48440.024
0.2162
0.503+000035
0.1847
0.481+0.031
0.7468
wwhi
1.12040.013
1.15910.011
0.0013
1.15910.006
0.0014
1.17011.0014
0.0026
1.15010.001
0.0327
comp 0.338100015
0.531
0.5639
0.534++0.009
0.5706
0.001
0.4057
0.535+0.033
0.9017
arts 0.830+0.007
0.849+0.004
0.0078
0.847++0010
0.0012
0.843+00.009
0.0003
0.849+0.010
0.00
jung
0.0001
0.009
0.1720
0.930+0.002
0.0646
0.929+000002
0.2675
0.930+0.001
0.0081
elec
1.503 10.035
1,577 10.088
0.1222
1..011
0,0880
1.552
0.1228
1,581 10.025
0.0027
/ lose for
1375
1175
1275
1276
Table A9: Comparison of results for ARFs [44] with different number of trees, and small Generative
Forests (us, GF) where the number of trees and number of iterations are fixed (T' 200 trees, total of
J = 500 splits in trees). Values are shown on the form average over the 5-folds + standard deviation. The p-values for the comparison of our results ("us") and ARFs are shown. Values appearing in green in p-vals mean (i) the average regularised OT cost for us (GF) is smaller than that of ARFs and (ii) p 0.1, meaning we can conclude that our method outperforms ARFs. Values appearing in magenta in p-vals mean (i) the average regularised OT cost for us (GF) is larger than that of ARFs and (ii) p < 0.1, meaning we can conclude that our method is outperformed by ARFs. The last row summarizes the number of times we win lose against ARFs according to the average metric used. To reduce size, domains are named by a tag: the correspondence with domains and their characteristics in Table AI
V.V.3.6 Full comparisons with MICE missing data imputation
The main file provides just two examples of domains for the comparison, abalone and analcatdata_ssppreme We provide here more complete results on the domain used in the main file and results more domains in the form of one table for each additional domain:
Table/A13 experiments on analcatdata_ (MP);
completing the results shown in Table
Table A14
experiments abalone completing the results shown in Table 4 (MF);
(tables below are ordered in increasing domain size, see Table A1
Table
experiments on iris;
Table A16
experiments on ringgauss;
Table A17
experiments on circgauss;
Table A
experiments gridgauss;
Table A19 19
experiments randgauss;
Table A20
experiments on student_
Table A21
experiments on student__petee titieett_prrformncee_ooooo
Table A22
experiments on kc1;
Table A23
experiments sigma_
Table
experiments compas;
. Table A25
experiments open
The large amount of pictures to process may make it difficult to understand first glance how our approaches behave against MICE, summarize here the key points:
35

---

domain
(GF)
CT-GANs
lag
7=200, J=500
E 10
p-val
E - 100
poval
E 300
p-val
E 1000
p-val
ring
0.283440.05
0.457+40.08
0,0029
0.546440.09
0,0020
4.405400044
0,048
4:3004
0.0299
circ
0.306++0.002
0.848+0.300
300
0,0217
0.480+0.0040
0.0044
0,44340.014
00001
0.035+0.075
0,0816
grid 0.39240.002
0.749
0.1279
0.409
0.099
0.426:000222
0,0233
0.009
0.1239
for
10.244
9.79615.454
0.0241
E8,99
0.0028
1.5
0.0020
1.30000311
0.0313
rand
0.000
0.746
0.0129
0,491 0.003
0.0017
0.0681
0.0003
0.527+00024
0.0124
0.574++0.00
+0.003
0.581+0.001
0.0024
0.586+00.006
0.0299
0.584+0.003
0.0228
lono 4.203+0.068
2.26340.035
2.084
1.98=0.136
0.0001
1.758
0.0005
stm 4.04400.13
L.311+0.074
0.0001
1.19900.055
0.0106
1.68400005
0.0346
116770.044
0.0036
wred
40273
2.836
0.0049
1..00
6
182550.127
6
1.384
0,0002
stp 40.02
1661
0,0010
1.141
0.0004
1.206.10.046
0.0015
11.66
0.0057
4.0018
0.54240.135
0,0399
4.039-000056
0.0196
0.402
0.0231
H0.066
0,0018'
aba 4,476
468940.053
I. F.063
0.75440.040
0.657
wwhh
1.000
1,77040.660 160
0.0009
I 10.094
1. 1,284400029
0.0006
1.
141.84
0.0117
art1"
4..007
1.38-=0.1092
0,0021
1.209 1.209+0.008 +0.08,
1006=00.013 0.0002
0.959 +00013 0.0051
wins/ / Jose for us -
1470
1470
1470
1470
Table A10: Comparison of results with respect to CT-GANs [47] trained with different number of epochs E. means p-val < 10-1 As already mentioned in Table A8 in some domains, indicated
with "*" CT-GANS crashed on some folds. For such domains, we indicate in index to CT-GANs results the number of folds (out of 5) for which this did not happen. In such cases, we restricted the statistical comparisons with us to the folds for which CT-GANs did not crash: the statistical tests take this into account; instead of providing all corresponding average performances for us, we keep giving the average performance for us on all five folds (leftmost column), which is thus indicative. Other conventions follow Table A9
first and most importantly, there is not one single type of our models that perform better than the other. Both Generative Forests and Ensembles of Generative Trees can be useful gives a clear
for the task of missing data imputation. For example, caaalcatdtaa_ppprncaa advantage to Generative Forests: they even beat MICE with random forests having 4 000 trees (that is hundreds of times more than our models) on both categorical variables (perr) and numerical variables (rmse). However, on ciregause, student_perrorment wwt.:ppeerromeeeppppmm and si sigma_ cabs, Ensembles of Generative Trees obtain the best results. On sigma_ iiga__cabs, they can perform on par with MICE if the number of tree is limited (which represents 100+ times less trees than MICE'S models);
as is already noted in the main file (MF) and visible on several plots (see e,g. sigma_ _aaaa,, overfitting can happen with our models (both Generative Forests and Ensembles of Gen- erative Trees), which supports the idea that a pruning mechanism or a mechanism to stop training would be a strong plus to training such models. Interestingly, in several cases where overfitting seems to happen, increasing the number of splits can reduce the phenomenon, at fixed number of trees; see for example iris (50- 100 iterations for EOGTs), gri gridgauss, randgauss and kc1 (GFs);
some domains show that our models seem to be better at estimating continuous (re- gression) rather than categorical (prediction) variables: see for example abalone, student__perormeet
student_perfee caa.eentt_perffmmnne__eaaeee
and our biggest domain, Note from that last domain that larger number of itera-
open_policing hartford. hooliiiigghhatfoddd tions or models with a larger number of trees may be required for the best results, in particular for Ensembles of Generative Trees;
small models may be enough to get excellent results on real world domains whose size would, first glance, seem to require much bigger ones: on compas, we can compete (rmse) or beat (perr) MICE whose models contain 7 000 trees with just 20 stumps;
it important to remember that our technique does not just offer the capability to do missing data imputation: our models can also generate data and compute the full density conditional to observed values, which is not the case of MICE's models, crafted with the sole purpose of solving the task of missing data imputation. Our objective was not to beat MICE, but rather show that Generative Forests and Ensembles of Generative Trees can also be useful for this task.
36

---

J 20
40
80
100
2.00
0.5
008
geneatre
3.79
0.75
0.75
07
peeeriee Frests
generatie forera
1007
25
35
20
25
90
15
43
13
15
20
25
35
(1)
0.75
13.78
1075
18755
10.75
07
0.7
20
30
#7we (7)
0.50
3.00
0.25
0:35
0.05
abalon
0.7
07
87
2.05
0.55
0.05
Table All: Results of generative forests on GEN-DISCRIM for four UCI domains, ordered, from top to bottom, in increasing domain size. In each row, the accuracy of distinguishing fakes from real is plotted (the lower, the better the technique) for four contenders: UNIFORM (generates observation uniformly at random), COPY ("optimal" contender using real data generated), GF. BOOTT inducing generative forests and generative trees (indicated for T 1). A clear pattern emerges, that as the domain size grows, increasing J buys improvements and, if J is large enough, increasing T also improves results. See Table A12 for comparisons (us vs COPY) in terms of p-values.
Ensembles of Generative Trees (ROGT) perr
Generative Forests (GF)
rmse
pert
rmse
180
112
2.43
143
5:48
20 iterattoon
70
0.25
025
(000
generabive fraeh
gengeitt tepal
#300 (7)
143
2.55
100 iterations
0.5
narginal
130
113
245
122
150
60
63
235
120
225
112
123
narghal
113
200 iterations
180
H000 mo01
H400 tozs
03
(400
02
Table A13: Missing data imputation: results analcatdata_supree with 5% missing features
(MCAR). for GF, BooST learning GFs and EOGTS, vs mice using RF (random forests) with 100

---

J 20
J 40
J 80
100
0406
0.3
0010
0.12
0435
1:20
00%
0.16
0.1
02
50.00
50003
50000
021
0.300
10000
20000
2.30
0401
8:0
0.04
0002
0300
(7)
07/66/11 (73
STRe0C (1)
(1)
0.303
0.001
200000
20.012
$6:004
0.30
21.003
10005
L03811
00891
0.004
0303
3,005
38 25
36
30
15
28
30
5.0011
1.004
g30001
30.0005
1.803
64177
401"
1.001
0000
g30005
$0.004
04800
abalone
00891
(9017)
Table A12: p-values for Student tests with Ho being "GF and COPY perform identically on GEN- DISCRIM" (for the domains in Talle Large values indicate we can keep Ho and thus consider that GF is successful at generating "realistic" data, Clearly, GF are successful for iris (p increases with T up to p 0.3 for J 40). For the other domains, Table All suggests increasing T. The curves for abalone reveal dramatic relative increase of as (J, T) increases, starting from p ~ 0, VT for J 20.
Ensembles of Generative Trees (BOGT) perr
Generative Forests (GF)
imsse
pert
imsse
245
20 iterations
0.0
06
gaauh Eanias
0.59
238
100 100 iterrattioon
0.5
06
mi (1)
Table A14: Missing data imputation: results on abalone with 5% missing features (MCAR), for
GF. BooST learning GFs and ROGTs, mice using RF (random forests). Conventions follow Table
A13
38

---

Ensembles Generative Trees (EOGT)
Generative Forests (GF)
perr
rmse
perr
rmse
20 iterrtionns
66
reight
68
mawgeoin (183)
10
18
10
18
12
18
18
12
16
8inee
50 iterationns center
4.5
68
1100 iterationns orsim)
80
Pres
Table A15: Missing data imputation: results iris with 5% missing features (MCAR), for
GF BooST learning GFs and EOGTs, vs mice using RF (random forests). Conventions follow Table
A13
39

---

Ens. of Generative Trees (EOGT)
Generative Forests (GF)
rmse
rmse
imputation (numerical variatles)
3.5
2.6
generative tree
2.5
2.4
2.5
22
Ristff 000 frees)
20 iterattio
mas
2.1
Of generatie 1005
1.8
Strees (T)
strees (T)
imputation moe (numerical vanaable)
2.8
2.7
2.8
generative tree
2.6
2.5
2.4
22
(ross)
100 iterations
2.1
Imputation
ens. of generative tees
1.9
1.4
1.8
Atrees
Atrees
imputation (numenical vartable))
2.8
2.6
generative tree
2.5
2.4
2.4
2.3
generative
7000
22
61 200 (rees)
2.1
200 iterations
Imputation men
generativ foreats
888
ens, of generalive teeo
1.8
1.8
10
12
16
18
10
12
14
16
18
imputation (sumerical variables)
2.5
2.4
Imputation (sumerical
2.6
2.8
generative
2.3
2.4
Rise trees)
400 iterations
22
We03)
2.1
generabive forests
1.8
2
10
12
14
16
18
20
10
12
14
16
18
20
Table A16: Missing data imputation: results ringgauss with 5% missing features (MCAR), for GF. BoOST learning GFs and EOGTs, mi ce using RF (random forests). Since there are nominal attributes in the domain, have removed column perr. Conventions otherwise follow Table A13
40

---

Ens. of Generative Trees (EOGT)
Generative Forests (GF) rmse
rmse
20
21
18
generative tree
18 +
oscerff (1000 trees)
20 iterrations
nice.t (1000 troos)
-6
13
margg
ens. of generative Tees
generative forests
atrees (T)
strees (T)
22
20
generative tree
Impuration (numenical
18
imputation (numerical
20
16
18
(1000 trees)
100 iterations
10
ens. of generatie trees
12
forests
atrees (T)
strees (T)
18
22
generattive tree
20
generative (1000 (rees)
15
17
200 iterations
74
mss
mice. (1000 trees)
generative
generative forests
Atrees
Atrees
21
generafive
20
18
generative tree
mice (1000 trees)
18
400 iterations
15
(1000 trees)
14
imputation
13
manginal
Imputation
generalive forests
ens. of generatve tees
10
12
14
18
10
14
18
20
Table A17: Missing data imputation: results circgauss with 5% missing features (MCAR), for GF. GF. BoOST learning GFs and EOGTs, mi ce using RF (random forests). Since there are nominal attributes in the domain, have removed column perr. Conventions otherwise follow Table A13
41

---

Ens. of Generative Trees (EOGT)
Generative Forests (GF)
rmse
Imss
(numerical varaties)
20
18
generative tree
(numericall
mice (1000 trees)
16
(ees)
15
14
marginal
gemonelvo-deop
13
20 itteraations
12
generative forests
16
18
#trees
strees (T)
19
20
generative tree
18
11000 Trees)
100 iterations
mice (1000 trees)
ens, of generative bees
imputation
generalivs forests
stroes
strees (T)
24
22
20
generative
generatie tree
16
200 iterations
mos
74
Trice (1000-wen5)
imputatio
ens. generative frees
marginal
atrees
strees (T)
21
20
generative
400 iterations
Imputation moe
hanginal
ce frees)
Impusation mose
16
mice if (1000 trees)
14
marginal
generative forests
23
ens, generatve tees
10
Atrees
strees
Table A18: Missing data imputation: results gridgauss with 5% missing features (MCAR), for GF. BoOST learning GFs and EOGTs, mi ce using RF (random forests). Since there are nominal attributes in the domain, have removed column perr. Conventions otherwise follow Table A13
42

---

Ens. of Generative Trees (EOGT)
Generative Forests (GF)
20
20
18
Imputaiio (numerical
16
16
generalive free
14
22
20 iterations
generatve tees
imputation
RiDe (1000 trocs)
race 1100 0003 generativv
10
12
14
18
20
10
12
14
16
18
20
strees
strees
mariinal
16
(numenicall
Impubation (numericall
generative
12
100 100 iterations
10
generative
10
generative free
a1 mobes
generative forests
18
strees
strees (T)
Imargimat
mamiina
18
16 12
generative tree
generative
200 iterations
10
generatiee fres
Imputation
RICE (1000 trees)
generative forests
2
Atrees (T)
Atrees (T)
R
20
to
400 iterations
imputatin mase
generative
generative forests
Strees
strees
Table A19: Missing data imputation: results randgauss with 5% missing features (MCAR), for GF. BoOST learning GFs and EOGTs, mi ce using RF (random forests). Since there are nominal attributes in the domain, have removed column perr. Conventions otherwise follow Table A13
43

---

Ensembles Generative Trees (FOGT)
Generative Forests (GF)
perr
rmsc
perr
imse
200 iteratios voroeaa 100 itterattonn varanay 20 Dnjierations coraaae
140
120
04
(1550) 11:7
pranl.a 1945
0355
moxx (1500 (oes)
P104-11
19:77
0.30
0.00
marg
gelerave S0nis
0.35
025
mang
05
100
0.45
gegense tee
F100 ww000 kemt
8lo44 (7)
400 iterations rocona
0.45
of gpoerci 199s
645
15000 beat!
genativa Ired
P10.7 71 11000 39
10ce (1e3)
16
10
Table A20: Missing data imputation: results Scuudett_perfornnn mat with 5% missing features (MCAR), for GF GF.BOOST learning GFS and EOGTs, vs mice using RF (random forests). Conventions follow TableAA3
44

---

Ensembles of Generative Trees (EOCT)
Generative Forests (GF)
perr
rmsc
perr
Imss
20 iiterations car3147
105
0.90
0:66
19
genarable
0:35
15500 11.87
6355
moo [10000 (o0g)
100 Dliitrations caroaa
Forgaa
05
Saaie frests
88004
400 ittrrattionn Toranay 200 itgirattooon veesaa
0.45
6.45
(1000
10
16
12
12
22
10 I0
00044
06
0.55
04
15
04
000 bands
(1900 kean!
035
(18430 1000)
DEC 010000 2EEE
mISEU 2011
Table A21: Missing data imputation: results student, student_perrormaatt wwwformanceeeeeeee _por with 5% missing features (MCAR), for GF. GF.BOSST learning GFS and EOGTS, vs mice using RF (random forests). Conventions follow TableAA3
45

---

Ensembles Generative Trees (EOGT)
Generative Forests (GF)
perr
rmse
perr
imse
20 iiteratiooss conoooaa
0.5
2:17
2010
0.39
0.59
ga 1rtthe T94
1409
12/g
044
100 Dltttrations
Rarch
Karch
6:5
401ch
201
0:15
BEAM
2010
2015
Surch
500 intertttioss parane 200. ittrations 1ars04
1.8v10
08.
1
0.9
1.009
144r
1.5rghh
645
12rchh
0.3
04
Gong
Axy
038
0.3
Garch
Barch
025
4010
662
02
2010
0.19
0:10
35
30
10
#11
4000
1,00yp
1.xr1P
0.55
0.66
14ur2h
05
0.2
14010
044
1.2g9*
040
12012
04
04
1x10
0.3
026
Table A22: Missing data imputation: results kc1 with 5% missing features (MCAR), for
GF. BOOST learning GFs and EOGTs, vs mice using RF (random forests). Conventions follow
Table A13
46

---

Ensembles of Generative Trees (EOGT)
Generative Forests (GP)
perr
rmmse
perr
imse
20 jiterations C000000
Easc
1000
e10 pa venttte
Seneratvve
0.55
LI0C leed!
0:0
100 iltirattions (araaa
0.9
3/000
genertive 20t
Setersivv tondl
C45
200 iniitratiion nanmose
0.7
0.75
$4500
4.00
0.55
0.63
100
210
200
1000
Pra00 01
Table A23: Missing data imputation: results on sigma_ with 5% missing features (MCAR), for GF. BooST learning GFs and EOGTs, vs mice using RF (random forests). Conventions follow Table
A13
47

---

Ensembles of Generative Trees (EOGT)
Generative Forests (GF)
perr
rmse
perr
rmse
500 interattoons 1onomas 100 iterationns vartaaa 20 Dittraaioon canoaaa
0:48
028
6:18
0.1
peloercvs Seaats
0.05
0.55
0.55
0.50
645
035
100
028
0.29
Selesivv Senuas
30
05
83
80
30
102
30
50
50
30
50
70
90
00
100
10
25
30
00
100
(7
80064
17906
0.55
0.55
2200
3000
2200
035
03
Leas
Table A24: Missing data imputation: results on compas with 5% missing features (MCAR), for
GF. BoOST learning GFs and EOGTs, vs mice using RF (random forests). Conventions follow Table
A13
48

---

Ensembles of Generative Trees (EOGT)
Generative Forests (GF)
perr
rmss
perr
rmse
nanora 20 Dittrrtioos SOTURRA
2200
2013
3040
3550
of peneratiee
3000
2100
1-440
11:00
generaive
114
110
100
20
20
Rowe (7)
Proes
2200
1200
100 iterations
pererzzo 2000
3200
300
3020
3340
2000
04
20
29
10
(ivex(T)
5.0 ittrrattoons ranoraa
07
2200
2200
3.00
3140
320
3220
03
Table A25: Missing data imputation: results on open_ apeen_ooliinnggarrrfeeee with 5% missing features (MCAR), for GF. BOOST learning GFs and EOGTs, vs mice using RF (random forests).
Conventions follow Table A13
49

---

KDE
-0.5
-1
expected log-dens
-1.5
-2
-2.5
only stumps
some trees not stumps
-3
-3.5
-4
4.5
500
1000
1500
2000
splits GF
Table A26: DENSITY:
the GF is grown by GF. BFoB in way that first learns a complete set of stumps (there are total of T 500 trees in the final model) and then grows some of the trees. The plateau for j & 500 leaves displays that quickly reach a limit in terms of maximal performances of stumps, this being probably dues to the fact that the dimension of the domain is small (2). We however remark that with just stumps, we still attain close performances to KDE (note that we plot the expected log-densities; see text for details).
the gridGauss domain:
10"10P
KDE
10"10"
KGE
100"10"
1"10P
10"10"
100"
1'00F
10"10>
10/103
splits
spllss GF
500,
2000
T 15, J 10000
Table A27: DENSITY: zoom on the abalone domain: with T = 500 trees, total of J 2000 as in Tables A28 and A29 we are clearly beaten by KDE (left). A much smaller of bigger trees (I' 15, J 10000) enough to become competitive and beat KDE, albeit not statistically significantly (right). The right picture also displays the interest into getting pruning or early stopping algorithms to prevent eventual overfitting.
V.V.3.7 Full comparisons with KDE on density estimation
For each domain we either use the expected density, or the expected negative log-density, as the metric be maximized. We consider the expected density to cope with the eventuality of zero (pointwise) density predictions. Tables A28 and A29 present the results against KDE (details in Table A28). Table A266 singles out result on the domain gridGauss, which displays an interesting pattern. The leaf chosen for split in GF BoOST is always the heaviest leaf; hence, as long as the iteration number j & (the maximum number of trees, which is 500 in this experiment), GF. BOOST grows stumps. In the case of gridGauss like in few other domains, there is clear plateau in performances for j & 500, which does not hold anymore as j > 500. This, believe, characterizes the fact that on these domains, which all share the property that their dimension is small, training stumps attains limit in terms of performances. TAbss that by changing basic parameters here, decreasing the number of trees, increasing the total number of iterations one can obtain substantially better results.
50

---

1110F
-2.
ecperte Seea
10h107
expected log -ens
100716"
-0.5
ospectel
344
17100
38
-1.
10"10"
42
300
1000
1500
2000
500
1000
1500
2000
500
1000
1500
2020
iris
ringGauss
circGauss
KDE
1'10
KDE
0.0001
1x10*
expected 0011
eqperter deas
1x30 19
1x10 12
100110
1x10
1x10
20
10'10
500
1000
1650
2000
500
1001
1300
2000
3G0
1000
1530
2000
splis
forestf ires
randCauss
t tictactoe
1110/5
1110
KDC
15
expeered Ingedaee
10'10
10'10
eloedeed cens
1110
excected
100/10"
-5
10
-10
1110
1'10
10"
10'10
000
1000
1600
2000
500
1000
1600
2000
500
1000
1000
2000
apilts
apils CF
ionosphere
student_ wwwerformaceeeeee _aat
winered
Table A28: Comparison of results for Kernel Density Estimation (KDE) and Generative Forests (us, GF) with parameters T 500 trees, total of J 2000 splits in trees, on first batch of domains, put in increasing size according Table A1 For each domain, compute for GF regular intervals the average + standard deviation either (i) density values or (ii) negative log density values for the test fold (sometimes, KDE gives 0 estimated density which prevents the computation of (ii).. Warning: some y scales are logscale. We then compute the baseline KDE and display its average i standard deviation in blue each picture. We perform, at each applicable iteration of GF. GF.BooST (i.e. each iteration for many domains, which can be seen from the plots), Student paired t-test over the five folds to compare the results with KDE, If we are statistically better (p 0.1), plot is displayed in green; if KDE is better, our plot is displayed in red; otherwise it is displayed in gray. When standard deviations not displayed, it means average standard deviation exceeds the plot's scale.
51

---

10"199
KUT
10
100
KJL
100
1110
10'15
expected de1e
10
100"10
1'0
100"10
1'10
1110"
171000
10m1p
10'10
100'10'3
11
100/10
11109
1000022
10 10
1'1046
sppiita OF
* apilla
s student_performaent por
amalcatdaatassuuromee
kc1
KDE
100'10"
KGE
10'10"
10h10P
1'1dt
100
103"10"
expeded
1"10P
1'10
1'109
100"10"
10"10
10"10P
10"
11100
2:ppit
splits GF
# spiits
winewhite
compas
Table A29: Comparison results for Kernel Density Estimation and Generative Forests (us, GF) where the number of trees and number of iterations (T 500 trees, total of J 2000 splits in trees), on a second batch of domains. Conventions follow Table A28
52

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Claims are supported by both the theoretical results presented in the paper and extensive experimental results, summarized in the main paper but otherwise presented in extenso in the Supplement.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Limitations are discussed, in particular the experimental section vs the SOTA (see e.g. experiment Lifelike).
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "L.imiations" 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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or 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 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
53

---

Answer: [Yes]
Justification: Assumptions are detailed, formal results given and full proofs are provided in the Appendix.
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 cross- referenced.
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 short proof sketch to provide intuition.
Inversell, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: (i) full code provided, (ii) extensive README.1t, (iii) coding choices dis- cussed in Appendix, (iv) all scripts provided for easy running of each experiments, (v) special visualization routines (e.g. heatmaps) also included the code, (vi) example domains (public and simulated) provided for quick assessment.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, 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 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 novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make 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 large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., 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 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 (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
54

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: (i) full code provided, (ii) extensive README.xt,, (iii) coding choices dis- cussed in Appendix, (iv) all seripts provided for easy running of each experiments, (v) special visualization routines (e.g. heatmaps) also included in the code, (vi) example domains (public and simulated) provided for quick assessment.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
bublic/guides/ wtwps///oooeuuiiiiiooooooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/pips.cc/public/uuiioe htw.bb/lcgggidss/eeeee Sttp://Sooeeeuuuioinnnooo
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if' applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Details are provided main text and Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper level of detail that is necessary to appreciate the results and make sense of them.
The experimental setting should be presented in the
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
standard devs and inferential statistics test done (details in main file + ap- pendix).
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
55

---

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 caleulating 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 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 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA].
Justification: Our code runs on any standard computer. Details of codes, computer and SOTA used (version, etc.) in appendix.
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 (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http::ttts::/t httt:::://nerrrps..cc http///arrp..cccpppaaaacccccaaaa
Answer: [Yes]
Justification:
The research of the paper follows the code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
See conclusion.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
56

---

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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No release of data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Appropriate credit referencesse are provided. Licenses listed in Appendix.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
57

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets provided.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
No research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
58

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
59


Reviews:
[{"review_id": "kLvjFhi9XJ", "reviewer": "Reviewer_kTDz", "summary": "The authors introduce a novel generative model (Generative Forests - GF) for sampling and density estimation, leveraging an ensemble of trees. Their method partitions the input domain by considering all possible intersections of the supports of the leaves across the ensemble, resulting in a much finer partitioning than a single tree could achieve. For each subset of the input domain thus obtained, the model estimates a uniform density based on an empirical training measure. Efficient algorithms for sampling from such a model and evaluating the densities are derived.\n\nTo train the model, the authors propose an algorithm that iteratively splits a selected leaf node in one of the ensemble's trees. This splitting is guided by minimizing a strictly proper loss for a binary class probability estimation task.\n\nThe authors evaluate their method's performance against competing approaches across three main dimensions: the quality of synthetic data generation, missing data imputation, and density estimation.", "questions": "1. In line 218 the authors mention regarding finding the optimal split in $\\text{splitPred}$ that \"the optimisation is no more computationally demanding\" than for decision tree induction. I'm not sure if this is a typo but it seems to me that, as the trees in the ensemble grow deeper, finding the best split could quickly become intractable.\nAs an example, in the case where only single stumps are used, the potential cardinality of $\\mathcal{P}(\\mathcal{T})$ at iteration $j$ is $2^j$ which means that intersections with that many subsets have to be considered when finding the best split point. This seems like an untenable scaling of the computation with the iteration number but maybe I am misunderstanding something about how the best split is selected as the authors' explanation is not clear.\n\n2. Regarding density modelling the authors only compare with KDE. Since ARF also provides density estimates why not compare against this method as well? Additionally [2] could also be worthwhile comparing against.\n\n3. Could the authors clarify what they mean by \"expected densities\" that are used \"to cope with the eventuality of zero (pointwise) density predictions\" in appendix section V.V.3.7? If their proposed model assigns 0 probability to a subset of the domain that has non-zero mass under the data generating distribution I would say that this is a defect of the model and a sign of poor regularization. Changing from the commonly used log-likelihood metric to one that doesn't penalize this so harshly should be surfaced and discussed in the main text in my opinion. Furthermore, it seems that this choice is made on a dataset-by-dataset basis, I can only assume depending on whether the proposed model yields $-\\infty$ log likelihoods which seems to happen for most non-toy datasets. As it stands, these details are hidden in the appendix while the main paper presents a potentially misleading picture based only on #wins.\n\n4. Still regarding 0 density predictions, the authors propose a way to avoid this issue for GFs in line 173. It would be interesting if this was explored further and the resulting (more regularized) density model compared to other approaches for density estimation based on log-likelihood.\n\n[2] Hongwei Wen, Hanyuan Hang. Random Forest Density Estimation, 2022 (https://proceedings.mlr.press/v162/wen22c.html)", "limitations": "I find that the authors hardly discuss the limitations of their method. Most importantly there is little discussion of training times and how they scale with the number of iterations/data dimensions/number of samples. There is also no discussion of how performance and generalization is expected to scale with these factors.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- I find that the paper reads resonably clearly. The language and notation used throughout the paper is very precise although it occasionally appears overly complex.\n\n- The proposed method is interesting and I believe enjoys reasonable novelty.\n\n- The method and theoretical results all appear to be sound.\n\n- The proposed method's ability to estimate densities makes it more versatile than other generative methods commonly used for tabular synthetic data generation. Few methods can match its generality in handling various types of tabular data, except for other tree-based methods like Adversarial Random Forests (ARF). In this context, the positive results presented in comparison to ARF are promising.\n\n- The authors have made their implementation code available.", "weaknesses": "While the authors adequately explain their ensemble tree-based model and its sampling and density computation methods, the explanation of the training algorithm is less thorough. There is insufficient discussion on how the method scales computationally with the number of trees and splitting iterations (see my first question). Additionally, more discussion on the motivation behind the formulation of the CPE task would be welcome.\n\nAccording to the paper's Lemma 4.4, GF estimates a different density value at each non-empty intersection of the supports of each leaf, derived directly from the empirical training measure. This is similar to ARF or other works such as [1] or [2] when using uniform densities at the leaves with the exception that these methods would output an averaged density estimated independently from leaves of each tree in the ensemble.\nIt is unclear why the proposed approach should be better. From a generalization perspective, I would intuitively assume that averaging densities from multiple trees has a regularizing effect compared to using a single tree (see [2]).\nOn the other hand, GF's density estimation is based on a finer partitioning, whose cardinality grows with the product of the depths of all trees in the ensemble. While this could providing greater representational capacity, it would seem to make the method more susceptible to overfitting.\n\nThe theoretical analysis provided also focuses only on approximating this empirical training measure, without addressing overfitting and the approximation of the data-generating measure.\nFor a model such as described above, it seems obvious that the less coarse the partitioning becomes, the more faithfully an empirical distribution can be approximated. I am therefore unsure of the practical significance of these results and I think the paper would benefit more from a discussion of generalization ability.\n\nMy main concern with the paper, however, lies with the evaluation and comparison to other methods:\n- For the many analyses presented in the main paper and the appendices, different methods are compared against and for each method/scenario combination different datasets are used. This lack of consistency in comparisons and datasets in the presented results, leaves an impression that results are missing.\n- The choice of datasets focuses on relatively small numbers of data points and mixes both synthetic toy data and real datasets together. This is compounded by some of the main results being presented only as summary data (#wins/#ties/#losses) over this heterogeneous group of datasets.\n- There is no serious attempt to compare the proposed method with state-of-the-art approaches for synthetic data generation, particularly neural network-based ones:\n    - The comparison is limited to CT-GAN, which has been shown to underperform almost every other popular neural network method, including the TVAE method put forward as a baseline in the same paper.\n    - Additionally, the authors do not tune any hyperparameters for CT-GAN beyond the number of epochs. As a GAN, CT-GAN can have convergence issues, and without proper tuning, it may fail to converge. This lack of tuning undermines the fairness of the comparison, especially since it is unclear how much the authors optimized the hyperparameters of their own method.\n    - The authors also report unusually long training times on a very small dataset, presumably because no GPU is used to train these models and possibly training for too long to no avail. While I understand that the proposed method can be trained on a CPU alone, and maybe that is the point being made, I don't think this remark is made in good faith. In my experience, methods like CT-GAN, TVAE, and TabDDPM can achieve reasonable performance quickly (within minutes to tens of minutes) when trained on a consumer GPU (e.g., 2080) even on larger datasets than those used in the reported experiments.\n    - Results for CT-GAN on the two larger datasets are not reported, so the comparison primarily relies on very small datasets where neural networks might perform worse.\n\n  A comparison with TabDDPM [3], a strong neural network-based generative method, would be valuable, as it is currently a standard benchmark in papers evaluating synthetic data and, in my opinion, a consistent contender for a state-of-the-art method.\n\n- The evaluation of generated samples relies solely on an Optimal Transport distance metric. Although I am not well-versed in the practical computation of this metric, the authors' comment about selecting an entropic regularization parameter that avoids numerical instabilities across all domains is not particularly reassuring. It raises the question of why other metrics were not used in conjunction.\n  - Additionally, the setup described by the authors (GEN-DISCRIM), which uses Random Forests to distinguish real from synthetic data, appears both reasonable and well-founded. I am curious why this wasn't the primary evaluation method for comparing with other approaches. Instead, it is only used to compare GF against optimistic and pessimistic baselines.\n  - On this topic, the authors might also want ot look at e.g., [4] for utility metrics in machine learning tasks that are common in comparing synthetic data generators, although I wouldn't personally fault them if they choose to disregard such metrics.\n\n- Finally, given that the proposed model is able to estimate densities and that evaluating the log-likelihood of held-out data is the gold standard for objectively measuring the quality of such models I don't understand why this evaluation doesn't have a more prominent place in the paper:\n  - The authors only compare their method to KDE, which GF seems to underperform on several datasets, particularly those with a moderate number of dimensions. This is concerning, and I think it is important to investigate how the proposed method scales to higher-dimensional data compared to KDE. \n  - ARF is missing as a baseline in these evaluations which is strange since it is another model that is capable of estimating densities. Additionally, other methods, such as [2], report consistently outperforming KDE, making it worthwhile to include as an additional comparison in my view.\n  - Finally, the evaluation setup is not throughly explained in the main paper and only summary results against KDE are presented. It seems that the authors don't always use log-likelihood to compare these models due to their proposed model predicting 0 density for test samples (see question 3 below). This issue is only mentioned in the appendix but should, in my view, be disclosed in the main paper.\n\n\n[1] Alvaro H. C. Correia, Robert Peharz, Cassio de Campos. Joints in Random Forests, 2020 (https://arxiv.org/abs/2006.14937)\n\n[2] Hongwei Wen, Hanyuan Hang. Random Forest Density Estimation, 2022 (https://proceedings.mlr.press/v162/wen22c.html)\n\n[3] Akim Kotelnikov, Dmitry Baranchuk, Ivan Rubachev, Artem Babenko. TabDDPM: Modelling Tabular Data with Diffusion Models, 2022 (https://arxiv.org/abs/2209.15421)\n\n[4] Lasse Hansen, Nabeel Seedat, Mihaela van der Schaar, Andrija Petrovic. Reimagining Synthetic Tabular Data Generation through Data-Centric AI: A Comprehensive Benchmark, 2023 (https://arxiv.org/abs/2310.16981)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for pointing the soundness, novelty and versatility of our approach. We must confess we found the review a tad offensive at times [kTDz-D] [kTDz-H], accusing us of a *complete lack of seriousness* in some of our experiments, acting *not in good faith* elsewhere, finding *strange* missing parts elsewhere. It is hard to swallow not just because of the language that implies we did not meet ethical standards of scientific papers, but also because it sounds like an *a priori* guilty verdict, that comes even before any explanation of ours. We apologize if our tone sounds \"combative\" at times. \n\nWe proceed in order of the review, with tags to help cross-referencing and navigation. Due to the length of our rebuttal, we put answers to \"questions\" field here and postpone the rest of our rebuttal to additional comments.\n\n## Questions\n\n> In line 218 [...] I'm not sure if this is a typo but it seems to me that, as the trees in the ensemble grow deeper, finding the best split could quickly become intractable. [...]\n\n[kTDz-I] Wrong: to find the best split, we only need to keep those elements in ${\\mathcal P}({\\mathcal T})$ **with $>0$ empirical measure** because the rest has zero measure (and related calculi to find the best split are trivial for all those), so we only have to store those elements with $>0$ empirical measure and their number is limited by the size of the training sample. It has also been implemented this way (please check the commented code, this is the purpose of the class MeasuredSupportAtTupleOfNodes). in addition, as we get deeper, the computation can in fact be much quicker because it also depends on the size of the training sample in the elements to compute the effect of the split, and this size obviously decreases through splitting. \n\nIt is no more computationally demanding than DT induction because then we only need to parse the whole set of training point at the leaf and check whether they go left or right, which is exactly the same procedure as for DT induction. At the end, we need to eventually split the corresponding elements of ${\\mathcal P}({\\mathcal T})$ whose support is included in the leaf, instead of one for a DT, but this cannot represent more than the size of the training sample at the leaf and thus costs in general less than the spltting test, for a global complexity that is still O(DT induction) (we sketch) -- we would be happy to make this more explicit.\n\nSee also [6MHb-A].\n\n> Regarding density modelling the authors only compare with KDE. Since ARF also provides density estimates why not compare against this method as well? \n\nWe hope we answered in [kTDz-H].\n\n> Could the authors clarify what they mean by \"expected densities\" that are used \"to cope with the eventuality of zero (pointwise) density predictions\" in appendix section V.V.3.7? [...] this is a defect of the model and a sign of poor regularization. \n\nIndeed, but this happened with our contender, not our technique: for generative forests, a mechanism prevents this, that we have implemented (see L173-L174) and for ensembles of generative trees (Section IV) this situation is impossible (L672-L673). We can make this more clear using part of the +1 page space.\n\n> [...] As it stands, these details are hidden in the appendix while the main paper presents a potentially misleading picture based only on #wins.\n\nWe agree but this comes as a consequence of (i) us adapting to our contender and (ii) us having to summarize all of this in a short format. See also [kTDz-C]. Since there is +1 page in the camera ready, we would be happy to oblige in moving more details to main file.\n\n> Still regarding 0 density predictions, the authors propose a way to avoid this issue for GFs in line 173. It would be interesting if this was explored further and the resulting (more regularized) density model compared to other approaches for density estimation based on log-likelihood.\n\nApart from indeed implementing this mechanism, we have not, for a simple reason: we did not optimize our models for density estimation because it was a side task (our \"motto\" could be \"*train a generative model, get missing data imputation and density estimation for free*\"). We are however *convinced* that there would be further optimization possible for the density estimation metrics that would most surely get better results (we can elaborate more in the camera ready using the +1 page)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pn67Xc7hFD", "reviewer": "Reviewer_cvp8", "summary": "The paper presents a novel boosting algorithm based on ensembles of generative trees, addressing tasks such as data binary classification, missing data imputation, and density estimation. The proposed algorithm optimizes specific loss functions and leverages the structure of the models to efficiently estimate densities given a generative model and partially specified observations. The authors demonstrate the practicality of their approach through comprehensive experiments, highlighting its effectiveness in binary classification compared to diverse state-of-the-art methods, including their competitors like Adversarial Random Forests (ARF), CT.GAN,  Vine copulas auto-encoders (VCAE) or Kernel Density Estimations(KDE). \n\nThe authors introduce a unique training methodology for these generative models, which is based on class probability estimation (CPE) in binary classification tasks. The loss functions are decomposed into partial losses for positive and negative classes, with the Bayes risk function defined as the optimal achievable loss given a certain positive base-rate. Properness and strict properness of the loss functions are critical properties, ensuring that the loss is minimized when the predicted probability matches the true class probability. The paper discusses various proper losses, such as square loss, logarithmic loss, and Matusita's loss, which are symmetric and differentiable. Furthermore, the paper explores loss functions in the context of density ratio estimation and introduces the likelihood ratio risk for assessing the performance of generative models. Using Bregman divergence and the generalized perspective transform, the authors propose a framework for evaluating the density ratios of different distributions. \n\nThis theoretical foundation supports the practical applications of their models, which show competitive performance over the dataset proposed. The authors carried out experiments on a total of 21 datasets from sources such as UCI, Kaggle, OpenML, and the Stanford Open Policing Project, or simulated datasets. These include datasets like iris, ringGauss, gridGauss, forestfires, tictactoe, ionosphere, student performance, winered, abalone, kc1, sigma-cabs, compas, artificial characters, jungle chess, open-policing-hartford, and electricity, with varying attributes and missing data conditions. The paper concludes that their models, trained with the novel generative tree algorithm, are strong contenders against existing state-of-the-art techniques.", "questions": "In Table 2, the final row displays the wins and losses for us. I am not closely following the numbers as you have already chosen the green one, which includes p-values indicating significance. Another query pertains to comparing the number of trees. It seems unfair to compare T=500 with competitors having fewer trees (10, 50, 100, 200). In simpler terms, I coudn’t comprehend why you mentioned that all these approaches rely on models that are vastly distinct from each other. I know that in the article the authors mentioned that ARFs are trained with a varying number of trees T ∈ {10, 50, 100, 200}. Additionally, ARFs incorporate an algorithm for tree size selection, eliminating the need for manual selection. On the other hand, CT-GANs undergo training with a different number of epochs E ∈ {10, 100, 300, 1000} but I don't follow why these models are then compared with generative forests comprising T = 500 trees and trained over a total of J = 2000 iterations. That approach was done for Table 2 and 4.", "limitations": "The work presented by the authors is highly promising since they have introduced a novel methodology for constructing generative tree models based on class probability estimation (CPE) as a loss function in binary classification tasks. However, the paper would benefit from a dedicated section discussing the current limitations of this method. Specifically, it would be useful to understand whether this approach can be applied with the same efficacy to multiclass classification or, with some modifications, to regression tasks.\n\nAdditionally, it would be valuable to identify the types of tabular data that the proposed method might struggle with or the conditions under which its performance may be suboptimal. For instance, are there specific data types or distributions where this model does not perform as well? A thorough examination of these aspects could enhance the article.\n\nMoreover, while the authors have laid a strong foundation for binary classification problems in their work, constructive suggestions for improvement include providing an analysis or discussion on how the current method could be extended or adapted to handle multiclass classification tasks or regression problems, which would be helpful.\n\nIn that line, another interesting thing could be identifying the specific types of tabular data that might present challenges for the proposed method, which would be beneficial. Under what conditions does the model's performance decline, and what are the characteristics of datasets where this approach is less effective?", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "Regarding to the originality, the paper introduces a novel approach to generative modeling by creating a generative forest based on Class Probability Estimation (CPE). This method represents a significant advancement over current state-of-the-art algorithms. By leveraging ensemble methods and decision tree induction for generative tasks, the paper presents a fresh perspective that has not been extensively explored in the literature. The combination of well-known techniques in a new context adds substantial value to the field and showcases the authors' innovative approach to generative modeling.\n\n\nThe quality of the submission is commendable. The paper is well-organized and meticulously indexed, with a comprehensive appendix that supports the main content. The methodology is robust, encompassing a detailed mathematical explanation, pseudocode for the proposed algorithm, and extensive experimental validation. The authors have tested their model on 21 diverse datasets from reputable sources such as UCI, Kaggle, OpenML, and the Stanford Open Policing Project. This thorough evaluation across various tasks, including data generation, missing data imputation, and density estimation, provides strong evidence of the model's performance and versatility. Additionally, the paper continues the line of research in generative models, building on previous work and demonstrating significant progress in this domain.\n\n\nThe paper is clearly written and well-organized, ensuring that readers can easily follow the authors' reasoning and methodology. The detailed descriptions of the mathematical foundation, the pseudocode, and the experimental setup are particularly noteworthy. These elements allow that an expert can reproduce the results. Furthermore, the inclusion of a comprehensive appendix adds to the clarity by providing additional details without cluttering the main text.\n\n\nThe results presented in the paper are of high value.  In that line, the authors have made a commendable effort by comparing their method with the closest approaches (ARF, copycat) cited in [42] and [29]. Furthermore, they have clearly outlined the distinctions and enhancements of their algorithm in comparison to these approaches.\n\nThe authors suggest that generative forest can effectively eliminate \"the slack\" when utilizing decision trees as discriminators. This implies that decision trees exhibit a more regulated and foreseeable behavior in contrast to neural networks. Decision trees are inherently more calibrated and provide more deterministic outcomes. As a result, the feedback they provide to the generator during training is more accurate and reliable. The proposed method seems to enhance binary classification performance compared to existing approaches and also addresses challenging tasks such as missing data imputation and density estimation. The model's ability to produce competitive results across a diverse array of datasets and tasks underscores its potential impact on both the research community and practical applications.", "weaknesses": "In section 1, the authors delve into the use of generative AI in the ML community and highlight two significant features of their generative forest. They emphasize its simplicity and the strong convergence guarantees it offers in a weak/strong learning model, akin to Valiant’s PAC learning boosting model. However, it remains unclear whether this generative forest, based on Class Probability Estimation (CPE), can effectively handle multiclass scenarios.\n\nSection 3 introduces the supervised loss for the generative tree. Nevertheless, from a synthesized perspective, the drafting in line 75 lacks clarity. The authors should consider enhancing the clarity of these lines.\n\nMoving on to Section 4, in line 125, the authors refer to 'c', but it is not clearly connected to the context provided in the text.\n\nRegarding the supplementary material, Table A3 is challenging to read as the footnotes overlap with the image.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for noting that our approach \"[...] presents a fresh perspective that has not been extensively explored in the literature [...]\" and noting that the quality of our submission is commendable.\n\n## weaknesses\n\n> In section 1, [...]\n\n[cvp8-A] we assume the reviewer wants to know if our models can tackle supervised learning with multiclass problems in the context of class probability estimation. The answer is yes, and it just resorts to the fact that our generative models can easily provide the full distribution of missing values given the observed ones and the generative model. Indeed, supervised learning is \"just\" missing data imputation where the class label is missing and the full distribution we obtain, in this case, is the complete Bayes rule estimates for $P[Y=c|X]$ (where $c$ ranges in any set, thus allowing multiclass). Note that we can do something \"slicker\" than supervised learning when additional variables are missing because in this case, we get the complete estimates for $P[\\mbox{all missing variables} = \\mbox{set of values}|\\mbox{observed variables}]$. The pointwise max for the set of values necessarily contains a prediction for the class.\n\n> Section 3 introduces the supervised loss for the generative tree. [...]\n\n[cvp8-B] we would definitely be happy to use part of the +1 camera-ready page to expand on this part as it grounds our approach in the supervised learning framework.\n\n> Moving on to Section 4, in line 125, [...]\n\n[cvp8-C] we agree. In fact part of the hardness probably comes from the fact that we did some \"acrobatic\" implicit referencing to save space: (C) is used before in lines L119+. Same as for [cvp8-B], we believe we can use part of the +1 page to polish this.\n\n> Regarding the supplementary material, Table A3 [...]\n\nIndeed !! We apologize (this will be fixed), the obfuscated line is: \n\n\"Table A3: 2D density plots ( Generative forests x = Life Style Index and y = Customer Rating) for data generated on sigma_cabs, from models learned with 5% missing features [...]\"\n\nIt is important because sigma_cabs is a real-world domain and some features appear to be \"trickier\" to generate than others.\n## questions\nWe directly reply here to the list of concerns. \n\n[cvp8-D] First, ARF have fewer trees *but* they are much bigger than ours (the technical reason being that to get a good model overall, each tree needs to be a good model of its own already, because the distribution learned is a convex combination of tree's -- get one wrong, and the overall model can be heavily penalized). In fine, their total number of splits is equivalent or bigger than ours. We propose to indicate the average total number of splits as well for ARF.\n\n[cvp8-E] \"[...] Additionally, ARFs incorporate an algorithm for tree size selection, eliminating the need for manual selection [...]\" Correct ! As we say in L311-L312, we do not have one in this paper. Such a matter would deserve a work of its own. However, the blueprint of such an algorithm seems intuitive: get inspiration from pruning algorithms in supervised decision tree induction.\n\n\"On the other hand, CT-GANs [...]\" We understand that the reviewer points out that some parameters look like pears and apples. It is true and we accept the criticism: we deliberately wanted to compare techniques coming from many different model types [ALL]. It then came as a constraint to figure out some good model parameters to train for the contenders: in the case of KDE, we kept the kernel that gave overall the best results on our datasets; we tried to use a number of epochs that looked sound for the datasets that we had in CT-GANs, etc. . This explains why we give several different results for our contenders, in order not to \"fix arbitrary\" values.\n\n## limitations\n\n> The work presented [...] multiclass classification [...] regression.\n\nOur method can indeed cope with supervised learning and this comes from the abilities of our models [cvp8-A]. **However**, this would represent a fourth task and we are not sure this represents a limitation of our work, which already contains experiments on 3 different tasks (no paper cited by the reviewers addresses this many tasks). Probably worth adding in a work of its own on [cvp8-E] ?\n\n> Additionally, it would be valuable to identify [...] proposed method might struggle with [...]\n\n[cvp8-F] We agree. We did not do it because we strongly suspect from our experiments that more than \"hard\" datasets, there is actually an eventually suboptimal choice of our parameters $J, T$. By deliberately choosing those from a very small set in our experiments, we accepted the eventual suboptimality of some of our results. We did not want to hypertune our method and we believe there is a simple path forward, which would then be useful to guess eventual hard datasets: first solve the pruning problem [cvp8-E]. We are happy to elaborate more on this in the +1 page.\n\n> Moreover, while the authors have laid a strong foundation [...]\n\nWe refer to [cvp8-A] on this.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ITR8yUxhCn", "reviewer": "Reviewer_uJTo", "summary": "The paper proposes a generative model based on an ensemble of trees (forest) for tabular data. The proposed model enjoys the following peculiar properties:\n1. Compared to generative models based on a single tree, it offers improved **expressiveness** in terms of partitioning the input space (linear for generative trees vs. polynomial for generative forest in terms of decision nodes in a tree).\n2. The model offers **unbiased** density estimation for sufficient large capacity, thanks to the fact that each node in each tree leverage decisions in proportion to the empirical distribution.\n3. Learning the structure of the trees is performed by minimizing an objective function based on the likelihood ratio risk. \n4. Computationallly speaking, data generation and density estimation can be performed in **parallel** with respect to the different trees. Indeed, results can be aggregated a posteriori by taking the intersection of selected regions.\n5. Apart from **data generation** and **density estimation**, the model can be extended to deal missing data and perform **data imputation**.\n\nExperiments are conducted on a series of tabular datasets from the UCI repository. The proposed solution is shown to outperform/being on par with existing tabular data generation (the most relevant being adversarial random forests), data imputation (e.g. MICE) and density estimation baselines (e.g. kernel density estimation).", "questions": "Overall, I like the extension of generative trees to ensembles. I’m willing to raise my score if all weaknesses are addressed during the rebuttal phase.", "limitations": "There are no additional suggestions.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The problem of learning a good generative model for tabular data is relevant **Relevance**\n2. The solution based on a tree ensemble represent a significant advance over solutions based on a single decision tree  **Significance**.\n3. The proposed model offers the possibility to tackle three different tasks, including density estimation, data generation and data imputation. Moreover, experiments demonstrate the efficacy of the solution when compared with corresponding baselines for each task **Significance**.\n4. The theory of the paper seem correct, however I haven’t gone through the proofs **Correctness**\n5. Code is available at the time of submission. No additional check has been conducted to verify the reproducibility of the results **Reproducibility**", "weaknesses": "1. One of the major concerns is with the novelty of the proposed solution **Novelty**. What is the relation with the work in [1]? The work in [1] is also providing a model able to tackle the three above-mentioned tasks. Would it be possible to provide a comparison?\n2. The paper is sometimes overloaded by unnecessary formalism, rendering the text hard to follow **Clarity**. For instance,\n    1. Line 92-109, why is the whole theory about risk minimisation for binary classification introduced, when the goal is to perform density estimation? Would simple likelihood learning suffice?\n    2. Definition of tree. “…labeled with subsets of their tail node’s variable domain”. Do you mean “”labeled with subset of attribute value for the corresponding variable?\n    3. Line 160-163. Can you make an example or in case leave out the sentence? Am I correct to say that the permutation invariance property is due to the final intersection operation or am I missing something?\n    4. Algorithm 3 in Step 2.1 How is node selection performed, uniformly at random? Moreover, can you provide some more details about the resulting trees, are they balanced?\n    5. Can you elaborate on the motivation of proving theorem 5.2 and discuss the significance of its results or link with the results in the experiments?\n3. All experiments are conducted on datasets with less 34 variables **Soundness**. Would it be possible to provide some comparisons with [1] on larger dimensional datasets (see the reference for example) and/or discuss the computational requirements?\n\n**Reference**\n\n[1] Generating and Imputing Tabular Data via Diffusion and Flow-based Gradient-Boosted Trees. AISTATS 2024", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for organising the review in a very clean way that allows for easy referencing, tagging two **significant** key strengths on which we elaborate further below, and being clearly open for discussion. We use W.X.Y to refer to the weakness section.\n\n> W.1 \"One of the major concerns [...]\"\n\nThere are two parts to this question, a technical one (relationship to [1]) and experimental (comparison with [1]).\n\n- technical part: [1] is based on diffusion models while we rely on stochastic generation, so the approaches are radically different (they solve ODEs for data generation, we essentially \"just\" sample Bernoulli random variables, see our algorithm starUpdate). We thank the reviewer for this reference as it in fact provides us with a contender type that is radically different from all our contenders (not just our method) [ALL]. \n\nAt this point, we would like to highlight a key difference with [1]: [1] has no formal analysis of the algorithm: no convergence / consistency result of any kind. Experimental results are important to tell the story but a good theory gives the backbone. Among all references pointed by all reviewers,  none provides rates of convergence. We do. We also emphasize that it is not complicated to show a consistency result in our case [kTDz-A2].\n\n- experimental comparison: the reviewers provided overall a number of potential additional contenders. Assuming a consensus emerges around our proposition in [ALL], we would be happy to provide an additional comparison with [1] on data generation, hoping our experimental section will remain readable using the +1 page of camera ready (we would not compare on missing data imputation as [1] make it explicit that they do worse than MICE and we are competitive).\n\n> W.2.1 \"The paper is sometimes overloaded by unnecessary formalism [...] Line 92-109, why is the whole theory [...]\"\n\n[uJTo-A] The formalism we introduce is necessary because we manage to train a generative model using the framework of supervised learning and our algorithm heavily relies on the loss definitions mentioned. Furthermore, the loss *properties* are also important because, it turns out, our convergence results are more general than those of [29]. Those definitions make the \"slack\" explicit. We are confident we can make the section \"breathe\" using part of the +1 page camera ready.\n\n> W.2.2 \"Definition of tree [...]\"\n\nCorrect. We can paraphrase.\n\n> W.2.3 \"Line 160-163. Can you make an example or in case leave out the sentence\"\n\nIt is correct *but* the sentence should remain because it grounds the proof (not given) of Lemma 4. We can add the reviewer's remark and merge it.\n\n> W.2.4 \"Algorithm 3 in Step 2.1 How is node selection performed, [...]\"\n\nWe choose the heaviest leaf among all trees (the one with the largest empirical mass in its support). In the code, it is method choose_leaf of class Algorithm.\n\n> W.2.5 \"Can you elaborate on the motivation of proving theorem 5.2 [...]\"\n\nThis is an empirical convergence rate under the weak learning assumption in the boosting framework. To summarize its importance, this has been the cornerstone of boosting algorithms since Valiant's weak/strong model and since Schapire's first proof that boosting is achievable in the model (1990). Such a result is thus fondamental: it shows an explicit rate under assumptions that are so \"weak\" that not satisfying them would just preclude learning (in the supervised setting, which is easier to state, failing the weak learning assumption would mean getting updates no better than a fair coin, thus indeed totally useless to learn). Kearns and Mansour in [18] summarize very well the importance of boosting in the context of decision tree induction, which is close to our setting. The first sentence of the abstract of the popular paper \"Additive logistic regression: a statistical view of boosting\", Friedman, Hastie and Tibshirani summarizes the importance of boosting as we just explained: \n\n**\"Boosting is one of the most important recent developments in classification methodology.\"**\n\n> W.3 All experiments conducted on datasets with less 34 variables [...] comparisons with [1] on larger dimensional datasets [...]\n\n[uJTo-B] (we correct: it is less than 35) We would be happy to do so, see [ALL], but note that among all datasets of [1], only 3 out of 27 have more than 35 features (we can use those ?).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JWISzq4NFd", "reviewer": "Reviewer_6MHb", "summary": "This paper introduces generative forests (GF), a new class of generative models designed for tabular data and based on sets of trees (forests), and a training algorithm called GF.BOOST. The algorithm is designed to be simple, making it easy to implement with minor modifications to existing CART-style decision tree induction schemes. \n\nThe GF models and GF.BOOST algorithm are evaluated across various domains, demonstrating their capability in tasks such as data generation, missing data imputation, and density estimation. The results show that even a small number of trees within a generator can be effective, highlighting the potential of the proposed approach in handling tabular data.", "questions": "- How computationally efficient to compute Eq. 4? From my understanding it is used for splitting a tree\n- Is there any mechanism to prune some trees in a forest (reduce T)? Traditional tree boosting builds trees sequentially, so there is opportunity for early stopping. I was wondering how critical here to have predefined T...\n- Is there any separate ablation how well this method works for categorical features?", "limitations": "- there seems to be some limitations in convergence analysis (e.g. symmetry of l). \n- otherwise, having separate (sub)section on limitations would be nice (e.g. runtime compared to traditional boosting methods).", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- I believe the paper is a nice addition to the ML community. Prevailing methods in data imputations for DTs are based on heuristics and tricks, whereas this paper approaches this problem with sounding probabilistic point of view, which makes a lot of sense to me. This naturally leads to the ability of generating more data, which may have serious implications in synthetic data generation literature. \n- The method is relatively easy to implement and can be done by straightforward extension of CART-style tree induction methods.", "weaknesses": "- Experiments section may need some improvements:\n     - Most datasets in Table 2 (which seem to be the main results table) are standard ML benchmarks. It would be really nice to have real-world kaggle-style datasets with missing values and compare with strong baselines therein.\n     - Adding traditional forests is also necessary to compare against established methods (xgboost, lightgbm, etc.)\n\n- I find most of the math notations hard to follow and can be significantly simplified.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for noting the importance of our formal contribution !\n\n## weaknesses\n\n> It would be really nice to have real-world kaggle-style datasets with missing values\n\nActually, sigma-cabs is a Kaggle dataset with missing values. Stanford Open Policing is not Kaggle but it also has missing values and is real world (see our Table A1). We understand the reviewer would like to have a few more ? Perhaps we can use [uJTo-B] ?\n\n> Adding traditional forests is also necessary to compare against [...]\n\nWe understand the reviewer would like us to add tests on supervised learning. We kindly refer to [cvp8-A] for a discussion on this matter.\n\n> I find most of the math notations hard to follow and can be significantly simplified\n\nWe attribute it to the fact that our approach is purely grounded in a supervised learning framework, which is indeed seldom for generative models. We refer to [cvp8-B][uJTo-A] for discussions on these and their importance; we would use part of the +1 camera ready to hopefully bring improved explanations.\n\n## questions\n\n> How computationally efficient to compute Eq. 4? \n\n[6MHb-A] Great question. We only need to keep those elements in ${\\mathcal P}({\\mathcal T})$ **with $>0$ empirical measure** because for all others their contribution to (4) is zero, so the complexity is linear in the size of the training sample (we cannot have more elements in the set). We also refer to [kTDz-I] for side remarks on the code we provide.\n\n>  Is there any mechanism to prune some trees in a forest (reduce T)? \n\nGreat question: as we say in [cvp8-E], there surely is, but it would deserve a paper of its own (we are talking about a pruning mechanism with provable properties). \n\n> I was wondering how critical here to have predefined T... [...]\n\nWe refer to [cvp8-F] for a similar discussion and the reason why we did not \"hypertune\" our parameters $T,J$.\n\n> Is there any separate ablation how well this method works for categorical features?\n\nWe would be happy to get additional context on this question -- does the reviewer think about testing \"all features\" vs \"only numerical features\" to test how much categorical features contribute to the model quality ? (note that we would have to push it to the appendix, see [ALL])\n\n## limitations\n\n> there seems to be some limitations in convergence analysis (e.g. symmetry of l).\n\nThis is in fact a limitation of a previous paper [29], limitation that we *remove* in our analysis, which is thus more general (see L497, that we can put in the main file using the +1 camera ready page)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5W4pgd3NF1", "reviewer": "Reviewer_Sk9u", "summary": "This paper proposes a generative model for tabular data based on a forest of trees. It is evaluated on the quality of the generated samples (using an optimal transport based distance to a held out test set), on data imputation and density estimation.", "questions": "What is the computational cost for training and inference compared to Generative Trees? (It would be interesting to provide wall-clock times)\n\nHow are the parameters chosen (number of trees, number of splits, ...)?", "limitations": "See questions", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Generative modeling for tabular data is an important research topic, and exploiting the strengths of trees (ubiquitous in this modality) for this generative task is a promising direction.\n\nThe framework inherits the flexibility of boosting, and the theoretical results (under weak learning assumptions) provide guarantees that the underlying distribution can be approximated well enough with enough trees.", "weaknesses": "Further empirical comparison could be conducted. For example, recent works have applied diffusion for tabular data (Kotelnikov et al.) as well as flow matching (Jolicoeur-Martineau et al.). It might be worth comparing to these more recent approaches.\n\nFurthermore, more metrics could be included for the LifeLike experiment to provide more nuanced results. See Jolicoeur-Martineau et al. for examples of such metrics.\n\nReferences:\n\nKotelnikov, A., Baranchuk, D., Rubachev, I., & Babenko, A. (2023, July). Tabddpm: Modelling tabular data with diffusion models. In International Conference on Machine Learning (pp. 17564-17579). PMLR.\n\nJolicoeur-Martineau, A., Fatras, K., & Kachman, T. (2024, April). Generating and imputing tabular data via diffusion and flow-based gradient-boosted trees. In International Conference on Artificial Intelligence and Statistics (pp. 1288-1296). PMLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to especially thank the reviewer for singling out the importance of boosting and our theoretical framework and results\n\n## weaknesses\n\n> Further empirical comparison could be conducted. [...]\n\nWe could be happy to do so, but kindly note that at this stage we have received criticisms that we cram a lot of experimental stuff in a small allotted space [kTDz-C]. Furthermore, our paper investigates three (3) different experimental settings on which we already have five (5) contenders (in fact 6 if we count the generative trees of [29], and even more if we consider \"copy\" to be one in our GEN-DISCRIM experiment, Section V.V.3.5); finally, the reviewers altogether suggest to add *five* (5) more contenders, in different parts of our three settings. As we write above [ALL], we would like to keep a good balance theory / experiments and so it would be important for the reviewers to get to a consensus on an additional experiment that we could detail as part of the +1 page. We make a suggestion in [ALL] that would be easy to carry out during camera-ready preparation and which rejoins the reviewer's suggestion.\n\n> Furthermore, more metrics could be included for the LifeLike [...]\n\nGood suggestion but kindly keep in mind that this would induce more space to allocate in our paper (see above). We suggest adding Grower and coverage in the appendix for our method and all our LifeLike experiments. Kindly note also that out of the many metrics in Jolicoeur-Martineau et al., an optimal transport distance is the only one that provides a statistically meaningful comparison at the distribution level (see [kTDz-F]). Jolicoeur-Martineau et al. use Wasserstein's metric, which is computationally expensive and prevents them from computing it on medium+ sized datasets (Cf their section B.2.2); we use a regularized version, now very popular since Cuturi [8], that still bears OT properties and is sufficiently fast that it could be computed on all our datasets even on our \"Low-end\" laptop.\n\n## questions\n\n> What is the computational cost for training and inference compared to Generative Trees? (It would be interesting to provide wall-clock times)\n\nIt is more computationally demanding than generative trees (GT's) for a single reason: when testing a split at a leaf, we have only one support to split in a GT (that corresponding to the leaf) while in a generative forest (GF), we need to test the splitting of all supports in ${\\mathcal P}({\\mathcal T})$ that are included in the leaf's. Note that this has a positive side: we can train much smaller GFs compared to GTs. So somehow we are slower with GFs but end up training models with less splits to get to the same quality. We could put times but such a question entails a broader one on our contenders and this could be sensitive [kTDz-F]. Note also that we have used a \"low end\" laptop and a \"medium+ end desktop\" for our experiments, *but* we have systematically trained our models on the laptop. It was deliberate as we wanted to make sure we could learn such models on a \"simple\" device. In this context, we are not sure we would not end up comparing peers and apples when it comes to times. At least we can propose to put the training times of our method for all our experiments, with a clear explanation of how / why we did so in a \"low-end\" laptop (and in the appendix) ?\n\n> How are the parameters chosen (number of trees, number of splits, ...)?\n\nWe deliberately did not optimize / hypertune these parameters, in order not to factor the \"human tuning\" in the explanation for the quality of our models (keep in mind we have three experimental settings), so we just picked informed guesses that would also represent fast enough training, see kTDz-E] [cvp8-F]. The other reason we have not done this is because we are convinced there is an automatic method to find the \"right\" parameters, which comes down to pruning our models, see [cvp8-E]. This of course would require a work / paper of its own.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
## To all reviewers

[ALL] We warmly thank all reviewers for their work and for all granting our paper with general "good or excellent" contribution field. Many questions have been asked and we take it as a value found that so many contenders were proposed, added to the five (5) we already have (in fact, 6 if we include the generative trees of [29] -- ref in our paper, and 7 if we add COPY in gen-discrim) for our three (3) distinct experimental settings (TVAE, TABDDPM, ARF-FORDE, RFDE, Forest-Flow). We hope it is obvious that it would be hard to cram substantially more content in our paper as it has already been remarked that its current state can already be hard to parse at points in the experiments [kTDz-C]. However, since there is a +1 page in the camera-ready we propose to add Forest-Flow, because it is another kind of model that does not belong to the categories of the models we have compared against (mixing elements of trees, neural nets, kernels or graphical models). However, the paper on Forest-Flow clearly mentions that their results are worse than MICE on missing data imputation. Since we are competitive with MICE, we would be happy to instead compare on data generation with Forest-Flow.

We would like to stress the need to *keep* the current formal part to its current state and not reduce it: for example, none of the papers cited by all reviewers have convergence rates on training. We also would like to add a few comments on the statistical consistency of our method [kTDz-A2].

Tags like [ALL], [kTDz-C] have been put for easy search in the page's content.

Meta-review: The authors propose a tree-based method as a generative model for tabular data. 

- **Reviews**: Initially, the paper received two very positive and three more critical reviews. Points of criticism were novelty, clarity, missing technical details, and the selection of experiments. 
- **Rebuttal**: The authors were able to convince also the rather critical reviewers by clarifying misunderstandings and providing numerous new experimental results. 
- **Decision**: While I recommend acceptance, it should be noted that scores negatively correlate with confidence. The reason, as also pointed out by Reviewer `uJTo`, likely is that the simplicity of the approach is sometimes hidden behind overcomplicated mathematical concepts. At the very least, the authors should simplify notation and improve the paper's readability in the camera-ready version.
Decision: Accept (poster)