𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Learning with Unreliable Boundary Queries

✍ Scribed by Avrim Blum; Prasad Chalasani; Sally A Goldman; Donna K Slonim

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
576 KB
Volume
56
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We introduce a model for learning from examples and membership queries in situations where the boundary between positive and negative examples is somewhat ill-defined. In our model, queries near the boundary of a target concept may receive incorrect or don't care'' responses, and the distribution of examples has zero probability mass on the boundary region. The motivation behind our model is that in many cases the boundary between positive and negative examples is complicated or fuzzy.'' However, one may still hope to learn successfully, because the typical examples that one sees do not come from that region.

We present several positive results in this new model. We show how to learn the intersection of two arbitrary halfspaces when membership queries near the boundary may be answered incorrectly. Our algorithm is an extension of an algorithm of Baum (1990Baum ( , 1991) ) that learns the intersection of two halfspaces whose bounding planes pass through the origin in the PAC-with-membership-queries model. We also describe algorithms for learning several subclasses of monotone DNF formulas.

πŸ“œ SIMILAR VOLUMES

Learning with an unreliable teacher
Learning with an unreliable teacher
✍ GΓ‘bor Lugosi πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 595 KB
Learning counting functions with queries
Learning counting functions with queries
✍ Zhixiang Chen; Steven Homer πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 1022 KB

We investigate the problem of learning disjunctions of counting functions, which are general cases of parity and modulo functions, with equivalence and membership queries. We prove that, for any prime number p, the class of disjunctions of integer-weighted counting functions with modulus p over the

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 \