问答社区的回答排序算法(一)

正好研究生的研究方向是问答社区的专家发现,所以,看过很多关于专家发现的 paper 以及一些工业界实践的经验。一直没有机会好好总结一下,借此机会梳理一下。问答社区的专家用户的发现有助于问题的顺利解决,并且也有助于提高问答社区的用户体验,有利于问答社区的长期发展。

现有的专家发现方法主要分为两种,一种是基于用户投票,另一种是基于用户之间的社交网络,本文将先介绍前一种。

基于用户投票的排序算法

顾名思义,就是利用用户的反馈,即投票数(又细分为赞成和反对)来对答案进行排名。下面介绍三种方法,分别被 Urban DictionaryAmazon知乎 采用。

得分 = 赞成票 - 反对票

假定有两个项目,项目 A 是 30 张赞成票,10 张反对票,项目 B 是 200 张赞成票,150 张反对票。如果按照上面的公式,B会排在前面,因为它的得分(200 - 150 = 50)高于 A(30 - 10 = 20)。但是实际上,B 的好评率只有 57%(200 / 350),而 A 为 75%(30 / 40),所以正确的结果应该是A排在前面。

Urban Dictionary 就是这种错误算法的实例。

得分 = 赞成票 / 总票数

如果总票数很大,这种算法其实是对的。问题出在如果总票数很少,这时就会出错。假定 A 有 2 张赞成票、0 张反对票,B 有 100 张赞成票、1 张反对票。这种算法会使得 A 排在 B 前面。这显然错误。

Amazon 便采用的是这种做法。

威尔逊得分

威尔逊得分的思想是,如果把一个回答展示给很多人看并让他们投票,内容质量不同的回答会得到不同比例的赞同和反对票数,最终得到一个反映内容质量的得分。当投票的人比较少时,可以根据已经获得的票数估计这个回答的质量得分,投票的人越多则估计结果越接近真实得分。

如果新一个回答获得了 1 票赞同 0 票反对,也就是说参与投票的用户 100% 都选了赞同,但是因为数量太少,所以得分也不会太高。如果一小段时间后这个回答获得了 20 次赞同 1 次反对,那么基于新算法,我们就有较强的信心把它排在另一个有 50 次赞同 20 次反对的回答前面。原因是我们预测当这个回答同样获得 50 次赞同时,它获得的反对数应该会小于 20。威尔逊得分算法最好的特性就是,即使前一步我们错了,现在这个新回答排到了前面,获得了更多展示,在它得到更多投票后,算法便会自我修正,基于更多的投票数据更准确地计算得分,从而让排序最终能够真实地反映内容的质量。

它有着很多优良特性:

  1. 投票总数趋向于正无穷时,得分也趋向正反馈占总反馈的比例,对于内容质量的解释下很强。
  2. 在数据比较少的情况,总票数较少和极端参数的情况下,结果也能保持很好的鲁棒性。
  3. 置信区间大学可以通过参数保证。
  4. 虽然二项分布是离散类型,但是由于得分表达式关于正负反馈次数的函数是连续的,因此可以引入非整数的投票(加权投票),同时不改变算法性质。
  5. 得分的取值范围是(0,1),与投票总数无关,间接的做了归一化。

威尔逊得分的计算公式如下:

$$score = \frac{\phi + \frac{z^2}{2n} - z * \sqrt{(\frac{\phi\ast (1 - \phi)}{n} + \frac{z^2}{4n^2}}}{(1 + \frac{z^2}{n})}$$

\(\phi\) 表示样本的赞成票比例,\(n\) 表示样本的大小,\(z_{1- \alpha/2}\) 表示对应某个置信水平的 \(z\) 统计量,这是一个常数,可以通过查表或统计软件包得到。一般情况下,在 95% 的置信水平下,z 统计量的值为 1.96。

威尔逊得分计算过程 (JavaScript 版本):

n = Up + Down
if (n==0) {
score = 0;
}
else {
z = 1.96
phat = Up / n
score = (phat + z*z/(2*n) - z * Math.sqrt((phat*(1-phat)+z*z/(4*n))/n))/(1+z*z/n);
}

可以看到,当 \(n\) 的值足够大时,这个下限值会趋向。如果 \(n\) 非常小(投票人很少),这个下限值会大大小于。实际上,起到了降低 “赞成票比例” 的作用,使得该项目的得分变小、排名下降。

知乎采用的就是这种方法,下面摘一段知乎产品总监对这个算法评价的一段话:

  因此未来我们会看到更多新创作的优质内容,快速获得靠前的排序,低质内容则会长期
保持在底部。细心的你可能也想到了,并不是所有的回答最终都会获得很多投票,大体上
获得投票总数较多的回答仍然会排在投票较少的回答前面。

需要提一下,这个威尔逊算法在 x = 0 时函数取值收敛为 0,无法对赞同为 0,但反对票数不一样的回答进行排序。为了方便,知乎默认所有回答者对自己的投票投了一票赞同。这样不仅解决了这个问题,而且让回答者也将自身权重参与到排序的计算中。

参考资料