Abstract
Given two subsets S1and S2(not necessarily finite) of Rd separable by a Boolean combination of learning halfspaces, we consider the problem of (in the sense of Valiant) the separation function from a finite set of examples, i.e., we produce with a high probability a function close to the actual separating function. Our solution consists of a system of N perceptrons and a single consolidator which combines the outputs of the individual perceptrons. We show that an off-line version of this problem, where the examples are given in a batch, can be solved in time polynomial in the number of examples. We also provide an online learning algorithm that incrementally solves the problem by suitably training a system of N perceptrons much in the spirit of the classical perceptron learning algorithm.
| Original language | English |
|---|---|
| Pages (from-to) | 765-768 |
| Number of pages | 4 |
| Journal | IEEE Transactions on Pattern Analysis and Machine Intelligence |
| Volume | 16 |
| Issue number | 7 |
| DOIs | |
| State | Published - Jul 1994 |
Funding
Two sets SI & iRd and SZ C iRd (not necessarily finite) are A-polyhedral separable if there exist N hyperplanes HJ = {z: = s;}, (for z,xJ E Rd,zJ, E 18, j = 1.2 :... N) that separate SI and S, through a Boolean formula as follows. Associate with each hyperplane HJ a Boolean variable tJ:fo r 3 E qd,t he variable E, is true if (z-’)~:> x(, and false if (xJ)Tz< .ri. It is not defined at points lying on the hyperplanes. A Boolean formula I/) = $( (1, (2, . . . ,( ,v ) separates the sets S1 and Sz if dl is true at every point of SI and false at every point of Sz.T hus, 4’ defines a map f+ : Rd H (0, l}, called the separating function such that for s,y E iRd: (a) f,t.(s=) f+(y) if both T and y belong to either SI or SZ, and (b) f+(s)# f+(y) if one of s and y belongs to SI Manuscript received July 27, 1992; revised August 16, 1993. This work was supported by the Engineering Research Program of the Office of Basic Energy Sciences of the U.S. Department of Energy, under Contract DE-AC05-840R21400 with Martin Marietta Energy Systems, Inc. This work was supported in part by the National Science Foundation under Grant IRI-9108610, Old Dominion University Summer Faculty Fellowship for 1991 and Virginia’s Center for Innovative Technology under Contract INF-90-015. This work was presented at 1 Ith International Conference on Pattem Recognition, The Hague, The Netherlands, August 30-September 3, 1992. Recommended for acceptance by Associate Editor P. W. Duin.
| Funders | Funder number |
|---|---|
| Office of Basic Energy Sciences | |
| Virginia’s Center for Innovative Technology | INF-90-015 |
| National Science Foundation | IRI-9108610 |
| U.S. Department of Energy | DE-AC05-840R21400 |
| Old Dominion University |
Keywords
- Computation learnability
- N-learners problem
- N-polyhedral separability
- perceptron