Machine learning via mathematical programming
Kristin P. Bennett · Minds at UW (University of Wisconsin) · 1993
The purpose of this research is to create novel algorithms for inductive machine learning based on mathematical programming. Given k sets, the problem is to create a function which can be used to classify a future point as a member of one of the k sets. We propose using a general function called a multisurface. A multisurface consists of a set of surfaces (usually linear) in $R\sp{n}$ that partition the input space into disjoint regions that are assigned an output classification. We show that a multisurface corresponds to a neural network as well as to a decision tree. Our general approach to creating a multisurface is to model each component of the multisurface as a system of linear inequalities and to minimize the errors in these inequalities. We consider a number of problems, including two-category discrimination, multicategory discrimination, and bilinear separation. For two-class problems, we investigate the multisurface method of pattern recognition proposed by Mangasarian. This linear programming method is equivalent to neural network training and compares favorably with the standard back-propagation algorithm of neural networks. However, the method is sensitive to noise. In this thesis we propose a new robust linear programming formulation for creating linear discriminants. Computationally, the proposed approach is superior to other linear programs. A decision-tree algorithm using the new robust linear program is competitive with other decision-tree methods of machine learning. We extend the two-class results to k-class problems. We propose a single linear program to create a piecewise-linear separator for k classes. To improve computational speed, we reformulate the problem as a piecewise-quadratic minimization problem. We develop a parallel gradient distribution algorithm to solve the problem in parallel and test the algorithm on a parallel machine. The resulting piecewise-linear separators can also be used for decision-tree construction. Finally, we address bilinear separability: Can two classes be completely separated using only two planes? This problem is NP-complete. We formulate the problem as a system of disjunctive linear inequalities that can be solved by bilinear programming. We develop a Frank-Wolfe-type algorithm for solving the bilinear program. Over 140 consecutive instances of the NP-complete problem were solved correctly using our algorithm.