如何使用众包分类对一百万张图片进行排名

86

我想通过制作一个游戏来对一组风景图片进行排名,让站点访问者评分,以找出人们最喜欢哪些图片。

有什么好的方法吗?

  • 热门或不热门风格?即显示单个图像,要求用户给其排名1-10。在我的看法中,这允许我计算平均分数,我只需要确保在所有图像上获得投票的数量平均分布。实现相当简单。
  • 选择A或B?即显示两个图像,要求用户选择更好的一个。这很吸引人,因为它没有数字排名,只是一个比较。但我该怎么实现呢?我的第一个想法是将其作为快速排序来完成,比较操作由人类提供,完成后,只需无限重复排序。

你会如何做呢?

如果你需要数字,我正在谈论的是拥有一百万张图片的网站,每天有20,000次访问。我想象可能只有一小部分人会玩这个游戏,为了方便起见,假设我每天可以生成2,000个人工排序操作!这是一个非营利性网站,好奇心旺盛的人可以通过我的个人资料找到它:)


1
我写了一个使用GAE的玩具应用程序,类似于http://rank.appspot.com/。它使用每个项目的动量概念,我怀疑它会退化成ELO的变体,尽管我是独立开发的。很高兴分享Python源代码。 - freespace
@freespace 我很想看看你算法的Python源代码。 - akaihola
也许在这个项目中,你可以尝试建立一个神经网络(当然只是为了好玩),并使用“选择A或B”输入来训练网络。也许经过大量的训练,神经网络将能够挑选出最美丽的那一个。 - Martijn Courteaux
12个回答

101

正如其他人所说,从1到10的排名并不太有效,因为人们的水平不同。

选择A或B的方法的问题在于系统不能保证是可传递的(A可以打败B,但B可以打败C,而C又可以打败A)。非可传递性比较运算符会破坏排序算法。在快速排序中,对于这个例子,未被选为枢轴的字母将被错误地排名。

在任何给定时间,您都希望对所有图片进行绝对排名(即使其中一些/全部图片处于并列状态)。同时,您还希望除非有人投票,否则您的排名不会改变。

我建议使用选择A或B(或平局)的方法,但类似于Elo评分系统来确定排名,该系统用于2人游戏(最初是国际象棋)中的排名:

Elo玩家评级系统通过比较玩家的比赛记录与对手的比赛记录,并确定玩家在比赛中获胜的概率。这个概率因素决定了每场比赛结果基于玩家得分而上升或下降的点数。当一个玩家击败一个具有更高等级的对手时,与击败一个等级较低的对手相比,这个玩家的评分会上升得更多(因为玩家应该击败那些具有较低评级的对手)。

Elo系统:

  1. 所有新玩家开始时都有一个基础评分1600
  2. 胜率=1/(10^((对手当前评分-玩家当前评分)/400) + 1)
  3. 得分点=如果他们赢了比赛,则为1分,如果输了,则为0分,如果平局,则为0.5分。
  4. 玩家新评分=玩家旧评分+(K值*(得分点-玩家获胜概率))

将“玩家”替换为图片,您就可以通过一个公式简单地调整两张图片的评分。然后,您可以使用这些数字分数进行排名。(此处的K-Value是比赛的“级别”。对于小型本地锦标赛为8-16,而大型邀请/区域锦标赛为24-32。您可以只使用像20这样的常数)。

使用这种方法,您只需要为每张图片保留一个数字,这比保留每张图片与其他每张图片的单独排名所需的内存要少得多。

编辑:基于评论添加了更多内容。


5
及物性并不重要。你只需要汇总人们的意见,预计他们在排名上会有分歧。人是一种嘈杂的数据来源,不够一致。 - Owen
5
我的观点是,如果你有 A > B > C > A 这种情况,那么简单地使用 ">" 作为比较符号是有问题的,因为你的排序永远不会(正确地)结束,即使没有更多的人投票,列表也会处于不断变化的状态。我的答案提供了解决这个问题的方法。 - Laplie Anderson
6
对于排名A/B方法,Elo系统肯定是可行的方式。不过,你最好使用比上面逐步增加的���法更好的方法。可以看一下Bayeselo:http://remi.coulom.free.fr/Bayesian-Elo/ - Fantius
1
@LaplieAnderson,有些人投A > B,有些人投B > A并没有什么问题,你只需要让它们互相抵消即可。这是所有康多塞投票系统的基础。例如,您正在计算A击败B的总次数。 - endolith
2
@endolith,这是针对OP存储比较并在其上使用快速排序的想法做出的回应。那样行不通。使用比较生成分数,然后对分数进行排序是可行的。 - Laplie Anderson
显示剩余2条评论

41
大多数对该问题的天真方法都存在一些严重问题。最糟糕的是bash.orgqdb.us显示引用的方式——用户可以投票支持(+1)或反对(-1),而最佳引用列表按总净分排序。这种算法存在可怕的时间偏差——即使只是稍微有趣,较早的引用也会通过简单的长寿累积大量正面评价。如果笑话随着时间的推移变得更加有趣,那么这种算法可能是有道理的,但请相信我,它们并没有。
有各种尝试来解决这个问题——查看每个时间段的正面评价数量,给更近期的评价加权,对旧评价实施衰减系统,计算正面评价与负面评价的比率等等。大多数都存在其他缺陷。
我认为最好的解决方案是网站The Funniest The CutestThe FairestBest Thing使用的修改后的康多塞投票系统
系统会给每个对象一个数字,该数字基于它所面对的事物中通常击败的百分比。因此,每个对象都会得到百分比分数NumberOfThingsIBeat / (NumberOfThingsIBeat + NumberOfThingsThatBeatMe)。此外,直到它们与一定比例的集合进行比较后,这些对象才能进入排名列表。
如果集合中存在Condorcet赢家,则该方法将找到它。鉴于统计性质,这是不太可能的,因此它会找到最接近成为Condorcet赢家的对象。
有关实施此类系统的更多信息,请参阅维基百科页面Ranked Pairs
该算法要求人们比较两个对象(即选择A或B),但实际上这是一件好事。我相信,在决策理论中,人类在比较两个对象方面要比抽象排名好得多。数百万年的进化使我们擅长从树上选出最好的苹果,但却很难决定我们选的苹果与真正的苹果本质有多接近。(顺便说一下,这就是为什么Analytic Hierarchy Process如此棒...但这有点偏题了。)

最后要说的一点是,SO使用一种算法来找到最佳答案,这个算法与bash.org找到最佳引用的算法非常相似。在这里它运作良好,但在那里则失败得很惨——主要原因是这里的旧答案可能会被编辑,尽管它们曾经高评价。bash.org不允许编辑,即使你能编辑那些关于过时网络模因的十年老笑话,也不清楚该如何编辑...总之,我的观点是正确的算法通常取决于问题的细节。 :-)


感谢提供关于康多塞投票系统的参考,这条线索让我找到了这个有用的维基百科页面 http://en.wikipedia.org/wiki/Ranked_Pairs。 - Paul Dixon
这些网站声称它们已经“崩溃”,并且此后被放弃。我不知道是算法有问题还是实现有误。 - endolith

12

我知道这个问题很老了,但我想做出贡献。

我会看一下微软研究开发的TrueSkill系统。它类似于ELO,但收敛时间要快得多(与线性相比呈指数增长),因此您可以从每个投票中获得更多的信息。然而,它在数学上更加复杂。

http://en.wikipedia.org/wiki/TrueSkill


TrueSkill的概念提供了很多通过“比赛”来排名事物的可能性。类似的概念被Bing用来提供相关的广告。我在http://www.moserware.com/2010/03/computing-your-skill.html写了很多关于TrueSkill细节的内容。 - Jeff Moser

8

我不喜欢“热或不热”风格。即使所有人都喜欢同样的图片,不同的人也会选择不同的数字。而且,我讨厌将事物评分为10分制,我从来不知道该选择哪个数字。

“选A或B”更简单、更有趣。您可以看到两幅图片,并在网站上进行比较。


5
这些来自维基百科的方程式使得计算Elo评分更加简单/有效,对于图像A和B的算法将会很简单:
  • 从数据库中获取Ne、mA、mB和评分RA、RB。
  • 通过使用执行的比较数量(Ne)和图像被比较的次数(m)以及当前评分来计算KA、KB、QA、QB:

K

QA

QB

  • 计算EA和EB。

EA

EB

  • 将获胜者的S得分设为1,失败者为0,如果平局则为0.5,
  • 使用以下公式计算双方的新等级: New Rating

  • 在数据库中更新新等级RA、RB和计数mA、mB。


4

您可能希望采用组合方式。

第一阶段: Hot-or-not风格(尽管我会选择3个选项投票:糟糕,一般/还行,很棒!)

将集合分成3个桶后,然后从同一桶中选择两个图像并选择“哪个更好”。

然后,您可以使用英式足球的晋升和降级系统将前几个“糟糕”的移动到Meh / OK区域,以便细化边缘情况。


4

排名1-10不可行,因为每个人的水平不同。总是给3-7分的人会被总是给1或10分的人超越。

a或b更加可行。


我很感激,但我想如果我确保每张图片获得相等数量的投票,那么它们应该会平均分配。问题是,我认为每张图片需要大约10个投票,根据上面的数字,这需要我13年的时间。到那时,我可能会有另外500万张图片 :) - Paul Dixon
1
由于人们倾向于选择平均值或高/低值,如果您决定这样做,我建议您将范围减少到1-5而不是1-10。 - Bill K

3
如果您喜欢使用选择A或B的策略,我建议阅读这篇论文:http://research.microsoft.com/en-us/um/people/horvitz/crowd_pairwise.pdf Chen, X.,Bennett, P.N.,Collins-Thompson,K.和Horvitz,E.(2013年2月)。在众包环境下的成对排名聚合。在第六届ACM国际网络搜索和数据挖掘会议论文集中(第193-202页)。ACM。
该论文介绍了Crowd-BT模型,将著名的Bradley-Terry成对比较模型扩展到众包环境中。它还提供了一种自适应学习算法来增强模型的时间和空间效率。您可以在Github上找到该算法的Matlab实现(但我不确定它是否有效)。

3

哇,我来晚了。

我非常喜欢ELO系统,但像Owen所说的,似乎你会花费很长时间才能建立起任何重要的结果。

我相信人类具有比仅仅比较两个图像更大的能力,但您需要将交互保持在最低限度。

那么,您可以展示n张图片(n是您可以在屏幕上显示的任意数量,可能是10、20、30,取决于用户的偏好),然后让他们选择他们认为在这些图片中最好的一张。现在回到ELO。您需要修改您的评分系统,但保持相同的精神。实际上,您已将一张图片与其他n-1张图片进行了比较。因此,您应该进行n-1次ELO评分,但应将评分变化除以n-1以匹配(以便具有不同n值的结果彼此协调)。

您完成了。现在您拥有所有优势。一个简单的评分系统,在一次点击中处理多张图片。


2
这段文字的意思是:“已停用的网站whatsbetter.com使用了Elo风格的方法。您可以在Internet Archive上阅读有关该方法的FAQ。”

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接