Consider a variant of the PAC model in which there are two example oracles: one that generates positive examples and one that generates negative examples, both according to the underlying distribution D on X .

Formally, given a target function $f : X → \{0,1\}$, let $D^+$ be the distribution over $X^+ = \{x\in X : f (x) = 1\}$ defined by $D^+(A) = D(A)/D(X + )$, for every A ⊂ X + .

  • Similarly, $D^−$ is the distribution over X induced by D.

The definition of PAC learnability in the two-oracle model is the same as the standard definition of PAC learnability except that here the learner has access to $m^+(,δ)$ i.i.d. examples from $D^+$ and $m^−( ,δ)$ i.i.d. examples from $D^−$ . The learner’s H goal is to output $h$ s.t. with probability at least $1 − δ$ (over the choice of the two training sets, and possibly over the nondeterministic decisions made by the learning algorithm), both $L_{D^+ , f } (h) ≤ \epsilon$ and $L {D−, f } (h) \le \epsilon$.

Show that if $H$ is PAC learnable (in the standard one-oracle model), then $H$ is PAC learnable in the two-oracle model.

This question is Exercise 3.9 of "understanding machine learning: from theory to algorithms".

Even if there is an solution manual to the book, the solution it provided for this exercise is hard to understand and has some confusing notations.

In particular, the solution it provided for this exercise (please search "Suppose that H is PAC learnable in the one-oracle model" in the solution manual) give 2 distributions, one is $D$ and the other is $D'$ as shown in the following picture, what's the relationship between $D$ and $D'$? Why does the derivation illustrated by my red arrow succeed?

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.