Concepts / Kernel Methods for Support Vector Machines

Kernel Methods for Support Vector Machines

The coefficient vector is written as α and belongs to R^m.

  • Programming

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.

High-dimensionalfeature spaceSmall samplecomplexityNorm regularizationComputational helpcreates two concernshelps yieldhelps overcome
How does norm regularization address the two related concerns identified for high-dimensional SVM optimization?

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.

x_1training inputψ(x_1)mapped examplewoptimal vectorx_mtraining inputψ(x_m)mapped examplemapmapweighted contributionweighted contribution
How is the optimal vector w constructed from the mapped training examples ψ(x_i)?
Formula

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 Rm. 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.

α_1coefficientψ(x_1)mapped training examplewresulting optimal vectorα_mcoefficientψ(x_m)mapped training exampleweightsweightscontributescontributes
How does each coefficient α_i connect to the corresponding mapped example ψ(x_i), and how do they combine to form w?
SymbolRoleSpace or size
αVector of weights for the mapped training examplesBelongs to Rm and contains m coefficients
α_iWeight for the mapped example ψ(x_i)One coefficient associated with training input x_i
wResulting optimal vectorA vector in the Hilbert space

The coefficient vector α and the optimal vector w are related, but they are not the same object.

A symbolic reconstruction

Worked example

Writing an optimal solution in Representer form

Suppose the training inputs are x_1 through x_m and the coefficient vector is α in Rm. Rewrite an optimal solution w using the mapped training examples.

  1. 1
    Map each input

    Represent each training input x_i in the Hilbert space as ψ(x_i).

  2. 2
    Match coefficients to examples

    Associate α_i with the corresponding mapped example ψ(x_i). The index i identifies both the coefficient and the training input.

  3. 3
    Form the weighted sum

    Multiply each ψ(x_i) by α_i and add the resulting contributions over all m training examples.

  4. 4
    Interpret the result

    The resulting sum is an optimal solution w whose form is guaranteed to exist by the Representer Theorem.

Result

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

Definition

The Representer Theorem guarantees the existence of a coefficient vector α in Rm such that an optimal solution w is a weighted sum of the mapped training examples ψ(x_1) through ψ(x_m).

Training inputsx_1 through x_mMapped examplesψ(x_1) through ψ(x_m)Optimal wweighted sumα in R^m suitable coefficient vectorexistsmapcombine with weightssupplies weights
Why can an optimal solution be represented within the span of the mapped training examples?

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

Weighted-sum formw uses ψ(x_i)Numerical α valuesnot supplied by theoremSuitable α existsα belongs to R^m Every possible wnot claimedtheorem guarantees
Which facts does the theorem guarantee about the form of w, and which details must be determined by optimization?
  • Common mistake

    Treating α as another name for w.

    What it looks like

    Writing that α is the optimal vector in the Hilbert space.

    Why it fails

    α is a vector of m coefficients in Rm, while w is the resulting vector in the Hilbert space.

    Do this instead

    Describe α as supplying the weights and w as the weighted sum of the mapped training examples.

  • Common mistake

    Claiming that the theorem gives the numerical values of α.

    What it looks like

    Concluding that the theorem alone tells you each α_i.

    Why it fails

    The theorem guarantees the existence of a suitable coefficient vector but does not provide its numerical values by itself.

    Do this instead

    Separate the theorem's structural guarantee from the optimization process that determines particular coefficients.

  • Common mistake

    Claiming that every vector w must be a weighted sum of the mapped training examples.

    What it looks like

    Replacing the statement about an optimal solution with a statement about all possible vectors.

    Why it fails

    The theorem's statement concerns the existence of an optimal solution of the relevant optimization problem with this form.

    Do this instead

    State the guarantee narrowly: an optimal solution can be represented in this way.

  • Common mistake

    Listing only the computational benefit of norm regularization.

    What it looks like

    Explaining regularization only as a way to make optimization easier.

    Why it fails

    The source identifies both computational help and small sample complexity in high-dimensional feature spaces.

    Do this instead

    Mention both benefits when explaining why the norm of w is regularized.

Check your understanding

MEDIUM

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 Rm. 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 Rm, what does that tell you about its relationship to the training inputs?

  • It supplies m coefficients, one for each training input

  • It is the same vector as w

  • It supplies one coefficient for every possible vector in the Hilbert space

Reveal answer
Answer:

It supplies m coefficients, one for each training input.

The coefficient vector α belongs to Rm, and α_i weights the mapped training example ψ(x_i).

Key takeaways

  1. 1
    Regularizing the norm of w helps keep sample complexity small in high-dimensional feature spaces and helps overcome computational difficulty.
  2. 2
    For training inputs x_1 through x_m, each input is mapped to ψ(x_i) in the Hilbert space.
  3. 3
    The Representer Theorem guarantees an optimal solution of the form w = α_1 ψ(x_1) + ... + α_m ψ(x_m).
  4. 4
    α belongs to Rm and supplies the weights; w is the resulting vector in the Hilbert space.
  5. 5
    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.

At a glance

  • 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 Rm, 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.

Related Topics

Related concepts

More concepts starting with K