Parte III
Evaluación de sistemas de IR
Almacenamiento y recuperación de
información en la Web
Evaluación de la recuperación
• Objetivo: evaluar la funcionalidad y eficiencia de un
sistema de IR
• Medidas usuales de evaluación:
– Tiempo de respuesta
– Espacio utilizado
– Evaluación de la eficiencia de recuperación basada en
• Colecciones prueba (TIPSTER/TREC, CACM, CISI,…)
• Diferentes medidas de evaluación
– Recall y Precision
– MAP, etc.
Almacenamiento y recuperación de
información en la Web
Medidas de evaluación
recall y precision
• El usuario desea realizar una solicitud de información
sobre una colección de docs
• Sean
– R: docs relevantes
– A: docs respuesta
Colección
|R|
R ecall=
Ra
|A|
R
P recision=
Ra
A
R a  C a rd ( A  R )
Almacenamiento y recuperación de
información en la Web
Evolución recuperación – precisión
Ejemplo
Suponemos las siguiente tabla de docs recuperados
orden
1
orden
d123
6
orden
d9
11
d38
R q   d 3 , d 5 6 , d 1 2 9  d ocu m en tos relevan tes
--A  d 123   A  1
2
d84
7
d511
12
d48
R ecall 
0
0
P recision 
d56
8
d12
9
---
13
d250
A  d 123 , d 84   A  2
R ecall 
0
0
P recision 
5
d6
d8
9
10
d187
d25
14
15
d113
d3
0
0
2
3
4
0
1
3
3
0
--A  d 123 , d 84 , d 56   A  3
R ecall 
1
 0, 3 3 %
3
Almacenamiento y recuperación de
información en la Web
P recision 
1
3
 0, 3 3 %
Evolución recuperación – precisión
Ejemplo
Doc
|A|
|Ra|
|R|
Recall
Precision
1
1
0
3
0
0
2
2
0
3
0
0
3
3
1
3
33,3
33,3
4
4
1
3
33,3
25
5
5
1
3
33,3
20
6
6
1
3
33,3
16,6
7
7
1
3
33,3
14,2
8
8
2
3
66,6
25
9
9
2
3
66,6
22,2
10
10
2
3
66,6
20
11
11
2
3
66,6
18,1
12
12
2
3
66,6
16,6
13
13
2
3
66,6
15,3
14
14
2
3
66,6
14,2
15
15
3
3
100
20
Almacenamiento y recuperación de
información en la Web
Evolución recuperación - precisión
• Para la representación de las curvas recall-precision
generalmente se emplean 11 niveles de recuperación
120
100
P re cis io n
80
60
40
20
0
0
20
40
60
80
R ec all
Almacenamiento y recuperación de
información en la Web
100
120
Consideraciones generales sobre las medidas
ryP
• En colecciones grandes no es posible disponer de
un conocimiento detallado de los docs.
• Considerar la combinación de ambas medidas (r y
P).
• Las medidas de r y P son para queries procesadas en
modo batch. Para sistemas de IR interactivos son
más convenientes medidas que cuantifiquen la
bondad del proceso.
Almacenamiento y recuperación de
información en la Web
Medida de Precisión promedio
• Desde el punto de vista de las
medidas de evaluación, los
algoritmos de recuperación
(search engines) evalúan
diferentes queries para evaluar
su eficacia.
• Una forma habitual de evaluar
un algoritmo consiste en
promediar las distintas
precisiones obtenidas para
cada query en cada nivel de
recuperación.
P (r) 
1
Nq
Nq
 P (r)
i
i 1
P (r )
P recision m edia al nivel r de re cuperacion
Pi ( r )
P recision al nivel r para la i-e sim a q
Nq
N º de qs utilizadas
Almacenamiento y recuperación de
información en la Web
Interpolación de la Precisión Promedio
• Para representar la evolución de la precisión
promedio se efectúa una interpolación de las
precisiones en cada nivel de recuperación
P ( r )  m ax P ( r )
r j  r  r j 1
r j   0,1, 2,
,10 
Almacenamiento y recuperación de
información en la Web
Interpolación de la Precisión Promedio
Ejemplo
Rq={d3,d56,d129}
Aq={d123,d84,d56,d6,d8,d9,d511,d129,d187,d25,d38,d48,d250,d113,d3}
– R=33%, P=33%
– R=66%, P=25%
– R=100%, P=20%
120
100
80
P ( r j )  m ax P ( r )
r j  r  r j 1
r j   0,1, 2,
Ej
,1 0 
r5  reca ll (5 0 % )
P recis ion
•
•
60
40
33
33
33
33
25
20
25
25
20
20
20
20
0
0
20
40
60
80
100
R e c a ll
Precision interpolada para 11 niveles de recall para Rq
Almacenamiento y recuperación de
información en la Web
120
Medida de Precisión Promedio en n
• Otra medida usual es el cálculo de la precisión promedio
tras n documentos relevantes recuperados (p. ej. 5, 10,
20, 30, 50, 100)
• Se calcula la media de las precisiones obtenidas hasta el
nivel de corte
• Este sistema favorece a los buscadores que recuperan los
documentos relevantes rápido
• Ej: si al nivel 5 tenemos unas medidas de precisión de 1,
0.66, 0.5, 0.4, 0.3
– [email protected] = (1+.66+.5+.4+.3)/5 = 0.572
Almacenamiento y recuperación de
información en la Web
Medida de R-Precision
• La idea es generar un valor resumen del ranking
mediante la precisión en la posición R-ésima del
ranking, siendo R el nº total de docs relevantes para
una query
– Para Rq={d3, d5,d9,d25,d39,d44,d56,d71, d89,d123}
• la 10-Precision es: 0.4 (4 docs relevantes en los 10 primeros)
– Para Rq={d3,d56,d129}
• la 3-Precision es: 0.33 (1 doc relevantes en los 3 primeros)
• Es útil para comprobar el comportamiento de un
algoritmo frente a cada ítem
Almacenamiento y recuperación de
información en la Web
Histogramas de R-Precisión
1.5
1
R-Precision A/B
• Las medidas de R-Precisión se
pueden usar para comparar el
comportamiento de dos
algoritmos de forma gráfica a lo
largo de diferentes búsquedas.
• Search Engines: A y B
• Numero de queries: 10
0.5
0
1
2
3
4
5
6
-0.5
-1
-1.5
R PA / B ( i )  R PA ( i )  R PB ( i )
R PA / B ( i )  0  A
B
R PA / B ( i )  0  A  B
R PA / B ( i )  0  A
B
Almacenamiento y recuperación de
información en la Web
Query Numbaer
7
8
9
10
Comparación de algoritmos IR
100
90
80
P re cis io n
70
60
50
40
30
20
10
0
0
20
40
60
80
100
120
R ec all
Curvas recall-precision para dos search engines diferentes
Almacenamiento y recuperación de
información en la Web
Discounted Cumulative Gain (DCG)
• Medida de la efectividad de un buscador
• Mide la ganancia de un documento basada en su posición en
la lista de documentos de un ranking
• Hipótesis
– Los documentos más relevantes son más útiles si aparecen en las
primeras posiciones del ranking. Su relevancia se debe penalizar
proporcionalmente a su posición con el logaritmo de su posición en el
ranking
– Los documentos más relevantes son más útiles que los parcialmente
relevantes y estos, a su vez, más que los no relevantes
– Se basa en la medida CG (p – posición en el ranking -)
p
CG p 
 rel
i
i 1
Almacenamiento y recuperación de
información en la Web
DCG (II)
DCG para una posición p en el ranking
p
D C G p  rel1 
rel i
 log
i2
p
DCG p 
2
reli
 log
i 1
2
2
i
1
(1  i )
nDCG representa la medida DCG normalizada para consultas sucesivas.
Para poder calcularla se supone conocida la distribución ideal, no siempre
posible.
nD C G p 
DCG p
 [0,1]
ID C G p
Almacenamiento y recuperación de
información en la Web
DCG (III)
Ejemplo:
Cálculo de la DCG para p=6
• Suponemos un usuario que valora
la lista de docs: D1, D2, D3, D4, D5, D6
que son el resultado de una
consulta q
• Los documentos se valoran en
una escala 0 a 3
– 0: no relevante
– 1,2: en cierto grado relevante
– 3: completamente relevante
• Resultado:
– 3, 2, 3, 0, 1, 2
i
reli
Logi
reli/Logi
1
3
---
---
2
2
1
2
3
3
1.59
1.887
4
0
2
0
5
1
2.32
0.431
6
2
2.59
0.772
6
CG6 
 rel
i
 3  2  3  0  1  2  11
i 1
Almacenamiento y recuperación de
información en la Web
DCG (y IV)
6
D C G 6  rel1 
rel i
 log
i2
2
 3  (2  1.887  0  0.431  0.772)  8.09
i
Supuesto un orden ideal (monótono decreciente): 3,3,2,2,1,0
6
ID C G 6  rel1 
rel i
 log
i2
2
 8.693
i
Ahora podemos calcular el nDCG para la consulta inicial
nD C G 6 
DCG6
nD C G 6

8.09
 0.9306
8.693
Almacenamiento y recuperación de
información en la Web
Medidas alternativas, I
• Media armónica
2
– Combina r y P
F  j =
F  [0,1]
1
1

– F=0 no se recuperan docs relevantes
r(j) P (j)
– F=1 todos los docs recuperados son
r ( j ) recu p era cio n j-esim o d o c
relevantes
P  j  p recisio n j-esim o d o c
– r y P altas  F alta
F
 j
Almacenamiento y recuperación de
información en la Web
recu p era cio n j-esim o d o c
Medidas alternativas, II
• Medida E (de evaluación)
– Combina r y P
– b=1  E(j)=1-F(j)
– b>1
• usuario interesado en P
– b<1
• usuario interesado en r
E
 j = 1-
1+ b
b
2

r(j)
r ( j)
P  j
F
b
 j
2
1
P (j)
recu p era cio n j-esim o d o c
p recisio n j-esim o d o c
recu p era cio n j-esim o d o c
p a ra m etro d efin id o p o r el u su a rio
Almacenamiento y recuperación de
información en la Web
Medidas alternativas, III
(orientadas al usuario)
• Pretenden tener en cuenta las diferencias existentes entre usuarios
interesados por un doc
• Contexto
– C: Colección de docs de referencia
– I: Ejemplo de solicitud de info
– R: Conjunto relevante de docs para I
– A: Conjunto recuperado
– U: Subconjunto de R conocido por el usuario
• |U| = Card(U)
– AU: docs conocidos por el usuario relevantes y recuperados
• |Rk| = Card(AU)
• |Ru|
– nº de docs relevantes desconocidos por el usuario que fueron recuperados
Almacenamiento y recuperación de
información en la Web
Medidas alternativas, IV
(orientadas al usuario)
|R|
|U|
|A|
|Rk|
Almacenamiento y recuperación de
información en la Web
|Ru|
Medidas alternativas, V
(orientadas al usuario)
• Alcance
– Fracción de los docs conocidos relevantes recuperados
alcance=
RK
U
• Novedad
– Fracción de los docs desconocidos relevantes recuperados
novedad=
RU
RU  R K
Almacenamiento y recuperación de
información en la Web
Medidas alternativas, VI
(orientadas al usuario)
• Recuperación relativa
– Cociente entre el nº de docs relevantes encontrados y el nº de docs
relevantes que el usuario esperaba encontrar
• Si encuentra tantos como esperaba --> RR=1
• Esfuerzo de recuperación
– Cociente entre el nº de docs relevantes que el usuario esperaba
encontrar y el nº de docs examinados con el fin de cubrir el nº anterior
Almacenamiento y recuperación de
información en la Web
Colecciones, I
• TIPSTER/TREC
– TREC  Text Retrieval Conference (1990)
• Dedicada a experimentación con colecciones grandes
(1.000.000 docs)
• Colección TREC: 6 CDs  1Gb cada uno
• Docs de: WSJ, AP, FT, etc.
• http://trec.nist.gov/
Almacenamiento y recuperación de
información en la Web
TREC, descripción
Disk
1
2
3
4
5
6
Contents
WSJ, 1987-1989
AP, 1989
ZIFF
FR, 1989
DOE
WSJ, 1990-1992
AP, 1988
ZIFF
FR, 1988
SJMN, 1991
AP, 1990
ZIFF
PAT, 1993
FT, 1991-1994
FR, 1994
CR, 1993
FBIS
LAT
FBIS
Size (MB)
267
254
242
260
184
242
237
175
209
287
237
345
243
564
395
235
470
475
490
Number Docs Words/Doc
(median)
98,732
245
84,678
446
75,180
200
25,960
391
226,087
111
74,520
301
79,919
438
56,920
182
19,860
396
90,257
379
78,321
451
161,021
122
6,711
4,445
210,158
316
55,630
588
27,922
288
130,471
322
131,896
351
120,653
348
Almacenamiento y recuperación de
información en la Web
Words/Doc
(mean)
434.0
473.9
473.0
1315.9
120.4
508.4
468.7
451.9
1378.1
453.0
478.4
295.4
5391.0
412.7
644.7
1373.5
543.6
526.5
581.3
Colecciones, II
• CACM
– 3204 artículos de Communications of the ACM (1958-1979)
• Campos
– Autores, fecha edición, palabras clave (reducidas a su raíz gramatical) de
título y abstract, referencias entre artículos, bibliografía, etc.
• Incluye un conjunto de 52 solicitudes de información. Ej: “Qué
artículos hay que traten de TSS (Time Sharing System), sistema
operativo de ordenadores IBM”
– El nº medio de docs relevantes para cada I es pequeño, en torno a 15.
Almacenamiento y recuperación de
información en la Web
Colecciones, III
• ISI (o CISI)
– 1460 docs escogidos del ISI (Institute of Scientific Information)
• Los docs escogidos se seleccionaron como los más citados en un estudio
sobre citación realizado por Small
• Propósito general: facilitar la investigación sobre similaridades basadas en
términos y patrones de referencias cruzadas
• Campos
– Autores, palabras clave (reducidas a su raíz gramatical) de título y abstract y nº de
“cocitaciones” para cada par de artículos
• Incluye un conjunto de 35 solicitudes de información en LN y qs booleanas y
41 sólo en LN.
– El nº medio de docs relevantes para cada I es grande, en torno a 50.
Almacenamiento y recuperación de
información en la Web
Calidad de los resultados
• ¿Se pueden aplicar los criterios de medida de la IR clásica a
la web?
• En IR clásica las medidas usadas son:
– Precisión: % de páginas recuperadas que son relevantes
– Recuperación: % de páginas relevantes que son recuperadas
• En web IR:
– El término relevante se liga al de calidad
– Una página es valorable si es una página de calidad para el objeto
de la búsqueda
– Precisión: número de páginas valorables recuperadas
Almacenamiento y recuperación de
información en la Web
Descargar

Evaluación