# Why bother with the dual problem when fitting SVM?

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?

-
Short answer is kernels. Long answer is keeerneeels (-; – mbq Dec 1 '11 at 0:26

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.

-
 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 and is faster than ? – Leo Mar 27 '12 at 22:50 @Leo: Note that I use  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. – blubb Mar 28 '12 at 7:15

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

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

-
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. – whuber Nov 30 '11 at 23:02