Jump to content

Multi-surface method

From Wikipedia, the free encyclopedia

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