陈天奇论文演讲.ppt

IntroductiontoBoostedTrees TianqiChenOct 222014 Outline ReviewofkeyconceptsofsupervisedlearningRegressionTreeandEnsemble WhatareweLearning GradientBoosting HowdoweLearn Summary ElementsinSupervisedLearning Notations i thtrainingexampleModel howtomakepredictiongiven includelinear logisticregression canhavedifferentinterpretations Linearmodel ThepredictionscoredependingonthetaskLinearregression Logisticregression isthepredictedscoreispredictedtheprobability oftheinstancebeingpositiveOthers forexampleinrankingcanbetherankscoreParameters thethingsweneedtolearnfromdataLinearmodel Elementscontinued ObjectiveFunction Objectivefunctionthatiseverywhere Lossontrainingdata Squareloss Logisticloss Regularization howcomplicatedthemodelis L2norm L1norm lasso TrainingLossmeasureshowwellmodelfitontrainingdata Regularization measurescomplexityofmodel Puttingknownknowledgeintocontext Ridgeregression Linearmodel squareloss L2regularizationLasso Linearmodel squareloss L1regularizationLogisticregression Linearmodel logisticloss L2regularizationTheconceptualseparationbetweenmodel parameter objectivealsogivesyouengineeringbenefits ThinkofhowyoucanimplementSGDforbothridgeregressionandlogisticregression ObjectiveandBiasVarianceTrade off Whydowewanttocontaintwocomponentintheobjective OptimizingtraininglossencouragespredictivemodelsFittingwellintrainingdataatleastgetyouclosetotrainingdatawhichishopefullyclosetotheunderlyingdistributionOptimizingregularizationencouragessimplemodelsSimplermodelstendstohavesmallervarianceinfuturepredictions makingpredictionstable TrainingLossmeasureshowwellmodelfitontrainingdata Regularization measurescomplexityofmodel Outline ReviewofkeyconceptsofsupervisedlearningRegressionTreeandEnsemble WhatareweLearning GradientBoosting HowdoweLearn Summary RegressionTree CART regressiontree alsoknownasclassificationandregressiontree DecisionrulessameasindecisiontreeContainsonescoreineachleafvalue Input age gender occupation age 15 ismale 2 1 0 1 Y N Y N Doesthepersonlikecomputergames predictionscoreineachleaf RegressionTreeEnsemble age 15 ismale 2 1 0 1 Y N Y N Y N 0 9 0 9 tree1 tree2UseComputerDaily f 2 0 9 2 9f 1 0 9 1 9Predictionofissumofscorespredictedbyeachofthetree TreeEnsemblemethods Verywidelyused lookforGBM randomforest AlmosthalfofdataminingcompetitionarewonbyusingsomevariantsoftreeensemblemethodsInvarianttoscalingofinputs soyoudonotneedtodocarefulfeaturesnormalization Learnhigherorderinteractionbetweenfeatures Canbescalable andareusedinIndustry Putintocontext ModelandParameters Model assumingwehaveKtrees Think regressiontreeisafunctionthatmapstheattributestothescoreParametersIncludingstructureofeachtree andthescoreintheleafOrsimplyusefunctionasparameters Insteadlearningweightsin wearelearningfunctions trees SpaceoffunctionscontainingallRegressiontrees Learningatreeonsinglevariable Howcanwelearnfunctions Defineobjective loss regularization andoptimizeit Example Considerregressiontreeonsingleinputt time IwanttopredictwhetherIlikeromanticmusicattimet t 2011 03 01 Y N t 2010 03 20Y 0 2 Equivalently Themodelisregressiontreethatsplitsontime N1 2 1 0 Piecewisestepfunctionovertime Learningastepfunction Thingsweneedtolearn Objectiveforsinglevariableregressiontree stepfunctions TrainingLoss Howwillthefunctionfitonthepoints Regularization Howdowedefinecomplexityofthefunction Numberofsplittingpoints l2normoftheheightineachsegment SplittingPositionsTheHeightineachsegment Learningstepfunction visually Comingback ObjectiveforTreeEnsemble Model assumingwehaveKtreesObjective Possiblewaystodefine Numberofnodesinthetree depthL2normoftheleafweights detailedlater Trainingloss ComplexityoftheTrees ObjectivevsHeuristic Whenyoutalkabout decision trees itisusuallyheuristicsSplitbyinformationgainPrunethetreeMaximumdepthSmooththeleafvaluesMostheuristicsmapswelltoobjectives takingtheformal objective viewletusknowwhatwearelearningInformationgain traininglossPruning regularizationdefinedby nodesMaxdepth constraintonthefunctionspaceSmoothingleafvalues L2regularizationonleafweights RegressionTreeisnotjustforregression Regressiontreeensembledefineshowyoumakethepredictionscore itcanbeusedforClassification Regression Ranking Italldependsonhowyoudefinetheobjectivefunction Sofarwehavelearned UsingSquarelossWillresultsincommongradientboostedmachineUsingLogisticlossWillresultsinLogitBoost Outline ReviewofkeyconceptsofsupervisedlearningRegressionTreeandEnsemble WhatareweLearning GradientBoosting HowdoweLearn Summary TakeHomeMessageforthissection Bias variancetradeoffiseverywhereTheloss regularizationobjectivepatternappliesforregressiontreelearning functionlearning WewantpredictiveandsimplefunctionsThisdefineswhatwewanttolearn objective model Buthowdowelearnit Nextsection SoHowdoweLearn Objective WecannotusemethodssuchasSGD tofindf sincetheyaretrees insteadofjustnumericalvectors Solution AdditiveTraining Boosting Startfromconstantprediction addanewfunctioneachtime Modelattrainingroundt Newfunction Keepfunctionsaddedinpreviousround AdditiveTraining Considersquareloss Howdowedecidewhichftoadd Optimizetheobjective ThepredictionatroundtisThisiswhatweneedtodecideinroundt Goal find tominimizethis Thisisusuallycalledresidualfrompreviousround TaylorExpansionApproximationofLoss GoalSeemsstillcomplicatedexceptforthecaseofsquarelossTakeTaylorexpansionoftheobjectiveRecallDefine Ifyouarenotcomfortablewiththis thinkofsquarelossComparewhatwegettopreviousslide OurNewGoal Objective withconstantsremovedwhereWhyspendingsmucheffortstoderivetheobjective whynotjustgrowtrees Theoreticalbenefit knowwhatwearelearning convergenceEngineeringbenefit recalltheelementsofsupervisedlearningandcomesfromdefinitionoflossfunctionThelearningoffunctiononlydependontheobjectiveviaandThinkofhowyoucanseparatemodulesofyourcodewhenyouareaskedtoimplementboostedtreeforbothsquarelossandlogisticloss Refinethedefinitionoftree Wedefinetreebyavectorofscoresinleafs andaleafindexmappingfunctionthatmapsaninstancetoaleaf age 15 ismale Y N Y N Leaf1 Leaf2 Leaf3 q 1 q 3 w1 2 w2 0 1 w3 1 Thestructureofthetree Theleafweightofthetree DefineComplexityofaTree cont Definecomplexityas thisisnottheonlypossibledefinition Numberofleaves L2normofleafscores age 15 ismale Y N Y N Leaf1 Leaf2 Leaf3 w1 2 w2 0 1 w3 1 RevisittheObjectives DefinetheinstancesetinleafjasRegrouptheobjectivebyeachleaf ThisissumofTindependentquadraticfunctions TheStructureScore TwofactsaboutsinglevariablequadraticfunctionLetusdefine Assumethestructureoftree q x isfixed theoptimalweightineachleaf andtheresultingobjectivevalueare Thismeasureshowgoodatreestructureis TheStructureScoreCalculation age 15 ismale Y N Y N Instanceindex 1 2 3 4 5 g1 h1 g2 h2 g3 h3 g4 h4 g5 h5 gradientstatistics Thesmallerthescoreis thebetterthestructureis SearchingAlgorithmforSingleTree EnumeratethepossibletreestructuresqCalculatethestructurescorefortheq usingthescoringeq Findthebesttreestructure andusetheoptimalleafweight But therecanbeinfinitepossibletreestructures GreedyLearningoftheTree Inpractice wegrowthetreegreedilyStartfromtreewithdepth0Foreachleafnodeofthetree trytoaddasplit Thechangeof objectiveafteraddingthesplitis Remainingquestion howdowefindthebestsplit thescoreofleftchildthescoreofifwedonotsplitthescoreofrightchild Thecomplexitycostbyintroducingadditionalleaf EfficientFindingoftheBestSplit Allweneedissumofgandhineachside andcalculateLefttorightlinearscanoversortedinstanceisenoughtodecidethebestsplitalongthefeature g1 h1 g4 h4 g2 h2 g5 h5 g3 h3 Whatisthegainofasplitrule Sayisagea AnAlgorithmforSplitFinding Foreachnode enumerateoverallfeaturesForeachfeature sortedtheinstancesbyfeaturevalueUsealinearscantodecidethebestsplitalongthatfeatureTakethebestsplitsolutionalongallthefeaturesTimeComplexitygrowingatreeofdepthKItisO ndKlogn oreachlevel needO nlogn timetosortTherearedfeatures andweneedtodoitforKlevelThiscanbefurtheroptimized e g useapproximationorcachingthesortedfeatures Canscaletoverylargedataset WhataboutCategoricalVariables SometreelearningalgorithmhandlescategoricalvariableandcontinuousvariableseparatelyWecaneasilyusethescoringformulawederivedtoscoresplitbasedoncategoricalvariables Actuallyitisnotnecessarytohandlecategoricalseparately Wecanencodethecategoricalvariablesintonumericalvectorusingone hotencoding Allocatea categoricallengthvector Thevectorwillbesparseiftherearelotsofcategories thelearningalgorithmispreferredtohandlesparsedata PruningandRegularization Recallthegainofsplit itcanbenegative WhenthetraininglossreductionissmallerthanregularizationTrade offbetweensimplicityandpredictivnessPre stoppingStopsplitifthebestsplithavenegativegainButmaybeasplitcanbenefitfuturesplits Post PrunningGrowatreetomaximumdepth recursivelyprunealltheleafsplitswithnegativegain Recap BoostedTreeAlgorithm AddanewtreeineachiterationBeginningofeachiteration calculateUsethestatisticstogreedilygrowatreeAddtothemodelUsually insteadwedoiscalledstep sizeorshrinkage usuallysetaround0 1Thismeanswedonotdofulloptimizationineachstepandreservechanceforfuturerounds ithelpspreventoverfitting Outline ReviewofkeyconceptsofsupervisedlearningRegressionTreeandEnsemble WhatareweLearning GradientBoosting HowdoweLearn Summary Questionstocheckifyoureallygetit Howcanwebuildaboostedtreeclassifiertodoweightedregressionproblem suchthateachinstancehaveaimportanceweight Backtothetimeseriesproblem ifIwanttolearnstepfunctionsovertime Isthereotherwaystolearnthetimesplits otherthanthetopdownsplitapproach Questionstocheckifyoureallygetit Howcanwebuildaboostedtreeclassifiertodoweightedregressionproblem suchthateachinstancehaveaimportanceweight Defineobjective calculate feedittotheoldtreelearningalgorithmwehaveforun weightedversion Againthinkofseparationofmodelandobjective howdoesthetheorycanhelpbetterorganizingthemachinelearningtoolkit Questionstocheckifyoureallygetit Timeseriesproblem AllthatisimportantisthestructurescoreofthesplitsTop downgreedy sameastreesBottom upgreedy startfromindividualpoints