Max-Margin Methods

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.

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.

What happens to an input x as the polynomial is evaluated and its sign assigns x to one of two classes?

Key point

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)〉.

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

Worked example

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.

1
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₂²).
2
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).
3
Take the inner product
The inner product 〈w, ψ(x)〉 multiplies corresponding entries and adds them, reproducing 3 + 2x₁ − x₂ + 4x₁² + 5x₁x₂.
4
Apply the sign
The classifier is sign(〈w, ψ(x)〉), which is the same classification rule as sign(p(x)).

Result

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}).

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}′.

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.

How is w related to the maximum-margin separating hyperplane in feature space, and how does it determine the polynomial classifier?

Key point

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

Common mistake
Treating ψ(x) as the original vector x.
What it looks like
Writing ψ(x) = x even though the polynomial has degree greater than one.
Why it fails
The feature map contains all monomials of x up to degree r, not just the original coordinates.
Do this instead
List the monomial coordinates required by the chosen degree before forming the inner product.
Common mistake
Saying that p(x) is linear in the original input coordinates.
What it looks like
Calling a term such as x₁x₂ a linear term in x.
Why it fails
The polynomial may be nonlinear in x. It is represented as a linear inner product only after the input is changed to ψ(x).
Do this instead
Say that p(x) becomes a linear expression in the transformed feature coordinates.
Common mistake
Forgetting the sign operation.
What it looks like
Identifying 〈w, ψ(x)〉 itself as the classifier.
Why it fails
The inner product is the polynomial score. The separating polynomial function is sign(p(x)), equivalently sign(〈w, ψ(x)〉).
Do this instead
Separate the score from the final sign-based decision.
Common mistake
Confusing the coefficient vector with an arbitrary feature.
What it looks like
Describing w as one of the monomials in ψ(x).
Why it fails
The monomials are coordinates of ψ(x), while w supplies the coefficients used in the inner product.
Do this instead
Keep the roles distinct: ψ(x) contains monomial features and w weights them.
Common mistake
Claiming that the compression reduction stays in R^{^d}.
What it looks like
Applying a halfspace compression result directly without changing the representation.
Why it fails
The reduction uses the lifted representation in R^{^d}′, where d′ = O(d^{^r}).
Do this instead
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.

Your attempt (not saved)

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.

At a glance

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 concepts

More concepts starting with M