Kernels in SVM primal form

Question

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$

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?

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.