Recuperação de Informação — Parte 2
Neste artigo darei continuidade sobre alguns tópicos de IR (Information Retrieval), falando sobre algumas técnicas e procedimentos utilizados no processo de recuperação de informação.
Ele terá a seguinte estrutura de tópicos:
1. Recuperação dos documentos
2. Análise e pré-processamento linguístico
3. Criação dos Índices
4. Scoring e Rankeamento
5. Próximos Passos
6. Conclusão
1. Recuperação dos documentos
Para iniciar o processo de indexação, primeiramente é necessário definir quais serão os documentos a serem considerados. Uma dificuldade a ser tratada é a de que existem vários formatos de documentos, como por exemplo, documentos com extensão .doc, .pdf, email, .html, enfim, cada qual com sua formatação e seus padrões.
Com esse leque de possibilidades, não é trivial recuperar informações destes documentos distintos, sendo necessário existir um tratamento prévio para o consumo destas informações, para que possamos criar os índices corretamente.
Antes de efetivamente indexarmos os documentos, é importante definirmos 2 pontos: a unidade e a granularidade.
Podemos explicar a unidade da seguinte forma: um livro é composto por diversas seções(índice, prefácio, resumo, capítulos, apêndices, etc), mas em um cenário hipotético existe a necessidade de capturarmos somente os capítulos do livro, desconsiderando as demais informações. Assim, a unidade definida para este cenário são os capítulos do livro.
A granularidade é o tamanho que os índices de um documento serão divididos. Utilizando o mesmo exemplo anterior, não é interessante indexarmos todos os capítulos do livro como um único documento, pois consultas para “Economia Brasil” podem retornar livros que contenham ”Brasil” no 1º capítulo e “Economia” no último capítulo, os quais talvez não sejam relevantes para a consulta. Poderíamos então indexar este documento na granularidade de seções dos capítulos, onde cada seção formaria um índice.
Por isso, é muito importante realizar a modelagem de forma cuidadosa e avaliar qual o nível de unidade e granularidade mais adequada para o domínio da pesquisa, pois isto é um fator determinante para o sucesso ou não do resultado da pesquisa.
2. Análise e Pré-processamento linguístico
A análise e o pré-processamento linguístico tem por objetivo tratar e preparar os documentos para que seja efetuada a criação dos índices.
Nesta fase são executadas a tokenização dos termos, a construção de classes de equivalência para os termos gerados, entre outros processos. A seguir, explanarei alguns processos que são utilizados para a análise e pré-processamento dos documentos recuperados.
2.1 — Tokenização
Após a definição da unidade e da granularidade dos documentos, é efetuada a tokenização, que é o processamento que divide o texto em partes, chamadas de tokens. Neste processo geralmente as pontuações dos textos são eliminadas e a divisão dos tokens é feita pelos espaços em brancos.
Os tokens são termos e eles são divididos entre classes, que são os tipos dos tokens. Por exemplo, o texto “a Aline tem a blusa azul”, tem 6 termos (tokens) e 5 classes (tipos), pois o termo “a” se repete, fazendo parte da mesma classe (tipo).
Neste processo de divisão existem algumas dificuldades, pois alguns termos que necessitam permanecer juntos, para que a semântica seja preservada, podem ser separados pela tokenização. Por exemplo, o termo “São Paulo”, seguindo a regra básica da tokenização, geraria os termos “São” e “Paulo”, alterando totalmente o significado. Outros exemplos de termos que necessitam ser avaliados mais cuidadosamente são as datas, números, valores, nomes compostos, entre outros, que se não forem tratados e tokenizados da forma correta, podem influenciar a qualidade da pesquisa.
Adicionalmente também existem algumas palavras comuns nos textos e que adicionam pouco valor para a busca de documentos. Essas palavras são conhecidas como Stop Words. Na língua portuguesa, os Stop Words são os artigos, preposições e alguns verbos comuns, que podem ser desconsiderados e não inclusos no Índice.
2.2 — Normalização
Algumas palavras que possuem diferenças superficiais na sequência de caracteres, mas têm o mesmo significado (ex.: carro forte e carro-forte), necessitam ser ajustadas pois, independente de como o usuário efetuar a consulta, os resultados de ambas devem ser retornados.
Para solucionar isto é realizada a normalização. Uma das formas de normalizar é a criação de classes de equivalência, que basicamente é um mapeamento que relaciona os termos e que faz com que a consulta retorne os documentos que contém os 2 termos. A classe de equivalência pode ser criada considerando a fonética e/ou a semântica(como os sinônimos carro e automóvel).
Além da classe de equivalência outro método de normalização é manter a relação entre os tokens não normalizados. Por exemplo, os sinônimos “carro” e “automóvel” podem ser considerados como resultados da mesma consulta, ou no momento da criação do índice, eles serem relacionados. Este último método é menos eficiente que a classe de equivalência.
Outras partes que sofrem a normalização na língua portuguesa são os acentos, as letras maiúsculas, etc, e em outras línguas existem algumas peculiaridades adicionais.
2.3 — Stemming
É uma técnica que reduz a palavra a sua raiz. Por exemplo, palavras como bibliotecas e bibliotecário podem ser reduzidas para bibliotec, aumentado assim o retorno de documentos nas consultas.
Apesar de gerar o aumento da quantidade de resultados, esta técnica pode afetar a eficiência da relevância, pois como reduz a palavra até sua raiz, pode fazer com que os termos consultados percam a semântica original.
2.4 — Lematização (lemmatization)
Consiste em, dado uma forma de termo flexionada (plural, verbo conjugado, gênero), reduzi-lo ao seu lema. Por exemplo, reduzir “andando” para “andar”, “destruição” para “destruir”.
Este processo, assim como o Stemming, aumenta a quantidade de retorno de documentos das consultas e também deve receber uma análise para verificar se não influenciará na qualidade dos resultados.
3. Índices
Para que a consulta seja efetuada com mais eficiência, ao invés de pesquisarmos diretamente nos documentos, são criados os índices que nos informam em quais documentos os termos estão e, de acordo com o algoritmo processado, qual sua frequência nos documentos, possibilitando uma maior assertividade no retorno dos resultados e fazendo com que a probabilidade de uma melhor relevância seja maior. Assim, abordarei alguns tipos de index e darei uma breve introdução nos algoritmos mais utilizados.
3.1 — Índices para consultas por frase (phrase queries)
Além das consultas simples por termos únicos, também é utilizada a consulta por frase, que possui aproximadamente 10% do volume das consultas da web. Essas consultas consistem quando 2 ou mais termos são utilizados na consulta, como por exemplo Universidade de São Paulo, onde os resultados só serão relevantes se contiverem os termos nesta ordem.
Existem algumas formas de atingirmos este objetivo, sendo uma delas a que chamamos de biword index, a qual considera o termo como um par de palavras na formação do índice. Por exemplo, no texto “a Aline tem a blusa azul”, “a Aline”, “Aline tem”, “tem a”, “a blusa” e “blusa azul” seriam termos distintos. Ao seguirmos esta divisão, alguns casos seriam resolvidos mas ainda sim este algoritmo nem sempre nos devolveria os resultados esperados, principalmente em frases longas.
Outra forma para resolvermos o problema de consulta por frases é o Índice Posicional (positional índex). Esta é uma das formas mais utilizadas, e para cada termo ela armazena a posição o qual ele aparece em cada documento. Considerando a frase anterior como um documento, o index ficaria da seguinte forma:
Com a estrutura acima possível que a busca seja feita mais eficientemente que o biword, além de possibilitar a busca por proximidade de termos.
3.2 — Algoritmos de criação de index
3.2.1 — Algoritmo BSBI
O algoritmo BSBI, após a tokenização, ordena os termos alfabeticamente e pelos id’s dos documentos os quais esses termos estão. Com os dados ordenados, o algoritmo agrupa os termos iguais, associando a eles a lista dos respectivos documentos onde aparecem. Finalmente são geradas as estatísticas, como a frequência dos termos para cada documento. Para pequenas quantidades de dados a memória pode ser utilizada mas, para grandes quantidades de dados, formas secundárias de armazenamento devem ser utilizadas. Neste último cenário é efetuado o merge, carregando um bloco de listas do armazenamento secundário para a memória, realizando a união (merge) e gravando-o novamente no armazenamento secundário. Isto torna o processo mais eficiente e menos custoso do que realizar estes processamentos no armazenamento secundário. Para exemplificar, segue exemplo deste processo:
Documento 1: a Aline tem a blusa azul
Documento 2: a bicicleta é azul
3.2.2 — Algoritmo SPIMI
Diferente do BSBI, o SPIMI pode trabalhar com conjunto de dados de qualquer tamanho, desde que haja espaço no disco. A diferença do SPIMI para o BSBI é que os termos são processados um a um, onde na primeira ocorrência deles, eles são adicionados no índice, e nas demais, eles são atualizados. Isto evita a necessidade da ordenação, fazendo que o processamento fique mais rápido e não necessitando a realização de merges constantes.
3.2.3 Índice Distribuído
Para conjuntos de dados extremamente grandes que não podem ser processados em máquinas únicas para criação de índices, o algoritmo de Índice Distribuído é utilizado. Como o nome já diz ele é processado de forma distribuída. Um dos mais conhecidos é o MapReduce.
3.2.4 Índice Dinâmico
Nos algoritmos anteriores consideramos que os documentos são estáticos, o que raramente ocorre, pois eles são incluídos, alterados e excluídos constantemente. Caso haja uma necessidade de que novos documentos sejam inclusos, uma solução é manter 2 índices, sendo um índice grande e principal e outro índice auxiliar, que fica na memória. As pesquisas são realizadas primeiramente no índice pequeno e, caso as repostas sejam poucas, o índice principal é acessado e o resultado dos dois índices unidos. Com o passar do tempo, o índice auxiliar pode ficar grande e, ao chegar neste ponto, ele deve ser unido (merge) com o índice principal.
4. Scoring e Rankeamento
No que vimos até agora, as consultas foram principalmente booleanas, ou seja, os documentos contém ou não contém os dados da consulta. Este tipo de consulta de certa forma é boa para usuários avançados que conhecem o domínio da consulta, mas geralmente é ruim para os demais.
Este tipo de pesquisa pode retornar um grande número de resultados e, em alguns casos, se adicionarmos mais um termo a consulta, a quantidade de resultado pode diminuir drasticamente, podendo até não retornar mais nenhum resultado.
Com o Scoring e Rankeamento os documentos mais relevantes são melhor ranqueados do que os menos relevantes, fazendo com que apareçam nas primeiras posições. Um dos principais desafios é: como podemos pontuar esses documentos adequadamente de acordo com seu conteúdo e o parâmetro da consulta?
Um dos métodos propostos para isso é o Coeficiente de Jaccard que tem por princípio dividir a interseção dos termos dos documentos com os da consulta pela união dos 2 e medir a relevância entre 0 e 1, onde 0 não possui relevância e 1 possui a maior relevância. Como exemplo, na consulta “bicicleta azul” e o documento “azul da cor do céu”, o coeficiente seria 1/6, pois contém 1 termo em comum (azul) e 6 termos da união. Um dos problemas do Jaccard é que ele não considera a frequência dos termos, o que impacta na assertividade do resultado final.
Outro método é o bag of words(saco de palavras), onde não são consideradas as ordens dos termos no documento. Documentos com “Brasil vence França” e “França vence Brasil” são considerados iguais e com a mesma relevância. De certa forma, este método é um retrocesso pois, com o Índice Posicional, apresentado nos tópicos anteriores, já conseguiríamos melhor relevância do que este método.
Além desses métodos citados acima, são utilizados também os métodos baseados na frequência dos termos (tf), que é definido pelo número de vezes que um termo aparece no documento. De qualquer forma, se utilizarmos somente o tf para a criação do scoring e rankeamento, um documento que apareça 10 vezes o termo (tf = 10) não é necessariamente mais relevante que um documento que apareça 1 vez (tf=1), pois a relevância não aumenta proporcionalmente com o tf. Se aplicarmos o log neste cálculo amortecemos o resultado mas mesmo assim é necessário algo mais assertivo para criarmos o rankeamento. Por isso, além de ser utilizada a frequência do termo no documento (tf), é considerada a frequência do termo na coleção (idf), que é conhecida como tf-idf. O tf-idf define a relevância do termo dentro da coleção de documentos. Resumidamente, ele atribui um peso para cada documento, sendo este peso o número de ocorrências do termo no documento (Dj), modificada por uma escala de importância do termo (Tj), conhecida como frequência inversa do documento (idf). O tf-idf é um dos métodos mais utilizados para rankeamento de documentos.
5. Próximos Passos
Atualmente, verificamos que a busca na web em informações de textos não estruturadas já é possível e mecanismos de buscas como Google e Bing nos permitem obter excelentes resultados para as consultas realizadas. Porém, outras formas de informações como vídeo, imagens e aúdio, também fazem parte desse conjunto de informações não estruturadas e necessitam fazer parte destas buscas. Isto é um desafio, conseguirmos identificar em vídeos, por exemplo, não somente o que esta sendo falado, mas também o contexto, o cenário, e qual é a “semântica” do vídeo, para que possamos indexá-los, gerando índices para consultas futuras. Ou seja, além da necessidade de otimização e evolução das consultas em textos, as consultas em outros formatos de dados não-estruturados devem ser evoluídas.
6. Conclusão
Nestes artigos pudemos visualizar como funciona uma máquina de busca padrão, alguns conceitos do modelo booleano, do índice invertido, e conhecer resumidamente as fases da criação da estrutura para consultas, além da citação de alguns algoritmos de criação de índice e de ranking.
Verificamos também que há um caminho para que possamos evoluir para abranger de forma ampla, com assertividade e relevância outros tipos de informações não estruturadas, como imagens, vídeos e áudio.
Com isto, agora temos uma visão geral do processo de Recuperação de Informação, desde a coleta dos documentos até a criação de ranking, concluindo que as informações devem ser retornadas com maior precisão e relevância para atendimento das necessidades do usuário.
