Conception de la notation par les pairs - choisir un graphique pour obtenir des classements / évaluations précis

Contexte. J'écris du code pour le classement semi-automatisé, en utilisant le classement par les pairs dans le cadre du processus de classement. Les étudiants reçoivent des paires d'essais à la fois, et les étudiants ont un curseur pour choisir lequel est le meilleur et combien il est meilleur. par exemple, le curseur pourrait ressembler à ceci:

A---X-B

Sur la base des résultats de la notation par les pairs, les essais sont classés et l'enseignant notera ensuite les X% supérieurs et les X% inférieurs et les scores pour tous les essais seront automatiquement calculés en fonction de cela. J'ai déjà trouvé des méthodes pour faire ce processus de classement / notation; cette partie fonctionne bien.

Ma question. Comment dois-je sélectionner les paires d'essais à remettre aux étudiants?

Les simulations suggèrent que nous avons besoin d'un essai pour être évalué par les pairs au moins 3 fois, pour obtenir un classement précis. Ainsi, chaque essai doit apparaître dans au moins 3 des paires présentées pour la notation par les pairs.

Nous pouvons considérer cela comme un problème de graphe. Considérez les essais comme des nœuds. Chaque bord représente une paire d'essais qui sont présentés au cours du processus de notation par les pairs. Les résultats de précision ci-dessus suggèrent que le degré de chaque nœud (ou de la plupart des nœuds) devrait être d'au moins 3. Quel type de graphique dois-je utiliser? Comment générer le graphique à utiliser lors de la notation par les pairs?

Un défi est que si vous avez des grappes dans le graphique, cela faussera les notes des pairs. Par exemple, nous ne voudrions pas que les essais de haute qualité soient notés par les pairs principalement par rapport aux essais de haute qualité, car cela fausserait les résultats de la notation par les pairs.

Que recommanderais-tu?

Je pense que ce problème pourrait être modélisé avec un graphique non orienté en utilisant quelque chose comme ce qui suit:

• Commencez par prendre le nœud avec le moindre degré et liez-le au moins suivant
• Continuez jusqu'à ce que votre diplôme moyen soit d'au moins 3
• Maximisez la connectivité des nœuds
• Minimiser le nombre de cliques

Est-ce une bonne approche? Sinon, que recommanderiez-vous à la place?

Il y a deux parties: (a) sélectionner un graphique ( conception expérimentale ) pour déterminer quelles paires d'essais les étudiants évalueront dans le processus de notation par les pairs, et (b) classer tous les essais, en fonction des notes de leurs pairs, pour déterminer quel enseignant devrait se classer. Je vais suggérer quelques méthodes pour chacun.

Choisir un graphique

Énoncé du problème. La première étape consiste à générer un graphique. En d'autres termes, vous devez sélectionner les paires d'essais à montrer aux étudiants pendant l'exercice de notation par les pairs.

Solution suggérée. Pour cette tâche, je vous suggère de générer un graphe aléatoire $G$ , sélectionné uniformément au hasard dans l'ensemble des 3 graphes (simples) réguliers.

Justification et détails. On sait qu'un d aléatoire$d$ graphe -Regular est un bon expandeur. En fait, les graphiques réguliers ont un facteur d'expansion asymptotiquement optimal. De plus, comme le graphique est aléatoire, cela devrait éliminer le risque de biaiser le classement. En sélectionnant un graphique uniformément au hasard, vous vous assurez que votre approche est également équitable pour tous les élèves. Je soupçonne qu'un graphique à 3 intervalles uniformément aléatoire sera optimal pour vos besoins.

Cela soulève la question: comment sélectionner un graphique (simple) à 3 intervalles réguliers sur $n$ sommets, uniformément au hasard?

Heureusement, il existe des algorithmes connus pour ce faire. Fondamentalement, vous procédez comme suit:

1. Créez points. Vous pouvez penser à cela comme 3 copies de chacun des n sommets. Générez, uniformément au hasard, une correspondance parfaite aléatoire sur ces 3 n points. (En d'autres termes, répétez la procédure suivante jusqu'à ce que les 3 n points soient associés: sélectionnez n'importe quel point non apparié et associez-le à un autre point choisi uniformément au hasard dans l'ensemble des points non appariés.)$3n$$n$$3n$$3n$

2. Pour chacun des deux points correspondant à la correspondance, tracez un bord entre les sommets correspondants (dont ils sont une copie). Cela vous donne un graphique sur sommets.$n$

3. Ensuite, testez si le graphique résultant est simple (c.-à-d. Qu'il n'a pas de boucles automatiques et pas d'arêtes répétées). Si ce n'est pas simple, jetez le graphique et revenez à l'étape 1. Si c'est simple, vous avez terminé; sortie ce graphique.

On sait que cette procédure génère une distribution uniforme sur l'ensemble des 3 graphes (simples) réguliers. De plus, il est connu qu'à l'étape 3, vous avez une probabilité constante d'accepter le graphique résultant, donc en moyenne l'algorithme fera $O(1)$ essais - c'est donc assez efficace (par exemple, le temps d'exécution polynomial).

J'ai vu cette approche attribuée à Bollobas, Bender et Canfield. L'approche est également résumée brièvement sur Wikipédia . Vous pouvez également trouver une discussion sur ce billet de blog .

Techniquement parlant, cela nécessite que le nombre soit pair (sinon il n'y a pas de graphe 3-régulier sur n sommets). Cependant, cela est facile à gérer. Par exemple, si $n$$n$$n$ est impair, vous pouvez choisir au hasard un essai, le mettre de côté, générer un graphique aléatoire à 3 intervalles sur les essais restants, puis ajouter 3 autres bords de l'essai mis de côté à 3 autres essais choisis au hasard. (Cela signifie qu'il y aura 3 essais qui sont en fait notés 4 fois, mais cela ne devrait pas faire de mal.)

Classement de tous les essais

Énoncé du problème. OK, alors maintenant vous avez un graphique, et vous avez présenté ces paires d'essais (comme indiqué par les bords du graphique) aux élèves pour qu'ils les notent pendant l'exercice de notation par les pairs. Vous avez les résultats de chaque comparaison d'essais. Maintenant, votre tâche est d'inférer un classement linéaire sur tous les essais, pour vous aider à déterminer lesquels faire évaluer par l'enseignant.

Solution. Je vous ai suggéré d'utiliser le modèle Bradley-Terry . C'est une approche mathématique qui résout exactement ce problème. Il a été conçu pour classer les joueurs dans certains sports, sur la base des résultats des matchs entre certaines paires de joueurs. Il suppose que chaque joueur a une force (inconnue), qui peut être quantifiée comme un nombre réel, et la probabilité qu'Alice bat Bob est déterminée par une fonction lisse de la différence de leurs forces. Puis, compte tenu des records de gains / pertes par paire, il estime la force de chaque joueur.

Cela devrait être parfait pour vous. Vous pouvez traiter chaque essai comme un joueur. Chaque comparaison entre deux essais (pendant le processus de notation par les pairs) est comme le résultat d'une correspondance entre eux. Le modèle Bradley-Terry vous permettra de prendre toutes ces données et de déduire une force pour chaque essai, où des forces plus élevées correspondent à de meilleurs essais. Vous pouvez maintenant utiliser ces points forts pour classer tous les essais.

$i$$j$

Il existe d'autres façons d'inférer les notes ou les classements pour tous les essais, compte tenu des données dont vous disposez. Par exemple, la méthode Elo en est une autre. J'en résume plusieurs dans ma réponse à une question différente ; lisez cette réponse pour plus de détails.

Un autre commentaire: le modèle Bradley-Terry suppose que le résultat de chaque comparaison entre deux joueurs est une victoire ou une perte (c'est-à-dire un résultat binaire). Cependant, il semble que vous disposerez en fait de données plus détaillées: votre curseur donnera une estimation approximative de la façon dont le correcteur a évalué un essai par rapport à un autre. L'approche la plus simple serait de simplement mapper chaque curseur sur un résultat binaire. Cependant, si vous le voulez vraiment, vous pourrez peut-être utiliser toutes les données, en utilisant une analyse plus sophistiquée. Le modèle Bradley-Terry consiste à effectuer une régression logistique. Si vous généralisez cela pour utiliser le logit commandé , je parie que vous pourriez tirer parti des informations supplémentaires que vous avez de chaque curseur, étant donné que les résultats des curseurs ne sont pas binaires mais sont l'une des nombreuses possibilités.

Utilisation efficace de l'enseignant

Vous proposez à l'enseignant de noter manuellement les X% supérieurs et les X% inférieurs de tous les essais (en utilisant le classement déduit des résultats de la notation par les pairs). Cela pourrait fonctionner, mais je soupçonne que ce n'est pas l'utilisation la plus efficace du temps limité de l'enseignant. J'aimerais plutôt suggérer une autre approche.

Je suggère que l'enseignant note un sous-ensemble des essais, le sous-ensemble étant soigneusement sélectionné pour essayer de fournir le meilleur étalonnage possible pour tous les essais qui n'ont pas été notés par l'enseignant. Pour cela, je pense que cela pourrait aider si vous avez sélectionné un échantillon d'essais couvrant la gamme des réponses possibles (donc pour chaque essai, il y a un essai évalué par l'enseignant qui n'est pas trop loin). Pour cela, je peux penser à deux approches que vous pourriez envisager d'essayer:

• $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$$k$

Je soupçonne que l'une ou l'autre de ces approches pourrait fournir des scores plus précis que de demander au professeur de classer les X% supérieurs et les X% inférieurs des essais - car les meilleurs et les pires essais ne sont probablement pas représentatifs de la masse des essais au milieu.

$d(e_1,e_2) = (s(e_1)-s(e_2))^2$$s(e)$$e$$e_1$$e_2$(en les traitant comme des chaînes de texte, en calculant la distance d'édition et en les divisant par la longueur de la plus grande des deux) et utilisez-les comme un autre facteur dans la fonction de distance. Vous pouvez également calculer des vecteurs de caractéristiques en utilisant un modèle de sac de mots sur les mots dans les essais, et utiliser la distance L2 entre ces vecteurs de caractéristiques (avec des caractéristiques normalisées à l'aide de tf-idf) comme un autre facteur de la fonction de distance. Vous pouvez utiliser une fonction de distance qui est une moyenne pondérée de la différence des forces (basée sur les estimations de Terry-Bradley), la distance d'édition normalisée et tout ce qui semble utile. Une telle fonction de distance plus sophistiquée pourrait aider à mieux aider l'algorithme de clustering à sélectionner les meilleurs$k$

quelques idées basées sur votre description pas exactement précise des entrées et sorties et de ce qui doit être calculé (vous pouvez peut-être réviser votre question en gardant cela à l'esprit).

apparemment, c'est fondamentalement le problème "chaud ou pas" "facemash" qui a pris naissance avec la fondation de Facebook (comme décrit dans le film "réseau social"). dans le "jeu" original, les utilisateurs disposaient de deux images et choisissaient entre les femmes les plus attirantes. dans votre système, le choix est entre deux essais, dont l'un est meilleur.

à partir d'un cyber-folklore proche, des algorithmes de classement Elo apparemment utilisés dans les systèmes de score de match d'échecs peuvent être utilisés pour calculer une solution convergente (dans ce cas, estimer fondamentalement le score des essais conformément au graphique de préférence dirigé exprimé), mais n'ont pas encore vu attentivement description / résumé de ceci.

une autre option consiste à utiliser Pagerank. qui calcule l'influence estimée d'une page sur la base du graphique de lien dirigé. les préférences des essais sont analogues aux liens vers une page Web.

le problème semble également similaire à l'analyse des citations où les articles scientifiques citent d'autres articles et l'influence des articles est estimée. [mais notez que Pagerank est également un algorithme de pointe dans ce domaine.]

[1] pourquoi utiliser les classements Elo pour l'algorithme de facemash? stackoverflow

[2] Système de classement Elo , wikipedia

[3] Pagerank , wikipedia

[4] analyse des citations , wikipedia