COMP9418: Advanced Topics in Statistical Machine Learning
MAP Inference
Instructor: University of Wales
Copyright By PowCoder代写 加微信 powcoder
Introduction
§ In this lecture, we study algorithm to compute queries of the form § MAP: maximum a posteriori hypothesis
§ MPE: maximum a posteriori explanation
§ In these queries, we are interested in finding the most probable
instantiations of a subset of variables
§ We discuss variations of the Variable Elimination algorithm to compute MAP and MPE queries
Introduction: Example
§ Consider a Bayesian network on the right
§ It concerns a population of 55% males and 45% females
𝑆 𝐶 Θ(|’ 𝐶 𝑇! Θ%!|’ 𝑆 Θ( 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .05 𝑦𝑒𝑠 𝑣𝑒 .80 𝑚𝑎𝑙𝑒 .55
𝑚𝑎𝑙𝑒 𝑛𝑜 .95 𝑦𝑒𝑠 𝑣𝑒 .20 𝑓𝑒𝑚𝑎𝑙𝑒 .45 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .01 𝑛𝑜 𝑣𝑒 .20
𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 .99 𝑛𝑜 𝑣𝑒 .80
§ They can suffer of a medical condition𝐶thatismorelikelyin 𝑆 𝐶 𝑇 Θ males ” %”|’,(
§ There are two diagnosis tests for 𝐶, 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .80 𝑇!and𝑇” 𝑚𝑎𝑙𝑒𝑦𝑒𝑠𝑣𝑒.20
! ” #|%!,%”
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1 𝑣𝑒𝑣𝑒𝑛𝑜 0
§ 𝑇” is more effective on females 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 .20
§ Both tests are equally effective on 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 .80
𝑣𝑒 𝑣𝑒 𝑣𝑒 𝑣𝑒 𝑣𝑒 𝑣𝑒 𝑣𝑒 𝑣𝑒 𝑣𝑒 𝑣𝑒
𝑦𝑒𝑠 0 𝑛𝑜 1 𝑦𝑒𝑠 0 𝑛𝑜 1 𝑦𝑒𝑠 1 𝑓𝑒𝑚𝑎𝑙𝑒𝑛𝑜𝑣𝑒.95 𝑣𝑒𝑣𝑒𝑛𝑜 0
males 𝑓𝑒𝑚𝑎𝑙𝑒𝑦𝑒𝑠𝑣𝑒 .95 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .05 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 .05
Introduction: Example
§ We can partition this population in four groups § Males and females, with or without the condition
§ Suppose a person takes both tests with the same results § Leads to the evidence 𝐴 = 𝑦𝑒𝑠
§ What is the most likely group this individual belongs? § This is an example of MAP instantiation
§ The most likely instantiation of 𝑆 and 𝐶 given 𝐴 = 𝑦𝑒𝑠 § In this query, 𝑆 and 𝐶 are MAP variables
§ The answer for this example is
§ 𝑆 = 𝑚𝑎𝑙𝑒 and 𝐶 = 𝑛𝑜 with posterior probability of ~49.3%
MAP and Inference
§ Variable and factor elimination algorithms can compute MAP instantiations
§ They are efficient with small number of MAP variables
§ We compute the posterior marginal over MAP variables and select the
instantiation with maximal probability
§ However, this approach is exponential in the number of MAP variables
§ Our objective in this lecture is to present algorithms for MAP instantiations
§ Not necessarily exponential in the number of MAP variables
MAP and MPE
§ MPE is a special case of MAP when MAP variables contain all unobserved network variables
§ In the previous example, it would result in 16 groups
§ Males and females, with or without the condition and the four possible outcomes for the two tests
§ This is the MAP instantiation for 𝑆, 𝐶, 𝑇! and 𝑇”
§Theansweris𝑆 = 𝑓𝑒𝑚𝑎𝑙𝑒,𝐶 =𝑛𝑜, 𝑇! = 𝑣𝑒, 𝑇” = 𝑣𝑒
§ With posterior probability ~47%
§ This case of MAP is known as MPE instantiation
§ MPE instantiations are much easier to compute than MAP
§ That is why they have their own name
§ MPE is not the answer for MAP
§ MPE projection on variables 𝑆 and 𝐶 is
𝑆 = 𝑓𝑒𝑚𝑎𝑙𝑒,𝐶 =𝑛𝑜
§ But the MAP answer of previous slides is
𝑆 = 𝑚𝑎𝑙𝑒and𝐶 = 𝑛𝑜
§ Although this technique is sometimes used as an approximation for MAP
Computing MPE
§ Given a network §TheMPEprobabilityforthevariables𝑸ofanetworkgivenevidence𝒆is
defined as
§ There may be several instantiations 𝒒 with maximal probability § Each of them is an MPE instantiation
§ The set of such instantiations is defined as
§ MPE instantiations can be characterized as instantiations 𝒒 that
maximizetheposteriordistribution
§Since𝑃𝒒𝒆 =)𝒒,𝒆 )𝒆
§ 𝑃(𝒆) is independent of the instantiation 𝒒
𝑀𝑃𝐸! 𝒆 ≝max𝑃(𝒒,𝒆) 𝒒
𝑀𝑃𝐸𝒆 ≝𝑎𝑟𝑔𝑚𝑎𝑥𝑃(𝒒,𝒆) 𝒒
𝑀𝑃𝐸𝒆 ≝𝑎𝑟𝑔𝑚𝑎𝑥𝑃(𝒒|𝒆) 𝒒
Computing MPE by Variable Elimination
§ Returning to our example
𝑆 𝐶 Θ(|’ 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .05
𝑚𝑎𝑙𝑒 𝑛𝑜 .95 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .01 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 .99
𝐶 𝑇! Θ%!|’ 𝑆 Θ( 𝑦𝑒𝑠 𝑣𝑒 .80 𝑚𝑎𝑙𝑒 .55
𝑦𝑒𝑠 𝑣𝑒 .20 𝑓𝑒𝑚𝑎𝑙𝑒 .45 𝑛𝑜 𝑣𝑒 .20
𝑆 𝐶 𝑇” Θ%”|’,( 𝑇! 𝑇” 𝐴 Θ#|%!,%”
𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .80 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠𝑣𝑒 .20 𝑚𝑎𝑙𝑒 𝑛𝑜𝑣𝑒 .20 𝑚𝑎𝑙𝑒𝑛𝑜𝑣𝑒.80
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1 𝑣𝑒 𝑣𝑒 𝑛𝑜 0 𝑣𝑒 𝑣𝑒𝑦𝑒𝑠 0
𝑓𝑒𝑚𝑎𝑙𝑒𝑦𝑒𝑠𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒𝑛𝑜𝑣𝑒.95
.95 .05 .05
1 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0 𝑣𝑒 𝑣𝑒 𝑛𝑜 1 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1 𝑣𝑒𝑣𝑒𝑛𝑜 0
Computing MPE by Variable Elimination
§ Returning to our example
§ We can compute the joint probability for this Bayesian network
§ (Even rows omitted since they have zero probabilities)
§ The MPE instantiation (assuming no evidence) is given in row 31
§ MPE probability (𝑀𝑃𝐸)) is .338580
𝑆 𝐶 𝑇! 1 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 3 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 5 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 7 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 9 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 11 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 13 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 15 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 17 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 19 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 21 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 23 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 25 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 27 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 29 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 31 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒
𝑣𝑒 𝑦𝑒𝑠 .017600 𝑣𝑒 𝑛𝑜 .004400 𝑣𝑒 𝑛𝑜 .004400 𝑣𝑒 𝑦𝑒𝑠 .001100 𝑣𝑒 𝑦𝑒𝑠 .020900 𝑣𝑒 𝑛𝑜 .083600 𝑣𝑒 𝑛𝑜 .083600 𝑣𝑒 𝑦𝑒𝑠 .334400 𝑣𝑒 𝑦𝑒𝑠 .003420 𝑣𝑒 𝑛𝑜 .000180 𝑣𝑒 𝑛𝑜 .000855 𝑣𝑒 𝑦𝑒𝑠 .000045 𝑣𝑒 𝑦𝑒𝑠 .004455 𝑣𝑒 𝑛𝑜 .084645 𝑣𝑒 𝑛𝑜 .017820 𝑣𝑒 𝑦𝑒𝑠 .338580
Computing MPE by Variable Elimination
§ We can compute 𝑀𝑃𝐸5 using Variable Elimination
§ However, when eliminating a variable, we maximize out instead of summing it out
§ To maximize out a variable 𝐵 from a factor 𝜙 𝐴, 𝐵, 𝐶 , we produce another factor over remaining variables 𝐴 and 𝐶
§ By merging all rows that agree on the values of these remaining variables
§ As we merge rows, we drop reference to the maximized variable and assign to the resulting row the
maximum probability associated with the merged rows
𝐴 𝐵 𝐶 𝜙𝐴,𝐵,𝐶 000 7
0 1 0 .2 011 2 100 3
1 0 1 .5 1 1 0 1.2 111 3
𝐴 𝐶 max𝜙𝐴,𝐶
00#7 0 1 4.5 103 113
Computing MPE by Variable Elimination
§ The result of maximizing out variable 𝐵 from factor 𝜙 is § Another factor, max 𝜙 that does not mention 𝐵
§ The new factor agrees with the old factor on the MPE probability
§ We can continue to maximize out max 𝜙 until we get the trivial factor
§ The probability assigned to this factor is the MPE probability
§ This method can be extended to provide the MPE instantiation (more later)
§ Maximization is commutative
§ Allow us to refer to maximizing out a set of variables without specifying the order
§ Also, max 𝜙!𝜙” = 𝜙! max 𝜙” if variable 𝑋 appears only in 𝜙” —
MPE VE: Algorithm
𝑸 ← variables in the network
𝜋 ← elimination order of variables 𝑸 𝑺 ← {𝜙𝒆: 𝜙 is a factor of the network} for𝑖 =1to|𝑸|do
𝜎% ← ∏& 𝜙&, where 𝜙& belongs to 𝑺 and mentions variable 𝜋(𝑖) 𝜏% ←max𝜎%
replace all factors 𝜙& in 𝑺 by factor 𝜏%
return trivial factor ∏*∈, 𝜏
• All factors are eliminated leading to a trivial factor
• 𝜙𝒆 is a factor with the rows of factor 𝜙 that match the evidence 𝒆
• Pruning should eliminate edges only since all variables are relevant to the
• This algorithm has the same complexity as VE, i.e., the time and space
complexity are 𝑂(𝑛 exp(𝑤)) for 𝑛 variables and an elimination width 𝑤
Computing MPE: Example
§ Returning to our example § Let us run MPE VE on this
§ With the elimination order 𝜋 = 𝑆,𝐶,𝐴,𝑇!,𝑇”
𝑆 𝐶 Θ(|’ 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .05
𝑚𝑎𝑙𝑒 𝑛𝑜 .95 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .01 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 .99
𝐶 𝑇! Θ%!|’ 𝑆 Θ( 𝑦𝑒𝑠 𝑣𝑒 .80 𝑚𝑎𝑙𝑒 .55
𝑦𝑒𝑠 𝑣𝑒 .20 𝑓𝑒𝑚𝑎𝑙𝑒 .45 𝑛𝑜 𝑣𝑒 .20
𝑆 𝐶 𝑇” Θ%”|’,( 𝑇! 𝑇” 𝐴 Θ#|%!,%”
𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .80 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠𝑣𝑒 .20 𝑚𝑎𝑙𝑒 𝑛𝑜𝑣𝑒 .20 𝑚𝑎𝑙𝑒𝑛𝑜𝑣𝑒.80
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1 𝑣𝑒 𝑣𝑒 𝑛𝑜 0 𝑣𝑒 𝑣𝑒𝑦𝑒𝑠 0
𝑓𝑒𝑚𝑎𝑙𝑒𝑦𝑒𝑠𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒𝑛𝑜𝑣𝑒.95
.95 .05 .05
1 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0 𝑣𝑒 𝑣𝑒 𝑛𝑜 1 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1 𝑣𝑒𝑣𝑒𝑛𝑜 0
Computing MPE: Example
§ Returning to our example § Let us run MPE VE on this
§ With the elimination order 𝜋 = 𝑆,𝐶,𝐴,𝑇!,𝑇”
𝑆 𝐶 𝜙!(𝑆,𝐶) 𝐶 𝑇! 𝜙”(𝑇!,𝐶) 𝑆 𝜙.(𝑆) 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .05 𝑦𝑒𝑠 𝑣𝑒 .80 𝑚𝑎𝑙𝑒 .55
𝑚𝑎𝑙𝑒 𝑛𝑜 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜
.95 .01 .99
𝑦𝑒𝑠 𝑣𝑒 .20 𝑛𝑜 𝑣𝑒 .20 𝑛𝑜 𝑣𝑒 .80
𝐶 𝑇” 𝜙/(𝑇”,𝐶,𝑆)
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1
𝜙0(𝑇!,𝑇”,𝐴)
𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒
𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒
.80 .20 .20 .80 .95 .05 .05 .95
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0 𝑣𝑒𝑣𝑒𝑛𝑜 1 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0 𝑣𝑒𝑣𝑒𝑛𝑜 1 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1 𝑣𝑒𝑣𝑒𝑛𝑜 0
𝑦𝑒𝑠 𝑣𝑒 𝑦𝑒𝑠 𝑣𝑒
Computing MPE: Example 𝑆
§ Returning to our example §Let us run MPE VE on this
§ With the elimination order
𝜋 = 𝑆,𝐶,𝐴,𝑇!,𝑇”
𝑆 𝐶 𝑇” 𝜙/(𝑇”,𝐶,𝑆)
𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .80
𝑆 𝐶 𝜙!(𝑆,𝐶) 𝐶 𝑇! 𝜙”(𝑇!,𝐶)
𝑚𝑎𝑙𝑒 𝑛𝑜 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜
.05 𝑦𝑒𝑠 𝑣𝑒 .95 𝑦𝑒𝑠 𝑣𝑒 .01 𝑛𝑜 𝑣𝑒 .99 𝑛𝑜 𝑣𝑒
.80 .20 .20 .80
𝜎!(𝑇”,S,C) .440 .110 .110 .440
𝑇! 𝑇” 𝐴 𝜙0(𝑇!,𝑇”,𝐴) 𝑣𝑒 𝑣𝑒𝑦𝑒𝑠 1
𝑣𝑒 𝑣𝑒 𝑛𝑜 0
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0 𝑣𝑒𝑣𝑒𝑛𝑜 1
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0 𝑣𝑒𝑣𝑒𝑛𝑜 1
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1 𝑣𝑒𝑣𝑒𝑛𝑜 0 15
𝑆 𝜙(𝑆) 𝑚𝑎𝑙𝑒𝑦𝑒𝑠𝑣𝑒 .20
𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒
𝑚𝑎𝑙𝑒 .55 × 𝑓𝑒𝑚𝑎𝑙𝑒 .45
𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 .80 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .95 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .05 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 .05 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 .95
𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .428 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .023
. 𝑚𝑎𝑙𝑒𝑛𝑜𝑣𝑒 .20
𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒
Computing MPE: Example 𝑆
§ Returning to our example §Let us run MPE VE on this
§ And use the elimination
𝐶 𝑇! 𝜙”(𝑇!,𝐶) 𝑦𝑒𝑠 𝑣𝑒 .80 𝑦𝑒𝑠 𝑣𝑒 .20
𝑛𝑜 𝑣𝑒 .20 𝑛𝑜 𝑣𝑒 .80
order 𝜋 = 𝑆,𝐶,𝐴,𝑇!,𝑇”
𝑆 𝐶 𝑇” 𝜎!(𝑇”,S,C) 𝑆 𝐶 𝑇” 𝜎”(𝑇”,S,C) 𝑇! 𝑇” 𝐴 𝜙0(𝑇!,𝑇”,𝐴)
𝐶 𝜙!(𝑆,𝐶) 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .05 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒
.440 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .110 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .110 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 .440 ≈𝑚𝑎𝑙𝑒𝑛𝑜𝑣𝑒 .428 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .023 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .023 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 .428 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒
.0220 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1 .0055 𝑣𝑒𝑣𝑒𝑛𝑜 0 .1045 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0 .4180 𝑣𝑒𝑣𝑒𝑛𝑜 1 .0043 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0 .0002 𝑣𝑒𝑣𝑒𝑛𝑜 1 .0228 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1 .4237 𝑣𝑒𝑣𝑒𝑛𝑜 0
𝑚𝑎𝑙𝑒𝑛𝑜.95×𝑚𝑎𝑙𝑒𝑛𝑜𝑣𝑒
𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .01 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 .99
𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒
Computing MPE: Example
§ Returning to our example §Let us run MPE VE on this
§ And use the elimination
order 𝜋 = 𝑆,𝐶,𝐴,𝑇!,𝑇” 𝑆 𝐶 𝑇” 𝜎”(𝑇”,S,C)
𝐶 𝑇! 𝜙”(𝑇!,𝐶) 𝑦𝑒𝑠 𝑣𝑒 .80 𝑦𝑒𝑠 𝑣𝑒 .20
𝑛𝑜 𝑣𝑒 .20 𝑛𝑜 𝑣𝑒 .80
𝑇! 𝑇” 𝐴 𝜙0(𝑇!,𝑇”,𝐴) 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1
𝑣𝑒 𝑣𝑒 𝑛𝑜 0
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0
𝑣𝑒 𝑣𝑒 𝑛𝑜 1 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0 𝑣𝑒 𝑣𝑒 𝑛𝑜 1 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1 𝑣𝑒 𝑣𝑒 𝑛𝑜 0
𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒
𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒
𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒
𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒
.0220 .0055 .1045 .4180 .0043 .0002 .0228 .4237
𝐶 𝑇 𝜏(𝑇,𝐶) “””
𝑦𝑒𝑠 𝑣𝑒 .0220 𝑦𝑒𝑠 𝑣𝑒 .0055 𝑛𝑜 𝑣𝑒 .1045
Computing MPE: Example
§ Returning to our example §Let us run MPE VE on this
§ And use the elimination order 𝜋 = 𝑆,𝐶,𝐴,𝑇!,𝑇”
𝐶 𝑇” 𝜏”(𝑇”,𝐶) 𝐶 𝑇! 𝜙”(𝑇!,𝐶) 𝑦𝑒𝑠 𝑣𝑒 .0220 𝑦𝑒𝑠 𝑣𝑒 .80 𝑦𝑒𝑠 𝑣𝑒 .0055 𝑦𝑒𝑠 𝑣𝑒 .20
𝑛𝑜 𝑣𝑒 .1045 𝑛𝑜 𝑣𝑒 .20
𝑛𝑜 𝑣𝑒 .4237
𝑇! 𝑇” 𝑣𝑒 𝑣𝑒
𝐴 𝜙0(𝑇!,𝑇”,𝐴) 𝑦𝑒𝑠 1
𝑣𝑒 𝑣𝑒 𝑛𝑜 0
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0
𝑣𝑒 𝑣𝑒 𝑛𝑜 1
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0
𝑣𝑒 𝑣𝑒 𝑛𝑜 1
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1
𝑣𝑒 𝑣𝑒 𝑛𝑜 0
Computing MPE: Example
§ Returning to our example § Let us run MPE VE on this
§ And use the elimination
order 𝜋 = 𝑆,𝐶,𝐴,𝑇!,𝑇”
𝑇! 𝑇” 𝐴 𝜙0(𝑇!,𝑇”,𝐴) 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1
𝑣𝑒 𝑣𝑒 𝑛𝑜 0
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0
𝑣𝑒 𝑣𝑒 𝑛𝑜 1 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0 𝑣𝑒 𝑣𝑒 𝑛𝑜 1 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1 𝑣𝑒 𝑣𝑒 𝑛𝑜 0
𝑇! 𝜎.(𝐶,𝑇!,𝑇”)
𝐶 𝑇” 𝜏”(𝑇”,𝐶) 𝐶 𝑇! 𝜙”(𝑇!,𝐶) 𝑦𝑒𝑠 𝑣𝑒 .0220 𝑦𝑒𝑠 𝑣𝑒 .80 𝑦𝑒𝑠𝑣𝑒 .0055×𝑦𝑒𝑠𝑣𝑒 .20≈
𝑛𝑜 𝑣𝑒 .1045 𝑛𝑜 𝑣𝑒 .20
.0176 .0044 .0044 .0011 .0209 .0836 .0847 .3390
.4237 𝑛𝑜 𝑣𝑒 .80
Computing MPE: Example
§ Returning to our example § Let us run MPE VE on this
§ And use the elimination
order 𝜋 = 𝑆,𝐶,𝐴,𝑇!,𝑇”
𝐶𝑇 𝑇 𝜎(𝐶,𝑇,𝑇) “!.!”
𝑇! 𝑇” 𝑣𝑒 𝑣𝑒
𝐴 𝜙0(𝑇!,𝑇”,𝐴)
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 𝑣𝑒𝑣𝑒𝑛𝑜
𝑦𝑒𝑠 𝑛𝑜 𝑦𝑒𝑠 𝑛𝑜 𝑦𝑒𝑠 𝑛𝑜
1 0 0 1 0 1 1 0
.0044 𝑇” 𝑇!
𝜏.(𝑇”, 𝑇!) 𝑣𝑒 𝑣𝑒 .0209 𝑣𝑒 𝑣𝑒 .0836 .0209 𝑣𝑒 𝑣𝑒 .0847 .0836 𝑣𝑒 𝑣𝑒 .3390
.0044 .0011
.0847 .3390
Computing MPE: Example
§ Returning to our example § Let us run MPE VE on this
§ And use the elimination order 𝜋 = 𝑆,𝐶,𝐴,𝑇!,𝑇”
𝑣𝑒 𝑣𝑒 𝑣𝑒 𝑣𝑒
𝑇! 𝑇” 𝑣𝑒 𝑣𝑒
𝑇! 𝜏.(𝑇”, 𝑇!) 𝑣𝑒 .0209 𝑣𝑒 .0836 𝑣𝑒 .0847 𝑣𝑒 .3390
𝐴 𝜙0(𝑇!,𝑇”,𝐴) 𝑦𝑒𝑠 1
𝑣𝑒 𝑣𝑒 𝑛𝑜 0
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0
𝑣𝑒 𝑣𝑒 𝑛𝑜 1
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0
𝑣𝑒 𝑣𝑒 𝑛𝑜 1
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1
𝑣𝑒 𝑣𝑒 𝑛𝑜 0
Computing MPE: Example
§ Returning to our example
𝑇” 𝑇! 𝜏.(𝑇”, 𝑇!)
𝑣𝑒 𝑣𝑒 .0209
𝑣𝑒 𝑣𝑒 .0836
𝑣𝑒 𝑣𝑒 .0847
𝑣𝑒 𝑣𝑒 .3390
𝑇! 𝑇” 𝑣𝑒 𝑣𝑒
Let us run MPE VE on this example
And use the elimination order 𝜋 = 𝑆,𝐶,𝐴,𝑇!,𝑇”
𝐴 𝜙0(𝑇!,𝑇”,𝐴) 𝑦𝑒𝑠 1
𝑣𝑒 𝑣𝑒 𝑛𝑜 0
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0
𝑣𝑒 𝑣𝑒 𝑛𝑜 1
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0
𝑣𝑒 𝑣𝑒 𝑛𝑜 1
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1
𝜏/(𝑇!,𝑇”) 𝑣𝑒𝑣𝑒 1
𝑣𝑒𝑣𝑒 1 𝑣𝑒𝑣𝑒 1 𝑣𝑒𝑣𝑒 1
Computing MPE: Example
§ Returning to our example § Let us run MPE VE on this
§ And use the elimination order 𝜋 = 𝑆,𝐶,𝐴,𝑇!,𝑇”
𝜏/(𝑇!, 𝑇”) 𝑇” 𝑇! 1 𝑣𝑒 𝑣𝑒 1 𝑣𝑒 𝑣𝑒 1 𝑣𝑒 𝑣𝑒 1 𝑣𝑒 𝑣𝑒
𝜏.(𝑇”, 𝑇!) .0209 .0836 .0847 .3390
Computing MPE: Example
§ Returning to our example § Let us run MPE VE on this
§ And use the elimination order 𝜋 = 𝑆,𝐶,𝐴,𝑇!,𝑇”
𝜏/(𝑇!, 𝑇”) 𝑇” 1 𝑣𝑒 1×𝑣𝑒 1𝑣𝑒 1𝑣𝑒
𝑇! 𝜏.(𝑇”, 𝑇!) 𝑇! 𝑇” 𝑣𝑒 .0209 𝑣𝑒 𝑣𝑒 𝑣𝑒 .0836 = 𝑣𝑒 𝑣𝑒 𝑣𝑒 .0847 𝑣𝑒 𝑣𝑒 𝑣𝑒 .3390 𝑣𝑒 𝑣𝑒
𝜎0(𝑇!, 𝑇”) .0209 .0847 .0836 .3390
Computing MPE: Example
§ Returning to our example § Let us run MPE VE on this
§ And use the elimination
order 𝜋 = 𝑆,𝐶,𝐴,𝑇!,𝑇”
𝜎0(𝑇!, 𝑇”) .0209 .0847 .0836 .3390
𝑇” 𝜏0(𝑇”) 𝑣𝑒 .0836 𝑣𝑒 .3390
Computing MPE: Example
§ Returning to our example § Let us run MPE VE on this
§ And use the elimination
order 𝜋 = 𝑆,𝐶,𝐴,𝑇!,𝑇”
𝑇” 𝜏0(𝑇”) 𝑣𝑒 .0836 𝑣𝑒 .3390
Computing MPE: Example
§ Returning to our example § Let us run MPE VE on this
§ And use the elimination
order 𝜋 = 𝑆, 𝐶, 𝐴, 𝑇!, 𝑇” § 𝑀𝑃𝐸U ≈ 0.3390
§ We can also be interested in the MPE instantiation
§ However, we lost this piece of information during the elimination
Recovering MPE Instantiation
§ We can modify the previous algorithm to compute the MPE instantiation
§ In addition to the MPE probability
§ The idea is to use extended factors
§ It assigns to each instantiation a number and an instantiation
§ We use 𝜙[𝑥] to denote the instantiation
§ While continuing to use 𝜙(𝑥) for denoting the number
§ The instantiation 𝜙[𝑥] is used to record the MPE instantiation as it is being constructed
𝑆 𝐶 𝑇” 𝜙(.)
𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒
.0220 .0055 .1045 .4180 .0043 .0002 .0228 .4237
𝐶 𝑇” 𝜙(.) 𝜙[.]
𝑦𝑒𝑠 𝑣𝑒 .0220 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .0055 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 .1045 𝑚𝑎𝑙𝑒
𝑛𝑜 𝑣𝑒 .4237 𝑓𝑒𝑚𝑎𝑙𝑒
𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑚𝑎𝑙𝑒 𝑛𝑜
𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜
Computing MPE Instantiation: Example
§ Returning to our example § Let us run MPE VE on this
example, but now computing the MPE instantiation with evidence 𝐴 = 𝑦𝑒𝑠
𝑆 𝐶 Θ’|( 𝐶 𝑇! 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .05 𝑦𝑒𝑠 𝑣𝑒 𝑚𝑎𝑙𝑒 𝑛𝑜 .95 𝑦𝑒𝑠 𝑣𝑒
𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .01 𝑛𝑜 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 .99 𝑛𝑜 𝑣𝑒
Θ%!|’ 𝑆 Θ( .80 𝑚𝑎𝑙𝑒 .55
.20 𝑓𝑒𝑚𝑎𝑙𝑒 .45 .20
𝑆 𝐶 𝑇” Θ%”|’,( 𝑇! 𝑇” 𝐴 Θ#|%!,%”
𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .80 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠𝑣𝑒 .20 𝑚𝑎𝑙𝑒 𝑛𝑜𝑣𝑒 .20 𝑚𝑎𝑙𝑒𝑛𝑜𝑣𝑒.80
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1 𝑣𝑒 𝑣𝑒 𝑛𝑜 0 𝑣𝑒 𝑣𝑒𝑦𝑒𝑠 0
𝑓𝑒𝑚𝑎𝑙𝑒𝑦𝑒𝑠𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒𝑛𝑜𝑣𝑒.95
.95 .05 .05
1 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0 𝑣𝑒 𝑣𝑒 𝑛𝑜 1 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1 𝑣𝑒𝑣𝑒𝑛𝑜 0
Computing MPE Instantiation: Example
§ Returning to our example § Let us run MPE VE on this
example, but now computing the MPE instantiation with evidence 𝐴 = 𝑦𝑒𝑠
𝑆 𝐶 𝜙!(𝑆,𝐶) 𝐶 𝑇! 𝜙”(𝑇!,𝐶) 𝑆 𝜙.(𝑆) 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .05 𝑦𝑒𝑠 𝑣𝑒 .80 𝑚𝑎𝑙𝑒 .55
𝑚𝑎𝑙𝑒 𝑛𝑜 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜
.95 .01 .99
𝑦𝑒𝑠 𝑣𝑒 .20 𝑛𝑜 𝑣𝑒 .20 𝑛𝑜 𝑣𝑒 .80
𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒
𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒
.80 .20 .20 .80 .95 .05 .05 .95
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0 𝑣𝑒𝑣𝑒𝑛𝑜 1 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0 𝑣𝑒𝑣𝑒𝑛𝑜 1 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1 𝑣𝑒𝑣𝑒𝑛𝑜 0
𝐶 𝑇” 𝜙/(𝑇”,𝐶,𝑆)
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1
𝑦𝑒𝑠 𝑣𝑒 𝑦𝑒𝑠 𝑣𝑒
𝜙0(𝑇!,𝑇”,𝐴)
Computing MPE Instantiation: Example
§ Returning to our example § Let us run MPE VE on this
example, but now computing the MPE instantiation with evidence 𝐴 = 𝑦𝑒𝑠
𝑆 𝐶 𝜙!(𝑆,𝐶) 𝐶 𝑇! 𝜙”(𝑇!,𝐶) 𝑆 𝜙.(𝑆) 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .05 𝑦𝑒𝑠 𝑣𝑒 .80 𝑚𝑎𝑙𝑒 .55
𝑚𝑎𝑙𝑒 𝑛𝑜 .95 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .01 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 .99
𝑦𝑒𝑠 𝑣𝑒 .20 𝑛𝑜 𝑣𝑒 .20 𝑛𝑜 𝑣𝑒 .80
𝑓𝑒𝑚𝑎𝑙𝑒 .45
𝑆 𝐶 𝑇”𝜙/(𝑇”,𝐶,𝑆) 𝑇! 𝑇” 𝑎 𝜙0(𝑇!,𝑇”,𝑎)
𝑚𝑎𝑙𝑒 𝑦𝑒𝑠𝑣𝑒 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒
.80 𝑣𝑒𝑣𝑒𝑦𝑒𝑠 1 .20 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0 .20 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0 .80 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1
𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .95 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .05 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 .05 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 .95
Computing MPE Instantiation: Example 𝑆
§ Returning to our example § Let us run MPE VE on this
example, but now computing the MPE instantiation with evidence 𝐴 = 𝑦𝑒𝑠
𝑆 𝐶 𝜙!(𝑆,𝐶) 𝐶 𝑇! 𝜙”(𝑇!,𝐶)
𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .05
𝑚𝑎𝑙𝑒 𝑛𝑜 .95 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .01 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 .99
𝑦𝑒𝑠 𝑣𝑒 .80 𝑦𝑒𝑠 𝑣𝑒 .20 𝑛𝑜 𝑣𝑒 .20 𝑛𝑜 𝑣𝑒 .80
𝑆 𝐶 𝑇” 𝜙/(𝑇”,𝐶,𝑆) 𝑆 𝐶 𝑇” 𝜎!(𝑇”,S,C)
𝑇! 𝑇” 𝑎 𝜙0(𝑇!,𝑇”,𝑎) 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1
𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒
𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑆 𝜙.(𝑆) 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒
𝑚𝑎𝑙𝑒 .55 × 𝑚𝑎𝑙𝑒 𝑛𝑜𝑣𝑒
.80 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .440
𝑓𝑒𝑚𝑎𝑙𝑒 .45
𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒
.20 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .20 𝑚𝑎𝑙𝑒 𝑛𝑜 .80 ≈ 𝑚𝑎𝑙𝑒 𝑛𝑜 .95 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .05 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .05 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 .95 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜
𝑣𝑒 .110 𝑣𝑒 .110 𝑣𝑒 .440 𝑣𝑒 .428 𝑣𝑒 .023 𝑣𝑒 .023 𝑣𝑒 .428
Computing MPE: Example 𝑆
§ Returning to our example § Let us run MPE VE on this
example, but now computing the MPE instantiation with evidence 𝐴 = 𝑦𝑒𝑠
𝐶 𝑇! 𝜙”(𝑇!,𝐶) 𝑦𝑒𝑠 𝑣𝑒 .80 𝑦𝑒𝑠 𝑣𝑒 .20
𝑛𝑜 𝑣𝑒 .20 𝑛𝑜 𝑣𝑒 .80
𝑆 𝐶 𝜙!(𝑆,𝐶) 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .05 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑚𝑎𝑙𝑒 𝑛𝑜 .95 × 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒
.440 𝑚𝑎𝑙𝑒 yes 𝑣𝑒
.0220 .0055 .1045 .4180 .0043 .0002 .0228 .4237
𝑇! 𝑇” 𝑎 𝜙0(𝑇!,𝑇”,𝑎) 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1
𝑆 𝐶 𝑇” 𝜎!(𝑇”,S,C) 𝑆 𝐶 𝑇” 𝜎”(𝑇”,S,C)
𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 .01 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒
𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 .99
.110 .110 .440 .428 .023 .023 .428
𝑚𝑎𝑙𝑒 yes 𝑣𝑒
𝑚𝑎𝑙𝑒 no 𝑣𝑒 ≈ 𝑚𝑎𝑙𝑒 no 𝑣𝑒
𝑓𝑒𝑚𝑎𝑙𝑒 yes 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 yes 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 no 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 no 𝑣𝑒
𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒
Computing MPE: Example
§ Returning to our example § Let us run MPE VE on this
example, but now computing the MPE instantiation with evidence 𝐴 = 𝑦𝑒𝑠
𝑆 𝐶 𝑇” 𝜎”(𝑇”,S,C)
𝑇! 𝑇” 𝑣𝑒 𝑣𝑒
𝑣𝑒 𝑣𝑒 𝑣𝑒 𝑣𝑒 𝑣𝑒 𝑣𝑒
𝑎 𝑦𝑒𝑠 𝑦𝑒𝑠 𝑦𝑒𝑠 𝑦𝑒𝑠
𝜙0(𝑇!, 𝑇”, 𝑎) 1
𝐶 𝑇! 𝑦𝑒𝑠 𝑣𝑒 𝑦𝑒𝑠 𝑣𝑒
𝑛𝑜 𝑣𝑒 𝑛𝑜 𝑣𝑒
𝜙”(𝑇!, 𝐶) .80 .20 .20 .80
𝑚𝑎𝑙𝑒 𝑚𝑎𝑙𝑒 𝑚𝑎𝑙𝑒 𝑚𝑎𝑙𝑒
yes 𝑣𝑒 yes 𝑣𝑒
.0220 .0055 .1045 .4180 .0043 .0002 .0228 .4237
.4237 𝑓𝑒𝑚𝑎𝑙𝑒
no 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 yes 𝑣𝑒
𝑦𝑒𝑠 𝑣𝑒 𝑦𝑒𝑠 𝑣𝑒
𝑛𝑜 𝑣𝑒 𝑛𝑜 𝑣𝑒
𝑚𝑎𝑙𝑒 𝑚𝑎𝑙𝑒 𝑚𝑎𝑙𝑒
𝑓𝑒𝑚𝑎𝑙𝑒 yes 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 no 𝑣𝑒 𝑓𝑒𝑚𝑎𝑙𝑒 no 𝑣𝑒
Computing MPE Instantiation: Example
§ Returning to our example
§ Let us run MPE VE on this example, but now computing the MPE instantiation with evidence 𝐴 = 𝑦𝑒𝑠
𝑇! 𝑇” 𝑎 𝜙0(𝑇!,𝑇”,𝑎) 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 0
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 1
𝐶 𝑇” 𝐶 𝑇” 𝜏”(𝑇”,𝐶) 𝐶 𝑇! 𝜙”(𝑇!,𝐶) 𝑦𝑒𝑠 𝑣𝑒
𝑦𝑒𝑠 𝑣𝑒 .0220 𝑚𝑎𝑙𝑒 𝑦𝑒𝑠 𝑣𝑒 .80 𝑦𝑒𝑠 𝑣𝑒 𝑦𝑒𝑠 𝑣𝑒 .0055 𝑚𝑎𝑙𝑒 × 𝑦𝑒𝑠 𝑣𝑒 .20 ≈ 𝑦𝑒𝑠 𝑣𝑒 𝑛𝑜 𝑣𝑒 .1045 𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 .20 𝑦𝑒𝑠 𝑣𝑒 𝑛𝑜 𝑣𝑒 .4237 𝑓𝑒𝑚𝑎𝑙𝑒 𝑛𝑜 𝑣𝑒 .80 𝑛𝑜 𝑣𝑒
𝑛𝑜 𝑣𝑒 𝑛𝑜 𝑣𝑒 𝑛𝑜 𝑣𝑒
𝑇! 𝜎.(C,𝑇!,𝑇”)
𝑣𝑒 .0176 𝑚𝑎𝑙𝑒 𝑣𝑒 .0044 𝑚𝑎𝑙𝑒 𝑣𝑒 .0044 𝑚𝑎𝑙𝑒 𝑣𝑒 .0011 𝑚𝑎𝑙𝑒 𝑣𝑒 .0209 𝑚𝑎𝑙𝑒 𝑣𝑒 .0836 𝑚𝑎𝑙𝑒 𝑣𝑒 .0847 𝑓𝑒𝑚𝑎𝑙𝑒 𝑣𝑒 .3390 𝑓𝑒𝑚𝑎𝑙𝑒
Computing MPE Instantiation: Example
§ Returning to our example § Let us run MPE VE on this
example, but now computing the MPE instantiation with evidence 𝐴 = 𝑦𝑒𝑠
𝐶 𝑇” 𝑇! 𝜎.(C,𝑇!,𝑇”)
𝑦𝑒𝑠 𝑣𝑒 𝑣𝑒 .0176 𝑚𝑎𝑙𝑒
𝑦𝑒𝑠 𝑣𝑒 𝑣𝑒 .0044 𝑚𝑎𝑙𝑒
𝑦𝑒𝑠 𝑣𝑒 𝑣𝑒 .0044 𝑚𝑎𝑙𝑒
𝑦𝑒𝑠 𝑣𝑒 𝑣𝑒 .0011 𝑚𝑎𝑙𝑒
𝑛𝑜 𝑣𝑒 𝑣𝑒 .0209 𝑚𝑎𝑙𝑒
𝑛𝑜 𝑣𝑒 𝑣𝑒 .0836 𝑚𝑎𝑙𝑒
𝑇! 𝑇” 𝑎 𝜙0(𝑇!,𝑇”,𝑎)
𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠 𝑣𝑒 𝑣𝑒 𝑦𝑒𝑠
𝜏.(𝑇”, 𝑇!) .0209 .0836 .0847 .3390
𝑛𝑜 𝑣𝑒 𝑣𝑒 .0847
𝑛𝑜 𝑣𝑒 𝑣𝑒 .3390
𝑓𝑒𝑚𝑎𝑙𝑒 𝑓𝑒𝑚𝑎𝑙𝑒
𝑚𝑎𝑙𝑒,𝑛𝑜 𝑓𝑒𝑚𝑎𝑙𝑒, 𝑛𝑜 𝑓𝑒𝑚𝑎𝑙𝑒, 𝑛𝑜
Computing MPE Instantiation: Example
§ Returning to our example
𝜏.(𝑇”, 𝑇!) .0209 .0836 .0847 .3390
Let us run MPE VE on this example, but now computing the MPE instantiation with evidence 𝐴 = 𝑦𝑒𝑠
𝑚𝑎𝑙𝑒,𝑛𝑜 𝑓𝑒𝑚𝑎𝑙𝑒, 𝑛𝑜 𝑓𝑒𝑚𝑎𝑙𝑒, 𝑛𝑜
𝑇! 𝑇” 𝑣𝑒 𝑣𝑒
𝑣𝑒 𝑣𝑒 𝑣𝑒 𝑣𝑒 𝑣𝑒 𝑣𝑒
𝑎 𝜙0(𝑇!, 𝑇”, 𝑎)
𝑦𝑒𝑠 0𝑣𝑒 𝑣𝑒 0 𝑦𝑒𝑠 0𝑣𝑒 𝑣𝑒 0 𝑦𝑒𝑠 1𝑣𝑒 𝑣𝑒 1
𝜏/(𝑇!, 𝑣𝑒 𝑣𝑒 1
Computing MPE Instantiation: Example
§ Returning to our example
Let us run MPE VE on this example, but now computing the MPE instantiation with evidence 𝐴 = 𝑦𝑒𝑠
𝜏.(𝑇”, 𝑇!) 𝑇! 𝑇” .0209 𝑚𝑎𝑙𝑒, 𝑛𝑜 𝑣𝑒 𝑣𝑒
𝑣𝑒 𝑣𝑒 .0836 𝑚𝑎𝑙𝑒,𝑛𝑜 ×𝑣𝑒 𝑣𝑒
𝑣𝑒 𝑣𝑒 .0847 𝑓𝑒𝑚𝑎𝑙𝑒, 𝑛𝑜 𝑣𝑒 𝑣𝑒
𝑣𝑒 𝑣𝑒 .3390 𝑓𝑒𝑚𝑎𝑙𝑒, 𝑛𝑜 𝑣𝑒 𝑣𝑒
𝑇” 𝑇! 𝑣𝑒 𝑣𝑒
𝜏/(𝑇!, 𝑇”) 1
𝑇! 𝑇” 𝜎0(𝑇!, 𝑇” ) 𝑣𝑒 𝑣𝑒 .0209
𝑣𝑒 𝑣𝑒 𝑣𝑒 𝑣𝑒 𝑣𝑒 𝑣𝑒
𝑚𝑎𝑙𝑒, 𝑛𝑜 0 𝑓𝑒𝑚𝑎𝑙𝑒,𝑛𝑜
0 𝑚𝑎𝑙𝑒, 𝑛𝑜 .3390 𝑓𝑒𝑚𝑎𝑙𝑒, 𝑛𝑜
Computing MPE Instantiation: Example
§ Returning to our example
𝑣𝑒 .3390 𝑓𝑒𝑚𝑎𝑙𝑒,𝑛𝑜,𝑣𝑒
Let us run MPE VE on this example, but now computing the MPE instantiation with evidence 𝐴 = 𝑦𝑒𝑠
𝜎0(𝑇!, 𝑇” )
.0209 𝑚𝑎𝑙𝑒,𝑛𝑜
𝑓𝑒𝑚𝑎𝑙𝑒, 𝑛𝑜 𝑚𝑎𝑙𝑒,𝑛𝑜 𝑓𝑒𝑚𝑎𝑙𝑒, 𝑛𝑜
𝑚𝑎𝑙𝑒, 𝑛𝑜, 𝑣𝑒
Computing MPE Instantiation: Exampl
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com