Probabilistic default reasoning with conditional c

ProbabilisticDefaultReasoningwithConditionalConstraintsThomasLukasiewicz([e-mail])InstitutundLudwigWittgensteinLaborf¨urInformationssysteme,TechnischeUniversit¨atWien,Favoritenstraße9-11,1040Wien,AustriaAbstract.Wepresentanapproachtoreasoningfromstatisticalandsubjectiveknowledge,whichisbasedonacombinationofprobabilisticreasoningfromconditionalconstraintswithapproachestodefaultreasoningfromconditionalknowledgebases.Moreprecisely,weintro-ducethenotionsof-,lexicographic,andconditionalentailmentforconditionalconstraints,whichareprobabilisticgeneralizationsofPearl’sentailmentinsystem,Lehmann’slexi-cographicentailment,andGeffner’sconditionalentailment,respectively.Weshowthatthenewformalismshaveniceproperties.Inparticular,theyshowasimilarbehaviorasreference-classreasoninginanumberofuncontroversialexamples.Thenewformalisms,however,alsoavoidmanydrawbacksofreference-classreasoning.Moreprecisely,theycanhandlecomplexscenariosandevenpurelyprobabilisticsubjectiveknowledgeasinput.Moreover,conclusionsaredrawninaglobalwayfromalltheavailableknowledgeasawhole.Wethenshowthatthenewformalismsalsohavenicegeneralnonmonotonicproperties.Indetail,thenewnotionsof-,lexicographic,andconditionalentailmenthavesimilarpropertiesastheirclassicalcounter-parts.Inparticular,theyallsatisfytherationalitypostulatesproposedbyKraus,Lehmann,andMagidor,andtheyhavesomegeneralirrelevanceanddirectinferenceproperties.Moreover,thenewnotionsof-andlexicographicentailmentsatisfythepropertyofrationalmono-tonicity.Furthermore,thenewnotionsof-,lexicographic,andconditionalentailmentarepropergeneralizationsofboththeirclassicalcounterpartsandtheclassicalnotionoflogicalentailmentforconditionalconstraints.Finally,weprovidealgorithmsforreasoningunderthenewformalisms,andweanalyzeitscomputationalcomplexity.Keywords:probabilisticdefaultreasoning,conditionalconstraint,systemZ,lexicographicentailment,conditionalentailment.AMSSubjectclassification:Primary68T30,68T37;Secondary68T271.IntroductionInthispaper,weelaborateanapproachtoreasoningwithstatisticalandsub-jectiveknowledge,whichisbasedonacombinationofprobabilisticreason-ingfromconditionalconstraintswithapproachestodefaultreasoningfromconditionalknowledgebases.Wefirstgiveaninformaldescriptionofthemainideasbehindourapproach.Assumethatwehavesomestatisticalknowledgeaboutasetofindividualsoftheform“everypenguinisabird”,“90–95%ofallbirdsfly”,and“atmost5%ofallpenguinsfly”.Moreover,assumethatourknowledgeaboutaparticularindividualcalledTweetyis“Tweetyisabird”inafirstscenarioc2001KluwerAcademicPublishers.PrintedintheNetherlands.lukasiewicz.tex;1/09/2001;20:56;p.12ThomasLukasiewiczand“Tweetyisapenguin”inasecondscenario.WhatdoweconcludeaboutTweety’sabilitytoflyinthesetwoscenarios?Thereisasignificantbodyofworkintheliteratureonreference-classreasoning,whichdealswithhandlingsuchproblemsofdrawingsubjectiveconclusionsfromstatisticalknowledgeaboutasetofindividualsandsomesubjectiveknowledgeaboutaparticularindividual.Reference-classreason-inggoesbacktoReichenbach[73]andwasfurtherrefinedespeciallybyKyburg[48,49,50,51]andPollock[72].SeealsotheworkbyLoui[58]andKyburgandMurtezao˘glu[52]foritsimplementations,andtheworkbyNg[66]foranimportantapplicationinempiricaldeductivedatabases.Themainideasbehindreference-classreasoningareasfollows.Thesub-jectiveknowledgeaboutaparticularindividualisequatedwiththestatis-ticsofareferenceclass,whichisinformallydefinedasasetofindividualsthatcontainstheparticularindividualandaboutwhichwehavesomestatis-tics.Ifthereareseveralreferenceclasseswithconflictingstatistics,thenthenarrowestoneanditsstatisticsarepreferred.Wenowillustratereference-classreasoningalongourintroductoryexam-ple.Inthefirstscenario,wehavethesetofallbirdsastheonlyreferenceclass.Thus,weconclude“Tweetyflieswithaprobabilitybetween0.9and0.95”.Inthesecondscenario,wehavethesetofallbirdsandthesetofallpenguinsastwodistinctreferenceclasseswithconflictingstatistics.Thenarrowestamongtheseclassesisthesetofallpenguins.Thus,weconclude“Tweetyflieswithaprobabilityofatmost0.05”.Reference-classreasoning,however,isnotuncontroversialintheliterature(seeespeciallytheworkbyLevi[57]andBacchusetal.[5,6]).Inparticular,itisoftenarguedthateventhoughreference-classreasoningdealsverywellwithsimplescenarios,itmayproduceunintuitiveconclusionsinmorecom-plexexamples.Moreover,anevenstrongercriticismformulatedbyBacchusetal.[5,6]isthattheprocedureofidentifyingreferenceclassesandselectingthepreferredonesseemsconceptuallyflawedasawhole,asitpresupposesthatalltherelevantknowledgeislocallyconcentratedinasinglepieceofinformation,thestatisticsofasinglereferenceclass,whichisrarelythecase.Inthispaper,wecriticizeanotherlimitationofreference-classreasoning,namelythatitjustallowsforclassicalsubjectiveknowledgeaboutasinglein-dividualasinput,andnotalsoforpurelyprobabilisticsubjectiveknowledge.Forinstance,whatdoweconcludeinthesecondscenarioofourexampleifourknowledgeis“Tweetyisapenguinwithaprobabilityofatleast0.9”,ratherthan“Tweetyisapenguin”?Howcanweresolvetheseproblemsandlimitationswhilekeepin