Coresets for Decision Trees of Signals
Authors: Ibrahim Jubran
Ernesto Evgeniy Sanches Shayda
Ilan Newman
Dan Feldman
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Coresets
Machine Learning
Decision Trees
Random Forests

Abstract: A $k$-decision tree $t$ (or $k$-tree) is a recursive partition of a matrix (2D-signal) into $k\geq 1$ block matrices (axis-parallel rectangles, leaves) where each rectangle is assigned a real label. Its regression or classification loss to a given matrix $D$ of $N$ entries (labels) is the sum of squared differences over every label in $D$ and its assigned label by $t$.
Given an error parameter $\varepsilon\in(0,1)$, a $(k,\varepsilon)$-coreset $C$ of $D$ is a small summarization that provably approximates this loss to \emph{every} such tree, up to a multiplicative factor of $1\pm\varepsilon$. In particular, the optimal $k$-tree of $C$ is a $(1+\varepsilon)$-approximation to the optimal $k$-tree of $D$.

We provide the first algorithm that outputs such a $(k,\varepsilon)$-coreset for \emph{every} such matrix $D$. The size $|C|$ of the coreset is polynomial in $k\log(N)/\varepsilon$, and its construction takes $O(Nk)$ time.
This is by forging a link between decision trees from machine learning -- to partition trees in computational geometry. 

Experimental results on \texttt{sklearn} and \texttt{lightGBM} show that applying our coresets on real-world data-sets boosts the computation time of random forests and their parameter tuning by up to x$10$, while keeping similar accuracy. Full open source code is provided.

Coresets for Decision Trees of Signals
Ibrahim Jubran
Ernesto Evgeniy Sanches Shayda Department of Computer Science University of Haifa, Israel ernestosanccess@gaall com
Department of Computer Science University of Haifa, Israel Jbrahim.jubugnan com
Πlan Newman
Dan Feldman
Department of Computer Science University of Haifa, Israel i llandes. haifa.ac.
Department of Computer Science University of Haifa, Israel dannyf. post@gmail......... com
Abstract
A k-decision tree /. (or k-tree) is recursive partition of a matrix (2D-signal) into & 2 block matrices (axis- eaxis-parallel rectangles, leaves) where each rectangle assigned a real label. Its regression or classification loss to given matrix D of entries (labels) is the sum of squared differences over every label D and its assigned label by t. Given error parameter E (0, 1), (k, e)-coreset C of D is a small summarization that provably approximates this loss to every such tree, up multiplicative factor of 1 + E. In particular, the optimal k-tree of C' is a (1 + E) aaaaprooxmmation to the optimal k-tree D.
We provide the first algorithm that outputs such (k,,))coreset for every such matrix D. The size |C| of the coreset is polynomial in i log(N)/e, and its con- struction takes ( k) time. This is by forging link between decision trees from machine learning to partition
in computational geometry.
Experimental results on sklearn and lightGBM show that applying our coresets real-world data-sets boosts the computation time of random forests and their parameter tuning by up to x10, while keeping similar accuracy. Full open source code is provided.
Introduction
Decision trees are one of the most common algorithms used in machine learning today, both in the academy and industry, for classification and regression problems [52]. Informally, decision tree is recursive binary partition of the input feature space into hyper-rectangles, where each such hyper-rectangle is assigned label. the labels are given from discrete set, the trees are usually called classification trees, and otherwise they are usually called regression trees. Variants include non-binary partitions and forests 229
Why decision trees? Advantages of decision trees, especially compared to deep learning, include: (i) Interpretability. They among the most popular algorithms for interpretable (transparent) machine learning [31]. (ii) Usually require small memory space, which also implies fast classification time. (iii) Accuracy. Decision trees are considered as one of the few competitors of deep networks, In competitions, such as the ones in Kaggle (36), they are one of the favorite classifiers [10], especially on small traditional tabular data. (iv) May learn from small training data.
The goal is usually to compute the optimal k-tree t" for a given dataset D and a given number & of leaves, according to some given loss function. In practice, researchers usually use ensemble of trees called forests, e.g., a Random Forest [2], which are usually learned from different subsets of the
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

10
5
2
3
4
Decision
depth:s
3
4
2
1
4
4
4
3
Tree
5
-1
-3
3
2
5
-2
-2
Regression
3
5
-2
-2
4
3
5
10
10
10
10
5
5
1
4
1
1
Figure 1: (Left); A one dimensional signal (orange points) and its segmentation into 25 "smooth" segments / leaves (green lines), Image taken from Section 1.10 ("Decision Trees") of the sklearn's User Guide [56]. The vector on top represents a subset of the signal's values. The bottom vectors represent 4-segmentation
v, similar to the horizontal green line segments. Each segment contains the average value of its corresponding segment from v. (Middle): A matrix that represents the 4 x 5 signal D = (((1,)))))))))))))).
((1.2 2), 4), (11,3) 5). ...} (in black) and a 3 x matrix that represents a 3 x 2 sub-signal B {((1,)) 2). 4). ((1,3), 4), ((2, 3). (in purple). (Right): A matrix that represents 5 5-segmentation 8 of A = [4] x [5]: see Definition| [ Since s is a 5-segmentation, partitions the [4] x [5] matrix into 5 distinct block matrices B1 (red), B2 (blue), B3 (yellow), Ba (green), and Bs (black) such that s assigns the same number for all the entries in the same block. The every entry in the left matrix to its corresponding entry on the right matrix. Also, there is no k-tree that can obtain the same partition.
SSE fitting loss (D,s) s) is the sum of squared differences
training set. The final classification is then based on a combination rule, such as majority or average vote. Since both the training and classification of each tree are computed independently and possibly in parallel, we focus on the construction of a single tree.
A dataset D in this paper is set D {=1, y1). ..... (xN, UN)} S A x R of pairs, where A is the feature space. Each pair (z, y) E consists of a database record (vector / sample) x E A and its real label y R. As common, converted to real numbers; see c.g. [27]. For example, in common classification problems A = Rd for some d and y E (0, 1) is binary number. The resulting model may be used for prediction on another test dataset, completion of missing values, or efficient storage of the original dataset by replacing the label of each pair (a., v) E D with the label (xx) that was assigned to it by the tree t. The last technique is used e.g. in the MPEG4 encoder [46). where decision trees of a specific structure (quad-trees) are used compress an image D that consists of -rayssae pairs (Ir, y).
assume that non-real features, such as categorical features,
Challenges. The motivation for this paper originated from the following challenges:
(i) Sub-optimality. Hardness of decision tree optimization is both theoretical and practical obsta- cle [31]. NP-hard to compute the optimal k-tree, or its approximation, when the number is not fixed 14 39] There were several attempts to improve the optimality of decision tree algorithms,, from binary-split decision trees as in 6, 8] in a line of work e.g. ( 61.. Nevertheless, greedy implementations e.g., CART [40] and C4.5 (5T) have remained the dominant methods in practice. (ii) Computation time. Due to this lack of optimality, finding a decision tree that provides a good accuracy usually requires many runs, since each of them returns only local minimum that might be arbitrarily far from the global optimum. The final model usually consists of a forest containing many trees. Popular forest implementations include the famous Sklearn, XGBoost, LightGBM, and CatBoost libraries 49 15 37 19), which all utilize (as default) an ensemble of at least 100 trees. Moreover, there is a list of dozen parameters calibrate including: number of trees, depth of each tree, pruning/splitting strategies on each tree and between them, and many others. To this end, the running time for obtaining reasonable results even on moderate size datasets might be impractical. (iii) Scalability. Existing techniques tend not to scale to realistically-sized problems unless simplified to trees of a specific form as stated in (31] (iv) Streaming, parallel, and dynamic updates. The common algorithms mentioned above do not support continuous learning or updating of the modeled tree when an input sample is either added or removed from the dataset, e.g., when the dataset does not fit into memory arrives on-the-fly. Similarly, we do not know techniques to train single tree parallel on multiple machines.
1.1 Coresets
"Coresets are one of the central methods to facilitate the analysis of large data sets." 47 Informally, for an input dataset D, a set of models, an approximation error e E (0, 1), and loss function l, coresct C' is data structure that approximates the loss {(D, t) for every model E T. up to

---

multiplicative factor of 1 + E, in time that depends only on |C]. Hence, ideally, C' is also much smaller than ther original input D.
Why coresets? The main motivation for constructing a coreset is to compute the optimal model or its approximation, much faster, while sacrificing little accuracy. Furthermore, a coreset for family of classifiers is many times a "silver bullet" that provides a unified solution to all Challenges (i)-(iv) above. Combining the two main coreset properties: merge and reduce [32 26 [ which
are usually satisfied, with the fact that a coreset approximates every model, and not just the optimal
model, enables it to support streaming and distributed data []]
parallel computation 21 handle
constrained versions of the problem 25 model compression 20 parameter tuning
and more.
Coreset construction techniques. There are many different techniques for coreset construction, ranging from loss-less to lossy, from deterministic to randomized, and from greedy to non-greedy con- structions. Examples include accurate coresets (33 and non-accurate coresets 2X] via computational geometry. random sampling-base
coresets [22 17
and greedy deterministic coresets via the
Frank-Wolfe algorithm [16]. Recently, many works focus on developing frameworks for general fam-
ilies of loss functions, e.g.. (22 57). We refer the interested reader to the surveys [2] I 50
with references therein.
Practical usage. Since a coreset is not just another solver that competes with existing solutions, but a data structure for approximating any given model in the family, algorithms or heuristics on the coreset to obtain similar results compared to the original (full) data. Since the coreset is small, we may run these heuristics multiple times, or apply the hyperparameter tuning using the coreset 43 thus reducing the computational burden by orders of magnitude.
apply existing approximation
(i) No coreset. Unfortunately, it is not clear at all that small coreset exists for a given family of models. In fact, we can conclude from [54] that a coreset for decision trees does not exist in general; see details below. In this case, we can either give up the coreset paradigm and develop a new solver, or add assumption on the input dataset, instead of targeting every possible dataset that may be very artificial and unrealistic, as the counter example in [54]. In this paper, choose the latter option. (ii) Unlike, say, uniform sampling, every problem formulation requires a different coreset construction, which may take years of research to design.
Main challenges:
1.2 First coreset for decision frees and their generalization
In this paper, we tackle generalized and more complex set of models than decision trees, where, rather than recursive binary partition, we allow the input feature space Rd to be partitioned into any disjoint axis axis-parallel hyper-rectangles; see Fig. [ This generalization is essential order to support future non-recursive and not necessarily binary classification models, e.g., ID3 and C4.5 30 51). To our knowledge, this is the first coreset with provable guarantees for constructing decision trees.
Definition 1 (k-seegenttation), For integer d 2 1 that denotes the dimension of the feature space A = Rdd and an integer k 2 1 that denotes the size of the partition (number of leaves), a function A R. is a k-segmentation axis axis-parallel hyper-rectange assigns unique value for all the entries in each of its k rectangles; see Fig. [ We define the union over all possible such k- k-segmentations by SEG
there is a partition B { ,BB) of A into k disjoint (blocks), such that {s(b) b B) = for every block B E B, iee
We now define our loss function, and an optimal k-segmentation model over some set A C Definition 2 (Loss function). For a dataset D = [z v1), (IN,yN)} C A x R, an integer k Z 1, and k-segmentation E SEG(k,d) we define the sum of squared error (SSE) loss
((D,s) = Σ (s(x) - y)²
(2,0)DD
as the loss of fitling to D. A k-segmentation 8" is an optimal k-segmentation of D if minimizes E(D, s) over every k-segmentation s E (EG ie., s E arg min, ((D,s). s). The optimal SSE loss is denoted by opt, (D) == ((D.s*).
For example, the optimal 1-segmentation s* of D the constant function s* Do EiewED y since the mean of a set of numbers minimizes the sum of squared distances to the elements of the set, Also, opt (D) 0 for every dataset D.
3

---

We are now ready to formally define a coreset for the k-segmentation problem (and dedesisoon trees of at most & leaves, in particular).
Definition 3 (Coreset). Let D = ((11, (Fm. S A x R be an imput dataset. Let k 2 1 be an integer and (0, 1) be the desired approximation error. A (k, -coreese for D is a data structure (C, u) where C C A x IR is an ordered set, and u. : C + [0, 00) is called a weight function, such that (C, u) suffices to approximate the loss E(D.s) of the original dataset D, up to multiplicative factor of + in time that depends only on |C] and k. for any k-segmentation s.
Practical usage. As defined above and discussed in Section 1.1 a coreset approximates every model in our set of models (kG Hence, a coreset for decision trees is clearly also a coreset for forests with an appropriate tuning for k. since every tree in the forest is approximated independently by the coreset. We expect that applying existing heuristics (not necessarily with provable guarantees) such as skleam [49] or LightGBM (37 on the coreset, would yield similar results compared to the original data. Indeed, our experimental results in Section [ validate those claims.
No coreset for general datasets. Unfortunately, even for the case of k = 4 and A C RR i.e., when the input is simply a one dimensional dataset D = { U1), ..... (In, yn)) where I1,' , In are real numbers, and the labels y1.- Vn E {0. 1} have only binary values, it is easy to construct datasets which have provably no sesegmentttionn (or even k-tree) coreset of size smaller than n; see e.g. [54). Hence, there is no non-trivial decision tree coreset for general datasets of n vectors in any dimension. However, as we prove in the rest of the paper, coreset does exist for datasets where the input is matrix, i.e., discrite signal where every coordinate in the domain is assigned label (value), rather than a random set of n vectors.
The first coreset for n. X m-signals. To overcome the above problem, while still obtaining a small coreset, we assume a discretization of the dataset so that every coordinate has a label. We also assume, mainly for simplicity and lack of space, that the input feature space is A = [n] x [m] S RR2 That is, the input can be represented by an n x m matrix. The output coreset may contain fraction of entries, as in Fig. 3 which is called an n X m signal; see Section 1.3, Our assumption on the input data seems to be the weakest assumption that can enable us to have a provably small coreset for any input. Furthermore, it seems natural for e.g. images, matrices, or any input data from sensors (such as GPS) that has a value every cell or continuous some other sense.
Previous work. The prior works [54 24 62]. which only handle the case of segmenting 1- dimensional signal, use relaxations similar to our relaxation above obtain a coreset of size (k)) However, our results apply easily for the case of vectors (1-dimensional signals) as in [54] and generalize for tensors if 2 We also give further applications, and provide extensive experiments with popular state of the art software.
A special case for d = includes image compression, where quadtrees are usually used in e.g. MPEG4 to replace the image by smooth blocks of different sizes (55), or for completion of missing values 58 Using dynamic programming. it is easy to compute the optimal tree of 2D-signal D in O(22n)) time (5). which is impractical even for small datasets, unless applied on a small coreset of D. However we do not know of any such coreset construction, for d 2 2, with provable guarantees on its size. To this end, the following questions are the motivation for this paper: (i): Is there small coreset for any n m signal (e.g. of sub-linear size)? (ii): If so, can it be computed efficiently? (iii): Can be used on real-world datasets to boost the performance of existing random forest implementations?
focus on the classic sum of squared distances (SSE) the risk minimization model [59]. However, our suggested techniques mainly assume that a coreset for the case k 1 is known, which is trivial for SSE, but exists for many other loss functions e.g., non-squared distances; see Section 6
Extensions. For simplicity,
1.3 Our Contribution
For any given eтror parameter E (0, 1), and an integer k 2 1, this paper answers affirmatively the above three questions. More formally, in this paper we provide:
(i): A proof that every n X m signal D has (koorect (C, u) of size |C| polynomial in log(nm)/s. To our knowledge, this is the first coreset for decision trees whose size is smaller than the input; see Theorem g Due to lack of space, our full proofs are given in the appendix.
(ii): novel coreset construction algorithm that outputs such a coreset (C, u) with the above guarantees, for every given input signal D. Its running time is ((mm)), i.c., linear in the input size

---

[D] Unlike common coreset constructions. our algorithm is deterministic; see Algorithm (iii): AutoML for decision trees: since the suggested coreset approximates every tree of at most leaves, we may use the same coreset for hyperparameter tuning. We demonstrate this in Section 5 by calibrating the parameter using only the coreset, as compared to using the original (big) data. (iv): Experimental results that apply modern solvers, such as the sklearn and LightGBM libraries, on this coreset for real-world public datasets. We show that our coreset can help boost the computation time of the above forest implementations and their parameter tuning by up to x10, while keeping similar accuracy; see Section 5
(v): Open source code for our algorithms (3]. We expect that it will be used by both the academic and industry communities, not only to improve the running time of existing projects, but also to extend the algorithms and experimental results to other libraries and cost functions; see Section 6
1.4 Novel technique: partition trees meet decision trees
In a seminal paper (28 during the 80's of the previous century. Haussler and Welz introduced the importance of VC-dimension by Vapnik-Cherroonnkke (60). Their main application was partition trees for answering range queries.
Informally, a partition tree of a given set of points on the plane is the result of computing recursively simplicial partition which is defined as follows. For set D of N points on the plane, a (1/e)- simplicial partition is the partition of D into O(1/s) subsets, such that: (i) each subset has at most N points, and (ii) Every line in the plane intersects the convex hull of at most /1/5 sets. Answering range queries of the form "how many points in 1 are in a given rectangular" in sub-linear time, using partition trees, is straightforward: We can sum in ((1/E) time the number of points in the subsets of the above simplicial partition that are not intersected by the query rectangular. We then continue recursively to count the points on each of the VI/e intersected sets.
In other words, the main idea behind the above work is to partition the input into (relatively small) number of subsets, each containing fraction of the input, such that each query (in this case, rectangular shape) might intersect only small fraction of those subsets. Such a partition is termed a simplicial partition. The number of points contained in onn-intereected subsets can be easily computed, while the sum of points in intersected subsets require more involved solution. The novelty in that work is how to achieve such a partition of the input.
Our paper closes a loop in the sense that it forges links between decision trees in machine learning to partition trees from computational geometry. We aim generalize the above technique from covering problems to regression and classification problems. This is by devising an algorithm which achieves the above requirements. but where the query is a decision tree (and not a rectangular shape), and the cost function is the sum of squared distances to the query and not the number of points.
More precisely, We partition the input dataset D into relatively small number of subsets, such that every possible decision tree (query) intersects at most few of these subsets. We then independently compress every subset via another novel algorithm such that the cost (sum of squared distances, in this case) of points contained in non-intersected subsets can be easily and accurately estimated, while the cost of points in intersected subsets can be provably approximated via a more involved calculation. This is very different from existing coreset techniques that are sampling-based utilize convex optimization greedy algorithms [16]. Our main challenge was to define and design such a "simplicial partition for sum of squared distances", and the coreset to be computed for each subset in this partition.
(38), or
1.5 Preliminaries
In this section we define the notation that will be used in the next sections.
Let n 2 1 and denote [n]
n}. An n-iignal is set ((z, f(x)) | x E [n]] that is
defined by a function f : [n] - R (known as the graph of f). For an additional integer m 2 1,
an n x m signal D = ([z,((z)) x E [m] x [m]] } is the set that corresponds to function
g [n] x [m]] + RR. That is, D represents an n x m real matrix whose size is |D] = N = nm.
For integers i j2,J1,2 such that S < i2 < and 1 < ji < j2 S m. an n x sub-signal
the set B- {(x.g(x)) x E (h,.... (2) x (i..... |2 C D; see Fig. 1 A sub-signal B
is called row (respectively, columm) if i = is (respectively,
J1 j2). For a sub-signal B,
5

---

denote by B" = =((G, v) ((i.)).)) E B) the transposed sub-signal. A k-segmentation is said to intersect an n x m sub-signal B if s assigns at least two distinct values to the entries of B, i.e., (s((r) (ar, y) E B 2 2. Furthermore, by definition, a k-segmentation induces a partition of an n x m sub-signal B into at most l n x m sub-signals. For two functions f:g : R - IR we use the big O notation f(x) E O(g(x)), thinking of (g((=)) as the class of all functions (ax)
such that [x(x)] < clg(x)) for every æ > Io. for some constants с and zo. Lastly, we denote SEGg :- SEG for brevity.
Paper organization. Section 2 provides a rough approximation to the k- k-segmentation problem. Section 3 provides an algorithm for computing simplicial partition for the k-segmentation problem. Each region in this partition will be then compressed individually in Section to obtain our desired coreset. Experimental results and discussions are given in Section and conclusion in Section 6
2 Bi-criteria Approximation
coreset construction usually requires some rough approximation the optimal solution as its input. Unfortunately, we do not know how to efficiently compute even constant factor approximation to the optimal k-segmentation problem in Definition as explained in Section[] Instead, we provide an (a, 3)& or bi-criteria approximation [22). where the approximation is with respect to a pair of parameters: the number of segments in the partition may be up to 3k instead of k, and the loss may be up to a opt& (D) instead of opt, (D).
Definition 4 ((a,, apppxxppximmtiinn Let D be an n x m sub-signal, k 2 1 be an integer and [n]] x [mm] - R is (a, ())s-ppprxxiittionn of D. if s is a Sk- segmentation whose fitting loss to D is at most a times the loss of the optimal k-segmentation of D, i.., s E (BG) and E(D, s) = > (Z.))D (s(x) - y)² S a (D).
let a > 1. A function
We now describe an algorithm that computes such an approximation, in time only linear in the input's size [D| nm. The following lemma gives the formal statement. A suggested implementation for the algorithm is given in the appendix, as well as the full proof of the lemma; see Section B
Lemma S. Let D {x11 y1 ... (Jrmm Uro) } be an n X m sub-signal and k: > 1 be an inleger. Then, there is an algorithm that can compute, in (kmm) time, an (ar, B) apprroxoxiationnn for D, where a E Ok log(nm)) and 3 E hO(1) log? (nm).
Overview of the bicriteria algorithm from Lemma 5 The algorithm is iterative and works as follows. At the ith iteration, we find a collection B, of at most disjoint sub-signals in D; (where Da = D is the input), for which: (i) EBEB, opt, (B) I opt, (D.) & opt, (D), and (ii) UBES, B has size [URE B| 2 DDl/cc for some parameter that depends on kt i... those sub-signals contain at least a 1/c fraction of D,. We then define D = D. \ UBEB, B. After repeating this for at most 1o E ((clog(nm)) iterations, we end up covering all entries of D with sub-signals where the overall loss of the sub-signals in each iteration is at most ( This defines a partition of D into a collection of at most tú disjoint sets B", which, in turn, define a set of most (tw)² distinct sub-signals. The output is now simply the function s that assigns, for every B E B and b E B, the mean value s(b)
F Σ
((.)).)) y of B. See Pseudo-code in Algorithm 4 at the appendix.
3 Balanced Partition
In this section we present Algorithm which computes a partition similar to the simplicial partition described in Section 1.4 It computes, in O(12)) time, partition B of the input D that satisfies the following properties: (i) [B] depends on k/s but independent of [D], (ii) the loss opt, (B) of every B E 1 is small, and (iii) every k-segmentation s intersects only few sub-signals B E B; see
Definition 6 Fig. 2 and Lemma] 7 A full proof is given at the appendix; see Section
Definition (Balanced Partition). Let D be an n. X m signal, le Z be an integer, and C₁ C22 C3 > A (cI, C22 ea) bbblancced partition of D is partition B of D such that: (i) B contains [B] S C1 n X m sub-signals, (ii) opt, (B) S 02 for every E B, and (ii)) every k-segmentation á intersects at most C3 nub-signals B E B (i.e., assigns more than one unique number to those sub-signals)
Lemma 7. Let D be an n x m signal, k 2 be an integer, E E 1/4) be an error parameter, and [n] x [m] R be (a, ()xx approoxiiiiiiinnnooco of D, where a, 3 L. Define == ((D.s)

---

5
Muegments
Not enough segments.
R3
enough regiennts Rg
R.
5
2
Sufficinnt
Rg
5
R2
Auggeenia reached.
(6) Sufficient
Figure 2:
(Left): 6 5 signal D consisting of 6 rows RI..... .Rg. (Middle): A step by step illustration of the call to B := PARTITION(D, signals (sub-matrices)
64) which partitions D into B] = 13 sub- follows. (1) B' SLICEPARTITION [Ri] [ 4) (top green row). (2) B' = SLICEPARTIIIN R R2,4) (middle green matrix), and so on as long as the output contains most | < 1/7 4 sub-signals (as in the bottom green matrix (3)). We then append B' to the output B3 and repeat with the remaining {R4, RG, R J- (4) B' == SLICEPARTITION : : which already returns [B'| 5 1/7 signals (yellow matrix). We append them B and repeat. (Right): The final partition B, where opt, (B) S 5790 0 1/4 64 = 4 for every B E B.
and 7 == 2 pK.
Let be an output of a call to PARTITION(D o,o); see Algorithm 2 Then B an -balanced partition of D. Moreover, B can be computed in (mm) time.
(o 10(2) 2,000000 ka
Overview of Algorithms ( Algorithmm@eet input
m-signal D and two parameters
a, y. Algorithm aiims to compute a balanced partition of D; see 2 In turn, it calls Algorithm [ which takes input dataset D, and a parameter a >> 0, and aims to compute a partition B of R. To do so, Algorithm T partitions R along the vertical dimension (e.g., into vertical slices), in greedy fashion, such that for every B E B, opt (B) is as large as possible, while still upper bounded by a. This will ensure that the partition is into relatively small number of slices. In the case where one of the sub-signals B in this vertical partition of R contains only one column, and already exceeds the maximum tolerance opt, (B) > d, we recursively apply Algorithm to 3 in order to partition B horizontally. As long as the total number of slices returned by Algorithm ii smaller than 1/%, Algorithm 2 adds yet another row the previous set of rows, and repeats the above process. At this point, the partition of the current horizontal slice (collection of rows) R is final, and is added to the output partition of Algorithm 2 In turn, a new horizontal slice R of just one row, the first row of D) that not included in the previous R, is initiated on which we again call Algorithm [
m sub-signal R that is defined by several contiguous rows of the original
Algorithm 1: SLICEPARTIIION (D,
Algorithm 2: PARTITION(D,7.o)
Input :A parameter dr > 0 and n X signal D [z, y))
Input :An n x m signal D, a parameter
7 (0, 1), and lower bound
o [0, opt, (D)]
Output:A partition B of D.
Output: A partition B of D; see Lemma
== and Obegin :=
while Coegin m do
1 B == and Thegin :=
B ((ii.)) v) E Dij Cbegin
2 while Thegin do
11 extract first column
3
R = ((i,,),)) E D Tbegin)
opt, (B) then
// extract first row
B = SLICEPARTIIION 7²0)
B' = SLICCEPARTITOO(BB' ,o)
B BB=Bu I
IB'EB\
s
Tend := Thegin
lastB' := B
Obegin == Chegin +1
7
while |B' S 1/7 and Fend < n do
else
rend Fend +
Gend Obegin
last = B'
while (B) S a and Cend < m do
10
10
Cend Cend + 1 and last == B B:=
((i,)))v) E D Dlic [Teegin; Tend // extract slice
11
((..)).) D l [Obegins Cend]]
11
SLICEPARTITION
12
B = B (lastB]
12
B = B U lastB'
13
Cbegin = Cend
13
Tbegin == Tend
return
B
14
return B
7

---

Coreset Construction
In this section, we present our main algorithm (Algorithm 3 which outputs a (k, - for given X signal D, the number of leaves k 2 1, and approximation error E (0, 1).
Overview of Algorithm 3 The algorithm first utilizes the (a, appppppooiiiaoo from Section 2 to obtain a lower bound S opt, (D) for the optimal k-segmentation. It then computes, as described in Section 3 balanced partition B of D, where opt, (B) is small and depends on Ø, for every B E B. Finally, it computes a small representation (Cp, uB) for every B E B, and returns the union of those representations. Each such pair (CB; uB) satisfies: (i) |Cal 4, and (ii) has the same weighted sum of values, weighted sum of squared values, and sum of weights, as B, i.e., [(a,))CC, up ((a,b) b)) (b B2 1) ye y² 1); see Fig. Such a representation can be computed using Caratheodory's theorem, as explained Section of the supplementary material.
8
11
3.3
12
10
15
Matrix form
17
17
12
Smoothed Cp
17
Smoothed
ug
21
21
32
Figure 3: (Left)) A matrix representing of 5 x 5 sub-signal B where is mapped into unique colors for every (a., y) B. (Middle): A representative (coreset) pair (CB, uB) for B where CB B is (small) subset and UB CB + [0, oo) is a weight function. That is, the pair (Cn, up) satisfies E(a,))CC, u ((a,b) b)) (b
12 1] = E (1 y² 1). (Right): A duplication of the coreset points according to their weight. We call the resulting pair a "smoothed" version of (Cp, uB); see more details and formal definition in Section D of the supplementary material.
Some intuition behind Algorithm 3 Consider some k-segmentation By the properties of the balanced partition of D, only small number of sub-signals B B are intersected by 8, i.c., assigned at least distinct values. For every non-intersected sub-signal B E B, the loss ((B, s) is accurately estimated by the (coreset) pair (CB, uB). the other hand, for every sub-signal B which is intersected by s, by the guarantees of the representation (CB, 1, the loss {(B, s) will be approximated, using only (CB. uB). up to some small error that depends on (B). However,
again by the properties of B, we have that opt (B) is small. Hence, using the union (C, u) of the
representations we can approximate (D, 8) as required. Furthermore, combining that Cn E O(1) for every B B with the fact that [B] is small yields that [C] is indeed small; see Theorem g
Algorithm 3: SIGNAL-CORESET/ k, E); see Theorem 8
Input :An n X signal D, an integer k 2 1, and an error parameter & E 1/4).
Output :A (5..eeet (C, for D.
= an (a,8)) approximation D for O(k log(nm)) and ((1)) log (nm) see Lemma 5 for suggested implementation.
7 :- e²2 /²k(B σ ((D.s) and ==
a
B = PARRITIOO( D, 0, ( // see Algorithm
for every set B E B do
(CB,uB)
(1, coreset for B, zero error coreset for k 1), such that CB B,
|Cal= and Σ (a uB((a, b)) (b b² 11 (y y² 11) this is done
using Caratheodory's theorem; see Corollary [17] in the appendix. Replace each of the coordinates a of the pairs (a, C with one of the 4 corner coordinates of the pairs in B see detailed explanation if the proof of Theorem g
C= C CUCCCC C' and u((a, b)) = ug((a, b)) for every (a, CB.
8 return (C, u)
Theorem 8 (Coreset). Let D (1),
) be signal i.e., N = mm.
Let 2 1 be an integer (that corresponds to the number of leaves/rectangles) and e E (0, 1/4) be an error parameter. Let (C, u) be the output of a call to SIGNAL- MONNAL-CRRESETD,,, k,k/A) for
8

---

sufficiently large constant A 2 1; see Algorithm 3 Then, (C,u) is a (k, co-orestt for D of size Mogg(N))00) see Defimition 3 Moreover, (C, u) can be computed in O(kN) time.
|C| E
(k gl
Coreset size. While Theorem gives a worst-case theoretical upper bound, this bound is too pessimistie in practice, as common in coreset papers 42 34 This phenomenon is well known for coresets; see discussion e.g., vs. average behaviour on structured real-world data, noise removing/smoothing by coresets, the fact that in practice we run heuristies that output a local minima (and not optimal solutions with global minimum), non-tight analysis (especially when it comes to constants), etc.
2 53]. The reasons might include: worst-case artificial examples
Our experiments in Section show that, empirically, the constructed coresets are significantly smaller: for N := nm ~ 140, 000, k == 1000, and = 0.2, Theorem S predicts, in the worst case, a coreset of size larger than the full dataset size N. However, such an e error is obtained with a coreset of size at most 1% of the input; see Fig. 4
5 Experimental Results
We implemented our coreset construction from Algorithm 3 in Python 3.7, and this section we evaluate its empirical results, both synthetic and real-world datasets. More results are placed in the supplementary material; see Section A Open spen-source code can be found in [35]. The hardware used was standard MSI Prestige 14 laptop with an Intel Core 17-107 IOU and 16GB of RAM. Since our coreset construction algorithm does not compete with existing solvers, but improves them by reducing their input a pre-prroeeee processing step, apply existing solvers black box on the small coreset returned by Algorithm B The results show that our coreset can boost, by up to x10 times, the running time and storage cost of common random forest implementations.
Implementations for forests. We used the following common implementations: (i) the func- tion RandomF orestRegressor from the .elearnnenssmble package, and (ii) the function LGBMRegressor from the lightGBM package that implements a forest of gradient boosted trees. Both functions were used with their default hyperparameters, unless states otherwise.
Data summarizations. We consider the following compression schemes:
(i): DT DT-coreset (D, k, The implementation based Algorithm 3 In all experiments we used constant & = 2000 for computing the coreset, regardless of the (larger) actual & value in each test, since k = 2000 was sufficient obtain sufficiently small empirical approximation error. Hence, the parameter e controls the trade-off between size and accuracy.
(ii): RandomSample(D D, r) returns uniform random sample of size from D. In all tests was set to the size of the coreset DT-coreset(D D, k, 8) for fair comparison.
Datasets. We used the following pair of datasets from the public UCI Machine Learning Reposi-
tory B. each of which was normalized to have zero mean and unit variance for every feature:
(i): Air Quality Dataset [18] contains n = 9358 instances and m 15 features.
(ii) Gesture Phase Segmentation Dataset 45 contains n = 9900 instances and m = 18 features. The experiment. The goal was to predict missing entries in every given dataset, by training random forests on the available data. The test set (missing values) consists of 30% of the dataset, and was extracted from the input dataset matrix by randomly and uniformly choosing a sufficient number of 5 x 5 patches in the input dataset, and defining them as missing values. The final loss of trained forest the sum of squared distances between the forest predictions for the missing values, and the ground truth values. To tune the hyperparameter k, we randomly generate set K. of possible values for k on a logarithmic scale. Then, we either: (i) apply the standard tuning (train the forest on the full data, for each value in K., and pick the one with the smallest test set error), (ii) compress the input (only once) into a small representative set, and then apply the standard tuning on the small, rather than the full, data. The experiment was repeated 10 times. All the results are averaged over all 10 tests; see Fig.
Discussion. While the size and accuracy of our coreset are independent of our exact implementation of Algorithm 33, the running time is heavily based on our naive implementation, as compared to the very efficient professional Python libraries. This explains why most of the running time is still devoted to the coreset construction rather than the forest training. Nevertheless, even our simple implementation yielded improvements of up to x10 in both computational time and storage, for relatively small accuracy drop of 0.03 in the SSE Tuning more than one hyperparameter will result in bigger improvement. Furthermore, Fig. 4 empirically shows that tuning hyperparameter on the

---

Datasel
Datasel (i)
Dataset (ii
Dalaset (ii)
0.68
Lypecar on the conaet
Fentenfforst cornet
Ligetcei cornet
0646
Rundomnheoa on the convet
on test set
9.00
186 the data
- 10% of
-1 1%
~10% of
1% of the data
-8% of
10.4
1% of
88%
the data
the data
the data
the data
1025
thtd
the data
Sample size
Sample size
10
Sample size
10
Sample size
Dataset (
Dataset (ii)
Dataset (
Dataset (ii
Cost ontontt
Compubetio
105
13T 10
Sample size
10
Sample size
101
Figure 4: Experimental results. (Top): The X-axis is the compression size. For every compression size 7 hyperparameter tuning is applied on both the coreset and the uniform sample (which are both of size y). A random forest is then trained, on the full data, using those tuned parameters. The Y-axis presents the test set SSE loss of the trained forests. (Bottom left): Hyperparameter tuning. For every different value of & (X-axis), a forest is trained using this parameter value either on the compression (of two different sizes) or on the full data. The -axis presents & + k/ 9/10,, where / is the normal SSE loss of the trained forest on the test set. (Bottom right): Time comparison. The Yaxxis presents the total running time of both to compute the compression and to tune the parameter k the compression (out of 50 different values). Note that the bottom right figures measure the total time to tune the parameter & in the bottom left figures, but using many more compression sizes. The optimal obtained parameter was then used to train the random forest in the top figures.
coreset yields loss curve very similar the loss curve of tuning the full data. Lastly, we observe that, in practice our coresets have size much smaller than predicted in the pessimistic theory.
6 Conclusions and Future Work
While coresets for k-trees do not exist in general, we provided an algorithm that computes such a coreset for every input X m signal. The coreset size depends polynomialy on & log(nm)) and can be computed in (nmnk) time. Our experimental results on real and synthetic datasets demonstrates how to apply existing forest implementations and tune their hyperparameters on our coreset to boost their running time and storage cost by up to x10. In practice our coreset works very well also on non-signal datasets, probably since they have "real-world" properties that do not exist in the artificial worst-case example from Section I. .2 An open problem
define these properties. Moreover, while this paper focuses on the sum of squares distances loss, we expect that the results can be generalized to support other loss functions; see Section 1.2] Lastly, supporting high-dimensional data (tensors), instead of matrices, is a straightforward generalization that can be achieved via minor modifications to our algorithms. We also leave this to future work.
Acknowledgments and Disclosure of Funding
This research was supported by The ISRAEL SCIENCE FOUNDATION, grant number 379/21.
References
[1] Pankaj K Agarwal, Graham Cormode, Zengfeng Huang, Jeff M Phillips, Zhewei Wei, and Ke Yi. Mergeable summaries. ACM Transactions on Database Systems (TODS), 38(4):1-28, 2013.
[2] Pankaj K Agarwal, Sariel Har-Peled, Kasturi R Varadarajan, et al. Geometric approximation via coresets. Combinatorial and computational geometry, 52:1-30, 2005.
[3] Arthur Asuncion and David Newman. Uci machine learning repository, 2007.
10

---

symposium on [4] Olivier Bachem, Mario Lucic, and Andreas Krause. Practical coreset constructions for machine learning. arXiv preprint 3XXYv:7703.064000 2017.
[5] Richard Bellman. Dynamic programming. Science, 153(3731):34-37, 1966.
[6] Kristin P Bennett. Decision tree construction via linear programming. Technical report, University of Wisconsin-Madison Department of Computer Sciences, 1992.
[7] Jon Louis Bentley and James B Saxe. Decomposable searching problems i. static-to-dynamic transformation. Journal of Algorithms, 1(4):301-358 1980.
[8] Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106(7):1039- 1082, 2017.
[9] Rafael Blanquero, Emilio Carrizosa, Cristina Molero-Rio, and Dolores Romero Morales. Opti- mal randomized classification trees. In Technical Report. 2018.
[10] Casper Solheim Bojer and Jens Peder Meldgaard. Kaggle forecasting competitions: An overlooked learning opportunity. International Journal of Forecasting, 37(2):587-603, 2021.
[11] Vladimir Braverman, Dan Feldman, and Harry Lang. New frameworks for offline and streaming
coreset constructions. arXiv preprint 1612.008811 2016.
[12] Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
[13] Constantin Carathéodory. Über den variabilitättsbreichh der koeffizienten von potenzreihen, die gegebene werte nicht annehmen. Mathematische Annalen, 64(1):95 1907.
[14] Venkatesan T Chakaravarthy, Vinayaka Pandit, Sambuddha Roy, Pranjal Awasthi, and Mukesh Mohania. Decision trees for entity identification: Approximation algorithms and hardness results. In Proceedings of the twenty-sixth ACM Principles of database systems, pages 53-62, 2007.
[15] Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pages 785-794, 2016.
[16] Kenneth L Clarkson. Coresets, sparse greedy approximation, and the frank-wolfe algorithm. ACM Transactions on Algorithms (TALG), 6(4):1-30, 2010.
[17] Michael Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng. and Aaron Sidford. Uniform sampling for matrix approximation. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 181-190, 2015.
[18] Saverio De Vito, Ettore Massera, Marco Piga, Luca Martinotto, and Girolamo Di Francia. On field calibration of an electronic nose for benzene estimation in an urban pollution monitoring scenario. Sensors and Actuators B: Chemical, 129(2):750-757, 2008
[19] Anna Veronika Dorogush, Vasily Ershov, and Andrey Gulin. Catboost: gradient boosting with categorical features support. arXiv preprint arXiv: 11363, 2018.
[20] Abhimanyu Dubey, Moitreya Chatterjee, and Narendra Ahuja. Coreset-based neural network compression. In Proceedings of the European Conference on Computer Vision (ECCV), pages 454-470 470, 2018
[21] Dan Feldman. Core-sets: Updated survey. Sampling Techniques for Supervised or Unsupervised Tasks, pages 23-44, 2020.
[22] Dan Feldman and Michael Langberg. unified framework for approximating and clustering data. In Proceedings of the forty-third annual ACM symposium Theory of computing, pages 569-578, 2011.
[23] Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant- size coresets for k-means, pea, and projective clustering. SIAM Journal on Computing. 49(3):601-657, 2020.
[24] Dan Feldman, Cynthia Sung, and Daniela Rus. The single pixel gps: learning big data signals from tiny coresets. In Proceedings of the 20th international conference on advances in geographic information systems, pages 23-32, 2012.
[25] Dan Feldman and Tamir Tassa. More constraints, smaller coresets: Constrained matrix approxi- mation of sparse big data. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 249-258, 2015.
11

---

[26] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. pages 291-300. 2004.
[27] Melissa Hardy. Regression with dummy variables, volume 93, Sage, 1993.
[28] D Haussler and E Welzl. Epsilon-nets and simplex range queries. In Proceedings of the Second Anmual Symposium on Computational Geometry, SCG 88,, page 61-71, New York, NY, USA, 1986. Association for Computing Machinery.
[29] Tin Kam Ho. Random decision forests. In Proceedings of 3rd international conference on document analysis and recognition, volume 1, pages 278-282 IEEE, 1995.
[30] Badr Hssina, Abdelkarim Merbouha, Hanane Ezzikouri, and Mohammed Erritali. A comparative study of decision tree id3 and c4. 5. International Journal of Advanced Computer Science and Applications, 4(2):13-19, 2014.
[31] Xiyang Hu, Cynthia Rudin, and Margo Seltzer. Optimal sparse decision trees. Advances in Neural Information Processing Systems (NeurIPS), 2019.
[32] Piotr Indyk, Sepideh Mahabadi, Mohammad Mahdian, and Vahab S Mirrokni. Composable core-sets for diversity and coverage maximization. In Proceedings of the 33rd ACM SIGMOD- SIGACT-SIGART symposium on Principles of database systems, pages 100-108, 2014.
[33] Ibrahim Jubran, Alaa Maalouf, and Dan Feldman. Overview of accurate coresets. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, page e e1429.
[34] Ibrahim Jubran, Murad Tukan, Alaa Maalouf, and Dan Feldman. Sets clustcring, In International Conference Machine Learning, pages 4994-5005. PMLR, 2020.
[35] Jubran, Ibrahim and Sanches, Ernesto and Newman, Ilan and Feldman, Dan. Open source code for the algorithms presented in this paper. 2021. Link for open-source code.
[36] Kaggle. Kaggle website. https: /wwp://www...o kaggle. /om/
[37] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang. Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu. Lightgbm: A highly efficient gradient boosting decision tree. Advances in neural information processing systems, 30:3144 146-3154, 2017.
[38] Michael Langberg and Leonard J Schulman. Universal E-approximators for integrals. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 188-607.55 SIAM, 2010.
[39] Hyafil Laurent and Ronald L Rivest. Constructing optimal binary decision trees is np-complete. Information processing letters, 5(1):15-17, 1976.
[40] Wei- Yin Loh. Classification and regression trees. Wiley interdisciplinary reviews: data mining and knowledge discovery, 1(1):14 23, 2011.
[41] Hanlin Lu, Ming-Ju Li, Ting He, Shiqiang Wang, Vijaykrishnan Narayanan, and Kevin S Chan.
Robust coreset construction for distributed machine learning. IEEE Journal on Selected Areas in Communications, 38( (8(10)24400-2111 2020.
[42] Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman. Training gaussian mixture models at scale via coresets. The Journal of Machine Learning Research, B(1):5885-5909) 2017.
[43] Alaa Maalouf, Ibrahim Jubran, and Dan Feldman. Fast and accurate least-mean-squeee squares solvers. In Advances in Neural Information Processing Systems, pages 8305-8316, 2019.
[44] Alaa Maalouf, Ibrahim Jubran, Murad Tukan, and Dan Feldman. Faster pac learning and smaller coresets via smoothed analysis. arXiv preprint arXiv:2006. 20ti:20000.04441,, 2020.
[45] Renata CB Madeo, Clodoaldo AM Lima, and Sarajane M Peres. Gesture unit segmentation using support vector machines: segmenting gestures from positions. In Proceedings of the 28th Annual ACM Symposium on Applied Computing, pages 46-52, 2013.
[46] Detlev Marpe, Thomas Wiegand, and Gary Sullivan. The h. 264/mmegg advanced video coding standard and its applications. IEEE communications magazine, 44(8): (((8)):334143) 2006.
[47] Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David Woodruff. On coresets for logistic regression. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Resa-Bianchi, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
12

---

[48]
Soliman Nasser, Ibrahim Jubran, and Dan Feldman. Autonomous toy drone via coresets for pose estimation. Sensors, 20(11):3042. 2020.
[49] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit- learn: Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011.
[50] Jeff M Phillips. Coresets and sketches. arXiv preprint arXiv: 2016.
[51] J Ross Quinlan. C4. progrums for machine leurning. Elsevier, 2014.
[52] Lior Rokach and Oded Maimon. Decision trees. In Data mining and knowledge discovery handbook, pages 165-192. Springer, 2005.
[53] Frédéric Ros and Serge Guillaume. Sampling techniques for supervised or unsupervised tasks. Springer, 2020.
[54] Guy Rosman, Mikhail Volkov, Danny Feldman, John W Fisher III, and Daniela Rus. Coresets for k-segmentation of streaming data. Neural Information Processing Systems Foundation, 2014.
[55] Eli Shusterman and Meir Feder. Image compression via improved quadtree decomposition algorithms. IEEE Transactions on Image Processing. 3(2):207-215, 1994.
https://scikit-leerr wwweernn.rrgsseeeeeeeeeeeeeeeeee or. stable/ [56] skleam. sklearn user guide decision trees.
modules/tree. html
[57] Morad Tukan, Alaa Maalouf, and Dan Feldman. Coresets for near-convex functions. Advances in Neural Information Processing Systems, 33, 2020.
[58] Bhekisipho Twala. An empirical comparison of techniques for handling incomplete data using decision trees. Applied Artificial Intelligence, 23(5):373-4055 2009.
[59] Vladimir Vapnik. Principles of risk minimization for learning theory. In Advances in neural information processing systems, pages 831-838, 1992.
[60] Vladimir Vapnik and Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity, pages 11-30. Springer, 20155
[61] Sicco Verwer and Yingqian Zhang. Learning optimal classification trees using a binary lin- ear program formulation. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 33, pages 1625-1632, 2019.
[62] Mikhail Volkov, Guy Rosman, Dan Feldman, John W Fisher, and Daniela Rus. Coresets for visual summarization with applications to loop closure. In 2015 IEEE International Conference on Robotics and Automation (ICRA), pages 3638-3645. IEEE, 2015.
13


Reviews:
[{"review_id": "v8zaQouzosZ", "reviewer": "Reviewer_nDd9", "summary": "The paper provides a new perspective on scalability for computing decision trees, and discusses how to build coresets for these objects.  The problem is posed as a data set over R^d x R, and the goal is to decompose R^d into rectangles with constant values so that the sum of squared errors from each rectangle to the points within it is minimized.  ", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper devises a greedy approach.  It greedy decomposes data into contiguous sets columns with, then roughly the same procedure is applied on each column set, dividing into contiguous sets of rows.  It recurses alternating on dimensions.  The algorithm and examples seem to be described in the d=2 case, but the discussion and experiments apply to larger d (15 and 18).  \n\nGiven the multi-dimensional histogram found, (with small extension) standard decision tree (and even random forest) algorithms can be run, and can be much more efficient.  Experiments show only a small loss in quality (say 3%) with about a factor 10 reduction in space and time.  \n\nThere are some size bounds on the coreset assuming nice properties of the data.  The polynomial terms  in terms of log N  (Where N is the data set size) and k (the number of leaves) is not specified, but is constant.  \n\n\nOverall, I like the idea for coresets for decision trees.  I can imagine a series of follow-on work to refine this work.  However, I have several concerns about this work itself:\n\n - the algorithmic description is not written in a way that is easy to understand.  It took several reads to (Hopefully correctly) decipher what I think is going on.  Also, it seems only described for 2 dimensions/features.  \n\n - there is related work in databases that looks at quite similar problems, and the relation is not discussed.  Namely work in R-trees and in sketching multi-dimensional histograms (e.g., https://dl.acm.org/doi/abs/10.1145/564691.564741 or https://dl.acm.org/doi/pdf/10.1145/564691.564741).  Given that this paper seems to propose a fairly simple greedy method, it would be useful to compare with this fairly extensive line of work.  \n\n - the paper claims a deep connection with partition trees, but does not really explain it in the main 9 pages.  I find this odd in that partition trees were mainly developed to deal with halfspace queries (of *any* orientation) and other objects which can be lifted to be halfspaces or composed of them.  There is a mostly different but parallel line of work that developed range queries techniques for axis-aligned queries, which seem to align with the axis-aligned rectangles used in decision trees and the proposed coresets.  \n\n - The paper's presented analysis is for a restricted set of decision tree problems.  It should work for any decision tree given that structure holds.  However, then experimentally they apply them to random forests.  It is not completely clear that (or how) the coresets apply to random forests.  There are two concerns: the multiple queries and the correlation between classifiers.  The first concern should probably be simple using a union bound or something.  But the second one I understand less - that is, if a coreset is too course, does it prevent the random forest from reaching as a high a precision since the difference between categories has been smoothed out.  \n  On the other hand, even vanilla decision trees still have an important place in ML since they are very explainable and favored among scientists who want a procedural explanation.  (random forests do not have this advantage -- this may be slightly conflated in the introduction).  \n\n\nOverall, I definitely like this direction, and I strongly encourage the authors to continue pursuing this.  However, I feel the writing of the paper could be significantly improved, so am not convinced this paper is ready for publication in NeurIPS.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not engage on this topic.  ", "review_text": "", "extra_scores": {"ethical_concerns": "The authors did not engage on this topic.  ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "nKd5ESx7-Yk", "reviewer": "Reviewer_1UMR", "summary": "The paper presents an efficient construction of coresets for decision trees. For general decision trees, coresets are useless because they cannot be very small. However, the result in this paper focuses on decisions trees for a restricted form of signal, namely, a function on the discrete grid of points $\\{1,2,\\dots, n\\} \\times \\{1,2,\\dots, m\\}$. The result is derived by relating this problem to the problem of constructing balanced partition trees for planar point sets. The theoretical result is also evaluated on synthetic and real datasets, showing impressive gains in runtime and storage requirements.", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "I find the result interesting, both from the perspective of discovering a useful subset of decision trees that can be shown to have coresets, and from the perspective of the elegant solution relating the problem to a geometric one. The result is perhaps not surprising, but useful.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "mZwUau_Dei", "reviewer": "Reviewer_BfeE", "summary": "This paper studies the coreset construction for the decision tree problem. In the 2D k-decision tree problem, the goal is to partition the input n x m matrix into k submatrices (with some restrictions) such that the summation of the cost over all submatrices is minimized. This paper gives the first coreset construction: it outputs a small subset of indices of the matrix with new weights such that the cost of any decision tree over the coreset is a (1+-eps)-approximation of the cost over the input matrix. The running time is O(knm) and the coreset size is polynomial in klog(nm)/eps.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Pros:\n-Decision tree is a fundamental problem in computer science. To the best of my knowledge, this paper gives the first coreset construction for the decision tree problem. Authors provided a novel partitioning scheme and connected it to the techniques in the theory of VC dimension. Such combination is non-trivial and I really like their partitioning algorithm which is simple and clever. \n-The algorithm is deterministic.\n-The experiments showed that the running time can be significantly improved.\n-The paper is well-written in general.\n\nCons:\n-There is a lack of discussion of previous work which uses the techniques from PAC learning and VC dimension to construct coresets for other problems. For example, Feldman and Langberg STOC'2011 gives a unified framework to construct coresets for k-clustering by reducing estimating the clustering objective to the range query problem in the field of VC dimension. Although the technical details are totally different, the high level structures of the algorithms are similar: both first require a good bicriteria approximation, then partition the data and finally handle each part separately. \n-Although authors claim that the techniques can be easily extended to higher dimensions (tensors), there is no formal statements. I think the precise statements for coreset size and running time for higher dimension d would be really appreciated in most applications with feature dimension > 2. \n\nOther comments:\n-What is the best possible dependency of the coreset size on k? I guess it is easy to prove that Omega(k) is a lower bound. But is linear dependence on k achievable? If we allow randomization, is it achievable?\n-Typo: Definition 6 (i): \"|\\mathcal{B}|\\leq c_1 n m\" -> \"|\\mathcal{B}|\\leq c_1\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I did not find any potentially negative societal impact of the work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "XUCN1OR0J5k", "reviewer": "Reviewer_ybbQ", "summary": "The paper introduces small data summaries known as coresets for decision trees on a two dimensional data domain. It does so by summarizing rectangular blocks of data with their mean value as an approximation for each cell's individual value, hereby approximating up to (1+-eps) relative error the squared loss induced by each k-partition that can be formed by a decision tree with k leaves.\nThe construction is done in linear time in the input parameters and data and the size of the summary is poly(k log(n)/eps).\nSome experiments show that the coresets are useful in practical settings where decision tree heuristics are compared on the coreset vs the original data.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper reads very well and the work is well-motivated. In the introduction to coresets maybeit should be added that C is much smaller than the data D (right in lines 66-69).\n\nit is just the squared error, not the MSE (l. 104)\n\nThe paper says there is no coresets in general, even in 1 dimension. but then for m x n-signals a coreset construction is presented. I find the discussion too vague. I didn't learn what was the problem that implies impossibility. And more importantly, what exactly is the relaxation that makes it possible again?\nCan you explain? (and modify the paper accordingly)\n\nIs an extension to d>2 tensor data even possible? Why is this only an outlook for future work and not dealt with? This is currently also vague (but minor).\n\nsince the coreset constructions are claimed to be different from existing sampling and greedy optimization, shouldn't there be some references on the appropriate surveys with more diverse coresets methods instead?\n\nI found it weird that we have mxn signals and then nxm sub-signals. maybe the authors could use some other letters to denote the input dimenions?\n\nDefinition of the O-notation should have c>0 and x_0 such that the inequality holds for all x>x_0. (199-200)\n\nt is overloaded  on page 6 before Sec. 3\n\nAlgo 2 inner while loop looks like the last iteration is run, but the result is not considered in the output. Please double check.\n\nFig 3  It seems that in the lower right corner there should be a low constant value and the lower left high value should be removed since it is covered by the other high value (22 and 21).\n\nregarding those tuples (b|b^2|1) it seems very similar to k-means \"clustering features\" used for example in BIRCH. Another reference that should be cited in this context is https://dl.acm.org/doi/10.1145/1132863.1132873 which stores the sum of values, sum of squared values and number of elements, i.e., the sum of those tuples in your paper.\n\ngenerally I suggest strongly to browse sudipto guha's DBLP for \"histogram\". There are a lot of extensions to other loss functions, fitting polynomials instead of constant values per bucket, streaming, more than one dimension. This seems very similar and strongly related to the contents of this submission or possible extensions.\n\nalpha, beta >0  -> alpha, beta >1 (eg in Def4 and Lem7)\n\nCoreset size: the authors claim that usually the theoretical bounds are much worse than in practice. Is this because the analysis is sloppy or loose? Are there any lower bounds? Or is this maybe since many \"real-world\" data sets from the usual ML repositories are easy to approximate?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"ethical_concerns": "-", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper was considered to have technical novelty and strength as "absolutely above the bar" of NeurIPS. However, there were very substantial concerns about the writing quality of the paper, almost of the level of being considered unpublishable in the current form. The authors are highly encourage to polish the paper and address all the writing concerns from the reviews (including comparison to past work).
Decision: Accept (Spotlight)