The multi-surface method (MSM) is a form of decision making using the concept of piecewise-linear separability of datasets to categorize data.

Introduction

edit

Two datasets are linearly separable if their convex hulls do not intersect. The method may be formulated as a feedforward neural network with weights that are trained via linear programming. Comparisons between neural networks trained with the MSM versus backpropagation show MSM is better able to classify data.[1] The decision problem associated linear program for the MSM is NP-Complete.

Mathematical formulation

edit

Given two finite disjoint point sets  , find a discriminant,   such that  . If the intersection of convex hulls of the two sets is the empty set, then it is possible to use a single linear program to obtain a linear discriminant of the form,  . Usually, in real applications, the sets' convex hulls do intersect, and a (often non-convex) piecewise-linear discriminant can be used, through the use of several linear programs.[2]

See also

edit

References

edit
  1. ^ Neural Network Training via Linear Programing, Advances in Optimization and Parallel Computing, 1992, p. 56
  2. ^ "Pattern Recognition via Linear Programming: Theory and Application to Medical Diagnosis", O. L. Mangasarian, R Setiono, and W. H. Wolberg, 1990