Citation
A Measure-Theoretic Interpretation of Sample Based Numerical Integration with Applications to Inverse and Prediction Problems Under Uncertainty

Material Information

Title:
A Measure-Theoretic Interpretation of Sample Based Numerical Integration with Applications to Inverse and Prediction Problems Under Uncertainty
Creator:
Butler, Troy
Physical Description:
Journal Article

Notes

Abstract:
The integration of functions over measurable sets is a fundamental problem in computational science. When the measurable sets belong to high dimensional spaces or the function is computationally complex, it may only be practical to estimate integrals based on weighted sums of function values from a finite collection of samples. Monte Carlo, Quasi-Monte Carlo, and other (pseudo-)random schemes are common choices for determining a set of samples. These schemes are appealing for their conceptual ease and ability to circumvent, with various degrees of success, the so-called ``curse of dimensionality.'' However, convergence is often slow and described in terms of probability. We consider a general measure-theoretic interpretation of any sample based algorithm for numerically approximating an integral. A priori error bounds are proven that provide insight into defining adaptive sampling algorithms solving error optimization problems. We use these bounds to improve integral approximations for both forward and inverse problems.
Acquisition:
Collected for Auraria Institutional Repository by the Self-Submittal tool. Submitted by Troy Butler.
Publication Status:
Unpublished

Record Information

Source Institution:
Auraria Institutional Repository
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.

Auraria Membership

Aggregations:
Auraria Library

Downloads

This item is only available as the following downloads:


Full Text

PAGE 1

DRAFT SIAMJ.S CI. C OMPUT. c r xxxxSocietyforIndustrialandAppliedMathematics Vol.xx,pp.x x{x AMeasure-TheoreticInterpretationofSampleBasedNumeri calIntegrationwith ApplicationstoInverseandPredictionProblemsUnderUnce rtainty T.Butler L.Graham y S.Mattis z and S.Walsh x Abstract. Theintegrationoffunctionsovermeasurablesetsisafunda mentalproblemincomputationalscience. Whenthemeasurablesetsbelongtohighdimensionalspaceso rthefunctioniscomputationally complex,itmayonlybepracticaltoestimateintegralsbase donweightedsumsoffunctionvalues fromanitecollectionofsamples.MonteCarlo,Quasi-Mont eCarlo,andother(pseudo-)random schemesarecommonchoicesfordeterminingasetofsamples. Theseschemesareappealingfor theirconceptualeaseandabilitytocircumvent,withvario usdegreesofsuccess,theso-called\curse ofdimensionality."However,convergenceisoftenslowand describedintermsofprobability.We considerageneralmeasure-theoreticinterpretationofan ysamplebasedalgorithmfornumerically approximatinganintegral.Apriorierrorboundsareproven thatprovideinsightintodening adaptivesamplingalgorithmssolvingerroroptimizationp roblems.Weusetheseboundstoimprove integralapproximationsforbothforwardandinverseprobl ems. Keywords. Numericalintegration,uncertaintyquantication,error analysis,adaptivesampling,MonteCarlo methods,inverseproblems 1.Introduction. Theproblemofquantifyinguncertaintyinappliedandcompu tational sciencecantakemanyformssuchascomputingcertainstatis ticalmomentsofaphysically importantquantity(e.g.,thepredictedmeanandstandardd eviationoftemperaturesina numericalclimatemodel)orcomputingprobabilitiesofeve ntsofengineeringinterest(e.g., theprobabilitythatstormsurgefromahurricanewillcause aleveetofail).Solvingthese problemsofteninvolvesthecomputationofanintegralofar andomvariable(i.e.,measurable function)oversomeevent(i.e.,measurableset).Inthispa per,weinterpretboththeforward andinverseproblemsofquantifyinguncertaintiesassocia tedwithaphysics-basedmodelin termsofintegralsofameasurablefunction.Oftentheseint egrals,andincertaincasesthe measurablefunctionitself,mustbenumericallyapproxima ted.Manynumericalintegration DepartmentofMathematicalandStatisticalSciences,Univ ersityofColoradoDenver,Denver,CO80202 ( Troy.Butler@ucdenver.edu ).ResearchsupportedbyU.S.DepartmentofEnergyOceofSc ience,Oceof AdvancedScienticComputingResearch,AppliedMathemati csprogramunderAwardNumberDE-SC00009279as partoftheDiaMonDMultifacetedMathematicsIntegratedCa pabilityCenter;andtheNationalScienceFoundation (DMS-1228206). y DepartmentofScienticComputing,FloridaStateUniversi ty,Tallahassee,Florida32306 ( lgraham@ices.utexas.edu ).ResearchsupportedbyU.S.DepartmentofEnergyOceofSc ience,Oce ofAdvancedScienticComputingResearch,AppliedMathema ticsprogramunderAwardNumberDE-SC0009324 aspartoftheDiaMonDMultifacetedMathematicsIntegrated CapabilityCenter;andbytheNationalScience FoundationGraduateResearchFellowshipunderGrantNo.DG E-1110007andtheDepartmentofEnergyOceof Science(DE-SC0010678). z InstituteforComputationalEngineeringandSciences(ICE S),UniversityofTexasatAustin,Austin,Texas 78712( smattis@ices.utexas.edu ).ResearchsupportedbyU.S.DepartmentofEnergyOceofSc ience,Oce ofAdvancedScienticComputingResearch,AppliedMathema ticsprogramunderAwardNumberDE-SC0009286 aspartoftheDiaMonDMultifacetedMathematicsIntegrated CapabilityCenter. x DepartmentofMathematicalandStatisticalSciences,Univ ersityofColoradoDenver,Denver,CO80202 ( Scott.Walsh@ucdenver.edu ).ResearchsupportedbytheNationalScienceFoundation(D MS-1228206). 1

PAGE 2

DRAFT 2 T.Butleret.al. schemesarewrittenastheweightedsumoffunctionvaluesch osenateitherspeciedorrandom inputsamples,e.g.,see[ 14 20 33 ]andthereferencestherein. Possiblythemostpopularmethodtoestimateintegralsisth eMonteCarlo(MC)method [ 20 26 ].TheerrorsinaMCapproximationhavebeenshowntodecreas eatarateof N 1 = 2 where N isthenumberofsamples.Quasi-MonteCarlo(QMC)methods[ 33 ]improveupon standardMCestimatesbyspecicationofamoresuitablesam plepointsetresultinginerrors thatdecreaseattherateof N 1 .TheadvantageofMCorQMCmethodsisthattherateof decayoftheerrorsisindependentofdimension.However,th eerrorsandconvergenceofthese methodsaredescribedintermsofprobabilities,e.g.,usin gtheLawofLargeNumbersand/or theCentralLimitTheorem. Inrecentyears,therehasbeenanincreasedinterestincomp utingintegralapproximations baseduponageometricpointofviewexploitingVoronoitess ellations[ 25 38 ].Someofthe foundationalelementsoftheserecentworksaredescribedw ithinthecomprehensivereview oncentroidalVoronoitessellationsfoundin[ 19 ].Inthiswork,webuilduponthegeneral formulationofoptimalquadraturerulespresentedin[ 19 ].Theresultisageneralmeasuretheoreticframeworkforinterpretingsamplebasedapproxi mationstointegralsthatapplies regardlessofhowthesamplesaregenerated.Undersuitable assumptionsaboutthemeasurable function,weproveapriorimeasure-theoreticboundsforag enericsamplebasedintegration scheme.Thistypeoferroranalysiscomplementsanyadditio nalerroranalysisorbounds availabletothespecicsamplebasedintegrationscheme.F urthermore,thetermsinvolved intheboundsprovidevaluableinsightintodeningadaptiv esamplingintermsofsolvingan optimizationproblemtoimprovenumericalaccuracyinthec omputations. Usingtheconceptof emulated samplesweavoidthecomputationallyexpensivegeometric procedureofexplicitlyconstructingand/ortriangulatin gtheVoronoitessellationsattheheart ofotherapproachesusingsuchtessellations.Theemulated samplesareusedtoprovideMC estimatesofcertaingeometricpropertiesoftheimplicitl ydenedVoronoitessellationsand guideadaptivesampling.Wealsoapplytheseideastoimprov etheaccuracyofthesolutionofa measure-theoreticinverseproblemwhichsubsequentlyimp rovesaccuracyinthecomputations ofprobabilitiesofvariousevents.Usingemulatedsamples hasotherpracticalbenets.For example,wearenotconstrainedbytheexplicitconstructio nofVoronoicellswhichoften restrictsthedimensionforwhichtheresultsof[ 25 38 ]canbeapplied. Akeyobservationfromthenumericalexamplesisthatthedis tributionoferrorsfrom ameasure-theoreticapproximationtoanintegralcanleadt ohigherprobabilitiesthatany singleintegralapproximationiswithinaspeciederrorto lerancecomparedtoMCestimates. Moreover,theadaptivesamplingstrategydenedintermsof anoptimizationproblemcan leadtoimprovedmeasure-theoreticestimatesthatsignic antlyreducethevarianceinthe errorswiththeadditionofasmallnumberofsamplescompare dtotraditionalMCestimates. Thisissignicantinproblemswhereeachfunctionevaluati oniscomputationallycomplex (e.g.,requiringthesolutionofadierentialequation)suc hthatitmayonlybepossibleto computeasingleintegralestimatefromaxednumberofsamp lesbeforereningtheestimate usingarelativelysmallnumberofadditionalsamples. Thispaperisorganizedasfollows.InSection 2 ,wereviewthegeneralnotationused throughoutaswellasdenethegeneraltypesofproblemscon sideredinthiswork.InSection 3 ameasure-theoreticinterpretationofnumericalintegrat ionisprovidedbasedon implicitly

PAGE 3

DRAFT Measure-TheoreticSample-BasedIntegration 3 denedVoronoicells.Section 4 providesthesimpleerrorboundsforthisinterpretationof numericalintegrationthatareusefulindeninganadaptiv esamplingstrategydescribed inSection 5 assolvingoneoftwooptimizationproblems.Section 4 alsodescribesaMC approach,calledemulation,forapproximatingvolumesand geometricfeaturesoftheimplicitly denedVoronoitessellationusefulinboththeintegralapp roximationsandadaptivesampling. Section 6 brieryreviewsthestructureofprobabilitymeasuressolvi ngthetypeofstochastic inverseproblemsconsideredinthiswork.Section 7 reviewsthecomputationalalgorithmfor approximatingtheseinverseprobabilitymeasures,theapp roximationerrorofcertaintypes ofinverseeventsinthecontextoftheerrorestimatesofSec tion 4 ,andatwo-stageadaptive samplingstrategyforreducingthiserror.InSection 8 ,numericalexamplesillustratethe variousideasandtechniquesonapredictionprobleminvolv inganepidemicmodelwitha15dimensionalparameterspaceandonastochasticinversepro bleminvolvingtheshallowwater equationsandaparametereldwithdataatthesub-gridscal e.Weprovidesomeconcluding remarksandpossibledirectionsoffutureresearchinSecti on 9 2.NotationandProblemDenitions. Letdenotethesetofalluncertaininputparametersforamodeland D denoteasubsetofthepossibleoutputdatadenedbyquantit ies ofinterest(QoI)fromthesolutionofthemodel.Assumethat theQoImap Q : !D is piecewisesmooth.Let B and B D denote -algebrasonand D ,and and D denote (volume)measuresonthemeasurablespaces( ; B )and( D ; B D ),respectively. Themeasure-theoreticstochasticinverseproblemweconsi derisdenedasfollows.We assumethemap Q : !D andprobabilitymeasure P D (absolutelycontinuouswithrespect to D )aregiven.Theproblemistodetermineprobabilitymeasure P on(absolutelycontinuouswithrespectto )suchthat P ( Q 1 ( A ))= P D ( A )forall A 2B D .Theassumptions ofabsolutecontinuityimplythattheproblemcanberestate dasndingaprobabilitydensity function (i.e.,theRadon-Nikodymderivativeof P withrespectto )satisfying P ( Q 1 ( A ))= Z Q 1 ( A ) dP = Z Q 1 ( A ) d = Z A D d D = Z A dP D = P D ( A ) forall A 2B D .Thisdensityissimplyanintegrablereal-valuedfunction on( ; B ; ).In Sections 6 and 7 ,webrieryreviewtheexistenceanduniquenessofsolutions tothisinverse problem,numericalapproximations,anderrorsintheappro ximation. Given P ,wemaycomputeprobabilitiesofevents A 2B .Alternatively,wemayconsider theproblemofprediction(orpredictionunderuncertainty )where f : R isanintegrable function(randomvariable,r.v.)andtheproblemistoestim ate R A f ( ) d (or R A f ( ) dP ) forsome A 2B .Examplesofthetypeoffunction f include,butarenotlimitedto,an unobservedquantityofinterest(whichwealsorefertoasQo I)denedasafunctionalofthe solutiontothemodel(possiblyatafuturetime),acharacte risticfunction B where B 2B isasetofphysicallyimportantmodelparameters,oreventh edensity .Thus,ageneral goalforsolvingthemeasure-theoreticinverseproblemist oestimate R A f ( ) d forsome speciedr.v. f and A 2B .Therefore,wefocusrstonthefundamentalpredictionpro blem ofestimating R A f ( ) d 3.MeasureTheoreticInterpretationofSampleBasedAlgorithmsforIntegr ation. Evenwhen f isknownexactlythevalueof R A f ( ) d isoftennumericallyapproximated

PAGE 4

DRAFT 4 T.Butleret.al. byaweightedsum I N ( f ):= X ( i ) 2 A w i f ( ( i ) ) : When R n and n issmall,itissometimespossibletousedeterministicquad raturerules (e.g.,Gauss{LegendreorGauss{Lobattorules[ 14 ])todeterminethesamplepoints ( i ) Ni =1 andweights w i toapproximate R A f ( ) d toaspeciedaccuracy.Weobtainageometric interpretationfortheweightsintermsofmeasuresof implicitly denedVoronoicells. Givenanintegrablefunction f : R ,acommonthemeinmeasuretheoryistowrite theintegralasthelimitofasequenceofintegralsofsimple functionapproximations( f n ) where f n f .Simplefunctionsaretypicallywrittenaslinearcombinat ionsofcharacteristic functions A for A 2B where A ( x )=1if x 2 A and A ( x )=0if x= 2 A .Let f n = N ( n ) X i =1 a i V i;N ( n ) where N ( n )denesthenumberofcells V i;N ( n ) N ( n ) i =1 B formingsometessellationofassociatedtotheapproximat ion f n ,andtheset f a i g N ( n ) i =1 R approximatesthefunctionvaluesonthecorrespondingcell s.Inthiscase,fromlinearityof theintegral, Z f n d = N ( n ) X i =1 a i ( V i;N ( n ) ) : Forsimplicityofnotation,weconsideraxedapproximatio n f N andwrite N insteadof N ( n )below.Sincethefunctionassumesthe a i values,wecaninterprettheintegralof f N as the R N innerproductbetweenthevectorsoffunctionvaluesandmea suresofsetsassociated tothosefunctionvalues.Typically,the a i valuesarechosensothat a i = f ( ( i ) )forsome ( i ) 2V i;N .Inthiscase,wehave Z f N d = N X i =1 f ( ( i ) ) ( V i;N ) : Itfollowsinthemoregeneralcaseofestimating R A fd that Z A fd Z A f N d = N X i =1 f ( ( i ) ) ( V i;N \ A ) : (3.1) Wemakeuseofthefollowingdenition.

PAGE 5

DRAFT Measure-TheoreticSample-BasedIntegration 5 Denition3.1. Foraxednumberofsamples ( i ) Ni =1 ,thereisa Voronoitessellation of denotedby fV i;N g Ni =1 denedby V i;N := n 2 : d v ( ( i ) ; ) d v ( ( j ) ; ) ; 8 j =1 ;:::;N o : Here, d v ( ; ) denotesametricon usedtodenetheVoronoicells. Thus,givenasetofsamplesinandtheassociatedfunctionv alues,ameasure-theoretic approximationto R A f isobtainedusingEq.( 3.1 )wheretheweightsaredenedinterms ofmeasuresoftheimplicitlydenedVoronoicells.Otherus esofVoronoicellsincludinga similargeometricpointofviewonintegralapproximations canbefoundin[ 19 25 38 ]andthe referencestherein.Inparticular,theworkof[ 38 ]isinterestingforadescriptionofso-called ( ; )-samplingschemestoproduceVoronoitessellationsonlow erdimensionalmanifoldswhere integralapproximationsarecomputed.Theapproachinthis paperusingemulatedsamples describedinSection 4 isuniqueinthat explicitconstructionofVoronoitessellationsisavoided andthereare norestrictionsonthetypeofsamplingscheme usedtoproduceintegralestimates. Mostnumericalquadraturetechniquesdonothaveweightseq ualto ( V i;N ).Thus, foranysamplebasednumericalintegrationscheme,wemayco mputetwoapproximations totheintegralwhichmaydier:(1)theapproximationdened bythescheme,denoted aboveby I N ( f ),and(2)themeasure-theoreticapproximationdenedbyEq .( 3.1 ).With thesetwoapproximationsandthelinearityoftheintegral, theerrorinthemeasure-theoretic approximationisdecomposedinto Z A ( f f N ) d = Z A fd I N ( f ) | {z } E mtd + I N ( f ) Z A f N d | {z } E meas (3.2) Here, E mtd denotestheerrorduetothestandardnumericalquadratures chemeand E meas denotestheerrorduetousingthesamesetofsamplesfromthe numericalquadraturescheme butwithweightschosenaccordingtothemeasuresoftheimpl icitlydenedVoronoicells.Usingtheexplicitformsfor I N ( f )and R A f N d ,andassuming A =fornotationalsimplicity, wehave E meas = N X i =1 f ( ( i ) )( w i ( V i;N )) : (3.3) Fortypicalnumericalquadraturetechniques,wehavethat E mtd = O ( g ( N ))where g ( N ) describestherateofconvergenceforthemethodasafunctio nofsamplesize.Thus,thesuitabilityofthemeasure-theoreticestimateasanalternativ eestimateforasetofsamplesdened onlyintermsofstandardnumericalquadraturetechniquesc omesdowntothediscrepancies in w i from ( V i;N ).However,themeasure-theoreticapproximationcanbe renedbyany additionalsetofsamples andassociatedfunctionvaluesavailablewhereasothernum ericalintegrationschemeshavelimitedadaptivitypropertieswher eadditionalsamplesandassociated functionvaluescanbeincludedonlyifthecriteriaofthesc hemearemet. Whenthesamplesaredeterministicallychosenaccordingto schemestypicallyusedin low-dimensionalspaces,theweightsoftencomefromevalua tionofsomeweightingfunction.

PAGE 6

DRAFT 6 T.Butleret.al. However,insomecasesitispossibletowritetheweightsase valuationsofanorthogonal Stieltjespolynomialassociatedwiththemeasure,andthes eweightssumtothemeasureof thesetbeingsampled[ 21 ]. ForastandardMCschemewhere ( i ) Ni =1 areindependentidenticallydistributed(i.i.d.) anduniformlysampled(withrespecttotheunderlyingvolum emeasure),thentheuniform weightingof1 =N inthesumcorrespondstoan approximationthateachVoronoicellhasthe samevolume ,whichcanbeinterpretedasthe expected valueofthevolumeof anyparticular Voronoicell.Inrandomsampleschemes,twosetsofsamplesm aycorrespondtothesame functionvalues,buttheassociatedVoronoicellsmayhavec ompletelydierentvolumes.This leadstoadistributionoferrorsforthenumericallyapprox imatedintegralsforaxedsample size,butasisshowninthefollowingsection,therealwayse xistsacomputableboundofthese errorsusingthemeasure-theoreticapproximationtothein tegralforanygivensetofsamples. However,theexpectedvalueof E meas iseasilyseentobezerointhiscase,sowefocuson usingMCschemestocreateaninitialsetofi.i.d.samplesfo rwhichbothestimatesofintegrals arecomputedandcompared. Weendthissectionrstwiththreeexamplesbasedoni.i.d.s amplingandMCintegration comparedtothemeasure-theoreticapproximationsinvario usdimensions.Thersttwoillustratetheconvergencepropertiesofthismethodinvariousd imensionsonGenzfunctions[ 22 ] chosentohavedierentqualitativeandquantitativeproper ties.Thethirdexamplexesthe samplesizetomakemoreexplicithowthevarianceintheerro rsmaybedecreasedbyusing Eq.( 3.1 )directlyonthesamplesusedforMCintegration.Inthenext section,weuseerror estimatestoguideadaptivesamplingtofurtherreducethev arianceintheerrorsofthisthird exampleandsignicantlyincreasetheprobabilitythatany randomlychosenintegralestimate usingEq.( 3.1 )isaccuratewithinaspeciederrortolerance.Thisisalso observedinthe numericalresultsofSection 8 .Suchresultshaveapotentiallysignicantimpactonprobl ems whereevaluationof f iscomputationallycomplexandonlyasingleestimateofthe integral canbecomputedbeforearelativelysmallsetofadditionals amplesandfunctionevaluations areusedtorenetheestimate. Example1. ThecontinuousintegrandfamilyofGenzfunctions[ 22 ]aredescribedby f ( x )=exp d X i =1 a i j x i u i j : Here, d denotesthedimension,andthefunctionsrisetoapeakcente redat ( u 1 ;u 2 ;:::;u d ) atexponentialratesfollowingthecoordinateaxeswhereth eratesaredeterminebythechoice of ( a 1 ;a 2 ;:::;a d ) .Thefunctionsaretypicallyintegratedovertheunithyperc ube,andananalyticvalueoftheintegraliseasilyobtained.Thechoiceof u i 'sdonotsignicantlyaect thedicultyofintegrationwhereaslargervaluesof a i 'sresultinmoredicultnumericalintegration.Wechosethe u i =0 : 5 and a i =5 followingtheexampledescriptionprovidedat https://www.sfu.ca/~ssurjano/cont.html wherevariouscodesarealsoavailable.Comparisonsoftheconvergenceofthemeansquareerror(MSE)in theMCandmeasure-theoretic integralapproximationsaresummarizedinFigure 3.1 for d =1 ; 5 ; and 10 .Foreachsample size,50setsofi.i.d.samplesweregeneratedandestimates ofthevolumesoftheimplicitly denedVoronoicellswerecomputedviaemulationof 1 E +5 samples(seeAlgorithm 1 ).We

PAGE 7

DRAFT Measure-TheoreticSample-BasedIntegration 7 observethattheMSEisseveralordersofmagnitudelesswhen d =1 ,whichisalsoseenin thefollowingexampleandgenerallyappearstobethetrendu ptodimensionsofabout d =4 Then,at d =5 ,theMSEresultsaresimilarandfollowsimilarratesofconv ergence.Athigher dimensions,startingaround d =10 ,weobservethattheMSEfortheMCestimateisbetter atsmallsamplesizes,buttherateofconvergenceisfasterf orthemeasure-theoreticestimate althoughoveralltheabsolutesizesoftheMSEforbothestim atesareextremelysmallforthis Genzfunctionasthedimensionincreases. n r n r r n n Figure3.1:Meansquareerror(verticalaxes)ofMCestimate s(dottedlinewithcircles)and measure-theoreticestimates(dottedlinewithsquares)at varioussamplesizes(horizontal axes)ofthecontinuousintegrandfamilyofGenzfunctionsw ithparameters u i =0 : 5and a i =5.Fromlefttoright:dimension1,5,and10.Theexpectedra teofconvergenceofthe MSEforanMCestimateisshownbythesolidblackline. Example2. TheoscillatoryintegrandfamilyofGenzfunctions[ 22 ]aredescribedby f ( x )=cos 2 u 1 + d X i =1 a i x i : Here, d denotesthedimension,andthefunctioncanbequicklyinteg ratedtohighprecision withaninputdomaincommonlychosentobetheunithypercube ,whichischosenhereas well.Theparameter u 1 doesnotaectthedicultyofnumericalintegrationwherea slarger choicesofthe a i parametersresultsinhigherfrequencyoscillationsandmo redicultnumericalintegration.Acommonchoiceof u 1 is 0 : 5 ,whichisusedhereaswell(e.g.,see https://www.sfu.ca/~ssurjano/oscil.html wherethe a i valuesarealsochosentobe 5 for each i ).Here,wechoose a i =10 foreach i toprovidesignicantoscillationsespeciallyinthe diagonaldirection 11 1 > 2 R d as d increases.Forexample,when d =10 ,changingvariablesalongthisdiagonaldirectionprovidesanee ctiveoscillatoryparameterof 100 Asinthepreviousexample,wesummarizetheMSEforMCandmea sure-theoreticintegral approximationsinFigure 3.2 usingasimilarsetupwith50repeatedtrialsforeachsample size usedandthesametypeofestimatesofthemeasuresoftheimpl icitlydenedVoronoicells. Weagainobservethatinlowdimensions,themeasure-theore ticapproximationhassignicantlylessMSEbyseveralordersofmagnitudecomparedtoat raditionalMCestimate.In higherdimensionstheresultsaresimilarbetweenthetwoes timates.However,asshownin Examples 3 and 4 ,theadaptivestrategiessuggestedinthefollowingsectio nscanhaveamore

PAGE 8

DRAFT 8 T.Butleret.al. signicantimpactonreducingthevarianceinestimatesfor themeasure-theoreticapproach comparedtothetypicalMCapproach. n #! r! r n #! r! r n #! r! r Figure3.2:Meansquareerror(verticalaxes)ofMCestimate s(dottedlinewithcircles)and measure-theoreticestimates(dottedlinewithsquares)at varioussamplesizes(horizontal axes)oftheoscillatoryintegrandfamilyofGenzfunctions withparameters u 1 =0 : 5and a i =10.Fromlefttoright:dimension1,5,and10.Theexpectedr ateofconvergenceofthe MSEforanMCestimateisshownbythesolidblackline. Example3. Let betheunit4{dimensionalhypercube,i.e., =[0 ; 1] 4 R n .Suppose f ( )= N 4i =1 2 sin 2 i ,so R fd =1 when istheLebesguemeasure.Theone-sample Kolmogorov-Smirnovtest[ 29 ]ata5%signicancelevelindicatesthatthesampledistrib ution from 1 E +4 MCapproximationsusing N =50 uniformi.i.d.samplesisnormallydistributed. Table 3.1 showsthattheexpectedMCapproximationfromthissampledi stributioniswithin 0.1%oftheexactvalueof R fd .Inotherwords, N =50 appearstobeasucientnumber ofi.i.d.samplestoproduceMCapproximationswiththecorr ectdistributionalproperties.We comparetheseresultstomeasure-theoreticapproximation susingEq.( 3.1 )onthesamefamily of N =50 samples.Table 3.1 summarizesafewofthestatisticalquantitiescomputedfro m thesampledistributions.Clearly,themeansarebothaccura teestimatesoftheexactintegral, butthestandarddeviationoftheMCapproximationsisappro ximately150%largerthanthe standarddeviationinthemeasure-theoreticapproximatio nusingthesamesamples.Theeect ofthisincreasedvarianceontheexpectedaccuracyofanygi venapproximationisillustrated furtherbyusingthesampledistributionstoestimatethepr obabilityofachievingacertainlevel ofaccuracy.Theprobabilitythatanysinglemeasure-theore ticapproximationiswithin 10% of theexactintegralvalueisapproximately 0 : 79 ,whichisabout 71 : 5% higherthantheprobability of 0 : 46 thatanysingleMCestimatehasthesameaccuracy. 4.ErrorBoundsforSampleBasedApproximationstoIntegrals. Below,weinitially assume R n and f 2C ()isLipschitzcontinuousandintegrable.Wethendescrib ehow theresultsextendtointergalsof f overarbitrary A 2B andformoregeneralbounded, butpossiblydiscontinuous,functions f .Forevery > 0,theintegrabilityof f impliesthere existscompact 1 suchthat R n 1 j f j d< [ 4 ].Thus,wemayassumewithoutlossof generalitythat f 0outsideofsomecompactsubsetof.Instead,forsimplicit y,weassume thatdenesacompactsetcontainingthesupportof f .Itfollowsthatthecontinuity assumptionof f ensuresintegrability.Werstconsidertheproblemofesti mating R fd usingEq.( 3.1 ).Weestablishbothlocalandglobalapriorierrorboundsth atprovideinsightin

PAGE 9

DRAFT Measure-TheoreticSample-BasedIntegration 9 SampleStatistics mean st.dev. 5thpctle 10thpctle 90thpctle 95thpctle MC 0.9997 0.1647 0.7394 0.7926 1.2165 1.2816 Eq.( 3.1 ) 1.0405 0.0663 0.9282 0.9552 1.1222 1.1438 Table3.1:SomesamplestatisticsfortheMCestimatesandme asure-theoreticestimatesof R [0 ; 1] 4 N 4i =1 2 sin 2 i usingasampledistributionof1 E +4estimatescomputingusing N =50 i.i.d.uniformrandomsamplesin=[0 ; 1] 4 designinganadaptivesamplingstrategyasdiscussedinSec tion 5 andinthecontextofsolving inverseproblemsinSection 7 .Weemphasizethattheseboundsholdforanysamplebased integrationschemeandaredeterministicevenwhenthesamp lesarerandomlygenerated. Theorem4.1. Suppose R n iscompactand f isLipschitzcontinuouson .Foranyset of N samples ( i ) Ni =1 ,let f N = P Ni =1 f ( ( i ) ) V i;N ,where fV i;N g Ni =1 istheassociated Voronoitessellationimplicitlydenedbythesamples ( i ) Ni =1 .Foreach i 2f 1 ; 2 ;:::;N g Z V i;N fd Z V i;N f N d C n;f diam ( V i;N ) nk =1 c i;k ; (4.1) wheretheconstants c i;k > 0 for k 2f 1 ; 2 ;:::;n g denethehalf-lengthsalongeachaxisof thecircumscribing n -dimensionalellipsoidoftheVoronoicell V i;N and C n;f dependsonthe Lipschitzconstant L of f andisadecreasingfunctionofdimension n givenby C n;f = L n= 2 ( n 2 +1) : (4.2) Proof: Since f ( ) f ( ( i ) ) L diam( V i;N )forany 2V i;N ,standardintegralinequalitiesimmediatelygive Z V i;N fd Z V i;N f N d L diam( V i;N ) ( V i;N ) : (4.3) Thereexistsapoint ~ ( i ) =( ~ ( i ) 1 ; ~ ( i ) 2 ;:::; ~ ( i ) n ) 2V i;N ,possiblydierentfrom ( i ) ,suchthat E i ( c 1 ;c 2 ;:::;c n ):= ( =( 1 ; 2 ;:::; n ): n X k =1 ( k ~ ( i ) k ) 2 c 2k < 1 ) (4.4) denesthecircumscribingellipsoidof V i;N .Since V i;N E i ( V i;N ) n= 2 ( n 2 +1) n Y k =1 c i;k ; (4.5) andtheconclusionfollows.

PAGE 10

DRAFT 10 T.Butleret.al. Theorem4.2. Suppose R n iscompactand f isLipschitzcontinuouson .Foranyset of N samples ( i ) Ni =1 ,let f N = P Ni =1 f ( ( i ) ) V i;N ,where fV i;N g Ni =1 istheassociated Voronoitessellationimplicitlydenedbythesamples ( i ) Ni =1 ,then Z fd Z f N d C f; sup 1 i N diam ( V i;N ) ; (4.6) wheretheconstant C f; = L () hasnodependenceonthedimension n Proof: Since fV i;N g Ni =1 tessellate,itfollowsfromlinearityoftheintegralthat Z fd Z f N d N X i =1 Z V i;N fd Z V i;N f N d : (4.7) TheconclusionfollowsfromtheinequalityofEq.( 4.3 )andnotingthattheadditivityof forpairwisedisjointmeasurablesetsalsoholdsforanycou ntablecollectionsofmeasurable setswithpairwiseintersectionsofzeromeasure. ThediametersoftheVoronoicellsinEqs.( 4.1 )and( 4.6 )canbeestimatedinanumberof waysincludingexplicitconstructionoftheVoronoicellsu singDelaunaytriangulation(e.g.,see [ 19 38 ])when n issmallorbypost-processingarandomsamplingoftheVoron oicellsusing Algorithm 1 .InAlgorithm 1 ,theideaistogenerate M N i.i.d.uniform(withrespectto ) samplesin,andbynearestneighborsearches 1 bineachofthesesamplesinthe N Voronoi cells.Thenearestneighborsearchesmaybecomputedinanum berofways,andwegenerally usek-dtreesonthe N samplestomoreecientlybinthe M i.i.d.sampleswithinthe N implicitly denedVoronoicells.Theruntimeforusingk-dtreestobins uchsampleshasbeen showntobe O ( nN 1 1 =n )where n isthedimensionofthesamplespaceconsideredhere[ 32 ]. Werefertothisprocessas emulation sincethesetofsamplesbinnedinVoronoicell V i;N canbe usedasani.i.d.uniformrandomsamplewithrespectto ( V i;N )foreach i 2f 1 ; 2 ;:::;N g .We canusetheseemulatedsamplesinanumberofwaysincludinga pproximatingthevolumesof VoronoicellsviasimpleMCestimatesorestimatingthediam eterofVoronoicellsasdescribed below.Remark4.1 WhenapproximatingthevolumeweightsinEq.( 3.1 )usingemulation,itis onlynecessarytoapproximatetherelativeweightsofcerta inVoronoicells.Specically,itis onlynecessarytoobtainestimatesfor ( V i;N \ A ) = ( V j;N \ A )whenever f ( ( k ) ) 6 =0 and V k;N \ A 6 = ; for k = i;j Sincethefunction f isnotevaluatedontheemulatedsamples,wedenotethesesam plesas n ( j ) e o Mj =1 tomaketheirroleincomputationsmoreexplicit.ForVorono icell V i;N n ( j ) e o ( j )= i V i;N ,sodiam( V i;N ) sup ( j )= i; ( k )= i d v ( ; ( j ) e ; ( k ) e )and ( V i;N ) # f j : ( j )= i g M Remark4.2 If K i denotesthenumberofemulatedsamplesin V i;N ,thenestimatingdiam( V i;N ) 1 Whilethealgorithmispresentedinasimpleformwithaneste dfor-loop,theouterloopiseasilyparallelized.

PAGE 11

DRAFT Measure-TheoreticSample-BasedIntegration 11 involves O ( K 2 i )metriccomputationsfollowedbyalinearsearchthatisals o O ( K 2 i ).Since diam( V i;N ) 2sup 2V i;N d v ( ; ( i ) ),wecanapproximatelooserboundswithasmallerarray ofdistancesinvolvingexactly K i metriccomputationsfollowedbyalinearsearchthatis O ( K i ). Algorithm1: Voronoisampleemulation Let ( i ) Ni =1 beanysetofsamplesandlet fV i;N g Ni =1 denotetheassociated VoronoitessellationfromDenition 3.1 For M N ,let n ( j ) e o Mj =1 denoteasetofuniform(withrespectto )i.i.d. randomsamples. for j =1 ;:::;M do for i =1 ;:::;N do if ( j ) e 2V i;N then ( j )= i end end end Itismorediculttoestimatetheconstants c i;k inEq.( 4.1 )usingemulationsinceitis azeroprobabilityeventthatanytwoemulatedsampleswillh aveanycoordinatesagree,i.e., almostsurelynotwopointslieonalineparalleltoacoordin ateaxis.However,thepositive constants c i;k areeachboundedby 1 2 diam( V i;N ).Inotherwords,replacingthecircumscribing n -dimensionalellipsoidbythecircumscribing n -dimensionalhypersphereyieldsthebound ofEq.( 4.8 )inthefollowingCorollarytoTheorem 4.1 ,whichcanalsobeusedtoprove Theorem 4.2 .TheboundofEq.( 4.9 )followsimmediatelyfromthefactthatdiam( V i;N ) 2sup 2V i;N d v ( ; ( i ) )orbyusingacircumscribing n -dimensionalhypersphereof V i;N with centerrestrictedtothepoint ( i ) .Inpractice,weusetheboundofEq.( 4.9 )withemulation sinceitisthemostcomputationallyecientboundtocomput e. Corollary4.1. Suppose R n iscompactand f isLipschitzcontinuous.Foranysetof N samples ( i ) Ni =1 ,let f N = P Ni =1 f ( ( i ) ) V i;N ,where fV i;N g Ni =1 istheassociatedVoronoi tessellationimplicitlydenedbythesamples ( i ) Ni =1 .Foreach i 2f 1 ; 2 ;:::;N g ,wehave thefollowingbounds, Z V i;N fd Z V i;N f N d C n;f [ diam ( V i;N )] n +1 ; (4.8) and Z V i;N fd Z V i;N f N d C n;f [2sup 2V i;N d v ( ; ( i ) )] n +1 ; (4.9) where C n;f dependsontheLipschitzconstant L of f andisadecreasingfunctionofdimension

PAGE 12

DRAFT 12 T.Butleret.al. n givenby C n;f = L n= 2 2 n ( n 2 +1) : (4.10) Thenalerrorboundresultforthissectionprovidestighte rlocalboundsinthecasewhere f 2C 1 ().Inthiscase,theconstants C n;f inpreviouslocalerrorbounds,whichareconstant over,nowdependonalocalLipschitzconstantdenedoneac h V i;N Theorem4.3. Suppose R n iscompactand f 2C 1 () .Theconstant C n;f inEq.( 4.8 ) andEq.( 4.9 )canbereplacedby C i;n;f thatdependsonlocalboundsof f @ j f g 1 j n andisa decreasingfunctionofdimension n givenby C i;n;f = n= 2 2 n ( n 2 +1) sup 2V i;N kr f ( ) k ; (4.11) where kk denotesthe2-normon R n .Moreover, C i;n;f C n;f forevery i 2f 1 ; 2 ;:::;N g Proof: Let :=( 1 ; 2 ;:::; n )denoteamulti-index,thenTaylor'stheoremandlinearity oftheintegralimplies Z fd Z f N d = Z V i;N 8<: X j j 1 Z 1 0 @ f ( ( i ) + t ( ( i ) )) dt ( ( i ) ) 9=; d : (4.12) Theconclusionfollowsfromthisequalityandthefactthatt hesmallestlocalLipschitzconstant of f over V i;N isdenedbysup 2V i;N kr f ( ) k Remark4.3 Theaboveresultsalsoapplyto R A fd wheretheonlychangetothebounds isintheglobalboundEq.( 4.6 )ofTheorem 4.2 where C f; isreplacedby C f;A = L ( A ). Remark4.4 Itiseasytoseethatasimplevariantoftheaboveresultsals oappliestobounded butdiscontinuous f ,e.g.,when f isitselfasimplefunction.Inthiscase,forthelocalerror bounds,replacetheLipschitzconstantby L =sup ;r 2V i;N j f ( ) f ( r ) j .Fortheglobalerror boundtakethemaximumofallsuch L computedthisway. 5.Adaptivesamplingstrategyforintegralapproximations. Here,wedescribehowto utilizetheerrorestimatesabovetoguidetheselectionofa dditionalsamplesreningthe integralestimates.Forasetof N samples ( i ) Ni =1 andsimplefunctionapproximation f N = P Ni =1 f ( ( i ) ) V i;N ,let f E i;N g Ni =1 denotetheerrorboundsofEq.( 4.9 )associatedwith f N .Givenasample 2 suchthat 6 = ( i ) for1 i N ,let ( N +1) := ( j ) N +1 j =1 := ( i ) Ni =1 [ ( N +1) ,and f N +1 = P N +1 j =1 f ( ( j ) ) V j;N +1 .Let f E i;N +1 g N +1 i =1 denotethe errorboundsofEq.( 4.9 )associatedwith f N +1 .Notethat V i;N +1 V i;N for1 i N ,i.e., theadditionof ( N +1) implicitlydenesarenementoftheVoronoitessellation. Consequently, E i;N +1 E i;N for1 i N and E N +1 ;N +1 max 1 i N E i;N .Thechoiceof ( N +1) = determineswhich(ifany)errorboundsarereduced.Thus,we write E i;N +1 ( )tomakeexplicit

PAGE 13

DRAFT Measure-TheoreticSample-BasedIntegration 13 thedependenceof E i;N +1 onthechoiceof ( N +1) = for1 i N +1.Let I beasubset ofindicesof f 1 ; 2 ;:::;N g .Foraspecied I andassociated f E i;N g i 2I ,wedenetheoptimal choiceof ( N +1) asthesolutiontothefollowingoptimizationproblem ( N +1) =argmin ( E N +1 ;N +1 ( )+ X i 2I E i;N +1 ( ) ) : (5.1) Thesolution ( N +1) ofEq.( 5.1 )maybeapproximatedfromasetofemulatedsampleswithin [ i 2I V i;N Theproblemofidentifyingthenext J optimalsamplescaneitherbedonesequentiallyby iterativelysolvingEq.( 5.1 )(possiblywithadierentsetofindices I chosenateachiteration), orasasinglebatchof J samplessolvingthefollowingoptimizationproblem n ( N + j ) o Jj =1 =argmin 8<: J X j =1 E N + j;N + J ( )+ X i 2I E i;N + J ( ) 9=; ; (5.2) where denotesthearrayoflength J ofsamples ( N + j ) Jj =1 .ThesolutiontoEq.( 5.2 )may produceadierentsetofsamples ( N + j ) Jj =1 thaniterativelysolvingEq.( 5.1 ) J times. Remark5.1 Theerrorboundsusedtodenetheoptimizationproblemsabo vemaybemodiedtousetheconstant C i;n;f fromEq.( 4.11 )ifderivativeinformationon f isavailableas discussedinTheorem 4.3 .Thisisnotstudiedinthisworksinceourmainnumericalres ults focusonMonteCarlobasedapproximationsonmodelsdevelop edwithoutadjoints.However, theuseof C i;n;f hasthepotentialtomaketheadaptiveapproachmoreecient sincetheerror boundsarethendenedbyaweightingofthegeometricfeatur esofthepartitioningbythe localsensitivityofthefunction. Intheexamplebelow,weuseemulatedsamplesfromspeciedc ollectionsofVoronoicells thataremarkedforrenementusingalocalerrorbound.Weap proximate(sub-)optimal solutionstoEq.( 5.2 )inparallelusingemulatedsampleswithineachVoronoicel landsolving Eq.( 5.1 )simultaneouslyforeachofthemarkedVoronoicellsindivi dually.InSection 8.1 weuseasimilarapproachforreningtheapproximationsofa predictedexpectedvalueof infectedindividualsusinganepidemicmodelwheredim()= 15. Example4. FromExample 3 ,eachintegralestimateisrenedinthefollowingways.For theestimatesusingEq.( 3.1 ),auniquesetof 1 E +4 emulatedsamplesisusedtocompute boththeintegralestimateaswellasthelocalerrorboundso fEq.( 4.9 ).Usingtheseerror boundsforeachestimate,atotalof10Voronoicellsaremark edforrenement.Theemulated samplesareusedtoapproximatelysolveEq.( 5.1 )foreachofthemarkedVoronoicellsto simultaneouslyapproximatethesolutionofEq( 5.2 ).Then,Eq.( 3.1 )isre-computedusing the10newadditionalsamples(foratotalof N =60 samples)andanewsetof 1 E +4 emulatedsamples.Themeanandstandarddeviationofthesere nedestimatesare1.0106 and0.0448,respectively.Inotherwords,themeanerrorisre ducedbyabout75%andthe standarddeviationisreducedbyabout33%.Furthermore,th eprobabilityofbeingwithin

PAGE 14

DRAFT 14 T.Butleret.al. 10%oftheactualintegralvalueisincreasedfromapproxima tely79%to96.7%withthese renedmeasure-theoreticestimates.Alternatively,fore achMCestimate,wegeneratean additional10uniformi.i.d.samplestorenetheassociate dMCestimate.Themeanofthe sampledistributionisunchanged,butthestandarddeviati onisreducedbyapproximately8.5% resultingintheprobabilityofproducinganestimatewithi n10%oftheexactvalueincreasing fromapproximately46%to49%usingtherenedMCestimates. 6.Solutionstothestochasticinverseproblem. Here,webrieryreviewtheexistence anduniquenessofsolutionstothemeasure-theoreticstoch asticinverseproblemdescribedin Section 2 .Foramorethoroughpresentationincludingproofsofthese results,theinterested readershouldreferto[ 5 7 8 9 ].InSection 7 ,wedescribethesamplebasedapproximationsof thesolution P tothestochasticinverseproblemandusethesubsequentpre dictionproblem R A f ( ) dP tomotivateadaptivesamplingstrategiesforreducingerro rsinthecomputations of P Recall Q : !D isassumedtobeapiecewisesmoothmapbetweenmeasurespace s ( ; B ; )and( D ; B D ; D ).While Q ( )isawelldenedvaluein D foreach 2 Q 1 isgenerallyaset-valuedfunctionthatmapsindividualpoi ntsin D onto generalizedcontours existingaspiecewisedenedmanifoldsinthatarethepreimages(orbers)ofthemap Q Thisimpliesthereexistsanequivalencerelationonwhere twopointsinareconsidered equivalentiftheyexistonthesamegeneralizedcontourand thespaceofequivalenceclasses ismeasurable[ 8 9 ].Denotethismeasurespaceofequivalenceclassesas( L ; B L ; L )where eachpointin L correspondstoauniquegeneralizedcontourin.Thismeasu respacemaybe representedexplicitlyinbyapiecewisecontinuousindex ingmanifold,calleda transverse parameterization ,deningabijectionbetween D andthegeneralizedcontours[ 8 ].Itisnot necessarytoexplicitlyconstructatransverseparameteri zationtoapproximate P [ 5 8 ],but thismeasurespaceisusefulindescribingthetheoreticala ndapproximatesolutions.The explicitrepresentationof( L ; B L )indenesacontour algebra C B on.Wecall eventsin C contourevents .Byconstruction,given P D on( D ; B D ),thereisaunique P L on( ; C )[ 8 ].However,thegoalistodeneaprobabilitymeasure P onthemeasurable space( ; B )asdescribedinSection 2 inordertocomputepredictionsgenerallyoftheform R A f ( ) dP .ThisrequiresanapplicationoftheDisintegrationTheore m[ 15 8 9 ]toprove thefollowingtheorem. Theorem6.1. Let ( ; B ) beameasurablespace.Assumethat P isaprobabilitymeasure on ( ; B ) .Thereexistsafamilyofconditionalprobabilitymeasures f P ` g on f ( C ` ; B C ` ) g givingthedisintegration, P ( A )= Z L ( A ) Z 1 L ( ` ) \ A dP ` ( ) dP L ( ` ) ; 8 A 2B : (6.1) Here, L : !L denotesaprojectionmap. Thus,anyprobabilitymeasureon( ; B )canbedecomposedintoaforminvolvinga probabilitymeasureon( L ; B L )uniquelydenedby P D andprobabilitymeasuresoneach measurablegeneralizedcontourspace( C ` ; B C ` )denedbytheconditionalprobabilities P ` Theconditionalprobabilitymeasureson f ( C ` ; B C ` ) g cannotbedeterminedbyobservationsof Q ( ) 2D .Wefollow[ 8 9 ]andadoptwhatisreferredtoasthe standardAnsatz determined

PAGE 15

DRAFT Measure-TheoreticSample-BasedIntegration 15 bythedisintegrationofthevolumemeasure tocomputeprobabilitiesofeventsinsideofa contourevent.ThestandardAnsatzisgivenby P ` = C ` = C ` ( C ` ) ; 8 ` 2L ; (6.2) where C ` isthedisintegratedvolumemeasureonthegeneralizedcont our C ` NotethatthestandardAnsatzcanbeusedevenwhenisnotcom pactaslongas () < 1 .TheapproximationmethodandresultingsamplingAlgorith m 2 (seeSection 7 ) canbeeasilymodiedforanyAnsatz.See[ 8 ]formoredetailsandtheoryregardinggeneral choicesoftheAnsatz.CombininganAnsatzwiththeDisinteg rationTheoremgivesaunique solutiontothestochasticinverseproblemasaprobability measure P denedon( ; B ). 7.Approximatingstochasticinversesolutions. Thefundamentalapproximationissues ofanymeasurearetheapproximationofeventsinthevarious algebras[ 9 ].Here,we discusstheeventapproximationsandconsideranewadaptiv esamplingalgorithmbasedon theanalysisofSection 4 foracertainsubclassofgoal-orientedinverseproblems. 7.1.Briefreviewofapproximations. Webeginwithafewdenitionstomakesenseofthe typesofeventsandsamplingschemesforwhichwecandiscuss convergenceoftheapproximate solutiontothestochasticinverseproblem. Denition7.1. Given ( i ) Ni =1 implicitlydeningtheVoronoitessellation fV i;N g Ni =1 and A 2B ,wesaythat A N := [ f j : ( j ) 2 A g V j;N isthe Voronoicoverageof A Denition7.2. Arulefordeningany N samples ( j ) Nj =1 iscalled B -consistent if ( A 4 A N ) 0 as N !1 ; 8 A 2B ; s.t. ( @A )=0 : Denition7.3. Given ( i ) Ni =1 ,associatedVoronoitessellation fV i;N g Ni =1 ,andmeasure P on ( ; B ) .Let ~ P ;N denotethe countingprobabilitymeasure (orsimply counting measure )on ( ; B ) denedby ~ P ;N ( A ):= N X i =1 P ( V i;N ) f ( i ) g ( A ) : Notethat ~ P ;N issimplyameasureofpointmassesateachsamplefrom ( i ) Ni =1 ,and thiscanbeusedtoestimatetheprobabilityof any A 2B .However,wecanonlyprove convergencetotheexactprobabilitywhen ( @A )=0[ 9 ]. Thesolutiontothestochasticinverseproblem P ,oratleastthevaluesof P ( V i;N ), oftenmustbeestimatedinordertodenethecountingmeasur e.Algorithm 2 describesone approachforapproximatingthesevalues. InAlgorithm 2 ,if V i = () =N ,thenthiscanbeinterpretedasusingastandardMC approximationtomeasuresofcontoureventsalongwiththes tandardAnsatztoestimate

PAGE 16

DRAFT 16 T.Butleret.al. Algorithm2: NumericalApproximationoftheInverseDensity Choosepoints ( i ) Ni =1 froma B -consistentruleimplicitlydeningthepartition fV i;N g Ni =1 of. Assignvalues Q i = Q ( ( i ) )forpoints ( i ) i =1 ; N Chooseadiscretizationpartition f I j g Mj =1 D of D Computeapproximations P D ;j P D ( I j )= R I j D d D j =1 ; ;M Let C j = f i : Q i 2 I j g j =1 ; ;M Let O i = f j : Q i 2 I j g i =1 ; N Let V i approximate ( V i;N ), i =1 ; ;N for i =1 ;:::;N do Set P ;N ( V i;N )= V i P k 2C O i V k P D ; O i end P ( V i;N )with P ;N ( V i;N ).Alternatively,wemayuseemulationasdescribedinSecti on 4 to computeimprovedestimatesof V i ( V i;N ). Insteadofusingthecountingmeasure ~ P ;N ,wemayalternativelyusetheapproximate measure P ;N computedusingAlgorithm 2 directlywhenestimating P ( A ).TheRadonNikodymderivativefor P ;N isgivenbythesimplefunction ;N ( ):= N X i =1 P ;N ( V i;N ) ( V i;N ) V i;N ( ) : (7.1) Theconsequenceisthat R A f ( ) dP R A f ( ) ;N ( ) d ,whichgenerallyrequirestheuse ofemulatedsamplestoapproximate.Remark7.1 NotethatusingEq.( 7.1 )tocomputeestimatesof R A f ( ) dP producesestimatesoftheformgiveninEq.( 3.1 )wherethemeasure isreplacedby P .Itisthenstraightforwardtodescribethemeasure-theoreticapproximatione rrorsinestimatesof R A f ( ) dP usingEq.( 7.1 ) 2 .Wethereforerestrictthemotivationanddescriptionofth eadaptivesamplingschemebelowtoreducingerrorsinEq.( 7.1 ). 7.2.Anadaptivesamplingstrategy. UsingEq.( 7.1 )with f ( )= A ( )forsomespecied A 2B ,wehave Z f ( ) dP Z f ( ) dP ;N = N X i =1 P ;N ( V i;N ) ( A \V i;N ) ( V i;N ) : (7.2) NotethattherighthandsideofEq.( 7.1 )istheexactvalueoftheintegral R f ( ) dP ;N 2 Thecountingmeasurehasadditionalapproximationerrorfr omusingthecharacteristicfunctionsonsingletonsofthesamplesinsteadoftheassociatedVoronoicel ls.

PAGE 17

DRAFT Measure-TheoreticSample-BasedIntegration 17 Whensolvingthestochasticinverseproblem,weareoftenin terestedinidentifyingand estimatingparticularregionsofgeneralizedcontours,e. g.,thegeneralizedcontoureventof highestprobabilityand/orcorrespondingtoaparticularo utputeventofphysicalimportance suchasafailure,threshold,orrareevent([ 35 36 ]areinterestingpapersthatusesurrogate modelsforthispurpose).Forthesakeofsimplicity,weassu methegoalistoaccurately estimate P ( Q 1 ( I ))with P ;N ( Q 1 ( I ))foraxedbutarbitrary I 2B D .Assuming I = I j forsome I j inAlgorithm 2 ,thentheaccuracyofthisestimatedependsentirelyuponth e accuracyoftheVoronoicoverageof Q 1 ( I j ) 3 asshownbelow.Let A j;M := Q 1 ( I j )and A j;M;N denotetheVoronoicoverageof A j;M .Let f = A j;M and f N = A j;M;N .Werewrite theproblemas P ( A j;M )= Z f ( ) dP Z fdP ;N = N X i =1 P ;N ( V i;N ) ( A j;M \V i;N ) ( V i;N ) : (7.3) Notethat R fdP ;N ontheright-handsideofEq.( 7.3 )isoftenestimatedusing R f N dP ;N i.e., A j;M isreplacedby A j;M;N inthesum.Weinterprettheerrorsinthisgoal-oriented inverseprobleminthecontextoftheerrorestimatesinSect ion 4 .FromRemark 4 and Eq.( 4.9 ),itfollowsthatlocalerrorsarenon-zerowhenever ( f Q 1 ( I ) \V i;N g4V i;N ) > 0. Thus,thevalueof ( A j;M 4 A j;M;N )describestheaccuracyoftheestimate.Forexample,if ( A j;M 4 A j;M;N )=0,thereexistsasetofindices If 1 ; 2 ;:::;N g anda Z2B withzero -measure(i.e., Z isa -nullset)suchthat A j;M;N = [ i 2I V i;N and A j;M = A j;M;N [Z .In thiscase,itfollowsthat P ( A j;M )= P Ni =1 P ;N ( V i;N ) ( A j;M;N \V i;N ) ( V i;N ) 4 Remark7.2 Aninterestingconsequenceisthatwhenthecontourevents Q 1 ( I j )areconvex forall1 j M ,thenthereexistsasetof M samples ( j ) Mj =1 suchthat V j;N = Q 1 ( I j ) forall1 j M .Forexample,if Q : !D islinear,andthepartition f I j g Mj =1 2B D hasthepropertythateach I j isconvex,then P ( Q 1 ( I j ))= P ;N ( Q 1 ( I j )).Thisistrue eveninthecasewheredim()=+ 1 .Inthegeneralcase,forany > 0,if Q isnon-linear andforeachcontourevent Q 1 ( I j )thereexistsconvexevents f C k;j g K j k =1 2B suchthat ( Q 1 ( I j ) 4 n [ K j k =1 C k;j o ) < and n f C k;j g K j k =1 o Mj =1 partitions,thenthereexistsasetof N = P Jj =1 K j samples ( i ) Ni =1 suchthat P ( Q 1 ( I j )) P ;N ( Q 1 ( I j )) < .Determining this\optimal"setofsamplesinrequiresadierentsamplin gstrategythandescribedhere andisthesubjectoffuturework. Weuseanadaptivesamplingstrategytoimprovetheaccuracy ofestimatedvolumesof speciccontoureventsdenedimplicitlybyidentifyingth eassociatedoutputeventsandusing thisinformationtoadjustthesamplinginsitu.Thissampli ngstrategycanbeinterpretedas proceedingintwostages.Thegoaloftherststageistoloca tethecontoureventin.The goalofthesecondstageistosamplefromthecontoureventin ordertoreducethe -error 3 Wecanalsoreplace I j byaunionof I j 's. 4 Notethatthisalsoimplies P ( A j;M )= ~ P ;N ( A j;M ),i.e.,thecountingmeasureisexactinthiscase.

PAGE 18

DRAFT 18 T.Butleret.al. intheVoronoicoverage.Therststageofsamplingmaybedon eeither(pseudo-)randomly ordeterministically.Forexample,wemayuseatransitionp robabilitykernelresultingina methodsimilartoMCMCsampling(e.g.,see[ 2 ]forsomeinterestingideasonsamplingsubsets inhighdimensionalspaceswithMCMCtypesamplingschemes) .When Q : !D issmooth and I 2B D isconvex 5 ,deterministicapproachessuchasmulti-variateNewton's method maybeusedtolocatethecontoureventin B .Inthenumericalexamplesbelow,weusea probability-basedadaptivesamplerforlocatingtheconto urevent Q 1 ( I )thatwasinitially describedby[ 24 ].Oncethecontoureventhasbeenlocated,wetypicallyusea transition probabilitykerneltogeneraterandomsampleswithin Q 1 ( I )andensurethattheoverall samplingschemeis B -consistent. 8.NumericalExamples.8.1.A15-DimensionalEpidemicModelExample.TheModel. TheSIRmodelisawell-studiedcompartmentalmodelinepide miologythat stratiesthepopulationintothreeclassesinordertomode lthecomplexdynamicsassociated withaninfectiousdiseaseoutbreak[ 31 ].The\S"classrepresentsindividualssusceptibleto infection,the\I"classaretheinfectedindividualscapab leofspreadingthedisease,andthe \R"classisforallindividualsthathaverecoveredorareim munetothedisease(orotherwise removedfromthesusceptibleclass,e.g.,throughvaccinat ionsorquarantine).TheMSEIRS modelgeneralizesthecommonSIRepidemicmodeltoincludeg roupsofinfantsprotected bymaternalantibodies(the\M"class)andgroupsofexposed andlatentinfectedbutnot infectious(the\E"class)[ 27 ].Thecouplednonlinearsystemofdierentialequationsde ning thismodelisgivenby 8>>>>>><>>>>>>: dM dt = B ( S + E + I + R ) ( + M ) M dS dt = M SI ( G + ) S + fR dE dt = SI ( + G ) E dI dt = E ( r + I + G ) I dR dt = rI ( G + f ) R + S (8.1) Sincevirusesmutateovertimeandpopulationdatarequires acompletecensuscountthatis ofteninfeasible,thecoecientsandinitialpopulationof eachclassinEq.( 8.1 )aresubject touncertaintyduringaninfectiousdiseaseoutbreak[ 11 ].Therefore,weconsiderboththe coecientsandinitialconditionsasuncertainmodelparam etersinthisexample.Wedenethe parameterdomainastheCartesianproductoftheintervals foreachparametersummarized inTable 8.1 Wenumericallysolvethemodeluntilanaltimeofsixweeksu singtheDormand-Prince methodcodedwithintheode45functioninMatlab,whichimpl ementsavariablestepRungeKuttamethodbasedonfourth-ordererrorestimates[ 18 ].Todeneareferenceintegralvalue tocomparetheadaptivesamplingapproachforapproximatin gprobabilisticpredictions,we use2 E +7i.i.d.uniformrandomsamplesintocomputeaMCestimate 5 orcanbedenedbytheunionofconvexeventsin B D

PAGE 19

DRAFT Measure-TheoreticSample-BasedIntegration 19 B avg.birthrate [2 : 72 E 4 ; 3 : 04 E 4] [week] 1 avg.temporaryimmunity [1 = 12 ; 1 = 4] [week] 1 M avg.infantdeathrate [4 E 3 ; 6 E 3] [week] 1 [1 E +6pop.] 1 contact/infectivityrate [1 : 92 E 3 ; 3 : 85 E 3] [week] 1 G avg.generaldeathrate [2 : 4 E 4 ; 2 : 72 E 4] [week] 1 1 = avg.infectiontime [0 : 571 ; 1] [week] 1 I avg.infecteddeathrate [4 : 81 E 6 ; 2 : 11 E 5] [week] 1 1 =r avg.recoverytime [0 : 7 ; 2 : 33] [week] 1 f avg.lossofimmunityrate [0 : 125 ; 0 : 25] [week] 1 avg.immunizationrate [0 : 015 ; 0 : 0375] [week] 1 M 0 initialinfants [2 : 5 ; 3 : 5] [1 E +6pop.] S 0 initialsusceptibles [260 ; 275] [1 E +6pop.] E 0 initialexposed [0 : 01 ; 0 : 5] [1 E +6pop.] I 0 initialinfected [0 : 1 ; 4] [1 E +6pop.] R 0 initialrecovered/immunized [10 ; 20] [1 E +6pop.] Table8.1:Uncertainparametersandinitialconditionsand theirintervalboundsinthe MSEIRSmodelgivenbyEq. 8.1 Aforwardprediction. Weconsidertheproblemofpredictingtheexpectednumberof infectedindividualsattheendofsixweeksforanygivenoutbr eakassumingthat isuniformly distributedwithin,i.e., E ( I (6; ))= 1 () R I (6; ) d ,where denotestheLebesgue measure.ThereferenceexpectedvaluecomputedfromtheMCe stimateof2 E +7i.i.d.uniform randomsamplesinis E ( I (6; )) 282 ; 034. Tosimulatethecasewhereintegralestimatesarecomputedu singasmallnumberof samples,weusesetsof1 E +2i.i.d.uniformrandomsamplesdenotedby ( i ) 100i =1 tocompare standardMCestimatestomeasure-theoreticapproximation susingEq.( 3.1 )onthesamesets ofsamples.Specically,wecomputeasampledistributiono f1 E +3MCestimatesof E ( I (6; )) whereeachMCestimateiscomputedusingadierentsetof ( i ) 100i =1 in.Foreachsetof ( i ) 100i =1 ,weuse1 E +5emulatedsamples n ( j ) e o 1 E +5 j =1 andEq.( 3.1 )tocomputeanassociated measure-theoreticapproximationto E ( I (6; )).EachMCestimateandtheassociatedEq.( 3.1 ) estimateissubsequentlyrenedbyusing50additionalsamp les ( i ) 150i =101 intoestimate E ( I (6; )).ForeachoftheMCestimates, ( i ) 150i =101 isasetofi.i.d.uniformrandomsamples in.ForeachoftheEq.( 3.1 )approximations,weuseEq.( 4.8 ) 6 tomarkthe50Voronoi cellswiththelargestcomputederrorboundsandapproximat elysolveEq.( 5.2 )withemulated samplesinthesamewayasdescribedinExample 4 Weareprimarilyinterestedintheaccuracyofanysingleest imateanditssubsequent renement.Thus,weusethesampledistributionstocompute andcomparetheapproximate probabilitiesofanysingleMCestimateormeasure-theoret icestimateusingEq.( 3.1 )(ortheir 6 where C n;f isaxedbutunknownconstantdependingon I (6; )

PAGE 20

DRAFT 20 T.Butleret.al. TypeofEstimate Prob.of5%accuracy Prob.of10%accuracy MC 0.248 0.474 Eq.( 3.1 ) 0.228 0.458 MCrened 0.287 0.561 Eq.( 3.1 )rened 0.330 0.621 Table8.2:Thetoptworowsshowtheprobabilityofanysingle MCestimateormeasuretheoreticestimateusingEq.( 3.1 )beingwithin5%and10%ofthereferencevalue E ( I (6; )) 282 ; 034.Thebottomtworowsshowtheseprobabilitiesiftheesti matesarerenedwithan additional50samples.renements)arewithinaspeciederrortolerancesofthere ferencevalue E ( I (6; )) 282 ; 034. Foranysetof ( i ) 100i =1 i.i.d.uniformrandomsamples,anMCestimateismorelikely to beaccuratethanthemeasure-theoreticapproximations(se ethetoptworowsofTable 8.2 ). Specically,theprobabilitythatanysingleMCestimateis accuratetowithin5%(resp.,10%) ofthereferencevalueisapproximately8.8%(resp.,3.5%)h igherthantheprobabilitythat theassociatedEq.( 3.1 )approximationisaccuratetowithinthesesametolerances .However, reningtheEq.( 3.1 )approximationsby(approximately)solvingEq.( 5.2 )withemulated samplesleadstoestimatesthataremorelikelytobewithint heseerrortolerancesthanrening theMCestimateswithi.i.d.uniformrandomsamples(seethe bottomtworowsofTable 8.2 ). Theprobabilitythatanysinglemeasure-theoreticapproxi mationiswithin5%(resp.,10%) ofthereferencevalueisapproximately15%(resp.,11%)hig herthantheprobabilitythana singlerenedMCestimateisaccuratetowithinthesesameto lerances. 8.2.ShallowWaterEquationModelandManning'sn.TheModel. Theshallowwaterequations(SWEs)arecommonlyusedtomode lhydrodynamicsystemswithlargehorizontallengthscalesrelative totheverticallengthscales.The SWEscanbederivedfromtheincompressibleNavier-Stokese quationviadepthintegration withahydrostaticpressure[ 37 34 ].Let H = + h denotethetotalwatercolumnheight where and h arethefree-surfaceelevationandthebathymetricdepth,r espectively,relative toadatum.Then,thecontinuityequationisgivenby @H @t + @Q x @x + @Q y @y =0(8.2)

PAGE 21

DRAFT Measure-TheoreticSample-BasedIntegration 21 where Q x = UH Q y = VH aretheruxperunitlengthintheinthe x;y -directions,respectively,and U;V arethedepth-averagedvelocities.Themomentumequations are @Q x @t + @UQ x @x + @VQ x @y fQ y = gH @ [ +( P s =g 0 ) ] @x + sx bx 0 + M x D x B x @Q y @t + @UQ y @y + @VQ y @x + fQ x = gH @ [ +( P s =g 0 ) ] @y + sy by 0 + M y D y B y (8.3) where f istheCoriolisparameter, g isgravity, P s istheatmosphericpressureatthefree surface, 0 isthereferencedensityofwater,and istheNewtonianequilibriumtidalpotential.Theterms M ( ) arethevertically-integratedlateralstressgradients, D ( ) aremomentum dispersion, s ( ) aretheimposedsurfacestresses,andnally b ( ) arethebottomstresscomponents.Thebottomstresstermsaredenedusingaquadrati c(orlinear)draglaw bx 0 = C f U j U j = n 2 gU j U j H 1 = 3 ; by 0 = C f V j U j = n 2 gV j U j H 1 = 3 (8.4) where n denotestheManning's n roughnesscoecientfromtheGauckler-Manning-Strickler formula.For H sucientlysmall C f issettoaconstanttopreventdivisionbyzero.Dueto thisformulation,inregionswhere H issmall(e.g.,inestuaries,tidalrats,shallowchannels, etc.)thebottomstressisespeciallysensitivetoManning' scoecient.TheManning's n coecientisahighlyvaryingspatialparameterthatisofte ndenedonasub-gridscale. DetailedeldmeasurementscanbeusedtodetermineManning 'scoecientforaspecic geographiclocation[ 1 12 3 ].Unfortunately,usingeldmeasurementstoestimateMann ing's coecientatanescaleoverlargephysicaldomainsisextre melycostprohibitive. ForthisreasonwefocusonestimatingManning'scoecientf orahydrodynamicmodel ofanidealizedinletwithslopedbathymetry.Wesolveahydr odynamicmodeloftheSWEs ontheidealizedinletusingtheADCIRC(ADvancedCIRCulati on)modelforcoastaland estuarinewaters.ADCIRChasbeenthoroughlyveriedandva lidatedagainstvarioustest problemsandhasbeenusedfornumerouscoastalengineering studies,nottheleastofwhich areseveralhurricanehindcastsincludingHurricanesBets y(1965),Ivan(2004),Dennis(2004), Katrina(2005),Rita(2005),Gustav(2008),andIke(2008)[ 6 16 30 28 17 ].ADCIRCuses anite-elementspatialdiscretizationandanite-dieren cetemporaldiscretization[ 37 ]. TheInverseProblem. Werefertheinterestedreaderto[ 10 ]foranin-depthdescriptionof theinverseproblemwhichwewillsummarizehereascontextf orinterpretingsamplebased numericalintegrationandtodemonstrateagoal-orientedp robabilitybasedadaptivesampling strategy[ 24 ].Thenumericalsolutionstotheinverseproblemwerecompu tedusingtheopensourcepackageBET[ 23 ].Weconsideranidealizedinletwithslopedbathymetryand an earthen-jettyextendingpartwayintothedomain(seeFigur e 8.1 ).Theleftboundaryisan openoceanboundarywithan M 2 tidalamplitudeof1.2[ m 2 =s ]enteringthedomainnormal totheboundary.Theremainingboundaryisalandboundarywi thnonormalrowandno slip.

PAGE 22

DRAFT 22 T.Butleret.al. Figure8.1:Bathymetry(in[m])fortheidealizedinletwith anearthenjetty.Thetwowhite circlesindicatethespatiallocationsoftheQoI. Wedenetheparameterdomaininthefollowingway.Weassume thatthelandcoveron therighthandsideoftheinletisdominatedbytwodierentty pesoflandcoverdesignated as\wetland"and\forest",respectively.Randomdataisgen eratedatthesubgridlevelto simulatethepixelationandclassicationoflandcovertyp esusingahighresolutionareal photograph.Followingthecommunitystandardofupscaling thissubgriddataasdetailedin [ 10 ],wedeneabasisofspatiallyheterogeneousfunctionswho selinearcombinationdenes theManning's n eldontheniteelementmesh.Here,welet=[0 : 07 ; 0 : 15] [0 : 1 ; 0 : 2] where 1 and 2 aretheManning's n coecientsforthelandclassicationsof\wetland"and \forest",respectively.InFigure 8.2 ,weschematicallyshowhowalinearcombinationofthe basisfunctionsusedinthisstudyproduceatypicalManning 's n eld.Finally,wedenethe QoIvectoras Q ( )=( q 1 ( ) ;q 2 ( ))wherethecomponentsarethemaximumwaterelevation recordedat x;y =(1900[m],1200[m])and(1900[m],-600[m]),respectively (seeFigure 8.1 ). Here,weconsidertheoverallgoalofsolvingthestochastic inverseproblemasapproximatingtheprobabilityofaspecicevent: A = Q 1 ( E ) ;E 2B D .Theevent E mayrepresent arareorthresholdevent,andthegoalistodeterminetheinp utsthatproducethisevent.To thisend,wedene E 2B D asarectanglecenteredatsomereferencevalue Q ( ref )withsides scaledbyafractionofthelengthof q i ()for i =1 ; 2.Inthecontextofthestochasticinverse problem,weseektoapproximate where D isuniformon E andsupp( D )= E 2B D Sincesupp( D )= E 2B D weonlyneedtoapproximate on A = Q 1 ( E ).InAlgorithm 3 weuseatransitionprobabilitykernelsimilartoMCMCsampl ingtorstlocate A andthento randomlygeneratesampleswithinAaspreviouslydiscussed inSection 7 .Thus,Algorithm 3 generates B -consistentsamples.InAlgorithm 3 weset B ( s j )tobe R ( s j ) \ where R ( s j ) aregeneralizedrectanglessimilartocenteredattheprev ioussample( ( i 1 ;j ) )andscaled by s j .Thetotalnumberofsamples ( i;j ) i;j is N M [ 24 ]. Forthisexample,weuse K =2, D 1 = E;D 2 = Dn E p 1 =1,and p 2 =0inAlgorithm 3 inordertoadaptivelygenerateasetof1 E +4samples.Wedene E 2B D astherectangle centeredat Q ( ref )= Q ((0 : 0781 ; 0 : 168))withsides15%ofthelengthsof q i ()for i =1 ; 2.In thetwoplotsofFigure 8.3 wecomparetheapproximationof usingthe1 E +4adaptively generatedsamplestoanapproximationof usingasetof121 2 =1 : 4641 E +4samples

PAGE 23

DRAFT Measure-TheoreticSample-BasedIntegration 23 += Figure8.2:OntheleftarethebasisfunctionsfortheMannin g's n eldcontributionsfrom theseparatelandcovertypes.AtypicalManning's n eldresultingfromasampleinis shownontheright.onaregulargrid.Akeyobservationisthattheprobabilitym assiscenteredmoreclosely totheactualreferencevalueusingtheadaptivesampleswhe reastheregulargridsamples produceamoreskewedinversedensity.Despiteusingapprox imately32%lesssamplesoverall (andthus32%fewermodelevaluations),47.03%oftheadapti vesamplesbelongto A = Q 1 ( E )comparedtojust4.576%oftheuniformsamples(i.e., O (10)moresamplesareused toapproximate A whenusing32%feweradaptivelygeneratedsamples). 0.08 0.09 0.1 0.11 0.12 0.13 0.14 0.15 0.1 0.11 0.12 0.13 0.14 0.15 0.16 0.17 0.18 0.19 0.2 6 1 6 2 50 100 150 200 250 0.08 0.09 0.1 0.11 0.12 0.13 0.14 0.15 0.1 0.11 0.12 0.13 0.14 0.15 0.16 0.17 0.18 0.19 0.2 6 1 6 2 200 400 600 800 1000 1200 1400 1600 1800 2000 2200 Figure8.3:Left:Approximationof using1 E +4adaptivesamples.Right:Approximation of usingaregulargridof1 : 4641 E +4samples. Wenowconductamorethoroughnumericalevaluationoftheee ctofusingAlgorithm 3

PAGE 24

DRAFT 24 T.Butleret.al. Algorithm3: AProbabilityBasedAdaptiveSampler[ 10 ] Chooseatransitionprobabilitykernel P t ( x;B ( s ))foraparameterizedevent B ( s ) 2B Initialize (0 ;j ) Mj =1 and M 1vector s = f s j g Mj =1 toinitialeventsize s 0 Setrelativesizetolerance r 2 (0 ; 1). Specifysubsets f D k g Kk =1 D andcompute p k = R D k D d D for j =1 ;:::;M do if Q ( (0 ;j ) ) 2 D k 0 forsome k 0 then p 0 ;j = p k 0 else p 0 ;j =0 end endChooseauserdenedtotalnumberofbatchruns N for i =1 ;:::;N do Generate M parametersamples ( i;j ) Mj =1 using P t ( ( i 1 ;j ) ;B ( s j )). for j =1 ;:::;M do if Q ( ( i;j ) ) 2 D k 0 forsome k 0 then p i;j = p k 0 else p i;j =0 endif p i;j > (1+ r ) p i 1 ;j then s j = s decrease s j elseif p i;j s max then s j = s max s 0j else s j =s 0j
PAGE 25

DRAFT Measure-TheoreticSample-BasedIntegration 25 pollutingestimatessothatallerrorsareduetonitesampl ing.Sinceweusethissurrogate forallcomputations,andforsimplicityofnotation,weref ertothissurrogateas Q below. The D -measureof E (andthusthe -measureof A = Q 1 ( E ))isreducedbydening E tobetherectanglecenteredat Q ( ref )withsides10%ofthelengthsof q i ()for i =1 ; 2. SimilartothenotationusedinSection 7.2 todescribeerrorsinestimatesof ( A ),welet A N denotetheVoronoicoverageof A .Observethattheuseofthesurrogateandthesimple geometryof E impliesthat ( A )canbecalculatedexactly.AsdescribedinSection 7.2 errorsintheestimate ( A N )of ( A )directlyresultinerrorsin ;N .Wethereforeuse theerrorsin ( A N )toquantifytheperformanceofAlgorithm 2 usingeitheradaptively generatedsamplesori.i.d.uniformrandomsamples.Withi. i.d.uniformrandomsamples,we alsoconsidertwodierentapproximationsto V i inAlgorithm 2 asdescribedinSection 7 :a standardMCapproximationwith V i = E ( ( V i;N ))= () =N andthemeasure-theoretic approximationusingemulation.Emulation should be(andis)usedwithadaptivesampling strategiessinceforagivenVoronoicell V i;N thereisnoclearapriorivalueof E ( ( V i;N )). Tocompareperformance,foragivensamplesize N ,wecomputethesamplemeanand varianceoftherelativeerrorsinestimatesof ( A E )using20dierentsetsofadaptivelyand uniformlyi.i.d.generatedsamples.Withthisnotation,we denoteby e therelativeerror e = j ( A N ) ( A ) j ( A ) : (8.5) Figure 8.4 showsthetheaveragemeanandvarianceintherelativeerror asafunctionofsample sizeforboththeuniformi.i.d.samplesets(withandwithou tvolumeemulation)andadaptive samplesets.Forthecomputationsinvolvingvolumeestimat ion,1 E +6emulatedsamplesare used.Table 8.3 showssomesamplestatisticsoftherelativeerrorsforgive nsamplesizesand sampletypes.Forastudyontheeectofemulationsamplesize ,werefertheinterestedreader to[ 24 ].ObserveinFigure 8.4 thatmeasure-theoreticapproximations(i.e.,computingi ntegrals asdescribedbyEq.( 3.1 )usingemulatedsamples)areconsistentlymoreaccurateth anthe MCapproximation.Furthermore,assamplesizeincreases,t headaptivesamplingapproach eventuallyproducesexpectederrorsandvariancessmaller thantheuniformapproach.Inthe plotsofFigure 8.4 thereisacrossoverpointwhenthesamplesizeisapproximat ely4 E +3 betweenthetwocurvesassociatedwithusingeitheruniform samplesoradaptivesamples. Recall,thattheadaptivesamplingstrategycanbeinterpre tedasproceedingintwostages (1)locatingthecontoureventinand(2)samplingfromthec ontourevent.Thiscrossover pointindicateswhenseveralofthesamplingchainsofthead aptivesamplerhavelocatedthe contoureventofinterestafterwhichtheadaptivesamplerw illcontinuetooutperformresults usinguniformsamples. APredictionProblem. Wenowconsiderthephysicallyimportantpredictionproble mof forecastingthetimeofinundationaroundandnearphysical obstacles.Suchforecastsare usefulindeterminingtheecacyofman-madeobstaclessuch ascreatingbarrierislands, extendingearthenjetties,and/orgenerallandmanagement practicesaectingManning's n coecientoffriction,e.g.,see[ 10 ]whichstudiedtheeectofboththeearthenjettylengthand Manning's n frictionofcoecient.Duringextremeeventssuchasstorms urgeresultingfrom hurricanesortropicalcyclones,suchforecastsmusttypic allybemadeasecientlyaspossible toensurethetimelycommuniqueofresultsincoordinationw ithemergencypersonnel.We

PAGE 26

DRAFT 26 T.Butleret.al. 10 2 10 3 Numberofsamples 10 2 10 1RelativeerrorAdaptive,Eq.(3.1)Uniform,Eq.(3.1)MonteCarlo 10 2 10 3 NumberofSamples 10 2 10 1se Figure8.4:Mean(left)andvariance(right)resultsofther elativeerrorintheestimates ( A E;N )asafunctionofsamplesize N .Thebluecurvesshowtheeectofusingadaptive samplingfromAlgorithm 3 ,theredlinesshowtheeectofusinguniformi.i.d.samplesw ith volumeemulation,andthegreenlinesshowtheeectofastand ardMCapproximation. Samplesize,type Relativeerror e e 9680uniform,MC 5.354E-02 4.457E-02 9680uniform,Eq.( 3.1 ) 1.406E-02 1.007E-02 9680adaptive,Eq.( 3.1 ) 5.196E-03 4.973E-03 10 6 uniform,MC 5.044E-03 3.862E-03 Table8.3:SamplestatisticsforFigure 8.4 thereforeconsiderthecomputationalcomplexityinproduc ingreliableresultsbasedonsolving thestochasticinverseproblemwithandwithoutadaptively generatedsample.Sincethewater enteringtheidealizedinletmustrowaroundthebottomofth eearthenjetty,wefocusthe predictionproblemonthetimeofinundationatthepoints( x 1 ;y 1 )=(1593 : 75 ; 1087 : 5)and ( x 2 ;y 2 )=(1593 : 75 ; 1012 : 5)whicharethenearestnodalpointsoftheniteelementmes h totherightoftheearthenjettyandequallyspacedbelowand abovethejettyentrance.To determinetheprobabilitydistributionontheuncertainMa nning's n coecients,wesolvethe stochasticinverseproblemasdescribedabovebyspecifyin ganuncertainrectanglearounda Q ref withlengthsofsideequalto15%ofthelengthsof q i ()for i =1 ; 2.Thestochasticinverse problemissolvedusingboth1 E +4uniformi.i.d.samplesand1 : 04 E +3adaptivelygenerated samples.Theseareroughlythenumberofsamplesweobserved wererequiredtoobtain similaraccuracyinthe -measureofthesupportoftheinversedensity.Forbothsolu tions, weidentifythesmallest -measureeventaccountingfor95%ofthetotalprobability, i.e.,we determinethe A 2B solving min f A 2B : P ( A )=0 : 95 g ( A ) :

PAGE 27

DRAFT Measure-TheoreticSample-BasedIntegration 27 Wethenpropagatetheevent A frombothsolutionsforwardthroughthemodelinorderto obtainanintervalofpredictionconditionedonthis95%pro babilityevent.Wesummarize theresultsinTable 8.4 withthetimeofinundationreferencedtotheinitialmodelr untime formattedashours:minutes:seconds.Thepredictioninter valswhere wasapproximated withadaptivesamplesarethesamedowntothesecondasthepr edictionintervalswhere wasapproximatedwith O (10) more uniformsamples.Thesearerepresentativeresults.We observedthatusingotherQoItosolvetheinverseproblemwi ththesamenumberofuniform andadaptivesamplesleadstosimilarresultswiththelarge stdierenceintheprediction intervalsgenerallybeingontheorderof10seconds. ( x;y ) Sampletype PredicitionInverval ( x 1 ;y 1 ) MC,1 E +4 [16:35:16,19:09:52] Eq.( 3.1 ),1 : 04 E +3 [16:35:16,19:09:52] ( x 2 ;y 2 ) MC,1 E +4 [26:28:48,27:19:14] Eq.( 3.1 ),1 : 04 E +3 [26:28:48,27:19:14] Table8.4:Predictionintervalsforthetimeofinundation( hours:minutes:seconds)atlocations ( x 1 ;y 1 )=(1593 : 75 ; 1087 : 5)(rstrow)and( x 2 ;y 2 )=(1593 : 75 ; 1012 : 5)(secondrow). 9.ConclusionsandFutureWork. Usingameasure-theoreticframeworktodescribesamplebasedintegralapproximationsproducesdeterministic errorbounds.Theuseofemulated samplesprovidesanecientwaytocomputetheseerrorbound sanddevelopadaptivesamplingtechniquestooptimallyreduceerrorswhileavoiding thecomputationallycomplexproblemofexplicitrepresentationoftheVoronoicells.Theuti lityofthisframework,erroranalysis, andadaptivesamplingtechniquesbasedontheseerrorestim ateswasdemonstratedforboth forwardandinverseuncertaintyquanticationproblems. Thereareseveralinterestingproblemsthatweleavetofutu rework.Theauthorsare currentlyinvestigatingtheuseofactivesubspaces(see[ 13 ]andthereferencestherein)to performdimensionreductionforagivensetofQoIandapplyt heapproachesdiscussedinthis worktotheactivesubspaceandrelatethesetothegeometric approximationofeventsinthe originalparameterspace.ThechoiceofQoIonthequalityof inversesolutionsobtainedvia adaptivesamplingisanotherinterestingproblem.Specic ally,dierentobservationnetworks leadtodierentsolutionsofthestochasticinverseproblem .Itisanopenquestiononhowto combinevastlydierentsetsofadaptivelygeneratedsample sthatareoptimalforthedierent solutionsinordertofurtherreduceuncertaintiesinthepa rameterspace. REFERENCES [1] GeorgeJ.Arcement,V.R.Schneider,andUnitedStates.Fede ralHighwayAdministration GuideforSelectingManning'sRoughnessCoecientsforNat uralChannelsandFloodPlainsUnited StatesGeologicalSurveyWater-supplyPaper2339 ,Tech.Report2339.,ForsalebytheBooksand Open-FileSection,U.S.GeologicalSurvey,1989. [2] Siu-KuiAuandJamesL.Beck Estimationofsmallfailureprobabilitiesinhighdimensio nsbysubset simulation ,ProbabilisticEngineeringMechanics,16(2001),pp.263{ 277.

PAGE 28

DRAFT 28 T.Butleret.al. [3] HarryH.1925-(HarryHawthorne)Barnes Roughnesscharacteristicsofnaturalchannels ,vol.1849, U.S.Govt.Print.O,Washington,1967. [4] V.I.Bogachev MeasureTheory(Volume2) ,Springer,2007. [5] J.Breidt,T.Butler,andD.Estep AMeasure-TheoreticComputationalMethodforInverseSens itivityProblemsI:MethodandAnalysis ,SIAMJournalonNumericalAnalysis,49(2011),pp.1836{18 59. [6] S.Bunya,JCDietrich,JJWesterink,BAEbersole,JMSmith,J HAtkinson,R.Jensen, DTResio,RALuettich,C.Dawson,etal. AHigh-ResolutionCoupledRiverineFlow, Tide,Wind,Wave,andStormSurgeModelforSouthernLouisia naandMississippi.Part I:ModelDevelopmentandValidation ,MonthlyWeatherReview,138(2010),pp.345{377. http://dx.doi.org/10.1175/2009MWR2906.1. [7] T.Butler,D.Estep,andJ.Sandelin AComputationalMeasureTheoreticApproachtoInverse SensitivityProblemsII:APosterioriErrorAnalysis ,SIAMJournalonNumericalAnalysis,50(2012), pp.22{45. [8] T.Butler,D.Estep,S.Tavener,C.Dawson,andJ.J.Westerin k AMeasure-TheoreticComputationalMethodForInverseSensitivityProblemsIII:Mult ipleQuantitiesofInterest ,SIAMJournal onUncertaintyQuantication,(2014),pp.1{27. [9] T.Butler,D.Estep,S.Tavener,C.Dawson,J.Westerink,and L.Graham SolvingStochastic InverseProblemsusingSigma-AlgebrasonContourMaps .arXiv:1407.3851,2015. [10] T.Butler,L.Graham,D.Estep,C.Dawson,andJ.J.Westerink Denitionandsolutionofa stochasticinverseproblemforthemanning'snparametere ldinhydrodynamicmodels ,Advancesin WaterResources,78(2015),pp.60{79. [11] AlexCapaldi,SamuelBehrend,BenjaminBerman,JasonSmith ,JustinWright,andAlunL. Lloyd Parameterestimationanduncertaintyquanticationforan epidemicmodel ,Mathematical BiosciencesandEngineering,9(2012),pp.553{576. [12] VenT.1919Chow Open-channelhydraulics ,BlackburnPress,Caldwell,N.J,2008. [13] P.Constantine ActiveSubspaces:EmergingIdeasforDimensionReductioni nParameterStudies SIAM,2015. [14] P.J.DavisandP.Rabinowitz MethodsofNumericalIntegration ,DoverPublications,2007. [15] C.DellacherieandP.A.Meyer ProbabilitiesandPotential ,North-HollandPublishingCo.,Amsterdam,1978. [16] JCDietrich,S.Bunya,JJWesterink,BAEbersole,JMSmith,J HAtkinson,R.Jensen, DTResio,RALuettich,C.Dawson,etal. Ahigh-resolutioncoupledriverinerow,tide,wind, windwave,andstormsurgemodelforsouthernLouisianaandM ississippi.PartII:SynopticdescriptionandanalysisofHurricanesKatrinaandRita ,MonthlyWeatherReview,138(2010),pp.378{404. http://dx.doi.org/10.1175/2009MWR2907.1. [17] JCDietrich,JJWesterink,ABKennedy,JMSmith,REJensen,M .Zijlema,LHHolthuijsen, C.Dawson,RALuettichJr,MDPowell,etal. HurricaneGustav(2008)wavesandstorm surge:Hindcast,synopticanalysis,andvalidationinSout hernLouisiana ,MonthlyWeatherReview, 139(2011),pp.2488{2522. [18] J.R.DormandandP.J.Prince Afamilyofembeddedrunge-kuttaformulae ,JournalofComputational andAppliedMathematics,6(1980),pp.19{26. [19] Q.Du,V.Faber,andM.Gunzburger Centroidalvoronoitessellations:Applicationsandalgor ithms SIAMReview,41(1999),pp.637{676. [20] G.S.Fishman MonteCarlo:Concepts,Algorithms,andApplications ,Springer,2013. [21] WalterGautschi Orthogonalpolynomials:applicationsandcomputation ,ActaNumerica,5(1996), pp.45{119. [22] AlanGenz Testingmultidimensionalintegrationroutines ,inProc.OfInternationalConferenceon Tools,MethodsandLanguagesforScienticandEngineering Computation,NewYork,NY,USA, 1984,ElsevierNorth-Holland,Inc.,pp.81{94. [23] LindleyGraham,StevenMattis,ScottWalsh,TroyButler,an dDamonMcDougall BET: Butler,Estep,TavenerMethodv1.0.2 ,Nov.2015.http://dx.doi.org/10.5281/zenodo.33858. [24] LindleyC.Graham AdaptiveMeasure-TheoreticParameterEstimationforCoas talOceanModeling PhDthesis,UniversityofTexasatAustin,Austin,TX,Augus t2015. [25] A.GuessabandG.Schmeisser Constructionofpositivedenitecubatureformulaeandapp roximation

PAGE 29

DRAFT Measure-TheoreticSample-BasedIntegration 29 offunctionsviavoronoitessellations ,AdvancesinComputationalMathematics,32(2010),pp.25{ 41. [26] J.M.Hammersley Montecarlomethodsforsolvingmultivariableproblems ,AnnalsoftheNewYork AcademyofSciences,86(1960),pp.844{874. [27] H.W.Hethcote Themathematicsofinfectiousdiseases ,SIAMReview,42(2000),pp.599{653. [28] MEHope,JJWesterink,ABKennedy,PCKerr,JCDietrich,CDaw son,CJBender, JMSmith,REJensen,MZijlema,etal. HindcastandvalidationofHurricaneIke(2008)waves, forerunner,andstormsurge ,JournalofGeophysicalResearch:Oceans,118(2013),pp.4 424{4460. [29] AnaJustel,DanielPe ~ na,andRub enZamar Amultivariatekolmogorov-smirnovtestofgoodnessof t ,Statistics&ProbabilityLetters,35(1997),pp.251{259. [30] A.B.Kennedy,U.Gravois,B.C.Zachry,J.J.Westerink,M.E. Hope,J.C.Dietrich,M.D. Powell,A.T.Cox,R.A.LuettichJr,andR.G.Dean OriginoftheHurricaneIkeforerunner surge ,GeophysicalResearchLetters,38(2011),p.L08608. [31] Yu.A.KuznetsovandC.Piccardi Bifurcationanalysisofperiodicseirandsirepidemicmode ls JournalofMathematicalBiology,32(1994),pp.109{121. [32] D.T.LeeandC.K.Wong Worst-caseanalysisforregionandpartialregionsearches inmultidimensionalbinarysearchtreesandbalancedquadtrees ,ActaInformatica,9(1977),pp.23{29. [33] G.LeobacherandF.Pillichshammer IntroductiontoQuasi-MonteCarloIntegrationandApplica tions ,Springer,2014. [34] LunaB.Leopold,GordonM.Wolman,andJohnP.Miller Fluvialprocessesingeomorphology W.H.Freeman,SanFrancisco,1964. [35] JingLi,JinglaiLi,andDongbinXiu Anecientsurrogate-basedmethodforcomputingrarefailu re probability ,JournalofComputationalPhysics,230(2011),pp.8683{86 97. [36] JingLiandDongbinXiu Evaluationoffailureprobabilityviasurrogatemodels ,JournalofComputationalPhysics,229(2010),pp.8966{8980. [37] RALuettichandJJWesterink ADCIRCUserManual:A(Parallel)AdvancedCirculationMode lfor Oceanic,CoastalANDEstuarineWaters ,UniversityofNorthCarolinaatChapelHillandUniversity ofNotreDame,version49ed.,April12010. [38] ChuanjiangLuo,JianSun,andYusuWang Integralestimationfrompointcloudind-dimensional space:Ageometricview ,inInProc.25thACMSympos.onComput.Geom,2009.