Regarding the sampling procedure in Adaboost algorithm

Question

The AdaBoost algorithm states that it is to train a classifier based on the training data according to a weight vector.

Assume the size of training data is N, the weight vector is of dimension N as well. I have three questions regarding this sampling procedure,

1) Will the size of sampled data be the same as the original data set? 2) What does the weight vector look like? If it is a distribution, then the sum of them has to be 1. Is that possible to have a weight vector with entries of integer number? 3) Generally, which algorithm can be used to sample a data set based on a given weight vector or a distribution?

Answer 1

There are two methods for training Adaboost. Either use the weight vector directly in the training of the weak learner, or use the weight vector to sample datapoints with replacement from the original data.

In the latter case the sampled dataset is the same size as the original dataset, and will contain some repeated datapoints. The weight vector is usually a distribution as it makes drawing the weighted sample easier, but any weight vector will work after normalisation. The simplest way to sample the new dataset is to make the weight vector a probability distribution, calculate its cumulative distribution function, then generate N random doubles in the range $(0,1]$. Then test to see what interval the random numbers are in.

for i = 1:N
    rnd = new Random(0.0,1.0)
    for j = 1:N
        if (cdf(j) < rnd)
            samplePoint(i) = dataPoint(j)
        end
    end
end

There are ways which aren't $O(n^2)$, but this is easier to understand.