## Product Rule for Random Variables

We introduced inference in the context of random variables, where there was a simple way to visualize what was going on in terms of joint probability tables. Marginalization referred to summing out rows or columns. Conditioning referred to taking a slice of the table and renormalizing so entries within that slice summed to 1. We then saw a more general story in terms of events. In fact, we saw that for many inference problems, using random variables to solve the problem is not necessary – reasoning with events was enough! A powerful tool we saw was Bayes' theorem.

We now return to random variables and build up to Bayes' theorem for random variables. This machinery will be extremely important as it will be how we automate inference for much larger problems in the later sections of the course, where we can have a large number of random variables at play, and a large amount of observations that we need to incorporate into our inference.

## Product Rule for Random Variables

We know that product rule for event is 
$$\mathbb {P}(\mathcal{A} \cap \mathcal{B}) = \mathbb {P}(\mathcal{A}) \mathbb {P}(\mathcal{A} | \mathcal{B})$$
Similarly the product rule for random varaible will be given by follwing formula if $p_Y(y) \neq 0$.
$$\begin{align}
    p_{x|y}(x|y) &= \frac{p_{X,Y}(x,y)}{p_Y(y)} \\
                 &\Downarrow      \\
    p_{X,Y}(x,y) &= p_Y(y) \, p_{x|y}(x|y)
\end{align}$$

<!-- Note: $p_Y(y) = 0 \Rightarrow p_{x|y}(x|y)=0$ -->

In general the formula for joint probabiliy distribution is given by

$$  p_{X,Y}(x,y) = \begin{cases}
       p_Y(y) \, p_{x|y}(x|y) & \mbox{if } p_Y(y) > 0 \\
       0                      & \mbox{if } p_Y(y) = 0
       \end{cases}
$$       

### More than 2 random variable

Suppose we have have three random variable then we can think any two as one random variable, for example trat last two as one random variable we get 

$$\begin{align}p_{X_1, X_2, X_3}(x_1, x_2, x_3) 
&= p_{X_1}(x_1)p_{X_2, X_3|X_1}(x_2, x_3|x_1) \\ 
&= p_{X_1}(x_1)p_{X2|X_1}(x_2|x_1)p_{X_3|X_1,X_2}(x_3|x_1,x_2) 
\end{align}$$

We can genrealize the formula as follows,

$$\begin{align}p_{X_1, X_2,\ldots, X_N}(x_1, x_2,\ldots,x_N) 
&= p_{X_1}(x_1) p_{X_2,\ldots, X_N|X_1}(x_2,\ldots, x_N|x_1) \\
&= p_{X_1}(x_1) p_{X_2|X_1}(x_2|x_1) p_{X_3,\ldots,X_N|X_1, X_2}(x_3,\ldots,x_N|x_1,x_2) \\
&= p_{X_1}(x_1) p_{X_2|X_1}(x_2|x_1) \cdots p_{X_N|X_1, \ldots, X_{N-1}}(x_n|x_1,\ldots,x_{N-1})
\end{align}$$

### Exercise: The Product Rule for Random Variables - Medical Diagnosis Revisited

Let's revisit the medical diagnosis problem we saw earlier. We now use random variables to construct a joint probability table.

Let random variable $X$ represent the patient's condition — whether “healthy" or “infected", with the following distribution for $X$:



Meanwhile, the test outcome $Y$ for whether the patient is infected is either “positive" (for the disease) or “negative". As before, the test is $99\%$ accurate, which means that the conditional probability table for $Y$ given $X$ is as follows (note that we also show how to write things out as a single table):



Using the product rule for random variables, what are the four entries for the joint probability table? Please provide the exact answer for these four quantities.

$p_{X,Y}(\text {healthy}, \text {positive}) = p_X(\text {healthy})~p_{Y|X}(\text {positive}~|~\text {healthy})$  


```python
prior_or_p_X = {
    "healthy" : 0.999,
    "infected": 0.001
}

p_Y_given_X = {
    ('positive', 'healthy' ): 0.01,
    ('positive', 'infected'): 0.99,
    ('negative', 'healthy' ): 0.99,
    ('negative', 'infected'): 0.01
}

# p_X_Y stores the joint probability dist. of X and Y
p_X_Y = {} 
for key, values in p_Y_given_X.items():
    p_X_Y[key[::-1]] = values * prior_or_p_X[key[1]]
    
p_X_Y    
```




    {('healthy', 'negative'): 0.98901,
     ('healthy', 'positive'): 0.00999,
     ('infected', 'negative'): 1e-05,
     ('infected', 'positive'): 0.00099}




```python
print("{0:.5f}".format(p_X_Y[('healthy', 'positive')]))
```

    0.00999


$p_{X,Y}(\text {healthy}, \text {negative}) = $


```python
print("{0:.5f}".format(p_X_Y[('healthy', 'negative')]))
```

    0.98901


$p_{X,Y}(\text {infected}, \text {positive}) =$


```python
print("{0:.5f}".format(p_X_Y[('infected', 'positive')]))
```

    0.00099


$p_{X,Y}(\text {infected}, \text {negative}) =$


```python
print("{0:.5f}".format(p_X_Y[('infected', 'negative')]))
```

    0.00001


## Baye's Rule for Random Variable

In inference, what we want to reason about is some unknown random variable $X$, where we get to observe some other random variable $Y$, and we have some model for how $X$ and $Y$ relate. Specifically, suppose that we have some “prior" distribution $p_X$ for $X$; this prior distribution encodes what we believe to be likely or unlikely values that $X$ takes on, before we actually have any observations. We also suppose we have a “likelihood" distribution $p_{Y∣X}$.



After observing that $Y$ takes on a specific value $y$, our “belief" of what $X$ given $Y=y$ is now given by what's called the “posterior" distribution $p_{X∣Y}(⋅∣y)$. Put another way, we keep track of a probability distribution that tells us how plausible we think different values $X$ can take on are. When we observe data $Y$ that can help us reason about $X$, we proceed to either upweight or downweight how plausible we think different values $X$ can take on are, making sure that we end up with a probability distribution giving us our updated belief of what $X$ can be.

Thus, once we have observed $Y=y$, our belief of what $X$ is changes from the prior $p_X$ to the posterior $p_{X∣Y}(⋅∣y)$.

Bayes' theorem (also called Bayes' rule or Bayes' law) for random variables explicitly tells us how to compute the posterior distribution $p_{X∣Y}(⋅∣y)$, i.e., how to weight each possible value that random variable $X$ can take on, once we've observed $Y=y$. Bayes' theorem is the main workhorse of numerous inference algorithms and will show up many times throughout the course.

**Bayes' theorem:** Suppose that $y$ is a value that random variable $Y$ can take on, and $p_Y(y)>0$. Then

$$p_{X\mid Y}(x\mid y)=\frac{p_{X}(x)p_{Y\mid X}(y\mid x)}{\sum _{ x'}p_{X}( x')p_{Y\mid X}(y\mid x')}$$
 
for all values $x$ that random variable $X$ can take on.

!!!important 
    Remember that $p_{Y∣X}(⋅∣x)$ could be undefined but this isn't an issue since this happens precisely when     $p_X(x)=0$, and we know that $p_{X,Y}(x,y)=0$ (for every $y$) whenever $p_X(x)=0$.

    Proof: We have

    $$p_{X\mid Y}(x\mid y)\overset {(a)}{=}\frac{p_{X,Y}(x,y)}{p_{Y}(y)}\overset {(b)}{=}\frac{p_{X}(x)p_{Y\mid X}  (y\mid x)}{p_{Y}(y)}\overset {(c)}{=}\frac{p_{X}(x)p_{Y\mid X}(y\mid x)}{\sum _{ x'}p_{X,Y}( x',y)}\overset {(d)}  {=}\frac{p_{X}(x)p_{Y\mid X}(y\mid x)}{\sum _{ x'}p_{X}( x')p_{Y\mid X}(y\mid x')},$$

    where step (a) uses the definition of conditional probability (this step requires $p_Y(y)>0$, step (b) uses the  product rule (recall that for notational convenience we're not separately writing out the case when $p_X(x)=0$, step (c) uses the formula for marginalization, and step (d) uses the product rule (again, for notational convenience, we're not separately writing out the case when $p_X(x′)=0$. 

## BAYES' THEOREM FOR RANDOM VARIABLES: A COMPUTATIONAL VIEW

Computationally, Bayes' theorem can be thought of as a two-step procedure. Once we have observed $Y=y$:

1. For each value $x$ that random variable $X$ can take on, initially we believed that $X=x$ with a score of $p_X(x)$, which could be thought of as how plausible we thought ahead of time that $X=x$. However now that we have observed $Y=y$, we weight the score $p_X(x)$ by a factor $p_{Y∣X}(y∣x)$, so

    $$\text {new belief for how plausible }X=x\text { is:}\quad \alpha (x\mid y)\triangleq p_{X}(x)p_{Y\mid X}(y\mid x),$$

    where we have defined a new table $α(⋅∣y)$ which is not a probability table, since when we put in the weights, the new beliefs are no longer guaranteed to sum to $1$ (i.e., $\sum _{x}\alpha (x\mid y)$ might not equal $1$)! $α(⋅∣y)$ is an unnormalized posterior distribution!

    Also, if $p_X(x)$ is already $0$, then as we already mentioned a few times, $p_{Y∣X}(y∣x)$ is undefined, but this case isn't a problem: no weighting is needed since an impossible outcome stays impossible.

    To make things concrete, here is an example from the medical diagnosis problem where we observe $Y = \text {positive}$:

    

2. We fix the fact that the unnormalized posterior table $α(⋅∣y)$ isn't guaranteed to sum to $1$ by renormalizing:

    $$p_{X\mid Y}(x\mid y)=\frac{\alpha (x\mid y)}{\sum _{ x'}\alpha ( x'\mid y)}=\frac{p_{X}(x)p_{Y\mid X}(y\mid x)}{\sum _{ x'}p_{X}( x')p_{Y\mid X}(y\mid x')}.$$
 
!!! Note
    Some times we won't actually care about doing this second renormalization step because we will only be   interested in what value that $X$ takes on is more plausible relative to others; while we could always do the renormalization, if we just want to see which value of $x$ yields the highest entry in the unnormalized table $α(⋅∣y)$, we could find this value of x without renormalizing!

### MAXIMUM A POSTERIORI (MAP) ESTIMATION

For a hidden random variable $X$ that we are inferring, and given observation $Y=y$, we have been talking about computing the posterior distribution $p_{X∣Y}(⋅|y)$ using Bayes' rule. ``The posterior is a distribution for what we are inferring``. Often times, we want to report which particular value of $X$ actually achieves the highest posterior probability, i.e., the most probable value $x$ that $X$ can take on given that we have observed $Y=y$.

The value that $X$ can take on that maximizes the posterior distribution is called the maximum a posteriori (MAP) estimate of $X$ given $Y=y$. We denote the MAP estimate by $\widehat{x}_{\text {MAP}}(y)$, where we make it clear that it depends on what the observed $y$ is. Mathematically, we write

$$\widehat{x}_{\text {MAP}}(y) = \arg \max _ x p_{X \mid Y}(x | y).$$
 
Note that if we didn't include the “arg" before the “max", then we would just be finding the highest posterior probability rather than which value–or “argument"–x actually achieves the highest posterior probability.

In general, there could be ties, i.e., multiple values that $X$ can take on are able to achieve the best possible posterior probability.

### Exercise: Bayes' Theorem for Random Variables - Medical Diagnosis, Continued

Recall the medical diagnosis setup from before, summarized in these tables:




Recall that Bayes' theorem is given by

$$p_{X\mid Y}(x\mid y)=\frac{p_{X}(x)p_{Y\mid X}(y\mid x)}{\sum _{ x'}p_{X}( x')p_{Y\mid X}(y\mid x')}$$
 
for all values $x$ that random variable $X$ can take on.

Use Bayes' theorem to compute the following probabilities: (Please be precise with at least 3 decimal places, unless of course the answer doesn't need that many decimal places. You could also put a fraction.)


```python
prior_or_p_X = {
    "healthy" : 0.999,
    "infected": 0.001
}

p_Y_given_X = {
    ('positive', 'healthy' ): 0.01,
    ('positive', 'infected'): 0.99,
    ('negative', 'healthy' ): 0.99,
    ('negative', 'infected'): 0.01
}

# p_X_Y stores the joint probabilty distribution of X and Y
p_X_Y = {}
for key, values in p_Y_given_X.items():
    p_X_Y[key[::-1]] = values * prior_or_p_X[key[1]]


# p_Y stores the marginal probabilty distribution Y    
p_Y = {}
for key, values in p_X_Y.items():
    if key[1] in p_Y:
        p_Y[key[1]] += values
        
    else:
        p_Y[key[1]] = values

# p_X_given_Y stores the conditional probability dist. of X given Y.         
p_X_given_Y = {}
for key, values in p_X_Y.items():
    p_X_given_Y[key] = values / p_Y[key[1]]
      
p_X_given_Y      
```




    {('healthy', 'negative'): 0.9999898889810116,
     ('healthy', 'positive'): 0.9098360655737705,
     ('infected', 'negative'): 1.0111018988493663e-05,
     ('infected', 'positive'): 0.09016393442622951}



$p_{X\mid Y}(\text {healthy}\mid \text {positive}) = $  


```python
print("{0:.5f}".format(p_X_given_Y [('healthy', 'positive')]))
```

    0.90984


$p_{X\mid Y}(\text {healthy}\mid \text {negative}) =$


```python
print("{0:.5f}".format(p_X_given_Y [('healthy', 'negative')]))
```

    0.99999


What is the MAP estimate for $X$ given $Y = \text{positive}$?


```python
comp = 0
MAP = ""
for key, val in p_X_given_Y.items():
    if 'positive' in key and comp < val:
        comp = val
        MAP = key[0]
        
print(MAP)
```

    healthy


What is the MAP estimate for $X$ given $Y=\text{negative}$?


```python
comp = 0
MAP = ""
for key, val in p_X_given_Y.items():
    if 'negative' in key and comp < val:
        comp = val
        MAP = key[0]
 
print(MAP) 
```

    healthy


### Exercise: Complexity of Computing Bayes' Theorem for Random Variables

This exercise is extremely important and gets at how expensive it is to compute a posterior distribution when we have many quantities we want to infer.

Consider when we have $N$ random variables $X_1, \dots , X_ N$ with joint probability distribution $p_{X_1, \dots , X_ N}$, and where we have an observation $Y$ related to $X_1, \dots , X_ N$ through the known conditional probability table $p_{Y\mid X_1, \dots , X_ N}$. Treating $X=(X_1, \dots , X_ N)$ as one big random variable, we can apply Bayes' theorem to get

$$\begin{eqnarray}
&& p_{X_1, X_2, \dots, X_N \mid Y}(x_1, x_2, \dots, x_N \mid y) \\
&&
= \frac{p_{X_1, X_2, \dots, X_N}(x_1, x_2, \dots, x_N)
        p_{Y\mid X_1, X_2, \dots, X_N}(y\mid x_1, x_2, \dots, x_N)}
       {\sum_{x_1'}
        \sum_{x_2'}
        \cdots
        \sum_{x_N'}
          p_{X}(x_1',
                x_2',
                \dots,
                x_N')
          p_{Y\mid X_1, X_2, \dots, X_N}(y\mid x_1',
                x_2',
                \dots,
                x_N')}.
\end{eqnarray}$$

Suppose each $X_i$ takes on one of $k$ values. In the denominator, how many terms are we summing together? Express your answer in terms of $k$ and $N$.

In this part, please provide your answer as a mathematical formula (and not as Python code). Use "$\hat{}$" for exponentiation, e.g., $x\hat{}2$ to denotes $x^2$. Explicitly include multiplication using $*$, e.g. $x*y$ is $xy$.

**Answer:** Here we have $k$ choices of $X_1$ and $k$ choices of $X_2$ and so on. Hence total number of terms will be $k^N$.


```python

```

3df24bcafcf937bbce8a5cf18fc4cb1a29102f2a
ipynb
Jupyter Notebook
week03/01 Product Rule for Random Variables.ipynb
infimath/Computational-Probability-and-Inference
e48cd52c45ffd9458383ba0f77468d31f781dc77
MIT
2019-04-04T03:07:47.000Z
2019-04-04T03:07:47.000Z
week03/01 Product Rule for Random Variables.ipynb
infimath/Computational-Probability-and-Inference
e48cd52c45ffd9458383ba0f77468d31f781dc77
MIT
week03/01 Product Rule for Random Variables.ipynb
infimath/Computational-Probability-and-Inference
e48cd52c45ffd9458383ba0f77468d31f781dc77
MIT
2021-02-27T05:33:49.000Z
2021-02-27T05:33:49.000Z
Qwen/Qwen-72B
1. YES
2. YES