Linear Separability

A Smaller Description

Suppose a training set can be classified perfectly by some predictor. A compression scheme asks whether the entire training set is necessary to describe that predictor. Instead of keeping every training example, the scheme selects or creates a smaller representation and then reconstructs a predictor from it. In the realizable case, the important requirement is that the reconstructed predictor makes zero mistakes on the original training set.

From Training Set to Predictor

The compression algorithm is represented by A: it receives the training set and produces a smaller representation. The reconstruction function B receives that representation and produces a predictor. In the realizable case, the required outcome is that the predictor reconstructed as B(A(S)) has zero loss on S. The original examples do not all need to be stored if the reconstruction procedure can recover a correct classifier from the smaller description.

Extremal Positive Examples

For linearly separable data, a hyperplane separates the positive examples from the negative examples. The extremal-example construction uses two positive examples per dimension. These examples are selected because their extreme positions help describe the geometry needed for a separating classifier, rather than because every training example must be remembered.

The geometric justification uses the convex hull of the relevant positive examples. When that convex hull does not contain the origin, the point in the convex hull closest to the origin can be used to obtain a separating direction. Thus, the retained examples are useful because they preserve the geometry supporting separation. They are not merely an arbitrary sample of the training set.

The Perceptron Route

A different compression route uses the Perceptron algorithm. The Perceptron searches for a separating hyperplane. When the training set is separated with margin gamma, the algorithm makes at most 1 divided by gamma squared updates before reaching a solution that makes no mistakes on the entire training set.

The examples involved in the Perceptron updates can serve as a compressed description. Since there are no more than 1 divided by gamma squared updates, the compression size k is no larger than 1 divided by gamma squared. This connects an algorithmic event, an update, to a bound on how much information may be needed to describe the resulting classifier.

Polynomial Features

A polynomial classifier may look nonlinear when viewed in the original input coordinates. It can nevertheless be treated as a halfspace problem after transforming the input. Let psi(x) contain all monomials of x up to degree r. The polynomial expression p(x) can then be written as the inner product of w and psi(x). The classifier is analyzed in this transformed feature space rather than directly in the original coordinates.

The transformation changes the representation, not the underlying classification task. In the transformed space, polynomial classification becomes halfspace classification. Therefore, the compression question can be studied using the same halfspace machinery, but with the transformed dimension d prime, which is O(d to the r) when monomials through degree r are included.

Geometric Meaning

Linear separability means that some hyperplane separates the positive and negative examples. This condition is the geometric foundation for the compression constructions described here. The extremal-example method relies on the geometry of a convex hull and its closest point to the origin, while the Perceptron method searches for a separating hyperplane and uses the margin to bound its updates.

Mistakes to Avoid

• Treating compression as ordinary data deletion.

  A compression scheme includes both a method for creating the representation and a reconstruction function. The goal is not merely to discard examples; it is to recover a predictor with zero training loss in the realizable case.

  Fix: Always identify the compressed representation and explain how the reconstruction procedure produces the predictor.

• Assuming every original training example must be retained.

  The purpose of compression is to retain a smaller representation that still determines a correct predictor on the training set.

  Fix: Ask which examples or update history support reconstruction, rather than counting all original examples.

• Confusing the two compression bounds.

  The extremal-example construction uses k = 2d, while the Perceptron route gives a size no larger than 1 divided by gamma squared when the margin is gamma.

  Fix: Match each bound to its construction: 2d for extremal positive examples and 1 divided by gamma squared for Perceptron updates.

• Analyzing a polynomial classifier only in the original coordinates.

  Polynomial classification can be rewritten as halfspace classification after mapping x to psi(x).

  Fix: Move the analysis to the transformed feature space and use its dimension d prime.

Check Your Understanding

Key Takeaways

1. A compression scheme replaces a realizable training set with a smaller representation and reconstructs a predictor with zero training loss.
2. For linearly separable data, extremal positive examples can support reconstruction; the construction uses two positive examples per dimension, giving k = 2d.
3. The Perceptron gives another compression route: with margin gamma, it makes at most 1 divided by gamma squared updates, so the compression size is no larger than that bound.
4. Polynomial classification can be rewritten as halfspace classification in the feature space produced by psi(x), whose dimension is d prime = O(d to the r) when monomials through degree r are used.
5. The geometric foundation is linear separability: a hyperplane separates the positive and negative examples.