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": "O9IJVN2EK1A", "reviewer": "Reviewer_QFcb", "summary": "This paper studies the problem of constructing coresets for decision trees of 2D-signals. The coreset aims to preserve the min squared error of every axis-parallel rectangular k-partitions of the data set (where k is a parameter). However, it has been observed that no small coreset exists for this task, and hence the authors add an assumption that the data points are from discrete [m] x [n]. \n\nThe authors propose an efficient algorithm for coreset construction. Empirical results show that their coresets can accelerate the computation time of random forests. The main approach is to first construct a balanced partition of signals via a bi-criteria approximate solution, and then construct an exact coreset for each partition using Caratheodory’s theorem.", "questions": "", "limitations": "", "rating": 6, "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": "Originality: This paper provides the first coreset result for decision trees. The approach of the construction of balanced partition may have independent interest. However, the paper did not adequately compare the result with previous works, and I’m not sure which of the techniques are entirely new, especially the balanced partition. Moreover, I didn’t find a related work section.\n\nQuality: The technical claims are sound, and well supported by details. The pictorial illustrations and examples help the understand a lot, and excellent explanations are provided for key claims and algorithms. The experiments are well designed, and the choice of baseline and datasets in the experiments are appropriate.\n\nClarity: I find several parts that require clarification. \n-\tThe coreset size in Theorem 8 contains a log N factor, which seems from \\alpha in Lemma 5 (bi-criteria approximate factor). If \\alpha=O(1), does the coreset size still contain log N? If not, this point should be clarified.\n-\tLine 6 of Algorithm 3 is strange to me. Why replacing the coordinates will not violate the coreset approximate guarantee? It is better to give some explanations.\n-\tRight of Figure 3. I don’t understand the meaning of “smooth” coreset. It seems that this notion only appears in the analysis of Algorithm 3, am I right? In general, I think the authors should give some explanations for this “smoothed” coreset.\n-\tLine 305. The authors said that they implemented Algorithm 3. However, Algorithm 3 is designed for 2D-signals, which seems different from the setting of real-world datasets in Lines 313-314, whose dimension > 10. I wonder how the authors construct coresets for their real-world datasets.\n\nSignificance: The results are interesting and the work initiates the study of the coreset for decision tree problem which is important in coreset areas. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Kn2kmrnaA_", "reviewer": "Reviewer_eRj1", "summary": "This work creates coresets for axis aligned decision trees. A decision tree is defined as a partition of the data (set of vectors + label) into axis-parallel rectangles such that all vectors in the same leaf get the same predicted label, and the cost of the tree is defined in terms of some loss (MSE in current paper) between the predicted and given labels. For a given dataset, this work constructs a “strong” coreset for all decision trees with k leaves. The coreset is linear in the number of decision tree leaves and logarithmic in the datapoints and classes. ", "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": "Decision trees are clearly an important set of models, and while the combinatorial structure that they impose on the data space is similar to the structure posed by range queries, there has not been enough work on the coreset construction question. The fact that there exists datasets (even in dimension=1) or which there are no sublinear size coresets follows from existing work. This work makes a specific assumption on the dataset -- that “every coordinate has a label”. This seems too strong an assumption. Frankly, it would be nice if the authors could explain why this is a useful assumption to make in getting around the lower bounds, as well as why this reflects real data properties (while this assumption is not directly satisfied, what is the closest thing to it that exists in real data).\n\nThe coreset construction is deterministic and utilizes a nice connection between partition tree data structure and decision trees. To me, this also seems to be a novel contribution. The coreset is constructed based on a union of points chosen from each partition of the resulting partition tree. \n\nOverall, the paper is well written, and the illustrations are helpful. The experimental results do show a significant improvement over uniform sampling, but only over sample size that is < 5-8% of the data. Beyond these, the advantage is not very significant. This is not very uncommon for the performance of coreset algorithms in real datasets.  The only real weakness I see is the strong assumption made for theoretical proofs. \n\n-\nPost response: Thanks, I am satisfied with the response. \n", "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": "2"}, "extra_text": {}}, {"review_id": "55toGol2eGw", "reviewer": "Reviewer_tPz3", "summary": "This paper constructs coresets for $k$-decision trees for 2D-signals. Think of 2-D signals as a 2-dimensional $m x n$ matrix and $k$-decision trees as a partition of this matrix into k disjoint axis-parallel rectangles. Cost of a partition is defined as follows: For each part $P$, define a number $s_P$ that minimizes the squared loss for the entries in the partition. The number $s_P$ is actually just the mean of the entries in that partition. The authors propose coresets to approximate cost of any $k$-decision tree upto a factor of 1+eps while storing only $k\\log(N)/\\epsilon$ entries of the matrix along with the weights that they compute obtaining a significant reduction in time required to compute the cost of any rectangle and therefore the time required to compute the cost of a $k$-decision tree. The authors do some experiments that show that decision trees can be trained on the coreset much faster than they can be trained on the entire dataset and that the decision trees they obtain have an error on test set not much larger than the decision tree trained on the entire signal.\n\nTo construct the coreset, the authors first give a $(\\alpha, \\beta)$ bicriteria approximation algorithm to obtain a lowerbound on the optimal cost of a k-tree on the dataset. Then they use the bicriteria approximation to compute a balanced partition of the signal such that 1. The number of parts is not too large, 2. Optimum cost for each partition is small, 3. Every k-segmentation intersects only a few sub-signals. They prove that there is a simple greedy algorithm that gives a balanced partition with some parameters that depend on $\\alpha, \\beta$ and the cost of the bicriteria solution.\n\nThen they show that for each part in the balanced partition, they only have to store 4 values and corresponding weights and this is enough to compute the $1+\\epsilon$ approximaton to the cost of $k$-segmentation for the signal. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "Strengths:\n- Algorithms are simple and easy to understand.\n- The proofs seem to be quite natural stemming from the fact that the algorithms are simple.\n- First coreset construction for decision trees.\n- Paper is well written.\n- Experiments show that test error is close to the optimal error and the coreset does better than a uniform sample of same number of points.\n\nWeaknesses:\n- In the current form of the paper, there is very little intution on why they are doing what their doing. It is just a series of theorems without much intution as to why they need those parameters in the theorem and how proving one theorem helps in achieving the parameters of the next theorem. Need to add more details connecting the theorems. I understand it may not be possible due to space constraints but more context would greatly help a reader understand the paper much better.\n\n\nSuggestion:\n- Using $(x,y) \\in B$ for a signal where $x$ is denotes a tuple and $y$ denotes a value is confusing. Maybe use a better notation?\n\nTypos:\n- Line 53 : foreset -> forest\n- Line 184 : simplicical -> simplicial\n- Definition 6: Should be $|\\mathcal{B}| \\le c_1$ instead of $c_1mn$\n\nQuestions:\n- Why is there a running time difference between decision trees trained on random sample vs decision trees trained on your coreset? Is the slowdown mainly due to your algorithm to compute cost of a $k$-segmentation?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers quite liked the first coreset for this fundamental machine learning model - decision trees - and the technical ingredients and ideas involved in the proof. The reviewers also felt the experimental results were solid. The only suggestions for improvement were to clarify more as to why this is the minimal assumption needed to skirt the lower bounds, and to add more intuition to the paper. 
Decision: Accept (Spotlight)