CS 3710 Advanced Topics in AI
                                                    Lecture 3
                                           Probabilistic graphical 
                                                      models 
                            Milos Hauskrecht
                            milos@cs.pitt.edu
                            5329 Sennott Square
                                               CS 3710 Probabilistic graphical models
                                Modeling uncertainty with probabilities
                            •  Representing large multivariate distributions directly and 
                               exhaustively is hopeless:
                                – The number  of parameters is exponential in the number of 
                                  random variables
                                – Inference can be exponential in the number of variables
                            •  Breakthrough  (late 80s, beginning of 90s)
                                – Bayesian belief networks
                                   • Give solutions to the space, acquisition bottlenecks
                                   • Partial solutions for time complexities
                                               CS 3710 Probabilistic graphical models
                                                                                                              1
                                              Graphical models
                            Aim: alleviate the representational and computational 
                              bottlenecks 
                            Idea: Take advantage of the structure, more specifically,  
                              independences and conditional independences that hold 
                              among random variables
                            Two classes of models:
                               – Bayesian belief networks
                                  • Modeling asymmetric (causal) effects and dependencies
                               – Markov random fields
                                  • Modeling symmetric effects and dependencies among 
                                    random variables
                                  • Used often to model spatial dependences (image 
                                    analysis)
                                               CS 3710 Probabilistic graphical models
                                    Bayesian belief networks (BBNs)
                            Bayesian belief networks.
                            •  Represent the full joint distribution over the variables more 
                               compactly using a smaller number of parameters. 
                            •  Take advantage of conditional and marginal independences
                               among random variables
                            •  A and B are independent
                                        P(A,B) = P(A)P(B)
                            •  A and B are conditionally independent given C
                                      P(A,B|C) = P(A|C)P(B|C)
                                      P(A|C,B) = P(A|C)
                                               CS 3710 Probabilistic graphical models
                                                                                                              2
                                             Bayesian belief networks (general)
                                    Two  components: B = (S,ΘS)                                  B           E
                                    •  Directed acyclic graph
                                        – Nodes correspond to random variables                          A
                                        – (Missing) links encode independences
                                                                                                  J           M
                                    •  Parameters
                                        – Local conditional probability distributions
                                           for every variable-parent configuration             P(A|B,E)
                                           P(X | pa(X ))                                    B   E     T       F
                                                 i          i                               T   T    0.95   0.05
                                        Where:                                              T   F     0.94   0.06
                                               pa(X ) -stand for parents of  X              F   T     0.29   0.71
                                                      i                              i      F   F     0.001 0.999
                                                           CS 3710 Probabilistic graphical models
                                                     Bayesian belief network.
                                                      P(B)                                  P(E)
                                                        T        F                           T         F
                                       Burglary       0.001 0.999       Earthquake         0.002  0.998
                                                                          P(A|B,E)
                                                                       B   E      T       F
                                                                       T   T    0.95   0.05
                                                       Alarm           T   F     0.94   0.06
                                                                       F   T     0.29   0.71
                                                                       F   F     0.001 0.999
                                                            P(J|A)                              P(M|A)
                                                      A    T      F                       A      T      F
                                      JohnCalls       T    0.90  0.1     MaryCalls        T    0.7    0.3
                                                      F    0.05  0.95                     F    0.01   0.99
                                                           CS 3710 Probabilistic graphical models
                                                                                                                                           3
                                      Full joint distribution in BBNs
                             Full joint distribution is defined in terms of local conditional 
                               distributions (obtained via the chain rule):
                               P(X1,X2,.., Xn) = ∏P(Xi | pa(Xi))
                                                    i=1,..n
                            Example:                                           B        E
                           Assume the following assignment                         A
                           of values to random variables                       J        M
                            B=T,E=T,A=T,J=T,M=F
                           Then its probability is:
                           P(B=T,E=T,A=T,J=T,M=F)=
                              P(B=T)P(E=T)P(A=T|B=T,E=T)P(J=T|A=T)P(M=F|A=T)
                                               CS 3710 Probabilistic graphical models
                                     Bayesian belief networks (BBNs)
                             Bayesian belief networks 
                             • Represent the full joint distribution over the variables more 
                               compactly using the product of local conditionals. 
                             • But how did we get to local parameterizations?
                             Answer:
                             • Graphical structure encodes conditional and marginal 
                               independences among random variables
                             • A and B are independent    P(A,B) = P(A)P(B)
                             • A and B are conditionally independent given C
                                          P(A|C,B) = P(A|C)
                                        P(A,B|C) = P(A|C)P(B|C)
                             • The graph structure implies the decomposition !!!
                                               CS 3710 Probabilistic graphical models
                                                                                                               4