PGM
Probabilistic Graphical Models (PGM)
PA154 Statistické nástroje pro korpusy
Fakulta informatiky
Masarykova Univerzita
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Models
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Graphical models
Bayesian networks
X1, . . . , Xn - nodes
directed graph
Markov networks
undirected graph
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Textual Information Extraction
Mrs. Green spoke today in New York. Green chairs the nance committee.
Person Location Person Organization
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Graphical models
Bayesian networks
Grade
Course Diculty
Student Intelligence
Student SAT
Reference Letter
P(G,D,I,S,L)
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Graphical models
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Graphical models
Daphne KollerPA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Chain Rule for Bayesian Networks
P(D,I,G,S,L) = P(D)P(I)P(G|I,D)P(S|I)P(L|G)
Distribution dened as a product of factors!
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Chain Rule for Bayesian Networks
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Bayesian network
A Bayesian network is:
 A directed acyclic graph ( DAG) G whose nodes represent
random variables X1, . . . , Xn
 For each node Xi a CPD P( Xi | ParG (Xi))
The BN represents a joint distribution via the chain rule for
Bayesian networks
P(X1, . . . , Xn) = i P(Xi|ParG(Xi))
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
BN Is a Legal Distribution: P ≥ 0
P is a product of CPDs
CPDs are non-negative
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
BN Is a Legal Distribution: P = 1
D,I,G,S,L P(D, I, G, S, L) = D,I,G,S,L P(D)P(I)P(G|I, D)P(S|I)P(L|G)
= D,I,G,S P(D)P(I)P(G|I, D)P(S|I) L P(L|G)
= D,I,G,S P(D)P(I)P(G|I, D)P(S|I)
= D,I,G P(D)P(I)P(G|I, D) S P(S|I)
= D,I P(D)P(I) G P(G|I, D)
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
P Factorizes over G
Let G be a graph over X1, . . . , Xn.
P factorizes over G if
P(X1, . . . , Xn) = i P(Xi|ParG(Xi))
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Naïve Bayes Model
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Naïve Bayes Classier
P(C=c1
|x1,...,xn)
P(C=c2|x1,...,xn)
= P(C=c1
)
P(C=c2)
n
i=1
P(xi|C=c1
)
P(xi|C=c2)
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Bernoulli Naïve Bayes for Text
P(C=c1
|x1,...,xn)
P(C=c2|x1,...,xn)
= P(C=c1
)
P(C=c2)
n
i=1
P(xi|C=c1
)
P(xi|C=c2)
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Multinomial Naïve Bayes for Text
P(C=c1
|x1,...,xn)
P(C=c2|x1,...,xn)
= P(C=c1
)
P(C=c2)
n
i=1
P(xi|C=c1
)
P(xi|C=c2)
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Summary
Simple approach for classication
Computationally ecient
Easy to construct
Surprisingly eective in domains with many weakly relevant
features
Strong independence assumptions reduce performance when
many features are strongly correlated
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Application: Diagnosis
Representation
Bayesian Networks
Application:
Diagnosis
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Medical Diagnosis: Pathnder (1992)
Help pathologist diagnose lymph node pathologies (60
dierent diseases)
Pathnder I: Rule-based system
Pathnder II used naïve Bayes and got superior performance
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Medical Diagnosis: Pathnder (1992)
Pathnder III: Naïve Bayes with better knowledge engineering
No incorrect zero probabilities
Better calibration of conditional probabilities
P(nding | disease1) to P(nding | disease2)
Not P(nding1 | disease) to P(nding2 | disease)
Heckerman et al.
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)
Medical Diagnosis: Pathnder (1992)
Pathnder IV: Full Bayesian network
Removed incorrect independencies;
Additional parents led to more accurate estimation of
probabilities
BN model agreed with expert panel in 50/53 cases, vs 47/53
for naïve Bayes model
Accuracy as high as expert that designed the model
Heckerman et al.
Daphne Koller
PA154 Statistické nástroje pro korpusy Probabilistic Graphical Models (PGM)