问个题　weighted random sampling - 未名空间MITBBS历史存档

问个题　weighted random sampling# JobHunting - 待字闺中

j*n2012-06-08 07:06

1 楼

１个ａｒｒａｙ里面每个数对应１个ｗｅｉｇｈｔ,比如［１,２,３］的　ｗｅｉｇｈ
ｔ　分别是［１０,２０,３０］,　叫你从［１,２,３］里面按照ｗｅｉｇｈｔ产生１
个随机数，　比如这里面，产生３的概率是产生１的概率的３倍。
简单的做法就是把这些ｗｅｉｇｈｔ加起来，从［１０,２０,３０］变成［１０，３０
，６０］，然后产生１个从［０，６０］的uniform随机数，看这个数是在哪个区间，
［０，１０］，［１０,３０］还是［３０,６０］　就知道应该返回１，２，３中间哪
个了。
问题是有没有做法可以不需要执行这个ｓｕｍ的过程，因为如果ａｒｒａｙ很大很大，
这种ｓｕｍ很可能就ｏｖｅｒｆｌｏｗ了。

h*e2012-06-08 07:06

2 楼

用double存sum不行吗？

【在 j*****n 的大作中提到】

: １个ａｒｒａｙ里面每个数对应１个ｗｅｉｇｈｔ,比如［１,２,３］的　ｗｅｉｇｈ
: ｔ　分别是［１０,２０,３０］,　叫你从［１,２,３］里面按照ｗｅｉｇｈｔ产生１
: 个随机数，　比如这里面，产生３的概率是产生１的概率的３倍。
: 简单的做法就是把这些ｗｅｉｇｈｔ加起来，从［１０,２０,３０］变成［１０，３０
: ，６０］，然后产生１个从［０，６０］的uniform随机数，看这个数是在哪个区间，
: ［０，１０］，［１０,３０］还是［３０,６０］　就知道应该返回１，２，３中间哪
: 个了。
: 问题是有没有做法可以不需要执行这个ｓｕｍ的过程，因为如果ａｒｒａｙ很大很大，
: 这种ｓｕｍ很可能就ｏｖｅｒｆｌｏｗ了。

l*a2012-06-08 07:06

3 楼

也overflow呢？

【在 h****e 的大作中提到】

: 用double存sum不行吗？

h*e2012-06-08 07:06

4 楼

那就用BigNum之类的。

【在 l*****a 的大作中提到】

: 也overflow呢？

k*g2012-06-08 07:06

5 楼

把数都放到int array，size of sum，O(1)即可，也不用search了
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite

X*K2012-06-08 07:06

6 楼

是个办法，不过sum都溢出了，这array得有多大。

j*n2012-06-08 07:06

7 楼

就是一些海量数据的玩意，我现在是把每个数都先scale down 一下，再加，会好一些
。搜了一下也没有什么好办法，都还是得加一加

g*s2012-06-08 07:06

8 楼

max_v = 0;
for i = 1 to n{
if (weight[i] > max_v) {
sum = sum * (max_v / weight[i]) ;
max_v = weight[i];
}
sum += weigh[i] / max_v;
if ( random(1) <= ( (weight[i]/max_v) / (sum) )
r = a[i];
}
return r;
max_v is alway the max value of weigh [0..i]
sum <= i

【在 j*****n 的大作中提到】

: １个ａｒｒａｙ里面每个数对应１个ｗｅｉｇｈｔ,比如［１,２,３］的　ｗｅｉｇｈ
: ｔ　分别是［１０,２０,３０］,　叫你从［１,２,３］里面按照ｗｅｉｇｈｔ产生１
: 个随机数，　比如这里面，产生３的概率是产生１的概率的３倍。
: 简单的做法就是把这些ｗｅｉｇｈｔ加起来，从［１０,２０,３０］变成［１０，３０
: ，６０］，然后产生１个从［０，６０］的uniform随机数，看这个数是在哪个区间，
: ［０，１０］，［１０,３０］还是［３０,６０］　就知道应该返回１，２，３中间哪
: 个了。
: 问题是有没有做法可以不需要执行这个ｓｕｍ的过程，因为如果ａｒｒａｙ很大很大，
: 这种ｓｕｍ很可能就ｏｖｅｒｆｌｏｗ了。

j*n2012-06-08 07:06

9 楼

先顶再看

l*n2012-06-08 07:06

10 楼

divided by sum to turn to [0,1] and then generate a [0,1] uniform

【在 j*****n 的大作中提到】

: １个ａｒｒａｙ里面每个数对应１个ｗｅｉｇｈｔ,比如［１,２,３］的　ｗｅｉｇｈ
: ｔ　分别是［１０,２０,３０］,　叫你从［１,２,３］里面按照ｗｅｉｇｈｔ产生１
: 个随机数，　比如这里面，产生３的概率是产生１的概率的３倍。
: 简单的做法就是把这些ｗｅｉｇｈｔ加起来，从［１０,２０,３０］变成［１０，３０
: ，６０］，然后产生１个从［０，６０］的uniform随机数，看这个数是在哪个区间，
: ［０，１０］，［１０,３０］还是［３０,６０］　就知道应该返回１，２，３中间哪
: 个了。
: 问题是有没有做法可以不需要执行这个ｓｕｍ的过程，因为如果ａｒｒａｙ很大很大，
: 这种ｓｕｍ很可能就ｏｖｅｒｆｌｏｗ了。

m*e2012-06-08 07:06

11 楼

如果数组大到让sum溢出，那么scale down也会underflow。
我想可以用Metropolis–Hastings，也就是选random pick一个数x1，再random pick一
个数x2,如果weight of x2大于weight of x1，改变状态到x1，否则以一定概率到x2。
After burning in like 10000 iterations, 后面产生的就是要的sample.
这不像是面试SDE的问题，楼主面的是什么职位可以告知么？

j*n2012-06-08 07:06

12 楼

M-H should work, but getting a good proposal distributon is not easy.
proving detailed balance is hard.
Just a bonus question for machine learning data scientist position.

【在 m*********e 的大作中提到】

: 如果数组大到让sum溢出，那么scale down也会underflow。
: 我想可以用Metropolis–Hastings，也就是选random pick一个数x1，再random pick一
: 个数x2,如果weight of x2大于weight of x1，改变状态到x1，否则以一定概率到x2。
: After burning in like 10000 iterations, 后面产生的就是要的sample.
: 这不像是面试SDE的问题，楼主面的是什么职位可以告知么？

g*s2012-06-08 07:06

13 楼

就是一道稍微改编的 weighted reservoir sampling algorithm.
始终记录到目前数字weight的最大值。然后用它scale。不能用sum进行scale。

【在 m*********e 的大作中提到】

: 如果数组大到让sum溢出，那么scale down也会underflow。
: 我想可以用Metropolis–Hastings，也就是选random pick一个数x1，再random pick一
: 个数x2,如果weight of x2大于weight of x1，改变状态到x1，否则以一定概率到x2。
: After burning in like 10000 iterations, 后面产生的就是要的sample.
: 这不像是面试SDE的问题，楼主面的是什么职位可以告知么？

j*n2012-06-08 07:06

14 楼

I agree, it is the best answer so far, in my mind.

【在 g***s 的大作中提到】

: 就是一道稍微改编的 weighted reservoir sampling algorithm.
: 始终记录到目前数字weight的最大值。然后用它scale。不能用sum进行scale。

m*e2012-06-08 07:06

15 楼

jet你是什么背景的？我也想找data scientist之类的职位，但是这种职位似乎不愿给
没有经验的fresh grad。可是找不到工作我又哪来的经验，在死循环中痛苦中。

Z*Z2012-06-08 07:06

16 楼

~~~~rrdw：这里是不是应该是<=?

【在 g***s 的大作中提到】

: max_v = 0;
: for i = 1 to n{
: if (weight[i] > max_v) {
: sum = sum * (max_v / weight[i]) ;
: max_v = weight[i];
: }
: sum += weigh[i] / max_v;
: if ( random(1) <= ( (weight[i]/max_v) / (sum) )
: r = a[i];
: }

g*s2012-06-08 07:06

17 楼

yes. typo.

【在 Z*****Z 的大作中提到】

:
: ~~~~rrdw：这里是不是应该是<=?
:

j*n2012-06-08 07:06

18 楼

１个ａｒｒａｙ里面每个数对应１个ｗｅｉｇｈｔ,比如［１,２,３］的　ｗｅｉｇｈ
ｔ　分别是［１０,２０,３０］,　叫你从［１,２,３］里面按照ｗｅｉｇｈｔ产生１
个随机数，　比如这里面，产生３的概率是产生１的概率的３倍。
简单的做法就是把这些ｗｅｉｇｈｔ加起来，从［１０,２０,３０］变成［１０，３０
，６０］，然后产生１个从［０，６０］的uniform随机数，看这个数是在哪个区间，
［０，１０］，［１０,３０］还是［３０,６０］　就知道应该返回１，２，３中间哪
个了。
问题是有没有做法可以不需要执行这个ｓｕｍ的过程，因为如果ａｒｒａｙ很大很大，
这种ｓｕｍ很可能就ｏｖｅｒｆｌｏｗ了。

h*e2012-06-08 07:06

19 楼

用double存sum不行吗？

【在 j*****n 的大作中提到】

: １个ａｒｒａｙ里面每个数对应１个ｗｅｉｇｈｔ,比如［１,２,３］的　ｗｅｉｇｈ
: ｔ　分别是［１０,２０,３０］,　叫你从［１,２,３］里面按照ｗｅｉｇｈｔ产生１
: 个随机数，　比如这里面，产生３的概率是产生１的概率的３倍。
: 简单的做法就是把这些ｗｅｉｇｈｔ加起来，从［１０,２０,３０］变成［１０，３０
: ，６０］，然后产生１个从［０，６０］的uniform随机数，看这个数是在哪个区间，
: ［０，１０］，［１０,３０］还是［３０,６０］　就知道应该返回１，２，３中间哪
: 个了。
: 问题是有没有做法可以不需要执行这个ｓｕｍ的过程，因为如果ａｒｒａｙ很大很大，
: 这种ｓｕｍ很可能就ｏｖｅｒｆｌｏｗ了。

l*a2012-06-08 07:06

20 楼

也overflow呢？

【在 h****e 的大作中提到】

: 用double存sum不行吗？

h*e2012-06-08 07:06

21 楼

那就用BigNum之类的。

【在 l*****a 的大作中提到】

: 也overflow呢？

k*g2012-06-08 07:06

22 楼

把数都放到int array，size of sum，O(1)即可，也不用search了
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite

X*K2012-06-08 07:06

23 楼

是个办法，不过sum都溢出了，这array得有多大。

j*n2012-06-08 07:06

24 楼

就是一些海量数据的玩意，我现在是把每个数都先scale down 一下，再加，会好一些
。搜了一下也没有什么好办法，都还是得加一加

g*s2012-06-08 07:06

25 楼

max_v = 0;
for i = 1 to n{
if (weight[i] > max_v) {
sum = sum * (max_v / weight[i]) ;
max_v = weight[i];
}
sum += weigh[i] / max_v;
if ( random(1) <= ( (weight[i]/max_v) / (sum) )
r = a[i];
}
return r;
max_v is alway the max value of weigh [0..i]
sum <= i

【在 j*****n 的大作中提到】

: １个ａｒｒａｙ里面每个数对应１个ｗｅｉｇｈｔ,比如［１,２,３］的　ｗｅｉｇｈ
: ｔ　分别是［１０,２０,３０］,　叫你从［１,２,３］里面按照ｗｅｉｇｈｔ产生１
: 个随机数，　比如这里面，产生３的概率是产生１的概率的３倍。
: 简单的做法就是把这些ｗｅｉｇｈｔ加起来，从［１０,２０,３０］变成［１０，３０
: ，６０］，然后产生１个从［０，６０］的uniform随机数，看这个数是在哪个区间，
: ［０，１０］，［１０,３０］还是［３０,６０］　就知道应该返回１，２，３中间哪
: 个了。
: 问题是有没有做法可以不需要执行这个ｓｕｍ的过程，因为如果ａｒｒａｙ很大很大，
: 这种ｓｕｍ很可能就ｏｖｅｒｆｌｏｗ了。

j*n2012-06-08 07:06

26 楼

先顶再看

l*n2012-06-08 07:06

27 楼

divided by sum to turn to [0,1] and then generate a [0,1] uniform

【在 j*****n 的大作中提到】

: １个ａｒｒａｙ里面每个数对应１个ｗｅｉｇｈｔ,比如［１,２,３］的　ｗｅｉｇｈ
: ｔ　分别是［１０,２０,３０］,　叫你从［１,２,３］里面按照ｗｅｉｇｈｔ产生１
: 个随机数，　比如这里面，产生３的概率是产生１的概率的３倍。
: 简单的做法就是把这些ｗｅｉｇｈｔ加起来，从［１０,２０,３０］变成［１０，３０
: ，６０］，然后产生１个从［０，６０］的uniform随机数，看这个数是在哪个区间，
: ［０，１０］，［１０,３０］还是［３０,６０］　就知道应该返回１，２，３中间哪
: 个了。
: 问题是有没有做法可以不需要执行这个ｓｕｍ的过程，因为如果ａｒｒａｙ很大很大，
: 这种ｓｕｍ很可能就ｏｖｅｒｆｌｏｗ了。

m*e2012-06-08 07:06

28 楼

如果数组大到让sum溢出，那么scale down也会underflow。
我想可以用Metropolis–Hastings，也就是选random pick一个数x1，再random pick一
个数x2,如果weight of x2大于weight of x1，改变状态到x1，否则以一定概率到x2。
After burning in like 10000 iterations, 后面产生的就是要的sample.
这不像是面试SDE的问题，楼主面的是什么职位可以告知么？

j*n2012-06-08 07:06

29 楼

M-H should work, but getting a good proposal distributon is not easy.
proving detailed balance is hard.
Just a bonus question for machine learning data scientist position.

【在 m*********e 的大作中提到】

: 如果数组大到让sum溢出，那么scale down也会underflow。
: 我想可以用Metropolis–Hastings，也就是选random pick一个数x1，再random pick一
: 个数x2,如果weight of x2大于weight of x1，改变状态到x1，否则以一定概率到x2。
: After burning in like 10000 iterations, 后面产生的就是要的sample.
: 这不像是面试SDE的问题，楼主面的是什么职位可以告知么？

g*s2012-06-08 07:06

30 楼

就是一道稍微改编的 weighted reservoir sampling algorithm.
始终记录到目前数字weight的最大值。然后用它scale。不能用sum进行scale。

【在 m*********e 的大作中提到】

: 如果数组大到让sum溢出，那么scale down也会underflow。
: 我想可以用Metropolis–Hastings，也就是选random pick一个数x1，再random pick一
: 个数x2,如果weight of x2大于weight of x1，改变状态到x1，否则以一定概率到x2。
: After burning in like 10000 iterations, 后面产生的就是要的sample.
: 这不像是面试SDE的问题，楼主面的是什么职位可以告知么？

j*n2012-06-08 07:06

31 楼

I agree, it is the best answer so far, in my mind.

【在 g***s 的大作中提到】

: 就是一道稍微改编的 weighted reservoir sampling algorithm.
: 始终记录到目前数字weight的最大值。然后用它scale。不能用sum进行scale。

m*e2012-06-08 07:06

32 楼

jet你是什么背景的？我也想找data scientist之类的职位，但是这种职位似乎不愿给
没有经验的fresh grad。可是找不到工作我又哪来的经验，在死循环中痛苦中。

Z*Z2012-06-08 07:06

33 楼

~~~~rrdw：这里是不是应该是<=?

【在 g***s 的大作中提到】

: max_v = 0;
: for i = 1 to n{
: if (weight[i] > max_v) {
: sum = sum * (max_v / weight[i]) ;
: max_v = weight[i];
: }
: sum += weigh[i] / max_v;
: if ( random(1) <= ( (weight[i]/max_v) / (sum) )
: r = a[i];
: }

g*s2012-06-08 07:06

34 楼

yes. typo.

【在 Z*****Z 的大作中提到】

:
: ~~~~rrdw：这里是不是应该是<=?
:

b*r2012-06-08 07:06

35 楼

the idea is great, but just picking bone from egg, why sum<=1? do i miss
anything?

【在 g***s 的大作中提到】

: max_v = 0;
: for i = 1 to n{
: if (weight[i] > max_v) {
: sum = sum * (max_v / weight[i]) ;
: max_v = weight[i];
: }
: sum += weigh[i] / max_v;
: if ( random(1) <= ( (weight[i]/max_v) / (sum) )
: r = a[i];
: }