3
$\begingroup$

Pattern classification by Duda, Hart, Stork (Section- 9.6.8) states that a 2-class training set of $d+1$ or less samples in a d−dimensional space is always linearly separable i.e. if the samples span the $d$ dimensions and not in any sub-space of $d$.

In short, for $n \le d + 1$, where $n$ is the number of samples, there exists a separating hyperplane.

How can it be proved?

$\endgroup$

1 Answer 1

4
$\begingroup$

Upon increasing the dimension by 1, it's easy to construct a separating hyperplane explicitly.

Index the vectors $v_i \in \mathbb{R}^d$ so that the first $k$ of them ($0 \le k \le d+1$) belong to one class and the remaining $d+1-k$ belong to the other. Embed them all (linearly) into $\mathbb{R}^{d+1}$ by sending $v_i$ to $u_i$ where the first $d$ coordinates of $u_i$ are those of $v_i$ and the $d+1^{st}$ coordinate is $1$. Let's call this map $\sigma$. The assumptions imply the $u_i$ are a basis for $\mathbb{R}^{d+1}$. Let $\omega_i, i=1,2,\ldots,d+1$ be the dual basis: that is, $\omega_j(u_i) = \delta_{ji}$. Define the linear form $\phi: \mathbb{R}^{d+1} \to \mathbb{R}$ via

$$\phi = \sum_{i=1}^k \omega_i - \sum_{i=k+1}^{d+1} \omega_i.$$

That is, $\phi(u_i) = 1$ when $i$ is in the first class and $\phi(u_i) = -1$ when $i$ is in the second class. A separating hyperplane is

$$H: \{x \in \mathbb{R}^{d} \ | \ \phi(\sigma(x)) = 0\}.$$

Example

Let $v_1 = (0,1)'$, $v_2 = (1,0)'$, and $v_3 = (1,1)'$ in $\mathbb{R}^2$ and suppose $k=1$ (i.e., $v_1$ is in one class--"blue"--and $v_2$ and $v_3$ are in the other class, "red").

Then

$$u_1 = (0,1,1)', \quad u_2 = (1,0,1)', \quad \text{and } u_3 = (1,1,1)'.$$

The forms dual to the $u_i$ are

$$\omega_1 = (-1,0,1), \quad \omega_2 = (0,-1,1), \quad \omega_3 = (1,1,-1),$$

as is readily checked by matrix multiplication (e.g., $\omega_2(u_1)$ = $(0,-1,1)(0,1,1)'$ = $0 + -1 + 1 = 0$, as required). Whence

$$\phi = \omega_1 - \omega_2 - \omega_3 = (-2,0,1).$$

For $x = (x_1, x_2)' \in \mathbb{R}^2$, $\phi(\sigma(x)) = (-2,0,1)(x_1,x_2,1)' = -2x_1 + 1$. A separating hyperplane is

$$H: -2x_1 + 1 = 0.$$

Points and a separating hyperplane

As a check, apply this formula for $H$ to the $v_i$, obtaining $1$, $-1$, and $-1$, as intended.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.