Feature Representations in Machine Learning

When a compression argument refers to the max-margin solution, identify w as the vector that both appears in the inner product and gives the direction of the max-margin solution in the transformed feature space.

Programming

From Polynomial Scores to Classifiers

A separating polynomial starts with a polynomial score p(x), where the input x belongs to R^{^d} and p has degree r. The classifier is formed by taking sign(p(x)). In other words, the polynomial produces a score, and the sign of that score determines which side of the separation the input belongs to.

Definition

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

The central idea is not to change the polynomial itself, but to change how the input is represented. The input is mapped to a feature vector ψ(x) containing the monomials of x up to degree r. In that representation, the same polynomial can be viewed as a linear expression.

A Polynomial as a Coordinate Combination

Every term in a degree-r polynomial is a monomial of the input coordinates with degree no greater than r. The feature map ψ(x) collects those monomials as coordinates. The coefficients that multiply those monomials are collected into a vector w. Once both collections are aligned, the polynomial is rewritten as the inner product 〈w, ψ(x)〉.

How do the monomials of p(x) become coordinates of ψ(x), and how do the coefficients in w combine with them to produce the polynomial score?

Worked example

Reading the Feature Representation

Suppose a degree-r polynomial has several monomial terms. How should its coefficients and monomials be organized to obtain an inner-product representation?

1
Collect the monomials
List every monomial of x that appears in the polynomial, including all monomials whose degree is up to r.
2
Build ψ(x)
Use those monomials as the coordinates of the feature representation ψ(x).
3
Build w
Place the corresponding polynomial coefficients in a vector w aligned with the coordinates in ψ(x).
4
Take the inner product
The aligned coefficient and feature vectors combine as 〈w, ψ(x)〉, which represents the same polynomial score p(x).

Result

The polynomial is represented as p(x) = 〈w, ψ(x)〉. The feature map supplies the monomial coordinates, while w supplies their coefficients.

The Separation Before and After Mapping

In the original input space, the classifier is described by sign(p(x)). The polynomial score separates inputs according to the sign of its value, producing positive and negative classification regions. After the representation change, the score is written as 〈w, ψ(x)〉, so the same classifier is described using a linear inner product in the feature space.

How does the sign of a degree-r polynomial divide the input space into positive and negative classification regions?

The important distinction is between the original space and the feature space. The original description may look nonlinear because p contains monomials. The transformed description is linear because the monomials have become coordinates and the polynomial is expressed through an inner product.

Compression Through Feature Space

The feature representation turns the polynomial compression problem into a halfspace compression problem. First map each input x in R^{^d} to ψ(x). Then represent the polynomial classifier using the inner product 〈w, ψ(x)〉. In the transformed space, the hypothesis has the form associated with a halfspace.

How does mapping x to ψ(x) transform a polynomial separator in the original space into a linear halfspace separator in a higher-dimensional feature space?

The transformed dimension is denoted d′, and the source states that d′ = O(d^{^r}). Therefore, constructing a compression scheme for separating polynomials reduces to constructing a compression scheme for halfspaces in R^{^d}′. The reduction works because the representation change preserves the classifier while changing the form in which it is expressed.

1
Start with an input x in R^{^d} and a degree-r polynomial classifier sign(p(x)).
2
Construct ψ(x) from all monomials of x up to degree r.
3
Choose w so that the polynomial is written as 〈w, ψ(x)〉.
4
Treat the resulting representation as a halfspace problem in R^{^d}′.
5
Use the halfspace compression perspective for the transformed problem.

The Geometric Role of w

The vector w is the coefficient vector in the representation p(x) = 〈w, ψ(x)〉. It is also the direction of the max-margin solution. This gives w two connected interpretations: algebraically, it combines the feature coordinates to reproduce the polynomial score; geometrically, it supplies the direction used by the corresponding halfspace in feature space.

What does w represent geometrically, and how does it correspond to the max-margin halfspace in feature space?

Key point

Common Interpretation Errors

Common mistake
Treating ψ(x) as a single new feature rather than a representation containing many coordinates.
What it looks like
Reading ψ(x) as one value instead of as the collection of all monomials of x up to degree r.
Why it fails
The reduction depends on placing the monomials into coordinates so that the polynomial can be expressed as an inner product.
Do this instead
Think of ψ(x) as a feature vector whose coordinates are the monomials appearing up to degree r.
Common mistake
Assuming the polynomial remains nonlinear after the representation change.
What it looks like
Stopping at sign(p(x)) and overlooking the representation 〈w, ψ(x)〉.
Why it fails
The central reduction is based on viewing the polynomial as a linear expression in the transformed coordinates.
Do this instead
Separate the two viewpoints: the classifier is polynomial in the original coordinates, but linear in the feature representation.
Common mistake
Confusing the original dimension d with the transformed dimension d′.
What it looks like
Describing the halfspace problem as one in R^d rather than R^d′.
Why it fails
The feature map creates a higher-dimensional representation, with d′ = O(d^{^r}) according to the source.
Do this instead
Track the space explicitly: x is in R^d, while the halfspace representation is in R^d′.
Common mistake
Treating w as unrelated to the geometry of the transformed problem.
What it looks like
Calling w only a list of polynomial coefficients.
Why it fails
The source also identifies w as the direction of the max-margin solution.
Do this instead
Remember both roles: w contains the coefficients for the inner product and gives the max-margin direction in feature space.

Compression Checklist

Best practice

When reading or constructing a compression argument for separating polynomials, inspect the representation change before looking for the compression mechanism itself. Ask what ψ(x) contains, how p(x) is written using w and ψ(x), and which hypothesis class appears after the rewriting. The answers should identify the monomial representation, the inner product 〈w, ψ(x)〉, and halfspaces in R^d′.

Question	Answer in this setting
What does ψ(x) contain?	All monomials of x up to degree r
How is p(x) rewritten?	As 〈w, ψ(x)〉
What class appears after rewriting?	Halfspaces in R^{^d}′
What is the role of w?	Coefficient vector and direction of the max-margin solution

The four checkpoints for following the feature-representation reduction

Check Your Understanding

MEDIUM

Explain in your own words why a compression scheme for halfspaces can be relevant to separating polynomials after applying the feature map ψ(x). Your answer should mention the monomial coordinates, the inner product with w, and the transformed dimension d′.

Hints

Begin with the form sign(p(x)).
State what is placed into ψ(x).
Rewrite the polynomial using 〈w, ψ(x)〉.
Identify the resulting hypothesis class and its space.

Your attempt (not saved)

What do you think happens?

After rewriting p(x) as 〈w, ψ(x)〉, which object supplies the direction of the max-margin solution?

The original input x
The monomial list by itself
The vector w
The transformed dimension d′

Reveal answer

Answer:

The vector w

The source identifies w as the vector in the inner-product representation and as the direction of the max-margin solution.

Key Takeaways

1
A separating polynomial is a classifier 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 can be rewritten as the inner product 〈w, ψ(x)〉.
4
This representation reduces compression for separating polynomials to compression for halfspaces in 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.

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)〉.
After this representation change, the problem becomes a halfspace problem in a higher-dimensional space R^{^d}′.
The transformed dimension satisfies d′ = O(d^{^r}).
The vector w represents the polynomial coefficients and gives the direction of the max-margin solution.

Related concepts

More concepts starting with F

From Polynomial Scores to Classifiers

A Polynomial as a Coordinate Combination

The Separation Before and After Mapping

Compression Through Feature Space

The Geometric Role of w

Common Interpretation Errors

Compression Checklist

Check Your Understanding

Key Takeaways

At a glance

Related Topics

Related concepts