Ad verba per numeros

Más evaluación...
Parametrización mediante AG
Friday, May 11, 2007, 01:22 PM
Manuel está trabajando en la "hibridación" de dos proyectos bastante distintos: un sistema para la extracción de palabras clave y un framework de algoritmos genéticos, os preguntaréis ¿para qué?

La respuesta es simple, el primer proyecto tiene una cantidad importante de parámetros que puede configurar el usuario, dependiendo de cómo se establezcan estos parámetros los resultados cambian; sin embargo, a priori no se puede saber cuáles son los adecuados; además, ¿adecuados para qué idioma? ¿Para qué temas?

El segundo proyecto permite encontrar soluciones para problemas que "típicamente" se resuelven mediante AGs. ¿Qué tipo de problemas son estos? Aquellos en los que el espacio de soluciones es muy grande, no hay un método "procedural" conocido para encontrar una solución óptima pero es relativamente sencillo diferenciar una solución "buena" de una "mala", dicho de otro modo, se dispone de una función para calcular la bondad (fitness) de las soluciones.

Así, la idea es buscar automáticamente parámetros para el sistema de extracción de palabras clave que den buenos resultados. Buenos resultados que, obviamente, serán buenos si "coinciden" con palabras clave obtenidas por otros medios (humanos o automáticos) y así llegamos al meollo del asunto (y pregunta de Manuel) que es el modo en que podemos evaluar semejante sistema.

Supongamos que para un documento dado el sistema a evaluar proporciona las siguientes palabras clave ordenadas de mayor a menor "importancia":

recombination
evolutionary
mutation
satisfactory
algorithms
Genetic
population
individual
solutions
generations
Además, para ese documento tenemos un archivo con el que comparar la salida del sistema a evaluar, la denominada ground-truth; en este caso:
genetic
algorithm
solution
optimization
population
evolution
fitness
Dados ambos ficheros es posible calcular en primer lugar la precisión de la solución, es decir, cuántos de los resultados que proporcionó son "válidos". Hay que decir, sin embargo, que la precisión habría que calcularla en distintos "puntos", en este caso, para cada palabra:
recombination	0/1 = 0%
evolutionary	0/2 = 0%
mutation	0/3 = 0%
satisfactory	0/4 = 0%
algorithms	0/5 = 0%
Genetic		0/6 = 0%
population	1/7 = 14,3%
individual	1/8 = 12,5%
solutions	1/9 = 11,1%
generations	1/10 = 10%
Sí, ya sé que algorithms y algorithm son básicamente la "misma palabra" y lo mismo solutions y solution, Genetic y genetic, etc. Más adelante nos ocuparemos de ese asunto; por el momento, debemos quedarnos con que la precisión en 10 es del 10%, es decir, proporcionando 10 palabras sólo el 10% están bien y la precisión en 3 es nula, ninguna de las 3 palabras era "válida" (en base a la ground-truth disponible).

Además de la precisión existe otra medida muy importante, la exhaustividad (recall), que nos indica qué porcentaje de los resultados válidos fueron proporcionados por el sistema en cada punto. En este caso:

recombination	0/7 = 0%
evolutionary	0/7 = 0%
mutation	0/7 = 0%
satisfactory	0/7 = 0%
algorithms	0/7 = 0%
Genetic		0/7 = 0%
population	1/7 = 14,3%
individual	1/7 = 14,3%
solutions	1/7 = 14,3%
generations	1/7 = 14,3%
Un punto interesante es lo sencillo que resulta "retorcer" la interpretación de estas medidas para ofrecer sistemas que de manera trivial lo hacen fantásticamente bien si sólo se toma una de las medidas.

Por ejemplo, para tener una exhaustividad del 100% basta con retornar todas las palabras del documento, así seguro que retornamos las relevantes; y para tener la máxima precisión basta con no retornar ninguna palabra clave, la precisión sería entonces 0/0 que, de manera convincente, puede argumentarse que es igual a la unidad.

Naturalmente, un sistema así resulta poco útil; además, el que proporciona trivialmente una precisión del 100% (eso es bueno) tiene una exhaustividad nula (eso es muy malo) y el que proporciona trivialmente una exhaustividad del 100% (eso es bueno) tiene una precisión que estará muy cerca de cero (eso es malo).

Lo interesante sería combinar ambas medidas en un único valor numérico y eso es precisamente lo que hace la medida F (nótese que P es la precisión y R la exhaustividad):

Antes de proseguir he de decir que dependiendo del sistema que estemos evaluando pueden interesarnos otras medidas y/o formas de apreciar su calidad: precisión interpolada, precisión media, punto break even, curvas precisión-exhaustividad, etc. Sin embargo, en este caso en que el sistema de extracción de palabras clave siempre va a retornar el mismo número lo más sencillo es calcular la precisión de dicha lista, la exhaustividad y, a partir de ambas, la medida F. Así, en el ejemplo la precisión es 0,100; la exhaustividad es 0,143 y la medida F es 0,118 que es bastante mala.

Sin embargo, un evaluador humano nos diría que hemos sido excesivamente estrictos; de hecho si pasamos ambas listas a minúsculas y les aplicamos stemming quedarían así:

recombin
evolutionari
mutat
satisfactori
algorithm
genet
popul
individu
solut
gener
Y la lista ground-truth:
genet
algorithm
solut
optim
popul
evolut
fit
Si determinamos ahora la precisión y exhaustividad tendríamos:
recombin	P: 0/1	R: 0/7
evolutionari	P: 0/2	R: 0/7
mutat		P: 0/3	R: 0/7
satisfactori	P: 0/4	R: 0/7
algorithm	P: 1/5	R: 1/7
genet		P: 2/6	R: 2/7
popul		P: 3/7	R: 3/7
individu	P: 3/8	R: 3/7
solut		P: 4/9	R: 4/7
gener		P: 4/10	R: 4/7
Es decir, la precisión es 0,40 y la exhaustividad es 0,57 por lo que la medida F será de 0,47 que está mucho mejor.

Bien, así pues es posible calcular para cada documento la calidad, mediante la medida F, de su solución; sin embargo, nos interesa tener un único valor para toda la colección de documentos; para ello deberíamos hacer la media de todas estas medidas F. Esto es lo que se conoce como macropromedio y otorga la misma importancia a todos los documentos; la alternativa es el micropromedio que exigiría evaluar precisión y exhaustividad tomando todos los documentos de manera combinada. No voy a entrar en mayores detalles sobre el micropromedio puesto que creo que para esta aplicación en concreto no interesa tanto que el porcentaje de aciertos sea elevado de manera global sino tener una idea del rendimiento medio que se puede obtener para cada texto individual.

En resumen, para cada documento debe disponerse de un archivo ground-truth que permitirá calcular precisión, exhaustividad y medida F para las palabras clave obtenidas por el sistema a evaluar; posteriormente se obtiene la media de todas las medidas F que se tomará como bondad; finalmente, el objetivo del algoritmo genético será buscar aquellos parámetros para blindLight que dan como resultado un promedio más elevado para la medida F.


Next