Kernel Methods for Support Vector Machines
Regularizing the norm of w helps both sample complexity and computation.
The high-dimensional optimization problem
In the SVM optimization problems from the previous chapter, the vector w is a central part of the solution. The difficulty is that the feature space may have high dimensionality, so working directly with w can create a computational problem. Regularizing the norm of w provides a useful response to this difficulty. In the SVM setting, it helps keep sample complexity small even when the feature space is high-dimensional, and it also helps overcome the computational problem.
Mapping the training inputs
Let the training inputs be x_1 through x_m. Kernel methods represent each input x_i in a Hilbert space through the mapping ψ(x_i). The Representer Theorem says that an optimal solution w can be expressed using these mapped training examples. The important structural move is therefore to stop treating the optimal w as an unrelated object and instead describe it through the training examples after mapping.
w = α_1 ψ(x_1) + α_2 ψ(x_2) + ... + α_m ψ(x_m)This expression says that each mapped training example contributes to w after being multiplied by a coefficient. The sum combines all of those contributions into the optimal vector. The theorem does not say that every possible vector w must be expressible this way. Its claim concerns the existence of an optimal solution with this form.
Reading the coefficient vector
The coefficient vector is written as α and belongs to R^m. That means α contains m coefficients, one corresponding to each of the m training inputs. The coefficient α_i determines the contribution of the mapped example ψ(x_i) in the weighted sum for w.
| Symbol | Role | Space or size |
|---|---|---|
| α | Vector of weights for the mapped training examples | Belongs to R^m and contains m coefficients |
| α_i | Weight for the mapped example ψ(x_i) | One coefficient associated with training input x_i |
| w | Resulting optimal vector | A vector in the Hilbert space |
A symbolic reconstruction
Writing an optimal solution in Representer form
Suppose the training inputs are x_1 through x_m and the coefficient vector is α in R^m. Rewrite an optimal solution w using the mapped training examples.
Map each input: Represent each training input x_i in the Hilbert space as ψ(x_i).
Match coefficients to examples: Associate α_i with the corresponding mapped example ψ(x_i). The index i identifies both the coefficient and the training input.
Form the weighted sum: Multiply each ψ(x_i) by α_i and add the resulting contributions over all m training examples.
Interpret the result: The resulting sum is an optimal solution w whose form is guaranteed to exist by the Representer Theorem.
An optimal solution can be written as w = α_1 ψ(x_1) + α_2 ψ(x_2) + ... + α_m ψ(x_m).
Notice what this reconstruction does and does not do. It correctly identifies the structure of the solution and the role of every index. It does not calculate particular numerical values for α. The theorem guarantees that a suitable α exists, but the theorem by itself does not provide those values.
The theorem's exact guarantee
The Representer Theorem guarantees the existence of a coefficient vector α in R^m such that an optimal solution w is a weighted sum of the mapped training examples ψ(x_1) through ψ(x_m).
The phrase existence of a suitable α is essential. The theorem provides the representational form of an optimal solution. It does not claim that every possible vector w has this form, and it does not select the numerical coefficient values for you.
Guarantee versus determination
Treating α as another name for w.
α is a vector of m coefficients in R^m, while w is the resulting vector in the Hilbert space.
Fix:
Describe α as supplying the weights and w as the weighted sum of the mapped training examples.Claiming that the theorem gives the numerical values of α.
The theorem guarantees the existence of a suitable coefficient vector but does not provide its numerical values by itself.
Fix:
Separate the theorem's structural guarantee from the optimization process that determines particular coefficients.Claiming that every vector w must be a weighted sum of the mapped training examples.
The theorem's statement concerns the existence of an optimal solution of the relevant optimization problem with this form.
Fix:
State the guarantee narrowly: an optimal solution can be represented in this way.Listing only the computational benefit of norm regularization.
The source identifies both computational help and small sample complexity in high-dimensional feature spaces.
Fix:
Mention both benefits when explaining why the norm of w is regularized.
Check your understanding
Write the Representer Theorem's representation of an optimal w using training inputs x_1 through x_m, their mapped versions ψ(x_i), and a coefficient vector α in R^m. Then state one fact the theorem guarantees and one fact it does not specify.
Hints
- Use one coefficient α_i for each mapped example ψ(x_i).
- The theorem concerns the existence of an optimal solution with the stated form.
- The theorem does not provide the numerical values of α by itself.
What do you think happens?
If you know that α is in R^m, what does that tell you about its relationship to the training inputs?
Reveal answer
Answer: It supplies m coefficients, one for each training input.
The coefficient vector α belongs to R^m, and α_i weights the mapped training example ψ(x_i).
Key takeaways
- Regularizing the norm of w helps keep sample complexity small in high-dimensional feature spaces and helps overcome computational difficulty.
- For training inputs x_1 through x_m, each input is mapped to ψ(x_i) in the Hilbert space.
- The Representer Theorem guarantees an optimal solution of the form w = α_1 ψ(x_1) + ... + α_m ψ(x_m).
- α belongs to R^m and supplies the weights; w is the resulting vector in the Hilbert space.
- The theorem guarantees the existence and form of a suitable representation, but it does not provide numerical values for α or claim that every possible w has that form.
Key Takeaways
- Norm regularization addresses both sample complexity and computation in high-dimensional SVM settings.
- The Representer Theorem rewrites an optimal w as a weighted sum of mapped training examples.
- The coefficient vector α is in R^m, and each α_i weights the corresponding ψ(x_i).
- The theorem guarantees that a suitable representation exists, not the numerical values of α.
- The guarantee applies to an optimal solution of the relevant optimization problem, not to every possible vector w.