Separating models of learning with faulty teachers

We study the power of two models of faulty teachers in Valiant’s PAC learning model and Angluin’s exact learning model. The first model we consider is learning from an incomplete membership oracle introduced by Angluin and Slonim D. Angluin, D.K. Slonim, Randomly fallible teachers: Learning monotone DNF with an incomplete membership oracle, Machine Learning 14 (1) (1994) 7–26]. In this model, the answers to a random subset of the learner’s membership queries may be missing. The second model we consider is random persistent classification noise in membership queries introduced by Goldman, Kearns and Schapire S. Goldman, M. Kearns, R. Schapire, Exact identification of read-once formulas using fixed points of amplification functions, SIAM Journal on Computing 22 (4) (1993) 705–726]. In this model, the answers to a random subset of the learner’s membership queries are flipped.