Compression Bounds in Machine Learning

A learning problem may involve a large collection of positive examples, but the reconstructed hypothesis does not always need to retain every example. For axis aligned rectangles, the important examples are the ones that determine the outer limits of the positive region. The compression scheme keeps those boundary-defining examples, then reconstructs a rectangle from them.

This gives the topic its central idea: the hypothesis class can be uncountably infinite, yet a particular sample can be represented by a finite collection of carefully selected examples. Algorithm A performs the selection, and function B performs the reconstruction.

The class of axis aligned rectangles is uncountable and infinite. The reason is that rectangle boundaries can vary along the coordinate axes, producing continuously many possible boundary choices. The compression result is therefore not based on listing every rectangle in the class. Instead, it shows that a sample can be summarized by a small number of selected positive examples.

Algorithm A examines the positive examples dimension by dimension. In each dimension, it selects two positive examples with extremal values: one associated with the minimum value and one associated with the maximum value. These examples preserve the outer limits that the reconstructed rectangle must respect.

Function B receives the examples retained by algorithm A. It returns the minimal enclosing rectangle of those selected examples. Minimal enclosing means that the returned axis aligned rectangle contains the selected examples while using the smallest coordinate-wise boundaries determined by them.

The two parts of the scheme have different responsibilities. Algorithm A decides which examples are worth keeping. Function B turns those retained examples into one rectangle. The reconstruction works because the retained examples preserve the minimum and maximum limits in every dimension.

The compression size is determined by the number of dimensions. In each of the d dimensions, algorithm A makes two extremal selections: one for the minimum and one for the maximum. Therefore the total compression size is k = 2d.

The source gives the result L_S(B(A(S))) = 0 for k = 2d in the realizable case. Here, A selects the extremal positive examples, and B returns their minimal enclosing rectangle. A zero value for the stated loss on S means that the reconstructed hypothesis makes no error on the sample S under the realizable-case assumption.

This result should be read carefully. It concerns the loss on the sample S in the realizable case. It does not say that every possible example outside the stated sample is automatically classified without error.