32 Training Set Bounds

Lets understand why the test set bounds we already got is no longer valid if $S$ is the training set.

• The test set bound was derived under the assumption that the coin-flips (errors $I[c(x_i)\ne y_i]$) are i.i.d.
• If $S$ was an independent test set then this is true provided the examples are i.i.d.
• If $S$ the training sample, then the classifier becomes a random variable as it depends on $S$, hence all $I[c(x_i))\ne y_i])$ depend on the same $c$ - they are no longer i.i.d!
• Therefore, the same bound would not hold true when $S$ is the training set!