Statistical Relational Artificial Intelligence Logic,Probability,andComputation Luc De Raedt KULeuven,Belgium Kristian Kersting TechnicalUniversityofDortmund,Germany Sriraam Natarajan IndianaUniversity David Poole UniversityofBritishColumbia SYNTHESISLECTURESONARTIFICIALINTELLIGENCE ANDMACHINE LEARNING#32 M &C Morgan &cLaypool publishers Copyright©2016byMorgan&Claypool StatisticalRelationalArtificialIntelligence:Logic,Probability,andComputation LucDeRaedt,KristianKersting,SriraamNatarajan,andDavidPoole www.morganclaypool.com ISBN:9781627058414 paperback ISBN:9781627058421 ebook DOI10.2200/S00692ED1V01Y201601AIM032 APublicationintheMorgan&ClaypoolPublishersseries SYNTHESISLECTURESONARTIFICIALINTELLIGENCEANDMACHINELEARNING Lecture#32 SeriesEditors:RonaldJ.Brachman,Yahoo!Labs WilliamW.Cohen,CarnegieMellonUniversity PeterStone,UniversityofTexasatAustin SeriesISSN Print1939-4608 Electronic1939-4616 ABSTRACT An intelligent agent interacting with the real world will encounter individual people, courses, testresults,drugsprescriptions,chairs,boxes,etc.,andneedstoreasonaboutpropertiesofthese individualsandrelationsamongthemaswellascopewithuncertainty. Uncertaintyhasbeenstudiedinprobabilitytheoryandgraphicalmodels,andrelationshave beenstudiedinlogic,inparticularinthepredicatecalculusanditsextensions.isbookexamines the foundations of combining logic and probability into what are called relational probabilistic models. It introduces representations, inference, and learning techniques for probability, logic, andtheircombinations. e book focuses on two representations in detail: Markov logic networks, a relational extensionofundirectedgraphicalmodelsandweightedfirst-orderpredicatecalculusformula,and Problog,aprobabilisticextensionoflogicprogramsthatcanalsobeviewedasaTuring-complete relationalextensionofBayesiannetworks. KEYWORDS probabilisticlogicmodels,relationalprobabilisticmodels,liftedinference,statistical relational learning, probabilistic programming, inductive logic programming, logic programming,machinelearning,Prolog,Problog,Markovlogicnetworks Contents Preface ...........................................................xiii 1 Motivation......................................................... 1 1.1 UncertaintyinComplexWorlds ......................................1 1.2 ChallengesofUnderstandingStarAI ..................................3 1.3 eBenefitsofMasteringStarAI .....................................5 1.4 ApplicationsofStarAI ..............................................5 1.5 BriefHistoricalOverview ..........................................12 PARTI Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2 StatisticalandRelationalAIRepresentations ........................... 17 2.1 ProbabilisticGraphicalModels ......................................17 2.1.1 BayesianNetworks ..........................................18 2.1.2 MarkovNetworksandFactorGraphs ...........................20 2.2 First-OrderLogicandLogicProgramming ............................22 3 RelationalProbabilisticRepresentations ............................... 27 3.1 AGeneralView:ParameterizedProbabilisticModels ....................28 3.2 TwoExampleRepresentations:MarkovLogicAndProbLog ..............34 3.2.1 UndirectedRelationalModel:MarkovLogic .....................35 3.2.2 DirectedRelationalModels:ProbLog ...........................37 4 RepresentationalIssues ............................................. 45 4.1 KnowledgeRepresentationFormalisms................................45 4.2 ObjectivesforRepresentationLanguage ...............................46 4.3 Directedvs.Undirectedmodels......................................48 4.4 First-OrderLogicvs.LogicPrograms.................................50 4.5 FactorsandFormulae..............................................51 4.6 ParameterizingAtoms .............................................52 4.7 AggregatorsandCombiningRules ...................................54 4.8 OpenUniverseModels.............................................58 4.8.1 IdentityUncertainty .........................................58 4.8.2 ExistenceUncertainty ........................................60 4.8.3 Ontologies.................................................62 PARTII Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5 InferenceinPropositionalModels .................................... 65 5.1 ProbabilisticInference .............................................65 5.1.1 VariableElimination .........................................66 5.1.2 RecursiveConditioning ......................................66 5.1.3 BeliefPropagation...........................................68 5.2 LogicalInference .................................................69 5.2.1 PropositionalLogic,Satisfiability,andWeightedModelCounting ....69 5.2.2 SemiringInference ..........................................70 5.2.3 eLeastHerbrandModel ...................................72 5.2.4 Grounding.................................................74 5.2.5 Proving ...................................................75 6 InferenceinRelationalProbabilisticModels ............................ 77 6.1 GroundedInferenceforRelationalProbabilisticModels ..................77 6.1.1 WeightedModelCounting....................................77 6.1.2 WMCforMarkovLogic .....................................77 6.1.3 WMCforProbLog..........................................78 6.1.4 KnowledgeCompilation......................................79 6.2 LiftedInference:ExploitingSymmetries ..............................80 6.2.1 ExactLiftedInference .......................................83 6.3 (Lifted)ApproximateInference......................................87 PARTIII Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 7 LearningProbabilisticandLogicalModels ............................. 93 7.1 LearningProbabilisticModels.......................................93 7.1.1 FullyObservedDataandKnownStructure .......................94 7.1.2 PartiallyObservedDatawithKnownStructure....................95 7.1.3 UnknownStructureandParameters.............................95 7.2 LogicalandRelationalLearning .....................................96 7.2.1 TwoLearningSettings .......................................97 7.2.2 eSearchSpace............................................98 7.2.3 TwoAlgorithms:ClausalDiscoveryandFOIL ....................99 7.2.4 FromPropositionaltoFirst-OrderLogic........................101 7.2.5 AnILPExample...........................................102 8 LearningProbabilisticRelationalModels ............................. 105 8.1 LearningasInference.............................................105 8.2 eLearningProblem ............................................106 8.2.1 eDataUsed.............................................106 8.3 ParameterLearningofRelationalModels.............................108 8.3.1 FullyObservableData ......................................108 8.3.2 PartiallyObservedData .....................................109 8.3.3 LearningwithLatentVariables ...............................111 8.4 StructureLearningofProbabilisticRelationalModels...................112 8.4.1 AVanillaStructureLearningApproach.........................113 8.4.2 ProbabilisticRelationalModels ...............................114 8.4.3 Boosting .................................................117 8.5 BayesianLearning ...............................................119 PARTIV BeyondProbabilities . . . . . . . . . . . . . . . . . . . . . 121 9 BeyondBasicProbabilisticInferenceandLearning...................... 123 9.1 LiftedSatisfiability...............................................123 9.2 ActinginNoisyRelationalWorlds ..................................124 9.3 RelationalOptimization...........................................129 10 Conclusions...................................................... 135 Preface is book aims to provide an introduction that can help newcomers to the field to get started, to understand the state-of-the-art and the current challenges and be ready for future advances. It reviews the foundations of StarAI, motivates the issues, justifies somechoices that have been made,andprovidessomeopenproblems.Layingbarethefoundationswillhopefullyinspireothers tojoinusinexploringthefrontiersandtheyetunexploredareas. etargetaudienceforthisbookconsistsofadvancedundergraduateandgraduatestudents andalsoresearchersandpractitionerswhowanttogetanoverviewofthebasicsandthestate-of- the-artinStarAI.Tothisaim,PartIstartswithprovidingthenecessarybackgroundinprobability andlogic.Wethendiscusstherepresentationsofrelationalprobabilitymodelsandtheunderlying issues.Afterward,wefocusfirstoninference,inPartII,andthenonlearning,inPartIII.Finally, wetouchuponrelationaltasksthatgobeyondthebasicprobabilisticinferenceandlearningtasks aswellassomeopenissues. ResearcherswhoarealreadyworkingonStarAI—weapologizetoanyonewhoseworkwe areaccidentallynotciting—mayenjoyreadingaboutpartsofStarAItheyarelessfamiliarwith. Wearegratefultoallthepeoplewhocontributedtothedevelopmentofstatisticalrelational learningandstatisticalrelationalAI.isbookismadepossiblebyyou. Wealsothankthereviewersfortheirvaluablefeedbackandourco-authors,whoaccompa- nied us on our StarAI adventures, such as Laura Antanas, Udi Apsel, Babak Ahmadi, Hendrik Blockeel, Wolfram Burgard, Maurice Bruynooghe, David Buchman, Hung H. Bui, Peter Car- bonetto, Alexandru Cocora, Fabrizio Costa, Michael Chiang, Walter Daelemans, Jesse Davis, Nando de Freitas, Kurt De Grave, Tinne De Laet, Bart Demoen, Kurt Driessens, Saso Dze- roski,omasG.Dietterich,AdamEdwards,AlanFern,DaanFierens,PaoloFrasconi,Roman Garnett,AmirGloberson,BerndGutmann,MartinGrohe,FabianHadiji,McEloryHoffmann, ManfredJaeger,GerdaJanssens,orstenJoachims,SaketJoshi,LeslieKaelbling,AndreasKar- wath,ArzooKatiyar,SeyedM.Kazemi,AngelikaKimmig,JacekKisynski,TusharKhot,Stefan Kramer,GautamKunapuli,Chia-LiKuo,TobiasLang,NielsLandwehr,DanielLowd,Cather- ineA.McCarty,eofrastosMantadelis,WannesMeert,BrianMilch,MartinMladenov,Bog- danMoldovan,RoserMorante,PlinioMoreno,MarionNeumann,DavideNitti,PhillipOdom, JoseOramas,DavidPage,AndreaPasserini,RuiPimenteldeFigueiredo,ChristianPlagemann, TapaniRaiko,ChristopherRe,KateRevoredo,AchimRettinger,RicardoRocha,ScottSanner, Vitor Santos Costa, Jose Santos-Victor, Erkal Selman, Rita Sharma, Jude W. Shavlik, Prasad Tadepalli,NimaTaghipour,Ingoon,HannuToivonen,PavelTokmakov,SunnaTorge,Marc Toussaint, Volker Tresp, Tinne Tuytelaars, Vincent Van Asch, Guy Van den Broeck, Martijn van Otterlo, Joost Vennekens, Jonas Vlasselaer, Zhao Xu, Shuo Yang, and Luke Zettlemoyer. anksforalltheencouragementandfun!ankstotheStaRAIlabatIndianaforproofreading thebook. Last but not least, we also thank our families and friends for their patience and support. anks! LDR and KK thank the European Commission for support of the project FP7-248258- First-MM. KK further thanks Fraunhofer Society, ATTRACT Fellowship ”STREAM”, the GermanScienceFoundation,DFGKE1686/2-1,aspartoftheDFGPriorityProgramme1527, andtheGerman-IsraeliFoundationforScientificResearchandDevelopment,GIF1180/2011. SNthanksArmyResearchOffice(ARO)grantnumberW911NF-13-1-0432undertheYoung InvestigatorProgramandtheNationalScienceFoundationgrantno.IIS-1343940.LDRthanks theResearchFoundationFlanders,andtheKULeuvenBOFfundfortheirsupport.DPthanks theNaturalSciencesandEngineeringResearchCouncilofCanada(NSERC)forongoingsup- port. LucDeRaedt,Leuven,Belgium KristianKersting,Dortmund,Germany SriraamNatarajan,Bloomington,USA DavidPoole,Vancouver,Canada February2016 C H A P T E R 1 Motivation ere are good arguments that an intelligent agent that makes decisions about how to act in a complexworldneedstomodelitsuncertainty;itcannotjustactpretendingthatitknowswhatis true.Anagentalsoneedstoreasonaboutindividuals(objects,entities,things)andaboutrelations amongtheindividuals. eseaspectshaveoftenbeenstudiedseparately,withmodelsforuncertaintyoftendefined in terms of features and random variables, ignoring relational structure, and with rich (logical) languagesforreasoningaboutrelationsthatignoreuncertainty.isbookstudiestheintegration oftheapproachestoreasoningaboutuncertaintyandreasoningaboutindividualsandrelations. 1.1 UNCERTAINTYINCOMPLEXWORLDS Overthelast30years,ArtificialIntelligence(AI)hasevolvedfrombeingskeptical,evenhostile, totheuseofprobabilitytoembracingprobability.Initially,manyresearcherswereskepticalabout statisticalAIbecauseprobabilityseemedtorelyontoomanynumbersanddidnotdealwiththe complexitiesof a world of individuals and things. But the use of probabilisticgraphical models, exploiting probabilistic independencies, has revolutionized AI. e independencies specified in suchmodelsarenatural,providestructurethatenablesefficientreasoningandlearning,andallow one to model complex domains. Many AI problems arising in a wide variety of fields such as machine learning, diagnosis, network communication, computer vision, and robotics have been elegantlyencodedandsolvedusingprobabilisticgraphicalmodels. Meanwhile,therehavealsobeenconsiderableadvancesinlogicalAI,whereagentsreason aboutthe structureof complexworlds. Oneaspect of this is in the semanticweband the use of ontologies to represent meaning in diverse fields from medicine to geology to the products in a catalogue. Generally, there is an explosive growth in the amount of heterogeneous data that is being collected in the business and scientific world. Example domains include biology and chemistry,transportationsystems,communicationnetworks,socialnetworks,androbotics.Like people,intelligentagentsshouldbeabletodealwithmanydifferenttypesofknowledge,requiring structuredrepresentationsthatgiveamoreinformativeviewoftheAItaskathand. Moreover,reasoningaboutindividualsandrelationsisallaboutreasoningwithregularities and symmetries. We lump individuals into categories or classes (such as “person” or “course”) because the individuals in a category share common properties—e.g., there are statements that are true about all living people such as they breath, they have skin and two biological parents. Similarly for relations, there is something in common between Sam being advised by Professor 2 1. MOTIVATION Optimization Cognitive … Science Uncertain Scaling Reasoning SAT IR Logic Mining Graphs and Trees Learning KR CV Search DM/ML Figure 1.1: Statistical Relational Artificial Intelligence (StarAI) combines probability, logic, and learningandcoversmajorpartsoftheAIspectrum. SmithandChrisbeingadvisedbyProfessorJohnson;therearestatementsaboutpublishingpa- pers, working on a thesis and projects that are common among the “advised by” relationships. Wewouldliketomakepredictionsabouttwopeopleaboutwhomallweknowmaybeonlytheir advisoryrelationships.Itisthesecommonalitiesandregularitiesthatenablelanguagetodescribe the world. Reasoning about regularities and symmetries is the foundation of logics built on the predicatecalculus,whichallowsstatementsaboutallindividuals. us, to deal with the real world we actually need to exploit uncertainty, independen- cies, and symmetries and tackle a long standing goal of AI, namely unifying first-order logic— capturing regularities and symmetries—and probability—capturing uncertainty and indepen- dence.Predicatelogicandprobabilitytheoryarenotinconflictwitheachother,theyaresynergis- tic.Bothextendpropositionallogic,onebyaddingrelations,individuals,andquantifiedvariables, theotherbyallowingformeasuresoverpossibleworldsandconditionalqueries.ismayexplain why there has been a considerable body of research in combining both of them over the last 25years,evolvingintowhathascometobecalledStatisticalRelationalArtificialIntelligence (StarAI);seealsoFig.1.1: thestudyanddesignofintelligentagentsthatactinworldscomposedofindividuals(objects, things),wheretherecanbecomplexrelationsamongtheindividuals,wheretheagentscan beuncertainaboutwhatpropertiesindividualshave,whatrelationsaretrue,whatindi- vidualsexist,whetherdifferenttermsdenotethesameindividual,andthedynamicsofthe world. e basic building block of StarAI are relational probabilistic models—we use this term in the broad sense, meaning any models that combine relations and probabilities. ey can be seen