Modelo Probabilístico

Eveline Alonso VelosoPUC-MINAS

Referências

BAEZA-YATES, Ricardo e RIBEIRO-NETO, Berthier. Modern Information Retrieval. 1ª edição, New York: ACM Press, 1999, capítulo 2.

Modelo Probabilístico Modelo baseado em teoria de

probabilidades. Alguns experimentos realizados pela

comunidade científica indicam que este modelo apresenta melhor desempenho;

do que o modelo vetorial. Outros experimentos indicam que o

modelo vetorial apresenta desempenho um pouco melhor;

para coleções gerais. Portanto, ainda não há um consenso na

comunidade científica.

Idéia Original Dada uma consulta especificada

por um usuário, há um conjunto de resposta ideal; um conjunto de documentos que

contém exatamente todos os documentos relevantes para essa consulta;

e nenhum outro. conjunto .R

Idéia Original

De forma semelhante: conjunto :

conjunto de documentos que contém exatamente todos os documentos não-relevantes para essa consulta;

e nenhum outro.

R

Idéia Original Dada a especificação completa de

todas as propriedades desse conjunto de resposta ideal; não teríamos nenhum problema em

recuperar seus documentos. Mas, quais são essas propriedades?

Não sabemos exatamente... porém, a semântica dos termos de

indexação indicados na consulta do usuário; podem ser utilizados para auxiliar a

caracterizar essas propriedades.

Idéia Original Suponha inicialmente

quais poderiam ser essas propriedades; isto nos dá a descrição

probabilística inicial do conjunto de resposta ideal.

Essa descrição inicial é utilizada para recuperar um primeiro conjunto de documentos.

d2

d10

d7

d3

d11

d5

Idéia Original Inicia-se então uma série de

interações com o usuário; com o objetivo de melhorar a descrição

do conjunto de resposta ideal. O usuário inspeciona os primeiros

documentos da lista de documentos recuperados; procurando os realmente relevantes; e indica para o sistema de recuperação

de informação quais são os documentos relevantes;

e quais não são.

Idéia Original O sistema de recuperação de

informação utiliza essa informação; para refinar a descrição do conjunto de

resposta ideal.

d2

d10

d7

d3

d11

d5

d2

d3

d7

d11

d10

d5

relevante

não-relevante

relevante

Idéia Original

Através da repetição desse processo por muitas vezes; espera-se que a descrição do

conjunto de resposta ideal melhore;

e aproxime-se suficientemente da real descrição do conjunto de resposta ideal.

Termos de Indexação Os pesos dos termos de

indexação assumem valores binários: wti,dj = peso do termo ti para o

documento dj. wti,dj = 1;

caso o termo ti apareça no documento dj.

wti,dj = 0; caso o termo ti não aparece no

documento dj.

Dada uma consulta qi, especificada pelo usuário, e um documento dj; o modelo probabilístico estima a

probabilidade do usuário considerar o documento dj relevante.

O modelo assume que essa probabilidade de relevância só depende; das representações da consulta qi e

do documento dj.

Princípio Probabilístico

Função de Ranking

Onde: : probabilidade do

documento dj ser relevante para a consulta qi.

: probabilidade do documento dj não ser relevante para a consulta qi.

)d|R(P

)d|R(P)d,q(sim)d,q(R

j

j

jiji

)d|R(Pj

)d|R(Pj

Função de Ranking

: probabilidade do termo ti estar presente em um documento aleatoriamente selecionado do conjunto .

: probabilidade do termo ti estar presente em um documento aleatoriamente selecionado do conjunto .

)R|t(P

)R|t(Plog

)R|t(P

)R|t(Plogd,qsim

i

i

i

i

deqdetji

jii

1

1

)R|t(Pi

)R|t(Pi

R

R

Ordenação Inicial dos Documentos Não conhecemos, no início, o

conjunto R. Por isso, é necessário estimar

inicialmente as probabilidades: e

Há várias possibilidades.

)R|t(Pi

)R|t(Pi

Ordenação Inicial dos Documentos Utilizaremos:

: constante para todos os termos de indexação ti. = 0,5.

: a distribuição dos termos de indexação entre os

documentos não-relevantes; aproxima-se da distribuição dos termos de

indexação entre todos os documentos da coleção. = ;

onde: ni = número de documentos onde ti aparece; N = número total de documentos da coleção.

)R|t(Pi

N

ni

)R|t(Pi

Ordenação Inicial dos Documentos Os documentos da coleção que

apresentam pelo menos um dos termos especificados na consulta qi são selecionados. Pode-se utilizar outro critério para

selecionar os documentos. Para cada documento selecionado;

sua similaridade com o consulta qi é calculada; utilizando-se as estimativas iniciais de e

Os documentos selecionados são ordenados;

em ordem decrescente de similaridade com a consulta qi.

)R|t(Pi

)R|t(Pi

Melhorando a Ordenação Inicial dos Documentos Seja

V: subconjunto dos documentos

inicialmente recuperados; formado pelos r documentos

melhor ranqueados. Vi:

subconjunto dos documentos de V; que contêm o termo de indexação

ti.

Melhorando a Ordenação Inicial dos Documentos Para melhorar a ordenação

probabilística dos documentos; precisamos melhorar as

estimativas. Estimativas reavaliadas:

1

50

V

,V)R|t(P i

i

1

50

VN

,Vn)R|t(P ii

i

Melhorando a Ordenação Inicial dos Documentos

Para cada documento anteriormente selecionado; sua similaridade com a consulta qi é recalculada;

utilizando-se as estimativas reavaliadas de e

Os documentos selecionados são reordenados; em ordem decrescente de similaridade com a

consulta qi. Esse procedimento é repetido;

até que a ordenação dos documentos selecionados não se modifique após duas iterações sucessivas.

)R|t(Pi

)R|t(Pi

Melhorando a Ordenação Inicial dos Documentos A ordenação dos documentos

melhora; sem a intervenção humana;

ao contrário da idéia original do modelo probabilístico, portanto.

Há a possibilidade também do usuário participar da indicação do conjunto V.

Vantagens

Ordena os documentos; em ordem decrescente de sua

probabilidade de relevância. Considera casamentos

parciais; entre documentos e consultas.

Desvantagens É necessário supor as

estimativas iniciais de e .

Não considera as freqüências dos termos nos documentos; utiliza pesos binários.

Considera que os termos de indexação são independentes.

)R|t(Pi

)R|t(Pi

Exercício 1 – Coleção Considere uma coleção composta

pelos seguintes documentos: d1: recuperação de informação. d2: sistemas de informação. d3: PUC-Minas. d4: PUC-Minas cursos sistemas de

informação. d5: PUC-Minas sistemas de

computação. d6: PUC-Minas cursos jogos digitais.

Exercício 1 – Consulta

Construa o arquivo invertido correspondente a essa coleção e responda a seguinte consulta utilizando o modelo probabilístico: q: Sistemas de informação.

Exercício 2 – Coleção Considere uma coleção composta

pelos seguintes documentos: d1: Eleição. Eleitor. d2: domicílio eleitoral. d3: Zona eleitoral. VOTO. d4: Título de eleitor. d5: Domicílio eleitoral. Zona eleitoral. d6: Domicílio eleitoral. ELEIÇÃO. d7: direito de votar. Domicílio eleitoral.

Exercício 2 – Operações sobre o Texto

Considere também que apenas as seguintes operações foram realizadas sobre o texto de seus documentos:

conversão de todos os caracteres para minúsculo;

eliminação de marcas de pontuação;

eliminação da stopword de.

Exercício 2 – Consulta Construa o arquivo invertido

correspondente a essa coleção. Considere que o seguinte conjunto

corresponde ao ranqueamento inicial dos documentos dessa coleção para a consulta q = domicílio eleitoral, processada através do modelo probabilístico:

{d3, d2, d5, d6, d7}

Indique o resultado obtido após o 1º refinamento desse conjunto-resposta.