Inference from Distributions

Definition:

• Calculating some useful quantity from a joint probability distribution
• We have a joint distribution of a joint distribution and wish to find $P(Q|e_1,e_2,...)$
• Evidence variables are variables in that help to query
  • this case: $e_i$
• Query variables are variables we wish to learn out
  • this case $Q$
• Hiddent variables are variables that are not in question
• $O(d^n)$ time complexity to find probability
• Ex:
  • Posterior probability: $P(Q|E_1=e_1,...,E_k=e_k)$, query with evidences
  • Most likely explaination: $\arg {\max }_{p}P(Q=q|E_1=e_1,...)$

Basic Inference:

• ex:
  • $P(B|+j,+m){\propto }_{B}P(B,+j,+m)={\sum }_{e,a}P(B,e,a,+j,+m)={\sum }_{e,a}P(B)P(e)P(a|B,e)P(+j|a)P(+m|a)$
  • $P(B|+j,+m)=P(B,+j,+m)/P(+j,+m)$, therefore proportional, but the denominator is easy to calculate so we ignore for now
• which is very long

Factors:

1. Joint Distribution factor
   • Joint distributions: entries sum to 1
     • varied $x$ and $y$
   • Selected Joint: only selected entries of joint distribution for some fixed value of some variables
     • assigned $x$, varied $Y$
     • nb of dimenionality of table is the number of varying variable
2. Conditional Distribution
   • Single conditional: entries $P(y|x)$, sums to 1
     • fixed $x$ and $y$
   • Family of conditionals: $P(Y|X)$: sums to domain of $X$
     • varied $x$ and $y$
     • has multiple conditionals
3. Specified Family: $P(y|X)$
   • fixed $y$ but for all $x$

Inference by Enumeration

• Procedure: Join all factors, eliminate all hidden variables, normalize
  • ex:
    • R (rain) → T (traffic) → L (late)
    • we have table for R, T|R and L|T
    • and we wish to query $P(L)$
  1. Join all factors: similar to JOIN clause
     • Build a new table from conditional table and independent
       • $P(R)\times P(T|R)=P(R,T)$ then $P(R,T)\times P(L|T)=P(R,T,L)$
  2. Eliminate all hidden variables:
     • Marginalize the joint table, ${\sum }_{R}P(R,T,L)=P(T,L)\to {\sum }_{T}P(T,L)=P(L)$
  3. Normalize to sum of 1
• ${\sum }_T{\sum }_{R}P(L|t)P(r)P(t|r)$, from right to left: joint r, joint t, eliminate r, eliminate t
• This way, it is join up the whole joint distribution before summing out the hidden variables, huge space complexity
• We can normalize early, which is Variable Elimination

Variable Elimination:

Procedure:

• Similar to inference by enumeration but we marginalize early to save space
• Join new variable from joint distribution, marginalize it and join new, marginalize,…
• With the same example:
  1. Join $P(R)\times P(T|R)=P(R,T)\to {\sum }_{R}P(R,T)=P(T)$
  2. Join $P(T)\times P(L|T)=P(T,L)\to {\sum }_{T}P(T,L)=P(L)$
• While there are still hidden variables, pick the hidden variable and join it and sum it out (eliminate)
• If there is evidence in the query, start with factors that join with the evidence first and only select the positive when joining
  • ex: query $P(L|+r):P(+r)\to P(+r)\times P(T|+r)=P(T,+r)\to P(T,+r)\times P(L|T)=P(L,T+r)$
  • $\to {\sum }_{T}P(L,T,+r)=P(L,+r)$
• If the final table is not $P(L|+r)$ but $P(L,+r)$, use Bayes’ theorem
  • $P(L,+r)\to P(+l|+r)=P(+l,+r)/P(+r)=P(+l,+r)/1$
• Normalize then we have the answer
  • ex: normalize between $L$ such ${\sum }_{L}P(L|+r)=1$

Variable Elimination Ordering:

• Ordering which variable to eliminate can reduce much of complicity
• ex:
  • With query $P(X_n|y_1,...,y_n)$, we join and marginalize right away
  • first way: top down, $Z\times X_1\times X_2\times ...\to Z.\prod X_i$ then times each $Y_i$ to sum out $X$
    • at $X_n$, we have all $X_i$ and $Z$, therefore, $2^{n+1}$
  • second way: bottom up, join all pairs $X_i\times Y_i$ first, then one by one join $Z$ to have $Y_n\times Z$
    • at $X_i\times Y_i$ steps, we only have $2^2$ entries, then times $Z$ and normalize to $2^2$
• Complexity is determined by the largest factor
• There is no order that always result to small factors