了解社区调整回答排序的背景可以看这篇专栏文章——
黄涛:社区如何对回答进行排序?你的一票很重要。社区使用的回答排序「威尔逊得分」算法表示为:
![]() 其中u为加权赞同票数,v为加权反对票数,![]()
为参数 这个算法中用来做排序依据的得分的更严谨的名称是「二项分布样本的威尔逊置信区间下界」。计算公式是在 1927 年由数学家 Edwin B. Wilson 发展得到的 [1],用来对二项分布进行参数估计。2009 年芝加哥的软件工程师 Evan Miller 提出 [2],可以用威尔逊置信区间的下界对具有正负双向投票的系统进行排序。在我最初通过煎蛋的介绍 [3] 了解到这个算法时,便立即被它的很多优良特性所吸引:
- 投票总数增加时,得分趋向于正向反馈占总反馈的比例,对于内容质量有较强的解释性。
- 在总票数较少(个位数投票)和极端参数(真实比例接近 0 或 100%)的情形下,结果也能具有较高的准确性。
- 置信区间大小可以通过参数控制。
- 虽然二项分布是离散模型,但是由于得分表达式关于正负反馈次数的函数是连续的,因此可以引入非整数的投票(加权投票),同时不改变算法性质。
- 得分的取值范围是 (0,1),与投票总数无关。因此可以间接地用来对不同问题下的回答做归一化的质量比较。
下面这两张图可以比较直观地显示威尔逊得分算法的几个重要特性。
![]() 为方便讨论,依次称左图中 up-vote, down-vote, score 对应的轴为 x,y,z 轴。右图为左图的等高线图。 左图的整体曲面形状,与通常理解中赞同票、反对票和回答质量的对应关系是相符的。固定反对票,赞同票越多得分越高;固定赞同票,反对越多得分越低;固定赞同与反对的比例,总票数越高得分越高。
总投票数较少时,回答如果获得投票,得分会快速增加,总票数越大增加速度越慢。体现为垂直 y 轴的平面截得的曲线斜率对 x 恒正且单调下降。同时,赞同数较高的回答,开始获得反对票时,得分会快速下降,总反对数越大下降速度越慢。垂直 x 轴的平面截得的曲线斜率对 y 恒负且单调上升。
对老版算法,对应函数 z = x - y,也不难画出上面两个图(这么简单的表达式,相信很多人闭上眼睛就已经把图画出来了)。老版算法的得分曲面实际为平面,因此各种截线都是平行直线(斜率为固定常数),右图等高线也是平行直线。
相对而言,新版算法对应的等高线图,等高线比老版更密集 [4],因此跨越等高线更容易。这也是新排序机制的上线说明中,我们说新算法能够做到对单次投票更加敏感的根本原因。
另一方面,函数曲面连续光滑,使得这个算法可以很好的处理浮点数投票,支持社区已有的用户话题权重机制。二者有机结合,让回答排序更符合真实的内容质量。
当然,使用威尔逊得分来决定排序也远非完善。不同的回答获得投票的能力不同,这一点受很多因素影响,包括作者的文风、内容是否属于专业领域等。这些差异目前还没有在算法中得到体现。
另一个问题是,算法在 x = 0 时函数取值收敛为 0,无法对赞同为 0 但有不同反对票数的回答进行排序。我们的处理方式是默认所有回答者对自己的回答投了一票赞同。这样不仅解决了这个问题,还能让回答者的权重参与到排序的计算中。
威尔逊得分是一个简单强大,但是价值还没有被充分发掘的算法。至今,世界范围内应用了这个算法的著名网站仍然寥寥无几 [5]。近几年开始见到一些应用较广的开源库支持威尔逊得分,关于它的讨论似乎也在逐渐增加 [6],还是很让人开心的。我也希望借此次社区排序算法升级,把这个算法介绍给更多国内的团队,希望能对大家有所助益。
注:
1. Binomial Proportion Confidence Interval - Wilson Score Interval - Wikipedia
2. How Not To Sort By Average Rating - Evan Miller
3. Reddit 的评论排序新算法 - 煎蛋
4. 新老算法的函数值域分别是 (0, 1) 和 ![]()
,不能直接比较,此处表述不严谨但不影响结论。
5. 目前我知道的包括 Reddit, Yelp 和 Digg,欢迎评论补充。
6. wilson-score - npm, Wilson score interval on corp.ling.stats, Visualising the Wilson score for ratings
说明:本回答成文于 2014 年 12 月 5 日,之后只有链接补充和错别字修改,没有修改过内容。 |