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?


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.

  • $\begingroup$ is $k(1 - \epsilon)^m$ a lower bound on the probability that exactly one hypothesis out of k is consistent ? $\endgroup$
    – calveeen
    Apr 29 '20 at 4:41
  • $\begingroup$ @calveeen It cannot be a lower bound. The probability that one hypothesis out of $k$ is consistent (according to you and your book) is $(1 - \epsilon)^m$, which is smaller than $k(1 - \epsilon)^m$, because $k \geq 1$. $\endgroup$
    – nbro
    Apr 29 '20 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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