algorithm - Cómo clasificar un millón de imágenes con un tipo de crowdsourcing
sorting (12)
Como otros han dicho, la clasificación del 1 al 10 no funciona tan bien porque las personas tienen diferentes niveles.
El problema con el método Pick A-or es que no se garantiza que el sistema sea transitivo (A puede vencer a B, pero B late a C y C le gana a A). Tener operadores de comparación no transitivos rompe los algoritmos de clasificación . Con quicksort, contra este ejemplo, las letras no elegidas como pivote se clasificarán incorrectamente una contra la otra.
En un momento dado, desea una clasificación absoluta de todas las imágenes (incluso si algunas / todas están vinculadas). También quiere que su clasificación no cambie a menos que alguien vote .
Utilizaría el método Pick A-or-B (o empate) , pero determinaría un ranking similar al sistema de clasificación Elo que se usa para clasificaciones en juegos de 2 jugadores (originalmente ajedrez):
El sistema de clasificación de jugadores de Elo compara los registros de partidos de los jugadores con los récords de partidos de sus oponentes y determina la probabilidad de que el jugador gane el emparejamiento. Este factor de probabilidad determina cuántos puntos sube o baja la clasificación de un jugador en función de los resultados de cada partido. Cuando un jugador derrota a un oponente con una calificación más alta, la calificación del jugador aumenta más que si derrota a un jugador con una calificación más baja (ya que los jugadores deben derrotar a los oponentes que tienen calificaciones más bajas).
El sistema Elo:
- Todos los jugadores nuevos comienzan con una calificación base de 1600
- WinProbability = 1 / (10 ^ ((Clasificación actual del oponente - Calificación actual del jugador) / 400) + 1)
- ScoringPt = 1 punto si ganan el partido, 0 si pierden y 0.5 para un sorteo.
- Nueva clasificación del jugador = Calificación anterior del jugador + (Valor K * (Probabilidad de ganancia del jugador de puntuación))
Reemplace "jugadores" con imágenes y tiene una manera simple de ajustar la clasificación de ambas imágenes en función de una fórmula. A continuación, puede realizar una clasificación con esos puntajes numéricos. (K-Value aquí es el "Nivel" del torneo. Es 8-16 para torneos locales pequeños y 24-32 para invitaciones / regionales más grandes. Puede usar una constante como 20).
Con este método, solo necesita mantener un número para cada imagen que requiere mucha menos memoria que mantener los rangos individuales de cada imagen en cada otra imagen.
EDITAR: Agregó un poco más de carne en base a los comentarios.
Me gustaría clasificar una colección de imágenes de paisajes haciendo un juego en el que los visitantes del sitio puedan calificarlas, con el fin de descubrir qué imágenes las personas encuentran más atractivas.
¿Cuál sería un buen método para hacer eso?
- ¿ Estilo caliente o no ? Es decir, mostrar una sola imagen, pedirle al usuario que la clasifique del 1 al 10. Según lo veo, esto me permite promediar los puntajes, y solo necesitaría asegurarme de obtener una distribución pareja de votos en todas las imágenes. Bastante simple de implementar.
- Elija A o B ? Es decir, mostrar dos imágenes, pedirle al usuario que elija la mejor. Esto es atractivo ya que no hay una clasificación numérica, es solo una comparación. ¿Pero cómo lo implementaría? Lo primero que pensé fue hacerlo como una prueba rápida, con las operaciones de comparación provistas por humanos, y una vez completadas, simplemente repita el género ad-infinitum.
¿Cómo lo harías?
Si necesita números, estoy hablando de un millón de imágenes, en un sitio con 20,000 visitas diarias. Me imagino que una pequeña proporción podría jugar el juego, por el bien de la discusión, digamos que puedo generar 2.000 operaciones de clasificación humana por día. Es un sitio web sin fines de lucro, y los curiosos lo encontrarán en mi perfil :)
El rango 1-10 no funcionará, todos tienen diferentes niveles. Alguien que siempre da calificaciones de 3-7 tendría su clasificación eclipsada por personas que siempre dan 1 o 10.
a-or es más viable.
El sitio web difunto whatsbetter.com utiliza un método de estilo Elo . Puede leer sobre el método en sus preguntas frecuentes en el Archivo de Internet .
Es posible que desee ir con una combinación.
Primera fase: estilo Hot-or-not (aunque me gustaría ir con un voto de 3 opciones: Sucks, Meh / OK. ¡Genial!)
Una vez que haya ordenado el conjunto en los 3 cubos, seleccionaría dos imágenes del mismo cubo e iré con "Lo que es más agradable"
A continuación, puede utilizar un sistema de promoción y degradación de Soccer en inglés para mover los primeros "Sucks" a la región Meh / OK, a fin de perfeccionar los casos extremos.
Estas ecuaciones de Wikipedia hacen más simple / más efectivo para calcular las calificaciones de Elo, el algoritmo para las imágenes A y B sería simple:
- Obtenga Ne, mA, mB y clasificaciones RA, RB desde su base de datos.
- Calcule KA, KB, QA, QB usando el número de comparaciones realizadas (Ne) y el número de veces que se comparó esa imagen (m) y las clasificaciones actuales:
- Calcule EA y EB.
- Califique la S del ganador: el ganador como 1, el perdedor como 0, y si tiene un sorteo como 0.5,
Calcule las nuevas clasificaciones para ambos usando:
Actualice las nuevas clasificaciones RA, RB y cuenta mA, mB en la base de datos.
La mayoría de los enfoques ingenuos al problema tienen algunos problemas serios. Lo peor es cómo bash.org y qdb.us muestran citas: los usuarios pueden votar una cotización hacia arriba (+1) o hacia abajo (-1), y la lista de las mejores cotizaciones se ordena según el puntaje neto total. Esto tiene un sesgo de tiempo horrible: las citas antiguas han acumulado un gran número de votos positivos a través de la longevidad simple, incluso si solo son ligeramente graciosos. Este algoritmo podría tener sentido si los chistes se hicieran más divertidos a medida que envejecían, pero, créanme, no lo hacen.
Hay varios intentos para solucionar esto, mirando el número de votos positivos por período de tiempo, ponderando votos más recientes, implementando un sistema de desintegración para votos antiguos, calculando la proporción de votos positivos a negativos, etc. La mayoría sufre otros defectos.
La mejor solución, creo, es la que usan los sitios web The Funniest The Cutest , The Fairest , and Best Thing : un sistema de votación Condorcet modificado :
El sistema le da a cada uno un número basado en, de las cosas que ha enfrentado, qué porcentaje de ellas usualmente supera. De modo que cada uno obtiene el puntaje de porcentaje NumberOfThingsIBeat / (NumberOfThingsIBeat + NumberOfThingsThatBeatMe). Además, las cosas se excluyen de la lista superior hasta que se las compara con un porcentaje razonable del conjunto.
Si hay un ganador de Condorcet en el set, este método lo encontrará. Como eso es improbable, dada la naturaleza estadística, encuentra el que está "más cerca" de ser un ganador de Condorcet.
Para obtener más información sobre la implementación de dichos sistemas, la página de Wikipedia sobre pares clasificados debe ser útil.
El algoritmo requiere que las personas comparen dos objetos (su opción Pick-A-or-B), pero francamente, eso es algo bueno. Creo que está muy bien aceptado en la teoría de la decisión que los humanos son mucho mejores al comparar dos objetos que en el ranking abstracto. Millones de años de evolución nos hacen buenos para elegir la mejor manzana del árbol, pero es terrible decidir cuán cerca está la manzana que escogimos de la verdadera forma platónica de la dulzura. (Por cierto, este es el motivo por el cual el Proceso de Jerarquía Analítica es tan ingenioso ... pero eso se está alejando un poco del tema).
Un punto final es que SO usa un algoritmo para encontrar las mejores respuestas, que es muy similar al algoritmo de bash.org para encontrar la mejor oferta. Funciona bien aquí, pero falla terriblemente allí, en gran parte porque es probable que se edite una respuesta antigua, altamente calificada, pero ahora obsoleta. bash.org no permite la edición, y no está claro cómo editar chistes de hace una década acerca de los memes de Internet ahora datados, incluso si pudieras ... En cualquier caso, mi punto es que el algoritmo correcto por lo general depende de los detalles de tu problema :-)
Me gusta la opción de ordenación rápida, pero me gustaría hacer algunas tweeks:
- Mantenga los resultados de "comparación" en un DB y promedielos.
- Obtenga más de una comparación por vista dándole al usuario de 4 a 6 imágenes y haga que las ordene.
- Seleccione qué imágenes mostrar ejecutando qsort y grabando y recortando cualquier cosa en la que no tenga suficientes datos. Luego, cuando tenga suficientes elementos grabados, escupir una página.
La otra opción divertida sería usar la multitud para enseñar una red neuronal.
No me gusta el estilo Hot-or-Not . Diferentes personas elegirían números diferentes, aunque a todos les gustara la imagen exactamente igual. También odio clasificar las cosas de 10, nunca sé qué número elegir.
Pick A-or-B es mucho más simple y divertido. Puede ver dos imágenes y se realizan comparaciones entre las imágenes del sitio.
Sé que esta pregunta es bastante antigua, pero pensé que contribuiría
Vería el sistema TrueSkill desarrollado en Microsoft Research. Es como ELO pero tiene un tiempo de convergencia mucho más rápido (se ve exponencial en comparación con el lineal), por lo que obtienes más de cada voto. Sin embargo, es matemáticamente más complejo.
Si prefiere usar la estrategia Pick A o B, recomendaría este documento: http://research.microsoft.com/en-us/um/people/horvitz/crowd_pairwise.pdf
Chen, X., Bennett, PN, Collins-Thompson, K., y Horvitz, E. (2013, febrero). Agrupación de clasificación por parejas en un entorno de colaboración. En Actas de la sexta conferencia internacional de ACM sobre búsqueda web y minería de datos (pp. 193-202). ACM
El documento habla sobre el modelo Crowd-BT , que amplía el famoso modelo de comparación de pares Bradley-Terry en la configuración de fuente colectiva. También proporciona un algoritmo de aprendizaje adaptativo para mejorar la eficiencia de tiempo y espacio del modelo. Puede encontrar una implementación de Matlab del algoritmo en Github (pero no estoy seguro de si funciona).
Wow, llegué tarde al juego.
Me gusta mucho el sistema ELO, pero al igual que Owen dice que me parece que tardarías en generar resultados significativos.
Creo que los humanos tenemos una capacidad mucho mayor que la simple comparación de dos imágenes, pero queremos mantener las interacciones al mínimo.
Entonces, ¿qué tal si muestra n imágenes (n es cualquier número que pueda mostrar visiblemente en una pantalla, esto puede ser 10, 20, 30 dependiendo de la preferencia del usuario) y les pida que escojan cuál creen que es mejor en ese lote. Ahora volvemos a ELO. Necesita modificar su sistema de calificaciones, pero mantener el mismo espíritu. De hecho, ha comparado una imagen con n-1 otras. Por lo tanto, realiza su calificación ELO n-1 veces, pero debe dividir el cambio de calificación entre n-1 para que coincida (de modo que los resultados con diferentes valores de n sean coherentes entre sí).
Ya terminaste Ahora tienes lo mejor de todos los mundos. Un sistema de calificación simple que funciona con muchas imágenes en un solo clic.
Escoger A o B es el más simple y menos propenso a los prejuicios, sin embargo, en cada interacción humana, le proporciona sustancialmente menos información. Creo que debido a la reducción del sesgo, Pick es superior y en el límite le proporciona la misma información.
Un esquema de puntuación muy simple es tener un conteo para cada imagen. Cuando alguien da una comparación positiva, incremente el conteo, cuando alguien da una comparación negativa, disminuya el conteo.
Ordenar una lista de enteros de 1 millón es muy rápido y demorará menos de un segundo en una computadora moderna.
Dicho esto, el problema está bastante mal planteado: le llevará 50 días mostrar cada imagen solo una vez.
Apuesto a que estás más interesado en las imágenes mejor clasificadas. Por lo tanto, es probable que desee predisponer su recuperación de imágenes según el rango predicho, por lo que es más probable que muestre imágenes que ya hayan logrado algunas comparaciones positivas. De esta forma, más rápidamente empezarás a mostrar imágenes ''interesantes''.