Browse Prior Art Database

Set Separation Algorithm Effective in Nonseparable Case

IP.com Disclosure Number: IPCOM000085944D
Original Publication Date: 1976-Jun-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Crowder, HP: AUTHOR [+3]

Abstract

Ordinary use of `training algorithms' or of linear programming for determining the linear separability of two point sets yield no useful information when the sets are not separable. An alternative linear programming formulation yields the information needed to delete points from the sets so that separability obtains.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Set Separation Algorithm Effective in Nonseparable Case

Ordinary use of `training algorithms' or of linear programming for determining the linear separability of two point sets yield no useful information when the sets are not separable. An alternative linear programming formulation yields the information needed to delete points from the sets so that separability obtains.

In the following description of the proposed method let two points sets P , Q in Euclidean n-space be given, represented as the mp columns P[j] and the m(0)columns Q[k] of the two matrices P,Q. Letting <.,.> denote inner product, the standard and efficient way to determine a linear separator of P from Q, when that is possible, is to find an n-vector u such that absolute value u[i] < or - 1 for all i and that: (1) Min(k) <u, Q[k]> - Max(j) <u, P[j]>. is maximized. This may be accomplished by known linear programming methods [1]. However, if the separation is not possible, then the quantity 1(1) is maximized for u = 0, which is of no use for further work.

The present method consists in the use of the following scheme to investigate point sets which are thought to be nearly, but not perfectly, separable, and for determining how they may be modified so as to become separable.

1. Determine the centroid PC of the set P and the centroid QC of the set Q. Set the vector d = PC-PQ.

2. Solve the linear programming problem of minimizing the scalar z under the restrictions:. (i) Pv - Qw + zd = 0 (ii) <e,v> = 1 (iii) <e,w> = 1 (iv) v, w > or - 0, where v and w are n-vectors and e = (1,1,..1) is of appropriate length.

Let u be the n-vector of optimal dual variables associated with the equations
(i), and r,s the two for (ii), (iii). Note that r+s will equal the minimum v...