Multi-surface method

Short description: Form of decision making in machine learning

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. 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.

See also

• Backpropagation
• Linear Programming