Knowledge compilation for belief function: from theory to practice
Supervisor: Daira Pinto Prieto (d.pintoprieto@vu.nl)
Background
Knowledge compilation is a collection of computational approaches that allows to break down some (computationally) hard problems into an offline and an online phase. If the online part can be computed in polynomial time, the problem is said to be compilable to P. In belief function theory there are some rules of combination of evidence whose computation is compilable to P. Therefore, we can think of real-world scenarios where uncertain evidence can be combined and decombined using these rules, overcoming the challenge of their computational complexity.
Description
This project aims to explore the application of knowledge compilation techniques for real reasoning scenarios under uncertainty. Some milestones of this project are:
- Getting familiar with belief function theory and knowledge compilation techniques.
- Following existing literature, implementing a knowledge compilation solution to compute some rules of combination for belief functions.
- Study the advantages and disadvantages of this solution compared to other algorithms.
- Extending the literature on the computation of combination rules through knowledge compilation. This may include adapting propositional formulas to accept more general evidence, or defining new propositional formulas to implement other rules of combination.
Depending on the student’s interests, the proportion between the theoretical and the practical parts of the thesis can vary.
Literature
Pierre Marquis. 2015. Compile! In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI’15). AAAI Press, 4112-4118.
Daira Pinto Prieto. Combining Uncertain Evidence: Logic and Complexity. Chapter 6. PhD thesis, University of Amsterdam, 2024. ISBN 978-94-6473-618-2.
Daira Pinto Prieto, Ronald de Haan, and Sébastien Destercke. 2024. How to efficiently decombine belief functions? In Proceedings of the 20th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU 2024).