基于实例的学习

1第8章基于实例的学习InstanceBasedLearning2InstanceBasedLearningk-NearestNeighborLocallyweightedregressionRadialbasisfunctionsCase-basedreasoningLazyandeagerlearning3NearestneighborKeyidea:juststorealltrainingexamplesNearestneighbor:Givenqueryinstancexq,firstlocatenearesttrainingexamplexn,thenestimate)(,iixfx)()(ˆnqxfxf4k-Nearestneighbork-Nearestneighbor:Givenxq,Ifdiscrete-valuedtargetfunction:takevoteamongitsknearestnbrsIfreal-valuedtargetfunction:takemeanoffvaluesofk-nearestnbrskxfxfkiiq1)()(ˆ5WhenToConsiderNearestNeighborInstancesmaptopointsinLessthan20attributesperinstanceLotsoftrainingdatan6Advantages&DisadvantagesAdvantages•Trainingisveryfast•Learncomplextargetfunctions•Don’tloseinformationDisadvantagesSlowatquerytimeEasilyfooledbyirrelevantattributes7VoronoiDiagram8BehaviorintheLimitConsiderp(x)definesprobabilitythatinstancexwillbelabeled1(positive)versus0(negative)NearestneighborAsnumberoftrainingexamples∞approachesGibbsAlgorithmGibbs:withprobabilityp(x)predict1else09BehaviorintheLimitConsiderp(x)definesprobabilitythatinstancexwillbelabeled1(positive)versus0(negative)k-NearestneighborAsnumberoftrainingexamples∞andkgetslarge,approachesBayesoptimalBayesoptimal:ifp(x)0.5thenpredict1,else0NoteGibbshasatmosttwicetheexpectederrorofBayesoptimal10Distance-WeightedkNNNearerneighborsaremoreheavilyweighted.Discrete-valuedReal-valuedwherekiiiVvqxfvwxf1))(,(maxarg)(ˆkiikiiiqwxfwxf11)()(ˆ2),(1iqixxdwItmakessensetousealltrainingexamplesinsteadofjustk.[Shepard,1968]11CurseofDimensionalityImagineinstancesdescribedby20attributesbutonly2arerelevanttotargetfunction.Curseofdimensionality:nearestnbriseasilymisleadwhenhigh-dimensionalXApproach:Stretchsomeaxesbyweight,andthencross-validation[MooreandLee,1944]12LocallyWeightedRegressionNotekNNformslocalapproximationtofforeachquerypointxq.Whynotformanexplicitapproximationforregionsurroundingxq?FitlinearfunctiontoknearestneighborsFitquadratic…Producespiecewiseapproximationtof)(ˆxf13Severalchoicesoferrortominimize•Squarederroroverknearestnbrs•Distance-weightedsquarederroroverallnbrs•…个近邻的kxxqqxfxfxE21))(ˆ)((21)(DxqqxxdKxfxfxE)),(())(ˆ)((21)(22)()()(ˆ110xawxawwxfnn14RadialBasisFunctionNetworksGlobalapproximationtotargetfunctionintermsoflinearcombinationoflocalapproximationsAdiferentkindofneuralnetworkCloselyrelatedtodistance-weightedregressionbut“eager”insteadof“lazy”15RadialBasisFunctionNetworks•whereai(x)aretheattributesdescribinginstancex,and•OnecommonchoiceforKu(d(xu,x))isKu(d(xu,x))=kuuuuxxdKwwxf10)),(()(),(2122xxduue16TrainingRBFNetworks•Q2:HowtotrainweightsassumehereGaussianKu•FirstchoosevarianceandperhapsmeanforeachKu--e.g.useEM•ThenholdKufixedandtrainlinearoutputlayer–efficientmethodstofitlinearfunction个近邻的kxxjqiqxaxfxfxxdKw)())(ˆ)())(,((17Case-BasedReasoning•Canapplyinstance-basedlearningevenwhen.•Case-BasedReasoningisinstance-basedlearningappliedtoinstanceswithsymboliclogicdescriptions.nX18Case-BasedReasoninginCADET•CADET:75storedexamplesofmechanicaldevices•eachtrainingexample:qualitativefunction(定性的功能),mechanicalstructure•newquerydesiredfunction•targetvalue:mechanicalstructureforthisfunction•Distancemetric:matchqualitativefunctiondescriptions192021LazyandEagerLearningLazy:waitforquerybeforegeneralizing•k-NearestNeighbor,LocallyWeightedRegression,Casebasedreasoning•Eager:generalizebeforeseeingquery•Radialbasisfunctionnetworks,ID3,Backpropagation,NaiveBayes22Doesitmatter?•Eagerlearnermustcreateglobalapproximation•Lazylearnercancreatemanylocalapproximations•iftheyusesameH,lazycanrepresentmorecomplexfns(e.g.considerH=linearfunctions)