For a soft margin SVM in primal form, we have a cost function that is:

$$J(\mathbf{w}, b) = C {\displaystyle \sum\limits_{i=1}^{m} max\left(0, 1 - y^{(i)} (\mathbf{w}^t \cdot \mathbf{x}^{(i)} + b)\right)} \quad + \quad \dfrac{1}{2} \mathbf{w}^t \cdot \mathbf{w}$$

When using kernel trick, we have to apply $\phi$ to our input data $x^{(i)}$. So our new cost function will be:

$$J(\mathbf{w}, b) = C {\displaystyle \sum\limits_{i=1}^{m} max\left(0, 1 - y^{(i)} (\mathbf{w}^t \cdot \phi(\mathbf{x}^{(i)}) + b)\right)} \quad + \quad \dfrac{1}{2} \mathbf{w}^t \cdot \mathbf{w}$$

But following Andrew Ng's machine learning course, after selecting all training examples as landmarks to apply gaussian kernel $K$, he rewrites the cost function this way:

$\hskip1in$enter image description here

where $f^{(i)}=(1, K(x^{(i)}, l^{(1)}), K(x^{(i)}, l^{(2)}), ..., K(x^{(i)}, l^{(m)}))$ is a $m+1$ dimensional vector ($m$ is the number of training examples). So i have two questions:

  1. The two cost functions are quite similar, but latter uses $f^{(i)}$ and former $\phi(x^{(i)})$. How is $f^{(i)}$ related to $\phi(x^{(i)})$ ? In case of gaussian kernels, i know that the mapping function $\phi$, maps our input data space to an infinite dimensional space, so $\phi(x^{(i)})$ must be an infinite dimensional vector, but $f^{(i)}$ has only $m+1$ dimensions.
  2. When using kernels, as there is no dot product in the primal form that can be computed by the kernel function, is it faster to solve the dual form with some algorithm like SMO than minimizing the primal form with gradient descent?

1 Answer 1


First, some terminology clarification, which is important for further understanding:

In your second formula, applying $\phi(\mathbf{x}^{(i)})$ is not using the kernel trick! Kernel trick is computing $K(\mathbf{x}^{(i)}, \mathbf{x}^{(j)})$ without computing $\phi(\mathbf{x}^{(i)})$ or $\phi(\mathbf{x}^{(j)})$, and even without the need to know their form explicitly.

With that in mind, to answer your questions:

  1. Recall that, for SVMs, $\mathbf{w}$ is defined as a linear combination of the data points: $$ \mathbf{w} = \sum_{j=1}^m \alpha_j \phi(\mathbf{x}^{(j)}) $$ This is (the?) essence of Support Vector Machines. Since they attempt to minimise $\mathbf{w}^t \cdot \mathbf{w}$, many $\alpha_j$'s will be zero, meaning that the corresponding $\mathbf{x}^{(j)}$'s do not affect the boundary. Those which do, whose corresponding $\alpha_j$'s are non-zero, are the support vectors. With this definition of $\mathbf{w}$ and applying the kernel trick, we come to: $$ \mathbf{w}^t \cdot \phi(\mathbf{x}^{(i)}) = \sum_{j=1}^m \alpha_j \phi(\mathbf{x}^{(j)}) \phi(\mathbf{x}^{(j)}) = \sum_{j=1}^m \alpha_j K(\mathbf{x}^{(i)}, \mathbf{x}^{(j)}) $$ or, in vector notation: $$ \mathbf{w}^t \cdot \phi(\mathbf{x}^{(i)}) = \alpha^t \cdot \mathbf{f}^{(i)} $$ where we define: $$ \mathbf{f}^{(i)} = [ ~ K(\mathbf{x}^{(i)}, \mathbf{x}^{(1)}), K(\mathbf{x}^{(i)}, \mathbf{x}^{(2)}), ..., K(\mathbf{x}^{(i)}, \mathbf{x}^{(m)}) ~ ]^t $$ This is almost the Ng notation. Recall that we also need to optimise for $b$, and Ng, for a more compact notation, puts $b$ as the first component of $\theta$ and must therefore prepend a one to the vector $\mathbf{f}^{(i)}$. He is actually saying: $$ b + \mathbf{w}^t \cdot \phi(\mathbf{x}^{(i)}) = \theta^t \cdot \mathbf{f}^{(i)} $$ where $$ \mathbf{f}^{(i)} = [ ~ 1, K(\mathbf{x}^{(i)}, \mathbf{x}^{(1)}), K(\mathbf{x}^{(i)}, \mathbf{x}^{(2)}), ..., K(\mathbf{x}^{(i)}, \mathbf{x}^{(m)}) ~ ]^t $$ and $$ \theta = [ ~ b, \alpha^{(1)}, \alpha^{(2)}, ..., \alpha^{(m)}) ~ ]^t $$ The rest of his notation is just defining $cost_k$ as an affine function of the above dot product (to get the "$1 - $" term), and accommodating the fact that his class labels are not $(-1, 1)$ (which are often used in machine learning community), but $(0, 1)$ (how they are typically used in statistics, like in logistic regression). As for the vector dimensionality, that's again explained by the kernel trick. SVM's never need to compute $\phi(\mathbf{x}^{(i)})$, because these terms never appear alone. They only appear as parts of dot products, which is computed by the kernel function (see my second formula above). The dimensionality of $\mathbf{f}^{(i)}$ has absolutely nothing to do with the dimensionality of $\phi$. $\mathbf{f}^{(i)}$ is simply a vector of all dot products (or kernel function evaluations) between $\mathbf{x}^{(i)}$ and every $\mathbf{x}^{(j)}$ (I'm ignoring $b$ here, which is the ($m+1$)th dimension).

  2. Correctly if I'm wrong, but I believe there is some misunderstanding in your second question. As I've shown above, there is a dot product in the primal form, and you can substitute it for the kernel function. The purpose of SMO (and other decomposition algorithms) is to make computation feasible for large amounts of data. Standard gradient descent algorithms would require $O(m^2)$ memory for storing all possible kernel values. Decomposition algorithms, specifically designed for SVMs, work on smaller subsets of data.

  • $\begingroup$ Thanks for your clear answer. I thought that the kernel trick is not applicable to the primal form, so the dual form is solved instead. But as you showed, the kernel trick is also applicable to the primal form. So can you tell me what are the advantages of the dual form over the primal? What about this post? $\endgroup$ Commented May 4, 2020 at 7:35
  • 1
    $\begingroup$ Basically, it is a performance issue. The post you linked explains it quite well in my opinion. Another way of looking at it is to observe how you find the solution. In the primal form, you need to check whether the approximate solution you've reached in each step is on the right side of a linear boundary (a hyperplane in a high dimensional space). That's not impossible, but computationally more costly than just checking whether the Lagrange coefficients ($\alpha_i$) are non-negative. $\endgroup$
    – Igor F.
    Commented May 4, 2020 at 16:43
  • $\begingroup$ Thank you for your answer which is very helpful. Can I have a follow up question on the minimization? We are trying to minimize wt⋅w, which involve both α and ϕ. Following Ng's notation (adapted from your explanation), the minimization problem involves α only. My question is are they equivalent? Thanks $\endgroup$
    – JJ LI
    Commented May 19, 2021 at 6:03
  • $\begingroup$ It often not the case that "many αj's will be zero", especially if the hyperparameters are tuned to maximise generalisation performance. IMHO the sparsity of SVMs should be viewed as a useful by-product of the formulation, rather than a design goal. If you want sparsity, then it is probably best to use an algorithm designed to be sparse (e.g. L1 regularisation). The primal weights can be extracted from the dual parameters, provided the kernel induced feature space is finite - it can't be done at all for the RBF kernel, for example. $\endgroup$ Commented May 19, 2021 at 6:51
  • 1
    $\begingroup$ @adosar SVMs never need to know $\mathbf{w}$ explicitly. The "shortcut" is called "the kernel trick". $\endgroup$
    – Igor F.
    Commented Dec 16, 2022 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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