6
$\begingroup$

I have read this question and I am confused by a part of the first answer, even though it is asked in the comments.

I don't understand why $$L_{(\mathcal{D}, f)}(h^{*}) = 0 \implies L_{S}(h^{*}) = 0$$

Why if the "True Error" equal to $0$ i.e. $L_{(\mathcal{D}, f)}(h^{*}) = 0$ then it's implied that the "Training Error" is also equal to $0$ i.e. $ L_{S}(h^{*}) = 0$?

After the answer to my previous question, I started understanding what is $\mathcal{D}$. Now, I think intuitively I can understand what they mean by this implication relation. So here's my intuitive explanation (please correct me if I'm wrong):

Since the classifier $h^*$ has zero error when applied to the "population" $\mathcal{X}$ (where $\mathcal{X}$ is the set of input datapoints, and where a "training" $\mathcal{X}$ is the training datapoints), this means that $h^*$ has information about all samples of $\mathcal{X}$ from the population and it has correctly classified them with $0$ error, hence when applied to one of these samples (i.e., in our case the training sample), it will clearly yield $0$ error.

I hope my intuitive explanation is understandable.

Is my understanding correct and how would I prove this more rigorously? (If it's possible to do so?)

$\endgroup$
3
  • $\begingroup$ I have the same question. Also does the implication need i.i.d. assumption? $\endgroup$
    – S.H.W
    Jan 11 at 1:25
  • $\begingroup$ @S.H.W, Given its from the understanding ML from theory to algs book that is a safe assumption. Statistical learning only just started going beyond i.i.d. around 2020 ish. $\endgroup$
    – prijatelj
    Jan 11 at 7:57
  • $\begingroup$ I ammend my statement. They often assume i.i.d. in statistical learning, thus greatly simplifying the problem. However, i.i.d. is not necessary for that implication to hold. Just that the same loss is measured on the predictions resulting from the true $h^*$, so the loss is then zero. $\endgroup$
    – prijatelj
    Jan 11 at 8:20

1 Answer 1

3
+50
$\begingroup$

The Reasoning is Correct

This reasoning is correct when the training sample $S$ is a representative sampling of the true (population) distribution $\mathcal{D}$ and there is no noise in the true labels.

Given this is the "realizable" case, which just means the loss can actually equal zero and thus the most correct hypothesis will result in a loss of zero, then if $h^*$ was the true or a correct hypothesis then there would be no error on any sampling of the distribution as long as there is no other source of uncertainty. This includes the finite sampling that is the training set.


Recall a random variable $R$ is always associated with a probability triple. which consists of the sample space $\Omega_R$ (really a set), the event space $\Sigma_R$ (the sigma algebra of that set), and a probability distribution $P_R$.

Note that the following proof holds without the assumption of $i.i.d.$ random variables.

In the following, I changed some of the structure and notation of the parts in hopes to aid reader's in understanding their relationships better and to emphasize explicit parts in the definitions of Ref. [1] that are left implicit in their notation as used in the question above.

Proof

We start by setting up what is given:

  1. Let there be some task $\mathcal{T} \triangleq \{(\mathscr{X},\Sigma_X), (\mathscr{Y}, \Sigma_Y)\}$ that consists of the input space and output space respectively. The task of a predictor is to find some $\mathcal{H}$-parameterized function $f : \mathcal{H} \times (\mathscr{X},\Sigma_X) \mapsto (\mathscr{Y}, \Sigma_Y)$ without error, which is theoretically possible in the "realizable" case as defined in Ref. [1].
    • $\mathcal{H}$ is used to denote the parameter set of the parameter space, which is the hypothesis space. This is important to note because any function written in a formal language (as all formal math and logic is) can be represented by a parameterized function whose parameters is a string written in that formal language. Think of it as a programming language where a program performing the task by computing the function $f$ is the hypothesis.
  2. Let there be a random variable $X$ whose probability triple is $(\mathscr{X}, \Sigma_X, P_X)$ and the support of $X$ is over the set of possible inputs to the task, $\mathscr{X}$.
  3. Let there be another random variable $Y$ over the output space, or label space, of the task, whose corresponding probability triple is $(\mathscr{Y}, \Sigma_Y, P_Y)$
  4. Let $\mathcal{D} = (X, Y)$ be the joint distribution of the two random variables simply concatenated together such that an input sample $x \in \mathscr{X}$ is paired with its correct label $y \in \mathscr{Y}$, resulting in the sample space of $\mathcal{D}$ to be $\Omega_\mathcal{D} = \{(x_i, y_i) : x_i \in \mathscr{X}, y_i \in \mathscr{Y}, i \in \mathbb{N} \}$.
    • Note that $i \in \mathbb{N}$ serves as an enumeration of all unique pairs, simply used here to emphasize they belong together and that $y_i$ is the correct label to be predicted for $x_i$. We continue to use this notation in the following.
  5. Let $\mathcal{L}: \mathscr{X} \times \mathscr{Y} \mapsto [0, \infty]$ be the loss function of interest, where $[0, \infty]$ is the range of the loss as a measure.
    • Using the empirical risk as $\mathcal{L}$, the loss over some set $S \subseteq \Omega_\mathcal{D}$ is $$\mathcal{L}_S\big(x, f(h, x)\big) = \frac{1}{|S|} \sum_{(x,y) \in S} f(h,x) \neq y$$
  6. Let $h^* \in \mathcal{H} : \forall\big( (x_i, y_i) \in \Omega_\mathcal{D} \big) : \Big( \mathcal{L}\big(x_i, f(h^*, x_i)\big) = 0 \Big)$ be the true hypothesis (coordinate in parameter space) or any equivalent hypothesis that solves the task in the "realizable" case, that is, without any error as measured by the loss function of interest.

As per what is given, $\forall (S \subseteq \Omega_\mathcal{D}): \Big(\mathcal{L}\big(x_i, f(h^*, x_i)\big) = 0 : (x_i, y_i) \in S \Big)$ $\blacksquare$

For the following reasons

  • every pair in the support of $\mathcal{D}$ will have a loss of zero in the realizable case by definition
  • any subset of that set of pairs will still have a loss of zero,
  • and because $h^*$ is the correct hypothesis which yields predictions with no error, that is a loss of zero.

Clarifying Notation

Some misunderstanding may result due to Ref. [1]'s notation for the definitions of $L_\mathcal{D}(h)$ and $L_S(h)$ in Section 3.2.1, and the question's notation of $L_{\mathcal{D},f}(h^*)$, as they made the measures about the hypothesis (parameter coordinate) instead of the input and output pairs, as I wrote in my proof. I rewrote $L_S(h)$ as $\mathcal{L}_S$ above under given knowledge 5. Rewriting the definition
for the probability of the loss not equaling zero given the hypothesis $h$ is as follows using my notation $$L_\mathcal{D}(h) = P_D\Big( (X, Y) \neq \big(x, f(h,x)\big) \Big) = P\Big( Y | X \neq f(h, x) \Big)$$

Notably, as Ref. [1] wrote $L_\mathcal{D}(h)$, the conditional distribution $Y |X$ is actually non-random due to their implicit assumption that the true label $y_i$ is fully determined by $x_i$, which is why the true hypothesis $h^*$ yields a probability zero of error. This is a result of assuming "realizable" learning, that is, there is a deterministic (non-random) mapping $f(h, X) = Y$. Otherwise, there would still be some uncertainty in the labels (noise as mentioned before) even when given $X=x$. Think about trying to predict the rolled outcomes of a fair die. The probability of your predictions being correct will asymptotically follow $\frac{1}{6}$ even if you modeled it correctly as a fair die. Given $X=x$, that is the max probability of being correct following empirical risk minimization (minimizing the error).


References

  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
$\endgroup$
6
  • $\begingroup$ Thanks for the answer but I'm looking for a rigorous proof. For example in these lecture notes, page 5, it's proved that assuming i.i.d. assumption we have $L_{S}(h^{*}) = 0$ with probability $1$ (Note that $L_{S}(h^{*})$ is a random variable). The curious fact is that in the book "Understanding Machine Learning: From Theory to Algorithms" the implication is stated before i.i.d. assumption. So it seems that they didn't use i.i.d. assumption. $\endgroup$
    – S.H.W
    Jan 11 at 10:36
  • $\begingroup$ @S.H.W I have updated my answer to include a formal proof and clarify some areas that may result in a misunderstanding for future readers of that book and these concepts. $\endgroup$
    – prijatelj
    Jan 11 at 19:12
  • $\begingroup$ Great answer, thanks. I must admit that I'm not convinced that i.i.d. assumption is unnecessary. Suppose that labeling function is $f$ and it's deterministic. We know that $$\mathcal{D}(\{x:h^*(x) = f(x) \}) = 1$$ and we want to find $$\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)\})$$ I think without independence assumption we can't go further. $\endgroup$
    – S.H.W
    Jan 11 at 20:14
  • $\begingroup$ The original question & it's linked Q's do not inquire about the necessity or sufficiency of the assumptions of i.i.d. or independent samples for the $L_\mathcal{D}(h^*) = 0 \implies L_S(h^*) = 0$ given realizable learning. I understand that is your primary interest given the bounty & your comments, however I think this would benefit from a new Q focused specifically on "Is i.i.d. or sample independence necessary for [this implication or whatever is your property of interest] to be True?" Perhaps write a new Q asking exactly what you're interested in? I am uncertain of your exact Q atm $\endgroup$
    – prijatelj
    Jan 11 at 20:30
  • $\begingroup$ If you write a new question, please link it here and I'll try to answer it. If you don't want to write a new Q, then I need more information on what you're interested in here being true with or without the i.i.d. or independent sampling assumptions. What you wrote here would also be with prob 1 given $h^*(x) = f(x)$, if I understand what you mean by your notation, so all the $x \in \mathscr{X}$ would have the same result as written, i.e., the equality holds. If it holds for the superset $\mathscr{X}$, then it holds for any subset of the domain as the function behavior does not change. $\endgroup$
    – prijatelj
    Jan 11 at 20:44

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.