Upload
elliando-dias
View
1.200
Download
5
Embed Size (px)
Citation preview
Recuperação Inteligente de Informações
Prof. Dr. Celso A. A. Kaestner
Pontifícia Universidade Católica do ParanáPrograma de Pós-Graduação em Informática Aplicada
Modelos Formais em IR
Parte I
Representação de documentos
• Os sistemas de IR tradicionais utilizam conjuntos de índices para representar os documentos;
• A idéia é que a semântica dos documentos seja representada por seus índices;
• Modelos mais utilizados: – booleano;– vetorial;– probabilista.
Modelos usados em IR
Non-Overlapping ListsProximal Nodes
Structured Models
Retrieval: Adhoc Filtering
Browsing
U s e r
T a s k
Classic Models
boolean vector probabilistic
Set Theoretic
Fuzzy Extended Boolean
Probabilistic
Inference Network Belief Network
Algebraic
Generalized Vector Lat. Semantic Index Neural Networks
Browsing
Flat Structure Guided Hypertext
Aspectos distintos: modelo de IR, visão
lógica dos docs., tarefa de recuperação.
Index Terms Full Text Full Text +Structure
RetrievalClassic
Set TheoreticAlgebraic
Probabilistic
ClassicSet Theoretic
AlgebraicProbabilistic
Structured
Browsing FlatFlat
HypertextStructure Guided
Hypertext
LOGICAL VIEW OF DOCUMENTS
USER
TASK
Definição formal deum sistema de IR
• Quádrupla (D,Q,F,R(qi,dj)) com– D: conjunto das representações dos docs. na coleção;– Q: conjunto das representações das consultas;– F: framework (arcabouço) para a modelagem dos
documentos, consultas e seu relacionamento;– R(qi,dj): função de ordenamento que associa a cada qi
ε Q e a cada dj ε D um número real que representa a similaridade entre o documento e a consulta.
Modelos clássicos em IR
• Nem todos os termos são úteis para representar o conteúdo dos docs.: termos menos freqüentes permitem identificar conjuntos mais restritos.
• A importância de um índice é representada pelos pesos a ele associados;
• Se ki é um índice, dj é um documento, wij é o peso associado a (ki,dj), que quantifica a importância do índice na descrição do conteúdo do documento.
Modelos clássicos em IR
Sejam: – ki: índice, dj: documento, N: número total de docs. – K = (k1, k2, …, kT) conjunto de índices; onde T:
número total de termos na coleção;– wij >= 0 : peso associado a (ki,dj); wij = 0 : indica
que o termo (índice) não pertence ao documento;– dj = (w1j, w2j, …, wTj) é o vetor formado pelos pesos
associados ao documento dj; – gi(dj) = wij é a função que retorna o peso associado
ao par (ki,dj).
O modelo booleano
• Modelo simples baseado na teoria dos conjuntos;• Consultas especificadas como expressões booleanas:
– semântica precisa;– formalismo elegante, framework simples.
• Termos presentes ou ausentes, ou seja wij ε {0,1};• Considerando:
– q = ka ∧ (kb ∨ ¬kc)– q (na f.n.d.) = (1,1,1) ∨ (1,1,0) ∨ (1,0,0)– cada componente de q (e.g. qcc=(1,1,0)) é
conjuntivo.
O modelo booleano
q = ka ∧ (kb ∨ ¬kc)
sim(q,dj) = 1 se ∃ (qcc) | (qcc ε q (f.n.d.)) ∧
(∀ki, gi(dj) = gi(qcc)) 0 no outro caso.
(1,1,1)(1,0,0)
(1,1,0)
Ka Kb
Kc
Deficiências do modelo booleano
• A recuperação é baseada numa decisão binária sem noção de matching parcial;
• Nenhuma ordenação de documentos é fornecida;• A passagem da necessidade de informação do usuário à
expressão booleana é considerada complicada;• As consultas booleanas formuladas pelos usuários são
freqüentemente simplistas;• Em conseqüência o modelo booleano retorna poucos ou
muitos documentos em resposta às consultas.
O modelo vetorial
• O uso de pesos binários é limitante;• Pesos não binários podem considerar mais
adequadamente matchings parciais;• Estes pesos são utilizados para calcular um grau de
similaridade entre a consulta e o documento;• Um conjunto ordenado de documentos é retornado,
fornecendo uma melhor resposta à consulta.
O modelo vetorial• Define-se:
– wij > 0 quando ki ∈ dj; – wiq >= 0 associado ao par (ki,q)– dj = (w1j, w2j, ..., wTj), q = (w1q, w2q, ..., wTq);– a cada termo ki está associado um vetor unitário i;– os vetores unitários i e j são considerados
ortonormais (i.e., são considerados como de ocorrência independente nos documentos) e formam uma base ortonormal para o espaço T-dimensional;
• Neste espaço, consultas e documentos são representados por vetores ponderados.
O modelo vetorial• Documentos são representados como “bags of words”;• Representados como vetores quando usados
computacionalmente:– Coordenadas: números em ponto flutuante;– Têm direção e magnitude;– Cada vetor reserva um lugar (dimensão) para cada
termo na coleção;– Portanto, muitos vetores são esparsos.
Exemplo em modelo vetorial
a: System and human system engineering testing of EPS
b: A survey of user opinion of computer system response time
c: The EPS user interface management system
d: Human machine interface for ABC computer applications
e: Relation of user perceived response time to error measurement
f: The generation of random, binary, ordered trees
g: The intersection graph of paths in trees h: Graph minors IV: Widths of trees and
well-quasi-ordering i: Graph minors: A survey
a b c d e f g h IInterface 0 0 1 0 0 0 0 0 0User 0 1 1 0 1 0 0 0 0System 2 1 1 0 0 0 0 0 0Human 1 0 0 1 0 0 0 0 0Computer 0 1 0 1 0 0 0 0 0Response 0 1 0 0 1 0 0 0 0Time 0 1 0 0 1 0 0 0 0EPS 1 0 1 0 0 0 0 0 0Survey 0 1 0 0 0 0 0 0 1Trees 0 0 0 0 0 1 1 1 0Graph 0 0 0 0 0 0 1 1 1Minors 0 0 0 0 0 0 0 1 1
nova galaxy heat h’wood film role diet fur
10 5 3
5 10
10 8 7
9 10 5
10 10
9 10
5 7 9
6 10 2 8
7 5 1 3
A
B
C
D
E
F
G
H
I
Exemplo em modelo vetorialDocument ids
terms
Frequency of terms on each document
Plotagem dos vetores
Star
Diet
Doc about astronomyDoc about movie stars
Doc about mammal behavior
Documentos no espaço 3D
• A similaridade ou proximidade de um documento d = (w1, …, wi, …, wT ) em relação a uma consulta
q = (q1, …, qi, …, qT ) é calculada pela função de
similaridade.• Existem muitas funções de similaridade:
- Produto interno: sim(q, d) = = q1 ∗ w1 + … + qT ∗ wT
Exemplo: Se d = (0.2, 0, 0.3, 1) e q = (0.75, 0.75, 0, 1), então sim(q, d) = 0.15 + 0 + 0 + 1 = 1.15
Exemplo em modelo vetorial
Observações:• Documento que têm mais termos em comum com a
consulta tendem a ter maior similaridade;• Para termos que aparecem em q e d, aqueles com
maiores pesos contribuem mais para sim(q, d) do que os que têm menores pesos;
• Documentos maiores são favorecidos;• A similaridade calculada não tem um limite superior
definido.
Exemplo em modelo vetorial
Métrica de similaridade normalizada
• Sim(q,dj) = cosΘ = [dj • q] / |dj| * |q|
= [Σ wij * wiq] / |dj| * |q|• Já que wij > 0 e wiq > 0, 0 <= sim(q,dj) <=1• Um documento é recuperado se realiza match parcial
com os termos da consulta.
i
j
dj
qΘ
Exemplo em modelo vetorial
system
interfaceuser
a
c
b
||||)cos(
BA
BAAB
⋅=θ
a b cInterface 0 0 1User 0 1 1System 2 1 1
Respondendo a uma consulta no modelo vetorial
• Representa-se a consulta como vetor;
• Calcula-se as distâncias a todos os docs.;
• Ordenação pela distância;
• Exemplo:– “computer system”
Query a b c d e f g h IInterface 0 0 0 1 0 0 0 0 0 0User 0 0 1 1 0 1 0 0 0 0System 1 2 1 1 0 0 0 0 0 0Human 0 1 0 0 1 0 0 0 0 0Computer 1 0 1 0 1 0 0 0 0 0Response 0 0 1 0 0 1 0 0 0 0Time 0 0 1 0 0 1 0 0 0 0EPS 0 1 0 1 0 0 0 0 0 0Survey 0 0 1 0 0 0 0 0 0 1Trees 0 0 0 0 0 0 1 1 1 0Graph 0 0 0 0 0 0 0 1 1 1Minors 0 0 0 0 0 0 0 0 1 1
Modelo vetorial
• Sim(q,dj) = [Σ wij * wiq] / |dj| * |q|• Como calcular os pesos wij e wiq ?
– freqüências simples tendem a favorecer palavras comuns • E.g. Query: The Computer Tomography
• Um peso adequado deve considerar 2 efeitos:– quantificação intra-documentos (similaridade)
• fator tf (term frequency) no documento;– quantificação inter-documentos (dissimilaridade)
• fator idf (inverse document frequency)– Usa-se o peso tf*idf : wij = tf(i,j) * idf(i).
Sejam: • N : número total de docs. na coleção;• ni: número de docs. contendo ki;• freq(i,j) freqüência simples de ki em dj;
O fator tf normalizado é f(i,j) = freq(i,j) / max(freq(l,j))onde o máximo é calculado sobre os termos que ocorrem em dj;
O fator idf é calculado como idf(i) = log (N/ni)onde log é usado para tornar os valores de tf e idf comparáveis, e pode ser interpretado como a quantidade de informação associada ao termo ki.
Modelo vetorial
• Os melhores esquemas de pesos são dados porwij = f(i,j) * log(N/ni)cuja estratégia é denominada tf-idf .
• Para uma consulta ponderada, uma sugestão é usar wiq = (0.5 + [0.5 * freq(i,q) / max(freq(l,q)]) * log(N/ni)
• O modelo vetorial com pesos tf-idf é uma boa estratégia para coleções gerais;
• Quanto aos resultados, o modelo vetorial é comparável às outras alternativas de ordenação, além de ser simples e rápido para calcular.
Modelo vetorial
Vantagens:• o uso de ponderação parcial melhora a qualidade
da resposta;• o matching parcial permite a recuperação de docs.
Que aproximam os requisitos da consulta;• a fórmula de ordenação pelo cosseno ordenada os
docs. de acordo com a similaridade com a consulta.Desvantagens:
• assume a independência dos termos índices (??); não fica claro se é má idéia.
Modelo vetorial
Modelo vetorial - exemplo I
k1 k2 k3 q • djd1 1 0 1 2d2 1 0 0 1d3 0 1 1 2d4 1 0 0 1d5 1 1 1 3d6 1 1 0 2d7 0 1 0 1
q 1 1 1
d1
d2
d3d4 d5
d6d7
k1k2
k3
d1
d2
d3d4 d5
d6d7
k1k2
k3
k1 k2 k3 q • djd1 1 0 1 4d2 1 0 0 1d3 0 1 1 5d4 1 0 0 1d5 1 1 1 6d6 1 1 0 3d7 0 1 0 2
q 1 2 3
Modelo vetorial - exemplo II
d1
d2
d3d4 d5
d6d7
k1k2
k3
k1 k2 k3 q • djd1 2 0 1 5d2 1 0 0 1d3 0 1 3 11d4 2 0 0 2d5 1 2 4 17d6 1 2 0 5d7 0 5 0 10
q 1 2 3
Modelo vetorial - exemplo III
Refinamentos
Resumo:
• A ponderação (wij ), é a combinação de 3 componentes:
1) Componente freqüência do termo:- 1.0 (b)
- fij (t)
- 0.5 + 0.5 (fij/maxi fij) ∈ [0.5,1] (n) ou K+ (1-K) (fij/maxi fij) com K ∈ [0,1]
Refinamentos
2)Componente freqüência na coleção: - 1.0 (x)
- log (N / fdi) (f)
- log ((N - fdi) / fdi) (p)
3) Componente de normalização do vetor:- nenhuma (x)
- pj / (||pj||) (c)
- Obs.: ||pj|| é a norma euclidiana do vetor pj
• Possível combinação dos 3 elementos: bxx, bxc,...
No tratamento da consulta
• A melhor combinação depende da aplicação;
1) Componente freqüência do termo:
- consulta curta, poucos termos => todos os
termos são importantes;
0.5 + 0.5 (fij/maxi fij) ∈ [0.5,1] (n)
- muitos termos, necessidade de maior
discriminação: fij (t)
No tratamento da consulta
2) Componente freqüência na coleção:
performance similar para f e p
- log (N / fdi) (f)
- log ((N - fdi) / fdi) (p)
3) Componente de normalização do vetor:
pouco importante:
- nenhuma (x)
No tratamento dos documentos
1) Componente freqüência do termo:
- vocabulário técnico, termos significativos:
0.5 + 0.5 (fij/maxi fij) ∈ [0.5,1] (n)
- vocabulário variado:
fij (t)
- documentos curtos, vocabulário controlado:
1.0 (b)
No tratamento dos documentos
2) Componente freqüência na coleção:
performance similar para f e p
log (N / fdi) (f)
log ((N - fdi) / fdi) (p)
coleções dinâmicas, necessidade de atualização:
1.0 (x)
No tratamento dos documentos
3) Componente normalização do vetor:
- se o comprimento for muito variável:
pj / (||pj||) (c)
senão: nenhuma (x)
• Melhores combinações (dependentes da aplicação)- documentos: tfc, nfc ou tpc,npc;- consultas: nfx, tfx, bfx ou (npx, tpx, bpx).
Modelo Probabilista
Problemas com o modelo vetorial:• Sem base semântica:
– Palavras-chave são plotadas como eixos;• São realmente independentes ?• São ortogonais ?
– Sem suporte para consultas booleanas:• Como encontrar docs. que não contém uma certa
palavra-chave ?
• Objetivo: capturar o problema de IR usando um formalismo probabilista;
• Dada a consulta do usuário, existe um conjunto resposta ideal– Consultas podem ser consideradas como
especificações das propriedades deste conjunto ideal de respostas (clustering);
• Quais são estas propriedades ? – Adivinhação inicial do conjunto (i.e., tentativa
inicial de encontrar o conjunto ideal);– Melhoria por iteração.
Modelo Probabilista
Modelo Probabilista
• Um conjunto inicial de docs. é recuperado;• O usuário inspeciona os docs. e indica os relevantes (em
geral somente os 10-20 iniciais são analisados);• O sistema de IR usa esta informação para refinar a
descrição do usuário em busca do conjunto resposta ideal;
• Repetindo o processo espera-se que a descrição do conjunto resposta ideal melhore;
• O conjunto ideal é modelado em termos probabilistas.
Modelo Probabilista
• Dada uma consulta q e um documento dj: – Estima-se a probabilidade que o usuário considere o
documento dj interessante (i.e., relevante). • O modelo assume que a probabilidade de relevância
depende somente das representações de q e dos dj;• O conjunto resposta ideal é denotado por R e deve
maximizar a probabilidade de relevância, e conter os documentos previstos como relevantes.
• Como computar as probabilidades ? Qual o espaço amostral ?
Modelo Probabilista
• O ordenamento probabilista é computado por:– sim(q,dj) = P(dj relevante-para q) /
P(dj não-relevante-para q)• Esta é a regra para um documento dj ser relevante;• Minimiza a probabilidade de um julgamento errôneo.
• Definição:– wij ∈ {0,1}– P(R | dj) : probabilidade que o doc seja relevante;– P(¬R | dj) : probabilidade que o doc seja não relevante.
Modelo Probabilista
• sim(q,dj) = P(R | dj) / P(¬R | dj) = [P(dj | R) * P(R)]
[P(dj | ¬R) * P(¬R)]~ P(dj | R)
P(dj | ¬R)
– P(dj | R) : probabilidade de selecionar randomicamente o documento dj do conjunto R de documentos relevantes.
Regra de Bayes
P(R ) e P(¬R )
igual para todos os docs.
Modelo Probabilista
• sim(q,dj) = [(Π g(dj)=1 P(ki|R)) *
(Π g(dj)=0 P(~ki|R))] /
[(Π g(dj)=1 P(ki|~R)) *
(Π g(dj)=0 P(~ki|~R))]• P(ki|R): probabilidade do índice ki pertencer a
um d ∈ R;• P(~ki|R): probabilidade do índice ki não estar
presente em d ε R.• P(ki|~R), P(~ki|~R): idem para d ∉ R.
Modelo Probabilista
• Usando log e considerando P(ki|R)+P(~ki|R)=1:
sim(q,dj) ~= Σ i=1,T wiq * wij *
{log [P(ki|R)/(1-P(ki|R))] +
log [(1-P(ki|~R)) / P(ki|~R)]}
• Inicialmente P(ki|R) = 0,5 e P(ki|~R)= ni / N – ni: número de docs. que contém ki;– N: número total de docs.
Modelo Probabilista
• Se V é conjunto de documentos inicialmente recuperados e Vi é o subconjunto de V que contém ki :– P(ki|R) = Vi / V ; e – P(ki|~R)= (ni -Vi) / (N - V) .
• O processo é repetido recursivamente.
Modelo Probabilista
• Correção para pequenos valores:– P(ki|R) = (Vi + 0,5) / (V + 1) ; e – P(ki|~R)= (ni -Vi + 0,5) / (N - V + 1).
• Ou então:– P(ki|R) = (Vi + (ni / N)) / (V + 1) ; e – P(ki|~R)= (ni -Vi + (ni / N)) / (N - V + 1).
Modelo Probabilista
• Vantagens:– Docs. ordenados em ordem decrescente de
probabilidade de relevância;• Desvantagens:
– necessidade de “adivinhação” inicial para
P(ki | R);– o método não considera os fatores tf e idf.
Comparação entre os modelos
• Modelo booleano: simples, não fornece matchings parciais e é considerado mais fraco;
• Experimentos de Salton e Buckley: o modelo vetorial tem em média desempenho superior ao modelo probabilista;
• Atualmente este é o pensamento dominante entre os pesquisadores da área.
Outros modelos• Modelos baseados em conjuntos difusos (fuzzy);• Extensões do modelo booleano: , adotando pesos
contínuos normalizados entre 0 e 1;• Modelos baseados em análise semântica latente
(LSA);• Modelos baseados em redes neurais;• Uso de redes bayesianas.
• Modelos para documentos estruturados;• Modelos para browsing.