Computational Methods for A Mathematical theory of

8ComputationalMethodsforAMathematicalTheoryofEvidence∗†JeffreyA.BarnettAbstract.Manyknowledge-basedexpertsystemsemploynumericalschemestorepresentevidence,ratecompetinghypotheses,andguidesearchthroughthedomain’sproblemspace.Thispaperhastwoobjectives:first,tointroduceonesuchscheme,developedbyArthurDempsterandGlenShafer,toawideraudience;sec-ond,topresentresultsthatcanreducethecomputation-timecomplexityfromexpo-nentialtolinear,allowingthisschemetobeimplementedinmanymoresystems.Inordertoenjoythisreduction,someassumptionsaboutthestructureofthetypeofevidencerepresentedandcombinedmustbemade.Theassumptionmadehereisthateachpieceoftheevidenceeitherconfirmsordeniesasinglepropositionratherthanadisjunction.Foranydomaininwhichtheassumptionisjustified,thesavingsareavailable.1IntroductionHowshouldknowledge-basedexpertsystemsreason?Clearly,whendomain-specificidiosyncraticknowledgeisavailable,itshouldbeformalizedandusedtoguidetheinferenceprocess.Problemsoccureitherwhenthesupplyofeasy-to-formalizeknowledgeisexhaustedbeforeoursystemspassthe“sufficiency”testorwhenthecomplexityofrepresentingandapplyingtheknowledgeisbeyondthestateofoursystembuildingtechnology.Unfortunately,withthecurrentstateofexpert-systemtechnology,thisisthenormal,nottheexcep-tionalcase.Atthispoint,afallbackpositionmustbeselected,andifourluckholds,theresultingsystemexhibitsbehaviorinterestingenoughtoqualifyasasuccess.∗FromProceedingsoftheSeventhInternationalConferenceonArtificialIntelli-gence,1981,868–875.†ThisresearchissupportedbytheDefenseAdvancedResearchProjectsAgencyunderContractNo.DAHC1572C0308.Viewsandconclusionscontainedinthisreportaretheauthor’sandshouldnotbeinterpretedasrepresentingtheofficialopinionorpolicyofDARPA,theUSGovernment,oranypersonoragencyconnectedwiththem.198J.A.BarnettTypically,afallbackpositiontakestheformofauniformityassumptionallow-ingtheutilizationofanon-domain-specificreasoningmechanism:forexample,thenumericalevaluationproceduresemployedinmycin[17]andinternist[14],thesimplifiedstatisticalapproachdescribedin[10],andamultivaluedlogicin[18].Thehearsay-iispeechunderstandingsystem[13]providesanotherexampleofanumericalevaluationandcontrolmechanism—however,itishighlydomain-specific.Section2describesanotherschemeofplausibleinference,onethataddressesboththeproblemofrepresentingnumericalweightsofevidenceandtheproblemofcombiningevidence.TheschemewasdevelopedbyArthurDempster[3,4,5,6,7,8,9],thenformulatedbyhisstudent,GlenShafer[15,16],inaformthatismoreamenabletoreasoninginfinitediscretedomainssuchasthoseencounteredbyknowledge-basedsystems.ThetheoryreducestostandardBayesianreasoningwhenourknowledgeisaccuratebutismoreflexibleinrepresentinganddealingwithignoranceanduncertainty.Section2isareviewandintroduction.Otherworkinthisareaisdescribedin[12].Section3notesthatdirecttranslationofthistheoryintoanimplemen-tationisnotfeasiblebecausethetimecomplexityisexponential.However,ifthetypeofevidencegatheredhasausefulstructure,thenthetimecomplexityissuedisappears.Section4proposesaparticularstructurethatyieldslineartimecomplexity.Inthisstructure,theproblemspaceispartitionedinseveralindependentwaysandtheevidenceisgatheredwithinthepartitions.Themethodologyalsoappliestoanydomaininwhichtheindividualexperiments(separatecomponentsoftheevidence)supporteitherasinglepropositionoritsnegation.Section5and6developthenecessarymachinerytorealizelineartimecomputations.Itisalsoshownthattheresultsofexperimentsmayvaryovertime,thereforetheevidenceneednotbemonotonic.Section7summarizestheresultsandnotesdirectionsforfutureworkinthisarea.2TheDempster-shaferTheoryAtheoryofevidenceandplausiblereasoningisdescribedinthissection.Itisatheoryofevidencebecauseitdealswithweightsofevidenceandnumericaldegreesofsupportbaseduponevidence.Further,itcontainsaviewpointontherepresentationofuncertaintyandignorance.Itisalsoatheoryofplausiblereasoningbecauseitfocusesonthefundamentaloperationofplausiblerea-soning,namelythecombinationofevidence.Thepresentationandnotationusedherecloselyparallelsthatfoundin[16].Aftertheformaldescriptionofhowthetheoryrepresentsevidenceispre-sentedinSect.2.1,anintuitiveinterpretationisgiveninSect.2.2,thenacomparisonismade,inSect.2.3,tothestandardBayesianmodelandsim-ilaritiesanddifferencesnoted.Theruleforcombiningevidence,Dempster’sorthogonalsum,isintroducedinSect.2.4andcomparedtotheBayesians’8ComputationalMethodsforAMathematicalTheoryofEvidence199methodofconditioninginSect.2.5.Finally,Sect.2.6definesthesimpleandseparablesupportfunctions.Thesefunctionsarethetheory’snaturalrepre-sentationofactualevidence.2.1FormulationoftheRepresentationofEvidenceLetΘbeasetofpropositionsabouttheexclusiveandexhaustivepossibilitiesinadomain.Forexample,ifwearerollingadie,Θcontainsthesixproposi-tionsoftheform‘thenumbershowingisi’where1≤i≤6.Θiscalledtheframeofdiscernmentand2ΘisthesetofallsubsetsofΘ.Elementsof2Θ,i.e.,subsetsofΘ,aretheclassofgeneralpropositionsinthedomain;forexample,theproposition‘thenumbershowingiseven’correspondstothesetofthethreeelementsofΘthatassertthedieshowseithera2,4,or6.Thetheorydealswithrefinings,c