Diseño de clasificación por pares: elegir un gráfico para obtener clasificaciones / clasificaciones precisas

Antecedentes. Estoy escribiendo un código para la calificación semiautomática, utilizando la calificación de pares como parte del proceso de calificación. Los estudiantes reciben pares de ensayos a la vez, y los estudiantes tienen un control deslizante para elegir cuál es mejor y cuánto mejor. por ejemplo, el control deslizante podría verse así:

A---X-B

Según los resultados de la calificación de los compañeros, los ensayos se clasifican y el maestro calificará el X% superior y el X% inferior y las puntuaciones de todos los ensayos se calcularán automáticamente en función de esto. Ya he encontrado métodos para hacer este proceso de clasificación / puntuación; Esa parte funciona bien.

Mi pregunta. ¿Cómo debo seleccionar qué pares de ensayos dar a los estudiantes?

Las simulaciones sugieren que necesitamos un ensayo para ser calificado por pares al menos 3 veces, para obtener una clasificación precisa. Por lo tanto, cada ensayo debe aparecer en al menos 3 de los pares que se presentan para la calificación de pares.

Podemos pensar en esto como un problema gráfico. Piense en los ensayos como nodos. Cada borde representa un par de ensayos que se presentan durante el proceso de calificación entre pares. Los resultados de precisión anteriores sugieren que el grado de cada nodo (o de la mayoría de los nodos) debe ser al menos 3. ¿Qué tipo de gráfico debo usar? ¿Cómo debo generar el gráfico para usarlo durante la calificación entre pares?

Un desafío es que si tiene grupos en el gráfico, esto sesgará las graduaciones de pares. Por ejemplo, no querríamos que los ensayos de alta calidad fueran calificados por pares, en su mayoría en comparación con los ensayos de alta calidad, porque eso sesgaría los resultados de la clasificación por pares.

¿Qué recomendarías?

Creo que este problema podría modelarse con un gráfico no dirigido usando algo como lo siguiente:

• Comience tomando el nodo con el menor grado y vincúlelo con el siguiente
• Continúa hasta que tu título promedio sea de al menos 3
• Maximice la conectividad del nodo
• Minimiza el número de camarillas

¿Es este un buen enfoque? Si no, ¿qué recomendarías en su lugar?

Hay dos partes en esto: (a) seleccionar un gráfico ( diseño experimental ) para determinar qué pares de ensayos evaluarán los estudiantes en el proceso de calificación de pares, y (b) clasificar todos los ensayos, según las calificaciones de pares del estudiante, determinar qué maestro debe clasificar. Sugeriré algunos métodos para cada uno.

Elegir un gráfico

Planteamiento del problema. El primer paso es generar un gráfico. En otras palabras, debe seleccionar qué pares de ensayos mostrar a los estudiantes durante el ejercicio de calificación entre pares.

Solución sugerida. Para esta tarea, le sugiero que genere un gráfico aleatorio , seleccionado uniformemente al azar del conjunto de todos los gráficos de 3 regulares (simples).$G$

Justificación y detalles. Se sabe que un gráfico aleatorio regular es un buen expansor. De hecho, los gráficos regulares tienen un factor de expansión asintóticamente óptimo. Además, debido a que el gráfico es aleatorio, esto debería eliminar el riesgo de sesgar la calificación. Al seleccionar un gráfico uniforme al azar, se asegura de que su enfoque sea igualmente justo para todos los estudiantes. Sospecho que un gráfico uniforme aleatorio de 3 regulares será óptimo para sus propósitos.$d$

Esto plantea la pregunta: ¿cómo seleccionamos un gráfico 3-regular (simple) en vértices, uniformemente al azar?$n$

Afortunadamente, existen algoritmos conocidos para hacer esto. Básicamente, haces lo siguiente:

1. Crea puntos. Puedes pensar en esto como 3 copias de cada uno de los n vértices. Genere, de manera uniforme al azar, una coincidencia perfecta aleatoria en estos 3 n puntos. (En otras palabras, repita el siguiente procedimiento hasta que los 3 n puntos estén emparejados: seleccione cualquier punto sin emparejar y emparejelo con otro punto elegido uniformemente al azar del conjunto de puntos sin emparejar).$3n$$n$$3n$$3n$

2. Para cada dos puntos que coincidan con la coincidencia, dibuje un borde entre los vértices correspondientes (de los que son una copia). Esto te da un gráfico en vértices.$n$

3. A continuación, pruebe si el gráfico resultante es simple (es decir, no tiene bucles automáticos ni bordes repetidos). Si no es simple, descarte el gráfico y regrese al paso 1. Si es simple, ya ha terminado; Salida de este gráfico.

Se sabe que este procedimiento genera una distribución uniforme en el conjunto de gráficos de 3 regulares (simples). Además, se sabe que en el paso 3 tiene una probabilidad constante de aceptar el gráfico resultante, por lo que, en promedio, el algoritmo realizará ensayos, por lo que esto es bastante eficiente (por ejemplo, tiempo de ejecución polinómico).$O(1)$

He visto este enfoque acreditado a Bollobas, Bender y Canfield. El enfoque también se resume brevemente en Wikipedia . También puede encontrar una discusión en esta publicación de blog .

$n$$n$$n$

Clasificación de todos los ensayos.

Planteamiento del problema. Bien, ahora tiene un gráfico y ha presentado estos pares de ensayos (como lo indican los bordes en el gráfico) a los estudiantes para que los califiquen durante el ejercicio de calificación de pares. Tienes los resultados de cada comparación de ensayos. Ahora su tarea es inferir una clasificación lineal en todos los ensayos, para ayudarlo a determinar cuáles debe evaluar el maestro.

Solución. Le sugerí que usara el modelo Bradley-Terry . Es un enfoque matemático que resuelve exactamente este problema. Fue diseñado para clasificar jugadores en algún deporte, basado en los resultados de los partidos entre algunos pares de jugadores. Se supone que cada jugador tiene una fuerza (desconocida), que puede cuantificarse como un número real, y la probabilidad de que Alice venza a Bob está determinada por una función suave de la diferencia de sus fuerzas. Luego, dados los registros de victorias / derrotas por parejas, estima la fuerza de cada jugador.

Esto debería ser perfecto para ti. Puedes tratar cada ensayo como un jugador. Cada comparación entre dos ensayos (durante el proceso de calificación entre pares) es como el resultado de una coincidencia entre ellos. El modelo Bradley-Terry le permitirá tomar todos esos datos e inferir una fortaleza para cada ensayo, donde las fortalezas más altas corresponden a mejores ensayos. Ahora puede usar esas fortalezas para ordenar por orden todos los ensayos.

$i$$j$

Existen formas alternativas de inferir clasificaciones o clasificaciones para todos los ensayos, dados los datos que tiene. Por ejemplo, el método Elo es otro. Resumo varios de ellos en mi respuesta a una pregunta diferente ; lea esa respuesta para más detalles.

Otro comentario: el modelo Bradley-Terry supone que el resultado de cada comparación entre dos jugadores es una victoria o una pérdida (es decir, un resultado binario). Sin embargo, parece que en realidad tendrá datos más detallados: su control deslizante le dará una estimación aproximada de cuánto mejor calificó un evaluador por pares un ensayo que otro. El enfoque más simple sería simplemente asignar cada control deslizante a un resultado binario. Sin embargo, si realmente lo desea, puede utilizar todos los datos mediante un análisis más sofisticado. El modelo Bradley-Terry implica hacer una regresión logística. Si generaliza el uso de logit ordenado , apuesto a que podría aprovechar la información adicional que tiene de cada control deslizante, dado que los resultados de los controles deslizantes no son binarios, pero son una de varias posibilidades.

Uso eficiente del profesor.

Sugiere que el maestro califique manualmente el X% superior y el X% inferior de todos los ensayos (utilizando la clasificación inferida de los resultados de la calificación entre pares). Esto podría funcionar, pero sospecho que no es el uso más eficiente del tiempo limitado del maestro. En cambio, me gustaría sugerir un enfoque alternativo.

Sugiero que haga que el maestro califique un subconjunto de los ensayos, con el subconjunto cuidadosamente seleccionado para tratar de proporcionar la mejor calibración posible para todos los ensayos que no fueron calificados por el maestro. Para esto, creo que podría ayudar si seleccionara una muestra de ensayos que cubrieran el rango de respuestas posibles (por lo tanto, para cada ensayo, hay algún ensayo calificado por el maestro que no está muy lejos de él). Para esto, puedo pensar en dos enfoques que podrías considerar probar:

• $n$$k$$k$$k$

• $k$$d(e_i,e_j)$$e_i$$e_j$$S$$d(e,S) = \min_{e' \in S} d(e,e')$$e$$S$$k$$e_1,e_2,\dots,e_k$$e_{i+1}$$d(e,\{e_1,e_2,\dots,e_i\})$$e$$e \notin \{e_1,e_2,\dots,e_i\}$$k$$k$ . Por lo tanto, sería razonable que el maestro calificara los ensayos seleccionados por el algoritmo FPF.$k$

Sospecho que cualquiera de estos enfoques podría proporcionar puntajes más precisos que hacer que el maestro califique el X% superior y el X% inferior de los ensayos, ya que los mejores y peores ensayos probablemente no son representativos de la masa de ensayos en el medio.

En ambos enfoques, podría usar una función de distancia más sofisticada que tenga en cuenta no solo las estimaciones de fuerza basadas en la calificación de pares, sino también otros factores derivados de los ensayos. La función de distancia más simple posible tendría en cuenta solo el resultado del modelo de Terry-Bradley, es decir, donde es la fuerza de ensayo según lo estimado por el modelo de Terry-Bradley basado en los resultados de la clasificación por pares. Sin embargo, puedes hacer algo más sofisticado. Por ejemplo, podría calcular la distancia de edición normalizada de Levenshtein entre el ensayo y s ( e ) e e 1 e 2$d(e_1,e_2) = (s(e_1)-s(e_2))^2$$s(e)$$e$$e_1$$e_2$(tratándolos como cadenas de texto, calculando la distancia de edición y dividiendo por la longitud del mayor de los dos) y utilícelo como otro factor en la función de distancia. También podría calcular vectores de características usando un modelo de bolsa de palabras en las palabras de los ensayos, y usar la distancia L2 entre estos vectores de características (con características normalizadas usando tf-idf) como otro factor en la función de distancia. Puede usar una función de distancia que sea un promedio ponderado de la diferencia en las fuerzas (según las estimaciones de Terry-Bradley), la distancia de edición normalizada y cualquier otra cosa que parezca útil. Dicho más sofisticado podría ayudar función de distancia hacer un mejor trabajo de ayudar al algoritmo de agrupamiento seleccionar cuales son las mejores ensayos para tener el grado de maestro.$k$

algunas ideas basadas en su descripción no exactamente precisa de entradas y salidas y lo que se va a calcular (tal vez pueda revisar su pregunta con eso en mente).

Aparentemente, este es básicamente el problema "hot or not" "facemash" que se originó con la fundación de Facebook (como se describe en la película "red social"). En el "juego" original, los usuarios tenían dos imágenes y elegían entre las mujeres más atractivas. en su sistema, la elección es entre dos ensayos, uno de los cuales es mejor.

desde casi el ciber folklore, aparentemente, los algoritmos de clasificación Elo utilizados en los sistemas de puntuación de partidas de ajedrez se pueden usar para calcular una solución convergente (en este caso, básicamente, estimar la puntuación de los ensayos consistentes con el gráfico de preferencia dirigida expresado), pero aún no se ha visto un cuidadoso descripción / escritura de esto.

Otra opción es utilizar Pagerank. que calcula la influencia estimada de una página en función del gráfico de enlace dirigido. Las preferencias a los ensayos son análogas a los enlaces a una página web.

El problema también parece similar al análisis de citas donde los artículos científicos citan otros artículos y se estima la influencia de los documentos. [pero tenga en cuenta que Pagerank también es un algoritmo líder en esta área.]

[1] ¿por qué usar las clasificaciones Elo para el algoritmo facemash? desbordamiento de pila

[2] Sistema de clasificación Elo , wikipedia

[3] Pagerank , wikipedia

[4] análisis de citas , wikipedia