Aluna: Camila Mari Matsubara
Supervisor: Prof. Dr. Marcelo Finger

Proposta [pdf]

Resumo da Monografia

A teoria de Revisão de Crenças surgiu devido à necessidade de modelar o comportamento de sistemas dinâmicos quando sofrem alteração em alguma informação do seu conteúdo. Tal teoria começou a se solidificar no início dos anos 80, com a publicação dos Postulados AGM (Alchorrón, Gardenfor, Makinson) [2], que descrevem as mínimas propriedades que um processo de mudança deve ter (que pode ser uma contração, expansão ou revisão - o caso mais interessante de se estudar).

Existem variantes do problema, onde a representação do sistema dinâmico em foco é alterada, conforme o que se deseja modelar. Neste trabalho, o problema será estudado sob a modelagem com Probabilidades Imprecisas. Neste caso, cada crença do sistema é representada por uma sentença da Lógica Proposicional Clássica, e cada sentença está associada a um intervalo de probabilidade. A interpretação é que as informações disponíveis ao sistema impõe que a verdadeira probabilidade da sentença está em um ponto dentro desse intervalo.

Uma das aplicações desse tipo de modelagem é o controle de requisitos no processo de desenvolvimento de software. Assumindo que a lista de requisitos corresponde ao sistema dinâmico, e que cada requisito deve ser atendido dentro de um intervalo de probabilidade, pode-se facilmente estimar o grau em que todos os itens da especificação serão afetados no caso de alteração no intervalo de algum item arbirário.

Objetivos

O objetivo deste trabalho é o estudo da Revisão de Crenças, especialmente com probabilidades imprecisas.

Dado um conjunto de crenças, a modelagem do seu comportamento visa, entre outras coisas, manter o conjunto consistente. Existem três operações de revisão: Contração (quando se deseja retirar uma informação. Para manter a consistência, eventualmente, é necessário retirar outras crenças); Expansão (quando se deseja adicionar uma crença consistente ao conjunto atual); e a Revisão propriamente dita (quando se deseja adicionar uma informação que contradiz o conjunto de crenças inicial).

Porém, no contexto probabilístico, apenas a operação de Revisão faz sentido, pois a Contração de uma sentença corresponde a revisá-la tornando seu intervalo de probabilidade (0,1), isto é, nada se sabe sobre esta sentença. E a Expansão corresponde ao caso fácil da Revisão, basta adicionar a sentença no conjunto pois ele se mantém consistente. Portanto, o trabalho se concentrará na operação de Revisão.

Apesar de o material disponível na literatura atualmente sobre a modelagem com intervalos de probabilidade ser escasso, objetivamos elaborar um estudo completo e robusto, analisando o seu contexto, descrevendo o problema sob este ponto de vista, e buscando técnicas e/ou algoritmos que solucionem o problema.

Esta monografia tem como objetivo descrever com detalhes todos os passos durante o trabalho, assim como registrar os resultados obtidos com os estudos.

Atividades já realizadas

• Levantamento bibliográfico de referências sobre a Revisão de Crenças e Revisão de Crenças Probabilísticas.
• Descrição do problema de Revisão de Crença sob uma nova perspectiva, assumindo probabilidades imprecisas associadas a cada crença.
• Definição de algumas restrições para a resolução do problema, a fim de obter propriedades equivalentes às da Revisão de Crenças original.
• Descrição de um algoritmo que manipula probabilidades imprecisas, a fim de auxiliar no processo da revisão.

Cronograma de atividades

Ativ. / Mês	Jun	Jul	Ago	Set	Out	Nov
1	x	x	x
2		x	x	x
3				x	x
4					x	x
5	x	x	x	x	x	x

Atividades:

1. Estudo de heurísticas para melhorar a qualidade das soluções
2. Implementação de algoritmos que resolvem o problema eficientemente
3. Análise de resultados
4. Preparação do pôster e da apresentação do trabalho
5. Preparação da Monografia

Estrutura esperada da Monografia

A monografia terá uma parte técnica e uma parte subjetiva, conforme descrito no roteiro para preparação. Cada parte estará dividida nos seguintes itens:

Parte Objetiva:

• Introdução: Apresenta, com uma visão geral, o problema a ser tratado, suas motivações e aplicações desses conceitos no mundo real.
• Conceitos e tecnologias: Definição dos conceitos utilizados na monografia; um estudo sobre a literatura existente; um estudo dos casos de Revisão de crença modelados em contextos diferentes ao da probabilidade imprecisa.
• Atividades realizadas e resultados obtidos: Descrição da metodologia aplicada ao longo do trabalho, e apresentação dos resultados obtidos durante os estudos.
• Conclusão da parte objetiva.
• Referências bibliográficas.

Parte Subjetiva:

• Experiência e aprendizado
• Desafios e frustrações encontrados durante a realização do trabalho.
• Disciplinas cursadas no BCC mais relevantes e a aplicação dos seus conceitos no trabalho.
• Trabalhos futuros.

Referências

1. Chan, H.; Darwiche, A. On the revision of probabilistic beliefs using uncertain evidence. Artificial Intellingence. Postprint, 2005.
2. Gardenfors, Peter. Knowlegde in flux: Modeling the Dynamics of Epistemic States. Massachussets Institute Technology, 1988.
3. Hansen, Pierre; Jaumard, Brigitte. Probabilistic Satisfiability. Montreal, Canada - March, 1996.
4. Sousa, Thiago Carvalho de. Revisão de modelos formais de sistemas de estados finitos. Dissertação de mestrado. Instituto de Matemática e Estatística. São Paulo, 2007.
5. Wasserman, Renata. Resource-bounded Belief Revision. Dissertação de doutorado. University of Amsterdam, 1999.