Models
Probabilistic Graphical Models (PGM)
PA154 Jazykové modelování (8.1)
Pavel Rychlý
pary@fi.muni.cz
April 20, 2021
Source: Probabilistic Graphical Models Daphne Koller
http://www.cojr5era.org/learn/probabili5tic-graphical-modeh
Domain expert
Models
Declarative representation Data
V huh f —
Model   I 1"™i"s
^ i   Alsonllim Algorithm
Probabilistic Graphical Models (PGM)
Probabilistic Graphical Models (PGM)
Graphical models
Textual Information Extraction
Bayesian networks
Xj., . . . , X„ - nodes directed graph
Markov networks
undirected graph
Mrs. Green spoke today in  New York. Green chairs the finance committee. Person Location    Person Organization
Mrs.     Green    spoke     todey       In        New      York     Green    chairs      the     finance committee
Probabilistic Graphical Models (PGM)
Probabilistic Graphical Models (PGM)
Graphical models
Graphical models
Bayesian networks
■ Grade
■ Course Difficulty
■ Student Intelligence
■ Student SAT
■ Reference Letter
P(G,D,I,S,L)
Probabilistic Graphical Models (PGM)
PA154 Jazykové modeli
Probabilistic Graphical Models (PGM)
Graphical models
Chain Rule for Bayesian Networks
	d1
0.6	0.4
	g1(A)	g2(B)	g3(C)
i°,d°	0.3	0.4	0.3
iV	0.0S	0.25	0.7
i1,d°	0.9	0.08	0.02
■V	0.5	0.3	0.2
	l°	I1
g1	0.1	0.9
2 g	0.4	0.6
q3	0.99	0.01
j° 0.95 0.05 j1 0.2 0.8
P(S|I)
p(D) ( Difficulty ) (Intelligence) p(l)
p(G|l,D)(fGrade J)   (T SAT )p(S|I)
Letter J)p(L|G)
P(DJ,G,S,L) = P{D)P{I)P{G\I, D)P(S\I)P(L\G) Distribution defined as a product of factors!
PA154 Jazykové model
Probabilistic Graphical Models (PGM)
Daphne Koller 7/22
PA154 Jazykové modeli
Probabilistic Graphical Models (PGM)
Chain Rule for Bayesian Networks
Bayesian network
d°	d1
0.6	0.4
	gV)	92(B)	g3(C)
i°.d°	0.3	0.4	0.3
i°,d1	0.05	0.25	0.7
iV	0.9	0.08	0.02
iV	0.5	0.3	0.2
	l°	I1
91	0.1	0.9
g2	0.4	0.6
q3	0.99	0.01
0.6*0.3*0.02*0.01*0.8
A Bayesian network is:
- A directed acyclic graph ( DAG) G whose nodes represent random variables Xi,..., X„
- For each node X a CPD P( X/| ParG(X,))
The BN represents a joint distribution via the chain rule for Bayesian networks
P(X-.,...,X„) = Xl,P{Xi\ParG{Xi))
c Graphical Models (PGM)
Daphne Koller 9/22
Probabilistic Graphical Models (PGM)
BN Is a Legal Distribution: P > 0
BN Is a Legal Distribution: E p = 1
P is a product of CPDs CPDs are non-negative
T.d.i.c.s.l p(°.'. G. 5, L) = T,d,,,g.s.l P(D)P(I)P{G\I, D)P(S\I)P(L\G) = T,D,,,G,sP(D)P(l)P(G\l,D)P(S\l)T.LP(L\G) = ED,,CSP(D)P(/)P(G|/,D)P(S|/) = ED,,,e P(D)P(/)P(G|/, D)£s P(3\l) = T,d,,P(D)P(I)T,gP(G\I,D)
PA154 Jazykové model
Probabilistic Graphical Models (PGM)
Probabilistic Graphical Models (PGM)
P Factorizes over G
Naive Bayes Model
Let G be a gra ph over Xi,..., X„. P factorizes over G if
P(X1,...,Xn) = lliP(Xi\ParG(Xi))
P{C,Xlt...,Xn) = P(C)Y[P(X;\C)
i=i
features X, Xj independent
Probabilistic Graphical Models (PGM)
Probabilistic Graphical Models (PGM) 14/22
Naive Bayes Classifier
Bernoulli Naive Bayes for Text
P(C=c'|xi,...,x„) _ P(C=c') ]-rn P(x,|C=c') P(C=c2|xi,...,x„) ~ P(C=c2) 11/=1 P(x;\C=c2)
cats dogs buy sell Financial 0.001 0.001 0.2 0.3 Pets      0.3    0.4    0.02 0.0001
I Pf'cat" appears | Label)
P(C=c'|xi,...,x„) _ P(C=c') Yjn P(x,|C=c') P(C=c2|xi,...,x„) — P(C=c2) 1 li'=l P(x,|C=c2)
Probabilistic Graphical Models (PGM)
Probabilistic Graphical Models (PGM)
Multinomial Naive Bayes for Text
Summary
cats dogs buy sell Financial 0.001 0.001 0.02 0.02 Pets      0.02  0.03 0.003 0.001
P(C=c'|xi,...,x„) _ P(C=c') T-rn P(x,|C=c') P(C=c2|xi,...,x„) — P(C=c2) 11/=1 P(x,|C=c2)
Simple approach for classification
► Computationally efficient
► Easy to construct
Surprisingly effective in domains with many weakly relevant features Strong independence assumptions reduce performance when many features are strongly correlated
Probabilistic Graphical Models (PGM)
PA154 Jazykové modeli
Probabilistic Graphical Models (PGM)
Application: Diagnosis
Medical Diagnosis: Pathfinder (1992)
Probabilistic
Graphical
Models
Representation Bayesian Networks
Application: Diagnosis
Help pathologist diagnose lymph node pathologies (60 different diseases)
Pathfinder I: Rule-based system
Pathfinder II used naive Bayes and got superior performance
Probabilistic Graphical Models (PGM) 19/22
Probabilistic Graphical Models (PGM)
Medical Diagnosis: Pathfinder (1992)
Medical Diagnosis: Pathfinder (1992)
Pathfinder III: Na'ive Bayes with better knowledge engineering
No incorrect zero probabilities
Better calibration of conditional probabilities
► P(finding\disease\) to P(finding\disease2)
► Not P(findingi\dise3se) to P(finding2\dise3se)
Heckerman et al.
■ Pathfinder 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 naive Bayes model
■ Accuracy as high as expert that designed the model
Heckerman et al.
Probabilistic Graphical Models (PGM) 21/22
Probabilistic Graphical Models (PGM)