This shows you the differences between two versions of the page.

Both sides previous revision Previous revision Next revision | Previous revision | ||

cs-401r:assignment-2 [2014/09/18 04:30] ringger [Exercises] |
cs-401r:assignment-2 [2014/09/24 21:22] (current) cs401rPML Updated labeling of sub-problems and/or problem options. |
||
---|---|---|---|

Line 12: | Line 12: | ||

Show your work. Be clear and concise. '''This assignment must be typed.''' | Show your work. Be clear and concise. '''This assignment must be typed.''' | ||

- | # [10 points] Prove that the relationship we call ''conditional independence'' is symmetric. In other words, Prove either (a) or (b) (since they are equivalent), and apply the same [[Proofs|standard of proof]] as in assignment 1: | + | # [10 points] Prove that the relationship we call ''conditional independence'' is symmetric. In other words, Prove either (option a) or (option b) (since they are equivalent), and apply the same [[Proofs|standard of proof]] as in assignment 1: |

- | #* (a) $P(X | Y, Z) = P(X | Z)$ if and only if $P(Y | X, Z) = P(Y | Z)$ | + | #* (option a) $P(X | Y, Z) = P(X | Z)$ if and only if $P(Y | X, Z) = P(Y | Z)$ |

- | #* (b) $P(X, Y | Z) = P(X | Z) \cdot P(Y|Z)$ if and only if $P(Y, X | Z) = P(Y | Z) \cdot P(X | Z)$ | + | #* (option b) $P(X, Y | Z) = P(X | Z) \cdot P(Y|Z)$ if and only if $P(Y, X | Z) = P(Y | Z) \cdot P(X | Z)$ |

#** (in other words, the "given $Z$" stays the same, while $X$ and $Y$ trade places). | #** (in other words, the "given $Z$" stays the same, while $X$ and $Y$ trade places). | ||

# [20 points: 10 points each] (based on exercise 2.2 in Koller and Friedman) Independence: | # [20 points: 10 points each] (based on exercise 2.2 in Koller and Friedman) Independence: | ||

- | #* Prove that for binary random variables $X$ and $Y$, the event-level independence $(x^0 \bot y^0)$ implies random-variable independence $(X \bot Y)$. Use the usual standard of proof. | + | #* (2.1) Prove that for binary random variables $X$ and $Y$, the event-level independence $(x^0 \bot y^0)$ implies random-variable independence $(X \bot Y)$. Use the usual standard of proof. |

- | #* Give a counterexample for nonbinary variables. | + | #* (2.2) Give a counterexample for nonbinary variables. |

# [20 points] Consider how to sample from a categorical distribution over four colors. Think of a spinner with four regions having probabilities $p_{red}$, $p_{green}$, $p_{yellow}$, and $p_{blue}$. Write pseudo-code for choosing a sample from this distribution. | # [20 points] Consider how to sample from a categorical distribution over four colors. Think of a spinner with four regions having probabilities $p_{red}$, $p_{green}$, $p_{yellow}$, and $p_{blue}$. Write pseudo-code for choosing a sample from this distribution. | ||

+ | #* You may assume that you have access to a function that samples a uniform random variable with support [0,1]. | ||

# [10 points] Does your pseudo-code scale to run efficiently on a distribution over ten thousand values? If not, rewrite it. If so, say why. | # [10 points] Does your pseudo-code scale to run efficiently on a distribution over ten thousand values? If not, rewrite it. If so, say why. | ||

# [20 points] Implement your pseudo-code, choose values for the four probabilities on the spinner as parameters to your procedure, and run it 100 times, keeping track of how many times each color shows up. Give the results as a vector of counts over the four colors. | # [20 points] Implement your pseudo-code, choose values for the four probabilities on the spinner as parameters to your procedure, and run it 100 times, keeping track of how many times each color shows up. Give the results as a vector of counts over the four colors. |