From Understanding Machine Learning: Theory and Algorithms:

What does the phrase in the red box below mean in terms of set theory?

I see that it means for every $h \in H$ we have $D(|L_s(h) - L_D(h)| \le \epsilon) \ge 1 - \delta$.

But how is $|L_s(h) - L_D(h)| \le \epsilon$ a random variable?

If it's a random variable then in should be of the form $\{a \in A : X(a) \le \epsilon\}$ where $X = |L_s(h) - L_D(h)|$ and $A$ is the sample space.

But what in this definition is $A$?

I know that $L_D(h) = \Bbb E_{z \text{~}D}[l(h,z)] = \sum_{z \in Z}l(h,z)D(z)$ and $L_S(h) = \frac{1}{m}\sum_{z_i \in S} l(h,z)$ where:

$l(h,z)$ is a loss function, $D$ is the distribution on $Z$, and $S$ is a training set.

enter image description here

  • $\begingroup$ $|L_s(h)-L_D(h)|\leq \epsilon$ is an event not a random variable. Further, one of the interesting aspects of probability theory is that often the sample space can be shoved under the rug, we really just care about probability measures and distributions—but this is probably not what you want to hear. $\endgroup$ – Nap D. Lover Jan 19 at 18:20
  • $\begingroup$ Ah, I see. So what would be the set-theoretic notation for the event $|L_S(h) - L_D(h)| \le \epsilon$? $\endgroup$ – Oliver G Jan 19 at 18:54
  • $\begingroup$ Exactly as you wrote: $X=|L_s(h)-L_D(h)|$ is the random variable, and the event is denoted $\{\omega \in \Omega : X(\omega) \leq \epsilon\}$ where $\Omega$ is the sample space, or often in shorthand as just $\{X \leq \epsilon\}$ taking into the convention about sample spaces I allude to in my first comment. I just wanted to (perhaps at the risk of pedantry) correct the terminology. One seldom needs to know what is $\Omega$ specifically to measure the set $\{X \leq \epsilon\}$. All you need is the law/distribution of $X$. $\endgroup$ – Nap D. Lover Jan 19 at 19:01
  • $\begingroup$ For example, consider a $\mathcal{U}(a,b)$ random variable on some sample space $\Omega$, i.e. $U: \Omega\to \mathbb{R}$. The distribution is known, $\mathbb{P}(U\leq u)=\frac{u-a}{b-a}$, and so for any Borel set of the real line, $B$, you can compute $\mathbb{P}(U\in B)$, in practice without having to deal with $\Omega$. See math.stackexchange.com/questions/2531810/… for a better and detailed exposition on how sample spaces are treated. $\endgroup$ – Nap D. Lover Jan 19 at 19:06
  • $\begingroup$ But that's exactly what I'm trying to understand. If $X$ is that function, what is the domain? What am I specifically showing the error of with this function? $\endgroup$ – Oliver G Jan 19 at 19:10

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.