3
$\begingroup$

Instead of finding a solution to a system of linear inequalities (Ax + b >= 0), I want to find any system of linear inequalities that satisfy a set of feasible points and does not satisfy a set of infeasible points. As the image shows, I am given points (either a bunch together or one by one) labelled with in/out, yes/no, or similar binary attribute to know if it should be within the system or not, and I want to find lines that separate these.

enter image description here

There should be some inductive method to fit any number of linear inequalities to satisfy these points. It's important that the output is a system of linear inequalities so it can be used as input into linear programming solvers to find new solutions. I've looked into SVM's but the model seams just to be a hyperplane. Maybe it is for use. A one-layer neural network should do the trick but then the number of lines must be set from start.

There are a few things to add to this problem.

  1. We want to keep as few lines as possible, or, we want to assume as little as possible of the "true" data set we do not yet fully know of (as any machine learning algorithm does).
  2. For the same reason as 1, we'd like to keep the lines as much "in between" the true and false points (just as SVM's)
$\endgroup$
3
  • $\begingroup$ Are you familiar with kernelized SVMs? $\endgroup$
    – nir shahar
    Sep 9 '21 at 18:34
  • $\begingroup$ Yes but to make it work, one need to set some parameter indicating that the "green" dots are not allowed to be misclassified while the red ones are. Is that possible? $\endgroup$ Sep 13 '21 at 11:33
  • $\begingroup$ Totally. If you know about hard-SVM and soft-SVM, then you can "combine" the two to make the greens always correct while allowing misclassifications in the red ones. Take a look at this question here. Anyways, one could come up with a formula for hard-SVM using a kernelized SVM, so its definitely possible. $\endgroup$
    – nir shahar
    Sep 13 '21 at 11:54
4
$\begingroup$

I suspect that you can just compute the convex hull of the set of feasible points and, for each edge of the hull, write down the equation of the semi-plane that includes all feasible points and such that the line on its boundary is an extension of the edge segment.

In your example:

hull example

$\endgroup$
6
  • 1
    $\begingroup$ If there exists a set of linear inequalities separating one set from the other, then the extension of the convex hull of one of the two sets is one such set of linear inequalities: if not, then (the boundaries of) the convex hulls of the sets intersect, so the sets are not linearly separable. Hence, this approach finds a solution if one exists. Note also that while this approach gets some solution, there may be other solutions with far fewer inequalities (the example in the figure can be done with 2 lines, for example) $\endgroup$
    – Discrete lizard
    Sep 9 '21 at 10:01
  • $\begingroup$ That one is smart! I could definitely use it. There are a few key points more to it, I'll update the question to add those in $\endgroup$ Sep 9 '21 at 12:51
  • $\begingroup$ Apparently the problem has already been considered here for the 2-dimentional case and an almost linear-time algorithm is known. $\endgroup$
    – Steven
    Sep 9 '21 at 18:43
  • $\begingroup$ The link is broken.. what's the paper called? $\endgroup$ Sep 13 '21 at 6:44
  • 1
    $\begingroup$ Herbert Edelsbrunner, Franco P. Preparata. Minimum Polygonal Separation in Information and Computation, Volume 77, Number 3, 1988. $\endgroup$
    – Steven
    Sep 13 '21 at 7:46

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.