机器学习与概率图模型 中科院自动化所系列报告 (王立威)

MachineLearningandGraphicalModels王立威北京大学信息科学技术学院[e-mail](LectureI)OutlineAbriefoverviewofMachineLearningGraphicalModels•Representation•Inference•Learning2DefinitionofMachineLearning:•Learningfromexperiences.“AcomputerprogramissaidtolearnfromexperienceEwithrespecttosomeclassoftasksTandperformancemeasureP,ifitsperformanceattasksinT,asmeasuredbyP,improveswithexperienceE.”-TomMitchell3“Classical”MachineLearningTasks:•Classification:spamfilter,facerecognition,…•RegressionHook’slaw,Kepler’slaw,…•RankingSearchengine•Probability(Distribution)Estimation4}1,1{:nfRRRnf:RRnf:“Classical”MachineLearningAlgorithms•ClassificationSVMBoostingRandomForestBagging(Deep)NeuralNetworks•RegressionLassoBoosting5SupportVectorMachines(SVMs)SVM:thelargemarginclassifierSVM:hingelossminimization+regularization22ll/BoostingBoosting:(implicit)largemarginclassifierBoosting:explossminimization(+regularization)ll/1“Classical”MachineLearningTheories•VCtheoryCapacityofthehypothesisspace•PAC-theory•MargintheoryConfidence•EmpiricalProcessesCapacity•PAC-BayestheoryPACinBayesframework•RegularizationCapacity,smoothness8MLtheories:QuantificationofOccam’sRazorForceLengthHook’slawComparisonof“Classical”MachineLearningTheories•Regularization:BayesianoptimalityOnlyasymptotic(convergence,rate,non-uniform)•VC/PAC,Margin,PAC-Bayes,…Relativeoptimality(optimalinahypothesisspace)Non-asymptotic(finitesamplebounds)10Limitationsofthe“Classical”ML•RepresentationEuclideanrepresentationforinput.Simplerepresentationforoutput.HowtorepresentSTRUCTURESindata?11OutlineAbriefoverviewofMachineLearningGraphicalModels•Representation•Inference•Learning12ChapterI:Representation13ProbabilisticGraphicalModels:WhatandWhy•PGMs:Amodelforjointprobabilitydistributionoverrandomvariables.Representdependenciesandindependenciesbetweentherandomvariables.•Whyisprobabilitydistributionimportant?Genesanddiseases,andeverything•WhyPGMwasinventedbycomputerscientist,whynotthestatisticians?14TwotypesofPGMs•Directedgraph:BayesianNetworks(BNs).•Undirectedgraph:MarkovRandomFields(MRFs)15BayesianNetworks(BNs)16(Intuitively)HowBNsRepresentJointpdfs:17Example1:ACB)|()|()()(BCPABPAPABCPGivenB,CandAareindependentNote:Dependencyvs.Causality(Intuitively)HowBNsRepresentJointpdfs:18Example2:ACB)|()|()()(ACPABPAPABCPGivenA,BandCareindependent(Intuitively)HowBNsRepresentJointpdfs:19Example3:ACB)|()()()(BCAPCPBPABCPBandCareindependent;ButgivenA,BandCareNOTindependent(Intuitively)HowBNsRepresentJointpdfs:20Example4:ACB)|()|()|()|()|()()()(EGPDFPCEPADPABCPBPAPABCDEFGPEDFGLearning:Findafactorizationruleaccordingtopreviousexamples.21ACB)|()|()|()|()|()()()(EGPDFPCEPADPABCPBPAPABCDEFGPEDFGFactorization:22ACBEDFGBNmustbeDAGThegraphmustbeacyclic!Definition(FactorizeaccordingtoaDAG):AprobabilitydistributionPissaidtobefactorizedaccordingtoadirectedacyclicgraphGif23Definition(BayesianNetwork):ABayesiannetworkisapair(P,G)ofaprobabilitydistributionandaDAG,wherePisfactorizedaccordingtoG,andallthe“local”conditionalprobabilitydistributionsaregiven.24Giventhefactorization,whichvariablesareindependentofC,givenC’sParentsAandB?25ACBEDFGFD,)|()|()|()|()|()()()(EGPDFPCEPADPABCPBPAPABCDEFGP26ACBEDFG)|()|()|()|()|()()()(EGPDFPCEPADPABCPBPAPABCDEFGP)|()|()|(ABDPABCPABCDP)|()|()|(ABFPABCPABCFPQuestion:LetCbeanode(randomvariable)inaBN.Whichnodes(randomvariables)areindependentofC,givenC’sParents?27Theorem(LocalMarkovpropertyforBN):ForanynodeC(randomvariable)inaBN,allnodesthatarenotdescendentsofCareindependentofC,givenC’sparents.Sparsevs.Dense28ACBDACBDVSWhatisthejointpdfoftherightBN?IsthereanyindependenceintherightBN?Question:GivenaBN=(P,G),canyoudetermine,forthreearbitrarysetsofrandomvariablesX={…},Y={…},andZ={…},whetherthefollowingconditionalindependencyhold?29Definition(activetrailinBN)Letx,ybetwonodesandZbeasetofnodes.ApathbetweenxandyaresaidtobeanactivetrialgivenZ,ifthefollowingsaretrue:1)Letbethepath,thenmoroneofitsdescendantsisnotinZ.Thatis,wheneverthereisa“v-structure”inthepath,themiddlenodeoroneofitsdescendantsisinZ;2)NoothernodealongthepathisinZ.30yymxx...''...Definition(D-separationinBN)LetX,Y,Zbethreesetsofnodes.XandYaresaidtobeD-separatedbyZifforeverynodexinXandeveryyinY,andeverypathbetweenxandy,thepathisnotanactivetrialgivenZ.Theorem(Informal)TheindependenciesinaBNareexactlythosecharacterizedbyD-separation.31TheoremForanyBN(P,G),andarbitrarysetsofnodesX,Y,Z.IfXandYareD-separatedbyZinG,then32P(Y|Z)P(X|Z)P(X,Y|Z)TheoremForanyDAGG,andanysetsofnodesX,Y,Z.IfXandYarenotD-separatedbyZinG,thentheremustexistaprobabilitydistributionPwhichfactorizeaccordingtoG,but33P(Y|Z)P(X|Z)P(X,Y|Z)34IsthereaBNthathaspreciselytheseindependencies?NoteverydistributioncanberepresentedbyaBNsatisfyingexactlyalltheindependencies!TheRepresentationLimitofBNTosumup:•BNrepresentsjointprobabilitydistributionsthatcanfactorizeaccordingto:•ThelocalindependenciesinBNarecharacterizedbyparentsandnon-descendants.•Theglobali