Compression Schemes for Halfspaces

Why Change the Representation

A separating polynomial classifies an input x by evaluating a polynomial p(x) and then taking its sign. The resulting function has the form sign(p(x)), where p is a degree-r polynomial on R^d. The key compression idea is not to compress the polynomial in its original coordinates directly. Instead, rewrite the polynomial as a linear expression in a new representation of the input. After this change of representation, the problem becomes a halfspace problem in a higher-dimensional space.

Separating Polynomial Functions

The polynomial p(x) produces a real-valued score. Taking its sign turns that score into the class decision represented by the function. The important point for compression is that p may contain monomials of different degrees, while the sign operation uses the final value of the whole polynomial.

The before-and-after view does not change the function being represented. It changes the description of the score: p(x) is rewritten as an inner product involving ψ(x). That rewritten score is what exposes the halfspace structure.

Building the Feature Map

The feature map ψ(x) is formed from all monomials of x up to degree r. Each monomial becomes a coordinate in the transformed representation. The coefficients of the polynomial are collected into a vector w with matching coordinates.

The coordinates of ψ(x) and w are paired by monomial type. A coordinate for a particular monomial in ψ(x) is multiplied by the coefficient for that same monomial in w. Adding these coordinate-wise products gives the inner product ⟨w, ψ(x)⟩, which represents p(x).

A Concrete Polynomial Rewrite

The Halfspace Reduction

Once p(x) is written as ⟨w, ψ(x)⟩, the separating-polynomial function becomes sign(⟨w, ψ(x)⟩). This has the form of a halfspace decision in the transformed feature space. The original input belongs to R^d, but the feature representation belongs to a higher-dimensional space R^d′, where d′ = O(d^r).

This is a reduction of compression problems. To construct a compression scheme for separating polynomials, construct a compression scheme for halfspaces in the transformed space. The polynomial problem is therefore approached through the halfspace problem after the representation change.

The Role of the Vector w

The vector w has two linked interpretations. Algebraically, it is the coefficient vector that lets the polynomial score be written as ⟨w, ψ(x)⟩. Geometrically, it supplies the direction used by the halfspace representation in feature space. The source identifies w as the direction of the max-margin solution.

Mistakes in the Reduction

• Treating ψ(x) as the original input x.

  The reduction depends on replacing x with a representation containing all monomials up to degree r.

  Fix: Track the feature map explicitly and write the score as ⟨w, ψ(x)⟩.

• Leaving polynomial coefficients out of w.

  The inner product reproduces p(x) only when the coordinates of w match the coefficients of the corresponding monomials.

  Fix: Pair every monomial coordinate in ψ(x) with its polynomial coefficient in w.

• Assuming the transformed problem is still in R^d.

  The reduction uses a feature space R^d′, with d′ = O(d^r).

  Fix: Distinguish the original input dimension d from the transformed dimension d′.

• Confusing the sign decision with the polynomial score.

  p(x) is the score, while sign(p(x)) is the separating-polynomial function.

  Fix: Keep the two stages separate: compute the polynomial score, then take its sign.

• Describing w only as a coefficient list.

  The source also identifies w as the direction of the max-margin solution.

  Fix: State both roles: w represents polynomial coefficients and gives the relevant feature-space direction.

Practice the Representation Change

Key Takeaways

1. A separating polynomial is a function of the form sign(p(x)), where p is a degree-r polynomial on R^d.
2. The feature map ψ(x) contains all monomials of x up to degree r.
3. With the polynomial coefficients collected in w, the score can be written as ⟨w, ψ(x)⟩.
4. The decision sign(⟨w, ψ(x)⟩) is a halfspace decision in a higher-dimensional space R^d′, where d′ = O(d^r).
5. The vector w is both the coefficient vector in the inner-product representation and the direction of the max-margin solution.