Design de classificação por pares - escolha de um gráfico para obter classificações / classificações precisas
Fundo.Estou escrevendo um código para a classificação semi-automática, usando a classificação por pares como parte do processo de classificação. Os alunos recebem pares de ensaios de cada vez, e os alunos têm um controle deslizante para escolher qual é o melhor e o quanto é melhor. por exemplo, o controle deslizante pode ser algo como isto:
Com base nos resultados da classificação pelos pares, os ensaios são classificados e o professor classifica os X% superiores e os X% inferiores e as pontuações para todos os ensaios serão calculadas automaticamente com base nisso. Eu já criei métodos para fazer esse processo de classificação / pontuação; essa parte funciona bem.
Minha pergunta. Como devo selecionar quais pares de ensaios dar aos alunos?
As simulações sugerem que precisamos de um ensaio para ser avaliado por pares pelo menos três vezes, para obter uma classificação precisa. Assim, cada ensaio deve aparecer em pelo menos 3 dos pares apresentados para classificação por pares.
Podemos pensar nisso como um problema gráfico. Pense nos ensaios como nós. Cada aresta representa um par de ensaios que são apresentados durante o processo de classificação por pares. Os resultados de precisão acima sugerem que o grau de cada nó (ou da maioria dos nós) deve ser pelo menos 3. Que tipo de gráfico devo usar? Como devo gerar o gráfico para ser usado durante a classificação por pares?
Um desafio é que, se você tiver clusters no gráfico, isso distorcerá as classificações dos pares. Por exemplo, não gostaríamos de ter ensaios de alta qualidade com classificação por pares, principalmente contra ensaios de alta qualidade, porque isso distorceria os resultados da classificação por pares.
Eu acho que esse problema pode ser modelado com um gráfico não direcionado usando algo como o seguinte:
Comece pegando o nó com o menor grau e vinculando-o ao próximo menos
Continue até que seu diploma médio seja pelo menos 3
Maximizar a conectividade do nó
Minimize o número de panelinhas
Será esta uma boa abordagem? Se não, o que você recomendaria?
Esta pode ser uma aplicação interessante para expansores . Você já tentou organizar as atribuições em um expansor?
sua idéia de arestas parece meio certa. as arestas indicam apenas uma comparação, não o resultado de uma comparação. portanto, apenas a presença / ausência de arestas não codifica muita informação, apenas as comparações que ocorreram. uma maneira natural de lidar com o problema envolve arestas ponderadas / direcionadas onde a direção é, por exemplo, em direção ao favorecido ... parece ser semelhante a um problema de fluxo ... você diz "controle deslizante", é de valores múltiplos? ou binário? "slider" parecia multivalorado para mim, como uma classificação.
Você pode esclarecer qual é a sua pergunta? Você está perguntando sobre como escolher o gráfico? Ou você está perguntando sobre, dado um gráfico e um conjunto de classificações para cada margem, como classificar todos os ensaios? O primeiro se enquadra na categoria geral de "desenho experimental" (e minha resposta o aborda); o último, na categoria geral de "análise de dados" (e tanto a minha resposta quanto a resposta de vzn fornecem alguns recursos úteis para isso).
Na verdade, tínhamos elaborado o ranking e a pontuação, mas tentaremos a abordagem abaixo.
— Is13 dez13
em algumas análises de problemas semelhantes, as palavras "classificação" e "pontuação" são intercambiáveis. agora aparece em outras revisões e edições, em seu sistema, você se refere a "classificação" como a estimativa baseada em computador de uma classificação com base nos dados de comparação e a "pontuação" como a decisão subjetiva baseada em humanos sobre a qualidade do ensaio (também geralmente chamado de "classificação") que segue o processo de classificação. & Você está interessado principalmente na distribuição dos pares de comparação ...
Existem duas partes para isso: (a) selecionar um gráfico ( desenho experimental ) para determinar quais pares de ensaios os alunos avaliarão no processo de classificação por pares; e (b) classificar todos os ensaios, com base nas notas dos pares, para determinar qual o professor deve classificar. Vou sugerir alguns métodos para cada um.
Declaração do problema. O primeiro passo é gerar um gráfico. Em outras palavras, você precisa selecionar quais pares de ensaios serão exibidos aos alunos durante o exercício de classificação por pares.
Solução sugerida. Para esta tarefa, sugiro que você gere um gráfico aleatório , selecionado uniformemente aleatoriamente no conjunto de todos os gráficos tridimensionais (simples).GG
Justificação e detalhes. Sabe-se que um gráfico regular aleatório é um bom expansor. De fato, os gráficos regulares têm fator de expansão assintoticamente ideal. Além disso, como o gráfico é aleatório, isso deve eliminar o risco de distorcer a classificação. Ao selecionar um gráfico uniformemente aleatoriamente, você garante que sua abordagem seja igualmente justa para todos os alunos. Suspeito que um gráfico 3-regular uniformemente aleatório seja ideal para seus propósitos.dd
Isso levanta a questão: como podemos selecionar um gráfico 3-regular (simples) em vértices, uniformemente aleatoriamente?nn
Felizmente, existem algoritmos conhecidos para fazer isso. Basicamente, você faz o seguinte:
Crie pontos. Você pode pensar nisso como 3 cópias de cada um dos n vértices. Gere, uniformemente aleatoriamente, uma correspondência perfeita aleatória nesses 3 n pontos. (Em outras palavras, repita o procedimento a seguir até que todos os 3 pontos n estejam emparelhados: selecione qualquer ponto não emparelhado e emparelhe-o com outro ponto escolhido uniformemente aleatoriamente no conjunto de pontos não emparelhados.)3 n3nnn3 n3n3 n3n
Para cada dois pontos correspondentes à correspondência, desenhe uma aresta entre os vértices correspondentes (dos quais são uma cópia). Isso fornece um gráfico em vértices.nn
Em seguida, teste se o gráfico resultante é simples (ou seja, não possui auto-loops nem arestas repetidas). Se não for simples, descarte o gráfico e volte para a etapa 1. Se for simples, você terminou; imprima este gráfico.
Eu vi essa abordagem creditada a Bollobas, Bender e Canfield. A abordagem também é resumida brevemente na Wikipedia . Você também pode encontrar uma discussão nesta postagem do blog .
Classificação de todos os ensaios
Declaração do problema. OK, agora você tem um gráfico e apresentou esses pares de ensaios (conforme indicado pelas bordas do gráfico) aos alunos para que eles classifiquem durante o exercício de classificação por pares. Você tem os resultados de cada comparação de ensaios. Agora, sua tarefa é inferir uma classificação linear em todos os ensaios, para ajudá-lo a determinar quais os que o professor deve avaliar.
Solução. Sugeri que você usasse o modelo Bradley-Terry . É uma abordagem matemática que resolve exatamente esse problema. Foi projetado para classificar jogadores em algum esporte, com base nos resultados de partidas entre alguns pares de jogadores. Ele assume que cada jogador possui uma força (desconhecida), que pode ser quantificada como um número real, e a probabilidade de Alice vencer Bob é determinada por alguma função suave da diferença de suas forças. Então, dados os registros de ganhos / perdas em pares, ele estima a força de cada jogador.
Isso deve ser perfeito para você. Você pode tratar cada ensaio como um jogador. Cada comparação entre dois ensaios (durante o processo de classificação por pares) é como o resultado de uma correspondência entre eles. O modelo de Bradley-Terry permitirá que você pegue todos esses dados e inferir uma força para cada ensaio, onde forças mais altas correspondem a melhores ensaios. Agora você pode usar esses pontos fortes para classificar todos os ensaios.
EuEujj
Existem maneiras alternativas de inferir classificações ou classificações para todos os ensaios, dados os dados que você possui. Por exemplo, o método Elo é outro. Resumo vários deles na minha resposta a uma pergunta diferente ; leia essa resposta para mais detalhes.
Outro comentário: O modelo de Bradley-Terry assume que o resultado de cada comparação entre dois jogadores é uma vitória ou uma perda (ou seja, um resultado binário). No entanto, parece que você realmente terá dados mais detalhados: seu controle deslizante fornecerá uma estimativa aproximada de quanto melhor o aluno classificou um ensaio do que outro. A abordagem mais simples seria apenas mapear cada controle deslizante para um resultado binário. No entanto, se você realmente quiser, poderá usar todos os dados usando uma análise mais sofisticada. O modelo de Bradley-Terry envolve fazer regressão logística. Se você generaliza isso para usar o logit ordenado , aposto que você poderia tirar proveito das informações extras que você tem de cada controle deslizante, já que os resultados dos controles deslizantes não são binários, mas são uma das várias possibilidades.
Uso eficiente do professor
Você sugere que o professor classifique manualmente o X% superior e o X% inferior de todos os ensaios (usando a classificação deduzida dos resultados da classificação por pares). Isso poderia funcionar, mas suspeito que não seja o uso mais eficiente do tempo limitado do professor. Em vez disso, gostaria de sugerir uma abordagem alternativa.
Sugiro que você classifique o professor em um subconjunto dos ensaios, com o subconjunto cuidadosamente selecionado para tentar fornecer a melhor calibração possível para todos os ensaios que não foram classificados pelo professor. Para isso, acho que pode ajudar se você selecionar uma amostra de ensaios que cubram a gama de respostas possíveis (portanto, para cada ensaio, há algum ensaio com classificação de professor que não está muito longe disso). Para isso, posso pensar em duas abordagens que você poderia considerar tentar:
kkd( eEu, ej)d(eEu,ej)eEueEuejejSSd( e , S) = mine′∈ Sd( e , e′)d(e,S)=mine′∈Sd(e,e′)eeSSkke1 1, e2, … , Eke1 1,e2,…,ek, Como segue:ei + 1eEu+1 1d( e , { e1 1, e2, … , EEu} )d(e,{e1 1,e2,…,eEu})eee ∉ { e1 1, e2, … , EEu}e∉{e1 1,e2,…,eEu}kkkkkk
Suspeito que qualquer uma dessas abordagens possa fornecer pontuações mais precisas do que fazer com que o professor classifique os X% superiores e os X% inferiores dos ensaios - uma vez que os melhores e os piores ensaios provavelmente não são representativos da massa de ensaios no meio.
d( e1 1, e2) = ( s ( e1 1) - s ( e2) )2d(e1 1,e2)=(s(e1 1)-s(e2))2s ( e )s(e)eee1 1e1 1e2e2kk
difícil de seguir em relação à declaração original do problema. você está resolvendo o problema de distribuir comparações uniformemente?
@ vzn, editei minha resposta para esclarecer. A pergunta parece estar se perguntando sobre como selecionar o gráfico, ou seja, quais pares de ensaios pedir aos alunos que comparem durante a avaliação por pares. A primeira metade da minha resposta fornece uma solução para essa pergunta. A segunda parte da minha resposta descreve como usar os resultados da classificação por pares para classificar todos os ensaios, para ajudar o professor a selecionar quais ensaios classificar.
algumas idéias baseadas em sua descrição não exata de entradas e saídas e no que deve ser calculado (talvez você possa revisar sua pergunta com isso em mente).
aparentemente, esse é basicamente o problema "quente ou não" "facemash" que se originou com a fundação do Facebook (como retratado no filme "rede social"). no "jogo" original, os usuários tinham duas fotos e escolheram entre as mais atraentes. no seu sistema, a escolha é entre dois ensaios, um dos quais é melhor.
do folclore quase cibernético, aparentemente, os algoritmos de classificação Elo usados ​​nos sistemas de pontuação de xadrez podem ser usados ​​para calcular uma solução convergente (nesse caso, basicamente, estimar a pontuação dos ensaios de acordo com o gráfico de preferência direcionado expresso), mas ainda não foi visto um cuidadoso descrição / redação disso.
outra opção é usar o Pagerank. que calcula a influência estimada de uma página com base no gráfico de links direcionados. as preferências dos ensaios são análogas aos links para uma página da web.
o problema também parece semelhante à análise de citações, onde artigos científicos citam outros artigos e a influência dos artigos é estimada. [mas observe que o Pagerank também é um algoritmo líder nessa área.]
[1] por que usar os rankings Elo para o algoritmo facemash? stackoverflow
[2] Sistema de classificação Elo , wikipedia
[4] análise de citação , wikipedia
esboço de como aplicar o Elo: as partidas do jogo são como comparações de ensaios. os ensaios têm pontuações e os ensaios com pontuação mais alta devem ganhar mais partidas. o algoritmo calcula pontuações mais consistentes com todas as correspondências.
observe que as idéias de citação tendem a supor que todas as comparações são distribuídas de maneira uniforme em todos os ensaios; caso contrário, se um ensaio estiver em mais comparações, poderá aumentar sua favorabilidade relativa. por isso parte dessa abordagem também é equilibrar as comparações fora, o que você parece estar se referindo, e é semelhante ao problema de tentar distribuir jogos sobre todos os jogadores ...