Embed Size (px)
Citation preview
Avaliação Sistemas deRecuperação da Informação
Prof. Rodrigo Tripodi Calumby
DEXA / UEFS [email protected]
Por que?
Ex.: Projeto de Aviões– Teste em simuladores e experimentos
– Construção e teste de protótipo
– Monitoramento do funcionamento● Ajuste de performance
Roteiro
● Introdução– Eficiência X Eficácia
● Avaliação de Resultados● Paradigma de Cranfield● Medidas de Avaliação● Iniciativas● Exercícios
Eficácia X Eficiência
● Eficácia– Capacidade de encontrar a informação certa
● Eficiência– Quão rápido isso é feito!
Eficácia X Eficiência
● Eficácia– Capacidade de encontrar a informação certa
– Qualidade do ranking produzido
● Eficiência– Quão rápido isso é feito!
– Tempo X Espaço
Eficácia X Eficiência
● São afetadas por vários fatores– Interface
– Técnicas de refinamento de consulta
– Sugestões de consulta
– Realimentação de relevância
● Muito difícil avaliá-las juntas
● Foco: Experimentos controlados
Eficácia X Eficiência
● Custo/Benefício– Pequeno aumento de eficácia com impacto
significante em eficiência não serve.
● Eficácia → estabilidade → eficiência
● Ajuste de parâmetros para favorecer eficácia ou eficiência
Custo
● Algoritmos → Hardware
● Custo X Eficácia X Eficiência
● Otimização– Parâmetros
– Não é SEO – Search Engine Optmization
Avaliação de resultados
● Usuários X Relevância● Métricas → noção de relevância● Permitem
– Avaliar a performance da máquina de busca
– Comparar diferentes sistemas
● Técnica básica– Resultados do sistema
X
– Resultados dos usuários
Avaliação de resultados
● Permitem responder questões práticas sobre– Modificações das funções de ranking
– Novas funções de ranking
– Eficácia para diferentes tipos de consulta● Produtos, notícias, imagens, etc.
● Consultas podem fazer parte de tarefas mais complexas
Avaliação de resultados
● Métricas numéricas– Simples
– Repetíveis
– Baixo custo
– Curto espaço de tempo
● Permitem verificar o que funciona ou não com base no efeito sobre as métricas
O Paradigma de Cranfield
● Origem da avaliação sistemática de sistemas de RI
● Mortimer Taube– Bibliotecário do gov. EUA.
– Uniterm System– 40.000 categorias de documentos– 7.000 palavras distintas– Indexação usando apenas estas palavras
● Cyril Cleverdon (1914-1997).– Faculdade de Aeronáutica, Cranfield, UK.
●
O Paradigma de Cranfield
● Cyril Cleverdon + Bob Thorne (1952)– Indexaram 200 docs usando Uniterm
– Thorne fez algumas consultas
– Uniterm● Muito simples● Não uso de semântica
– Cleverdon não ficou satistfeito!● Não tinha dados suficientes para comparar os
sistemas de indexação
O Paradigma de Cranfield
● Cyril Cleverdon + Bob Thorne (1952)– Indexaram 200 docs usando Uniterm
– Thorne fez algumas consultas
– Uniterm● Muito simples● Não uso de semântica
– Cleverdon não ficou satisfeito!● Não tinha dados suficientes para comparar os
sistemas de indexação
O Paradigma de Cranfield
● 1957 - Financiamento do NSF (National Science Foundation)
● Cranfield-1– Comprar 4 sistemas de indexação
● Incluindo o Uniterm
– Indexação manual de 18.000 artigos sobre engenharia aeronáutica
– Avaliação de 1.200 questões de busca● Cada uma baseada em um único artigo● Objetivo: encontrar o artigo no catálogo
O Paradigma de Cranfield
Os 4 sistemas eram basicamente equivalentes em termos de precisão dos
resultados
O Paradigma de Cranfield
Os 4 sistemas eram basicamente equivalentes em termos de precisão dos
resultados
Entendimento da relação: Recall Precision
O Paradigma de Cranfield
● Cranfield-2● Novos experimentos
– Experimentos em menor escala● 1.400 documentos● 279 questões
– Relevância de todos os documentos em relação a cada questão (manualmente)
● 6 estudantes em três meses
O Paradigma de Cranfield
● Cranfield-2– Conjunto de documentos
– Conjunto de consultas
– Relevância Consulta/Documento
● Conclusões– Em situações práticas, a maioria das
consultas não exigem recall alta
– Apenas alguns itens relevantes (web)
O Paradigma de Cranfield
● Base da avaliação moderna de RI● Desvantagens/Assume que:
– A relevância de um documento é independente da relevância de outro documento
– O julgamento de relevância por especialistas reflete a população
– Todos os documentos relevantes para uma consulta são conhecidos a priori
O Paradigma de Cranfield
● Base da avaliação moderna de RI● Desvantagens/Assume que:
– A relevância de um documento é independente da relevância de outro documento
– O julgamento de relevância por especialistas reflete a população
– Todos os documentos relevantes para uma consulta são conhecidos a priori
O Paradigma de Cranfield
● Base da avaliação moderna de RI● Desvantagens/Assume que:
– A relevância de um documento é independente da relevância de outro documento
– O julgamento de relevância por especialistas reflete a população
– Todos os documentos relevantes para uma consulta são conhecidos a priori
1991 - The Gerard Salton Award (SIGIR)
Avaliação da RI Moderna
● Segue o Paradigma de Cranfield● Coleções de referência
– Rapidez para comparação de sistemas/funções
– Reprodução de experimentos
– Podem ser construídas para diferentes contextos com diferentes características
● Faces● Plantas● Imagens de satélite● Imagens Médicas● Web
Medidas de Avaliação
Precision e Recall
● Precision = taxa de itens relevantes no resultado retornado
● Recall = taxa de itens relevantes retornados em relação a quantidade total de itens relevantes
Precision e Recall
Precision=númeroderelevantes noresultado
tamanhodoresultado
Recall=número derelevantes noresultado
número total de relevantes
Precision e Recall
Item Relevante? Precision Recall
1 SIM 1.00 0.17
2 NÃO 0.50 0.17
3 SIM 0.67 0.33
4 SIM 0.75 0.50
5 SIM 0.80 0.67
6 SIM 0.83 0.83
7 NÃO 0.71 0.83
8 NÃO 0.63 0.83
9 NÃO 0.56 0.83
10 SIM 0.60 1.00
Precision e Recall
● Interpolação
fonte: http://nlp.stanford.edu/IR-book/html/htmledition/evaluation-of-ranked-retrieval-results-1.html
Precision e Recall
● Precision at Recall X
Recall 0.1
Recall 0.2
Recall 0.3
Recall 0.4
...
Precision e Recall
● Precision at Recall X
Recall 0.1
Recall 0.2
Recall 0.3
Recall 0.4
...
Recall Precision
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Precision e Recall
● Precision at Recall X
Recall 0.1
Recall 0.2
Recall 0.3
Recall 0.4
...
Recall Precision
0.0 0.9596
0.1 0.9596
0.2 0.9332
0.3 0.8892
0.4 0.8549
0.5 0.8067
0.6 0.7395
0.7 0.6441
0.8 0.4657
0.9 0.2968
1.0 0.1240
Precision e Recall
● Precision at Recall X
Recall 0.1
Recall 0.2
Recall 0.3
Recall 0.4
...
Recall Precision
0.0 0.9596
0.1 0.9596
0.2 0.9332
0.3 0.8892
0.4 0.8549
0.5 0.8067
0.6 0.7395
0.7 0.6441
0.8 0.4657
0.9 0.2968
1.0 0.1240
interpolação
Precision e Recall
Precision e Recall
Precision e Recall
Precision e Recall
Precision e Recall
Precision e Recall
Qual é melhor?
Precision e Recall
Área abaixoda curva
P@N
● Precisão do resultado em uma determinada profundidade– P@5
– P@10
– P@20
– P@N
F-measure
● Ponderação entre Precision e Recall
● Balanceada
AP (Average Precision)
● Precisão interpolada média para cada relevante encontrado
AP (Average Precision)
● Precisão interpolada média em 11 pontos– Média dos valores de precisão para recall 0.0,
0.1, 0.2, …, 1.0
MAP (Mean Average Precision)
● Média de AP para múltiplas consultas
GMAP (Geometric Mean Average Precision)
MAP X GMAP
Método AP(1) AP(2)
A 0.02 0.40
B 0.04 0.38
MAP X GMAP
Método AP(1) AP(2) MAP
A 0.02 0.40 0.21
B 0.04 0.38 0.21
MAP X GMAP
Método AP(1) AP(2) MAP GMAP
A 0.02 0.40 0.21 0.0894
B 0.04 0.38 0.21 0.1232
MRR(Mean Reciprocal Rank)
● O importante é o primeiro resultado– Que pode ser o único
● Ex.:– Resposta a questões
– Busca de URL
( Pooling )
● Avaliação de relevância incompleta– Pooling
● Combinação de resultados de vários sistemas e refino por especialistas
● Precision X Recall– Irrelevantes e não retornados são tratados da
mesma forma → não relevantes
– Pooling: Muitos não recuperados são tratados como irrelevantes
BPREF(Binary Preference)
● Número de vezes que itens irrelevantes aparecem antes de itens relevantes
irrelevantes
no máximo
( Níveis Relevância )
● Múltiplos níveis– Muito relevante– Relevante
– Neutro– Irrelevante– Muito Irrelevante
● Ranking– Itens mais relevantes devem estar no topo do ranking– Itens relevantes que aparecem no final do ranking não tem
muita importância.
NDCG(Normalized Discounted Cumulated Gain)
● Adequada com níveis de relevância não binária
● Leva em consideração– Posição do elementos no ranking
– Nível de relevância de cada elemento
NDCG(Normalized Discounted Cumulated Gain)
● Cumulated/Cumulative Gain
NDCG(Normalized Discounted Cumulated Gain)
● Cumulated/Cumulative Gain
NDCG(Normalized Discounted Cumulated Gain)
● Discounted Cumulated Gain
NDCG(Normalized Discounted Cumulated Gain)
● Discounted Cumulated Gain
NDCG(Normalized Discounted Cumulated Gain)
● Discounted Cumulated Gain– Não gera valor relativo ao ground-truth,
apenas em relação ao resultado avaliado● Precision e Recall → relativos aos itens relevantes
existentes para a consulta
● Podemos calcular G, CG e DCG Ideais
NDCG(Normalized Discounted Cumulated Gain)
● Discounted Cumulated Gain– Não gera valor relativo ao ground-truth,
apenas em relação ao resultado avaliado● Precision e Recall → relativos aos itens relevantes
existentes para a consulta
● Podemos calcular G, CG e DCG Ideais
NDCG(Normalized Discounted Cumulated Gain)
● Discounted Cumulated Gain– Não gera valor relativo ao ground-truth,
apenas em relação ao resultado avaliado● Precision e Recall → relativos aos itens relevantes
existentes para a consulta
● Podemos calcular G, CG e DCG Ideais
NDCG(Normalized Discounted Cumulated Gain)
● Discounted Cumulated Gain– Não gera valor relativo ao ground-truth,
apenas em relação ao resultado avaliado● Precision e Recall → relativos aos itens relevantes
existentes para a consulta
● Podemos calcular G, CG e DCG Ideais
NDCG(Normalized Discounted Cumulated Gain)
NDCG(Normalized Discounted Cumulated Gain)
● Quanto podemos melhorar?– Não podemos comparar curvas CG ou DCG
para 2 algoritmos
– Podemos comparar ● curvas CG com ICG● curvas DCG com IDCG● curvas NDCG para dois algoritmos● NDCG@K para dois algoritmos
Iniciativas
● TREC– Texto e Video
● INEX– XML
● CLEF– Imagens
● IRSI, FIRE, NTCIR...
Além disso,
● User-centered evaluation● Novidade e Diversidade● Métricas de correlação de ranks● Estudo de correlação de métricas● Testes estatísticos
Fontes das Imagens
● Porquê– http://www.aviastar.org/pictures/england/miles
_m-20.gif– http://onlyhdwallpapers.com/thumbnail/aircra
ft_prototypes_desktop_1131x707_hd-wallpaper-708758.jpg
– http://www.ipmsstockholm.org/magazine/2008/06/images/todos_3.jpg
● Cyril Cleverdon– http://en.wikipedia.org/wiki/Cyril_Cleverdon
Bibliografia
● Steffan Buettcher, Charles L. A. Clarke e Gordon V. Cormack. Information Retrieval – Implementing and Evaluating Search Engines. The MIT Press, 2010.
● Ricardo Baeza-Yates e Berthier Ribeiro-Neto. Modern Information Retrieval: The Concepts and Technology behind Search. Addison-Wesley, 2ed, 2011.
● Bruce Croft, Donald Metzler e Trevor Strohman. Search Engines – Information Retrieval in Practice. Addison-Wesley, 2009.
● Christopher D. Manning, Prabhakar Raghavan e Hinrich Schütze. An Introduction to Information Retrieval. Cambridge University Press, 2008.
Obrigado!
Dúvidas?
Exercícios
Exercícios5
10
0
0
0
5
1
0
10
0
0
0
5
1
0
1
5
0
0
0
10
5
0
10
0
0
10
0
1
5
0
0
0
5
1
0
1
0
5
0
10
0
● Duas Consultas →– 20 imagens– 10 relevantes
● Precision X Recall● MAP e GMAP● NDCG
Resultado
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.00.00
0.20
0.40
0.60
0.80
1.00
1.20
Precision X Recall
Q1
Q2
AVG
Recall
Pre
cisi
on
Resultado
MAP= 0.6916
GMAP= 0.6827
Resultado
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 200.0000
0.1000
0.2000
0.3000
0.4000
0.5000
0.6000
0.7000
0.8000
0.9000
NDCG
Q1
Q2
AVG
Rank
ND
CG
