Part I: EM and Shift-Invariant Models

 

Problem 1 (1 pt)

Give the expression for P(X,Y) in terms of P(Z), P(X,Y|Z), P(X|Z), and P(Y|Z).

Solution:

This is simple. To avoid confusion, we will introduce the following notation: $P_X(X)$ will generally represent the probability that the random variable $X$ will take the value $X$. Thus, $P_{X_1}(X)$ is the probability that $X_1$ takes the value $X$.

Any $X,Y$ pair can be generated from any given urn in many ways: $X_1$ can take a range of values, provided $X_2$ takes the value $X-X_1$. Similarly $Y_1$ can take a range of values provided $Y_2$ takes the value $Y - Y_1$. Thus, the probabiliyty of generating a given $X,Y$ from any given urn $Z$ is given by \[ P_{X,Y}(X,Y | Z) = \sum_{X_1, Y_1} P_{X_1,Y_1}(X_1,Y_1|Z) P_{X_2}(X-X_1 | Z) P_{Y_2}(Y-Y_1|Z) \]

In any draw any of the urn could be selected. Thus the overall probability of generating a specific $X,Y$ is given by: \[ P_{X,Y}(X,Y) = \sum_Z P(Z) \sum_{X_1, Y_1} P_{X_1,Y_1}(X_1,Y_1|Z) P_{X_2}(X-X_1 | Z) P_{Y_2}(Y-Y_1|Z) \]

Problem 2

You are given a histogram of counts H(X,Y) obtained from a large number of observations. H(X,Y) represents the number of times (X,Y) was observed. Give the EM update rules to estimate P(Z), P(X,Y|Z), P(X|Z), and P(Y|Z).

Solution:

We will use the following notation: $P_X(x)$ will be used to refer to the probability that the random variable $X$ takes the value $x$.

In short, the solution is as follows. In the E step we will compute the following posteriors: \[ \begin{align} P_{X_1, Y_1, Z}(X_1, Y_1, Z | X, Y) &= \frac{P_{X_1, Y_1, X, Y, Z}(X_1, Y_1, X, Y, Z)}{P_{X,Y}(X,Y)} \\ &= \frac{P_{X_1, Y_1, X_1, Y_1, Z}(X_1, Y_1, X-X_1, Y-Y_1, Z)}{P_{X,Y}(X,Y)} \\ &= \frac{P_Z(Z)P_{X_1,Y_1}(X_1, Y_1 | Z) P_{X_2}(X-X_1 | Z) P_{Y_2}(Y-Y_1|Z)}{P_{X,Y}(X,Y)} \end{align} \]

and \[ \begin{align} P_Z(Z|X,Y) &= \sum_{X_1,Y_1} P_{X_1, Y_1, Z}(X_1, Y_1, Z | X, Y) \\ P_{X_2,Z}(X_2, Z|X,Y) &= \sum_{Y_1} P_{X_1, Y_1, Z}(X-X_2, Y_1, Z | X, Y) \\ P_{Y_2,Z}(Y_2, Z|X,Y) &= \sum_{X_1} P_{X_1, Y_1, Z}(X_1, Y-Y_1, Z | X, Y) \end{align} \]

Then in the M step we will compute updated formulae. We can define the following expected counts: \[ \begin{align} N &= \sum_{X,Y} H(X,Y) \\ N(Z) &= \sum_{X,Y} H(X,Y) P_Z(Z|X,Y) \\ N(X_1,Y_1,Z) &= \sum_{X,Y} H(X,Y) P_{X_1, Y_1, Z}(X_1, Y_1, Z | X, Y)\\ N(X_2,Z) &= \sum_{X,Y} H(X,Y) P_{X_2, Z}(X_2, Z | X, Y)\\ N(Y_2,Z) &= \sum_{X,Y} H(X,Y) P_{Y_2, Z}(Y_2, Z | X, Y) \end{align} \]

This leads us to the following updated estimates: \[ \begin{align} P_Z(Z) &= \frac{N(Z)}{N} \\ P_{X_1,Y_1}(X_1, Y_1 |Z) &= \frac{N(X_1, Y_1, Z)}{N(Z)} \\ P_{X_2}(X_2 |Z) &= \frac{N(X_2, Z)}{N(Z)} \\ P_{Y_2}(Y_2 |Z) &= \frac{N(Y_2, Z)}{N(Z)} \end{align} \]

The solution can actually be expessed in many alternate forms, all of which are equivalent. For instance, one may write $P_{X_2, Z}(X_2, Z | X, Y)$ and $P_{Y_2, Z}(Y_2, Z | X, Y)$ as follows: \[ \begin{align} P_{X_2, Z}(X_2, Z | X, Y) &= \frac{P_Z(Z)\sum_{Y_1} P_{X_1,Y_1}(X-X_2, Y_1 | Z) P_{X_2}(X_2 | Z) P_{Y_2}(Y-Y_1|Z)}{P_{X,Y}(X,Y)} \\ P_{Y_2, Z}(Y_2, Z | X, Y) &= \frac{P_Z(Z)\sum_{X_1} P_{X_1,Y_1}(X_1, Y-Y_2,| Z) P_{X_2}(X-X_1 | Z) P_{Y_2}(Y_2|Z)}{P_{X,Y}(X,Y)} \end{align} \]

Other variants are also possible

Problem part 3 (3 pts)

[This picture] :

 

Solution:

You solution should pull out the four space invader types as your individual $P_{X_1,Y_1}(X,Y|Z)$ distributions (i.e. if you view the distributions from above they should look approximately like the space invaders). The solution will not be perfect -- the actual results will vary depending on initialization, and you may end up with $P_{X_1,Y_1}(X,Y|Z)$ terms that look like mixtures of the invaders. That is OK, provided the four images you get are all different.