Wie man eine Million Bilder mit einer Crowdsourcing-Sorte bewertet

Ich möchte eine Sammlung von Landschaftsbildern in ein Spiel einordnen, in dem Website-Besucher sie bewerten können, um herauszufinden, welche Bilder für die Menschen am attraktivsten sind.

Was wäre eine gute Methode dafür?

• Hot-or-Not-Stil ? Wenn Sie also ein einzelnes Bild anzeigen, bitten Sie den Benutzer, es von 1-10 zu bewerten. Aus meiner Sicht kann ich so die Punktzahlen mitteln, und ich muss nur sicherstellen, dass ich eine gleichmäßige Verteilung der Stimmen auf alle Bilder bekomme. Ziemlich einfach zu implementieren.
• Wählen Sie A-oder-B ? Dh zwei Bilder anzeigen, Benutzer bitten, das bessere auszuwählen. Dies ist ansprechend, da es kein numerisches Ranking gibt, sondern nur einen Vergleich. Aber wie würde ich es umsetzen? Mein erster Gedanke war, es als Quicksort zu tun, wobei die Vergleichsoperationen von Menschen bereitgestellt wurden, und nach Abschluss einfach die Sortierung ad infinitum zu wiederholen.

Wie würdest du das machen?

Wenn Sie Zahlen benötigen, spreche ich von einer Million Bildern auf einer Website mit 20.000 täglichen Besuchen. Ich würde mir vorstellen, dass ein kleiner Teil das Spiel spielen könnte. Nehmen wir an, ich kann 2.000 menschliche Sortieroperationen pro Tag generieren! Es ist eine gemeinnützige Website, und die unheilbar Neugierigen werden sie über mein Profil finden :)

Wie andere gesagt haben, funktioniert Rang 1-10 nicht so gut, weil die Leute unterschiedliche Niveaus haben.

Das Problem bei der Pick A-or-B- Methode besteht darin, dass nicht garantiert wird, dass das System transitiv ist (A kann B schlagen, aber B schlägt C und C schlägt A). Nichttransitive Vergleichsoperatoren unterbrechen Sortieralgorithmen . Bei Quicksort werden in diesem Beispiel die Buchstaben, die nicht als Drehpunkt ausgewählt wurden, falsch gegeneinander eingestuft.

Zu jedem Zeitpunkt möchten Sie eine absolute Rangfolge aller Bilder (auch wenn einige / alle davon gebunden sind). Sie möchten auch, dass sich Ihr Ranking nur ändert, wenn jemand abstimmt .

Ich würde die Methode Pick A-or-B (oder Unentschieden) verwenden, aber eine Rangfolge bestimmen, die dem Elo-Bewertungssystem ähnelt, das für Ranglisten in 2-Spieler-Spielen verwendet wird (ursprünglich Schach):

Das Elo-Spielerbewertungssystem vergleicht die Spielaufzeichnungen der Spieler mit den Spielaufzeichnungen ihrer Gegner und bestimmt die Wahrscheinlichkeit, dass der Spieler das Matchup gewinnt. Dieser Wahrscheinlichkeitsfaktor bestimmt, wie viele Punkte die Bewertung eines Spielers basierend auf den Ergebnissen jedes Spiels steigt oder fällt. Wenn ein Spieler einen Gegner mit einer höheren Bewertung besiegt, steigt die Bewertung des Spielers stärker als wenn er oder sie einen Spieler mit einer niedrigeren Bewertung besiegt (da Spieler Gegner mit einer niedrigeren Bewertung besiegen sollten).

Das Elo-System:

1. Alle neuen Spieler beginnen mit einer Basisbewertung von 1600
2. WinProbability = 1 / (10 ^ ((Aktuelle Bewertung des Gegners - Aktuelle Bewertung des Spielers) / 400) + 1)
3. ScoringPt = 1 Punkt, wenn sie das Match gewinnen, 0, wenn sie verlieren, und 0,5 für ein Unentschieden.
4. Neue Bewertung des Spielers = Alte Bewertung des Spielers + (K-Wert * (ScoringPt - Gewinnwahrscheinlichkeit des Spielers))

Ersetzen Sie "Spieler" durch Bilder und Sie haben eine einfache Möglichkeit, die Bewertung beider Bilder basierend auf einer Formel anzupassen. Sie können dann eine Rangfolge mit diesen numerischen Bewertungen durchführen. (K-Wert ist hier das "Level" des Turniers. Es ist 8-16 für kleine lokale Turniere und 24-32 für größere Einladungen / Regionale. Sie können einfach eine Konstante wie 20 verwenden.)

Bei dieser Methode müssen Sie nur eine Nummer für jedes Bild behalten, was viel weniger speicherintensiv ist, als die einzelnen Ränge jedes Bildes zueinander zu halten.

EDIT: Etwas mehr Fleisch hinzugefügt, basierend auf Kommentaren.

Die meisten naiven Herangehensweisen an das Problem haben einige schwerwiegende Probleme. Das Schlimmste ist, wie bash.org und qdb.us Zitate anzeigen - Benutzer können ein Zitat nach oben (+1) oder unten (-1) abstimmen, und die Liste der besten Zitate wird nach der Gesamtnettowertung sortiert. Dies leidet unter einer schrecklichen zeitlichen Tendenz - ältere Zitate haben durch einfache Langlebigkeit eine große Anzahl positiver Stimmen gesammelt, auch wenn sie nur geringfügig humorvoll sind. Dieser Algorithmus könnte sinnvoll sein, wenn Witze mit zunehmendem Alter lustiger werden, aber - glauben Sie mir - nicht.

Es gibt verschiedene Versuche, dies zu beheben - Betrachtung der Anzahl positiver Stimmen pro Zeitraum, Gewichtung neuer Stimmen, Implementierung eines Zerfallsystems für ältere Stimmen, Berechnung des Verhältnisses von positiven zu negativen Stimmen usw. Die meisten leiden unter anderen Mängeln.

Die beste Lösung - denke ich - ist die, die die Websites The Funniest The Cutest , The Fairest und Best Thing verwenden - ein modifiziertes Condorcet-Abstimmungssystem :

Das System gibt jedem eine Zahl, die darauf basiert, wie viel Prozent der Dinge, mit denen es konfrontiert ist, normalerweise geschlagen werden. Jeder erhält also die prozentuale Punktzahl NumberOfThingsIBeat / (NumberOfThingsIBeat + NumberOfThingsThatBeatMe). Außerdem werden Dinge von der Top-Liste ausgeschlossen, bis sie mit einem angemessenen Prozentsatz des Satzes verglichen wurden.

Wenn es einen Condorcet-Gewinner im Set gibt, wird diese Methode ihn finden. Da dies aufgrund des statistischen Charakters unwahrscheinlich ist, findet es denjenigen, der dem Condorcet-Gewinner am nächsten kommt.

Für weitere Informationen zur Implementierung solcher Systeme sollte die Wikipedia-Seite über Ranglistenpaare hilfreich sein.

Der Algorithmus erfordert, dass Benutzer zwei Objekte vergleichen (Ihre Auswahl-A-oder-B-Option), aber ehrlich gesagt ist das eine gute Sache. Ich glaube, dass es in der Entscheidungstheorie sehr gut akzeptiert ist, dass Menschen zwei Objekte weitaus besser vergleichen können als abstrakte Ranglisten. Millionen von Jahren der Evolution machen es uns gut, den besten Apfel vom Baum zu pflücken, aber schrecklich zu entscheiden, wie nahe der Apfel, den wir gepflückt haben, an der wahren platonischen Form der Anhaftung liegt. (Dies ist übrigens der Grund, warum der Prozess der analytischen Hierarchie so geschickt ist ... aber das kommt ein bisschen vom Thema ab.)

Ein letzter Punkt ist, dass SO einen Algorithmus verwendet, um die besten Antworten zu finden, der dem Algorithmus von bash.org sehr ähnlich ist, um das beste Zitat zu finden. Es funktioniert hier gut, scheitert dort aber furchtbar - zum großen Teil, weil eine alte, hoch bewertete, aber jetzt veraltete Antwort hier wahrscheinlich bearbeitet wird. bash.org erlaubt keine Bearbeitung, und es ist nicht klar, wie Sie jahrzehntealte Witze über jetzt datierte Internet-Memes bearbeiten würden, selbst wenn Sie könnten ... Auf jeden Fall ist mein Punkt, dass normalerweise der richtige Algorithmus hängt von den Details Ihres Problems ab. :-)

Ich weiß, dass diese Frage ziemlich alt ist, aber ich dachte, ich würde dazu beitragen

Ich würde mir das TrueSkill-System ansehen, das bei Microsoft Research entwickelt wurde. Es ist wie bei ELO, hat jedoch eine viel schnellere Konvergenzzeit (sieht im Vergleich zu linear exponentiell aus), sodass Sie mit jeder Abstimmung mehr erreichen. Es ist jedoch mathematisch komplexer.

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

Ich mag den Hot-or-Not-Stil nicht . Unterschiedliche Personen würden unterschiedliche Zahlen auswählen, selbst wenn sie alle das Bild genau gleich mochten. Außerdem hasse ich es, Dinge mit 10 zu bewerten. Ich weiß nie, welche Nummer ich wählen soll.

Auswahl A-oder-B ist viel einfacher und lustiger. Sie sehen zwei Bilder und es werden Vergleiche zwischen den Bildern auf der Site durchgeführt.

Diese Gleichungen aus Wikipedia machen es einfacher / effektiver, Elo-Bewertungen zu berechnen. Der Algorithmus für die Bilder A und B wäre einfach:

• Holen Sie sich Ne, mA, mB und Bewertungen RA, RB aus Ihrer Datenbank.
• Berechnen Sie KA, KB, QA, QB anhand der Anzahl der durchgeführten Vergleiche (Ne) und der Häufigkeit des Bildvergleichs (m) sowie der aktuellen Bewertungen:

• Berechnen Sie EA und EB.

• Erziele das S des Gewinners: der Gewinner als 1, der Verlierer als 0 und wenn du ein Unentschieden als 0,5 hast,

• Berechnen Sie die neuen Bewertungen für beide mit:

• Aktualisieren Sie die neuen Bewertungen RA, RB und zählt mA, mB in der Datenbank.

Vielleicht möchten Sie mit einer Kombination gehen.

Erste Phase: Hot-or-Not-Stil (obwohl ich mit 3 Optionen abstimmen würde: Sucks, Meh / OK. Cool!)

Sobald Sie das Set in die 3 Eimer sortiert haben, würde ich zwei Bilder aus demselben Eimer auswählen und mit "Was ist schöner" fortfahren.

Sie könnten dann ein englisches Fußball-Promotions- und Herabstufungssystem verwenden, um die obersten "Sucks" in die Meh / OK-Region zu verschieben, um die Randfälle zu verfeinern.

Rang 1-10 funktioniert nicht, jeder hat unterschiedliche Level. Jemand, der immer 3-7 Bewertungen gibt, würde seine Rangliste von Leuten verdunkeln lassen, die immer 1 oder 10 geben.

a-or-b ist praktikabler.

Wow, ich bin spät im Spiel.

Ich mag das ELO-System sehr, aber wie Owen sagt, scheint es mir, dass Sie langsam signifikante Ergebnisse erzielen würden.

Ich glaube, Menschen haben eine viel größere Kapazität als nur den Vergleich zweier Bilder, aber Sie möchten die Interaktionen auf ein Minimum beschränken.

Wie wäre es also, wenn Sie n Bilder anzeigen (n ist eine beliebige Zahl, die Sie sichtbar auf einem Bildschirm anzeigen können, dies können 10, 20, 30 sein, je nach Präferenz des Benutzers) und sie dazu bringen, auszuwählen, welche ihrer Meinung nach in dieser Menge am besten ist. Nun zurück zu ELO. Sie müssen Ihr Bewertungssystem ändern, aber den gleichen Geist beibehalten. Sie haben tatsächlich ein Bild mit n-1 anderen verglichen. Sie führen Ihre ELO-Bewertung also n-1 Mal durch, aber Sie sollten die Änderung der Bewertung durch n-1 teilen, um sie anzupassen (damit die Ergebnisse mit unterschiedlichen Werten von n miteinander kohärent sind).

Du bist fertig. Sie haben jetzt das Beste von allen Welten. Ein einfaches Bewertungssystem, das mit vielen Bildern mit einem Klick arbeitet.

Wenn Sie die Strategie A oder B bevorzugen, würde ich dieses Dokument empfehlen: http://research.microsoft.com/en-us/um/people/horvitz/crowd_pairwise.pdf

Chen, X., Bennett, PN, Collins-Thompson, K. & Horvitz, E. (2013, Februar). Paarweise Rangaggregation in einer Crowdsourcing-Umgebung. In Proceedings der sechsten internationalen ACM-Konferenz zu Websuche und Data Mining (S. 193-202). ACM.

Das Papier berichtet über das Crowd-BT- Modell, das das berühmte paarweise Bradley-Terry-Vergleichsmodell auf Crowdsource-Einstellungen erweitert. Es bietet auch einen adaptiven Lernalgorithmus, um die Zeit- und Raumeffizienz des Modells zu verbessern. Sie können eine Matlab-Implementierung des Algorithmus auf Github finden (aber ich bin nicht sicher, ob es funktioniert).

Die nicht mehr existierende Website whatsbetter.com verwendete eine Elo-Methode . Sie können über die Methode in ihren FAQ im Internetarchiv lesen .

Wählen Sie A-oder-B am einfachsten und weniger anfällig für Verzerrungen. Bei jeder menschlichen Interaktion erhalten Sie jedoch wesentlich weniger Informationen. Ich denke, aufgrund der Bias-Reduzierung ist Pick überlegen und liefert Ihnen im Grenzfall die gleichen Informationen.

Ein sehr einfaches Bewertungsschema besteht darin, für jedes Bild eine Zählung durchzuführen. Wenn jemand einen positiven Vergleich gibt, erhöhen Sie die Anzahl, wenn jemand einen negativen Vergleich gibt, verringern Sie die Anzahl.

Das Sortieren einer 1-Millionen-Ganzzahlliste ist sehr schnell und dauert auf einem modernen Computer weniger als eine Sekunde.

Das Problem ist jedoch eher schlecht gestellt. Sie benötigen 50 Tage, um jedes Bild nur einmal anzuzeigen.

Ich wette, Sie interessieren sich mehr für die am höchsten bewerteten Bilder? Sie möchten Ihre Bildwiederherstellung wahrscheinlich nach dem vorhergesagten Rang verzerren. Daher zeigen Sie mit größerer Wahrscheinlichkeit Bilder, die bereits einige positive Vergleiche erzielt haben. Auf diese Weise werden Sie schneller "interessante" Bilder anzeigen.

Ich mag die Option zum schnellen Sortieren, aber ich würde ein paar Wochen machen:

• Behalten Sie die "Vergleichsergebnisse" in einer Datenbank und mitteln Sie sie dann.
• Erhalten Sie mehr als einen Vergleich pro Ansicht, indem Sie dem Benutzer 4-6 Bilder geben und sie sortieren lassen.
• Wählen Sie aus, welche Bilder angezeigt werden sollen, indem Sie qsort ausführen und alles aufzeichnen und zuschneiden, für das Sie nicht genügend Daten haben. Wenn Sie dann genügend Elemente aufgezeichnet haben, spucken Sie eine Seite aus.

Die andere lustige Option wäre, die Menge zu nutzen, um ein neuronales Netz zu unterrichten.