Learning with unreliable boundary queries

July 1995

Learning with unreliable boundary queries

Authors:

Avrim Blum, Prasad Chalasani, Sally A. Goldman, and Donna K. Slonim

Abstract:

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 (1990, 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.
@conference{Blum-1995-16189,
author = {Avrim Blum And Prasad Chalasani And Sally A. Goldman And Donna K. Slonim},
title = {Learning with unreliable boundary queries},
booktitle = {Proceedings of 8th Annual Conference on Computational Learning Theory (COLT '95)},
year = {1995},
month = {July},
pages = {98 - 107},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.