Sistemas de Recuperação da Informação

Sistemas de Recuperação da

Informação

Parte III

Consultas

ConsultasConsultas

Principais modelos de recuperação da informação:

• Pesquisa em textos

• Modelos clássicos

•Consultas Booleanas

• Modelo vetorial

• Modelo probabilístico

• Modelos avançados

• Booleano estendido e modelo fuzzy

• Vetorial estendido e análise semântica latente

• Outros modelos probabilísticos – redes Bayesianas

ConsultasConsultas

Pesquisa em textos :

Problema: encontre as ocorrências de um termo em uma fonte

Termo e Fonte são cadeias de caracteres

Principais algoritmos:

• Ingênuo

• Knuth-Morris-Pratt

• Boyer-Moore

• Shift-or

• Karp-Rabin

• frases

Aplicações:

• Pesquisa por stop-words

• Detecção de radicais, afixos, sufixos

• Pesquisa por frases

• Pesquisa por termos compostos

ConsultasConsultas

Algoritmo ingênuo:

Dado um termo t de comprimento m e uma fonte d de comprimento n

Algoritmo:Dado t com tam(t)=m e d com com tam(d) = npara i=1 até n-m {

k=i;para (j=1; j<=m & t[j] ==d[k]; j++) k++;se (j>m) então imprima(“t ocorre na posição i de d”);

}

EXEMPLO: d = “a aba do abajour abriu abaixo”t = “abaixo”

Complexidade: O(n.m)

ConsultasConsultas

Algoritmo de Knuth-Morris-Pratt:

Dependendo da estrutura do termo t a cada diferença entre t e o substring da fonte d pode-se dar um passo maior para a próxima comparação

Definição do passo:passo(j)=max{ i / t[k] = t[j-i+k], k=1,..,i-1 e t[i] t[j]}

EXEMPLO: d = “a aba do abajour abriu abaixo” t = “abaixo

abaixo abaixo abaixo abaixo

a b a i x o1 2 1 2 3 4

Complexidade: 2n

ConsultasConsultas

Algoritmos de Boyer-Moore:

Compara da direita para a esquerda

Alg1: Compare da direita para a esquerda

Em um descasamento em d(i) procure d(i) em t e fixe o deslocamento, k

EXEMPLO: d = “a la embaixo abajour” t = “abaixo

abaixo abaixo abaixo

k=6k=1k=6

Pesquisa um termo ou vários termos

Complexidade: n + r m

ConsultasConsultas

Algoritmos Shift-Or:

Se baseia em automatas e usa operações entre bitstrings

VANTAGENS:

• simplicidade: operações binárias

• tempo real: tempo fixo para processar cada letra

• sem buffering: não precisa armazenar o texto integral

Alg: - crie uma assinatura para cada caractere do alfabeto

- crie um estado inicial D0 = 11111

- para cada caractere lido, aplique a fórmula Di = shift-left(Di-1) | T[corrente]

- pare quando o primeiro bit do estado for ‘0’

Complexidade: O(nm/w) w=tamanho do byte

ConsultasConsultas

Algoritmos Shift-Or:

EXEMPLO: d = “abdabababc” t = “ababc”

t = “a b a b c”T(a) 1 0 1 0 0 = 11010T(b) 0 1 0 1 0 = 10101T(c) 0 0 0 0 1 = 01111T(d) 0 0 0 0 0 = 11111

Operação sobre os estados:

D0 = 11111Di = shift-left(Di-1) | T[corrente] (‘|’ é o ou lógico)

texto = “a b d a b a b a b c”D0 = 11111T(x) = 11010 10101 11111 11010 10101 11010 10101 11010 10101 01111 Di = 11110 11101 11111 11110 11101 11010 10101 11010 10101 01111

Variante cDi = 11110 11101 11111 11110 11101 11010 10101 01010

ConsultasConsultas

Frases:

• Procure o símbolo menos frequente na consulta

• localize-o no texto

• analise a vizinhança (exata ou aproximada)

EXEMPLO: d = “ser ou não ser, eis a questão”frequência das letras:freq(‘s’) = 4 -> “er ou não er, ei a quetão”freq(‘e’) = 4 -> “r ou não r, i a qutão”freq(‘r’) = 2 -> “ ou não i a qutão”freq(‘o’) = 3 -> “u nã i a qutã”Freq(‘u’) = 2 -> “nã i a qtã”freq(‘n’) = 1 -> “ã i a qtã”Freq(‘a) = 3 -> “iqt”freq(‘i’) = freq(q) = freq(t) = 1 -> “”

OBS.: pode-se trocar a letra por um n-grama

ConsultasConsultas

Consultas Booleanas

•Em bancos de dados podemos fazer uma consulta:

SELECT nome, idade FROM pessoaWHERE idade > 18

Em Recuperação da Informação só podemos procurar pela existência ou não de um termo em um documento.

Esta existência pode ser precisa, aproximada, importante

Em RI os dados não têm semântica.

Para um 18 não sabemos que representa uma idade e nem de quem

Consultas BooleanasConsultas Booleanas

•Uma consulta booleana é uma combinação lógica de palavras-chave.

EXEMPLO: Quais documentos falam de 'recuperação' e de 'informação' mas não de 'teoria'?

Pode ser oriunda de

• Uma expressão em linguagem natural interpretada

• Uma interface que permite a declaração de expressões Booleanas

'recuperação' AND 'informação' AND NOT('teoria')?

ConsultasConsultas

Consultas Booleanas

EXPRESSÕES BOOLEANAS (EB):

Dado um conjunto de termos t = {t1, ..., tn} e duas EBs e1 e e2:

• Um termo é uma expressão booleana (EB)

• (e1 AND e2) é uma EB

• NOT(e1) é uma EB.

Definimos

• (e1 OR e2) NOT(NOT(e1) AND NOT(e2))

• (e1 XOR e2) (e1 OR e2) AND NOT(e1 AND e2)


EXECUÇÃO DE EXPRESSÕES BOOLEANAS:

1ª solução: GREPPING

• Seja U = {D1, .., Dn} um conjunto de documentos

• Dada a consulta “'recuperação' AND 'informação' AND NOT('teoria')”

• realizar uma pesquisa em texto em cada documento e responder a consulta


EXECUÇÃO DE EXPRESSÕES BOOLEANAS:

• Dado um conjunto de termos t = {t1, ..., tn}

• Dado um conjunto de documentos U, seja Di U o subconjunto de U que contém ti, para i=1,..n

Dado uma expressão Booleana e, denotamos U(e) ou

simplesmente (e) o resultado da aplicação de e a U. Temos:

• (ti) = Di – (p.ex. da lista invertida)

• (ei AND ej) = Di Dj

• (NOT(ei)) = U - Di.

PROPOSIÇÃO:

•(ei OR ej) = Di Dj


EXECUTAR EXPRESSÕES BOOLEANAS significa:

• Encontrar listas (de documentos)

• Operar listas

OPERAÇÕES PRIMITIVAS SOBRE LISTAS

• intercala(l1,l2): forma lista com todos elementos de ambas as listas

• todos(l): elimina duplicatas

• comuns(l): mantém uma entrada de cada elemento duplicado

• uns(l): só mantém os elementos que ocorrem uma vez na lista


• a OR b = todas(intercala(a,b))

• a AND b = comuns(intercala(a,b))

• a XOR b = uns(intercala(a,b))

• NOT(a) = ?

OPERAÇÕES BOOLEANAS EM FUNÇÃO DAS PRIMITVAS

• a AND NOT(b) = a – b = uns(intercala(a, a AND b)


EXEMPLO:

Seja (T1) = {D1, D3) (T2) = {D1, D2} (T3) = (D2, D3,D4}

Calculemos ( (T1 OR T2) AND NOT(T3) )

Intercala(T1,T2) = {D1,D1,D2,D3}T1 OR T2 = {D1,D2,D3}

Intercala( (T1 OR T2), T3) = {D1,D2,D2,D3,D3,D4}( (T1 OR T2) AND T3 ) = {D2,D3}

Intercala ( (T1 OR T2),( (T1 OR T2) AND T3) ) = {D1,D2,D2,D3,D3}(T1 OR T2) AND NOT(T3) = {D1}


OTIMIZAÇÃO:

DADO:

a AND b AND c

Ordenar a, b, c e processar primeiro os pares com menor frequência.


Além de consultas por palavras-chave:

• casamento parcial (consultas-AND longas e consultas-OR longas)

• ranking dos resultados

• frases

• proximidade entre termos (‘informação’ ANTES ou PERTO_DE ‘recuperação’)

• importância dos termos (frequência, idf)

• termos compostos, conceitos (sinonímia, mero-,hiper- e hyponímia)

• documentos semi-estruturados (dividido em ‘TÍTULO’, ‘AUTOR’, ‘RESUMO’, ‘PALAVRAS CHAVE’, RESTO composto por CAPÍTULOS, ... Ex. encontre livros com AUTOR contendo ‘Baeza-Yates’ e um capítulo sobre ‘signature files’)

• agrupamento de documentos

Consultas Booleanas EstendidasConsultas Booleanas Estendidas

Modelos: Mixed Min-Max (MMM), Paice e P-norma

Modelo MMM é baseado na teoria de conjuntos fuzzy:Sejam termos ‘a’ e ‘b’

• dega é o grau de pertinência de ‘a’ a um certo conjunto (documento)

• degab = min(dega, degb)

• degab = max(dega, degb)

Dado consultas COR = (a1 OR a2 OR ... OR an)e CAND = (a1 AND a2 AND ... AND an), e um documento D, define-se:

• sim(COR,D) = kor1*max(dega1,...degan) + kor2*min(dega1,..,degan)

• sim(CAND,D) = kand1*min(dega1,...degan) + kand2*max(dega1,..,degan)

• os ‘k’s são coeficientes reguladores, sendo kor1 = 1 – kor2 e kand1 = 1-kand2. Bons resultados ocorrem com kor1 > 0.2 e kand1 [0.5,0.8]

Consultas Booleanas EstendidasConsultas Booleanas Estendidas

Modelos: Mixed Min-Max (MMM), Paice e P-norma

Modelo de Paice:Similar ao MMM mas, ao invés de considerar os max e min de todos termos da consulta, leva todos pesos em consideração.

Modelo de P-norma:Neste modelo tanto os termos da consulta como os termos nos documentos são ponderados.

Detalhes sobre estes dois modelos em:

• Frakes&Baeza-Yates, “Information Retrieval – Data Structures & Algorithms” Prentice-Hall (1992)

• Kowalski “Informationh Retrieval – Theory and Implementation” Kluwer (1997)


EXERCÍCIO

Seja (T1) = {D1, D3) (T2) = {D1, D2} (T3) = (D2, D3,D4}

Calcular (NOT(T3) OR (T1 AND T2 AND T3))

• a OR b = todas(intercala(a,b))

• a AND b = comuns(intercala(a,b))

• a XOR b = uns(intercala(a,b))

• a AND NOT(b) = a – b = uns(intercala(a, a AND b)

• a OR NOT(b) = ??

Modelo VetorialModelo Vetorial

Considera um dicionário com n termos como um espaço com n dimensões.

• assim, os k termos que indexam um documento D formam um vetor com k dimensões no espaço n-dimensional;

• o valor de do vetor de D na dimensão k é o peso de k em D, p(k,D)

• todos m documentos de uma base de documentos formam m vetores;

• os termos de uma consulta C também formam um vetor com pesos p(k,C)

• procura-se os vetores de documentos mais próximos do vetor da consulta


Vantagens sobre o modelo Booleano:

• considera termos ponderados

• recupera documentos que não casam com todos termos da consulta

• permite rankeamento do resultado;


Temos então dois vetores:

• c = <pc1,pc2,...,pcn>

• dk = <pk1,pk2,...,pkn>

• A proximidade é dada pelo coseno do ângulo entre os vetores c e d

• sim(c,dk) = (c d) / (|c| X |dk|) =

i=1..n pki X pci

sim(c,dk) = ______________________________________

i=1..n pki2 x i=1..n pci

2

n = número de termos

dk = k-ésimo documento

pci = peso do i-ésimo termo na consulta

pki = peso do i-ésimo termo no documento dk


Obtenção dos pesos:

tf = freq (k,D) (freqüência do termo k no documento D)

idf = log (N / nk) (inverse document frequency), onde N

é o número de documentos na coleção e nk número de documentos em que o termo ocorre.

tfidf = freq (k,S) log (N / nk) (inverse document frequency),

é o peso do termo k no documento D


EXEMPLO:

um novo documento d2 contém as palavras

– ‘petróleo’ 18 vezes

– ‘refinaria’ 8 vezes

na base de 2048 documentos ocorrem:

– ‘petróleo’ em 128 deles

– ‘Brasil’ em 16 deles

– ‘ refinaria’ em 1024 deles

teríamos os cálculos:

Vetor com tf : <‘petróleo’: 18, ‘ refinaria’: 8>

cálculo com tfitf (‘petróleo’)= 18*log(2048/128) = 18*1,2 = 21,6

tfitf (‘Brasil’)= 0

tfitf (‘refinaria’)= 8*log(2048/1024) = 8*0,3 = 2,4

Logo temos o vetor d2 = <21.6, 0, 2.4>


EXEMPLO:

um novo documento d3 contém as palavras

– ‘petróleo’ 10 vezes

– ‘Brasil’ 10 vezes

na base de 2048 documentos ocorrem:

• ‘petróleo’ em 128 deles

• ‘Brasil’ em 16 deles

• ‘ refinaria’ em 1024 deles

teríamos os cálculos:

Vetor com tf : <‘petróleo’: 10, ‘Brasil’: 10>

cálculo com tfitf (‘petróleo’)= 10*log(2048/128) = 10*1,2 = 12

tfitf (‘Brasil’)= 10*log(2048/16) = 10*2,1 = 21

Logo temos o vetor d3 = <12, 21, 0>


EXEMPLO: temos os vetores

d1 = <4.8, 16.87, 3>

d2 = <21.6, 0, 2.4>

d3 = <12, 21, 0>Seja a consulta com

tf : <‘petróleo’: 1, ‘Brasil’: 1, ‘ refinaria’: 1>

c = <1.2, 2.1, 0.3>

• i=1..n pki X pci

sim(c,d1) = ______________________________________ = (1.2x4.8 + 2.1x16.87+0.3x3)


2 (23.04+284.6+9) x (1.44+4.41+0.09)

sim(c,d1) = (5.76+ 35.43+0.9) / 316.64 x 5.94) = 42.09 / (17.794x2.44) = 42.1/43.4=0.97



d1 = <4.8, 16.87, 3>

d2 = <21.6, 0, 2.4>



c = <1.2, 2.1, 0.3>


sim(c,d2) = ______________________________________ = (1.2x21.6 + 2.1x0+0.3x2.4)


2 (466.56+5.76) x (1.44+4.41+0.09)

sim(c,d2) = (25.95+0.72) / 472.32 x 5.94) = 26.67 / (21.73x2.437) = 26.67/52.956=0.50



d1 = <4.8, 16.87, 3>

d2 = <21.6, 0, 2.4>



c = <1.2, 2.1, 0.3>


sim(c,d3) = ______________________________________ = (1.2x12 + 2.1x21)


2 (144+441) x (1.44+4.41+0.09)

sim(c,d3) = (14.4+44.1) / 585 x 5.94) = 58.5/ (24.187x2.437) = 58.5/58.94 = 0.992

sim(c,d1) = (5.76+ 35.43+0.9) / 316.64 x 5.94) = 42.09 / (17.794x2.44) = 42.1/43.4= 0.97

sim(c,d2) = (25.95+0.72) / 472.32 x 5.94) = 26.67 / (21.73x2.437) = 26.67/52.956= 0.50


Problemas com o modelo vetorial:

• mudanças na base

• os termos são independentes entre si• Se um documento discute petróleo no Brasil e futebol na Argentina irá atender a uma consulta sobre petróleo no futebol.

Modelo Vetorial GeneralizadoModelo Vetorial Generalizado

Permite relacionar termos entre si por vetores chamados minterms:

• dado um vetor de palavras chave:

•c = <p1,p2,...,pn>, para associar pc1 com pc3 ele é combinado com o minterm

•m5 = <1,0,1,0...,0> e é considerado um fator de correlação c13

este modelo é controverso suas vantagens não são consolidadas

Feedback de relevânciaFeedback de relevância

Como reduzir problemas de terminologia e relevância?

• Um thesaurus (mais genérico, estático)

• Um ambiente interativo (personalizado, dinâmico)

Feedback de relevância:

itens relevantes são usados para refazer os pesos nos termos da consulta e expandí-la


A partir da consulta original C0 é calculada uma nova consulta C’.

Dados

• C0 o vetor da consulta original

• r o número de itens relevantes

• DRi os vetores dos itens relevantes

• nr o número de itens irrelevantes

• DNRj os vetores dos itens irrelevantes

Temos

C` = C0 + (1/r) i=1..r DRi – (1/nr) i=1..nr DNRi


Original

C` = C0 + (1/r) i=1..r DRi – (1/nr) i=1..nr DNRi

Variante

C` = C0 + i=1..r DRi – i=1..nr DNRi

Feedback positvo = i=1..r DRi

Feedback negativo = i=1..nr DNRi


relevante

irrelevante

Feedback positivo Feedback negativo


• Suponhamos que d3 e d2 são relevantes e d1 não

•Temos r = 2, nr = 1 e sejam = 1, = (1/r * 1/2) = ¼ e = (1/nr * ¼) = ¼

Então

c’ = C0 + (<20,0,2>+<12, 20,0) – (5,15,3>) =

= 1<1.2, 2.1, 0.3> + ¼ (<20+12, 0+20, 2+0> - ¼ (5, 15, 3>

= <1.2, 2.1, 0.3> + ¼ <27, 5, -1> = <7.95, 3.35, 0.05>

temos os vetores

d1 = <5, 15, 3>

d2 = <20, 0, 2>

d3 = <12, 20, 0> a consulta c = <1.2, 2.1, 0.3>


Obtivemos

C’ = <7.95, 3.35, 0.05> <8, 3.4, 0.1>

temos os vetores

d1 = <5, 15, 3>

d2 = <20, 0, 2>

d3 = <12, 20, 0>

a consulta c = <1.2, 2.1, 0.3>

Reaplicando:


sim(c,d3) = ______________________________________ = (1.2x12 + 2.1x21)


2 (144+441) x (1.44+4.41+0.09)

Modelo ProbabilísticoModelo Probabilístico

Sabendo-se que, dado

uma consulta c e

uma coleção de N documentos

Existe um conjunto de Rc ou R documentos relevantes para c.

Dado um documento d considera-se

P(R|d) a probabilidade de d ser relevante (estar em R), e

P(R-1|d) a probabilidade de d não estar em R

Define-se

sim(d,c) = P(R|d) / P(R-1|d) = (P(d|R) x P(R)) / (P(d|R-1)xP(R-1))

Sendo P(d|R) a probabilidade de um d qualquer ser de R

Temos, então: sim(d,c) P(d|R)/ P(d|R-1)


Dado uma consulta c um documento d e um termo t

Podemos dividir a coleção em

R o número de documentos relevantes para c.

N o número total de documentos

nt ou n número de documentos contendo t, e

rt ou r o número de documentos não contendo t

+ -

+ r n-r n

- R-r N-n-R+r N-n

R N-R N


+ -

+ r n-r n

- R-r N-n-R+r N-n

R N-R NFórmulas alternativas para a distribuição dos termos entre documentos relevantes e não-relevantes, determinando o peso wt ou w de t na consulta c:

F1: w1 = log( (r/R) / (n/N))

F2: w2 = log( (r/R) / ((n-r)/N-R)) )

F3: w3 = log ( (r/((R-r)) / (N/(N-n)) )

F4: w4 = (r/(R-r)) / ((n-r)/((N-n-R+r)) )

Experimentalmente a fórmula F4 se mostrou a mais adequada


sim1(c, dj) = i=1..Q(C + log((N-ni) / ni )

Sendo

Q = o número de termos comuns entre dj e c

C = uma constante de regulagem (p.ex. = 1)

ni = o número de documentos contendo ti

N = o número total de documentos

SIMILARIDADE sem necessidade de uma análise preliminar de relevância(revisão probabilística de F4)

sim2(c, dj) = i=1..Q(C + idfi) * fij )

Sendo

fij = K + (1-K) (freqij / maxfreqj)

freqij = a frequência de ti em dj

maxfreqj = a frequência de algum termo em dj

idfi = log (N / ni) (idf de ti em D)

K = uma constante de ajuste (para documentos pequenos 0.5, senão, 0.3)

Modelo Probabilístico - ExemploModelo Probabilístico - Exemplo

Suponhamos a base de documentos

petróleo refinaria Brasil Argentina futebol transporte jogo nacional

d1 4 10 8 0 0 3 0 0

d2 0 0 5 3 0 3 0 0

d3 1 0 3 3 2 0 0 1

d4 0 0 0 8 7 0 2 4

d5 5 8 2 2 0 5 0 2

d6 0 0 4 0 6 1 5 2

c 1 1 2 1 1 0 1 0

Total

10 18 22 16 15 12 7 9

A base tem 109 palavras


Calcular

Q = (o número de termos comuns entre dj e c) C = 1 (uma constante de regulagem (p.ex. = 1) ni = (o número de documentos contendo ti N = (o número total de documentos)

Petróleo Refinaria Brasil Argentina Futebol Transporte Jogo Nacional

Total

ni

sim1(c, dj) = i=1..Q(C + log((N-ni) / ni )


Q = (o número de termos comuns entre dj e c) N = (o número total de documentos) maxfreqj = (freq do termo max. no documento) K = 0,5 (constante de ajuste)idfi = log (N / ni) (idf de ti em D)ni = (número de documentos contendo ni)

fij = K + (1-K) (freqij / maxfreqj)

sim2(c, dj) = i=1..Q(C + idfi) * fij )

freq/

f

Petró-leo

refinaria Brasil Argentina futebol trans-porte

jogo nacio-nal

Q max-freq

d1 4/ 10/ 8/ 0/ 0/ 3/ 0/ 0/

d2 0/ 0/ 5/ 3/ 0/ 3/ 0/ 0/

d3 1/ 0/ 3/ 3/ 2/ 0/ 0/ 1/

d4 0/ 0/ 0/ 8/ 7/ 0/ 2/ 4/

d5 5/ 8/ 2/ 2/ 0/ 5/ 0/ 2/

d6 0/ 0/ 4/ 0/ 6/ 1/ 5/ 2/

c 1/ 1/ 2/ 1/ 1/ 0/ 1/ 0/

ni

idfi

Modelo Probabilístico - ExemploModelo Probabilístico - Exemplofreq/

f

Petró-leo

refinaria Brasil Argentina futebol trans-porte

jogo nacio-nal

d1 4/ 10/ 8/ 0/ 0/ 3/ 0/ 0/

d2 0/ 0/ 5/ 3/ 0/ 3/ 0/ 0/

d3 1/ 0/ 3/ 3/ 2/ 0/ 0/ 1/

d4 0/ 0/ 0/ 8/ 7/ 0/ 2/ 4/

d5 5/ 8/ 2/ 2/ 0/ 5/ 0/ 2/

d6 0/ 0/ 4/ 0/ 6/ 1/ 5/ 2/

c 1/ 1/ 2/ 1/ 1/ 0/ 1/ 0/

Total

10 18 22 16 15 12 7 9

cálculo com tfitf (‘petróleo’)= 4*log(109/10) = 4*1,2 = 4,15

tfitf (‘refinaria’)= 10*log(109/18) = 7,82

tfitf (‘Brasil’)= 8*log(109/22) = 5,56, tfitf (‘transporte’)= 3*log(109/12) = 2,87

Logo temos o vetor d1 = <4.15, 7.82, 5.56, 0, 0, 2.87, 0, 0>

A base tem 109 palavras

Documents

Sistemas de Recuperação da Informação