Baixe o app para aproveitar ainda mais
Prévia do material em texto
Modelos de Recuperação de Informação Prof. Dr. Bruno Tenório Ávila Recuperação de Informação Agenda Modelos Clássicos de Recuperação de Informação: • Modelo Booleano • Modelo Espaço Vetorial • Modelo Probabilista Para cada modelo, veremos: • Representação do documento • Representação da consulta • Função de busca Modelo Booleano Representação do Documento Representação da Consulta Função de Busca Corpus É dado um corpus C = {d1, d2, ..., dm} consistindo de m documentos. Neste caso, temos que m = 4; Documento 1 (d1): • A lógica como ciência começou a se desenvolver com o filósofo Aristóteles. Por meio da leitura dos diálogos de Platão, Aristóteles investigou a existência de uma lei que rege o pensamento para que se atinja o conhecimento de algo, a verdade, sem cair em contradição. Para Aristóteles, a lógica seria um instrumento para a ciência e a filosofia. A lógica aristotélica estava a serviço de uma explicação da realidade e baseava-se na distinção entre verdadeiro e falso. Corpus Documento 2 (d2): • Investigando os tipos de raciocínio, Aristóteles construiu uma teoria cujo núcleo é a caracterização e análise dos silogismos. Um exemplo típico de silogismos é: “Todo homem é mortal; Sócrates é homem; Logo, Sócrates é mortal”. Uma característica importante da silogística aristotélica é a utilização de símbolos que representam expressões substantivas a fim de estabelecer certo rigor nas demonstrações matemáticas. Corpus Documento 3 (d3): • Apesar das limitações para representar todos os tipos de inferências, o domínio da lógica silogística de Aristóteles prevaleceu até o século XIX, quando George Boole concebeu um sistema de símbolos e regras aplicável tanto a números binários como a enunciados. Com esse sistema é possível codificar proposições em linguagem simbólica e manipulá-las quase da mesma maneira como se faz com números. Com o trabalho de Boole, a lógica afasta-se da filosofia e aproxima-se da matemática. Corpus Documento 4 (d4): • A álgebra booleana é um sistema binário no qual existem somente dois valores possíveis para qualquer sistema algébrico: 1 ou 0, verdadeiro ou falso. Essa teoria revelou-se ideal para o funcionamento de circuitos eletrônicos e foi fundamental na idealização da arquitetura dos computadores modernos. Vocabulário Dado o vocabulário V, ou seja, um conjunto de n termos representativos para o corpus em questão: Por exemplo: • V = {aristoteles, booleano, computador, falso, filosofia, logica, matematica, platao, socrates, verdadeiro} • n = 10 𝑉 = {𝑡1, 𝑡2, … , 𝑡𝑛} t1 t2 t3 t10 Representação do Documento Os documentos são representados como conjunto de termos de indexação, sendo tais conjuntos representados como vetores de pesos binários de tamanho n: • Cada posição no vetor corresponde a um termo usado na indexação dos documentos; • Cada valor indica apenas se determinado termo está (1) ou não (0) presente no documento; Representação do Documento Por exemplo: • Documento d2 contém os termos t1, t7, t9, e não contém os termos t2, t3, t4, t5, t6, t8, t10; • Analogamente, o documento d2 está na interseção entre os conjuntos t1, t7 e t9; t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 d1 1 0 0 1 1 1 0 1 0 1 d2 1 0 0 0 0 0 1 0 1 0 d3 1 0 0 0 1 1 1 0 0 0 d4 0 1 1 1 0 0 0 0 0 1 Operadores Booleanos Operador Tipo de Busca Diagramas de Venn Significado E, AND Conjuntiva Produto lógico Simbolizado por A E B O documento é recuperado se os dois termos de indexação A e B estão associados a ele. OU, OR Aditiva Soma lógica Simbolizada por A OU B O documento é recuperado quando possui pelo menos um dos termos A ou B. NÃO, NOT Subtrativa Diferença lógica Simbolizada por A NÃO B (mesmo que A E NÃO B) O documento é recuperado se tem o termo A e não tem o termo B. Operadores Booleanos – Exercício Dados os conjuntos A = {1, 2, 3, 6, 7, 8}, B = {2, 3, 4, 5, 6, 7} e C = {1, 3, 5, 7, 9, 10}, responda as expressões booleanas: a) A E B, A E C, B E C b) A OU B, A OU C, B OU C c) A NÃO B, B NÃO A d) C E (A OU B) Representação da Consulta A representação da consulta é feita através das expressões booleanas; Exemplos: Consulta aristoteles AND filosofia t1 AND t5 aristoteles OR filosofia t1 OR t5 aristoteles AND NOT filosofia t1 AND NOT t5 computador AND (aristoteles AND NOT filosofia) t3 AND (t1 AND NOT t5) Recuperação O resultado da consulta é o conjunto de documentos cuja representação satisfazem às restrições lógicas da expressão de busca, ou seja, que fazem a expressão booleana assumir o valor lógico VERDADEIRO. Recuperação t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 d1 1 0 0 1 1 1 0 1 0 1 d2 1 0 0 0 0 0 1 0 1 0 d3 1 0 0 0 1 1 1 0 0 0 d4 0 1 1 1 0 0 0 0 0 1 Consulta filosofia AND matematica t5 AND t7 t5 t7 d1 d3 d2 d4 Resultado d3 Recuperação t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 d1 1 0 0 1 1 1 0 1 0 1 d2 1 0 0 0 0 0 1 0 1 0 d3 1 0 0 0 1 1 1 0 0 0 d4 0 1 1 1 0 0 0 0 0 1 Consulta filosofia OR matematica t5 OR t7 t5 t7 d1 d3 d2 d4 Resultado d1, d2, d3 Recuperação t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 d1 1 0 0 1 1 1 0 1 0 1 d2 1 0 0 0 0 0 1 0 1 0 d3 1 0 0 0 1 1 1 0 0 0 d4 0 1 1 1 0 0 0 0 0 1 Consulta filosofia NOT matematica t5 NOT t7 t5 t7 d1 d3 d2 d4 Resultado d1 Exercício 1) Utilizando o modelo booleano, o corpus de 4 documentos e o vocabulário V, qual o resultado das buscas: a) t6 AND t7 b) t6 OR t7 c) t6 AND NOT t7 2) Escreva em português o tipo de documentos retornados pelas expressões de busca abaixo: a) web OR informação b) recuperação AND (web OR informação) c) recuperação AND informação AND web Função de Busca Relevância “binária”: • O documento é considerado relevante se e somente se seu “casamento” com a consulta é verdadeiro, isto é se o valor verdade da consulta se torna verdadeiro para aquele documento; • Não é possível ordenar os documentos recuperados, pois todos igualmente tornam verdadeiro a expressão de busca; Exemplo: Consulta t1 AND t2 AND t3 t1 t3 t2 Documentos apresentados ao usuário Espaço de termos de indexação Análise do Modelo Booleano Vantagens: • Modelo simples baseado em teoria bem fundamentada; • Fácil de entender e implementar em computador; • Permite uma maior precisão na recuperação; Desvantagens: • Assume independência entre os termos usados na indexação; • Não permite casamento parcial entre consulta e documento; • Não permite ordenação dos documentos recuperados; • A necessidade de informação do usuário deve ser expressa em termos de uma expressão booleana; • Nem todo usuário é capaz disso; Exercício Trabalho individual para fazer de acordo com o Modelo Booleano: 1. Construir um corpus com 10 documentos (artigos, noticias, etc.) 2. Construir um vocabulário com 10 palavras representativas para todos os documentos 3. Construir a representação dos documentos 4. Construir a representação de 10 consultas 5. Listar os resultados das consultas. Modelo Vetorial Representação do Documento Representação da Consulta Função de Busca Vocabulário Dado o vocabulário V, ou seja, um conjunto de n termos representativos para o corpus em questão: Por exemplo: • V = {aristoteles, falso, filosofia} • n = 3 𝑉 = {𝑡1, 𝑡2, … , 𝑡𝑛} Representação do Documento Os documentos são representados como vetores no espaço n-dimensional de termos de indexação, tal que cada termo do vocabulário V = {t1, t2, ...,tn} é um eixo de um espaço vetorial e wi,j representa o peso do i-ésimo termo do j-ésimo documento. t1 t2 t3 d1 w1,1 w2,1 w3,1 d2 w1,2 w2,2 w3,2 d3 w1,3 w2,3 w3,3 d4 w1,4 w2,4 w3,4 Representação do Documento aristoteles falso d1 0,6 0,2 aristoteles falso 0,6 0,2 d1 0,4 filosofia d1 = (0.6, 0.2) d1 = (0.6, 0.2, 0.4) t1 t2 t3 d1 0.6 (w1,1) 0.2 (w2,1) 0.4 (w3,1) Representação da Consulta A consulta q também é representada como um vetor no espaço n-dimensional de termos. Consulta q aristoteles falso Representação da consulta q aristoteles 0,5 falso 0,5 filosofia 0,0 aristoteles falso q 0,5 0,5 t1 t2 t3 q 0.5 (w1,q) 0.5 (w2,q) 0.0 (w3,q) filosofia 0,0 Representação do Documento e da Consulta Consulta q aristoteles falso Documento d1 A lógica como ciência começou a se desenvol- ver com o filósofo Aristóteles. Por meio da leitura dos diálogos de Platão, Aristóteles investigou ... Representação da consulta q aristoteles 0,5 falso 0,5 filosofia 0,0 Representação do documento d1 aristoteles 0,6 falso 0,2 filosofia 0,4 Representação do Documento e da Consulta Consulta q aristoteles 0,5 falso 0,5 filosofia 0,0 Documento d1 aristoteles 0,6 falso 0,2 filosofia 0,4 aristoteles falso 0,6 0,2 d1 0,4 filosofia q 0,5 0,5 t1 t2 t3 d1 0.6 (w1,1) 0.2 (w2,1) 0.4 (w3,1) q 0.5 (w1,q) 0.5 (w2,q) 0.0 (w3,q) Função de Busca O modelo ordena os documentos recuperados de acordo com sua similaridade em relação à consulta: • Calcula-se a similaridade entre o vetor expressão de busca q e cada vetor documento d; • Similaridade pode ser medida pelo cosseno do ângulo entre q e d; t1 t2 d q θ 𝑠𝑖𝑚𝑖𝑙𝑎𝑟𝑖𝑑𝑎𝑑𝑒 𝑞, 𝑑 = cos(𝜃) Função de Busca Similaridade pode ser medida pelo cosseno do ângulo entre q e d: • Função inversamente relacionada ao ângulo entre os documentos, pois quanto menor é o ângulo entre os documentos, maior o cosseno e, portanto, a similaridade entre q e d; • Varia entre 0 e 1; • Independe do tamanho do vetor (considera apenas sua direção); Função de Busca t1 t2 d q θ t1 t2 q d t1 t2 q d t1 t2 qd Função de Busca Calcular o cosseno entre dois vetores arbitrários: 𝑠𝑖𝑚𝑖𝑙𝑎𝑟𝑖𝑑𝑎𝑑𝑒 𝑞, 𝑑𝑗 = cos(𝜃) = 𝑖=1 𝑛 𝑤𝑖,𝑗 × 𝑤𝑖,𝑞 𝑖=1 𝑛 𝑤𝑖,𝑗 2 × 𝑖=1 𝑛 𝑤𝑖,𝑞 2 Função de Busca – Exemplo 1 𝑠𝑖𝑚𝑖𝑙𝑎𝑟𝑖𝑑𝑎𝑑𝑒 𝑞, 𝑑1 = 𝑖=1 3 𝑤𝑖,1 × 𝑤𝑖,𝑞 𝑖=1 3 𝑤𝑖,1 2 × 𝑖=1 3 𝑤𝑖,𝑞 2 t1 t2 t3 d1 0.6 (w1,1) 0.2 (w2,1) 0.4 (w3,1) q 0.5 (w1,q) 0.5 (w2,q) 0.0 (w3,q) = 𝑤1,1 × 𝑤1,𝑞 + 𝑤2,1 × 𝑤2,𝑞 + (𝑤3,1 × 𝑤3,𝑞) 𝑤1,1 2 +𝑤2,1 2 +𝑤3,1 2 × 𝑤1,𝑞 2 +𝑤2,𝑞 2 +𝑤3,𝑞 2 n = 3 j = 1 = 0.6 × 0.5 + 0.2 × 0.5 + (0.4 × 0.0) 0.62 + 0.22 + 0.42 × 0.52 + 0.52 + 0.02 = 0.3 + 0.1 0.36 + 0.04 + 0.16 × 0.25 + 0.25 = 0.76 Função de Busca – Exemplo 1 1) Calcule a similaridade entre a consulta e o documento d2 representados abaixo: t1 t2 t3 d1 0.6 (w1,1) 0.2 (w2,1) 0.4 (w3,1) d2 0.4 (w1,2) 0.0 (w2,2) 0.0 (w3,2) q 0.5 (w1,q) 0.5 (w2,q) 0.0 (w3,q) 𝑠𝑖𝑚𝑖𝑙𝑎𝑟𝑖𝑑𝑎𝑑𝑒 𝑞, 𝑑2 = 𝑖=1 3 𝑤𝑖,2 × 𝑤𝑖,𝑞 𝑖=1 3 𝑤𝑖,2 2 × 𝑖=1 3 𝑤𝑖,𝑞 2 = 0.4 × 0.5 + 0.0 × 0.5 + (0.0 × 0.0) 0.42 + 0.02 + 0.02 × 0.52 + 0.52 + 0.02 = 1 2 = 0.70 Função de Busca – Exemplo 1 1) Calcule a similaridade entre a consulta e o documento d2 representados abaixo: t1 t2 t3 d1 0.6 (w1,1) 0.2 (w2,1) 0.4 (w3,1) d2 0.4 (w1,2) 0.0 (w2,2) 0.0 (w3,2) q 0.5 (w1,q) 0.5 (w2,q) 0.0 (w3,q) aristoteles falso 0,6 0,2 d20,4 filosofia q0,5 d1 Função de Busca – Exemplo 1 2) Calcule a similaridade entre a consulta e o documento d3 representados abaixo: t1 t2 t3 d1 0.6 (w1,1) 0.2 (w2,1) 0.4 (w3,1) d2 0.4 (w1,2) 0.0 (w2,2) 0.0 (w3,2) d3 0.4 (w1,3) 0.0 (w2,3) 0.4 (w3,3) q 0.5 (w1,q) 0.5 (w2,q) 0.0 (w3,q) 𝑠𝑖𝑚𝑖𝑙𝑎𝑟𝑖𝑑𝑎𝑑𝑒 𝑞, 𝑑3 = 𝑖=1 3 𝑤𝑖,3 × 𝑤𝑖,𝑞 𝑖=1 3 𝑤𝑖,3 2 × 𝑖=1 3 𝑤𝑖,𝑞 2 = 0.4 × 0.5 + 0.0 × 0.5 + (0.4 × 0.0) 0.42 + 0.02 + 0.42 × 0.52 + 0.52 + 0.02 = 1 2 = 0.50 Função de Busca – Exemplo 1 2) Calcule a similaridade entre a consulta e o documento d3 representados abaixo: t1 t2 t3 d1 0.6 (w1,1) 0.2 (w2,1) 0.4 (w3,1) d2 0.4 (w1,2) 0.0 (w2,2) 0.0 (w3,2) d3 0.4 (w1,3) 0.0 (w2,3) 0.4 (w3,3) q 0.5 (w1,q) 0.5 (w2,q) 0.0 (w3,q) aristoteles falso 0,6 0,2 d20,4 filosofia q0,5 d1 d3 Função de Busca – Exemplo 1 3) Calcule a similaridade entre a consulta e o documento d4 representados abaixo: t1 t2 t3 d1 0.6 (w1,1) 0.2 (w2,1) 0.4 (w3,1) d2 0.4 (w1,2) 0.0 (w2,2) 0.0 (w3,2) d3 0.4 (w1,3) 0.0 (w2,3) 0.4 (w3,3) d4 0.0 (w1,4) 0.2 (w2,4) 0.0 (w3,4) q 0.5 (w1,q) 0.5 (w2,q) 0.0 (w3,q) 𝑠𝑖𝑚𝑖𝑙𝑎𝑟𝑖𝑑𝑎𝑑𝑒 𝑞, 𝑑4 = 𝑖=1 3 𝑤𝑖,4 × 𝑤𝑖,𝑞 𝑖=1 3 𝑤𝑖,4 2 × 𝑖=1 3 𝑤𝑖,𝑞 2 = 0.0 × 0.5 + 0.2 × 0.5 + (0.0 × 0.0) 0.02 + 0.22 + 0.02 × 0.52 + 0.52 + 0.02 = 1 2 = 0.70 Função de Busca – Exemplo 1 3) Calcule a similaridade entre a consulta e o documento d4 representados abaixo: aristoteles falso 0,6 d20,4 filosofia q0,5 d1 d3 t1 t2 t3 d1 0.6 (w1,1) 0.2 (w2,1) 0.4 (w3,1) d2 0.4 (w1,2) 0.0 (w2,2) 0.0 (w3,2) d3 0.4 (w1,3) 0.0 (w2,3) 0.4 (w3,3) d4 0.0 (w1,4) 0.2 (w2,4) 0.0 (w3,4) q 0.5 (w1,q) 0.5 (w2,q) 0.0 (w3,q) d4 Recuperação Associa pesos positivos não-binários aos termos dos documentos e da expressão de busca; Isso permite casamento “parcial” entre consulta e documento: • Esses pesos são usados para calcular um “grau de similaridade” entre consulta e documento; O usuário recebe um conjunto ordenado de documentos como resposta à sua consulta: • Mais interessante do que apenas uma lista desordenada de documentos; Recuperação – Exemplo 1 Consulta aristoteles falso Resultado (em ordem) d1, d2, d4, d3 t1 t2 t3 similaridade d1 0.6 0.2 0.4 0.76 d2 0.4 0.0 0.0 0.70 d3 0.4 0.0 0.4 0.50 d4 0.0 0.2 0.0 0.70 q 0.5 0.5 0.0 Cálculo dos Pesos dos Documentos Este modelo pode utilizar diferentes fórmulas para: • Calcular os pesos dos vetores: • Número de ocorrências dos termos no documento; • TF-IDF (mais usado); • Calcular a medida de similaridade entre consulta e documentos: • Cosseno (mais usado); • Jaccard, Coeficiente de Pearson, etc. Essa escolha depende de quem constrói o SRI, e não do modelo Espaço Vetorial. Cálculo dos Pesos dos Documentos Número de ocorrências: • Contagem dos termos em um documento; • Por exemplo, documento d1: aristoteles 4 falso 1 filosofia 2 t1 t2 t3 d1 4 1 2 d2 2 0 0 d3 1 0 1 d4 0 1 0 Cálculo dos Pesos dos Documentos TF-IDF: • Term Frequency (TF): • Frequência do termo no documento; • Quanto maior, mais relevante é o termo para descrever o documento; • Inverse Document Frequency (IDF): • Inverso da frequência do termo entre os documentos da coleção; • Termo que aparece em muitos documentosnão é útil para distinguir relevância; • Peso associado ao termo varia entre 0 e 1 e tenta balancear os dois fatores acima. Cálculo dos Pesos dos Documentos O cálculo do peso wi,j pelo método TF-IDF é dado por: 𝑤𝑖,𝑗 = 𝑡𝑓𝑖,𝑗 × 𝑖𝑑𝑓𝑖 onde 𝑡𝑓𝑖,𝑗 = 𝑓𝑖,𝑗 𝑚𝑎𝑥𝑙 𝑓𝑙,𝑗 e 𝑖𝑑𝑓𝑖 = log 𝑚 𝑚𝑖 . - tfi,j é a frequência do termo ti no documento dj normalizada. - fi,j é o número de ocorrências do termo ti no documento dj. - maxl {fl,j} é o número de ocorrências do termo mais comum tl em dj. - idfi é o inverso da frequência do termo ti no corpus. - mi é o número de documentos que contêm o termo ti. - m é o número total de documentos no corpus. Cálculo dos Pesos dos Documentos – Exemplo 2 tfi,j t1 t2 t3 maxl {fl,j} d1 1.0 0.25 0.5 4 d2 1.0 0.0 0.0 2 d3 1.0 0.0 1.0 1 d4 0.0 1.0 0.0 1 fi,j t1 t2 t3 d1 4 1 2 d2 2 0 0 d3 1 0 1 d4 0 1 0 t1 t2 t3 mi 3 2 2 idfi log(4/3) = 0.12 log(4/2) = 0.30 0.3 wi,j t1 t2 t3 d1 1.0 x 0.12 = 0.12 0.08 0.15 d2 1.0 x 0.12 = 0.12 0.0 0.0 d3 1.0 x 0.12 = 0.12 0.0 0.3 d4 0.0 x 0.12 = 0.00 0.3 0.0 wi,j = idfi x tfi,j 𝑖𝑑𝑓𝑖 = log 𝑚 𝑚𝑖 𝑡𝑓𝑖,𝑗 = 𝑓𝑖,𝑗 𝑚𝑎𝑥𝑙 𝑓𝑙,𝑗 Cálculo dos Pesos da Consulta Os pesos para a consulta q são: • Se o i-ésimo termo existe na consulta, então 𝑤𝑖,𝑞 = 1; • Caso contrário, 𝑤𝑖,𝑞 = 0,5. t1 t2 t3 q w1,q w2,q w3,q aristoteles falso q d d 0,5 1,0 1,0 Cálculo dos Pesos da Consulta – Exemplo 2 t1 t2 t3 q 1 1 0,5 Consulta aristoteles falso Análise do Modelo Vetorial Vantagens: • Pesos associados a termos nos documentos e buscas; • Permite casamento parcial dos documentos com a expressão de busca; • Ordena documentos de acordo com o grau de similaridade com a consulta; Desvantagens: • Assim como o modelo booleano assume independência entre os termos usados na indexação; • É menos intuitivo que o modelo booleano; • Não é possível especificar relações frasais ou de sinonímia, nem a exclusão de termos na busca; Recuperação – Exemplo 2 1) Faça a recuperação da consulta “aristoteles falso” usando o Modelo Vetorial e o método TF-IDF: Dica: use as representações dos documentos e da consulta do Exemplo 2 calculadas anteriormente. Consulta aristoteles falso Recuperação – Exemplo 2 Resultado (em ordem) d1, d2, d4, d3 t1 t2 t3 Similaridade d1 0,12 0,08 0,15 0,88 d2 0,12 0,00 0,00 0,67 d3 0,12 0,00 0,30 0,56 d4 0,00 0,30 0,00 0,67 q 1 1 0,5 Exercício 2) Trabalho individual para fazer de acordo com o Modelo Vetorial e o método TF-IDF: 1. Construir um corpus com 5 documentos (artigos, noticias, etc.). 2. Construir um vocabulário com 5 palavras representativas para todos os documentos. 3. Construir a representação dos documentos. 4. Construir a representação de 5 consultas. 5. Listar os resultados das consultas. Referências ROWLEY, J. A Biblioteca Eletrônica. Briquet de Lemos / Livros, 2002. (Capítulo 7); BAYEZA-YATES, RIBEIRO-NETO. Modern Information Retrieval. Addison Wesley: 1999; FERNEDA, E. Introdução aos modelos computacionais de recuperação de informação. Rio de Janeiro: Ciência Moderna, 2012. Modelos de Recuperação de Informação Aula 2 – Recuperação de Informação Prof. Dr. Bruno Tenório Ávila brunotavila@gmail.com Depto. de Ciências da Informação, UFPE
Compartilhar