6
$\begingroup$

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?
$\endgroup$
3
+50
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Mehran Torki May 4 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. May 4 at 16:43

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.