The dissertation of Yoav Freund is approved

UniversityofCaliforniaSantaCruzDatalteringanddistributionmodelingalgorithmsformachinelearningAdissertationsubmittedinpartialsatisfactionoftherequirementsforthedegreeofDoctorofPhilosophyinComputerandInformationSciencesbyYoavFreundSeptember1993ThedissertationofYoavFreundisapproved:ManfredK.WarmuthDavidHausslerDavidP.HelmboldDeanofGraduateStudiesandResearchCopyrightcbyYoavFreund1993iiiContentsAbstractviAcknowledgmentsvii1.Introduction11.1Boostingbymajority::::::::::::::::::::::::::::::::::::::::41.2QueryByCommittee:::::::::::::::::::::::::::::::::::::::71.3Learningdistributionsofbinaryvectors:::::::::::::::::::::::::::::82.Boostingaweaklearningalgorithmbymajority102.1Introduction:::::::::::::::::::::::::::::::::::::::::::::102.2Themajority-votegame::::::::::::::::::::::::::::::::::::::142.2.1Optimalityoftheweightingscheme:::::::::::::::::::::::::::192.2.2Therepresentationalpowerofmajoritygates::::::::::::::::::::::202.3Boostingaweaklearnerusingamajorityvote::::::::::::::::::::::::::222.3.1Preliminaries::::::::::::::::::::::::::::::::::::::::222.3.2Boostingusingsub-sampling:::::::::::::::::::::::::::::::242.3.3BoostingUsingltering::::::::::::::::::::::::::::::::::312.3.4Randomizedlearningalgorithmsandrandomizedhypotheses:::::::::::::372.3.5TheresourcesneededforpolynomialPAClearning:::::::::::::::::::382.3.6Relationstootherbounds:::::::::::::::::::::::::::::::::402.4Extensions::::::::::::::::::::::::::::::::::::::::::::::412.4.1Usingboostingfordistribution-speciclearning:::::::::::::::::::::412.4.2Boostingmultiplevaluedconcepts::::::::::::::::::::::::::::452.4.3Boostingrealvaluedconcepts:::::::::::::::::::::::::::::::462.4.4ParallelizingPAClearning:::::::::::::::::::::::::::::::::472.5Summaryandopenproblems:::::::::::::::::::::::::::::::::::482.6Summaryofnotation::::::::::::::::::::::::::::::::::::::::482.6.1ConceptLearningNotation::::::::::::::::::::::::::::::::482.6.2Notationforthedescribingboosting:::::::::::::::::::::::::::492.6.3Meaningofcommonnotationindierentsections::::::::::::::::::::502.6.4SpecialNotation::::::::::::::::::::::::::::::::::::::50iv3.AcceleratinglearningusingQuerybyCommittee523.1Introduction:::::::::::::::::::::::::::::::::::::::::::::523.2Preliminaries::::::::::::::::::::::::::::::::::::::::::::543.3Twosimplelearningproblems:::::::::::::::::::::::::::::::::::553.4TheQuerybyCommitteelearningalgorithm::::::::::::::::::::::::::573.5RelatinginformationgainandpredictionerrorforQuerybyCommittee:::::::::::593.6ConceptclassesthatareecientlylearnableusingQBC::::::::::::::::::::643.6.1Uniformlydistributedhalf-spaces:::::::::::::::::::::::::::::643.6.2Relaxingtheuniformityconstraints:::::::::::::::::::::::::::713.6.3Perceptrons:::::::::::::::::::::::::::::::::::::::::743.7Learningusingunlabeledexamplesandmembershipqueries::::::::::::::::::773.8Summary::::::::::::::::::::::::::::::::::::::::::::::784.Unsupervisedlearningofdistributionsonbinaryvectorsusingtwolayernetworks804.1Introduction:::::::::::::::::::::::::::::::::::::::::::::804.2Theinuencecombinationdistributionmodel::::::::::::::::::::::::::834.2.1Notation:::::::::::::::::::::::::::::::::::::::::::834.2.2TheModel:::::::::::::::::::::::::::::::::::::::::834.2.3Discussionofthemodel::::::::::::::::::::::::::::::::::864.2.4Comparisonwithprincipalcomponentsanalysis:::::::::::::::::::::894.2.5Universalityofthemodel:::::::::::::::::::::::::::::::::894.2.6Relationsbetweenthebinary-valuedandthereal-valuedmodels:::::::::::904.3Learningthemodelfromexamples::::::::::::::::::::::::::::::::924.3.1Learningbygradientascentonthelog-likelihood::::::::::::::::::::924.3.2Approximatingthegradient::::::::::::::::::::::::::::::::944.3.3ProjectionPursuitmethods::::::::::::::::::::::::::::::::954.3.4OverviewofProjectionPursuit::::::::::::::::::::::::::::::954.3.5ProjectionPursuitandthecombinationmodel:::::::::::::::::::::984.3.6PPalgorithmforlearningthecombinationmodel::::::::::::::::::::994.4Experimentalwork:::::::::::::::::::::::::::::::::::::::::1015.Concludingremarks113References119A.AppendixesregardingBoostingbyMajority123A.1Boostingthereliabilityofalearningalgorithm:::::::::::::::::::::::::123A.2Divisibilitylemma:::::::::::::::::::::::::::::::::::::::::123A.3ProofofLemma2.3.10:::::::::::::::::::::::::::::::::::::::125vB.Projectiondistributionsofthebinarycombinationmodel.127DatalteringanddistributionmodelingalgorithmsformachinelearningYoavFreundabstractThisthesisisconcernedwiththeanalysisofalgorithmsformachinelearning.Themainfocusisontheroleofthedistributionoftheexamplesusedforlearning.Chapters2and3areconcernedwithalgorithmsforlearningconceptsfromrandomexamples.Briey,thegoalofthelearneristoobserveasetoflabeledinstancesandgenerateahypothesisthatapproximatestherulethatmapstheinstancestotheirlabels.Chapter2describesandanalysesanalgorithmforimprovingtheperformanceofageneralconceptlearningalgorithmbyselectingthoselabeledinstancesthataremostinformative.ThisworkisanimprovementoverpreviousworkbySchapire.Theanalysisprovidesupperboundsonthetime,spaceandnumberofe