2 ms·
Here's a sampling algorithm that will work, as long as the maximum weight isn't too much greater than the average weight: 1) Determine the maximum weight mw.
by mjtokelly 18y ago
Here's a sampling algorithm that will work, as long as the maximum weight isn't too much greater than the average weight:
1) Determine the maximum weight mw. (This is O(N) the first time, O(K) subsequent times.)
2) Repeat until an index i is accepted:
a) Generate a random pair (i, x), where i is a uniform integer over [1,N], and x is a uniform float over [0,mw].
b) Accept index i if weight(i) < x.
3) Return the accepted index i.
This gives you the desired distribution in time O(mw/aw) (maximum weight over average weight).
- mjtokelly 18y agoAn example of Rejection Sampling: http://en.wikipedia.org/wiki/Rejection_sampling http://en.wikipedia.org/wiki/Rejection_sampling
- bravura 18y agoRejection sampling is perhaps not a good option, because the assumption does not hold: "the maximum weight isn't too much greater than the average weight" In learning algorithms, the distribution of the weights can get piqued.