Comment classer un million d’images avec un sorting crowdsourced

J’aimerais classer une collection d’images de paysages en créant un jeu dans lequel les visiteurs du site peuvent les évaluer, afin de découvrir quelles images sont les plus intéressantes.

Quelle serait une bonne méthode pour le faire?

  • Style chaud ou pas ? Ie montrer une seule image, demandez à l’utilisateur de le classer de 1-10. À mon avis, cela me permet de faire la moyenne des scores, et je devrais simplement m’assurer que les votes soient répartis de manière égale entre toutes les images. Assez simple à mettre en œuvre.
  • Choisissez A ou B ? Ie montrer deux images, demander à l’utilisateur de choisir le meilleur. C’est attrayant car il n’y a pas de classement numérique, c’est juste une comparaison. Mais comment pourrais-je le mettre en œuvre? Ma première pensée a été de le faire rapidement, avec les opérations de comparaison fournies par les humains, et une fois terminé, il suffit de répéter le sorting ad-infinitum.

Comment vastu le faire?

Si vous avez besoin de chiffres, je parle d’un million d’images, sur un site de 20 000 visites quotidiennes. J’imagine qu’une petite proportion pourrait jouer le jeu, pour des raisons d’argumentation, disons que je peux générer 2 000 opérations de sorting humain par jour! C’est un site Web à but non lucratif, et les curieux seront au courant grâce à mon profil 🙂

Comme d’autres l’ont dit, le classement 1-10 ne fonctionne pas très bien car les gens ont des niveaux différents.

Le problème avec la méthode Pick A ou B est qu’il n’est pas garanti que le système soit transitif (A peut battre B, mais B bat C et C bat A). Avoir des opérateurs de comparaison non transcriptionnels casse les algorithmes de sorting . Avec quicksort, dans cet exemple, les lettres non choisies comme pivot seront mal classées les unes par rapport aux autres.

À tout moment, vous voulez un classement absolu de toutes les images (même si certaines / toutes sont liées). Vous voulez également que votre classement ne change pas à moins que quelqu’un ne vote .

J’utiliserais la méthode Pick A-or-B (ou tie) , mais déterminerais un classement similaire à celui d’ Elo qui est utilisé pour les classements dans les jeux à 2 joueurs (à l’origine aux échecs):

Le système de classement des joueurs Elo compare les enregistrements de match des joueurs à ceux de leurs adversaires et détermine la probabilité que le joueur remporte le match. Ce facteur de probabilité détermine combien de points la note d’un joueur augmente ou diminue en fonction des résultats de chaque match. Lorsqu’un joueur vainc un adversaire avec une note plus élevée, la note du joueur augmente plus que s’il a vaincu un joueur avec une note inférieure (puisque les joueurs doivent vaincre des adversaires ayant des notes plus faibles).

Le système Elo:

  1. Tous les nouveaux joueurs commencent avec une note de base de 1600
  2. WinProbability = 1 / (10 ^ ((note actuelle de l’adversaire – note actuelle du joueur) / 400) + 1)
  3. ScoringPt = 1 point s’ils gagnent le match, 0 s’ils perdent et 0,5 pour un match nul.
  4. Nouvelle note du joueur = Ancienne note du joueur + (Valeur K * (Probabilité de victoire du joueur)

Remplacez “joueurs” par des images et vous avez un moyen simple d’ajuster le classement des deux images en fonction d’une formule. Vous pouvez ensuite effectuer un classement en utilisant ces scores numériques. (Valeur K ici est le “Niveau” du tournoi. Il est 8-16 pour les petits tournois locaux et 24-32 pour les plus grands invitations / régionales. Vous pouvez simplement utiliser une constante comme 20).

Avec cette méthode, il vous suffit de conserver un numéro pour chaque image, ce qui nécessite beaucoup moins de mémoire que de conserver les classements individuels de chaque image les uns par rapport aux autres.

EDIT: Ajout d’un peu plus de viande en fonction des commentaires.

La plupart des approches naïves au problème posent de sérieux problèmes. Le pire est la façon dont bash.org et qdb.us affichent les citations – les utilisateurs peuvent voter une citation (+1) ou une baisse (-1), et la liste des meilleures citations est sortingée en fonction du score net total. Cela souffre d’un biais de temps horrible – les citations plus anciennes ont accumulé un grand nombre de votes positifs via une longévité simple, même si elles ne sont que marginalement humoristiques. Cet algorithme pourrait avoir du sens si les blagues devenaient plus amusantes à mesure qu’elles grandissaient, mais – croyez-moi – elles ne le font pas.

Il y a plusieurs tentatives pour résoudre ce problème – en examinant le nombre de votes positifs par période, en pondérant les votes les plus récents, en appliquant un système de décroissance pour les votes plus anciens, en calculant le rapport entre votes positifs et négatifs.

La meilleure solution – je pense – est celle que les sites Web The Funniest The Cutest , The Fairest et Best Thing utilisent – un système de vote Condorcet modifié :

Le système donne à chacun un nombre basé sur, parmi les choses auxquelles il a été confronté, quel pourcentage d’entre eux bat habituellement. Ainsi, chacun obtient le score de NumberOfThingsIBeat / (NumberOfThingsIBeat + NumberOfThingsThatBeatMe). De plus, les choses sont exclues de la liste supérieure jusqu’à ce qu’elles soient comparées à un pourcentage raisonnable de l’ensemble.

S’il y a un gagnant Condorcet dans l’ensemble, cette méthode le trouvera. Étant donné que c’est peu probable, compte tenu de la nature statistique, il trouve celui qui est le plus proche d’être un gagnant de Condorcet.

Pour plus d’informations sur la mise en œuvre de tels systèmes, la page Wikipedia sur les paires classées devrait être utile.

L’algorithme exige que les gens comparent deux objects (votre option Pick-A-or-B), mais franchement, c’est une bonne chose. Je pense qu’il est très bien accepté dans la théorie de la décision que les humains sont nettement meilleurs pour comparer deux objects qu’au classement abstrait. Des millions d’années d’évolution nous permettent de cueillir la meilleure pomme de l’arbre, mais c’est terrible de décider à quel point la pomme que nous avons cueillie correspond à la véritable forme d’apparence platonicienne. (C’est d’ailleurs la raison pour laquelle le processus de hiérarchie analytique est si astucieux … mais cela devient un peu hors sujet.)

Un dernier point à retenir est que SO utilise un algorithme pour trouver les meilleures réponses, ce qui est très similaire à l’ algorithme de bash.org pour trouver la meilleure citation. Cela fonctionne bien ici, mais échoue terriblement là-bas – en grande partie parce qu’une vieille réponse, hautement cotée, mais maintenant dépassée, est susceptible d’être modifiée. bash.org n’autorise pas l’édition, et il n’est pas clair comment vous pourriez même éditer des blagues vieilles de dix ans sur les mèmes internet maintenant datés, même si vous pouviez … En tout cas, mon point est que le bon algorithme habituellement dépend des détails de votre problème. 🙂

Je sais que cette question est assez ancienne mais je pensais y consortingbuer

Je regarderais le système TrueSkill développé à Microsoft Research. C’est comme ELO, mais le temps de convergence est beaucoup plus rapide (il semble exponentiel par rapport à linéaire), vous obtenez donc plus de votes. Il est cependant plus complexe mathématiquement.

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

Je n’aime pas le style Hot-or-Not . Différentes personnes choisiraient des nombres différents même si elles ont toutes aimé l’image exactement de la même manière. Aussi, je déteste noter les choses sur 10, je ne sais jamais quel numéro choisir.

Pick A-or-B est beaucoup plus simple et funner. Vous obtenez deux images et des comparaisons sont faites entre les images sur le site.

Ces équations de Wikipedia rendent plus simple / plus efficace le calcul des notes d’Elo, l’algorithme pour les images A et B serait simple:

  • Obtenez Ne, mA, mB et notes RA, RB de votre firebase database.
  • Calculer KA, KB, QA, QB en utilisant le nombre de comparaisons effectuées (Ne) et le nombre de fois où cette image a été comparée (m) et les notations actuelles:

K

QA

QB

  • Calculer EA et EB.

EA

EB

  • Marquez le S du gagnant: le vainqueur à 1, le perdant à 0 et si vous avez un nul à 0,5,
  • Calculez les nouvelles notes pour les deux en utilisant: Nouveau classement

  • Mettez à jour les nouvelles notations RA, RB et compte mA, mB dans la firebase database.

Vous voudrez peut-être aller avec une combinaison.

Première phase: style hot-or-not (bien que j’irais avec un vote de 3 options: Sucks, Meh / OK. Cool!)

Une fois que vous avez sortingé le jeu dans les 3 compartiments, alors je sélectionnerais deux images du même seau et je choisirais “Le plus beau”

Vous pouvez ensuite utiliser un système de promotion et de rétrogradation anglais Soccer pour déplacer les quelques “suçons” dans la région Meh / OK, afin d’affiner les cas limites.

Le classement 1-10 ne fonctionnera pas, tout le monde a des niveaux différents. Quelqu’un qui donne toujours une note de 3 à 7 aurait son classement éclipsé par des gens qui donnent toujours 1 ou 10.

a-ou-b est plus pratique.

Wow, je suis en retard dans le jeu.

J’aime beaucoup le système ELO, mais comme Owen le dit, il me semble que vous tarderiez à obtenir des résultats significatifs.

Je pense que les humains ont une capacité beaucoup plus grande que la simple comparaison de deux images, mais vous voulez garder les interactions au ssortingct minimum.

Alors, que diriez-vous de montrer n images (n étant un nombre quelconque que vous pouvez visiblement afficher sur un écran, cela peut être 10, 20, 30 selon les préférences de l’utilisateur) et les choisir qui, selon eux, sont les meilleures dans ce lot. Maintenant, revenons à ELO. Vous devez modifier votre système de notation, mais garder le même esprit. Vous avez en fait comparé une image à n-1 autres. Donc, vous faites votre évaluation ELO n-1 fois, mais vous devez diviser le changement de note par n-1 pour correspondre (afin que les résultats avec des valeurs différentes de n soient cohérents les uns avec les autres).

Vous avez terminé. Vous avez maintenant le meilleur de tous les mondes. Un système de notation simple fonctionnant avec de nombreuses images en un clic.

Si vous préférez utiliser la stratégie Pick A ou B, je vous recommande ce document: http://research.microsoft.com/en-us/um/people/horvitz/crowd_pairwise.pdf

Chen, X., Bennett, PN, Collins-Thompson, K. et Horvitz, E. (2013, février). Agrégation de classement par paires dans un contexte de crowdsourcing. Dans Actes de la sixième conférence internationale d’ACM sur la recherche sur le Web et l’exploration de données (pp. 193-202). ACM.

Le papier parle du modèle Crowd-BT qui étend le fameux modèle de comparaison par paires Bradley-Terry à la définition de crowdsource. Il fournit également un algorithme d’apprentissage adaptatif pour améliorer l’efficacité temporelle et spatiale du modèle. Vous pouvez trouver une implémentation Matlab de l’algorithme sur Github (mais je ne suis pas sûr que cela fonctionne).

Le site Web disparu whatsbetter.com a utilisé une méthode de style Elo . Vous pouvez lire sur la méthode dans leur FAQ sur Internet Archive .

Choisissez A ou B c’est le plus simple et le moins enclin au biais, cependant, à chaque interaction humaine, vous recevez beaucoup moins d’informations. Je pense qu’en raison de la réduction du biais, Pick est supérieur et dans la limite il vous fournit les mêmes informations.

Un système de notation très simple consiste à compter chaque image. Lorsque quelqu’un donne une comparaison positive, incrémenter le compte, lorsque quelqu’un donne une comparaison négative, décrémenter le compte.

Trier une liste de 1 million d’entiers est très rapide et prendra moins d’une seconde sur un ordinateur moderne.

Cela dit, le problème est plutôt mal posé – il vous faudra 50 jours pour afficher chaque image une seule fois.

Je parie que vous êtes plus intéressé par les images les mieux classées? Donc, vous voulez probablement biaiser votre recherche d’image par rang prédite – vous êtes donc plus susceptible de montrer des images qui ont déjà réalisé quelques comparaisons positives. De cette façon, vous commencerez plus rapidement à montrer des images «intéressantes».

J’aime l’option de sorting rapide mais je ferais quelques tweeks:

  • Conservez les résultats de la comparaison dans une firebase database et calculez leur moyenne.
  • Obtenez plus d’une comparaison par vue en donnant à l’utilisateur 4 à 6 images et en les sortingant.
  • Sélectionnez les images à afficher en exécutant qsort et en enregistrant et en coupant tout ce qui ne contient pas suffisamment de données. Ensuite, lorsque vous avez suffisamment d’éléments enregistrés, crachez une page.

L’autre option amusante serait d’utiliser la foule pour enseigner un réseau neuronal.