evaluacion de sistemas inteligentes de acceso a la información

Evaluación de los SINAI

José Carlos Cortizo Pérez http://www.esp.uem.es/jccortizo [email protected]

Departamento de Sistemas Informáticos Escuela Superior Politécnica Universidad Europea de Madrid

José Carlos Cortizo Pérez

Índice

Introducción

Colecciones de Datos

Espacio de Documentos

Recall, Precisón, F-measure

Accuracy, ROC/AUC

Sistemas Inteligentes de Acceso a la Información

Introducción


Introducción

Existen muchos modelos y algoritmos para cada tarea, ¿cuál es el mejor?

Cada sistema se suele componer de varios elementos

ranker, normalización, selección de términos, etc.

¿Qué componente es mejor para cada problema?

¿Cuánto va a tardar un usuario en encontrar la información que le interesa?

¿Por qué evaluar?



Introducción

La relevancia de los documentos es algo difícil de medir

Muchas veces responde a criterios humanos

Subjetividad

Situación (depende de las necesidades actuales)

Cognitivo (depende de la percepción)

Dinámico (cambia con el tiempo)

Dificultades



Introducción

La relevancia de los documentos es algo difícil de medir

Muchas veces responde a criterios humanos

Otras muchas, no responde a una mera respuesta SI/NO, si no que es un valor continuo

Dificultades



Introducción

Efectividad

Capacidad de satisfacer las necesidades del usuario

Eficiencia

Complejidad teórica

Tiempos de respuesta

Nos centramos en efectividad

Términos de la Evaluación



Introducción

Existen múltiples métricas, dependiendo tanto de la tarea concreta como de otros factores

Casi todas ellas se basan en disponer de una colección de datos de referencia

Métricas



¿Alguna pregunta?



Una colección de datos es un conjunto de elementos (webs, correos, artículos, etc.) que han sido revisadas y “etiquetadas” por humanos

Sirven como referencia a la hora de evaluar SINAIs

Las colecciones dependen, o son específicas, de las tareas a evaluar

¿Qué son?




Existe una gran variedad de colecciones ya “prefabricadas” y, en muchos casos, ejercen como estándares

¿De dónde sacarlas?




Reuters-21578

Reuters-22173

RCV1(Reuters Corpus Volume 1)

TREC-AP

Construcción propia: A partir de DMOZ, categorías de Yahoo!, catálogos de bibliotecas, etc.

Categorización de Texto




OHSUMED (Medicina)

LISA (Abstracts de ciencia)

TREC

CERC (búsqueda empresarial)

Recuperación de Información




TREC Blogs06

ENRON

Spam Corpus

Spam Assassin Public Corpus

Filtrado de Información




Netflix

Auto-creadas a partir de Flickr, Amazon, etc.

Recomendación



¿Alguna pregunta?




Colección de documentos

Relevantes Recuperados




A B

C D

Relevantes

No Recuperados


Espacio de DocumentosMatriz de Confusión


Recuperados No Recuperados

Relevantes

No Relevantes

A B

C D



La matriz de confusión anterior es para un problema de 2 clases

P.e: Recuperados vs. No-Recuperados

Se puede extender el concepto a espacios con N clases

Matriz de Confusión



Espacio de DocumentosMatriz de Confusión



¿Alguna pregunta?


Recall, Precisión, F-Measure


Métricas de Recuperación de I.

Es la proporción entre documentos relevantes recuperados y documentos relevantes

A mayor recall, el sistema nos devolverá una mayor proporción de documentos relevantes

recall = A / (A+B)

Recall




Es la proporción entre documentos relevantes recuperados y documentos recuperados

Nos da una idea de lo “buenos” que son los documentos que nos devuelve el sistema

precision = A / (A + C)

Precisión




Generalmente recall y precisión son inversamente proporcionales

Recall vs. Precisión


Precisión

Recall

punto ideal



Se suele buscar un equilibrio entre métricas

O primar las necesidades del usuario/sistema

P.e. Un médico preferirá mayor recall

Un usuario en Google suele preferir precisión

Recall vs. Precisión




Varias consultas

Necesidad de promediar

Ranking de documentos

Necesidad de normalizar

Factores adicionales




2 enfoques

Macroaveraging

Calcular para cada consulta y promediar

Todas las consultas tienen igual importancia

Microaveraging

Sumar tablas para todas las consultas y calcular 1 valor

Consultas con más docs. tienen mayor peso

Promedio




Si no hay ranking de documentos, obtenemos sólo 1 valor de recall y de precisión

Con ranking de documentos, podemos calcular la precisión para 11 niveles de recall (0.0, 0.1...1.0)

Esto devuelve una gráfica que permite analizar el rendimiento de forma visual

Ranking de documentos



Métricas de Recuperación de I.Ranking de documentos


N # doc relevante1 588 X2 589 X3 5764 590 X5 9866 592 X7 9848 9889 57810 98511 10312 59113 772 X14 990

R=1/6=0.167; P=1/1=1R=2/6=0.333; P=2/2=1R=3/6=0.5; P=3/4=0.75R=4/6=0.667; P=4/6=0.667

R=5/6=0.833; P=5/13=0.38


Métricas de Recuperación de I.Curva recall/precisión


0

0,25

0,50

0,75

1,00

0.1670.333

0.50.667

0.8333



Con el método anterior, logramos valores de recall y precisión en puntos que no tienen por qué estar justo en valores de recall pertenecientes a {0.0, 0.1, ..., 1.0}

Para lograr los valores de precisión asociados a estos puntos de recall, debemos interpolar

Interpolación de la curva recall/precisión



Métricas de Recuperación de I.Interpolación de la curva recall/precisión


0

0,25

0,50

0,75

1,00

0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0


Métricas de Recuperación de I.Interpolación de la curva recall/precisión


0

0,25

0,50

0,75

1,00

0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.00

0,25

0,50

0,75

1,00

0.1670.333

0.50.667

0.8333



La precisión interpolada en el punto de recall estándar j, es el valor máximo de la precisión para cualquier nivel de recall entre el j y el (j+1)

¿Cómo interpolamos?



Métricas de Recuperación de I.¿Cómo interpolamos?


N # doc relevante

recall precisión1 588 X 0,167 1,02 589 X 0,333 1,03 576 0,333 1,04 590 X 0,5 0,755 986 0,5 0,756 592 X 0,667 0,6677 984 0,667 0,6678 988 0,667 0,6679 578 0,667 0,66710 985 0,667 0,66711 103 0,667 0,66712 591 0,667 0,66713 772 X 0,833 0,3814 990 0,833 0,38

Recall Precisión0,0 1,00,1 1,00,2 1,00,3 1,00,4 0,750,5 0,750,6 0,6670,7 0,380,8 0,380,9 0,01,0 0,0


Métricas de Recuperación de I.Comparación de técnicas/sistemas



Métricas de Recuperación de I.Es la precisión en la posicion R del ranking de resultados para una consulta que tiene R documentos relevantes

R-precision


N #Doc Rel.1 588 X2 589 X3 5764 590 X5 9866 592 X7 9848 9889 772 X

R = # doc. relevantes = 6

R-precision = 4/6 = 0.67



Es una métrica que tiene en cuenta tanto el Recall como la precisión

Es la media harmónica del recall y la precisión

F =

F-Measure


2 · P · RP + R

=2

(1/R) + (1/P)


Métricas de Recuperación de I.Es una variante de la F-measure que permite establecer pesos (énfasis) para la precisión y el recall

E =

Los valores de β controlan el “trade-off” entre recall y precisión

β = 1 : Igual peso para recall y precisión

β > 1 : Mayor peso para el recall

β < 1 : Mayor peso para la precisión

E-Measure

(1+ β2)PRβ2P+R

=(1+ β2)

(β2/R) + (1/P)


¿Alguna pregunta?


Accuracy, ROC, AUC



El recall, precisión, F y E, son métricas aptas para la recuperación de información

También para el filtrado, ya que se puede ver como una especie de recuperación

Sin embargo, otras tareas necesitan de otras métricas más adecuadas

Otras métricas



Métricas de Recuperación de I.Notación




TP es el número de instancias que pertenecen a la clase (+), que el clasificador ha clasificado como (+)

TN es el número de instancias que pertenencen a la clase (-), que el clasificador ha clasificado como (-)

FP es el número de instancias que pertenecen a la clase (-) pero que el clasificador ha clasificado como (+)

FN es el número de instancias que pertenecen a la clase (+) pero que el clasificador ha clasificado como (-)

Notación




π0 es la probabilidad a priori de la clase (+)

π0 es la probabilidad a priori de la clase (-)

p0 es la proporción de veces que el clasificador predice (+)

p1 es la proporción de veces que el clasificador predice (-)

p1 = 1 - p0

Notación




tprate = TP / π0 hit rate, recall, sensivity

fprate = FP / π1 false alarm rate, especifity

precision = TP / TP + FP

accuracy = ( TP + TN ) / (π0 + π1)

accuracy es precisión clasificadora, no confundir con precisión normal

Ratios básicos



Métricas de Recuperación de I.Accuracy vs Precisión


↑accuracy, ↓precisión ↑precisión, ↓accuracy



Las curvas ROC han sido ampliamente utilizadas en el diagnóstico médico para visualizar y analizar el comportamiento de los sistemas de diagnóstico

Permiten comparar el rendimiento de un clasificador para un gran rango de costes de error y distribución de clases

Curva ROC



Métricas de Recuperación de I.Curva ROC




Si solo tengo un valor de TPR y FPR, solo tengo un punto en el espacio ROC

Con clasificadores probabilísticos, además de la clasificación de cada instancia, tenemos la probabilidad, si ordenamos los resultados en función de la probabilidad...

Curva ROC



Métricas de Recuperación de I.Curva ROC




Comparar gráficas resulta complicado, sobre todo cuándo una no está siempre por encima de otra

AUC es el área bajo la curva, que nos permite tener un valor único que refleje lo “buena” o “mala” que pueda ser una clasificación

AUC



¿Alguna pregunta?


Bibliografía

Baeza-Yates, Ricardo; Ribeiro-Neto, Berthier. Modern information retrieval. Addison-Wesley, 1999 (Z699.35 .I53 B34 Biblioteca UEM, edificio C).

Raymond Mooney. Performance Evaluation of Information Retrieval Systems. Tema 4 de su curso en IR.

http://www.cs.utexas.edu/~mooney/ir-course/slides/Evaluation.ppt

Adicional


¿Alguna pregunta?

evaluacion de sistemas inteligentes de acceso a la información

Education