2008-5-6 Wang Houfeng, Icler, PKU 1
Graphical Model
Wang Houfeng
Institute of Computational Linguistics
Peking University
2008-5-6 Wang Houfeng, Icler, PKU 2
Outline
¾Intro
• Directed Graph(BN)
• Undirected Graphical Model(MRF)
• General Inference in GM
• Variable elimination
• Belief Propagation
2008-5-6 Wang Houfeng, Icler, PKU 3
Overview
• Graphical models define probability distributions
over complex domains.
• These distributions are too complex to directly
estimate or work with. Thus, we factorize the
distribution - i.e. divide it into manageable parts.
these models allows us to estimate the probability of
various events and to find the events which maximize
that probability
2008-5-6 Wang Houfeng, Icler, PKU 4
Typical Applications
• These are particularly useful in NLP:
naive Bayes for document classification
n-grams for language modelling
Hidden Markov Models (HMMs) for sequencing tasks
(chunking, POS tagging, named entity recognition)
probabilistic context free grammars (P-CFGs) for
syntax parsing
…
2008-5-6 Wang Houfeng, Icler, PKU 5
Graphical Model
• Modularity: a complex system is built by combining
simpler parts(node).
• Probability theory: ensures consistency, provides
interface models to data(node &edge).
• Graph theory: efficient general purpose algorithms.
Probability Theory Graph Theory
+
评论3