Answers.Body: <p>Let <span class="math-container">$A$</span> and <span class="math-container">$B$</span> be two events. In general, the probability that either <span class="math-container">$A$</span> or <span class="math-container">$B$</span> occurs is defined as</p>
  
  <p><span class="math-container">$$
  P(A \text{ or } B) = P(A) + P(B) - P(A \text{ and } B)
  $$</span></p>
  
  <p>If <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are disjoint, i.e. they cannot happen at the same time, then <span class="math-container">$P(A \text{ and } B) = 0$</span>, so the above formula becomes</p>
  
  <p><span class="math-container">$$
  P(A \text{ or } B) = P(A) + P(B)
  $$</span></p>
  
  <p>If the probability of one <strong>arbitrary</strong> hypothesis being consistent with <span class="math-container">$m$</span> training examples is <span class="math-container">$(1-\epsilon)^m$</span>, then, given the rule above and assuming that only one hypothesis is consistent with <span class="math-container">$m$</span> training examples, the probability of <strong>one or more</strong> (i.e. at least one) of the hypotheses being consistent with training examples is the sum of the probabilities, i.e. <span class="math-container">$k (1-\epsilon)^m$</span>.</p>
  
  <p>This probability can be bigger than one if more than one hypothesis is consistent with <span class="math-container">$m$</span> training examples. In that case, you have to take into account the probability that both hypotheses are consistent.</p>
  
  <p>See e.g. notes <a href="https://faculty.math.illinois.edu/~hildebr/408/408general1.pdf" rel="nofollow noreferrer">General Probability, I: Rules of probability</a> for more details about the union rule and other rules of probability.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-29T04:41:39.133Z
Answers.Text: is $k(1 - \epsilon)^m$ a lower bound on the probability that exactly one hypothesis out of k is consistent ?
Answers.UserDisplayName: calveeen
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-29T12:12:32.753Z
Answers.Text: @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$.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-29T04:26:42.723Z
Answers.LastActivityDate: 2020-04-29T23:17:25.600Z
Answers.LastEditDate: 2020-04-29T23:17:25.600Z
Answers.UserDisplayName: nbro
Body: <p>My question is actually related to the addition of probabilities. I am reading on computational learning theory from <a href="http://profsite.um.ac.ir/~monsefi/machine-learning/pdf/Machine-Learning-Tom-Mitchell.pdf" rel="nofollow noreferrer">Tom Mitchell's machine learning book</a>. </p>
  
  <p>In chapter 7, when proving the upper bound of probabilities for <span class="math-container">$\epsilon$</span> exhausted version space (theorem 7.1), it says that the probability that at least one hypothesis out of the <span class="math-container">$k$</span> hypotheses in the hypotheses space <span class="math-container">$|H|$</span> being consistent with <em>m</em> training examples is at most <span class="math-container">$k(1- \epsilon)^m$</span>. </p>
  
  <p>I understand that the probability of a hypothesis, <span class="math-container">$h$</span>, consistent with <em>m</em> training examples is <span class="math-container">$(1-\epsilon)^m$</span>. However, why is it possible to add the probabilities for <span class="math-container">$k$</span> hypotheses? And might the probability be greater than 1 in this case?</p>
  
Tags: <machine-learning><proofs><probability><computational-learning-theory><statistics>
Title: Why is probability that at least one hypothesis out of $k$ being consistent with $m$ training examples $k(1- \epsilon)^m$?
UserDisplayName: calveeen
ThreadText: # Why is probability that at least one hypothesis out of $k$ being consistent with $m$ training examples $k(1- \epsilon)^m$?
  
  (Asked by: username_0 on 2020-04-29)
  
  My question is actually related to the addition of probabilities. I am reading on computational learning theory from [Tom Mitchell's machine learning book](http://profsite.um.ac.ir/~monsefi/machine-learning/pdf/Machine-Learning-Tom-Mitchell.pdf).
  
  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?
  
  **Tags:** machine-learning, proofs, probability, computational-learning-theory, statistics
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-04-29. Score: 1 | Accepted answer
  
  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](https://faculty.math.illinois.edu/~hildebr/408/408general1.pdf) for more details about the union rule and other rules of probability.
  
  > **Comments:**
  > **username_0**: is $k(1 - \epsilon)^m$ a lower bound on the probability that exactly one hypothesis out of k is consistent ?  
  > **username_1**: @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$.  
  
  ---
  
  