Why is probability that at least one hypothesis out of $k$ being consistent with $m$ training examples $k(1- \epsilon)^m$?

Question

My question is actually related to the addition of probabilities. I am reading on computational learning theory from Tom Mitchell's machine learning book.

In chapter 7, when proving the upper bound of probabilities for $\epsilon$ exhausted version space (theorem 7.1), it says that the probability that at least one hypothesis out of the $k$ hypotheses in the hypotheses space $|H|$ being consistent with m training examples is at most $k(1- \epsilon)^m$.

I understand that the probability of a hypothesis, $h$, consistent with m training examples is $(1-\epsilon)^m$. However, why is it possible to add the probabilities for $k$ hypotheses? And might the probability be greater than 1 in this case?

Answer 1

Let $A$ and $B$ be two events. In general, the probability that either $A$ or $B$ occurs is defined as

$$ P(A \text{ or } B) = P(A) + P(B) - P(A \text{ and } B) $$

If $A$ and $B$ are disjoint, i.e. they cannot happen at the same time, then $P(A \text{ and } B) = 0$, so the above formula becomes

$$ P(A \text{ or } B) = P(A) + P(B) $$

If the probability of one arbitrary hypothesis being consistent with $m$ training examples is $(1-\epsilon)^m$, then, given the rule above and assuming that only one hypothesis is consistent with $m$ training examples, the probability of one or more (i.e. at least one) of the hypotheses being consistent with training examples is the sum of the probabilities, i.e. $k (1-\epsilon)^m$.

This probability can be bigger than one if more than one hypothesis is consistent with $m$ training examples. In that case, you have to take into account the probability that both hypotheses are consistent.

See e.g. notes General Probability, I: Rules of probability for more details about the union rule and other rules of probability.