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.

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.

Given two finite disjoint point sets ${\displaystyle {\mathcal {A,B}}\in \mathbb {R} ^{n}}$, find a discriminant, ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ such that ${\displaystyle f({\mathcal {A}})>0,f({\mathcal {B}})\leq 0}$. 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, ${\displaystyle f(x)=cx+\gamma }$. 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]

• Backpropagation
• Linear programming