Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1997-01-01

Filename

WUCS-97-17.PDF

DOI:

10.7936/K7P55KP2

Technical Report Number

WUCS-97-17

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 to 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 [7, 6] 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 elarning several subclasses of monotone DNF formulas.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7P55KP2

Download

Share

COinS