An algorithm to learn read-once threshold formulas, and transformations between learning models

Nader H. Bshouty; Thomas R. Hancock; Lisa Hellerstein; Marek Karpinski

doi:10.1007/BF01205054

An algorithm to learn read-once threshold formulas, and transformations between learning models

Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, Marek Karpinski

Research output: Contribution to journal › Article › peer-review

Abstract

We present a membership query (i.e. black box interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of Boolean threshold functions. We also present a catalogue of generic transformations that can be used to convert an algorithm in one learning model into an algorithm in a different model.

Original language	English (US)
Pages (from-to)	37-61
Number of pages	25
Journal	Computational Complexity
Volume	4
Issue number	1
DOIs	https://doi.org/10.1007/BF01205054
State	Published - Mar 1994

Keywords

68Q20
68T05
Subject classifications
equivalence queries
justifying assignments
learning algorithms
learning models
membership queries
read-once threshold formulas
transformations

ASJC Scopus subject areas

Theoretical Computer Science
General Mathematics
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1007/BF01205054

Cite this

@article{e722acfdd4f848ef954acfd4d9e916c4,

title = "An algorithm to learn read-once threshold formulas, and transformations between learning models",

abstract = "We present a membership query (i.e. black box interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of Boolean threshold functions. We also present a catalogue of generic transformations that can be used to convert an algorithm in one learning model into an algorithm in a different model.",

keywords = "68Q20, 68T05, Subject classifications, equivalence queries, justifying assignments, learning algorithms, learning models, membership queries, read-once threshold formulas, transformations",

author = "Bshouty, {Nader H.} and Hancock, {Thomas R.} and Lisa Hellerstein and Marek Karpinski",

year = "1994",

month = mar,

doi = "10.1007/BF01205054",

language = "English (US)",

volume = "4",

pages = "37--61",

journal = "Computational Complexity",

issn = "1016-3328",

publisher = "Birkhauser Verlag Basel",

number = "1",

}

TY - JOUR

T1 - An algorithm to learn read-once threshold formulas, and transformations between learning models

AU - Bshouty, Nader H.

AU - Hancock, Thomas R.

AU - Hellerstein, Lisa

AU - Karpinski, Marek

PY - 1994/3

Y1 - 1994/3

N2 - We present a membership query (i.e. black box interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of Boolean threshold functions. We also present a catalogue of generic transformations that can be used to convert an algorithm in one learning model into an algorithm in a different model.

AB - We present a membership query (i.e. black box interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of Boolean threshold functions. We also present a catalogue of generic transformations that can be used to convert an algorithm in one learning model into an algorithm in a different model.

KW - 68Q20

KW - 68T05

KW - Subject classifications

KW - equivalence queries

KW - justifying assignments

KW - learning algorithms

KW - learning models

KW - membership queries

KW - read-once threshold formulas

KW - transformations

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

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

U2 - 10.1007/BF01205054

DO - 10.1007/BF01205054

M3 - Article

AN - SCOPUS:0008165967

SN - 1016-3328

VL - 4

SP - 37

EP - 61

JO - Computational Complexity

JF - Computational Complexity

IS - 1

ER -

An algorithm to learn read-once threshold formulas, and transformations between learning models

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this