Confused the concept of a distribution in the book "Understanding machine learning"

Question

I am reading the book "Understanding machine learning: from theory to algorithms" by Shai Shalev-Shwartz and I am confused by the concept of a underlying distribution $D$.

In the second chapter of the book, it states the domain has a underlying distribution $D$ and a training set $S$ of size $m$ is sampled according to $D$. I guess $D$ refers to a probability measure of a probability space $(\Omega, F)$, where $F$ is a sigma-algebra and $\Omega$ is the domain of points.

But later in the book, when it talks about the i.i.d assumption it makes when sampling the points, is says

The i.i.d. assumption: The examples in the training set are independently and identically distributed (i.i.d.) according to the distribution D. That is, every $x_{i}$ in S is freshly sampled according to $D$ and then labeled according to the labeling function, $f$. We denote this assumption by $S ∼ D^{m}$ where $m$ is the size of $S$, and $D^{m}$ denotes the probability over m-tuples induced by applying $D$ to pick each element of the tuple independently of the other members of the tuple.

My question is:

• Is my guess on $D$ being a probability measure correct ?

• What does this $D^{m}$ mean? Is it also some probability measure? If it is, then what does its corresponding probability space look like and how is it induced by $D$ ?

Any help is appreciated.

Answer 1

Yes, I agree that the book is referencing some kind of probability distribution as the data generating process.

Under the iid assumption, we may define the problem over the product space and work with the measurable space $(\Omega^n,\mathcal{F}^n)$ where the $\Omega^n$ denote the cartesian product $\Omega \times \dots\times\Omega$ and $\mathcal{F}$ is $\sigma$-algebra generated by the $n$-dimensional rectangles $A\times B$ and we may define a product measure $F^n$ over it.

If $\mu$ and $\nu$ are $\sigma$-finite define over two measurable spaces $(X,\mathcal{F})$ and $(Y,\mathcal{G})$, there exists a unique measure $\lambda$ in the product space $(X\times Y, \mathcal{F}\times \mathcal{G})$ such that $$ \lambda(A\times B) = \mu(A)\nu(B) $$ such that $\mathcal{F}\times \mathcal{G}$ is generated by the sets $A\times B$ where $A\in\mathcal{F}$ and $B\in\mathcal{G}$.

In probability we usually work with measures dominated by either the Lebesgue or the counting measure that are $\sigma$-finite over $\mathbb{R}$ and $\mathbb{N}$ respectively, so that's why under iid $F^n= (F)^n$ such that the first is the product measure and the latter simply the power of the distributions.