67
$\begingroup$

Given the data points $x_1, \ldots, x_n \in \mathbb{R}^d$ and labels $y_1, \ldots, y_n \in \left \{-1, 1 \right\}$, the hard margin SVM primal problem is

$$ \text{minimize}_{w, w_0} \quad \frac{1}{2} w^T w $$ $$ \text{s.t.} \quad \forall i: y_i (w^T x_i + w_0) \ge 1$$

which is a quadratic program with $d+1$ variables to be optimized for and $i$ constraints. The dual

$$ \text{maximize}_{\alpha} \quad \sum_{i=1}^{n}{\alpha_i} - \frac{1}{2}\sum_{i=1}^{n}{\sum_{j=1}^{n}{y_i y_j \alpha_i \alpha_j x_i^T x_j}}$$ $$ \text{s.t.} \quad \forall i: \alpha_i \ge 0 \land \sum_{i=1}^{n}{y_i \alpha_i} = 0$$ is a quadratic program with $n + 1$ variables to be optimized for and $n$ inequality and $n$ equality constraints.

When implementing a hard margin SVM, why would I solve the dual problem instead of the primal problem? The primal problem looks more 'intuitive' to me, and I don't need to concern myself with the duality gap, the Kuhn-Tucker condition etc.

It would make sense to me to solve the dual problem if $d \gg n$, but I suspect there are better reasons. Is this the case?

$\endgroup$
4
  • 37
    $\begingroup$ Short answer is kernels. Long answer is keeerneeels (-; $\endgroup$
    – user88
    Dec 1 '11 at 0:26
  • 2
    $\begingroup$ The most important thing of dual problem is to introduce the kernel trick, aiming at mapping the original data into space with higher dimension. $\endgroup$ Jun 21 '18 at 2:24
  • $\begingroup$ It is perhaps worth pointing out that the kernel trick and $d \gg n$ in OP's question are related. For (many) kernels of interest, the primal problem would be infinite-dimensional ($d = \infty$). Also, solving the primal problem would require knowing "a feature map" of the RKHS which is often hard to figure out for a given kernel. $\endgroup$
    – passerby51
    Jan 3 at 15:03
  • $\begingroup$ PEGASOS. You can use PEGASOS +primal optimization + kernel without dual. $\endgroup$
    – Germania
    Oct 1 at 18:33
57
$\begingroup$

Based on the lecture notes referenced in @user765195's answer (thanks!), the most apparent reasons seem to be:

Solving the primal problem, we obtain the optimal $w$, but know nothing about the $\alpha_i$. In order to classify a query point $x$ we need to explicitly compute the scalar product $w^Tx$, which may be expensive if $d$ is large.

Solving the dual problem, we obtain the $\alpha_i$ (where $\alpha_i = 0$ for all but a few points - the support vectors). In order to classify a query point $x$, we calculate

$$ w^Tx + w_0 = \left(\sum_{i=1}^{n}{\alpha_i y_i x_i} \right)^T x + w_0 = \sum_{i=1}^{n}{\alpha_i y_i \langle x_i, x \rangle} + w_0 $$

This term is very efficiently calculated if there are only few support vectors. Further, since we now have a scalar product only involving data vectors, we may apply the kernel trick.

$\endgroup$
9
  • 7
    $\begingroup$ Wait, wait. Let's say you have two support vectors x1 and x2. You can't have fewer than two, right? Are you saying that computing <x1, x> and <x2, x> is faster than <w, x>? $\endgroup$
    – Leo
    Mar 27 '12 at 22:50
  • 1
    $\begingroup$ @Leo: Note that I use <x1, x> and wTx. The former is used as a symbol for a kernel evaluation K(x1, x), which projects x1 and x into a very high-dimensional space and computes implicitly the scalar product of the projected values. The latter is the normal scalar product, so w and x have to be projected explicitly, and then the scalar product is calculated explicitly. Depending on the choice of the kernel, a single explicit calculation may take much more computation than many kernel evaluations. $\endgroup$
    – blubb
    Mar 28 '12 at 7:15
  • 3
    $\begingroup$ As I understand the primal problem, $\alpha$'s are the Lagrange multipliers, so why can't we solve the primal problem to find $\alpha$'s? I mean we probably don't have to resort to the dual problem to find out $\alpha$'s, do we? $\endgroup$
    – avocado
    Apr 7 '14 at 3:48
  • 5
    $\begingroup$ "Further, since we now have a scalar product only involving data vectors, we may apply the kernel trick." - That's also true in the primal formulation. $\endgroup$
    – Firebug
    May 23 '17 at 15:57
  • 2
    $\begingroup$ If folks want more detail on the comment from @Firebug ... check out equations 10-12 of lib.kobe-u.ac.jp/repository/90001050.pdf (which is an unconstrained version of the primal). $\endgroup$
    – MrDrFenner
    Feb 19 '18 at 21:37
15
$\begingroup$

Read the second paragraph in page 13 and the discussion proceeding it in these notes:

Tengyu Ma and Andrew Ng. Part V: Kernel Methods. CS229 Lecture Notes. 2020 October 7.

$\endgroup$
2
  • 22
    $\begingroup$ That is a great reference and clearly answers the question. I think your reply will be better appreciated if you could summarize the answer here: that makes this thread stand by itself. $\endgroup$
    – whuber
    Nov 30 '11 at 23:02
  • $\begingroup$ I believe page 23 is also of relevance $\endgroup$
    – siegfried
    Apr 29 at 12:39
3
$\begingroup$

Here's one reason why the dual formulation is attractive from a numerical optimization point of view. You can find the details in the following paper:

Hsieh, C.-J., Chang, K.-W., Lin, C.-J., Keerthi, S. S., and Sundararajan, S., “A Dual coordinate descent method forlarge-scale linear SVM”, Proceedings of the 25th International Conference on Machine Learning, Helsinki, 2008.

The dual formulation involves a single affine equality constraint and n bound constraints.

1. The affine equality constraint can be "eliminated" from the dual formulation.

This can be done by simply looking at your data in $R^{d+1}$ via the embedding of $R^d$ in $R^{d+1}$ resuling from adding a single "$1$" coordinate to each data point, i.e. $R^d \to R^{d+1}: (a_1,..., a_d) \mapsto (a_1, ..., a_d, 1)$.

Doing this for all points in the training set recasts the linear separability problem in $R^{d+1}$ and eliminates the constant term $w_0$ from your classifier, which in turn eliminates the affine equality constraint from the dual.

2. By point 1, the dual can be easily cast as a convex quadratic optimization problem whose constraints are only bound constraints.

3. The dual problem can now be solved efficiently, i.e. via a dual coordinate descent algorithm that yields an epsilon-optimal solution in $O(\log(\frac{1}{\varepsilon}))$.

This is done by noting that fixing all alphas except one yields a closed-form solution. You can then cycle through all alphas one by one (e.g. choosing one at random, fixing all other alphas, calculating the closed form solution). One can show that you'll thus obtain a near-optimal solution "rather quickly" (see Theorem 1 in the aforementioned paper).

There are many other reasons why the dual problem is attractive from an optimization point of view, some of which exploit the fact that it has only one affine equality constraint (the remaing constraints are all bound constraints) while others exploit the observation that at the solution of the dual problem "often most alphas" are zero (non-zero alphas corresponding to support vectors).

You can get a good overview of numerical optimization considerations for SVMs from Stephen Wright's presentation at the Computational Learning Workshop (2009).

P.S.: I'm new here. Apologies for not being good at using mathematical notation on this website.

$\endgroup$
1
-1
$\begingroup$

In my opinion, the prediction time argument (that predictions from the dual solution are faster than from the primal solution) is nonsense. A comparison makes only sense if you use a linear kernel in the first place, because otherwise you cannot make predictions with the primal (or at least it is not clear to me how that would work). But if you have a linear kernel, then computing the kernel is the dot product and is strictly slower for the dual than for the primal, because you need to compute it for at least 2 (and typically much more points). It would then be much faster to rely on the simply dot product $\mathbf w^Tx$. In fact, if you have a linear kernel, you would just compute $\mathbf w$ explicitly and use it for predictions, just as you would do with the primal solution.

The two true arguments are:

  1. The kernel trick can be applied (already mentioned by others)

  2. The optimization process is much more straight forward for the dual problem and can be easily done with gradient descent

I will shed some light on the second point, since little has been said about that.

The main problem with the primal problem is that it cannot be easily optimized using standard gradient descent in spite of its convexity. You can easily detect this if you try to implement a solution to both problems (primal and dual) with a gradient-descent approach. Btw. the dual you formulated also has an issued, but this can be resolved as said below.

There are in fact three annoying things about optimizing the primal, at least when trying to solve it using gradient descent:

  1. there is no trivial valid initial solution. In fact, already an initial solution must be a perfect separator. You can find one with the perceptron algorithm. In the dual, you can initialize all the $\alpha_i := 0$, which is also common practice. It is noteworthy that this corresponds to setting $w = 0$, which is not a feasible solution to the primal. However, in the dual this is not a problem, because only the optimal solution needs to be feasible in the primal.

  2. the standard gradient update rule $\mathbf w' \leftarrow \mathbf w + \eta \nabla$ does not make a lot of sense and will not help you to converge to the optimum even though the problem is convex. The issue is that the gradient $\nabla$ is $\mathbf w$ itself, so you would in fact only shorten or stretch $\mathbf w$ but not change its orientation. But the latter is typically necessary unless your initial solution already had the correct slope.

  3. the threshold $w_0$ does not occur in the objective function and its gradient is 0, but it should be updated in accordance with changes in $\mathbf w$.

Putting all this together, my personal reason to not optimize the primal is that, even though it is convex, there is no straight forward way of doing this with gradient descent. Note that this issue is not prevalent in the soft margin classifier, because here you can initialize $\mathbf w = 0$ and also have more sensible gradient steps. The problem is simply that it is annoying to deal with the linear constraints.

The dual problem as posed by you also is annoying when being solved with GD, because you still have the balance constraint $\sum y_i\alpha_i = 0$. You can get rid of that when adding the $\mathbf 1$ column to the data and treating it as part of $\mathbf w$. If you do that, you do not have the condition on optimality anymore for the Lagrangian, and optimization can be easily and efficiently done with simple batch gradient descent.

$\endgroup$
-8
$\begingroup$

In my opinion in the lecture notes of Andrew ng, its been clearly mentioned that the primal problem of 1/||w||, is a non convex problem. The dual is a convex problem and its always easy to find the optimum of a convex function.

$\endgroup$
1
  • 2
    $\begingroup$ The SVM primal as stated above is convex. $\endgroup$
    – Danica
    Feb 7 '17 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.