PAC-learning definition

Question

I am new in this field. In the book Foundations of Machine Learning by Mehryar Mohri, Afshi Rostamizadeh, and Ameet Talwalkar. The authors define the generalized error of a hypothesis as

$ R(h) = \Pr_{x \sim D}[h(x) \neq c(x)] = E_{x \sim D}[1_{h(x) \neq c(x)}]$

which is a number. However in the Definition 2.3 a concep class $C$ is said to be PAC-learnable if

$Pr_{S\sim D^{m}}[R(h_{S}) \leq \varepsilon ] \geq 1 - \delta$

for any $m \geq poly(1/\varepsilon,1/\delta,n, size(c)) $. Since by definition $R(h) = \Pr_{x \sim D}[h(x) \neq c(x)]$ is a number, What does this mean $Pr_{S\sim D^{m}}[R(h_{S}) \leq \varepsilon ] $ and $h_{S}$ in formal terms? The authors explain that $h_{S}$ depends on the sample $S$, but the question is how?

Another reason I have this question is due to the fact that every $h$ is defined as a function $h: \mathcal{X} \to \mathcal{Y}$ and the distribution $D$ is defined on $\mathcal{X}$, not on the hypothesis set $H$ where for each $h \in \mathcal{H}$, $h: \mathcal{X} \to \mathcal{Y}$.

Answer 1

$R(h)$ is not necessarily a number, it is a deterministic function of $h$. So, it would be a number if $h$ is deterministic, but if $h$ is a random variable, then $R(h)$ is also a random variable.

We consider $S \sim D^m$, a dataset that consists of $m$ i.i.d. samples, assumed to be drawn with respect to $D$. Accordingly, $h_S$ denotes the function that we end up with when we observed this fixed dataset $S$ (hence the subscript $S$).

Like you said, $R(h)$ is just a number for a given fixed $h$. However, in the case of $Pr_{S\sim D^m}(R(h_S))$, $h_S$ is NOT fixed and hence, neither is $R(h_S)$. Notice that it depends on the random dataset $S$ and as a function of a random variable, it is also a random variable.

Here is an example I just made up to demonstrate what these concepts correspond to:

Suppose you have a system that keeps spitting out pictures of animals and you want to classify them. Let's say, $\mathcal{Y} = \{\text{cat, dog, rat}\}$ and $\mathcal{X}$ is the set of all pictures that this picture generator can spit out that shows one of these three animals. Then, $D$ is defined over $\mathcal{X}$ because it describes the probability of observing a specific picture, for all possible pictures. Then, $S$ is $m$ observed pictures from this picture generator, sampled in i.i.d. fashion. These are concepts that are independent from your learning system, but only related to the nature of the problem you're dealing with.

Suppose you believe the best way to classify which animal is in a picture is to use a convolutional neural network (CNN) of a specific size and architecture and is trained using a certain algorithm. Then, you are restricting your hypothesis set $H$ as the set of all CNNs of that architecture and size that can be obtained via your specified training approach. If you instead decided to use SVMs, you would have ended up with a different $H$. Since $S$ is random, the CNN you'll obtain (i.e. $h_S$) is also random.

Notice there is an inherent randomness in $h_S$ due to the randomness in $S$, but there can be even more randomness if your training algorithm is non-deterministic. So, depending on the training approach that takes you from $S$ to $h_S$, $h_S$ can be a random variable even for a fixed $S$ (think about stochastic gradient descent).

Long story short, due to these random factors at play, $R(h_S)$ is not just a number, but a random variable.