Inteligência Artificial

Segundo trimestre de 2008

Horário alfa: 2a (8-10), 4a (10-12)

Sala: S 501 (bloco B)

Email do professor: jeronimo.pellegrini ufabc edu br

Novidades:

03/09 -- Conceitos finais disponíveis
28/08 -- Notas parciais disponíveis
11/08 -- Ordem das avaliações modificada (como acordado em sala)
10/08 -- Exercícios 13 e 14 (Processamento de Língua Natural) disponíveis ***
07/08 -- Prazo do exercício 12 adiado
26/07 -- *** Exercício 12 (Aprendizado Estatístico) disponível ***
21/07 -- Nova indicação de livro (aprendizado estatístico, Alpaydin)
21/07 -- *** Exercício 11 (Planejamento) disponível ***
11/07 -- * Prazo para o exercício 9 *
09/07 -- * Prazo para o exercicio 8 *
05/07 -- * Exercício 10, não obrigatório disponível *
01/07 -- *** Exercício 9 (Aprendizado por Reforço) disponível ***
01/07 -- Dica para o exercício 7
27/06 -- *** Exercício 8 (Tomada de Decisões em Sequência) disponível ***
26/06 -- *** Exercício 7 (Teoria da Utilidade) disponível ***
26/06 -- Prova adiada
23/06 -- Exercício 3 (jogos) teve o prazo adiado
23/06 -- Um texto recomendado sobre Teoria da Utilidade
22/06 -- Artigo recomendado sobre HMMs (Hidden Markov Models)
19/06 -- Lista de exercícios entregues
19/06 -- Dica para exercício de jogos
19/06 -- Exercícios: quando fizerem o texto, entreguem em PDF
18/06 -- Nova indicação de livro (planejamento, LaValle)
15/06 -- *** Exercícios 5 e 6 (Redes Bayesianas, Algoritmos Genéticos) disponíveis ***
15/06 -- Mais um livro recomendado para Linguística Computacional
12/06 -- *** Exercício 4 (Ontologias) disponível ***
12/06 -- Ordem dos tópicos alterada ("Planejamento" foi p/a frente)
11/06 -- Lista inicial de temas para trabalho
08/06 -- Leitura recomendada para 11/06 modificada
08/06 -- Dois artigos sobre representação do conhecimento
08/06 -- Livro recomendado sobre sistemas multiagentes
07/06 -- Link para ferramenta: Protégé
06/06 -- Livros e artigo recomendados sobre representação do conhecimento
06/06 -- *** Exercício 3 (jogos) disponível  ***
06/06 -- Aula sobre sistemas multi-agentes mudou para o final do curso
06/06 -- Nova indicação de livro (sistemas multiagentes, Vidal)
05/06 -- Exercício 1 teve prazo adiado (o livro não está disponível na biblioteca)
04/06 -- A aula de 04/06 será só sobre Computação Evolutiva
04/06 -- Nova indicação de livro (computação evolutiva, Linden (RL))
03/06 -- Nova indicação de livro (probabilidades, DeGroot)
03/06 -- Listas de exercícios disponíveis

Ementa

Introdução. Técnicas de busca. Jogos adversariais. Representação do conhecimento. Sistemas baseados em conhecimento. Tratamento de incerteza.

Dinâmica do curso

A primeira aula começa com questões administrativas e segue com um apanhado geral da história e diferentes conceituações da IA

Nas outras aulas, recomendo fortemente que o aluno leia os textos previamente indicados.

• Leia os textos com calma! Não adianta "ler em diagonal".
• Programe-se! Se um texto está marcado para o dia 16/06, por exemplo, isto significa que você já deverá tê-lo lido no dia 16. Você deve prestar atenção ao conteúdo e tamanho de cada leitura recomendada para se preparar para as aulas.
• How to Study, de William Rapaport (interessante, pode ajudar muito).

Avaliação

A avaliação tem quatro componentes:

• Uma prova
• Um trabalho
• Exercícios
• Participação em uma discussão (marcada inicialmente para o último dia letivo)

Cópias em provas ou trabalhos resultam em conceito F na disciplina.

Exercícios / mini-trabalhos

• 1 - Probabilidades. Entregar em papel, manuscrito. Prazo: 11/06 18/06 (quarta) * adiado
• 2 - Algoritmos genéticos. Pode ser por e-mail. Prazo: 11/06 (quarta)
• 3 - Jogos. Pode ser por e-mail. Prazo: 23/06 30/06 (segunda) * adiado
• 4 - Representação do Conhecimento. Pode ser por e-mail. Prazo: 30/06 (segunda)
• 5 - Algoritmos Genéticos (II). Pode ser por e-mail. Prazo: 18/06 (quarta)
• 6 - Redes Bayesianas. Pode ser por e-mail. Prazo: 23/06 (segunda)
• 7 - Teoria da Utilidade. Pode ser por e-mail. Prazo: 08/07 14/07 (segunda) * adiado
• 8 - Tomada de Decisões em Sequência. Pode ser por e-mail. Prazo: 21/07 (segunda)
• 9 - Aprendizado por Reforço. Pode ser por e-mail. Prazo: 28/07 (segunda)
• 10 - Jogos e um pouco de tudo. Não precisa entregar! Este é para quem gosta de IA e jogos, e quer algo para fazer por muito tempo.
• 11 - Planejamento Pode ser por e-mail. Prazo: 04/08 (segunda)
• 12 - Aprendizado Estatístico. Prazo: 06/08 (quarta) 11/08 (segunda)
• 13 - Processamento de Língua Natural. Prazo: 20/08 (quarta)
• 14 - Processamento de Língua Natural (II). Prazo: 20/08 (quarta)

Dicas:

• No exercício 3, pode ser necessário evitar a explosão combinatória. Vimos algumas dessas técnicas em aula (estão também no livro)
• No exercício 7, procure literatura de Microeconomia e de Filosofia da Ciência

Exercícios entregues

Veja a tabela com noas e exercícios entregues. ESTA NOTA NÃO É DEFINITIVA! Ainda á possível entregar trabalhos, e ainda há notas de exercícios a enrtar no cômputo!

Programa

Antenção: este é um cronograma aproximado! O ritmo pode mudar e aulas podem mudar de ordem durante o curso. As colunas "Referências" mostram a leitura recomendada para cada aula. As siglas podem ser encontradas na seção de bibliografia, abaixo.

Algumas leituras recomendadas não estão definidas ainda; outras estão "mais ou menos" definidas (sem o capítulo e seção). Estas informações serão refinadas durante o curso.

Como há apenas quatro trabalhos, faremos as apresentações em um único dia. Isto provavelmente nos permitirá adiar a data da prova (se todos concordarem -- isto deve ser confirmado ainda).

Veja os slides que haviam sido peparados para a aula 1.

Slides da aula sobre busca com informação.

Importante: precisaremos de um pouco de Teoria de Probabilidades a partir da aula sobre Incerteza até o final do curso. Leiam (ou re-leiam) textos de introdução à Probabilidade, variáveis aleatórias discretas e distribuições "famosas" (normal, exponencial, etc), e façam exercícios. É particularmente importante entender: conceitos básicos de análise combinatória, probabilidade condicional, Teorema de Bayes.

Ferramentas

Embora não haja um grande trabalho de implementação a ser feito, alguns exercícios poderão envolver programação ou uso de feramentas. Darei instruções específicas com cada trabalho. Os links abaixo não são necessariamente algo a ser usado nos trabalhos; são exemplos de ferramentas que podem ser usadas em IA.

• PDDL
• ZMDP
• Protégé

Trabalhos

Bibliografia

As siglas em negrito são as usadas como leitura recomendada no programa da disciplina.

O Russel & Norvig é o livro-texto; será usado na maioria das aulas.

• AIMA Russel & Norvig Inteligência Artificial. Há 3 cópias na biblioteca.

Usaremos outros para assuntos específicos:

• RL Sutton & Barto Reinforcement Learning Disponível livremente na Internet.
• ML Mitchell, T. Machine Learning Há uma cópia na biblioteca.
• VL Vieira, R. Lima, V. L. S. Lingüística computacional: princípios e aplicações. Jornada de Atualização em Inteligência Artificial (JAIA) 2001.
• PW Pellegrini & Wainer Processos de Decisão de Markov: um tutorial Fornecerei uma cópia.

Além destes, distribuirei mais material ao longo do curso.

Outras sugestões

Há também livros que não existem na biblioteca, mas que merecem ser mencionados, e alguns textos que poderão ser usados por duplas no trabalho prático.

Sobre probabilidades:

• DeGroot. Probability and Statistics. Tem na biblioteca.
• Grinstead, C. & Snell, J. Introduction to Probability. Disponível na Internet.
• O livro de Manning, C. D. & Schütze, H. (veja a seção de Linguística Computacional, abaixo) tem uma introdução à Probabilidade, com exercícios.
• Knuth & outros. Matemática Concreta.

Incluirei mais recomendações em breve.

Sobre aprendizado estatístico:

• ML Mitchell, T. Machine Learning Há uma cópia na biblioteca.
• Alpaydin, E. Introduction to Machine Learning
• ESL Hastie, T; Tibshirani, R; Friedman, J The Elements of Statistical Learning: Data Mining, Inference, and Prediction.

Teoria da Utilidade

• Bertsekas, D. Dynamic Programming and Optimal Control Há um apêndice sobre Teoria da Utilidade (apêndice G).

Hidden Markov Models (HMMs)

• Rakesh Dugad tem um excelente tutorial sobre HMMs
• Material didático de Steven Bird; e a página do curso dele
• Rabiner, L. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Veja a errata

Processos de Decisão de Markov:

• Puterman, M. Markov Decision Processes.
• Bertsekas, D. Dynamic Programming and Optimal Control.

Sobre planejamento:

• LaValle, S. Planning Algorithms. Disponível inteiro sem custo, mesmo tendo sido lançado em 2006!
• AP Ghalab, Nau & Traverso Automated Planning: theory and practice.
• Rintanen, J. Introduction to Automated Planning. Disponível no site do autor (em publications).

Sistemas Multiagentes

• Vidal, J. Fundamentals of Multiagent Systems with NetLogo Examples. Disponível (mas incompleto -- ele não fez o último capítulo ainda)
• Hahn, C. A Domain Specific Modeling Language for Multiagent Systems. É bem simples, dá pra ler em 10 minutos. Só para ver algo que foi publicado no AAMAS.
• Marcolino, L. & Chaimowicz, L. A Coordination Mechanism for Swarm Navigation: Experiments and Analysis. Também, só um exemplo de artigo do AAMAS.
• Chalkiadakis, G. & Boutilier, C. Sequential Decision Making in Repeated Coalition Formation under Uncertainty. Também do AAMAS, sobre tomada sequencial de decisões. Aprenda sobre Processos de Decisão de Markov e iteração de valores antes.
• Gerhard Weiss. Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence
• Michael Wooldridge. Introduction to MultiAgent Systems

Redes Neurais:

• FNN Fausett, L. Fundamentals of Neural Networks Este livro é muito bem escrito, embora não seja tão detalhado como o do Haykin. vale a pena como uma introdução ao assunto.
• Haykin, S. Redes Neurais O estilo e a organização deixam a desejar, mas é um livro importante e razoavelmente completo.

Representação do Conhecimento

• Shapiro, S. Knowledge Representation. consta da Encyclopedia of Cognitive Science; está disponível aqui, na página do autor
• Brachman, Ronald J., & Levesque, Hector J. Knowledge Representation and Reasoning. Se puder escolher só um livro sobre representação do conhecimento, que seja este.
• Sowa, J. Knowledge Representation: Logical, Philosophical, and Computational Foundations. Um livro razoavelmente novo.
• Baral, C. Knowledge Representation, Reasoning and Declarative Problem Solving.
• Haak, S. Filosofia das Lógicas. Só sobre a parte de Lógica, mas excelente neste aspecto.
• Davis, R.; Shrobe, H. & Szolovits, P. What Is a Knowledge Representation? AI Magazine 14(1): Spring 1993, 17-33. Disponível aqui, com mais informação sobre representação do conhecimento.
• Noy, N & McGuinness, D. Ontology Development 101: A Guide to Creating Your First Ontology. Disponível no site do Protégé
• Levesque, H. et al. Golog: a logic programming language for dynamic domains. Pegue no CiteSeer

Computação Evolutiva, otimização com colônias de formigas e otimização:

• EC de Jong, K. Evolutionary Computation: a unified approach.
• ACO Dorigo, M. Ant Colony Optimization.
• Linden, R. Algoritmos Genéticos: uma importante ferramenta da Inteligência Computacional.
• Maniezzo, V & Carbonaro, A. Ant Colony Optimization: an overview.
• DS Dorigo, M. & Socha, K. An Introduction to Ant Colony Optimization.Displnível no site do Marco Dorigo, na seção "publications"
• DBS Dorigo, M. Birattari, M & Stützle, T. Ant Colony Optimization, também na página do Dorigo.
• Whitley, D. A Genetic Algorithm Tutorial, no Citeseer.

Linguística Computacional:

• Manning, C. D. & Schütze, H. Foundations of Statistical Natural Language Processing. A introdução pode ser baixada livremente do site do livro na MIT Press, e livro pode ser lido on-line. Este é um excelente livro!
• Pereira, F. & Shieber, S. Prolog and Natural Language Analysis. O livro está disponível livremente.
• Jurafsky, D. & Martin, J. Speech and Language Processing.

Assuntos relacionados e visões diferentes:

• Carolyn Sobel The Cognitive Sciences.
• Minsky, M. The Society of Mind.
• von Neumann, J. O Computador e o Cérebro.
• Wilson, R; Keil, F. The MIT Encyclopedia of the Cognitive Sciences.
• Pessis-Pasternak, G. Do Caos à Inteligência Artificial.
• Teixeira, J. F. Filosofia da Mente e Inteligência Artificial.
• McDermott, D. Mind and Mechanism.
• Brooks, R. A. Cambrian Intelligence.