PROBABILISTIC LOGIC PROGRAMMING WITH CONDITIONAL C

INFSYSRESEARCHREPORTInstitutf¨urInformationssystemeAbtg.WissensbasierteSystemeTechnischeUniversit¨atWienFavoritenstraße9-11A-1040Wien,AustriaTel:[phone]Fax:[e-mail]¨URINFORMATIONSSYSTEMEABTEILUNGWISSENSBASIERTESYSTEMEPROBABILISTICLOGICPROGRAMMINGWITHCONDITIONALCONSTRAINTSThomasLukasiewiczINFSYSRESEARCHREPORT1843-00-01FEBRUARY&MAY2000INFSYSRESEARCHREPORTINFSYSRESEARCHREPORT1843-00-01,FEBRUARY&MAY2000PROBABILISTICLOGICPROGRAMMINGWITHCONDITIONALCONSTRAINTSREVISEDVERSION,MAY2000ThomasLukasiewicz1Abstract.Weintroduceanewapproachtoprobabilisticlogicprogramminginwhichprobabilitiesaredefinedoverasetofpossibleworlds.Moreprecisely,classicalprogramclausesareextendedbyasubintervalof[0;1℄thatdescribesarangefortheconditionalprobabilityoftheheadofaclausegivenitsbody.Wethenanalyzethecomplexityofselectedprobabilisticlogicprogrammingtasks.Itturnsoutthatprobabilisticlogicprogrammingiscomputationallymorecomplexthanclassicallogicprogramming.Moreprecisely,thetractabilityofspecialcasesofclassicallogicprogramminggenerallydoesnotcarryovertothecorrespondingspecialcasesofprobabilisticlogicprogramming.Moreover,wealsodrawaprecisepictureofthecomplexityofdecidingandcomputingtightlogicalconsequencesinprobabilisticreasoningwithconditionalconstraintsingeneral.Wethenpresentlinearoptimizationtechniquesfordecidingsatisfiabilityandcomputingtightlogicalconsequencesofprobabilisticlogicprograms.Thesetechniquesareefficientinthespecialcaseinwhichwehavefewrelevantpurelyprobabilisticknowledge.WefinallyshowthatprobabilisticlogicprogrammingundercertainsyntacticandsemanticrestrictionsiscloselyrelatedtovanEmden’squantitativede-duction,andthushascomputationalpropertiessimilartoclassicallogicprogramming.Basedonthisresult,wepresentanefficientapproximationtechniqueforprobabilisticlogicprogramming.1InstitutundLudwigWittgensteinLaborf¨urInformationssysteme,TechnischeUniversit¨atWien,Favoritenstraße9-11,A-1040Vienna,Austria.E-mail:[e-mail]:IamverygratefultoThomasEiter,GeorgGottlob,NicolaLeone,andCristinelMateisforusefuldiscussions.ManythanksalsotoGabrieleKern-Isbernerforusefulcommentsonanearlierversionofthispaper.ThisworkwassupportedbyaDFGgrantandtheAustrianScienceFundProjectNZ29-INF.ThispaperisasubstantiallyextendedandrevisedversionofapaperthatappearedinProceedingsofthe13thEuropeanConferenceonArtificialIntelligence(ECAI-98),pages388-392,1998[42].Copyrightc2000bytheauthors2INFSYSRR1843-00-011IntroductionDuringtherecentdecades,themanagementofuncertaintyhascometoplayanimportantroleinknowl-edgerepresentationandreasoning.Manydifferentformalismsandmethodologieshavebeenproposedforhandlinguncertainknowledge.Mostofthemaredirectlyorindirectlybasedonprobabilitytheory.Probabilisticpropositionallogicsandtheirvariousdialectshavebeenthoroughlystudiedintheliterature(cf.especiallytheworkbyNilsson[56],FrischandHaddawy[20],andFaginetal.[18]).Theirextensionstoprobabilisticfirst-orderlogicscanbeclassifiedintofirst-orderlogicsinwhichprobabilitiesaredefinedoverthedomainandthoseinwhichprobabilitiesaregivenoverasetofpossibleworlds(cf.especiallytheworkbyHalpern[29]andBacchusetal.[4]).Thefirstonesaresuitablefordescribingstatisticalknowledge,whilethelatterareappropriateforrepresentingsubjectiveknowledge(alsocalleddegreesofbelief).Oneimportantelementofmanyformallanguagesforrepresentingprobabilisticknowledgeareintervalrestrictionsforconditionalprobabilities,alsocalledconditionalconstraints[47].Inparticular,theliteraturecontainsextensiveworkonprobabilisticreasoningaboutpropositionalconditionalconstraints(cf.especiallytheworkbyDuboisandPrade’sgroup[17,1,16],FrischandHaddawy[20],andtheauthor[43,47]).Asanimportantformalismforreasoningwithclassicalknowledge,logicprogramming[39,3]startedintheearly1970’s[36]basedonearlierworkinautomatedtheoremproving,andbegantoflourishespeciallywiththespreadingofPROLOG.Logicprogrammingisnowawell-establishedknowledgerepresentationandreasoningformalisminartificialintelligenceanddeductivedatabases.Manyapplicationsinpracticemakeitindispensableforaknowledge-representationandreasoningsystemtodealwithuncertainknowledge.Theneedforrepresentinguncertaintyinthelogicprogrammingframe-workisalreadyreportedbyagreatnumberofpublicationsonmany-valuedlogicprogramming[67,5,19,7],logicprogrammingwithsignedformulas[40,27],generalizedannotatedlogicprogramming[35,38],andprobabilisticlogicprogramming(seereferencesbelow).Inthispaper,weelaborateanapproachtoprobabilisticlogicprogrammingwithconditionalconstraints,whichcanbeunderstoodbothasaprobabilisticgeneralizationofclassicallogicprogrammingandasafirst-ordergeneralizationofprobabilisticreasoningwithpropositionalconditionalconstraints.Moreprecisely,weextendclassicalprogramclausesbyasubintervalof[0;1℄thatdescribesarangefortheconditionalprob-abilityoftheheadofaclausegivenitsbody.Moreover,ourprobabilisticlogicprogramshaveasubjectivesemanticsinwhichprobabilitiesaredefinedoverasetofpossibleworlds.Inthispaper,wefocusespeciallyonthecomputationalaspectsofprobabil