持续创作，加速成长！这是我参与「日新计划 10 月更文挑战」的第6天，点击检查活动详情

在第一篇打分体系闲谈1 – 时间衰减咱们聊了两种相对简略的打分算法Hacker News和Reddit Hot Formula，也提出了几个这两种算法或许存在的问题，这一篇咱们就其间的一两个问题进一步讨论：

  • 怎么归纳浏览量和点赞量对文章进行打分[期望功效函数->点赞率]
  • 怎么处理浏览量较小时，点赞率不相信的问题[wald Interval -> wilson]

Reddit Hot Formula？ 期望功效函数！

让咱们从上一篇咱们提到的Reddit Hot Formula来说起，抛开文章质量的惩罚项，只考虑点赞拍砖的低配版打分公式是

score=sign(U−D)∗log10∣U−D∣+seconds/4500score = sign(U-D)* log_{10}{|U-D|} + seconds/4500

Evan从经济学期望功效这个新颖的视点试图对上述公式进行复现，几个根本假定包含：

  • 用户改写界面的行为∼Poisson() \sim Poisson(\lambda)
  • 每次改写看到新/老文章的概率是q/(1−q)q/(1-q), 喜爱/不喜爱的概率是p/(1−p)p/(1-p)
  • 老文章功效为0，喜爱的新文章功效为1， 不喜爱的新文章功效为-1

上述概率p,q能够用已有数据进行估量：

  • 在没有任何和文章相关的信息时，喜爱不喜爱的概率是相同的p=12p=\frac{1}{2}, 当咱们获得一篇文章的点赞量和拍砖数时咱们能够用点赞率对概率进行更新得到p=U+1U+D+2p = \frac{U+1}{U+D+2}

  • 概率q是一篇t时间前发布的文章没有被作者读过的概率,换言之便是用户在t时间内没有改写界面的概率q=p(N=0)=p(x>t)=exp(−t)q = p(N_\lambda=0)= p(x>t)= exp(-\lambda t)

综上咱们能够得到对数功效的表达式：

Utility=p∗q−(1−p)∗q=exp(−t)∗(U+1U+D+2−D+1U+D+2)=exp(−t)∗(U−DU+D+2)log(Utility)=log(U−D)−log(U+D+2)−tUtility = p * q -(1-p) * q \\ = exp(-\lambda t ) *(\frac{U+1}{U+D+2} – \frac{D+1}{U+D+2}) \\ = exp(-\lambda t ) *(\frac{U-D}{U+D+2}) \\ log(Utility ) = log(U-D) – log(U+D+2) – \lambda t \\

和上述Reddit Hot Formula比照咱们会发现当U>D的时分，两个表达式是根本共同的，最大的不同是Reddit没有期望功效的第二个对数项log(U+D+2)log(U+D+2)。换言之Reddit只考虑点赞量而没有考虑点赞量对应的基数，这个基数能够是点赞+拍砖或者是用户的浏览量。

咱们举个比如你就会了解这种打分或许存在的问题，咱们拿Stack overflow来举个比如，下图的两个问题获得了差不多的投票57 vs. 53，可是会发现第一个问题比第二个问题多一倍的浏览量4k vs. 2K, 所以从投票率来看反而是第二个问题的投票率更高。

打分排序系统漫谈2 - 点赞量？点赞率?! 置信区间！

点估量？区间估量！

这样看似乎咱们应该使用点赞（投票）率而非简略的点赞量来对文章进行打分，可是点赞坦率的永远可信么？ 咱们再看一个比如

打分排序系统漫谈2 - 点赞量？点赞率?! 置信区间！
打分排序系统漫谈2 - 点赞量？点赞率?! 置信区间！

单从投票率来看，第一个问题投票率高达50%可是浏览量只要2 ，而第二个问题投票率较低可是浏览量很高。假如但从投票率来看，似乎第一个问题排名更高，可是直觉告诉咱们第二个问题应该排名更靠前。这就触及统计学中点估量的相信度问题。

让咱们来把用户点赞这个行为抽象一下，咱们假定每一个用户要么点赞要么拍砖，每一个用户之间的行为之间独立，所以每个用户∼Bernoulli(p)\sim Bernoulli(p), 其间p是点赞的概率。当样本量足够大的时分，依据大数规律用户点赞的频率会趋于点赞率lim⁡x→∞P(∣nxn−p∣<)=1\lim\limits_{x \to \infty} P(|\frac{n_x}{n} – p| < \epsilon)=1

可是当用户量不行，样本比较小的时分，计算的点赞率会和整体概率会存在较大的误差。一种处理方法便是使用区间估量而非点估量，咱们给出点赞率估量的下鸿沟而非点赞率的估量值。

最常用的二项分布的区间估量由近似正态分布给出。依据大数规律，参数为n,p的二项分布在n→∞n \to \infty的时分 p−pp(1−p)/n∼N(0,1)\frac{\hat{p}-p}{\sqrt{p(1-p)/n}} \sim N(0,1)。依据正态分布的相信区间咱们会得到二项分布的近似区间估量如下

p(∣p−pp(1−p)/n∣<z/2)=1−where 相信度是0.95，=0.05p是依据每个用户点赞行为给出的点赞率的估量n是样本量，能够是用户点赞+拍砖的总和，或者是用户浏览量p是整体的点赞率是咱们期望得到的估量p( | \frac{\hat{p}-p}{\sqrt{p(1-p)/n}} | < z_{\alpha/2}) = 1- \alpha \\ where \, 相信度是0.95，\alpha = 0.05 \\ \hat{p}是依据每个用户点赞行为给出的点赞率的估量\\ n是样本量，能够是用户点赞+拍砖的总和，或者是用户浏览量\\ p是整体的点赞率是咱们期望得到的估量\\

Wald Interval 对上述近似区间用样本估量p\hat{p}代替整体p，给出了最常用的二项分布相信区间：

p−,p+=pz/2p(1−p)/np_-,p_+ = \hat{p} \pm z_{\alpha/2}\sqrt{\hat{p}(1-\hat{p})/n}

wald相信区间适用大多数状况，可是鄙人面三个状况下会存在问题：

  • 样本不行，n太小时，p\hat{p}和整体的p比较会误差较大
  • p→0p \to 0 or p→1p \to 1会导致方差趋于0，使得相信区间明显偏窄
  • p=0，1p =0，1 相信区间长度为0

而在估量文章点赞率这个场景下咱们不可避免的会碰到上述3个状况，在这种状况咱们往往会使用更加杂乱的相信区间算法。来来来下面让咱们说说其间一种高配版的相信区间- Wilson Interval

Wilson Score

Wilson对Walt相信区间做了修正, Wilson相信区间的上下界如下：

p−,p+=p+z/222n1+z/22nz/2p(1−p)n+z/224n21+z/22np_-,p_+ = \frac{\hat{p} + \frac{z^2_{\alpha/2}}{2n}} {1 +\frac{z^2_{\alpha/2}}{n}} \pm z_{\alpha/2}\frac{\sqrt{\frac{\hat{p}(1-\hat{p})}{n} + \frac{z^2_{\alpha/2}}{4n^2} }}{1 +\frac{z^2_{\alpha/2}}{n}}

看着老杂乱了，让咱们来拆解一下你就会发现原理蛮好了解的。先说说对整体均值的估量，wilson对p\hat{p}进行了如下调整：

p→p~=p+z/222n1+z/22n\hat{p} \to \tilde{p} = \frac{\hat{p} + \frac{z^2_{\alpha/2}}{2n}} {1 +\frac{z^2_{\alpha/2}}{n}}

当样本量足够大Wilson和Walt对整体均值的估量会趋于共同。当样本量很小的时分, 不同于walt,wilson给样本估量加了一个12\frac{1}{2}的贝叶斯前置概率(点赞和拍砖的概率各是50%),然后不断用新增样本来对这个前置概率进行调整。从而避免样本较小的时分样本估量过度偏离整体的问题。

whenlim⁡n→∞p~→pwhenlim⁡n→0p~→12when \lim\limits_{n \to \infty} \tilde{p} \to \hat{p} \\ when \lim\limits_{n \to 0} \tilde{p} \to \frac{1}{2} \\

方差部分也做了相同的处理, 当样本足够大的时分wilson和walt对整体方差的估量会趋于共同，可是当样本小的时分和上述样本均值的处理方法相同，会趋于贝叶斯前置概率对应的方差p→12⇒p(1−p)→14\hat{p} \to \frac{1}{2} \Rightarrow \hat{p}(1-\hat{p}) \to \frac{1}{4}

p(1−p)n→p(1−p)n+z/224n21+z/22n\sqrt{\frac{\hat{p}(1-\hat{p})}{n}} \to \frac{\sqrt{\frac{\hat{p}(1-\hat{p})}{n} + \frac{z^2_{\alpha/2}}{4n^2} }}{1 +\frac{z^2_{\alpha/2}}{n}}

下面两张图片很直观的给出了不同样本数量(n=10 vs.100)下，样本均值的估量所对应的相信区间的长度（方差估量）。当样本大的时分Wilson和Wald简直相同，当样本小的时分，随着p趋于0 or 1,Wilson相信区间会明显宽于Walt区间。

打分排序系统漫谈2 - 点赞量？点赞率?! 置信区间！
打分排序系统漫谈2 - 点赞量？点赞率?! 置信区间！

而Wilson打分便是取Wilson相信区间的下界:

score=p+z/222n1+z/22n−z/2p(1−p)n+z/224n21+z/22nscore= \frac{\hat{p} + \frac{z^2_{\alpha/2}}{2n}} {1 +\frac{z^2_{\alpha/2}}{n}} – z_{\alpha/2} \frac{\sqrt{\frac{\hat{p}(1-\hat{p})}{n} + \frac{z^2_{\alpha/2}}{4n^2} }}{1 +\frac{z^2_{\alpha/2}}{n}}

Wilson打分方式有几个很好的特性：

  • 点赞率(p)相同，浏览量(n)越高得分越高
  • 点赞率趋于0时, score = 0
  • 点赞率趋于1时, score = 11+z/22/n\frac{1}{1+z^2_{\alpha/2}/n}, 浏览量越高，得分越挨近1，反之浏览量越小，得分越低，这样会对小样本点赞率高的问题进行调整
  • 相信度越高，z/2z_{\alpha/2}越大，点赞率越不重要，而样本量n越重要

鄙人一篇文章咱们持续聊聊另一种更灵活的处理小样本打分的方法- 贝叶斯更新

Reference

  1. www.ucl.ac.uk/english-usa…
  2. www.ruanyifeng.com/blog/2012/0…
  3. www.evanmiller.org/how-not-to-…
  4. 二项分布参数的区间估量,朱永生《粒子物理数据剖析根底与前沿》研讨会