Skip to main content
Cross Validated

Return to Question

Notice removed Draw attention by Pugl
Bounty Ended with galoosh33's answer chosen by Pugl
Tweeted twitter.com/StackStats/status/986270753732653057
added 799 characters in body
Source Link
Pugl
Pugl
  • 1.5k
  • 3
  • 24
  • 45

I believe that I have somewhat an understanding of the objective and loss functions associated with Support Vector Machines (SVM), however, one point is still confusing me: The fact that the margins of the SVM can be characterized only by the Support Vectors is often named as a reason for their efficient optimization.

What I do not understand is this: To know what the Support Vectors will be, doesn't the algorithm have to consider all the datapoints in the beginning? I.e. is this sparse representation not only possible after training?

Edit: Here is an example:

In other words, if all data points other than the support vectors were removed, the algorithm would find the same solution. This property, known as sparseness, has many consequences, both in the implementation and in the analysis of the algorithm

From this paper: Cristianini, N. and Scholkopf, B. (2002). Support Vector Machines and Kernel Methods: The New Generation of Learning Machines, page 39.

So, I understand how the (hinge) loss function looks like, how we come to this function at all, and how derivation can lead to a solution - but I guess I don't understand how this is algorithmically implemented such that only the support vectors are needed (from when on are only these needed, how exactly does this affect the SVM optimization?)

I believe that I have somewhat an understanding of the objective and loss functions associated with Support Vector Machines (SVM), however, one point is still confusing me: The fact that the margins of the SVM can be characterized only by the Support Vectors is often named as a reason for their efficient optimization.

What I do not understand is this: To know what the Support Vectors will be, doesn't the algorithm have to consider all the datapoints in the beginning? I.e. is this sparse representation not only possible after training?

I believe that I have somewhat an understanding of the objective and loss functions associated with Support Vector Machines (SVM), however, one point is still confusing me: The fact that the margins of the SVM can be characterized only by the Support Vectors is often named as a reason for their efficient optimization.

What I do not understand is this: To know what the Support Vectors will be, doesn't the algorithm have to consider all the datapoints in the beginning? I.e. is this sparse representation not only possible after training?

Edit: Here is an example:

In other words, if all data points other than the support vectors were removed, the algorithm would find the same solution. This property, known as sparseness, has many consequences, both in the implementation and in the analysis of the algorithm

From this paper: Cristianini, N. and Scholkopf, B. (2002). Support Vector Machines and Kernel Methods: The New Generation of Learning Machines, page 39.

So, I understand how the (hinge) loss function looks like, how we come to this function at all, and how derivation can lead to a solution - but I guess I don't understand how this is algorithmically implemented such that only the support vectors are needed (from when on are only these needed, how exactly does this affect the SVM optimization?)

Notice added Draw attention by Pugl
Bounty Started worth 50 reputation by Pugl
Source Link
Pugl
Pugl
  • 1.5k
  • 3
  • 24
  • 45

The role of Support Vectors in optimization

I believe that I have somewhat an understanding of the objective and loss functions associated with Support Vector Machines (SVM), however, one point is still confusing me: The fact that the margins of the SVM can be characterized only by the Support Vectors is often named as a reason for their efficient optimization.

What I do not understand is this: To know what the Support Vectors will be, doesn't the algorithm have to consider all the datapoints in the beginning? I.e. is this sparse representation not only possible after training?