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:

A---X-B

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.

O que você recomendaria?

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?

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.

Escolhendo um gráfico

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).$G$

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.$d$

Isso levanta a questão: como podemos selecionar um gráfico 3-regular (simples) em vértices, uniformemente aleatoriamente?$n$

Felizmente, existem algoritmos conhecidos para fazer isso. Basicamente, você faz o seguinte:

1. 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.)$3n$$n$$3n$$3n$

2. 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.$n$

3. 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.

$O(1)$

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 .

$n$$n$$n$

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.

$i$$j$

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:

• $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$, Como segue:$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$

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(e_1,e_2) = (s(e_1)-s(e_2))^2$$s(e)$$e$$e_1$$e_2$$k$

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

[3] Pagerank , wikipedia

[4] análise de citação , wikipedia