๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

PAC Learning Intersections of Halfspaces with Membership Queries

โœ Scribed by S. Kwek; L. Pitt

Publisher
Springer
Year
1998
Tongue
English
Weight
323 KB
Volume
22
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

An Efficient Membership-Query Algorithm
An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution
โœ Jeffrey C Jackson ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 566 KB

We present a membership-query algorithm for efficiently learning DNF with respect to the uniform distribution. In fact, the algorithm properly learns with respect to uniform the class TOP of Boolean functions expressed as a majority vote over parity functions. We also describe extensions of this alg

Fast Learning of k-Term DNF Formulas wit
Fast Learning of k-Term DNF Formulas with Queries
โœ A. Blum; S. Rudich ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 649 KB

This paper presents an algorithm that uses equivalence and membership queries to learn the class of \(k\)-term DNF formulas in time \(n \cdot 2^{o(k)}\), where \(n\) is the number of input variables. This improves upon previous \(O\left(n^{k}\right)\) bounds and allows one to learn DNF formulas of \