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

正如其他人所说,排名1-10并不能很好地工作,因为人们有不同的水平。

问题在于 拾取AO-B 方法是不保证系统是可传递的(A可以打败B,B可以打败C,C可以打败A)。 具有不可传递的比较运算符会破坏排序算法 . 对于QuickSort,在本例中,未选择作为轴的字母将不正确地相互排列。

在任何给定的时间,您都需要对所有图片进行绝对排名(即使其中一些/所有图片是绑定的)。你也希望你的排名不会改变 除非有人投票 .

我会用 选择A或B(或领带) 方法,但确定类似于 Elo ratings system 用于2个棋类游戏(原国际象棋)的排名:

ELO玩家等级 系统比较玩家的比赛记录 对抗对手的比赛记录 并确定 赢得比赛的运动员。这个 概率因素决定了多少 玩家评分上升或 根据每个 比赛。当一个玩家打败一个 得分较高的对手 玩家的等级比 他或她用 评分较低(因为玩家应该 击败低水平的对手 评级)。

ELO系统:

1. 所有新玩家的基本等级都是 一千六百
2. winprobability=1/(10^((opponent_ s current rating_ player_ s current rating)/400)+1)
3. 如果他们赢了,得1分;如果他们输了,得0分;平局,得0.5分。
4. 玩家的新评级=玩家的旧评级+(k值*(分数点玩家的获胜概率)

用图片替换“玩家”,您可以使用简单的方法根据公式调整两张图片的评级。然后,您可以使用这些数值分数执行排名。(这里的k值是锦标赛的“级别”。当地小型锦标赛为8-16,大型邀请赛/地区赛为24-32。你可以用20这样的常数。

使用这种方法,您只需要为每张图片保留一个数字,这比将每张图片的单个列组保留到另一张图片要少得多。

编辑:根据评论增加了一些肉。

大多数天真的解决问题的方法都有一些严重的问题。最糟糕的是 bash.org 和 qdb.us 显示报价-用户可以投票一个报价向上(+1)或向下(-1),最佳报价的列表是按总分排序的。这是一个可怕的时间偏差-旧的引用通过简单的寿命积累了大量的积极的选票,即使他们只是稍微幽默。如果随着年龄的增长,笑话变得更有趣,但是-相信我-他们不会的话,这个算法可能是有意义的。

有各种各样的尝试来解决这个问题——查看每个时间段的正票数量,加权最近的票,为老票实施衰减系统,计算正票和负票的比率,等等。大多数都有其他缺陷。

我认为最好的解决方案是 The Funniest The Cutest , The Fairest 和 Best Thing 使用-A modified Condorcet voting system :

这个系统根据它所面对的事情,给每个人一个数字,它通常能打败他们的百分比。所以每个人都得到了分数百分比,分数是多少(分数+分数)。此外,在将它们与合理比例的集合进行比较之前,它们都被禁止进入顶部列表。

如果有一个秃鹰胜利者在集合中,这个方法会找到它。由于这是不太可能的,考虑到统计性质,它找到了一个“最接近”成为秃鹰赢家。

有关实现此类系统的更多信息,请访问维基百科 Ranked Pairs 应该会有帮助。

该算法要求人们比较两个对象(您的pick-a-or-b选项),但坦率地说,这是一件好事。我相信,在决策理论中,人们比抽象的排序更擅长比较两个对象,这一点已被广泛接受。数百万年的进化使我们善于从树上摘下最好的苹果,但在决定我们摘下的苹果与真正柏拉图式的苹果有多接近时却很糟糕。(顺便说一下,这就是为什么 Analytic Hierarchy Process 太漂亮了……但这有点离题了。)

最后一点是,So使用一种算法来找到最佳答案,这与 bash.org 找到最佳报价的算法。它在这里工作得很好,但在那里却失败了——很大程度上是因为一个旧的,高评价的,但现在过时的答案很可能会被编辑。bash.org不允许编辑,也不清楚你怎么会编辑十年前关于现在已经过时的网络备忘录的笑话,即使你能……无论如何,我的观点是,正确的算法通常取决于问题的细节。:-)

我知道这个问题由来已久,但我想我会有所贡献。

我想看看微软研究院开发的TrueSkill系统。它与ELO类似,但收敛速度更快(与线性相比,它看起来是指数级的),所以每次投票都能得到更多的结果。然而,它在数学上更为复杂。

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

我不喜欢 热的还是不热的 . 不同的人会选择不同的数字,即使他们都喜欢完全相同的图像。我也讨厌把事情打分到10分之外,我不知道该选哪个号码。

拾取AO-B 更简单更有趣。您可以看到两个图像,并对站点上的图像进行比较。

这些方程来自 Wikipedia 使计算ELO分级更简单/更有效,图像A和B的算法将简单:

• 从数据库中获取ne、ma、mb和ratings ra、rb。
• 使用执行的比较次数(ne)和图像比较次数(m)和当前分级计算ka、kb、qa、qb:

• 计算ea和eb。

• 得分:赢家为1,输家为0,如果平局为0.5,

• 使用以下两种方法计算新评级:

• 更新数据库中的新评级ra、rb和counts ma、mb。

你可能想要一个组合。

第一阶段: 不管是热的还是不热的(尽管我会投3票:烂,好。酷!

一旦你把这组图片分为3个格,那么我会从同一个格中选择两张图片,然后选择“哪个更好”。

然后,你可以使用一个英国的足球升职和降职系统,将前几个“吸吮”的人转移到MEH/OK区域,以完善边缘案例。

排名1-10不起作用,每个人都有不同的等级。一个总是给3-7分的人,他的排名会被总是给1或10分的人盖过。

A或B更可行。

哇,我比赛迟到了。

我非常喜欢ELO系统,但就像欧文说的,在我看来,你会慢慢建立起任何重要的结果。

我相信人类比仅仅比较两幅图像有更大的能力,但是你想把互动保持在最低限度。

那么,你如何显示n个图像(n是你可以在屏幕上看到的任何数字,这可能是10,20,30,取决于用户的喜好)并让他们选择他们认为在那一批中最好的。现在回到ELO。你需要修改你的评级系统,但保持同样的精神。实际上,您已经将一个图像与其他n-1图像进行了比较。所以你做了n-1次ELO评分,但是你应该将评分的变化除以n-1进行匹配(这样,不同n值的结果是一致的)。

你完了。你现在拥有了世界上最好的。一个简单的分级系统,一次点击就可以处理许多图像。

如果您更喜欢使用“选择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, 二月)。众包环境中的成对排名聚合。在 第六届ACM网络搜索国际会议论文集 以及数据挖掘(第193-202页)。ACM。

这家报纸讲述了 人群BT 该模型将著名的布拉德利-特里配对比较模型扩展到众包设置中。提出了一种自适应学习算法,提高了模型的时间和空间效率。您可以在上找到算法的matlab实现 Github (但我不确定是否有效)。

不复存在的网站whatsbeater.com使用了 Elo style method . 你可以在他们的 FAQ on the Internet Archive .

拾取AO-B 这是最简单的,也不容易产生偏见,但是在每个人的互动中,它给你的信息都要少得多。我认为由于偏见的减少,选择是优越的,在限制它提供给你同样的信息。

一个非常简单的评分方案是对每张照片进行计数。当有人进行正比较时,递增计数;当有人进行负比较时,递减计数。

对100万个整数列表进行排序非常快速,在现代计算机上只需要不到一秒钟的时间。

也就是说,这个问题是相当不适的-你只需要50天的时间来显示每个图像一次。

我敢打赌,尽管你对排名最高的图片更感兴趣?因此,您可能希望通过预测的排名来偏向于图像检索,因此您更可能显示已经实现了几个正比较的图像。这样,您就可以更快地开始显示“有趣的”图像。

我喜欢快速分类,但我会做一些镊子:

• 将“比较”结果保存在数据库中,然后求平均值。
• 通过给用户4-6个图像并让它们排序,可以对每个视图进行多个比较。
• 通过运行qsort并记录和剪裁您没有足够数据的任何内容,选择要显示的图像。然后,当你有足够的项目记录,吐出一页。

另一个有趣的选择是利用人群来教授神经网络。