0
$\begingroup$

I am reading a book about classification systems. They tell me that Bagging is a technique where "we perform sampling with replacement, building the classifier on each bootstrap sample. Each sample has probability $1-(1/N)^N$ of being selected."

What could they mean by this? Probably this is quite easy but somehow I do not get it. N is the number of classifier combinations (=samples), right? Why is the formula given above right? Why isn't the probability of a sample being selected simply $1/N$?

$\endgroup$
  • $\begingroup$ My notes said the chance for a sample to be selected at least once is $1-\left(1-\frac1N\right)^N$. $\endgroup$ – peterwhy Nov 15 '13 at 17:30
1
$\begingroup$
  1. The probability of being selected in some particular trial is $1/N$.
  2. The probability of not being selected in some particular trial is $1-1/N$.
  3. The probability of not being selected in any of $M$ trials is $(1-1/N)^M$, since the events are independent.
  4. The probability of being selected at least once in $M$ trials is $1-(1-1/N)^M$, since this event is complementary to 3.

If the number of trial is equal to the size $N$, you get $1-(1-1/N)^N$, as in peterwhy's comment. The formula $1-(1/N)^N$ gives the probability of not being selected at least once in $N$ trials. (Because $(1/N)^N$ is the probability of being selected in every trial.)

$\endgroup$

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.