0
$\begingroup$

The second section of these notes points explains how one might PAC learn the concept class of intervals of all positive half-lines in $\mathbb{R}$. If we restricted our attention to $\mathbb{N}$ instead of $\mathbb{R}$, is this concept class still PAC learnable?

$\endgroup$

1 Answer 1

2
$\begingroup$

Yes, it's trivial. The learning algorithm consists of choosing the smallest positive example $x_0$, and taking the hypothesis to be $h(x)=1[x\ge x_0]$. All of the generalization guarantees proved for $\mathbb{R}$ hold here as well. In particular, it's a proper PAC learner for a VC-class of VC-dim 1. You can also use the specialized structure (of the class and algorithm) to shave off the superfluous $\log(n)$ factor you'd get from generic VC-based bounds.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.