Jak uszeregować milion obrazów za pomocą crowdsourcingu

Chciałbym uszeregować kolekcję obrazów krajobrazowych, tworząc grę, w której odwiedzający witrynę mogą je oceniać, aby dowiedzieć się, które obrazy są najbardziej atrakcyjne dla ludzi.

Jaka byłaby dobra metoda zrobienia tego?

• Styl Hot or Not ? To znaczy pokaż pojedynczy obraz, poproś użytkownika o uszeregowanie go w zakresie od 1 do 10. Jak widzę, pozwala mi to uśrednić wyniki i musiałbym tylko upewnić się, że otrzymam równy rozkład głosów na wszystkie obrazy. Dość proste do wykonania.
• Wybierz A lub B ? To znaczy pokaż dwa obrazy, poproś użytkownika o wybranie lepszego. Jest to atrakcyjne, ponieważ nie ma rankingu liczbowego, to tylko porównanie. Ale jak bym to zaimplementował? Moją pierwszą myślą było zrobienie tego w trybie szybkiego sortowania, z operacjami porównania zapewnianymi przez ludzi, a po zakończeniu po prostu powtórz sortowanie w nieskończoność.

Jak byś to zrobił?

Jeśli potrzebujesz liczb, mówię o milionie obrazów w witrynie z 20 000 odwiedzin dziennie. Wyobrażam sobie, że mała część może zagrać w tę grę, ze względu na argumentację, powiedzmy, że mogę wygenerować 2000 operacji sortowania ludzi dziennie! Jest to strona non-profit, a nieuleczalnie ciekawi znajdą ją na moim profilu :)

Jak powiedzieli inni, ranking 1-10 nie działa tak dobrze, ponieważ ludzie mają różne poziomy.

Problem z metodą Pick A-lub-B polega na tym, że nie ma gwarancji, że system będzie przechodni (A może pokonać B, ale B pokonuje C, a C pokonuje A). Posiadanie nieprzechodnich operatorów porównania przerywa działanie algorytmów sortowania . W przypadku szybkiego sortowania w tym przykładzie litery, które nie zostały wybrane jako oś obrotu, zostaną nieprawidłowo uszeregowane względem siebie.

W dowolnym momencie chcesz mieć absolutny ranking wszystkich zdjęć (nawet jeśli niektóre / wszystkie z nich są powiązane). Chcesz także, aby Twój ranking nie zmieniał się, chyba że ktoś zagłosuje .

Użyłbym metody Wybierz A-lub-B (lub remis) , ale określam ranking podobny do systemu rankingowego Elo, który jest używany do rankingów w grach 2-osobowych (pierwotnie w szachy):

System rankingowy Elo porównuje wyniki meczów graczy z wynikami meczów przeciwników i określa prawdopodobieństwo wygrania pojedynku przez gracza. Ten współczynnik prawdopodobieństwa określa, o ile punktów ocena gracza wzrośnie lub spadnie na podstawie wyników każdego meczu. Kiedy gracz pokona przeciwnika z wyższą oceną, ocena gracza rośnie bardziej, niż gdyby pokonał gracza z niższą oceną (ponieważ gracze powinni pokonać przeciwników, którzy mają niższy ranking).

System Elo:

1. Wszyscy nowi gracze zaczynają z rankingiem podstawowym 1600
2. WinProbability = 1 / (10 ^ ((aktualna ocena przeciwnika - aktualna ocena gracza) / 400) + 1)
3. ScoringPt = 1 punkt, jeśli wygrają mecz, 0 jeśli przegrają i 0,5 za remis.
4. Nowa ocena gracza = stara ocena gracza + (wartość K * (punktacja - prawdopodobieństwo wygranej gracza))

Zastąp „zawodników” obrazkami, a uzyskasz prosty sposób dostosowania oceny obu obrazków na podstawie wzoru. Następnie możesz przeprowadzić ranking przy użyciu tych wyników liczbowych. (Wartość K to tutaj „Poziom” turnieju. Jest to 8-16 dla małych lokalnych turniejów i 24-32 dla większych zaproszeń / zawodów regionalnych. Możesz po prostu użyć stałej, np. 20).

Dzięki tej metodzie wystarczy zachować tylko jedną liczbę dla każdego obrazu, co zajmuje dużo mniej pamięci niż utrzymywanie poszczególnych rang każdego obrazu względem siebie.

EDYCJA: Dodano trochę więcej mięsa na podstawie komentarzy.

Większość naiwnych podejść do problemu wiąże się z poważnymi problemami. Najgorszy jest sposób, w jaki bash.org i qdb.us wyświetlają cytaty - użytkownicy mogą głosować w górę (+1) lub w dół (-1), a lista najlepszych cytatów jest sortowana według całkowitego wyniku netto. Cierpi na tym okropne uprzedzenie czasowe - starsze cytaty zgromadziły ogromną liczbę pozytywnych głosów dzięki prostej długowieczności, nawet jeśli są tylko marginalnie humorystyczne. Ten algorytm może mieć sens, jeśli dowcipy stawały się zabawniejsze wraz z wiekiem, ale - wierz mi - tak się nie dzieje.

Istnieją różne próby rozwiązania tego problemu - patrząc na liczbę pozytywnych głosów w danym okresie, ważenie nowszych głosów, wdrażanie systemu zanikania starszych głosów, obliczanie stosunku głosów pozytywnych do negatywnych itp. Większość z nich ma inne wady.

Najlepszym rozwiązaniem - jak sądzę - jest takie, które wykorzystuje serwisy The Funniest The Cutest , The Fairest i Best Thing - zmodyfikowany system głosowania Condorcet :

System nadaje każdemu liczbę w oparciu o rzeczy, z którymi się zmierzył, jaki procent z nich zwykle bije. Więc każdy z nich otrzymuje wynik procentowy NumberOfThingsIBeat / (NumberOfThingsIBeat + NumberOfThingsThatBeatMe). Ponadto rzeczy są wykluczane z górnej listy, dopóki nie zostaną porównane z rozsądnym procentem zestawu.

Jeśli w zestawie jest zwycięzca Condorcet, ta metoda go znajdzie. Ponieważ jest to mało prawdopodobne, biorąc pod uwagę charakter statystyczny, znajduje to, kto jest „najbliżej” zwycięzcy Condorceta.

Więcej informacji na temat wdrażania takich systemów można znaleźć na stronie Wikipedii o parach rankingowych .

Algorytm wymaga od ludzi porównania dwóch obiektów (opcja Pick-A-or-B), ale szczerze mówiąc, to dobrze. Uważam, że w teorii podejmowania decyzji bardzo dobrze przyjmuje się, że ludzie znacznie lepiej radzą sobie z porównywaniem dwóch obiektów niż w rankingu abstrakcyjnym. Miliony lat ewolucji sprawiają, że jesteśmy dobrzy w zrywaniu najlepszego jabłka z drzewa, ale straszni w decydowaniu o tym, jak blisko zerwane jabłko wyrasta z prawdziwą platońską formą zastosowania. (Nawiasem mówiąc, to jest powód, dla którego proces hierarchii analitycznej jest tak sprytny ... ale to jest trochę poza tematem.)

Ostatnim punktem, na który należy zwrócić uwagę, jest to, że SO używa algorytmu do znajdowania najlepszych odpowiedzi, który jest bardzo podobny do algorytmu bash.org w celu znalezienia najlepszego cytatu. Tutaj działa dobrze, ale tam bardzo zawodzi - w dużej mierze dlatego, że stara, wysoko oceniana, ale teraz przestarzała odpowiedź tutaj prawdopodobnie zostanie zredagowana. bash.org nie pozwala na edycję i nie jest jasne, w jaki sposób można by nawet edytować sprzed dziesięcioleci dowcipy o przestarzałych memach internetowych, nawet gdybyś mógł ... W każdym razie chodzi mi o to, że zwykle odpowiedni algorytm zależy od szczegółów twojego problemu. :-)

Wiem, że to pytanie jest dość stare, ale pomyślałem, że wniesie swój wkład

Spojrzałbym na system TrueSkill opracowany w Microsoft Research. To jest jak ELO, ale ma znacznie szybszy czas zbieżności (wygląda wykładniczo w porównaniu z liniowym), dzięki czemu uzyskujesz więcej z każdego głosowania. Jest to jednak bardziej złożone matematycznie.

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

Nie podoba mi się styl Hot-or-Not . Różni ludzie wybieraliby różne liczby, nawet jeśli wszystkim podobał się obraz dokładnie taki sam. Nienawidzę też oceniania rzeczy na 10, nigdy nie wiem, którą liczbę wybrać.

Wybór A-lub-B jest znacznie prostszy i przyjemniejszy. Widzisz dwa obrazy i dokonuje się porównań między obrazami na stronie.

Te równania z Wikipedii sprawiają, że obliczanie ocen Elo jest prostsze / bardziej efektywne, algorytm dla obrazów A i B byłby prosty:

• Pobierz Ne, mA, mB i oceny RA, RB ze swojej bazy danych.
• Oblicz KA, KB, QA, QB na podstawie liczby wykonanych porównań (Ne) i liczby porównań tego obrazu (m) oraz bieżących ocen:

• Oblicz EA i EB.

• Zdobądź S: zwycięzca 1, przegrany 0, a jeśli masz remis 0,5,

• Oblicz nowe oceny dla obu przy użyciu:

• Zaktualizuj nowe oceny RA, RB i liczy mA, mB w bazie danych.

Możesz wybrać kombinację.

Pierwsza faza: styl gorący lub nie (chociaż wybrałbym głosowanie z 3 opcjami: Sucks, Meh / OK. Cool!)

Po posortowaniu zestawu do 3 zasobników wybrałbym dwa obrazy z tego samego zasobnika i przeszedłem do opcji „Co jest ładniejsze”

Następnie możesz użyć systemu awansów i degradacji w angielskiej piłce nożnej, aby przesunąć kilka najlepszych „Sucks” do regionu Meh / OK, aby udoskonalić skrajne przypadki.

Klasyfikacja 1-10 nie zadziała, każdy ma inny poziom. Ktoś, kto zawsze wystawia oceny 3-7, miałby jego ranking przyćmiony przez ludzi, którzy zawsze dają 1 lub 10.

a-or-b jest bardziej wykonalne.

Wow, jestem spóźniony w grze.

Bardzo podoba mi się system ELO, ale tak jak mówi Owen, wydaje mi się, że powolne byłoby uzyskiwanie jakichkolwiek znaczących wyników.

Uważam, że ludzie mają znacznie większe możliwości niż zwykłe porównywanie dwóch obrazów, ale chcesz ograniczyć interakcje do absolutnego minimum.

Więc co powiesz na pokazanie n obrazów (n to dowolna liczba, którą możesz w widoczny sposób wyświetlić na ekranie, może to być 10, 20, 30 w zależności od preferencji użytkownika) i nakłonić ich do wybrania tego, co według nich jest najlepsze w tej partii. Teraz wróć do ELO. Musisz zmodyfikować swój system ocen, ale zachowaj ten sam duch. W rzeczywistości porównałeś jeden obraz z n-1 innymi. Więc robisz swoją ocenę ELO n-1 razy, ale powinieneś podzielić zmianę oceny przez n-1, aby dopasować (tak, aby wyniki z różnymi wartościami n były ze sobą spójne).

Jesteś skończony. Masz teraz to, co najlepsze ze wszystkich światów. Prosty system oceniania pracujący z wieloma obrazami jednym kliknięciem.

Jeśli wolisz korzystać ze strategii Wybierz A lub B, polecam ten artykuł: http://research.microsoft.com/en-us/um/people/horvitz/crowd_pairwise.pdf

Chen, X., Bennett, PN, Collins-Thompson, K. i Horvitz, E. (2013, luty). Agregacja rankingu parami w ustawieniach crowdsourcingowych. W materiałach szóstej międzynarodowej konferencji ACM poświęconej wyszukiwaniu w Internecie i eksploracji danych (str. 193-202). ACM.

Artykuł mówi o modelu Crowd-BT, który rozszerza słynny model porównawczy parami Bradley-Terry na ustawienie crowdsource. Zapewnia również adaptacyjny algorytm uczenia się w celu zwiększenia wydajności czasowej i przestrzennej modelu. Możesz znaleźć implementację algorytmu Matlab na Github (ale nie jestem pewien, czy to działa).

Nieistniejąca witryna internetowa whatsbetter.com wykorzystywała metodę w stylu Elo . Możesz przeczytać o tej metodzie w ich FAQ w Internet Archive .

Wybierz A-lub-B to najprostszy i mniej podatny na uprzedzenia sposób, jednak przy każdej interakcji z człowiekiem dostarcza znacznie mniej informacji. Myślę, że ze względu na redukcję odchylenia Pick jest lepszy iw granicach zapewnia te same informacje.

Bardzo prostym schematem punktacji jest liczenie dla każdego obrazu. Kiedy ktoś podaje pozytywne porównanie, zwiększaj licznik, gdy ktoś podaje negatywne porównanie, zmniejszaj licznik.

Sortowanie listy zawierającej 1 milion liczb całkowitych jest bardzo szybkie i na nowoczesnym komputerze zajmie mniej niż sekundę.

To powiedziawszy, problem jest raczej źle postawiony - wyświetlenie każdego obrazu tylko raz zajmie 50 dni.

Założę się, że bardziej interesują Cię najwyżej ocenione obrazy? Dlatego prawdopodobnie chcesz przesunąć wyszukiwanie obrazu według przewidywanej rangi - dzięki czemu masz większe szanse na wyświetlenie obrazów, które uzyskały już kilka pozytywnych porównań. W ten sposób szybciej zaczniesz wyświetlać „interesujące” obrazy.

Podoba mi się opcja szybkiego sortowania, ale zrobiłbym kilka poprawek:

• Zachowaj wyniki „porównania” w bazie danych, a następnie uśrednij je.
• Uzyskaj więcej niż jedno porównanie na widok, dając użytkownikowi 4-6 obrazów i sortując je.
• Wybierz obrazy do wyświetlenia, uruchamiając qsort i nagrywając i przycinając wszystko, na temat czego nie masz wystarczających danych. Następnie, gdy masz już wystarczająco dużo zapisanych pozycji, wypluj stronę.

Inną zabawną opcją byłoby wykorzystanie tłumu do nauczenia sieci neuronowej.