PROBABILISTIC LOGIC PROGRAMMING UNDER INHERITANCE

INFSYSRESEARCHREPORTInstitutf¨urInformationssystemeAbtg.WissensbasierteSystemeTechnischeUniversit¨atWienFavoritenstraße9-11A-1040Wien,AustriaTel:[phone]Fax:[e-mail]¨URINFORMATIONSSYSTEMEABTEILUNGWISSENSBASIERTESYSTEMEPROBABILISTICLOGICPROGRAMMINGUNDERINHERITANCEWITHOVERRIDINGThomasLukasiewiczINFSYSRESEARCHREPORT1843-01-05MAY2001INFSYSRESEARCHREPORTINFSYSRESEARCHREPORT1843-01-05,MAY2001PROBABILISTICLOGICPROGRAMMINGUNDERINHERITANCEWITHOVERRIDING(PRELIMINARYREPORT,MAY2001)ThomasLukasiewicz1Abstract.Wepresentprobabilisticlogicprogrammingunderinheritancewithoverriding.Thisapproachisbasedonnewnotionsofentailmentforreasoningwithconditionalcon-straints,whichareobtainedfromtheclassicalnotionoflogicalentailmentbyaddingin-heritancewithoverriding.Thisisdonebyusingrecentapproachestoprobabilisticdefaultreasoningwithconditionalconstraints.Weanalyzethesemanticpropertiesofthenewen-tailmentrelations.Wealsopresentalgorithmsforprobabilisticlogicprogrammingunderinheritancewithoverriding,andweanalyzeitscomplexityinthepropositionalcase.1InstitutundLudwigWittgensteinLaborf¨urInformationssysteme,TUWien,Favoritenstraße9-11,A-1040Vienna,Austria.E-mail:[e-mail]:IamverygratefultoGabrieleKern-Isbernerforvaluablecommentsonanearlierversionofthispaper.ThisworkhasbeensupportedbyaDFGgrantandtheAustrianScienceFundunderprojectNZ29-INF.Copyrightc2001bytheauthors2INFSYSRR1843-01-051IntroductionAnumberofrecentresearcheffortsaredirectedtowardsintegratinglogic-orientedandprobability-basedrepresentationandreasoningformalisms.Inparticular,thereareapproachestoprobabilisticlogicprogrammingthatcombinelogicprogrammingtechniqueswithprobabilitiesoverpossibleworlds[25,26,4,5,20].Theyarebasedonthemodel-theoreticnotionoflogicalentailment,whichiswell-knownfromprobabilisticpropositionallogics[28,7,6].Thenotionoflogicalentailment,however,hasoftenbeencriticizedintheliteratureforitsinferentialweakness.Forthisreason,manyrecentapproachestowardsintegratinglogicandprob-abilitiescombinelogic-basedformalismswithBayesiannetworks[33,32,13,27,15].Anotherwaytoovercometheinferentialweaknessoflogicalentailmentistousetheprinci-pleofmaximumentropy[24]ortheprincipleofsequentialmaximumentropy[21],wherethelatteriscloselyrelatedtoBayesiannetworks.Themaximumentropyapproach,however,hasthedrawbackthatitdoesnotproperlymodelimprecisioninourknowledgebase.Thatis,maximumentropyalwaysproducesasinglejointdistribution,forexample,alsointheextremecasewhenourknowledgebaseisempty.Inthispaper,weinvestigateaverypromisingnewapproachofstrengtheningthenotionoflogicalentailmentinprobabilisticlogic,whichdoesnothavetheabove-mentioneddrawbackofthemaximumentropyapproach.Thisapproachalsohasadvantagesovertheabovecombinationsoflogic-basedformalismswithBayesiannetworks,asitdoesnotassumeacyclicBayesiannetworkstructureswithcompleteandpreciseconditionalprobabilities.Thisnewapproachisinspiredbyreference-classreasoning,whichgoesbacktoReichenbach[34]andwasfurtherrefinedespeciallybyKyburg[17,18]andPollock[31].Reichenbach[34]describesreference-classreasoningasfollows:“Ifweareaskedtofindtheprobabilityholdingforanindividualfutureevent,wemustfirstincorporatethecaseinasuitablereferenceclass.Anindividualthingoreventmaybeincorporatedinmanyreferenceclasses.Wethenproceedbyconsideringthenarrowestreferenceclassforwhichsuitablestatisticscanbecompiled.”Thatis,Reichenbachsuggeststoequateourknowledgeaboutaparticularindividualwiththestatisticsfromareferenceclass,whichisinformallydefinedasasetofindividualstowhichourparticularindividualbelongsandaboutwhichwehave“suitablestatistics”.Moreover,ifthereareseveralreferenceclasseswithconflictingstatistics,thenweshouldpreferthesmallestoneanditsassociatedstatistics.Interestingly,Reichenbach’sguidelinesmaybeinterpretedasinheritancewithoverridingasitisknownfromobject-orientedprogramminglanguages.Theaspectofinheritanceisexpressedbythefactthatanyclasscontainingtheparticularindividualcanbeconsideredasreferenceclass,whiletheaspectofoverridingisexpressedbythefactthatsmallerreferenceclassesarepreferredtolargerones.Itturnsoutthattheclassicalnotionoflogicalentailmentinprobabilisticlogicdoesnotfollowtheprincipleofinheritancewithoverriding.Itisthusanaturalideatostrengthenlogicalentailmentbyaddinginheritancewithoverriding.Inthispaper,werealizethisideabyusingrecentapproachestoprobabilisticdefaultreasoningfrom[22,23].INFSYSRR1843-01-053Themaincontributionsofthispapercanbesummarizedasfollows:Wepresentprobabilisticlogicprogrammingunderinheritancewithoverriding,whichisbasedonrecentapproachestoprobabilisticdefaultreasoningfrom[22,23].Wedescribegeneralnonmontonicpropertiesofentailmentunderinheritancewithoverriding.Wepresentalgorithmsforprobabilisticlogicprogrammingunderinheritancewithoverriding.Weanalyzethecomputationalcomplexityofprobabilisticlogicprogrammingunderinheri-tancewithoverridinginthepropositionalcase.Notethatallproofsaregivenintheappendix.2PreliminariesInthissection,wedescribetheprobabilisticback