机器学习课件9. 计算学习理论.pptVIP

*计算学习理论*学习理论在什么样的条件下学习可能成功？在什么样的条件下某个特定的学习算法可以保证成功？*LearningTheoryTheoremsthatcharacterizeclassesoflearningproblemsorspecificalgorithmsintermsofcomputationalcomplexityorsamplecomplexity,i.e.thenumberoftrainingexamplesnecessaryorsufficienttolearnhypothesesofagivenaccuracy.Complexityofalearningproblemdependson:Sizeorexpressivenessofthehypothesisspace.学习器所考虑的假设空间的大小和复杂度Accuracytowhichtargetconceptmustbeapproximated.目标概念须近似到怎样的精度Probabilitywithwhichthelearnermustproduceasuccessfulhypothesis.学习器输出成功假设的可能性Mannerinwhichtrainingexamplesarepresented,e.g.randomlyorbyquerytoanoracle.训练样例提供给学习器的方式：由施教者给出或者随机生成。*TypesofResultsLearninginthelimit收敛性:Isthelearnerguaranteedtoconvergetothecorrecthypothesisinthelimitasthenumberoftrainingexamplesincreasesindefinitely?SampleComplexity样本复杂度:Howmanytrainingexamplesareneededforalearnertoconstruct(withhighprobability)ahighlyaccurateconcept?ComputationalComplexity计算复杂度:Howmuchcomputationalresources(timeandspace)areneededforalearnertoconstruct(withhighprobability)ahighlyaccurateconcept?Highsamplecomplexityimplieshighcomputationalcomplexity,sincelearneratleastneedstoreadtheinputdata.MistakeBound出错界限:Learningincrementally,howmanytrainingexampleswillthelearnermisclassifybeforeconstructingahighlyaccurateconcept.*LearningintheLimitGivenacontinuousstreamofexampleswherethelearnerpredictswhethereachoneisamemberoftheconceptornotandisthenistoldthecorrectanswer,doesthelearnereventuallyconvergetoacorrectconceptandnevermakeamistakeagain.Nolimitonthenumberofexamplesrequiredorcomputationaldemands,butmusteventuallylearntheconceptexactly,althoughdonotneedtoexplicitlyrecognizethisconvergencepoint.Bysimpleenumeration,conceptsfromanyknownfinitehypothesisspacearelearnableinthelimi