Coresets for Decision Trees of Signals

Code

• github.com/ernestosanches/decision-trees-coreset
  OfficialIn papernone★ 5

Abstract

A k-decision tree t (or k-tree) is a recursive partition of a matrix (2D-signal) into k 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 (0,1), a (k,)-coreset C of D is a small summarization that provably approximates this loss to every such tree, up to a multiplicative factor of 1. In particular, the optimal k-tree of C is a (1+)-approximation to the optimal k-tree of D. We provide the first algorithm that outputs such a (k,)-coreset for every such matrix D. The size |C| of the coreset is polynomial in k(N)/, 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 sklearn and 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 x10, while keeping similar accuracy. Full open source code is provided.

Reproductions