linear separability

[Alexis Wieland]

> From: christoph bruno herwig <cherwig at eng.clemson.edu>

> Given a binary (-1/1) valued training set consisting of n-dimensional
> input vectors (homogeneous coordinates: n-1 inputs and a 1 for the bias
> term as the n-th dimension) and 1-dimensional target vectors. For this 2-class
> classification problem I wish to prove (non-) linear separability
> solely on the basis of the given training set (hence determine if
> the underlying problem may be solved with a 2-layer feedforward network).

> My approach so far: 
> Denote input vectors of the first (second) class with H1 (H2). We need 
> to find a hyperplane in n-dimesional space separating vectors of H1
> and H2. The hyperplane goes through the origin of the n-dimensional
> hypercube.  ...

Your analysis relies on the dividing hyperplane passing through the
origin, a condition that you dutifully state.  But this need not be
the case for linearly separable problems.  Consider the simple 2D case
with the four points (1,1), (1,-1), (-1,1), (-1,-1).  Place one point
in H1 and the rest in H2.  The problem is clearly linearly separable,
but there is no line that passes through the origin that will serve.
The min distance from the origin to the dividing hyperplane for a class
with one element increases with dimension of the input.

- alexis.        (Mr. Spiral :-)