On Continuous Distributions and Parameter Estimation in Probabilistic Logic Programs (Over continue verdelingen en het schatten van parameters in probabilistische logische programma's)

In the last decade remarkable progress has been made on combining statistical machine learning techniques, reasoning under uncertainty, and relational representations. The branch of Artificial Intelligence working on the synthesis of these three areas is known as statistical relational learning or probabilistic logic learning.ProbLog, one of the probabilistic frameworks developed, is an extension of the logic programming language Prolog with independent random variables that are defined by annotating logical facts with probabilities. The separation of the logical and probabilistic part of the model is based on the distribution semantics. Driven by the demand for models that are able to handle continuous values and can be automatically optimized on training data, this thesis introduces several algorithms and extensions to the ProbLog language. Continuous-valued data arise naturally in robotics, human activity recognition and bio-medical applications. Moreover, the models used are complex and the available data is often noisy and incomplete. Hence tuning a model towards the specifics of theenvironment can hardly be done manually. This poses two crucial challenges for probabilistic programming languages such as ProbLog: processing continuous values and being able to learn from training data.This thesis makes four main contributions to the field of probabilistic logic learning. Hybrid ProbLog is an extension for ProbLog with continuous facts that allows for exact inference. Distributional Programs combine elements of ProbLog, Hybrid ProbLog and CP-Logic into a very expressive language for dealing with continuous distributions. A sampling-based inference algorithm is used to answer conditional queries, while the deterministic information inthe program guides the sampling process. LFE-ProbLog is able to learn the parameters of a ProbLog program from queries and proofs, while LFI-ProbLog is optimized to learn the parameters from partial interpretations. Together they cover the standard learning settings considered in PLL. All learning approaches have been evaluated in several relational real-world domains.I Foundations 3 1 Introduction 5 2 Preliminaries 11 2.1 Logic Programming........................... 11 2.1.1 Syntax.............................. 12 2.1.2 Semantics And Inference.................... 14 2.2 Binary Decision Diagrams....................... 16 2.3 Probabilistic Inference ......................... 19 2.4 Distribution Semantics......................... 20 3 ProbLog 21 3.1 Syntax And Semantics......................... 21 3.2 Inference................................. 24 3.3 Annotated Disjunctions ........................ 29 II Continuous Distributions 33 Outline of Part II 35 4 An Exact Inference Approach to Continuous Distributions 37 4.1 Hybrid ProbLog ............................ 38 4.1.1 Distribution Over Continuous Subprograms . . . . . . . . . 42 4.1.2 Success Probabilities of Queries. . . . . . . . . . . . . . . . 43 4.2 ExactInference............................. 47 4.3 Experiments............................... 52 4.4 Conclusions And Future Work..................... 55 5 An Approximate Inference Approach to Continuous Distributions 57 5.1 Distributional Programs........................ 58 5.1.1 Syntax.............................. 59 5.1.2 Distribution Semantics..................... 62 5.1.3 TP Semantics.......................... 63 5.2 Forward Sampling Using Magic Sets And Backward Reasoning . . 64 5.2.1 Probabilistic Magic Set Transformation . . . . . . . . . . . 64 5.2.2 Rejection Sampling With Heuristic Lookahead . . . . . . . 66 5.3 Experiments............................... 68 5.4 Related Work.............................. 72 5.5 Conclusions And Future Work..................... 73 Conclusions of Part II 75 III Parameter Learning 77 Outline of Part III 79 6 Learning from Probabilistic Entailment 81 6.1 Parameter Learning in Probabilistic Databases . . . . . . . . . . . 82 6.2 Deriving The Gradient......................... 88 6.2.1 Gradient of Possible World Probability. . . . . . . . . . . . 88 6.2.2 Gradient of Success Probability................ 92 6.2.3 Gradient of Mean Squared Error ............... 94 6.3 Computingthe Gradient By Means of BDDs . . . . . . . . . . . . 95 6.4 Imbalanced Data Sets ......................... 97 6.5 Experiments............................... 98 6.5.1 Datasets............................. 99 6.5.2 Evaluation Metrics....................... 100 6.5.3 Methodology .......................... 100 6.5.4 Quality of Estimated Probabilities . . . . . . . . . . . . . . 101 6.5.5 Influence of Approximations.................. 103 6.5.6 Learning From Entailment And From Proofs . . . . . . . . 104 6.5.7 Comparison to State-Of-The-Art ............... 106 6.6 Related Work.............................. 112 6.7 Conclusions And Future Work..................... 114 7 Learning from Interpretations 115 7.1 Learning From Interpretations .................... 116 7.1.1 Full Observability ....................... 117 7.1.2 Partial Observability...................... 118 7.2 The LFI-ProbLog Algorithm ..................... 120 7.2.1 Computing the BDD For An Interpretation . . . . . . . . . 122 7.2.2 Calculating Expected Counts ................. 125 7.2.3 Automated Theory Splitting ................. 129 7.3 Experiments............................... 130 7.3.1 WebKB ............................. 130 7.3.2 Smokers............................. 132 7.4 Related Work.............................. 136 7.5 Conclusions And Future Work..................... 138 Conclusions of Part III 139 IV Round-Up 141 8 Summary and Future Work 143 A Correctness of Mapping Annotated Disjunctions 149 B Properties of The Sigmoid Function 151 C Translating Markov Logic Clauses Into ProbLog Clauses 153 D Correctness of Gradient Computation Algorithm 157 E Gradient Computation for Hybrid ProbLog 161 F Computing Expected Counts on Interpretation-Restricted Theory 167 G Kullback-Leibler Divergence Between ProbLog Programs 169 Bibliography 173 Publication List 185 Curriculum vitae 191nrpages: 191status: publishe