Unformatted text preview:

Exact Inference I February 12, 1999 1Exact Inference IMark PeotIn this lecture we will look at issues associated with exact inference.1.0 QueriesThe objective of probabilistic inference is to compute a joint distribution of a set of query variables given values for a set of conditioning or evidence variables. These joint distribu-tions are generally computed by summing out the variables for nuisance variables; vari-ables that are neither evidence nor query variables. Say that the set of all variables in a JPD is . (EQ 1) is a normalization constant that is only a function of , . is the set of nuisance variables, . will be understood to be a general summation operator that sums over both discrete and continuous variables.An important subproblem for inference is to compute the expectation or of a function (called a statistic) on the set of query variables. Some of the more important of these statistics include:Probability that : If is discrete: The Kronecker delta1 or indicator function is . If is continuous: The Dirac delta function is and has the property that .1. Actually, the notation is usually used for a Kronecker delta function.XPQE{}PQE,{}PE{}---------------------KePX{}N∑==KeEKePX{}XE\∑= NNXQE∪()\= ΣEgQ()E{}gQ()E〈|〉qk=qδqkδ qk,()1 if qk=()0 otherwise = Pq k={} δqk,()PqE{}q∑=q δ x()1σ 2π--------------ex22σ2---------–σ 0→lim=δ qk–()fqE()qd∫fq k=()=Exact Inference I February 12, 1999 2Mean of the posterior: . .Moments of the posterior: . , the th moment of .1Covariance of the posterior: . .Generating Functions: . .Some algorithms (for example, simulation algorithms) compute conditional expectations of functions without computing . We will define a query to be a tuple consisting of a set of query variables, a set of evidence variables and, optionally, a function on the query variables.One key point about this presentation: if there is a choice, I will show the Markov Net-work version of the algorithm. A Markov Net algorithm can always be used to solve the Markov Net associated with every belief network. Let be a belief network. The Markov Net associated with this belief network is .2.0 Vertex EliminationThe first algorithm that we will discuss is the vertex elimination algorithm [Zhang+Poole, 94]. The vertex elimination algorithm is similar in spirit to the D’Ambrosio’s Symbolic Probabilistic Inference algorithm and Dechter’s bucket elimination algorithm. The input to the algorithm consists of a query and a Markov net = . The algorithm computes by incrementally removing (via mar-ginalization) the variables in .Instantiating VariablesUsually we are given specific values for the evidence variables. If a variable is observed, we can simplify the corresponding distribution function or matrix to be a func-tion of all of the variables other than . So, we can replace each of the potentials of the 1. Alternative notation for expectationgq() q= qE〈|〉 qP q E{}q∑=gq() qk= qkE〈|〉 qkPqE{}q∑= kqgq1q2,()q1q2q1E〈|〉q2E〈|〉–=cov q1q2, E() q1q2Pq1q2, E{}q1q2,∑q1E〈|〉q2E〈|〉–=gq() eqt= MtE() eqtE〈|〉=PQE{}BGP,()=MGmP,()=QE,() BGXL,()= P,()PQE{}XQE∪()\eeExact Inference I February 12, 1999 3form with a corresponding distribution . We will call this operation instantiation with row reduction.1 Alternatively, we can add a vector to the Markov net to represent the like-lihood of the evidence: . If , that is, consists of all zeros except for the ith element , we say that has been instantiated to its ith state.The algorithm:Let be the set of distributions in .Instantiate the distributions in that have evidence. Let if instantiation with row reduction is used.Let if instantiation without row reduction is used.Let be a numbering on .for from 1 to , do Remove the distributions in that contain . Call this set . Let . Add to . The answer is derived by multiplying all of the potentials left in .A variant of the algorithm can determine the maximum probability instantiation for all of the variables in : Let be the set of distributions in .Instantiate the distributions in that have evidence. Let if row reduction if no row reduction.Let be a numbering on .1. Note that this actually implies a topology change in the belief network: Observing a node decouples that node from its children.φ x1… e … xn,,,,()φex1… xn,,()φ x1… eve=()…xn,, ,,()=eexyzx|ey|ez|eλ e() λ e() δ eve,() 00… 1 … 0,, ,, ,[]== λveeΦφ1φ2…φn,,,{}=MΦNXQE∪()\=NXQ\=α NiNΦαi() Φ’φnewX() φiX()φiΦ’∈∏α i()∑=φnewΦΦXE\Φφ1φ2…φn,,,{}=MΦNXE\= NX=α NExact Inference I February 12, 1999 4for from 1 to , do 1. Remove the distributions in that contain . Call this set . 2. Let . 3. Add to . The maximum probability instantiation for the variables in given is given by the values for that maximize the in line (2) above.3.0 The Polytree Algorithm and Cutset ConditioningThe principal disadvantage of the vertex elimination algorithm is that it has to start from scratch to compute each query. Other algorithms, such as the polytree and join tree algo-rithms attempt to compute marginals for multiple variables simultaneously. Read: Mark Peot and Ross Shachter, Fusion and propagation with multiple observations in belief networks. (Course Reader) 3.1 Input to the AlgorithmThe input to the polytree algorithm is a Bayes net and evidence . The output is a set of marginals . 3.2 Recursive ConditioningNote that we do not need to condition each node on every possible instantiation for the cutset variables. Each cutset variable is only relevant to the nodes on the loop that it cuts. This issue is explored in more detail by Javier Diez-Vegas (Recursive Conditioning) and Adnan Darwiche (Dynamic Conditioning).4.0 The Junction Tree AlgorithmThe junction tree algorithm (aka Hugin aka Jensen Algorithm aka Cluster Tree Algorithm) computes the joint distribution for each maximal clique in a decomposable graph.1 1. For those of you that care, the theory for junction trees is developed from a more general concept of clus-ter trees. I don’t think cluster trees are very important so I am moving directly to junction trees. iNΦαi() Φ’φnewX() φiX()φiΦ’∈∏α i()max=φnewΦXE\ Eα i() φiX()φiΦ’∈∏BGXL,()= P,()=Ee= PX1e{}…PXne{},,{}Exact Inference I February 12, 1999


View Full Document

Duke STA 294 - Exact Inference I

Documents in this Course
Load more
Download Exact Inference I
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Exact Inference I and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Exact Inference I 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?