Sensitivity Analysis of Enumerated Trees of Increasing Boolean 枚举树增加布尔的敏感性分析_第1页
Sensitivity Analysis of Enumerated Trees of Increasing Boolean 枚举树增加布尔的敏感性分析_第2页
Sensitivity Analysis of Enumerated Trees of Increasing Boolean 枚举树增加布尔的敏感性分析_第3页
Sensitivity Analysis of Enumerated Trees of Increasing Boolean 枚举树增加布尔的敏感性分析_第4页
Sensitivity Analysis of Enumerated Trees of Increasing Boolean 枚举树增加布尔的敏感性分析_第5页
已阅读5页，还剩51页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

SensitivityAnalysisofEnumeratedTreesofIncreasingBooleanExpressions

SaketAnand,DavidMadigan,RichardMammone,FredRobertsEnumerationandSelectionofOptimumDecisionTreeABC0101AsetofdecisiontreesisconstructedforeachcompleteandmonotonicbooleanfunctionwhereinputsrepresenttestsperformedbyeachsensorABCY00000010010001101000101111011111Y=f(A,B,C)wherefiscompleteandmonotonicThecostofeachtreeisevaluatedandtheoptimumtreeselected.CA0A101B1EnumerationandSelectionofOptimumDecisionTreeThedecisiontreesareconstructedusing4sensorsForthreesensors,thereare114monotonicandcompletebooleanexpressions.Thesecanbeimplementedusing11808distincttrees.Thetreesareevaluatedandrankedusingthecostfunction1.Thetreewiththelowestcostisselectedastheoptimumdecisiontree.1Stroud,P.D.andSaegerKJ.,“EnumerationofIncreasingBooleanExpressionsandAlternativeDigraphImplementationsforDiagnosticApplications〞,ProceedingsVol.IV,Computer,CommunicationandControlTechnologiesCostFunctionusedforevaluatingthedecisiontrees.CTot=

CFalsePositive*PFalsePositive+CFalseNegative*PFalseNegative

+CfixedTheErrorProbabilityoftheentiretreeiscomputedfromtheerrorprobabilitiesoftheindividualsensors.where,

CFalsePositiveisthecostoffalsepositive(TypeIerror)

CFalseNegativeisthecostoffalsenegative(TypeIIerror)

PFalsePositiveistheprobabilityofafalsepositiveoccurring

PFalseNegative

istheprobabilityofafalsenegativeoccurring

Cfixedisthefixedcostofutilizationofthetree.ProbabilityofErrorforIndividualSensorsForithsensor,thetype1(P(Yi=1|X=0))andtype2(P(Yi=0|X=1))errorsaremodeledusingGaussiandistributions.StateofnatureX=0representsabsenceofabomb.StateofnatureX=1representspresenceofabomb.Yirepresentstheoutcomeofsensori.Itischaracterizedby:Ki,discriminationcoefficientTi,decisionthresholdΣi,varianceofthedistributionsKiP(Yi|X=1)P(Yi|X=0)TiCharacteristicsofatypicalsensorReceiverOperatingCharacteristic(ROC)CurveTheROCcurveistheplotoftheProbabilityofcorrectdetection(PD)vs.theProbabilityoffalsepositive(PF).TheROCcurveisusedtoselectanoperatingpoint,whichprovidesthetradeoffbetweenthePDandPFEachsensorhasaROCcurveandthecombinationofthesensorsintoadecisiontreehasacompositeROCcurve.TheparameterwhichisvariedtogetdifferentoperatingpointsontheROCcurveisthesensorThresholdandacombinationofThresholdsforthedecisiontree.EqualErrorRate(EER)istheoperatingpointontheROCcurvewhere,

PF

=

1-PDP(Yi|X=1)P(Yi|X=0)TiKiPDPFOperatingPoint101EERStroud-SaegerExperimentsStroud-SaegerrankedalltreesformedfromfourgivensensorsA,B,CandDaccordingtoincreasingtreecosts.Thecostfunctionusedwasasshowninearlierslides.Valuesusedintheirexperiment:CA=.25;KA=4.37;ΣA=1;CB=.25;KB=1.53;ΣB=1;CC=10;KC=2.9;ΣC=1;CD=30;KD=4.6;ΣD=1;whereCiistheindividualcostofutilizationofsensori,KiisthesensordiscriminationpowerandΣiistherelativespreadfactorforsensori.Valuesofothervariablesarenotknown.CostSensitivitytoGlobalParametersValuesusedintheexperiment:CA=.25;P(YA=1|X=1)=.9856;P(YA=1|X=0)=.0144;CB=1;P(YB=1|X=1)=.7779;P(YB=1|X=0)=.2221;CC=10;P(YC=1|X=1)=.9265;P(YC=1|X=0)=.0735;CD=30;P(YC=1|X=1)=.9893;P(YC=1|X=0)=.0107; whereCiistheindividualcostofutilizationofsensori.Theprobabilitieshavebeencomputedforathresholdcorrespondingtotheequalerrorrate.CFalseNegativetobevariedbetween25millionand500billiondollarsLowandhighestimatesofdirectandindirectcostsincurredduetoafalsenegative.

CFalsePositive

tobevariedbetween180and720dollarsCostincurredduetofalsepositive(4men*(3-6hrs)*(15–30$/hr)P(X=1)tobevariedbetween3/109and1/100,000StructureoftreeswhichcamefirstRankwith3sensors(A,CandD)Treenumber49BooleanExpr:01010111Treenumber37BooleanExpr:00011111acbc10101ab1c001abc0111Treenumber55BooleanExpr:01111111Frequencyofoptimaltreeswith3sensors(A,CandD)whenoneparameterwasvariedConstantParameter(s)VariableParameter(s)TreeNumbersFrequency(outof10,000)EquivalentBooleanExpressionP(X=1)=1.281x10-6,CFalsePositive=492.61CFalseNegative375680001111155943201111111P(X=1)=0.8373x10-5,CFalseNegative=4.2681x1011CFalsePositive55994601111111CFalseNegative=4.4747x1011,CFalsePositive=351.9526P(X=1)37540001111155994601111111RandomlyselectedfixedparametervaluesVariationofCTotvs.CFalseNegative

P(X=1)andCFalsePositive

werekeptconstantatthespecifiedvalueandCTotwascomputedfor10,000randomlyselectedvaluesofCFalseNegative

inthespecifiedrange.RandomlyselectedfixedparametervaluesP(X=1)andCFalseNegativewerekeptconstantatthespecifiedvalueandCTotwascomputedfor10,000randomlyselectedvaluesofCFalsePositiveinthespecifiedrange.RandomlyselectedfixedparametervaluesVariationofCTotvs.CFalsePositiveCFalsePositiveandCFalseNegativewerekeptconstantatthespecifiedvalueandCTotwascomputedfor10,000randomlyselectedvaluesofP(X=1)inthespecifiedrange.RandomlyselectedfixedparametervaluesVariationofCTotvs.P(X=1)Frequencyofoptimaltreeswith3sensors(A,CandD)whenoneparameterwasvariedFixedparametervaluesselectedatStroudandSaegervaluesConstantParameter(s)VariableParameter(s)TreeNumbersFrequency(outof10,000)EquivalentBooleanExpressionP(X=1)=3x10-8,CFalsePositive=600CFalseNegative371000000011111P(X=1)=3x10-8,CFalseNegative=5x1010CFalsePositive371000000011111CFalseNegative=5x1010,CFalsePositive=600P(X=1)4910801010111376940001111155919801111111VariationofCTotvs.CFalseNegative

P(X=1)andCFalsePositive

werekeptconstantatthespecifiedvalueandCTotwascomputedfor10,000randomlyselectedvaluesofCFalseNegative

inthespecifiedrange.FixedparametervaluesselectedatStroudandSaegervaluesP(X=1)andCFalseNegativewerekeptconstantatthespecifiedvalueandCTotwascomputedfor10,000randomlyselectedvaluesofCFalsePositiveinthespecifiedrange.FixedparametervaluesselectedatStroudandSaegervaluesVariationofCTotvs.CFalsePositiveCFalsePositiveandCFalseNegativewerekeptconstantatthespecifiedvalueandCTotwascomputedfor10,000randomlyselectedvaluesofP(X=1)inthespecifiedrange.FixedparametervaluesselectedatStroudandSaegervaluesVariationofCTotvs.P(X=1)VariationofCTotwrtCFalseNegativeandCFalsePositive

CTot=

CFalsePositive*P(X=0)*P(Y=1|X=0)+CFalseNegative*P(X=1)*P(Y=0|X=1)

+CfixedRandomlyselectedfixedparametervaluesVariationofCTotwrtCFalseNegativeandP(X=1)CTot=

CFalsePositive*P(X=0)*P(Y=1|X=0)+CFalseNegative*P(X=1)*P(Y=0|X=1)

+CfixedRandomlyselectedfixedparametervaluesVariationofCTotwrtCFalsePositiveandP(X=1)CTot=

CFalsePositive*P(X=0)*P(Y=1|X=0)+CFalseNegative*P(X=1)*P(Y=0|X=1)

+CfixedRandomlyselectedfixedparametervaluesVariationofCTotwrtCFalseNegativeandCFalsePositive

CTot=

CFalsePositive*P(X=0)*P(Y=1|X=0)+CFalseNegative*P(X=1)*P(Y=0|X=1)

+CfixedFixedparametervaluesselectedatStroudandSaegervaluesVariationofCTotwrtCFalseNegativeandP(X=1)CTot=

CFalsePositive*P(X=0)*P(Y=1|X=0)+CFalseNegative*P(X=1)*P(Y=0|X=1)

+CfixedFixedparametervaluesselectedatStroudandSaegervaluesVariationofCTotwrtCFalsePositiveandP(X=1)CTot=

CFalsePositive*P(X=0)*P(Y=1|X=0)+CFalseNegative*P(X=1)*P(Y=0|X=1)

+CfixedFixedparametervaluesselectedatStroudandSaegervaluesTreeStructureandcorrespondingBooleanExpressionsTreenumber11785BooleanExpr:Treenumber11605BooleanExpr:a1cd011b1a1bc1d01d01TreeStructureandcorrespondingBooleanExpressionsTreenumber9133BooleanExpr:Treenumber8965BooleanExpr:d01acd011b0d01acd01b01cd01b1TreeStructureandcorrespondingBooleanExpressionsTreenumber6797BooleanExpr:Treenumber2473BooleanExpr:0000000101111111acd0101cd01b10abc0d1cd01b101TreeStructureandcorrespondingBooleanExpressionsTreenumber11305BooleanExpr:ad101cd01b1VariationofCTotvs.CFalseNegative

P(X=1)andCFalsePositive

werekeptconstantatthespecifiedvalueandCTotwascomputedfor10,000randomlyselectedvaluesofCFalseNegative

inthespecifiedrange.RandomlyselectedfixedparametervaluesP(X=1)andCFalseNegativewerekeptconstantatthespecifiedvalueandCTotwascomputedfor10,000randomlyselectedvaluesofCFalsePositiveinthespecifiedrange.RandomlyselectedfixedparametervaluesVariationofCTotvs.CFalsePositiveCFalsePositiveandCFalseNegativewerekeptconstantatthespecifiedvalueandCTotwascomputedfor10,000randomlyselectedvaluesofP(X=1)inthespecifiedrange.RandomlyselectedfixedparametervaluesVariationofCTotvs.P(X=1)VariationofCTotvs.CFalseNegative

P(X=1)andCFalsePositive

werekeptconstantatthespecifiedvalueandCTotwascomputedfor10,000randomlyselectedvaluesofCFalseNegative

inthespecifiedrange.FixedparametervaluesselectedatStroudandSaegervaluesP(X=1)andCFalseNegativewerekeptconstantatthespecifiedvalueandCTotwascomputedfor10,000randomlyselectedvaluesofCFalsePositiveinthespecifiedrange.FixedparametervaluesselectedatStroudandSaegervaluesVariationofCTotvs.CFalsePositiveCFalsePositiveandCFalseNegativewerekeptconstantatthespecifiedvalueandCTotwascomputedfor10,000randomlyselectedvaluesofP(X=1)inthespecifiedrange.FixedparametervaluesselectedatStroudandSaegervaluesVariationofCTotvs.P(X=1)Frequencyofoptimaltreeswith4sensorswhentwoparameterswerevaried.Thefixedparameterswererandomlyselected.

RandomlyselectedfixedparametervaluesConstantParameter(s)VariableParameter(s)TreeNumbersFrequency(outof10,000)EquivalentBooleanExpressionCFalsePositive=453.6849CFalseNegativeP(X=1)50510000000001111111679718000100010111111189655000010101011111119001700010101011111119017600010101011111119133235000101011111111111605862101010111111111111178510620111111111111111CFalseNegative=4.7485x1010P(X=1),CFalsePositive261710000000111111111679716000100010111111189651210001010101111111900170001010101111111901713000101010111111191333920001010111111111113059901010101011111111160593510101011111111111P(X=1)=0.6344x10-5CFalseNegative,CFalsePositive679720001000101111111896513000101010111111191336500010101111111111130513010101010111111111605792801010111111111111178519790111111111111111VariationofCTotwrtCFalseNegativeandCFalsePositive

CTot=

CFalsePositive*P(X=0)*P(Y=1|X=0)+CFalseNegative*P(X=1)*P(Y=0|X=1)

+CfixedRandomlyselectedfixedparametervaluesVariationofCTotwrtCFalseNegativeandP(X=1)CTot=

CFalsePositive*P(X=0)*P(Y=1|X=0)+CFalseNegative*P(X=1)*P(Y=0|X=1)

+CfixedRandomlyselectedfixedparametervaluesVariationofCTotwrtCFalsePositiveandP(X=1)CTot=

CFalsePositive*P(X=0)*P(Y=1|X=0)+CFalseNegative*P(X=1)*P(Y=0|X=1)

+CfixedRandomlyselectedfixedparametervaluesFrequencyofoptimaltreeswith4sensorswhentwoparameterswerevaried.ThefixedparameterswereselectedattheStroudandSaegervalues.ConstantParameter(s)VariableParameter(s)TreeNumbersFrequency(outof10,000)EquivalentBooleanExpressionCFalsePositive=600CFalseNegativeP(X=1)50510000000001111111247320000000101111111250910000000101111111679718000100010111111189651380001010101111111900119000101010111111190177000101010111111191331840001010111111111113056501010101011111111160592320101011111111111117853330111111111111111CFalseNegative=5x1010P(X=1),CFalsePositive67971400010001011111118965117000101010111111190019000101010111111190179000101010111111191333740001010111111111113059601010101011111111160593810101011111111111P(X=1)=3x10-8,CFalseNegative,CFalsePositive505110000000001111111775500000001000011112473420000000101111111261740000000011111111167975580001000101111111896538330001010101111111913354060001010111111111116051050101011111111111VariationofCTotwrtCFalseNegativeandCFalsePositive

CTot=

CFalsePositive*P(X=0)*P(Y=1|X=0)+CFalseNegative*P(X=1)*P(Y=0|X=1)

+CfixedFixedparametervaluesselectedatStroudandSaegervaluesVariationofCTotwrtCFalseNegativeandP(X=1)CTot=

CFalsePositive*P(X=0)*P(Y=1|X=0)+CFalseNegative*P(X=1)*P(Y=0|X=1)

+CfixedFixedparametervaluesselectedatStroudandSaegervaluesVariationofCTotwrtCFalsePositiveandP(X=1)CTot=

CFalsePositive*P(X=0)*P(Y=1|X=0)+CFalseNegative*P(X=1)*P(Y=0|X=1)

+CfixedFixedparametervaluesselectedatStroudandSaegervaluesSensitivitytoSensorPerformanceCA=.25;KA=4.37;ΣA=1CB=.25;KB=1.53;ΣB=1CC=15;KC=2.9;ΣC=1CD=30;KD=4.6;ΣD=1Theprobabilityoffalsepositivefortheithsensoriscomputedas:P(Yi=1|X=0)=0.5erfc[Ti/√2]Theprobabilityofdetectionfortheithsensoriscomputedas:P(Yi=1|X=1)=0.5erfc[(Ti-Ki)/(Σ√2)]whereCiistheindividualcostofutilizationofsensori,KiisthediscriminationpowerofthesensorandΣiisthespreadfactorforthesensorFollowingexperimentshavebeendoneusingsensorsA,B,CandDasdescribedbelowbyvaryingtheindividualsensorthresholdsTA,TBandTCfrom-4.0to+4.0instepsof0.4.ThesevalueswerechosensincetheygaveusaROCcurvefortheindividualsensorsoveracompleterangeP(Yi=1|X=0)andP(Yi=1|X=1)Frequencyofoptimaltreeswith3sensorswhentheThresholdswerevaried.Thefixedparameters(CFalsePositive,CFalseNegative,P(X=1))wereselectedrandomly.Fifteentreesattainedrankone,outofwhichtreenumber37wasthemostfrequent.ConstantsTreeNumbersFrequencyBooleanExpressionCFalseNegative==5.0125x109P(X=1)=5.05x10-6andCFalsePositive=450271140001011129146000101112183000000014926401010111513220101011125957000101112314750001010115243700010011384572000111111952560001010115828000000014558730011011155105870111111171339200000111371751500011111Performance(ROC)ofBestDecisionTreeforTreenumber37Performance(ROC)ofBestDecisionTreeforTreenumber37Frequencyofoptimaltreeswith4sensorswhentheThresholdswerevaried.Thefixedparameters(CFalsePositive,CFalseNegative,P(X=1))wereselectedrandomly.244treesattainedrankone,outofwhichtreenumber445wasthemostfrequent.Only15mostfrequentlyoccurringoptimaltreesoutofthe241aretabulatedbelow.ConstantsTreeNumbersFrequencyBooleanExpressionCFalseNegative==4.8668x1011P(X=1)=7.5361x10-6andCFalsePositive=499.754451

人人文库> 全部分类> 行业资料 > 信息产业

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论