varyingwww.haole008.com
www.haole008.com 时间:2021-04-06 阅读:()
EvidenceandscenariosensitivitiesinnaiveBayesianclassiersSiljaRenooij*,LindaC.
vanderGaagDepartmentofInformationandComputingSciences,UtrechtUniversity,P.
O.
Box80.
089,3508TBUtrecht,TheNetherlandsAvailableonline29February2008AbstractEmpiricalevidenceshowsthatnaiveBayesianclassiersperformquitewellcomparedtomoresophisticatedclassiers,eveninviewofinaccuraciesintheirparameters.
Inthispaper,westudytheeectsofsuchparameterinaccuraciesbyinves-tigatingthesensitivityfunctionsofanaiveBayesiannetwork.
Weshowthat,asaconsequenceofthenetwork'sindepen-denceproperties,thesesensitivityfunctionsarehighlyconstrained.
WefurtherinvestigatewhetherthepatternsofsensitivitythatfollowfromthesefunctionssupporttheobservedrobustnessofnaiveBayesianclassiers.
Inadditiontostandardsensitivitiesgivenavailableevidence,wealsostudytheeectofparameterinaccuraciesinviewofscenariosofadditionalevidence.
Weshowthatstandardsensitivityfunctionssucetodescribesuchscenariosensitivities.
2008ElsevierInc.
Allrightsreserved.
Keywords:NaiveBayesianclassiers;Sensitivity;Robustness1.
IntroductionBayesiannetworksareoftenemployedforclassicationpurposeswhereaninputinstancedescribedintermsofobservablefeaturevariables,istobeassignedtooneofanumberofpossibleoutputclasses.
TheBayesiannetworkforthispurposecomputes,giventheinstance,theposteriorprobabilitydistributionoverthevariablemodellingtheseclasses.
Theactualclassierthenisafunctionthatassignsasingleclasstotheinstance,basedonthecomputedposteriordistribution.
SuchclassiersareoftenbuiltuponanaiveBayesiannetwork,consistingofasingleclassvariableandanumberoffeaturevariables,whicharemodelledasbeingmutuallyindependentgiventheclassvariable.
Theparameterprobabilitiesforsuchanetworkaregenerallyestimatedfromdataandinevitablyareinaccurate.
Experimentshaveshown,timeandagain,thatclassiersbuiltonnaiveBayesiannetworksarecompetitivewithother,oftenmoresophisticatedclassicationmodels,regardlessofthesizeandqualityofthedatasetfromwhichtheyarelearned,e.
g.
[5,9,12].
VariousaspectsofthenaiveBayesianclassierhavebeenstudiedinattemptstoexplainthesendings.
Forbinaryclassvariables,forexample,itwasshownthatthecommonlyusedwinner-takes-allrule,whichassignsaninstancetoaclasswithhighestposteriorprobabilityaccordingtotheunderlyingBayesiannetwork,contributestothenaiveclassier'ssuccess[5].
Theobservedrobustnesswas0888-613X/$-seefrontmatter2008ElsevierInc.
Allrightsreserved.
doi:10.
1016/j.
ijar.
2008.
02.
008*Correspondingauthor.
E-mailaddresses:silja@cs.
uu.
nl(S.
Renooij),linda@cs.
uu.
nl(L.
C.
vanderGaag).
Availableonlineatwww.
sciencedirect.
comInternationalJournalofApproximateReasoning49(2008)398–416www.
elsevier.
com/locate/ijaralsoattributedtotheindependencepropertiesoftheclassier.
Itwasshown,forexample,thatnaiveBayesianclassiersperformwellnotonlyforcompletelyindependentfeaturevariables,butalsoforfunctionallydepen-dentones[5,12].
WenotethatmostofthefavourableexperimentalreportsonnaiveBayesianclassiersarebasedontheassumptionofabinaryclassvariablewitharatheruniformpriorprobabilitydistributionoveritsvalues.
Inthispaper,wefollowupontheobservationthat,apparently,inaccuraciesintheparameterprobabilitiesoftheunderlyingnaiveBayesiannetworkdonotsignicantlyaecttheperformanceoftheclassier.
Weemploysensitivity-analysistechniquestostudytheeectsofparametervariationontheposteriorprobabilitydistributionscomputedfromanaiveBayesiannetwork,andtherebycontributefurthercorroborationfortheobservedrobustnessofthistypeofclassier.
WewouldliketonotethatsensitivityanalysishasbeenappliedbeforeinthecontextofnaiveBayesianclassiers,asameansofprovidingboundsontheamountofparametervariationthatisallowedwithoutchanging,foranyofthepossibleinputinstances,themostlikelyvalueofabinaryclassvariable[3].
Theseboundsareusefulforestablishingwhichparameteruponvariationcanneverchangetheclassier'soutput,regardlessoftheenteredevidence.
Thecomputationofthesebounds,however,requireseitherexplicitenumerationoverallpossibleinstancesoraconversionofthenaiveBayesianclassierintoanordereddecisiondiagram.
WeextendontheseearlierresultsbystudyingthemathematicalfunctionsthatdescribethesensitivityofaposteriorprobabilityofinterestcomputedfromthenaiveBayesiannetwork,tovariationofaparameter'svalue;thesefunctionsaretermedsensitivityfunctions[1,4].
WeshowthattheindependenceassumptionsunderlyinganaiveBayesiannetworkconstrainthesesensitivityfunctionstosuchanextentthattheycanbeestablishedexactlyfromverylimitedinformationfromthenetworkathand.
Inaddition,westudythesensitivitypropertiesthatfollowfromtheconstrainedfunctionsandarguehowthesepropertiessupporttheobservedrobustnessofnaiveBayesianclassiers.
Inthispaper,wealsointroducethenovelnotionofscenariosensitivity,whichweuseforfurtherstudyingaclassier'srobustness.
Forclassicationproblems,itisoftenassumedthatevidenceisavailableforeverysinglefeaturevariable.
Innumerousapplicationdomains,however,thisassumptionmaynotberealistic,especiallynotfordomainsinwhichevidenceisgatheredselectivelyinastepwisemanner.
Thequestionthenariseshowmuchimpactfurtherevidencecouldhaveonthecomputedposteriorprobabilitydistributionsandhowsen-sitivethisimpactistoinaccuraciesinthenetwork'sparameters.
Weintroducethenotionofscenariosensitiv-itytocapturethelattertypeofsensitivityandshowthattheeectsofparametervariationinviewofscenariosofadditionalevidencecanbeestablishedecientlyfornaiveBayesiannetworks.
Thepaperisorganisedasfollows.
InSection2,wepresentsomepreliminariesonsensitivityfunctionsandtheirassociatedsensitivityproperties.
InSection3,weestablishthefunctionalformofthesensitivityfunctionsforanaiveBayesiannetworkintermsofvariationoftheparameterprobabilitiesoftheclassvariable,andaddresstheensuingsensitivityproperties.
Section4addressesthesensitivityfunctionsandassociatedproper-tiesthatresultfromvariationoftheparameterprobabilitiesofthefeaturevariables.
InSection5weintroducethenotionofscenariosensitivityandshowthatitcanbeestablishedfromstandardsensitivityfunctions.
ThepaperendswithourconcludingobservationsinSection6.
2.
PreliminariesandnotationABayesiannetworkessentiallyisacompactrepresentationofajointprobabilitydistributionProverasetofstochasticvariablesV[10].
Thevariablesandtheirinterrelationshipsarecapturedasnodesandarcs,respec-tively,inanacyclicdirectedgraphG.
AssociatedwitheachnodeinthegraphisasetofparameterprobabilitieshVjpVthatcapturethestrengthoftherelationshipbetweenavariableVanditsparentspV.
FromaBayesiannetwork,anypriororposteriorprobabilityofinterestoveritsvariablescanbecomputed.
Inthispaper,wefocusmorespecicallyonnaiveBayesiannetworks,inwhichthedigraphmodellingtheinterrelation-shipsbetweenthevariableshasarestrictedtopology.
ThedigraphofsuchanetworkiscomposedofnodesfCg[EwithEfE1;Eng,nP2,andarcsC;Eiforalli1;n;thevariableCiscalledtheclassvariableandthevariablesEiaretermedfeaturevariables.
TherestrictedtopologyofthedigraphofanaiveBayesiannetworkcapturesconditionalindependenceofanytwofeaturevariablesgiventheclassvariable.
AlthoughanyprobabilitycanbecomputedfromanaiveBayesiannetwork,theposteriorprobabilitiesofthevariousclassvaluesareofprimaryinterest.
ThenetworkfurtherisassociatedwithaclassicationfunctionS.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416399which,basedupontheseposteriorprobabilities,returnsasinglemostlikelyclassvalue,breakingtiesatrandom.
TheparameterprobabilitiesofaBayesiannetworkareeitherestimatedfromdataorassessedbydomainexperts,andinevitablyincludesomeinaccuracies.
Toinvestigatetheeectsoftheseinaccuraciesonthecom-putedposteriorprobabilities,aBayesiannetworkcanbesubjectedtoasensitivityanalysis.
Insuchananalysis,oneormorenetworkparametersarevariedsystematicallyandtheeectsofthisvariationonanoutputprob-abilityofinterestarestudied.
Inthispaper,wefocusprimarilyonsensitivityanalysesinwhichjustoneparam-eterisbeingvaried;suchananalysisistermedaone-waysensitivityanalysis.
Theeectsoftheparametervariationarecapturedbyasimplemathematicalfunction,calledasensitivityfunction.
Beforereviewingthefunctionalformofsuchasensitivityfunction,weobservethatuponvaryingaparticularparameterprobabil-ity,theparameterspertainingtothesameconditionaldistributionshouldbeco-variedtoensurethattheirsumremainsone.
Thewell-knownschemeofproportionalco-variationisoftenusedforthispurpose1asithasbeenshowntoresultinthesmallestchangeintheoutputdistribution[2].
Underthisscheme,anyone-waysensi-tivityfunctionisaquotientoftwolinearfunctionsintheparameterunderstudy[1,4].
Moreformally,uponvaryingasingleparameterprobabilityx,thefunctionfPrcjexthatexpressestheoutputprobabilityofinterestPrcjeintermsofxtakestheformfPrcjexfPrc;exfPrexaxbgxhwheretheconstantsa;b;g;harebuiltfromthenon-variedparametersfromthenetworkunderstudy.
Thefourconstantsarederivedanalyticallyin[4];feasiblealgorithmsfortheircomputationareavailablefrom[4,7].
Inthesequel,insteadoffPrcjexwewilloftenwritefcxorfxforshort,aslongasnoconfusionispossible.
Inouranalyses,wefurtherassumethatparameterswithanoriginalassessmentof0or1arenotvaried,sincetheseparametersrepresentlogicalconsequencesorimpossibilitiesandthereforedonotincludeanyinaccuracies.
Aone-waysensitivityfunctionfxcantakeoneofthreegeneralforms.
Thefunctionislineariftheprob-abilityofinterestisapriorprobabilityratherthanaposteriorprobability,oriftheprobabilityoftheenteredevidenceisunaectedbytheparametervariation;notethatinthelattercasewehavethatPreisaconstantandhenceg0.
IftheprobabilityPreoftheevidenceequals0wheneverx0,inwhichcasewehavethath0,thenitisreadilyshownthatthesamemustholdforthemarginalprobabilityPrc;e,thatis,wemusthavethatb0;thesensitivityfunctionthenreducestoaconstant.
Inallothercasesthesensitivityfunctionisafragmentofarectangularhyperbola,whichtakesthegeneralformfxrxsttxrstxs;withshg;tag;andrbgstwiththeconstantsa;b;g;hasabove.
Intheremainderofthepaper,wefocusonthislasttypeoffunctionandassumeanysensitivityfunctiontobehyperbolicunlessexplicitlystatedotherwise.
Arectangularhyper-bolaingeneralhastwobranchesandtwoasymptotesdeningitscenters;t;Fig.
1illustratesthelocationsofthepossiblebranchesrelativetotheasymptotes.
Weobservethatasensitivityfunctionisdenedby06x;fx61;thetwo-dimensionalspaceoffeasiblepointsthusdened,istermedtheunitwindow.
Sinceasensitivityfunctionmoreovershouldbecontinuousforx20;1,itsverticalasymptotenecessarilyliesout-sidetheunitwindow,thatis,eithers1.
FromtheseobservationsweconcludethatahyperbolicsensitivityfunctionisafragmentofjustoneofthefourpossiblebranchesshowninFig.
1.
Fromasensitivityfunction,variouspropertiescanbecomputedthatservetosummarisetheeectsofparametervariation.
Herewebrieyreviewthepropertiesofsensitivityvalue[8]andofadmissibledeviation[13].
Thesensitivityvalueforaparameterxistheabsolutevaluejof=oxx0joftherstderivativeofthesen-sitivityfunctionfxattheparameter'soriginalvaluex0.
Itdescribestheeectofaninnitesimallysmallshiftintheparameterontheoutputprobabilityofinterest.
Inessence,thelargerthesensitivityvalueforaparam-eteris,thelessrobusttheoutputprobabilityofinterestwillbetoinaccuraciesintheparameter.
Wewouldlike1Whenaparameterprobabilityhisvariedfromthevalueholdtothevaluehnew,eachparameterh06hfromthesamedistributionisvariedfromh0oldtoh0new,whereh0newh0old1hnew1hold.
400S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416tonotethattheimpactofalargershiftinaparameter'svalueisstronglydependentuponthelocationofthevertexofthesensitivityfunction,thatis,ofthepointwherejof=oxxj1.
Thevertexcanliewithintheunitwindow,ortoitsleftorright.
Avertexthatlieswithintheunitwindowbasicallymarksthetransitionfromparametervalueswithalargesensitivityvaluetoparametervalueswithasmallsensitivityvalue,orviceversa.
Aparameterwithasmallsensitivityvaluecanthushavelargereectsthanitssensitivityvaluesuggests,ifitliesintheproximityofthevertex,thatis,ifitsoriginalvaluex0isclosetothevertex'x-value.
IftheposteriorprobabilitiescomputedfromaBayesiannetworkareusedforestablishingthemostlikelyvalueofanoutputvariable,itistheeectofparametervariationontheoutputvaluethatisofinterest.
Foraparameterwithanoriginalvalueofx0,theadmissibledeviationisapaira;b,whereaistheamountofvariationallowedtoval-uessmallerthanx0withoutchangingthemostlikelyoutputvalueandbistheamountofvariationallowedtolargervalues;thesymbolsand!
areusedtoindicatethatvariationisallowedtotheboundariesoftheunitwindow.
Thelargertheadmissibledeviationforaparameteris,therefore,themorerobusttheoutputvaluewillbetoinaccuraciesinthisparameter.
3.
SensitivitytoclassparametersUponbeingsubjectedtoasensitivityanalysis,theindependencepropertiesofanaiveBayesiannetworkstronglyconstrainthegeneralformoftheresultingsensitivityfunctions.
Infact,givenjustlimitedinformationfromthenetwork,theexactfunctionscanbereadilyestablishedforeachclassvalueandeachparameterprob-ability.
Inthissectionwederivethesensitivityfunctionsthatdescribeanoutputprobabilityofinterestasafunctionofaparameterfortheclassvariable.
Wedetailthesensitivitypropertiesthatfollowfromthesefunc-tionsanddiscusstheirpossibleeectsontherobustnessofnaiveBayesianclassiers.
InSection4,wewilladdressthesensitivityfunctionsforparametersforthefeaturevariablesinasimilarfashion.
3.
1.
FunctionalformsThefollowingpropositionstatesthefunctionalformofany(hyperbolic)sensitivityfunctionthatdescribesanoutputprobabilityofanaiveBayesiannetworkintermsofasingleparameterxhc0,associatedwithaspecicvaluec0oftheclassvariableC.
Thepropositionmorespecicallyshowsthatsuchafunctionishighlyconstrainedandcaninfacttakeonlyoneoftwoforms.
Proofsofthisandsubsequentpropositionsarepre-sentedinAppendixA.
Proposition1.
Letxhc0beaparameterprobabilitypertainingtothevaluec0oftheclassvariableC,andletx0beitsoriginalvalue.
LetPrcjebeanoutputprobabilityofinterestwiththeoriginalvaluep0,andletp00betheoriginalvalueofPrc0je.
Then,thesensitivityfunctionfPrcjexhasthefollowingform:√|2r|center(s,t)vertexr1t≤1r0s0s>1t≥0IIVIIIIIFig.
1.
TworectangularhyperbolaswithbranchesintheIstandIIIrdquadrantsrelativetothehyperbola'scenter,andintheIIndandIVthquadrants,respectively;theconstraintsontheconstantsr,sandtarespecicforsensitivityfunctions.
S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416401fPrcjex1sxxsifcc0p01p00sx1xsotherwise8>:inwhichthevalues,deningthefunction'sverticalasymptote,equalss1p00x0x0p00Thevaluet,deningthehorizontalasymptoteofthesensitivityfunction,equalst1sifcc0p01p00sotherwise(WenotethattheabovepropositionpertainstoasingleoutputprobabilityofinterestPrcje.
Sincethechoiceofclassvaluec,however,isarbitrary,thepropositionholdsforanyvalueofC.
Theoriginalvaluep0oftheoutputprobabilityofinterestobviouslydependsonthevalueofcunderconsiderationand,asaresult,sodoestheactualvalueofthehorizontalasymptotet.
Fromtheaboveproposition,weobservethatthesensitivityfunctionfPrc0jexpertainingtotheclassvaluewhoseparameterprobabilityisbeingvaried,includesthepointsfc000andfc011fromtheunitwindow;thefunctionthusisafragmentofeitheraIInd-quadrantoraIVth-quadranthyperbolabranch.
ThesensitivityfunctionsfPrcjex,c6c0,pertainingtotheothervaluesoftheclassvariablethenarefragmentsofeitherIst-orIIIrd-quadranthyperbolabranches.
Fig.
2illustratesthetwopossiblesituations.
ThesensitivityfunctionfPrc0jexbeingaIInd-quadrantfunctioncorrespondswithaverticalasymptotetotherightoftheunitwindow,thatis,withs>1andhencewithx0>p00;thesensitivityfunctionspertainingtotheothervaluesofCthenareIIIrd-quadrantfunctions.
TheIVth-andIst-quadrantcombinationoffunctionscorrespondswithx0>>:wherep0againistheoriginalvalueofPrcjeandp00istheoriginalvalueofPrc0je;x0istheparameter'sori-ginalvalueasbefore.
From1p00Pp0foranyvaluecoftheclassvariable,weobservethatthehighestsen-sitivityvaluefortheparameterxisobtainedwhentheoutputprobabilityofinterestpertainstotheclassvaluec0whoseparameterisbeingvaried.
Thesensitivityvaluefoundtheninfactmatchestheupperboundonsen-sitivityvaluesforsensitivityfunctionsingeneral[11].
Notethatforabinaryclassvariable,wewouldhavethat1p00p0andthesensitivityvaluesforthetwoclassvalueswouldbethesame.
Thesensitivityvaluescom-putedfromthefunctionfPrc0jexfordierentcombinationsofvaluesforx0andp00aredepictedinFig.
3.
Thegureshowsthatlargesensitivityvaluescanbefoundonlyforratherextremeparametervaluesincombina-S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416403tionwithlessextremeoutputprobabilities.
Wefurtherrecallthat,despitetheirsmallsensitivityvalues,alsoparameterswithanoriginalvalueclosetothex-valueofthesensitivityfunction'svertexmayshowsignicanteectsuponvariation.
Forclassparameters,thesensitivityfunctionfPrc0jexalwayshasitsvertexwithintheunitwindow;thevertexinfactliesonthelinex1fx.
Iftheverticalasymptoteofthesensitivityfunctionliesquiteclosetotheunitwindowandthevertexinadditionisnottoofarfromtheasymptote,thenaparam-eterwithanoriginalvalueintheproximityofthevertexwillshowconsiderableimpactontheoutputprob-abilityifitisvariedfurthertothenearbyextreme.
Fromtheaboveconsiderations,wehavethatinnaiveBayesiannetworkstheoutputprobabilityofinterestwillbesensitivetovariationinaclassparameteronlyiftheclassvalueunderconsiderationeitheroccursratherseldomlyorquitefrequentlyinthedomainofapplicationandtheinstanceathanddoesnotsupportthe(un)likelihoodofthisclassvalue.
AslongastheclassparametersofanaiveBayesiannetworkarenothighlyunbalanced,therefore,willtheprobabilitywithwhichaninstanceispredictedtobelongtoaparticularclassbequiteinsensitivetoparametervariation.
WenotethatitisnotuncommontondclassvariableswithsuchdistributionsinthedomainsinwhichnaiveBayesianclassiersarebeingapplied.
Yet,alsotheoutputprobabilitiescomputedfromanaiveBayesiannetworkinwhichoneormoreclassvalueshaverathersmallpriorprobabilities,willbequiterobustaslongastheposteriorprobabilitiescomputedfortheseclassesarequiteextremeforallpossibleinstances.
3.
2.
2.
AdmissibledeviationInviewofestablishingthemostlikelyclassvalueforaninstance,thepropertyofadmissibledeviationisofinterest.
Werecallthattheadmissibledeviationforaparametergivestheamountofvariationthatisallowedinitsoriginalvaluebeforethemostlikelyclassvaluechanges.
ThefollowingpropositiongivestheadmissibledeviationforaclassparameterinanaiveBayesiannetwork.
Thepropositionmorespecicallyshowsthatthemostlikelyclassvaluechangesexactlyonceuponvaryingsuchaparameter.
Proposition2.
Letxhc0beaparameterprobabilitypertainingtothevaluec0oftheclassvariableC,andletx0beitsoriginalvalue.
Letp00betheoriginalvalueofPrc0je,letpT0argmaxc6c0fPrcjeg,andletcTbeavalueofCforwhichPrcTjepT0.
Then,fPrcjex6fPrcTjexforallc6c0Furthermore,theadmissibledeviationforxisa;bx0xm;!
ifpT0p000;!
or;0otherwise8>:wherexmpT0x01x0p00pT0x000.
20.
40.
60.
81x000.
20.
40.
60.
81p'000.
511.
522.
53|dfc'/dx(x0)|Fig.
3.
Thesensitivityvalueforaclassparameterxhc0andsensitivityfunctionfPrc0jex,asafunctionoftheoriginalparametervaluex0andtheoriginalposteriorp00.
404S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416Fromtheaboveproposition,weobservethatanyclassparametercanbevariedtotheboundaryoftheunitwindowinoneofthetwopossibledirectionswithoutchangingthemostlikelyclassvalue,asindicatedbytheand!
symbols.
Uponvaryinganysuchparameterintheotherdirection,themostlikelyclassvaluechangesexactlyonce.
NotethatFig.
2supportstheseobservations.
ForthecasewherepT0p00,wenotethat,giventheoriginalvaluex0oftheparameterunderstudy,thetwoclassvaluesc0andcTareequallylikely.
Theboundarytowhichtheparametercanbevariedwithoutinducingachangethendependsonwhichofthetwoclassvaluesisdesignatedtheuniquemostlikelyclassbythenetwork'sassociatedclassicationfunction.
WefurtherobservethatthesmallerthedierenceisbetweenthetwoposteriorprobabilitiespT0andp00,thesmallertheadmissibledeviationfortheparameterisandthelessrobusttheclassvaluereturnedbytheclassierwillbe.
Asaspecialcaseoftheaboveproposition,weconsiderauniformlydistributedbinaryclassvariable,thatis,weconsiderthecasewherex00:5andpT01p00;notethatinthiscasewendforthevaluexmatwhichthetwosensitivityfunctionsintersect,thatxm1p00.
Theadmissibledeviationfortheclassparameterxhc0thenequalsp000:5;!
ifpT0p00,thatis,iftheinstancepointstotheothervalueoftheclassvariable.
Wenotethatthemoreextremetheoriginalvaluep00ofthepos-teriorprobabilityofinterestis,thelargertheadmissibledeviationwillbeandthelessimpactvariationofaclassparametercanhaveonthemostlikelyclassvalue.
Furthernotethatfornon-binaryclassvariables,thevalueofxmintheadmissibledeviationmaybelessextreme,whichmayresultinsmalleradmissibledevi-ationsandalessrobustoutputclass.
Example2.
WeconsideragainthenaiveBayesiannetworkandtheassociatedpatientinformationfromExample1.
SupposethatweareinterestedintheeectsofinaccuraciesintheparameterprobabilityxhSIVA,withanoriginalvalueofx00:10,onthemostlikelyclassvalueestablishedforourpatient.
Werecallthat,withtheparameter'soriginalvalue,stageIVAisthemostlikelystageforthepatient,withaprobabilityof0.
61;thesecondmostlikelystageisstageIIA,withaprobabilityof0.
19.
Usingtheseprobabilities,wendforthevaluexmfromProposition2thatxm0:190:10=0:900:610:190:100:03.
Theadmissibledeviationfortheparameterunderstudythusis0:07;!
.
Thisadmissibledeviationindicatesthattheparametercanbevariedfrom0.
10to1.
00withoutinducingachangeinthemostlikelystageforthepatient.
Theparametercanalsobevariedtosmallervalues,butthemostlikelystagewillchangefromIVAtoIIAiftheparameteradoptsavaluesmallerthan0.
03.
Notethatthemostlikelystagecannotchangeintoanyothervalueuponvaryingtheparameter.
Furthernotethat,althoughinabsolutetermsonlyasmallshiftisallowedtosmallerparametervalues,theadmissibledeviationisquitelargerelativetotheparameter'soriginalvalue.
Nowsupposethatweweretouseatwo-valuedratherthanasix-valuedvariableclassvariable.
WedeneforthispurposethenewvariableOperable,ofwhichthevalue'yes'coincideswithstagesI,IIAandIIB,andthevalue'no'capturesthestagesIII,IVAandIVB.
Giventhepatient'savailableinformation,theposteriorsPrOperableyesje0:21andPrOperablenoje0:79arecomputed;thevalue'no'thusisthemostlikelyclassvalueforthepatient.
SupposethatweareinterestedintheeectsofinaccuraciesintheparameterxhOperableno,withanoriginalvalueofx00:61,onthemostlikelyvalueoftheoutputvariable.
Wendthatthesensitivityfunctionsassociatedwiththetwovaluesoftheclassvariableintersectatxm0:29.
Theadmissibledeviationforparameterxthusequals0:32;!
.
Thisadmissibledeviationindicatesthattheparametercanbevariedfrom0.
61to1.
00withoutinducingachangeinthemostlikelyclassvalue.
Theparametercanalsobevariedtovaluessmallerthan0.
61,butthemostlikelyvaluewillchangefrom'no'to'yes'iftheparameteradoptsavaluesmallerthan0.
29.
Notethattheparametercanthusbevariedtoapproximatelyhalfitsoriginalvalue.
Fromtheaboveconsiderations,weconcludethatthemostlikelyclassvalueestablishedfromanaiveBayes-iannetworkwillbequitesensitivetoinaccuraciesinthenetwork'sclassparametersiftheoutputprobabilitiesfortheclassvariablearemoreorlessuniformlydistributed.
Morespecically,themostlikelyclassvaluewillnotbeveryrobusttovariationintheclassparametersifithasapproximatelythesameposteriorprob-abilityastherunner-upvalue.
TheclassicationperformanceofanaiveBayesianclassierwillthusbequiterobustifthemajorityofpresentedinstancesresultinasingleratherlikelyclassvalue.
Infact,itwillberobustaslongasthemajorityofinstancesbelongtotheapriorimostlikelyclass,whichwewouldexpectiftheclas-sierissucientlytailoredtothedomainofapplication.
S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–4164054.
SensitivitytofeatureparametersInthissectionwederiveforanaiveBayesiannetworkthesensitivityfunctionsthatdescribeanoutputprobabilityofinterestasafunctionofaparameterforafeaturevariable.
Weshowthatalsoforfeatureparameterstheexactsensitivityfunctionscanbereadilyestablishedgivenjustlimitedinformationfromthenetwork.
WefurtherdetailthesensitivitypropertiesfollowingfromthefunctionsanddiscusstheirpossibleeectsontherobustnessofnaiveBayesianclassiers.
4.
1.
FunctionalformsThefollowingpropositionstatesthefunctionalformofany(hyperbolic)sensitivityfunctionthatdescribesanoutputprobabilityofanaiveBayesiannetworkintermsofasinglefeatureparameterxhe0vjc0,wheree0vdenotesavalueofthefeaturevariableEvandc0isavalueoftheclassvariable.
Thepropositionshowsthatthefunctionagainishighlyconstrained;infact,foranyclassvalueandanyfeatureparameter,onlyoneoffourfunctionalformscanresult.
Proposition3.
LetEvbeafeaturevariableandletevbeitsvalueintheinstancee.
Letxhe0vjc0beaparameterprobabilitypertainingtothevaluee0vofEvandtheclassvaluec0,andletx0beitsoriginalvalue.
LetPrcjebeanoutputprobabilityofinterestwiththeoriginalvaluep0,andletp00betheoriginalvalueofPrc0je.
Then,thesensitivityfunctionfPrcjexhasoneofthefollowingforms:fPrcjexxxsifcc0andeve0vx1xsifcc0andev6e0vp0x0sxsotherwise8>>>:inwhichthevalues,deningthefunction'sverticalasymptote,equalssx0x0p00ifeve0vx01x0p00otherwise8>:Thevaluet,deningthehorizontalasymptoteofthesensitivityfunction,ist1ifcc00otherwiseWeconsideragainthepossiblelocationsofthesensitivityfunctionsforafeatureparameterunderstudy.
Forthecasewhereeve0v,wendforthevaluesx0x0=p00oftheverticalasymptotethats1;wethenndIIIrd-andIInd-quadrantbranches,respectively.
Fig.
4illustratesthetwopossiblesituations.
TointuitivelyexplainwhythefunctionfPrc0jexagainhasadif-ferentshapefromtheotherfunctions,weobservethatvaryingafeatureparameterheijc0givenaparticularvaluec0oftheclassvariablehasadirecteectontheposteriorprobabilityPrc0jeofthisclassvaluec0only;theprobabilitiesPrcje,c6c0,fortheothervaluesoftheclassvariableareaectedonlyindirectlytoensurethatthedistributionovertheclassvariablesumstoone.
Fromthehighlyconstrainedformofthefunctions,moreover,wehavethatallfunctionsfPrcjex,c6c0,havethesameshape.
TheshapeofthefunctionfPrc0jexthereforemustbedeviant.
Weagainillustratethefunctionalformofthesensitivityfunctionsderivedabovewithanexample.
Theexampleoncemoredemonstratesthatasaresultoftheirconstrainedform,anysensitivityfunctioncanbeestablishedfromverylimitedinformation.
Example3.
WeagainconsiderthenaiveBayesiannetworkandthepatientinformationfromExample1.
WefurtherconsiderthefeaturevariableCT-loco,modellingthepresenceorabsenceofloco-regionalmetastasesassuggestedbyaCTscanofthepatient'sthorax.
Thenetworkincludesthefollowingparameterprobabilitiesforthisvariable:TheposteriorprobabilitydistributionPrSjecomputedovertheclassvariablegiventheavailablendingsforourpatient,whoshowsnosignsofloco-regionalmetastases,arefoundinExample1.
NowsupposethatweareinterestedintheeectofinaccuraciesintheparameterprobabilityxhCT-loconojSIVAontheseposteriorprobabilities.
Theeectiscapturedbysixsensitivityfunctionswiththesameverticalasymptote,whosevaluesisreadilyestablished:sincetheoriginalvalueoftheparameterequals0.
52andtheoriginalposteriorprobabilityofstageIVAforthepatientis0.
61,wendthats0:520:52=0:610:33.
ThesensitivityfunctionfIVAxthereforeisaIVth-quadranthyperbolabranch;thefunctionsfortheotherstagesareIst-quadrantbranches.
Notethatforthecomplementoftheparameterx,thesixsensitivityfunctionswouldallhavetheirverticalasymptoteats1:33.
Withoutperforminganyfurthercomputations,weestablishthatfIVAxxx0:33andfSxPrSje0:85x0:33foranyS6IVAFromtheaboveconsiderations,wehavethatthesensitivityfunctionsresultingfromaone-wayanalysisforafeatureparameter,arehighlyconstrained.
Justasthesensitivityfunctionsfortheclassparameters,wendthatthefunctionsforthefeatureparametersareexactlydeterminedbytheoriginalvaluesfortheseparametersandtheoriginalposteriorprobabilitydistributionfortheoutputvariableofinterest.
Computingtheexactfunctionsasaconsequenceagainrequiresjustasinglenetworkpropagationtoestablishtheposteriorclassdistribution.
4.
2.
SensitivitypropertiesFromthesensitivityfunctionsderivedabove,anysensitivitypropertypertainingtoanetwork'sfeatureparameterscanbecomputed.
Weagainstudythepropertiesofsensitivityvalueandadmissibledeviation.
4.
2.
1.
SensitivityvalueFromthesensitivityfunctionfPrcjexexpressingtheoutputprobabilityPrcjeintermsofafeatureparameterxhe0vjc0,theassociatedsensitivityvalueisreadilyestablished:iftheobservedinstanceeincludesthevalueeve0v,wendthathCT-locojSIIIAIIBIIIIVAIVBCT-locoyes0.
020.
020.
480.
480.
480.
27no0.
980.
980.
520.
520.
520.
73S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416407ofPrcjeoxx01p00p00x0ifcc0p0p00x0otherwise8>:wherep0againistheoriginalvalueofPrcjeandp00istheoriginalvalueofPrc0je;x0istheparameter'sori-ginalvalueasbefore.
Iftheinstanceeincludesanotherobservedvalueev6e0v,thenasimilarresultisfoundbyreplacingx0by1x0.
From1p00Pp0foranyvaluecoftheclassvariable,wendthatthehighestsensi-tivityvaluefortheparameterxagainisobtainedwhentheoutputprobabilityofinterestpertainstothesameclassvaluec0asthefeatureparameterbeingvaried,regardlessofthevaluethatisobservedforthefeaturevar-iableEv.
Forthecasewheretheinstanceeincludesthevalueeve0v,Fig.
5depictsthesensitivityvalueoffPrc0jexfordierentcombinationsofvaluesforx0andp00.
Thegureshowsthatlargesensitivityvaluescanonlybefoundiftheoriginalvaluex0fortheparameterunderstudyisquitesmallandtheoriginalpos-teriorprobabilityp00islessextreme;morespecically,wehavethatofPrc0je=oxx0>1ifandonlyifx0p00and1x0p00andx0>>>>>>>>>>>>>>:wherexmpT0x0p00ifeve0v1pT01x0p00ifev6e0v8>:Fromtheaboveproposition,weobservethatanyfeatureparametercanbevariedtotheboundaryoftheunitwindowinatleastonedirectionwithoutchangingthemostlikelyclassvalue.
Uponvaryinganysuchparam-eterintheotherdirection,themostlikelyclassvaluecanchangeatmostonce.
Figs.
4and6supporttheseobservations.
ForthecasewherepT0p00,weagainnotethattheboundarytowhichtheparametercanbevar-iedwithoutinducingachangedependsonwhichofthetwoclassvaluesc0andcTisdesignatedtheuniquemostlikelyclassbythenetwork'sclassicationfunction.
WefurtherobservethatthesmallerthedierencebetweentheposteriorprobabilitiespT0andp00is,thesmallertheadmissibledeviationfortheparameterisandthelessrobustthereturnedclassvaluewillbe.
Weconsiderafeatureparameterxhe0vjc0andaninstanceeinwhicheve0vhasbeenobserved;similarargumentsholdforev6e0v.
Wesupposethattheclassvaluec0isnotthemostlikelyclassvaluegiventheavail-ableevidence.
Iftheoriginalvaluex0oftheparameterisrathersmall,wewouldnotexpecttondthefeaturevaluee0vwithclassc0.
Whenactuallyobserved,therefore,thefeaturevaluedoesnotsupportc0.
Iftheotherobservationsintheinstancealsodonotsupportc0,weexpectthatpT0)p00andalargeadmissibledeviationcanbefoundfortheparameter.
Iftheotherobservationsfromtheinstancedosupporttheclassvaluec0,how-ever,wewouldexpecttondalargerp00andhenceasmalleradmissibledeviation.
Fig.
6illustratestheseobservations.
Nowif,ontheotherhand,theoriginalparametervaluex0isrelativelylarge,wewouldindeedexpecttondthefeaturevaluee0vwithclassc0.
Theactualobservationofe0vthensupportsc0andweexpecttondasomewhatlargerposteriorprobabilityp00andarelativelysmalladmissibledeviation.
Areverseargumen-tationholdsforthecasewherec0isthemostlikelyclassvalue.
Example4.
WeconsideragainthenaiveBayesiannetworkandthepatientinformationfromExamples1and3.
Supposethatweareoncemoreinterestedintheeectofinaccuraciesintheparameterprobability00.
20.
40.
60.
8100.
20.
40.
60.
81fc(x)xx0fc'(x)00.
20.
40.
60.
8100.
20.
40.
60.
81fc(x)xx0fc'(x)Fig.
6.
Examplesensitivityfunctionsforafeatureparameterxhe0vjc0withoriginalvaluex00:2;c0isnotthemostlikelyclassvalue,andvariationoftheparametereithermakesc0themostlikelyvalue(left)ordoesnotchangethemostlikelyvalue(right).
S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416409xhCT-loconojSIVA,withanoriginalvalueofx00:52,onthemostlikelyclassvalueestablishedforourpatient.
Werecallthat,withtheparameter'soriginalvalue,stageIVAisthemostlikelystageforthepatient,withaprobabilityof0.
61;thesecondmostlikelystageisstageIIA,withaprobabilityof0.
19.
Wefurtherrecallthatforthepatientnosignsofloco-regionalmetastaseswerefoundontheCTscan.
Usingtheaboveprobabilities,wenowndforthevaluexmfromProposition3thatxm0:190:52=0:610:16.
Theadmissibledeviationfortheparameterunderstudythusis0:36;!
.
Thisadmissibledeviationindicatesthattheparametercanbevariedfrom0.
52to1.
00withoutinducingachangeinthemostlikelystageofthepatient'scancer.
Theparametercanalsobevariedtosmallervalues,butthemostlikelystagewillchangefromIVAtoIIAiftheparameteradoptsavaluesmallerthan0.
16.
Notethattheparametercanthusbevariedtoapproximatelyone-thirdofitsoriginalvalue.
Furthernotethatthemostlikelystagecannotchangeintoanyothervalueuponvaryingtheparameterunderstudy.
Fromtheaboveconsiderations,weconcludethatthemostlikelyclassvalueestablishedfromanaiveBayes-iannetworkwillbequitesensitivetoinaccuraciesinthenetwork'sfeatureparametersiftheoutputprobabil-itiesfortheclassvariablearemoreorlessuniformlydistributed.
Morespecically,themostlikelyclassvaluewillnotbeveryrobusttovariationinthefeatureparametersifithasapproximatelythesameposteriorprob-abilityastherunner-upvalue.
TheclassicationperformanceofanaiveBayesianclassierwillthusbequiterobustifthemajorityofpresentedinstancesresultinasingleratherlikelyclassvalue.
Yet,theoutputclassvalueestablishedfromanaiveBayesiannetworkinwhichoneormorefeaturesgivenaparticularclasshaverathersmallpriorprobabilities,willalsobequiterobustaslongastheposteriorprobabilitiescomputedforthisclassareratherextremeforallpossibleinstances.
5.
ScenariosensitivityForclassicationproblems,itisgenerallyassumedthatevidenceisavailableforeverysinglefeaturevar-iable.
Intheprevioussection,infact,wealsoadoptedthisassumption.
Inpracticalapplications,however,thisassumptionmaynotalwaysberealistic.
Inthemedicaldomain,forexample,apatientistobeclassiedintooneofanumberofdiseaseswithoutbeingsubjectedtoeverypossiblediagnostictest.
Thequestionthenariseshowmuchimpactadditionalevidencecouldhaveontheprobabilitydistributionovertheclassvariableandhowsensitivethisimpactistoinaccuraciesinthenetwork'sparameters.
Theformerissueiscloselyrelatedtothenotionofvalueof(perfect)informationandcanbestudiedaspartofasensitivity-to-evidence(SE)analysis[6].
Thelatterissueinvolvesanotionofsensitivitythatdiersfromthestandardnotionusedintheprevioussectionsinthatitpertainsnottoactuallyavailableevidencebuttoscenarioswithpossiblyadditionalevidence.
Werefertothisnotionofsensitivityasscenariosensitivityandusethetermevidencesensitivitytorefertothemorestandardnotion.
AlthoughitisapplicabletoBayesiannetworksingeneral,werestrictourdiscussionofthenotionofscenariosensitivityheretothecontextofnaiveBayesiannetworks.
Beforeelaboratingontheeectsofinaccuraciesinanetwork'sfeatureparametersontheimpactofaddi-tionalevidence,webeginbyreviewingtheimpactofthenewevidenceitselfonanoutputprobabilityofinter-est.
Forthispurpose,weconsider,foraspecicclassvalue,theratioofthetwoposteriorprobabilitiesgiventheavailableinstancepriortoandafterreceivingthenewevidence,respectively.
LetEOandENbesetsoffea-turevariableswith;EO&ENEandENEOfE1;Elg,16l6n.
LeteOandeNbeconsistentinstancesofEOandEN,respectively,suchthateNextendstheavailableinstanceeOwiththenewlyobtainedevidenceforthevariablesE1;El.
Then,foreachclassvaluec,wehavethatPrcjeNPrcjeOQli1PreijcPcjQli1PreijcjPrcjjeOwhereeiisthevalueofEiinEN.
Notethattheabovepropertyallowsustocomputethenewposteriorprob-abilitydistributionovertheclassvariablefromthepreviousonewithoutperforminganyadditionalnetworkpropagations.
Example5.
WeconsideragainthenaiveBayesiannetworkandtheassociatedpatientinformationfromthepreviousexamples.
Supposethat,inadditiontothediagnosticteststowhichthepatienthasalreadybeen410S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416subjected,aCTscanoftheupperabdomencanbeperformedtoestablishthepresenceofmetastasesintheliver.
ThenetworkincludesthefollowingparameterprobabilitiesforthefeaturevariableCT-liver:hCT-liverjSIIIAIIBIIIIVAIVBCT-liveryes0.
050.
050.
050.
050.
050.
69no0.
950.
950.
950.
950.
950.
31Fordecidingwhetherornottoperformthescan,wewouldliketoknowthepossibleimpactofthetestresultontheposteriorprobabilitydistributionoverthevariousstagescomputedforourpatient,thatis,weareinterestedintheposteriordistributionsgivenanadditionalpositiveresultandgivenanadditionalnegativeresultfromthescan.
FromtheparameterprobabilitiesmentionedaboveandtheoriginalposteriorprobabilitydistributionPrSjefromExample1,wecomputetheprobabilityofapositivetestresulttobePSPrCT-liveryesjSPrSje0:12.
Werecallthatforourpatient,theoriginalprobabilityofstageIVBwascomputedtobe0.
11.
Givenanadditionalpositiveresultfromthescan,thenewprobabilityofstageIVBwouldbePrIVBjeN0:690:120:110:63NotethatapositivetestresultfromtheCTscanoftheliverwould,forthispatient,changethemostlikelystagefromIVAtoIVB.
Furthernotethatthenewposteriorprobabilitydistributionoverthevariousstagescanbeestablishedwithoutrequiringanyadditionalcomputationsfromthenetwork.
Similarobservationsholdforcomputingtheimpactofanegativetestresultontheposteriorprobabilitydistribution.
Sofar,weconsideredtheimpactofadditionalevidenceontheposteriorprobabilitydistributionovertheclassvariablecomputedfromanaiveBayesiannetwork.
Wenowturntothesensitivityofthisimpacttoinac-curaciesinthenetwork'sparametersandwritetheaboveprobabilityratioasafunctionofaparameterx:hxPrcjeNPrcjeOxPrcjeNxPrcjeOxTheimpactofinaccuraciesinparametersofalreadyobservedfeaturevariablesontheposteriordistributionovertheclassvariablecanbestudiedwiththesensitivityfunctionsgivenintheprevioussections.
Thesefunc-tions,however,donotprovideforestablishingtheeectofinaccuraciesinparametersofyetunobservedfea-tures.
Focusingonthelatter,wenowobservethat,iftheparameterxpertainstoavariablefromthesetENEOofnewlyobservedfeaturevariables,thenthedenominatorintheaboveformulaisaconstantwithrespecttox.
ThefunctionhxthenjustscalesthesensitivityfunctionfPrcjeNxdescribingtheoutputprob-abilitygivenallavailableevidence.
GiventheposteriorprobabilitydistributionPrCjeOovertheclassvari-ablepriortoobtainingthenewinformation,wecanthereforeimmediatelydeterminethesensitivityoftheimpactoftheadditionalevidencetoparametervariationfromthesensitivityfunctionfPrcjeNx.
NotethatforanaiveBayesiannetworkthelatterfunctionisreadilyestablishedforeachfeatureparameterxoncetheposteriorprobabilitydistributionPrCjeNisavailable.
Example6.
Weconsideragainthepreviousexample.
SupposethatwenowareinterestedintheeectsofinaccuraciesintheparameterprobabilityxhCT-liveryesjIVBofthefeaturevariableCT-liverontheratiooftheposteriorprobabilitiesofstageIVB.
Werecallthatthenewposteriorprobabilityofthisstagegiventheadditionalevidenceofapositivetestresultwouldbe0.
63;theprobabilityofIVBgivenjusttheavailableevidencewas0.
11.
WenowestablishthesensitivityfunctionfPrIVBjeNxx=x0:41andndthathIVBx10:11xx0:41FromExample3wehadthattheprobabilityoftheclassvalueIVBincreasedfrom0.
11to0.
63uponapositiveliverscan,therebybecoming5.
7timesaslikely.
Wecannowinadditionconcludethatiftheparameterxisvaried,theclassvalueIVBcanbecomeatmost6.
4timesaslikelyaswithouttheadditionalevidence.
S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–4164116.
ConcludingobservationsNumerousexperimentshaveshownthatclassiersbuiltonnaiveBayesiannetworksperformquitewell,eveniftheirparameterprobabilitiesareknowntoincludeconsiderableinaccuracies.
Inthispaper,weusedsensitivity-analysistechniquestostudytheeectsoftheseparameterinaccuraciesontheposteriorprobabilitydistributionscomputedfromanaiveBayesiannetwork.
Weshowedthattheindependencepropertiesofsuchanetworkservetohighlyconstrainthefunctionalformoftheassociatedsensitivityfunctions.
Thesefunctions,infact,aredeterminedsolelybytheoriginalvalueoftheparameterunderstudyandtheoriginalposteriorprobabilitydistributionovertheclassvariable,andcanthusbeecientlycomputed,requiringasinglenet-workpropagationonly.
ThepropertiesthatwederivedfromthesensitivityfunctionsfurtherprovidedsomefundamentalcorroborationfortheempiricallyobservedrobustnessofnaiveBayesianclassiersinpractice.
Inourfutureresearch,wewouldliketofurtherunderpintheobservedrobustnessofnaiveBayesianclas-siersbystudyingpropertiesofsensitivity.
Inthispaper,forexample,wehavestudiedtheeectsofvaryingasingleparameterprobabilityonlyonanoutputprobabilityofinterest.
Especiallywhendiscussingthepossibleeectsofinaccuraciesinanetwork'sfeatureparameters,itseemsonlynaturaltoconsidertheeectsofsimul-taneousvariationoftwoormoreparameters.
Ingeneral,then-waysensitivityfunctionsthatdescribesucheectsarefractionsoftwomulti-linearfunctionsintheparametersvaried.
Establishingandanalysingthesefunctionsquicklybecomesinfeasible.
InnaiveBayesiannetworks,however,thesefunctionsmayagainturnouttohaveratherconstrainedforms.
Forexample,onlyfeatureparameterspertainingtothesamevalueoftheclassvariablecaninteractintheireectonthecomputedposteriorprobabilities.
Withoutsuchinter-actioneects,weexpectthatourobservationsconcerningtherobustnessofaclassier'sperformancetoparametervariationcanbegeneralised.
Studyingtheinteractioneectsindetail,moreover,mayresultinaddi-tionalinsightsintheapparentlackofsensitivitytoparameterinaccuracies.
Inthispaper,wefurtherintroducedthenovelnotionofscenariosensitivity,whichdescribestheeectsofparameterinaccuraciesinviewofscenariosofadditionalevidence.
WeshowedthatfornaiveBayesiannetworkssuchscenariosensitivitiescanbereadilyexpressedintermsofthemorestandardsensitivityfunctions.
Morespe-cically,forparametersofnewlyobservedfeaturevariables,thescenariosensitivityfunctionsjustscalewiththestandardones.
Inthenearfuture,wewouldliketostudythepropertiesofscenariosensitivityfunctionsforallclassierparameters,andstudythenotionofscenariosensitivityinBayesiannetworksingeneral.
AppendixAA.
1.
TheproofofProposition1Proof.
Letxhc0beaparameterwithoriginalvaluex0,pertainingtothevaluec0ofclassvariableC.
LetPrcjebeanoutputprobabilityofinterestwithoriginalvaluep0,andletp00betheoriginalvalueofPrc0je.
WebeginbywritingthemarginalprobabilityPrc;easafunctionoftheparameterxhc0ofthenetwork'sclassvariable.
Usingthedenitionofconditionalprobability,wehavethatPrc;ePrejchcIfcistheclassvaluewhoseparameterprobabilityisbeingvaried,thatis,ifcc0,thenPrc;erelatesdirectlytotheparameterxhc0inthesensethatPrc;exPrejcx.
Ifc6c0,ontheotherhand,wehavethattheconditionalprobabilityintheexpressionaboveco-varieswiththeparameterx.
Wethenndthatthemar-ginalprobabilityPrc;erelatestoxasPrc;exPrejchc1x1x0WethusndthatthemarginalprobabilityPrc;ecanbeexpressedintermsoftheparameterxhc0asPrc;exPrejc0xifcc0Prejchc1x0xPrejchc1x0otherwise8:Similarly,usingthedenitionofmarginalisation,theprobabilityPrecanbewrittenasPrexPrc0;exXc6c0Prc;ewherethemarginalprobabilityPrc0;erelatestotheparameterxasindicatedaboveandthesumPc6c0Prc;eisconstantwithrespecttox.
Notethattheparametershevjc0forev6e0v,whichco-varywithx,arenopartoftheaboveexpressionsincesuchvaluesevdonotoccurintheinputinstancee,asaresultofourassumptioneve0v.
414S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416Wedenethefollowingconstants:aYEi2EnfEvgheijc0hc0Prc0;ex0bYEi2EheijchchXc6c0Prc;ePrePrc0;eFortheclassvaluecc0wenowndforthesensitivityfunctionfPrc0jexthatfPrc0jexPrc0;exPrexaxaxhxxsandfortheclassvaluec6c0wendthatfPrcjexfPrc;exfPrexbaxhrxswheretheconstantsh=adenestheverticalasymptotethatissharedbythefunctionsfPrc0jexandfPrcjex,c6c0;itsvalueequalssx0PrePrc0;ePrc0;ex01PrePrc0;ex0x0p00Theconstantrb=aofthefunctionfPrcjexwithc6c0nowdirectlyfollowsfromfcx0p0r=x0s.
Finally,thefunctionfPrc0jexhasahorizontalasymptotedenedbyta=a1.
ThefunctionfPrcjexwithc6c0hast0=a0.
Thepropositionsummarisestheseproperties.
hA.
4.
TheproofofProposition4Proof.
LetEvbeafeaturevariablewithvalueevininstancee.
Letxhe0vjc0beaparameterwithoriginalvaluex0,pertainingtothevaluee0vofEvandtheclassvaluec0.
Letp00betheoriginalvalueofPrc0je;inaddition,letpT0argmaxc6c0fPrcjegandletcTbeavalueofCforwhichPrcTjepT0.
TherstpropertystatedinthepropositionfollowsfromtheobservationthatallfunctionsfPrcjewithc6c0havethesamehorizontalandverticalasymptotesandthereforedonotintersect.
Asaconsequence,eitherc0orcTisthemostlikelyvalueofC,regardlessofthevalueofx.
Fortheadmissibledeviationfortheparameterhe0vjc0,weconsiderthevaluexmatwhichthetwofunctionsfPrc0jexandfPrcTjexintersect.
Weestablishthisvalueforthesituationwhereeve0v;forev6e0vtheproofisanalogous.
Foreve0vwendthatfPrc0jexfPrcTjex()xxspT0x0sxs()xpT0x0sSubstitutingsintheaboveformulawithitsvaluex0x0=p00resultsinxmpT0x0=p0020;1i.
Notethattheintersectionofthetwofunctionslieswithintheunit-windowifxmxm.
Theadmissibledeviationsgiveneve0vnowfollowimmediatelyfromthefunctionalforms.
hReferences[1]E.
Castillo,J.
M.
Gutierrez,A.
S.
Hadi,SensitivityanalysisindiscreteBayesiannetworks,IEEETransactionsonSystems,Man,andCybernetics27(1997)412–423.
[2]H.
Chan,A.
Darwiche,Adistancemeasureforboundingprobabilisticbeliefchange,in:R.
Dechter,M.
Kearns,R.
S.
Sutton(Eds.
),Proceedingsofthe18thNationalConferenceonArticialIntelligence,AAAIPress,2002,pp.
539–545.
S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416415[3]H.
Chan,A.
Darwiche,ReasoningaboutBayesiannetworkclassiers,in:C.
Meek,U.
Kjrul(Eds.
),Proceedingsofthe19thConferenceonUncertaintyinArticialIntelligence,MorganKaufmann,2003,pp.
107–115.
[4]V.
M.
H.
Coupe,L.
C.
vanderGaag,PropertiesofsensitivityanalysisofBayesianbeliefnetworks,AnnalsofMathematicsandArticialIntelligence36(2002)323–356.
[5]P.
Domingos,M.
Pazzani,OntheoptimalityofthesimpleBayesianclassierunderzero-oneloss,MachineLearning29(1997)103–130.
[6]F.
V.
Jensen,BayesianNetworksandDecisionGraphs,Springer-Verlag,2001.
[7]U.
Kjrul,L.
C.
vanderGaag,Makingsensitivityanalysiscomputationallyecient,in:C.
Boutilier,M.
Goldszmidt(Eds.
),Proceedingsofthe16thConferenceonUncertaintyinArticialIntelligence,MorganKaufmann,2000,pp.
317–325.
[8]K.
B.
Laskey,SensitivityanalysisforprobabilityassessmentsinBayesiannetworks,IEEETransactionsonSystems,Man,andCybernetics25(1995)901–909.
[9]P.
Liu,L.
Lei,N.
Wu,Aquantitativestudyoftheeectofmissingdatainclassiers,in:N.
Gu,D.
Wei,Z.
Xie,H.
Wang,S.
X.
Wang,B.
Shi(Eds.
),IEEEProceedingsofthe5thInternationalConferenceonComputerandInformationTechnology,2005,pp.
28–33.
[10]J.
Pearl,ProbabilisticReasoninginIntelligentSystems,MorganKaufmann,1988.
[11]S.
Renooij,L.
C.
vanderGaag,Evidence-invariantsensitivitybounds,in:M.
Chickering,J.
Halpern(Eds.
),Proceedingsofthe20thConferenceonUncertaintyinArticialIntelligence,AUAIPress,2004,pp.
479–486.
[12]I.
Rish,AnempiricalstudyofthenaiveBayesclassier,in:IJCAIWorkshoponEmpiricalMethodsinArticialIntelligence,2001,pp.
41–46.
[13]L.
C.
vanderGaag,S.
Renooij,Analysingsensitivitydatafromprobabilisticnetworks,in:J.
S.
Breese,D.
Koller(Eds.
),Proceedingsofthe17thConferenceonUncertaintyinArticialIntelligence,MorganKaufmann,2001,pp.
530–537.
[14]L.
C.
vanderGaag,S.
Renooij,Onthesensitivityofprobabilisticnetworkstoreliabilitycharacteristics,ModernInformationProcessing:FromTheorytoApplications,Elsevier,2006,pp.
385–405.
416S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416
vanderGaagDepartmentofInformationandComputingSciences,UtrechtUniversity,P.
O.
Box80.
089,3508TBUtrecht,TheNetherlandsAvailableonline29February2008AbstractEmpiricalevidenceshowsthatnaiveBayesianclassiersperformquitewellcomparedtomoresophisticatedclassiers,eveninviewofinaccuraciesintheirparameters.
Inthispaper,westudytheeectsofsuchparameterinaccuraciesbyinves-tigatingthesensitivityfunctionsofanaiveBayesiannetwork.
Weshowthat,asaconsequenceofthenetwork'sindepen-denceproperties,thesesensitivityfunctionsarehighlyconstrained.
WefurtherinvestigatewhetherthepatternsofsensitivitythatfollowfromthesefunctionssupporttheobservedrobustnessofnaiveBayesianclassiers.
Inadditiontostandardsensitivitiesgivenavailableevidence,wealsostudytheeectofparameterinaccuraciesinviewofscenariosofadditionalevidence.
Weshowthatstandardsensitivityfunctionssucetodescribesuchscenariosensitivities.
2008ElsevierInc.
Allrightsreserved.
Keywords:NaiveBayesianclassiers;Sensitivity;Robustness1.
IntroductionBayesiannetworksareoftenemployedforclassicationpurposeswhereaninputinstancedescribedintermsofobservablefeaturevariables,istobeassignedtooneofanumberofpossibleoutputclasses.
TheBayesiannetworkforthispurposecomputes,giventheinstance,theposteriorprobabilitydistributionoverthevariablemodellingtheseclasses.
Theactualclassierthenisafunctionthatassignsasingleclasstotheinstance,basedonthecomputedposteriordistribution.
SuchclassiersareoftenbuiltuponanaiveBayesiannetwork,consistingofasingleclassvariableandanumberoffeaturevariables,whicharemodelledasbeingmutuallyindependentgiventheclassvariable.
Theparameterprobabilitiesforsuchanetworkaregenerallyestimatedfromdataandinevitablyareinaccurate.
Experimentshaveshown,timeandagain,thatclassiersbuiltonnaiveBayesiannetworksarecompetitivewithother,oftenmoresophisticatedclassicationmodels,regardlessofthesizeandqualityofthedatasetfromwhichtheyarelearned,e.
g.
[5,9,12].
VariousaspectsofthenaiveBayesianclassierhavebeenstudiedinattemptstoexplainthesendings.
Forbinaryclassvariables,forexample,itwasshownthatthecommonlyusedwinner-takes-allrule,whichassignsaninstancetoaclasswithhighestposteriorprobabilityaccordingtotheunderlyingBayesiannetwork,contributestothenaiveclassier'ssuccess[5].
Theobservedrobustnesswas0888-613X/$-seefrontmatter2008ElsevierInc.
Allrightsreserved.
doi:10.
1016/j.
ijar.
2008.
02.
008*Correspondingauthor.
E-mailaddresses:silja@cs.
uu.
nl(S.
Renooij),linda@cs.
uu.
nl(L.
C.
vanderGaag).
Availableonlineatwww.
sciencedirect.
comInternationalJournalofApproximateReasoning49(2008)398–416www.
elsevier.
com/locate/ijaralsoattributedtotheindependencepropertiesoftheclassier.
Itwasshown,forexample,thatnaiveBayesianclassiersperformwellnotonlyforcompletelyindependentfeaturevariables,butalsoforfunctionallydepen-dentones[5,12].
WenotethatmostofthefavourableexperimentalreportsonnaiveBayesianclassiersarebasedontheassumptionofabinaryclassvariablewitharatheruniformpriorprobabilitydistributionoveritsvalues.
Inthispaper,wefollowupontheobservationthat,apparently,inaccuraciesintheparameterprobabilitiesoftheunderlyingnaiveBayesiannetworkdonotsignicantlyaecttheperformanceoftheclassier.
Weemploysensitivity-analysistechniquestostudytheeectsofparametervariationontheposteriorprobabilitydistributionscomputedfromanaiveBayesiannetwork,andtherebycontributefurthercorroborationfortheobservedrobustnessofthistypeofclassier.
WewouldliketonotethatsensitivityanalysishasbeenappliedbeforeinthecontextofnaiveBayesianclassiers,asameansofprovidingboundsontheamountofparametervariationthatisallowedwithoutchanging,foranyofthepossibleinputinstances,themostlikelyvalueofabinaryclassvariable[3].
Theseboundsareusefulforestablishingwhichparameteruponvariationcanneverchangetheclassier'soutput,regardlessoftheenteredevidence.
Thecomputationofthesebounds,however,requireseitherexplicitenumerationoverallpossibleinstancesoraconversionofthenaiveBayesianclassierintoanordereddecisiondiagram.
WeextendontheseearlierresultsbystudyingthemathematicalfunctionsthatdescribethesensitivityofaposteriorprobabilityofinterestcomputedfromthenaiveBayesiannetwork,tovariationofaparameter'svalue;thesefunctionsaretermedsensitivityfunctions[1,4].
WeshowthattheindependenceassumptionsunderlyinganaiveBayesiannetworkconstrainthesesensitivityfunctionstosuchanextentthattheycanbeestablishedexactlyfromverylimitedinformationfromthenetworkathand.
Inaddition,westudythesensitivitypropertiesthatfollowfromtheconstrainedfunctionsandarguehowthesepropertiessupporttheobservedrobustnessofnaiveBayesianclassiers.
Inthispaper,wealsointroducethenovelnotionofscenariosensitivity,whichweuseforfurtherstudyingaclassier'srobustness.
Forclassicationproblems,itisoftenassumedthatevidenceisavailableforeverysinglefeaturevariable.
Innumerousapplicationdomains,however,thisassumptionmaynotberealistic,especiallynotfordomainsinwhichevidenceisgatheredselectivelyinastepwisemanner.
Thequestionthenariseshowmuchimpactfurtherevidencecouldhaveonthecomputedposteriorprobabilitydistributionsandhowsen-sitivethisimpactistoinaccuraciesinthenetwork'sparameters.
Weintroducethenotionofscenariosensitiv-itytocapturethelattertypeofsensitivityandshowthattheeectsofparametervariationinviewofscenariosofadditionalevidencecanbeestablishedecientlyfornaiveBayesiannetworks.
Thepaperisorganisedasfollows.
InSection2,wepresentsomepreliminariesonsensitivityfunctionsandtheirassociatedsensitivityproperties.
InSection3,weestablishthefunctionalformofthesensitivityfunctionsforanaiveBayesiannetworkintermsofvariationoftheparameterprobabilitiesoftheclassvariable,andaddresstheensuingsensitivityproperties.
Section4addressesthesensitivityfunctionsandassociatedproper-tiesthatresultfromvariationoftheparameterprobabilitiesofthefeaturevariables.
InSection5weintroducethenotionofscenariosensitivityandshowthatitcanbeestablishedfromstandardsensitivityfunctions.
ThepaperendswithourconcludingobservationsinSection6.
2.
PreliminariesandnotationABayesiannetworkessentiallyisacompactrepresentationofajointprobabilitydistributionProverasetofstochasticvariablesV[10].
Thevariablesandtheirinterrelationshipsarecapturedasnodesandarcs,respec-tively,inanacyclicdirectedgraphG.
AssociatedwitheachnodeinthegraphisasetofparameterprobabilitieshVjpVthatcapturethestrengthoftherelationshipbetweenavariableVanditsparentspV.
FromaBayesiannetwork,anypriororposteriorprobabilityofinterestoveritsvariablescanbecomputed.
Inthispaper,wefocusmorespecicallyonnaiveBayesiannetworks,inwhichthedigraphmodellingtheinterrelation-shipsbetweenthevariableshasarestrictedtopology.
ThedigraphofsuchanetworkiscomposedofnodesfCg[EwithEfE1;Eng,nP2,andarcsC;Eiforalli1;n;thevariableCiscalledtheclassvariableandthevariablesEiaretermedfeaturevariables.
TherestrictedtopologyofthedigraphofanaiveBayesiannetworkcapturesconditionalindependenceofanytwofeaturevariablesgiventheclassvariable.
AlthoughanyprobabilitycanbecomputedfromanaiveBayesiannetwork,theposteriorprobabilitiesofthevariousclassvaluesareofprimaryinterest.
ThenetworkfurtherisassociatedwithaclassicationfunctionS.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416399which,basedupontheseposteriorprobabilities,returnsasinglemostlikelyclassvalue,breakingtiesatrandom.
TheparameterprobabilitiesofaBayesiannetworkareeitherestimatedfromdataorassessedbydomainexperts,andinevitablyincludesomeinaccuracies.
Toinvestigatetheeectsoftheseinaccuraciesonthecom-putedposteriorprobabilities,aBayesiannetworkcanbesubjectedtoasensitivityanalysis.
Insuchananalysis,oneormorenetworkparametersarevariedsystematicallyandtheeectsofthisvariationonanoutputprob-abilityofinterestarestudied.
Inthispaper,wefocusprimarilyonsensitivityanalysesinwhichjustoneparam-eterisbeingvaried;suchananalysisistermedaone-waysensitivityanalysis.
Theeectsoftheparametervariationarecapturedbyasimplemathematicalfunction,calledasensitivityfunction.
Beforereviewingthefunctionalformofsuchasensitivityfunction,weobservethatuponvaryingaparticularparameterprobabil-ity,theparameterspertainingtothesameconditionaldistributionshouldbeco-variedtoensurethattheirsumremainsone.
Thewell-knownschemeofproportionalco-variationisoftenusedforthispurpose1asithasbeenshowntoresultinthesmallestchangeintheoutputdistribution[2].
Underthisscheme,anyone-waysensi-tivityfunctionisaquotientoftwolinearfunctionsintheparameterunderstudy[1,4].
Moreformally,uponvaryingasingleparameterprobabilityx,thefunctionfPrcjexthatexpressestheoutputprobabilityofinterestPrcjeintermsofxtakestheformfPrcjexfPrc;exfPrexaxbgxhwheretheconstantsa;b;g;harebuiltfromthenon-variedparametersfromthenetworkunderstudy.
Thefourconstantsarederivedanalyticallyin[4];feasiblealgorithmsfortheircomputationareavailablefrom[4,7].
Inthesequel,insteadoffPrcjexwewilloftenwritefcxorfxforshort,aslongasnoconfusionispossible.
Inouranalyses,wefurtherassumethatparameterswithanoriginalassessmentof0or1arenotvaried,sincetheseparametersrepresentlogicalconsequencesorimpossibilitiesandthereforedonotincludeanyinaccuracies.
Aone-waysensitivityfunctionfxcantakeoneofthreegeneralforms.
Thefunctionislineariftheprob-abilityofinterestisapriorprobabilityratherthanaposteriorprobability,oriftheprobabilityoftheenteredevidenceisunaectedbytheparametervariation;notethatinthelattercasewehavethatPreisaconstantandhenceg0.
IftheprobabilityPreoftheevidenceequals0wheneverx0,inwhichcasewehavethath0,thenitisreadilyshownthatthesamemustholdforthemarginalprobabilityPrc;e,thatis,wemusthavethatb0;thesensitivityfunctionthenreducestoaconstant.
Inallothercasesthesensitivityfunctionisafragmentofarectangularhyperbola,whichtakesthegeneralformfxrxsttxrstxs;withshg;tag;andrbgstwiththeconstantsa;b;g;hasabove.
Intheremainderofthepaper,wefocusonthislasttypeoffunctionandassumeanysensitivityfunctiontobehyperbolicunlessexplicitlystatedotherwise.
Arectangularhyper-bolaingeneralhastwobranchesandtwoasymptotesdeningitscenters;t;Fig.
1illustratesthelocationsofthepossiblebranchesrelativetotheasymptotes.
Weobservethatasensitivityfunctionisdenedby06x;fx61;thetwo-dimensionalspaceoffeasiblepointsthusdened,istermedtheunitwindow.
Sinceasensitivityfunctionmoreovershouldbecontinuousforx20;1,itsverticalasymptotenecessarilyliesout-sidetheunitwindow,thatis,eithers1.
FromtheseobservationsweconcludethatahyperbolicsensitivityfunctionisafragmentofjustoneofthefourpossiblebranchesshowninFig.
1.
Fromasensitivityfunction,variouspropertiescanbecomputedthatservetosummarisetheeectsofparametervariation.
Herewebrieyreviewthepropertiesofsensitivityvalue[8]andofadmissibledeviation[13].
Thesensitivityvalueforaparameterxistheabsolutevaluejof=oxx0joftherstderivativeofthesen-sitivityfunctionfxattheparameter'soriginalvaluex0.
Itdescribestheeectofaninnitesimallysmallshiftintheparameterontheoutputprobabilityofinterest.
Inessence,thelargerthesensitivityvalueforaparam-eteris,thelessrobusttheoutputprobabilityofinterestwillbetoinaccuraciesintheparameter.
Wewouldlike1Whenaparameterprobabilityhisvariedfromthevalueholdtothevaluehnew,eachparameterh06hfromthesamedistributionisvariedfromh0oldtoh0new,whereh0newh0old1hnew1hold.
400S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416tonotethattheimpactofalargershiftinaparameter'svalueisstronglydependentuponthelocationofthevertexofthesensitivityfunction,thatis,ofthepointwherejof=oxxj1.
Thevertexcanliewithintheunitwindow,ortoitsleftorright.
Avertexthatlieswithintheunitwindowbasicallymarksthetransitionfromparametervalueswithalargesensitivityvaluetoparametervalueswithasmallsensitivityvalue,orviceversa.
Aparameterwithasmallsensitivityvaluecanthushavelargereectsthanitssensitivityvaluesuggests,ifitliesintheproximityofthevertex,thatis,ifitsoriginalvaluex0isclosetothevertex'x-value.
IftheposteriorprobabilitiescomputedfromaBayesiannetworkareusedforestablishingthemostlikelyvalueofanoutputvariable,itistheeectofparametervariationontheoutputvaluethatisofinterest.
Foraparameterwithanoriginalvalueofx0,theadmissibledeviationisapaira;b,whereaistheamountofvariationallowedtoval-uessmallerthanx0withoutchangingthemostlikelyoutputvalueandbistheamountofvariationallowedtolargervalues;thesymbolsand!
areusedtoindicatethatvariationisallowedtotheboundariesoftheunitwindow.
Thelargertheadmissibledeviationforaparameteris,therefore,themorerobusttheoutputvaluewillbetoinaccuraciesinthisparameter.
3.
SensitivitytoclassparametersUponbeingsubjectedtoasensitivityanalysis,theindependencepropertiesofanaiveBayesiannetworkstronglyconstrainthegeneralformoftheresultingsensitivityfunctions.
Infact,givenjustlimitedinformationfromthenetwork,theexactfunctionscanbereadilyestablishedforeachclassvalueandeachparameterprob-ability.
Inthissectionwederivethesensitivityfunctionsthatdescribeanoutputprobabilityofinterestasafunctionofaparameterfortheclassvariable.
Wedetailthesensitivitypropertiesthatfollowfromthesefunc-tionsanddiscusstheirpossibleeectsontherobustnessofnaiveBayesianclassiers.
InSection4,wewilladdressthesensitivityfunctionsforparametersforthefeaturevariablesinasimilarfashion.
3.
1.
FunctionalformsThefollowingpropositionstatesthefunctionalformofany(hyperbolic)sensitivityfunctionthatdescribesanoutputprobabilityofanaiveBayesiannetworkintermsofasingleparameterxhc0,associatedwithaspecicvaluec0oftheclassvariableC.
Thepropositionmorespecicallyshowsthatsuchafunctionishighlyconstrainedandcaninfacttakeonlyoneoftwoforms.
Proofsofthisandsubsequentpropositionsarepre-sentedinAppendixA.
Proposition1.
Letxhc0beaparameterprobabilitypertainingtothevaluec0oftheclassvariableC,andletx0beitsoriginalvalue.
LetPrcjebeanoutputprobabilityofinterestwiththeoriginalvaluep0,andletp00betheoriginalvalueofPrc0je.
Then,thesensitivityfunctionfPrcjexhasthefollowingform:√|2r|center(s,t)vertexr1t≤1r0s0s>1t≥0IIVIIIIIFig.
1.
TworectangularhyperbolaswithbranchesintheIstandIIIrdquadrantsrelativetothehyperbola'scenter,andintheIIndandIVthquadrants,respectively;theconstraintsontheconstantsr,sandtarespecicforsensitivityfunctions.
S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416401fPrcjex1sxxsifcc0p01p00sx1xsotherwise8>:inwhichthevalues,deningthefunction'sverticalasymptote,equalss1p00x0x0p00Thevaluet,deningthehorizontalasymptoteofthesensitivityfunction,equalst1sifcc0p01p00sotherwise(WenotethattheabovepropositionpertainstoasingleoutputprobabilityofinterestPrcje.
Sincethechoiceofclassvaluec,however,isarbitrary,thepropositionholdsforanyvalueofC.
Theoriginalvaluep0oftheoutputprobabilityofinterestobviouslydependsonthevalueofcunderconsiderationand,asaresult,sodoestheactualvalueofthehorizontalasymptotet.
Fromtheaboveproposition,weobservethatthesensitivityfunctionfPrc0jexpertainingtotheclassvaluewhoseparameterprobabilityisbeingvaried,includesthepointsfc000andfc011fromtheunitwindow;thefunctionthusisafragmentofeitheraIInd-quadrantoraIVth-quadranthyperbolabranch.
ThesensitivityfunctionsfPrcjex,c6c0,pertainingtotheothervaluesoftheclassvariablethenarefragmentsofeitherIst-orIIIrd-quadranthyperbolabranches.
Fig.
2illustratesthetwopossiblesituations.
ThesensitivityfunctionfPrc0jexbeingaIInd-quadrantfunctioncorrespondswithaverticalasymptotetotherightoftheunitwindow,thatis,withs>1andhencewithx0>p00;thesensitivityfunctionspertainingtotheothervaluesofCthenareIIIrd-quadrantfunctions.
TheIVth-andIst-quadrantcombinationoffunctionscorrespondswithx0>>:wherep0againistheoriginalvalueofPrcjeandp00istheoriginalvalueofPrc0je;x0istheparameter'sori-ginalvalueasbefore.
From1p00Pp0foranyvaluecoftheclassvariable,weobservethatthehighestsen-sitivityvaluefortheparameterxisobtainedwhentheoutputprobabilityofinterestpertainstotheclassvaluec0whoseparameterisbeingvaried.
Thesensitivityvaluefoundtheninfactmatchestheupperboundonsen-sitivityvaluesforsensitivityfunctionsingeneral[11].
Notethatforabinaryclassvariable,wewouldhavethat1p00p0andthesensitivityvaluesforthetwoclassvalueswouldbethesame.
Thesensitivityvaluescom-putedfromthefunctionfPrc0jexfordierentcombinationsofvaluesforx0andp00aredepictedinFig.
3.
Thegureshowsthatlargesensitivityvaluescanbefoundonlyforratherextremeparametervaluesincombina-S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416403tionwithlessextremeoutputprobabilities.
Wefurtherrecallthat,despitetheirsmallsensitivityvalues,alsoparameterswithanoriginalvalueclosetothex-valueofthesensitivityfunction'svertexmayshowsignicanteectsuponvariation.
Forclassparameters,thesensitivityfunctionfPrc0jexalwayshasitsvertexwithintheunitwindow;thevertexinfactliesonthelinex1fx.
Iftheverticalasymptoteofthesensitivityfunctionliesquiteclosetotheunitwindowandthevertexinadditionisnottoofarfromtheasymptote,thenaparam-eterwithanoriginalvalueintheproximityofthevertexwillshowconsiderableimpactontheoutputprob-abilityifitisvariedfurthertothenearbyextreme.
Fromtheaboveconsiderations,wehavethatinnaiveBayesiannetworkstheoutputprobabilityofinterestwillbesensitivetovariationinaclassparameteronlyiftheclassvalueunderconsiderationeitheroccursratherseldomlyorquitefrequentlyinthedomainofapplicationandtheinstanceathanddoesnotsupportthe(un)likelihoodofthisclassvalue.
AslongastheclassparametersofanaiveBayesiannetworkarenothighlyunbalanced,therefore,willtheprobabilitywithwhichaninstanceispredictedtobelongtoaparticularclassbequiteinsensitivetoparametervariation.
WenotethatitisnotuncommontondclassvariableswithsuchdistributionsinthedomainsinwhichnaiveBayesianclassiersarebeingapplied.
Yet,alsotheoutputprobabilitiescomputedfromanaiveBayesiannetworkinwhichoneormoreclassvalueshaverathersmallpriorprobabilities,willbequiterobustaslongastheposteriorprobabilitiescomputedfortheseclassesarequiteextremeforallpossibleinstances.
3.
2.
2.
AdmissibledeviationInviewofestablishingthemostlikelyclassvalueforaninstance,thepropertyofadmissibledeviationisofinterest.
Werecallthattheadmissibledeviationforaparametergivestheamountofvariationthatisallowedinitsoriginalvaluebeforethemostlikelyclassvaluechanges.
ThefollowingpropositiongivestheadmissibledeviationforaclassparameterinanaiveBayesiannetwork.
Thepropositionmorespecicallyshowsthatthemostlikelyclassvaluechangesexactlyonceuponvaryingsuchaparameter.
Proposition2.
Letxhc0beaparameterprobabilitypertainingtothevaluec0oftheclassvariableC,andletx0beitsoriginalvalue.
Letp00betheoriginalvalueofPrc0je,letpT0argmaxc6c0fPrcjeg,andletcTbeavalueofCforwhichPrcTjepT0.
Then,fPrcjex6fPrcTjexforallc6c0Furthermore,theadmissibledeviationforxisa;bx0xm;!
ifpT0p000;!
or;0otherwise8>:wherexmpT0x01x0p00pT0x000.
20.
40.
60.
81x000.
20.
40.
60.
81p'000.
511.
522.
53|dfc'/dx(x0)|Fig.
3.
Thesensitivityvalueforaclassparameterxhc0andsensitivityfunctionfPrc0jex,asafunctionoftheoriginalparametervaluex0andtheoriginalposteriorp00.
404S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416Fromtheaboveproposition,weobservethatanyclassparametercanbevariedtotheboundaryoftheunitwindowinoneofthetwopossibledirectionswithoutchangingthemostlikelyclassvalue,asindicatedbytheand!
symbols.
Uponvaryinganysuchparameterintheotherdirection,themostlikelyclassvaluechangesexactlyonce.
NotethatFig.
2supportstheseobservations.
ForthecasewherepT0p00,wenotethat,giventheoriginalvaluex0oftheparameterunderstudy,thetwoclassvaluesc0andcTareequallylikely.
Theboundarytowhichtheparametercanbevariedwithoutinducingachangethendependsonwhichofthetwoclassvaluesisdesignatedtheuniquemostlikelyclassbythenetwork'sassociatedclassicationfunction.
WefurtherobservethatthesmallerthedierenceisbetweenthetwoposteriorprobabilitiespT0andp00,thesmallertheadmissibledeviationfortheparameterisandthelessrobusttheclassvaluereturnedbytheclassierwillbe.
Asaspecialcaseoftheaboveproposition,weconsiderauniformlydistributedbinaryclassvariable,thatis,weconsiderthecasewherex00:5andpT01p00;notethatinthiscasewendforthevaluexmatwhichthetwosensitivityfunctionsintersect,thatxm1p00.
Theadmissibledeviationfortheclassparameterxhc0thenequalsp000:5;!
ifpT0p00,thatis,iftheinstancepointstotheothervalueoftheclassvariable.
Wenotethatthemoreextremetheoriginalvaluep00ofthepos-teriorprobabilityofinterestis,thelargertheadmissibledeviationwillbeandthelessimpactvariationofaclassparametercanhaveonthemostlikelyclassvalue.
Furthernotethatfornon-binaryclassvariables,thevalueofxmintheadmissibledeviationmaybelessextreme,whichmayresultinsmalleradmissibledevi-ationsandalessrobustoutputclass.
Example2.
WeconsideragainthenaiveBayesiannetworkandtheassociatedpatientinformationfromExample1.
SupposethatweareinterestedintheeectsofinaccuraciesintheparameterprobabilityxhSIVA,withanoriginalvalueofx00:10,onthemostlikelyclassvalueestablishedforourpatient.
Werecallthat,withtheparameter'soriginalvalue,stageIVAisthemostlikelystageforthepatient,withaprobabilityof0.
61;thesecondmostlikelystageisstageIIA,withaprobabilityof0.
19.
Usingtheseprobabilities,wendforthevaluexmfromProposition2thatxm0:190:10=0:900:610:190:100:03.
Theadmissibledeviationfortheparameterunderstudythusis0:07;!
.
Thisadmissibledeviationindicatesthattheparametercanbevariedfrom0.
10to1.
00withoutinducingachangeinthemostlikelystageforthepatient.
Theparametercanalsobevariedtosmallervalues,butthemostlikelystagewillchangefromIVAtoIIAiftheparameteradoptsavaluesmallerthan0.
03.
Notethatthemostlikelystagecannotchangeintoanyothervalueuponvaryingtheparameter.
Furthernotethat,althoughinabsolutetermsonlyasmallshiftisallowedtosmallerparametervalues,theadmissibledeviationisquitelargerelativetotheparameter'soriginalvalue.
Nowsupposethatweweretouseatwo-valuedratherthanasix-valuedvariableclassvariable.
WedeneforthispurposethenewvariableOperable,ofwhichthevalue'yes'coincideswithstagesI,IIAandIIB,andthevalue'no'capturesthestagesIII,IVAandIVB.
Giventhepatient'savailableinformation,theposteriorsPrOperableyesje0:21andPrOperablenoje0:79arecomputed;thevalue'no'thusisthemostlikelyclassvalueforthepatient.
SupposethatweareinterestedintheeectsofinaccuraciesintheparameterxhOperableno,withanoriginalvalueofx00:61,onthemostlikelyvalueoftheoutputvariable.
Wendthatthesensitivityfunctionsassociatedwiththetwovaluesoftheclassvariableintersectatxm0:29.
Theadmissibledeviationforparameterxthusequals0:32;!
.
Thisadmissibledeviationindicatesthattheparametercanbevariedfrom0.
61to1.
00withoutinducingachangeinthemostlikelyclassvalue.
Theparametercanalsobevariedtovaluessmallerthan0.
61,butthemostlikelyvaluewillchangefrom'no'to'yes'iftheparameteradoptsavaluesmallerthan0.
29.
Notethattheparametercanthusbevariedtoapproximatelyhalfitsoriginalvalue.
Fromtheaboveconsiderations,weconcludethatthemostlikelyclassvalueestablishedfromanaiveBayes-iannetworkwillbequitesensitivetoinaccuraciesinthenetwork'sclassparametersiftheoutputprobabilitiesfortheclassvariablearemoreorlessuniformlydistributed.
Morespecically,themostlikelyclassvaluewillnotbeveryrobusttovariationintheclassparametersifithasapproximatelythesameposteriorprob-abilityastherunner-upvalue.
TheclassicationperformanceofanaiveBayesianclassierwillthusbequiterobustifthemajorityofpresentedinstancesresultinasingleratherlikelyclassvalue.
Infact,itwillberobustaslongasthemajorityofinstancesbelongtotheapriorimostlikelyclass,whichwewouldexpectiftheclas-sierissucientlytailoredtothedomainofapplication.
S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–4164054.
SensitivitytofeatureparametersInthissectionwederiveforanaiveBayesiannetworkthesensitivityfunctionsthatdescribeanoutputprobabilityofinterestasafunctionofaparameterforafeaturevariable.
Weshowthatalsoforfeatureparameterstheexactsensitivityfunctionscanbereadilyestablishedgivenjustlimitedinformationfromthenetwork.
WefurtherdetailthesensitivitypropertiesfollowingfromthefunctionsanddiscusstheirpossibleeectsontherobustnessofnaiveBayesianclassiers.
4.
1.
FunctionalformsThefollowingpropositionstatesthefunctionalformofany(hyperbolic)sensitivityfunctionthatdescribesanoutputprobabilityofanaiveBayesiannetworkintermsofasinglefeatureparameterxhe0vjc0,wheree0vdenotesavalueofthefeaturevariableEvandc0isavalueoftheclassvariable.
Thepropositionshowsthatthefunctionagainishighlyconstrained;infact,foranyclassvalueandanyfeatureparameter,onlyoneoffourfunctionalformscanresult.
Proposition3.
LetEvbeafeaturevariableandletevbeitsvalueintheinstancee.
Letxhe0vjc0beaparameterprobabilitypertainingtothevaluee0vofEvandtheclassvaluec0,andletx0beitsoriginalvalue.
LetPrcjebeanoutputprobabilityofinterestwiththeoriginalvaluep0,andletp00betheoriginalvalueofPrc0je.
Then,thesensitivityfunctionfPrcjexhasoneofthefollowingforms:fPrcjexxxsifcc0andeve0vx1xsifcc0andev6e0vp0x0sxsotherwise8>>>:inwhichthevalues,deningthefunction'sverticalasymptote,equalssx0x0p00ifeve0vx01x0p00otherwise8>:Thevaluet,deningthehorizontalasymptoteofthesensitivityfunction,ist1ifcc00otherwiseWeconsideragainthepossiblelocationsofthesensitivityfunctionsforafeatureparameterunderstudy.
Forthecasewhereeve0v,wendforthevaluesx0x0=p00oftheverticalasymptotethats1;wethenndIIIrd-andIInd-quadrantbranches,respectively.
Fig.
4illustratesthetwopossiblesituations.
TointuitivelyexplainwhythefunctionfPrc0jexagainhasadif-ferentshapefromtheotherfunctions,weobservethatvaryingafeatureparameterheijc0givenaparticularvaluec0oftheclassvariablehasadirecteectontheposteriorprobabilityPrc0jeofthisclassvaluec0only;theprobabilitiesPrcje,c6c0,fortheothervaluesoftheclassvariableareaectedonlyindirectlytoensurethatthedistributionovertheclassvariablesumstoone.
Fromthehighlyconstrainedformofthefunctions,moreover,wehavethatallfunctionsfPrcjex,c6c0,havethesameshape.
TheshapeofthefunctionfPrc0jexthereforemustbedeviant.
Weagainillustratethefunctionalformofthesensitivityfunctionsderivedabovewithanexample.
Theexampleoncemoredemonstratesthatasaresultoftheirconstrainedform,anysensitivityfunctioncanbeestablishedfromverylimitedinformation.
Example3.
WeagainconsiderthenaiveBayesiannetworkandthepatientinformationfromExample1.
WefurtherconsiderthefeaturevariableCT-loco,modellingthepresenceorabsenceofloco-regionalmetastasesassuggestedbyaCTscanofthepatient'sthorax.
Thenetworkincludesthefollowingparameterprobabilitiesforthisvariable:TheposteriorprobabilitydistributionPrSjecomputedovertheclassvariablegiventheavailablendingsforourpatient,whoshowsnosignsofloco-regionalmetastases,arefoundinExample1.
NowsupposethatweareinterestedintheeectofinaccuraciesintheparameterprobabilityxhCT-loconojSIVAontheseposteriorprobabilities.
Theeectiscapturedbysixsensitivityfunctionswiththesameverticalasymptote,whosevaluesisreadilyestablished:sincetheoriginalvalueoftheparameterequals0.
52andtheoriginalposteriorprobabilityofstageIVAforthepatientis0.
61,wendthats0:520:52=0:610:33.
ThesensitivityfunctionfIVAxthereforeisaIVth-quadranthyperbolabranch;thefunctionsfortheotherstagesareIst-quadrantbranches.
Notethatforthecomplementoftheparameterx,thesixsensitivityfunctionswouldallhavetheirverticalasymptoteats1:33.
Withoutperforminganyfurthercomputations,weestablishthatfIVAxxx0:33andfSxPrSje0:85x0:33foranyS6IVAFromtheaboveconsiderations,wehavethatthesensitivityfunctionsresultingfromaone-wayanalysisforafeatureparameter,arehighlyconstrained.
Justasthesensitivityfunctionsfortheclassparameters,wendthatthefunctionsforthefeatureparametersareexactlydeterminedbytheoriginalvaluesfortheseparametersandtheoriginalposteriorprobabilitydistributionfortheoutputvariableofinterest.
Computingtheexactfunctionsasaconsequenceagainrequiresjustasinglenetworkpropagationtoestablishtheposteriorclassdistribution.
4.
2.
SensitivitypropertiesFromthesensitivityfunctionsderivedabove,anysensitivitypropertypertainingtoanetwork'sfeatureparameterscanbecomputed.
Weagainstudythepropertiesofsensitivityvalueandadmissibledeviation.
4.
2.
1.
SensitivityvalueFromthesensitivityfunctionfPrcjexexpressingtheoutputprobabilityPrcjeintermsofafeatureparameterxhe0vjc0,theassociatedsensitivityvalueisreadilyestablished:iftheobservedinstanceeincludesthevalueeve0v,wendthathCT-locojSIIIAIIBIIIIVAIVBCT-locoyes0.
020.
020.
480.
480.
480.
27no0.
980.
980.
520.
520.
520.
73S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416407ofPrcjeoxx01p00p00x0ifcc0p0p00x0otherwise8>:wherep0againistheoriginalvalueofPrcjeandp00istheoriginalvalueofPrc0je;x0istheparameter'sori-ginalvalueasbefore.
Iftheinstanceeincludesanotherobservedvalueev6e0v,thenasimilarresultisfoundbyreplacingx0by1x0.
From1p00Pp0foranyvaluecoftheclassvariable,wendthatthehighestsensi-tivityvaluefortheparameterxagainisobtainedwhentheoutputprobabilityofinterestpertainstothesameclassvaluec0asthefeatureparameterbeingvaried,regardlessofthevaluethatisobservedforthefeaturevar-iableEv.
Forthecasewheretheinstanceeincludesthevalueeve0v,Fig.
5depictsthesensitivityvalueoffPrc0jexfordierentcombinationsofvaluesforx0andp00.
Thegureshowsthatlargesensitivityvaluescanonlybefoundiftheoriginalvaluex0fortheparameterunderstudyisquitesmallandtheoriginalpos-teriorprobabilityp00islessextreme;morespecically,wehavethatofPrc0je=oxx0>1ifandonlyifx0p00and1x0p00andx0>>>>>>>>>>>>>>:wherexmpT0x0p00ifeve0v1pT01x0p00ifev6e0v8>:Fromtheaboveproposition,weobservethatanyfeatureparametercanbevariedtotheboundaryoftheunitwindowinatleastonedirectionwithoutchangingthemostlikelyclassvalue.
Uponvaryinganysuchparam-eterintheotherdirection,themostlikelyclassvaluecanchangeatmostonce.
Figs.
4and6supporttheseobservations.
ForthecasewherepT0p00,weagainnotethattheboundarytowhichtheparametercanbevar-iedwithoutinducingachangedependsonwhichofthetwoclassvaluesc0andcTisdesignatedtheuniquemostlikelyclassbythenetwork'sclassicationfunction.
WefurtherobservethatthesmallerthedierencebetweentheposteriorprobabilitiespT0andp00is,thesmallertheadmissibledeviationfortheparameterisandthelessrobustthereturnedclassvaluewillbe.
Weconsiderafeatureparameterxhe0vjc0andaninstanceeinwhicheve0vhasbeenobserved;similarargumentsholdforev6e0v.
Wesupposethattheclassvaluec0isnotthemostlikelyclassvaluegiventheavail-ableevidence.
Iftheoriginalvaluex0oftheparameterisrathersmall,wewouldnotexpecttondthefeaturevaluee0vwithclassc0.
Whenactuallyobserved,therefore,thefeaturevaluedoesnotsupportc0.
Iftheotherobservationsintheinstancealsodonotsupportc0,weexpectthatpT0)p00andalargeadmissibledeviationcanbefoundfortheparameter.
Iftheotherobservationsfromtheinstancedosupporttheclassvaluec0,how-ever,wewouldexpecttondalargerp00andhenceasmalleradmissibledeviation.
Fig.
6illustratestheseobservations.
Nowif,ontheotherhand,theoriginalparametervaluex0isrelativelylarge,wewouldindeedexpecttondthefeaturevaluee0vwithclassc0.
Theactualobservationofe0vthensupportsc0andweexpecttondasomewhatlargerposteriorprobabilityp00andarelativelysmalladmissibledeviation.
Areverseargumen-tationholdsforthecasewherec0isthemostlikelyclassvalue.
Example4.
WeconsideragainthenaiveBayesiannetworkandthepatientinformationfromExamples1and3.
Supposethatweareoncemoreinterestedintheeectofinaccuraciesintheparameterprobability00.
20.
40.
60.
8100.
20.
40.
60.
81fc(x)xx0fc'(x)00.
20.
40.
60.
8100.
20.
40.
60.
81fc(x)xx0fc'(x)Fig.
6.
Examplesensitivityfunctionsforafeatureparameterxhe0vjc0withoriginalvaluex00:2;c0isnotthemostlikelyclassvalue,andvariationoftheparametereithermakesc0themostlikelyvalue(left)ordoesnotchangethemostlikelyvalue(right).
S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416409xhCT-loconojSIVA,withanoriginalvalueofx00:52,onthemostlikelyclassvalueestablishedforourpatient.
Werecallthat,withtheparameter'soriginalvalue,stageIVAisthemostlikelystageforthepatient,withaprobabilityof0.
61;thesecondmostlikelystageisstageIIA,withaprobabilityof0.
19.
Wefurtherrecallthatforthepatientnosignsofloco-regionalmetastaseswerefoundontheCTscan.
Usingtheaboveprobabilities,wenowndforthevaluexmfromProposition3thatxm0:190:52=0:610:16.
Theadmissibledeviationfortheparameterunderstudythusis0:36;!
.
Thisadmissibledeviationindicatesthattheparametercanbevariedfrom0.
52to1.
00withoutinducingachangeinthemostlikelystageofthepatient'scancer.
Theparametercanalsobevariedtosmallervalues,butthemostlikelystagewillchangefromIVAtoIIAiftheparameteradoptsavaluesmallerthan0.
16.
Notethattheparametercanthusbevariedtoapproximatelyone-thirdofitsoriginalvalue.
Furthernotethatthemostlikelystagecannotchangeintoanyothervalueuponvaryingtheparameterunderstudy.
Fromtheaboveconsiderations,weconcludethatthemostlikelyclassvalueestablishedfromanaiveBayes-iannetworkwillbequitesensitivetoinaccuraciesinthenetwork'sfeatureparametersiftheoutputprobabil-itiesfortheclassvariablearemoreorlessuniformlydistributed.
Morespecically,themostlikelyclassvaluewillnotbeveryrobusttovariationinthefeatureparametersifithasapproximatelythesameposteriorprob-abilityastherunner-upvalue.
TheclassicationperformanceofanaiveBayesianclassierwillthusbequiterobustifthemajorityofpresentedinstancesresultinasingleratherlikelyclassvalue.
Yet,theoutputclassvalueestablishedfromanaiveBayesiannetworkinwhichoneormorefeaturesgivenaparticularclasshaverathersmallpriorprobabilities,willalsobequiterobustaslongastheposteriorprobabilitiescomputedforthisclassareratherextremeforallpossibleinstances.
5.
ScenariosensitivityForclassicationproblems,itisgenerallyassumedthatevidenceisavailableforeverysinglefeaturevar-iable.
Intheprevioussection,infact,wealsoadoptedthisassumption.
Inpracticalapplications,however,thisassumptionmaynotalwaysberealistic.
Inthemedicaldomain,forexample,apatientistobeclassiedintooneofanumberofdiseaseswithoutbeingsubjectedtoeverypossiblediagnostictest.
Thequestionthenariseshowmuchimpactadditionalevidencecouldhaveontheprobabilitydistributionovertheclassvariableandhowsensitivethisimpactistoinaccuraciesinthenetwork'sparameters.
Theformerissueiscloselyrelatedtothenotionofvalueof(perfect)informationandcanbestudiedaspartofasensitivity-to-evidence(SE)analysis[6].
Thelatterissueinvolvesanotionofsensitivitythatdiersfromthestandardnotionusedintheprevioussectionsinthatitpertainsnottoactuallyavailableevidencebuttoscenarioswithpossiblyadditionalevidence.
Werefertothisnotionofsensitivityasscenariosensitivityandusethetermevidencesensitivitytorefertothemorestandardnotion.
AlthoughitisapplicabletoBayesiannetworksingeneral,werestrictourdiscussionofthenotionofscenariosensitivityheretothecontextofnaiveBayesiannetworks.
Beforeelaboratingontheeectsofinaccuraciesinanetwork'sfeatureparametersontheimpactofaddi-tionalevidence,webeginbyreviewingtheimpactofthenewevidenceitselfonanoutputprobabilityofinter-est.
Forthispurpose,weconsider,foraspecicclassvalue,theratioofthetwoposteriorprobabilitiesgiventheavailableinstancepriortoandafterreceivingthenewevidence,respectively.
LetEOandENbesetsoffea-turevariableswith;EO&ENEandENEOfE1;Elg,16l6n.
LeteOandeNbeconsistentinstancesofEOandEN,respectively,suchthateNextendstheavailableinstanceeOwiththenewlyobtainedevidenceforthevariablesE1;El.
Then,foreachclassvaluec,wehavethatPrcjeNPrcjeOQli1PreijcPcjQli1PreijcjPrcjjeOwhereeiisthevalueofEiinEN.
Notethattheabovepropertyallowsustocomputethenewposteriorprob-abilitydistributionovertheclassvariablefromthepreviousonewithoutperforminganyadditionalnetworkpropagations.
Example5.
WeconsideragainthenaiveBayesiannetworkandtheassociatedpatientinformationfromthepreviousexamples.
Supposethat,inadditiontothediagnosticteststowhichthepatienthasalreadybeen410S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416subjected,aCTscanoftheupperabdomencanbeperformedtoestablishthepresenceofmetastasesintheliver.
ThenetworkincludesthefollowingparameterprobabilitiesforthefeaturevariableCT-liver:hCT-liverjSIIIAIIBIIIIVAIVBCT-liveryes0.
050.
050.
050.
050.
050.
69no0.
950.
950.
950.
950.
950.
31Fordecidingwhetherornottoperformthescan,wewouldliketoknowthepossibleimpactofthetestresultontheposteriorprobabilitydistributionoverthevariousstagescomputedforourpatient,thatis,weareinterestedintheposteriordistributionsgivenanadditionalpositiveresultandgivenanadditionalnegativeresultfromthescan.
FromtheparameterprobabilitiesmentionedaboveandtheoriginalposteriorprobabilitydistributionPrSjefromExample1,wecomputetheprobabilityofapositivetestresulttobePSPrCT-liveryesjSPrSje0:12.
Werecallthatforourpatient,theoriginalprobabilityofstageIVBwascomputedtobe0.
11.
Givenanadditionalpositiveresultfromthescan,thenewprobabilityofstageIVBwouldbePrIVBjeN0:690:120:110:63NotethatapositivetestresultfromtheCTscanoftheliverwould,forthispatient,changethemostlikelystagefromIVAtoIVB.
Furthernotethatthenewposteriorprobabilitydistributionoverthevariousstagescanbeestablishedwithoutrequiringanyadditionalcomputationsfromthenetwork.
Similarobservationsholdforcomputingtheimpactofanegativetestresultontheposteriorprobabilitydistribution.
Sofar,weconsideredtheimpactofadditionalevidenceontheposteriorprobabilitydistributionovertheclassvariablecomputedfromanaiveBayesiannetwork.
Wenowturntothesensitivityofthisimpacttoinac-curaciesinthenetwork'sparametersandwritetheaboveprobabilityratioasafunctionofaparameterx:hxPrcjeNPrcjeOxPrcjeNxPrcjeOxTheimpactofinaccuraciesinparametersofalreadyobservedfeaturevariablesontheposteriordistributionovertheclassvariablecanbestudiedwiththesensitivityfunctionsgivenintheprevioussections.
Thesefunc-tions,however,donotprovideforestablishingtheeectofinaccuraciesinparametersofyetunobservedfea-tures.
Focusingonthelatter,wenowobservethat,iftheparameterxpertainstoavariablefromthesetENEOofnewlyobservedfeaturevariables,thenthedenominatorintheaboveformulaisaconstantwithrespecttox.
ThefunctionhxthenjustscalesthesensitivityfunctionfPrcjeNxdescribingtheoutputprob-abilitygivenallavailableevidence.
GiventheposteriorprobabilitydistributionPrCjeOovertheclassvari-ablepriortoobtainingthenewinformation,wecanthereforeimmediatelydeterminethesensitivityoftheimpactoftheadditionalevidencetoparametervariationfromthesensitivityfunctionfPrcjeNx.
NotethatforanaiveBayesiannetworkthelatterfunctionisreadilyestablishedforeachfeatureparameterxoncetheposteriorprobabilitydistributionPrCjeNisavailable.
Example6.
Weconsideragainthepreviousexample.
SupposethatwenowareinterestedintheeectsofinaccuraciesintheparameterprobabilityxhCT-liveryesjIVBofthefeaturevariableCT-liverontheratiooftheposteriorprobabilitiesofstageIVB.
Werecallthatthenewposteriorprobabilityofthisstagegiventheadditionalevidenceofapositivetestresultwouldbe0.
63;theprobabilityofIVBgivenjusttheavailableevidencewas0.
11.
WenowestablishthesensitivityfunctionfPrIVBjeNxx=x0:41andndthathIVBx10:11xx0:41FromExample3wehadthattheprobabilityoftheclassvalueIVBincreasedfrom0.
11to0.
63uponapositiveliverscan,therebybecoming5.
7timesaslikely.
Wecannowinadditionconcludethatiftheparameterxisvaried,theclassvalueIVBcanbecomeatmost6.
4timesaslikelyaswithouttheadditionalevidence.
S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–4164116.
ConcludingobservationsNumerousexperimentshaveshownthatclassiersbuiltonnaiveBayesiannetworksperformquitewell,eveniftheirparameterprobabilitiesareknowntoincludeconsiderableinaccuracies.
Inthispaper,weusedsensitivity-analysistechniquestostudytheeectsoftheseparameterinaccuraciesontheposteriorprobabilitydistributionscomputedfromanaiveBayesiannetwork.
Weshowedthattheindependencepropertiesofsuchanetworkservetohighlyconstrainthefunctionalformoftheassociatedsensitivityfunctions.
Thesefunctions,infact,aredeterminedsolelybytheoriginalvalueoftheparameterunderstudyandtheoriginalposteriorprobabilitydistributionovertheclassvariable,andcanthusbeecientlycomputed,requiringasinglenet-workpropagationonly.
ThepropertiesthatwederivedfromthesensitivityfunctionsfurtherprovidedsomefundamentalcorroborationfortheempiricallyobservedrobustnessofnaiveBayesianclassiersinpractice.
Inourfutureresearch,wewouldliketofurtherunderpintheobservedrobustnessofnaiveBayesianclas-siersbystudyingpropertiesofsensitivity.
Inthispaper,forexample,wehavestudiedtheeectsofvaryingasingleparameterprobabilityonlyonanoutputprobabilityofinterest.
Especiallywhendiscussingthepossibleeectsofinaccuraciesinanetwork'sfeatureparameters,itseemsonlynaturaltoconsidertheeectsofsimul-taneousvariationoftwoormoreparameters.
Ingeneral,then-waysensitivityfunctionsthatdescribesucheectsarefractionsoftwomulti-linearfunctionsintheparametersvaried.
Establishingandanalysingthesefunctionsquicklybecomesinfeasible.
InnaiveBayesiannetworks,however,thesefunctionsmayagainturnouttohaveratherconstrainedforms.
Forexample,onlyfeatureparameterspertainingtothesamevalueoftheclassvariablecaninteractintheireectonthecomputedposteriorprobabilities.
Withoutsuchinter-actioneects,weexpectthatourobservationsconcerningtherobustnessofaclassier'sperformancetoparametervariationcanbegeneralised.
Studyingtheinteractioneectsindetail,moreover,mayresultinaddi-tionalinsightsintheapparentlackofsensitivitytoparameterinaccuracies.
Inthispaper,wefurtherintroducedthenovelnotionofscenariosensitivity,whichdescribestheeectsofparameterinaccuraciesinviewofscenariosofadditionalevidence.
WeshowedthatfornaiveBayesiannetworkssuchscenariosensitivitiescanbereadilyexpressedintermsofthemorestandardsensitivityfunctions.
Morespe-cically,forparametersofnewlyobservedfeaturevariables,thescenariosensitivityfunctionsjustscalewiththestandardones.
Inthenearfuture,wewouldliketostudythepropertiesofscenariosensitivityfunctionsforallclassierparameters,andstudythenotionofscenariosensitivityinBayesiannetworksingeneral.
AppendixAA.
1.
TheproofofProposition1Proof.
Letxhc0beaparameterwithoriginalvaluex0,pertainingtothevaluec0ofclassvariableC.
LetPrcjebeanoutputprobabilityofinterestwithoriginalvaluep0,andletp00betheoriginalvalueofPrc0je.
WebeginbywritingthemarginalprobabilityPrc;easafunctionoftheparameterxhc0ofthenetwork'sclassvariable.
Usingthedenitionofconditionalprobability,wehavethatPrc;ePrejchcIfcistheclassvaluewhoseparameterprobabilityisbeingvaried,thatis,ifcc0,thenPrc;erelatesdirectlytotheparameterxhc0inthesensethatPrc;exPrejcx.
Ifc6c0,ontheotherhand,wehavethattheconditionalprobabilityintheexpressionaboveco-varieswiththeparameterx.
Wethenndthatthemar-ginalprobabilityPrc;erelatestoxasPrc;exPrejchc1x1x0WethusndthatthemarginalprobabilityPrc;ecanbeexpressedintermsoftheparameterxhc0asPrc;exPrejc0xifcc0Prejchc1x0xPrejchc1x0otherwise8:Similarly,usingthedenitionofmarginalisation,theprobabilityPrecanbewrittenasPrexPrc0;exXc6c0Prc;ewherethemarginalprobabilityPrc0;erelatestotheparameterxasindicatedaboveandthesumPc6c0Prc;eisconstantwithrespecttox.
Notethattheparametershevjc0forev6e0v,whichco-varywithx,arenopartoftheaboveexpressionsincesuchvaluesevdonotoccurintheinputinstancee,asaresultofourassumptioneve0v.
414S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416Wedenethefollowingconstants:aYEi2EnfEvgheijc0hc0Prc0;ex0bYEi2EheijchchXc6c0Prc;ePrePrc0;eFortheclassvaluecc0wenowndforthesensitivityfunctionfPrc0jexthatfPrc0jexPrc0;exPrexaxaxhxxsandfortheclassvaluec6c0wendthatfPrcjexfPrc;exfPrexbaxhrxswheretheconstantsh=adenestheverticalasymptotethatissharedbythefunctionsfPrc0jexandfPrcjex,c6c0;itsvalueequalssx0PrePrc0;ePrc0;ex01PrePrc0;ex0x0p00Theconstantrb=aofthefunctionfPrcjexwithc6c0nowdirectlyfollowsfromfcx0p0r=x0s.
Finally,thefunctionfPrc0jexhasahorizontalasymptotedenedbyta=a1.
ThefunctionfPrcjexwithc6c0hast0=a0.
Thepropositionsummarisestheseproperties.
hA.
4.
TheproofofProposition4Proof.
LetEvbeafeaturevariablewithvalueevininstancee.
Letxhe0vjc0beaparameterwithoriginalvaluex0,pertainingtothevaluee0vofEvandtheclassvaluec0.
Letp00betheoriginalvalueofPrc0je;inaddition,letpT0argmaxc6c0fPrcjegandletcTbeavalueofCforwhichPrcTjepT0.
TherstpropertystatedinthepropositionfollowsfromtheobservationthatallfunctionsfPrcjewithc6c0havethesamehorizontalandverticalasymptotesandthereforedonotintersect.
Asaconsequence,eitherc0orcTisthemostlikelyvalueofC,regardlessofthevalueofx.
Fortheadmissibledeviationfortheparameterhe0vjc0,weconsiderthevaluexmatwhichthetwofunctionsfPrc0jexandfPrcTjexintersect.
Weestablishthisvalueforthesituationwhereeve0v;forev6e0vtheproofisanalogous.
Foreve0vwendthatfPrc0jexfPrcTjex()xxspT0x0sxs()xpT0x0sSubstitutingsintheaboveformulawithitsvaluex0x0=p00resultsinxmpT0x0=p0020;1i.
Notethattheintersectionofthetwofunctionslieswithintheunit-windowifxmxm.
Theadmissibledeviationsgiveneve0vnowfollowimmediatelyfromthefunctionalforms.
hReferences[1]E.
Castillo,J.
M.
Gutierrez,A.
S.
Hadi,SensitivityanalysisindiscreteBayesiannetworks,IEEETransactionsonSystems,Man,andCybernetics27(1997)412–423.
[2]H.
Chan,A.
Darwiche,Adistancemeasureforboundingprobabilisticbeliefchange,in:R.
Dechter,M.
Kearns,R.
S.
Sutton(Eds.
),Proceedingsofthe18thNationalConferenceonArticialIntelligence,AAAIPress,2002,pp.
539–545.
S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416415[3]H.
Chan,A.
Darwiche,ReasoningaboutBayesiannetworkclassiers,in:C.
Meek,U.
Kjrul(Eds.
),Proceedingsofthe19thConferenceonUncertaintyinArticialIntelligence,MorganKaufmann,2003,pp.
107–115.
[4]V.
M.
H.
Coupe,L.
C.
vanderGaag,PropertiesofsensitivityanalysisofBayesianbeliefnetworks,AnnalsofMathematicsandArticialIntelligence36(2002)323–356.
[5]P.
Domingos,M.
Pazzani,OntheoptimalityofthesimpleBayesianclassierunderzero-oneloss,MachineLearning29(1997)103–130.
[6]F.
V.
Jensen,BayesianNetworksandDecisionGraphs,Springer-Verlag,2001.
[7]U.
Kjrul,L.
C.
vanderGaag,Makingsensitivityanalysiscomputationallyecient,in:C.
Boutilier,M.
Goldszmidt(Eds.
),Proceedingsofthe16thConferenceonUncertaintyinArticialIntelligence,MorganKaufmann,2000,pp.
317–325.
[8]K.
B.
Laskey,SensitivityanalysisforprobabilityassessmentsinBayesiannetworks,IEEETransactionsonSystems,Man,andCybernetics25(1995)901–909.
[9]P.
Liu,L.
Lei,N.
Wu,Aquantitativestudyoftheeectofmissingdatainclassiers,in:N.
Gu,D.
Wei,Z.
Xie,H.
Wang,S.
X.
Wang,B.
Shi(Eds.
),IEEEProceedingsofthe5thInternationalConferenceonComputerandInformationTechnology,2005,pp.
28–33.
[10]J.
Pearl,ProbabilisticReasoninginIntelligentSystems,MorganKaufmann,1988.
[11]S.
Renooij,L.
C.
vanderGaag,Evidence-invariantsensitivitybounds,in:M.
Chickering,J.
Halpern(Eds.
),Proceedingsofthe20thConferenceonUncertaintyinArticialIntelligence,AUAIPress,2004,pp.
479–486.
[12]I.
Rish,AnempiricalstudyofthenaiveBayesclassier,in:IJCAIWorkshoponEmpiricalMethodsinArticialIntelligence,2001,pp.
41–46.
[13]L.
C.
vanderGaag,S.
Renooij,Analysingsensitivitydatafromprobabilisticnetworks,in:J.
S.
Breese,D.
Koller(Eds.
),Proceedingsofthe17thConferenceonUncertaintyinArticialIntelligence,MorganKaufmann,2001,pp.
530–537.
[14]L.
C.
vanderGaag,S.
Renooij,Onthesensitivityofprobabilisticnetworkstoreliabilitycharacteristics,ModernInformationProcessing:FromTheorytoApplications,Elsevier,2006,pp.
385–405.
416S.
Renooij,L.
C.
vanderGaag/Internat.
J.
Approx.
Reason.
49(2008)398–416
- varyingwww.haole008.com相关文档
- equivalentwww.haole008.com
- icalwww.haole008.com
- resultantwww.haole008.com
- recognizedwww.haole008.com
- Sourceswww.haole008.com
- PAwww.haole008.com
数脉科技：香港服务器低至350元/月;阿里云CN2+BGP线路,带宽10M30M50M100M
数脉科技(shuhost)8月促销：香港独立服务器，自营BGP、CN2+BGP、阿里云线路，新客立减400港币/月，老用户按照优惠码减免!香港服务器带宽可选10Mbps、30Mbps、50Mbps、100Mbps带宽，支持中文本Windows、Linux等系统。数脉香港特价阿里云10MbpsCN2，e3-1230v2，16G内存，1T HDD 或 240G SSD，10Mbps带宽，IPv41个，...
新加坡云服务器 1核2Gg 46元/月 香港云服务器 1核2G 74元/月 LightNode
LightNode是一家成立于2002年,总部位于香港的VPS服务商。提供基于KVM虚拟化技术.支持CentOS、Ubuntu或者Windows等操作系统。公司名：厦门靠谱云股份有限公司官方网站：https://www.lightnode.com拥有高质量香港CN2 GIA与东南亚节点（河内、曼谷、迪拜等）。最低月付7.71美金，按时付费，可随时取消。灵活满足开发建站、游戏应用、外贸电商等需求。首...
UCloud：美国云服务器,洛杉矶节点大促,低至7元起/1个月
ucloud美国云服务器怎么样?ucloud是国内知名云计算品牌服务商家，目前推出全球多地机房的海外云服务器。UCloud主打的优势是海外多机房，目前正在进行的2021全球大促活动参与促销的云服务器机房就多达18个。UCloud新一代旗舰产品快杰云服务器已上线洛杉矶节点，覆盖北美和亚太地区，火热促销中， 首月低至7元，轻松体验具备优秀性能与极高性价比的快杰云服务器。点击进入：ucloud美国洛杉矶...
www.haole008.com为你推荐
-
怎么查询商标想要知道一个商标是否被注册，在哪里查到的比较权威？钟神发跪求钟神发名言出处，A站大神看过来同ip站点同IP做同类站好吗？www.522av.com在白虎网站bhwz.com看电影要安装什么播放器？www.haole012.comhttp://fj.qq.com/news/wm/wm012.htm 这个链接的视频的 第3分20秒开始的 背景音乐 是什么?haole16.com国色天香16 17全集高清在线观看 国色天香qvod快播迅雷下载地址www.175qq.com这表情是什么？朴容熙给我介绍几个韩国 ulzzang 最好是像柳惠珠那样的 不要出道的...汴京清谈汴京还被称为什么？干支论坛天干地支