Understanding Machine Learning: From Theory to Algorithms

3.5 Exercises 53

of the two training sets, and possibly over the nondeterministic decisions made
by the learning algorithm), bothL(D+,f)(h)≤andL(D−,f)(h)≤.
1.(*)Show that ifHis PAC learnable (in the standard one-oracle model),
thenHis PAC learnable in the two-oracle model.
2.(**)Defineh+to be the always-plus hypothesis andh−to be the always-
minus hypothesis. Assume thath+,h−∈H. Show that ifHis PAC learn-
able in the two-oracle model, thenHis PAC learnable in the standard
one-oracle model.