Concepts / Max-Margin Methods

Max-Margin Methods

Separating polynomials are functions of the form sign(p(x)), with p a degree-r polynomial on R^d.

  • Programming

From Polynomial Scores to Classes

A separating polynomial takes an input x in R^d, evaluates a degree-r polynomial p(x), and then uses the sign of that value as the classification rule. In compact form, the function is sign(p(x)). The important idea in max-margin methods is that this apparently nonlinear polynomial rule can be rewritten as a linear rule after changing the representation of the input.

evaluatetake signpositive signnegative signxinput in R^dp(x)degree-r polynomial scoresign(p(x))polynomial classifierpositive classnegative class
What happens to an input x as the polynomial is evaluated and its sign assigns x to one of two classes?

The polynomial itself produces a score. The classifier is obtained only after applying sign to that score. This distinction matters because the score can be rewritten as an inner product, while the final classification rule remains sign of that inner product.

Building the Feature Map

The representation change is the central step. Construct a feature map ψ(x) whose coordinates contain all monomials of x up to degree r. The coefficients of the polynomial are collected into a vector w. With this representation, the polynomial can be written as the inner product 〈w, ψ(x)〉. Thus the same score that was written as p(x) can also be written as 〈w, ψ(x)〉.

coordinatecoordinatecoordinatecoordinatecoordinatecoordinatecombine with w1degree 0 monomialψ(x)monomial representation〈w, ψ(x)〉polynomial scorex₁degree 1 monomialx₂degree 1 monomialx₁²degree 2 monomialx₁x₂degree 2 monomialx₂²degree 2 monomial
How does a degree-r polynomial become an inner product w·ψ(x), and which coordinates of ψ(x) correspond to polynomial monomials?

A Degree-Two Walkthrough

Rewriting a Two-Variable Polynomial

For illustration, consider the degree-two polynomial p(x₁, x₂) = 3 + 2x₁ − x₂ + 4x₁² + 5x₁x₂. Rewrite its score using a feature map and a coefficient vector.

List the monomials: For degree two, use the degree-zero, degree-one, and degree-two monomials appearing in the representation. One possible ordered feature map is ψ(x) = (1, x₁, x₂, x₁², x₁x₂, x₂²).

Collect coefficients: Match each monomial with its coefficient. The coefficient of x₂² is zero because that monomial does not appear in the chosen polynomial. This gives w = (3, 2, −1, 4, 5, 0).

Take the inner product: The inner product 〈w, ψ(x)〉 multiplies corresponding entries and adds them, reproducing 3 + 2x₁ − x₂ + 4x₁² + 5x₁x₂.

Apply the sign: The classifier is sign(〈w, ψ(x)〉), which is the same classification rule as sign(p(x)).

The polynomial classifier can be represented as sign(p(x)) = sign(〈w, ψ(x)〉) for the displayed feature map and coefficient vector.

This example shows the two levels of the construction. The feature map determines which monomial coordinates are available. The vector w supplies the coefficients used to combine those coordinates. Changing the order of the coordinates would require changing the order of the entries in w, but the inner-product representation would express the same polynomial when the pairing remains consistent.

Lifting the Compression Problem

After applying ψ, the polynomial score has the linear form 〈w, ψ(x)〉. Therefore, the polynomial classifier can be viewed as a halfspace classifier on the transformed inputs ψ(x). The original input lives in R^d, while the transformed representation lives in a higher-dimensional space R^d′. The source states that d′ = O(d^r).

maprepresent inuse wtake signxR^dψ(x)all monomials up to degreerR^d′d′ = O(d^r)〈w, ψ(x)〉linear scorehalfspace decisionsign(〈w, ψ(x)〉)
How does mapping x to ψ(x) transform sign(p(x)) into a linear halfspace decision in a higher-dimensional space?

This is a reduction, not a claim that the original polynomial is linear in its original coordinates. The polynomial becomes linear in the transformed coordinates supplied by ψ. Consequently, constructing a compression scheme for separating polynomials can be reduced to constructing a compression scheme for halfspaces in R^d′.

apply ψuse halfspace schemetransfer representationinput examplesx in R^dmapped examplesψ(x) in R^d′halfspace compressioncompressed representationpolynomial classifiersign(〈w, ψ(x)〉)
How can a compression scheme for halfspaces in the lifted feature space be used for the polynomial classifier?

The Role of the Vector w

The vector w has a dual role. Algebraically, it is the coefficient vector that forms the inner product 〈w, ψ(x)〉. Geometrically, the source identifies w as the direction of the max-margin solution. Thus the direction selected by the max-margin viewpoint supplies the direction used by the linear representation in feature space.

is the direction offormsequivalent sign rulewcoefficient vectormax-margin directionsolution directionsign(p(x))polynomial classifier〈w, ψ(x)〉feature-space score
How is w related to the maximum-margin separating hyperplane in feature space, and how does it determine the polynomial classifier?

When reading a proof or compression argument, identify w before focusing on the final classifier. It is both the coefficient vector in the inner product and the direction associated with the max-margin solution.

Common Representation Mistakes

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

    The feature map contains all monomials of x up to degree r, not just the original coordinates.

    Fix: List the monomial coordinates required by the chosen degree before forming the inner product.

  • Saying that p(x) is linear in the original input coordinates.

    The polynomial may be nonlinear in x. It is represented as a linear inner product only after the input is changed to ψ(x).

    Fix: Say that p(x) becomes a linear expression in the transformed feature coordinates.

  • Forgetting the sign operation.

    The inner product is the polynomial score. The separating polynomial function is sign(p(x)), equivalently sign(〈w, ψ(x)〉).

    Fix: Separate the score from the final sign-based decision.

  • Confusing the coefficient vector with an arbitrary feature.

    The monomials are coordinates of ψ(x), while w supplies the coefficients used in the inner product.

    Fix: Keep the roles distinct: ψ(x) contains monomial features and w weights them.

  • Claiming that the compression reduction stays in R^d.

    The reduction uses the lifted representation in R^d′, where d′ = O(d^r).

    Fix: Track the dimension change created by the feature map.

Practice the Reduction

MEDIUM

Suppose p is a degree-r polynomial on R^d. Explain, in three linked statements, how to turn sign(p(x)) into a halfspace decision. Then state what the source says about the dimension of the transformed space and identify the role of w.

Hints
  • Begin by describing what ψ(x) contains.
  • Write the polynomial score as an inner product.
  • Finish by connecting the transformed problem to halfspaces and the max-margin direction.

A strong answer should include the sequence: ψ(x) contains all monomials up to degree r; p(x) is written as 〈w, ψ(x)〉; sign(p(x)) becomes sign(〈w, ψ(x)〉), a halfspace decision in R^d′; and d′ = O(d^r). It should also state that w is the direction of the max-margin solution.

Key Takeaways

  1. A separating polynomial is a function of the form sign(p(x)), with p a degree-r polynomial on R^d.
  2. The feature map ψ(x) contains all monomials of x up to degree r.
  3. The polynomial score can be rewritten as the inner product 〈w, ψ(x)〉.
  4. This representation turns the polynomial classification problem into a halfspace problem in R^d′, where d′ = O(d^r), so compression for the polynomial reduces to compression for halfspaces in the lifted space.
  5. The vector w is the coefficient vector in the inner-product representation and the direction of the max-margin solution.

Key Takeaways

  • Separating polynomials classify inputs using sign(p(x)) for a degree-r polynomial p.
  • The feature map ψ(x) records all monomials up to degree r, allowing p(x) to be written as 〈w, ψ(x)〉.
  • The transformed classifier is a halfspace classifier in a higher-dimensional space R^d′ with d′ = O(d^r).
  • Compression for separating polynomials can therefore be approached through compression for halfspaces in the lifted space.
  • The vector w supplies the inner-product coefficients and points in the direction of the max-margin solution.

Related Topics

  • Halfspaces
  • Feature Maps
  • Compression Schemes
  • Maximum-Margin Classification