Generating Random Logic Programs Using Constraint Programming
This work addresses a bottleneck for researchers developing inference algorithms in probabilistic logic programming by providing a scalable tool for comprehensive testing, though it is incremental as it builds on existing constraint programming methods.
The authors tackled the problem of limited testing for probabilistic logic program inference algorithms by developing a constraint programming approach to generate random logic and probabilistic logic programs, introducing a new constraint to control independence structure. They validated the model with a combinatorial proof and used it to compare inference algorithms across synthetic problems, enabling developers to evaluate algorithms across diverse instances.
Testing algorithms across a wide range of problem instances is crucial to ensure the validity of any claim about one algorithm's superiority over another. However, when it comes to inference algorithms for probabilistic logic programs, experimental evaluations are limited to only a few programs. Existing methods to generate random logic programs are limited to propositional programs and often impose stringent syntactic restrictions. We present a novel approach to generating random logic programs and random probabilistic logic programs using constraint programming, introducing a new constraint to control the independence structure of the underlying probability distribution. We also provide a combinatorial argument for the correctness of the model, show how the model scales with parameter values, and use the model to compare probabilistic inference algorithms across a range of synthetic problems. Our model allows inference algorithm developers to evaluate and compare the algorithms across a wide range of instances, providing a detailed picture of their (comparative) strengths and weaknesses.