Multi-surface method
The multi-surface method (MSM) is a form of decision making using the concept of piecewise-linear separability of datasets to categorize data.
Introduction
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
Given two finite disjoint point sets [math]\displaystyle{ \mathcal{A,B} \in \mathbb{R}^n }[/math], find a discriminant, [math]\displaystyle{ f:\mathbb{R}^n \to \mathbb{R} }[/math] such that [math]\displaystyle{ f(\mathcal{A}) \gt 0, f(\mathcal{B}) \le 0 }[/math]. 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, [math]\displaystyle{ f(x)=cx+\gamma }[/math]. 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
- Backpropagation
- Linear Programming
References
- ↑ Neural Network Training via Linear Programing, Advances in Optimization and Parallel Computing, 1992, p. 56
- ↑ "Pattern Recognition via Linear Programming: Theory and Application to Medical Diagnosis", O. L. Mangasarian, R Setiono, and W. H. Wolberg, 1990
 |  |
