概率图模型导论——概率论与图论相结合.ppt

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

2、ordan. /jordan/graphical.html,Outline,Preparations Probabilistic Graphical Models (PGM) Directed PGM Undirected PGM Insights of PGM,Outline,Preparations PGM “is” a universal model Different thoughts of machine learning Different training approaches Different data types Bayes

3、ian Framework Chain rules of probability theory Conditional Independence Probabilistic Graphical Models (PGM) Directed PGM Undirected PGM Insights of PGM,Different thoughts of machine learning,Statistics (modeling uncertainty, detailed information) vs. Logics (modeling complexity, high level informa

4、tion) Unifying Logical and Statistical AI. Pedro Domingos, University of Washington. AAAI 2006. Speech: Statistical information (Acoustic model + Language model + Affect model) + High level information (Expert/Logics),Different training approaches,Maximum Likelihood Training: MAP (Maximum a Posterio

5、ri) vs. Discriminative Training: Maximum Margin (SVM) Speech: classical combination Maximum Likelihood + Discriminative Training,Different data types,Directed acyclic graph (Bayesian Networks, BN) Modeling asymmetric effects and dependencies: causal/temporal dependence (e.g. speech analysis, DNA seq

6、uence analysis) Undirected graph (Markov Random Fields, MRF) Modeling symmetric effects and dependencies: spatial dependence (e.g. image analysis),PGM “is” a universal model,To model both temporal and spatial data, by unifying Thoughts: Statistics + Logics Approaches: Maximum Likelihood Training + D

7、iscriminative Training Further more, the directed and undirected models together provide modeling power beyond that which could be provided by either alone.,Bayesian Framework,What we care is the conditional probability, and its is a ratio of two marginal probabilities.,A posteriori probability,Like

8、lihood,Priori probability,Class i,Normalization factor,Observation,Problem description Observation Conclusion (classification or prediction),Bayesian rule,Chain rules of probability theory,Conditional Independence,Outline,Preparations Probabilistic Graphical Models (PGM) Directed PGM Undirected PGM

9、Insights of PGM,PGM,Nodes represent random variables/states The missing arcs represent conditional independence assumptions The graph structure implies the decomposition,Directed PGM (BN),Representation,Conditional Independence,Probability Distribution,Queries,Implementation,Interpretation,Probabili

10、ty Distribution,Definition of Joint Probability Distribution,Check:,Representation,Graphical models represent joint probability distributions more economically, using a set of “local” relationships among variables.,Conditional Independence (basic),Assert the conditional independence of a node from i

11、ts ancestors, conditional on its parents.,Interpret missing edges in terms of conditional independence,Conditional Independence (3 canonical graphs),Classical Markov chain “Past”, “present”, “future”,Common cause Y “explains” all the dependencies between X and Z,Marginal Independence,Common effect M

12、ultiple, competing explanation,Conditional Independence,Conditional Independence (check),One incoming arrow and one outgoing arrow,Two outgoing arrows,Two incoming arrows,Check through reachability,Bayes ball algorithm (rules),Outline,Preparations Probabilistic Graphical Models (PGM) Directed PGM Un

13、directed PGM Insights of PGM,Undirected PGM (MRF),Representation,Conditional Independence,Probability Distribution,Queries,Implementation,Interpretation,Probability Distribution(1),Clique A clique of a graph is a fully-connected subset of nodes. Local functions should not be defined on domains of no

14、des that extend beyond the boundaries of cliques. Maximal cliques The maximal cliques of a graph are the cliques that cannot be extended to include additional nodes without losing the probability of being fully connected. We restrict ourselves to maximal cliques without loss of generality, as it cap

15、tures all possible dependencies. Potential function (local parameterization) : potential function on the possible realizations of the maximal clique,Probability Distribution(2),Maximal cliques,Probability Distribution(3),Joint probability distribution Normalization factor,Boltzman distribution,Condi

16、tional Independence,Its a “reachability” problem in graph theory.,Representation,Outline,Preparations Probabilistic Graphical Models (PGM) Directed PGM Undirected PGM Insights of PGM,Insights of PGM (Michael I. Jordan),Probabilistic Graphical Models are a marriage between probability theory and grap

17、h 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 quer