问一道面试题 - 未名空间MITBBS历史存档

b*y2014-03-31 07:03

1 楼

假设有个链接，用户可以选择点击或者不点击，点击率就是p= C/N, C是点击的人，N是
总共看到这个link的人，N要多大才能对这个p有confidence？
我知道如果有两个概率p1,p2, 判断他们是不是significantly different，这个可以通
过假设 null hypothesis 是 p1=p2, 然后通过z score推导出N需要多大才有
confidence。但是上面这题只有一个value，要判断是不是有confidence怎么做？什么
是Null hypothesis?还是说有别的思路，不需要hypothesis testing？
望赐教！

w*a2014-03-31 07:03

2 楼

大概是 (9 / p - 9) 或 (9 / p + 9)
或干脆答 10 / p

【在 b********y 的大作中提到】

: 假设有个链接，用户可以选择点击或者不点击，点击率就是p= C/N, C是点击的人，N是
: 总共看到这个link的人，N要多大才能对这个p有confidence？
: 我知道如果有两个概率p1,p2, 判断他们是不是significantly different，这个可以通
: 过假设 null hypothesis 是 p1=p2, 然后通过z score推导出N需要多大才有
: confidence。但是上面这题只有一个value，要判断是不是有confidence怎么做？什么
: 是Null hypothesis?还是说有别的思路，不需要hypothesis testing？
: 望赐教！

B*n2014-03-31 07:03

3 楼

In order to have "confidence", you need to know how large the error you
would accept.

【在 b********y 的大作中提到】

: 假设有个链接，用户可以选择点击或者不点击，点击率就是p= C/N, C是点击的人，N是
: 总共看到这个link的人，N要多大才能对这个p有confidence？
: 我知道如果有两个概率p1,p2, 判断他们是不是significantly different，这个可以通
: 过假设 null hypothesis 是 p1=p2, 然后通过z score推导出N需要多大才有
: confidence。但是上面这题只有一个value，要判断是不是有confidence怎么做？什么
: 是Null hypothesis?还是说有别的思路，不需要hypothesis testing？
: 望赐教！

c*h2014-03-31 07:03

4 楼

正解！

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

: In order to have "confidence", you need to know how large the error you
: would accept.

w*a2014-03-31 07:03

5 楼

generally 3 sigma

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

: In order to have "confidence", you need to know how large the error you
: would accept.

c*z2014-03-31 07:03

6 楼

I think it is a question on sample size :)
Take a look at this:
www.unc.edu/~rls/s151-2010/class23.pdf
Three rules to take home:
1. when n > 30, the t-score approaches the z-score and we can use the theory
of normal distributions, on which all the sample size stuff is based;
2. since we are guessing standard error anyway, there is no precise minimal
sample size to talk about;
3. when there isn't enough sample, we can resample with replacement, i.e.
bootstrapping.
Conclusion: sample size doesn't matter that much, unless when you only have
a dozen records or so...
Hope that helps :)

h*32014-03-31 07:03

7 楼

model CTR啊？
现在比较流行的方法是Bayesian的方法。一个impression就是一个被奴隶(Bernoulli)
事件，用户点的概率就是p，不点的概率就是1-p。CTR就是参数p。假设你有a+b个观测
样本，其中a是点击了的样本个数，b是没有点的个数，那么p就是服从beta(a,b)的分布
。当这个beta(a,b)分布的variance越小，说明p的变化可能性就越小，那么你的
confidence就更大。

【在 b********y 的大作中提到】

: 假设有个链接，用户可以选择点击或者不点击，点击率就是p= C/N, C是点击的人，N是
: 总共看到这个link的人，N要多大才能对这个p有confidence？
: 我知道如果有两个概率p1,p2, 判断他们是不是significantly different，这个可以通
: 过假设 null hypothesis 是 p1=p2, 然后通过z score推导出N需要多大才有
: confidence。但是上面这题只有一个value，要判断是不是有confidence怎么做？什么
: 是Null hypothesis?还是说有别的思路，不需要hypothesis testing？
: 望赐教！

w*a2014-03-31 07:03

8 楼

这个才叫正解
前面的答案正是基于此
假定BINOMIAL OR POISSON 分布

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

: model CTR啊？
: 现在比较流行的方法是Bayesian的方法。一个impression就是一个被奴隶(Bernoulli)
: 事件，用户点的概率就是p，不点的概率就是1-p。CTR就是参数p。假设你有a+b个观测
: 样本，其中a是点击了的样本个数，b是没有点的个数，那么p就是服从beta(a,b)的分布
: 。当这个beta(a,b)分布的variance越小，说明p的变化可能性就越小，那么你的
: confidence就更大。

T*u2014-03-31 07:03

9 楼

我看到第一句就想多了，如果有相同的人人登录多次，有时候看到点了，有时候没点，
咋办？

T*u2014-03-31 07:03

10 楼

不知道hoeffding inequality可行否

【在 b********y 的大作中提到】

: 假设有个链接，用户可以选择点击或者不点击，点击率就是p= C/N, C是点击的人，N是
: 总共看到这个link的人，N要多大才能对这个p有confidence？
: 我知道如果有两个概率p1,p2, 判断他们是不是significantly different，这个可以通
: 过假设 null hypothesis 是 p1=p2, 然后通过z score推导出N需要多大才有
: confidence。但是上面这题只有一个value，要判断是不是有confidence怎么做？什么
: 是Null hypothesis?还是说有别的思路，不需要hypothesis testing？
: 望赐教！

b*y2014-03-31 07:03

11 楼

找了一个wiki 链接
http://en.wikipedia.org/wiki/Sample_size_determination
这里是用Normal distribution进行approximation，得到confidence interval 宽度,
作为error bound，对给定的error bound可以求出sample size.
这个问题如果用beta distribution 来近似，是不是要麻烦很多啊, 大部分情况是不是
用normal 来近似就可以了?

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

: model CTR啊？
: 现在比较流行的方法是Bayesian的方法。一个impression就是一个被奴隶(Bernoulli)
: 事件，用户点的概率就是p，不点的概率就是1-p。CTR就是参数p。假设你有a+b个观测
: 样本，其中a是点击了的样本个数，b是没有点的个数，那么p就是服从beta(a,b)的分布
: 。当这个beta(a,b)分布的variance越小，说明p的变化可能性就越小，那么你的
: confidence就更大。

D*u2014-03-31 07:03

12 楼

笼统的说用Posterior Beta 和 Normal都可以，但是一般的网页CTR都非常小，不要忘
记Normal approximate Binomial对 p是有要求的，不能太小。所以最好还是用
Posterior Beta 。
道理都是一样的，先确定一个error bound，10%, 5%，或者1%，然后，根据
Posterior Beta或者Normal的standard deviation的表达式计算n。
幸运的是，两个distribution的standard deviation的表达式都很简单，可是计算过程
中，都还需要额外的参数，那就是p0对于Normal，（a，b）对于Posterior Beta 。
所以你的link中的针对Normal的Wald方法，直接取p0=0.5了，这样就有一个很简单的式
子可以用了。这是个maximum variance 假设，但是，这个对于CTR来说偏差太大了，不
建议使用，当然还有一些更复杂方法的来correct Normal的这个issue，不过表达式都
很复杂。当然，你若问是否可以估计一个相对较小的p0,比如0.01，答案是这样就违反
Normal assumption了。
对于Posterior Beta 同样需要对beta的两个参数a,b有个估计，这个可以灵活的运用
，没有a/(a+b)不能过小的限制，而且即使使用flat的jeffrey prior, 效果也远好于
Normal的Wald方法。至于是否可以得到一个简单的表达式，我觉得取决于a,b的取值，
用jeffrey prior应该是有一个简单的表达式的。
所以，如果想简单，直接上Normal p0=0.5的Normal Wald，如果想效果好，用
Posterior Beta 再根据之前的经验选好a，b。