21
$\begingroup$

Why do people use Quadratic Programming techniques (such as SMO) when dealing with kernelized SVMs? What is wrong with Gradient Descent? Is it impossible to use with kernels or is it just too slow (and why?).

Here is a little more context: trying to understand SVMs a bit better, I used Gradient Descent to train a linear SVM classifier using the following cost function:

$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}$

I am using the following notations:

  • $\mathbf{w}$ is the model's feature weights and $b$ is its bias parameter.
  • $\mathbf{x}^{(i)}$ is the $i^\text{th}$ training instance's feature vector.
  • $y^{(i)}$ is the target class (-1 or 1) for the $i^\text{th}$ instance.
  • $m$ is the number of training instances.
  • $C$ is the regularization hyperparameter.

I derived a (sub)gradient vector (with regards to $\mathbf{w}$ and $b$) from this equation, and Gradient Descent worked just fine.

Now I would like to tackle non-linear problems. Can I just replace all dot products $\mathbf{u}^t \cdot \mathbf{v}$ with $K(\mathbf{u}, \mathbf{v})$ in the cost function, where $K$ is the kernel function (for example the Gaussian RBF, $K(\mathbf{u}, \mathbf{v}) = e^{-\gamma \|\mathbf{u} - \mathbf{v}\|^2}$), then use calculus to derive a (sub)gradient vector and go ahead with Gradient Descent?

If it is too slow, why is that? Is the cost function not convex? Or is it because the gradient changes too fast (it is not Lipschitz continuous) so the algorithm keeps jumping across valleys during the descent, so it converges very slowly? But even then, how can it be worse than Quadratic Programming's time complexity, which is $O({n_\text{samples}}^2 \times n_\text{features})$? If it's a matter of local minima, can't Stochastic GD with simulated annealing overcome them?

$\endgroup$
6
$\begingroup$

Set $\mathbf w = \phi(\mathbf x)\cdot \mathbf u$ so that $\mathbf w^t \phi(\mathbf x)=\mathbf u^t \cdot \mathbf K$ and $\mathbf w^t\mathbf w = \mathbf u^t\mathbf K\mathbf u$, with $\mathbf K = \phi(\mathbf x)^t\phi(\mathbf x)$, where $\phi(x)$ is a mapping of the original input matrix, $\mathbf x$. This allows one to solve the SVM through the primal formulation. Using your notation for the loss:

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

$ \mathbf{K}$ is a $m \times m$ matrix, and $\mathbf{u}$ is a $m \times 1$ matrix. Neither is infinite.

Indeed, the dual is usually faster to solve, but the primal has it's advantages as well, such as approximate solutions (which are not guaranteed in the dual formulation).


Now, why is the dual so much more prominent isn't obvious at all: [1]

The historical reasons for which most of the research in the last decade has been about dual optimization are unclear. We believe that it is because SVMs were first introduced in their hard margin formulation [Boser et al., 1992], for which a dual optimization (because of the constraints) seems more natural. In general, however, soft margin SVMs should be preferred, even if the training data are separable: the decision boundary is more robust because more training points are taken into account [Chapelle et al., 2000]


Chapelle (2007) argues the time complexity of both primal and dual optimization is $\mathcal{O}\left(nn_{sv} + n_{sv}^3\right)$, worst case being $\mathcal{O}\left(n^3\right)$, but they analyzed quadratic and approximate hinge losses, so not a proper hinge loss, as it's not differentiable to be used with Newton's method.


[1] Chapelle, O. (2007). Training a support vector machine in the primal. Neural computation, 19(5), 1155-1178.

$\endgroup$
  • 1
    $\begingroup$ +1 Could you maybe expand on the time complexity also $\endgroup$ – seanv507 Aug 19 '16 at 10:32
  • $\begingroup$ @seanv507 thanks, indeed I should have addressed that, I'll soon update this answer. $\endgroup$ – Firebug Aug 19 '16 at 14:23
4
$\begingroup$

If we apply a transformation $\phi$ to all input weight vectors ($\mathbf{x}^{(i)}$), we get the following cost function:

$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}$

The kernel trick replaces $\phi(\mathbf{u})^t \cdot \phi(\mathbf{v})$ by $K(\mathbf{u}, \mathbf{v})$. Since the weight vector $\mathbf{w}$ is not transformed, the kernel trick cannot be applied to the cost function above.

The cost function above corresponds to the primal form of the SVM objective:

$\underset{\mathbf{w}, b, \mathbf{\zeta}}\min{C \sum\limits_{i=1}^m{\zeta^{(i)}} + \dfrac{1}{2}\mathbf{w}^t \cdot \mathbf{w}}$

subject to $y^{(i)}(\mathbf{w}^t \cdot \phi(\mathbf{x}^{(i)}) + b) \ge 1 - \zeta^{(i)})$ and $\zeta^{(i)} \ge 0$ for $i=1, \cdots, m$

The dual form is:

$\underset{\mathbf{\alpha}}\min{\dfrac{1}{2}\mathbf{\alpha}^t \cdot \mathbf{Q} \cdot \mathbf{\alpha} - \mathbf{1}^t \cdot \mathbf{\alpha}}$

subject to $\mathbf{y}^t \cdot \mathbf{\alpha} = 0$ and $0 \le \alpha_i \le C$ for $i = 1, 2, \cdots, m$

where $\mathbf{1}$ is a vector full of 1s and $\mathbf{Q}$ is an $m \times m$ matrix with elements $Q_{ij} = y^{(i)} y^{(j)} \phi(\mathbf{x}^{(i)})^t \cdot \phi(\mathbf{x}^{(j)})$.

Now we can use the kernel trick by computing $Q_{ij}$ like so:

$Q_{ij} = y^{(i)} y^{(j)} K(\mathbf{x}^{(i)}, \mathbf{x}^{(j)})$

So the kernel trick can only be used on the dual form of the SVM problem (plus some other algorithms such as logistic regression).

Now you can use off-the-shelf Quadratic Programming libraries to solve this problem, or use Lagrangian multipliers to get an unconstrained function (the dual cost function), then search for a minimum using Gradient Descent or any other optimization technique. One of the most efficient approach seems to be the SMO algorithm implemented by the libsvm library (for kernelized SVM).

$\endgroup$
  • 1
    $\begingroup$ I'm not sure why you marked your answer Community Wiki. This seems like a perfectly valid answer to your question. $\endgroup$ – Sycorax Jun 1 '16 at 16:37
  • $\begingroup$ Thanks @GeneralAbrial. I marked my answer as Community Wiki to avoid any suspicion that I knew the answer before asking the question. $\endgroup$ – MiniQuark Jun 2 '16 at 6:57
  • 1
    $\begingroup$ You should always do what you think is right, but it's perfectly kosher to ask and answer your own question. $\endgroup$ – Sycorax Jun 2 '16 at 12:28
  • $\begingroup$ Wait, couldn't you transform the weight vector to $\mathbf w = \phi(x)\cdot \mathbf u$ so that $\mathbf w^t \phi(x)=\mathbf u \cdot \mathbf K$ and $\mathbf w^t\mathbf w = \mathbf u^t\mathbf K\mathbf u$, with $\mathbf K = \phi^t\phi$, and then optimize the sample weights $\mathbf u$? $\endgroup$ – Firebug Aug 18 '16 at 20:49
2
$\begingroup$

I might be wrong, but I don't see how we can replace the dot products with kernels without turning it into the dual problem.

The kernels map the input implicitly to some feature space where $x$ becomes $\phi(x)$, the loss function then becomes
$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}$
If Gaussian kernel is applied, $\phi(\mathbf{x}^{(i)})$ will have ifinite dimensions, so will $\mathbf{w}$.

It seems difficult to optimize a vector of infinite dimensions using gradient descent directly.

Update
Firebug's answer gives a way of replacing the dot products with kernels in the primal formulation.

$\endgroup$

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.