machine-learning-17

Quiz1onWednesday•~20multiplechoiceorshortanswerquestions•Inclass,fullperiod•Onlycoversmaterialfromlecture,withabiastowardstopicsnotcoveredbyprojects•Studystrategy:Reviewtheslidesandconsulttextbooktoclarifyconfusingparts.Project3previewMachineLearningComputerVisionJamesHays,BrownSlides:IsabelleGuyon,ErikSudderth,MarkJohnson,DerekHoiem,LanaLazebnikPhoto:CMUMachineLearningDepartmentprotestsG20ClusteringStrategies•K-means–Iterativelyre-assignpointstothenearestclustercenter•Agglomerativeclustering–Startwitheachpointasitsownclusteranditerativelymergetheclosestclusters•Mean-shiftclustering–Estimatemodesofpdf•Spectralclustering–SplitthenodesinagraphbasedonassignedlinkswithsimilarityweightsAswegodownthischart,theclusteringstrategieshavemoretendencytotransitivelygrouppointseveniftheyarenotnearbyinfeaturespaceThemachinelearningframework•Applyapredictionfunctiontoafeaturerepresentationoftheimagetogetthedesiredoutput:f()=“apple”f()=“tomato”f()=“cow”Slidecredit:L.LazebnikThemachinelearningframeworky=f(x)•Training:givenatrainingsetoflabeledexamples{(x1,y1),…,(xN,yN)},estimatethepredictionfunctionfbyminimizingthepredictionerroronthetrainingset•Testing:applyftoaneverbeforeseentestexamplexandoutputthepredictedvaluey=f(x)outputpredictionfunctionImagefeatureSlidecredit:L.LazebnikPredictionStepsTrainingLabelsTrainingImagesTrainingTrainingImageFeaturesImageFeaturesTestingTestImageLearnedmodelLearnedmodelSlidecredit:D.HoiemandL.LazebnikFeatures•Rawpixels•Histograms•GISTdescriptors•…Slidecredit:L.LazebnikClassifiers:Nearestneighborf(x)=labelofthetrainingexamplenearesttox•Allweneedisadistancefunctionforourinputs•Notrainingrequired!TestexampleTrainingexamplesfromclass1Trainingexamplesfromclass2Slidecredit:L.LazebnikClassifiers:Linear•Findalinearfunctiontoseparatetheclasses:f(x)=sgn(wx+b)Slidecredit:L.LazebnikManyclassifierstochoosefrom•SVM•Neuralnetworks•NaïveBayes•Bayesiannetwork•Logisticregression•RandomizedForests•BoostedDecisionTrees•K-nearestneighbor•RBMs•Etc.Whichisthebestone?Slidecredit:D.Hoiem•Imagesinthetrainingsetmustbeannotatedwiththe“correctanswer”thatthemodelisexpectedtoproduceContainsamotorbikeRecognitiontaskandsupervisionSlidecredit:L.LazebnikUnsupervised“Weakly”supervisedFullysupervisedDefinitiondependsontaskSlidecredit:L.LazebnikGeneralization•Howwelldoesalearnedmodelgeneralizefromthedataitwastrainedontoanewtestset?Trainingset(labelsknown)Testset(labelsunknown)Slidecredit:L.LazebnikGeneralization•Componentsofgeneralizationerror–Bias:howmuchtheaveragemodeloveralltrainingsetsdifferfromthetruemodel?•Errorduetoinaccurateassumptions/simplificationsmadebythemodel–Variance:howmuchmodelsestimatedfromdifferenttrainingsetsdifferfromeachother•Underfitting:modelistoo“simple”torepresentalltherelevantclasscharacteristics–Highbiasandlowvariance–Hightrainingerrorandhightesterror•Overfitting:modelistoo“complex”andfitsirrelevantcharacteristics(noise)inthedata–Lowbiasandhighvariance–LowtrainingerrorandhightesterrorSlidecredit:L.LazebnikBias-VarianceTrade-off•Modelswithtoofewparametersareinaccuratebecauseofalargebias(notenoughflexibility).•Modelswithtoomanyparametersareinaccuratebecauseofalargevariance(toomuchsensitivitytothesample).Slidecredit:D.HoiemBias-VarianceTrade-offE(MSE)=noise2+bias2+varianceSeethefollowingforexplanationsofbias-variance(alsoBishop’s“NeuralNetworks”book):•:D.HoiemBias-variancetradeoffTrainingerrorTesterrorUnderfittingOverfittingComplexityLowBiasHighVarianceHighBiasLowVarianceErrorSlidecredit:D.HoiemBias-variancetradeoffManytrainingexamplesFewtrainingexamplesComplexityLowBiasHighVarianceHighBiasLowVarianceTestErrorSlidecredit:D.HoiemEffectofTrainingSizeTestingTrainingGeneralizationErrorNumberofTrainingExamplesErrorFixedpredictionmodelSlidecredit:D.HoiemRemember…•Noclassifierisinherentlybetterthananyother:youneedtomakeassumptionstogeneralize•Threekindsoferror–Inherent:unavoidable–Bias:duetoover-simplifications–Variance:duetoinabilitytoperfectlyestimateparametersfromlimiteddataSlidecredit:D.HoiemSlidecredit:D.HoiemHowtoreducevariance?•Chooseasimplerclassifier•Regularizetheparameters•GetmoretrainingdataSlidecredit:D.HoiemVerybrieftourofsomeclassifiers•K-nearestneighbor•SVM•BoostedDecisionTrees•Neuralnetworks•NaïveBayes•Bayesiannetwork•Logisticregression•RandomizedForests•RBMs•Etc.Generativevs.DiscriminativeClassifiersGenerativeModels•Representboththedataandthelabels•Often,makesuseofconditionalindependenceandpriors•Examples–NaïveBayesclassifier–Bayesiannetwork•ModelsofdatamayapplytofuturepredictionproblemsDiscriminativeModels•Learntodirectlypredictthelabelsfromthedata•Often,assumeasimpleboundary(e.g.,linear)•Examples–Logisticregression–SVM–Boosteddecisiontrees•OfteneasiertopredictalabelfromthedatathantomodelthedataSlidecredit:D.HoiemClassification•Assigninputvectortooneoftwoormoreclasses•Anydecisionruledividesinputspaceintodecisionregionsseparatedby