1
$\begingroup$

With hard margin support vector machines (SVMs), it suffices to find the critical points of the Lagrangian $L = \frac{1}{2}||\theta||^2 - \sum_{n=1}^{N} \alpha_n (y^{(n)} (\vec{\theta}^T\vec{x}^{(n)} + \theta_0) - 1)$ over all $ \alpha_n$, where $\vec{\theta}^T\vec{x}^{(n)} + \theta_0 = 0$ is the seperating hyperplane, $y^{(n)}$ is the label (1 or -1), and there are $N$ data points.

I don't have much of a background in optimization, however, so I wanted to ask for methods that are commonly used to solve this optimization problem. Since $\alpha_n$ are unknown, for example, I wasn't sure how we could use gradient descent here, since we cannot compute the derivative numerically given unknown $\alpha_n$.

$\endgroup$

1 Answer 1

1
$\begingroup$

The Lagrange multipliers $\alpha_i$ are also unknowns. You may not ultimately need the values, but you do need to solve for them.

Think of $L$ as a function of the unknown variables:

$$L(\theta_0, \ldots, \theta_N, \alpha_1, \ldots, \alpha_N)$$

The stationary points of $L$ are the points where $\nabla L = \vec{0}$. That means all of the partial derivatives are zero:

$$\begin{eqnarray*}\frac{\partial L}{\partial \theta_0} & = & 0 \\ & \vdots & \\ \frac{\partial L}{\partial \theta_N} & = & 0 \\ \frac{\partial L}{\partial \alpha_1} & = & 0 \\ & \vdots & \\ \frac{\partial L}{\partial \alpha_N} & = & 0 \end{eqnarray*}$$

So while you have $2N+1$ unknowns, you also have $2N+1$ equations.

To understand why this works, take look at what the extra equations mean. This:

$$0 = \frac{\partial L}{\partial \alpha_i} = y^{(i)} \left( \vec{\theta}^T \vec{x}^{(i)} + \theta_0 \right) - 1$$

Is precisely this:

$$y^{(i)} \left( \vec{\theta}^T \vec{x}^{(i)} + \theta_0 \right) = 1$$

...and that equation should look familiar to you. The "extra" equations that you need to solve for are precisely the equality constraints on your optimisation problem.

$\endgroup$

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.