Changement de croyances local et application à l'information spatiale
Institution:
Aix-Marseille 1Disciplines:
Directors:
Abstract EN:
When facing uncertain, incomplete and inaccurate information, we need a belief change operation in order to manage the belief evolution in presence of new information. The problem of belief change, in general, is known as a NP-difficult one, and there does not exist an efficient algorithm that can process huge amount of data. To circumvent this problem, we are interested in local belief change operations, namely local belief revision, local belief contraction, and local belief expansion operations. A new model -the C-structure model- for belief representation and local belief revision is proposed. A C-structure represents a thematic view of the overall knowledge of an agent with a good understanding of the interactions between topics. Hence, it provides the agent with an extra-structure, which helps circumscribing the relevant part of beliefs during a revision operation. Then, four local belief change operators are defined, based on the C-structure model : one for local expansion, one for local contraction, and two for local belief revision, internal and external ones. The contraction and revision operators are proved sound and complete by comparing them to traditional non local belief change operators. Local belief revision based on the C-structure model is characterized semantically ; first, in the special case of fully overlapping theories, then in the general case of arbitrary theories. Finally, the spatial information is considered : it provides an interesting application to the C-structure model and the associated revision operations. A new model -the G-structure model- is defined. Then, a new local belief revision approach, based on the G-structure model, is proposed and compared to the REM approach which is based on the Reiter algorithm for diagnosis.
Abstract FR:
Lorsque nous sommes confrontés à des informations incomplètes, incertaines, imprécises ou évolutives, nous avons besoin d’un mécanisme de changement de croyances car celles-ci évoluent en présence d’une nouvelle information. Ce problème de changement de croyances est connu pour être un problème NP-difficile, pour lequel il n’existe pas d’algorithmes efficaces pouvant traiter un volume important de données. Pour résoudre ce problème, cette thèse se concentre sur les approches locales du changement de croyances, à savoir la révision, la contraction et l’expansion locales de croyances. Nous proposons un nouveau modèle, appelé le modèle C-structure, pour la représentation et la révision locale de croyances. Une C-structure représente une vision thématique de la connaissance globale d’un agent avec une bonne compréhension des interactions entre thèmes. Elle permet d’équiper l’agent d’une extra-structure qui facilite l’introduction de la notion de pertinence lors de la révision de croyances. Ensuite, quatre opérateurs de changement de croyances locaux sont définis, basés sur le modèle C-structure. Ces opérateurs locaux comprennent un opérateur d’expansion, un opérateur de contraction et deux opérateurs de révision, interne et externe. Nous prouvons que les opérateurs de révision et de contraction locales sont complets et corrects en les comparant à des opérateurs traditionnels non locaux. La révision de croyances locale basée sur le modèle C-structure est caractérisée sémantiquement, d’abord dans le cas spécial des théories complètement chevauchantes, ensuite dans le cas général des théories arbitraires. Enfin, comme application aux modèles et approches de révision locale précédents, nous définissons un nouveau modèle, nommé G-structure, pour représenter et réviser localement l’information spatiale. Une approche de révision locale basée sur ce dernier modèle est proposée et comparée à l’approche REM basée sur l’algorithme de Reiter pour le diagnostic.