Learning separations by boolean combinations of half-spaces

N. S.V. Rao; E. M. Oblow; C. W. Glover

doi:10.1109/ICPR.1992.201850

Learning separations by boolean combinations of half-spaces

N. S.V. Rao, E. M. Oblow, C. W. Glover

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Given two subsets S₁ and S₂ (not necessarily finite) of R^d separable by a boolean combination of N halfspaces, we consider the problem of learning (in the sense of Valiant [13]# 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 exmaples are given in a batch, can be solved in time polynomial in the number of examples. We also provide an on-line learning algorithm that incrementally solves the problem by suitably training a system of N perceptrons much in the spirit of classical perceptron learning algorithm.

Original language	English
Title of host publication	Conference B
Subtitle of host publication	Pattern Recognition Methodology and Systems
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	603-606
Number of pages	4
ISBN (Print)	0818629150
DOIs	https://doi.org/10.1109/ICPR.1992.201850
State	Published - 1992
Externally published	Yes
Event	11th IAPR International Conference on Pattern Recognition, IAPR 1992 - The Hague, Netherlands Duration: Aug 30 1992 → Sep 3 1992

Publication series

Name	Proceedings - International Conference on Pattern Recognition
Volume	2
ISSN (Print)	1051-4651

Conference

Conference	11th IAPR International Conference on Pattern Recognition, IAPR 1992
Country/Territory	Netherlands
City	The Hague
Period	08/30/92 → 09/3/92

Funding

true if ( Z ~ ) ~2Z and false if if ( ~ j ) 5~ xxi. It ~-~ The authors gratefully acknowledge the continuing financial support of this learning research by Oscar Manley of the Basic Energy Sciences Program in the Department of Energy and Teresa McMullen in the Intelligent Systems Program of the Office of Naval Research in the Department of Defense. Also, the first author is funded by National Science Foundation under grant #IRI-9108610, Oak Ridge National Laboratory operated by Martin Marietta nnder contracts #19X-SE043V and #SOX- SJ433V,O ld Dominion University Summer Faculty Fellowship for 1991 and Virginia’s Center for Innovative Technology under contract # INF-90-015.

Access to Document

10.1109/ICPR.1992.201850

Cite this

Rao, N. S. V., Oblow, E. M., & Glover, C. W. (1992). Learning separations by boolean combinations of half-spaces. In Conference B: Pattern Recognition Methodology and Systems (pp. 603-606). Article 201850 (Proceedings - International Conference on Pattern Recognition; Vol. 2). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICPR.1992.201850

@inproceedings{1858878a4fb8418486174296a32befa3,

title = "Learning separations by boolean combinations of half-spaces",

abstract = "Given two subsets S1 and S2 (not necessarily finite) of Rd separable by a boolean combination of N halfspaces, we consider the problem of learning (in the sense of Valiant [13]# 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 exmaples are given in a batch, can be solved in time polynomial in the number of examples. We also provide an on-line learning algorithm that incrementally solves the problem by suitably training a system of N perceptrons much in the spirit of classical perceptron learning algorithm.",

author = "Rao, {N. S.V.} and Oblow, {E. M.} and Glover, {C. W.}",

note = "Publisher Copyright: {\textcopyright} 1992 Institute of Electrical and Electronics Engineers Inc. All rights reserved.; 11th IAPR International Conference on Pattern Recognition, IAPR 1992 ; Conference date: 30-08-1992 Through 03-09-1992",

year = "1992",

doi = "10.1109/ICPR.1992.201850",

language = "English",

isbn = "0818629150",

series = "Proceedings - International Conference on Pattern Recognition",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "603--606",

booktitle = "Conference B",

}

Rao, NSV, Oblow, EM & Glover, CW 1992, Learning separations by boolean combinations of half-spaces. in Conference B: Pattern Recognition Methodology and Systems., 201850, Proceedings - International Conference on Pattern Recognition, vol. 2, Institute of Electrical and Electronics Engineers Inc., pp. 603-606, 11th IAPR International Conference on Pattern Recognition, IAPR 1992, The Hague, Netherlands, 08/30/92. https://doi.org/10.1109/ICPR.1992.201850

Learning separations by boolean combinations of half-spaces. / Rao, N. S.V.; Oblow, E. M.; Glover, C. W.
Conference B: Pattern Recognition Methodology and Systems. Institute of Electrical and Electronics Engineers Inc., 1992. p. 603-606 201850 (Proceedings - International Conference on Pattern Recognition; Vol. 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Learning separations by boolean combinations of half-spaces

AU - Rao, N. S.V.

AU - Oblow, E. M.

AU - Glover, C. W.

PY - 1992

Y1 - 1992

N2 - Given two subsets S1 and S2 (not necessarily finite) of Rd separable by a boolean combination of N halfspaces, we consider the problem of learning (in the sense of Valiant [13]# 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 exmaples are given in a batch, can be solved in time polynomial in the number of examples. We also provide an on-line learning algorithm that incrementally solves the problem by suitably training a system of N perceptrons much in the spirit of classical perceptron learning algorithm.

AB - Given two subsets S1 and S2 (not necessarily finite) of Rd separable by a boolean combination of N halfspaces, we consider the problem of learning (in the sense of Valiant [13]# 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 exmaples are given in a batch, can be solved in time polynomial in the number of examples. We also provide an on-line learning algorithm that incrementally solves the problem by suitably training a system of N perceptrons much in the spirit of classical perceptron learning algorithm.

UR - http://www.scopus.com/inward/record.url?scp=85051425876&partnerID=8YFLogxK

U2 - 10.1109/ICPR.1992.201850

DO - 10.1109/ICPR.1992.201850

M3 - Conference contribution

AN - SCOPUS:85051425876

SN - 0818629150

T3 - Proceedings - International Conference on Pattern Recognition

SP - 603

EP - 606

BT - Conference B

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 11th IAPR International Conference on Pattern Recognition, IAPR 1992

Y2 - 30 August 1992 through 3 September 1992

ER -

Learning separations by boolean combinations of half-spaces

Abstract

Publication series

Conference

Funding

Access to Document

Other files and links

Fingerprint

Cite this