Probabilistic default reasoning with strict and de

INFSYSRESEARCHREPORTInstitutf¨urInformationssystemeAbtg.WissensbasierteSystemeTechnischeUniversit¨atWienFavoritenstraße9-11A-1040Wien,AustriaTel:[phone]Fax:[e-mail]¨URINFORMATIONSSYSTEMEABTEILUNGWISSENSBASIERTESYSTEMEPROBABILISTICDEFAULTREASONINGWITHSTRICTANDDEFEASIBLECONDITIONALCONSTRAINTSThomasLukasiewiczINFSYSRESEARCHREPORT1843-00-02FEBRUARY&DECEMBER2000INFSYSRESEARCHREPORTINFSYSRESEARCHREPORT1843-00-02,FEBRUARY&DECEMBER2000PROBABILISTICDEFAULTREASONINGWITHSTRICTANDDEFEASIBLECONDITIONALCONSTRAINTSREVISEDVERSION,DECEMBER2000ThomasLukasiewicz1Abstract.Wepresentanapproachtoreasoningfromstatisticalandsubjectiveknowledge,whichisbasedonacombinationofprobabilisticreasoningfromconditionalconstraintswithapproachestodefaultreasoningfromconditionalknowledgebases.Moreprecisely,weintroducethenotionsofz-,lexicographic,andconditionalentailmentforconditionalconstraints,whichareprobabilisticgen-eralizationsofPearl’sentailmentinsystemZ,Lehmann’slexicographicentailment,andGeffner’sconditionalentailment,respectively.Weshowthatthenewformalismshaveniceproperties.Inparticular,theyshowasimilarbehaviorasreference-classreasoninginanumberofuncontroversialexamples.Thenewformalisms,however,alsoavoidmanydrawbacksofreference-classreasoning.Moreprecisely,theycanhandlecomplexscenariosandevenpurelyprobabilisticsubjectiveknowl-edgeasinput.Moreover,conclusionsaredrawninaglobalwayfromalltheavailableknowledgeasawhole.Wethenshowthatthenewformalismsalsohavenicegeneralnonmonotonicproperties.Indetail,thenewnotionsofz-,lexicographic,andconditionalentailmenthavesimilarpropertiesastheirclassicalcounterparts.Inparticular,theyallsatisfytherationalitypostulatesproposedbyKraus,Lehmann,andMagidor,andtheyhavesomegeneralirrelevanceanddirectinferenceproper-ties.Moreover,thenewnotionsofz-andlexicographicentailmentsatisfythepropertyofrationalmonotonicity.Furthermore,thenewnotionsofz-,lexicographic,andconditionalentailmentarepropergeneralizationsofboththeirclassicalcounterpartsandtheclassicalnotionoflogicalen-tailmentforconditionalconstraints.Finally,weprovidealgorithmsforreasoningunderthenewformalisms,andweanalyzeitscomputationalcomplexity.1InstitutundLudwigWittgensteinLaborf¨urInformationssysteme,TechnischeUniversit¨atWien,Favoritenstraße9-11,A-1040Vienna,Austria.E-mail:[e-mail]:IamverygratefultoSalemBenferhat,AngeloGilio,andJ¨urgKohlasfortheirusefulcommentsonanearlierversionofthispaper.ManythanksalsotoJohnPollockforhelpfulcommentsandforpointingoutrelevantliterature.ThisworkwassupportedbytheAustrianScienceFundunderprojectNZ29-INFandbyaDFGgrant.ThispaperisasubstantiallyextendedandrevisedversionofapaperthatappearedinProceedingsofthe8thInternationalWorkshoponNon-MonotonicReasoning,SpecialSessiononUncertaintyFrameworksinNMR,Breckenridge,CO,USA,April9–11,2000.Copyrightc2000bytheauthors2INFSYSRR1843-00-021IntroductionInthispaper,weelaborateanapproachtoreasoningwithstatisticalandsubjectiveknowledge,whichisbasedonacombinationofprobabilisticreasoningfromconditionalconstraintswithapproachestodefaultreasoningfromconditionalknowledgebases.Wefirstgiveaninformaldescriptionofthemainideasbehindourapproach.Assumethatwehavesomestatisticalknowledgeaboutasetofindividualsoftheform“everypenguinisabird”,“90–95%ofallbirdsfly”,and“atmost5%ofallpenguinsfly”.Moreover,assumethatourknowledgeaboutaparticularindividualcalledTweetyis“Tweetyisabird”inafirstscenarioand“Tweetyisapenguin”inasecondscenario.WhatdoweconcludeaboutTweety’sabilitytoflyinthesetwoscenarios?Thereisasignificantbodyofworkintheliteratureonreference-classreasoning,whichdealswithhan-dlingsuchproblemsofdrawingsubjectiveconclusionsfromstatisticalknowledgeaboutasetofindividualsandsomesubjectiveknowledgeaboutaparticularindividual.Reference-classreasoninggoesbacktoRe-ichenbach[68]andwasfurtherrefinedespeciallybyKyburg[43,44,45,46]andPollock[67].SeealsotheworkbyLoui[53]andKyburgandMurtezao˘glu[47]foritsimplementations,andtheworkbyNg[61]foranimportantapplicationinempiricaldeductivedatabases.Themainideasbehindreference-classreasoningareasfollows.Thesubjectiveknowledgeaboutaparticularindividualisequatedwiththestatisticsofareferenceclass,whichisinformallydefinedasasetofindividualsthatcontainstheparticularindividualandaboutwhichwehavesomestatistics.Ifthereareseveralreferenceclasseswithconflictingstatistics,thenthenarrowestoneanditsstatisticsarepreferred.Wenowillustratereference-classreasoningalongourintroductoryexample.Inthefirstscenario,wehavethesetofallbirdsastheonlyreferenceclass.Thus,weconclude“Tweetyflieswithaprobabilitybetween0.9and0.95”.Inthesecondscenario,wehavethesetofallbirdsandthesetofallpenguinsastwodistinctreferenceclasseswithconflictingstatistics.Thenarrowestamongtheseclassesisthesetofallpenguins.Thus,weconclude“Tweetyflieswithaprobabilityofatmost0.05”.Reference-classreasoning,however,isnotuncontroversialintheliterature(seeespeciallytheworkbyLevi[52]andBacchusetal.[3,4]).Inparticular,itisoftenarguedthateventhoughreference-classreas