资源描述:
《Foundation of Machine Learning [Part02]》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、FoundationsofMachineLearningLecture2MehryarMohriCourantInstituteandGoogleResearchmohri@cims.nyu.eduPACLearningConcentrationBoundsMotivationSomecomputationallearningquestions•Whatcanbelearnedefficiently?•Whatisinherentlyhardtolearn?•Ageneralmodeloflearning?Complexity•Computationalcomplexity:timeandspa
2、ce.•Samplecomplexity:amountoftrainingdataneededtolearnsuccessfully.•Mistakebounds:numberofmistakesbeforelearningsuccessfully.MehryarMohri-FoundationsofMachineLearningpage3ThislecturePACModelSamplecomplexity-finitehypothesisspace-consistentcaseSamplecomplexity-finitehypothesisspace-inconsistentcaseConc
3、entrationboundsMehryarMohri-FoundationsofMachineLearningpage4DefinitionsX:setofallpossibleinstancesorexamples,e.g.,thesetofallmenandwomencharacterizedbytheirheightandweight.c:X→{0,1}:thetargetconcepttolearn,e.g.,c(x)=0foramale,c(x)=1forafemaleexample.C:conceptclass,asetoftargetconceptsc.D:targetdistr
4、ibution,afixedprobabilitydistributionoverX.TrainingandtestexamplesaredrawnaccordingtoD.MehryarMohri-FoundationsofMachineLearningpage5DefinitionsS:trainingsample.H:setofconcepthypotheses,e.g.,thesetofalllinearclassifiers.ThelearningalgorithmreceivessampleSandselectsahypothesishSfromHapproximatingc.Mehry
5、arMohri-FoundationsofMachineLearningpage6ErrorsTrueerrororgeneralizationerrorofhwithrespecttothetargetconceptcanddistributionD:errorD(h)=Pr[h(x)=c(x)].x∼DEmpiricalerror:averageerrorofhonthetrainingdatasampledaccordingtodistributionD,m1errorD(h)=1h(xi)=c(xi).mi=1MehryarMohri-FoundationsofMachineL
6、earningpage7PACModel(Valiant,1984)PAClearning:ProbablyApproximatelyCorrectlearning.Definition:conceptclassisCPAC-learnableifthereexistsalearningalgorithmsuchthat:L•forallandalldistributions,c∈C,>0,δ>0,DPr[error(hS)≤]≥1−δ,S∼D•forsamplesofsizeforafixedSm=poly(1/,1/δ)polynomial.MehryarMohri-Foundation
7、sofMachineLearningpage8RemarksConceptclassCisknowntothealgorithm.Distribution-freemodel:noassumptiononD.Bothtrainingandtestexamplesdrawn.∼DProbably:confidence.1−δApproximatelycorrect:accuracy.1−Efficie