Essentially, linearly separable points are just those corners that can be cut off with just one slice as marked out by a hyperplane.

E.g. for a cube, the following 4 points (red) are not linearly separable - no single cut by a plane (tilted at whatever angle) across the cube can slice off exactly these 4 points:

enter image description here

So this begs the question: given $n$ points on an $m$-dimensional hypercube, how can I tell if these $n$ points are linearly separable?

  • $\begingroup$ @AsalBeagDubh - thanks, sounds like that might be what I want, but what is $p_i - p_0$? $\endgroup$ – mchen Jun 5 '13 at 15:40
  • $\begingroup$ Sorry, I deleted my comment because I think I misread the question. $p_i-p_0$ just means the vector pointing from the point $p_0$ to the point $p_i$. $\endgroup$ – user64687 Jun 5 '13 at 17:03
  • $\begingroup$ related math.stackexchange.com/questions/18056/… $\endgroup$ – leonbloy Jun 9 '13 at 18:34

This is a crucial problem in machine learning, much studied since the 60'sand there is no easy characterisation or criterion - nor even efficient algorithms. See eg this and this, , and references, or google for "Threshold Logic".


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.