49
$\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$
  • 26
    $\begingroup$ Short answer is kernels. Long answer is keeerneeels (-; $\endgroup$ – user88 Dec 1 '11 at 0:26
  • $\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$ – BigeyeDestroyer Jun 21 '18 at 2:24
39
$\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$
  • 5
    $\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
  • 1
    $\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
  • 2
    $\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
13
$\begingroup$

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

http://cs229.stanford.edu/notes/cs229-notes3.pdf

$\endgroup$
  • 17
    $\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
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 ----> R^(d+1): (a1,..., ad) |---> (a1, ..., ad, 1).

Doing this for all points in the training set recasts the linear separability problem in R^(d+1) and eliminates the constant term w0 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(1/epsilon)).

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$
-5
$\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
    $\begingroup$ The SVM primal as stated above is convex. $\endgroup$ – Dougal 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.