Publication Details
Title: Read-Once Threshold Formulas, Justifying Assignments, and Generic Tranformations
Author: N. H. Bshouty, T. R. Hancock, L. Hellerstein, and M. Karpinski
Group: ICSI Technical Reports
Date: March 1992
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-020.pdf
Overview:
We present a membership query (i.e. interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of boolean threshold functions. Using a generic transformation from [Angluin, Hellerstein, Karpinski 89], this gives an algorithm using membership and equivalence queries for exactly identifying the class of read-once formulas over the basis of boolean threshold functions and negation. We also present a series of generic transfor- mations that can be used to convert an algorithm in one learning model into an algorithm in a different model. Keywords: Learning Algorithms, Queries, Read-Once Formulas, Threshold Functions.
Bibliographic Information:
ICSI Technical Report TR-92-020
Bibliographic Reference:
N. H. Bshouty, T. R. Hancock, L. Hellerstein, and M. Karpinski. Read-Once Threshold Formulas, Justifying Assignments, and Generic Tranformations. ICSI Technical Report TR-92-020, March 1992
Author: N. H. Bshouty, T. R. Hancock, L. Hellerstein, and M. Karpinski
Group: ICSI Technical Reports
Date: March 1992
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-020.pdf
Overview:
We present a membership query (i.e. interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of boolean threshold functions. Using a generic transformation from [Angluin, Hellerstein, Karpinski 89], this gives an algorithm using membership and equivalence queries for exactly identifying the class of read-once formulas over the basis of boolean threshold functions and negation. We also present a series of generic transfor- mations that can be used to convert an algorithm in one learning model into an algorithm in a different model. Keywords: Learning Algorithms, Queries, Read-Once Formulas, Threshold Functions.
Bibliographic Information:
ICSI Technical Report TR-92-020
Bibliographic Reference:
N. H. Bshouty, T. R. Hancock, L. Hellerstein, and M. Karpinski. Read-Once Threshold Formulas, Justifying Assignments, and Generic Tranformations. ICSI Technical Report TR-92-020, March 1992