Algoritmo: Pesquisa binária quando os valores são incertos

Eu preciso de um algoritmo para fazer uma pesquisa binária quando o teste em cada etapa pode dar o resultado errado.

Antecedentes: preciso colocar os alunos nos 12 níveis de dificuldade mais adequados. A abordagem atual é a força bruta e faz 60 perguntas de múltipla escolha com 4 respostas e dificuldade crescente, parando depois de três erradas e colocando o aluno no nível: floor((score - 1) / 5) + 1com um mínimo de 1.

Estamos preocupados com o fato de os clientes serem desativados quando enfrentam um teste com até 60 perguntas antes de poderem usar o programa, portanto, gostaríamos de minimizar o número de perguntas feitas no teste. Também estamos preocupados que os clientes estejam pulando o teste de colocação (porque parece longo) e abandonando o programa porque parece muito fácil.

A colocação mediana está na verdade no nível 2, então 50% dos alunos têm uma pontuação <11 (isto é, respostas <14 perguntas). Curiosamente, isso pode ser porque eles ficam entediados e param de levar as perguntas a sério (são crianças pequenas).

Solução proposta: implemente o teste como uma pesquisa binária em doze itens, começando com uma pergunta no nível de dificuldade 6/7 e prosseguindo com base em se a pergunta está certa ou errada. Em teoria, isso pode encontrar o nível de dificuldade apropriado para eles em 3-4 perguntas.

O Problema: Como você pode imaginar, a partir do teste existente, terminando apenas após três respostas erradas e usando 60 perguntas para escolher entre 12 níveis, queremos permitir que os alunos digam respostas corretas (o que devem fazer 25% do tempo) ou acidentalmente dando respostas incorretas (dedos gordos, pergunta incorreta etc). Isso é ainda mais importante com uma pesquisa binária, porque encontrar a resposta certa na primeira pergunta pode colocá-lo na metade superior dos níveis de dificuldade, mesmo se você errar todas as outras perguntas.

Então, existe um algoritmo reconhecido para uma pesquisa binária em que você não pode garantir que um teste individual seja preciso?

Ingenuamente, eu poderia tentar a melhor de 3 ou 5 perguntas em cada etapa e, como as perguntas iniciais têm um efeito maior no resultado final do que as perguntas posteriores, talvez adicione essas perguntas adicionais apenas nas etapas iniciais e não nas posteriores. Existe mais do que isso?

Trate o problema como uma matriz de probabilidades bayesianas; inicialmente, suponha que exista uma chance de 1/13 de que a criança esteja logo abaixo de cada nível e, para ser completo, uma chance de 1/13 de estar fora do topo. Então: 1) Encontre o nível mediano da sua matriz, ou seja, o nível em que a probabilidade de estar acima dela é mais próxima de 50% 2) Faça uma pergunta à criança a partir desse nível. 3) Use a regra de Bayes para atualizar a probabilidade de cada célula, assumindo uma taxa de erro de 25%. Encerre e retorne o nível mais provável quando uma célula atingir uma probabilidade suficientemente alta, ou eu acho que quando você ficar sem perguntas em um nível.

Um tratamento mais rigoroso desse algoritmo está aqui ; Eu recomendo lê-lo antes de implementar.