Ad verba per numeros

Parametrizacin mediante AG
Friday, May 11, 2007, 03:22 PM
Manuel est trabajando en la "hibridacin" de dos proyectos bastante distintos: un sistema para la extraccin de palabras clave y un framework de algoritmos genticos, os preguntaris para qu?

La respuesta es simple, el primer proyecto tiene una cantidad importante de parmetros que puede configurar el usuario, dependiendo de cmo se establezcan estos parmetros los resultados cambian; sin embargo, a priori no se puede saber cules son los adecuados; adems, adecuados para qu idioma? Para qu temas?

El segundo proyecto permite encontrar soluciones para problemas que "tpicamente" se resuelven mediante AGs. Qu tipo de problemas son estos? Aquellos en los que el espacio de soluciones es muy grande, no hay un mtodo "procedural" conocido para encontrar una solucin ptima pero es relativamente sencillo diferenciar una solucin "buena" de una "mala", dicho de otro modo, se dispone de una funcin para calcular la bondad (fitness) de las soluciones.

As, la idea es buscar automticamente parmetros para el sistema de extraccin de palabras clave que den buenos resultados. Buenos resultados que, obviamente, sern buenos si "coinciden" con palabras clave obtenidas por otros medios (humanos o automticos) 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
Adems, 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 precisin de la solucin, es decir, cuntos de los resultados que proporcion son "vlidos". Hay que decir, sin embargo, que la precisin habra 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 bsicamente la "misma palabra" y lo mismo solutions y solution, Genetic y genetic, etc. Ms adelante nos ocuparemos de ese asunto; por el momento, debemos quedarnos con que la precisin en 10 es del 10%, es decir, proporcionando 10 palabras slo el 10% estn bien y la precisin en 3 es nula, ninguna de las 3 palabras era "vlida" (en base a la ground-truth disponible).

Adems de la precisin existe otra medida muy importante, la exhaustividad (recall), que nos indica qu porcentaje de los resultados vlidos 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 interpretacin de estas medidas para ofrecer sistemas que de manera trivial lo hacen fantsticamente bien si slo 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 mxima precisin basta con no retornar ninguna palabra clave, la precisin sera entonces 0/0 que, de manera convincente, puede argumentarse que es igual a la unidad.

Naturalmente, un sistema as resulta poco til; adems, el que proporciona trivialmente una precisin 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 precisin que estar muy cerca de cero (eso es malo).

Lo interesante sera combinar ambas medidas en un nico valor numrico y eso es precisamente lo que hace la medida F (ntese que P es la precisin 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: precisin interpolada, precisin media, punto break even, curvas precisin-exhaustividad, etc. Sin embargo, en este caso en que el sistema de extraccin de palabras clave siempre va a retornar el mismo nmero lo ms sencillo es calcular la precisin de dicha lista, la exhaustividad y, a partir de ambas, la medida F. As, en el ejemplo la precisin 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 dira que hemos sido excesivamente estrictos; de hecho si pasamos ambas listas a minsculas y les aplicamos stemming quedaran 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 precisin y exhaustividad tendramos:
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 precisin 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 solucin; sin embargo, nos interesa tener un nico valor para toda la coleccin de documentos; para ello deberamos 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 exigira evaluar precisin 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 aplicacin 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 precisin, 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 gentico ser buscar aquellos parmetros para blindLight que dan como resultado un promedio ms elevado para la medida F.



Next