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.


Back Next