Machine learning: PAC-learnability

135 Views Asked by At

Would love your help (even a clue or a direction) with this question from hw assignment.

Let $\mathcal{C}$ denote the class of all possible target concepts defined over a set of instances $\mathcal{X}$.

Suppose that $\mathcal{H}$ is a space of binary hypotheses containing the constant concept $c_1$ defined by $c_1(x) = +1$ for all $x \in \mathcal{X}$, and having the property that $\mathcal{C} \setminus \{c_1\}$ is PAC-learnable by an algorithm $L$ using $\mathcal{H}$ with sample complexity $m(\delta, \epsilon)$.

Provide a learning algorithm $L'$ that uses $L$, so that $\mathcal{C}$ (including $c_1$) is PAC-learnable by $L'$ using $\mathcal{H}$ with sample complexity $\max\{m(\delta,\epsilon), \frac{\log\frac{1}{\delta}}{\epsilon}\} $