QMC And Variable Importance

Lecture 4/4: QMC and Variable Importance1QMC and Variable ImportanceArt B. OwenStanford UniversityIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance2These slides are from a series of four lectures given at the Johann Radon Institute forComputational and Applied Mathematics (RICAM) held on March 24 and March 25 2021.It was an honor to be asked to present on quasi-Monte Carlo (QMC) sampling in Austria, fromwhere so much of QMC comes and has come. The talks were virtual; I would have otherwisemade sure to get some Linzertorte. That will have to wait.1. Quasi-Monte Carlo2. Randomized Quasi-Monte Carlo3. QMC Beyond the Cube4. QMC and Variable ImportanceA small number of corrections have been made since then.Introduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance3Black box functionsy f (x), wherex (x1 , x2 , . . . , xd ) X dYXjj 1Questions How important is xj ? How important is xu for u 1:d?ContextModels in science and engineering:semiconductors, aerospace, malaria control, climate models, · · ·Black box predictions:AI / machine learningQuasi-Monte CarloEffective dimensionIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance4What is importance?A variable is important if changing it changes something else that is important.Local sensitivity f (x0 ) xjet ceteraGlobal sensitivityMake random changes to xu keeping x u fixedstudy E((f (x) f (x0 ))2 )where xu6 x0u and x u x0 uIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance5Global sensitivity analysisGlobal: consider all x not just focal x0potentially all x06 x not just localSome referencesFor books giving context and uses see:Fang, Li & Sudijanto (2010), Saltelli, Chan & Scott (2009), Saltelli, Ratto & Andres (2008),Cacuci, Ionescu-Bujor & Navon (2005), Saltelli, Tarantola & Campolongo (2004), Santner,Williams & Notz (2003)Many scientific communities participate, many terms:FANOVADACEFASTSAMOMASCOTUCMHDMRNPUAUQMajor survey paperRazavi et al. (2021) 26 authorsEnvironmental Modelling and SoftwareIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance6Outline1) ANOVA and notation2) Sobol’ indices and mean dimension3) Mean dimension of ridge functions4) Mean dimension of a neural network5) Shapley valueIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance72dANOVA for L [0, 1]Origins: Hoeffding (1948)Sobol’ (1969)Efron & Stein (1981)NotationFor u 1:d {1, . . . , d} u card(u) u uc {1, 2, . . . , d} uIf u {j1 , j2 , . . . , j u } then xu (xj1 , . . . , xj u ) and dxu Qj udxjDecompositionf (x) Xfu (x)u 1:dfu (x) only depends on xj for j u.Introduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance8ANOVA propertiesZj u 1fu (x) dxj 0Z0u 6 v fu (x)fv (x) dx 0VariancesZVar(f ) 2(f (x) µ) dx Xσu2u 1:d R f (x)2 dx u 6 u22σu σu (f ) 0u .General L2Independence is criticalUniformity is notIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance9Sobol’ indicesτ 2u Xσv2v contained in uSobol’ (1993)v ‘touches’ uHomma & Saltelli (1996)v uτ 2u Xσv2v u6 Large τ 2u means xu importantSmall τ 2u means xu unimportantcan be frozen Sobol’Normalizationτ 2uτ 2uandare like R2 measures for xu22σσIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance10Examplesd 4 and u {1, 2}222τ 2{1,2} σ{1} σ{2} σ{1,2}222 σ{1,2} σ{2}τ 2{1,2} σ{1}2222 σ{1,3} σ{1,4} σ{2,3} σ{2,4}2222 σ{1,3,4} σ{2,3,4} σ{1,2,3} σ{1,2,4}2 σ{1,2,3,4}Identityτ 2u τ 2 u σ 2Introduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance11Variance explainedτ 2u is the variance ‘explained by’ xuR1f (x) dxj 0. ( )For j v ,0 vE(f (x) xu ) XE(fv (x) xu )v 1:d XE(fv (x) xu ) by ( )v u Xfv (x)v uAs a Sobol’ index Var E(f (x) xu ) Var Xv u fv (x) Xσv2 τ 2uv uIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance12Hybrid pointsy xu :z u means x , j ujyj zj , j 6 u.Examplex (0.1, 0.2, 0.3, 0.4, 0.5, 0.6)z (0.9, 0.8, 0.7, 0.6, 0.5, 0.4)x{1,2,4,5} :z {3,6} (0.1, 0.2, 0.7, 0.4, 0.5, 0.4)Glue: is a ‘glue operator’.We glue xu to z u to get xu :z u [0, 1]dIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance13An identityFor x, ziid U[0, 1]dE(f (x)f (xu :z u )) X XE(fv (x)fv0 (xu :z u ))v 1:d v 0 1:d XE(fv (x)fv (xu :z u ))orthogonalityv 1:d XE(fv (x)fv (xu :z u ))line integral on zjv u XE(fv (x)2 )fv does not depend on z uv u µ2 τ 2uFrom Sobol’ (1993)Introduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance14Pick and freeze methodsEvaluate f at two points: xuFreeze:keep some componentse.g., xuPick:change the otherse.g., x u z uIdentitiesτ 2u Zf (x)f (xu :z u ) dx dz µ2Z1τ 2u ((f (x) f (x u :z u ))2 dx dz2Sobol’ (1993)Jansen (1999)Use MC, QMC, RQMCThere are many such identitiesLike tomographyglobal integrals reveal internal structurewe don’t have to estimate any fuIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance15Mean dimensionν(f ) Xu 1:dLow mean dimensionσu2 u 2σ f dominated by low dimensional aspectsIdentity from Liu & O (2006)dXτ 2j d XX1j u σu2j 1 u 1:dj 1 dX X1j u σu2u 1:d j 1 X u σu2u 1:dAnswer from 2d variance components equalssum of d Sobol’ indicesIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance16ExampleKuo, Schwab, Sloan (2011)f (x) 11 P500j 1xj /j!, x U[0, 1]500Find numerically that1.00356 6 ν(f ) 6 1.00684(99% confidence)vs effective dimension1) easier to compute2) not defined via 0.99 or other threshold3) not restricted to integer valuesIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance17Ridge functionsf (x) g(θT x),x, θ RdMore generallyf (x) g(ΘT x),Θ Rd r ,x Rdr dg : Rr RWe’re interested inr dNormalizationΘT Θ IrθT θ 1Introduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance18Ridge functions and QMC1) P. Constantine (2015) ridge functions are ubiquitous in physical sciences andengineering(active subspaces)2) Integrands that are dominated by low dimensional aspects are favorable for QMC3) Smooth ridge functions are dominated by low dimensional aspectsThereforeQMC should often be very effective in the physical sciencesFiner print1) usually f (x) g(ΘT x)2) the low dimensional parts ought to be regularCommonly true Griebel, Kuo, Sloan (2013, 2017)3) we use mean dimensionIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance19SpoilerSometimes mean dim is O(1) as d Sometimes mean dim is O( d) as d What matters1) smoothness of g(·)2) sparsity of θ or ΘIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance20Gaussian settingx N (0, Id ) z ΘT x N (0, Ir ) z θT x N (0, 1)MomentsLet ϕ(x) be N (0, I) densityZµ Rdσ2 Zg(ΘT x)ϕd (x) dx Zg(z)ϕr (z) dzRrZ 22Tg(Θ x) µ ϕd (x) dx g(z) µ ϕr (z) dzRdRrMonte Carlo rate independent of dIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance21One dimensional ridge functions dX 1f (x) g xj g N (0, 1)d j 1 x N (0, I)1d θ d1.5Examples of g(z)Kink1.00.5Phi( z t )0.0g(z)Step 3 2 10123Introduction to QMC Sampling: RICAM, March 2021z

Lecture 4/4: QMC and Variable Importance22Smoothg d1 Xf (x) g xjd j 1 Zz tg(z) Φ(z t) ϕ(y) dy g(z) Phi( z t ) for t 0, 1, 21.4 t 2 1.2 t 1 1.1Mean dimension1.3 t 0 1.0 1e 001e 031e 061e 09Nominal dimensionRand. Sobol’ points on Sobol’ index n1 6 log2 (d) 6 35 214 ; 5 repeats.τ 2j all the sameIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance23Jump g dX1f (x) g xjd j 1 g(z) 1{z t}10000g(z) 1( z t ) at: t 0, 1, 2 t 0t 1t 2Sqrt(d) 100010 100 1 Mean dimension 1e 001e 021e 041e 061e 08Nominal dimension Introduction to QMC Sampling: RICAM, March 2021Via randomized Sobol’ n 216 ; 5 repeats.

Lecture 4/4: QMC and Variable Importance24Kink g dX1f (x) g xjd j 1 g(z) max(0, z t)PuzzlerIs a kink like a step or like Φ(z t)?Infinite Hardy-Krause variation like the stepHas weak derivative like Φ(z t)Kink is a once integrated stepsee Griewank, Kuo, Leövey & Sloan (2018)For jump or kink: fu is smooth for u dGriebel, Kuo & Sloan (2013, 2017)Introduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance25Kink gd 1 Xf (x) g xjd j 1 g(z) max(z t, 0)4.0Kinks at t 2, 0, 2 t 2 3.0 2.52.0 1.5t 0 1.0Mean dimension 1e 00t 2 1e 031e 06Nominal dimension 1e 09Introduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance26TheoremTheorem 3.1 of Hoyt & O (2020) upper bound for ν(f ) whenf (x) g(xT Θ) and g(·) is Hölder αLipschitz corollaryIf f (x) g(ΘT x) for x N (0, Id ) with ΘT Θ Ir thenC2ν(f ) 6 r 2σwhere g is Lipschitz C with σ 2 Var(f (x)) Var(g(z)).r 1 corollaryFor d r 1 and g(z) g(z 0 ) 6 Ckz z 0 kα0 α61ν(f ) O(d1 α )Implied constants in Hoyt & O (2020)Introduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance27Mean dimension of a neural networkPaper is Hoyt & O (2021)Journal of Uncertainty QuantificationTheorem is about how to computedX2τ̂ {j}j 1efficiently handling O(d2 ) correlationsVariant of Winding stairs works bestJansen, Rossing, Daamen (1994)ExampleMean dimension of a neural network on 28 28 768 pixelsIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance28MNIST dataDigits 0, 1, . . . , 9 in 28 28 gray level images70,000 images from LeCunNeural net architecture from Yalcin (2018)Second last layer produces g0 (x), g2 (x), . . . , g9 (x).Last layer (softmax) isexp(gy (x))fy (x) P9j 0 exp(gj (x))Mean dimensionThe gj had modest mean dimensionThe fj not so muchProblemVery unrealistic independence models on the 768 pixel valuesIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance29Independent pixel distributionsFrom left to rightU{0, 1}768U[0, 1]768resample pixels independently from dataresample pixels (one class)Example imageIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance30ν(fy ) with tion to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance31ν(gy ) without 801.861.671.691.82Introduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance32Pixel importance mapsFunctions are gy for predicting Y yMap shows τ 2j for 786 pixels jLarger brighterResampling pixels from y 0 imagesIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance33Next topic:Shapley value1) connects to Sobol’ indices2) bridge to variable importance in machine learningIntroduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance3415 million EurosShapley’s (1953) value can be used to quantify the contribution of members to a team.We need to know what each subset of the team would have accomplished.Example from Bank of International SettlementQ:TeamOutput value in e 00,000B,C11,000,000A,B,C15,000,000How should we split the e15,000,000 earned by A, B, C among them?Introduction to QMC Sampling: RICAM, March 2021

Lecture 4/4: QMC and Variable Importance3515 million EurosShapley’s (1953) value can be used to quantify the contribution of members to a team.We need to know what each subset of the team would have accomplished.Example from Bank of International SettlementQ:TeamOutput value in e 00,000B,C11,000,000A,B,C15,000,000How should we split the e15,000,000 earned by A, B, C among them?A: Shapley says: A gets e4,500,000,Introduction to QMC Sampling: RICAM, March 2021B gets e5,000,000,C gets e5,500,000