We define a new noise model in which the learner draws examples from a mixt
ure of the "true" distribution and a "noise" distribution. We show how to l
earn monomials in our model, when the "'true" distribution is a product dis
tribution. We show that our results apply not only to product distributions
but to a wide class of distributions. (C) 1998 Published by Elsevier Scien
ce B.V. All rights reserved.