Graphical Models for High Dimensional Density Estimation.pdf

GraphicalModelsforHighDimensional DensityEstimation Thesissubmitted pletionoftherequirements forthedegreeof BachelorofSciencewithHonours inthe DepartmentofMathematics atthe AustralianNationalUniversity 14June2002 Supervisors Acknowledgements ,whotrulytaughtmetolovemathematics. Particularthankstomyparents,andtoGod, alsotomysupervisors,whohavebeenunfailinglypositive,interestedandhelpful. IacknowledgetheassistanceofMinosGarofalakis,whokindlysentmeacopyofaBell Labsreportthatexpandedupontheirpublishedpapers. rades-in-armsStephen Leslie,PatrickCostello,andCathyMenon:forfriendship,encouragement,andmany Ham,whopointedoutlongagothatIwouldbemadnottodohonours(onthedubious assumptionthatIwasn’tmadtostartwith). MarkusHegland,StephenRobertsandmyparentshavebothdonesigni?cantquantities ofproofreading,anderrorsareentirelymyownfault. Manythankstomyhouse-matesDavidandGeo?,forrelievingmeofhavingtocookduring thelastfewweeks,andnumerousotherinstancesofpracticalsupportandencouragement overtheyear. Lastbutnotleast,fortheirongoingencouragementandprayers,inalphabeticalorder: Alistair,BenJ,theCardsgroupingeneral,severalDavids,Emma(inde?anceofprobabil- ity!),Liz(foremailfullofsunshine),Lu,Gubba,MattG,Nathan,Owen,Ruth,SteveJ,and manyother. ,thanksverymuchtoall! i Contents Acknowledgements i ListofFigures v Notation vii Chapter1. Introduction 1 . Motivation 1 . Summaryofresearch 2 . Outlineofthisthesis 2 . Originality 3 . Non-parametricmodels 4 Chapter2. DensityEstimation 7 . Probabilityindiscreteandcontinuousspaces 8 . Thedensityestimationproblem 14 . Thecurseofdimensionality 17 . Standardestimationtechniques 19 . Measuringthedistancebetweendensityestimates 24 . Non-parametricmodels 28 Chapter3. GraphTheory 31 . ChordalGraphs 33 . Trees 34