4
$\begingroup$

I have this conjecture whose verification I haven't been able to find online anywhere. If you have N - 1 distinct points that each have one of two classes, can you find a linear decision boundary in an N dimensional space that perfectly separates the classes?

EDITS Changed N to N-1. If you are in R^3 with the points (1, 0, 0), (2, 0, 0) (3, 0, 0) and you have the colors Red, Blue, Red respectively, you won't be able to draw a plane that separates them.

$\endgroup$
0

2 Answers 2

6
$\begingroup$

Short answer

In general this is not true. Consider $N-1$ points in $\mathbb{R}^N$ and a line $d$. Place the $N-1$ points any way you want in $d$. Now, the intersection of any affine hyperplane of $\mathbb{R}^N$ with $d$ will either be empty, a point, or the whole line. Any way, if $N-1 \ge 3$, not all classifications will be possible.

Longer answer

This being said, let's get to the interesting part. It is also always possible to place $N-1$ points in $\mathbb{R}^N$ such that they can be classified in any way you want by an affine hyperplane. In fact, you can place up to $N+1$ points in $\mathbb{R}^N$ and still have that property.

To prove this, we'll explicity place $N+1$ points in $\mathbb{R}^N$ in a particular way and count the number of ways we can classify those points. If we get $2^{N+1}$ ways of classifying them, it will mean that we can make any classification we want. (Make sure you see why.)

I say that the points $$ x_1 = (1^1, \dots, 1^N), x_2 = (2^1, \dots, 2^N), \dots, x_{N+1} = ((N+1)^1, \dots, (N+1)^N) $$ will do the job.


Recall that our classification function is $sign(h(x_i))$, where $h(x_i)$ is the dot product between a weight vector $w=(w_0, w_1, \dots, w_N)$ and our vector $x_i$ augmented with a new coordinate fixed to $1$. That is, for $< , >$ the dot product, $$ h(x_i) = <(w_0, w_1, \dots, w_N), (1, x_{i_1}, \dots, x_{i_N}) > $$ If we let $P$ be a polynomial of $\mathbb{R}[X]$ and say $P = w_0 + w_1 X + \dots + w_N X^N$, then we find $$ h(x_i) = P(i) $$

Now, fix $h(x_1) = P(1) >0$ (you could also say $P(1) < 0$ ). Choose any $d \le N$ and $u_1, \dots u_d \in \{2, 3, \dots, N+1\}$ such that $u_1 < u_2 < \dots < u_d$. We can choose $P$ (that is, choose the weights $w_i$ using polynomial interpolation) such that \begin{array}{l} P(1) > 0, \dots P(u_1 -1 ) >0\\ P(u_1) < 0, \dots P(u_2 -1) < 0\\ P(u_2) > 0, \dots P(u_3 -1 ) >0\\ \vdots\\ (-1)^d P(u_d) >0 , \dots, (-1)^d P(u_N) >0 \end{array}

We thus have an alternance in our classification over the intervals $[1, u_1), [u_1, u_2), \dots, [u_d, N]$.


It's now time to count. For two choices of $d$, the classifications are disjoint. We had two choices for the sign of $P(1)$, and ${N \choose d}$ possibilities for the $u_1, \dots u_d$. Therefore, the we can classify our $N+1$ points in (at least) $$ 2\cdot \sum\limits_{i=0}^{N} {N\choose i} = 2^{N+1} $$ ways. We won!

Generalisation

I went through that long argument in order to get this number : $2\cdot \sum\limits_{i=0}^{N} {N\choose i}$. It turns out that $N$ points in $\mathbb{R}^d$ can be chosen so they can be classified in $$ m(N) := 2\cdot \sum\limits_{i=0}^{d} {N-1\choose i} $$ ways. Furthermore, no $N$ points will have more than $m(N)$ classifications.

You can use the proof we made in order to build $N$ points that can be classified in $m(N)$ ways. I found it is harder to prove that $m(N)$ is also a maximum (I'd be interested in a simple proof, if someone has one.)


Note: I think I got carried away.

$\endgroup$
2
$\begingroup$

VC-dimension and shattering are keywords for this kind of question. The typical expression involved is "A 2-D hyperplane shatters 3 points". Indicating that if there are three points that can have two classes, then a 2-D hyperplane can always separate the classes. So N distinct points can be separated by a N-1 dimensional hyperplane in a N-1 dimensional space.

For more information see slides 8 and 9: https://www.google.si/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CCAQFjAA&url=https%3A%2F%2Fwww.cs.toronto.edu%2F~hinton%2Fcsc2515%2Fnotes%2Flec10svm.ppt&ei=X9hNVYmQNMONsAGj54GoCQ&usg=AFQjCNFuwD_e_uNS4e1eLmeY9K4mKTdOWw&sig2=1bwN22vlPsMvovR8Y4e1_w&bvm=bv.92885102,d.bGg

I am not sure how this works out for more than 2 classes.

$\endgroup$

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.