Machine learning lecture 21 Tommi S Jaakkola MIT AI Lab tommi ai mit edu Topics Graphical models and decision theory utilities expected utility framework influence diagrams examples Exact inference in graphical models basics of probabilistic inference chains and clustering belief propagation and messages Tommi Jaakkola MIT AI Lab 2 Background utility theory Utilities provide a numerical scale at which to measure preferences about alternative outcomes For us to be able to cast our preferences as utilities our preferences need to satisfy a few reasonable conditions transitivity preferring B over A and C over B means that you also prefer C over A continuity for any such A B and C there s a probability p such that a lottery where we get A with probability p and C with probability 1 p is equally preferable to B a few other perhaps more self evident assumptions are needed Tommi Jaakkola MIT AI Lab 3 Background expected utility framework Once we have subjective utilities for each available action and each possible outcome situation we can decide which action we should take Expected utility framework Given a probability distribution P c over all the uncertain quantities c we ought to select the action that maximizes the expected utility X a argmax Ec P U c a argmax P c U c a a A a A c where A is the set of available actions and U c a is the utility of choosing action a in context c Tommi Jaakkola MIT AI Lab 4 Influence diagrams basics Influence diagrams are graphical models that combine beliefs about uncertain quantities available actions and associated utilities into a common representation c a U a argmax Ec P U c a a A Basic components decision node s squares specify the actions we can take chance nodes circles specify our belief about the values of variables relevant for decisions utility node diamond specifies the utility of any decision in a contex c Tommi Jaakkola MIT AI Lab 5 Influence diagrams example Minimum probability of error classification Suppose we know all the class conditional densities p x i i 1 m and the prior class probabilities P i x i a U The utility U i a 1 if i a and zero otherwise utility is defined as one minus error We do not have access to class i directly but the uncertainty about the class label is captured by the posterior P i x Tommi Jaakkola MIT AI Lab 6 Example cont d x i a U We choose the action class with the highest expected utility a argmax Ei P i x U i a a argmax a m X P i x U i a i 1 argmax P a x a which is the action that we have previously seen to minimize the probability of error Tommi Jaakkola MIT AI Lab 7 Influence diagrams cont d Our decisions may affect the random quantities outcomes c a U For example the course you choose to take can influence the grade you are likely to get Tommi Jaakkola MIT AI Lab 8 Influence diagrams cont d We may expect to know the values of some variables at the decision time our decisions become responsive strategies functions of known quantities i x a U arrows into the decision node s denote the information available at the decision time a argmax E i x P i p x i U i a x a where a is a strategy providing an action a x for each x Tommi Jaakkola MIT AI Lab 9 Influence diagrams cont d i x The resulting strategy will again yield the minimum probability of error provided that U i a 1 U when i a and zero otherwise XZ a argmax P i p x i U i a x dx a argmax a i XZ a p x P i x U i a x dx i Z argmax p x P a x x dx a where the maximum argmaxa P a x Tommi Jaakkola MIT AI Lab is attained when a x 10 Influence diagrams cont d A bit more complex example controlled Markov chain s 0 a 0 s 1 s2 a 1 a 2 U U s0 a0 s1 a1 n X r st at t 0 Tommi Jaakkola MIT AI Lab 11 Topics Exact inference in graphical models basics of probabilistic inference chains and clustering belief propagation and messages Tommi Jaakkola MIT AI Lab 12 Nature of probabilistic inference Example a hidden Markov model P s0 x0 sn xn P0 s0 Po x0 s0 P1 s1 s0 s x Given the observation sequence x 0 x n all the information about the associated hidden states is already contained in the joint probability distribution P s0 x 0 sn x n What s left to do Tommi Jaakkola MIT AI Lab 13 Nature of probabilistic inference We have to explicate the relevant information this involves propagating information across the graph model Forward backward algorithm s x Forward step information from the past about the current state Backward step information from future observations about the current state We want analogous computations for more general graph models Tommi Jaakkola MIT AI Lab 14 Equivalence of graphs We want the inference algorithm to exploit the graph structure independencies implied by the graph structure Many distinct graphs are equivalent in terms of conditional independencies and therefore can be treated the same in the inference algorithm Example Tommi Jaakkola MIT AI Lab 15 Probabilistic inference example It is always possible to cluster the variables nodes into larger sets and deal with it as before just on the level of the sets of variables Examples S0 S1 chain 1 chain 2 x x A chain is not a very efficient structure in this sense Tommi Jaakkola MIT AI Lab 16 Probabilistic inference We can generalize forward backward to operate on a tree structure rather than a chain x x tree as a chain Tommi Jaakkola MIT AI Lab tree propagation 17 Belief propagation Let s first adopt a common notation for the underlying probability model and the observed data xi xj ij xi xj P xj xi i xi P xi j xj 1 xk k xk xk x k These potential functions are chosen to ensure that Y Y P x1 xn data i xi ij xi xj i i j edges Tommi Jaakkola MIT AI Lab 18 Belief propagation cont d We can now define how each node in the graph should communicate with upstream and downstream nodes neighbors xi xj A message passing scheme 1 Initialize messages to 1 2 Message information that j sends to i is X Y mj i xi ij xi xj j xj ml j xj xj Tommi Jaakkola MIT AI Lab xk l6 i 19