0
$\begingroup$

I'm reading up on the theory behind support vector machines and would like a good reference with some general results about linear separability.

Specifically, questions like below:

Given two finite $A$, $B \subset \mathbb{R}^n$, of cardinality $k$, must there always exist a linear separation, even when $k > n$?

Seems like the answer is no, and a specific example when $k = 4$, $n = 2$ seems to generalize well. Consider the corners of a square, where each corner is colored either red or blue. If we color one diagonal red, and the other diagonal blue, then linear separation in $\mathbb{R}^2$ is impossible. In fact, this holds true for the corners of any convex quadrilateral.

Although in higher dimensions, one can make the points non-coplanar and circumvent this, the counterexample always works if the points are coplanar, and thus the question is false as stated.

I'm obviously only poking around in the dark here, but any direction would be much appreciated.

Improve this question
$\endgroup$
2
  • $\begingroup$ In the space you don't need co-planarity. Any two sets of points that have intersecting convex hulls cannot be separated by a hyperplane, and this may easily happen for $n+2$ points in generic position in $\mathbb R^n$ already. It is not quite clear to me what you are asking in general. IMHO, a nice elementary book in convex/combinatiorial geometry and a few general ideas from linear algebra should suffice for the purpose of reading the stuff you are trying to read (if the authors explain their theory in "mathematical common" and don't try to introduce a bunch of new terms on every page). $\endgroup$
    – fedja
    Commented Dec 6, 2017 at 0:33
  • $\begingroup$ That makes sense. I guess what I'm asking for is exactly such a book. $\endgroup$
    – Fred Byrd
    Commented Dec 6, 2017 at 0:57

1 Answer 1

Reset to default
1
$\begingroup$

Linear separability is only guaranteed if $k\leq n+1$. Vapnik and chervonenkis easily proved that an affine hyperplane in a space of dimension $n$ can at most shatter (classify in all possible arbitrary ways) a set of $n+1$ points in the space. This number has been called Vapnik-Chervonenkis dimension.

There is an answer in this thread: https://stats.stackexchange.com/questions/187912/how-to-make-the-conclustion-that-vc-dimension-for-hyperplane-in-mathbbr3/188224#188224

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .