Como classificar um milhão de imagens com uma classificação crowdsourced

Eu gostaria de classificar uma coleção de imagens de paisagens fazendo um jogo em que os visitantes do site possam classificá-las, a fim de descobrir quais imagens as pessoas acham mais atraentes.

Qual seria um bom método de fazer isso?

• Estilo quente ou não ? Ou seja, para mostrar uma única imagem, peça ao usuário para classificá-la de 1 a 10. A meu ver, isso me permite calcular a média das pontuações, e eu só preciso garantir uma distribuição uniforme dos votos em todas as imagens. Bastante simples de implementar.
• Escolha A-ou-B ? Ou seja, mostre duas imagens, peça ao usuário para escolher a melhor. Isso é atraente, pois não há classificação numérica, é apenas uma comparação. Mas como eu o implementaria? Meu primeiro pensamento foi fazer isso como uma classificação rápida, com as operações de comparação sendo fornecidas por humanos e, uma vez concluídas, simplesmente repetir a classificação ad-infinitum.

Como você faria isso?

Se você precisa de números, estou falando de um milhão de imagens, em um site com 20.000 visitas diárias. Eu imagino que uma pequena proporção possa jogar o jogo, para fins de argumentação, digamos que eu possa gerar 2.000 operações de classificação humana por dia! É um site sem fins lucrativos, e os curiosos terminais irão encontrá-lo em meu perfil :)

Como outros já disseram, a classificação de 1 a 10 não funciona muito bem porque as pessoas têm níveis diferentes.

O problema com o método Pick A-or-B é que não é garantido que o sistema seja transitivo (A pode vencer B, mas B vence C e C vence A). Ter operadores de comparação não transitivos quebra algoritmos de classificação . Com o quicksort, neste exemplo, as letras não escolhidas como pivô serão classificadas incorretamente umas contra as outras.

A qualquer momento, você deseja uma classificação absoluta de todas as fotos (mesmo se algumas / todas estiverem empatadas). Você também deseja que sua classificação não mude, a menos que alguém vote .

Eu usaria o método Pick A-or-B (ou empate) , mas determinaria a classificação semelhante ao sistema de classificação Elo que é usado para classificações em jogos de 2 jogadores (originalmente xadrez):

O sistema de classificação de jogadores Elo compara os registros de jogo dos jogadores com os registros de jogo de seus oponentes e determina a probabilidade de o jogador ganhar o jogo. Este fator de probabilidade determina quantos pontos a classificação de um jogador aumenta ou diminui com base nos resultados de cada partida. Quando um jogador derrota um oponente com uma classificação mais alta, a classificação do jogador sobe mais do que se ele ou ela derrotasse um jogador com uma classificação mais baixa (já que os jogadores devem derrotar oponentes com classificações mais baixas).

O sistema Elo:

1. Todos os novos jogadores começam com uma classificação básica de 1600
2. WinProbability = 1 / (10 ^ ((Avaliação atual do oponente - Avaliação atual do jogador) / 400) + 1)
3. ScoringPt = 1 ponto se vencer a partida, 0 se perder e 0,5 para empate.
4. Nova classificação do jogador = Classificação anterior do jogador + (K-Value * (ScoringPt – Probabilidade de vitória do jogador))

Substitua "jogadores" por imagens e você terá uma maneira simples de ajustar a classificação de ambas as imagens com base em uma fórmula. Você pode então realizar uma classificação usando essas pontuações numéricas. (K-Value aqui é o "Nível" do torneio. É 8-16 para pequenos torneios locais e 24-32 para convites / regionais maiores. Você pode usar uma constante como 20).

Com este método, você só precisa manter um número para cada imagem, o que exige muito menos memória do que manter as classificações individuais de cada imagem entre si.

EDIT: Adicionado um pouco mais de carne com base nos comentários.

A maioria das abordagens ingênuas do problema apresenta alguns problemas sérios. O pior é como bash.org e qdb.us exibem as cotações - os usuários podem votar uma cotação para cima (+1) ou para baixo (-1), e a lista das melhores cotações é classificada pela pontuação líquida total. Isso sofre de um viés de tempo horrível - citações mais antigas acumularam um grande número de votos positivos por meio da simples longevidade, mesmo que sejam apenas ligeiramente humorísticas. Este algoritmo pode fazer sentido se as piadas ficarem mais engraçadas à medida que envelhecem, mas - acredite em mim - elas não ficam.

Existem várias tentativas de corrigir isso - olhar para o número de votos positivos por período de tempo, ponderar votos mais recentes, implementar um sistema de decadência para votos mais antigos, calcular a proporção de votos positivos para negativos, etc. A maioria sofre de outras falhas.

A melhor solução - eu acho - é o que os sites o mais engraçado o mais bonito , o mais justo e melhor coisa de uso - um sistema de votação Condorcet modificado :

O sistema dá a cada um um número baseado em, das coisas que enfrentou, em qual porcentagem delas ele normalmente bate. Assim, cada um obtém a pontuação percentual NumberOfThingsIBeat / (NumberOfThingsIBeat + NumberOfThingsThatBeatMe). Além disso, as coisas são excluídas da lista superior até que sejam comparadas a uma porcentagem razoável do conjunto.

Se houver um vencedor Condorcet no conjunto, este método o encontrará. Como isso é improvável, dada a natureza estatística, ele encontra aquele que está "mais próximo" de ser um vencedor do Condorcet.

Para obter mais informações sobre a implementação de tais sistemas, consulte a página da Wikipedia sobre pares classificados deve ser útil.

O algoritmo requer que as pessoas comparem dois objetos (sua opção Pick-A-ou-B), mas francamente, isso é uma coisa boa. Acredito que seja muito bem aceito na teoria da decisão que os humanos são muito melhores em comparar dois objetos do que em classificações abstratas. Milhões de anos de evolução nos tornam bons em colher a melhor maçã da árvore, mas terríveis em decidir quão perto a maçã que colhemos se aproxima da verdadeira forma platônica de maciez. (Este é, a propósito, o motivo pelo qual o Processo de Hierarquia Analítica é tão bacana ... mas isso está saindo um pouco do assunto.)

Um último ponto a fazer é que o SO usa um algoritmo para encontrar as melhores respostas que é muito semelhante ao bash.org algoritmo do para encontrar a melhor citação. Funciona bem aqui, mas falha terrivelmente ali - em grande parte porque uma resposta antiga, bem avaliada, mas agora desatualizada, provavelmente será editada. bash.org não permite a edição, e não está claro como você faria para editar piadas antigas sobre memes da internet agora datados, mesmo se você pudesse ... Em qualquer caso, meu ponto é que o algoritmo certo geralmente depende dos detalhes do seu problema. :-)

Eu sei que esta questão é bastante antiga, mas pensei em contribuir

Eu olharia para o sistema TrueSkill desenvolvido na Microsoft Research. É como o ELO, mas tem um tempo de convergência muito mais rápido (parece exponencial em comparação ao linear), então você obtém mais de cada votação. É, no entanto, mais complexo matematicamente.

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

Eu não gosto do estilo Hot-or-Not . Pessoas diferentes escolheriam números diferentes, mesmo se todas gostassem da imagem exatamente igual. Também odeio classificar coisas em dez, nunca sei qual número escolher.

Escolha A ou B é muito mais simples e divertido. Você consegue ver duas imagens, e são feitas comparações entre as imagens do site.

Essas equações da Wikipedia tornam mais simples / mais eficaz calcular as classificações Elo, o algoritmo para as imagens A e B seria simples:

• Obtenha Ne, mA, mB e classificações RA, RB de seu banco de dados.
• Calcule KA, KB, QA, QB usando o número de comparações realizadas (Ne) e o número de vezes que a imagem foi comparada (m) e as avaliações atuais:

• Calcule EA e EB.

• Marque o S do vencedor: o vencedor com 1, o perdedor com 0 e se você empatar com 0,5,

• Calcule as novas classificações para ambos usando:

• Atualize as novas classificações RA, RB e contagens mA, mB no banco de dados.

Você pode querer ir com uma combinação.

Primeira fase: estilo quente ou não (embora eu vá com uma votação de 3 opções: uma merda, Meh / OK. Legal!)

Depois de classificar o conjunto nos 3 baldes, eu selecionaria duas imagens do mesmo balde e diria "Qual é a melhor"

Você poderia então usar um sistema de promoção e rebaixamento do futebol inglês para mover os poucos "Sucks" principais para a região Meh / OK, a fim de refinar os casos extremos.

A classificação de 1 a 10 não funcionará, todos têm níveis diferentes. Alguém que sempre dá 3 a 7 avaliações teria sua classificação eclipsada por pessoas que sempre dão 1 ou 10.

a-ou-b é mais funcional.

Uau, estou atrasado no jogo.

Gosto muito do sistema ELO, mas, como Owen diz, parece-me que você demoraria a acumular resultados significativos.

Acredito que os humanos têm uma capacidade muito maior do que apenas comparar duas imagens, mas você deseja manter as interações ao mínimo.

Então, que tal você mostrar n imagens (sendo n qualquer número que você possa exibir visivelmente em uma tela, isso pode ser 10, 20, 30 dependendo da preferência do usuário, talvez) e fazer com que eles escolham o que acham que é melhor naquele lote. Agora, de volta ao ELO. Você precisa modificar seu sistema de classificação, mas manter o mesmo espírito. Na verdade, você comparou uma imagem a n-1 outras. Portanto, você faz sua classificação ELO n-1 vezes, mas deve dividir a mudança de classificação por n-1 para corresponder (de modo que os resultados com valores diferentes de n sejam coerentes entre si).

Você Terminou. Você agora tem o melhor de todos os mundos. Um sistema de classificação simples que trabalha com muitas imagens em um clique.

Se você preferir usar a estratégia Escolha A ou B, eu recomendaria este artigo: http://research.microsoft.com/en-us/um/people/horvitz/crowd_pairwise.pdf

Chen, X., Bennett, PN, Collins-Thompson, K., & Horvitz, E. (2013, fevereiro). Agregação de classificação em pares em um ambiente de crowdsourcing. In Proceedings of the sixth ACM International Conference on Web search and data mining (pp. 193-202). ACM.

O artigo fala sobre o modelo Crowd-BT , que estende o famoso modelo de comparação de pares de Bradley-Terry ao cenário de crowdsource. Ele também fornece um algoritmo de aprendizado adaptativo para aumentar a eficiência de tempo e espaço do modelo. Você pode encontrar uma implementação Matlab do algoritmo no Github (mas não tenho certeza se funciona).

O extinto site whatsbetter.com usava um método do estilo Elo . Você pode ler sobre o método em seu FAQ no Internet Archive .

Escolha A-ou-B é o mais simples e menos sujeito a preconceitos, no entanto, a cada interação humana, ele fornece substancialmente menos informações. Acho que por causa da redução do viés, o Pick é superior e no limite fornece a mesma informação.

Um esquema de pontuação muito simples é ter uma contagem para cada imagem. Quando alguém dá uma comparação positiva incrementa a contagem, quando alguém dá uma comparação negativa, diminui a contagem.

Classificar uma lista de 1 milhão de inteiros é muito rápido e leva menos de um segundo em um computador moderno.

Dito isso, o problema está mal colocado - você levará 50 dias para mostrar cada imagem apenas uma vez.

Aposto que você está mais interessado nas imagens com melhor classificação? Portanto, você provavelmente deseja enviesar a recuperação de sua imagem pela classificação prevista - portanto, é mais provável que mostre imagens que já alcançaram algumas comparações positivas. Desta forma, você começará a mostrar imagens 'interessantes' mais rapidamente.

Gosto da opção de classificação rápida, mas faria alguns ajustes:

• Mantenha os resultados da "comparação" em um banco de dados e faça a média deles.
• Obtenha mais de uma comparação por visualização, fornecendo ao usuário de 4 a 6 imagens e ordenando que eles as classifiquem.
• Selecione quais imagens exibir executando qsort e gravando e aparando tudo o que você não tem dados suficientes. Então, quando você tiver itens suficientes registrados, cuspa uma página.

A outra opção divertida seria usar a multidão para ensinar uma rede neural.