AdditiveModels，Trees，andRelatedModelsProf.LiqingZhangDept.ComputerScience&Engineering,ShanghaiJiaotongUniversityIntroduction9.1:GeneralizedAdditiveModels9.2:Tree-BasedMethods9.3:PRIM:BumpHunting9.4:MARS:MultivariateAdaptiveRegressionSplines9.5:HME:HierarchicalMixtureofExperts9.1GeneralizedAdditiveModelsIntheregressionsetting,ageneralizedadditivemodelshastheform:

Here

sareunspecifiedsmoothandnonparametricfunctions.InsteadofusingLBE(LinearBasisExpansion)inchapter5,wefiteachfunctionusingascatterplotsmoother(e.g.acubicsmoothingspline)GAM(cont.)Fortwo-classclassification,theadditivelogisticregressionmodelis:

Here

GAM(cont)Ingeneral,theconditionalmeanU(x)ofaresponseyisrelatedtoanadditivefunctionofthepredictorsviaalinkfunctiong:

Examplesofclassicallinkfunctions:Identity:Logit:Probit:Log:FittingAdditiveModelsTheadditivemodelhastheform:HerewehaveGivenobservations,acriterionlikepenalizedsumsquarescanbespecifiedforthisproblem:

Wherearetuningparameters.FAM(cont.)Conclusions:ThesolutiontominimizePRSSiscubicsplines,howeverwithoutfurtherrestrictionsthesolutionisnotunique.Ifholds,itiseasytoseethat:

Ifinadditiontothisrestriction,thematrixofinputvalueshasfullcolumnrank,then(9.7)isastrictconvexcriterionandhasanuniquesolution.Ifthematrixissingular,thenthelinearpartoffjcannotbeuniquelydetermined.(Buja1989)LearningGAM:BackfittingBackfittingalgorithmInitialize:Cycle: j=1,2,…,p,…,1,2,…,p,…,(mcycles)

UntilthefunctionschangelessthanaprespecifiedthresholdBackfitting:PointstoPonderComputationalAdvantage?Convergence?Howtochoosefittingfunctions?FAM(cont.)Initialize:Cycle:untilthefunctionschangelessthanaprespecifiedthreshold.Algorithm9.1TheBackfittingAlgorithmforAdditiveModels.AdditiveLogisticRegression2024/12/711ThegeneralizedadditivelogisticmodelhastheformThefunctionsareestimatedbyabackfittingwithinaNewton-Raphsonprocedure.LogisticRegressionModeltheclassposteriorintermsofK-1log-oddsDecisionboundaryissetofpointsLineardiscriminantfunctionforclasskClassifytotheclasswiththelargestvalueforits

k(x)LogisticRegressioncon’tParametersestimationObjectivefunctionParametersestimationIRLS(iterativelyreweightedleastsquares)Particularly,fortwo-classcase,usingNewton-Raphsonalgorithmtosolvetheequation,theobjectivefunction:LogisticRegressioncon’tLogisticRegressioncon’tLogisticRegressioncon’tLogisticRegressioncon’tLogisticRegressioncon’tFeatureselectionFindasubsetofthevariablesthataresufficientforexplainingtheirjointeffectontheresponse.Onewayistorepeatedlydroptheleastsignificantcoefficient,andrefitthemodeluntilnofurthertermscanbedroppedAnotherstrategyistorefiteachmodelwithonevariableremoved,andperformananalysis

ofdeviancetodecidewhichonevariabletoexcludeRegularizationMaximumpenalizedlikelihoodShrinkingtheparametersviaanL1constraint,imposingamarginconstraintintheseparablecaseFittinglogisticregressionFittingadditivelogisticregression1.2.Iterate:Usingweightedleastsquarestofitalinearmodeltoziwithweightswi,givenewestimates3.Continuestep2until converge1. where2.Iterate:b.a.a.c.c.Usingweightedbackfittingalgorithmtofitanadditivemodeltoziwithweightswi,givenewestimatesb.3.Continuestep2untilconvergeAdditiveLogisticRegression:BackfittingAdditiveLogisticRegressionComputestartingvalues:,where,thesampleproportionofones,andset.Defineand.Iterate:ConstructtheworkingtargetvariableConstructweightsFitanadditivemodeltothetargetsziwithweightswi,usingaweightedbackfittingalgorithm.ThisgivesnewestimatesContinuestep2.untilthechangeinthefunctionsfallsbelowaprespecifiedthreshold.Algorithm9.2LocalScoringAlgorithmfortheAdditiveLogisticRegressionModel.SPAMDetectionviaAdditiveLogisticRegressionInputvariables(predictors):48quantitativepredictors—thepercentageofwordsintheemailthatmatchagivenword.Examplesincludebusiness,address,internet,free,andgeorge.Theideawasthatthesecouldbecustomizedforindividualusers.6quantitativepredictors—thepercentageofcharactersintheemailthatmatchagivencharacter.Thecharactersarech;,ch(,ch[,ch!,ch$,andch#.Theaveragelengthofuninterruptedsequencesofcapitalletters:CAPAVE.Thelengthofthelongestuninterruptedsequenceofcapitalletters:CAPMAX.Thesumofthelengthofuninterruptedsequencesofcapitalletters:CAPTOT.Outputvariable:SPAM(1)orEmail(0)fj’saretakenascubicsmoothingsplines2024/12/7AdditiveModels222024/12/7AdditiveModels232024/12/7AdditiveModels24SPAMDetection:ResultsTrueClassPredictedClassEmail(0)SPAM(1)Email(0)58.5%2.5%SPAM(1)2.7%36.2%Sensitivity:Probabilityofpredictingspamgiventruestateisspam=Specificity:Probabilityofpredictingemailgiventruestateisemail=GAM:SummaryUsefulflexibleextensionsoflinearmodelsBackfittingalgorithmissimpleandmodularInterpretabilityofthepredictors(inputvariables)arenotobscuredNotsuitableforverylargedataminingapplications(why?)Introduction9.1:GeneralizedAdditiveModels9.2:Tree-BasedMethods9.3:PRIM:BumpHunting9.4:MARS:MultivariateAdaptiveRegressionSplines9.5:HME:HierarchicalMixtureofExperts9.2Tree-BasedMethodBackground:Tree-basedmodelspartitionthefeaturespaceintoasetofrectangles,andthenfitasimplemodel(likeaconstant)ineachone.Apopularmethodfortree-basedregressionandclassificationiscalledCART(classificationandregressiontree)CARTCARTExample:Let’sconsideraregressionproblem:continuousresponseYinputsX1andX2.Tosimplifymatters,weconsiderthepartitionshownbythetoprightpaneloffigure.ThecorrespondingregressionmodelpredictsYwithaconstantCminregionRm：Forillustration,wechooseC1=-5,C2=-7,C3=0,C4=2,C5=4inthebottomrightpanelinfigure9.2.RegressionTreeSupposewehaveapartitionintoMregions:R1R2…..RM.WemodeltheresponseYwithaconstantCmineachregion:

IfweadoptasourcriterionminimizationofRSS,itiseasytoseethat:RegressionTree(cont.)FindingthebestbinarypartitionintermofminimumRSSiscomputationallyinfeasibleAgreedyalgorithmisused.

HereRegressionTree(cont.)Foranychoicejands,theinnerminimizationissolvedby:ForeachsplittingvariableXj

thedeterminationofsplitpointscanbedoneveryquicklyandhencebyscanningthroughalloftheinput,determinationofthebestpair(j,s)isfeasible.Havingfoundthebestsplit,wepartitionthedataintotworegionsandrepeatthesplittingprogressineachofthetworegions.RegressionTree(cont.)Weindexterminalnodesbym,withnodemrepresentingregionRm.Let|T|denotesthenumberofterminalnotesinT.Letting:Wedefinethecostcomplexitycriterion:ClassificationTree:theproportionofclasskonmode:themajorityclassonnodemInsteadofQm(T)definedin(9.15)inregression,wehavedifferentmeasuresQm(T)ofnodeimpurityincludingthefollowing:MisclassificationError:GiniIndex:Cross-entropy(deviance):ClassificationTree(cont.)Example:Fortwoclasses,ifpistheproportionofinthesecondclass,thesethreemeasuresare:

1-max(p,1-p),2p(1-p),-plog(p)-(1-p)log(1-p）2024/12/7AdditiveModels372024/12/7AdditiveModels38Introduction9.1:GeneralizedAdditiveModels9.2:Tree-BasedMethods9.3:PRIM:BumpHunting9.4:MARS:MultivariateAdaptiveRegressionSplines9.5:HME:HierarchicalMixtureofExperts9.3PRIM:BumpHuntingThepatientruleinductionmethod(PRIM)findsboxesinthefeaturespaceandseeksboxesinwhichtheresponseaverageishigh.Henceitlooksformaximainthetargetfunction,anexerciseknownasbumphunting.PRIM(cont.)PRIM(cont.)PRIM(cont.)Introduction9.1:GeneralizedAdditiveModels9.2:Tree-BasedMethods9.3:PRIM:BumpHunting9.4:MARS:MultivariateAdaptiveRegressionSplines9.5:HME:HierarchicalMixtureofExpertsMARS:MultivariateAdaptiveRegressionSplinesMARSusesexpansionsinpiecewiselinearbasisfunctionsoftheform:(x-t)+and(t-x)+.Wecallthetwofunctionsareflectedpair.MARS(cont.)TheideaofMARSistoformreflectedpairsforeachinputXjwithknotsateachobservedvalueXij

ofthatinput.Therefore,thecollectionofbasisfunctionis:Themodelhastheform:whereeachhm(x)isafunctioninCoraproductoftwoormoresuchfunctions.MARS(cont.)Westartwithonlytheconstantfunctionh0(x)=1inthemodelsetMandallfunctionsinthesetCarecandidatefunctions.AteachstageweaddtothemodelsetMthetermoftheform:

thatproducesthelargestdecreaseintrainingerror.TheprocessiscontinueduntilthemodelsetMcontainssomepresetmaximumnumberofterms.MARS(cont.)MARS(cont.)MARS(cont.)Thisprogresstypicallyoverfitsthedataandsoabackwarddeletionprocedureisapplied.ThetermwhoseremovalcausesthesmallestincreaseinRSSisdeletedfromthemodelateachstep,producinganestimatedbestmodelofeachsize.GeneralizedcrossvalidationisappliedtoestimatetheoptimalvalueofThevalueM(λ)istheeffectivenumberofparametersinthemodel.Introduction9.1:GeneralizedAdditiveModels9.2:Tree-BasedMethods9.3:PRIM:BumpHunting9.4:MARS:MultivariateAdaptiveRegressionSplines9.5:HME:HierarchicalMixtureofExpertsHierarchicalMixturesofExpertsTheHMEmethodcanbeviewedasavariantofthetree-basedmethods.Difference:Themaindifferenceisthatthetreesplitsarenotharddecisionsbutrathersoftprobabilisticones.InanHMEalinear(orlogisticregression)modelisfittedineachterminalnode,insteadofaconstantasintheCART.HME(cont.)Asimpletwo-levelHMEmodelisshowninFigure.Itcanbeviewedasatreewithsoftsplitsateachnon-terminalnode.HME(cont.)Theterminalnodeiscalledexpertandthenon-terminalnodeiscalledgatingnetworks.TheideaeachexpertprovidesapredictionabouttheresponseY,thesearecombinedtogetherbythegatingnetworks.

HME(cont.)Thetopgatingnetworkhastheoutput:whereeachisavectorofunknownparameters.Thisrepres-entsasoftK-waysplit(K=2inFigure9.13.)Eachistheprobabilityofassigninganobservationwithfeaturevectorxtothejthbranch.HME(cont.)Atthesecondlevel,thegatingnetworkshaveasimilarform:Attheexperts,wehaveamodelfortheresponsevariableoftheform:Thisdiffersaccordingtotheproblem.HME(cont.)Reg