算法与计算机科学evanmiller.org编辑精选
如何不按平均评分排序
How Not To Sort By Average Rating
2009 — 2024，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。作者给出基于二项分布置信区间下界的排序方法（Wilson score lower bound），在评价少时压低分数、评价多时逐步接近真实好评率，并附有公式和代码。
为什么经久不衰：它用一个小而可实现的统计修正解决了评分排序中的小样本和刷分问题，公式可直接落地，因此十多年后仍是产品与工程讨论中的常引经典。
HN 评论精选
用 Beta 分布直观解释公式，并指出它只是置信区间的粗略近似。
很多人抱怨数学太复杂，但这不该那么难懂。假设存在一个恒定的底层概率 p，表示随机用户会给某事物正面评价；如果观察到 4 个正面和 5 个负面评价，那么给定这些投票后 p 的可能取值有一个概率分布（Beta 分布），形如 p^4(1-p)^5。观测越多，这条似然曲线就越尖锐。文章里那个古怪的公式，就是对这条曲线 95% 置信区间的一个近似；这个近似不太好，因为曲线是偏斜的（可以试试 10/50），而且它假设均值正好在置信区间中点。正确计算需要反转一个麻烦的积分，即不完全 Beta 函数。
a1k0n查看英文原文
There are a lot of comments complaining about how complicated the math is. This shouldn't be all that hard to understand. The assumption is that there's some constant p underlying probability that a random person will rate a given thing positively. If we observe, for instance, 4 positive and 5 negative reviews or votes, there's a probability distribution (known as a Beta distribution) which tells us what the possible values of p are given the votes we observe: p^4 (1-p)^5. graph: https://www.google.com/search?q=x%5E4+(1-x)%5E5%20from%200%20to%201 Now if we observe 40 and 50, respectively, the curve looks like this: https://www.google.com/search?q=exp(20+%2B+40+log(x)+%2B+50+log(1-x))%20from%200%20to%201 (I had to do it in the log domain because Google's grapher underflows otherwise -- the 20 is just to make the numbers big enough to graph. The more correct thing involves gamma functions and that just gets in the way right now) The more you observe, the more sharply peaked the likelihood function is. The funky equation in the article is an approximation to the confidence interval of that graph -- 95% of the probability mass is said to be within those bounds. It's not a great approximation, for one because the graph is skewed (try it with 10/50) and it assumes that the mean is exactly in the middle of the confidence interval. The correct computation involves the inversion of a messy integral called the incomplete beta function. Scipy has a package which includes betaincinv which solves this more exactly: >>> import scipy.special >>> scipy.special.betaincinv(5,6, [0.025, 0.975]) array([ 0.18708603, 0.73762192]) would be the 95% confidence interval for 4 positive and 5 negative votes; >>> scipy.special.betaincinv(41,51, [0.025, 0.975]) array([ 0.34599562, 0.54754792]) for 40 and 50, respectively. [edit: apologies, I had to run and get ready for work -- I didn't really have time to make this very comprehensible; but i just now fixed a bug in my confidence interval stuff above]
作者回应批评，强调算法追求单边（宁可漏排不可错排），并指出多级评分并不直接。
原文作者在此。对学术型读者，这篇论文批评了该方法（链接略）。当然，我认为作者们没抓住这个算法的要点，因为我基本想要一个单边系统：假阴性可以接受，假阳性很糟。另外，若处理多于两种结果，可参考多项置信区间（链接略）。应用到五星系统并不直接，因为我不清楚星级之间如何关联：是线性尺度、离散桶，还是 Tukey 的 froots and flogs？我不确定。顺便说，我很快会推出一个实现该算法的 Mac 统计应用。
EvanMiller查看英文原文
Original author here. For the academically inclined, there is a critique of this approach in this paper: http://www.dcs.bbk.ac.uk/~dell/publications/dellzhang_ictir2011.pdf Of course, I think the authors miss the point of the algorithm, since I basically wanted a system that is one-sided (i.e. false negatives are OK but false positives are bad). Also, if you deal with more than two outcomes you might be interested in multinomial confidence intervals, described here: http://www.math.wsu.edu/faculty/genz/papers/mvnsing/node8.html The application to 5-star systems is not straightforward, since it's not clear to me how stars relate to each other. Is it a linear scale? Are they discrete buckets? Or maybe we want to use Tukey's froots and flogs? I'm not sure. By the way, I'm coming out with a stats app for Mac soon that implements this algorithm and much more. Drop me your email address if interested: http://wizard.evanmiller.org/
提出用 Dirichlet-多项共轭先验做贝叶斯排序，并用 alpha 控制小样本敏感度。
我同意文章的精神，但这类情况下用贝叶斯处理在概念上清楚得多。假设评分由一个稳定的随机过程产生，底层分布是多项分布（暂时忽略评分的有序性），并使用 Dirichlet 共轭先验。这样就得到某条目未来评分的后验分布。后验的好处是，可以按“随机比较时一个条目被评为高于另一个的概率”来排序。调整 Dirichlet 先验的 alpha 大小，就能调节对小样本的敏感度：alpha 小，看到评分后后验变化快；alpha 大，则需要大量证据。多项模型加共轭 Dirichlet 先验的好处是数学非常简单。
NathanRice查看英文原文
While I agree with the spirit of the article, this is one of those cases where a Bayesian treatment is conceptually much clearer. Assume that ratings are being generated by a stable stochastic process where the underlying distribution is multinomial (ignoring the ordinal character of ratings, for the time being) and use a dirichlet conjugate prior. This gives you a posterior distribution over new ratings for an item. The benefit of a posterior here is that it lets you rank items by thinking in terms of the probability that the viewer would rank one item higher than another at random. By adjusting the magnitude of the alpha parameter to the dirichlet prior, you adjust your sensitivity to small numbers of observations. A small initial alpha will lead to rapid changes in the posterior upon observing ratings, whereas a large alpha requires a significant body of evidence. The best part of the multinomial model with conjugate dirichlet prior is that the math is REALLY simple. The normalizing constant for the dirichlet distribution looks scary when stated in terms of the gamma function, but given this is the discrete case, just pretend everywhere you see the gamma(x), it is replaced with (x - 1)! and you will be ok. Let me know if you would like to learn more, I would be happy to help.
平均分激励恶意打低分，中位数更诚实；提出能否兼得。
平均值（即便采用文中的方法）仍然不具备博弈论意义上的“诚实”。例如，某物有 100 条评价、平均 4 星，而一个认为其真实评分应为 3 星的评价者，会有动机给它打 1 星，因为这样能把平均分拉向自己期望的结果。看评分分布会发现，很多人确实这么干。只要平局是任意打破而不是取平均，中位数评分在这个意义上就是“诚实”的。数学挑战：有没有办法把文中提到的理想性质和诚实性结合起来？我猜有，但还没试过。
paulgb查看英文原文
Averages (even with the post's approach) still have the problem of not being "honest" in the game theory sense. For example, if something is rated 4 stars with 100 reviews, a reviewer who believes its true rating should be 3 stars is motivated to give it 1 star because that will move the average rating closer to his desired outcome. A look at rating distributions shows that this is in fact how many people behave. Median ratings are "honest" in this sense, as long as ties are broken arbitrarily rather than by averaging. Math challenge: is there a way of combining the desirable properties mentioned in the post with the property of honesty? I suspect there is but I haven't tried it.
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选游戏中的六边形网格
Hexagonal grids for games
Red Blob Games 的六边形网格教程，系统讲解游戏中六边形网格的坐标系（轴向、立方坐标等）、邻居计算、与像素坐标互转、视野与寻路等常见问题。
算法与计算机科学上首页 5 次 · 2013–2020redblobgames.com编辑精选