bagging vs. pasting in ensemble learning

Question

I am bit confused about two concepts.

From my understanding Bagging is when each data is replaced after each choice. so for example for each subset of data you pick one from population, replace it then pick one again, etc... and this is repeated for each subset of data.

But for pasting people say it is sampling without replacement however does that mean you can't have same data on any subset? I thought it picks one subset w/o replacement but when it replaces all data when picking another subset, no?

Answer 1

Actually I think that you are mostly correct, except that in my understanding "with/without replacement" applies only to selecting one subset, not across subsets. This means that if we have a training set of instances $T=\{t_1,..,t_N\}$:

• With bagging, a particular sample can contain duplicate instances, in other words it is not a subset of $T$ but a multiset where an instance $t_i$ may occur several times. Of course the probability to pick the same instance $t_i$ $n$ times decreases quickly when $n$ increases, depending on the size $N$.
• With pasting a sample is a subset of $T$ and cannot contain the same instance $t_i$ twice. However another sample is drawn again from the full set $T$, which means that it is possible for an instance to be selected in several different samples.

In theory, the size of a sample can be higher than $N$ with bagging but not with pasting.

Note that I'm referring to multiset for the sake of clarity but formally $T$ itself is not a set since in theory it may contain the same instance twice.