The training error of best hypothesis

Question

Let $\mathcal{X}$ and $\mathcal{Y}$ denote the domain set and label set respectively. Also let $\mathcal{D}$ be a distribution over $\mathcal{X}$ and $f:\mathcal{X} \to \mathcal{Y}$ be the true labeling function. So for generating the data, we first sample from $\mathcal{D}$ and then apply function $f$. We define the error of a prediction rule $h:\mathcal{X} \to \mathcal{Y}$ to be, $$L_{\mathcal{D} , f}(h) = \mathcal{D}(\{x:h(x) \not = f(x) \}).$$Suppose that the realizability assumption for hypothesis class $\mathcal{H}$ holds which means that there exists $h^* \in \mathcal{H}$ such that $L_{\mathcal{D} , f}(h^*) = 0$. We collect $m$ samples $S=\{(x_1,y_1),(x_2,y_2),\dots , (x_m,y_m) \}$ and compute the error of $h^*$ on $S$: $$L_S(h^*) = \frac{|i\in [m]: h^*(x_i) \not = y_i|}{m}$$ Now we have:$$\mathbb{P}[L_S(h^*) = 0] = \mathcal{D}^m(\{(x_1,x_2,\dots, x_m):h^*(x_1) = f(x_1) \ \text{and} \ h^*(x_2) = f(x_2) \ \text{and} \dots h^*(x_m) = f(x_m)\})$$ If the samples are independent then, $$\mathbb{P}[L_S(h^*) = 0] = \mathcal{D}(\{x_1: h^*(x_1) = f(x_1)\})\mathcal{D}(\{x_2: h^*(x_2) = f(x_2)\}) \dots \mathcal{D}(\{x_m: h^*(x_m) = f(x_m)\}) = 1.$$ What about the case in which samples are dependent? How can it be proved that $\mathbb{P}[L_S(h^*) = 0] = 1$?

Answer 1

In general you just can write \begin{eqnarray*} \mathbb{P}[L_S(h^*) = 0] &=& \mathcal{D}(\{x_1: h^*(x_1) = f(x_1)\})\\ && \mathcal{D}(\{x_2: h^*(x_2) = f(x_2)\}|h^*(x_1) = f(x_1))\\ && \mathcal{D}(\{x_3: h^*(x_3) = f(x_3)\}|h^*(x_1) = f(x_1),h^*(x_2) = f(x_2)) \dots, \end{eqnarray*} and all of the terms have to be 1.

This is because $\mathcal{D}(\{x: h^*(x) = f(x)\})=1$ by assumption, and therefore $\mathcal{D}(\{x: h^*(x) = f(x)\}|C)=1$ must hold for any $C$ with $P(C)>0$ as $P(A)=P(A|B)P(B)+P(A|B^c)P(B^c)$, which can only be 1 if $P(A|B)$ is 1 as long as $P(B)\neq 0$. (Note that there is a certain mix-up in notation between your use of ${\mathcal{D}}$ and my use of $P$ here, and I'm too lazy to fix that. The argument shouldn't be affected.)

Answer 2

tl;dr : The Assumptions Avoid the Proof

What is assumed avoids having to prove either the sample dependent or independent case. It merely follows by what is assumed. The distribution $\mathcal{D}$ is irrelevant in this case because the actual distribution involved in your $\mathbb{P}[L_S(h^*) = 0] = 1$ is a Dirac distribution with all the probability on $L_S(h^*) = 0$ as follows from assumptions of $h^*$ in "realizable" learning. Absolute certainty lies in determinism.

Note that how you wrote the equality between the expressions using $\mathcal{D}$ to define $\mathbb{P}[L_S(h^*) = 0]$ is incorrect because $\mathcal{D}$ is only about the probability of witnessing a sample $x \in \mathcal{X}$, not about the probability of error. As written $x $ ~ $ \mathcal{D}$ does not necessarily equal probability 1, but comparing if $h^*(x) = f(x)$ is independent of the probability of $x$ occurring as they are defined, and so that is 1 by def of $h^*$.

Below, I explain in detail my point without a proof because that quickly turns into an open question in research of statistical learning if you keep relaxing distribution constraints from i.i.d. to beyond ergodic and stationary process into a non-stationary stochastic processes.

Note if you were to practically find $h^*$, $\mathcal{D}$ and the dependency between its samples absolutely matters.

An Explanation Without Formal Proof

I believe the issue lies in where the probability distributions actually affect anything, in particular $L_S$ and $L_{\mathcal{D}, f}$. This is often an issue when people use $P(\cdot)$ without specifying what equals what, or which probability distribution things are relative to. To help be clear what source of uncertainty I am referring to, I will continue (as from my prior answer here) to refer to $\mathcal{D} = (X, Y)$ as a joint distribution of input $X$ and output $Y$ as random variables, and $f(X) = Y$.

As per your question and the assumption of "realizable learning", the only distribution that could matter is $X$. I explain that now.

If $h^*(x) = f(x) = y$ for all $x \in \mathcal{X}$, which we are given, then the error in prediction from $h^*(x)$ wrt $f(x)$ is zero, always, regardless of any random or purposeful assortment, permutation, or poking and prodding of these functions' definitions. If given the same $x$ as input, they produce the same $y$, as that's what their equality means.

The formal theorem for this is the Data Processing Inequality, as defined in Ref. [2], Section 2.8

Theorem 2.8.1 (Data-processing inequality) If $X \rightarrow Y \rightarrow Z$ [is a markov chain of three random variables, $X,Y,Z$], then $I(X;Y) \ge I(X;Z)$.

This means that as long as there is only one source of uncertainty (as in entropy), in our case $X$ because assuming "realizable learning" means $f(X) = Y$ is a deterministic function and there is no other source of error, thus allowing zero error in the loss, then any deterministic transformation of that random variable can only have equal expected uncertainty or less. Given $h^*(X) = f(X) = Y$ by definition and "realizable learning" assumption, then all the uncertainty (probability) in $Y$ is fully determined by $X$ as transformed by $f$.

So that's the reason the loss is zero in addition to the fact that this magical $h^*$ is plucked from the imagination and not defined on how it is obtained. The curse of being too general to be useful, but yet given these properties assumed, we can reason about such an object.

This is why I stated in my last answer that if $h^*$ yields zero error on all of $\mathcal{X}$, then applying that hypothesis to any subset of $\mathcal{X}$ also yields zero error. Doesn't matter about the distribution $X$ over the space $\mathcal{X}$, because we have this magically correct $h^*$ and the $f(\cdot)$ and the losses are independent of $\mathcal{D}$ after $h^*$ is assumed.

If you want to know how to actually find $h^*$, that is an entirely different problem ripe with model assumptions including that the hypothesis space you considered even includes a correct hypothesis that could yield zero error (this is identifiability, and related is the concept of parameter or hypothesis space misspecification).

In this context, to address dependency of samples across time you need to use stochastic processes, where a process is a function over time, and a stochastic process is essentially how the random variable changes over time. There the dependency on prior states can involve either observed or latent (hidden) states. This is now a time series problem, and here be monsters. ;)

Further Reading

For more reading on finding $h^*$, I provide a snippet from this answer that is relevant after updating the reference numbers here. Recall I refer to the hypothesis space as the parameter space.

1. identifiable [Ref. 3], meaning that the model is able to represent the observed process and is typically meant as a single parameter is point-identifiable from the information available in the observations, and
2. "consistent" or is a "well behaved" parameter space with a "well behaved" update function that can converge to the true parameter.

This is discussed at length in [Ref. 4, Ch.6--9], specifically with regard to Bayesian modelling. Unfortunately, this is not open access.

What you are seeking in such a case is a mathematical and algorithmic formalization of inductive reasoning and inference, which has been of great interest for centuries. The Bayesian modeling approach tends to be involved in the probabilistic mathematical induction. Some relevant books of interest include Ref. 5 Ch. 5 & Ref. 6 Ch. 2.

---

References

= Closed Access. = Open Access.

1. Shalev-Shwartz, Shai and Ben-David, Shai. "Understanding Machine Learning: From Theory to Algorithms". May 2014. Cambridge University Press. ISBN 978-1-139-95274-3
   • https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/
2. Cover, Thomas M. and Thomas, Joy A. "Elements of Information Theory". John Wiley & Sons, Inc. 2006. 2nd Ed. ISBN-13 978-0-471-24195-9
   • https://doi.wiley.com/10.1002/047174882X
3. Lewbel, Arthur. 2019. "The Identification Zoo: Meanings of Identification in Econometrics." Journal of Economic Literature, 57 (4): 835-903.
   • preprint: https://www.bc.edu/content/dam/bc1/schools/mcas/economics/pdf/working-papers/wp957.pdf
4. Ghosal, Subhashis, and Aad Van der Vaart. Fundamentals of nonparametric Bayesian inference. Vol. 44. Cambridge University Press, 2017.
   • https://scholar.google.com/citations?view_op=view_citation&hl=en&user=u2tifuYAAAAJ&citation_for_view=u2tifuYAAAAJ:HDshCWvjkbEC
5. Li, Ming, and Paul Vitányi. An introduction to Kolmogorov complexity and its applications. Vol. 3. New York: Springer, 2008.
   • https://link.springer.com/book/10.1007/978-3-030-11298-1
6. Hutter, Marcus. Universal artificial intelligence: Sequential decisions based on algorithmic probability. Springer Science & Business Media, 2004.
   • https://link.springer.com/book/10.1007/b138233
   • Public related slides: http://www.hutter1.net/ai/suaibook.pdf