Curso de Pós-graduação em Ciência da Computação
Recuperação de Informação - Máquinas de Busca na Web (DCC923)

Última alteração: 01 de Março de 2015

Primeira aula: 04 de Março de 2015

1º semestre de 2015
Carga horária: 60 horas
Pré-requisito para a disciplina: Algoritmos e Estruturas de Dados III
Horario : Segunda: 09:25 - 11:05, Quarta: 09:25 - 11:05
Professores: Berthier Ribeiro-Neto e Nivio Ziviani
Monitor: Sabir Ribas

Introdução

Recuperação de Informação (RI) é a atividade de recuperar itens de informação armazenados em um meio que possa ser acessado por computador. Um item de informação é geralmente constituído de texto (tais como documentos diversos, páginas Web, livros, etc.), embora possa conter outros tipos de dados tais como fotografias, gráficos e figuras. RI lida com a representação, armazenamento, organização e acesso a itens de informação. A representação e organização dos itens de informação deve prover ao usuário acesso facilitado à informação de seu interesse.

A área de RI cresceu muito em importância com a introdução da Web. A despeito de seu sucesso, a Web introduziu uma série de problemas por si mesma. De fato, encontrar informação util na Web é frequentemente uma tarefa tediosa e difícil. A maior dificuldade é a ausência de um modelo de dados claramente definido. Isto implica que a semântica e a estrutura dos dados é frequentemente mal definida e de baixa qualidade. Tais dificuldades tem atraído a atenção para a área de RI e suas técnicas como soluções promissoras. Além disso, máquinas de busca formam a principal infraestrutura tecnológica de empresas gigantes como Google e Yahoo.

O principal objetivo da disciplina é estudar algoritmos e estruturas de dados para sistemas de busca na Web. Uma máquina de busca localiza documentos a partir das necessidades de informação colocadas pelo usuário, por meio de uma consulta formal. Em máquinas de busca, essa necessidade de informação deve primeiro ser traduzida em termos de um conjunto de palavras chave que são então usados na formulação de uma consulta. Dada a consulta do usuário, o objetivo maior de uma máquina de busca é obter informação que é útil ou relevante para o usuário.

Objetivos Específicos da Disciplina

O objetivo principal da disciplina é investigar o projeto e implementação de técnicas e ferramentas que possibilitem o desenvolvimento de máquinas de busca para a WWW. Ao final do curso o aluno deverá conhecer em profundidade os principais componentes de uma máquina de busca para documentos Web. Além disso, são estudados tópicos adicionais tais como classificação de textos e algoritmos utilizados em sistemas de recomendação.

A disciplina terá três objetivos principais:

• Estudar os coletores de páginas Web.
• Estudar técnicas para geração de um índice para coleções de documentos web.
• Estudo e implementação dos principais modelos de recuperação de informação disponíveis na literatura. Esses modelos correspondem as estratégias de ranking implementadas pelas máquinas de busca.

Cada aluno terá que construir protótipos de dois dos três principais componentes de uma máquina de busca para a Web: indexador e processador de consultas. A partir de um conjunto de páginas coletadas da Web deverá ser criado um índice para ser utilizado pelo processador de consultas.

Programa

1. Coleta: arquitetura de um coletor de páginas web, principais problemas envolvidos.
2. Indexação: Arquivos invertidos e listas invertidas, compressão de textos, compressão de listas invertidas.
3. Modelagem: Modelos de RI, modelos clássicos de RI (booleano, vetorial e probabilístico), BM25, language meodels, generalized vector space model, set-based model.
4. Relevance Feedback: Vector model, clicks, local analysis.
5. Avaliação da Recuperação: Precisão e revocação, coleções de referência, paradigma de Cranfield, bpref, Kendall-Tau, crowdsourcing, clickthrough data.
6. Consultas: Consultas lógicas, consultas ordenadas por relevância, estruturas de acesso ao vocabulário, busca sequencial no vocabulário, busca exata e aproximada.
7. Calssification: machine learning, unsupervised and supervised algorithms, feature selection, evaluation metrics.
8. Properties of documents: Modeling natural languages, elimination of stopwords, keyword selection, taxonomies, compression.
9. Introdução a Sistemas de recomendação: definição do problema; algoritmos: colaborativos, baseados em conteúdo e híbridos; exemplos de algoritmos.

Bibliografia Básica

• Ricardo Baeza-Yates and Berthier Ribeiro-Neto: Modern Information Retrieval, Addison Wesley, 2011, 913 pages, Second edition.
• Ian H. Witten, Alistair Moffat e Timothy C. Bell: Managing Gigabytes: Compressing and Indexing Documents and Images, Morgan Kaufmann Publishers, 1999, second edition.
• Principais conferências:
• World Wide Web Conference (WWW)
• ACM Conference on Research and Development in Information Retrieval (SGIR)
• String processing and Information Retrieval (SPIRE)
• European Conference on Information Retrieval (ECIR)
• ACM Conference Information and Knowledge Management (CIKM)
• ACM Conference on Recommender Systems (RECSYS)
• Conferências de bancos de dados: por ex. Very Large Data Bases (VLDB), SIGMOD
• Principais periódicos:
• ACM Transactions on Information Systems (TOIS)
• ACM Transactions on Information Systems and Technology (TIST)
• Journal of the American Society for Information Science and Technology (JASIST)
• IEEE Transactions on Knowledge and Data Engineering (TKDE)
• Information Management and Processing
• Information Retrieval
• World Wide Web Journal (w3j.com)

Avaliação da Aprendizagem

Os alunos serão avaliados por meio de:

• Construção dos principais componentes de uma máquina de busca na web: indexador e processador de consultas.
• Uma prova
• Projeto de pesquisa:

  -- Seminário curto sobre especificação do projeto.

  -- Seminário final sobre o projeto.

  -- Um paper formato ACM de 6 páginas.

Acesso a Bibliotecas Online

Mais instruções no site www.biblioteca.icex.ufmg.br seguindo a opção Sites de Pesquisa dentro de links (ou com a bibliotecária).

• Portal Periódicos da CAPES (permite acesso a várias bibliotecas, inclusive a todo IEEE, a partir de qualquer endereço da UFMG, podendo ser acessado via site da biblioteca do ICEx (www.biblioteca.icex.ufmg.br)
• ACM: acesso a todas as publicações e conferências, de qualquer máquina do DCC/UFMG (www.acm.org/dl)
• Computer Science Bibliography, permite busca por autor, titulo de papers em geral (www.acm.org/sigs/sigmod/dblp/db/)
• IEEE: acesso a vários títulos da biblioteca online (www.computer.org), acesso via portal Periódicos da CAPES permite um acesso de cada vez, pegar senha com a bibliotecária
• Web of Science: contém informação bibliográfica de três bancos de dados: Science Citation Index Expanded, Social Science Citation Index, Arts and Humanities Citation Index (www.webofscience.fapesp.br)
• DBLP: computer science bibliography
• USENIX: Advanced Computing Systems Association (www.usenix.org), pegar senha com a bibliotecária
• Mathscinet (www.ams.org/mathscinet): acesso aos banco de dados Association Mathematical Society com cobertura nas áreas de matemática e computação, podendo ser acessado via site da biblioteca do ICEx (www.biblioteca.icex.ufmg.br)

Links úteis

1. Codigo para ser usado no TP1
2. Search Engines Information Retrieval in Practice
3. High Performance Index and Query Evaluation for IR
• Justin Zobel
• Alistair Moffat
4. Programa para geração de curvas revocação vs. precisão

Aulas, Slides e TPs (calendário tentativo: pode mudar)

Aula	Mês	Dia	Assunto	Referência	TPs
01	Mar	04	Apres (Berthier e Nivio)	MIR Chap1, CursoRI
02		09	Indexing (Nivio)	Indexing	TP1 (E)
03		11	Ranking in IR, Boolean model (Berthier)	MIR Chap3
04		16	Indexing (Nivio)	Vocabulario
05		18	Index Compression (Nivio)	Index compression
06		23	Vocabulario (Nivio)	Perfect hashing
07		25	Term weighting, Vector model (Berthier)	MIR Chap3
08		30	Probabilistic model, Set-based model, BM25 model (Berthier)	MIR Chap3
09		01	Probabilistic model, Set-based model, BM25 model (Berthier)	MIR Chap3
10		06	Pagerank (Sabir)	Paper, Pagerank, MIR Chap11
11		08	Text compression (Nivio)	Text compression, Z8.2, MIR Chap6	Projeto Pesquisa
12		13	Crawling (Nivio)	Olston-najork-2010 Crawling, MIR Chap12
13		15	Crawling (Nivio)	Olston-najork-2010 Crawling, SPIRE11, SPIRE13, Tese-Cristiano
		20	Recesso escolar
14		22	Query processing (Nivio)	Querying	TP2 (E)
15		27	Probabilistic model, Set-based model, BM25 model (Berthier)	MIR Chap3
		28	Entrevista 9:00 - 12:00h sobre projetos pesquisa (sala Berthier)	Ordem lexicográfica nome aluno, 15 minutos para cada projeto
		29	Não haverá aula
16	Mai	04	Query processing (Nivio)	Querying
		06	Não haverá aula
17		11	Query processing (Nivio)	Querying
18		13	Search evaluation I (Berthier)	MIR Chap4
19		18	Language models (Berthier)	MIR Chap3
20		20	Search evaluation II (Berthier)	MIR Chap4
21		25	Text Classification: the problem (Berthier)	MIR Chap8
22		27	Text classification: decision trees, KNN (Berthier)	MIR Chap8
23	Jun	01	Relevance feedback; Text classification: Rochio, Naive Bayes (Berthier)	MIR Chap5, MIR Chap8
24		03	Text classification: SVM & Ensemble (Berthier)	MIR Chap8
25		08	Prova
26		10	Devolução de prova; acerto seminários
27		17	Seminarios 1, 2, 3 e 4	Lista de seminarios
28		22	Seminarios 5, 6, 7 e 8	Lista de seminarios
24		22	Seminarios 9, 10, 11 e 12	Lista de seminarios
30		29	Seminarios 13, 14, 15 e 16	Lista de seminarios
31	Jul	01	Seminarios 17, 18, 19 e 20	Lista de seminarios