1
$\begingroup$

I am thinking about the following case where the data in region 1 is always positive and the data in region 2 is always negative, but the data in region 3 can be both positive and negative. Are there any existing results on finding exactly the $l_1$ and $l_2$ (or region 3)?

svm

As far as my understanding of SVM when the data is not perfectly linearly separable, we can maximize the soft margin to find the separating hyperplane. We can control the penalty of misclassification to achieve different separating hyperplanes. But is there a method for finding the exactly correct separating plane like $l_1$ and $l_2$? I am not very familiar with SVM, and I would really appreciate it if you can provide some comments or references.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I think you can create a "half-hard" SVM problem. It will be like the hard SVM for positive labels (without the error term) but for negative example it will be the like the soft SVM (with the error term).

This wil guarantee you get the line that labels correctly all positive examples, but still tries to label as many of the negative examples as it can (and also create the largest margin it can)

You can do this twice to get both lines $l_1$ and $l_2$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ However, i dont know how you would be able to easily compute the SVM solution in this case. Maybe you can define it as a soft-SVM problem, and add additional restrictions that make the error term to be exactly 0, and try to see how its dual behaves $\endgroup$
    – nir shahar
    Commented May 21, 2021 at 14:32
  • $\begingroup$ I am sorry, but I didn't quite get how can you run hard SVM when the data is not perfectly separable? For example, in order to get $l_1$, do we need to manually preprocess the data, like changing the positive examples under $l_1$ to be negative and then run hard SVM to get $l_1$? Could you explain more about running hard SVM for positive labels and running soft SVM for negative labels? $\endgroup$
    – Francis
    Commented May 26, 2021 at 16:40
  • $\begingroup$ Look at the hard SVM definition and the soft SVM definition. Now, create a linear program where for positive labels you add the hard SVM constraint, and for negative labels you put the soft SVM constraint. The solution to this LP is $l_2$ $\endgroup$
    – nir shahar
    Commented May 26, 2021 at 18:22

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.