Model Selection with Many More Variables than …

1 Victoria StoddenStanford UniversityModel Selection with many MoreVariables than ObservationsMicrosoft Research AsiaMay 8, 2008 Victoria StoddenDepartment of Statistics, Stanford UniversityClassical Linear Regression Problem> Given predictors and response ,> Linear Model , with > Estimate with > Widely used in a huge amount of empiricalstatistical 1ny yX =+0,)N 2( 1(') 'XXXy Victoria StoddenDepartment of Statistics, Stanford UniversityDeveloping Trend> Classical Model requires , but recentdevelopments have pushed people beyond theclassical Model , to .pn<pn Victoria StoddenDepartment of Statistics, Stanford UniversityNew Data Types>MicroArray Data: is number of genes, isnumber of patients>Financial Data: is number of stocks, prices,etc, is number of time points>Data Mining: automated data collection canimply large numbers of Variables >Texture Classification in Images (eg.)

2 Satellite):is number of pixels, is number of imagespppnnnVictoria StoddenDepartment of Statistics, Stanford UniversityEstimating the Model > Can we find an estimate for when ?> George Box (1986) Effect-Sparsity: the vastmajority of factors have zero effect, only a smallfraction actually affect the reponse.> can still be modeled but nowmust be sparse, containing a few nonzeroelements, the remaining elements yX =+ Victoria StoddenDepartment of Statistics, Stanford UniversityCommonly Used Strategies for Sparse Modeling1. All Subsets Regression Fit all possible linear models for all levels of Forward Stepwise Regression Greedy approach that chooses each variable in the modelsequentially by significance LASSO (Tibshirani 1994), LARS (Efron, Hastie,Johnstone, Tibshirani 2002) shrinks some coefficient estimates to StoddenDepartment of Statistics, Stanford UniversityLASSO and LARS: a quick tour> LASSO solves:for a choice of.

3 > LARS: a stepwise approximation to LASSO Advantage: guaranteed to stop in n steps2 2 yXt tVictoria StoddenDepartment of Statistics, Stanford UniversityA New Perspective> Up until now we ve described the statistical viewof the problem when .> Now we introduce ideas from Signal Processingand a new tool for understanding regressionwhen , in the case of large.>Claim: This will allow us to see that, for certainproblems, statistical solutions such as LASSO,LARS, are just as good as all pn>nVictoria StoddenDepartment of Statistics, Stanford UniversityBackground from Signal Processing> There exists a signal , and several ortho-bases(eg. sinusoids, wavelets, gabor).> Concatenation of several ortho-bases is adictionary.> Postulate that the signal is sparselyrepresentable, made up from fewcomponents of the dictionary.> Motivation: Image = Texture + Cartoon Signal = Sinusoids + Spikes Signal = CDMA + TDMA + FM +.

4 YVictoria StoddenDepartment of Statistics, Stanford UniversityOvercomplete DictionariesCanonical Basis orthogonal columnsStandard Fourier Basis where indicates cosine, sine orthogonal columns10 0001 0000 1000 01 1 (,0)(,) n2, 0,,/2kkkn ==..0,1n is an overcomplete dictionary2[|]CFnnABB =Victoria StoddenDepartment of Statistics, Stanford UniversityOriginal ImageExample: Image = Texture + Cartoon(Elad and Starck 2003)Victoria StoddenDepartment of Statistics, Stanford UniversityExample: Image = Texture + Cartoon(Elad and Starck 2003)Cartoon (Curvelets) Texture (local sinusoids)Victoria StoddenDepartment of Statistics, Stanford UniversityFormal Signal Processing Problem DescriptionSignal decomposition: with a noise term:If #bases > 1, .SignalMatrixCoefficientsNoisenpsignal length = #basesobservationspredictorsDecompositio nRegressionyX yAzxyAx=, (0,)yAxzzN 2=+ /pn p > n Victoria StoddenDepartment of Statistics, Stanford UniversitySignal Processing Pursuit (Mallat, Zhang 1993) Forward Stepwise Pursuit (Chen, Donoho 1994) Simple global optimization criteria:3.

5 Maximally Sparse Solution: Intuitively most compelling but not feasible!0 0() xPyAx= 1 1( ) minx xPyAx= Victoria StoddenDepartment of Statistics, Stanford University> We can t hope to do an all subsets search, butwe are lucky! is a convex problem, and it can sometimessolve . Problem Impossible!0l1()P0()PVictoria StoddenDepartment of Statistics, Stanford University Equivalence> Signal processing results show solvesfor certain problems.> Donoho, Huo (IEEE IT, 2001)> Donoho, Elad (PNAS, 2003)> Tropp (IEEE IT, 2004)> Gribonval (IEEE IT, 2004)> Cand s, Romberg, Tao (IEEE IT, to appear)0()P1()P1, 0()llVictoria StoddenDepartment of Statistics, Stanford UniversityPhase Transition in Random Matrix Model >> , where has random nonzeros,positions random.> Phase Plane : degree of sparsity : degree of underdeterminationTheorem (DLD 2005) There exists a criticalsuch that, for every , for theoverwhelming majority of pairs, if , solves.

6 ,, (0,1)npijAAN /kn =/np =1()P0()P(w )w <xk(,) w <(,)yAyAx=Victoria StoddenDepartment of Statistics, Stanford UniversityPhase Transition: equivalence1, 0()ll/kn =/np =Combinatorial Search! solves1P0 PCombinatorial Search!Victoria StoddenDepartment of Statistics, Stanford UniversityParadigm for study> is a property of an algorithm,> is a random ensemble,> Find the Phase Transitions for property .Approach pioneered by Donoho, Drori, and Tsaig:1. Generate , where Run full solution path to find solution ,3. PropertyP(,)yXP22 : P yX = Victoria StoddenDepartment of Statistics, Stanford UniversityThis implies a statistics question!> Could this paradigm be used for linearregression with noisy data?> For example, when are LASSO, LARS, ForwardStepwise just as good as all subsets regression?> Reformulate problems with Noise:20, 20() minPyX + 21, 2 1() minPyX + Victoria StoddenDepartment of Statistics, Stanford UniversityExperiment Setup> , with random entries generated from , and normalized columns.

7 > is a -vector with the first entries drawnfrom remaining entries .> ~ -vector.>Create> We find the solution using an algorithm(LASSO, LARS, Forward Stepwise) with and as (0,1)N pk(0,100)U0(0,16) Nn yX =+ XyVictoria StoddenDepartment of Statistics, Stanford UniversityQuestions> Will there be any phase transition?> Can we learn something about the properties ofthese algorithms from the Phase Diagram?Victoria StoddenDepartment of Statistics, Stanford UniversityLASSO, LARS Phase Transitions for Noisy ModelLASSO, z~N(0,16)LARS, z~N(0,16)Victoria StoddenDepartment of Statistics, Stanford UniversityAside: Stepwise Thresholding> Stepwise Algorithm typical implementation: Add the variable with the highest t-statistic to the Model , ifthat t-statistic is greater than , (Bonferroni).> Stepwise Algorithm: False Discovery Rate(FDR) Threshold: Add the variable with the highest t-statistic to the Model , ifthat t-statistic s p-value is less than the FDR statistic.

8 , where is (the FDR parameter), is the number of Variables in the currentmodel, and is the potential number of ()p*statqkFDRp qkp{# falseDiscoveries}{# totalDiscoveries}EVictoria StoddenDepartment of Statistics, Stanford UniversityStepwise Phase Transitions for Noisy ModelStepwise , z~N(0,16) Stepwise FDR, z~N(0,16)2log()pVictoria StoddenDepartment of Statistics, Stanford UniversityPhase Transition Surprises>Surprise: LASSO finds underlying Model , for>Hoped for: LARS finds underlying Model , for..>Surprise: Stepwise only successful for..LASSO <LARS <LASSOc Victoria StoddenDepartment of Statistics, Stanford UniversityError Analysis> with increased noise levels, at what sparsitylevels does these algorithms continue to recoverthe correct underlying Model , if at all?> We fix and examine a slice of the phasetransition =Victoria StoddenDepartment of Statistics, Stanford UniversityLasso Normalized L2 ErrorVictoria StoddenDepartment of Statistics, Stanford UniversityLARS Normalized L2 ErrorVictoria StoddenDepartment of Statistics, Stanford UniversityForward Stepwise Normalized L2 ErrorVictoria StoddenDepartment of Statistics, Stanford UniversityFDR Stepwise Normalized L2 ErrorVictoria StoddenDepartment of Statistics, Stanford UniversityExperiences with Noisy Case> Phase Diagrams revealing, stimulating.

9 > Stepwise Regression falls apart at a criticalsparsity level (why?)> LARS in same cases works very well!> Suggests other interesting properties to study.> Other algorithms: Forward Stagewise, BackwardElimination, Stochastic Search VariableSelection, ..Victoria StoddenDepartment of Statistics, Stanford UniversityIntroducing SparseLab! > Matlab toolbox that makes software solutions forsparse systems available.> Growing research on sparsity, variable selectionissues could advance the research communityif they have standard tools.> SparseLab is a system to do StoddenDepartment of Statistics, Stanford UniversitySparseLab in Depth> Reproducible Research: SparseLab makesavailable the code to reproduce figures inpublished papers.> Some papers currently included: Model Selection When the Number of Variables Exceedsthe Number of Observations (Donoho, Stodden 2006) Extensions of Compressed Sensing (Tsaig, Donoho 2005) Neighborliness of Randomly-Projected Simplices in HighDimensions (Donoho, Tanner 2005) High-Dimensional Centrally-Symmetric Polytopes WithNeighborliness Proportional to Dimension (Donoho 2005)> All open source!

10 Victoria StoddenDepartment of Statistics, Stanford UniversityAcknowledgmentsDavid DonohoIddo DroriJoshua Sweetkind-SingerYaakov Tsaig