Parameter estimation in stochastic logic programs

Stochastic logic programs (SLPs) are logic programs with parameterised clau ses which define a log-linear distribution over refutations of goals. The l og-linear distribution provides, by marginalisation, a distribution over va riable bindings, allowing SLPs to compactly represent quite complex distrib utions. We analyse the fundamental statistical properties of SLPs addressing issues concerning infinite derivations, 'unnormalised' SLPs and impure SLPs. Afte r detailing existing approaches to parameter estimation for log-linear mode ls and their application to SLPs, we present a new algorithm called failure -adjusted maximisation (FAM). FAM is an instance of the EM algorithm that a pplies specifically to normalised SLPs and provides a closed-form for compu ting parameter updates within an iterative maximisation approach. We empiri cally show that FAM works on some small examples and discuss methods for ap plying it to bigger problems.