Deducir respuestas correctas, de exámenes de opción múltiple

Question

Estoy buscando una manera algorítmica para resolver el siguiente problema.

Problema

Decir que hemos dado un examen de opción múltiple con 100 preguntas, con 4 respuestas por pregunta (exactamente uno de los cuatro está correcto), correctamente cada respuesta vale un punto, respuesta incorrecta vale cero puntos. Si ahora tenemos una base de datos D de un montón de hojas de respuesta y sus correspondientes puntos, por ejemplo,

D:= { ('ABAA...', 80), ('ABAB...', 80), ('ABAC...', 80), ('ABAD...', 81), ... }

¿Cómo podemos saber que las respuestas son correctas? No estoy buscando algo probabilístico, pero las respuestas que son sin duda correcta.

Algunas ideas

Hay algunas estrategias obvias como:

• busque a alguien que alcanzó los 100 puntos; tienes todas tus respuestas
• buscar pruebas, cuyas respuestas se diferencian sólo por uno (en el ejemplo de base de datos dada, podemos deducir la respuesta a la pregunta 4 "D")
• busque a alguien que respondió todo mal, puede descartar las respuestas a esas preguntas

Pero ¿qué información podemos obtener de otras combinaciones de respuestas?

La visualización de las hojas de respuesta como un espacio métrico tenemos

100 - S(prueba) = d(prueba, correcto)

para la distancia de hamming d(.,.), la puntuación de S(.) y la hoja correcta correcta.

Tal vez alguien me podría dar una reformulación del problema, lo que produce un mayor aplicación obvia. Cualquier aporte es apreciado.

Editar:

No teniendo en cuenta la complejidad del cálculo, no puedo lograr algo por la intersección de las bolas $$ \bigcap_i B_{d(t_i,\textrm{correcto})}(t_i), $$ con las pruebas de $t_i$ y bolas $B_d(x) := \{y: d(x,y)\leq d\}$?

Answer 1

Actualización:

Hoy en día, como yo estaba mirando a través de algunas de las interesantes matemáticas/problemas de programación en projecteuler, me di cuenta de Número de la Mente (el problema número 185), y de inmediato me recordó a la de matemáticas.SE pregunta; ellos son prácticamente equivalentes. La búsqueda de una solución a la projectuler problema, he encontrado una solución (escrito en python) de un sitio de la hermana: codereview.SE. (En realidad no lo he leído).

Lo que sigue es lo que originalmente publicado.

Algunas Observaciones:

1. Según la base de datos D, no puede ser capaz de determinar las respuestas correctas. Por ejemplo, si la pregunta número 100 es muy complicado y como resultado, todo el mundo elige C o D, aunque la respuesta correcta es A, entonces no podemos determinar la respuesta correcta.

2. Vamos a corregir algunas anotaciones: Vamos a $\mathcal{A}$ ser las respuestas correctas y $\mathcal{\hat{A}}$ ser algunos de adivinar de $\mathcal{A}$. (Así que ambos son cadenas, 100 letras de largo.) Deje $t_i$ ser una prueba cuyo resultado actual es de 85; decir $S_{\mathcal{A}}(t_i) = 85$. Además, vamos a suponer que si nos recalificación de la $t_i$ según $\mathcal{\hat{A}}$, podemos obtener una nueva puntuación $S_{\mathcal{\hat{A}}}(t_i) = 90$. Entonces tenemos límites inferior y superior para $d(\mathcal{A},\mathcal{\hat{A}})$ = el número de letras que se diferencian: $$5=|90-85| \leq d(\mathcal{A},\mathcal{\hat{A}}) \leq (100-85) + (100-90) = 25.$$ La primera desigualdad se cumple debido a que la prueba de $t_i$ se clasifica incorrectamente $\mathcal{\hat{A}}$ durante al menos 5 preguntas. El segundo es el triángulo de la desigualdad; $d(\mathcal{A},\mathcal{\hat{A}}) \leq d(\mathcal{A},t_i) + d(t_i,\mathcal{\hat{A}})$. (Observe que $d(\mathcal{A},t_i) = 100 - S_{\mathcal{A}}(t_i)$ etc.) La segunda desigualdad es óptimo, ya que podemos imaginar todos los 15 de respuestas incorrectas de $t_i$ se consideran correctas ( $\mathcal{\hat{A}}$ ) y de 10 de sus respuestas correctas a ser contados como incorrecta (por $\mathcal{\hat{A}}$).

Answer 2

El grado de cada uno es una función lineal de las alternativas seleccionadas (coeficiente es 0 para una alternativa incorrecta, 1 para el derecho). Dada la combinación correcta de documentos clasificados, tienen todos coeficientes y, por tanto, respuestas correctas todas. Visto de esta forma, es una cuestión de independencia lineal del conjunto de papeles.

Tal vez este ataque como un ANOVA (regresión lineal multivariable) resulta útil.

Answer 3

Aquí es lo que tengo hasta el momento. Me dio un poco de pensamiento y a mí me parece, que el problema es muy similar a la de un la trilateración problema .

Así que lo que mi primera aproximación es, es cruzan todas las esferas $S_d(x) := \{y: d(x,y)= d\}$ $x$ siendo una prueba y $d$ de los puntos que falten para una puntuación perfecta.

Por razones obvias no funcionan bien para la cantidad de preguntas que originalmente iba, pero para un pequeño número de preguntas parece que funciona.

Código

Aquí está el código de python hice programa para el cálculo de $$ \bigcap_i S_{d(t_i,\textrm{correcto})}(t_i): $$

import itertools
import random

def hammingDistance(s1, s2):
    assert len(s1) == len(s2)
    return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))

def hammingSphere(word, distance, alphabet):
    positions = itertools.combinations(range(len(word)), distance)
    for pos in positions:
        letterCombinations = itertools.product(alphabet, repeat=distance)
        for letters in letterCombinations:
            tmp = list(word[:])
            for i,l in zip(pos, letters):
                if tmp[i] == l:
                    break
                else:
                    tmp[i] = l
            else:
                yield tuple(tmp)


def findPossiblyCorrectAnswers(tests, choices):
    bestTest = max(tests, key=lambda x: x[1])
    maxPoints = len(bestTest[0])
    possibleAnswers = set(hammingSphere(bestTest[0], maxPoints-bestTest[1], choices))
    for test in tests:
        possibleAnswers = possibleAnswers.intersection(set(hammingSphere(test[0], maxPoints-test[1], choices)))
    return possibleAnswers

def remainingOptions(tests, choices):
    return [set(x) for x in zip(*findPossiblyCorrectAnswers(tests, choices))]

def buildTests(correct, alphabet, numTest):
    tests = []
    maxPoints = len(correct)
    for i in range(numTest):
        tests.append([random.choice(alphabet) for _ in range(len(correct))])
    return [(t, maxPoints-hammingDistance(t, correct)) for t in tests]

### TESTING:

correct = "AAAAAAAA" # The correct answer
choices = "ABCD"
numTests = 8
tests = buildTests(correct, choices, numTests) # Build some tests with known correct answer sheet
print(tests) # Display the test database
print(remainingOptions(tests, choices)) # Display remaining choices

Resultados

Se produce la siguiente salida

[(['B', 'A', 'C', 'C', 'C', 'B', 'D', 'A'], 2),
(['C', 'D', 'C', 'B', 'C', 'B', 'A', 'C'], 1),
(['B', 'C', 'D', 'D', 'C', 'D', 'C', 'C'], 0),
(['C', 'D', 'C', 'A', 'D', 'D', 'D', 'C'], 1),
(['A', 'C', 'D', 'C', 'D', 'B', 'A', 'B'], 2),
(['C', 'C', 'D', 'B', 'A', 'B', 'A', 'C'], 2),
(['A', 'A', 'D', 'D', 'B', 'C', 'D', 'B'], 2),
(['C', 'B', 'D', 'B', 'A', 'A', 'D', 'D'], 2)]

[set(['A']), set(['A']), set(['A', 'B']), set(['A']), set(['A']), set(['A', 'B']), set(['A', 'B']), set(['A', 'D'])]

Que son el llenado de las pruebas y sus resultados, así como de los conocimientos acerca de las soluciones.

Así que para ocho personas al azar responder a una prueba de selección múltiple con ocho preguntas, un buen montón de información que se puede extraer de ella.