Introduction to Coresets

Motivation & Coresets

Big Data is a catchy buzzword nowadays. You may hear it in many conversations on trending topics, such as deep learning (DL), machine learning (ML), robotics, and more. Notably, the gains of machine learning have come at the expense of ever-larger and more complicated models trained on vast volumes of datasets. In fact, many recent advancements in ML have been made possible by the sheer size of the training data.

Well, the answer to this question depends on the scenario at hand:

Limited Hardware

In many cases, we are interested in applying a machine/deep learning algorithm on an edge device with power constraints such as IoT devices and smartphones, such hardware may not be able to handle the large memory/CPU demands of the ML algorithm (training process), even on a tiny input data. In this case, even a set of 1000 training images will be considered Big Data.

Limited Time

When we have time constraints for solving a given problem, small data sets may be considered Big Data. For example, assume that we are interested in parsing 100 images each of size 256× 256× 3 in less than a millisecond → this small set of images, is considered as big data under the given time constraints.

New computation models

The streaming model

Here, the input data is streamed (“on-the-fly”). Data items enter one by one (or in batch/chunk form) into a system with limited memory that cannot store more than m points at a time. The objective here is to maintain the optimal solution (or a robust approximation to it) for the whole data received so far in the infinite stream.

The distributed model

The input data items come at multiple nodes (machines, on the cloud, networks, AWS, or GPUs) in a parallel setup, and the solution must be aggregated effectively at a root node. The aim in this case is to keep the optimal solution (or a close approximation to it) for the union of the datasets dispersed over all nodes.

Mislabeled input data

Data quality

Even when the data is correctly labeled, data scientists are interested in identifying important (high-quality) images. If we are dealing with a classification problem for dogs or cows, and we are given the following data set:

We can observe that the 4th image is very weird, as it is very strange to see a cow indoors. Hence this image is either (i) very important as it is one of a kind, and in this case, we should focus on such an image when we train our model to make sure we classify it correctly, or (ii) should be removed as it does not reflect the usual cases, and we do not want our model to take this image into consideration.

Coresets

A common practical and theoretically supported approach for solving the above challenges is called “coreset”. Coresets have been getting increased attention during the past year. Informally, a coreset is (usually) a small, weighted subset of the original input set of items, such that solving the problem on the coreset will yield the same solution as solving the problem on the original big data.

Defining a problem

To formally define and build coresets for a machine learning problem, first, we need to formally define all the ingredients required to form a machine learning problem. We now give the basic three ingredients to define an optimization problem:

1. The input data (denoted by ): this is the input (usually large) dataset, which we are interested in optimizing some cost function with respect to it.
2. The query set (denoted by ): this is the set of all possible candidate solutions/models, where usually the goal of ML, is to output a model from this set, which minimizes the desired cost function with respect to the input data.
3. The cost function we wish to optimize.

These three ingredients, formally define the optimization problem at hand. For example, in linear regression:

1. The input data is a set and their label function (red points in the figure).
2. The query set is the set of every vector in (the green line is an example of a query/candidate solution).
3. The cost function we wish to minimize is .

Defining a coreset

Given all the ingredient which defines/forms an optimization problem, i.e.,

• Let be an input set.
• Let be the query set – the set of candidate solutions.
• Let be a cost function.

Then, a coreset is a pair where and such that for every query

• .

Coresets Properties

Coreset has many interesting properties other than approximating the optimal solution of the original big data. In this article, we will summarize only three properties of coresets:

1. A coreset for an input data approximates the loss of the with respect to any query (candidate solution) and not only the optimal one, i.e., for every . This is very important to support streaming data and to show that optimal solutions, approximated solutions, or even heuristics on the coreset yields a good result on the full data.

   

2. A union of coresets is a coreset. Assume you are given a set that was partitioned into 5 subsets . For each of these subsets, we computed coreset, i.e., for every set we have computed its own coreset which satisfies for every
   Define the set and the weights function as the union of the five weight functions, we get that is a coreset for , i.e., for every

   

3. Coreset of a Coreset is a Coreset. Recall the set which is a coreset for the input data . We can further compute a coreset (once more) for to obtain a new smaller coreset . Now, for every

   1. and
   2. 

   Thus, is a (smaller) coreset for . We note that now the approximation error of is larger than the one of , as we computed a coreset for a coreset.

How to Compute a Coreset?

So now we understand that coreset is a kind of data summarization that gives a very strong approximation of the original data. But how can we compute a coreset for a given input dataset?

There are numerous algorithms and methods for computing coresets, each is given for some ML problem. However, mainly, these techniques can be divided into two classes:

1. Deterministic coresets: In this class, the algorithms which compute the coresets output a set that is guaranteed (100%) to give an approximation for the full data.
2. Sampling-based coresets: In this class, the algorithms which compute the coresets output a set that with a very high probability is a coreset.

Each of these classes has its pros and cons, for example, class 2, is probabilistic and may fail occasionally, but usually, all the algorithms falling in this class are very efficient, hence, giving very quick approximations of the original data. Furthermore, to compute a sampling-based coreset we can utilize the following famous importance sampling framework (which most of the recent papers use). The framework states the following:

1. Given the tuple which defines our ML problem at hand.
2. For every item be a number defining its importance/sensitivity – we will explain how to compute it next.

Once we have this defined and computed (the importance of each item in the set), the importance sampling framework applies the following simple steps to compute a coreset:

1. Set , i.e., t is the total (sum of) importance of all points.
2. Build the set as an i.i.d Sample of points according to The larger the m the better the approximation error of the final coreset.
3. For every define its weight as:

Then, with high probability, is a coreset for , i.e., and , such that for every query

.

Note. The sample (coreset) size is a function of the desired approximation error, probability of failure, total sensitivity t, and another problem-dependent measure of complexity. We will provide more theoretical detail and insights in future blog posts.

But how to compute the importance ?

Informally, the importance of a point/item is defined as the maximum contribution this point gives to the loss/cost function across all possible candidate solutions, i.e., if there exists such that is large with respect to then, is important to the query

The formal definition is given as follows:

• For every :
  

To explain the definition of sensitivity/importance let’s look at the following two cases, when is high and when is low and see the difference between them.

If is high

There exists a solution , such that affects the loss too much ( is important).

affects

If is low

For every solution does not affect the loss, hence, it is not important.

does not affect

Hence, we sample based on this measure, as it indicates whether there exists a solution in which our point contributes to its cost, so it is considered important with respect to this solution.