Foundation of Machine Learning [Part02]

《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,￿m1error￿D(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