Feature Representations in Machine Learning
Separating polynomials are functions of the form sign(p(x)), with p a degree-r polynomial on R^d.
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.
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)〉.
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?
Collect the monomials: List every monomial of x that appears in the polynomial, including all monomials whose degree is up to r.
Build ψ(x): Use those monomials as the coordinates of the feature representation ψ(x).
Build w: Place the corresponding polynomial coefficients in a vector w aligned with the coordinates in ψ(x).
Take the inner product: The aligned coefficient and feature vectors combine as 〈w, ψ(x)〉, which represents the same polynomial score p(x).
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.
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.
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.
- Start with an input x in R^d and a degree-r polynomial classifier sign(p(x)).
- Construct ψ(x) from all monomials of x up to degree r.
- Choose w so that the polynomial is written as 〈w, ψ(x)〉.
- Treat the resulting representation as a halfspace problem in R^d′.
- 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.
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.
Common Interpretation Errors
Treating ψ(x) as a single new feature rather than a representation containing many coordinates.
The reduction depends on placing the monomials into coordinates so that the polynomial can be expressed as an inner product.
Fix:
Think of ψ(x) as a feature vector whose coordinates are the monomials appearing up to degree r.Assuming the polynomial remains nonlinear after the representation change.
The central reduction is based on viewing the polynomial as a linear expression in the transformed coordinates.
Fix:
Separate the two viewpoints: the classifier is polynomial in the original coordinates, but linear in the feature representation.Confusing the original dimension d with the transformed dimension d′.
The feature map creates a higher-dimensional representation, with d′ = O(d^r) according to the source.
Fix:
Track the space explicitly: x is in R^d, while the halfspace representation is in R^d′.Treating w as unrelated to the geometry of the transformed problem.
The source also identifies w as the direction of the max-margin solution.
Fix:
Remember both roles: w contains the coefficients for the inner product and gives the max-margin direction in feature space.
Compression Checklist
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
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.
What do you think happens?
After rewriting p(x) as 〈w, ψ(x)〉, which object supplies the direction of the max-margin solution?
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
- A separating polynomial is a classifier of the form sign(p(x)), with p a degree-r polynomial on R^d.
- The feature map ψ(x) contains all monomials of x up to degree r.
- The polynomial can be rewritten as the inner product 〈w, ψ(x)〉.
- This representation reduces compression for separating polynomials to compression for halfspaces in R^d′, where d′ = O(d^r).
- The vector w is both 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)〉.
- 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.