|
[ Voltar ] MAC499 - Proposta de MonografiaRecuperação de Informações por Álgebra Linear Computacional
IntroduçãoCom a evolução de bibliotecas digitais e o crescimento exponencial da quantidade de documentos disponíveis na Internet, tornaram-se necessários métodos eficazes para o armazenamento, o processamento e a recuperação de informações. Tais métodos podem ser aplicados a um grande banco de dados, quando implementados em sistemas de alta performance. Um exemplo de sistema de grande escala conhecido atualmente é o Google. Seus usuários definem perguntas e o sistema fornece conjuntos de documentos relacionados a elas através de um processamento de dados. Técnicas automáticas desse tipo, no entanto, não são fáceis de implementar. Problemas associados à ambigüidade da linguagem natural, aos diversos idiomas existentes e aos tipos de informações (texto, figuras, áudio e vídeo) motivam pesquisadores a estudarem diversas maneiras de contorná-los. Indexar grandes quantidades de dados usando recursos limitados de processamento e retornar documentos realmente relevantes às pesquisas são ainda grandes desafios. Isto pode ser observado em eventos internacionais conhecidos como o Text REtrieval Conference (TREC) [9], que ocorre anualmente desde 1992. Um sistema bem conhecido (inclusive pelos participantes do TREC), com grandes contribuições na área, é o SMART (System for the Mechanical Analysis and Retrieval of Text) [7,8], baseado no modelo vetorial. Uma variante mais recente do método é o LSI (Latent Semantic Indexing) [2]. O modelo vetorial, que é o principal objeto de nosso estudo, armazena informações em uma matriz, onde cada coluna representa um documento e cada linha está associada a um termo do "dicionário". A pesquisa do usuário ao banco de dados é representada por um vetor. Com isso, os documentos relevantes à pesquisa são identificados utilizando-se, por exemplo, a decomposição por valores singulares (SVD) [5]. [ Topo ]
ObjetivosO foco deste trabalho é, essencialmente, verificar como a Álgebra Linear Computacional pode ser usada no contexto do modelo vetorial para Recuperação de Informações. Em especial, veremos como a fatoração QR e a decomposição SVD podem ser úteis para indexar grandes quantidades de texto. Apesar do projeto envolver principalmente o estudo das técnicas, algumas implementações e certos experimentos também serão realizados. Algoritmos como a fatoração QR (com rotações de Givens, Householder e pivoteamento de colunas) [5,10,11] e a decomposição por valores singulares [5] serão implementadas usando o Octave [4], linguagem de alto nível usada para computação numérica. Experimentos serão feitos com os programas implementados e com o já citado SMART. [ Topo ]
Atividades já realizadasEste projeto tem como base o artigo Matrices, Vector Spaces, and Information Retrieval de Berry et al [2]. A partir deste, foram encontradas outras referências, as quais possibilitaram a abordagem dos seguintes tópicos:
[ Topo ]
Cronograma de atividades para o segundo semestrePara os primeiros quatro meses do semestre, todos os itens listados abaixo envolvem o estudo, a análise e a criação de um texto detalhado: Julho: Criação de "thesaurus"; comparação entre termos e
entre documentos; operações com vetores de pesquisas.
Para o mês de Novembro, espera-se que o foco do trabalho seja, essencialmente, a preparação do pôster, da apresentação e da parte subjetiva da monografia. [ Topo ]
Estrutura esperada da monografiaA monografia será composta da parte técnica e da parte subjetiva. A primeira seguirá os moldes dos relatórios do PIBIC/CNPq e da FAPESP, contendo os seguintes tópicos:
Na segunda parte da monografia serão relacionados a experiência obtida na iniciação científica com o Bacharelado em Ciência da Computação. Desse modo, os seguintes itens serão abordados:
[ Topo ]
Bibliografia[1] R. Baeza-Yates, B. Ribeiro-Neto. Modern Information Retrieval. Addison-Wesley, 1999. [2] M. W. Berry, Z. Drmac, E. R. Jessup. Matrices, Vector Spaces, and Information Retrieval. SIAM Review, 41:2, pp. 335-362, 1999. [3] M. W. Berry, S. T. Dumais, G. W. O'Brien, Using Linear Algebra for Intelligent Information Retrieval, SIAM Review, 37, pp. 573-595, 1995. [4] J. W. Eaton. GNU Octave Manual. Network Theory Ltd., 2002. [5] G. H. Golub, C. Van Loan. Matrix Computations. 3rd ed. Johns Hopkins University Press, Baltimore, MD, 1996. [6] G. Kowalski, M. T. Maybury. Information Storage and Retrieval Systems, Theory and Implementation. Kluwer Academic Publishers, 2000. [7] G. Salton, M. J. McGill. Introduction to Modern Information Retrieval. McGraw Hill, New York, 1983. [8] System for the Mechanical Analysis and Retrieval of Text (SMART). ftp://ftp.cs.cornell.edu/pub/smart. [9] Text REtrieval Conference (TREC), http://trec.nist.gov, Aug 01, 2000. [10] L. N. Trefethen, D. Bau. Numerical Linear Algebra. Society for Industrial and Applied Mathematics, 1997. [11] D. S. Watkins. Fundamentals of Matrix Computations. John Wiley & Sons, 1991. [ Topo ]
|