Re: Why multiply right side of Hoeffding Inequality by number of hypothesis?
Oh, I think I got it.
The link in reasoning that I missed is that probability of bad event in each hypothesis MAY AFFECT our final choice. But we don't know how, so we consider the range between the best and the worst possible cases.
The best case  bad events happening in tested hypothesis don't affect our choice of the final one at all, so for probability of bad event in g(x) we can still use Hoeffding without factor M.
The worst case  when we have such sample, and such hypothesis set, and such learning algorithm that bad event in some hypothesis makes us to select the very same hypothesis as a final one. In this unlucky situation probability of bad event in final hypothesis will be probability of "at least one hypothesis in a set has bad event".
Am I right?
