1 Maximal Consistency, Theory of Evidence and Baye

1MaximalConsistency,TheoryofEvidenceandBayesianConditioningintheInvestigativeDomainAldoFrancoDragoniIstitutodiInformaticaUniversityofAncona,viaBrecceBianche,I-60131Ancona,Italy1IntroductionDuringtheupstreamphaseofaninquiry,muchofthedetectives’andmagistrates’everydaytaskconsistsin1.acquiringinformationfrominvestigationsonthespotandwitnesses’depositions2.introducinghypotheticalrulestolinkthevarioushypothesesintoevidentialnetworks3.findingthecontradictionsinsideandacrossthevariousdepositions4.judgingthecredibilityoftheinformationitems5.judgingthereliabilityofthewitnessesInArtificialIntelligence,findingcontradictions(orincompatibilities)andrearrangingtheknowledgebaseinordertoremovethemisoftenreferredtoas“beliefrevision”.Somewhatdepartingfromtheliteratureonthissubject(see[37]forasurvey),weconceivedamodelforbeliefrevisionthatsuitedthemulti-sourcecharacteristicoftheinquirydomain[38].ThatmodellayeddownthearchitectureofanInquirySupportSystem(hereaftercalledISS)thatcouldhelpadetectivetoperformtheactivities3,4and5(see[16]).ThatISS’sultimatetaskswerethoseof:1.findingthemaximalconsistentsubsetsofthebeliefsaboutthecaseunderconsideration2.orderingthemw.r.t.theirglobaldegreeofbelievability.However,thecredibilityoftheinformationitems,aswellasthereliabilityofthewitnesses,wereestimatedinsomestrangeandrathernaiveways.OneofISS’worstcharacteristicwasthatsuchvaluesweredependent(atleasttheoretically)fromtheparticularchronologicalsequenceofthedepositionsreceivedfromthevariouswitnesses.RecentlywerealizedthattheBelief-FunctionFormalismadoptedtoaggregateauditevidence[13,18,19]worksaswellhere,and,expecially,thattheDempster’sRuleofCombinationisapowerfultooltocombinatetestimoniescomingfromdifferentindependentinformationsources.By“independent”wemeanthateachsourcereferinformation2perceiveddirectlyaseyewitnessandthats/hedoesnotarrangethedepositionwithsomeothersources.Ontheotherhand,wealsorealizedthattheclassicprobabilistictechniqueofBayesianConditioningisagoodmethodtoestimatethewitnesses’reliability,sinceitsatisfieswhatwedefined“safetynorm”(seesection4.1)andsinceitsetsatzerothereliabilityofawitnessthatcontradictshim/herself(aswebelieveitshouldbedone,seeagainsection4.1).Consequently,were-engineerizedthesystemtotakeadvantageofthepotentialityofthesetechniques.TheresultingnewISSisdescribedinthispaperwhichisorganizedasfollows.Section2introducesthemodelforbeliefrevisioninamulti-sourceenvironmentthatisthecoreofboth,theoldandthenewISS.Section3presentstheBelief-FunctionFormalismandtheBayesianConditioningasappliedinthismulti-sourcesenvironment.Section4illustratesthenewISSdiscussingtherelevanceoftheseideasintheinquirydomain.Section5containsanexampleandsection6discussesmeritsandlimitsofISS.2AModelforBeliefRevisioninaMulti-SourceEnvironmentSincetheseminal,influentialandphilosophicalworkofAlchourrón,GärdenforsandMakinson[39],theideason“beliefrevision”havebeenprogressivelyrefined[22,37]andamelioratedtowardnormative,effectiveandquasi-computableparadigms[26,29].Definedasasymbolicmodel-theoreticalproblem,beliefrevisionhasimmediatelybeenapproachedbothasaqualitativesyntacticprocessandasanumericalmathematicalissue.Tryingtogiveaunitary(althoughapproximate)perspectiveofthiscompositesubject,webeginbysayingthatbeliefrevisioncanbegivenbothasyntacticandasemanticcharacterization,asdepictedinFigure1.ThecognitivestateKandtheincominginformationAcanberepresentedeitherassetsofsentencesorassetsofpossibleworlds(themodelsofthesetsofsentences).Thenumbersαicanbeeitherreals(normallybetween0and1),representingexplicitlythecredibilityofthesentences/models,orordinals,representingimplicitlythebelievabilityofthesentences/modelsw.r.t.theotherones.Essentially,thebeliefrevisionprocessconsistsintheredefinitionoftheseweightsofcredibilityinthelightoftheincominginformation.TheresultingrevisedcognitivestateisgenerallydenotedKA*.3α1Α:Α…→Β:αn¬ΒΑ:Α…→Β:¬Β:…???+=possibleworld1:possibleworldn:…possibleworldjpossibleworldk…α1αmpossibleworld1:possibleworldn:…??+=CognitiveStateKIncomingInformationARevisedCognitiveStateKA*SyntacticConnotationSemanticConnotationFig1.SyntacticandSemanticconnotationsoftheBeliefRevisionprocessMostofthemethodsforbeliefrevisiondevelopedsofarobeythefollowingthreerationalityprinciples[1,2,22-27]:BR1.Consistency:KA*shouldbeconsistent(whateveritcoudmeaninanumericalsetting)BR2.MinimalChange:KA*shouldbeascloseaspossibletoKBR3.PriorityofIncomingInformation:KA*mustembodyA(thisisthereasonwhyAcomeswithoutaweightinFigure1;itsweightisundertakentobe“1”)Accordingtous,inamulti-agentenvironment,whereinformationcomesfromavarietyofhumanorartificialsourceswithdifferentdegreesofreliability,beliefrevisionhastodepartconsiderablyfromtheoriginalframework.Particularly,thelastprincipleshouldbeabandoned.Whilegivingprioritytotheincominginformationisacceptablewhenupdatingtherepresentationofanevolvingworld,itisnotgenerallyjustifiedwhenrevisingtherepresentationofastaticsituation.Inthiscase,thechronologicalsequenceoftheinformativeactshasnothingtodowiththeircredibilityorimportance.Furthermore,acceptingthein