概率图模型导论概率论与图论相结合

1、第十讲 概率图模型导论 Chapter 10 Introduction to Probabilistic Graphical Models Weike Pan, and Congfu Xupanweike, xucongfu Institute of Artificial Intelligence College of Computer Science, Zhejiang UniversityOctober 12, 2006浙江大学计算机学院人工智能引论课件ReferencesAn Introduction to Probabilistic Graphical Models. Michael

2、I. Jordan. OutlinePreparationsProbabilistic Graphical Models (PGM)Directed PGMUndirected PGMInsights of PGMOutlinePreparationsPGM “is” a universal modelDifferent thoughts of machine learningDifferent training approachesDifferent data typesBayesian FrameworkChain rules of probability theoryConditiona

3、l IndependenceProbabilistic Graphical Models (PGM)Directed PGMUndirected PGMInsights of PGMDifferent thoughts of machine learningStatistics (modeling uncertainty, detailed information) vs. Logics (modeling complexity, high level information)Unifying Logical and Statistical AI. Pedro Domingos, Univer

4、sity of Washington. AAAI 2006.Speech: Statistical information (Acoustic model + Language model + Affect model) + High level information (Expert/Logics)Different training approachesMaximum Likelihood Training: MAP (Maximum a Posteriori) vs. Discriminative Training: Maximum Margin (SVM)Speech: classic

5、al combination Maximum Likelihood + Discriminative TrainingDifferent data typesDirected acyclic graph (Bayesian Networks, BN)Modeling asymmetric effects and dependencies: causal/temporal dependence (e.g. speech analysis, DNA sequence analysis)Undirected graph (Markov Random Fields, MRF)Modeling symm

6、etric effects and dependencies: spatial dependence (e.g. image analysis)PGM “is” a universal modelTo model both temporal and spatial data, by unifyingThoughts: Statistics + LogicsApproaches: Maximum Likelihood Training + Discriminative Training Further more, the directed and undirected models togeth

7、er provide modeling power beyond that which could be provided by either alone.Bayesian FrameworkWhat we care is the conditional probability, and its is a ratio of two marginal probabilities.A posteriori probabilityLikelihoodPriori probabilityClass iNormalization factorObservationProblem description

8、Observation Conclusion (classification or prediction)Bayesian ruleChain rules of probability theoryConditional IndependenceOutlinePreparationsProbabilistic Graphical Models (PGM)Directed PGMUndirected PGMInsights of PGMPGMNodes represent random variables/statesThe missing arcs represent conditional

9、independence assumptions The graph structure implies the positionDirected PGM (BN)RepresentationConditional IndependenceProbability DistributionQueriesImplementationInterpretationProbability DistributionDefinition of Joint Probability DistributionCheck:RepresentationGraphical models represent joint

10、probability distributions more economically, using a set of “local” relationships among variables.Conditional Independence (basic)Assert the conditional independence of a node from its ancestors, conditional on its parents.Interpret missing edges in terms of conditional independenceConditional Indep

11、endence (3 canonical graphs) Classical Markov chain“Past”, “present”, “future”Common causeY “explains” all the dependencies between X and ZMarginal Independence Common effect Multiple, competing explanationConditional IndependenceConditional Independence (check)One ing arrow and one outgoing arrowTw

12、o outgoing arrowsTwo ing arrowsCheck through reachabilityBayes ball algorithm (rules)OutlinePreparationsProbabilistic Graphical Models (PGM)Directed PGMUndirected PGMInsights of PGMUndirected PGM (MRF)RepresentationConditional IndependenceProbability DistributionQueriesImplementationInterpretationPr

13、obability Distribution(1)CliqueA clique of a graph is a fully-connected subset of nodes.Local functions should not be defined on domains of nodes that extend beyond the boundaries of cliques.Maximal cliquesThe maximal cliques of a graph are the cliques that cannot be extended to include additional n

14、odes without losing the probability of being fully connected.We restrict ourselves to maximal cliques without loss of generality, as it captures all possible dependencies.Potential function (local parameterization) : potential function on the possible realizations of the maximal clique Probability D

15、istribution(2)Maximal cliquesProbability Distribution(3)Joint probability distribution Normalization factorBoltzman distributionConditional IndependenceIts a “reachability” problem in graph theory.RepresentationOutlinePreparationsProbabilistic Graphical Models (PGM)Directed PGMUndirected PGMInsights

16、 of PGMInsights of PGM (Michael I. Jordan)Probabilistic Graphical Models are a marriage between probability theory and graph theory. A graphical model can be thought of as a probabilistic database, a machine that can answer “queries” regarding the values of sets of random variables. We build up the database in pieces, using probability theory to ensure that the pieces have a consistent overall interpretation. Probability theory also justifies the inferential machinery that allows the pieces to be put together “on the fly” to answer the queries. I