2
$\begingroup$

Screenshot from this video:

enter image description here

This describes the decision boundary of support vector machine as a optimization problem with two constraints. But it seems to assume that the data points are linearly separable, what if they are not?

$\endgroup$

1 Answer 1

3
$\begingroup$

For problems which are not linearly separable soft margin SVM is used instead: $$ \begin{align} \min_{\mathbf{w},b,\xi} &\frac{1}{2}\|\mathbf{w}\|^2 + C\sum_{i=1}^{N} \xi_i, \\ \text{s.t. } &y_i\big(\langle \mathbf{w}, \phi(\mathbf{x}_i) \rangle + b)\big) \geq 1 - \xi_i \quad \forall i, \\ &\xi_i \geq 0 \quad \forall i, \end{align}$$ where $\mathbf{w}$ is the separating hyperplane in feature space, $\mathbf{x}_i$ are the training instances, $y_i \in \{-1, +1\}$ the labels and $\phi(\cdot)$ the embedding function. The slack variables $\xi$ allow us to violate constraints (e.g. training instances that lie inside the margin or on the wrong side of the separating hyperplane) but violations are minimized by adding the slack variables to the cost function.

The solution to this problem is a separating hyperplane that does permit some misclassifications. The hyperparameter $C$ is used to balance between training misclassifications and the complexity of the separating hyperplane.

$\endgroup$

Your Answer

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

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